# Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 29 references that are in the map.
- First posted on arXiv 27 Apr 2022.

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

- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [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)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [Adapting to Delays and Data in Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2010.06022/) (2020)
- [Stochastic Bandits with Delay-Dependent Payoffs](https://mlsanity.com/paper/1910.02757/) (2019)
- [Bandit Online Learning with Unknown Delays](https://mlsanity.com/paper/1807.03205/) (2018)
- [An Actor-Critic Contextual Bandit Algorithm for Personalized Mobile Health Interventions](https://mlsanity.com/paper/1706.09090/) (2017)
- [Nonstochastic Bandits with Composite Anonymous Feedback](https://mlsanity.com/paper/2112.02866/) (2021)
- [Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback](https://mlsanity.com/paper/2012.07048/) (2020)
- [Policy Regret in Repeated Games](https://mlsanity.com/paper/1811.04127/) (2018)

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

- [Adversarial Bandits with Multi-User Delayed Feedback: Theory and Application](https://mlsanity.com/paper/2310.11188/) (2023)

## Abstract (arXiv)

We study the adversarial bandit problem with composite anonymous delayed feedback. In this setting, losses of an action are split into d components, spreading over consecutive rounds after the action is chosen. And in each round, the algorithm observes the aggregation of losses that come from the latest d rounds. Previous works focus on oblivious adversarial setting, while we investigate the harder non-oblivious setting. We show non-oblivious setting incurs Omega(T) pseudo regret even when the loss sequence is bounded memory. However, we propose a wrapper algorithm which enjoys o(T) policy regret on many adversarial bandit problems with the assumption that the loss sequence is bounded memory. Especially, for K-armed bandit and bandit convex optimization, we have O(T2/3) policy regret bound. We also prove a matching lower bound for K-armed bandit. Our lower bound works even when the loss sequence is oblivious but the delay is non-oblivious. It answers the open problem proposed in citewang2021adaptive, showing that non-oblivious delay is enough to incur tildeOmega(T2/3) regret.