Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 37 ยท Monte Carlo and Temporal Difference

Monte Carlo Control: Exploring Starts and Epsilon-Soft Policies

Find optimal policies with Monte Carlo control: estimate action values q, improve greedily, guarantee exploration with exploring starts or epsilon-soft policies, with blackjack and grid world code.

Prediction estimates how good a given policy is. Control finds a good policy. Monte Carlo control follows the generalized policy iteration pattern from the DP chapter: estimate values from data, improve the policy, repeat. Two things change compared with DP: we have no model, so we must estimate action values q(s, a), and we must make sure the agent keeps exploring, since an improving policy tends to stop visiting anything but its favorite actions.

Why action values?

With a model, the greedy improvement step looks one step ahead using p and v. Without a model that lookahead is impossible, but with q we can simply pick argmax over a of q(s, a). So MC control estimates q(s, a) by averaging the returns that followed taking a in s, exactly as MC prediction averaged returns for s.

The exploration problem

If the policy is deterministic and greedy, many state-action pairs are never tried, so their q never gets estimated and the agent may never find out that one of them is better. Two classic fixes:

  1. Exploring starts (ES). Begin every episode in a randomly chosen state-action pair (every pair has a nonzero probability). Afterwards follow the current greedy policy. Simple and effective when you control the start, as in a simulator, but unrealistic in a real environment.
  2. Epsilon-soft policies (on-policy control). Keep a policy that always gives every action at least probability epsilon / |A|, for example epsilon-greedy. It explores forever through its own randomness, with no special starts. The price: the learned policy is the best epsilon-soft policy, not the best deterministic one.
flowchart LR
    Q["Q(s,a) estimates"] -->|"improve: greedy or epsilon-greedy"| PI["policy"]
    PI -->|"generate episodes"| E["returns"]
    E -->|"average into Q"| Q

Monte Carlo ES on the grid world

We use the 4x4 grid (deterministic, -1 per step, terminals at the corners). Each episode starts at a random non-terminal square with a random first action. The policy is greedy with respect to the current Q. A bad early policy might loop forever (walk into a wall again and again), so we cap episodes at 60 steps; the huge negative returns of such loops quickly make those actions look bad.

Python Monte Carlo control with exploring starts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see arrows that lead every square toward a terminal corner, and values near -(distance to the nearest terminal). Notice what was not needed: no transition table, only sampled episodes and a random start.

Epsilon-soft MC control: blackjack

Now the realistic setting: we cannot choose the starting hand, so the policy explores by itself. The player may hit or stick at each sum of 12 or more (below 12, hitting is always right). We learn Q((sum, dealer card, usable ace), action) using an epsilon-greedy policy with epsilon = 0.1, first-visit updates, and the one terminal reward.

Python On-policy epsilon-greedy MC control for blackjack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The table that comes out is close to the well-known optimal blackjack strategy for this simplified game: stick on 17 and above everywhere; on 12 to 16 hit when the dealer shows a strong card (7 to ace, written 7, 8, 9, 10, 1) and stick when the dealer shows a weak card (2 to 6). A few cells disagree with that rule (in the seeded run, 14 against a dealer 6 and 15 against a dealer 10) because the differences in value are tiny and the estimates are noisy: another sign of why more data and decaying epsilon help.

Epsilon-soft improvement step

For an epsilon-greedy policy the improvement is not "pick argmax" but "give the greedy action probability 1 - epsilon + epsilon / |A| and every other action epsilon / |A|". It still satisfies a policy improvement theorem within the class of epsilon-soft policies: you converge to the best epsilon-soft policy. To approach the true optimum, decay epsilon toward 0 over time (the idea of GLIE: greedy in the limit with infinite exploration). The alternative is off-policy control, where the data come from an exploratory behavior policy but the learned policy is fully greedy. That is the subject of the next lesson.

Common mistakes

  • Estimating only v and trying to improve without a model. You need q (or a model).
  • Using exploring starts in a real environment where you cannot choose where episodes begin.
  • Forgetting that a deterministic greedy policy with no exploration can lock out better actions forever.
  • Using a constant epsilon and then reporting the learned policy's performance including the random actions, which understates what the greedy policy would score.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does MC control estimate action values q(s, a) instead of v(s)?

    With q, greedy improvement needs only argmax over actions, no transition model.
  2. 2. What do exploring starts guarantee?

    Starting episodes from random state-action pairs ensures all pairs get visited.
  3. 3. What is an epsilon-soft policy?

    It keeps exploring forever through its own randomness.
  4. 4. Which method learns the best epsilon-soft policy rather than the best deterministic one?

    On-policy control improves the same epsilon-greedy policy that generates the data, so it converges within the epsilon-soft class.

Summary

  • MC control = GPI with sampled returns: estimate q, improve the policy, repeat.
  • Exploration is essential: exploring starts (random initial pairs) or epsilon-soft policies (permanent randomness).
  • On-policy epsilon-greedy control finds the best epsilon-soft policy; decaying epsilon approaches the optimum.
  • Blackjack shows MC finding a near-optimal strategy with no model of the game.

Next: Off-Policy Learning and Importance Sampling