📊 statistics

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

This paper establishes the asymptotic optimality of the $\rho\text{-}\mathrm{NPTS}_{\mathrm{SG}}$ algorithm for risk-averse multi-armed bandits with sub-Gaussian rewards, proving that it achieves instance-dependent regret matching the theoretical lower bound for any continuous risk functional without requiring parametric assumptions or Lipschitz conditions.

Original authors: Joel Q. L. Chang

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Joel Q. L. Chang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a manager trying to pick the best employee from a team of candidates. In the classic version of this problem, you only care about who makes the most money. But in the real world, you also care about risk.

Do you want the employee who makes a huge amount of money but might quit tomorrow?
Or the one who makes a steady, reliable amount?
Maybe you want the one who makes the most money relative to how much stress they cause (like a "Sharpe ratio" in finance).

This is the world of Risk-Averse Bandits. The "bandit" is a slot machine with multiple arms (candidates). You pull an arm to see the reward, but you want to learn which one is best without wasting too many pulls on the bad ones.

The Problem: The "Growing Alphabet" Mess

For years, scientists had a great tool called Thompson Sampling to solve this. It works like this:

You keep a "belief" (a map) about how good each arm is based on what you've seen so far.
You randomly pick a scenario from that map and choose the arm that looks best in that specific scenario.
You repeat this.

However, there was a major snag. The paper explains that as you pull an arm more and more times, your "belief map" gets incredibly complicated. It's like trying to draw a map where every single step you've ever taken gets its own unique color. The more steps you take, the more colors you need.

Mathematicians call this a "growing alphabet."

The Old Problem: Because the map kept getting more complex with every single pull, the math used to prove the algorithm was "optimal" (meaning it learns as fast as theoretically possible) would explode into a mess. The numbers got so huge (super-exponential) that the proof broke down.
The Result: We knew the algorithm worked in practice, but we couldn't mathematically prove it was the best possible way to do it, especially for tricky risk measures like the Sharpe ratio.

The Solution: The "Grid" Trick

The author, Joel Chang, introduces a clever trick to fix this mess. He calls it a Discretisation Lemma.

Imagine your map is a high-resolution photo with millions of tiny pixels (the "growing alphabet"). Trying to analyze every single pixel is impossible.

The Trick: Instead of looking at every pixel, you lay a fixed grid (like graph paper) over the photo. You only care about which "square" on the grid a pixel falls into.
Why it works: Even if you take a million steps, you only have a fixed number of squares on your graph paper. This keeps the math simple and manageable. The author proves that this "grid" approximation is close enough to the real thing that you don't lose any accuracy, but it stops the numbers from exploding.

What Did They Prove?

Using this grid trick, the paper proves two main things:

It Works for Any "Smooth" Risk Measure: Whether you care about the average reward, the worst-case scenario (CVaR), or the risk-adjusted return (Sharpe ratio), this algorithm learns at the absolute fastest speed theoretically possible.
- Analogy: Before, we could only prove this worked for simple rules like "pick the highest average." Now, we proved it works for complex rules like "pick the highest average divided by the volatility," without needing to assume the rewards follow a specific shape (like a perfect Bell Curve).
It Works for Real-World Data (Sub-Gaussian): The authors extended this to handle data that isn't stuck between 0 and 1 (like money between $0 and $1). They proved it works for data that can go anywhere but has "thin tails" (meaning extreme outliers are very rare, like in a normal distribution).
- The "Anchor-Free" Upgrade: The old version needed a "safety anchor" (a fake starting point) to work. The new version, called $\rho$ -NPTSSG, doesn't need this anchor. It just starts pulling arms and learns from pure experience.

Why This Matters (According to the Paper)

No More "Magic" Assumptions: Previous methods often required you to guess the shape of the data (e.g., "Assume the rewards are Gaussian"). This new method doesn't care what the shape is, as long as the risk measure is "continuous" (small changes in data lead to small changes in risk).
The Sharpe Ratio Breakthrough: The paper specifically highlights that this is the first time anyone has mathematically proven an algorithm is optimal for the Sharpe ratio (a very popular but mathematically tricky metric) without assuming the data follows a specific formula.
It's Not Just a Heuristic: For a long time, people used this algorithm because it "seemed" to work well in experiments. Now, we have a mathematical guarantee that it is the best possible way to solve this problem.

Summary

The paper takes a powerful but mathematically messy algorithm, gives it a "grid" to keep things organized, and proves that it is the fastest possible way to learn which option is best when you care about risk. It removes the need for rigid assumptions about the data and solves a problem that had been open for years.

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

Problem Statement
The paper addresses the Multi-Armed Bandit (MAB) problem under risk-averse objectives. Unlike standard MAB settings that maximize expected reward, risk-averse settings aim to optimize general risk functionals $\rho$ (e.g., Conditional Value-at-Risk (CVaR), mean-variance, Sharpe ratio, or distortion risk measures). The specific challenge tackled is the theoretical analysis of $\rho$ -NPTS (a nonparametric Thompson Sampling algorithm proposed by Chang and Tan [2022]). While Chang and Tan proved instance-optimal regret for a parametric companion ( $\rho$ -MTS), they left the optimality of the nonparametric $\rho$ -NPTS as an open problem.

The fundamental obstacle is that $\rho$ -NPTS constructs a Dirichlet posterior where the effective alphabet size grows with the number of observations ( $N_k$ ). Direct application of existing tail bounds results in a super-exponential prefactor of $(N_k)^{N_k/2}$ , which prevents the proof of logarithmic regret bounds. Furthermore, prior results often required strong conditions such as the "dominance" condition (for parametric methods) or Lipschitz continuity of the risk functional (for UCB-type algorithms), excluding important non-Lipschitz functionals like the Sharpe ratio.

