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

arXiv: https://arxiv.org/abs/2410.15156 · HTML: https://mlsanity.com/paper/2410.15156/

## 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 (most cited first, 16 of 16)

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Fictitious play in zero-sum stochastic games](https://mlsanity.com/paper/2010.04223/) (2020)
- [Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2211.17116/) (2022)
- [How to Combine Tree-Search Methods in Reinforcement Learning](https://mlsanity.com/paper/1809.01843/) (2018)
- [On the convergence of optimistic policy iteration for stochastic shortest path problem](https://mlsanity.com/paper/1808.08763/) (2018)
- [On the Convergence of Reinforcement Learning with Monte Carlo Exploring Starts](https://mlsanity.com/paper/2007.10916/) (2020)
- [On The Convergence Of Policy Iteration-Based Reinforcement Learning With Monte Carlo Policy Evaluation](https://mlsanity.com/paper/2301.09709/) (2023)
- [Distributed Asynchronous Policy Iteration for Sequential Zero-Sum Games and Minimax Control](https://mlsanity.com/paper/2107.10406/) (2021)
- [Markov α-Potential Games](https://mlsanity.com/paper/2305.12553/) (2023)
- [The Role of Lookahead and Approximate Policy Evaluation in Reinforcement Learning with Linear Value Function Approximation](https://mlsanity.com/paper/2109.13419/) (2021)
- [Kullback-Leibler-Quadratic Optimal Control](https://mlsanity.com/paper/2004.01798/) (2020)
- [Reinforcement Learning with Unbiased Policy Evaluation and Linear Function Approximation](https://mlsanity.com/paper/2210.07338/) (2022)
- [Episodic Logit-Q Dynamics for Efficient Learning in Stochastic Teams](https://mlsanity.com/paper/2205.13266/) (2022)

## 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.