State-Value Functions

Why One Starting State Is Not Enough

In reinforcement learning, solving a task means finding a policy that produces substantial reward over the long run. However, a policy is not called optimal merely because it performs well in one situation or from one starting state. Optimality is evaluated across all states.

Comparing Policies State by State

Let vπ(s) represent the state value produced by policy π at state s. Policy π is better than or equal to policy π′ when vπ(s) is greater than or equal to vπ′(s) for every state. In plain language, the first policy must produce an expected return at least as high as the second policy from every state being considered.

Why the Ordering Is Partial

The comparison rule does not necessarily place every pair of policies in order. One policy may have a higher value in one state, while another policy has a higher value in a different state. When that happens, neither policy is better than or equal to the other under the rule, because each policy is worse somewhere.

Testing Optimality in Every State

A policy is optimal when its expected return is at least as high as the expected return of every other policy, starting from every state. In a finite task, at least one policy is better than or equal to all other policies. Every policy meeting this standard is an optimal policy, denoted by π∗.

The Finite Decision Process

In a finite Markov decision process, the policy is evaluated through the states, available actions, transitions, and rewards that make up the task. The policy specifies a way of behaving, and its state-value function records the expected return associated with following that policy from each state. Optimality means that this behavior produces an expected return at least as high as every alternative policy from every state.

When Optimal Policies Tie

Optimality does not require a unique policy. There may be more than one policy that is better than or equal to all other policies. All policies meeting this standard are denoted by π∗.

An optimal policy identifies a way of behaving. The optimal state-value function, written v∗, identifies the best expected return associated with each state. Therefore, multiple optimal policies can exist while sharing exactly the same state-value function.

Common Reasoning Errors

• Declaring a policy optimal because it performs best in one state.

  Optimality requires the expected return to be at least as high as every other policy from every state.

  Fix: Compare the policies across all states before making an optimality claim.

• Assuming that every pair of policies must be orderable.

  Each policy is worse in at least one state, so neither satisfies the better-than-or-equal comparison against the other.

  Fix: Allow the result that the policies are incomparable under the state-by-state rule.

• Assuming that there can be only one optimal policy.

  The definition permits more than one policy to meet the optimality standard.

  Fix: Distinguish the possibility of multiple optimal policies from the shared optimal state-value function.

• Treating an optimal policy and the optimal state-value function as the same thing.

  A policy identifies behavior, while v∗ identifies the best expected return associated with each state.

  Fix: Use policy language for behavior and state-value-function language for expected returns by state.

Check Your Understanding

Essential Takeaways

1. Policy π is better than or equal to policy π′ when its state value is at least as high in every state.
2. Because one policy can be better in some states while another is better in others, not every pair of policies can be ordered.
3. In a finite task, an optimal policy is at least as good as every other policy from every state.
4. There may be multiple optimal policies, and all of them can share one optimal state-value function, v∗.
5. A policy describes behavior, while a state-value function describes expected return associated with states.