Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

arXiv:2606.09191 · cs.LG, stat.ML · Submitted 2026-08-22 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards".

Jane: The paper was written by the authors from.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: We've just established that "Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards" is a major breakthrough in sequential decision making, specifically focusing on risk and sub-Gaussian rewards.

Jane: It’s important to understand that this isn't just about achieving a good average outcome; it’s about the specific way the algorithm handles uncertainty in sub-Gaussian environments where we know the tails of reward distributions are constrained.

Lu: The paper tackles two variants, one is for bounded support and then they prove a result for sub-Gaussian rewards, which provides a lot of flexibility for real-world data.

Meng: I’m trying to grasp what "sub-Gaussian" means in practice; does it mean the outcomes are concentrated around the average but never too far away?

Lalam: Yes, that's right; it ensures we can bound how much of a tail event is possible, which allows us to be more aggressive in exploring options while still being safe.

Tom: So, by linking Thompson Sampling—which is usually about picking the best based on probability—with this risk-averse framework, they’ are making a significant step toward understanding robust AI agents.

Jane: Exactly; we're moving from just "good" to "provably optimal given a specific set of risks."

Summary: Tom: Moving past the title and authors, the paper provides a very clear summary of its findings, which is that its primary algorithm achieves instance-optimal regret.

Jane: Regret is simply how much worse we are than the best possible strategy over time, and achieving instance-optimal means that' our performance matches the theoretical lower bound for every single arm setup.

Lu: The central obstacle they overcame was a super-exponential prefactor in earlier work by Chang and Tan, which they found to be fundamental to proving optimality for rho-NPTS.

Meng: I see them addressing this by introducing a "discretization lemma" that projects the complex, growing posterior onto a fixed grid of size M, which seems like a clever way to keep things manageable.

Lalam: This mechanism is crucial because it allows us to manage the complexity of an ever-growing set of observed rewards without letting that growth destroy our ability to prove optimality.

Tom: It’s incredible that they managed to break through this super-exponential barrier while maintaining the full power of Thompson Sampling. Jane, how do you think this technical achievement will be perceived by other researchers?

Jane: I think it signals a new era for risk-averse bandit research, suggesting that previous constraints on what kind of rewards we could model were unnecessarily restrictive.

Improvements: Tom: Now we’re looking at the specific improvements this paper offers, particularly how it compares to prior methods like rho-MTS and rho-NPTS from Chang and Tan.

Jane: The biggest improvement is that the authors require only continuity of the risk functional rho, which is a much weaker condition than requiring "dominance" or the Lipschitz condition found in UCB-type algorithms.

Lu: This means this method applies to a whole class of risk measures, including things like the Sharpe ratio, where no finite global Lipschitz constant exists, making it applicable to functions that were previously off-limits.

Meng: The fact that rho-NPTSSG is an "anchor-free" variant is a practical improvement; it means we don't need some arbitrary fixed point like X 0k=one for initialization.

Lalam: And the improved result covers Gaussian arms, which Shah et al.' two thousand twenty-five studied using a specific Normal-Gamma prior, but this method achieves the same result without making that strong parametric assumption.

Tom: It’s truly unifying different approaches into one robust framework. Jane, what does this mean for practitioners who have these complex risk functions?

Jane: They can't worry about whether their functional meets some strict "dominance" requirement, they can just use the continuity of the risk measure itself to get optimal results.

Conclusion: Tom: To wrap up our discussion of "Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards," we've seen a paper that achieves incredible things in risk-aware AI.

Jane: We’ve covered how it solves the problem of achieving instance-optimal regret and discussed how its weak requirements apply to handle complex, non-Lipschitz risk functions like the Sharpe ratio.

Lu: The theoretical work is sound, proving that rho-NPTSSG matches the lower bound exactly across sub-Gaussian distributions.

Meng: From an engineering standpoint, I'm impressed that they’ don't need a pre-specified grid or to run in a different distribution class, just raw data fed into the Dirichlet structure.

Lalam: I think the future for this is huge, potentially allowing AI systems to make decisions with provable safety and efficiency under much broader sets of uncertain reward distributions.

Tom: It's truly a powerful result that we’re seeing in this field of AI. Let's thank Lu, Meng, and Lalam for sharing their insights on the work of "Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards."

Jane: Goodbye everyone!

cs.LG, stat.ML

