The environment is typically formulated as a finite-state Markov decision process (MDP), and reinforcement learning algorithms for this context are highly related to dynamic programming techniques. State transition probabilities and reward probabilities in the MDP are typically stochastic but stationary over the course of the problem.
Reinforcement learning differs from the supervised learning problem in that correct input/output pairs are never presented, nor sub-optimal actions explicitly corrected. Further, there is a focus on on-line performance, which involves finding a balance between exploration (of uncharted territory) and exploitation (of current knowledge).
Formally, the basic reinforcement learning model consists of:
Reinforcement learning applies particularly well to problems where long-term reward can be had at the expense of short-term reward, this class of problems is normally handled using a reinforcement learning technique known as Temporal Difference. It has been applied successfully to various problems, including robot control, elevator scheduling, and backgammon.
Leslie Kaelbling, Michael Littman, Andrew Moore. Reinforcement Learning: A Survey. Journal of Artificial Intelligence Research 4 (1996) pp. 237–285. (CiteSeer reference)
Richard Sutton and Andrew Barto. Reinforcement Learning. MIT Press, 1998. (available online)References