TL;DR
This paper introduces the "G algorithm," a novel approach to input generalization in delayed reinforcement learning (DRL) that recursively splits the state space based on statistical reinforcement differences. It demonstrates that the G algorithm reliably finds optimal policies in complex domains where traditional backpropagation struggles, highlighting the importance of a sound statistical basis for generalization in DRL.
What Problem Does This Paper Address?
Delayed reinforcement learning (DRL) aims to train autonomous agents to learn optimal action policies without explicit supervision, receiving only delayed numerical rewards. While promising, a major hurdle for DRL is "input generalization": enabling agents to act intelligently in novel but similar situations. Existing methods, like connectionist backpropagation, have shown some success but often exhibit unpredictable behavior and fail in complex domains. This paper tackles the challenge of efficiently generalizing from limited experience in high-dimensional state spaces, where storing a lookup table for every possible state is computationally infeasible.
Methods
The core contribution is the G algorithm, which addresses input generalization by building a tree-structured Q-table. Instead of a monolithic table, G recursively splits the state space based on statistical measures of how input bits affect reinforcement.
- Recursive Splitting: The algorithm starts with a single "block" representing the entire state space. It then statistically tests individual input bits for relevance. If a bit is found to be relevant (i.e., it significantly influences reinforcement or state values), the block is split into two sub-blocks based on whether the bit is on or off. This process continues, creating a tree where leaf nodes represent specific state subspaces.
- Statistical Relevance Tests: The G algorithm employs statistical tests (specifically, Student's t-test) to determine bit relevance. It considers two types of relevance:
- Value Relevance: How a bit affects the immediate and discounted future value of a state.
- Action Relevance: How a bit influences the optimal action to take in a given state.
- D Statistics: To handle sparse and infrequent rewards (like ghost deaths in their domain), the paper introduces "D statistics." This extends Q-learning by tracking the probability distribution of receiving specific reinforcements, providing richer statistical information than simple summed rewards.
- Enforcing Normality & Low-Frequency Noise: The authors address practical issues like the t-test's assumption of normality (violated by sparse rewards) by delaying splits until sufficient data is collected. They also tackle the problem of slowly changing "noise" bits that can falsely appear relevant by separating learning into distinct action value and bit relevance phases.
Datasets
The primary domain used for evaluation is a subproblem from the Amazon videogame, specifically a scenario where an agent controls an "amazon" icon that must kill ghosts. This domain was chosen for its complexity, featuring:
- High-dimensional input spaces (potentially over 2^100 distinct inputs).
- Sparse and infrequent rewards (ghost deaths).
- Ghosts programmed to avoid alignment, making learning difficult.
- Variance in state values due to limited perception.
The authors also reference Lin's domain, another video game involving food collection and obstacle avoidance, for comparison with backpropagation.
Key Insights and Ideas
- Statistical Rigor for Generalization: The G algorithm's success stems from its foundation in sound statistical tests for bit relevance. This makes its behavior more predictable than connectionist methods like backpropagation, which can converge to unpredictable local minima.
- Orthogonal Inputs are Key: The G algorithm's effectiveness relies on the assumption that input bits are individually relevant. The authors hypothesize that well-designed perceptual systems should "orthogonalize" inputs in this way, making them independently informative.
- The Perils of Linearity: The paper suggests that previous successes of backpropagation in domains like Lin's might be due to the linearity of the problem's Q-function representation. When the Q-function is nonlinear, backpropagation's performance can degrade significantly.
- D-Statistics for Sparse Rewards: Extending Q-learning to track reinforcement distributions (D-statistics) is crucial for learning effectively in domains with infrequent but high-value rewards.
Key Results
- In the Amazon subproblem, the G algorithm reliably learned the optimal policy, even with ten bits of noise added to the inputs.
- The G algorithm successfully handled domains with up to thirty input bits, where traditional Q-learning tables would be too large to store.
- Backpropagation, tested on the simplest Amazon problem with extensive parameter tuning, failed to find the optimal policy within a reasonable number of ticks (average run length of 70,000 ticks, with some up to 210,000 ticks).
- In Lin's domain, a simple linear associator performed as well as backpropagation, suggesting the domain's linearity was key to backpropagation's success.
Limitations and Future Work
- Normality Assumption: The t-test used for relevance relies on the assumption of normally distributed data, which is violated in their domain. While addressed by delaying splits, the authors suggest using statistical tests of normality for a more principled approach.
- Relevance of Bit Groups: The G algorithm's incremental, one-bit-at-a-time splitting assumes individual bit relevance. It may fail if groups of bits are collectively relevant but individually irrelevant. The authors suggest this constraint can be placed on the perceptual system.
- Output Generalization: The paper acknowledges that output generalization (learning which actions are relevant) is also a significant problem, analogous to input generalization, and suggests the G algorithm could be extended to address it.
- Comparison with Other Methods: The authors express a desire to compare G with other methods like CMAC and clustering techniques in future work.
- Further Analytic and Empirical Study: The authors emphasize the need for more analytic study and empirical testing across a spectrum of domains to fully understand the performance of DRL algorithms, particularly in light of the input generalization problem.
Summary updated