Reinforcement Learning (AD-802 (B)) Unit 2 Notes

How unit 2 is examined

Bandits (UCB, PAC, median elimination) carry the marks, with one passive versus active RL comparison; the rest is DP, Monte-Carlo and TD basics.

Bandit algorithms – UCB

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. A multi-armed bandit has $k$ arms, each with an unknown reward distribution; the agent pulls one arm per step and sees only that arm's reward. It is RL with a single state, so actions do not change what comes next.

Key points.

The objective is to maximise cumulative reward, or equivalently to minimise regret, the reward lost by not always pulling the best arm.
The core difficulty is exploration versus exploitation: pulling the best-looking arm earns now, while trying other arms may reveal a better one.
The action value is the sample average $Q_t(a)=\frac{\text{sum of rewards from } a}{n_a}$, updated incrementally.
Regret is $\rho_T = T\mu^* - \sum_t r_t$, where $\mu^*$ is the best arm's mean; good algorithms make it grow only logarithmically in $T$.
UCB is optimism in the face of uncertainty: each arm gets its estimate plus a bonus that is large for rarely pulled arms, and the highest total is played.
Median Elimination finds a near-best arm: sample every arm, discard the worse-than-median half, shrink the tolerance, and repeat until one arm remains.
PAC means the algorithm returns an arm within $\epsilon$ of the best with probability at least $1-\delta$, using a bounded number of samples.

Formula. $$A_t=\arg\max_a\left[Q_t(a)+\sqrt{\frac{2\ln t}{n_a}}\right]$$

Example. UCB1 with $t=12$, $\ln 12=2.485$.

Arm	$n_a$	$Q$	Bonus $\sqrt{2\ln t/n_a}$	UCB
1	3	0.55	1.287	1.837
2	4	0.63	1.115	1.745
3	3	0.61	1.287	1.897
4	2	0.40	1.576	1.976

Arm 4 is played next, since it has the highest UCB (1.976). Its low $Q$ is outweighed by its bonus, because it has been pulled least.

<mark>A bandit algorithm balances exploration and exploitation to maximise cumulative reward, which is the same as minimising regret.</mark>

Answer frame. Objective question: open with the bandit definition; draw nothing; develop points 1-4; close with the exploration-exploitation trade-off. Numerical: write the formula, tabulate bonus and UCB per arm, close with the bold arm. Three-part explain: give each of UCB, median elimination and PAC a definition and a formula or guarantee.

Asked: [14 marks] (Jun 2025) Explain the following with respect to bandit algorithms: i) Median Elimination ii) Upper Confidence Bound (UCB) algorithm iii) Probably Approximately Correct (PAC) Asked: [7 marks] (Jun 2025) What is the key objective of bandit algorithms with reference to reinforcement learning? Asked: [7 marks] (Jun 2025) After 12 iterations of UCB1 on a 4-arm bandit, $n_1=3, n_2=4, n_3=3, n_4=2$ and $Q_{12}(1)=0.55, Q_{12}(2)=0.63, Q_{12}(3)=0.61, Q_{12}(4)=0.40$. Which arm should be played next? Pitfall: Using $\ln$ of the arm's own count instead of the total steps $t$ in the bonus.

PAC

Definition. Probably Approximately Correct learning guarantees an answer that is approximately right, within $\epsilon$, with probability at least $1-\delta$.

In bandits, an $(\epsilon,\delta)$-PAC algorithm returns an arm whose mean is within $\epsilon$ of the best.
Sample complexity is the number of pulls needed, and it grows as $\frac{1}{\epsilon^2}\ln\frac{1}{\delta}$ per arm.
Smaller $\epsilon$ or $\delta$ means more samples.
Median Elimination is the standard PAC bandit algorithm.

Median Elimination

Definition. Median Elimination is a PAC best-arm identification method that repeatedly discards the worse half of the arms.

