mlsanityData to 7 Oct 2026

Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learning

arXiv 2302.04376 ↗First posted 8 Feb 2023cs.LG cs.AI stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

A practical challenge in reinforcement learning are combinatorial action spaces that make planning computationally demanding. For example, in cooperative multi-agent reinforcement learning, a potentially large number of agents jointly optimize a global reward function, which leads to a combinatorial blow-up in the action space by the number of agents. As a minimal requirement, we assume access to an argmax oracle that allows to efficiently compute the greedy policy for any Q-function in the model class. Building on recent work in planning with local access to a simulator and linear function approximation, we propose efficient algorithms for this setting that lead to polynomial compute and query complexity in all relevant problem parameters. For the special case where the feature decomposition is additive, we further improve the bounds and extend the results to the kernelized setting with an efficient algorithm.

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

Builds on

41 of 91 references.

References · 41

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2019Solving Rubik's Cube with a Robot Handcited by 699
  3. 2018QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 697
  4. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  5. 2019Emergent Tool Use From Multi-Agent Autocurriculacited by 308
  6. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  7. 2018Mean Field Multi-Agent Reinforcement Learningcited by 202
  8. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  9. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  10. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  11. 2019Multi-Agent Deep Reinforcement Learning for Large-scale Traffic Signal Controlcited by 159
  12. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
29 more
  1. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  2. 2015High Dimensional Bayesian Optimisation and Bandits via Additive Modelscited by 137
  3. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  4. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  5. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  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. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  9. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  10. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  11. 2021Learning and Planning in Complex Action Spacescited by 76
  12. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  13. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  14. 2020Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routingcited by 61
  15. 2018High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groupscited by 58
  16. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  17. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  18. 2014Near-optimal Reinforcement Learning in Factored MDPscited by 41
  19. 2021Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learningcited by 38
  20. 2021Efficient Local Planning with Linear Function Approximationcited by 21
  21. 2021Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedbackcited by 19
  22. 2021Improved Regret Bound and Experience Replay in Regularized Policy Iterationcited by 18
  23. 2020Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RLcited by 16
  24. 2020Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processescited by 13
  25. 2020PowerNet: Multi-agent Deep Reinforcement Learning for Scalable Powergrid Controlcited by 13
  26. 2021Bias-Robust Bayesian Optimization via Dueling Banditscited by 11
  27. 2021A Short Note on the Relationship of Information Gain and Eluder Dimensioncited by 7
  28. 2020Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Settingcited by 3
  29. 2021Locality Matters: A Scalable Value Decomposition Approach for Cooperative Multi-Agent Reinforcement Learningcited by 3

Built on by

Cited by year (2026 to 7 Oct)

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

6 papers.

  1. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  2. 2024Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learningcited by 9
  3. 2024Efficient Monte Carlo Tree Search via On-the-Fly State-Conditioned Action Abstractioncited by 6
  4. 2025Reinforcement learning with combinatorial actions for coupled restless banditscited by 5
  5. 2026Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learningcited by 1
  6. 2026Latent Spherical Flow Policy for Reinforcement Learning with Combinatorial Actionscited by 0