Reinforcement Learning

Every model we trained this semester, from linear regression to last week’s transformer, used labeled examples. Even language modeling obtains a label from the next token. Reinforcement learning instead learns from rewards generated through interaction. Modern chatbots also use reinforcement learning from human feedback to fine-tune pretrained transformers.

No Labels, No Dataset

Since the Linear Models unit, our recipe has been empirical risk minimization: collect a dataset of pairs \((\mathbf{x}^{(i)}, y^{(i)})\), pick a function class, and minimize a loss that scores each prediction against its label. Reinforcement learning breaks that recipe in three distinct ways.

  • No labels. A reward is a score, not an answer. When a chess program loses, the environment says “that was worth \(-1\),” not which of the forty moves was the mistake, let alone what the right move was. Compare the cross-entropy loss, which hands the model the exact correct token and the exact direction to nudge every probability.

  • Delayed reward. The consequences of an action arrive later, sometimes much later: the fatal wobble happens at step \(30\) and the pole hits the ground at step \(50\). Deciding which past actions deserve credit for a reward is called the credit assignment problem, and no previous unit had anything like it, because every training example scored itself instantly.

  • The agent generates its own data. An agent’s data is its own experience: the states it sees are the states its current behavior steers it into. A chess program that never castles collects no data about castling, so the quality of what it learns is limited by the adventurousness of how it acts, a tension we return to at the end of the lecture.

All three follow because an interaction has replaced the fixed dataset.

The Agent–Environment Loop

At each time step \(t = 0, 1, 2, \ldots\), the agent observes the current state \(s_t \in \mathcal{S}\) of the environment and chooses an action \(a_t \in \mathcal{A}\), where \(\mathcal{S}\) is the set of states and \(\mathcal{A}\) the set of actions. The environment responds with a scalar reward \(r_t \in \mathbb{R}\) and the next state \(s_{t+1}\), and the loop repeats.

An agent sends an action to the environment, which returns a reward and the next state.

In the diagram, the top arrow is the agent’s one output, an action, and the bottom two arrows are everything the environment says back: a number and a new state. Nothing in that thin channel ever tells the agent what it should have done.

Our running example, in class and in the demo, is CartPole: a pole balances on a cart, and the agent keeps it from falling by nudging the cart. The state \(s_t \in \mathbb{R}^4\) holds the cart’s position and velocity and the pole’s angle and angular velocity; the actions are \(\mathcal{A} = \{\text{push left}, \text{push right}\}\); the reward is \(r_t = 1\) for every step the pole stays up. An episode is one run of the loop from a fresh start until the pole falls or a step limit is reached. Doing nothing is not an option: the pole is unstable, so the agent survives only by actively steering. Reinforcement learning determines the rule for choosing actions.

Policies

The agent’s behavior is its policy \(\pi\): for each state \(s\), a probability distribution \(\pi(a | s)\) over the actions, from which the agent samples \(a_t \sim \pi(\cdot | s_t)\). A policy is generally stochastic, meaning it rolls dice; a deterministic rule puts all the probability on one action.

The demo compares two CartPole policies. The random policy ignores the state entirely: \(\pi(a|s) = \frac12\) for both actions. The hand-coded policy is one deterministic line: push right when the pole’s angle plus its angular velocity is positive, and left otherwise. In words, push in the direction the pole is leaning and falling, read off the state’s last two coordinates. A stochastic policy continues trying actions it currently rates lower, which supports exploration. The next lecture also uses this randomness to differentiate expected reward with respect to the policy’s parameters.

Trajectories, Return, and the Discount Factor

