# Nonstochastic Bandits with Composite Anonymous Feedback

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 40 references that are in the map.
- First posted on arXiv 6 Dec 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (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)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [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)
- [Bandit Online Learning with Unknown Delays](https://mlsanity.com/paper/1807.03205/) (2018)
- [Online Learning with Local Permutations and Delayed Feedback](https://mlsanity.com/paper/1703.04274/) (2017)
- [On the Complexity of Bandit Linear Optimization](https://mlsanity.com/paper/1408.2368/) (2014)
- [Re-examination of Bregman functions and new properties of their divergences](https://mlsanity.com/paper/1803.00641/) (2018)
- [Adversarial Delays in Online Strongly-Convex Optimization](https://mlsanity.com/paper/1605.06201/) (2016)
- [Bandits with Delayed, Aggregated Anonymous Feedback](https://mlsanity.com/paper/1709.06853/) (2017)
- [Online Learning with Composite Loss Functions](https://mlsanity.com/paper/1405.4471/) (2014)
- [Asymptotic Convergence in Online Learning with Unbounded Delays](https://mlsanity.com/paper/1604.05280/) (2016)
- [Learning by Repetition: Stochastic Multi-armed Bandits under Priming Effect](https://mlsanity.com/paper/2006.10356/) (2020)

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

- [Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2201.13172/) (2022)
- [A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs](https://mlsanity.com/paper/2305.08629/) (2023)
- [Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2305.07911/) (2023)
- [Non-stochastic Bandits With Evolving Observations](https://mlsanity.com/paper/2405.16843/) (2024)
- [Dynamical Linear Bandits](https://mlsanity.com/paper/2211.08997/) (2022)
- [Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When Partial Feedback Counts](https://mlsanity.com/paper/2206.00586/) (2022)
- [Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedback](https://mlsanity.com/paper/2303.13604/) (2023)
- [Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback](https://mlsanity.com/paper/2505.24193/) (2025)
- [Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback](https://mlsanity.com/paper/2204.12764/) (2022)
- [Stochastic Contextual Bandits with Long Horizon Rewards](https://mlsanity.com/paper/2302.00814/) (2023)
- [Adversarial Bandits with Multi-User Delayed Feedback: Theory and Application](https://mlsanity.com/paper/2310.11188/) (2023)
- [Learning from Delayed Feedback in Games via Extra Prediction](https://mlsanity.com/paper/2509.22426/) (2025)
- [An Application of Online Learning to Spacecraft Memory Dump Optimization](https://mlsanity.com/paper/2202.06617/) (2022)
- [Multi-Armed Bandits with Generalized Temporally-Partitioned Rewards](https://mlsanity.com/paper/2303.00620/) (2023)
- [Budgeted Recommendation with Delayed Feedback](https://mlsanity.com/paper/2405.11417/) (2024)
- [Linear Convergence in Games with Delayed Feedback via Extra Prediction](https://mlsanity.com/paper/2602.17486/) (2026)

## Abstract (arXiv)

We investigate a nonstochastic bandit setting in which the loss of an action is not immediately charged to the player, but rather spread over the subsequent rounds in an adversarial way. The instantaneous loss observed by the player at the end of each round is then a sum of many loss components of previously played actions. This setting encompasses as a special case the easier task of bandits with delayed feedback, a well-studied framework where the player observes the delayed losses individually. Our first contribution is a general reduction transforming a standard bandit algorithm into one that can operate in the harder setting: We bound the regret of the transformed algorithm in terms of the stability and regret of the original algorithm. Then, we show that the transformation of a suitably tuned FTRL with Tsallis entropy has a regret of order √(d+1)KT, where d is the maximum delay, K is the number of arms, and T is the time horizon. Finally, we show that our results cannot be improved in general by exhibiting a matching (up to a log factor) lower bound on the regret of any algorithm operating in this setting.