On-Line Policy Iteration with Trajectory-Driven Policy Generation
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.
Rosa: I'm Rosa.
Dev: And I'm Dev, here with Taro.
Rosa: We're looking at the paper: "On-Line Policy Iteration with Trajectory-Driven Policy Generation".
Dev: Here's the gist of the paper. On-Line Policy Iteration with Trajectory-Driven Policy Generation introduces an on-line policy iteration method that generates a sequence of cost-improving policies and corresponding trajectories starting from a given policy, which is motivated by problems requiring repeated solutions from the same initial state <ref:2604.15004#pg2>.
Rosa: The method is fast enough for on-line use and provides a principled way to train neural network-based policies using trajectory data while preserving monotonic cost improvement <ref:2604.15004#pg4>.
Dev: Problem Formulation and Policy Iteration Context The paper considers deterministic finite-horizon optimal control problems defined by the system dynamics xk+1 = fk(xk, uk) and stage costs gk(xk, uk) with a terminal cost gN(xN) <ref:2604.15004#pg2>.
Rosa: The optimal cost function J∗ is computed via dynamic programming (DP), which is computationally prohibitive for many practical problems <ref:2604.15004#pg3>.
Paper summary: Dev: So to wrap up, we're talking about "On-Line Policy Iteration with Trajectory-Driven Policy Generation." The authors introduce this method that generates a sequence of cost-improving policies and trajectories on the fly, which is useful when you have repeated solutions from the same initial state.
Rosa: It’s basically fast enough for real-time use and provides a way to train neural network based policies using that trajectory data while preserving cost improvement.
Dev: The core idea rests on this natural consistency condition they put on the generator G, which ensures the generated policy reproduces the tail of the given trajectory from every state along that trajectory, guaranteeing cost improvement at your starting point.
Rosa: So what does this mean for us? It means for problems like path planning where you keep trying to find a better route from a fixed starting point, this approach is more robust than some prior methods like Learning Model Predictive Control.
Dev: They found it actually has more cost improvement than LMPC in those comparisons and is better suited when you start with a poor initial policy.
Rosa: It combines the ideas of rollout and policy iteration with flexible trajectory based representations, which supports neural network policies, showing effectiveness in both discrete and continuous problems.
Dev: The limitation they mention is that they assume you can get an improved policy by using just a single complete trajectory starting from your initial state.
Rosa: That’s the constraint there. So this paper gives us a structured way to use real operational data to iteratively refine policies while keeping an eye on those cost improvements, and that's what they’re showing us with this on-line policy iteration method.
Conclusion: Rosa: So we've been looking at this paper about on-line policy iteration that generates policies based on actual trajectories, and now we're wrapping up the main points and what this means for us.
Dev: Yeah, it’s titled "On-Line Policy Iteration with Trajectory-Driven Policy Generation," and the authors are showing how you can do this while it's actually running in real time.
Rosa: What they’re doing is taking a starting policy and, at every step, using the actual path taken to generate a better one. It's about making sure that the cost keeps getting lower as you go along.
Dev: Right, and they use this generator to build the next policy based on what happened in that specific trajectory. It’s not just guessing; it’s basing it on real data from the system.
Rosa: The big deal here is that it works well for training policies using trajectory data, especially when those policies are built with neural networks, which is pretty relevant for modern control systems.
Dev: And the results show that this method preserves that cost improvement property even when you're doing it on-line. It’s fast enough for real-time use without taking forever to figure out the next step.
Rosa: So, if you're dealing with problems where you need repeated solutions from the same starting point, this approach gives a principled way to train your AI policies using what the system is actually doing right now.
Dev: Exactly. It moves beyond just solving one problem and shows how to continuously improve the solution based on experience.
Rosa: This opens up some interesting possibilities for path planning and other control problems where you can't easily get a perfect mathematical model upfront, but you have data flowing in constantly.
Yuchao Li, Fei Chen, Yingke Li, Chuchu Fan, Dimitri Bertsekas
Arizona State University · MIT
eess.SY, cs.SY, math.OC
Submitted: 2026-04-16
Updated: 2026-11-04
Code: https://github.com/yuchaotaigu/On-Line-Policy-Iteration
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 90/100
The gist: On-Line Policy Iteration with Trajectory-Driven Policy Generation introduces an on-line policy iteration method that generates a sequence of cost-improving policies and corresponding trajectories…
Key concepts
- Policy Iteration (PI)
- A method that generates a sequence of control strategies ($\pi_0, \pi_1, \dots$) by repeatedly applying a policy and then updating it. This process aims to find an optimal policy by ensuring each new policy yields a lower or equal cost than the previous one.
- Trajectory-Driven Policy Generation
- The core mechanism where a generator ($G$) takes an existing trajectory and uses it to create the next, improved policy. A key requirement is that the new policy must reproduce the future behavior seen in the trajectory from every state along that path, which guarantees cost reduction.
- On-Line Policy Iteration
- An iterative approach designed for real-time use. Instead of solving complex dynamic programming problems fully, it generates policies sequentially in an on-line manner, allowing for fast updates and continuous improvement of the control strategy.
- Cost Improvement Guarantee
- A formal guarantee that after each iteration ($\pi_{\ell+1}$), the cost starting from the initial state ($x_0$) will be less than or equal to the cost from the previous policy ($\pi_{\ell}$). This ensures that every step taken in the on-line process moves toward a better solution.
Terminology
Summary
On-Line Policy Iteration with Trajectory-Driven Policy Generation introduces an on-line policy iteration method that generates a sequence of cost-improving policies and corresponding trajectories starting from a given policy, which is motivated by problems requiring repeated solutions from the same initial state <ref:2604. p. 015004#pg2>. The method is fast enough for on-line use and provides a principled way to train neural network-based policies using trajectory data while preserving monotonic cost improvement <ref:2604. p. 015004#pg4>.
Problem Formulation and Policy Iteration Context
The paper considers deterministic finite-horizon optimal control problems defined by the system dynamics xk+1 = fk(xk, uk) and stage costs gk(xk, uk) with a terminal cost gN(xN) <ref:2604.15004#pg2>. The optimal cost function J∗ is computed via dynamic programming (DP), which is computationally prohibitive for many practical problems <ref:2604. p. 115004#pg3>. Policy iteration (PI) serves as an alternative, generating a sequence of policies π0, π1,. p. 4.. which are improving in the sense that Jπk+1(x0) ≤ Jπk(x0), and PI converges to the optimal policy after N iterations <ref:2604. p. 1 p. 115004#pg4>.
On-Line Policy Generation Mechanism
The on-line PI algorithm starts with a policy π0 and at the lth iteration, it applies this policy to obtain a feasible trajectory, and then uses a generator G to obtain a new policy πl+1 <ref:2604.15004#pg4>. The algorithm involves computing controls ul+1k via minimization steps (Eqs. p. 5 p. 5 10-13) based on the current policy and cost functions <ref:2604. p. 6 p. 615004#pg8>. A natural consistency condition for the generator G ensures that the generated policy reproduces the tail of the given trajectory from every state along that trajectory, which guarantees cost improvement at x0 <ref:2604. p. 6 p. 615004#pg9>.
Guarantees and Variants
Under a mild consistency condition on the generator, Proposition 3.1 guarantees that policies are improving at x0 in the sense that Jπl+1(x0) ≤ Jπl(x0), and the sequence is convergent <ref:2604. p. 615004#pg9>. A simplified on-line PI variant reduces real-time computation by using iteration-dependent constraint sets Uk(xk, µk). p. 9 Furthermore, multiagent on-line PI extends this framework by treating each control component as an agent and performing sequential minimizations to compute the control vector.
Computational Applications and Comparisons
The algorithm is effective in combinatorial optimization problems, such as multidimensional assignment, where it computes cost-improving solutions with computation time less than 70 milliseconds in the worst case <ref:2604.15004#pg10>. In path planning for drones and robotic arms, the method generates significantly improved sequences of policies compared to prior methods like Learning Model Predictive Control (LMPC). p. 2 The stochastic variants extend the framework by replacing deterministic components with sampled distributions, showing convergence properties under consistency assumptions. The method demonstrates robustness across various scenarios involving different obstacle layouts and multi-agent coordination. p. 2
Concluding Remarks
The framework combines rollout and policy iteration ideas with flexible trajectory-based policy representations, supporting neural-network-based policies. Computational results confirm its effectiveness in both discrete and continuous problems, suggesting an interesting subject for further research into the robustness of the framework in the absence of an exact system model. p. 2 The comparison with LMPC suggests that on-line PI is better suited for path-planning problems when initialized from poor policies. p. 6
References
[BC99] Dimitri P. Bertsekas and David A. p. 0 p. 0 Castanon. Rollout algorithms for stochastic scheduling problems
[Bel57] Richard E. Bellman. Dynamic Programming <ref:2604. p. 1 p. 115004#pg4>
[Ber20a] Dimitri Bertsekas. Multiagent value iteration algorithms in dynamic programming and reinforcement learning
[Ber21b] Dimitri P. Bertsekas. On-line policy iteration for infinite horizon dynamic programming <ref:2604. p. 3 p. 315004#pg4>
[Ber21a] Dimitri Bertsekas. Multiagent reinforcement learning: Rollout and policy iteration
[BTW97] Dimitri P. Bertsekas, John N. p. 0 p. 0 Tsitsiklis, and Cynara Wu. Rollout algorithms for combinatorial optimization <ref:2604. p. 0 p. 015004#pg10>
[CA98] Hong Chen and Frank Allg¨ower. A quasi-infinite horizon nonlinear model predictive control scheme with guaranteed stability
[CH21] Peter Corke and Jesse Haviland. Not your grandmother’s toolbox–the robotics toolbox reinvented for Python
[CSD24] Fei Chen, Mayank Sewlia, and Dimos V. Dimarogonas. Cooperative control of heterogeneous multi-agent systems under spatiotemporal constraints
[DFJ11] Dimos V. Dimarogonas, Emilio Frazzoli, and Karl H. Johansson. Distributed event-triggered control for multi-agent systems
[ERL+23] William Emanuelsson, Alejandro Penacho Riveiros, Yuchao Li, Karl H. Johansson, and Jonas M˚artensson. Multiagent rollout with reshuffling for warehouse robots path planning
[HLA+25] Kim Hammar, Yuchao Li, Tansu Alpcan, Emil C. Lupu, and Dimitri Bertsekas. p. 0 p. 0 Adaptive network security policies via belief aggregation and rollout
[KG88] S.S. A. Keerthi and Elmer G. Gilbert. Optimal infinite-horizon feedback laws for a general class of constrained discrete-time systems: Stability and moving-horizon approximations
[Kha86] Oussama Khatib. Real-time obstacle avoidance for manipulators and mobile robots
[KSP22] Alla Kammerdiner, Alexander Semenov, and Eduardo L. Pasiliao. Multidimensional assignment problem for multipartite entity resolution
[LJMB21] Yuchao Li, Karl H. Johansson, Jonas M˚artensson, and Dimitri P. p. 0 p. 0 Bertsekas. Data-driven rollout for deterministic optimal control
[MLWB24] Pratyusha Musunuru, Yuchao Li, Jamison Weber, and Dimitri Bertsekas. An approximate dynamic programming framework for occlusion-robust multi-object tracking
[OSFM07] Reza Olfati-Saber, J. Alex Fax, and Richard M. Murray. Consensus and cooperation in networked multi-agent systems
[RB17] Ugo Rosolia and Francesco Borrelli. Learning model predictive control for iterative tasks: A data-driven control framework
[RB19] Ugo Rosolia and Francesco Borrelli. Learning how to autonomously race a car: a predictive control approach
[RLM+22] Ugo Rosolia, Yingzhao Lian, Emilio T. Maddalena, Giancarlo Ferrari-Trecate, and Colin N. Jones. On the optimality and convergence properties of the iterative learning model predictive controller
[SD87] Mario Sznaier and Mark J. Damborg. Suboptimal control of linear systems with state and control inequality constraints
[Sec01] Nicola Secomandi. A rollout policy for the vehicle routing problem with stochastic demands
[SGG+15] Bruno Scherrer, Mohammad Ghavamzadeh, Victor Gabillon, Boris Lesner, and Matthieu Geist. Approximate modified policy iteration and its application to the game of Tetris
[SHM+16] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot et al. Mastering the game of Go with deep neural networks and tree search
[SSS+17] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker et al. Mastering the game of Go without human knowledge
[SWD+17] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms
[Tes95] Gerald Tesauro. Temporal difference learning and TD-Gammon
[TG96] Gerald Tesauro and Gregory R. Galperin. On-line policy improvement using Monte-Carlo search
Page 1
On-Line Policy Iteration with Trajectory-Driven Policy Generation introduces an on-line policy iteration method that generates a sequence of cost-improving policies and corresponding trajectories starting from a given policy, which is motivated by problems requiring repeated solutions from the same initial state <ref:2604.15004#pg2>. The method is fast enough for on-line use and provides a principled way to train neural network-based policies using trajectory data <ref:2604. p. 015004#pg4>.
Pruning redundant reasoning tokens
The paper considers deterministic finite-horizon optimal control problems with a fixed initial state, where the state evolves according to xk+1 = fk(xk, uk) <ref:2604.15004#pg2>. The cost of a policy π starting from x0 is given by Jπ(x0) = gN(xN) + Σgk(xk, µk(xk)) <ref:2604. p. 115004#pg3>. The optimal cost function J∗ is computed via dynamic programming (DP), which is computationally prohibitive for most practical problems <ref:2604. p. 115004#pg4>. Policy iteration (PI) generates a sequence of policies π0, π1,. p. 4.. which are improving in the sense that Jπk+1(x0) ≤ Jπk(x0), and PI converges to the optimal policy after N iterations <ref:2604.15004#pg4>.
How the training signal is built
The on-line PI algorithm starts with a given policy π0 and at the lth iteration, it applies this policy to obtain a corresponding feasible trajectory, and then uses a generator G to obtain a new policy πl+1 <ref:2604.15004#pg4>. The algorithm involves computing controls ul+1k via minimization steps (Eqs. 10-13) based on the current policy and cost functions <ref:2604.15004#pg8>. A natural consistency condition for the generator G ensures that the generated policy reproduces the tail of the given trajectory from every state along that trajectory, which guarantees cost improvement at x0 <ref:2604.15004#pg9>.
Where the gains come from
The method's gains stem from combining rollout and policy iteration ideas with flexible trajectory-based policy representations and supports neural-network-based policies. The simplified variant reduces real-time computation while preserving the cost improvement property, and multiagent on-line PI extends this framework to handle multiagent control by performing sequential minimizations. p. 0 Computational studies show its effectiveness in discrete optimization and path planning problems, achieving significant cost reduction in all tested cases <ref:2604. p. 015004#pg10>. The stochastic extensions further extend the framework by introducing sampled distributions, showing convergence properties under consistency assumptions. The comparison with LMPC indicates that on-line PI is more robust to poor initial policies and has a larger cost improvement than LMPC. p. 0
[BC99] Dimitri P. Bertsekas and David A. Castanon. Rollout algorithms for stochastic scheduling problems
[Bel57] Richard E. Bellman. Dynamic Programming <ref:2604.15004#pg4>
[Ber20a] Dimitri Bertsekas. Multiagent value iteration algorithms in dynamic programming and reinforcement learning
[Ber21b] Dimitri P. Bertsekas. On-line policy iteration for infinite horizon dynamic programming <ref:2604.15004#pg4>
[Ber21a] Dimitri Bertsekas. Multiagent reinforcement learning: Rollout and policy iteration
[BTW97] Dimitri P. Bertsekas, John N. Tsitsiklis, and Cynara Wu. Rollout algorithms for combinatorial optimization <ref:2604.15004#pg10>
[CA98] Hong Chen and Frank Allg¨ower. A quasi-infinite horizon nonlinear model predictive control scheme with guaranteed stability
[CH21] Peter Corke and Jesse Haviland. Not your grandmother’s toolbox–the robotics toolbox reinvented for Python
[CSD24] Fei Chen, Mayank Sewlia, and Dimos V. Dimarogonas. Cooperative control of heterogeneous multi-agent systems under spatiotemporal constraints
[DFJ11] Dimos V. Dimarogonas, Emilio Frazzoli, and Karl H. Johansson. Distributed event-triggered control for multi-agent systems
[ERL+23] William Emanuelsson, Alejandro Penacho Riveiros, Yuchao Li, Karl H. Johansson, and Jonas M˚artensson. Multiagent rollout with reshuffling for warehouse robots path planning
[HLA+25] Kim Hammar, Yuchao Li, Tansu Alpcan, Emil C. Lupu, and Dimitri Bertsekas. Adaptive network security policies via belief aggregation and rollout
[KG88] S.S. A. Keerthi and Elmer G. Gilbert. Optimal infinite-horizon feedback laws for a general class of constrained discrete-time systems: Stability and moving-horizon approximations
[Kha86] Oussama Khatib. Real-time obstacle avoidance for manipulators and mobile robots
[KSP22] Alla Kammerdiner, Alexander Semenov, and Eduardo L. Pasiliao. Multidimensional assignment problem for multipartite entity resolution
[LJMB21] Yuchao Li, Karl H. Johansson, Jonas M˚artensson, and Dimitri P. Bertsekas. Data-driven rollout for deterministic optimal control
[MLWB24] Pratyusha Musunuru, Yuchao Li, Jamison Weber, and Dimitri Bertsekas. An approximate dynamic programming framework for occlusion-robust multi-object tracking
[OSFM07] Reza Olfati-Saber, J. Alex Fax, and Richard M. Murray. Consensus and cooperation in networked multi-agent systems
[RB17] Ugo Rosolia and Francesco Borrelli. Learning model predictive control for iterative tasks: A data-driven control framework
[RB19] Ugo Rosolia and Francesco Borrelli. Learning how to autonomously race a car: a predictive control approach
[RLM+22] Ugo Rosolia, Yingzhao Lian, Emilio T. Maddalena, Giancarlo Ferrari-Trecate, and Colin N. Jones. On the optimality and convergence properties of the iterative learning model predictive controller
[SD87] Mario Sznaier and Mark J. Damborg. Suboptimal control of linear systems with state and control inequality constraints
[Sec01] Nicola Secomandi. A rollout policy for the vehicle routing problem with stochastic demands
[SGG+15] Bruno Scherrer, Mohammad Ghavamzadeh, Victor Gabillon, Boris Lesner, and Matthieu Geist. Approximate modified policy iteration and its application to the game of Tetris
[SHM+16] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre et al. Mastering the game of Go with deep neural networks and tree search
[SSS+17] David Silver, Julian Schrittwieser et al. Mastering the game of Go without human knowledge
[SWD+17] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms
[Tes95] Gerald Tesauro. Temporal difference learning and TD-Gammon
[TG96] Gerald Tesauro and Gregory R. Galperin. On-line policy improvement using Monte-Carlo search
Page 3
The cost of the kth stage is denoted by gk(xk, uk) <ref:2604.15004#pg3>. Upon reaching state xN at the Nth stage, there is a terminal cost gN(xN) <ref:2604. p. 115004#pg3>. The optimal cost starting from x0 is denoted by J∗(x0) = min π∈Π Jπ(x0), where Π is the set of all policies <ref:2604. p. 115004#pg3>.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
On-line Policy Iteration can generate a sequence of cost-improving policies for deterministic finite-horizon optimal control problems starting from a fixed initial state, which is fast enough for on-line use in repetitive tasks like path planning or discrete optimization.
-
The algorithm can be extended to handle multiagent systems where the control vector is composed of multiple components by treating each component as an agent and performing sequential minimizations, leading to computational savings when discretization is involved.
-
The stochastic variant allows the system to sample policies from a probability distribution defined by a stochastic generator, which enables training neural network-based policies using trajectory data while preserving cost improvement under consistency conditions.
-
A simplified on-line PI variant reduces real-time computation by replacing general minimization with iteration-dependent subsets of control constraints, allowing for faster policy updates when state and cost function evaluations are costly simulations.
-
The framework can be applied to highly nonlinear problems and scales well with control dimension, as the method does not require analytical expressions for system dynamics or cost functions, only efficient real-time simulation of trajectories.
Sources
- On-Line Policy Iteration for Infinite Horizon Dynamic Programming
- Adaptive Network Security Policies via Belief Aggregation and Rollout
- An Approximate Dynamic Programming Framework for Occlusion-Robust Multi-Object Tracking
- Proximal Policy Optimization Algorithms
Related papers
- Industrial Load Modeling and Optimization for Market-Based Interaction with Power Systems
- Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints
- Certified Set Convergence for Piecewise Affine Systems
- Symbolic Control for Stochastic Systems via Finite Parity Games
- Multiobjective optimization-based design and dispatch of islanded, hybrid microgrids for remote, off-grid communities in sub-Saharan Africa
- Physiology-informed layered sensing for intelligent human-exoskeleton interaction