Reinforcement Learning

Reinforcement learning is learning to act from the consequences of acting. An agent observes the state of its environment, chooses an action, and receives a reward and a new state; then it chooses again. Nobody tells it which action would have been right. Its aim is to choose actions so that the rewards it collects over time are as large as possible.

Three things set this apart from supervised learning, where every example comes with its correct answer. The feedback grades the action that was taken but does not name a better one. It often arrives long after the actions that earned it, so the agent must work out which of its many earlier choices deserve the credit, a difficulty known as the credit assignment problem. And the data depend on the agent: what it experiences next is decided by what it does now, so it must balance using what it already knows against trying what it does not. The name comes from animal psychology, where a behavior followed by a reward is said to be reinforced: it becomes more likely to happen again.

This note builds the standard framework (Markov decision processes, returns, value functions and the Bellman equations), then the methods that learn from experience (temporal-difference learning and Q-learning), then exploration, and finally the two extensions behind most modern results, neural-network function approximation and policy gradients. One small grid world runs through it, and every number quoted for it was computed, exactly or by simulation with fixed random seeds.

Video: Reinforcement Learning: How AI Learns by Trial and Error, a six-minute visual explainer of this note, from the agent, its rewards and the return to the value of a square, the Bellman equation, Q-learning learned try by try, and why to explore first.

A robot and its charger

The running example is a grid of 7 columns and 5 rows. Squares are named (column, row), counting from (0, 0) at the bottom left. A robot starts at (0, 2), the left end of the middle row, and its charger sits at (6, 2), the right end. Walls fill rows 1 and 3 except at the two outer columns, so three corridors connect the start and the charger: the middle row, 6 moves long, and the top and bottom rows, reached through the outer columns, 10 moves each. One square of row 1, (3, 1), just below the middle of the short corridor, holds a staircase going down.

In each square the robot can move up, down, left or right. Driving onto the charger pays a reward of +10 and ends the episode; driving into the stairs, from (3, 2) above or from (3, 0) below, pays −10 and ends it too. Every other move pays 0, and a move into a wall or off the grid leaves the robot where it was. That leaves 24 squares in which the robot stands and chooses.

Markov decision processes

The standard model is a Markov decision process. It has a set of states \(\mathcal{S}\), a set of actions \(\mathcal{A}\), and dynamics

\[p(s', r \mid s, a) = \Pr\left[ S_{t+1} = s',\, R_{t+1} = r \mid S_t = s,\, A_t = a \right],\]

the probability that taking action \(a\) in state \(s\) leads to state \(s'\) with reward \(r\). Capital letters denote the random quantities at step \(t\) and lowercase letters the values they take. The agent and the environment together produce the sequence \(S_0, A_0, R_1, S_1, A_1, R_2, \ldots\), which in an episodic task like the grid world stops when a terminal state is reached. The Markov property is built into \(p\): the next state and reward depend on the past only through the current state and action, so the state must carry everything the future depends on. In the grid world the state is the robot's square, and \(p\) puts probability 1 on a single outcome for every square and move.

The agent's behavior is a policy \(\pi(a \mid s)\), the probability of choosing action \(a\) in state \(s\). A deterministic policy, one action per state, is the special case that puts all the probability on one action.

Return and discounting

The agent's objective is not the next reward but the whole sequence of them. The return from step \(t\) is the discounted sum of the rewards that follow,

\[G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1},\]

where the discount factor \(\gamma\), between 0 and 1, sets how much a reward \(k\) steps away counts compared with one received now. A discount below 1 keeps the sum finite in tasks that never end and expresses a preference for sooner rewards. The return satisfies the recursion \(G_t = R_{t+1} + \gamma G_{t+1}\), on which the Bellman equations below are built.

In the grid world, with \(\gamma = 0.9\), the only nonzero reward on a successful route is the last one, so a route that reaches the charger in \(n\) moves has the return \(10\,\gamma^{n-1}\): 5.90 for the six-move middle corridor and 3.87 for either ten-move corridor. With \(\gamma = 1\) both routes would be worth 10 and the robot would have no reason to hurry; a small negative reward on every move is the other common way to say the same thing.

Value functions

A value function predicts the return. The value of a state under a policy \(\pi\) is the expected return when starting there and following \(\pi\),

\[V^\pi(s) = \mathbb{E}_\pi\left[ G_t \mid S_t = s \right],\]

