Reinforcement Learning

Reinforcement learning studies how a computational agent should act inside an environment in order to achieve a goal, and Sutton and Barto's textbook Reinforcement Learning: An Introduction frames this as a continual loop of interaction. At each discrete time step the agent observes the current state of the environment, selects an action from the set of actions available to it, and the environment responds by transitioning to a new state and emitting a numerical reward signal. This closed loop of state, action, and reward repeats indefinitely or until a terminal state is reached, and it is the basic unit from which every reinforcement learning problem is built. Sutton and Barto emphasize that the agent does not need a supervisor telling it the correct action at every step; instead it must discover which actions lead to good outcomes purely through trial-and-error experience and the consequences those actions produce. This distinguishes reinforcement learning from supervised learning, where labeled correct answers are provided directly, and from unsupervised learning, where no evaluative feedback exists at all.

The formal mathematical object used to describe this interaction is the Markov Decision Process, or MDP, which Sutton and Barto present as the idealized framework underlying nearly all of reinforcement learning theory. An MDP is defined by a set of states, a set of actions, a transition function that specifies the probability of moving to each next state given the current state and action, and a reward function that specifies the expected reward received for a given state-action transition. The Markov property requires that the next state and reward depend only on the current state and action, not on the full history of how the agent arrived there, so the current state must summarize all information relevant to the future. This property is what makes the framework mathematically tractable, since the agent can plan and learn using only the present state rather than an ever-growing history. Sutton and Barto stress that many real problems can be reformulated to satisfy or closely approximate the Markov property by enriching what is included in the state representation.

Central to this framework is what Sutton and Barto call the reward hypothesis, the idea that all goals an agent might pursue can be represented as the maximization of the expected cumulative sum of a scalar reward signal received over time. Under the reward hypothesis, complex, qualitative objectives such as winning a game or navigating safely are translated into a numerical reward at each step, and the agent's entire purpose becomes maximizing the expected total of these numbers, appropriately discounted into the future. Two further concepts organize how an agent pursues this goal: a policy, which is a mapping from states to the probabilities of selecting each available action, and a value function, which estimates the expected cumulative reward the agent can expect to obtain starting from a given state, or from a given state-action pair, while following a particular policy. Sutton and Barto describe the value function as answering a different question than the reward: reward indicates what is good in an immediate, one-step sense, whereas value indicates what is good in the long run after accounting for the states that are likely to follow. Because of this, an agent can rationally sacrifice a small immediate reward for a much larger reward later, and most reinforcement learning algorithms are built around estimating value functions in order to derive or improve a policy.

Q-learning is a classical reinforcement learning algorithm, described in Sutton and Barto's textbook, that learns an action-value function estimating the expected return of taking a given action in a given state and thereafter following an optimal policy. For decades this action-value function was typically represented with a table or a simple linear function, which worked well for small, low-dimensional problems but broke down as the number of possible states grew, as is the case when the state is a raw video frame with thousands of pixels. Mnih and colleagues addressed this limitation in their 2015 Nature paper Human-level control through deep reinforcement learning by introducing the Deep Q-Network, or DQN, which uses a deep convolutional neural network to approximate the action-value function directly from raw pixel input. The network takes recent screen frames as input and outputs an estimated value for every possible joystick action, allowing the same architecture to be applied to many different games without any game-specific feature engineering.

Training a deep neural network directly on sequential, correlated reinforcement learning data is notoriously unstable, so Mnih et al. introduced two key techniques to stabilize learning. The first is experience replay, in which the agent's observed transitions of state, action, reward, and next state are stored in a memory buffer and later sampled in random mini-batches for training, which breaks the harmful correlations between consecutive experiences and allows each transition to be reused multiple times. The second is the use of a separate, periodically updated target network to generate the target values used in the Q-learning update, which reduces oscillations and divergence that would otherwise occur if the same rapidly changing network were used to both select and evaluate actions. Combined with standard convolutional layers for processing the pixel input, these two innovations allowed a single algorithm, using the same network architecture and the same hyperparameters throughout, to be trained separately on many different games.

As reported in the Nature paper published in volume 518, pages 529 to 533, in 2015, the DQN agent was evaluated on 49 classic Atari 2600 games using only raw pixels and the game score as input, with no access to internal game state or hand-crafted features. Mnih and colleagues report that DQN was able to surpass the performance of all previous general-purpose algorithms on this benchmark and achieved a level of play comparable to that of a professional human games tester across the set of 49 games, all using the same algorithm, network architecture, and hyperparameters. This result was significant precisely because a single unified system, rather than a collection of game-specific solutions, learned competent or superhuman play across a wide and diverse range of games directly from sensory input, which the authors present as a step toward more general-purpose learning agents. The paper is widely regarded as a landmark demonstration that deep learning and reinforcement learning could be combined effectively at scale, and it helped launch the modern subfield now commonly known as deep reinforcement learning.