Each round samples every surviving arm equally and computes the empirical means.
Arms whose mean is below the median are eliminated, halving the set.
Tolerance $\epsilon$ and confidence $\delta$ are split across rounds, and about $\log_2 k$ rounds remain.
The final arm is $\epsilon$-optimal with probability $1-\delta$, using $O\left(\frac{k}{\epsilon^2}\ln\frac{1}{\delta}\right)$ samples.

Policy Gradient

Definition. Policy gradient methods directly parameterise the policy $\pi_\theta(a|s)$ and adjust $\theta$ by gradient ascent on expected return $J(\theta)$.

The REINFORCE update is $\theta\leftarrow\theta+\alpha\,G_t\nabla_\theta\ln\pi_\theta(a_t|s_t)$.
It handles continuous actions and gives stochastic policies naturally.
Estimates have high variance, reduced by subtracting a baseline.
It is on-policy and needs complete episodes.

Full RL & MDPs

Definition. Full RL is learning in an MDP $(S,A,P,R,\gamma)$, where actions change future states, unlike a bandit. Passive RL learns the value of a fixed given policy; active RL learns the optimal policy while choosing its own actions.

Passive RL evaluates a fixed policy $\pi$, so the agent only observes and the task is prediction.
Active RL must decide what to do, so it must explore and the task is control.
Passive RL needs no exploration; active RL must balance exploration and exploitation.
Passive methods include direct utility estimation, adaptive DP and TD; active methods include Q-learning, SARSA and active adaptive DP.

Basis	Passive RL	Active RL
Policy	Fixed	Learned and changing
Goal	Evaluate $V^\pi$	Find $\pi^*$
Exploration	Not needed	Essential
Task	Prediction	Control
Example	TD(0) on given policy	Q-learning

Asked: [7 marks] (Jun 2025) What is meant by passive and active reinforcement learning and how do we compare the two?

Bellman Optimality

Definition. The Bellman optimality equation says the optimal value of a state equals the best action's expected reward plus discounted optimal value of the next state.

