On-Policy vs Off-Policy Learning

In reinforcement learning, an agent interacts with an environment by following some policy — a mapping from states to a distribution over actions. When we ask "what is the value of policy π?" we must specify whose actions generated the data used to estimate that value. This gives rise to two policies that a learning algorithm may juggle simultaneously: the behavior policy $b$, which actually selects actions and generates the observed trajectory, and the target policy $\pi$, whose value function or action-value function we are trying to learn.

On-policy learning occurs when $b = \pi$: the agent learns about the exact policy it is following. Classic examples include first-visit Monte Carlo control with ε-greedy policies, and SARSA: On-Policy TD Control. Because the data-generating policy and the evaluated policy coincide, updates directly reflect the returns the agent will actually experience, and no correction for distributional mismatch is needed. The tradeoff is that since $b$ must explore (e.g., be ε-greedy), the learned value function is only guaranteed to reflect the best exploratory policy, not the true optimal deterministic policy.

Off-policy learning occurs when $b \neq \pi$: the agent behaves according to $b$ (which explores) while learning about $\pi$ (often the greedy, optimal policy). This decoupling is powerful — it permits learning purely from historical logs, from a human demonstrator, or from a completely different exploration strategy — but it introduces a fundamental estimation problem. Returns observed under $b$ are samples from the wrong distribution of trajectories relative to $\pi$; naively averaging them estimates $b$'s value, not $\pi$'s. The standard fix is importance sampling, which reweights observed returns by the ratio of probabilities that $\pi$ versus $b$ would have produced the observed action sequence, covered in depth in Importance Sampling for Off-Policy Methods. Alternatively, some off-policy TD methods (like Q-learning) sidestep explicit importance sampling by directly bootstrapping off the target policy's greedy action-value, exploiting the structure of the Bellman optimality equation rather than reweighting whole trajectories. A key requirement for either paradigm to work is coverage: every state-action pair with nonzero probability under $\pi$ must have nonzero probability of being visited under $b$. Formally, $\pi(a\mid s) > 0 \implies b(a\mid s) > 0$. Without this, off-policy learning cannot observe the data needed to estimate $\pi$'s value at all — a structural precondition, not a numerical nicety.

Both paradigms slot into the same general model-free prediction/control loop; the difference lies in which policy chooses actions and which policy's values get updated.

On-policy control (as in Monte Carlo control or SARSA) improves the policy it is currently following. It alternates between (1) generating experience with the current (soft, exploratory) policy and (2) updating the value estimates and then policy toward greediness with respect to those estimates — but only within the space of policies that still explore.

Off-policy control maintains two policies explicitly: a behavior policy $b$ used to act (and explore), and a target policy $\pi$ (often deterministic-greedy) whose action-value function $Q_\pi$ we accumulate estimates of. The update rule must correct for the fact that actions were chosen by $b$, not $\pi$.

General on-policy TD control template

``` Initialize Q(s, a) arbitrarily for all s, a Initialize policy π to be ε-greedy with respect to Q repeat for each episode: s ← initial state a ← action chosen from s using π (ε-greedy on Q) repeat for each step of episode: take action a, observe reward r and next state s' a' ← action chosen from s' using π (ε-greedy on Q) # SAME policy used for update Q(s, a) ← Q(s, a) + α [ r + γ Q(s', a') − Q(s, a) ] s ← s' ; a ← a' until s is terminal ``` This is exactly the SARSA update — note that the action `a'` used inside the TD target is the actual next action the agent will take, sampled from the same ε-greedy policy that generated the trajectory. That is the hallmark of on-policy learning: the update target is consistent with the data-generating process.

General off-policy TD control template (Q-learning style)

