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

When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependence
Sep 11, 2026Zichen Wang, Haoyang Hong, Huazheng WangContextual Bandits
Department of ECE and CSL, University of Illinois Urbana-Champaign · School of Electrical Engineering and Computer Science, Oregon State University
Minimax-Optimality of Posterior Sampling for Reinforcement Learning
Sep 27, 2026Taewon Goo, Kihyuk HongRegret Minimization in RL Markov Decision Processes
KAIST
Prior Diffusiveness and Regret in the Linear-Gaussian Bandit
Jan 5, 2026Yifan Zhu, John C. Duchi, Benjamin Van RoyThompson Sampling Multi-Armed Bandits
Department of Electrical Engineering, Stanford University, California, United States.

Sep 11, 2026J/K move · Enter open · S save

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

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

Open paper AskPDF arXiv

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.

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