Reinforcement Learning: A Survey

Leslie Pack Kaelbling
Michael L. Littman
lpk,mlittman@cs.brown.edu
Computer Science Department, Box 1910, Brown University
Providence, RI 02912-1910 USA
- Andrew W. Moore
awm@cs.cmu.edu
Smith Hall 221, Carnegie Mellon University, 5000 Forbes Avenue
Pittsburgh, PA 15213 USA

Abstract:

This paper surveys the field of reinforcement learning from a computer-science perspective. It is written to be accessible to researchers familiar with machine learning. Both the historical basis of the field and a broad selection of current work are summarized. Reinforcement learning is the problem faced by an agent that learns behavior through trial-and-error interactions with a dynamic environment. The work described here has a resemblance to work in psychology, but differs considerably in the details and in the use of the word ``reinforcement.'' The paper discusses central issues of reinforcement learning, including trading off exploration and exploitation, establishing the foundations of the field via Markov decision theory, learning from delayed reinforcement, constructing empirical models to accelerate learning, making use of generalization and hierarchy, and coping with hidden state. It concludes with a survey of some implemented systems and an assessment of the practical utility of current methods for reinforcement learning.

• Introduction
  • Reinforcement-Learning Model
  • Models of Optimal Behavior
  • Measuring Learning Performance
  • Reinforcement Learning and Adaptive Control
• Exploitation versus Exploration: The Single-State Case
  • Formally Justified Techniques
    • Dynamic-Programming Approach
    • Gittins Allocation Indices
    • Learning Automata
  • Ad-Hoc Techniques
    • Greedy Strategies
    • Randomized Strategies
    • Interval-based Techniques
  • More General Problems
• Delayed Reward
  • Markov Decision Processes
  • Finding a Policy Given a Model
    • Value Iteration
    • Policy Iteration
    • Enhancement to Value Iteration and Policy Iteration
    • Computational Complexity
• Learning an Optimal Policy: Model-free Methods
  • Adaptive Heuristic Critic and
  • Q-learning
  • Model-free Learning With Average Reward
• Computing Optimal Policies by Learning Models
  • Certainty Equivalent Methods
  • Dyna
  • Prioritized Sweeping / Queue-Dyna
  • Other Model-Based Methods
• Generalization
  • Generalization over Input
    • Immediate Reward
      • CRBP
      • ARC
      • REINFORCE Algorithms
      • Logic-Based Methods
    • Delayed Reward
      • Adaptive Resolution Models
  • Generalization over Actions
  • Hierarchical Methods
    • Feudal Q-learning
    • Compositional Q-learning
    • Hierarchical Distance to Goal
• Partially Observable Environments
  • State-Free Deterministic Policies
  • State-Free Stochastic Policies
  • Policies with Internal State
    • Recurrent Q-learning
    • Classifier Systems
    • Finite-history-window Approach
    • POMDP Approach
• Reinforcement Learning Applications
  • Game Playing
  • Robotics and Control
• Conclusions
• References
• About this document ...