mlsanityData to 7 Oct 2026

A Reduction-based Framework for Sequential Decision Making with Delayed Feedback

arXiv 2302.01477 ↗First posted 3 Feb 2023cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

We study stochastic delayed feedback in general multi-agent sequential decision making, which includes bandits, single-agent Markov decision processes (MDPs), and Markov games (MGs). We propose a novel reduction-based framework, which turns any multi-batched algorithm for sequential decision making with instantaneous feedback into a sample-efficient algorithm that can handle stochastic delays in sequential decision making. By plugging different multi-batched algorithms into our framework, we provide several examples demonstrating that our framework not only matches or improves existing results for bandits, tabular MDPs, and tabular MGs, but also provides the first line of studies on delays in sequential decision making with function approximation. In summary, we provide a complete set of sharp results for multi-agent sequential decision making with delayed feedback.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 47 of its 69 references that are in the map. First posted on arXiv 3 Feb 2023.

Builds on

47 of 69 references.

References · 47

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2013Online Learning under Delayed Feedbackcited by 137
  5. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  6. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  7. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  8. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  9. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  10. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  11. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  12. 2019Batched Multi-armed Bandits Problemcited by 97
35 more
  1. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  2. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  3. 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 60
  4. 2018Linear Bandits with Stochastic Delayed Feedbackcited by 55
  5. 2017Stochastic Bandit Models for Delayed Conversionscited by 53
  6. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  7. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  8. 2019Nonstochastic Multiarmed Bandits with Unrestricted Delayscited by 46
  9. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  10. 2019An Optimal Algorithm for Adversarial Bandits with Arbitrary Delayscited by 44
  11. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  12. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  13. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
  14. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  15. 2020Stochastic bandits with arm-dependent delayscited by 36
  16. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  17. 2021Stochastic Multi-Armed Bandits with Unrestricted Delay Distributionscited by 33
  18. 2018Setting up a Reinforcement Learning Task with a Real-World Robotcited by 32
  19. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  20. 2020Adapting to Delays and Data in Adversarial Multi-Armed Banditscited by 29
  21. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  22. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  23. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  24. 2022Delayed Feedback in Generalised Linear Bandits Revisitedcited by 23
  25. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  26. 2020Delay-Aware Multi-Agent Reinforcement Learning for Cooperative and Competitive Environmentscited by 21
  27. 2021Nonstochastic Bandits and Experts with Arm-Dependent Delayscited by 18
  28. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  29. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 14
  30. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  31. 2022Model-Based Reinforcement Learning for Offline Zero-Sum Markov Gamescited by 11
  32. 2022The Complexity of Infinite-Horizon General-Sum Stochastic Gamescited by 10
  33. 2023Delayed Feedback in Kernel Banditscited by 10
  34. 2022Multi-Agent Reinforcement Learning with Reward Delayscited by 9
  35. 2023Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learningcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 2; 2025: 1; 2026: 1.

7 papers.

  1. 2024SpecDec++: Boosting Speculative Decoding via Adaptive Candidate Lengthscited by 73
  2. 2023Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observationscited by 4
  3. 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
  4. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  5. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 2
  6. 2025Rainbow Delay Compensation: A Multi-Agent Reinforcement Learning Framework for Mitigating Delayed Observationcited by 0
  7. 2026Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learningcited by 0