Input Generalization in Delayed Reinforcement Learning: An Algorithm and Performance Comparisons

David Chapman, Leslie Pack Kaelbling

Abstract

Delayed reinforcement learning is an attractive framework for the unsupervised learning of action policies for autonomous agents. Some existing delayed reinforcement learning techniques have shown promise in simple domains. However, a number of hurdles must be passed before they are applicable to realistic problems. This paper describes one such difficulty, the input generalization problem (whereby the system must generalize to produce similar actions in similar situations) and an implemented solution, the G algorithm. This algorithm is based on recursive splitting of the state space based on statistical measures of differences in reinforcements received. Connectionist backpropagation has previously been used for input generalization in reinforcement learning. We compare the two techniques analytically and empirically. The G algorithm's sound statistical basis makes it easy to predict when it should and should not work, whereas the behavior of back-propagation is unpredictable. We found that a previous successful use of backpropagation can be explained by the linearity of the application domain. We found that in another domain, G reliably found the optimal policy, whereas none of a set of runs of backpropagation with many combinations of parameters did.

Introduction

In Reinforcement Learning (RL), an agent learns to act by receiving rewards or penalties. Standard "Q-learning" stores these lessons in a table. However, if an agent has 100 binary sensors, the table would need $2^{100}$ entries—more than the number of atoms in the universe. This is the input generalization problem.

To survive in the real world, an agent must realize that most sensor data is irrelevant at any given moment (e.g., the color of the sky doesn't matter when you're trying to avoid a cliff). While researchers often use neural networks (backpropagation) to "compress" this state space, these models are notoriously difficult to tune, prone to local minima, and offer little insight into why they make certain decisions.

The G Algorithm

The authors propose the G algorithm, which takes a "divide and conquer" approach to the state space through recursive splitting.

Decision tree structure of the G algorithm showing recursive splitting based on input bits.

The algorithm starts by assuming all inputs are irrelevant. It then monitors the "relevance" of each input bit using the Student’s t-test to compare the rewards received when a bit is "on" versus "off." If the difference is statistically significant, the algorithm splits that part of the state space into two new "leaf nodes" in a tree.

To make the system more sensitive to rare rewards, the authors extended Q-learning into "D-learning," which tracks the probability distribution of discrete reinforcement values rather than just a single average. Furthermore, to prevent "slow noise" from tricking the t-test, the algorithm toggles between a phase of updating Q-values and a phase of testing bit relevance.

Experimental Results

The paper evaluates the algorithm using two simulated environments: Amazon, a difficult videogame sub-problem requiring high-precision control, and Lin’s Domain, a benchmark where an agent collects food and avoids obstacles.

Performance comparison over time, demonstrating the learning efficiency of the G algorithm compared to alternative methods.

In the Amazon domain, the G algorithm was given 10 bits of pure random noise. It successfully ignored all of them, never once splitting the state space on a noise bit. On the Amazon task, the G algorithm consistently found the optimal policy in about 35,000 ticks. In contrast, backpropagation failed to find the optimal policy even after 210,000 ticks, despite testing dozens of different parameter combinations. While Q-learning would require billions of years of experience to fill a table for 30 input bits, the G algorithm successfully mastered 30-bit problems by focusing only on the relevant dimensions.

Key Insights

  • The Linearity Hypothesis: The authors discovered that backpropagation’s success in earlier RL research was often due to the tasks being "unexpectedly easy." They proved this by showing a simple linear associator performed just as well as a complex neural network on Lin's domain.
  • Orthogonality in Perception: The G algorithm assumes that if a bit is important, its importance will be visible in isolation. The authors argue that a "well-designed perceptual system" should provide such independent, "orthogonal" bits to the learner.
  • Transparency: Because G is based on a decision tree and statistical tests, it is "mathematically well-characterized." One can inspect the tree to see exactly which sensors the agent is prioritizing.

Limitations and Future Work

The G algorithm splits on one bit at a time, meaning it may fail the "Parity Problem" where two bits are only relevant when seen together (e.g., XOR). Additionally, when the algorithm splits a node, it currently resets statistics for that region to avoid "poisoning" new nodes with old data, which slows the learning rate. Future work suggests applying similar tree-splitting logic to the action space to help agents learn which muscle movements are relevant for specific tasks.

Summary updated

Abstract

Delayed reinforcement learning is an attractive framework for the unsupervised learning of action policies for autonomous agents. Some existing delayed reinforcement learning techniques have shown promise in simple domains. However, a number of hurdles must be passed before they are applicable to realistic problems. This paper describes one such difficulty, the input generalization problem (whereby the system must generalize to produce similar actions in similar situations) and an implemented solution, the G algorithm. This algorithm is based on recursive splitting of the state space based on statistical measures of differences in reinforcements received. Connectionist backpropagation has previously been used for input generalization in reinforcement learning. We compare the two techniques analytically and empirically. The G algorithm's sound statistical basis makes it easy to predict when it should and should not work, whereas the behavior of back-propagation is unpredictable. We found that a previous successful use of backpropagation can be explained by the linearity of the application domain. We found that in another domain, G reliably found the optimal policy, whereas none of a set of runs of backpropagation with many combinations of parameters did.
BibTeX
@inproceedings{chapman1991input,
  author = {David Chapman and Leslie Pack Kaelbling},
  title = {{Input Generalization in Delayed Reinforcement Learning: An Algorithm and Performance Comparisons}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
}
Figure