Policy Iteration

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

Sep 30, 2026cs.LG

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

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.

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

Ask PDF

Sep 14, 2026cs.LG

Learning to Solve Stochastic Controls with Unknown Drifts and Running Rewards: Theory, Algorithms and Convergence

We study continuous-time and possibly high-dimensional stochastic control problems where drift coefficients and running reward functions are unknown. Due to these missing model primitives, we take the exploratory, reinforcement learning (RL) framework of Wang, Zariphopoulou, and Zhou(2020) with relaxed controls and entropy regularization. The objective is to develop theoretically grounded, efficient and scalable RL algorithms to learn both the optimal value functions (which also solve the exploratory HJB equation) and optimal exploratory feedback control policies. When the diffusion coefficients do not contain control, we employ probabilistic representations of both the optimal value function and its gradient based on an auxiliary state process depending only on the diffusion part of the original dynamics. With a delicate analysis on some properly defined mappings and their fixed points, this leads to the introduction of our policy iteration algorithms and their convergence. We demonstrate the performance of our algorithms through various numerical examples. Finally, we study a special control-dependent diffusion case where probability representation of the Hessian is called for.

Jin Ma, Gaozhan Wang, Jianfeng Zhang +1

Department of Mathematics, University of Southern California, Los Angeles, CA 90089 · Department of Industrial Engineering and Operations Research, Columbia University, New York, NY 10027

Reinforcement Learning Stochastic Optimal Control Policy Iteration RL Exploration Maximum Entropy RL Continuous-Time RL

Ask PDF

Aug 5, 2026eess.SY

Exact Model-Free Policy Iteration for Co-safe LTL Planning

This work studies model-free reinforcement learning for co-safe linear temporal logic (sc-LTL) objectives in finite Markov decision processes, which can be reduced to maximal reachability objectives via the standard product construction. For this problem, direct sample-based bootstrap methods (e.g., TD or Q-learning) may fail to converge to optimal policies due to the noncontractive nature and nonuniqueness of solutions to the Bellman equation. We develop a new two-step model-free reinforcement learning method that first uses a discounted surrogate to identify a clamp set that resolves this nonuniqueness, and then applies undiscounted policy evaluation and greedy policy improvement with guarantees of finding an optimal solution. We prove almost-sure convergence of the policy evaluation step and finite termination of the policy iteration algorithm at an optimal policy. These theoretical results are validated through numerical experiments on a stochastic grid world.

Zetong Xuan, Yu Wang

Department of Mechanical and Aerospace Engineering, University of Florida, Gainesville, FL 32611 USA

Reinforcement Learning Policy Iteration Model-Free RL Policy Learning Linear Temporal Logic

Ask PDF

Jun 14, 2026cs.LG

Scalar-Stepsize Nonuniform Monte Carlo Optimistic Policy Iteration: A Certified Counterexample

Tsitsiklis proved convergence of Monte Carlo optimistic policy iteration under a uniform update structure and identified nonuniform update frequencies as a delicate obstruction. We give a certified negative answer for the natural scalar-stepsize, unnormalized asynchronous state-value recursion with fixed nonuniform state-selection probabilities. In a three-state, two-action discounted MDP, the nonuniform update frequencies induce a diagonally scaled greedy-policy mean field with a certified nonconstant attracting hybrid periodic orbit. With a bounded unbiased geometric-horizon estimator and Robbins--Monro stepsizes, the original stochastic recursion remains trapped near the cycle with positive probability and therefore fails to converge. The example pinpoints a geometric obstruction: uniform sampling gives radial residual contraction, whereas scalar nonuniform sampling anisotropically distorts the residual dynamics and can generate switched attracting cycles.

Yuanlong Chen

Markov Decision Processes Policy Optimization Stochastic Approximation Policy Iteration

Ask PDF

Jun 9, 2026cs.LG

Convergence of Monte Carlo Optimistic Policy Iteration: Beyond Uniform State-Action Updates

