Computing v* with Policy Iteration

The Translation Problem

The central challenge is not to calculate a particular number. It is to translate the policy-iteration idea used for computing v* into an action-value form. The exercise asks what policy iteration would look like when q-values, rather than state values, are the main quantities being represented and updated.

Two Targets, Two Representations

The notation v* identifies the state-value target named in the original exercise. The notation q* identifies the corresponding action-value target. The important distinction is the object being represented: a state-value formulation is organized around values associated with states, while the action-value formulation is organized around values associated with state-action choices. Therefore, adapting the algorithm requires more than replacing one symbol with another. The representation, the iteration process, and the final result must all be expressed in action-value language.

The Policy-Iteration Cycle

A complete action-value formulation can be organized as a repeated cycle. First, choose an action-value representation for the current policy. Next, perform policy evaluation in that representation so the current policy has corresponding q-values. Then perform policy improvement using those q-values to determine the next policy. Continue the evaluation and improvement process until the policy-iteration procedure has reached its final result. The result is reported as q*.

A Complete Algorithm Blueprint

1. Specify the action-value representation. State clearly that the quantities being stored or computed are q-values associated with state-action pairs.
2. Choose or receive an initial policy. The policy supplies the current action choices whose action values will be evaluated.
3. Evaluate the current policy using action values. The evaluation stage must produce q-values for the current policy rather than leaving the solution in state-value notation.
4. Improve the policy using the evaluated q-values. The improvement stage uses the action-value representation to revise the policy's action choices.
5. Repeat action-value policy evaluation and policy improvement as required by the policy-iteration procedure.
6. When the iteration has reached its final policy result, identify the corresponding action-value result as q*.
7. State the output explicitly. A complete answer should say that the algorithm computes q*, not v*.

A Worked Design Example

This example demonstrates the level of completeness expected from an algorithm-design answer. It does not pretend that an unspecified environment has numerical q-values. Instead, it makes the representation, iteration stages, target, and missing inputs explicit.

Missing Inputs for Calculation

The supplied material is enough to design the requested action-value version conceptually, but it is not enough to calculate numerical q* values. The source specifically notes that no particular environment, action set, reward description, initial policy, or earlier v* algorithm is supplied.

Common Specification Errors

• Treating q* as if it were simply another spelling of v*

  The source identifies the main task as reformulating the entire policy-iteration process using action values.

  Fix: Make the representation, evaluation stage, improvement stage, and final output action-value based.

• Giving only the target name

  A complete algorithm must connect the representation, the iteration process, and the q* result.

  Fix: Include the action-value representation, policy evaluation, policy improvement, repetition, and final result.

• Inventing a numerical environment

  The source provides none of the particular numerical information needed for a calculation.

  Fix: State the missing information and give a general algorithm blueprint instead.

• Leaving policy evaluation and improvement disconnected

  The policy-iteration process must show how evaluation produces action values and how improvement uses them to update the policy.

  Fix: Present the stages as a cycle: represent, evaluate, improve, repeat, and report q*.

Practice: Audit an Algorithm

Final Checklist

1. The action-value target named by the exercise is q*, in analogy with v*.
2. The central task is to reformulate policy iteration so that action values are the main quantities represented and updated.
3. A complete algorithm connects the action-value representation, policy evaluation, policy improvement, repeated iteration, and the final q* result.
4. The supplied material does not support a numerical q* calculation because it omits a particular environment, action set, reward description, initial policy, and earlier v* algorithm.
5. When numerical inputs are missing, provide a precise algorithmic blueprint rather than inventing values.