Solving Transition-Independent Multi-agent MDPs with Sparse Interactions (Extended version)
In cooperative multi-agent sequential decision making under uncertainty, agents must coordinate to find an optimal joint policy that maximises joint value. Typical algorithms exploit additive structure in the value function, but in the fully-observable multi-agent MDP setting (MMDP) such structure is not present. We propose a new optimal solver for transition-independent MMDPs, in which agents can only affect their own state but their reward depends on joint transitions. We represent these dependencies compactly in conditional return graphs (CRGs). Using CRGs the value of a joint policy and the bounds on partially specified joint policies can be efficiently computed. We propose CoRe, a novel branch-and-bound policy search algorithm building on CRGs. CoRe typically requires less runtime than the available alternatives and finds solutions to problems previously unsolvable.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingDecision Making Under UncertaintySequential Decision MakingSimilar Papers 제목 키워드 기반
Cluster-Based Control of Transition-Independent MDPs
This work studies efficient solution methods for cluster-based control policies of transition-independent Markov decision processes (TI-MDPs). We focus on control of multi-agent systems, whereby a central planner (CP) in…
ClusteringStructural Equivalence and Learning Dynamics in Delayed MARL
We formally establish the equivalence between Observation Delay (OD) and Action Delay (AD) in cooperative partially observable multi-agent systems using observation-action histories. We show that both systems generate id…
Solving Non-Rectangular Reward-Robust MDPs via Frequency Regularization
In robust Markov decision processes (RMDPs), it is assumed that the reward and the transition dynamics lie in a given uncertainty set. By targeting maximal return under the most adversarial model from that set, RMDPs add…
Solving Long-run Average Reward Robust MDPs via Stochastic Games
Markov decision processes (MDPs) provide a standard framework for sequential decision making under uncertainty. However, MDPs do not take uncertainty in transition probabilities into account. Robust Markov decision proce…
Decision MakingDecision Making Under UncertaintySequential Decision MakingMATE: Solving Contextual Markov Decision Processes with Memory of Accumulated Transition Embeddings
We propose MATE, a simple yet effective memory architecture for solving Contextual Markov Decision Processes (CMDPs), a family of MDPs parameterized by an unobserved context. In CMDPs, an optimal agent can adapt online b…