The asymptotic behaviour of Monte Carlo optimistic policy iteration (MC-O-PI) is a long-standing open question. When the model of the environment is unknown, as is common in practice, the only known condition that guarantees convergence to optimality is impractical. In its canonical form, this condition requires that the episodes used for policy evaluation be initialised uniformly over the entire state-action space. This paper strictly relaxes that requirement. Specifically, we prove that initial-visit MC-O-PI converges to optimality even when updates are uniform only over the actions within each state. This allows episodes to start in different states at arbitrary frequencies; a realistic implementation when the state space is large or unknown but the action space in each state is manageable. The proof departs from the classical analysis of Tsitsiklis whose central commutativity argument no longer applies when states are updated at different frequencies. Instead, we first show that the mean-field dynamics of MC-O-PI generate monotonically improving policies when updates are uniform over the actions in each state, and then prove that noise cannot consistently prevent this improvement by extending the lock-in argument of the combined stability-ODE method. This approach suggests a new way to study optimistic policy-iteration algorithms in general.

Octave Oliviers, Glenn Vinnicombe

Department of Engineering University of Cambridge Cambridge, UK

Markov Decision Processes Reinforcement Learning Policy Optimization Policy Iteration Policy Learning

Ask PDF

May 11, 2026cs.LG

Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework

In this work, we show that natural policy gradient, a core algorithm in reinforcement learning, admits an exact formulation as a smoothed and averaged form of policy iteration. Specifically, we introduce doubly smoothed policy iteration (DSPI), a Bellman-operator framework in which each policy is obtained by applying a regularized greedy step to a weighted average of past

Q

-functions. DSPI includes policy iteration, dual-averaged policy iteration, natural policy gradient, and more general policy dual averaging methods as special cases. Using only monotonicity and contraction of smoothed Bellman operators, we prove distribution-free global geometric convergence of DSPI. Consequently, standard natural policy gradient and policy dual averaging achieve an iteration complexity of

\mathcal{O}((1-γ)^{-1}\log((1-γ)^{-1}ε^{-1}))

for computing an

ε

-optimal policy, without modifying the MDP, adding regularization beyond the mirror map inherent in the update, or using adaptive, trajectory-dependent stepsizes. For the unregularized greedy case, corresponding to dual-averaged policy iteration, we also prove finite termination. The same Bellman-operator framework further extends to discounted MDPs with linear function approximation and stochastic shortest path problems.

Phalguni Nanda, Zaiwei Chen

Edwardson School of Industrial Engineering, Purdue University

Policy Gradient Reinforcement Learning Natural Gradient Methods Policy Optimization Policy Iteration Policy Gradient Methods+1

Ask PDF

May 6, 2026cs.LG

Approximate Next Policy Sampling: Replacing Conservative Target Policy Updates in Deep RL

We revisit a classic "chicken-and-egg" problem in reinforcement learning: to safely improve a policy, the value function must be accurate on the state-visitation distribution of the updated policy. That distribution over states is unknown and cannot be sampled for the purposes of training the value function. Conservative updates solve this problem, but at the cost of shrinking the policy update. This paper explores an alternative solution, Approximate Next Policy Sampling (ANPS), which addresses the problem by modifying the training distribution rather than constraining the policy update. ANPS is satisfied if the distribution of the training data approximates that of the next policy. To demonstrate the feasibility and efficacy of ANPS, we introduce Stable Value Approximate Policy Iteration (SV-API). SV-API modifies the standard approximate policy iteration loop to hold the target policy fixed while an iteratively updated behavioral policy gathers relevant experience. It only commits to a new policy once a convergence criterion has been met. If certain stability criteria are met, the update is guaranteed to be safe; otherwise, it remains no less safe than standard approximate policy iteration. Applying SV-API to PPO yields Stable Value PPO (SV-PPO), which matches or improves performance on high-dimensional discrete (Atari) and continuous control benchmarks while executing substantially larger target policy updates. These results demonstrate the viability of ANPS as a new solution to this classic challenge in RL.

Dillon Sandhu, Ronald Parr

Department of Computer Science, Duke University, USA

Policy Optimization Policy Iteration Proximal Policy Optimization Safe RL Policy Learning

Ask PDF

Mar 16, 2026cs.AI

Algorithms for Deciding the Safety of States in Fully Observable Non-deterministic Problems: Technical Report

