Generalization and Scaling in Reinforcement Learning

David H. Ackley, Michael L. Littman

This foundational 1989 paper by David Ackley and Michael Littman explores how neural networks can solve the "search problem" inherent in reinforcement learning (RL). At a time when supervised learning techniques like backpropagation were gaining massive traction, the authors sought to adapt those tools to environments where the "correct" answer isn't provided by a teacher, but must instead be discovered through trial and error.

The Bottleneck of Reinforcement Learning

In supervised learning, an algorithm is explicitly given the correct answer for a given input. In reinforcement learning, the agent only receives a scalar reward—a "thumbs up" or "thumbs down." This creates a massive bottleneck: before the network can learn the correct input-output mapping, it first has to find it.

In large problem spaces, the time required to randomly stumble upon a correct input-output pair grows exponentially. The authors argue that for RL to be practical, an agent must be able to generalize. If it discovers that one specific output is good for a certain input, it should be able to infer that similar outputs might be good for similar inputs. This paper investigates whether neural networks can provide this "on-line generalization" to drastically speed up the search for rewards.

Complementary Reinforcement Back-Propagation (CRBP)

To bridge the gap between supervised and reinforcement learning, the authors propose CRBP. The core idea is to treat an RL problem as a supervised learning problem with a moving target:

  1. Stochastic Output: The network produces a "search vector" of probabilities. A binary output vector is then generated via Bernoulli trials (coin flips based on those probabilities).
  2. Reward Logic: If the output is rewarded, the network performs standard backpropagation using that successful output as the target. This makes that specific success more likely in the future.
  3. Punishment Logic (The "Complement"): If the output is punished, the network uses the complement of that output (flipping all 0s to 1s and vice versa) as the target. This pushes the network to search in the "opposite" direction of the failure.

The authors also introduce several refinements to stabilize training, including probability stretching to prevent the network from getting stuck in deterministic states too early, asymmetric learning rates (using a smaller rate for punishment than for reward), and an update loop that ensures weight changes have a functional effect before moving on.

Testing Generalization

The authors evaluated CRBP on several scalable synthetic problems designed to test different types of generalization:

  • $n$-majority: The output should be all 1s if the majority of input bits are 1, otherwise all 0s (tests "output generalization").
  • $n$-copy: The output should be an exact bit-for-bit copy of the input (tests 1-to-1 mapping).
  • $2^k$-attractors: A family of problems spanning the spectrum between majority and copy.
  • Inverse Arithmetic: A "degenerate" problem where many different outputs are correct for a single input.

Key Insights and Results

The experiments revealed several fascinating dynamics about how neural networks navigate search spaces:

  • Search is a Generalization Test: In RL, searching for the right answer and learning that answer happen simultaneously. A strong algorithm uses its early successes to narrow down where to look for future ones.
  • Structuring the Void: In problems with many correct answers (like Inverse Arithmetic), CRBP didn't just find random solutions. It tended to discover "structured" solutions, such as inventing a form of positional notation. Structured mappings are easier for a neural network to represent and generalize.
  • Overfitting is Self-Limiting: Unlike supervised learning, where a model might overfit a static training set, RL learning stops once the agent consistently finds the reward. This "automatic" stopping point makes the network less prone to the typical pitfalls of over-parameterization.
Scaling advantage of CRBP over table-lookup methods

Most importantly, CRBP demonstrated a massive scaling advantage. While a simple table-lookup algorithm ($T_{ref}$) was faster for very small problems (e.g., 3-4 bits), CRBP scaled exponentially better. For the $n$-majority problem, the table-lookup time grew at a rate of $4.2^n$, while CRBP grew at only $1.6^n$. CRBP consistently began outperforming the non-generalizing table-lookup method at around 6 bits of input.

Interestingly, architecture played a crucial role depending on the task. For the $n$-copy problem, the network actually performed better without hidden units (using direct input-to-output "shortcut" connections), showing that the optimal architecture depends heavily on the correlation between input and output.

Limitations and Legacy

While groundbreaking, the paper acknowledges several limitations. The learning rates were hand-picked for each problem size, whereas a truly autonomous agent would need to tune these dynamically. Furthermore, the "be like not-o" assumption (training on the complement) is a heuristic; while effective for binary vectors, it is a coarse exploration strategy that might struggle in more complex environments. Finally, the experiments were limited to relatively small bit-vectors (up to 14 bits).

Despite these constraints, Ackley and Littman's work laid crucial groundwork for understanding how neural networks can autonomously navigate and generalize within vast search spaces—a challenge that remains at the heart of modern Deep Reinforcement Learning today.