Submitted: 2026-08-22

Updated: 2026-08-25

Comments: Withdrawn due to a counterexample identified after posting that invalidates a key step in the risk-averse regret bounds. The result does not hold as stated under the assumptions given. We are revising the analysis and will resubmit if the fix can be established rigorously

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 95/100

The gist: The following is a detailed summary of the scientific paper: The paper addresses sequential decision-making in multi-armed bandit (MAB) frameworks where objectives go beyond expected reward,

Key concepts

Sub-Gaussian Rewards
This type of reward distribution ensures that we can bound how much of a tail event is possible. This constraint allows researchers to be more aggressive in exploring options while still maintaining safety, which is crucial for robust AI agents.
Instance-Optimal Regret
Regret measures how much worse an algorithm performs compared to the best possible strategy over time. Achieving instance-optimal means that the algorithm's performance matches the theoretical lower bound for every single setup, proving its efficiency.
Risk Functional $\rho$
This is a measure of risk used in decision making. The paper improves methods by requiring only continuity of this functional, which is a much weaker condition than previous requirements like 'dominance,' expanding its applicability.

Terminology

Summary

The following is a detailed summary of the scientific paper:

The paper addresses sequential decision-making in multi-armed bandit (MAB) frameworks where objectives go beyond expected reward, utilizing risk-averse measures such as mean-variance, conditional value-at-risk (CVaR), and general distortion risk measures.

Problem Statement and Context

Chang and Tan [2022] unified these settings under a nonparametric Thompson Sampling framework, proposing rho-MTS (parametric) and rho-NPTS (nonparametric). While they proved instance-optimal regret for the parametric version (rho-MTS), they left the nonparametric version (rho-NPTS) as an open problem. The core obstacle was that in rho-NPTS, the effective alphabet grows with N k, and applying the tail bounds of Chang and Tan [2022] directly yields a super-exponential prefactor (N k) N k/2 that their proof technique cannot absorb.

Key Contributions

