Decentralised Q-Learning for Multi-Agent Markov Decision Processes with a Satisfiability Criterion

• URL: http://arxiv.org/abs/2311.12613v1
• Date: Tue, 21 Nov 2023 13:56:44 GMT
• Title: Decentralised Q-Learning for Multi-Agent Markov Decision Processes with a Satisfiability Criterion
• Authors: Keshav P. Keval, Vivek S. Borkar
• Abstract summary: We propose a reinforcement learning algorithm to solve a multi-agent Markov decision process (MMDP) The goal is to lower the time average cost of each agent to below a pre-specified agent-specific bound.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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.

Related papers

• Approximate Linear Programming for Decentralized Policy Iteration in Cooperative Multi-agent Markov Decision Processes [5.842054972839244]
  We consider a cooperative multi-agent Markov decision process involving m agents. In the policy iteration process of multi-agent setup, the number of actions grows exponentially with the number of agents. We propose approximate decentralized policy iteration algorithms using approximate linear programming with function approximation.
  arXiv  Detail & Related papers  (2023-11-20T14:14:13Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  We study multi-agent reinforcement learning (MARL) for the general-sum Markov Games (MGs) under the general function approximation. We introduce a novel complexity measure called the Multi-Agent Decoupling Coefficient (MADC) for general-sum MGs. We show that our algorithm provides comparable sublinear regret to the existing works.
  arXiv  Detail & Related papers  (2023-10-10T01:39:04Z)
• Deep Multi-Agent Reinforcement Learning for Decentralized Active Hypothesis Testing [11.639503711252663]
  We tackle the multi-agent active hypothesis testing (AHT) problem by introducing a novel algorithm rooted in the framework of deep multi-agent reinforcement learning. We present a comprehensive set of experimental results that effectively showcase the agents' ability to learn collaborative strategies and enhance performance.
  arXiv  Detail & Related papers  (2023-09-14T01:18:04Z)
• Distributed Consensus Algorithm for Decision-Making in Multi-agent Multi-armed Bandit [7.708904950194129]
  We study a structured multi-agent multi-armed bandit (MAMAB) problem in a dynamic environment. A graph reflects the information-sharing structure among agents, and the arms' reward distributions are piecewise-stationary with several unknown change points. The goal is to develop a decision-making policy for the agents that minimizes the regret, which is the expected total loss of not playing the optimal arm at each time step.
  arXiv  Detail & Related papers  (2023-06-09T16:10:26Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees. We study this question in a general framework for interactive decision making with multiple agents. We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making.
  arXiv  Detail & Related papers  (2023-05-01T06:46:22Z)
• Emergence of Theory of Mind Collaboration in Multiagent Systems [65.97255691640561]
  We propose an adaptive training algorithm to develop effective collaboration between agents with ToM. We evaluate our algorithms with two games, where our algorithm surpasses all previous decentralized execution algorithms without modeling ToM.
  arXiv  Detail & Related papers  (2021-09-30T23:28:00Z)
• Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT [106.83952081124195]
  Reinforcement learning (RL) has been widely investigated and shown to be a promising solution for decision-making and optimal control processes. We propose an adaptive ADMM (asI-ADMM) algorithm and apply it to decentralized RL with edge-computing-empowered IIoT networks. Experiment results show that our proposed algorithms outperform the state of the art in terms of communication costs and scalability, and can well adapt to complex IoT environments.
  arXiv  Detail & Related papers  (2021-06-30T16:49:07Z)
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach [128.62787284435007]
  We propose the mean-field proximal policy optimization (MF-PPO) algorithm, at the core of which is a permutation-invariant actor-critic neural architecture. We prove that MF-PPO attains the globally optimal policy at a sublinear rate of convergence. In particular, we show that the inductive bias introduced by the permutation-invariant neural architecture enables MF-PPO to outperform existing competitors.
  arXiv  Detail & Related papers  (2021-05-18T04:35:41Z)
• Multi-Agent Determinantal Q-Learning [39.79718674655209]
  We propose multi-agent determinantal Q-learning. Q-DPP promotes agents to acquire diverse behavioral models. We demonstrate that Q-DPP generalizes major solutions including VDN, QMIX, and QTRAN on decentralizable cooperative tasks.
  arXiv  Detail & Related papers  (2020-06-02T09:32:48Z)
• FACMAC: Factored Multi-Agent Centralised Policy Gradients [103.30380537282517]
  We propose FACtored Multi-Agent Centralised policy gradients (FACMAC) It is a new method for cooperative multi-agent reinforcement learning in both discrete and continuous action spaces. We evaluate FACMAC on variants of the multi-agent particle environments, a novel multi-agent MuJoCo benchmark, and a challenging set of StarCraft II micromanagement tasks.
  arXiv  Detail & Related papers  (2020-03-14T21:29:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.