Reinforcement Learning: A Survey

Leslie Pack Kaelbling, Michael L. Littman and Andrew W. Moore’s 1996 survey organizes reinforcement learning as a problem of learning to act through interaction and reward. It compares formal objectives, algorithms, computational costs and implemented systems from the research available then. Its contribution is a map of the field’s choices and obstacles, rather than a new universal benchmark.^[1]

What counts as success?

Finite-horizon, discounted and average-reward objectives can favor different actions in the same environment. Section 1 separates the objective defining a successful policy—a rule for choosing actions—from the performance of the learning process itself: eventual optimality, speed, performance after a fixed time and regret, the reward lost while learning compared with acting optimally from the beginning. Faster convergence can incur larger penalties along the way.^[1]

Sections 2–3 introduce exploration versus exploitation and Markov decision processes. In the basic finite-state setup, reward and the distribution of the next state depend on the current state and action; earlier history adds no further predictive information once these are given. Dynamic programming uses a known model to calculate useful actions. Learning methods must instead obtain information through experience, including when a reward arrives long after the action that helped produce it.^[1]

Experience, computation and representation

The survey contrasts model-free learning with learning an environmental model and planning with it. Its Q-learning discussion estimates the long-term value of state–action pairs directly. For its tabular, finite-state and finite-action discounted setting, the stated convergence result requires every pair to be sampled infinitely often and the learning rate to decay appropriately; it does not promise fast learning or resolve exploration. Dyna combines real experience, model learning and additional planning updates. Prioritized sweeping directs updates toward states affected by important changes, using predecessor relationships.^[1]

A value backup is a computation that updates an estimated value from rewards and successor values. Table 1 makes the tradeoff visible in a deterministic, 3,277-state maze. Q-learning took 531,000 environment steps and 531,000 value backups; Dyna took 62,000 steps and 3,055,000 backups; prioritized sweeping took 28,000 steps and 1,010,000 backups. All used optimistic exploration; Q-learning’s learning rate was 1, and the model-based methods were allowed up to 200 backups per transition. These are results for that configuration, not general speed rankings.^[1]

Sections 6–7 explain why tables become impractical in large spaces and why incomplete observations change the problem. In the office-to-printer example, two locations both look like a hall but require different actions. Treating the observation as the full state loses information needed for good decisions; memory or a representation of uncertainty can matter. The applications discussion similarly distinguishes TD-Gammon with handcrafted board features from a less successful version with little predefined knowledge.^[1]

What the survey leaves to the designer

The conclusion stresses task structure and prior knowledge: staged tasks, local feedback, imitation, decomposition and initial reflexes can make difficult learning problems more tractable. Its assessment belongs to 1996; its convergence conditions and selected demonstrations do not establish present-day capability or safety. For Outer Alignment, its enduring comparison is that reward amounts alone leave the time horizon and treatment of learning-period outcomes unsettled. Policy invariance under reward transformations: Theory and application to reward shaping asks the different question of which changes to rewards preserve a given objective.^[1]