Monte Carlo Policy Evaluation

Why Coverage Matters

Monte Carlo policy evaluation estimates action-values from experience in complete episodes. That estimate can improve only when the state-action pairs being evaluated are encountered. If some pairs are never encountered, the method cannot continually learn from those pairs. The central requirement is therefore not merely to complete episodes, but to keep every relevant state-action pair reachable through experience.

Exploring Starts Across Episodes

The exploring-starts assumption gives every state-action pair a nonzero probability of being the starting pair of an episode. The method does not require every pair to be selected equally often. It requires only that no pair has zero probability of starting an episode.

Two Sources of Exploration

Exploring starts can be useful in an idealized setting, but it cannot generally be assumed during direct interaction with an environment. Real starting conditions may not be arranged to cover state-action pairs. In that situation, exploration must be handled through another mechanism, such as a stochastic policy that gives every action in each state a nonzero probability of selection.

From Episodes to Action-Values

Policy evaluation gathers many complete episodes while following the current policy. For each visited state-action pair, the experienced episode supplies an observed return. Those returns are used to estimate the action-value function for the current policy. One episode does not produce the exact action-value function; the approximate function approaches the true function asymptotically as many episodes are experienced.

Evaluation and Improvement

Policy evaluation changes the available knowledge about the current policy: experienced episodes are used to estimate its action-values. Policy improvement changes the policy itself: the action-values are compared, and a new policy is made greedy with respect to them. Improvement is not another round of episode averaging. It is a decision rule applied to the action-value function produced by evaluation.

Common Misunderstandings

• Assuming that completing episodes is enough for action-value evaluation.

  Monte Carlo evaluation needs experience for the pairs whose action-values are being estimated.

  Fix: Ensure continual exploration through exploring starts or, in direct interaction, through a stochastic policy with nonzero probability for every action in each state.

• Interpreting exploring starts as equal-frequency starts.

  The requirement is only that every pair has a nonzero probability of starting an episode.

  Fix: Focus on nonzero probability, not equal probability.

• Treating a brief exploratory phase as continual exploration.

  Exploration must remain available throughout the learning process for the stated action-value evaluation requirement.

  Fix: Use a mechanism that continues to provide access to the pairs being evaluated.

• Mixing up evaluation and improvement.

  Evaluation estimates action-values from episodes, whereas improvement applies a decision rule to those estimates.

  Fix: First evaluate the current policy, then construct a policy that chooses maximal action-values.

• Assuming that one episode gives the exact action-value function.

  Monte Carlo evaluation uses many episodes, and the approximate action-value function approaches the true function asymptotically.

  Fix: Treat individual returns as experience contributing to estimates gathered across episodes.

Practice the Cycle

Learning Progression

1. Begin with an arbitrary policy.
2. Maintain coverage of state-action pairs through exploring starts or suitable stochastic policy behavior.
3. Follow the current policy through many complete episodes.
4. Use the experienced returns to estimate the current policy's action-value function.
5. Improve the policy by choosing an action with maximal action-value at each state.
6. Evaluate the new policy and repeat the evaluation-improvement cycle.
7. Under the stated assumptions, the cycle ends with the optimal policy and optimal action-value function.

1. Monte Carlo action-value evaluation requires continual exploration because every pair being evaluated must continue to receive experience. Exploring starts provide coverage by assigning every state-action pair a nonzero probability of beginning an episode, which guarantees infinite encounters in the limit of infinitely many episodes. In direct interaction, a stochastic policy can provide an alternative by assigning every action in each state a nonzero selection probability. Monte Carlo policy iteration separates evaluation from improvement: episodes estimate the current policy's action-values, and improvement makes the next policy greedy with respect to those values. Repeating these steps moves an arbitrary initial policy toward the optimal policy under the stated assumptions.