KTH Builds a 3-Step Formula to Bound Worst-Case AI Risk
A new paper turns an abstract lower-bound recipe for tail-risk in interactive learning into concrete, order-tight bounds for Gaussian estimation and bandits.
Takeaways
- KTH researchers turn an abstract Bayesian CVaR lower-bound framework into concrete bounds via a two-point Hellinger template.
- The recipe: pick a hard model pair, verify a balanced-pair loss condition, bound squared Hellinger through KL.
- Gaussian mean estimation gets a worst-case CVaR lower bound scaling as c_alpha divided by square root of n.
- Two-armed Gaussian bandits get a worst-case CVaR regret lower bound scaling as c_alpha times square root of T.
- Bounds recover known Bayes-risk rates while retaining explicit dependence on risk level alpha, unlike expectation bounds.
- Builds on the interactive Fano method of Chen, Foster, Han, Qian, Rakhlin, Xu (NeurIPS 2024).
Most lower bounds in statistical learning theory tell you the smallest average error any algorithm can achieve. That is comforting on paper, but average performance hides the rare, expensive failures that risk-sensitive systems, from portfolio optimizers to safety-critical controllers, actually care about. A new theoretical paper from KTH Royal Institute of Technology tackles this gap by showing how to derive explicit tail-risk lower bounds for interactive learners like bandits, using a framework that had, until now, remained mostly abstract.
The setting is interactive statistical decision making (ISDM), a formulation from Chen et al. that unifies information-theoretic lower bounds for statistical estimation and interactive decision making, arguing that classical tools like Fano, Le Cam and Assouad fall short for algorithms that collect data interactively such as bandits and reinforcement learning. Chen et al. resolved this by introducing an interactive Fano method. A recent follow-up by Bongole, Oechtering, and Skoglund pushed the idea toward tail-sensitive criteria like Conditional Value-at-Risk (CVaR), producing a generalized-Fano corollary that lower bounds Bayesian CVaR under the prior-predictive law.
That corollary came with a catch: it was abstract. It named the ingredients (a benchmark under a reference law, a divergence budget) without telling you how to actually compute them for a concrete problem.