Decentralised Q-Learning for Multi-Agent Markov Decision Processes with
  a Satisfiability Criterion
Keshav P. Keval Vivek S. Borkar
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.