PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Mohammad Pedramfar, Siamak Ravanbakhsh

arXiv:2610.21908v1cs.LGmath.OCstat.ML

TL;DR

Many learning systems produce diverse outputs by sampling, so the goal can be to learn a high-reward distribution rather than identify one best action. This paper develops a framework and sampling algorithms for learning the Gibbs distribution of an unknown reward, with logarithmic-in-T sampling regret in standard settings at fixed temperature.

  • Problem

    Many systems produce outputs by sampling, but classical bandit and reinforcement-learning formulations instead target repeated selection of a single maximizing action.

    Source: §1 · p. 1

  • Method

    The paper formulates tilted sampling as learning the unknown reward’s Gibbs distribution and develops confidence-based and Thompson-style sampling methods.

    Source: §1 · p. 2, §3.4 · p. 5, §3.5 · p. 6

  • Results

    Sampling regret can be logarithmic in T at fixed temperature because it is controlled by squared confidence widths rather than first-order uncertainty.

    Source: Sampling regret · p. 2

  • Takeaways & Limitations

    Learning to sample from a soft-optimal distribution has a different uncertainty structure from learning to identify a hard optimum.

    Source: Sampling regret · p. 2

    The analysis assumes bounded rewards, direct noisy reward feedback, and exact Gibbs sampling; approximate-sampling error and computational cost remain future-work directions.

    Source: §5 · p. 8

Abstract

from arXiv · show

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.

1 INTRODUCTION

Many learning systems need high-reward distributions rather than a single maximizing action; this paper studies learning to sample from the Gibbs distribution induced by an unknown reward. It develops a general framework and sampling algorithms whose regret reflects squared confidence widths and can be logarithmic in time at fixed temperature.

Sampling regret.

  • Learning to sample is statistically distinct from learning to optimize: squared confidence widths can yield logarithmic-in-T sampling regret at fixed temperature.Classical regret instead reflects first-order uncertainty and scales as eO(√T) in standard models.Source: Sampling regret · p. 2
  • The paper generalizes finite-armed sampling to general action spaces, time-varying action sets, function classes, and Bayesian learning.It also gives a black-box transfer of confidence-set and width-process analyses to UCS and TS2 under direct noisy reward feedback.Source: Sampling regret · p. 2
  • The framework introduces SWC, UCS, and TS2 as sampling counterparts to confidence-based and Thompson-style methods.The Gibbs operator gives smooth generalizations of UCB and Thompson sampling, interpolating between sampling and maximization.Source: Sampling regret · p. 2
  • Unified confidence-width decompositions for SWC and UCS simplify and extend prior logarithmic-regret analyses of optimistic and greedy sampling methods.The analyses provide model-independent confidence-width bounds.Source: Sampling regret · p. 2
  • The paper introduces a Bayesian sampling-regret decomposition for TS2 using new KL-divergence bounds for posterior-sampled Gibbs distributions.This extends the analysis beyond frequentist algorithms to posterior sampling.Source: Sampling regret · p. 2
  • UCS and TS2 simultaneously control forward and reverse KL regret with identical bounds under the same confidence event and without exponential dependence on βC.Source: Sampling regret · p. 2

2 PROBLEM SETUP AND REGRET DECOMPOSITION

The setup models T-round learning with unknown bounded rewards and potentially changing available-action sets. Confidence sets support optimistic and posterior-randomized algorithms, whose regret analysis uses uncertainty widths along the realized actions.

2 PROBLEM SETUP AND REGRET DECOMPOSITION

  • Each round, the learner observes an available action set, chooses an action, and receives a noisy reward from an unknown bounded function; the Bayesian setting places a prior on its parameter.The reward function takes values in [0, C].Source: §2 · p. 3

Confidence sets.

  • Confidence sets collect functions plausible given revealed information, and their upper and lower bounds define action-specific widths over the realized action set.The width quantifies uncertainty about an action's reward, and cumulative widths along the trajectory are central to the regret analysis.Source: Confidence sets · p. 3

Algorithms.

  • UCB selects optimistically using upper confidence bounds, while TS samples a model from the posterior; both admit regret analysis through confidence widths along realized actions.The algorithms are operationally different, but the analysis uses a common confidence-width lens.Source: Algorithms · p. 3

3 TILTED SAMPLING

Tilted sampling learns the Gibbs distribution induced by an unknown reward, rather than identifying a single best action. Its KL-based regret connects distribution matching to entropy-regularized value, while confidence-width decompositions support sampling algorithms and logarithmic-in-T guarantees under suitable conditions.

