# No Weighted-Regret Learning in Adversarial Bandits with Delays

arXiv: https://arxiv.org/abs/2103.04550 · HTML: https://mlsanity.com/paper/2103.04550/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 51 references that are in the map.
- First posted on arXiv 8 Mar 2021.

## Builds on (most cited first, 15 of 15)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Linear Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/1807.02089/) (2018)
- [Stochastic Bandit Models for Delayed Conversions](https://mlsanity.com/paper/1706.09186/) (2017)
- [Nonstochastic Multiarmed Bandits with Unrestricted Delays](https://mlsanity.com/paper/1906.00670/) (2019)
- [An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays](https://mlsanity.com/paper/1910.06054/) (2019)
- [Stochastic bandits with arm-dependent delays](https://mlsanity.com/paper/2006.10459/) (2020)
- [Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation](https://mlsanity.com/paper/2006.00475/) (2020)
- [Learning Adversarial Markov Decision Processes with Delayed Feedback](https://mlsanity.com/paper/2012.14843/) (2020)
- [Adapting to Delays and Data in Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2010.06022/) (2020)
- [Multi-scale exploration of convex functions and bandit convex optimization](https://mlsanity.com/paper/1507.06580/) (2015)
- [Gradient-free Online Learning in Games with Delayed Rewards](https://mlsanity.com/paper/2006.10911/) (2020)

## Built on by (most cited first, 12 of 12)

- [Delayed Bandits: When Do Intermediate Observations Help?](https://mlsanity.com/paper/2305.19036/) (2023)
- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs](https://mlsanity.com/paper/2503.19856/) (2025)
- [Exploiting Curvature in Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2506.07595/) (2025)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting](https://mlsanity.com/paper/2305.12131/) (2023)
- [A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees](https://mlsanity.com/paper/2602.02634/) (2026)
- [Risk-Aware Linear Bandits: Theory and Applications in Smart Order Routing](https://mlsanity.com/paper/2208.02389/) (2022)
- [Reinforcement Learning with Action-Triggered Observations](https://mlsanity.com/paper/2510.02149/) (2025)
- [Capacity-Constrained Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2606.11711/) (2026)
- [Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization](https://mlsanity.com/paper/2608.16216/) (2026)
- [Cordial Learning: Distributed Training with Correlated Data](https://mlsanity.com/paper/2610.03330/) (2026)

## Abstract (arXiv)

Consider a scenario where a player chooses an action in each round t out of T rounds and observes the incurred cost after a delay of dt rounds. The cost functions and the delay sequence are chosen by an adversary. We show that in a non-cooperative game, the expected weighted ergodic distribution of play converges to the set of coarse correlated equilibria if players use algorithms that have "no weighted-regret" in the above scenario, even if they have linear regret due to too large delays. For a two-player zero-sum game, we show that no weighted-regret is sufficient for the weighted ergodic average of play to converge to the set of Nash equilibria. We prove that the FKM algorithm with n dimensions achieves an expected regret of Oleft(nT^frac34+√nT^frac13D^frac13right) and the EXP3 algorithm with K arms achieves an expected regret of Oleft(√log Kleft(KT+Dright)right) even when D=sumt=1Tdt and T are unknown. These bounds use a novel doubling trick that, under mild assumptions, provably retains the regret bound for when D and T are known. Using these bounds, we show that FKM and EXP3 have no weighted-regret even for dt=Oleft(tlog tright). Therefore, algorithms with no weighted-regret can be used to approximate a CCE of a finite or convex unknown game that can only be simulated with bandit feedback, even if the simulation involves significant delays.