mlsanityData to 14 Oct 2026

Non-stochastic Bandits With Evolving Observations

arXiv 2405.16843 ↗First posted 27 May 2024cs.LGcited by 4

Not on the map. Why?

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.

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

24 of 37 references.

References · 24

  1. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  2. 2013Online Learning under Delayed Feedbackcited by 141
  3. 2018Stochastic bandits robust to adversarial corruptionscited by 119
  4. 2016Delay and Cooperation in Nonstochastic Banditscited by 71
  5. 2018Linear Bandits with Stochastic Delayed Feedbackcited by 55
  6. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  7. 2019Nonstochastic Multiarmed Bandits with Unrestricted Delayscited by 46
  8. 2020Stochastic bandits with arm-dependent delayscited by 36
  9. 2021Stochastic Multi-Armed Bandits with Unrestricted Delay Distributionscited by 34
  10. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  11. 2021Online Learning with Optimism and Delaycited by 33
  12. 2020Adapting to Delays and Data in Adversarial Multi-Armed Banditscited by 29
12 more
  1. 2020Prediction with Corrupted Expert Advicecited by 27
  2. 2022A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedbackcited by 23
  3. 2020Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimismcited by 22
  4. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  5. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 21
  6. 2021Nonstochastic Bandits and Experts with Arm-Dependent Delayscited by 18
  7. 2021Nonstochastic Bandits with Composite Anonymous Feedbackcited by 16
  8. 2023A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPscited by 15
  9. 2023A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delayscited by 11
  10. 2020Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedbackcited by 9
  11. 2018Adversarial Online Learning with noisecited by 7
  12. 2023Uniswap Liquidity Provision: An Online Learning Approachcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 2.

4 papers.

  1. 2025Contextual Linear Bandits with Delay as Payoffcited by 7
  2. 2026Decentralized Online Convex Optimization with Unknown Feedback Delayscited by 2
  3. 2025On Mitigating Affinity Bias through Bandits with Evolving Biased Feedbackcited by 0
  4. 2026Pooling and Drift in Delayed Banditscited by 0