Is modified policy iteration a reinforcement-learning algorithm?

Its classical form is model-based dynamic programming; approximate and sampled versions connect it to reinforcement learning.

Does m = 1 always mean one whole policy-iteration cycle?

Under the stated greedy-then-evaluate convention, it gives one optimality backup, the value-iteration update.

Should m be as large as possible?

Not necessarily. More evaluation work can become unnecessary when the policy is about to change.

AI Glossary / Reinforcement learning and robotics / Advanced

Modified policy iteration

Definition

Modified policy iteration is a dynamic-programming method that alternates greedy policy improvement with partial policy evaluation. Instead of fully solving for each policy's value before improving it, the algorithm performs a chosen number of evaluation updates. This provides a practical middle ground between value iteration and full policy iteration for suitable Markov decision problems.

What it means

Policy iteration can spend substantial effort evaluating a policy that will soon change. Value iteration changes the greedy decision rule more frequently but may propagate long-term consequences slowly. Modified policy iteration adjusts how much evaluation work occurs between improvements.
The modification is deliberate computational scheduling, not permission to ignore the transition model or stop whenever a policy looks reasonable. Its evaluation values can remain approximate even after the selected actions appear stable for a short time.

How it works

For a discounted finite Markov decision process, let V be the current value estimate. First choose a policy pi that is greedy with respect to V: at each state, maximize immediate expected reward plus discounted expected next-state value.
Hold that policy fixed and apply its Bellman evaluation operator m times, starting from V. In notation, V_new = (T_pi)^m V, where T_pi V = r_pi + gamma P_pi V. Repeat the greedy and evaluation stages.
With this convention, m = 1 reproduces value iteration because a single backup under a greedy policy equals an optimality backup. Evaluating to convergence gives the policy-iteration limit. Finite m greater than one lies between these endpoints.
Convergence results require the corresponding assumptions, such as bounded rewards and discount factor below one in the standard setting. Sampled updates, function approximation, and approximate greedy steps introduce additional errors and require their own analysis.

Three practical examples

Small navigation models: a planner computes a decision rule from a known transition table while balancing evaluation work against policy improvements.
Inventory simulation: a finite-state model is solved offline, comparing several evaluation budgets before selecting a computational approach.
Algorithm research: approximate modified policy iteration provides a framework for studying how evaluation and improvement errors interact in larger decision problems.

Think of it this way

Think of revising a schedule after a preliminary calculation of its downstream effects. Fully analyzing every temporary schedule may waste effort, but changing it after almost no analysis may lead to many revisions. Modified policy iteration chooses an intermediate amount of analysis before asking whether a better decision rule is available.

Worked example

Consider an original two-state continuing problem with discount factor gamma = 0.5. At state A, Stay gives reward 1 and returns to A; Go gives reward 0 and moves to B. At B, the only action gives reward 3 and returns to B. All transitions are deterministic.
Start with V(A) = V(B) = 0. The greedy policy chooses Stay at A, because its one-step comparison is 1 versus 0. Hold that policy fixed and perform two synchronous evaluation sweeps, meaning each sweep uses the previous sweep's values.
After the first sweep, V = (1, 3). After the second, V(A) = 1 + 0.5 times 1 = 1.5 and V(B) = 3 + 0.5 times 3 = 4.5.
Improve the policy using these partial values. At A, Stay scores 1 + 0.5 times 1.5 = 1.75, while Go scores 0 + 0.5 times 4.5 = 2.25. The policy switches to Go even though the old policy was not fully evaluated.
The exact old-policy values would have been (2, 6). The exact new-policy values are (3, 6): B's continuing reward sums to 3/(1 - 0.5) = 6, and moving there from A gives 0 + 0.5 times 6 = 3. These exact values confirm the improvement in this example.
Notice a stopping trap: after just the first evaluation sweep, both action comparisons at A equal 1.5. A tie-breaking rule that keeps Stay could leave the policy unchanged temporarily, although further evaluation reveals Go is better. Temporary policy stability with incomplete evaluation is not, by itself, an optimality certificate.

Illustrative case study

Fictional case: Elm Planning compares solvers for a finite scheduling simulator. Exact policy evaluation is relatively costly, so the team tries one, two, and several evaluation sweeps between greedy improvements.
Engineers verify each implementation on small models with known solutions, use consistent tie-breaking, and compare total computation rather than only the number of outer iterations. They also check an appropriate residual-based stopping rule instead of stopping after one unchanged action table.
The team records the trade-off that works for its particular simulator. This fictional case illustrates algorithm selection and verification; it makes no claim that a fixed evaluation budget is universally fastest.

Common misconceptions and mistakes

Partial evaluation does not mean changing the policy after every inner sweep; the selected policy stays fixed during that evaluation phase. The number of sweeps is not a discount factor or the length of an actual episode.
An unchanged greedy policy can be premature evidence when its value estimate remains incomplete. Faster convergence in outer iterations does not necessarily mean lower wall-clock time. Guarantees for exact finite discounted models should not be transferred automatically to neural approximation, noisy simulation, or undiscounted problems.

Business use

Modified policy iteration can reduce wasted evaluation work when repeatedly solving a structured decision model. Its practical benefit depends on transition sparsity, action count, discounting, and implementation cost. Teams should benchmark total computation and solution quality on representative models. A planning solution also inherits the limitations of the model and reward specification, even when the numerical algorithm converges correctly.

Check your understanding

Why can the worked method switch to Go before reaching the old policy's exact value (2, 6)?

Answer: The partial estimate (1.5, 4.5) already provides enough information for the greedy comparison to favor Go. Exact evaluation is not required for that particular decision.

Related terms

Learn next

Implement synchronous policy evaluation on a tiny transition table, then alternate it with greedy improvement. Compare m = 1, several finite values, and evaluation to convergence while recording residuals and total computational work.

Policy evaluation

Sources

Martin L. Puterman and Moon Chirl Shin, Modified Policy Iteration Algorithms for Discounted Markov Decision Problems (1978), publisher abstract: https://pubsonline.informs.org/doi/10.1287/mnsc.24.11.1127 Bruno Scherrer and colleagues, Approximate Modified Policy Iteration and its Application to the Game of Tetris (2015), introductory equations and Section 2: https://www.jmlr.org/papers/volume16/scherrer15a/scherrer15a.pdf

Independent review checked Scherrer and colleagues, Equations 1–2.

Previous: Modified Kumaraswamy distribution Next: Modular Language Model