and the action value is the expected return after taking action \(a\) in state \(s\) and following \(\pi\) afterwards,

\[Q^\pi(s, a) = \mathbb{E}_\pi\left[ G_t \mid S_t = s,\, A_t = a \right].\]

The optimal value functions are the best achievable by any policy, \(V^*(s) = \max_\pi V^\pi(s)\) and \(Q^*(s, a) = \max_\pi Q^\pi(s, a)\), and in a finite Markov decision process a single policy attains them in every state at once. Given \(Q^*\), acting optimally needs no further knowledge: in each state, take an action with the largest \(Q^*(s, a)\). Given only \(V^*\), choosing an action requires looking one step ahead through the dynamics, \(\arg\max_a \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma V^*(s') \right]\), so an agent that does not know \(p\) is better off learning action values.

The Bellman equations

Splitting the return into its first reward and the rest, \(G_t = R_{t+1} + \gamma G_{t+1}\), and taking expectations gives a consistency condition that every value function satisfies, the Bellman expectation equation:

\[V^\pi(s) = \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma V^\pi(s') \right].\]

For the optimal values the average over the policy's actions becomes a maximum, which gives the Bellman optimality equations:

\[V^*(s) = \max_a \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma V^*(s') \right], \qquad Q^*(s, a) = \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma \max_{a'} Q^*(s', a') \right].\]

In words, the value of a state is the best, over all actions, of the reward now plus the discounted value of the state the action leads to. Terminal states have value 0. In a deterministic world each sum has a single term, and the equation reads \(V^*(s) = \max_a \left[ r + \gamma V^*(s') \right]\), where \(r\) and \(s'\) are the reward and the next state of action \(a\).

The grid world's optimal values follow directly. The three squares next to the charger are worth 10, and every other square is worth 0.9 times its best neighbor: 9, 8.1, 7.29 and so on, so a square \(d\) moves from the charger along the best route has \(V^*(s) = 10\,\gamma^{d-1}\), and the start is worth 5.90. The stairs lower no value here, because the maximum simply avoids the move into them; in a world where moves sometimes slip sideways, the squares beside the stairs would be worth less than their distance suggests.

Value iteration

The optimality equation can be solved by turning it into an update. Value iteration starts from any guess, usually \(V_0 = 0\) everywhere, and applies the right-hand side to every state, again and again:

\[V_{k+1}(s) = \max_a \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma V_k(s') \right].\]

The update is a contraction in the maximum norm, \(\max_s \left| V_{k+1}(s) - V^*(s) \right| \le \gamma \max_s \left| V_k(s) - V^*(s) \right|\), so for \(\gamma < 1\) it converges to \(V^*\) from any starting guess. Policy iteration is the alternative: evaluate the current policy by solving its expectation equation, make the policy greedy with respect to the result, and repeat; in a finite problem it reaches an optimal policy in finitely many rounds. Both belong to dynamic programming (Bellman, 1957), and both need the dynamics \(p\).

In the grid world, starting from zeros, sweep \(k\) sets exactly the squares \(k\) moves from the charger to their final values: the three squares worth 10 after the first sweep, the three worth 9 after the second, the start after the sixth, and the two far corners, (0, 0) and (0, 4), after the eighth, after which nothing changes. This is how a late reward reaches the early decisions: credit flows backward from the charger one step per sweep, carried by the values of the squares in between.

Learning from experience: temporal differences

Without the dynamics, the agent can still estimate values from experience, by trying actions and observing what happens. Monte Carlo methods wait until the end of an episode and move the estimate toward the observed return, \(V(S_t) \leftarrow V(S_t) + \alpha \left[ G_t - V(S_t) \right]\), where the step size \(\alpha\), between 0 and 1, sets how far each estimate moves. Temporal-difference learning (Sutton, 1988) updates after every step instead, replacing the unknown rest of the return with the current estimate of the next state's value:

\[V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right].\]

The bracket, \(\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\), is the temporal-difference error: how much better or worse the step turned out than the estimate predicted. Using an estimate inside the target is called bootstrapping. The target is biased while the estimates are still wrong, but it varies far less than a full return, and learning can proceed during an episode rather than after it.

Q-learning

Q-learning (Watkins, 1989) applies the same idea to action values and to the optimality equation:

\[Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a') - Q(S_t, A_t) \right],\]

with the maximum taken as 0 when \(S_{t+1}\) is terminal. The target uses the best action at the next state, whatever action the agent actually takes there. That makes Q-learning off-policy: it learns the values of acting optimally while behaving in some other way. In a finite problem it converges to \(Q^*\) with probability 1, provided every action is tried in every state infinitely often and the step sizes shrink suitably, summing to infinity while their squares have a finite sum (Watkins and Dayan, 1992). In a deterministic world like this one the sampled target is the exact Bellman backup, so a constant step size converges as well. SARSA, the on-policy counterpart, uses the action actually taken next, \(Q(S_{t+1}, A_{t+1})\), and so learns the values of the policy it follows, exploration included.

The grid-world run starts with every score \(Q(s, a) = 0\) and uses \(\alpha = 0.5\) and \(\gamma = 0.9\). For its first 300 episodes the robot chooses its moves uniformly at random; after that it always takes the move with the best score. The first episode wanders 49 moves, up the left column and back and forth along the top, before reaching the charger from above. Only one score changes, that of the last move, from 0 to \(0.5 \times 10 = 5\), because every earlier target was \(0 + \gamma \cdot 0\). The second episode reaches the charger through the middle and scores its last move in the same way. In the third, the move into the square above the last one gets credit, \(0.5 \times (0 + 0.9 \times 5) = 2.25\), while the last move's score grows to 7.5; the fourth does the same along the middle corridor; the fifth falls down the stairs from below and gives that move −5. Credit moves back one transition per visit, a sampled, piecemeal version of the value-iteration sweeps. The random robot falls down the stairs in 193 of its 300 exploring episodes. Yet afterwards its best score in every square, \(\max_a Q(s, a)\), equals \(V^*(s)\) to one decimal, the best-scoring move in every square is an optimal one, and every episode it then drives takes the six-move corridor. It learned the values of acting well while acting at random.

Exploration

Acting on the current estimates, called exploitation, collects the most reward the agent knows how to get; trying something else, called exploration, is the only way to find out whether more is available. An agent that always exploits settles on whatever first earned credit. Run with the same seed as above but always taking its best-scoring move, the robot's first two episodes are identical to the explorer's, because a choice among four equal zeros is a random choice. It then reaches the charger often enough over the top that this route's credit arrives at the start first, after episode 15, when moving up becomes the only move from the start with a positive score; it never enters the middle corridor again after episode 13, and from episode 16 on it drives the ten-move route every time. The middle corridor's credit stops at (3, 2), two squares short of the start. Over 1000 seeds, 104 such greedy learners ended on a ten-move route, while all 1000 learners that explored for 300 episodes first found the six-move corridor.

The usual compromise is \(\varepsilon\)-greedy action selection: with probability \(\varepsilon\) a random action, otherwise the best-scoring one, often with \(\varepsilon\) decreasing over time. It is simple but shallow. Random deviations of one step at a time rarely string together the many deliberate moves needed to discover a distant improvement: a robot that took a random move one time in five from its first episode ended on a ten-move route in 102 of 1000 seeds after 300 episodes, no better than never exploring, and in 20 of 300 seeds after 3000. Directed methods do better: optimistic initial values, which make untried actions look attractive until they have been tried; bonuses for uncertainty, as in upper confidence bounds; bonuses for rarely visited states; and intrinsic rewards for surprise, often called curiosity.

Function approximation and deep Q-networks

A table with one number per state and action fits the grid world, \(24 \times 4 = 96\) numbers, but not most problems of interest: Go has about \(2 \times 10^{170}\) legal positions (Tromp, 2016), and a state made of camera pixels is practically never seen twice. The remedy is to compute the action values with a parameterized function \(Q(s, a; \theta)\), usually a neural network, and to adjust its parameters \(\theta\) so as to shrink the squared temporal-difference error. The deep Q-network of Mnih and colleagues (2015) did this with the screen pixels of Atari games as the state and learned 49 games with one architecture, reaching human-level scores on many of them. It minimizes

\[L(\theta) = \mathbb{E}\left[ \left( r + \gamma \max_{a'} Q(s', a'; \theta^-) - Q(s, a; \theta) \right)^2 \right]\]

over transitions \((s, a, r, s')\) sampled from a replay buffer of past experience, where \(\theta^-\) is a copy of the parameters that is refreshed only every few thousand steps. Both devices address a known instability: bootstrapping, off-policy learning and function approximation together can make the estimates diverge, a combination Sutton and Barto call the deadly triad.

Policy gradients

Value-based methods learn scores and derive a policy from them. Policy-gradient methods instead parameterize the policy itself, \(\pi_\theta(a \mid s)\), and climb the expected return \(J(\theta) = \mathbb{E}_{\pi_\theta}\left[ G_0 \right]\). The policy gradient theorem expresses the gradient as an expectation that can be estimated from sampled episodes; the REINFORCE estimator (Williams, 1992) is

\[\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta}\left[ \sum_t \gamma^t\, G_t\, \nabla_\theta \log \pi_\theta(A_t \mid S_t) \right],\]

which makes actions followed by high returns more likely and actions followed by low returns less likely; in practice the factor \(\gamma^t\) is often dropped. Subtracting a baseline that depends only on the state, \(G_t - b(S_t)\), leaves the gradient unchanged in expectation and reduces its variance. With a learned value function as the baseline, the difference estimates the advantage of the action over the policy's average, and learning the two together gives actor-critic methods. Proximal policy optimization, PPO (Schulman and colleagues, 2017), keeps each update small by clipping the ratio \(\rho_t = \pi_\theta(A_t \mid S_t) / \pi_{\theta_{\text{old}}}(A_t \mid S_t)\) of new to old action probabilities to the interval \([1 - c, 1 + c]\), with \(c\) around 0.2, inside its objective. Policy gradients handle continuous actions such as motor torques directly and can represent stochastic policies, which is why they dominate robot control and the fine-tuning of language models.

Where it has worked

• Games from pixels. The deep Q-network learned 49 Atari 2600 games from the screen and the score alone (Mnih and colleagues, 2015).
• Go. AlphaGo combined a policy network, first trained on human games and then improved by reinforcement learning from games against itself, with a value network and Monte Carlo tree search, and beat Fan Hui 5–0 in 2015 and Lee Sedol 4–1 in 2016 (Silver and colleagues, 2016). AlphaZero learned Go, chess and shogi from self-play alone (Silver and colleagues, 2018).
• Legged robots. Locomotion policies trained with reinforcement learning in simulation have been transferred to real four-legged robots walking over rough terrain (Hwangbo and colleagues, 2019; Lee and colleagues, 2020).
• Language models. In reinforcement learning from human feedback, a reward model is trained on people's comparisons between answers, and the language model is then tuned with PPO to score well under it (Christiano and colleagues, 2017; Ouyang and colleagues, 2022). More recently, models trained with reinforcement learning on problems whose answers can be checked automatically, such as math and code, learned to reason at length before answering (DeepSeek-AI, 2025).

References

• R. Sutton and A. Barto, Reinforcement Learning: An Introduction, 2nd edition, MIT Press, 2018.
• R. Bellman, Dynamic Programming, Princeton University Press, 1957.
• R. Sutton, Learning to Predict by the Methods of Temporal Differences, Machine Learning, 1988.
• C. Watkins, Learning from Delayed Rewards, PhD thesis, University of Cambridge, 1989.
• C. Watkins and P. Dayan, Q-Learning, Machine Learning, 1992.
• R. Williams, Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning, Machine Learning, 1992.
• V. Mnih and colleagues, Human-Level Control through Deep Reinforcement Learning, Nature, 2015.
• D. Silver and colleagues, Mastering the Game of Go with Deep Neural Networks and Tree Search, Nature, 2016.
• D. Silver and colleagues, A General Reinforcement Learning Algorithm That Masters Chess, Shogi, and Go through Self-Play, Science, 2018.
• J. Schulman and colleagues, Proximal Policy Optimization Algorithms, arXiv:1707.06347, 2017.
• J. Hwangbo and colleagues, Learning Agile and Dynamic Motor Skills for Legged Robots, Science Robotics, 2019.
• J. Lee and colleagues, Learning Quadrupedal Locomotion over Challenging Terrain, Science Robotics, 2020.
• P. Christiano and colleagues, Deep Reinforcement Learning from Human Preferences, NeurIPS 2017.
• L. Ouyang and colleagues, Training Language Models to Follow Instructions with Human Feedback, NeurIPS 2022.
• DeepSeek-AI, DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning, arXiv:2501.12948, 2025.
• J. Tromp, The Number of Legal Go Positions, Computers and Games, 2016.