홈 › Papers

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

2023-02-08 · Volodymyr Tkachuk, Seyed Alireza Bakhtiari, Johannes Kirschner, Matej Jusup, Ilija Bogunovic, Csaba Szepesvári

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.

📄 PDF Abstract BibTeX arXiv:2302.04376

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Learning-based Directed Graph Abstraction of Combinatorial Spaces for Order-Preserving Search in Mixed-Combinatorial Nonlinear Optimization

2026-05-31 · Gishnu Madhu, Feng Liu, Souma Chowdhury arxiv

Mixed-combinatorial nonlinear programming (MCNLP) problems arise in many engineering design and planning applications, e.g., due to categorical, component, and geometric design choices, as well as joint task and motion p…

Motion Planning

Decentralized Cooperative Planning for Automated Vehicles with Continuous Monte Carlo Tree Search

2018-09-10 · Karl Kurzer, Florian Engelhorn, J. Marius Zöllner

Urban traffic scenarios often require a high degree of cooperation between traffic participants to ensure safety and efficiency. Observing the behavior of others, humans infer whether or not others are cooperating. This …

Reinforcement learning with combinatorial actions for coupled restless bandits

2025-03-01 · Lily Xu, Bryan Wilder, Elias B. Khalil, Milind Tambe

Reinforcement learning (RL) has increasingly been applied to solve real-world planning problems, with progress in handling large state spaces and time horizons. However, a key bottleneck in many domains is that RL method…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Sequential Decision Making

Distributed Policy Iteration for Scalable Approximation of Cooperative Multi-Agent Policies

2019-01-25 · Thomy Phan, Kyrill Schmid, Lenz Belzner, Thomas Gabor 외

Decision making in multi-agent systems (MAS) is a great challenge due to enormous state and joint action spaces as well as uncertainty, making centralized control generally infeasible. Decentralized control offers better…

Decision Making Multi-agent Reinforcement Learning Reinforcement Learning

Solving routing problems for multiple cooperative Unmanned Aerial Vehicles using Transformer networks, vol. 122, pp. 106085, 2023

2023-03-09 · Engenieering of Artificial Intelligence Applications 2023 3 · Daniel Fuertes, Carlos R. del Blanco, Fernando Jaureguizar, Juan José Navarro 외

Missions involving Unmanned Aerial Vehicle usually consist of reaching a set of regions, performing some actions in each region, and returning to a determined depot after all the regions have been successfully visited or…

Combinatorial Optimization Deep Reinforcement Learning Multi-agent Reinforcement Learning