MC Control without Exploring Starts

In our initial look at Monte Carlo Control, we assumed the ability to use "exploring starts." This assumption means that every possible state-action pair $(s, a)$ has a non-zero chance of being the starting point of an episode. By starting episodes across the full range of possibilities, we could guarantee that our agent eventually gathered experience (and calculated returns) for all actions in all relevant states, allowing it to learn the optimal action-value function $Q^*(s, a)$.

However, the exploring starts assumption is often unrealistic. In many simulations or physical systems, we don't have the luxury of initiating an episode from any arbitrary state-action pair. Consider training a robot to navigate a maze: you can probably reset it to the official start state, but you likely can't force it to begin mid-maze having just taken a specific turn. Similarly, in games, you usually start from a predefined initial state. If we only ever start from one state and always follow our current best guess for the policy (acting greedily), we might never try certain actions in certain states, leaving potential improvements undiscovered. We might find a locally optimal policy without ever realizing a much better one exists, reachable only through actions we never explored.

How can we ensure sufficient exploration to find the optimal policy if we cannot rely on exploring starts? The answer lies in modifying the policy itself to incorporate exploration. We'll focus here on on-policy methods, where the agent learns about the same policy it uses to make decisions.

Ensuring Exploration with Epsilon-Soft Policies

The core idea is simple: instead of always choosing the action believed to be best (the greedy action), the agent should occasionally choose an action at random. This ensures that, over time, all actions get sampled from all visited states.

A common approach to achieve this in on-policy learning is to use $\epsilon$-soft policies. An $\epsilon$-soft policy is one that assigns a minimum probability, $\frac{\epsilon}{|\mathcal{A}(s)|}$, to selecting any action $a$ in state $s$, where $|\mathcal{A}(s)|$ is the number of available actions in that state and $\epsilon$ is a small positive number (e.g., 0.1).

Specifically, for an $\epsilon$-soft policy $\pi$:

• The action $a^*$ that currently appears best according to the action-value function $Q(s, a)$ (i.e., $a^* = \arg\max_a Q(s, a)$) is chosen with probability $1 - \epsilon + \frac{\epsilon}{|\mathcal{A}(s)|}$.
• All other non-greedy actions are chosen with probability $\frac{\epsilon}{|\mathcal{A}(s)|}$.

Mathematically, the policy $\pi(a|s)$ is defined as:

$$\pi(a|s) = \begin{cases} 1 - \epsilon + \frac{\epsilon}{|\mathcal{A}(s)|} & \text{if } a = \arg\max_{a'} Q(s, a') \\ \frac{\epsilon}{|\mathcal{A}(s)|} & \text{if } a \neq \arg\max_{a'} Q(s, a') \end{cases}$$

This ensures that $\pi(a|s) > 0$ for all state-action pairs. The parameter $\epsilon$ controls the trade-off between exploration (trying random actions) and exploitation (choosing the best-known action). A higher $\epsilon$ means more exploration; a lower $\epsilon$ means more exploitation.

On-Policy MC Control with Epsilon-Soft Policies

How does this fit into our Monte Carlo control loop, which follows the pattern of Generalized Policy Iteration (GPI)?

1. Policy Evaluation: We use the current $\epsilon$-soft policy $\pi$ to generate complete episodes of experience. We then estimate the action-value function $Q^\pi(s, a)$ by averaging the returns observed following each state-action pair $(s, a)$ across these episodes (using either first-visit or every-visit MC prediction). Because the policy is $\epsilon$-soft, we are guaranteed to eventually sample all actions from any state that is visited.
2. Policy Improvement: Having updated our estimate of $Q^\pi$, we improve the policy. We make the policy greedy with respect to the new action-value estimates. However, to maintain exploration, the improved policy $\pi'$ is not purely greedy but is constructed to be $\epsilon$-soft based on the new greedy actions. For each state $s$, find the action $a^* = \arg\max_a Q^\pi(s, a)$. The new policy $\pi'$ is then set according to the $\epsilon$-soft definition above, using $a^*$ as the greedy action.

This cycle of evaluation using an $\epsilon$-soft policy and improvement towards an $\epsilon$-soft greedy policy continues. The process drives the policy towards an optimal $\epsilon$-soft policy. This policy is the best possible policy within the constraint that it must explore with probability $\epsilon$. It's optimal among the class of $\epsilon$-soft policies.

In practice, it's common to start with a larger $\epsilon$ (encouraging exploration early on) and gradually decrease it over time. If $\epsilon$ decays towards zero, the policy approaches the truly optimal policy $\pi^*$. However, ensuring convergence requires careful management of the decay schedule and theoretical conditions (like ensuring infinite exploration of all pairs, often summarized as GLIE - Greedy in the Limit with Infinite Exploration).

By using $\epsilon$-soft policies, on-policy Monte Carlo methods can effectively learn optimal behavior even when exploring starts are not feasible, making them applicable to a wider range of problems where learning must occur solely through ongoing interaction. The next section details the algorithm for On-Policy First-Visit MC Control using this approach.