Reinforcement Learning

An agent interacts with an environment through a trajectory $\tau=(S_0,A_0,R_1,S_1,\ldots)$. A Markov Decision Process is $(\mathcal{S},\mathcal{A},P,R,\gamma)$: states, actions, transition probabilities, rewards, and discount factor. The Markov property says the current state contains the information needed to predict the next transition given an action; Unit 19 develops the stochastic-process foundation.

The return after time $t$ is $$G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots.$$ A smaller $\gamma$ favors immediate reward; a value near one gives longer-horizon consequences more weight. In finite episodes $\gamma$ may equal one, while continuing tasks usually use $\gamma<1$ to keep returns finite.

A policy $\pi(a\mid s)$ may be deterministic or stochastic. RL differs from supervised learning because actions affect which future observations and rewards become available.

The state value is $V^\pi(s)=\mathbb{E}_\pi[G_t\mid S_t=s]$ and the action value is $Q^\pi(s,a)=\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a]$. The Bellman expectation equation decomposes value into one-step reward plus discounted value under the same policy: $$V^\pi(s)=\sum_a\pi(a\mid s)\sum_{s',r}p(s',r\mid s,a)[r+\gamma V^\pi(s')].$$

Optimality replaces the policy average with the best next choice: $$V^*(s)=\max_a\sum_{s',r}p(s',r\mid s,a)[r+\gamma V^*(s')].$$ A Bellman backup applies one of these right-hand sides to update an estimate.

Policy evaluation repeatedly applies the Bellman expectation backup until values stabilize for a fixed policy. Policy improvement then acts greedily with respect to those values. Alternating the two gives policy iteration. Value iteration combines partial evaluation and improvement by repeatedly applying the Bellman optimality operator.

For a finite discounted MDP, the optimality operator is a contraction, so repeated exact backups converge to $V^*$. In larger problems, sampling and function approximation replace exhaustive state sweeps.

Model-free Q-learning updates from an observed transition: $$Q(s,a)\leftarrow Q(s,a)+\alpha\big[r+\gamma\max_{a'}Q(s',a')-Q(s,a)\big].$$ The bracketed quantity is the temporal-difference (TD) error. It is off-policy because its target uses the greedy next action even when behavior explores.

$\epsilon$-greedy selects a random action with probability $\epsilon$ and otherwise a greedy action. With $m$ actions and a unique greedy action, that action's total probability is $1-\epsilon+\epsilon/m$. A stochastic policy instead learns a full probability distribution, which is useful for naturally uncertain or continuous control.

A DQN replaces the table with $Q(s,a;\theta)$. An experience replay buffer breaks short-range correlations and reuses transitions in random mini-batches. A separate target network supplies slowly changing bootstrap targets. Without these devices, moving targets, correlated data, and maximization bias can destabilize learning; monitor seeds and learning curves rather than trusting one run.

Policy gradients directly maximize $J(\theta)=\mathbb{E}_{\tau\sim\pi_\theta}[G_0]$. The score-function estimator weights log-policy gradients by returns: $$\nabla_\theta J(\theta)=\mathbb{E}[\nabla_\theta\log\pi_\theta(A_t\mid S_t)G_t].$$ High-return actions become more probable; a baseline can reduce variance without changing the expected gradient.

The advantage $A(s,a)=Q(s,a)-V(s)$ says whether an action is better than the state's baseline. Actor–critic methods use an actor for $\pi_\theta$ and a critic for $V_\phi$ or $Q_\phi$. A one-step TD error $\delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t)$ is a practical advantage estimate.

PPO constrains policy changes through a clipped probability-ratio objective, improving reliability compared with unconstrained large policy steps. It remains sensitive to reward design, normalization, rollout length, and implementation details.