PaperlayerView exact revision on arXiv

Source-linked AI summary

An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning

Richard S. Sutton, A. Rupam Mahmood, Martha White

arXiv:1503.04269v2cs.LG

TL;DR

The paper asks how parametric TD learning can remain stable when learning a target policy from off-policy data. It varies update emphasis according to the followon distribution and introduces emphatic TD(λ). The method is stable under general off-policy training, while empirical comparison with other methods remains future work.

  • Problem

    Off-policy TD learning with linear function approximation can be unstable because behavior-policy distributions and target-policy transitions do not align.

  • Method

    Emphatic TD(λ) varies update emphasis using importance sampling to reweight updates according to the followon distribution.

  • Results

    Emphatic TD(λ) is proven stable under general off-policy training, with per-step complexity linear in the number of parameters.

  • Takeaways & Limitations

    Compared with gradient-TD methods, emphatic TD(λ) uses one learned parameter vector and one step-size parameter while retaining linear per-step complexity.

  • Takeaways & Limitations

    A proper empirical comparison with other methods remains future work, and high variance can still arise with long eligibility traces and importance sampling.

Abstract

from arXiv · show

In this paper we introduce the idea of improving the performance of parametric temporal-difference (TD) learning algorithms by selectively emphasizing or de-emphasizing their updates on different time steps. In particular, we show that varying the emphasis of linear TD($λ$)'s updates in a particular way causes its expected update to become stable under off-policy training. The only prior model-free TD methods to achieve this with per-step computation linear in the number of function approximation parameters are the gradient-TD family of methods including TDC, GTD($λ$), and GQ($λ$). Compared to these methods, our _emphatic TD($λ$)_ is simpler and easier to use; it has only one learned parameter vector and one step-size parameter. Our treatment includes general state-dependent discounting and bootstrapping functions, and a way of specifying varying degrees of interest in accurately valuing different states.

1. Parametric Temporal-Difference Learning

Parametric TD learning uses temporal differences to learn long-term predictions with function approximation. This paper addresses the instability of such methods under off-policy training by varying update emphasis.

  • TD learning uses the change between successive predictions as an error signal for updating earlier predictions.
  • Off-policy learning estimates the target policy’s value function while data are generated by a different behavior policy.
  • Existing off-policy approaches trade computational cost, data requirements, storage, learning speed, or algorithmic complexity.
  • The paper varies TD(λ) update emphasis to reweight updates toward the followon distribution under the target policy.
  • Emphatic TD(λ) is presented as a simpler linear-complexity alternative with one learned parameter vector and one step-size parameter.

2. On-policy Stability of TD(0)

On-policy TD(0) stability is analyzed through the expected update matrix and its associated key matrix. Under stated distribution and feature assumptions, positive definiteness yields stability, while full convergence requires additional conditions.

  • Linear function approximation represents state values through the inner product of a parameter vector and state feature vector.
  • Stability is determined by the steady-state expectation of the random update matrix, lim_t→∞E[A_t].
  • The expected update matrix has the form Φ^⊤ wrapped around a key matrix and Φ, with positive definiteness of the key matrix supporting stability.
  • For on-policy TD(0), the key matrix is positive definite under the stated column-sum condition, making the algorithm stable.
  • Unique parameter convergence additionally assumes linearly independent features, while probability-one convergence requires further conditions and a step-size schedule.

3. Instability of Off-policy TD(0)

Off-policy TD(0) can diverge because behavior-policy state frequencies and target-policy transitions produce an unstable expected update. The θ→2θ example illustrates this mechanism directly.

  • The θ→2θ problem occurs when a transition maps estimates θ to 2θ, causing repeated updates to amplify the parameter.
  • On-policy trajectories constrain this problematic transition because entering the highly valued state must eventually be followed by an offsetting decrease or reward.
  • Off-policy data are generated by behavior policy µ while values are learned for target policy π, with importance sampling correcting action-probability differences.
  • The off-policy key matrix uses D_µ(I − γP_π), whose mismatched distribution and transition structure can make column sums negative and threaten positive definiteness.
  • In the example, the expected update has A = −0.2, so the algorithm is not stable.
  • Repeated equal-frequency transitions produce a positive net change in θ, and smaller step sizes reduce only the divergence rate.

