# Non-stochastic Bandits With Evolving Observations

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 37 references that are in the map.
- First posted on arXiv 27 May 2024.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [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)
- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [Nonstochastic Multiarmed Bandits with Unrestricted Delays](https://mlsanity.com/paper/1906.00670/) (2019)
- [Stochastic bandits with arm-dependent delays](https://mlsanity.com/paper/2006.10459/) (2020)
- [Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions](https://mlsanity.com/paper/2106.02436/) (2021)
- [Learning Adversarial Markov Decision Processes with Delayed Feedback](https://mlsanity.com/paper/2012.14843/) (2020)
- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [Adapting to Delays and Data in Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2010.06022/) (2020)
- [Prediction with Corrupted Expert Advice](https://mlsanity.com/paper/2002.10286/) (2020)
- [A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback](https://mlsanity.com/paper/2206.14906/) (2022)
- [Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism](https://mlsanity.com/paper/2012.11579/) (2020)
- [Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2201.13172/) (2022)
- [On Optimal Robustness to Adversarial Corruption in Online Decision Problems](https://mlsanity.com/paper/2109.10963/) (2021)
- [Nonstochastic Bandits and Experts with Arm-Dependent Delays](https://mlsanity.com/paper/2111.01589/) (2021)
- [Nonstochastic Bandits with Composite Anonymous Feedback](https://mlsanity.com/paper/2112.02866/) (2021)
- [A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs](https://mlsanity.com/paper/2305.08629/) (2023)
- [A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays](https://mlsanity.com/paper/2308.10675/) (2023)
- [Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback](https://mlsanity.com/paper/2012.07048/) (2020)
- [Adversarial Online Learning with noise](https://mlsanity.com/paper/1810.09346/) (2018)
- [Uniswap Liquidity Provision: An Online Learning Approach](https://mlsanity.com/paper/2302.00610/) (2023)

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

- [Contextual Linear Bandits with Delay as Payoff](https://mlsanity.com/paper/2502.12528/) (2025)
- [Decentralized Online Convex Optimization with Unknown Feedback Delays](https://mlsanity.com/paper/2601.07901/) (2026)
- [On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback](https://mlsanity.com/paper/2503.05662/) (2025)
- [Pooling and Drift in Delayed Bandits](https://mlsanity.com/paper/2609.01761/) (2026)

## Abstract (arXiv)

We introduce a novel online learning framework that unifies and generalizes pre-established models, such as delayed and corrupted feedback, to encompass adversarial environments where action feedback evolves over time. In this setting, the observed loss is arbitrary and may not correlate with the true loss incurred, with each round updating previous observations adversarially. We propose regret minimization algorithms for both the full-information and bandit settings, with regret bounds quantified by the average feedback accuracy relative to the true loss. Our algorithms match the known regret bounds across many special cases, while also introducing previously unknown bounds.