Foundations of Reinforcement Learning

Supervised learning fits a function to labelled examples; unsupervised learning models the structure of unlabelled data. Reinforcement learning is the third paradigm: there are no labels, only a stream of interaction, and a scalar reward that says how good the last move was but never which move was right.¹ An agent must discover a good behaviour by trying actions and observing their consequences, trading off the reward available now against the states its choices lead to later. This lesson builds the formal object that makes the problem tractable, the Markov decision process, and derives the equations that every algorithm in the rest of the module solves, exactly or approximately.

The agent-environment interface

At each discrete step $t$ the agent observes a state $S_t\in \mathcal{S}$, selects an action $A_t\in \mathcal{A}$, and the environment responds with a scalar reward $R_{t+1}\in \mathbb{R}$ and a next state $S_{t+1}$. The loop closes and repeats. Everything the agent can learn is contained in the resulting trajectory $S_0,A_0,R_1,S_1,A_1,R_2,\dots$.

The environment is the source of both signals the agent does not control, the reward and the next state. The agent controls only its action. The whole of reinforcement learning is the question of how to choose actions, from experience alone, so that the long-run reward is large.

The single most important distinction from supervised learning: the reward is evaluative, not instructive. A label tells the model the correct output; a reward only scores the action taken, leaving the agent to infer, across many trials, which actions were responsible. This is the credit-assignment problem, and it is why the value functions below exist.

Markov decision processes

The interface becomes solvable once we assume the dynamics are Markov: the next state and reward depend only on the current state and action, not on the full history. The history collapses into the present state.

A finite Markov decision process packages the dynamics into a five-tuple.

The kernel $P$ and reward $R$ together are the model. When the agent knows them, the problem is one of planning, solved exactly by the dynamic programming of the last section. When it does not, it must learn from sampled transitions, the subject of later lessons. For example, in a small gridworld, states are cells, actions move between adjacent cells, and the reward is $-1$ per step until a goal cell is reached.

The Markov assumption is a modelling choice, not a law of nature. If the raw observation is not Markov (a single video frame hides velocity), the standard fix is to engineer a state that is, by stacking frames or carrying a recurrent summary, so that the tuple above applies to the constructed state.

Returns and discounting

The agent maximizes the return $G_t$, the discounted sum of future rewards. The discount $\gamma$ weights a reward $k$ steps away by ${\gamma }^k$.

The definition obeys a one-step recursion that drives every equation downstream: peel off the first reward and the rest is a return from $t+1$.

Two regimes arise. An episodic task terminates in an absorbing state (a game ends, a maze is solved), so the sum is finite and $\gamma =1$ is admissible. A continuing task runs forever, and the sum converges only because $\gamma <1$ bounds it: if $\left|R\right|\le R_{\max }$ then $\left|G_t\right|\le R_{\max }{\sum }_{k\ge 0}{\gamma }^k=R_{\max }/\left(1-\gamma \right)$.

Beyond guaranteeing convergence, discounting encodes a genuine preference: a reward now is worth more than the same reward later, and it caps the influence of the distant, uncertain future on the present decision. The weight the return places on the reward $k$ steps ahead is exactly ${\gamma }^k$, and the two discount factors decay at visibly different rates.

Policies and value functions

A policy is the agent's behaviour: a mapping from states to a distribution over actions, $\pi \left(a\mid s\right)=\mathrm{Pr}\left[A_t=a\mid S_t=s\right]$. A deterministic policy is the special case that puts all mass on one action, $\pi (s)=a$. The agent's task is to find a policy whose return is large, and to rank policies we need to measure the return a policy earns, which is what the value functions do.

The two are linked by averaging $Q^{\pi }$ over the policy's action distribution, and conversely by expanding one step of dynamics:

The first identity says a state's value is the policy-weighted average of its action-values; the second says an action's value is its immediate reward plus the discounted value of where it leads.

The Bellman expectation equations