3 TILTED SAMPLING

  • When confidence widths accumulate logarithmically, squared-width regret bounds yield logarithmic-in-T sampling regret at fixed temperature.The bounds have complementary linear- and squared-width forms; their crossover depends on statistical complexity and reward normalization.Source: §3 · p. 3, §3.5 · p. 6

3.1 Sampling Objective

  • The Gibbs target is defined on the currently available action set, and the learner chooses a reward function before sampling from its induced distribution.The action set may vary over time, and the learner controls a full distribution rather than selecting only one action.Source: §3.1 · p. 4, §3.2 · p. 4

3.3 Sampling Regret

  • Sampling regret measures the learner’s distributional mismatch from the target; it is also the suboptimality gap in KL-regularized reward maximization.The factor 1/β gives the gap reward-regret units and links distribution matching to the zero-temperature optimization limit.Source: §3.3 · p. 4

Bandit optimization as a limit of tilted sampling.

  • As β increases, the Gibbs operator concentrates on reward maximizers, so UCS and TS2 recover UCB and Thompson sampling in the zero-temperature limit.Total-variation regret does not share reverse KL’s entropy-regularized value interpretation or its classical-regret limit; forward KL instead penalizes failure to cover target-mass regions.Source: Bandit optimization as a limit of… · pp. 4–5

3.4 Algorithms

  • UCS uses an upper confidence reward function, while TS2 uses a posterior-sampled reward function; both are smooth generalizations of classical UCB and Thompson sampling.Sampling With Confidence (SWC) controls reward-estimate uncertainty through confidence widths without requiring the chosen estimate to belong to the confidence set.Source: §3.4 · p. 5

3.5 Sampling Regret Decomposition

  • Global Gibbs inequalities and confidence bounds convert reward-function uncertainty into linear- and squared-width regret decompositions.The squared-width structure arises from prediction error weighted by the learner’s sampling distribution, giving little weight to rarely sampled regions.Source: §3.5 · pp. 5–6
  • Posterior exchangeability gives TS2 matching reverse- and forward-KL bounds, while UCS obtains both directions through pointwise optimism.For TS2, swapping the true parameter and posterior draw equates expected directed-KL terms; its bounds also hold for expected Bayesian forward-KL regret.Source: §3.5 · p. 6
  • Generic SWC has sublinear KL bounds only when β exp(βC)W2(T) = o(T), with sublinear confidence-failure terms; no temperature-independent sublinear guarantee holds uniformly over SWC.UCS removes the exponential factor from the squared-width bound and also provides a temperature-independent linear-width bound.Source: §3.5 · p. 6

4 A BLACK-BOX TRANSFER OF CONFIDENCE-WIDTH ANALYSES TO SAMPLING REGRET

The section transfers confidence-width analyses from bandit optimization to tilted-sampling regret by separating a Gibbs/KL decomposition from bounds on accumulated uncertainty. Least-squares confidence sets and squared Eluder complexity provide model-specific inputs for regret guarantees.

4 A BLACK-BOX TRANSFER OF CONFIDENCE-WIDTH ANALYSES TO SAMPLING REGRET

  • The transfer framework combines a Gibbs/KL decomposition with confidence-width bounds, yielding temperature-independent guarantees from linear widths and temperature-dependent guarantees from squared widths.Its statistical inputs can come from confidence-set and Eluder-dimension arguments or other model-specific constructions.Source: §4 · pp. 6–7

4.1 Confidence Sets

  • Least-squares confidence sets use an increasing radius sequence chosen to contain the true reward function uniformly over time with high probability.For standard finite-dimensional parametric classes, the radius can depend on effective model dimension.Source: §4.1 · p. 7

4.2 Eluder Dimension and the Squared Width Process

  • The squared Eluder coefficient links classical Eluder-dimension growth to accumulated squared uncertainty, while its untruncated squared-ratio definition differs from clipped variants.The confidence-set definition also yields bounds on both width and squared-width processes.Source: §4.2 · pp. 7–8

4.3 General Regret Guarantees

  • With P(E^c)=O(1/T), Theorem 5 bounds reverse- and forward-KL regret for UCS (expected sampling regret, fixed unknown θ) and TS2 (Bayesian sampling regret, θ∼ρ), and both regrets for SWC-framework algorithms under that confidence-set choice.Source: §4.3 · p. 8
  • Theorem 5 connects model-specific complexity bounds to UCS, TS2, and SWC, and recovers prior special-case analyses under their respective settings.The cited connections include the optimistic bandit analysis of Zhao et al. [66] and finite-armed sampling of Pedramfar and Ravanbakhsh [39].Source: §4.3 · p. 8, Table 2 · p. 8

