Chapter 5 — Monte Carlo methods.

Monte Carlo (MC) methods are the first that learn optimal behaviour without a model — directly from sampled experience: episodes of states, actions, and rewards. They estimate values by averaging the actual returns observed. This page covers MC prediction (first- and every-visit), why we estimate action values, the problem of maintaining exploration, MC control with exploring starts, on-policy \(\varepsilon\)-soft methods, and off-policy learning via importance sampling. MC applies only to episodic tasks and does not bootstrap. Maps to lectures CS6–CS7.

Learning from experience, not a model

Unlike dynamic programming, Monte Carlo methods do not assume complete knowledge of the environment. They require only experience — sample sequences of states, actions, and rewards from actual or simulated interaction. Learning from actual experience is striking because it requires no prior knowledge of the environment's dynamics, yet can attain optimal behaviour. Learning from simulated experience is also powerful: even when a model is available, it is often far easier to generate sample episodes from it than to compute the explicit probability distributions DP requires.

Monte Carlo methods solve the RL problem by averaging sample returns. To ensure well-defined returns are available, MC methods here are defined only for episodic tasks: experience is divided into episodes, and all episodes eventually terminate. Only on the completion of an episode are value estimates and policies changed. MC methods are thus incremental in an episode-by-episode sense, not a step-by-step (online) sense.

Monte Carlo prediction

Begin with learning the state-value function \(v_\pi\) for a given policy. Recall that the value of a state is the expected return — expected cumulative future discounted reward — starting from that state. An obvious way to estimate it from experience is simply to average the returns observed after visits to that state. As more returns are observed, the average should converge to the expected value. This idea underlies all Monte Carlo methods.

Suppose we wish to estimate \(v_\pi(s)\) given a set of episodes obtained by following \(\pi\) and passing through \(s\). Each occurrence of state \(s\) in an episode is called a visit to \(s\). Two variants:

• First-visit MC estimates \(v_\pi(s)\) as the average of the returns following the first visit to \(s\) in each episode.
• Every-visit MC averages the returns following all visits to \(s\).

Both converge to \(v_\pi(s)\) as the number of visits (or first visits) goes to infinity. For first-visit MC this follows directly from the law of large numbers: each return is an independent, identically distributed estimate of \(v_\pi(s)\) with finite variance, so the sequence of averages converges to the expected value. Every-visit MC is less straightforward but also converges.

First-visit MC prediction, for estimating V ≈ v_π:
  Initialize V(s) arbitrarily; Returns(s) ← empty list, for all s
  loop forever (for each episode):
    generate an episode following π:  S0,A0,R1,…,S_{T-1},A_{T-1},R_T
    G ← 0
    for t = T-1, T-2, …, 0:
       G ← γ·G + R_{t+1}
       if S_t not in S_0,…,S_{t-1}:        # first visit
          append G to Returns(S_t)
          V(S_t) ← average(Returns(S_t))

Why MC is fundamentally different from DP

An important fact: Monte Carlo methods do not bootstrap. The estimate for each state is independent — the estimate for one state does not build upon the estimate of any other state, unlike DP, where each value is updated using the values of successor states. In particular, the computational expense of estimating the value of a single state is independent of the number of states. This makes MC especially attractive when one requires the value of only one or a subset of states: you can generate episodes starting from those states and average returns, ignoring the rest of the state space entirely. (DP must sweep all states.)

Monte Carlo estimation of action values

If a model is not available, it is particularly useful to estimate action values (the values of state–action pairs) rather than state values. With a model, state values alone suffice to determine a policy — one looks ahead one step and chooses the action leading to the best combination of reward and next state. Without a model, state values alone are not enough: you must explicitly estimate the value of each action for the values to be useful in suggesting a policy. So one of our primary goals for Monte Carlo methods is to estimate \(q_*\). The MC method is the same: average the returns following each visit to a state–action pair \((s,a)\).

The problem of maintaining exploration

A serious complication arises: many state–action pairs may never be visited. If \(\pi\) is a deterministic policy, then in following it one will observe returns only for one action from each state. With no returns to average, the MC estimates of the other actions will not improve. This is the general problem of maintaining exploration — to compare alternatives we need to estimate the value of all actions from each state, not just the one currently favoured. There are two principal ways to guarantee that all state–action pairs are encountered: exploring starts, and using only soft policies.

