mlsanityData to 14 Oct 2026

Simulation-Based Optimistic Policy Iteration For Multi-Agent MDPs with Kullback-Leibler Control Cost

arXiv 2410.15156 ↗First posted 19 Oct 2024cs.AI cs.MA cs.SYcited by 0

Not on the map. Why?

Abstract (arXiv)

This paper proposes an agent-based optimistic policy iteration (OPI) scheme for learning stationary optimal stochastic policies in multi-agent Markov Decision Processes (MDPs), in which agents incur a Kullback-Leibler (KL) divergence cost for their control efforts and an additional cost for the joint state. The proposed scheme consists of a greedy policy improvement step followed by an m-step temporal difference (TD) policy evaluation step. We use the separable structure of the instantaneous cost to show that the policy improvement step follows a Boltzmann distribution that depends on the current value function estimate and the uncontrolled transition probabilities. This allows agents to compute the improved joint policy independently. We show that both the synchronous (entire state space evaluation) and asynchronous (a uniformly sampled set of substates) versions of the OPI scheme with finite policy evaluation rollout converge to the optimal value function and an optimal joint policy asymptotically. Simulation results on a multi-agent MDP with KL control cost variant of the Stag-Hare game validates our scheme's performance in terms of minimizing the cost return.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 16 of its 31 references that are in the map. First posted on arXiv 19 Oct 2024.

Builds on

16 of 31 references.

References · 16

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  2. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
  3. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 58
  4. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  5. 2020Fictitious play in zero-sum stochastic gamescited by 26
  6. 2022Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learningcited by 20
  7. 2018How to Combine Tree-Search Methods in Reinforcement Learningcited by 16
  8. 2018On the convergence of optimistic policy iteration for stochastic shortest path problemcited by 9
  9. 2020On the Convergence of Reinforcement Learning with Monte Carlo Exploring Startscited by 9
  10. 2023On The Convergence Of Policy Iteration-Based Reinforcement Learning With Monte Carlo Policy Evaluationcited by 9
  11. 2021Distributed Asynchronous Policy Iteration for Sequential Zero-Sum Games and Minimax Controlcited by 6
  12. 2023Markov α-Potential Gamescited by 6
4 more
  1. 2021The Role of Lookahead and Approximate Policy Evaluation in Reinforcement Learning with Linear Value Function Approximationcited by 5
  2. 2020Kullback-Leibler-Quadratic Optimal Controlcited by 4
  3. 2022Reinforcement Learning with Unbiased Policy Evaluation and Linear Function Approximationcited by 4
  4. 2022Episodic Logit-Q Dynamics for Efficient Learning in Stochastic Teamscited by 3

Built on by

Not cited yet.