Research map / Optimization / Nonconvex and smooth optimization
Convergence of Fast Policy Iteration in Markov Games and Robust MDPs
Keith Badger, Jefferson Huang, Marek Petrik
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use RCPI instead of value iteration | policy iteration for MGs and RMDPs · Markov games (large) | median runtime (s): 253.0 -> 2.3 | Improved |
| use RCPI-infinity instead of value iteration | policy iteration for MGs and RMDPs · Inventory RMDP (large) | median runtime (s): 23629.6 -> 84.8 | Improved |
| use RCPI-infinity instead of value iteration | policy iteration for MGs and RMDPs · Gambler's Ruin RMDP (large) | median runtime (s): 106.6 -> 54.3 | Improved |
| add recovery steps to RCPI (m unbounded vs m=0) (ablation) | policy iteration for MGs and RMDPs · Inventory RMDP (large) | median runtime (s): 87.8 -> 84.8 | No clear effect |
| use RCPI instead of Filar-Tolwinski | policy iteration for MGs and RMDPs · Gambler's Ruin RMDP (large) | median runtime (s): 77.1 -> 54.3 | Improved |
| use RCPI instead of PAI | policy iteration for MGs and RMDPs · Inventory problems | Bellman residual | Improved |
| use RCPI instead of Hoffman-Karp | policy iteration for MGs and RMDPs · Gambler's Ruin RMDP (small) | median runtime (s): 14.4 -> 4.7 | Improved |
| use RCPI instead of Winnicki-Srikant | policy iteration for MGs and RMDPs · Markov Games (small) | median runtime (s): 1.0 -> 0.3 | Improved |
| use WS or VI instead of closed-form evaluation | policy iteration for MGs and RMDPs · Gambler's Ruin RMDP (small) | median runtime (s): RCPI 4.7 vs WS 5.2 vs VI 8.7 | Mixed |
| use Armijo line search (FT) instead of pure Newton (PAI) | policy iteration for MGs and RMDPs · Markov game of Example 4.1 | convergence | Hurt |
| use PAI instead of FT | policy iteration for MGs and RMDPs · Inventory problems | Bellman residual | Mixed |
Closest papers by meaning
- Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs (NeurIPS 2023 · similarity 0.89)
- Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.88)
- Efficient Value Iteration for s-rectangular Robust Markov Decision Processes (ICML 2024 · similarity 0.87)
- Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees (NeurIPS 2025 · similarity 0.87)
- Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.87)
- Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
