Online EXP3 Learning in Adversarial Bandits with Delayed Feedback

Ilai Bistritz, Zhengyuan Zhou, Xi Chen, Nicholas Bambos, Jose H. BlanchetNeurIPS 2019 · OpenReview

Introduction

In standard multi-armed bandit problems, a learner chooses an action (an "arm") and immediately observes the associated cost. However, in real-world applications ranging from high-frequency trading to clinical trials, feedback is frequently delayed. Worse still, an adversary might intentionally manipulate these delays to hinder the learner's performance.

While previous research has explored delays in "full information" settings—where the costs of all possible actions are revealed—this paper tackles the significantly more challenging bandit feedback setting, where the learner only observes the cost of the action actually taken. The core question is: how can a learner maintain "no-regret" performance when forced to make sequential decisions based on stale or missing information? This paper proves that the classic EXP3 algorithm is surprisingly robust to adversarial feedback delays, providing tight regret bounds, a novel adaptive mechanism, and surprising insights into game-theoretic convergence.

Methodology

As a purely theoretical work, the paper relies on rigorous mathematical derivation and regret analysis rather than empirical datasets. The authors focus on adapting and analyzing the EXP3 (Exponential-weight algorithm for Exploration and Exploitation) algorithm under a delayed feedback regime.

  1. EXP3 with Delays: The algorithm maintains probability weights for each arm. When a delayed cost finally arrives, the algorithm retroactively updates the weights based on the historical action.
  2. A Novel Doubling Trick: Standard "doubling tricks," which are typically used to handle unknown time horizons, fail when the delays themselves are unknown. To solve this, the authors propose a new variant that starts a new "epoch" based on the number of missing feedback samples, rather than simply the time elapsed.
  3. Adaptive Step Sizes for Games: For two-player zero-sum games experiencing asynchronous delays, the authors propose using a time-varying step size ($\eta_t$) that is square-summable but not summable (e.g., $\eta_t \approx 1/t$).

Key Insights and Theoretical Results

EXP3 is "Pre-paid" for Delays

A fascinating insight from the analysis is that EXP3 is inherently more robust to delays than full-information algorithms. Because EXP3 already "pays the price" for having limited feedback by exploring, the additional penalty incurred by delayed feedback is relatively small. Specifically, the delay term in the regret bound does not scale with $K$ (the number of arms).

For a known horizon and known delays, EXP3 achieves a regret bound of $O\left(\sqrt{\ln K (KT + \sum_{t=1}^T d_t)}\right)$. This matches the optimal non-delayed regret when delays are relatively small ($d_t \le K$). Furthermore, the authors show that extreme delays extending beyond the total time horizon $T$ are redundant, allowing them to tighten the bound by specifically accounting for missing samples.

Adaptive Regret

When the time horizon and delays are unknown, the proposed doubling trick allows the adaptive EXP3 algorithm to achieve a regret of $O\left(\sqrt{\ln K (K^2T + \sum_{t=1}^T d_t)}\right)$.

Equilibrium vs. No-Regret

Perhaps the most surprising finding is that convergence to a Nash Equilibrium is a more robust property than the no-regret property itself. In a two-player zero-sum game, delays might be so massive (e.g., super-linear delays where $d_t = O(t \log t)$) that players suffer linear regret, effectively "losing" against an adversary. However, the authors prove that as long as the players use the correct adaptive step size $\eta_t$, the ergodic average of their strategy profiles will still reliably converge to the set of Nash Equilibria.

Limitations and Future Directions

While the theoretical contributions are strong, the authors note a few areas for future refinement:

  • The $K^2$ Factor: In the adaptive "doubling trick" scenario, the regret bound includes a $K^2$ factor. The authors conjecture that this bound is loose and could potentially be improved to $K$ with more sophisticated analysis.
  • Asymmetric Players and General Games: The current game-theoretic analysis focuses on two-player zero-sum games. Future work could explore how these delayed dynamics manifest in general-sum games or multi-agent systems with more than two players.
  • Practical Implementation: As a theoretical exposition, the paper does not address the computational and memory overhead required to manage large buffers of delayed feedback in real-world, high-throughput systems.

Summary updated

Abstract

Consider a player that in each of T rounds chooses one of K arms. An adversary chooses the cost of each arm in a bounded interval, and a sequence of feedback delays \left{ d<em>{t}\right} that are unknown to the player. After picking arm a</em>{t} at round t, the player receives the cost of playing this arm d<em>{t} rounds later. In cases where t+d</em>{t}&gt;T, this feedback is simply missing. We prove that the EXP3 algorithm (that uses the delayed feedback upon its arrival) achieves a regret of O\left(\sqrt{\ln K\left(KT+\sum<em>{t=1}^{T}d</em>{t}\right)}\right). For the case where \sum<em>{t=1}^{T}d</em>{t} and T are unknown, we propose a novel doubling trick for online learning with delays and prove that this adaptive EXP3 achieves a regret of O\left(\sqrt{\ln K\left(K^{2}T+\sum<em>{t=1}^{T}d</em>{t}\right)}\right). We then consider a two player zero-sum game where players experience asynchronous delays. We show that even when the delays are large enough such that players no longer enjoy the “no-regret property”, (e.g., where d<em>{t}=O\left(t\log t\right)) the ergodic average of the strategy profile still converges to the set of Nash equilibria of the game. The result is made possible by choosing an adaptive step size \eta</em>{t} that is not summable but is square summable, and proving a “weighted regret bound” for this general case.
BibTeX
@inproceedings{bistritz2019online,
  author = {Ilai Bistritz and Zhengyuan Zhou and Xi Chen and Nicholas Bambos and Jose H. Blanchet},
  title = {{Online EXP3 Learning in Adversarial Bandits with Delayed Feedback}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=1S0Bt0ZNbRq},
}
Figure