Learned action policies are increasingly popular in sequential decision-making, but suffer from a lack of safety guarantees. Recent work introduced a pipeline for testing the safety of such policies under initial-state and action-outcome non-determinism. At the pipeline's core, is the problem of deciding whether a state is safe (a safe policy exists from the state) and finding faults, which are state-action pairs that transition from a safe state to an unsafe one. Their most effective algorithm for deciding safety, TarjanSafe, is effective on their benchmarks, but we show that it has exponential worst-case runtime with respect to the state space. A linear-time alternative exists, but it is slower in practice. We close this gap with a new policy-iteration algorithm iPI, that combines the best of both: it matches TarjanSafe's best-case runtime while guaranteeing a polynomial worst-case. Experiments confirm our theory and show that in problems amenable to TarjanSafe iPI has similar performance, whereas in ill-suited problems iPI scales exponentially better.

Johannes Schmalz, Chaahat Jain

Saarland University, Germany

Policy Iteration Model-Based Planning

Ask PDF

Nov 26, 2025cs.LG

Iterative GRPO: Batch-Online Policy Iteration for Multi-Turn RL via Single-Turn RLHF

Practical LLM agents often operate over multi-turn conversations where success is determined only after the full interaction ends. Most multi-turn RL methods train via on-policy rollouts, but unlike in single-turn RLHF, the policy cannot produce a trajectory alone, since an external environment must respond after each agent turn. For conversational agents, this environment is a user, but real users are generally unavailable inside the training loop and simulated users are difficult to build faithfully. Separately, real-world deployment is rarely fully online or fully offline. The common production pattern is called "batch online," where the current policy is deployed to collect a batch of interaction data, then retrained on that batch and redeployed. We show that this batch-online setting creates an opportunity for applying the classical approximate policy iteration algorithm. Our central observation is that running standard token-level, single-turn GRPO with a learned turn-level

Q

-function as the reward model is a policy improvement step for the multi-turn problem. Building on this, we present Iterative GRPO, which alternates between fitting

Q^π

from logged Monte Carlo returns via standard reward modeling (policy evaluation) and running single-turn GRPO against

Q^π

(policy improvement). During policy improvement, the learned

Q^π

scores candidate responses by their expected downstream return, avoiding the need for simulator rollouts of the remaining conversation. Overall, this allows us to do principled multi-turn RL using only single-turn RLHF methods without an interactive environment or user simulator inside the training loop. We demonstrate the effectiveness of Iterative GRPO on six multi-turn negotiation environments.

Daniel R. Jiang, Ankur Samanta, Yukai Yang +3

Meta · FAIR at Meta

Reinforcement Learning Policy Iteration Policy Learning RL for LLM Agents

Ask PDF

Jun 9, 2025math.OC

Continuous Policy and Value Iteration for Stochastic Control Problems and Its Convergence

We introduce a continuous policy-value iteration algorithm where the approximations of the value function of a stochastic control problem and the optimal control are simultaneously updated through Langevin-type dynamics. This framework applies to both the entropy-regularized relaxed control problems and the classical control problems, with infinite horizon. We establish policy improvement and demonstrate convergence to the optimal control under the monotonicity condition of the Hamiltonian. By utilizing Langevin-type stochastic differential equations for continuous updates along the policy iteration direction, our approach enables the use of distribution sampling and non-convex learning techniques in machine learning to optimize the value function and identify the optimal control simultaneously.

Qi Feng, Gu Wang

Department of Mathematics, Florida State University, Tallahassee, 32306 · Department of Mathematical Sciences, Worcester Polytechnic Institute, Worcester, MA 01609

Stochastic Optimal Control Policy Iteration Optimal Control

Ask PDF

May 1, 2025cs.LG

Gaussian process policy iteration with additive Schwarz acceleration for forward and inverse HJB and mean field game problems

In this paper, we propose a Gaussian Process (GP)-based policy iteration framework for addressing both forward and inverse problems in Hamilton--Jacobi--Bellman (HJB) equations and mean field games (MFGs). Policy iteration is formulated as an alternating procedure between evaluating the value function under a fixed control policy and improving the policy. In our approach, we model the unknown fields using GPs within a policy-iteration framework that converts the nonlinear system into a sequence of linear PDE subproblems. Then, leveraging the linear structure, the updates for the value function and, in the MFG setting, the population density admit explicit representer formulas under linear PDE collocation constraints. The policy is subsequently updated pointwise via a Legendre transform step, which involves a low-dimensional maximization over the control variable. This maximization is explicit for standard quadratic costs. For smooth, strictly convex costs, this pointwise maximization is solved through its first-order optimality condition, whereas in constrained or non-smooth cases, it becomes a low-dimensional constrained maximization problem. To improve convergence, we incorporate the additive Schwarz acceleration as a preconditioning step following each policy update. Numerical experiments demonstrate the effectiveness of the Schwarz acceleration in improving computational efficiency.

