Monte Carlo Policy Evaluation

Continual exploration is necessary for Monte Carlo policy evaluation of action values.

Programming

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.

How do nonzero starting probabilities provide continuing coverage of every state-action pair across infinitely many episodes?

Worked example

Applying the exploring-starts condition

Suppose an environment has several state-action pairs, and each pair has a nonzero probability of being selected as the starting pair.

1
Check the probabilities
Verify that no state-action pair has zero probability of starting an episode.
2
Consider infinitely many episodes
Under the exploring-starts assumption, the nonzero probability for each pair guarantees that every pair is encountered infinitely often in the limit.
3
Connect coverage to evaluation
Because each pair continues to appear in experience, Monte Carlo evaluation can continue learning about the action-values of those pairs.

Result

Exploring starts supplies the coverage needed for action-value evaluation in the limit of infinitely many episodes.

Two Sources of Exploration

Exploration source	How actions are encountered	Where the coverage comes from
Exploring starts	Episodes begin with state-action pairs selected under a starting rule	The starting rule gives every state-action pair a nonzero probability
Stochastic policy	The agent sometimes selects each action while interacting in a state	The policy gives every action in each state a nonzero selection probability

Both mechanisms support continual access to actions, but one supplies exploration at episode starts and the other supplies it through policy behavior.

What is the difference between coverage supplied by episode starting conditions and coverage supplied by action selection during interaction?

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.

How does an experienced episode move from visited state-action pairs to observed returns and then to updated action-value estimates?

Worked example

Evaluating an initial policy

Consider an initial policy named π0. The agent follows π0 through many complete episodes.

1
Follow π0
The episodes are generated while the current policy π0 determines the agent's behavior.
2
Record experience
For each state-action choice encountered, the episode provides an associated return.
3
Estimate action-values
The returns from many episodes are used to estimate how valuable each state-action choice is when continuing to follow π0.

Result

Evaluation produces an approximate action-value function for π0; with infinitely many suitable episodes, the action-value function is computed exactly under the stated idealized assumptions.

Evaluation and Improvement

How does the process alternate between evaluating the current policy and improving it until the policy approaches optimality?

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.

What changes during evaluation, what changes during improvement, and how are their inputs and outputs connected?

Common Misunderstandings

Common mistake
Assuming that completing episodes is enough for action-value evaluation.
What it looks like
An agent completes many episodes but never encounters some state-action pairs.
Why it fails
Monte Carlo evaluation needs experience for the pairs whose action-values are being estimated.
Do this instead
Ensure continual exploration through exploring starts or, in direct interaction, through a stochastic policy with nonzero probability for every action in each state.
Common mistake
Interpreting exploring starts as equal-frequency starts.
What it looks like
Expecting every state-action pair to start exactly the same number of episodes.
Why it fails
The requirement is only that every pair has a nonzero probability of starting an episode.
Do this instead
Focus on nonzero probability, not equal probability.
Common mistake
Treating a brief exploratory phase as continual exploration.
What it looks like
The agent explores at the beginning and then loses all ability to encounter some actions.
Why it fails
Exploration must remain available throughout the learning process for the stated action-value evaluation requirement.
Do this instead
Use a mechanism that continues to provide access to the pairs being evaluated.
Common mistake
Mixing up evaluation and improvement.
What it looks like
Calling the comparison of action-values another round of episode averaging.
Why it fails
Evaluation estimates action-values from episodes, whereas improvement applies a decision rule to those estimates.
Do this instead
First evaluate the current policy, then construct a policy that chooses maximal action-values.
Common mistake
Assuming that one episode gives the exact action-value function.
What it looks like
Using the return from a single episode as the final value for every action.
Why it fails
Monte Carlo evaluation uses many episodes, and the approximate action-value function approaches the true function asymptotically.
Do this instead
Treat individual returns as experience contributing to estimates gathered across episodes.

Practice the Cycle

MEDIUM

A current policy is followed through many complete episodes. The episodes provide returns for the state-action pairs encountered, and the resulting estimates show that one action has the maximal action-value at a particular state. Identify which operation has just occurred, which operation comes next, and what the next policy should do at that state.

Hints

Episode returns are used during policy evaluation.
The operation that uses maximal action-values is policy improvement.
The next policy should choose an action with the maximal estimated action-value.

Your attempt (not saved)

What do you think happens?

If every state-action pair has a nonzero probability of starting an episode, what does the exploring-starts assumption guarantee in the limit of infinitely many episodes?

Every pair is selected equally often
Every pair is encountered infinitely often
Only the currently best pair is encountered
No pair needs to be encountered again

Reveal answer

Answer:

Every pair is encountered infinitely often.

The guarantee depends on every pair having nonzero starting probability. Equal frequency is not required.

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.

Key Takeaways

Continual exploration is necessary because action-values can be learned only from experience involving the state-action pairs being evaluated.
Exploring starts guarantee coverage by giving every state-action pair a nonzero probability of beginning an episode; over infinitely many episodes, every pair is encountered infinitely often.
A stochastic policy can provide exploration during direct interaction by giving every action in each state a nonzero probability of selection.
Policy evaluation estimates action-values from experienced episodes, while policy improvement constructs a greedy policy from those estimates.
Repeating evaluation and improvement begins with an arbitrary policy and, under the stated assumptions, ends with the optimal policy and optimal action-value function.

More concepts starting with M