Summary updated

Abstract

In associative reinforcement learning, an environment generates input vectors, a learning system generates possible output vectors, and a re(cid:173) inforcement function computes feedback signals from the input-output pairs. The task is to discover and remember input-output pairs that generate rewards. Especially difficult cases occur when rewards are rare, since the expected time for any algorithm can grow exponentially with the size of the problem. Nonetheless, if a reinforcement function possesses regularities, and a learning algorithm exploits them, learning time can be reduced below that of non-generalizing algorithms. This paper describes a neural network algorithm called complementary re(cid:173) inforcement back-propagation (CRBP), and reports simulation results on problems designed to offer differing opportunities for generalization. 1 REINFORCEMENT LEARNING REQUIRES SEARCH Reinforcement learning (Sutton, 1984; Barto &amp; Anandan, 1985; Ackley, 1988; Allen, 1989) requires more from a learner than does the more familiar supervised learning paradigm. Supervised learning supplies the correct answers to the learner, whereas reinforcement learning requires the learner to discover the correct outputs before they can be stored. The reinforcement paradigm divides neatly into search and learning aspects: When rewarded the system makes internal adjustments to learn the discovered input-output pair; when punished the system makes internal adjust(cid:173) ments to search elsewhere. Generalization and Scaling in Reinforcement Learning 551 1.1 MAKING REINFORCEMENT INTO ERROR Following work by Anderson (1986) and Williams (1988), we extend the backprop(cid:173) agation algorithm to associative reinforcement learning. Start with a "garden va(cid:173) riety" backpropagation network: A vector i of n binary input units propagates through zero or more layers of hidden units, ultimately reaching a vector 8 of m sigmoid units, each taking continuous values in the range (0,1). Interpret each 8j as the probability that an associated random bit OJ takes on value 1. Let us call the continuous, deterministic vector 8 the search vector to distinguish it from the stochastic binary output vector o. Given an input vector, we forward propagate to produce a search vector 8, and then perform m independent Bernoulli trials to produce an output vector o. The i - 0 pair is evaluated by the reinforcement function and reward or punishment ensues. Suppose reward occurs. We therefore want to make 0 more likely given i. Backpropagation will do just that if we take 0 as the desired target to produce an error vector (0 - 8) and adjust weights normally. Now suppose punishment occurs, indicating 0 does not correspond with i. By choice of error vector, backpropagation allows us to push the search vector in any direction; which way should we go? In absence of problem-specific information, we cannot pick an appropriate direction with certainty. Any decision will involve assumptions. A very minimal "don't be like 0" assumption-employed in Anderson (1986), Williams (1988), and Ackley (1989)-pushes s directly away from 0 by taking (8 - 0) as the error vector. A slightly stronger "be like not-o" assumption-employed in Barto &amp; Anandan (1985) and Ackley (1987)-pushes s directly toward the complement of 0 by taking ((1 - 0) - 8) as the error vector. Although the two approaches always agree on the signs of the error terms, they differ in magnitudes. In this work, we explore the second possibility, embodied in an algorithm called complementary reinforcement back-propagation ( CRBP). Figure 1 summarizes the CRBP algorithm. The algorithm in the figure reflects three modifications to the basic approach just sketched. First, in step 2, instead of using the 8j'S directly as probabilities, we found it advantageous to "stretch" the values using a parameter v. When v &lt; 1, it is not necessary for the 8i'S to reach zero or one to produce a deterministic output. Second, in step 6, we found it important to use a smaller learning rate for punishment compared to reward. Third, consider step 7: Another forward propagation is performed, another stochastic binary out(cid:173) put vector 0* is generated (using the procedure from step 2), and 0* is compared to o. If they are identical and punishment occurred, or if they are different and reward occurred, then another error vector is generated and another weight update is performed. This loop continues until a different output is generated (in the case of failure) or until the original output is regenerated (in the case of success). This modification improved performance significantly, and added only a small percentage to the total number of weight updates performed. 552 Ackley and Littman O. Build a back propagation network with input dimensionality n and output dimensionality m. Let t = 0 and te = O. <li>Pick random i E 2n and forward propagate to produce a/s. 2. Generate a binary output vector o. Given a uniform random variable ~ E [0,1] and parameter 0 &lt; v &lt; 1, OJ = {1, if(sj - !)/v+! ~ ~j
BibTeX
@inproceedings{ackley1989generalization,
  author = {David H. Ackley and Michael L. Littman},
  title = {{Generalization and Scaling in Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1989},
}
Figure