mlsanityData to 7 Oct 2026

Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints

arXiv 2402.01111 ↗First posted 2 Feb 2024cs.LG cs.AI cs.MAcited by 3

Not on the map. Why?

Abstract (arXiv)

We study the problem of multi-agent reinforcement learning (MARL) with adaptivity constraints -- a new problem motivated by real-world applications where deployments of new policies are costly and the number of policy updates must be minimized. For two-player zero-sum Markov Games, we design a (policy) elimination based algorithm that achieves a regret of widetildeO(√H3 S2 ABK), while the batch complexity is only O(H+loglog K). In the above, S denotes the number of states, A,B are the number of actions for the two players respectively, H is the horizon and K is the number of episodes. Furthermore, we prove a batch complexity lower bound Omega(fracHlogAK+loglog K) for all algorithms with widetildeO(√K) regret bound, which matches our upper bound up to logarithmic factors. As a byproduct, our techniques naturally extend to learning bandit games and reward-free MARL within near optimal batch complexity. To the best of our knowledge, these are the first line of results towards understanding MARL with low adaptivity.

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

Builds on

54 of 75 references.

References · 54

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  4. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  5. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  6. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  7. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  8. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  9. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  10. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  11. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  12. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
38 more
  1. 2019Batched Multi-armed Bandits Problemcited by 97
  2. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  3. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  4. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  5. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  6. 2020Towards Playing Full MOBA Games with Deep Reinforcement Learningcited by 78
  7. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  8. 2020Adaptive Reward-Free Explorationcited by 77
  9. 2020Sequential Batch Learning in Finite-Action Linear Contextual Banditscited by 63
  10. 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 60
  11. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  12. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  13. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  14. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  15. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  16. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  17. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  18. 2020Task-agnostic Exploration in Reinforcement Learningcited by 37
  19. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  20. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  21. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  22. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  23. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 28
  24. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  25. 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26
  26. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  27. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  28. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  29. 2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
  30. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  31. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  32. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 13
  33. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  34. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  35. 2020Distributed Deep Reinforcement Learning for Intelligent Load Scheduling in Residential Smart Gridscited by 10
  36. 2022Doubly Fair Dynamic Pricingcited by 8
  37. 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPscited by 8
  38. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

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

3 papers.

  1. 2024Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizescited by 12
  2. 2024Differentially Private Reinforcement Learning with Self-Playcited by 1
  3. 2026EvoNash-MARL: A Closed-Loop Multi-Agent Reinforcement Learning Framework for Medium-Horizon Equity Allocationcited by 1