5 LIMITATIONS AND FUTURE DIRECTIONS

The paper bounds its guarantees to fixed temperature and exact Gibbs sampling under bounded rewards and direct noisy feedback. It distinguishes tilted sampling from related work that assumes a known target or reward, framing unknown-reward Gibbs sampling under bandit feedback as a statistical learning problem.

5 LIMITATIONS AND FUTURE DIRECTIONS

  • The guarantees assume bounded rewards, direct noisy reward feedback, and exact Gibbs sampling; a matching lower bound for joint dependence on horizon, temperature, and class complexity remains open.Approximate-sampling error and computational cost are identified as future directions.Source: §5 · p. 8

A RELATED WORKS

  • Prior entropy-regularized control work generally computes or approximates Gibbs-optimal policies when the reward or value function is known, whereas tilted sampling learns the distribution from bandit feedback.This shift yields a distinct regret notion and second-order uncertainty structure.Source: A RELATED WORKS · p. 12
  • The statistical problem of learning implicit target distributions in KL-regularized and RLHF objectives has received comparatively little attention, with recent online-learning work beginning to address it.The related-work discussion cites recent online-learning study [66].Source: A RELATED WORKS · p. 12
  • MCMC methods assume a known, queryable target and focus on computational mixing, while tilted sampling studies an unknown reward accessed through noisy bandit feedback.The paper describes its regret control through cumulative confidence widths rather than mixing time.Source: A RELATED WORKS · p. 13
  • GFlowNets and neural samplers typically assume access to the reward or unnormalized target; this framework instead gives a regret-theoretic account of sampling under bandit feedback.It positions UCS and TS2 as optimism and posterior-sampling exploration strategies for Gibbs sampling.Source: A RELATED WORKS · p. 13

B PROOF OF THEOREM 1

The proof uses a conditional distribution identity for Thompson-style sampling and bounds regret on and off the confidence event.

B PROOF OF THEOREM 1

  • When the confidence condition fails, per-round regret is bounded by C, so the expected contribution is controlled by summing failure indicators.The proof states this bound directly for the failure event.Source: B PROOF OF THEOREM 1 · p. 13
  • Conditioned on the history and sampled action, the posterior draw and true parameter have the same conditional distribution, yielding an identity used in the Thompson-sampling decomposition.The action and optimal action are measurable functions of their respective parameter draws.Source: B PROOF OF THEOREM 1 · p. 14
  • The proof sums the per-round decomposition over time and takes expectations to obtain the regret bound.The supplied proof passages state this step for both the UCB and Thompson-style arguments.Source: B PROOF OF THEOREM 1 · pp. 13–14

C BANDIT OPTIMIZATION AS A LIMIT OF TILTED SAMPLING

As temperature grows, Gibbs sampling concentrates on reward maximizers, connecting tilted sampling to hard optimization. The appendix also establishes KL bounds for Gibbs distributions and a Bayesian bound for posterior-random Gibbs distributions.

C BANDIT OPTIMIZATION AS A LIMIT OF TILTED SAMPLING

  • If the maximizer set has zero base-measure mass, setwise convergence in the stated result cannot hold, and weak limits need not be unique.When weak limits exist, their distribution can depend on local behavior of the reward and base measure near maximizers.Source: C BANDIT OPTIMIZATION AS A LIMIT OF… · p. 15
  • As β grows, any weak limit of the Gibbs measures is supported on the maximizers; when the maximizer set has positive base-measure mass, the measures converge setwise to the normalized base measure on that set.For a unique maximizer, the supported limit is the Dirac measure at that action.Source: C BANDIT OPTIMIZATION AS A LIMIT OF… · pp. 14–17

D FREQUENTIST BOUNDS ON KL-DIVERGENCE

E BAYESIAN BOUNDS ON KL-DIVERGENCE

  • The Bayesian KL argument averages over posterior function draws and reduces both width terms to expectations under the mixture of their Gibbs distributions.The resulting bound has coefficient β2.Source: E BAYESIAN BOUNDS ON KL-DIVERGENCE · pp. 21, 23

F PROOF OF THEOREM 2

The proof bounds either directed instantaneous KL regret by 2C using the shared range bound on rewards and confidence bounds, then sums over rounds.

F PROOF OF THEOREM 2

G PROOF OF THEOREM 3

On the confidence event, optimism bounds the reward gap by the confidence width, yielding linear- and squared-width regret bounds; outside it, the proof uses a 2C bound.