4. Off-policy Stability of Emphatic TD(0)

The paper uses excursion-based emphasis to reweight off-policy TD(0) updates, producing a positive-definite key matrix and stability under general off-policy training.

  • Motivation: Off-policy learning is difficult because behavior and target policies induce different state distributions that function approximation can make indistinguishable.Importance sampling can reweight encountered states, but later approaches often optimize objectives weighted by the behavior distribution.
  • Excursion weighting: The excursion view treats each update as beginning a contemplated target-policy excursion from the current state sampled under the behavior distribution.Importance sampling ratios determine how likely observed actions are under the target policy relative to the behavior policy.
  • Emphatic TD(0): Followon emphasis uses a scalar trace F_t to emphasize or de-emphasize each update, with F_0 = 1 in the simplest off-policy algorithm.The followon trace induces a diagonal emphasis matrix F whose state weights are defined from long-run conditional expectations of F_t.
  • Stability result: Emphatic TD(0) is proven stable because its key and A matrices are positive definite, making it the simplest such linear-function-approximation TD algorithm.The emphasis weights the second state more than ten times as strongly as the first, reflecting its greater frequency under the target policy.

5. The General Case

The general case extends emphatic TD to state-dependent discounting, bootstrapping, and interest, while retaining a unified algorithmic formulation for varied predictive questions.

  • State-dependent discounting: State-dependent discounting defines how long rewards remain accumulated, including complete or partial soft termination without changing state transitions.Soft termination is useful for finite excursions, option models, and other predictive questions.
  • State-dependent discounting: In the five-state chain, discounting states at the ends terminates returns while actions and transitions continue indefinitely.The target policy’s correct values are 1, 1, 2, and then increase by one for successive states to the left.
  • State interest: Explicit interest functions specify which states should receive more accurate value estimates when function approximation cannot represent all states exactly.Choosing interest from features can shift accuracy toward underrepresented states and make the focus substantially more balanced.
  • General bootstrapping: The paper generalizes conventional λ to a state-dependent bootstrapping function λ(s), allowing different degrees of bootstrapping in different states.The resulting λ-return remains central to the theoretical forward-view interpretation of TD methods.
  • Final algorithm: The final emphatic TD(λ) algorithm is specified by four equations combining importance sampling, the followon trace, emphasis, and an eligibility trace.The followon trace F_t is scalar memory, while M_t is the nonnegative emphasis applied at step t.

6. Off-policy Stability of Emphatic TD(λ)

The paper proves that emphatic TD(λ), using followon-distribution-based emphasis, has a positive-definite key matrix and a stable expected update under general off-policy conditions. Stability requires assumptions including positive interest in every state; later work establishes almost-sure convergence with decreasing step sizes.

  • The key matrix is M(I − PπΓΛ)^−1(I − PπΓ), combining emphasis weighting with state-dependent discounting and bootstrapping.M contains emphasis weights, while Γ and Λ contain the discount and bootstrapping functions.
  • Under finite-state, coverage, discounting, feature-independence, and expectation-existence assumptions, the algorithm’s A matrix is positive definite and its expected update is stable.The theorem additionally assumes a behavior-policy stationary distribution with positive mass and strictly positive interest, stated in the surrounding proof.
  • Strictly positive interest i(s) for every state makes all key-matrix column sums positive, yielding positive definiteness and stability.The result is obtained after analyzing the emphasis-weighted key matrix and its column sums.
  • Yu later showed that emphatic TD(λ) converges with probability one under appropriately decreasing step sizes, although stability alone is not always sufficient for convergence.Convergence is to the unique fixed point of the deterministic algorithm.
  • The fixed point is characterized as a zero of the emphasis-weighted projected Bellman error for the λ-dependent Bellman operator.The operator accounts for state-dependent discounting and bootstrapping and has vπ as its fixed point.
  • If interest is zero in some states, the key matrix need not be positive definite; the paper conjectures positive semidefiniteness may suffice for convergence of states with nonzero emphasis.This conjecture could also remove the assumption that feature-matrix columns are linearly independent.