Running a policy produces a trajectory, the alternating sequence of states, actions, and rewards the loop generates: \[ \tau = (s_0, a_0, r_0, s_1, a_1, r_1, s_2, \ldots). \] The trajectory is the agent’s version of a training example, and we score it from time \(t\) onward by its return, which discounts each future reward by how long we wait on it: \[ G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^k r_{t+k}, \] where the discount factor \(\gamma \in [0, 1)\) shrinks the weight on each additional step of delay. (After an episode ends, the later rewards are zero.) Discounting is an interest rate on reward: just as a dollar today is worth more than a dollar next year, a unit of reward now is worth \(1/\gamma\) units of reward one step from now. Discounting also keeps the infinite sum finite.

The definition hides a one-step recursion. Split off the \(k = 0\) term and factor \(\gamma\) out of everything that remains: \[ G_t = r_t + \gamma\left(r_{t+1} + \gamma r_{t+2} + \cdots\right) = r_t + \gamma G_{t+1}. \] In words, today’s return is today’s reward plus \(\gamma\) times tomorrow’s return. Taking the expectation of this identity (linearity of expectation, from lecture one) produces the Bellman consistency equation, the workhorse identity of the field.

Discount weights decay geometrically with steps into the future; larger discount factors produce longer effective horizons.

In the plot, the weight \(\gamma^k\) on a reward \(k\) steps ahead decays geometrically, and the dashed lines mark the effective horizon \(1/(1-\gamma)\), where each curve crosses the gray \(1/e\) line: at \(\gamma = 0.99\) a reward a hundred steps out still carries over a third of its face value. Both are worth a hand computation before we trust them; they are the lecture’s two in-class exercises.

Worked Example: A Four-Step Episode

The first in-class exercise makes the return and its recursion concrete. Take a four-step episode with these rewards: \[ r_0 = 1, \quad r_1 = 0, \quad r_2 = 2, \quad r_3 = 4, \] and \(\gamma = 0.9\). Summing the weighted terms gives \(G_0 = 5.536\), and the recursion \(G_t = r_t + \gamma G_{t+1}\) checks out at every step.

Solution to the class exercise The return from the start follows by summing the four weighted terms directly: \[ G_0 = r_0 + \gamma r_1 + \gamma^2 r_2 + \gamma^3 r_3 = 1 + (0.9)(0) + (0.81)(2) + (0.729)(4) = 1 + 0 + 1.62 + 2.916 = 5.536. \] The same summation started at each later step gives the remaining three returns: \[ G_1 = 0 + (0.9)(2) + (0.81)(4) = 5.04, \qquad G_2 = 2 + (0.9)(4) = 5.6, \qquad G_3 = 4. \] Now verify the recursion \(G_t = r_t + \gamma G_{t+1}\) at \(t = 0\) by computing both sides. The left side is \(G_0 = 5.536\) from the direct sum, and the right side is: \[ r_0 + \gamma G_1 = 1 + (0.9)(5.04) = 1 + 4.536 = 5.536. \] The two sides agree, and the same check goes through at \(t = 1\) and \(t = 2\).

Sweeping back to front, the recursion computes each return with one multiplication and one addition; every reinforcement learning implementation computes returns this way, including next lecture’s.

Worked Example: The Effective Horizon

The second exercise asks how far into the future a discounted agent effectively sees. The effective horizon \(1/(1-\gamma)\) is roughly the number of future steps that still matter non-negligibly: \(10\) steps at \(\gamma = 0.9\) and \(100\) at \(\gamma = 0.99\).

Solution to the class exercise Sum the weights over all future steps with the geometric series formula: \[ \sum_{k=0}^{\infty} \gamma^k = \frac{1}{1 - \gamma}. \] Two facts justify the name effective horizon: the first \(1/(1-\gamma)\) steps contribute the bulk of the total weight, and by step \(1/(1-\gamma)\) the weight has decayed by a factor of \(e \approx 2.718\). (That second fact is the compound-interest limit: \(\gamma^{1/(1-\gamma)} = (1 - (1-\gamma))^{1/(1-\gamma)} \approx e^{-1}\) when \(\gamma\) is close to \(1\).) Comparing the two values in the plot above: \[ \gamma = 0.9: \quad \frac{1}{1 - 0.9} = 10, \qquad\qquad \gamma = 0.99: \quad \frac{1}{1 - 0.99} = 100. \]

