Policy Iteration for Optimal Decision Making

The important change is not merely renaming v* as q*. A complete solution must specify what is stored, how policy evaluation and policy improvement operate on that representation, and how the final q* result is obtained.

Programming

From v* to q*

Policy iteration is not restricted to state values. The central task is to reformulate the policy-iteration process so that action values are the quantities represented, computed, and updated throughout. The target of this action-value version is q*, in analogy with the state-value target v* named in the source exercise.

Key point

What is the difference between a value assigned to a state and a value assigned to a state-action pair?

The Iteration Loop

The action-value algorithm can be organized by adapting the policy-iteration approach used for v*. First choose or receive a policy and establish an action-value representation. Then evaluate that policy using action values. Next improve the policy using the evaluated action values. Repeat evaluation and improvement until the policy and its action-value representation reach the optimal result. The final action-value result is identified as q*.

What happens next as action-value policy evaluation and policy improvement alternate until q* is obtained?

1
Represent the quantities to be computed as action values for state-action pairs.
2
Start with a policy, whether supplied by the problem or selected as the initial policy for the algorithm.
3
Evaluate the current policy using the action-value representation.
4
Improve the policy by using the evaluated action values to select the preferred action in each state.
5
Repeat evaluation and improvement while the policy is still changing.
6
When the policy-iteration process has reached its stable result, report the corresponding action-value result as q*.

A Representation to Track

The representation determines what the algorithm can evaluate and improve. For v*, the central quantity is organized by state. For q*, the central quantity must distinguish actions as well as states. That means the action-value representation must make it possible to refer to the value associated with a particular state-action pair and to compare the available action values when improving the policy.

How are q* values organized when each state can have multiple action values?

This organization is why an action-value solution cannot simply copy a state-value solution and change the final symbol. The algorithm must retain action-specific information throughout policy evaluation and policy improvement. Otherwise, there would be no action-value basis for revising the policy.

Abstract Walkthrough

Consider a generated abstract setting with two states and several available actions. No rewards, transitions, numerical values, initial policy, or discount information are supplied here. The purpose of this example is therefore to trace the structure of the algorithm, not to calculate q* numerically.

Worked example

Tracing the Action-Value Version

Organize policy iteration for a setting in which each state has more than one available action, with q* as the desired result.

1
Represent
Create an action-value representation that distinguishes the value associated with each state-action pair. This is the quantity that the algorithm will evaluate and update.
2
Initialize
Begin with a policy. The policy identifies the current action choice associated with each state.
3
Evaluate
Evaluate the current policy using action values. The result describes the action values associated with following the current policy.
4
Improve
Use the evaluated action values to revise the policy. In each state, the action-value information provides the basis for selecting the preferred action.
5
Repeat
Return to policy evaluation after an improvement. Continue alternating the two stages while the policy is not yet stable.
6
Report
When the iteration reaches its stable optimal result, report the corresponding action-value function as q*.

Result

The complete action-value policy-iteration design connects the q representation, repeated evaluation and improvement, and the final q* result.

Key point

The example is complete as an algorithmic outline but deliberately not numerical. The source material does not specify an environment or numerical inputs from which particular q* values could be calculated.

Inputs Before Calculation

Before attempting a numerical q* computation, check whether the problem supplies the information needed to define and run the iteration. The supplied source does not provide a particular environment, action set, reward description, initial policy, or earlier v* algorithm. Consequently, it supports an algorithm-design answer but not a numerical q* result.

What model, reward, discount, state, and action information must be supplied before q* can be calculated numerically?

Common mistake
Treating q* as though it were only a renamed v*.
What it looks like
The solution discusses only values organized by state and changes the final answer symbol to q*.
Why it fails
The action-value formulation must use action values as the main quantities being represented and updated.
Do this instead
Describe the representation, evaluation stage, improvement stage, and final result in action-value terms.
Common mistake
Giving only the policy-improvement step.
What it looks like
The solution says to choose the highest-valued action but does not explain how the action values are obtained or how the process repeats.
Why it fails
A complete algorithm must connect representation, iteration, and the q* result.
Do this instead
Include both policy evaluation and policy improvement, together with the stopping and reporting stages.
Common mistake
Inventing numerical q* values when the problem supplies no numerical environment.
What it looks like
A solution reports specific action values even though no environment, action set, reward description, initial policy, or earlier algorithm is provided.
Why it fails
The supplied material supports an algorithm-design answer, not a numerical calculation.
Do this instead
State which inputs are missing and give the complete abstract algorithm instead.
Common mistake
Stopping after policy evaluation.
What it looks like
The solution evaluates one policy and calls its action values q*.
Why it fails
Policy iteration requires the evaluation and improvement stages to alternate toward the optimal result.
Do this instead
Improve the policy after evaluation and repeat until the process reaches its stable result.

Practice Check

MEDIUM

Write a six-step outline for an action-value policy-iteration algorithm. Your outline should begin with the q representation, include policy evaluation and policy improvement, explain when the process repeats, and identify the final result. Then list the information you would request before attempting a numerical computation.

Hints

Use action-value language rather than replacing q* with v*.
Separate evaluating the current policy from improving the policy.
Check for the environment, action set, reward description, initial policy, and discount information.

Your attempt (not saved)

What do you think happens?

If an exercise gives no particular environment, action set, reward description, initial policy, or earlier v* algorithm, can it determine numerical q* values?

Reveal answer

Answer:

No. It can support an algorithm-design answer, but the missing numerical information prevents a numerical q* calculation.

The source explicitly describes the supplied material as defining the scope of the exercise rather than providing a numerical calculation.

What to Remember

1
Policy iteration applies to action values as well as state values.
2
The action-value target is q*, while v* is the state-value target named in the source exercise.
3
A complete q* algorithm must specify the action-value representation, policy evaluation, policy improvement, repetition, and final reporting.
4
Policy improvement uses the evaluated action values to select the preferred action in each state.
5
Numerical q* computation requires supplied problem information; the source material alone provides an algorithm-design task rather than numerical inputs.

At a glance

The action-value version of policy iteration is intended to compute q*.
q* is organized around state-action pairs, whereas v* is the state-value target named in the source exercise.
The algorithm alternates action-value policy evaluation and policy improvement.
A valid solution connects representation, iteration, and the final q* result.
Without an environment, actions, rewards, initial policy, and other required information, only the algorithmic structure—not numerical q* values—can be given.

Related concepts

More concepts starting with P