G PROOF OF THEOREM 3

  • On E_t, optimism and the confidence bounds give 0 ≤ g_t − f_θ ≤ w_Ft on A_t.Source: G PROOF OF THEOREM 3 · p. 23
  • Lemma 4 yields both linear- and squared-width bounds on E_t, with the nonnegative gap allowing M = 0 for the squared-width bound.Source: G PROOF OF THEOREM 3 · p. 23
  • On E_t, either directed instantaneous KL regret is at most 2C; expectations over randomness and summation over rounds complete the proof.Source: G PROOF OF THEOREM 3 · p. 23

H PROOF OF THEOREM 4

Theorem 4's proof conditions two posterior draws on confidence events and uses posterior-averaged bounds to control regret by squared widths. The following subsection connects confidence-set geometry to pairwise disagreement.

H PROOF OF THEOREM 4

  • Conditioned on history and action, θ and the TS² draw are independent and identically distributed; conditioning each on its own confidence event preserves independence with a common restricted law.The proof considers histories where the joint good event has positive conditional probability; otherwise its contribution vanishes.Source: H PROOF OF THEOREM 4 · p. 23
  • Applying the posterior-averaged part of Lemma 6 to the restricted function law gives a squared-width bound for the Gibbs mixture.Source: H PROOF OF THEOREM 4 · p. 23
  • Exchanging θ and the posterior draw gives the same constants, confidence event, and width expectations for forward KL as for reverse KL.Source: H PROOF OF THEOREM 4 · p. 24
  • Outside the good event, either directed instantaneous KL regret is at most 2C because g_t and f_θ lie in [0, C].Source: H PROOF OF THEOREM 4 · p. 24

I BOUNDING WIDTH PROCESS WITH SQUARED ELUDER COEFFICIENT

J ELUDER DIMENSION VS. SQUARED ELUDER COEFFICIENT

This section relates squared Eluder coefficient bounds to ordinary Eluder dimension by partitioning rounds according to disagreement scales. Under stated growth conditions, it derives bounds for the squared-width process.

J ELUDER DIMENSION VS. SQUARED ELUDER COEFFICIENT

  • The proof partitions rounds with large current disagreement into scales and further separates each scale by past disagreement.It treats small-current-disagreement rounds separately and covers the remaining rounds with the sets S_k.Source: J ELUDER DIMENSION VS. SQUARED ELUDER… · p. 25
  • The scale-wise sets are bounded using ordinary Eluder dimension by partitioning their action sequences into Eluder-independent subsequences.The proof bounds the number of denominator levels and the length of each block before combining the scale bounds.Source: J ELUDER DIMENSION VS. SQUARED ELUDER… · pp. 26–27
  • The resulting bound applies to the squared Eluder coefficient for arbitrary action and function-pair sequences.Source: J ELUDER DIMENSION VS. SQUARED ELUDER… · p. 27
  • For a > 0, the section states a bound under the specified horizon and tolerance conditions, using the assumed Eluder-dimension growth.The proof substitutes the growth bound k+1 dim_E(F, α_k+1) < C²c(T) log2(T)^(b+1) into Lemma 7.Source: J ELUDER DIMENSION VS. SQUARED ELUDER… · pp. 27–29

K EXTENDED COMPARISON AND ALGORITHMS

Tilted sampling replaces hard optimization with a Gibbs-distribution target, changing the uncertainty order from first-order to second-order. The section contrasts this geometry with optimization and presents UCS and TS², including a posterior-sampling procedure.

K EXTENDED COMPARISON AND ALGORITHMS

  • Optimization uses a hard argmax and first-order uncertainty, whereas tilted sampling uses a smooth KL-based metric and second-order uncertainty.The comparison identifies the uncertainty terms as w_Ft(A_t) and w_Ft(A_t)^2, respectively.Source: K EXTENDED COMPARISON AND ALGORITHMS · p. 30
  • UCS and TS² are presented as optimistic and Bayesian sampling algorithms, respectively, with O(log T) regret at fixed β.TS² samples a parameter from the posterior, forms its reward function, then samples an action from the corresponding Gibbs distribution.Source: K EXTENDED COMPARISON AND ALGORITHMS · p. 30
  • The Gibbs operator interpolates between optimization and sampling; as β → ∞, its targets concentrate on maximizers and recover bandit optimization under stated regularity conditions.The passage refers to regularity conditions discussed in Appendix C.Source: Table 3 · p. 30

Related papers

Loading 2610.21908v1…