7. Derivation of the Emphasis Algorithm

Emphatic algorithms derive each time step’s emphasis by accounting for how earlier updates bootstrap through later states. The resulting total emphasis combines propagated prior emphasis with the current state’s intrinsic interest.

  • Emphatic algorithms update bootstrapped-from states in direct proportion to the emphasis assigned to the current update.If a later state is fully bootstrapped from, it receives corresponding emphasis.
  • The forward view of off-policy TD(λ) determines how each earlier value update bootstraps from later states under general discounting and bootstrapping.This relationship supplies the quantities needed to derive the emphasis recursion.
  • At time t, total emphasis sums propagated emphasis from all earlier times, weighted by their bootstrapping contributions, plus intrinsic interest i(S_t).This construction yields the emphasis recursion used by the algorithm.

8. Empirical Examples

The empirical examples illustrate emphatic TD’s stability under off-policy training while exposing potentially severe variance fluctuations. In the tested problems, emphatic TD converges where conventional off-policy TD diverges and achieves lower MSVE in one bounded example.

  • The paper presents these experiments as verification and elucidation of formal results, not as a thorough empirical comparison with other methods.The authors explicitly state that such a comparison is beyond the article’s scope.
  • Infinite variance in the followon-related variables left emphatic TD vulnerable to occasional extremely large parameter fluctuations.The expected value of F_t tends to zero in the example, but its variance is infinite.
  • Emphatic TD rapidly approached the correct value of zero in most runs, whereas off-policy TD diverged in every individual run.A few emphatic-TD trajectories made very large deviations before returning.
  • With a behavior policy favoring the left state while the target policy treated both states equally, conventional off-policy TD(0) diverged but emphatic TD(0) converged reliably to zero.The increased update variance motivated using α = 0.0001.
  • In a bounded 5-state example, both algorithms converged reliably, and emphatic TD achieved lower MSVE without establishing a general empirical advantage.The experiment used λ = 0, α = 0.001, θ0 = 0, and unit interest across states.
  • The experiments compare stochastic trajectories with a deterministic expected-update trajectory, which emphatic TD follows in an average sense for small step sizes.The deterministic update is θ̄_t+1 = θ̄_t + α(b − Aθ̄_t).

9. Conclusions and Future Work

The paper introduces emphatic TD(λ), which varies update emphasis to address instability in off-policy linear TD learning. It also identifies potential approximation-error benefits and outlines empirical comparisons and extensions as future work.

  • Emphatic TD(λ) uses step-to-step emphasis to address the instability of conventional TD(λ) with linear function approximation under off-policy training.The approach varies update strength based on importance sampling and is presented as a solution to this instability problem.
  • The method is intended to have lower variance than earlier importance-sampling approaches.The paper attributes this goal to its way of varying update emphasis over time.
  • Proper empirical comparison with other methods remains future work.The authors also identify extensions to action-value, control, true-online, weighted-importance-sampling, and least-squares methods as future directions.
  • Adjusting λ or i functions may improve the algorithm by preserving positive definiteness while reducing the variance of F_t.This is proposed as an alternative direction for improving the current emphasis design.
  • When parameters vary across steps, emphatic TD(λ) may improve asymptotic approximation error relative to conventional TD(λ).In an episodic example, emphasis increases linearly toward the final state while conventional TD(λ) weights all steps equally; this could improve asymptotic MSVE when features cannot represent the value function exactly.
Loading 1503.04269v2…