Reinforcement learning dates back to the early days of cybernetics and work in statistics, psychology, neuroscience, and computer science. In the last five to ten years, it has attracted rapidly increasing interest in the machine learning and artificial intelligence communities. Its promise is beguiling--a way of programming agents by reward and punishment without needing to specify how the task is to be achieved. But there are formidable computational obstacles to fulfilling the promise.
This paper surveys the historical basis of reinforcement learning and some of the current work from a computer science perspective. We give a high-level overview of the field and a taste of some specific approaches. It is, of course, impossible to mention all of the important work in the field; this should not be taken to be an exhaustive account.
Reinforcement learning is the problem faced by an agent that must learn behavior through trial-and-error interactions with a dynamic environment. The work described here has a strong family resemblance to eponymous work in psychology, but differs considerably in the details and in the use of the word ``reinforcement.'' It is appropriately thought of as a class of problems, rather than as a set of techniques.
There are two main strategies for solving reinforcement-learning problems. The first is to search in the space of behaviors in order to find one that performs well in the environment. This approach has been taken by work in genetic algorithms and genetic programming, as well as some more novel search techniques [101]. The second is to use statistical techniques and dynamic programming methods to estimate the utility of taking actions in states of the world. This paper is devoted almost entirely to the second set of techniques because they take advantage of the special structure of reinforcement-learning problems that is not available in optimization problems in general. It is not yet clear which set of approaches is best in which circumstances.
The rest of this section is devoted to establishing notation and
describing the basic reinforcement-learning model.
Section 2 explains the trade-off between exploration and
exploitation and presents some solutions to the most basic case of
reinforcement-learning problems, in which we want to maximize the
immediate reward. Section 3 considers the more general
problem in which rewards can be delayed in time from the actions that
were crucial to gaining them. Section 4 considers some
classic model-free algorithms for reinforcement learning from delayed
reward: adaptive heuristic critic, 
and Q-learning.
Section 5 demonstrates a continuum of algorithms that are
sensitive to the amount of computation an agent can perform between
actual steps of action in the environment. Generalization--the
cornerstone of mainstream machine learning research--has the
potential of considerably aiding reinforcement learning, as described
in Section 6. Section 7 considers the
problems that arise when the agent does not have complete perceptual
access to the state of the environment. Section 8 catalogs
some of reinforcement learning's successful applications. Finally,
Section 9 concludes with some speculations about important
open problems and the future of reinforcement learning.