Fundamentals: MDPs, Values, and the Bellman Equation#

(Lecture time: 0:10–0:30)

The Markov Decision Process#

An MDP is the standard formalism for sequential decision-making, defined by the tuple

$$ (\mathcal{S}, \mathcal{A}, P, R, \gamma) $$

$\mathcal{S}$ — set of states
$\mathcal{A}$ — set of actions
$P(s' \mid s, a)$ — transition dynamics
$R(s, a)$ — reward function
$\gamma \in [0, 1)$ — discount factor

The Markov property: the future depends only on the current state and action, not the full history. (Real problems are often partially observed — POMDPs — but we set that aside today.)

Return, policy, value#

The return is the discounted sum of future rewards:

$$ G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^k r_{t+k} $$

A policy $\pi(a \mid s)$ maps states to (distributions over) actions. Its state-value and action-value functions:

$$ V^\pi(s) = \mathbb{E}_\pi\!\left[ G_t \mid s_t = s \right], \qquad Q^\pi(s, a) = \mathbb{E}_\pi\!\left[ G_t \mid s_t = s,\, a_t = a \right] $$

The Bellman equation#

The single most important equation of the lecture. Value today decomposes into immediate reward plus discounted value tomorrow:

$$ V^\pi(s) = \mathbb{E}_{a \sim \pi,\ s' \sim P}\!\left[ R(s,a) + \gamma V^\pi(s') \right] $$

and for the optimal value function:

$$ V^*(s) = \max_a\ \mathbb{E}_{s'}\!\left[ R(s,a) + \gamma V^*(s') \right] $$

Why it matters: the Bellman equation turns a horizon-infinite optimization into a local, recursive consistency condition. Nearly every RL algorithm — value iteration, Q-learning, DQN, actor-critic — is a way of (approximately) solving it.

Deep dive: Bellman as a fixed point (skipped live)

The Bellman optimality operator $\mathcal{T}$ defined by $(\mathcal{T}V)(s) = \max_a \mathbb{E}[R(s,a) + \gamma V(s')]$ is a $\gamma$-contraction in the sup norm, so by the Banach fixed-point theorem it has a unique fixed point $V^*$, and repeated application (value iteration) converges to it from any initialization. This is why tabular methods provably work.

Q-learning in one slide#

Learn $Q^*$ directly from experience tuples $(s, a, r, s')$:

$$ Q(s,a) \leftarrow Q(s,a) + \alpha \Big[ \underbrace{r + \gamma \max_{a'} Q(s', a')}_{\text{TD target}} - Q(s,a) \Big] $$

It is off-policy (learns the optimal policy while behaving exploratorily, e.g. $\varepsilon$-greedy) and model-free (never learns $P$).

In this section#

Bandits & exploration — the exploration/exploitation trade-off in its purest form
Q-table Worked example: gridworld — one fully worked Q-table computation
Q-learning — Q-learning