# Smoothing Policy Iteration for Zero-sum Markov Games

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

## 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 3 Dec 2022.

## Builds on (most cited first, 16 of 16)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2007.07461/) (2020)
- [Distributional Soft Actor-Critic: Off-Policy Reinforcement Learning for Addressing Value Estimation Errors](https://mlsanity.com/paper/2001.02811/) (2020)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [Robust Reinforcement Learning using Adversarial Populations](https://mlsanity.com/paper/2008.01825/) (2020)
- [Risk Averse Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1904.00511/) (2019)
- [Towards General Function Approximation in Zero-Sum Markov Games](https://mlsanity.com/paper/2107.14702/) (2021)
- [Improved Robustness and Safety for Autonomous Vehicle Control with Adversarial Reinforcement Learning](https://mlsanity.com/paper/1903.03642/) (2019)
- [Improving Generalization of Reinforcement Learning with Minimax Distributional Soft Actor-Critic](https://mlsanity.com/paper/2002.05502/) (2020)
- [A Generalized Minimax Q-learning Algorithm for Two-Player Zero-Sum Stochastic Games](https://mlsanity.com/paper/1906.06659/) (2019)
- [Mixed Policy Gradient: off-policy reinforcement learning driven jointly by data and model](https://mlsanity.com/paper/2102.11513/) (2021)
- [Improve Generalization of Driving Policy at Signalized Intersections with Adversarial Learning](https://mlsanity.com/paper/2204.04403/) (2022)
- [Reinforcement Solver for H-infinity Filter with Bounded Noise](https://mlsanity.com/paper/2008.00674/) (2020)

## Abstract (arXiv)

Zero-sum Markov Games (MGs) has been an efficient framework for multi-agent systems and robust control, wherein a minimax problem is constructed to solve the equilibrium policies. At present, this formulation is well studied under tabular settings wherein the maximum operator is primarily and exactly solved to calculate the worst-case value function. However, it is non-trivial to extend such methods to handle complex tasks, as finding the maximum over large-scale action spaces is usually cumbersome. In this paper, we propose the smoothing policy iteration (SPI) algorithm to solve the zero-sum MGs approximately, where the maximum operator is replaced by the weighted LogSumExp (WLSE) function to obtain the nearly optimal equilibrium policies. Specially, the adversarial policy is served as the weight function to enable an efficient sampling over action spaces.We also prove the convergence of SPI and analyze its approximation error in ∞ -norm based on the contraction mapping theorem. Besides, we propose a model-based algorithm called Smooth adversarial Actor-critic (SaAC) by extending SPI with the function approximations. The target value related to WLSE function is evaluated by the sampled trajectories and then mean square error is constructed to optimize the value function, and the gradient-ascent-descent methods are adopted to optimize the protagonist and adversarial policies jointly. In addition, we incorporate the reparameterization technique in model-based gradient back-propagation to prevent the gradient vanishing due to sampling from the stochastic policies. We verify our algorithm in both tabular and function approximation settings. Results show that SPI can approximate the worst-case value function with a high accuracy and SaAC can stabilize the training process and improve the adversarial robustness in a large margin.