When designing algorithms for sequential decision-making—such as multi-armed bandits, online optimization, or reinforcement learning—our standard benchmark for success is regret. Regret measures the difference between the total loss incurred by our algorithm and the loss of the best fixed decision in hindsight.
For years, the gold standard in theoretical guarantees was expected regret. Expected regret answers a simple question: If we run this algorithm in a million parallel universes, how well does it perform on average?
While mathematically convenient, expected regret hides a dangerous flaw. In real-world deployments—whether routing internet packets, managing financial portfolios, or treating patients in a clinical trial—we do not get a million universes. We get exactly one run. If an algorithm has low expected regret but high variance, a practitioner might find themselves in a catastrophic worst-case realization.
To guarantee safety and reliability, we need high-probability regret bounds. These bounds provide a strict certificate: with probability at least $1 - \delta$ (where $\delta$ is a tiny risk tolerance), the actual regret accumulated in a single execution will not exceed a specified threshold.
The Core Challenge: The Variance of Partial Feedback
Why is proving high-probability bounds so much harder than proving expected bounds? The root of the problem lies in how algorithms learn from partial information.
In a full-information setting, the learner observes the losses of all possible actions at every step. Because these losses are typically bounded, standard concentration inequalities (like Hoeffding's or Azuma's inequalities) apply cleanly, ensuring that the empirical average converges rapidly to the true mean.
In a bandit setting, however, the learner only observes the loss of the action they chose. To evaluate actions they didn't choose, the algorithm must construct an estimator. The standard tool for this is the importance-weighted estimator:
$$\hat{\ell}_t(a) = \frac{\ell_t(a)}{p_t(a)} \mathbb{I}(a_t = a)$$
where $p_t(a)$ is the probability the algorithm assigns to choosing action $a$.
Herein lies the trap. If an action looks unpromising, $p_t(a)$ becomes very small. If the algorithm then decides to sample that action to explore, and happens to hit it ($\mathbb{I}(a_t = a) = 1$), the estimator divides by a tiny fraction, causing $\hat{\ell}_t(a)$ to explode. As noted by Chung-Wei Lee et al., these importance-weighted estimators inherently produce heavy-tailed distributions. While these extreme spikes cancel out in expectation, they completely break traditional concentration analysis, making high-probability guarantees incredibly elusive.
Taming the Tails: Algorithmic Mechanisms
To achieve high-probability guarantees, researchers have developed mechanisms to explicitly control the variance of these loss estimators.
1. Biased Estimators and Implicit Exploration
Historically, the easiest way to prevent the importance-weighted estimator from exploding was to force the algorithm to explore by mixing its action distribution with a uniform distribution. This guaranteed that $p_t(a)$ never dropped below a certain threshold. However, forcing explicit exploration degrades practical performance because the algorithm is compelled to make intentionally poor choices.
Gergely Neu demonstrated that we can "explore no more" by shifting the modification from the action selection step to the loss estimator itself. By using implicitly biased loss estimators, one can strictly control the variance of the learning process without forcing the algorithm into suboptimal actions, achieving optimal high-probability bounds naturally.
2. Variance Control and Clipping
Another powerful approach is to directly penalize or clip high-variance estimates. Thodoris Lykouris et al. showed that by strictly controlling the variance of loss estimators through a dual-threshold freezing mechanism, one can achieve high-probability "small-loss" bounds—where the regret scales with the loss of the best action rather than the total time horizon. In reinforcement learning, Jinglin Chen et al. utilized a "clipping" variant of randomized least-squares value iteration to bound worst-case deviations, ensuring that exploration noise does not cause catastrophic single-run failures.
Defeating Adaptive Adversaries
The challenge intensifies when moving from an environment with fixed, stochastic noise to one governed by an adaptive adversary—an opponent that alters future losses based on the player's past actions.
Early work in online linear optimization often struggled to provide robust guarantees against such adversaries. Peter Bartlett et al. bridged this major gap by introducing the GEOMETRICHEDGE.P algorithm, which achieved the first high-probability regret bounds that are optimal in their dependence on time ($T$) against adaptive adversaries.
When physical constraints are added to the problem, the limits of high-probability learning become apparent. For instance, Nicolò Cesa-Bianchi et al. explored online learning under switching costs (where changing actions incurs a penalty). They demonstrated a fundamental gap: while switching costs are manageable under full information, they force a much harsher $\Theta(T^{2/3})$ regret in bandit settings, highlighting the difficulty of maintaining high-confidence stability when feedback is limited and actions are constrained. Conversely, Jason Altschuler et al. proved that even with these switching constraints, the minimax optimal regret is still achievable with high confidence, ensuring that learners do not have to sacrifice single-run robustness to accommodate operational constraints.
From Bandits to Structured Environments
As the field has matured, the push for high-probability guarantees has expanded from simple multi-armed bandits into highly structured settings:
- Contextual Bandits: In applications like personalized medicine, decisions are guided by side information (contexts). Shipra Agrawal et al. provided a major milestone by establishing the first high-probability regret bounds for Thompson Sampling with linear payoffs, proving that Bayesian heuristics can be made robust against rare, catastrophic scenarios.
- Adversarial MDPs: In complex environments where state transitions are governed by a Markov Decision Process but rewards change arbitrarily, Aviv Rosenberg et al. introduced
UC-O-REPS. This framework handles convex performance criteria (like risk aversion) while maintaining high-probability safety certificates across volatile deployments. - Delayed Feedback: In distributed or real-world systems, the feedback from an action is often delayed. András György 0001 et al. developed data-adaptive variants of the Exp3 algorithm, proving that high-probability bounds are achievable even when information arrives late and out of order.
Conclusion
High-probability regret analysis transforms online learning from an "on-average" statistical theory into a rigorous framework for risk-sensitive engineering. By designing estimators that explicitly bound variance, clip extreme outliers, and account for adversarial adaptations, these algorithms ensure that their worst-case individual realizations remain safely bounded.