Discerning Temporal Difference Learning

Jianfei MaAAAI 2024 · DOI

Introduction

Temporal Difference (TD) learning is a fundamental method for value estimation in reinforcement learning (RL). Standard TD($\lambda$) algorithms rely on eligibility traces to distribute credit to past states, typically using a recency heuristic that assumes states visited more recently or frequently are more important. However, this "one-size-fits-all" approach often fails in environments with significant visitation imbalances or noisy rewards. This paper introduces Discerning Temporal Difference Learning (DTD), a framework that incorporates a flexible "emphasis function" to selectively weight state importance during credit assignment.

Methodology

The core contribution of DTD is the derivation of a "discerning $\lambda$-return" based on a fundamental mathematical identity that replaces the constant $(1-\lambda)$ weighting factor with a state-dependent term $(f_{t+n-1} - f_{t+n}\lambda)$.

The Emphasis Function ($f$)

The emphasis function $f$ assigns a non-negative "significance" value to each state. This allows the algorithm to:

  • Rebalance Visitation: By setting $f$ to the inverse of state visitation counts, DTD counteracts bias toward high-frequency states.
  • Filter Noise: By assigning low emphasis to states with high reward variance, the algorithm prevents noisy data from destabilizing the value function.
  • Prioritize Learning: Adaptive DTD uses the absolute expected TD error as a dynamic emphasis function, prioritizing states where the model is most "surprised."

The update rule is modified such that the eligibility trace becomes $e_t = \gamma \lambda e_{t-1} + f_t \phi_t$, and the weight update is scaled by $f_t$. This makes DTD a "magnitude-centric" approach to prioritization, similar in spirit to Prioritized Experience Replay (PER) but implemented through online updates.

Experimental Evaluation

The authors evaluated DTD against standard TD($\lambda$) and other state-of-the-art methods like Emphatic TD (ETD) and Preferential TD (PTD) across several benchmarks:

  1. Skewed Random Walks: 5-state chains with left-skewed, center-elevated, and right-skewed initial distributions.
  2. Noisy Reward Chains: 10-state chains with varying levels of Gaussian noise.
  3. Boyan Chain: A classic 13-state benchmark for value estimation.
  4. Feature Approximation: Tests using Tabular, Inverted, and Dependent feature representations.
DTD performance (RMSPBE) across different state visitation distributions compared to standard TD(λ). The top row shows the state frequency distributions.

Key Results

DTD demonstrated superior performance across all test scenarios:

  • Lower Error in Imbalanced Tasks: As shown in the visitation experiments, DTD achieved significantly lower Mean-Square Projected Bellman Error (MSPBE) than TD($\lambda$) by ensuring rare states received sufficient update magnitude.
  • Robustness to Noise: In noisy reward experiments, DTD maintained stable, low-variance predictions where standard TD($\lambda$) performance degraded.
  • Faster Convergence: On the Boyan chain and feature-aliased tasks, DTD outperformed ETD and PTD, showing the effectiveness of its adaptive emphasis mechanism.
Performance comparison of DTD(λ) against TD(λ), ETD(λ), and PTD on the Dependent feature task (left) and the Boyan chain (right).

Discussion and Future Work

DTD offers a computationally efficient, online method for improving credit assignment in RL. While the current work focuses on linear function approximation, the authors suggest the potential for scaling to deep RL via a "Discerning Advantage Estimator." Future research will focus on testing DTD in high-dimensional environments and investigating the stability of adaptive emphasis functions in non-linear settings.

Summary updated

BibTeX
@inproceedings{ma2024discerning,
  author = {Jianfei Ma},
  title = {{Discerning Temporal Difference Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i13.29335},
}
Figure