Chapter 5 Monte Carlo Learning

This chapter we will introduce a model-free approach for deriving optimal policy.

Here, model-free means learning from experience without explicitly using an environment transition and reward model for planning. Monte Carlo methods estimate values by averaging sampled returns. Model-free methods can still use Bellman equations: TD learning and Q-learning approximate Bellman backups using sampled transitions. A neural network that represents a value or policy is not, by itself, an environment model.

Probably the following example can better illustrate

Example Flip a coin

The result (either head or tail) is denoted as a random variable $X$.

• if the result is head, then $X = +1$.

• if the result is tail, then $X = −1$.

The aim is to compute $\mathbb E[X]$.

The model-based approach is to calculate the expectation through the definition.

$$\mathbb E[X] = \sum_{x} p(x)x = 0.5 \times 1 + 0.5 \times (-1) = 0$$

Problem: it may be impossible to know the precise distribution!!

The model-free approach is based on sampling.

We flip the coin many times, and then calculate the average of the outcomes.

Suppose we get a sample sequence: ${x_1, x_2, . . . , x_N}$. Then, the mean can be approximated as:

$$\mathbb{E[X]} \simeq \bar{x} = \sum_{j=1}^{N} \tfrac{x_j}{N}$$

This is the idea of Monte Carlo estimation and it is supported by the Law of Large Numbers to be accurate.

Monte Carlo (MC) Basic Algorithm

The policy iteration involves two processes, namely policy evaluation and policy improvement.

As mentioned before, the differences between model-based and model-free is policy evaluation in which how to gain the action value is of paramount importance.

model-based and model-free approach for calculating action value

Here we use the expression 2, namely estimate the expectation of every state-action pair as their real value.

Here is a thorough statement and the corresponding pseudocode.

Given an initial policy $\pi_{0}$, there are two steps at the $k$th iteration.

1. Step 1 Policy Evaluation: This step is to obtain $q_{\pi_{k}}(s, a)$ for all $(s, a)$. Specifically, for each action-state pair $(s, a)$, run an infinite number of (or sufficiently many) episodes. The average of their returns is used to approximate $q_{\pi_{k}}(s, a)$.

2. Step 2 Policy Improvement: Just like the policy improvement in the policy iteration. Acquire the maximum action value in every state.

Exactly the same as the policy iteration algorithm, except that we estimate $q_{\pi_{k}}(s, a)$ directly, instead of solving $v_{\pi_{k}}(s)$.

MC Basic (a model-free variant of policy iteration)

Questions

Why does MC Basic estimate action values instead of state values?

• For the greedy policy-improvement step used here, state values alone are insufficient to compare actions without an environment model. Estimating action values directly provides those comparisons. Later, actor-critic methods will use sampled transitions and a state-value baseline to update a parameterized policy.

• With exact evaluation, this procedure reduces to policy iteration. Finite-sample Monte Carlo estimates introduce error; convergence claims require appropriate sampling, coverage, and evaluation accuracy, rather than merely a large finite number of episodes.

Monte Carlo (MC) Exploring Starts Algorithm

In MC Basic Algorithm, we have to start from every state-action pair and do many samplings to estimate, which is less efficient. In detail, the episode also visits many other state-action pairs such as $(s_2, a_4), (s_2, a_3)$, and $(s_5, a_1)$. These visits can also be used to estimate the corresponding action values. In particular, we can decompose the episode into multiple subepisodes:

subepisodes

Compare with MC Basic, MC Exploring Starts sufficiently utilize data. The method goes:

Given a episode, it also focuses on other state-action pairs. Each can be regarded as a start and can be used to do a self-estimation.

For data appears in one episode, there are two methods:

• first-visit: only the one first appear in the episode will be leveraged to do average.

• every-visit: no matter how many times it appear, all will be used to do average.

For when to update the policy. Also, there are two methods:

• The first method is, in the policy evaluation step, to collect all the episodes starting from a state-action pair and then use the average return to approximate the action value.

This is the one adopted by the MC Basic algorithm.

The problem of this method is that the agent has to wait until all episodes have been collected.

• The second method updates value estimates with returns from each completed episode, then improves the policy without waiting for a full evaluation. Each return is a noisy sample, so repeated visits and suitable averaging or step sizes still matter. Exploring starts supplies coverage of the state-action pairs.

In this way, we can improve the policy episode-by-episode.

In fact, this strategy falls into the scope of generalized policy iteration introduced in the last chapter. That is, we can still update the policy even if the value estimate is not sufficiently accurate.

MC Exploring Starts (an efficient variant of MC Basic)

Here $g$ is the cumulative discounted return starting from current timestep $t$. But it is derived backward from $T-1$ to $t$.

Ordinary full-return MC waits until the episode terminates before calculating its returns. However, the value estimate can be updated incrementally between episodes, for example $Q_{N+1}=Q_N+(G_{N+1}-Q_N)/(N+1)$. Thus, waiting for a complete return is different from being unable to maintain an incremental mean. The full-episode algorithm described here assumes episodes terminate; continuing tasks require additional treatment such as truncated returns.

Q: if a state-action pair does not appear in the first episode. How to calculate the average action value?

A: At the beginning of the algorithm, all Return(s, a) are initialized as 0. If not appearing, it will remain 0.

Monte Carlo (MC) $\varepsilon$-greedy Algorithm

A policy is called soft if the probability to take any action is positive.

A soft policy gives each action positive probability at a visited state, which can replace exploring starts when suitable reachability, reset, and exploration conditions ensure sufficient coverage. It does not guarantee that a few long episodes will visit every state-action pair; some states may be unreachable from the available starts.

The difference between exploring starts and $\varepsilon$-greedy is just the policy turned from deterministic to stochastic. That is, to integrate $\varepsilon$-greedy policies into MC learning, we only need to change the policy improvement step from greedy to $\varepsilon$-greedy.

$\varepsilon$-greedy policy

$\varepsilon$-greedy algorithm

It does not require exploring starts, but still requires to visit all state-action pairs in a different form.

There are two parameters, namely the $\varepsilon$ and the step length of the episode. All of them will affect the algorithm performance.

We can see from below examples:

example

example

A fixed positive $\varepsilon$ maintains exploration but generally prevents an unconstrained optimal policy when it assigns probability to strictly suboptimal actions. Stochasticity itself does not imply suboptimality: mixing among equally optimal actions can still be optimal. Also, the greedy part of a learned $\varepsilon$-greedy policy is not automatically optimal. Here, consistent means that its greedy actions agree with those of an optimal policy, which must be checked rather than assumed.

Iteration

consistency

We can see when $\varepsilon$ is large, the policy is not consistent with optimal policy.

In practice, $\varepsilon$ controls the exploration trade-off. Tabular convergence results can use a policy that is greedy in the limit with infinite exploration, together with suitable step sizes and other assumptions. A greedy evaluation policy may be extracted after learning, but turning exploration off alone does not prove that it is optimal.