Monte Carlo control with exploring starts

Monte Carlo control — approximating optimal policies — follows the same generalized-policy-iteration pattern as DP: maintain an approximate policy and an approximate value function, with the value function repeatedly altered to more closely approximate the value function for the current policy, and the policy repeatedly improved to be greedy with respect to the current value function. One assumption to guarantee all pairs are visited is exploring starts: every episode starts in a state–action pair chosen so that every pair has nonzero probability of being selected as the start. Over infinitely many episodes this guarantees all pairs are visited. Then alternate: evaluate \(q\) from episodes (using exploring starts), improve the policy to be greedy with respect to \(q\). This algorithm, Monte Carlo ES, converges to the optimal policy.

On-policy MC control (ε-soft)

On-policy methods attempt to evaluate or improve the policy that is used to make decisions. The way to ensure continual exploration is to make the policy soft — meaning \(\pi(a\mid s)>0\) for all states and actions — gradually shifting closer and closer to a deterministic optimal policy. A common choice is the \(\varepsilon\)-greedy (a kind of \(\varepsilon\)-soft) policy: most of the time choose the action with maximal estimated value, but with probability \(\varepsilon\) choose an action at random. All non-greedy actions are given the minimal probability of selection \(\tfrac{\varepsilon}{|\mathcal{A}(s)|}\), and the greedy action gets the remaining \(1-\varepsilon+\tfrac{\varepsilon}{|\mathcal{A}(s)|}\). On-policy MC control evaluates and improves the same \(\varepsilon\)-soft policy it uses to act, and converges (via the policy improvement theorem applied to \(\varepsilon\)-soft policies) to the best policy among the \(\varepsilon\)-soft policies.

Off-policy prediction via importance sampling

All learning control methods face a dilemma: they seek to learn action values conditional on subsequent optimal behaviour, but they need to behave non-optimally in order to explore all actions. On-policy methods resolve this with a compromise — they learn about a near-optimal policy that still explores. The more direct off-policy approach uses two policies: a target policy \(\pi\) that is learned about and becomes the optimal policy, and a separate, more exploratory behaviour policy \(b\) that is used to generate behaviour. Because we learn about \(\pi\) from data generated by \(b\), off-policy methods are more general and more powerful (on-policy is the special case \(\pi=b\)) — but they are also of greater variance and slower to converge.

The importance-sampling ratio

How can we estimate the expected returns under the target policy \(\pi\) given returns generated under a different behaviour policy \(b\)? By importance sampling — weighting returns according to the relative probability of their trajectories occurring under the target and behaviour policies. The relative probability of a trajectory from \(t\) to the end under the two policies, the importance-sampling ratio, is

Notice the environment's transition probabilities, though unknown, appear identically in numerator and denominator and so cancel — the ratio depends only on the two policies and the sequence of actions, not on the model. To estimate \(v_\pi\), we then scale the returns generated under \(b\) by \(\rho\) and average. This requires the coverage assumption: every action taken under \(\pi\) must also be possible under \(b\) (\(\pi(a\mid s)>0 \Rightarrow b(a\mid s)>0\)).

Ordinary vs weighted importance sampling

There are two ways to combine the scaled returns. Ordinary importance sampling divides the sum of scaled returns by the number of episodes — it is unbiased but can have very high (even infinite) variance. Weighted importance sampling divides by the sum of the weights \(\rho\) — it is biased (the bias converges to zero) but has dramatically lower variance and is strongly preferred in practice. The bias–variance trade-off here is a recurring theme in off-policy learning.

Where MC sits — and what comes next

Monte Carlo methods learn value functions and optimal policies from experience in the form of sample episodes, which gives them at least three advantages over DP: they can learn optimal behaviour directly from interaction with the environment, with no model; they can be used with simulation or sample models; it is easy and efficient to focus on a small subset of states. A fourth advantage (developed later) is that they may be less harmed by violations of the Markov property, because they do not bootstrap. Their main limitation: they must wait until the end of an episode before updating, and their estimates have higher variance because a full return depends on many random actions and transitions.

Lecture map & recap

References & the vault

• ← Book Explained (all chapters)
• ← Chapter 4 — Dynamic Programming
• CS6–CS7 — Slides Explained · the lecture version
• Sutton & Barto — RL: An Introduction (2e), free PDF · Chapter 5