Decentralised Q-learning For Multi-agent Markov Decision Processes With A Satisfiability Criterion

Abstract

In this paper, we propose a reinforcement learning algorithm to solve a multi-agent Markov decision process (MMDP). The goal, inspired by Blackwell's Approachability Theorem, is to lower the time average cost of each agent to below a pre-specified agent-specific bound. For the MMDP, we assume the state dynamics to be controlled by the joint actions of agents, but the per-stage costs to only depend on the individual agent's actions. We combine the Q-learning algorithm for a weighted combination of the costs of each agent, obtained by a gossip algorithm with the Metropolis-Hastings or Multiplicative Weights formalisms to modulate the averaging matrix of the gossip. We use multiple timescales in our algorithm and prove that under mild conditions, it approximately achieves the desired bounds for each of the agents. We also demonstrate the empirical performance of this algorithm in the more general setting of MMDPs having jointly controlled per-stage costs.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keykeval2023decentralised

Related papers

• Scalable Spectral Representations For Multi-agent Reinforcement Learning In Network Mdps (2024)0.00
• Multi-agent Determinantal Q-learning (2020)0.00
• Planning And Learning In Average Risk-aware Mdps (2025)0.00
• Multi-timescale Ensemble Q-learning For Markov Decision Process Policy Optimization (2024)6.34
• Independent And Decentralized Learning In Markov Potential Games (2022)0.00
• A Provably-efficient Model-free Algorithm For Constrained Markov Decision Processes (2021)0.00
• MA2QL: A Minimalist Approach To Fully Decentralized Multi-agent Reinforcement Learning (2022)0.00
• Learning To Collaborate In Markov Decision Processes (2019)0.00