Methodology
The authors introduce $\rho$ -NPTSSG, an anchor-free variant of the nonparametric Thompson Sampling algorithm designed for distributions with bounded density and sub-Gaussian tails ( $P(B, \sigma)$ ). The core technical innovation is a discretisation lemma (and its truncated analogue for sub-Gaussian tails) that projects the growing-alphabet Dirichlet posterior onto a fixed grid.

Discretisation and Aggregation:
The paper defines a fixed grid $G_M$ of size $M$ . For any observed reward sequence, the empirical measure is projected onto this grid by aggregating Dirichlet weights corresponding to observations falling within the same grid bin.
- Key Insight: By the aggregation property of the Dirichlet distribution, the projected weights on the occupied bins follow a Dirichlet distribution with a fixed dimension ( $M^+ \le M$ ), regardless of the sample size $N_k$ .
- Consequence: This projection caps the polynomial prefactor in the tail bounds at degree $(M-1)/2$ , which is independent of $N_k$ . This breaks the super-exponential barrier that blocked prior proofs.
Algorithm Variants:
- $\rho$ -NPTS (Bounded Support): Operates on distributions with support in $[0, 1]$ and bounded density. It uses a fixed anchor (the right endpoint) and a uniform grid.
- $\rho$ -NPTSSG (Sub-Gaussian): Operates on distributions on $\mathbb{R}$ with bounded density and sub-Gaussian tails. It removes the fixed anchor (using round-robin initialization instead) and employs a truncated discretisation lemma. This lemma uses a grid centered on the empirical mean with a width that shrinks as the sample size grows, while truncating the tails to control overflow probability.
Regret Analysis:
The proof follows a standard decomposition of regret into terms where the algorithm pulls a suboptimal arm with a "high" Thompson score versus a "low" score.
- Upper Bound: Utilizes the discretisation lemma to apply the tail bounds of Chang and Tan [2022] to the fixed-grid projection. The continuity of $\rho$ (specifically $D_\infty$ -continuity) ensures that the risk of the projected measure approximates the true risk.
- Lower Bound: Matches the instance-dependent lower bound established by Chang and Tan [2022], which relies on the Kullback-Leibler (KL) divergence minimization problem $K^\rho_{\inf}$ .

Key Contributions

Resolution of the Open Problem: The paper proves that $\rho$ -NPTSSG achieves instance-optimal regret of $\sum_{k: \Delta^\rho_k > 0} \frac{\Delta^\rho_k \log n}{K^\rho_{\inf}(\nu_k, r^\rho_1)} + o(\log n)$ for any continuous risk functional $\rho$ on the class of distributions with bounded density and sub-Gaussian tails.
Weaker Conditions: The result requires only the continuity of the risk functional $\rho$ $ρ$ (specifically with respect to the Lévy–Prokhorov metric). This is strictly weaker than:
- The "dominance" condition required for the parametric $\rho$ -MTS.
- The Lipschitz condition required for UCB-type algorithms.
- This allows the first instance-optimal guarantees for non-Lipschitz functionals, such as the Sharpe ratio, without assuming parametric reward distributions.
Discretisation Lemma: The paper introduces a technical lemma that controls a growing-alphabet Dirichlet posterior at a fixed resolution. This lemma is of potential independent interest for any problem involving Dirichlet processes with growing support.
Sub-Gaussian Extension: The authors extend the bounded-support results to the broader class of sub-Gaussian distributions (including Gaussian arms) via a truncated discretisation approach, removing the need for a pre-specified support interval.

Results

Theorem 1 (Bounded Support): Establishes asymptotic optimality for $\rho$ -NPTS on $P(B)$ under continuity alone.
Theorem 2 (Sub-Gaussian): Establishes asymptotic optimality for $\rho$ -NPTSSG on $P(B, \sigma)$ .
Experimental Validation: The paper presents four experiments validating the theory:
1. $\rho$ -NPTS tracks the instance-optimal lower bound for CVaR on Beta arms, outperforming the Risk-LCB baseline (which has a $\log^2 n$ guarantee).
2. $\rho$ -NPTS achieves $O(\log n)$ regret for the Sharpe ratio on truncated-normal arms, a case where no prior algorithm provided guarantees due to non-Lipschitzness.
3. The algorithm handles composite functionals (e.g., $0.5 \text{CVaR} + 0.5 \text{Sharpe}$ ) without modification.
4. $\rho$ -NPTSSG converges to the instance-optimal lower bound for Gaussian arms, matching the performance of the specialized Normal-Gamma Thompson Sampling algorithm (Shah et al. [2025]) without assuming Gaussian rewards.

Significance and Claims
The paper claims to settle the theoretical status of nonparametric Thompson Sampling for risk-averse bandits. It demonstrates that these algorithms are not merely empirical heuristics but are provably asymptotically optimal.

The significance lies in the relaxation of assumptions:

Practitioners can use raw observations without pre-specifying a reward grid or tuning an alphabet size.
The method applies to a strictly broader class of risk functionals (including the Sharpe ratio) and distribution classes (sub-Gaussian) than previous optimal methods.
The result subsumes concurrent work by Shah et al. [2025] by providing a sharper, instance-optimal constant for the Sharpe ratio without requiring conjugate priors or parametric assumptions.

The authors note that the bounded-density assumption is necessary for the bin-probability bounds used in the proof and does not hold for distributions with point masses (e.g., Bernoulli), for which the parametric $\rho$ -MTS remains the complementary solution. Future work directions identified include contextual bandits, heavy-tailed rewards, and discrete distributions.