Reinforcement Learning

A Brief History of RL

Core Concepts

A Brief History of Bandits

Multi-Armed Bandit

Notation

$K$ arms  ·  $\mathcal{A} = \{1,\ldots,K\}$
$\mu_a = \mathbb{E}[R_t \mid A_t = a]$  ·  $\mu^* = \max_{a \in \mathcal{A}} \mu_a$
$h_t = (a_1,r_1,\ldots,a_{t-1},r_{t-1}) \in \mathcal{H}_t$
$\pi(\cdot \mid h_t) \in \Delta(\mathcal{A})$

Objective

$$\pi^* = \arg\max_{\pi}\; \underset{\substack{A_t \sim \pi(\cdot \mid H_t) \\ R_t \sim \nu_{A_t}}}{\mathbb{E}}\!\left[\sum_{t=1}^{T} R_t\right]$$

Regret

$$\text{Reg}_T = T\mu^* - \underset{\substack{A_t \sim \pi(\cdot \mid H_t) \\ R_t \sim \nu_{A_t}}}{\mathbb{E}}\!\left[\sum_{t=1}^{T} R_t\right]$$

ε-Greedy

Flip a coin: explore at random with probability ε, exploit the best arm otherwise.

$A_t$

$\text{Uniform}(\mathcal{A})$

explore

$\arg\max_{a}\,\hat{\mu}_a$

exploit

Upper Confidence Bound

Pick the arm with the highest optimistic estimate — uncertainty is a bonus.

Thompson Sampling

Sample a belief for each arm, then act as if the sample were the truth.

Notebook 01 — Bandits

Implement ε-Greedy, compare all three algorithms, and analyse HP sensitivity.

Stationary vs Contextual Bandits

Contextual Bandits

Context $X_t \sim \mathcal{D}$ — observed before acting

History $H_t = (X_1, A_1, R_1,\, \ldots,\, X_{t-1}, A_{t-1}, R_{t-1})$

Policy $A_t \sim \pi(\cdot \mid H_t, X_t)$

Reward $R_t \sim \nu_{A_t,\, X_t}$

Regret $\displaystyle\mathrm{Reg}_T = \underset{X_t \sim \mathcal{D}}{\mathbb{E}}\!\left[\sum_{t=1}^{T} \max_a \mu_{a,X_t}\right] - \underset{\substack{X_t \sim \mathcal{D} \\ A_t \sim \pi}}{\mathbb{E}}\!\left[\sum_{t=1}^{T} R_t\right]$

Markov Decision Processes

A Practical Case: Grid World

Instantaneous distribution
$\mu_t(s)=\mathbb{P}(S_t = s)$ — marginal distribution at time $t$

→

Mean drift
$\mathbb{E}[\Delta S_t \mid S_t = s]$ — mean drift under $P$

