Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learning
This addresses a practical problem for researchers and practitioners in reinforcement learning dealing with large-scale multi-agent systems, though it is incremental as it builds on existing work in planning with linear function approximation.
The paper tackles the computational challenge of planning in combinatorial action spaces, such as those in cooperative multi-agent reinforcement learning, by proposing efficient algorithms that achieve polynomial compute and query complexity in all relevant problem parameters, with further improvements for additive feature decompositions and extensions to kernelized settings.
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.