The authors introduce rho-NPTSSG, an anchor-free nonparametric Thompson Sampling algorithm for risk-averse bandits. The paper makes three key contributions:

  1. Primary Result (Theorem 2): rho-NPTSSG achieves instance-optimal regret on P(B, sigma (B, sigma)) for any continuous rho, achieving a rate of k (rho k / K inf(nu k, r 1 rho)) n + o(n). This is the first instance-optimal guarantee for non-Lipschitz functionals such as the Sharpe ratio without parametric reward assumptions.

  2. Bounded-Support Stepping Stone (Theorem 1): rho-NPTS achieves the same rate on P(B under continuity alone, which is weaker than the dominance condition of rho-MTS and the Lipschitz condition of UCB, resolving the open problem of Chang and Tan [2022].

  3. Technical Device: A discretisation lemma (bounded support) and a truncated discretisation lemma (sub-Gaussian tails), which project the growing-alphabet Dirichlet posterior onto a fixed grid, holding all polynomial prefactors at fixed degree independent of sample size and breaking the super-exponential barrier that blocked prior proofs.

Scope of Applicability

The results apply to:

  • Any continuous risk functional rho. The requirement is continuity of rho: strictly weaker than the dominance condition... and strictly weaker than the Lipschitz condition...

The class P(B, sigma) of distributions with bounded density and sub-Gaussian tails, including Gaussian arms.

Detailed Results

The primary result (Theorem 2) proves that rho-NPTSSG achieves a regret matching the instance-dependent lower bound. The key technical device is a discretisation lemma projecting the growing-alphabet posterior onto a fixed M-point grid, capping the polynomial prefactor at degree (M - 1)/2 independently of sample size.

The bounded-support case (Theorem 1) provides a stepping stone, showing that rho-NPTS achieves the same rate under only continuity alone.

Conclusion

By combining bounds on Term A and Term B, the authors show that E[T k(n)] (n / (K inf(nu k, r 1 rho) - epsilon 3/2)) + O(1), leading to the exact asymptotic rate. The lower bound is established by consistency and Chang and Tan [2022], Theorem 2.

Improvements for AI systems

The following improvements outline how the theoretical breakthroughs in this paper can be translated into a highly precise, provably optimal AI system.

We replace or enhance existing Thompson Sampling (TS) implementations with the ** rho-NPTSSG** framework, leveraging two critical technical lemmas:

1. Integration of the Discretization Lemma (Bounded Support):

  • Implementation: Instead of relying on a fixed, pre-specified support set S for the Dirichlet prior (as required by rho-MTS), we dynamically project the growing-alphabet Dirichlet posterior (Dir(1N k)) onto a fixed, uniform grid G M = g 1,, g M.

  • Mechanism: This projection uses the Dirichlet aggregation property to define a new vector of parameters j (the count of observed rewards falling into bin I j). The resulting system operates on an M-dimensional fixed-size grid.

  • Benefit: This capping mechanism ensures that the polynomial prefactor in the regret bound is capped at a fixed degree (M-1)/2, independent of the sample size N k, effectively resolving the super-exponential barrier that previously limited theoretical proofs.

2. Integration of the Truncated Discretization Lemma (Sub-Gaussian Tails):

  • Implementation: For scenarios involving sub-Gaussian reward distributions (e.g., Gaussian arms), we replace the fixed uniform grid G M with an empirical-mean-centered truncated grid G M(N).

  • Mechanism: We introduce a truncation radius T M = sigma squared M. This allows us to bound the probability of overflow (where the true reward falls outside the truncation range) by nu k(X - N > T M) 2/M.

  • Benefit: This adaptation allows the system to maintain a fixed, manageable grid while accurately modeling distributions that do not have bounded support, providing a consistent framework for all P(B, sigma) classes.

3. Adoption of the No-Anchor Initialization (rho-NPTSSG):

  • Implementation: The system is initialized without the fixed anchor X 0k=1 (which was a necessary artifact of previous proofs). Instead, it uses a round-robin initialization, and subsequent samples are drawn purely from the empirical posterior Dir(1N k).

  • Mechanism: This removes a specific structural constraint, allowing the algorithm to operate on the pure empirical posterior.

The resulting system is not merely a heuristic improvement; it is a provably optimal decision-making agent. Its capabilities are defined by its mathematical guarantees:

1. Achieving Instance-Optimal Regret:

  • The system achieves the exact, instance-dependent lower bound on cumulative regret: O (rho k over sqrt K inf(nu k, r 1 rho) n + o(n)). This means the system performs as well as any other possible algorithm for that specific problem instance.

2. Handling Non-Lipschitz Risk Functionals:

  • The system provides the first rigorous guarantee for non-Lipschitz functionals (such as the Sharpe Ratio, Sharpe(nu) = E nu[X] / Var nu(X)). Because it relies only on D infinity-continuity rather than a stringent Lipschitz condition, it can apply to complex risk measures where traditional algorithms fail.

3. Handling Complex and Composite Risk Profiles:

  • It successfully manages composite functionals (e.g., 0.5 CVaR 0.75 + Sharpe Ratio) for which no prior algorithmic guarantees existed, as the proof structure is robust to complex functional definitions provided they are continuous.

4. Universal Applicability to Sub-Gaussian Classes:

  • The system is guaranteed to be optimal across the entire class P(B, sigma), including distributions with bounded density (Beta) and those with sub-Gaussian tails (Gaussian), without requiring any prior parametric assumptions about the reward distribution.

Abstract

We prove that ρ-NPTS SG, an anchor-free nonparametric Thompson Sampling algorithm for risk-averse bandits, achieves regret matching the instance-dependent lower bound to leading order in n, establishing it as asymptotically optimal for any continuous risk functional ρ (CVaR, mean-variance, Sharpe ratio, distortion risk measures, and more) on the class of distributions with bounded density and sub-Gaussian tails, including Gaussian arms. Both this result and its bounded-support counterpart require only continuity of ρ: strictly weaker than the dominance condition of prior parametric Thompson Sampling results, and strictly weaker than the Lipschitz condition of UCB-type algorithms, yielding the first instance-optimal guarantees for non-Lipschitz functionals such as the Sharpe ratio without parametric reward assumptions. The bounded-support case is developed first as a stepping stone sharing the same proof structure. The key technical contributions are a discretisation lemma (bounded support) and a truncated discretisation lemma (sub-Gaussian tails), each projecting the growing-alphabet Dirichlet posterior onto a fixed grid via the Dirichlet aggregation property, holding all polynomial prefactors at fixed degree independent of sample size and breaking the super-exponential barrier that blocked prior proofs.

Sources

Related papers