$V^*(s)=\max_a\sum_{s'}P(s'|s,a)\,[R+\gamma V^*(s')]$.
$Q^*(s,a)=\sum_{s'}P(s'|s,a)\,[R+\gamma\max_{a'}Q^*(s',a')]$.
The max makes it non-linear, so it has no closed form and is solved iteratively.
Acting greedily on $V^*$ gives an optimal policy.

Dynamic Programming - Value iteration, Policy iteration

Definition. Dynamic programming solves an MDP with a known model by reusing computed values through Bellman equations.

It needs the full model $P$ and $R$.
It bootstraps: each value is updated from other estimated values.
The two main methods are value iteration and policy iteration.
Cost per sweep is $O(|S|^2|A|)$, so it suits small state spaces.

Policy Evaluation

Definition. Policy evaluation computes $V^\pi$ for a fixed policy by repeatedly applying the Bellman expectation equation.

Update: $V_{k+1}(s)=\sum_a\pi(a|s)\sum_{s'}P(s'|s,a)[R+\gamma V_k(s')]$.
Start from any $V_0$ and sweep all states.
Stop when the largest change is below a small threshold $\theta$.
It converges to $V^\pi$ for $\gamma<1$.

Value Iteration

Definition. Value iteration turns the Bellman optimality equation into an update, combining one evaluation sweep and improvement.

Update: $V_{k+1}(s)=\max_a\sum_{s'}P(s'|s,a)[R+\gamma V_k(s')]$.
Iterate until the maximum change is below $\theta$.
Extract the policy by taking the greedy action.
It needs no explicit policy while running.

Policy Iteration

Definition. Policy iteration alternates full policy evaluation with greedy policy improvement until the policy stops changing.

Evaluate the current $\pi$ to get $V^\pi$.
Improve: $\pi'(s)=\arg\max_a\sum_{s'}P(s'|s,a)[R+\gamma V^\pi(s')]$.
Repeat until $\pi'=\pi$, which gives $\pi^*$.
It usually needs few iterations, but each evaluation is costly.

DP Extensions and Convergence using Contraction Mapping

Definition. The Bellman operator is a $\gamma$-contraction in the max norm, so repeated application converges to a unique fixed point (Banach theorem).

$\|TV-TU\|_\infty\le\gamma\|V-U\|_\infty$ for $\gamma<1$.
Hence value iteration converges to $V^*$ from any start, at a geometric rate.
Extensions include asynchronous DP, in-place updates and prioritised sweeping.
Generalised policy iteration mixes partial evaluation with improvement.

Monte-Carlo (MC) Learning

Definition. Monte-Carlo learning estimates values by averaging complete-episode returns, without a model.

$V(s)$ is the average return $G_t$ observed after visiting $s$.
First-visit uses the first visit per episode; every-visit uses all.
It works only on episodic tasks and updates after the episode ends.
It has high variance but no bias and does not bootstrap.

Temporal-Difference (TD) Learning

Definition. TD learning updates a value from the immediate reward and the next state's estimate, so it bootstraps and needs no model.

TD(0): $V(s_t)\leftarrow V(s_t)+\alpha[r_{t+1}+\gamma V(s_{t+1})-V(s_t)]$.
The bracket is the TD error $\delta_t$.
It updates every step, works on continuing tasks, and has lower variance than MC.
It is biased, since the target uses an estimate.

TD-Lambda and Eligibility Traces

Definition. TD($\lambda$) blends n-step returns using a decay $\lambda\in[0,1]$, implemented with eligibility traces.

Trace: $e_t(s)=\gamma\lambda e_{t-1}(s)+\mathbb{1}[s_t=s]$.
Update: $V(s)\leftarrow V(s)+\alpha\,\delta_t\,e_t(s)$ for all states.
$\lambda=0$ gives TD(0) and $\lambda=1$ gives Monte-Carlo.
Recently visited states receive the most credit for the error.

Last-minute revision

Bandit: one state, $k$ arms; goal is to maximise cumulative reward, i.e. minimise regret.
UCB1: $Q(a)+\sqrt{2\ln t/n_a}$; play the argmax.
Jun 2025 numerical: UCB values 1.837, 1.745, 1.897, 1.976; play arm 4.
Median Elimination drops the below-median half each round.
PAC: within $\epsilon$ of best with probability $1-\delta$.
Passive RL evaluates a fixed policy; active RL learns the optimal one and must explore.
Bellman optimality: $V^*(s)=\max_a\sum P[R+\gamma V^*(s')]$.
Bellman operator is a $\gamma$-contraction, so VI converges.
Policy iteration: evaluate, improve, repeat until stable.
MC uses full returns; TD(0) uses $r+\gamma V(s')$.
TD($\lambda$): $\lambda=0$ is TD(0), $\lambda=1$ is MC.

Memory hooks

UCB = Estimate plus Uncertainty bonus: optimism for the unknown.
PAC = "Probably" is $\delta$, "Approximately" is $\epsilon$.
Passive watches, active acts.
MC waits for the end; TD learns step by step.
Lambda dial: 0 is TD, 1 is Monte-Carlo.

Coverage checklist

Bandit algorithms – UCB: Jun 2025 14-mark explain, 7-mark objective, 7-mark UCB1 numerical.
PAC: covered under UCB question and own section.
Median Elimination: covered under UCB question and own section.
Policy Gradient: no past question.
Full RL & MDPs: Jun 2025 passive versus active comparison.
Bellman Optimality: no past question.
Dynamic Programming - Value iteration, Policy iteration: no past question.
Policy Evaluation: no past question.
Value Iteration: no past question.
Policy Iteration: no past question.
DP Extensions and Convergence using Contraction Mapping: no past question.
Monte-Carlo (MC) Learning: no past question.
Temporal-Difference (TD) Learning: no past question.
TD-Lambda and Eligibility Traces: no past question.

Account

Reinforcement Learning (AD-802 (B)) - Unit 2 Short Notes