Temporal-Difference Networks with History

Brian Tanner, Richard S. SuttonIJCAI 2005 · OpenReview

Abstract: Temporal-difference (TD) networks are a formalism for expressing and learning grounded world knowledge in a predictive form. However, not all partially observable Markov decision processes can be efficiently learned with TD networks. In this paper, we extend TD networks by allowing the network-update process (answer network) to depend on the recent history of previous actions and observations rather than only on the most recent action and observation. We show that this extension enables the solution of a larger class of problems than can be solved by the original TD networks or by history-based methods alone. In addition, we apply TD networks to a problem that, while still simple, is significantly larger than has previously been considered. We show that history-extended TD networks can learn much of the common-sense knowledge of an egocentric gridworld domain with a single bit of perception.

Introduction

In reinforcement learning, an agent's ability to represent its environment—its "state"—is crucial for predicting future outcomes. While traditional methods often rely on abstract hidden states, Temporal-Difference (TD) networks utilize "predictive representations," where the state is defined by the expected outcomes of various action sequences (e.g., "If I move forward, I will likely see a wall").

Despite their promise, standard TD networks face a significant hurdle in partially observable environments: cyclic dependencies. In these scenarios, learning one prediction requires another to be accurate, but if all start as random guesses, the system fails to converge. This paper introduces an extension to TD networks that incorporates a short window of recent history to provide the necessary "anchors" for learning.

The Cycle-World Trap

The authors identify the "Cycle-World" as a primary failure case for standard TD networks. In this environment, an agent moves through a deterministic loop of states with only a single landmark.

Cycle World environment and its associated question network.

Because standard TD networks only observe the most recent action and observation, they cannot distinguish between identical-looking locations within the cycle. This leads to a circular logic trap where predictions depend on other unlearned predictions, preventing the network from ever finding a stable ground truth to begin the learning process.

Methods: TD Networks with History

To address these limitations, the authors propose TD Networks with History. The architecture consists of two main components:

  1. The Answer Network: Generates the actual predictions.
  2. The Question Network: Defines the temporal relationships between these predictions.

The key innovation lies in the input feature vector ($x_t$). While original TD networks only considered the current observation and the previous step's predictions, the extended version includes a $k$-length window of recent history (the last several actions and observations). This history acts as a non-cyclic signal. Even a short history can uniquely identify specific states, providing the "anchor" needed to train deeper predictive nodes through standard gradient-descent learning rules.

Experimental Evaluation

The approach was tested on three synthetic environments:

  • Cycle World: A deterministic loop testing the ability to break cyclic dependencies.
  • Ring World: A 5-state world with reversible actions, testing "indefinite memory"—the ability to track location regardless of the number of steps taken.
  • Egocentric Gridworld: A 104-state maze where the agent has only one bit of perception (detecting a wall directly in front). This represents a significant scale-up for TD network benchmarks.

Synergy and Performance

A core finding is that the combined model is more than the sum of its parts. The predictive nodes leverage the history to build a more efficient model than either history-based or standard TD methods could achieve alone.

Comparison of RMS error across different levels of history and predictive depth.

As shown in the performance data, increasing the "Predictive Levels" (the depth of the question network) dramatically reduces RMS error compared to using "History Alone." For instance, a TD network can solve the Cycle World using a history window of only 2 steps, whereas a history-only model would require 5 steps. Furthermore, because TD networks are recursive, they can maintain a sense of location indefinitely, whereas history-only models are strictly limited by their window size.

Conclusion

By augmenting TD networks with history, the authors demonstrate that agents can learn complex spatial "common sense"—such as understanding that a 360-degree turn leaves the world unchanged—even with extremely limited sensors. While the structure of the Question Network still requires manual design, this work paves the way for more robust, self-learning predictive representations in complex, partially observable worlds.

Summary updated

Abstract

Temporal-difference (TD) networks are a formalism for expressing and learning grounded world knowledge in a predictive form [Sutton and Tanner, 2005]. However, not all partially observable Markov decision processes can be efficiently learned with TD networks. In this paper, we extend TD networks by allowing the network-update process (answer network) to depend on the recent history of previous actions and observations rather than only on the most recent action and observation. We show that this extension enables the solution of a larger class of problems than can be solved by the original TD networks or by history-based methods alone. In addition, we apply TD networks to a problem that, while still simple, is significantly larger than has previously been considered. We show that history-extended TD networks can learn much of the common-sense knowledge of an egocentric gridworld domain with a single bit of perception.
BibTeX
@inproceedings{tanner2005temporal,
  author = {Brian Tanner and Richard S. Sutton},
  title = {{Temporal-Difference Networks with History}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
  url = {https://openreview.net/forum?id=HJW3WHGdbS},
}
Figure