Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes that the anchor-free nonparametric Thompson Sampling algorithm, $ρ\text{-}\mathrm{NPTS}_{\mathrm{SG}}$, achieves asymptotic optimality for risk-averse bandits with sub-Gaussian rewards, matching the instance-dependent lower bound of regret to leading order in $\log n$. The result is significant as it extends optimal guarantees to a broader class of continuous risk functionals, including the Sharpe ratio, without requiring the stricter conditions imposed by previous parametric methods. Key technical advancements include a discretisation lemma and a truncated discretisation lemma, which facilitate the projection of the Dirichlet posterior onto a fixed grid, overcoming limitations of earlier approaches.
Achieving regret matching the instance-dependent lower bound for risk-averse bandits, this work breaks new ground by providing optimal guarantees for non-Lipschitz functionals like the Sharpe ratio without parametric assumptions.
We prove that $ρ\text{-}\mathrm{NPTS}_{\mathrm{SG}}$, an anchor-free nonparametric Thompson Sampling algorithm for risk-averse bandits, achieves regret matching the instance-dependent lower bound to leading order in $\log 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.