Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs

Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei, Mengxiao Zhang

Abstract

We develop a new approach to obtaining high probability regret bounds for online learning with bandit feedback against an adaptive adversary. While existing approaches all require carefully constructing optimistic and biased loss estimators, our approach uses standard unbiased estimators and relies on a simple increasing learning rate schedule, together with the help of logarithmically homogeneous self-concordant barriers and a strengthened Freedman's inequality. Besides its simplicity, our approach enjoys several advantages. First, the obtained high-probability regret bounds are data-dependent and could be much smaller than the worst-case bounds, which resolves an open problem asked by Neu (2015). Second, resolving another open problem of Bartlett et al. (2008) and Abernethy and Rakhlin (2009), our approach leads to the first general and efficient algorithm with a high-probability regret bound for adversarial linear bandits, while previous methods are either inefficient or only applicable to specific action sets. Finally, our approach can also be applied to learning adversarial Markov Decision Processes and provides the first algorithm with a high-probability small-loss bound for this problem.

Introduction

In the realm of online learning, such as the Multi-armed Bandit (MAB) problem, a learner iteratively selects actions and receives feedback. Traditional research has largely focused on expected regret—the average performance gap between the learner and the best fixed action. However, algorithms optimized for average performance, like the famous EXP3, often exhibit high variance, potentially leading to catastrophic failure in individual runs.

To ensure reliability, particularly against adaptive adversaries who adjust their strategies based on the learner's history, high-probability regret bounds are essential. Historically, achieving these bounds necessitated the use of complex, "biased" loss estimators. These estimators are mathematically cumbersome and difficult to generalize to more structured problems like linear bandits or Markov Decision Processes (MDPs). This paper introduces a breakthrough "Bias no more" approach, utilizing standard unbiased estimators coupled with a dynamic learning rate to bridge this gap.

Methodology

The proposed framework moves away from manual bias construction, relying instead on three foundational pillars:

1. Unbiased Estimators and Increasing Learning Rates

Rather than attempting to reduce variance through estimator bias, the authors employ standard unbiased importance-weighted estimators. To mitigate the inherent high variance, they implement a learning rate schedule that increases whenever the "risk" (variance) associated with an action exceeds a certain threshold. This increasing schedule generates a negative term in the regret analysis that effectively cancels out large variance terms.

2. Lifting and Self-Concordant Barriers

For the more complex case of linear bandits, the action set is "lifted" into a higher-dimensional space ($\mathbb{R}^{d+1}$). This allows for the application of logarithmically homogeneous self-concordant barriers. This geometric transformation enables the use of specific regularizers that naturally bound the variance of the estimators within the conic hull of the action space.

Geometric representation of the lifting technique and Dikin ellipsoids used for linear bandits.

3. Strengthened Freedman’s Inequality

The analysis is supported by a new, strengthened version of Freedman’s inequality. This tool is critical for handling random upper bounds on variables, allowing the researchers to prove that the negative terms from the increasing learning rate can reliably offset the variance of unbiased estimators in high-probability settings.

Key Insights and Results

The core innovation lies in variance cancellation: the realization that a carefully tuned increasing learning rate acts as a buffer against the volatility of unbiased estimators. This "template"—combining log-barriers with increasing learning rates—proves versatile across multiple domains.

Data-Dependent "Small-Loss" Bounds

A significant advantage of this approach is the derivation of data-dependent bounds. If the optimal action incurs a small total loss ($L^*$), the algorithm's regret scales with $\sqrt{L^*}$ rather than the worst-case $\sqrt{T}$. This means the algorithm automatically performs better in "easy" environments.

  • Multi-armed Bandits (MAB): Achieved a high-probability small-loss bound of $\tilde{O}(\sqrt{dL^*})$, matching or exceeding previous biased methods.
  • Adversarial Linear Bandits: Resolved a long-standing open problem by providing the first general and efficient algorithm with a high-probability regret bound of $\tilde{O}(d\sqrt{\nu T})$ (where $\nu$ is the barrier parameter).
  • Adversarial MDPs: Established the first high-probability small-loss bound for MDPs with unknown transitions, scaling as $\tilde{O}(|X|\sqrt{J|A|L^*})$.

Discussion and Future Work

While the "Bias no more" approach simplifies the algorithmic design, some challenges remain. The current proofs require tuning the initial learning rate based on the total loss $L^*$, which is typically unknown. Although a "doubling trick" can bypass this, it adds implementation complexity. Furthermore, the regret bounds for adaptive adversaries currently include an extra dependence on the dimension $d$. Future research will focus on reducing this dimensional dependence and investigating the optimality of the scaling factors in the MDP setting.

Summary updated

Abstract

We develop a new approach to obtaining high probability regret bounds for online learning with bandit feedback against an adaptive adversary. While existing approaches all require carefully constructing optimistic and biased loss estimators, our approach uses standard unbiased estimators and relies on a simple increasing learning rate schedule, together with the help of logarithmically homogeneous self-concordant barriers and a strengthened Freedman's inequality. Besides its simplicity, our approach enjoys several advantages. First, the obtained high-probability regret bounds are data-dependent and could be much smaller than the worst-case bounds, which resolves an open problem asked by Neu (2015). Second, resolving another open problem of Bartlett et al. (2008) and Abernethy and Rakhlin (2009), our approach leads to the first general and efficient algorithm with a high-probability regret bound for adversarial linear bandits, while previous methods are either inefficient or only applicable to specific action sets. Finally, our approach can also be applied to learning adversarial Markov Decision Processes and provides the first algorithm with a high-probability small-loss bound for this problem.
BibTeX
@inproceedings{lee2020bias,
  author = {Chung-Wei Lee and Haipeng Luo and Chen-Yu Wei and Mengxiao Zhang},
  title = {{Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=eANXTo7OCj},
}
Figure