The Tilted Sampling Problem: Optimism, Posterior Sampling, and Logarithmic Regret

Mohammad Pedramfar; Siamak Ravanbakhsh

cs.LGOct 15, 2026

The Tilted Sampling Problem: Optimism, Posterior Sampling, and Logarithmic Regret

Authors: Mohammad Pedramfar, Siamak Ravanbakhsh

Organizations: Mila – Québec AI Institute, McGill University

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.

Figures & tables

Panel of Figure 1 — Figure 1: Schematic sampling-regret upper bound $R(T,\beta)=\min\!\bigl\{\sqrt{T\log T},\ \beta\log T\bigr\}$ illustrating the complementary linear- and squared-width bounds for UCS and TS 2 in Theorems 3 and 4 . ( 1(a) ) For fixed $\beta$ and $T>1$ , the square-root branch is active when $T/\log T\leq\beta^{2}$ , and the logarithmic branch when $T/\log T\geq\beta^{2}$ . The large-horizon crossover satisfies $T^{\star}(\beta)=\beta^{2}\log T^{\star}(\beta)$ , with $T^{\star}(\beta)\sim 2\beta^{2}\log\beta$ as $\beta\to\infty$ ; beyond it the bound follows $\beta\log T$ . ( 1(b) ) For each $T$ the bound is linear in $\beta$ up to the kink $\beta^{\star}(T)=\sqrt{T/\log T}$ and saturates at $\sqrt{T\log T}$ beyond it.

Bandit Optimization	Tilted Sampling
$\max f(a)$	$\pi\propto\exp(\beta f)$
Non-smooth	Smooth (KL)
First-order	Second-order
$\sum w_{t}\to\sqrt{T}$	$\sum w_{t}^{2}\to\log T$
UCB / TS	UCS / TS 2

Table 1: Optimization vs. sampling. KL geometry smooths the objective, converting first-order uncertainty into second-order regret.

Problem	$\gamma_{T}$	$d_{E}$	$(1+\gamma_{T})d_{E}$	Prior special case
$K$ -armed bandit	$\widetilde{O}(\log K)$	$\widetilde{O}(K)$	$\widetilde{O}(K\log K)$	SWC–RKL/FKL [ 39 ]
Finite class $\mathcal{F}$	$\widetilde{O}(\log\|\mathcal{F}\|)$	$d_{E}$	$\widetilde{O}(d_{E}\log\|\mathcal{F}\|)$	UCS–RKL [ 66 ] Greedy–RKL–pref. [ 58 ]
Linear bandit ( $d$ -dim.)	$\widetilde{O}(d)$	$\widetilde{O}(d)$	$\widetilde{O}(d^{2})$	—
Sparse linear ( $s$ -sparse)	$\widetilde{O}(s\log d)$	$\widetilde{O}(d)$	$\widetilde{O}(sd\log d)$	—
GLM ( $d$ -dim.)	$\widetilde{O}(d)$	$\widetilde{O}(d)$	$\widetilde{O}(d^{2})$	—

Table 2: Complexity instantiations for Theorem 5 . Here

d_{E}=\operatorname{EC}^{\operatorname{sq}}(1,\mathcal{F},T)

, and rates suppress logarithmic factors in

T

and problem-dependent constants. Substituting the fourth column into Theorem 5 gives two-sided UCS, TS 2 , and SWC regret bounds. The final column records the limited prior special cases: Pedramfar and Ravanbakhsh, [39] treat finite-armed SWC for both KL directions, with bounded noise assumed for forward KL; Zhao et al., 2025b [66] establish the finite-class result only for UCS and reverse KL; and Wu et al., [58] analyze greedy sampling under preference feedback, with reverse-KL-equivalent regret in the Bradley–Terry specialization. Our SWC result instead uses direct reward feedback. For finite

\mathcal{F}

, cardinality controls

\gamma_{T}

, while

d_{E}

remains a separate, model-dependent exploration complexity. The sparse-linear row uses the generic ambient-dimensional bound on

d_{E}

; sharper rates require additional structure. The generalized-linear row assumes the usual quantitative regularity conditions on the link function.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

	Bandit Optimization	Tilted Sampling
