The Tilted Sampling Problem: Optimistic and Posterior Sampling Achieve Logarithmic Regret

From Optimal Action Selection to Soft-Optimal Distribution Sampling

The core objective of traditional online learning and reinforcement learning is to identify a single optimal action or policy. However, the application scenarios of modern learning systems are undergoing a fundamental shift: entropy-regularized reinforcement learning, RLHF (Reinforcement Learning from Human Feedback), and reward-oriented generative models no longer aim to find a "hard optimal" solution, but rather to sample diverse high-quality outputs from a soft-optimal distribution induced by an unknown reward function.

This shift has given rise to an entirely new online learning problem---tilted sampling. Researchers define the objective as sampling from a Gibbs distribution, where the reward function is unknown. Sampling regret is defined as the temperature-normalized cumulative KL divergence between the learner's distribution and the Gibbs target distribution, which corresponds exactly to the suboptimality gap in entropy-regularized reward maximization. This framework unifies and generalizes several recently emerged settings based on sampling and KL regularization in the bandit and reinforcement learning literature.

The Gibbs distribution (also known as the Boltzmann distribution) is a core concept in statistical physics and machine learning, with the form $\pi(a) \propto \exp(r(a)/\tau)$, where $r(a)$ is the reward of action $a$ and $\tau$ is the temperature parameter. Higher temperatures yield flatter, more exploratory distributions; as temperature approaches zero, the distribution degenerates to a Dirac distribution over the optimal action---the "hard optimal" solution. Thus, the Gibbs distribution naturally characterizes the soft objective of "with what probability to select each action." In entropy-regularized reinforcement learning, the optimal policy takes exactly the Gibbs distribution form, with the entropy regularization coefficient and temperature being reciprocals of each other. This makes "maximizing entropy-regularized reward" and "matching the Gibbs distribution" mathematically equivalent, and is the fundamental reason why the tilted sampling framework can unify multiple settings.

Structural Differences in Sampling Regret

The core contribution of this work lies in revealing a key insight: the uncertainty structure of sampling regret is fundamentally different from classical regret minimization.

In standard regret minimization, due to first-order uncertainty effects, the regret upper bound typically takes the form $\widetilde{O}(\sqrt{T})$. However, under the tilted sampling framework, sampling regret is dominated by the square of the confidence width, which under standard fixed-temperature settings produces logarithmic regret---i.e., $O(\log T)$ or $\widetilde{O}(\log T)$.

This difference is not a fine-tuning of technical details but reflects a change in the nature of the problem itself. When the learning objective shifts from "finding the optimum" to "learning to sample," the learner does not need to precisely eliminate all uncertainty---it only needs to cover high-reward regions with appropriate probability weights. This "soft" objective permits more efficient exploration strategies, yielding theoretically exponential regret improvement (from $\sqrt{T}$ to $\log T$).

Temperature-normalized cumulative KL divergence is the key to understanding sampling regret. Standard regret measures suboptimality by reward differences, whereas sampling regret measures the discrepancy between the learner's distribution $\hat{\pi}_t$ and the target Gibbs distribution $\pi^$, in the form $\sum_t \tau \cdot \mathrm{KL}(\hat{\pi}_t | \pi^)$. Temperature normalization is necessary because the scale of KL divergence varies with temperature: lower temperatures yield sharper distributions, where the same probability deviation incurs greater reward loss. After normalization, this quantity equals exactly the suboptimality gap in entropy-regularized reward maximization---the difference between the learner's expected regularized reward at that moment and the optimal value. This equivalence allows sampling regret to be analyzed with information-theoretic tools while also being directly interpretable as a loss in decision quality, serving as a bridge connecting statistical learning theory and reinforcement learning practice.

UCS and TS²: Sampling Versions of Optimistic and Posterior Strategies

To characterize this new problem, researchers developed sampling counterparts of classical algorithms:

• UCS (Upper Confidence Sampling): Transfers the optimism principle of UCB to the sampling setting. It does not seek to identify the optimal action, but instead uses confidence upper bounds to construct an optimistic Gibbs sampling distribution.
• TS² (Thompson Sampling squared): A sampling variant of Thompson Sampling. The "squared" in its name hints at the central role of the confidence-width-squared term in sampling regret.

Both algorithms come with a unified regret decomposition framework capable of explaining and extending recently emerged logarithmic regret guarantees. Notably, the researchers also provide for the first time a Bayesian sampling regret decomposition based on new bounds for posterior random Gibbs distributions, offering theoretical tools for understanding the behavior of posterior sampling in tilted problems.

Upper Confidence Bound (UCB) is the core algorithm for classical bandit problems. Its idea is to construct confidence upper bounds for each action's reward estimate and select the action with the largest upper bound, thereby balancing exploitation and exploration, corresponding to $\widetilde{O}(\sqrt{T})$ regret. UCS transfers this principle to the sampling setting: rather than selecting a single action, it constructs an optimistic Gibbs distribution from confidence upper bounds and samples from it. Thompson Sampling (TS) adopts a Bayesian perspective, sampling a reward function from the posterior distribution over rewards and then selecting actions accordingly. TS² is its sampling variant, where "squared" points to the dominance of the confidence-width-squared term in sampling regret---meaning the algorithm only needs the confidence width to shrink at a rate of $1/\sqrt{t}$, and after accumulating the squares, achieves logarithmic regret. The two algorithms represent natural extensions of the frequentist and Bayesian approaches, respectively, under tilted sampling.

Theoretical Significance and Practical Implications

The most important theoretical conclusion of this work can be summarized in one sentence: learning to sample from a soft-optimal distribution and identifying a hard-optimal solution are statistically two fundamentally different problems.

This distinction has direct practical implications. In RLHF and generative model fine-tuning, pursuing a "unique optimal output" is neither correct nor necessary; algorithm design should directly target the distribution matching objective, leveraging the logarithmic convergence properties of sampling regret to build more efficient training pipelines. For entropy-regularized reinforcement learning, this means providing tighter theoretical guidance for temperature parameters and exploration strategies.

The unified regret decomposition established by the researchers also provides an analytical template for future work---any online learning problem involving KL regularization or Gibbs sampling may benefit from this framework. Research in this direction is pushing us from the paradigm of "optimizing a single objective" toward a new paradigm of "learning to sample distributions."

One-line Summary

Tilted sampling reveals that learning to sample from a soft-optimal distribution is statistically fundamentally different from identifying a hard-optimal solution, with regret dropping from √T to log T.

Paragraph Summary

This article introduces tilted sampling, a new problem in online learning and reinforcement learning, where the goal is no longer to find a single optimal action but to sample diverse high-quality outputs from a Gibbs soft-optimal distribution induced by an unknown reward function. Sampling regret is defined as the temperature-normalized cumulative KL divergence between the learner's distribution and the Gibbs target distribution, corresponding to the suboptimality gap in entropy-regularized reward maximization. The key insight is that sampling regret is dominated by the square of the confidence width, yielding only logarithmic regret at fixed temperature, in stark contrast to the √T upper bound of classical regret minimization. Researchers propose UCS and TS² algorithms corresponding to optimistic and posterior sampling, establish a unified regret decomposition framework, and provide the first Bayesian sampling regret decomposition. This work has direct practical implications for RLHF and generative model fine-tuning.