New Thompson Sampling Algorithm Achieves Optimal Performance for Risk-Averse Decision-Making

A new preprint posted to arXiv establishes that ρ-NPTS_SG, an anchor-free nonparametric Thompson Sampling algorithm, matches the instance-dependent lower bound on regret to leading order in log n for risk-averse bandit problems with sub-Gaussian rewards, including Gaussian arms. The algorithm applies to any continuous risk functional, covering CVaR, mean-variance, Sharpe ratio, and distortion risk measures, among others, on distributions with bounded density and sub-Gaussian tails. Crucially, the proof requires only continuity of the risk functional—a condition strictly weaker than the dominance condition needed by prior parametric Thompson Sampling results and strictly weaker than the Lipschitz condition required by UCB-type algorithms. The key technical innovations are a discretisation lemma for bounded-support distributions and a truncated discretisation lemma for sub-Gaussian tails, both of which project a growing-alphabet Dirichlet posterior onto a fixed grid using the Dirichlet aggregation property, keeping polynomial prefactors at fixed degree and breaking a super-exponential barrier that had blocked earlier proofs. The bounded-support case is treated first as a structural stepping stone sharing the same proof architecture. These results provide the first instance-optimal guarantees for non-Lipschitz risk functionals such as the Sharpe ratio in a fully nonparametric setting, with potential implications for risk-sensitive applications in finance and operations research.