TL;DR
This paper introduces a surprisingly simple framework for achieving high-probability regret bounds in adversarial bandit problems and Markov Decision Processes (MDPs). By ditching the complex "biased" loss estimators typically used in this field and instead combining standard unbiased estimators with an increasing learning rate and geometric "lifting" techniques, the authors achieve state-of-the-art, data-dependent performance guarantees.
The Challenge of High-Probability Regret
In online learning with bandit feedback, a learner repeatedly chooses actions and only observes the loss for the chosen action. Most research focuses on expected regret—how much worse the learner performs compared to the best fixed action on average. However, in real-world applications, variance matters. An algorithm might boast excellent average performance but fail catastrophically in a single, unlucky run.
To mitigate this, researchers seek high-probability regret bounds, which guarantee performance even in worst-case scenarios. This is especially critical when facing an adaptive adversary—an opponent who dynamically changes their strategy based on the learner's past moves.
Traditionally, securing these bounds required "biased" loss estimators. By intentionally underestimating losses, algorithms could artificially reduce variance. While effective, these estimators are mathematically cumbersome and often lead to "worst-case" bounds that fail to capitalize on "easy" environments where the best action has a very small total loss.
A Simpler Method: Online Mirror Descent
The authors propose a novel approach based on Online Mirror Descent (OMD). Their framework relies on three key mathematical pillars:
- Unbiased Estimators + Increasing Learning Rate: Instead of biasing the estimator, the authors use standard importance-weighted (unbiased) estimators. To handle the resulting high variance, they employ a learning rate that increases whenever the "uncertainty" (measured by the Hessian of the regularizer) becomes too large. This dynamic adjustment elegantly cancels out the large variance terms in the mathematical analysis.
- Geometric Lifting: For linear bandits, the authors "lift" the problem from $d$ dimensions to $d+1$ dimensions. This allows them to use a logarithmically homogeneous self-concordant barrier (a "normal barrier") as a regularizer. This geometric trick ensures the variance of their estimators stays mathematically manageable.
- Strengthened Freedman’s Inequality: The authors develop a new version of a classic concentration inequality for martingales. Their strengthened version allows the upper bound of the random variables to be a random variable itself (provided it is predictable), which is essential for analyzing their adaptive learning rate schedule.
Key Insights
- "Bias No More": The most significant breakthrough is the realization that biased estimators—long thought to be a strict necessity for high-probability bounds—are actually optional. A smart learning rate schedule can do the heavy lifting.
- Small-Loss Bounds: The paper focuses on "data-dependent" bounds. Instead of the regret scaling strictly with the total time $T$ (e.g., $\sqrt{T}$), it scales with the loss of the best action $L^*$. If the best action is very good (small $L^*$), the algorithm learns much faster.
- Efficiency for Linear Bandits: Previous high-probability algorithms for linear bandits were either computationally inefficient (impossible to run in practice) or only worked for very specific shapes (like spheres). This approach provides the first general and efficient algorithm for any convex action set.
Theoretical Results
The authors provide high-probability regret bounds for three major settings, advancing the theoretical frontier in each:
- Multi-armed Bandits (MAB): They achieve a small-loss bound of $\tilde{O}(\sqrt{dL^* \ln(d/\delta)})$, matching the best-known results but with a significantly simpler algorithm.
- Adversarial Linear Bandits: They provide the first efficient algorithm with a high-probability bound of $\tilde{O}(d\sqrt{\nu L^*})$, where $\nu$ is a parameter related to the complexity of the action set.
- Adversarial MDPs: They deliver the first high-probability small-loss bound for MDPs with unknown transitions, scaling with $\tilde{O}(|X|\sqrt{J|A|L^*})$, where $|X|$ is the state space and $|A|$ is the action space.
Limitations and Future Work
While a major theoretical step forward, the paper notes a few limitations. In the linear bandit setting, the regret bound has a slightly higher dependence on the dimension $d$ compared to non-efficient algorithms; reducing this dependence remains an open problem. Additionally, while they provide the first small-loss bound for MDPs, it is currently unknown if this bound is "minimax optimal" (the best possible bound theoretically achievable). Finally, as a purely theoretical work, future empirical validation will be needed to see how these algorithms perform in real-world software implementations compared to traditional biased-estimator methods.
Summary updated