Optimal Policy
Policy evaluation measures a given policy by assigning expected returns to states.
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 π |
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.
Start: Begin with an initial function v0 that assigns an estimate to each state.
Update: Apply the Bellman-based update using the current estimate and the fixed policy.
Repeat: Use the revised function as the next estimate, producing v1, v2, and later functions.
Interpret: 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).
Identify the target: The quantity being requested is vπ(15), so begin with state 15 rather than with a specified first action.
Apply 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.
Use the transitions: Use the stated destinations from state 15 and the relevant expected returns to revise the estimate.
Change 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.
Evaluate 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.
First evaluation: Evaluate π0 to obtain its value function vπ0.
First improvement: Use vπ0 to produce a better policy π1, unless π0 is already optimal.
Second evaluation: Evaluate π1 to obtain vπ1. This value function describes the new policy, not the old one.
Continue: 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.
Assuming that every iterative evaluation must eventually stop.
The resulting value for some states may be negative infinity, so the standard iterative evaluation algorithm may not terminate.
Fix:
Check whether the policy can continue forever before assuming that repeated evaluation has a finite stopping point.Treating a changed transition as if it were the same evaluation problem.
Changing gridworld transitions changes the evaluation problem even when the policy remains unchanged.
Fix:
Reevaluate 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 |
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
- Policy evaluation holds a policy fixed and computes expected returns for states, producing vπ(s).
- The action-value function qπ(s, a) specifies an initial action before the agent follows policy π.
- Iterative evaluation produces successive estimates v0, v1, v2, and later approximations rather than one immediate final assessment.
- Policy iteration alternates between evaluating the current policy and improving it using its value function.
- In a finite MDP, strict improvement and the finite number of possible policies guarantee that policy iteration reaches an optimal policy after finitely many iterations.
Key Takeaways
- 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.