``` Initialize Q(s, a) arbitrarily for all s, a Behavior policy b: e.g., ε-greedy with respect to Q (keeps exploring) repeat for each episode: s ← initial state repeat for each step of episode: a ← action chosen from s using b (ε-greedy, exploratory) take action a, observe reward r and next state s' Q(s, a) ← Q(s, a) + α [ r + γ max_{a'} Q(s', a') − Q(s, a) ] s ← s' until s is terminal ``` Here the TD target uses $\max_{a'} Q(s', a')$ — the value under the greedy target policy — regardless of which action $b$ actually takes next. The behavior policy explores freely; the bootstrap target always looks toward the greedy policy. This is why Q-learning is off-policy: the update evaluates $\pi_{\text{greedy}}$, but the trajectory was generated by $b$.

General off-policy Monte Carlo template with importance sampling

For episodic Monte Carlo prediction of $\pi$ using data from $b$, the update requires reweighting the return by the importance-sampling ratio: ``` Initialize Q(s, a) arbitrarily, C(s, a) ← 0 for all s, a b ← any soft policy with coverage of π (b(a|s) > 0 whenever π(a|s) > 0) repeat for each episode: generate an episode using b: s0, a0, r1, s1, a1, r2, ..., sT G ← 0 W ← 1 for t = T-1 downto 0: G ← γ G + r_{t+1} C(s_t, a_t) ← C(s_t, a_t) + W Q(s_t, a_t) ← Q(s_t, a_t) + (W / C(s_t, a_t)) [ G − Q(s_t, a_t) ] W ← W * π(a_t | s_t) / b(a_t | s_t) if W == 0: break # no more correction possible, stop early ``` This is weighted importance sampling applied backward through the trajectory; the ratio $W$ accumulates the likelihood ratio of the whole suffix under $\pi$ versus $b$, and the loop terminates early once $W$ hits zero (i.e., $\pi$ would never have taken an action that $b$ did).

Time and space complexity. Both on-policy and off-policy tabular TD control have identical per-step cost: $O(1)$ time and $O(1)$ additional memory per update (beyond the $O(|S||A|)$ table itself), since each step touches one $Q(s,a)$ entry and performs a constant number of arithmetic operations. Off-policy Monte Carlo with importance sampling is also $O(T)$ per episode of length $T$, same as on-policy Monte Carlo — the importance-sampling ratio is a single running product computed in $O(1)$ per step. So off-policy correction does not change the asymptotic per-step complexity; it changes the statistical properties of the estimator (variance) and the structural requirements (coverage).

Correctness of on-policy TD control (SARSA). SARSA's target $r + \gamma Q(s',a')$ is an unbiased sample of the Bellman expectation equation for the current ε-greedy policy $\pi$, because $a'$ is drawn from exactly that policy:

Under standard stochastic-approximation conditions (Robbins–Monro step sizes $\sum_t \alpha_t = \infty$, $\sum_t \alpha_t^2 < \infty$, plus GLIE — greedy in the limit with infinite exploration — policy updates), SARSA provably converges to the optimal action-value function $Q_*$ with probability 1 in the tabular case. The proof follows the same fixed-point contraction argument used for TD(0): the Bellman operator for a fixed policy is a $\gamma$-contraction in sup-norm, and as the policy becomes greedy in the limit, the sequence of policy evaluations tracks an increasingly optimal policy.

Correctness of off-policy TD control (Q-learning). Q-learning's target $r + \gamma \max_{a'} Q(s',a')$ is a sample of the Bellman optimality equation, independent of which policy chose the next action in the actual trajectory:

where $T_*$ is the Bellman optimality operator, a $\gamma$-contraction with unique fixed point $Q_*$. Because this target does not depend on the behavior policy's action-selection distribution at all (only that $s,a$ pairs are visited infinitely often), Q-learning converges to $Q_*$ under the same step-size conditions, regardless of what the behavior policy is, so long as it guarantees infinite visits to every state-action pair (coverage). This is the deep reason Q-learning needs no explicit importance-sampling ratio: the max operator already "hard-codes" the target policy into the update, sidestepping distributional correction.

Correctness of importance-sampling Monte Carlo. For off-policy Monte Carlo prediction, ordinary importance sampling gives an unbiased estimator of $v_\pi(s)$:

The proof is a direct change-of-measure computation: the probability of a trajectory under $\pi$ equals its probability under $b$ times $\rho_{t:T-1}$, so reweighting returns by this ratio exactly compensates for sampling from the wrong distribution. Weighted importance sampling (normalizing by cumulative $W$) trades a small bias for dramatically reduced variance, and is consistent (bias → 0 as sample count → ∞).

Tradeoffs, honestly stated.

• Variance: On-policy updates have bounded variance tied only to environment stochasticity. Off-policy importance sampling ratios $\rho$ can have unbounded variance — if $\pi$ and $b$ diverge sharply, a single trajectory's weight can explode, making naive off-policy Monte Carlo estimators wildly noisy despite being unbiased.
• What is learned: On-policy control learns the best policy within the exploratory family (e.g., best ε-greedy policy), never quite reaching the fully greedy optimum while ε > 0. Off-policy control can learn the fully greedy optimal policy while the agent behaves however is convenient or safe.
• Stability with function approximation: Off-policy learning combined with bootstrapping (TD-style updates) and function approximation forms the deadly triad — the combination can diverge (Q-values blow up) even though each ingredient is individually well-behaved. On-policy TD with function approximation has stronger (though not unconditional) convergence guarantees for linear approximators.

Consider a tiny 1-D gridworld: states $\{A, B, C\}$ with $C$ terminal, reward $+1$ on entering $C$ and $0$ otherwise, $\gamma = 1$. Two actions: `right` (intended direction) and `left`. Suppose the agent's true optimal policy is "always go right," but behavior policy $b$ is ε-greedy with ε = 0.5 (uniform over both actions half the time). Behavior policy $b$ generates one episode: `A →(right) B →(left) A →(right) B →(right) C`, with rewards `0, 0, 0, 1`.

On-policy (SARSA) update, using the actual next action taken by $b$:

SARSA's targets are contaminated by the exploratory `left` moves — e.g. step 1's target bootstraps off $Q(B,\text{left})$, a genuinely bad action, because that's what the agent is actually going to do next. SARSA is honestly estimating the ε-soft policy's value, warts and all.

Off-policy (Q-learning) update, using $\max_{a'} Q(s',a')$ regardless of what $b$ actually does next:

Even though step 2's action was the exploratory (suboptimal) `left`, the target still looks toward the best action from $A$ — Q-learning always bootstraps toward the greedy policy, so its Q-values converge toward $Q_*$ (the value of "always go right") even while behavior wanders. This is the concrete cash-value of the on-policy/off-policy distinction: same data, two different estimators, converging to two different (though related) objects.

Watkins's 1989 doctoral thesis proved that Q-learning converges to the optimal action-value function under mild conditions — remarkably, without requiring the behavior policy to be related to the target policy beyond ensuring adequate exploration. This was a conceptually striking result at the time: it showed learning could be fully decoupled from acting, a property that later became essential for reusing large offline datasets and human demonstration data in modern reinforcement learning systems.

Off-policy learning underlies almost all modern deep reinforcement learning at scale. DQN and its successors (Double DQN, Rainbow) rely on off-policy Q-learning to reuse a replay buffer of past experience many times, dramatically improving sample efficiency versus on-policy methods that must discard data after one use. Offline (batch) reinforcement learning — training entirely from fixed historical logs, common in recommendation systems, healthcare, and industrial control — is only possible because off-policy learning permits behavior and target policies to differ arbitrarily (subject to coverage). Off-policy actor-critic methods like DDPG, TD3, and SAC power continuous-control robotics research and simulated locomotion benchmarks. On-policy methods remain dominant where stability matters more than sample efficiency: PPO and TRPO, used heavily in RLHF pipelines for large language models, are on-policy precisely because they need reliable, low-variance policy-gradient estimates and are willing to pay the cost of discarding old rollouts. The choice between on-policy and off-policy design is, in effect, a choice between sample efficiency and stability — a tradeoff engineers make explicitly when choosing an algorithm for a production system.

Ask the tutor: Can you walk through why Q-learning's convergence proof does not depend on the behavior policy, using the Bellman optimality operator's contraction property?