Substituting each identity into the other produces a self-consistency condition on $V^{\pi }$ alone, the Bellman expectation equation. We derive it from the return recursion $G_t=R_{t+1}+\gamma G_{t+1}$.

The third line splits the expectation and conditions the second term on the next state; the fourth uses ${\mathbb{E}}_{\pi }[G_{t+1}\mid S_{t+1}=s^{\prime }]=V^{\pi }(s^{\prime })$, the definition of the value function one step later. The same argument applied to $Q^{\pi }$ gives its Bellman expectation equation:

These equations are read off a backup diagram: a one-step look-ahead tree that averages over the action chosen by $\pi$ (open circles) and the next state drawn by $P$ (filled circles), backing the successor values up to the root.

A backup by hand

Take a gridworld cell $s$ whose action is fixed by the policy to up, with reward $-1$ per step and $\gamma =0.9$. Suppose the move is stochastic: with probability $0.8$ the agent lands in the intended cell $s_{\uparrow }$, and with probability $0.1$ each it slips left into $s_{\leftarrow }$ or right into $s_{\to }$. From a current value estimate $V(s_{\uparrow })=5$, $V(s_{\leftarrow })=2$, $V(s_{\to })=1$, the Bellman expectation backup evaluates one line of arithmetic:

The successor values are averaged under the transition probabilities, scaled by $\gamma$, and offset by the one-step reward. Every method in this module reduces to a rule for producing and repeating that single number.

Optimal value functions

A policy $\pi$ is at least as good as ${\pi }^{\prime }$ if $V^{\pi }(s)\ge V^{{\pi }^{\prime }}(s)$ for every state. This partial order has a maximum: there always exists an optimal policy ${\pi }^{\star }$ that dominates all others simultaneously. Its value functions are the optimal value functions:

Optimality replaces the policy-average in the Bellman equation with a $\max$ over actions: the optimal value of a state is the value of its best action, not the average over a fixed policy. The two backups differ at exactly one node, where the action branches meet.

The optimality equation immediately yields the optimal policy: act greedily with respect to $Q^{\star }$. There is no need to look further than one step, because $Q^{\star }$ has already folded the entire future into each action-value.

This is why the model-free methods of later lessons, such as $Q$-learning, target $Q^{\star }$ rather than $V^{\star }$: with $Q^{\star }$ in hand, the agent acts optimally without ever consulting a model.

Dynamic programming

When the model $\left(P,R\right)$ is known, the Bellman equations can be turned into algorithms that compute the value functions exactly. Two ideas combine: policy evaluation computes $V^{\pi }$ for a fixed policy, and policy improvement turns a value function into a better policy.

Iterative policy evaluation treats the Bellman expectation equation as an assignment, sweeping it to convergence:

Policy improvement replaces $\pi$ with the policy greedy w.r.t. its own value:

Alternating the two is policy iteration: evaluate the current policy fully, then improve it, and repeat until the policy stops changing.

The two operations alternate around a cycle: evaluation makes $V$ consistent with $\pi$, improvement makes $\pi$ greedy w.r.t. $V$, and the fixed point of the cycle satisfies the Bellman optimality equation.

Value iteration short-circuits the cycle: rather than evaluate each policy to convergence, it applies the Bellman optimality update once per sweep, folding improvement and evaluation into a single $\max$.

Each sweep contracts the error toward zero, so the value estimate converges geometrically to $V^{\star }$. The error after $k$ sweeps shrinks like ${\gamma }^k$.

Convergence as a contraction

Both algorithms converge for the same reason: the Bellman operator is a contraction in the max norm, so iterating it is a Banach fixed-point iteration that converges geometrically to the unique fixed point. Define the optimality operator $\mathcal{T}$ acting on a value function $V$ by

The discount factor is doing double duty: it makes the return finite and it is exactly the contraction modulus that guarantees the algorithms converge. As $\gamma \to 1$ the contraction weakens, convergence slows, and planning over a long horizon becomes harder, the geometric counterpart of the discounting trade-off in the table above.