Xianjin Yang, Jingguo Zhang

Department of Computing and Mathematical Sciences, California Institute of Technology, CA, USA. · Department of Mathematics and Risk Management Institute, National University of Singapore, Singapore.

Mean Field Games Stochastic Optimal Control Policy Iteration PDE Inverse Problems

Ask PDF

Oct 11, 2023cs.LG

Bridging the Gap between Newton-Raphson Method and Regularized Policy Iteration

Regularization is a cornerstone of modern reinforcement learning. Regularized policy iteration (RPI) provides a fundamental scheme for solving regularized Markov decision processes (RMDPs), and the widely used soft actor-critic algorithm arises as a special case when the regularizer is Shannon entropy. Despite its empirical success, the theoretical underpinnings of RPI remain unclear. In this paper, we address this gap by proving that RPI is formally equivalent to the standard Newton-Raphson method applied to the Bellman equation smoothed by strongly convex regularizers. This equivalence enables a unified convergence analysis of existing methods and supports the development of accelerated algorithms. We show that RPI enjoys local quadratic convergence; notably, for Shannon entropy, the guarantee is dimension-free. We further study RPI with inexact policy evaluation, establishing its equivalence to an inexact Newton method in which each Newton step is solved via truncated iterations, and derive an asymptotic linear convergence rate of

γ^{M}

, where

M

denotes the number of operator steps used in policy evaluation. Finally, motivated by higher-order Newton schemes, we propose a new algorithm for RMDPs that achieves third-order local convergence. Numerical experiments corroborate our theory and demonstrate the practical advantages of the proposed algorithm. Overall, our results advance the theoretical understanding of regularization in reinforcement learning and suggest new directions for efficient algorithm design.

Zeyang Li, Chuxiong Hu, Yunan Wang +4

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

Markov Decision Processes Reinforcement Learning Policy Optimization Policy Iteration Second-Order Optimization

Ask PDF

Date pendingcs.LG

Monotone Neural Policy Iteration for High-Dimensional First-Order Hamilton--Jacobi--Bellman Equations

We analyze a neural semi-discrete method for high-dimensional first-order Hamilton-Jacobi-Bellman (HJB) equations with known or learned dynamics. Centered differences and an artificial viscosity

Nh=O(h)

define a monotone operator evaluated through

2d+1

shifted network queries; policy iteration solves the resulting Bellman equation without a tensor grid. At fixed

h

, the sharp componentwise condition

\max_i|f_i|\le2N

turns every frozen-policy operator into a nearest-neighbor Markov-chain generator with a policy-independent total jump rate. Uniformization gives whole-space well-posedness for measurable feedbacks, an explicit Poisson-tail bound on the numerical domain of dependence, and boundary-free localization. The representation also yields a posteriori policy-evaluation bounds that account for residual and learned-model errors. A greedy-gap analysis controls inexact policy iteration at fixed

h

; a separate consistency estimate connects the semi-discrete equation to the continuous HJB equation. Experiments reproduce the extremal tail, show rates consistent with

O(\sqrt h)

and nearly

h

-independent exact-policy-iteration decay, and assess empirical estimator effectivity. A nonsmooth example shows that the continuous residual can miss a non-viscosity solution, whereas the shifted residual detects the defect. Further tests provide a structured interval-verified certificate calibration, an early-budget benefit of policy freezing for bang-bang control, and learned-dynamics diagnostics. A structured nonlinear problem with active compact-control constraints is tested against a manufactured semi-discrete reference through

d=1024

Minseok Kim, Yeongjong Kim, Namkyeong Cho +1

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

Neural PDE Solvers Stochastic Optimal Control Policy Iteration Optimal Control

Ask PDF

Momentum

Related topics

Latest papers 13