mlsanityData to 7 Oct 2026

Cooperative Online Learning in Stochastic and Adversarial MDPs

arXiv 2201.13170 ↗First posted 31 Jan 2022cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We study cooperative online learning in stochastic and adversarial Markov decision process (MDP). That is, in each episode, m agents interact with an MDP simultaneously and share information in order to minimize their individual regret. We consider environments with two types of randomness: fresh -- where each agent's trajectory is sampled i.i.d, and non-fresh -- where the realization is shared by all agents (but each agent's trajectory is also affected by its own actions). More precisely, with non-fresh randomness the realization of every cost and transition is fixed at the start of each episode, and agents that take the same action in the same state at the same time observe the same cost and next state. We thoroughly analyze all relevant settings, highlight the challenges and differences between the models, and prove nearly-matching regret lower and upper bounds. To our knowledge, we are the first to consider cooperative reinforcement learning (RL) with either non-fresh randomness or in adversarial MDPs.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 36 of its 67 references that are in the map. First posted on arXiv 31 Jan 2022.

Builds on

36 of 67 references.

References · 36

  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. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  5. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 189
  6. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  7. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  8. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  9. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  10. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  11. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  12. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
24 more
  1. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  2. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  3. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  4. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  5. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  6. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  7. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  8. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  9. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  10. 2016Delay and Cooperation in Nonstochastic Banditscited by 71
  11. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  12. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  13. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  14. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  15. 2020Distributed Cooperative Decision Making in Multi-agent Multi-armed Banditscited by 38
  16. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  17. 2020Cooperative Multi-Agent Bandits with Heavy Tailscited by 31
  18. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  19. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  20. 2019Individual Regret in Cooperative Nonstochastic Multi-Armed Banditscited by 20
  21. 2021One More Step Towards Reality: Cooperative Bandits with Imperfect Communicationcited by 15
  22. 2020Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisionscited by 13
  23. 2021Confidence-Budget Matching for Sequential Budgeted Learningcited by 11
  24. 2021Provably Efficient Multi-Agent Reinforcement Learning with Fully Decentralized Communicationcited by 5

Built on by

Cited by year (2026 to 7 Oct)

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

4 papers.

  1. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  2. 2026A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guaranteescited by 3
  3. 2026The Horizon Threshold in Cooperative Multi-Agent Reward-Free Explorationcited by 0
  4. 2026Collaborating in Multi-Armed Bandits with Strategic Agentscited by 0