Policy Iteration

Follow this topic Ask about this topic

Momentum

2 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 13

All topics

Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy
Sep 30, 2026Han Zhong, Yinyu YeMarkov Decision Processes Policy Iteration
Shanghai Jiao Tong University. · Shanghai Jiao Tong University, SIMIS, and Stanford University.
Learning to Solve Stochastic Controls with Unknown Drifts and Running Rewards: Theory, Algorithms and Convergence
Sep 14, 2026Jin Ma, Gaozhan Wang, Jianfeng Zhang +1Reinforcement Learning Stochastic Optimal Control
Department of Mathematics, University of Southern California, Los Angeles, CA 90089 · Department of Industrial Engineering and Operations Research, Columbia University, New York, NY 10027
Exact Model-Free Policy Iteration for Co-safe LTL Planning
Aug 5, 2026Zetong Xuan, Yu WangReinforcement Learning Policy Iteration
Department of Mechanical and Aerospace Engineering, University of Florida, Gainesville, FL 32611 USA
Scalar-Stepsize Nonuniform Monte Carlo Optimistic Policy Iteration: A Certified Counterexample
Jun 14, 2026Yuanlong ChenMarkov Decision Processes Policy Optimization
Convergence of Monte Carlo Optimistic Policy Iteration: Beyond Uniform State-Action Updates
Jun 9, 2026Octave Oliviers, Glenn VinnicombeMarkov Decision Processes Reinforcement Learning
Department of Engineering University of Cambridge Cambridge, UK
Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework
May 11, 2026Phalguni Nanda, Zaiwei ChenPolicy Gradient Reinforcement Learning
Edwardson School of Industrial Engineering, Purdue University
Approximate Next Policy Sampling: Replacing Conservative Target Policy Updates in Deep RL
May 6, 2026Dillon Sandhu, Ronald ParrPolicy Optimization Policy Iteration
Department of Computer Science, Duke University, USA
Algorithms for Deciding the Safety of States in Fully Observable Non-deterministic Problems: Technical Report
Mar 16, 2026Johannes Schmalz, Chaahat JainPolicy Iteration Model-Based Planning
Saarland University, Germany
Iterative GRPO: Batch-Online Policy Iteration for Multi-Turn RL via Single-Turn RLHF
Nov 26, 2025Daniel R. Jiang, Ankur Samanta, Yukai Yang +3Reinforcement Learning Policy Iteration
Meta · FAIR at Meta
Continuous Policy and Value Iteration for Stochastic Control Problems and Its Convergence
Jun 9, 2025Qi Feng, Gu WangStochastic Optimal Control Policy Iteration
Department of Mathematics, Florida State University, Tallahassee, 32306 · Department of Mathematical Sciences, Worcester Polytechnic Institute, Worcester, MA 01609
Gaussian process policy iteration with additive Schwarz acceleration for forward and inverse HJB and mean field game problems
May 1, 2025Xianjin Yang, Jingguo ZhangMean Field Games Stochastic Optimal Control
Department of Computing and Mathematical Sciences, California Institute of Technology, CA, USA. · Department of Mathematics and Risk Management Institute, National University of Singapore, Singapore.
Bridging the Gap between Newton-Raphson Method and Regularized Policy Iteration
Oct 11, 2023Zeyang Li, Chuxiong Hu, Yunan Wang +4Markov Decision Processes Reinforcement Learning
Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, United States · Department of Mechanical Engineering, Tsinghua University, Beijing 100084, China · College of Artificial Intelligence and the School of Vehicle and Mobility, Tsinghua University, Beijing 100084, China
Monotone Neural Policy Iteration for High-Dimensional First-Order Hamilton--Jacobi--Bellman Equations
Date pendingMinseok Kim, Yeongjong Kim, Namkyeong Cho +1Neural PDE Solvers Stochastic Optimal Control
Department of Applied Artificial Intelligence, Seoul National University of Science and Technology, Seoul, Republic of Korea. · Department of Mathematics, Pohang University of Science and Technology, Pohang, Republic of Korea. · Department of Mathematical Finance and Big Data, Gachon University, Seongnam, Republic of Korea +1

Sep 30, 2026, cs.LGJ/K move · Enter open · S save

Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy

Han Zhong, Yinyu Ye

Shanghai Jiao Tong University. · Shanghai Jiao Tong University, SIMIS, and Stanford University.

Markov Decision Processes Policy Iteration Linear Markov Decision Processes

Open paper AskPDF arXiv

We establish an exponential iteration lower bound in the number of states for Howard's policy iteration on deterministic discounted Markov decision processes, with at most two actions per state. This rules out strong polynomiality of Howard's policy iteration when the discount factor is part of the input and yields an exponential separation from the simplex method with Dantzig's pivoting rule, which is proved to be strongly polynomial on this class. Even when each reward is restricted to logarithmic bit length, we obtain a stretched-exponential iteration lower bound. The gap between Howard's decentralized and simultaneous selfish improvements and Dantzig's coordinated selection of a single action with the largest gain across all states reveals a ``price'' of algorithmic anarchy.

Momentum

Related topics

Latest papers 13