Convergence of Fast Policy Iteration in Markov Games and Robust MDPs

Keith Badger, Marek Petrik, Jefferson Huang

Abstract

Markov games and robust MDPs are closely related models that involve computing a pair of saddle point policies. As part of the long-standing effort to develop efficient algorithms for these models, the Filar-Tolwinski (FT) algorithm has shown considerable promise. As our first contribution, we demonstrate that FT may fail to converge to a saddle point and may loop indefinitely, even in small games. This observation contradicts the proof of FT's convergence to a saddle point in the original paper. As our second contribution, we propose Residual Conditioned Policy Iteration (RCPI). RCPI builds on FT, but is guaranteed to converge to a saddle point. Our numerical results show that RCPI outperforms other convergent algorithms by several orders of magnitude.

Introduction

In standard Reinforcement Learning (MDPs), Policy Iteration is the gold standard for speed, often converging much faster than simple Value Iteration. However, in Markov Games—where an adversary minimizes reward—or Robust MDPs—where one accounts for worst-case model uncertainty—standard optimistic policy iteration methods often fail. They frequently "cycle," where the agent improves its policy, the adversary adapts, and the system returns to a previous state without reaching the optimal saddle point.

For decades, the Filar-Tolwinski (FT) algorithm was considered a reliable "fast" method due to its use of a line search (Armijo’s rule). However, this work debunks that assumption. We show that because the Bellman residual in games is non-differentiable, the line search can trap the algorithm in an infinite loop. This necessitates a new approach that balances the speed of policy iteration with the reliability of Value Iteration.

Methods: Residual Conditioned Policy Iteration (RCPI)

We introduce Residual Conditioned Policy Iteration (RCPI), which ensures convergence through a "safety check" mechanism. The algorithm proceeds in three main steps:

  1. The Fast Step: Similar to FT or PAI, it performs a joint update of both the agent's and the adversary's policies and evaluates the resulting value function.
  2. The Safety Check: Unlike its predecessors, RCPI evaluates the Bellman residual—a measure of value function self-consistency.
  3. The Fallback: If the fast step fails to reduce the residual sufficiently, the algorithm reverts to a standard Value Iteration (VI) backup.

RCPI includes a hyperparameter $m$ (recovery steps). A small $m$ makes the algorithm more conservative, reverting to VI quickly, while a larger $m$ allows more attempts to refine a policy before falling back. This structure guarantees that RCPI's worst-case complexity is no worse than VI, while its practical performance is significantly higher.

Experimental Results

We evaluated RCPI against several baselines, including Value Iteration (VI), Hoffman-Karp (HK), and the Filar-Tolwinski (FT) method across four domains: Random Markov Games, Inventory Management, Gambler’s Ruin, and Gridworld.

Convergence of various algorithms over time. The bottom plot highlights how PAI can fail to converge, while RCPI reaches the tolerance threshold.

The results demonstrate that RCPI is both more reliable and significantly faster than traditional methods. In the Inventory Management domain, for instance, PAI failed to converge, getting stuck in a suboptimal cycle. In contrast, RCPI avoided this cycle and reached the optimal solution efficiently.

Comparison of computation time (seconds) across different domains. RCPI shows massive speedups over Value Iteration in large-scale problems.

As shown in the table above, the performance gap is most pronounced in large-scale problems. In the "Large" Inventory Management task, RCPI solved the environment in approximately 85 seconds, whereas standard Value Iteration required over 23,000 seconds—a speedup of approximately 270x. Furthermore, traditional convergent methods like Hoffman-Karp (HK) often failed to complete within the allotted time for large instances.

Conclusion

RCPI provides a robust and efficient solution for solving Markov Games and Robust MDPs. By conditioning policy updates on the Bellman residual, it avoids the cycling issues that plague previous "fast" methods while maintaining a massive performance advantage over Value Iteration. Future work includes investigating optimal tuning for the recovery step hyperparameter $m$ and extending these convergence guarantees to model-free reinforcement learning settings.

Summary updated

Abstract

Markov games and robust MDPs are closely related models that involve computing a pair of saddle point policies. As part of the long-standing effort to develop efficient algorithms for these models, the Filar-Tolwinski (FT) algorithm has shown considerable promise. As our first contribution, we demonstrate that FT may fail to converge to a saddle point and may loop indefinitely, even in small games. This observation contradicts the proof of FT's convergence to a saddle point in the original paper. As our second contribution, we propose Residual Conditioned Policy Iteration (RCPI). RCPI builds on FT, but is guaranteed to converge to a saddle point. Our numerical results show that RCPI outperforms other convergent algorithms by several orders of magnitude.
BibTeX
@misc{badger2025convergence,
  author = {Keith Badger and Marek Petrik and Jefferson Huang},
  title = {{Convergence of Fast Policy Iteration in Markov Games and Robust MDPs}},
  year = {2025},
  eprint = {2508.06661},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.06661},
}

Loading related content...

Figure