Off-Policy Correction

Importance Sampling is the foundational statistical technique for off-policy correction. It re-weights the expectation of a target policy's return using the likelihood ratio between the target and behavior policies.

• Core Formula: The importance weight is (\rho_t = \frac{\pi(a_t|s_t)}{\mu(a_t|s_t)}), where (\pi) is the target policy and (\mu) is the behavior policy.
• Corrects Bias: By multiplying returns or TD errors by (\rho_t), it provides an unbiased estimate of the target policy's value, but can introduce high variance, especially with long trajectories.
• Use Case: The theoretical basis for more advanced methods; often used in simple or tabular settings.

Per-Decision Importance Sampling is an optimization of naive IS that applies importance weights only to future rewards affected by a given action, significantly reducing variance.

• Key Insight: The importance of an action only matters for rewards received after that action is taken. Rewards before the action are independent of the policy change.
• Variance Reduction: By trimming unnecessary weights, it produces a lower-variance estimator than full-trajectory IS, making it more practical for Monte Carlo off-policy evaluation.
• Foundation: Serves as a core component within more integrated algorithms like Retrace.

Retrace(λ) is a low-variance, safe off-policy return estimator that uses truncated importance sampling and is guaranteed to converge for any behavior policy.

• Truncated Weights: Uses (c_t = \lambda \min(1, \frac{\pi(a_t|s_t)}{\mu(a_t|s_t)})) as a trace coefficient. The (\min(1, \cdot)) clipping ensures stability.
• Safe & Efficient: Provides a good bias-variance trade-off. It is "safe" because the clipping guarantees convergence even with arbitrary off-policy data.
• Application: Used as a drop-in replacement for TD(λ) in algorithms like ACER to compute corrected Q-value targets.

V-trace is an off-policy correction algorithm designed for proximal policy optimization in distributed actor-critic architectures, notably used in IMPALA.

• Dual Clipping: Introduces two clipping parameters: (\bar{\rho}) for variance control on the value function target, and (\bar{c}) for bias control on the policy gradient.
• Target Policy Optimization: The (\bar{\rho}) clip creates a conservatively updated target value function, while the policy is improved towards a clipped target policy.
• Industry Use: Enables stable training from massively parallel, lagged actors generating experience with slightly stale policies.

The Tree-Backup algorithm performs off-policy correction without importance sampling by recursively bootstrapping on the target policy's action probabilities.

• Mechanism: For an n-step update, the return is built by taking the actual action at time t, but for future steps, it uses the expected value under the target policy, not sampled actions.
• Eliminates IS: Avoids importance weights entirely, leading to low variance but introducing bias if the behavior policy deviates significantly.
• Hybrid Form: Often combined with IS in algorithms like Q(σ) to navigate the bias-variance spectrum.

Q(λ) with Off-Policy Correction (Watkins's Q(λ) or Peng's Q(λ)) extends TD(λ) to the off-policy control setting by carefully managing eligibility traces.

• Watkins's Q(λ): Resets the eligibility trace to zero on exploratory (non-greedy) actions. This makes it highly off-policy but can slow learning.
• Peng's Q(λ): Does not zero traces on non-greedy actions, making it more efficient but technically semi-gradient. It's a popular pragmatic choice.
• Role: Provides a mechanism for multi-step learning in classic off-policy control algorithms like Q-learning.

Importance sampling is the foundational statistical technique used to estimate an expectation under one distribution (the target policy) using samples drawn from another distribution (the behavior policy). In off-policy RL, it provides the initial, often high-variance, weight correction:

• Core Formula: The importance sampling ratio is ( \rho_t = \frac{\pi(a_t|s_t)}{\mu(a_t|s_t)} ), where (\pi) is the target policy and (\mu) is the behavior policy.
• Variance Challenge: Direct use leads to unstable updates, especially with long trajectories, due to the product of many ratios.
• Role in Correction: Algorithms like Retrace and V-trace build upon this concept by introducing clipped or decaying ratios to control variance while maintaining consistency.

Temporal Difference error is the primary learning signal in value-based reinforcement learning, representing the difference between current value estimates and bootstrapped targets. It is central to prioritization and correction:

• Definition: For a transition ((s_t, a_t, r_t, s_{t+1})), the one-step TD error is ( \delta_t = r_t + \gamma V(s_{t+1}) - V(s_t) ).
• Connection to PER: Prioritized Experience Replay uses the magnitude of the TD error (|\delta_t|) to determine sampling probability, focusing learning on surprising transitions.
• Target for Correction: Off-policy correction methods like V-trace compute a modified, policy-corrected TD error across multiple steps to create a stable target for the value function.

N-Step returns unify Monte Carlo (full trajectory) and one-step Temporal Difference methods by bootstrapping after N real steps. They are a key building block for multi-step off-policy correctors:

• Trade-off Control: Adjusting N balances the bias of TD methods with the variance of Monte Carlo returns.
• Off-Policy Challenge: Using raw N-step returns with data from a different policy introduces bias. Tree Backup and Retrace(λ) algorithms are designed to compute corrected N-step returns.
• V-trace Example: The V-trace target is essentially a form of λ-return, where the horizon is controlled by a discount factor and the trace is cut by clipping the importance sampling ratios.

The experience replay buffer is the data structure that stores past transitions ((s, a, r, s')) for later sampling. It is the physical substrate that enables off-policy learning and correction:

• Core Function: Decouples the behavior policy (which fills the buffer) from the target policy (which learns from it) by storing experiences in a FIFO queue.
• Implementation: Typically implemented as a circular buffer with fixed buffer capacity. Common sampling strategies include uniform random sampling and prioritized sampling.
• Necessity for Correction: Without a buffer mixing data from different policies, off-policy correction algorithms would have no diverse data to learn from. It provides the off-policy data that requires correction.

Retrace(λ) is a specific, efficient off-policy correction algorithm for evaluating a target policy (\pi) using traces generated by a behavior policy (\mu). It is a direct sibling to V-trace.

• Key Mechanism: It uses truncated importance sampling ratios ( c_t = \lambda \min(1, \frac{\pi(a_t|s_t)}{\mu(a_t|s_t)}) ) to cut the trace and control variance.
• Theoretical Guarantees: Retrace(λ) provides a low-variance, safe update (it never diverges) and is guaranteed to converge to the value function of the target policy under mild conditions.
• Application: Used in deep RL as a drop-in replacement for standard Q-learning updates to learn safely from any off-policy data, including noisy exploration or expert demonstrations.

V-trace is an off-policy actor-critic correction algorithm popularized by the IMPALA architecture for distributed reinforcement learning. It corrects value targets for policy evaluation.

• Dual Clipping: Uses two clipping parameters: (\bar{\rho}) for the value function update (can be unclipped) and (\bar{c}) for the policy gradient update (must be ≤1).
• Target Calculation: The V-trace target for state (s_t) is a corrected, multi-step return: ( v_t = V(s_t) + \sum_{k=t}^{t+n-1} \gamma^{k-t} (\prod_{i=t}^{k-1} c_i) \rho_k \delta_k V ).
• Practical Impact: Enabled stable, scalable training of agents across hundreds of machines using asynchronous, off-policy data, making it a cornerstone of modern large-scale RL.