Wall cells
$P(s' \mid s) = 0$ if $s'$ is a wall

Initial distribution
$S_0 \sim \delta_{s_0}$,   $s_0 = (19,\,0)$

Discrete-Time Markov Chain

The future depends only on the present — not on how we got here.

Markov Property

$$\mathbb{P}(S_{t+1} \mid S_0,\ldots,S_t) = P(\cdot \mid S_t)$$

Instantaneous Distribution

$\mu_t \in \Delta(\mathcal{S})$  ·  $[\mu_t]_s = \mathbb{P}(S_t = s)$ $$\mu_{t+1} = \mu_t\, P$$

Controlled Markov Chain

Introducing actions: the agent now shapes its own transition dynamics.

Action

$A_t \sim \pi(\cdot \mid S_t)$  ·  $A_t \in \mathcal{A}$

Controlled Kernel

$P : \mathcal{S} \times \mathcal{A} \to \Delta(\mathcal{S})$

Induced Kernel

$$P^\pi(s' \mid s) = \sum_{a \in \mathcal{A}} \pi(a \mid s)\cdot P(s' \mid s, a)$$ $$\mu_{t+1}^\pi = \mu_t^\pi\, P^\pi$$

Notebook 02 — Controlled Markov Chains

Simulate policies on a grid, observe stationary distributions, mixing times, and discounted occupation measures.

Markov Decision Process

An MDP is a controlled Markov chain with a reward signal.

Action

$A_t \sim \pi(\cdot \mid S_t)$  ·  $A_t \in \mathcal{A}$

Controlled Kernel

$P : \mathcal{S} \times \mathcal{A} \to \Delta(\mathcal{S})$

Reward

generic   $r : \mathcal{S} \to \mathbb{R}$

tabular   $R \in \mathbb{R}^{|\mathcal{S}|}, \; [R]_s = r(s)$

Policy Evaluation (Model-Based)

Bellman Equation

The value of a state is the immediate reward plus the discounted value of what comes next.

Bellman Operator

Repeated application converges to the unique fixed point — guaranteed by contraction.

Policy Evaluation Algorithm (Model-Based)

$\pi$ = Spiral CCW

$\pi$ = Rightward

Policy Improvement (Model-Based)

Policy Improvement (Model-Based)

Greedy w.r.t. the value function yields a strictly better policy.

Policy Iteration (Model-Based)

Policy Iteration (Model-Based)

Eval $\pi_0$

Eval $\pi_1$

Eval $\pi^*$

↓

↗

↓

···↗

↓

$\pi_1$ greedy

$\pi_2$ greedy

$\pi^*$ optimal

Bellman Optimality Operator

Replace the policy average with a max — directly targeting the optimal value.

$$(\mathcal{T}^* V)(s) \;=\; \max_{a \in \mathcal{A}}\; \underset{S' \sim P(\cdot \mid s,\, a)}{\mathbb{E}}\!\left[r(s) + \gamma\, V(S')\right]$$

Value Iteration (Model-Based)

PI vs VI

Two roads to the same destination: PI alternates eval/improve, VI fuses them.

Policy Iteration

Value Iteration

Notebook 03 — Dynamic Programming

Evaluate fixed policies on a grid, visualise the effect of γ, then find the optimal policy via Policy Iteration and Value Iteration.

Temporal Difference Learning (Model-Free)

TD(0) — Policy Evaluation V-function

Pseudocode

