The Tilted Sampling Problem: Optimism, Posterior Sampling, and Logarithmic Regret
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 Õ(√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 TS2) 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.
Related
- Accelerating posterior sampling in Bayesian inverse problems with diffusion models: an online-offline perspective
- Learning to Replace MCMC in Split-Gibbs Diffusion Posterior Sampling via Deep Unfolding
- Flow Annealing Posterior Sampling for Function-Space Regression and Inverse Problems
- Minimax-Optimality of Posterior Sampling for Reinforcement Learning
- Efficient Posterior Sampling for ℤ2 Synchronization
BibTeX
@misc{pedramfar2026tilted,
title = {{The Tilted Sampling Problem: Optimism, Posterior Sampling, and Logarithmic Regret}},
author = {Mohammad Pedramfar and Siamak Ravanbakhsh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21908},
eprint = {2610.21908},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21908},
}
RIS
TY - UNPB
TI - The Tilted Sampling Problem: Optimism, Posterior Sampling, and Logarithmic Regret
AU - Mohammad Pedramfar
AU - Siamak Ravanbakhsh
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.21908
UR - https://arxiv.org/abs/2610.21908
AB - 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 Õ(√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.
ER -