On-Policy MC Control

Why Does This Exist?

In model-free reinforcement learning, an agent does not have access to transition probabilities $p(s', r \mid s, a)$. To make decisions without knowing the environment's underlying physics, the agent cannot simply learn state values $v(s)$; it must learn action values $q(s, a)$. With $q(s, a)$ in hand, acting greedily is straightforward: choose $\arg\max_a q(s, a)$ without looking one step ahead into unknown future states.

However, estimating action values from sampled experience creates a fundamental exploration dilemma. If an agent behaves according to a deterministic policy $\pi(s)$, it will always choose the same action from a given state. Alternative actions from that state will never be sampled, their returns will never be observed, and the agent can never discover whether an untested branch holds higher reward.

The theoretical solution used in early Monte Carlo control is the Assumption of Exploring Starts: every episode begins at a state-action pair $(s_0, a_0)$ sampled with non-zero probability across all possible pairs in $\mathcal{S} \times \mathcal{A}$. While mathematically convenient, exploring starts is practically impossible in real systems. An autonomous car cannot be initialized in mid-collision on step zero; a chemical plant cannot be booted directly into an explosive pressure state; a game of chess must always begin at the standard opening board.

Without exploring starts, reinforcement learning divides into two paradigms:

1. Off-policy learning: The agent uses an exploratory behavior policy $b$ to generate transitions, while using importance sampling ratios to evaluate and improve a distinct target policy $\pi$.
2. On-policy learning: The agent evaluates and improves the very same policy that it uses to generate decisions in the environment.

On-Policy First-Visit Monte Carlo Control solves the exploration bottleneck without exploring starts by constraining the policy to remain $\varepsilon$-soft. By assigning a minimum probability of selection to every available action at every state, the agent guarantees that all state-action pairs will be sampled infinitely often as training proceeds, enabling true model-free Generalized Policy Iteration from arbitrary fixed starting states.

Think of It Like This

How It Actually Works

Eliminating Exploring Starts via $\varepsilon$-Soft Policies

Let $\mathcal{S}$ denote the set of states, and $\mathcal{A}(s)$ denote the finite set of actions available in state $s$. A policy $\pi(a \mid s)$ defines the probability of selecting action $a$ given state $s$.

An $\varepsilon$-soft policy is any stochastic policy where the probability of choosing any available action is strictly bounded below:

where $\varepsilon \in (0, 1]$. Because every action maintains non-zero probability at every visit, every state-action pair $(s, a)$ reachable under the environment dynamics is guaranteed to be visited infinitely often as the number of episodes approaches infinity.

Among all valid $\varepsilon$-soft policies, the policy that places maximum probability on the best-performing action is the $\varepsilon$-greedy policy:

where ties for the maximal action value are broken arbitrarily.

The non-greedy actions (of which there are $|\mathcal{A}(s)| - 1$) each receive an exploration share of $\frac{\varepsilon}{|\mathcal{A}(s)|}$. Their combined mass is:

Summing the greedy and non-greedy action probabilities confirms that $\pi(\cdot \mid s)$ is a valid probability distribution:

Policy Improvement Theorem for $\varepsilon$-Soft Policies

In Generalized Policy Iteration (GPI), we alternate between policy evaluation (updating $Q \approx q_\pi$) and policy improvement (updating $\pi \approx \text{greedy}(Q)$). For on-policy MC control to work, shifting from an $\varepsilon$-greedy policy $\pi$ to a new $\varepsilon$-greedy policy $\pi'$ with respect to $q_\pi$ must guarantee that the expected return does not decrease.

Let $q_\pi(s, a)$ be the true action-value function under policy $\pi$. The expected value of state $s$ when taking actions according to the new $\varepsilon$-greedy policy $\pi'$ is:

Substituting the definition of the $\varepsilon$-greedy policy $\pi'$:

Now consider the expected value of state $s$ under the original policy $\pi$:

Notice that the weighting coefficients $w(a) = \frac{\pi(a \mid s) - \frac{\varepsilon}{|\mathcal{A}(s)|}}{1 - \varepsilon}$ are non-negative (since $\pi(a \mid s) \ge \frac{\varepsilon}{|\mathcal{A}(s)|}$) and sum to $1$:

Because any convex combination (weighted average) of numbers cannot exceed their maximum:

Multiplying by $(1 - \varepsilon)$ and adding the uniform baseline $\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_a q_\pi(s, a)$ to both sides gives:

By the Policy Improvement Theorem, if $q_\pi(s, \pi'(s)) \ge v_\pi(s)$ for all states $s$, then:

Equality holds if and only if $\pi$ is already optimal among all $\varepsilon$-soft policies. Thus, every $\varepsilon$-greedy policy improvement step strictly increases or maintains performance within the space of $\varepsilon$-soft policies.

Complete Algorithm: On-Policy First-Visit MC Control

The full algorithm proceeds episode by episode without needing a transition model or exploring starts:

1. Initialization:

   • Set $Q(s, a) \in \mathbb{R}$ arbitrarily (typically $0.0$) and visit counts $N(s, a) \leftarrow 0$ for all $s \in \mathcal{S}, a \in \mathcal{A}(s)$.
   • Initialize $\pi(a \mid s)$ as an arbitrary $\varepsilon$-soft policy (e.g., uniform probability $\frac{1}{|\mathcal{A}(s)|}$).
   • Fix discount factor $\gamma \in [0, 1]$ and exploration parameter $\varepsilon \in (0, 1]$.

2. Episode Generation:

   • Sample a complete trajectory using behavior policy $\pi$: $$S_0, A_0, R_1, S_1, A_1, R_2, \dots, S_{T-1}, A_{T-1}, R_T, S_T$$

3. Backward Return Accumulation & First-Visit Update:

   • Initialize cumulative return $G \leftarrow 0$.
   • For each step $t = T-1, T-2, \dots, 0$: $$G \leftarrow \gamma G + R_{t+1}$$
   • First-Visit Gate: Check if the pair $(S_t, A_t)$ appeared earlier in the episode (i.e., at any index $k < t$).
   • If $(S_t, A_t)$ is visited for the first time:
     • Increment count: $N(S_t, A_t) \leftarrow N(S_t, A_t) + 1$
     • Update action value via incremental sample average: $$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \frac{1}{N(S_t, A_t)} \left[ G - Q(S_t, A_t) \right]$$
     • Determine best action: $A^* \leftarrow \arg\max_a Q(S_t, a)$
     • Update policy $\pi(\cdot \mid S_t)$ for all $a \in \mathcal{A}(S_t)$: $$\pi(a \mid S_t) \leftarrow \begin{cases} 1 - \varepsilon + \dfrac{\varepsilon}{|\mathcal{A}(S_t)|} & \text{if } a = A^* \\[6pt] \dfrac{\varepsilon}{|\mathcal{A}(S_t)|} & \text{if } a \neq A^* \end{cases}$$

Worked numerical example

Consider a decision state $s$ with 3 available actions: $\mathcal{A}(s) = \{a_1, a_2, a_3\}$ ($|\mathcal{A}| = 3$), discount factor $\gamma = 0.9$, and exploration parameter $\varepsilon = 0.3$.

Initial Values and Baseline Policy

Prior to the current episode, the agent has recorded:

• $Q(s, a_1) = 2.0$ with $N(s, a_1) = 4$
• $Q(s, a_2) = 1.0$ with $N(s, a_2) = 2$
• $Q(s, a_3) = 0.5$ with $N(s, a_3) = 1$

The current greedy action is $a^* = a_1$. Under $\varepsilon = 0.3$, the exploratory allocation per action is:

The baseline $\varepsilon$-greedy policy assigns:

Episode Generation

At time step $t=0$, the agent is in state $s$. A random roll falls into the exploratory interval, selecting action $a_2$ (drawn with probability $0.10$).

The episode continues through subsequent states, generating transition rewards:

• Step $0$: $(s, a_2) \to$ reward $R_1 = +1.0$, next state $s_1$
• Step $1$: $(s_1, a_1) \to$ reward $R_2 = +4.0$, next state $s_2$
• Step $2$: $(s_2, a_3) \to$ reward $R_3 = +10.0$, terminal state $s_T$

Backward Return Computation

Iterating backward from terminal state $s_T$ with $\gamma = 0.9$:

• Step $2$: $G_2 = R_3 = 10.0$
• Step $1$: $G_1 = R_2 + \gamma G_2 = 4.0 + 0.9(10.0) = 4.0 + 9.0 = 13.0$
• Step $0$: $G_0 = R_1 + \gamma G_1 = 1.0 + 0.9(13.0) = 1.0 + 11.7 = 12.7$

First-Visit Update for $(s, a_2)$

We inspect the trajectory: pair $(s, a_2)$ appeared only at $t=0$. The first-visit condition is satisfied.

1. Increment visit count: $$N(s, a_2) \leftarrow 2 + 1 = 3$$
2. Update action-value estimate $Q(s, a_2)$: $$Q_{\text{new}}(s, a_2) = Q_{\text{old}}(s, a_2) + \frac{1}{N(s, a_2)} \left[ G_0 - Q_{\text{old}}(s, a_2) \right]$$ $$Q_{\text{new}}(s, a_2) = 1.0 + \frac{1}{3} \left( 12.7 - 1.0 \right) = 1.0 + \frac{11.7}{3} = 1.0 + 3.9 = 4.9$$

Policy Improvement Step

Compare the updated action values at state $s$:

• $Q(s, a_1) = 2.0$
• $Q(s, a_2) = 4.9$
• $Q(s, a_3) = 0.5$

The greedy action flips from $a_1$ to $a_2$ because $4.9 > 2.0$. The policy $\pi(\cdot \mid s)$ updates immediately:

Through exploratory sampling on-policy, the agent discovered that $a_2$ leads to high long-term returns, updated $Q(s, a_2)$, and shifted $80\%$ of its future action selection mass onto $a_2$ without requiring exploring starts.

Code

The following self-contained Python implementation trains an agent on a gridworld navigation task using on-policy first-visit Monte Carlo control. The agent begins at $(0, 0)$ and must reach the goal $(2, 2)$ while accumulating $-1$ reward per step:

1import random2from typing import Dict, List, Tuple3
4
5class GridWorld:6    """A 3x3 gridworld navigation task where reaching (2, 2) is terminal."""7
8    def __init__(self, width: int = 3, height: int = 3) -> None:9        self.width = width10        self.height = height11        self.start = (0, 0)12        self.goal = (width - 1, height - 1)13        self.state = self.start14        self.num_actions = 415        # Actions: 0: Up, 1: Down, 2: Left, 3: Right16        self.moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]17
18    def reset(self) -> Tuple[int, int]:19        """Reset environment to standard start state."""20        self.state = self.start21        return self.state22
23    def step(self, action: int) -> Tuple[Tuple[int, int], float, bool]:24        """Apply action, returning next_state, reward, and done flag."""25        dr, dc = self.moves[action]26        nr = max(0, min(self.height - 1, self.state[0] + dr))27        nc = max(0, min(self.width - 1, self.state[1] + dc))28        self.state = (nr, nc)29        reward = -1.030        done = (self.state == self.goal)31        return self.state, reward, done32
33
34class OnPolicyFirstVisitMCControl:35    """On-policy first-visit Monte Carlo control using epsilon-soft policies."""36
37    def __init__(38        self,39        env: GridWorld,40        epsilon: float = 0.2,41        gamma: float = 0.9,42    ) -> None:43        self.env = env44        self.epsilon = epsilon45        self.gamma = gamma46        self.num_actions = env.num_actions47
48        # Initialize Q-values and visit counts for all state-action pairs49        self.Q: Dict[Tuple[int, int], List[float]] = {50            (r, c): [0.0] * self.num_actions51            for r in range(env.height)52            for c in range(env.width)53        }54        self.N: Dict[Tuple[int, int], List[int]] = {55            (r, c): [0] * self.num_actions56            for r in range(env.height)57            for c in range(env.width)58        }59
60    def select_action(self, state: Tuple[int, int]) -> int:61        """Select action according to current epsilon-greedy policy."""62        if random.random() < self.epsilon:63            # Explore: uniform random selection across all actions64            return random.randint(0, self.num_actions - 1)65        # Exploit: pick greedy action with random tie-breaking66        q_vals = self.Q[state]67        max_q = max(q_vals)68        best_actions = [a for a, q in enumerate(q_vals) if q == max_q]69        return random.choice(best_actions)70
71    def generate_episode(72        self, max_steps: int = 10073    ) -> List[Tuple[Tuple[int, int], int, float]]:74        """Roll out an episode under the epsilon-soft policy."""75        episode: List[Tuple[Tuple[int, int], int, float]] = []76        state = self.env.reset()77        for _ in range(max_steps):78            if state == self.env.goal:79                break80            action = self.select_action(state)81            next_state, reward, done = self.env.step(action)82            episode.append((state, action, reward))83            state = next_state84            if done:85                break86        return episode87
88    def train(self, num_episodes: int = 3000) -> None:89        """Run on-policy first-visit Monte Carlo control across episodes."""90        for _ in range(num_episodes):91            episode = self.generate_episode()92            if not episode:93                continue94
95            # Identify the first occurrence step index for each (state, action) pair96            first_occurrence: Dict[Tuple[Tuple[int, int], int], int] = {}97            for t, (s, a, _) in enumerate(episode):98                if (s, a) not in first_occurrence:99                    first_occurrence[(s, a)] = t100
101            # Backward pass to accumulate discounted return G102            G = 0.0103            for t in reversed(range(len(episode))):104                s, a, r = episode[t]105                G = self.gamma * G + r106
107                # First-visit update condition108                if first_occurrence[(s, a)] == t:109                    self.N[s][a] += 1110                    # Incremental sample average update111                    self.Q[s][a] += (G - self.Q[s][a]) / self.N[s][a]112
113    def get_greedy_policy(self) -> Dict[Tuple[int, int], str]:114        """Extract dominant greedy direction for each state."""115        action_chars = {0: "^", 1: "v", 2: "<", 3: ">"}116        policy: Dict[Tuple[int, int], str] = {}117        for s, q_vals in self.Q.items():118            if s == self.env.goal:119                policy[s] = "G"120            else:121                best_a = max(range(self.num_actions), key=lambda a: q_vals[a])122                policy[s] = action_chars[best_a]123        return policy124
125
126# Execution and validation127if __name__ == "__main__":128    random.seed(42)129    env = GridWorld(width=3, height=3)130    agent = OnPolicyFirstVisitMCControl(env, epsilon=0.2, gamma=0.9)131    agent.train(num_episodes=3000)132
133    policy = agent.get_greedy_policy()134    print("Learned Greedy Policy:")135    for r in range(3):136        row = [f" {policy[(r, c)]} " for c in range(3)]137        print("".join(row))138
139    print("\nState-Action Values Q(s, a) at Start State (0, 0):")140    action_labels = ["Up   ", "Down ", "Left ", "Right"]141    for a, name in enumerate(action_labels):142        print(f"  {name}: {agent.Q[(0, 0)][a]:.2f} (Visits: {agent.N[(0, 0)][a]})")

Expected Output

1Learned Greedy Policy:2 v  v  v 3 >  v  v 4 >  >  G 5
6State-Action Values Q(s, a) at Start State (0, 0):7  Up   : -4.55 (Visits: 166)8  Down : -3.90 (Visits: 2829)9  Left : -4.56 (Visits: 188)10  Right: -3.98 (Visits: 189)

Watch Out For

The Quick Version

• On-Policy Monte Carlo Control eliminates the unrealistic requirement of exploring starts by forcing the behavior policy to remain $\varepsilon$-soft ($\pi(a \mid s) \ge \frac{\varepsilon}{|\mathcal{A}(s)|} > 0$).
• The algorithm is strictly on-policy: it evaluates and improves the exact same $\varepsilon$-greedy distribution that generates trajectories in the environment.
• The Policy Improvement Theorem for $\varepsilon$-Soft Policies guarantees that choosing the greedy action with probability $1 - \varepsilon + \frac{\varepsilon}{|\mathcal{A}|}$ monotonically improves expected return: $q_\pi(s, \pi'(s)) \ge v_\pi(s)$.
• Returns are accumulated backwards along complete episodic rollouts, and action values $Q(s, a)$ are updated incrementally on the first visit of each state-action pair.
• The learned policy converges to $\pi_*^\varepsilon$ (the best $\varepsilon$-soft policy); annealing $\varepsilon \to 0$ over training bridges the gap to the globally optimal deterministic policy $\pi^*$.

What to Read Next

• Monte Carlo Exploring Starts
• Monte Carlo Control
• Epsilon-Greedy