Target	$\arg\max_{a\in\mathcal{A}_{t}}f_{\theta}(a)$	$S_{\beta,t}(f_{\theta})\propto\exp(\beta f_{\theta})\,\mu_{t}$
Learner’s choice	action $A_{t}\in\mathcal{A}_{t}$	distribution $A_{t}\sim S_{\beta,t}(g_{t})$
Performance metric	$f_{\theta}(A_{t}^{\star})-f_{\theta}(A_{t})$	$\tfrac{1}{\beta}D_{\mathrm{KL}}(S_{\beta,t}(g_{t})\,\\|\,S_{\beta,t}(f_{\theta}))$
Geometry	non-smooth (hard $\arg\max$ )	smooth (KL / Fisher)
Uncertainty order	first-order $w_{\mathcal{F}_{t}}(A_{t})$	second-order $w_{\mathcal{F}_{t}}(A_{t})^{2}$
Width process	$\sum_{t=1}^{T}w_{\mathcal{F}_{t}}(A_{t})$	$\sum_{t=1}^{T}w_{\mathcal{F}_{t}}(A_{t})^{2}$

Appendix

Table 3: Optimization vs. sampling. KL geometry smooths the objective, converting first-order uncertainty in classical bandit optimization into second-order regret in tilted sampling. The Gibbs operator

S_{\beta,t}

interpolates between the two regimes: as

\beta\to\infty

the sampling targets concentrate on maximizers and tilted sampling recovers bandit optimization under the regularity conditions discussed in Appendix C .

Posterior Sampling

Posterior sampling generates draws from Bayesian posteriors to quantify uncertainty and support inference, prediction, and decision-making.

See all 69 papers

Sep 11, 2026

When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence

We study KL-regularized contextual bandits under both reward and preference feedback. While existing regret guarantees typically depend on the eluder dimension, we show that simple greedy sampling can achieve polylogarithmic regret without explicit dependence on this complexity measure. For reward feedback, we analyze a greedy algorithm that samples directly from the Gibbs policy induced by the estimated reward. We extend the result to preference feedback under both general preference and Bradley--Terry models, while also sharpening existing dimension-dependent guarantees. Our analysis reveals a trade-off between greedy sampling and upper confidence bound-style exploration: greedy sampling enjoys stronger regret guarantees when KL regularization is sufficiently strong, whereas additional exploration yields sharper bounds as the regularization weakens.

Zichen Wang, Haoyang Hong, Huazheng Wang

Department of ECE and CSL, University of Illinois Urbana-Champaign · School of Electrical Engineering and Computer Science, Oregon State University

Contextual Bandits

Ask PDF

Sep 27, 2026

Minimax-Optimality of Posterior Sampling for Reinforcement Learning

Posterior sampling for reinforcement learning (PSRL) is one of the simplest and most effective exploration methods, but a basic question has remained open: does unmodified PSRL achieve minimax regret without structural assumptions on the prior? We answer yes. Exact vanilla PSRL is minimax optimal in leading-order Bayesian regret under arbitrary correlated priors. The difficulty is that a posterior-sampled transition model is coupled with its own continuation value. We overcome this with a common empirical transition reference that isolates the resulting value mismatch and a Bellman-based variance argument that controls it without an extra leading-order state-space factor. For finite-horizon, time-inhomogeneous tabular MDPs with unknown stochastic rewards, this yields the minimax

\widetilde{O}(\sqrt{SAH^3K})

regret rate under arbitrary joint priors over rewards and transitions. The same proof principle gives the minimax

\widetilde{O}(d\sqrt{H^3K})

rate for linear-mixture MDPs under arbitrary joint parameter priors.

Taewon Goo, Kihyuk Hong

KAIST

Regret Minimization in RL Markov Decision Processes Bayesian RL Posterior Sampling

Ask PDF

Jan 5, 2026

Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

We prove that Thompson sampling exhibits

\tilde{O}(σd \sqrt{T} + d r \sqrt{\mathrm{Tr}(Σ_0)})

Bayesian regret in the linear-Gaussian bandit with a

\mathcal{N}(μ_0, Σ_0)

prior distribution on the coefficients, where

d

is the dimension,

T

is the time horizon,

r

is the maximum

\ell_2

norm of the actions, and

σ^2

is the noise variance. In contrast to existing regret bounds, this shows that to within logarithmic factors, the prior-dependent

burn-in'' term $d r \sqrt{\mathrm{Tr}(Σ_0)}$ decouples additively from the minimax (long run) regret $σd \sqrt{T}$. Previous regret bounds exhibit a multiplicative dependence on these terms. We establish these results via a new

elliptical potential'' lemma, and also provide a lower bound indicating that the burn-in term is unavoidable.

Yifan Zhu, John C. Duchi, Benjamin Van Roy

Department of Electrical Engineering, Stanford University, California, United States.

Thompson Sampling Multi-Armed Bandits Regret Minimization

Ask PDF

Abstract

Posterior Sampling

Explore similar work

When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence

Minimax-Optimality of Posterior Sampling for Reinforcement Learning

Prior Diffusiveness and Regret in the Linear-Gaussian Bandit