Input: $\mathcal{D} = \{(s_t,\, a_t,\, r_t,\, s'_t)\}$  with  $s'_t \sim P^\pi(\cdot \mid s_t)$ ← on-policy

Init: $v(s) \leftarrow 0 \quad \forall\, s \in \mathcal{S}$

For each $(s_t,\, a_t,\, r_t,\, s'_t) \in \mathcal{D}$:

$\delta_t = r_t + \gamma\,v(s'_t) - v(s_t)$

$v(s_t) \leftarrow v(s_t) + \alpha\,\delta_t$

Action-Value Function Q-Function

TD(0) — Policy Evaluation Q-function (SARSA)

Pseudocode

Input: $\mathcal{D} = \{(s_t,\, a_t,\, r_t,\, s'_t,\, a'_t)\}$  with  $a'_t \sim \pi(\cdot \mid s'_t)$ ← on-policy

Init: $q(s, a) \leftarrow 0 \quad \forall\, s \in \mathcal{S},\, a \in \mathcal{A}$

For each $(s_t,\, a_t,\, r_t,\, s'_t,\, a'_t) \in \mathcal{D}$:

$\delta_t = r_t + \gamma\,q(s'_t, a'_t) - q(s_t, a_t)$

$q(s_t, a_t) \leftarrow q(s_t, a_t) + \alpha\,\delta_t$

$\hat{v}(s) = \textstyle\sum_a \pi(a \mid s)\, q(s, a)$

V-function vs Q-function

Q removes the need for a model: the greedy policy reads directly from the table.

Q-Learning Off-Policy TD(0)

Pseudocode

Input: $\mathcal{D} = \{(s_t,\, a_t,\, r_t,\, s'_t)\}$  with  $a_t \sim b(\cdot \mid s_t)$ ← any behavior

Init: $q(s, a) \leftarrow 0 \quad \forall\, s,\, a$

For each $(s_t,\, a_t,\, r_t,\, s'_t) \in \mathcal{D}$:

$\delta_t = r_t + \gamma\,\max_{a'} q(s'_t,\, a') - q(s_t, a_t)$

$q(s_t, a_t) \leftarrow q(s_t, a_t) + \alpha\,\delta_t$

$\hat{v}^*(s) = \max_a\, q(s, a) \;\xrightarrow{k\to\infty}\; v^*$

How Far Should We Look? n-step Return

Choosing the Horizon n-step Return

The λ-Return TD(λ)

Forward View TD(λ)

Backward View Eligibility Traces

Notebook 03b — Model-Free Methods

TD(0) policy evaluation, effect of α, SARSA vs Q-Learning control, and TD(λ) eligibility traces — all on the Grid World.

Tabular → Deep RL

When the state space grows, replace the table with a neural network.

tabular — doesn't scale

$Q \in \mathbb{R}^{|\mathcal{S}| \times |\mathcal{A}|} \quad \xrightarrow{\text{large }\mathcal{S}} \quad \text{intractable}$

function approximation

$V_w(s),\quad Q_w(s,a),\quad \pi_\theta(\cdot \mid s)$

same Bellman · same TD target

$w \leftarrow w + \alpha\,\nabla_w\,\mathcal{L}(w)$

DQN Deep Q-Network

loss

$\mathcal{L}(w) = \underset{(S_t,A_t,R_t,S_{t+1}) \sim \mathcal{B}}{\mathbb{E}}\!\left[\Bigl(R_t + \gamma \max_{a'} Q_{w^-}(S_{t+1},a') - Q_w(S_t,A_t)\Bigr)^{\!2}\right]$

update

$w \leftarrow w - \alpha\,\nabla_w\mathcal{L}(w)$   every step

$w^- \leftarrow w$   every $C$ steps

Notebook 03c — Deep RL

DQN · Experience replay · Target network

Why Policy Gradient?

Instead of learning values and deriving a policy, optimize the policy directly.

Policy Gradient Theorem

The gradient of performance equals an expectation over log-policy times return.

REINFORCE Monte Carlo Policy Gradient

Init: $\theta$ arbitrary

For $k = 0, 1, 2, \ldots$

── collect trajectory ───────────

$S_0 \sim \delta_0$

For $t = 0, \ldots, T{-}1$:

$A_t \sim \pi_\theta(\cdot \mid S_t)$ sample action

$S_{t+1} \sim P(\cdot \mid S_t, A_t)$ sample next state

── update ───────────────────────

$G_T \leftarrow 0$

For $t = T{-}1, \ldots, 0$:

$G_t \leftarrow r(S_t) + \gamma\, G_{t+1}$

$\theta \leftarrow \theta + \alpha\, G_t\, \nabla_\theta \log \pi_\theta(A_t \mid S_t)$

Variance Reduction Baseline

Advantage Function

Definition

$$A^{\pi_\theta}(s,a) \;=\; Q^{\pi_\theta}(s,a) - V^{\pi_\theta}(s)$$

REINFORCE with baseline

Optimal $b^*(s) = V^{\pi_\theta}(s)$

$\theta \leftarrow \theta + \alpha\, A^{\pi_\theta}(S_t, A_t)\,\nabla_\theta \log \pi_\theta(A_t \mid S_t)$

Actor-Critic

The critic estimates the advantage; the actor updates in the direction it points.

TD Error — advantage estimate

$$\delta_t \;=\; r(S_t) + \gamma\,V_w(S_{t+1}) - V_w(S_t)$$

Critic update

$w \leftarrow w + \beta\,\delta_t\,\nabla_w V_w(S_t)$

Actor update

$\theta \leftarrow \theta + \alpha\,\delta_t\,\nabla_\theta \log \pi_\theta(A_t \mid S_t)$

TRPO Trust Region Policy Optimization

Maximize improvement while staying inside a KL trust region around the current policy.

$\displaystyle r_t(\theta) \;=\; \frac{\pi_\theta(A_t \mid S_t)}{\pi_{\theta_\text{old}}(A_t \mid S_t)}$

objective

$\pi^* = \displaystyle\arg\max_\theta \underset{\substack{S_t \sim d^{\pi_{\theta_\text{old}}} \\ A_t \sim \pi_{\theta_\text{old}}(\cdot \mid S_t)}}{\mathbb{E}}\!\Big[r_t(\theta)\cdot A^{\pi_{\theta_\text{old}}}(S_t,A_t)\Big]$

constraint

$\text{s.t.}\;\;\underset{S_t \sim d^{\pi_{\theta_\text{old}}}}{\mathbb{E}}\!\left[\text{KL}\!\left(\pi_{\theta_\text{old}}(\cdot\mid S_t)\,\|\,\pi_\theta(\cdot\mid S_t)\right)\right]\leq\delta$

PPO Proximal Policy Optimization

Replace the KL constraint with a simple clip — same idea, much simpler to implement.

$\displaystyle r_t(\theta) \;=\; \frac{\pi_\theta(A_t \mid S_t)}{\pi_{\theta_\text{old}}(A_t \mid S_t)}$

objective

$$\pi^* = \arg\max_\theta \underset{\substack{S_t \sim d^{\pi_{\theta_\text{old}}} \\ A_t \sim \pi_{\theta_\text{old}}(\cdot \mid S_t)}}{\mathbb{E}}\!\left[\min\!\left(\begin{array}{l}r_t(\theta)\,A^{\pi_{\theta_\text{old}}},\\[4pt]\text{clip}(r_t(\theta),1{-}\varepsilon,1{+}\varepsilon)\,A^{\pi_{\theta_\text{old}}}\end{array}\right)\right]$$

no KL constraint — ε controls the trust region

$\text{clip}\!\left(r_t(\theta),\,1{-}\varepsilon,\,1{+}\varepsilon\right) \;\in\; [1{-}\varepsilon,\;1{+}\varepsilon]$

Evolutionary Strategies Black-box Policy Search

Estimate the gradient by evaluating random perturbations — no backpropagation needed.

$\theta_i = \mu_k + \sigma\varepsilon_i, \quad \varepsilon_i \sim \mathcal{N}(0, I)$

objective

$\mu^* = \displaystyle\arg\max_{\mu} \underset{\theta \sim \mathcal{N}(\mu,\,\sigma^2 I)}{\mathbb{E}}\!\left[J(\theta)\right]$

update — no gradient needed

$\mu_{k+1} = \mu_k + \dfrac{\alpha}{n\sigma} \displaystyle\sum_{i=1}^{n} J(\theta_i)\,\varepsilon_i$

CMA-ES Covariance Matrix Adaptation

Adapt both the mean and the covariance of the search distribution using elite samples.

$\theta_i \sim \mathcal{N}(\mu_k,\; C_k)$

objective

$(\mu^*, C^*) = \displaystyle\arg\max_{\mu,\, C} \underset{\theta \sim \mathcal{N}(\mu,\, C)}{\mathbb{E}}\!\left[J(\theta)\right]$

update — top-λ elites, weights wᵢ ∝ rank J(θᵢ)

$\mu_{k+1} = \displaystyle\sum_{i=1}^{\lambda} w_i\,\theta_i$

$C_{k+1} = \displaystyle\sum_{i=1}^{\lambda} w_i\,(\theta_i - \mu_k)(\theta_i - \mu_k)^\top$

Deep PPO actor-critic · shared trunk

A single network with shared features for both policy and value heads.

combined loss

$\mathcal{L}(\theta) = \mathcal{L}^{\text{clip}} + c_1\,\mathcal{L}^{\text{value}} - c_2\,\mathcal{L}^{\text{entropy}}$

clip $-\underset{\substack{S_t \sim d^{\pi_{\theta_\text{old}}} \\ A_t \sim \pi_{\theta_\text{old}}(\cdot \mid S_t)}}{\mathbb{E}}\!\left[\min\!\left(r_t\hat{A}_t,\;\operatorname{clip}(r_t,1\!\pm\!\varepsilon)\hat{A}_t\right)\right]$

value $\underset{S_t \sim d^{\pi_{\theta_\text{old}}}}{\mathbb{E}}\!\left[\bigl(V_\theta(S_t) - \hat{V}_t\bigr)^2\right]$

entropy $\underset{S_t \sim d^{\pi_{\theta_\text{old}}}}{\mathbb{E}}\!\left[\mathcal{H}(\pi_\theta(\cdot \mid S_t))\right]$

Notebook 04 — Policy Gradient

REINFORCE · PPO · Brax Humanoid

Notebook 05 — Evolution Strategies

ES · CMA-ES · Brax InvertedDoublePendulum