Moving \(\gamma\) from \(0.9\) to \(0.99\) looks like a small nudge, and it is a tenfold extension of the agent’s sight. The two numbers have a second reading: when every reward equals \(1\), as in CartPole, an episode that never ends earns exactly \(\sum_k \gamma^k = 1/(1-\gamma)\), so \(10\) and \(100\) are ceilings on the discounted return. The demo watches two very different episodes run into them.

The Markov Decision Process

We have been informal about what the environment is; the standard formalization is the Markov decision process (MDP). An MDP consists of the state space \(\mathcal{S}\), the action space \(\mathcal{A}\), a transition distribution \(\Pr(s_{t+1} | s_t, a_t)\) over next states, the reward \(r_t\) produced alongside each transition, and the discount factor \(\gamma\). The load-bearing assumption sits in the transition distribution’s arguments, the Markov property: the next state depends only on the current state and action, not on the rest of the history. That is what the word “state” means here, a summary of the past sufficient to predict the future. CartPole’s four numbers qualify: Newtonian mechanics computes the next configuration from them alone; how the pole got to its current lean is irrelevant. (When the observation is not a sufficient summary, a single video-game frame showing positions but not velocities, the theory gets harder; we assume fully observed states.)

Maximizing Expected Return

A trajectory is random twice over: the policy rolls dice to pick actions, and the environment rolls dice to pick next states. So the return \(G_0\) is a random variable, and the objective is its expectation: \[ \max_{\pi} \; J(\pi) = \mathbb{E}_{\tau \sim \pi}\left[G_0\right] = \mathbb{E}_{\tau \sim \pi}\left[\sum_{t=0}^{\infty} \gamma^t r_t\right], \] where \(\tau \sim \pi\) denotes a trajectory generated by running the policy \(\pi\) in the MDP. We cannot compute this expectation exactly, since summing over all trajectories is hopeless, but we can sample from it by running episodes, precisely the situation the Monte Carlo estimator of lecture two was built for; next lecture we estimate both \(J(\pi)\) and its gradient by averaging sampled trajectories. Sampling from \(\pi\) carries a catch that no fixed dataset ever had: the policy we are evaluating is also the policy that decides what we get to see.

Exploration vs. Exploitation

At any moment the agent has a best guess about which actions pay; should it exploit that guess, or explore an action that currently looks worse? An agent can remain wrong because its current policy does not generate the experience needed to correct it.

Our hand-coded CartPole policy makes this concrete: exploiting it produces trajectories only from states that this one rule visits, so the agent gets no evidence about alternatives. Stochastic policies are the simplest hedge: keep \(\pi(a|s) > 0\) for every action, so everything gets tried occasionally (exploring optimally is a theory of its own, multi-armed bandits; the policies of the next two lectures explore by staying random).

Episode returns from a random policy cluster near the bottom, while a hand-coded policy usually reaches the episode cap.

In the plot, every episode’s return under each policy is a dot: the random policy’s cloud hugs the bottom, while the hand-coded policy rides the episode cap with a handful of unlucky starts falling short. The demo compares the policies and shows how discounting changes their measured returns.

Our best policy was hand-coded, which does not scale past a pole on a cart. Next lecture we make the policy a neural network \(\pi_{\boldsymbol\theta}\) and ascend the gradient \(\nabla_{\boldsymbol\theta} \mathbb{E}[G_0]\); differentiating through an expectation over the policy’s own randomness is the job of the log-derivative trick. Before then, Problem 23 treats \(\gamma\) as a bias-variance knob when rewards contain both transient noise and an episode-wide shock. It is the temporal version of Problem 12’s question about repeated augmentations that share one source. The value function becomes the baseline used to reduce policy-gradient variance later in the unit.