Policy iteration versus value iteration

The same idea, alternating evaluation and improvement, admits a spectrum of schedules collectively called generalized policy iteration. Policy iteration evaluates fully before improving; value iteration improves after a single evaluation sweep; the general scheme interleaves partial amounts of each.

The two processes are simultaneously cooperative and competitive: improvement makes the value stale by changing the policy, evaluation corrects the value, and the joint fixed point, where the policy is greedy in its own value, is precisely the Bellman optimality equation, hence ${\pi }^{\star }$.

Where the model breaks down

Dynamic programming is exact, but it needs two things that vanish at scale: the model $(P,R)$ and a value table with one entry per state. Both fail the moment the state space is large, and the failures are what the rest of this module — and the standalone reinforcement-learning subject — exist to fix.

The model is usually unknown. A robot does not know its transition kernel; a game-playing agent is not handed the rules as equations. When $(P,R)$ is unavailable, the Bellman backups above cannot be computed, and the agent must sample transitions instead. Replacing the expectation ${\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)V(s^{\prime })$ with an average over sampled successors carries dynamic programming into Monte Carlo and temporal-difference learning, the subject of the next lesson.

The table does not fit. A tabular $V(s)$ needs one number per state; backgammon has $10^{20}$ states and Go has $10^{170}$, so no table can hold them and no sweep can visit them all. The fix is function approximation: replace the table with a parameterized $V_{\theta }(s)$ or $Q_{\theta }(s,a)$ — a neural network — and learn $\theta$ from samples. That single substitution is what makes the subject deep reinforcement learning, and it is where the deep Q-network lesson picks up.

The contraction guarantee is fragile under approximation. The clean $\gamma$-contraction proof above assumes exact backups on a table. Combine it with function approximation and off-policy sampling and the guarantee can break — the value estimates can diverge. This is the deadly triad (function approximation, bootstrapping, off-policy training), and much of modern deep RL is engineering around it. Sutton and Barto's text treats it at length; this module meets it concretely when DQN's target network and replay buffer appear, both of which exist precisely to keep the approximate backup stable.¹

In short, this lesson is the exact, small-state ideal, and everything downstream is what survives when the model disappears and the table is replaced by a network. The Bellman equations do not change; only how their expectations are computed and stored does.

Takeaways

• Reinforcement learning is interaction-driven: an agent maps states to actions and receives an evaluative reward, maximizing the discounted return$G_t={\sum }_{k\ge 0}{\gamma }^k{R}_{t+k+1}$ rather than any immediate signal.
• The Markov decision process $\left(\mathcal{S},\mathcal{A},P,R,\gamma \right)$ is the formal object; the Markov property lets the present state summarize the past, and $\gamma$ sets the effective horizon $1/\left(1-\gamma \right)$.
• Value functions rank behaviour: $V^{\pi }(s)$ scores a state, $Q^{\pi }(s,a)$ a state-action pair, and they satisfy the Bellman expectation equations, a linear self-consistency on the value of a fixed policy.
• The optimal value functions satisfy the Bellman optimality equations (a $\max$ over actions), and any policy greedy w.r.t. $Q^{\star }$ is optimal, which is why model-free methods target $Q^{\star }$.
• With a known model, policy iteration and value iteration compute $V^{\star }$ exactly; both converge because the Bellman operator is a $\gamma$-contraction in the max norm, giving the geometric rate $\Vert V_k-V^{\star }\Vert \le {\gamma }^k\Vert V_0-V^{\star }\Vert$.
• The unifying picture is generalized policy iteration: evaluation and improvement drive the value and policy to the mutually consistent fixed point $\left(V^{\star },{\pi }^{\star }\right)$. The same loop, with sampled experience replacing the model, becomes Monte Carlo and temporal-difference learning; the sampling and convergence intuitions connect to Monte Carlo methods and to the fixed-point geometry of the optimization landscape.