analiza aiqbench
This arXiv paper gives a theoretical framework for online learning where the goal is to sample from a reward-tilted (Gibbs) distribution rather than find a single best action. Its main claim is that this sampling regret scales logarithmically in T at fixed temperature, unlike the square-root scaling of classical regret, and that the authors propose UCB- and Thompson-style algorithms for it. For readers working on RLHF or entropy-regularized RL, the useful takeaway is that sampling diverse, soft-optimal outputs may be statistically easier than identifying a hard optimum, though these are theoretical bounds that still need empirical validation.
The Tilted Sampling Problem: Optimism, Posterior Sampling, and Logarithmic Regret
arXiv:2610.21908v1 Announce Type: new Abstract: Many modern learning systems are used not to select a single best action, but to sample diverse high-quality outputs. Examples include entropy-regularized reinforcement learning, RLHF, and reward-guided generative modeling. Motivated by these settings, we study tilted sampling: an online learning problem in which the goal is to sample from the Gibbs distribution induced by an unknown reward function. We define sampling regret as the temperature-normalized cumulative KL divergence between the learner's distribution and the Gibbs target, corresponding to the suboptimality gap in entropy-regularized reward maximization. Our framework generalizes recent sampling-based and KL-regularized formulations in bandits and reinforcement learning. Our main contribution is a general regret framework that captures the different uncertainty structure of tilted sampling and classical regret minimization. While standard regret scales as $\widetilde{O}(\sqrt{T})$ due to first-order uncertainty, sampling regret is governed by squared confidence widths, yielding logarithmic-in-$T$ regret in standard settings at fixed temperature. We develop sampling analogues of UCB and Thompson sampling (UCS and TS$^2$) and provide unified regret decompositions that explain and extend recent logarithmic guarantees, including the first Bayesian sampling-regret decomposition based on new bounds for posterior-random Gibbs distributions. Our results show that learning to sample from a soft-optimal distribution is statistically distinct from learning to identify a hard optimum.
Abstract:Many modern learning systems are used not to select a single best action, but to sample diverse high-quality outputs. Examples include entropy-regularized reinforcement learning, RLHF, and reward-guided generative modeling. Motivated by these settings, we study tilted sampling: an online learning problem in which the goal is to sample from the Gibbs distribution induced by an unknown reward function. We define sampling regret as the temperature-normalized cumulative KL divergence between the learner's distribution and the Gibbs target, corresponding to the suboptimality gap in entropy-regularized reward maximization. Our framework generalizes recent sampling-based and KL-regularized formulations in bandits and reinforcement learning. Our main contribution is a general regret framework that captures the different uncertainty structure of tilted sampling and classical regret minimization. While standard regret scales as $\widetilde{O}(\sqrt{T})$ due to first-order uncertainty, sampling regret is governed by squared confidence widths, yielding logarithmic-in-$T$ regret in standard settings at fixed temperature. We develop sampling analogues of UCB and Thompson sampling (UCS and TS$^2$) and provide unified regret decompositions that explain and extend recent logarithmic guarantees, including the first Bayesian sampling-regret decomposition based on new bounds for posterior-random Gibbs distributions. Our results show that learning to sample from a soft-optimal distribution is statistically distinct from learning to identify a hard optimum.
Machine Learning (cs.LG); Optimization and Control (math.OC); Machine Learning (stat.ML)
arXiv:2610.21908 [cs.LG]
(or arXiv:2610.21908v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.21908 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 306 cuvinte
Subiecte conexe
Regret Analysis of Retry-Based Bandits
arXiv · 1 oct. 2026
Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling
arXiv · 3 sept. 2026
Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization
arXiv · 15 oct. 2026
Convergence-Rate-Guided Algorithm Design of Expected Improvement for Continuous Simulation Optimization
arXiv · 14 oct. 2026