Optimal Policy
Policy evaluation measures a policy; it does not yet replace that policy with a supposedly better one.
The Question Behind Evaluation
An optimal policy is not usually found by declaring the best action immediately. A more reliable route is to evaluate a policy first, use that evaluation to improve the policy, and repeat the process. The central question during evaluation is: if an agent starts in a particular state and continues following a specified policy, what return should it expect?
Policy evaluation measures a policy; it does not yet replace that policy with a supposedly better one.
Fixed-Policy Value
Policy evaluation holds policy π fixed and assigns an expected return to each state. The result is the value function vπ(s). The notation begins with a state because the question begins there: what return is expected from state s when the agent follows policy π?
In a gridworld with an equiprobable random policy, evaluation must account for the policy's action choices. It must not select an action simply because that action appears best. The policy is being measured as it is, including its prescribed action choices.
| Quantity | Starting information | What happens afterward |
|---|---|---|
| vπ(s) | State s | The agent follows policy π |
| qπ(s, a) | State s and specified action a | The agent first takes a, then follows policy π |
The action-value function includes a specified first action; the value function begins with a state.
Successive Evaluation Estimates
Iterative policy evaluation does not produce the final assessment in one conceptual jump. It begins with an initial value function, applies a Bellman-based update, and obtains a revised function. Repeating the update creates a sequence such as v0, v1, v2, and so on. Each stage uses the available estimate to revise the values assigned to states.
Reading an Iterative Evaluation Trace
Suppose a fixed policy is being evaluated through successive estimates v0, v1, v2, and later estimates.
- 1Start
Begin with an initial function v0 that assigns an estimate to each state.
- 2Update
Apply the Bellman-based update using the current estimate and the fixed policy.
- 3Repeat
Use the revised function as the next estimate, producing v1, v2, and later functions.
- 4Interpret
Treat the sequence as successive approximations to the value function for the policy, not as unrelated policies.
The policy remains fixed while the value estimates change.
Gridworld Update Reasoning
A useful way to organize a gridworld evaluation is to separate three questions. First, which state or state-action quantity is being evaluated? Second, what does the policy do after the specified starting condition? Third, which expected returns must be combined to revise the current estimate? This separation prevents the starting condition, the policy, and the transition structure from being confused.
Reevaluating State 15
A new state 15 is placed below state 13. From state 15, left leads to 12, up leads to 13, right leads to 14, and down leads back to 15. First evaluate vπ(15) while the original-state transitions remain unchanged. Then change the transition for down from state 13 so that it leads to state 15, and reevaluate vπ(15).
- 1Identify the target
The quantity being requested is vπ(15), so begin with state 15 rather than with a specified first action.
- 2Apply the policy
Account for the action choices made by the policy from state 15. Under an equiprobable random policy, the calculation must include the policy's action choices instead of selecting whichever action looks best.
- 3Use the transitions
Use the stated destinations from state 15 and the relevant expected returns to revise the estimate.
- 4Change the model
When down from state 13 is changed to lead to state 15, the transition structure has changed, so the evaluation problem has changed even though the policy has not.
- 5Evaluate again
Recompute the value for state 15 under the altered gridworld rather than reusing the old evaluation unchanged.
A policy and a transition structure are separate parts of the evaluation problem.
Policy Iteration Cycle
Policy iteration repeats two stages. Evaluation computes the value function for the current policy. Improvement uses that value function to produce a better policy unless the current policy is already optimal. The value function is therefore an intermediate result: it tells us how good the current decisions are and supplies information for changing those decisions.
Tracing Policies and Value Functions
Begin with a policy π0 and apply policy iteration.
- 1First evaluation
Evaluate π0 to obtain its value function vπ0.
- 2First improvement
Use vπ0 to produce a better policy π1, unless π0 is already optimal.
- 3Second evaluation
Evaluate π1 to obtain vπ1. This value function describes the new policy, not the old one.
- 4Continue
Use vπ1 to support the next improvement and continue alternating the two stages.
The trace has the form π0, vπ0, π1, vπ1, and so on, until an optimal policy is reached.
Termination and the Infinite-Loop Risk
Iterative policy evaluation may fail to terminate in some undiscounted episodic tasks. A policy can allow the agent to continue forever, such as moving back and forth between two states without terminating. For some policies and states, the resulting value may be negative infinity. In that situation, the standard iterative policy-evaluation algorithm may not terminate.
Common mistake Assuming that every iterative evaluation must eventually stop.
What it looks likeA policy permits an agent to move back and forth between two states forever in an undiscounted episodic task.
Why it failsThe resulting value for some states may be negative infinity, so the standard iterative evaluation algorithm may not terminate.
Do this insteadCheck whether the policy can continue forever before assuming that repeated evaluation has a finite stopping point.
Common mistake Treating a changed transition as if it were the same evaluation problem.
What it looks likeChanging the transition from down at state 13 so that it leads to state 15.
Why it failsChanging gridworld transitions changes the evaluation problem even when the policy remains unchanged.
Do this insteadReevaluate the state under the altered transition structure.
Why Policy Iteration Stops
Policy iteration has a finite stopping guarantee in a finite MDP. Every improvement is strictly better than the previous policy unless the previous policy is already optimal. A finite MDP has only finitely many possible policies. Therefore, the process cannot keep producing new strictly better policies forever. After finitely many iterations, it reaches an optimal policy together with its optimal value function.
| Process | What changes between stages | Stopping idea |
|---|---|---|
| Iterative policy evaluation | The value estimate changes while the policy is held fixed | May fail to terminate in some undiscounted tasks where a policy can continue forever |
| Policy iteration | The policy changes after evaluation and improvement | In a finite MDP, strictly better policies cannot continue forever |
Value-estimate updates and policy changes are different processes with different termination considerations.
The finite-termination argument concerns the sequence of policies. It does not mean that every individual value estimate is produced in one update.
Practice: Separate the Stages
A gridworld uses an equiprobable random policy. State 15 is below state 13. From state 15, left leads to 12, up leads to 13, right leads to 14, and down leads back to 15. Explain what must be identified before evaluating vπ(15). Then explain why the evaluation must be repeated if down from state 13 is changed to lead to state 15.
Hints
- Begin by identifying whether the target is vπ(15) or qπ(15, a).
- Keep the policy's action choices separate from the transition structure.
- A changed transition creates a changed evaluation problem.
Write a verbal trace for policy iteration beginning with π0. Include the value function produced by evaluating π0, the improved policy, and the value function produced by evaluating that improved policy.
Hints
- Use the pattern policy, evaluation, value function, improvement, new policy.
- Remember that the value function supports improvement but is not itself the final policy.
- Stop when the current policy is already optimal.
Key Takeaways
- 1Policy evaluation holds a policy fixed and computes expected returns for states, producing vπ(s).
- 2The action-value function qπ(s, a) specifies an initial action before the agent follows policy π.
- 3Iterative evaluation produces successive estimates v0, v1, v2, and later approximations rather than one immediate final assessment.
- 4Policy iteration alternates between evaluating the current policy and improving it using its value function.
- 5In a finite MDP, strict improvement and the finite number of possible policies guarantee that policy iteration reaches an optimal policy after finitely many iterations.
At a glance
- Evaluation asks how much return to expect when starting from a state and following a fixed policy.
- vπ(s) starts with a state, whereas qπ(s, a) specifies the first action as well.
- Iterative evaluation revises value estimates successively while keeping the policy fixed.
- Policy iteration hands each evaluated value function to a policy-improvement stage.
- Because a finite MDP has finitely many policies and each non-final improvement is strict, policy iteration terminates at an optimal policy.