Deep Reinforcement Learning

Multi-Armed Bandit: Advanced Topics

📅 Published: 2026-07-18

🎓 Level: postgraduate

👥 Audience: Postgraduate students studying Deep Reinforcement Learning

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures in this subject. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Sample-average estimation & action value methods — covered in Lecture 2 (Sample-Average Estimation, Action Value Methods).
Greedy and epsilon-greedy action selection — covered in Lecture 2 (Greedy Action Selection, Epsilon-Greedy Action Selection) and Lecture 1 (Greedy Action Selection, Epsilon-Greedy).
Incremental update derivation — covered in Lecture 2 (Derivation of the Incremental Update).
Sample-average vs. constant step-size — covered in Lecture 2 (Sample-Average vs. Constant Step-Size).
Stationary vs. non-stationary rewards — covered in Lecture 2 (Stationary vs. Non-Stationary Rewards).
Role of the step size α — covered in Lecture 1 (The Role of the Step Size α).
Contextual bandits introduction — covered in Lecture 2 (When MAB is Not Enough: Contextual Bandits).

Multi-Armed Bandit: Advanced Topics

3.1 Review: MAB Fundamentals Recap

This section reviews the core ideas from multi-armed bandits. We need these building blocks before tackling advanced topics like non-stationarity and UCB.

Symbol registry — Section 3.1:

$Q (a)$ — estimated value of action $a$ — scalar
$q^{*} (a)$ — true expected reward for action $a$ — scalar
$R$ — reward received from an action — scalar
$N (a)$ — number of times action $a$ has been selected — integer
$ϵ$ (epsilon) — exploration rate — scalar in $(0, 1)$
$ar g max_{a}$ — "the action $a$ that maximizes" — operator

3.1.1 Core Concepts Review

Hook: Imagine walking into a casino with five slot machines. You have 100 coins. Each machine has a different — but hidden — average payout. How do you maximize your winnings?

The tourist analogy: Picture a tourist in Paris who wants to find the best bakery. There are five bakeries on the street. Each day, the tourist picks one bakery and rates the croissant on a 1–10 scale. After a few days, the tourist starts to get a sense of which bakery is best. But here is the catch: the tourist can never be sure, because each croissant is slightly different. Maybe bakery B gave one amazing croissant on day one, but its average is mediocre. Maybe bakery C gave a mediocre croissant on day one, but its average is actually high.

The tourist's problem is exactly the multi-armed bandit (MAB) problem. Each bakery is an arm. Each rating is a reward. The tourist is the agent trying to figure out which arm is best while getting as many good croissants as possible.

Where the analogy breaks: Unlike bakeries, bandit arms don't run out of croissants. You can pull the same arm forever. But the rewards you get are noisy — the same arm can give different rewards each time.

What is a K-armed bandit problem?

A K-armed bandit (also called a multi-armed bandit or MAB) is a decision problem where:

You have $K$ actions (arms) to choose from.
Each action $a$ has a hidden true value $q^{*} (a)$ — the average reward you would get if you pulled that arm infinitely many times.
You don't know $q^{*} (a)$ . You only see the reward $R$ each time you pull an arm.
Your goal: maximize total reward over time.

The name comes from slot machines ("one-armed bandits") — a K-armed bandit is a slot machine with K levers.

Key insight: If your problem depends on state — if the best action changes based on what you observe — then vanilla MAB is not enough. For example:

Driving: Your action (turn left, brake, accelerate) depends on the current road state. MAB ignores state, so it can't drive a car.
Chess: Your move depends on the board. MAB doesn't model this.
Weather and umbrella: You pick an umbrella based on the weather. The weather doesn't change because you took an umbrella.

If actions depend on states, you need either contextual bandits (covered in 3.9) or full reinforcement learning (covered later). Vanilla MAB is the simplest case: no state, just arms and rewards.

When does MAB fit? When the environment doesn't change based on your actions. Examples: choosing which ad to show on a webpage, selecting which email subject line to use for a campaign, deciding which drug dosage to test on the next patient (one-shot).

3.1.2 Action Value Methods

Hook: You've been pulling arms. How do you keep score? How do you know which arm is good?

Analogy: Think of tracking which coffee shop gives the best espresso. After visiting each shop several times, you keep a mental average rating for each. You don't need to know the true average quality — you just need a good enough estimate to pick where to go next morning.

Action value — the sample average method:

The action value $Q_{n} (a)$ is your estimate of how good action $a$ is after $n$ total time steps. The simplest way to compute it is by averaging all the rewards you have received from action $a$ :

$Q_{n} (a) = \frac{R _{1} + R _{2} + \dots + R _{N_{n} (a)}}{N _{n} ( a )}$

where:

$Q_{n} (a)$ — estimated value of action $a$ at time step $n$ (scalar)
$R_{i}$ — the $i$ -th reward received from action $a$ (scalar)
$N_{n} (a)$ — number of times action $a$ has been selected up to time $n$ (integer)

If $N_{n} (a) = 0$ (action never selected), we define $Q_{n} (a)$ as some default, often 0.

This is called the sample average method because $Q_{n} (a)$ is literally the sample mean of the rewards from action $a$ .

True value vs. estimate — a critical distinction:

$q^{*} (a)$ — the true expected reward for action $a$ . This is the number you would get if you pulled arm $a$ infinitely many times and averaged. You never know this.
$Q_{n} (a)$ — your estimate of $q^{*} (a)$ based on the rewards you have seen so far.

By the law of large numbers, as $N_{n} (a) \to \infty$ , $Q_{n} (a) \to q^{*} (a)$ . But with finite pulls, your estimate is noisy.

Worked example — sample averages:

You have 3 arms. After 6 total pulls, you have:

Arm	Pulls	Rewards	$Q (a)$
A1	3	2, 4, 3	$(2 + 4 + 3) /3 = 3.0$
A2	2	5, 1	$(5 + 1) /2 = 3.0$
A3	1	7	$7/1 = 7.0$

Your estimates: $Q (A 1) = 3$ , $Q (A 2) = 3$ , $Q (A 3) = 7$ .

A greedy agent picks A3 (highest estimate). But A3 was only pulled once — the estimate is unreliable. Maybe A3's true value is 2 and you got lucky.

Sense-check: With only 6 pulls, you have very little information. The estimates will change a lot with more data.

Scope: Sample averaging assumes:

Rewards are drawn from a fixed distribution (stationarity).
Past rewards are independent of each other (IID).

If rewards change over time, sample averaging gives equal weight to old and new data. This is bad in non-stationary environments — covered in 3.4.

Pitfall: Don't confuse $Q (a)$ with $q^{*} (a)$ . Your estimate might be way off, especially for arms pulled few times. Always check $N (a)$ — the number of pulls — before trusting an estimate.

3.1.3 Action Selection Methods Review

Hook: You have estimates for each arm. Now: which arm do you actually pull?

The explore-exploit tradeoff — the professor's French analogy:

The professor gives a vivid analogy for why exploration matters. Imagine you want to learn French. You go to France. If you only speak what you already know, you never learn new words. You have to try, fail, try, fail — and with time, things change. At some point, you want to use what you have learned (exploit). But even then, you need to keep exploring, because as you move across France, the slang, local culture, and way of speaking change.

The mapping:

Speaking what you know = exploiting
Trying new phrases = exploring
Getting better at French = learning the true action values
Regional slang changes = non-stationarity (covered in 3.4)

Greedy action selection:

Always select the action with the highest estimated value:

$A_{t} = ar g a max Q_{t} (a)$

$A_{t}$ — action chosen at time $t$
$ar g max_{a}$ — "the action $a$ that maximizes"
Ties broken randomly

Greedy exploits current knowledge. It never explores. If the initial estimate of the best arm is wrong (due to bad luck), greedy never corrects.

Epsilon-greedy action selection:

A simple fix to add exploration. At each time step:

Generate a random number $p \in [0, 1)$ .
If $p < ϵ$ : select a random action (exploration).
If $p \geq ϵ$ : select the greedy action $ar g max_{a} Q_{t} (a)$ (exploitation).

$ϵ$ (epsilon) is a number between 0 and 1. Common choice: $ϵ = 0.1$ (10% exploration, 90% exploitation).

The two-stage decision: First the coin flip decides explore vs. exploit. Then the arm is chosen. When exploring, the agent picks uniformly at random — no arm is favored. When exploiting, the agent picks the arm with the highest $Q$ .

Why epsilon-greedy guarantees learning:

As $t \to \infty$ , every arm gets tried infinitely often (because of the random exploration). By the law of large numbers, $Q_{t} (a) \to q^{*} (a)$ for all arms. This means the greedy action converges to the truly best arm. The probability of picking the optimal arm converges to at least $1 - ϵ$ .

Worked example — greedy vs. epsilon-greedy:

Three arms, true values (unknown to agent): $q^{*} (A 1) = 3$ , $q^{*} (A 2) = 5$ , $q^{*} (A 3) = 4$ .

After 10 pulls with initial luck:

Arm	$Q (a)$	$N (a)$
A1	6.0	2
A2	4.0	5
A3	3.0	3

Greedy: Picks A1 (highest $Q = 6.0$ ). But A1's true value is only 3 — the agent got lucky on 2 pulls. Greedy keeps picking A1 forever, missing the true best arm (A2).

Epsilon-greedy ( $ϵ = 0.1$ ): 90% of the time picks A1 (same as greedy). But 10% of the time, picks a random arm. This gives A2 and A3 occasional chances. Over time, A2's estimate will rise toward 5, and the agent will start exploiting A2.

Sense-check: Greedy is stuck. Epsilon-greedy recovers. The cost of exploration is small (10% of pulls), but the benefit is huge (finding the true best arm).

Comparison — Greedy vs. Epsilon-Greedy:

Dimension	Greedy	Epsilon-Greedy
Exploration	None	$ϵ$ % random
Risk of getting stuck	High	Low
Short-term reward	Higher initially	Lower initially
Long-term reward	Lower	Higher
Parameters to set	None	$ϵ \in (0, 1)$
Convergence to optimal	Not guaranteed	Guaranteed (as $t \to \infty$ )

Pitfall: Setting $ϵ$ too high (e.g., 0.5) wastes half your pulls on random exploration. Setting it too low (e.g., 0.01) barely explores and might get stuck. The right value depends on the problem — typically 0.05 to 0.2 works well.

Pitfall: In non-stationary environments (where true values change), don't decay $ϵ$ to zero over time. You need ongoing exploration to track changes. Keep $ϵ$ constant.

Recap: Greedy exploits what you know; epsilon-greedy adds random exploration via $ϵ$ . This tradeoff is the heart of RL: exploit for short-term reward, explore for long-term learning. The French analogy captures the spirit — you must try and fail to learn.

Bridge: Next we look at what happens when the reward distributions change over time — non-stationarity — which makes the exploration-exploitation tradeoff even more important.

Real-world connection: Epsilon-greedy style algorithms are used in clinical trials (testing multiple treatments while mostly using the best-known one), online advertising (showing the best-performing ad while testing new ones), and recommendation systems (suggesting what users like while occasionally trying new content). Companies like Netflix and Spotify use bandit algorithms to balance showing popular content (exploit) with introducing users to new content (explore).

3.2 Stationary vs Non-Stationary Rewards

Symbol registry — Section 3.2:

$Var (R ∣ A = a)$ — reward variance for action $a$ — scalar
$q_{t}^{*} (a)$ — true value of action $a$ at time $t$ — scalar
$ϵ$ (epsilon) — exploration rate — scalar

3.2.1 Reward Variance Scenarios

Hook: Two slot machines both have an average payout of 5 dollars. One always pays exactly 5. The other pays 0 half the time and 10 half the time. Which one is easier to figure out?

Analogy — the dart board: Think of pulling an arm as throwing a dart at a target. Low variance means your darts cluster tightly around the bullseye — after a few throws, you know exactly where you're aiming. High variance means your darts scatter all over the board — you need many throws to figure out where the center is.

Reward variance measures how spread out the rewards are around the true mean. Formally, if the true value of arm $a$ is $q^{*} (a)$ , then the reward variance is:

$Var (R ∣ A = a) = E [(R - q^{*} (a))^{2}]$

The testbed experiments in the textbook use unit variance: each arm's reward is drawn from a normal distribution with mean $q^{*} (a)$ and variance 1.

Scenario 1 — Unit variance (standard case):

The mean reward might be around 10, but each pull gives a noisy reward. Higher variance means you cannot quickly confirm that you have learned the benefit of an action. You need to keep exploring longer. Don't bring $ϵ$ down too soon — the estimates are still uncertain.

Scenario 2 — Zero variance (deterministic rewards):

If you pull an arm that gives 5, it gives 5 every time — no noise. In theory, try each arm once and you know the true values. Pure greedy (try all once, then always pick the max) would work.

Why pure greedy is still risky even with zero variance:

The professor warns: "Even if you think that reward variance is 0 on paper, the actual scenario might actually introduce some uncertainty."

Real-world systems are never perfectly deterministic. Measurement noise, environmental drift, and model misspecification all add hidden variance. If you assume zero variance and use pure greedy, a single unlucky observation can lock you onto the wrong arm forever.

Worked example — variance and exploration:

Two arms, both with true value 5:

Arm	Variance	Observed rewards (3 pulls)	$Q (a)$
A1	0	5, 5, 5	5.0
A2	10	12, -1, 4	5.0

After 3 pulls, both have the same estimate. But A1's estimate is reliable (variance = 0, every pull gave 5). A2's estimate is unreliable (variance = 10, rewards ranged from -1 to 12).

Implication: With high variance, you need more pulls to be confident. With low variance, fewer pulls suffice. The right $ϵ$ depends on the variance — higher variance needs more exploration.

Recap: Variance determines how noisy the rewards are. High variance = noisy = need more exploration. Low variance = clean = can exploit sooner. Even zero variance on paper doesn't mean zero variance in practice.

3.2.2 Non-Stationary Rewards

Hook: What if the best arm today is not the best arm tomorrow?

Analogy — the stock market: Imagine picking stocks. Yesterday, tech stocks were the best performers. Today, energy stocks are surging. The "best" stock changes over time. If you only looked at historical averages and never re-evaluated, you'd miss the shift. Non-stationarity means the ground truth moves.

Non-stationary rewards: A reward distribution is non-stationary if the probability distribution for one or more actions changes over time. Formally:

$q_{t}^{*} (a) \neq = q_{t^{'}}^{*} (a) for some t \neq = t^{'}$

In a stationary environment, $q^{*} (a)$ is fixed. In a non-stationary environment, $q^{*} (a)$ drifts — the best arm at time 100 might not be the best at time 1000.

Why this matters for action-value estimation:

In a stationary environment, sample averaging works well — old data is just as useful as new data. In a non-stationary environment, old data is misleading. If arm A was best six months ago but arm B is best now, averaging all historical rewards gives a stale estimate.

Worked example — non-stationarity:

An online ad platform shows two ads. For the first 1000 users, ad A gets 10% click-through rate (CTR) and ad B gets 5%. The platform picks ad A (greedy).

Then user preferences shift. Ad B's CTR rises to 12%, ad A's drops to 3%. But the platform still thinks ad A is better because the historical average (over 2000 users) says so.

The problem: Sample averaging gives equal weight to old and new data. The stale data from the first 1000 users drowns out the signal from recent users.

The fix: Use a constant step size $α$ instead of $1/ n$ — covered in 3.4.

Handling non-stationarity — keep exploring:

The professor's industry example captures this perfectly. A manager approves your project plan one month, then changes direction the next month. If you stopped exploring after the first approval, you'd be out of date.

Rule: In non-stationary environments, never set $ϵ$ to zero. Keep $ϵ$ at some reasonable constant forever. Experiment with different values to find what works best.

Pitfall: Don't assume your environment is stationary. Most real-world environments are non-stationary: user preferences change, markets shift, competitors enter and exit. Build in ongoing exploration from the start.

Pitfall: Don't decay $ϵ$ to zero over time in non-stationary problems. If you stop exploring, you'll miss shifts in the reward landscape. Keep $ϵ$ constant or use a schedule that never reaches zero.

3.2.3 Real-World Formulations: Stationary vs. Non-Stationary Settings

To choose the right algorithm, you must identify whether your deployment environment is stationary or non-stationary. The table below outlines how common real-world domains manifest in both settings:

Stationary vs. Non-Stationary Settings Across Domains:

Setting	Stationary Version	Non-Stationary Version
Slot-machine Style Bandit	Each arm has a fixed payout distribution throughout the experiment. A long sequence of plays yields increasingly accurate estimates of fixed action values.	The payout pattern shifts after maintenance, a rule change, or altered operating conditions. Older observations no longer reflect present arm values.
Online Advertisement	During a short A/B experiment, the click probability for each advertisement is assumed nearly fixed. Each ad has a stable average reward.	User attention shifts with seasons, holidays, ad fatigue/repeated exposure, competitor campaigns, or current news. An ad that worked well earlier becomes less effective.
Treatment Choice	A controlled clinical study compares a few treatment protocols for a tightly defined patient group over a short period with stable patient characteristics.	Patient mix, disease variants, co-medications, adherence rates, and hospital practices evolve over time. Outcome distributions drift, so old evidence must not dominate forever.
Cloud Configuration	A cloud microservice is evaluated under a constant synthetic workload and fixed infrastructure. Each configuration exhibits a stable latency/throughput distribution.	Workload volume, traffic mix, background jobs, network congestion, and hardware contention fluctuate dynamically. The best configuration at 8 AM may fail during peak evening load.

In real-world engineering deployments, expecting non-stationarity is almost always safer. Practically all production bandit systems must track action values continuously rather than converging once and stopping adaptation.

Recap: Non-stationarity means the true action values change over time. This breaks sample averaging and pure greedy methods. The fix: use constant step sizes (3.4) and keep exploring ( $ϵ > 0$ always).

Bridge: Next we work through a complete epsilon-greedy example step by step, analyzing exactly when exploration vs. exploitation occurred.

Real-world connection: Online advertising is the canonical non-stationary bandit problem. User attention shifts daily — what's trending today is forgotten tomorrow. Google's ad auction system and Facebook's newsfeed algorithms use non-stationary bandit methods to adapt to these shifts in real time.

3.3 Epsilon-Greedy: Worked Example

Symbol registry — Section 3.3:

$Q (a)$ — estimated value of action $a$ — scalar
$N (a)$ — number of times action $a$ has been selected — integer
$ϵ$ — exploration rate — scalar in $(0, 1)$

Hook: Given a sequence of action selections and rewards, can you figure out exactly when the agent explored and when it exploited? This is like being a detective — the actions leave clues.

3.3.1 Problem Setup

The detective problem: You are given a log of an epsilon-greedy agent's behavior. Your job: for each time step, determine whether the agent certainly used epsilon (exploration), maybe used epsilon, or certainly used greedy (exploitation).

Problem setup:

K = 4 arms: A1, A2, A3, A4
Initial estimates: $Q_{0} (a) = 0$ for all $a$
Action values updated using sample averages: $Q_{n} (a) = \frac{\sum R _{i}}{N ( a )}$
Action selection: epsilon-greedy

Experience sequence:

Time	Action	Reward
1	A1	1
2	A2	1
3	A2	2
4	A2	2
5	A3	3

Question: On which time steps did epsilon definitely occur? On which time steps could it have occurred?

3.3.2 Step-by-Step Analysis

How to think about it: The professor's key insight: "Your entry point is, you first decide whether to do a random (epsilon) or 1-epsilon. And then only you are looking at the value."

This means: the coin flip happens first. If the agent explores (epsilon case), it picks any arm randomly. If it exploits (1-epsilon case), it picks the arm with the highest $Q$ .

So: if a non-best arm is chosen while a strictly better arm exists, it must be epsilon. If the best arm is chosen, it could be greedy or epsilon (the random pick might land on the best arm by luck).

Time Step 1: Selecting A1

Current estimates: A1=0, A2=0, A3=0, A4=0 (all equal)
Got reward 1, so $Q (A 1) = 1$
Analysis: All values are tied at 0. Greedy would pick any arm (random tiebreak). Epsilon would also pick any arm. No way to tell.
Verdict: MAYBE epsilon

Time Step 2: Selecting A2

Current estimates: A1=1, A2=0, A3=0, A4=0
A1 has the highest value (1), but A2 was selected
Got reward 1, so $Q (A 2) = 1$
Analysis: If greedy, A1 would definitely be chosen (it's the unique best). A2 was chosen instead. The only explanation: epsilon case (random exploration).
Verdict: CERTAINLY epsilon

Time Step 3: Selecting A2

Current estimates: A1=1, A2=1, A3=0, A4=0
Two arms tied for highest: A1 and A2 (both 1)
Got reward 2, so $Q (A 2) = (1 + 2) /2 = 1.5$
Analysis: Greedy could pick either A1 or A2 (random tiebreak). Epsilon could also pick any arm. A2 could be either.
Verdict: MAYBE epsilon

Time Step 4: Selecting A2

Current estimates: A1=1, A2=1.5, A3=0, A4=0
A2 has the highest value (1.5)
Got reward 2, so $Q (A 2) = (1 + 2 + 2) /3 = 5/3 \approx 1.67$
Analysis: Greedy would pick A2 (highest value). Epsilon could also pick A2 (randomly). Both explanations work.
Verdict: MAYBE epsilon

Time Step 5: Selecting A3

Current estimates: A1=1, A2=5/3 ≈ 1.67, A3=0, A4=0
A2 has the highest value (5/3), but A3 was selected
Got reward 3, so $Q (A 3) = 3$
Analysis: If greedy, A2 would definitely be chosen (unique best). A3 was chosen instead. Must be epsilon.
Verdict: CERTAINLY epsilon

3.3.3 Key Takeaway

The rule: We can say "certainly epsilon" only when a non-greedy action is chosen while a strictly better action exists. We can never say "certainly greedy" — even the greedy choice could happen by random exploration.

The professor's analogy: "There is a topper in the class, and you choose somebody else for the competition. I think the teacher have done something randomly." If the teacher picks the topper, maybe it was merit, maybe it was luck. But if the teacher picks someone else, it was definitely not based on merit.

Pitfall: Don't confuse "maybe epsilon" with "probably epsilon." At time step 4, A2 has the highest value. It could be greedy or epsilon. We simply can't tell. The analysis only distinguishes certain epsilon from possible epsilon.

Pitfall: The decision order matters. The coin flip (epsilon vs. 1-epsilon) happens before looking at Q values. This is why a non-best arm being chosen is strong evidence of epsilon — the agent didn't even consider Q values when exploring.

Worked example — computing Q values step by step:

Let's trace the full Q value table:

Time	Action	Reward	$Q (A 1)$	$Q (A 2)$	$Q (A 3)$
0	—	—	0	0	0
1	A1	1	1	0	0
2	A2	1	1	1	0
3	A2	2	1	1.5	0
4	A2	2	1	5/3	0
5	A3	3	1	5/3	3

At time 5, after the update, A3 suddenly has the highest value (3). If the agent continues, it might exploit A3 next — unless epsilon sends it elsewhere.

Sense-check: The sample average formula is working correctly. Each Q is the mean of all rewards received from that arm.

Recap: Reverse-engineering epsilon-greedy is a detective exercise. Look at the Q values before each action. If a non-best arm is chosen, it's certainly epsilon. If the best arm is chosen, it's maybe epsilon. You can never prove "certainly greedy."

Bridge: Next we tackle how to handle non-stationarity — when the reward distributions change over time — using a constant step size instead of sample averaging.

Real-world connection: This kind of analysis is used in A/B testing forensics. When a company runs an epsilon-greedy ad campaign and later reviews the logs, analysts can identify which ad impressions were exploration (random) vs. exploitation (best-known). This helps estimate the true cost of exploration and validate that the algorithm is working correctly.

3.4 Handling Non-Stationarity: Constant Step Size

Symbol registry — Section 3.4:

$Q_{n}$ — action value estimate after $n$ updates — scalar
$Q_{n + 1}$ — updated action value estimate — scalar
$R_{n}$ — reward received at step $n$ — scalar
$n$ — number of times the action has been selected — integer
$α$ (alpha) — constant step size — scalar in $(0, 1]$
$\frac{1}{n}$ — decreasing step size (sample average) — scalar

Hook: You've been tracking your favorite restaurant's quality for a year. Your average rating is 7.5. Yesterday you had a terrible meal — rating 2. Should that one bad meal barely move your average, or should it shake your confidence?

3.4.1 The Problem with Sample Averaging

Analogy — the 50-year-old learner: Imagine two 50-year-olds at a company. One says, "I'm 50. My ability to learn is going down. I have a four-year study plan — slow and steady." The other says, "Age is just a number. I keep learning. I'm better than my juniors."

Sample averaging is the first person. Constant step size is the second.

Why sample averaging fails in non-stationary environments:

The sample average update uses step size $1/ n$ , where $n$ is the number of times the action has been selected. As $n$ grows, the step size shrinks toward zero.

At step 1000 with current estimate $Q = 30$ , a new reward of 5 gives:

$Q_{1001} = 30 + \frac{1}{1000} (5 - 30) = 30 + 0.025 = 30.025$

The new reward barely moves the estimate. At step 10,000, the update would be $1/10, 000$ of the difference — negligible.

The problem: If the true value has shifted (non-stationarity), the agent needs to respond to new data. But sample averaging gives old data equal weight to new data. The agent adapts too slowly.

3.4.2 Rewriting the Incremental Update Formula

Derivation — from sample average to incremental update:

The sample average after $n$ rewards is:

$Q_{n} = \frac{R _{1} + R _{2} + \dots + R _{n - 1}}{n - 1}$

We can split the sum for $Q_{n + 1}$ :

$Q_{n + 1} = \frac{1}{n} i = 1 \sum n R_{i} = \frac{1}{n} (R_{n} + i = 1 \sum n - 1 R_{i}) = \frac{1}{n} (R_{n} + (n - 1) \cdot \frac{1}{n - 1} i = 1 \sum n - 1 R_{i}) = \frac{1}{n} (R_{n} + (n - 1) Q_{n}) = \frac{1}{n} (R_{n} + n Q_{n} - Q_{n}) = Q_{n} + \frac{1}{n} [R_{n} - Q_{n}]$

Incremental update formula:

$Q_{n + 1} = Q_{n} + \frac{1}{n} [R_{n} - Q_{n}]$

where:

$Q_{n + 1}$ — new action value estimate (scalar)
$Q_{n}$ — old action value estimate (scalar)
$R_{n}$ — reward received at time step $n$ (scalar)
$n$ — number of times this action has been selected (integer)
$1/ n$ — step size (scalar, decreases with $n$ )

Key insight: We don't need to store all past rewards. Just keep $Q_{n}$ and $n$ , and update with each new reward. This is $O (1)$ memory and $O (1)$ computation per step.

3.4.3 Numerical Example of Incremental Update

Worked example:

Given: $Q_{n} = 10$ , $R_{n} = 5$ , $n = 5$ .

Step 1: Compute the correction factor.

$R_{n} - Q_{n} = 5 - 10 = - 5$

Step 2: Multiply by step size.

$\frac{1}{n} (R_{n} - Q_{n}) = \frac{1}{5} (- 5) = - 1$

Step 3: Update the estimate.

$Q_{n + 1} = 10 + (- 1) = 9$

Sense-check: The current average is 10. The new reward (5) is below the average. So the average should decrease — and it does, from 10 to 9.

Step-Size Shrinking Illustration (Receiving Identical Rewards):

Suppose the current estimate for an action is $Q_{4} = 3.0$ , and the next observed reward is $R_{4} = 7.0$ . Since this is the 4th reward for this action, the sample-average step size is $1/4$ :

$Q_{5} = 3.0 + \frac{1}{4} (7.0 - 3.0) = 3.0 + 1.0 = 4.0$

Suppose the same reward target $7.0$ is observed again at step 5. The step size shrinks to $1/5$ :

$Q_{6} = 4.0 + \frac{1}{5} (7.0 - 4.0) = 4.0 + 0.6 = 4.6$

And if $7.0$ is observed again at step 6, the step size shrinks to $1/6$ :

$Q_{7} = 4.6 + \frac{1}{6} (7.0 - 4.6) = 4.6 + 0.4 = 5.0$

Observation: The estimate moves toward the target $7.0$ , but each successive correction becomes smaller because the step-size $1/ n$ diminishes as count $n$ increases.

3.4.4 General Update Form

The general update rule — a pattern you'll see throughout RL:

$NewEstimate \leftarrow OldEstimate + StepSize \times [Target - OldEstimate]$

where:

NewEstimate — the updated $Q$ value (scalar)
OldEstimate — the previous $Q$ value (scalar)
StepSize — $α$ or $1/ n$ , learning rate, in $(0, 1]$ (scalar)
Target — the reward signal $R_{n}$ (scalar)

The term $[Target - OldEstimate]$ is the error — how far the old estimate is from the new observation. The step size controls how much we move toward the target.

This pattern appears in Q-learning, SARSA, TD learning, and many other RL algorithms. Learn it now; you'll use it everywhere.

Don't confuse "target" with "correct answer": In supervised learning, the target is fixed (the true label). In bandits and RL, the target is a noisy reward — it changes with every pull. The professor warns: "Target is a term everyone confuses because we are actually going to use the term target left, right, center going forward in complex algorithms."

3.4.5 Constant Step Size for Non-Stationarity

The fix: Replace $1/ n$ with a constant $α \in (0, 1]$ , e.g., $α = 0.1$ .

The professor's comparison: at step 1000, $1/ n = 0.001$ (barely listens to new data). With $α = 0.1$ , the agent always gives new rewards "due importance" — 10% weight to the new reward, 90% to the old estimate.

Constant step size update rule:

$Q_{n + 1} = Q_{n} + α [R_{n} - Q_{n}]$

where $α \in (0, 1]$ is a fixed constant (e.g., 0.1, 0.2).

Why this works for non-stationarity: The weight on old data decays exponentially. Expanding the recursion:

$Q_{n + 1} = Q_{n} + α [R_{n} - Q_{n}] = α R_{n} + (1 - α) Q_{n} = α R_{n} + (1 - α) [α R_{n - 1} + (1 - α) Q_{n - 1}] = α R_{n} + α (1 - α) R_{n - 1} + (1 - α)^{2} Q_{n - 1} = (1 - α)^{n} Q_{1} + i = 1 \sum n α (1 - α)^{n - i} R_{i}$

The weight on reward $R_{i}$ is $α (1 - α)^{n - i}$ . Recent rewards get higher weight; old rewards decay exponentially with factor $(1 - α)$ . This is called an exponential recency-weighted average.

Worked example — constant vs. decreasing step size:

Current estimate: $Q = 10$ . New reward: $R = 5$ .

Step size	Update	New $Q$	Weight on new reward
$1/ n = 1/1000$	$10 + 0.001 (5 - 10)$	10.005	0.1%
$α = 0.1$	$10 + 0.1 (5 - 10)$	9.5	10%
$α = 0.5$	$10 + 0.5 (5 - 10)$	7.5	50%

With sample averaging ( $1/ n$ ), the update is tiny. With constant $α$ , the update is significant. The agent "hears" the new reward.

Sense-check: In a non-stationary environment, the new reward is more informative than old rewards. A higher step size lets the agent respond to changes faster.

Worked example — Simple Tracking Illustration ( $α = 0.2$ ):

Case 1: Reward level increases (Improvement).

Current estimate $Q = 10$ , step size $α = 0.2$ . The next two observed rewards are $14$ and $16$ :

$Q \leftarrow 10 + 0.2 (14 - 10) = 10 + 0.8 = 10.8$

$Q \leftarrow 10.8 + 0.2 (16 - 10.8) = 10.8 + 1.04 = 11.84$

The estimate steadily moves upward as the action's payout distribution improves.

Case 2: Reward level decreases (Degradation).

Current estimate $Q = 12$ , step size $α = 0.2$ . The next two observed rewards drop to $8$ and $7$ :

$Q \leftarrow 12 + 0.2 (8 - 12) = 12 - 0.8 = 11.2$

$Q \leftarrow 11.2 + 0.2 (7 - 11.2) = 11.2 - 0.84 = 10.36$

The estimate adjusts downward, ensuring older high rewards do not dominate current performance estimates forever.

Convergence tradeoff: With constant $α$ , the estimate never fully converges — it keeps fluctuating around the true value. This is by design in non-stationary environments: you want the estimate to keep adapting. The textbook's convergence conditions ( $\sum α_{n} = \infty$ , $\sum α_{n}^{2} < \infty$ ) are met by $1/ n$ but not by constant $α$ . This means constant $α$ won't converge to the true value — but in a non-stationary world, the true value itself is moving, so convergence to a fixed point isn't the goal.

3.4.6 Student Q&A on Step Size

Q: $R_{n} - Q_{n}$ is an error term. How are we making sure that in the next iteration we are reducing the error?

A: Don't think of $Target - OldEstimate$ as an error to minimize. In supervised learning, the target is the correct answer — fixed. Here, the target is a new reward each time. Even if you keep pulling the same arm, you get different rewards. Sometimes you get a jackpot, sometimes you get penalized for the same action. Your objective is not to minimize error — it's to track the true expected value as it changes. As the target moves, you keep your $Q$ value updated to reflect the rewards you're actually getting.

Q: If $α$ is constant, won't the first reward get undue privilege? For example, I pull arm 1 and get reward 10. The true average is around 2–3. Now $Q = 10$ , and every future update uses weight 0.2. The first outcome dominates.

A: This is a real concern, but it's philosophical. Two ways to think about it:

Initialization caution: Start with conservative initial values (e.g., 0) rather than using the first reward as the starting point.
Alpha decay: Start with a higher $α$ and gradually reduce it to a lower constant. This lets early estimates settle quickly, then maintains adaptability.

The professor's analogy: "When you join my team, I want to be careful about giving you credit or blame initially. With time, this will settle."

Recap: Sample averaging ( $1/ n$ ) converges but adapts too slowly for non-stationary problems. Constant step size ( $α$ ) maintains responsiveness to recent rewards via exponential recency weighting. The general update rule — $NewEstimate \leftarrow OldEstimate + StepSize [Target - OldEstimate]$ — is a pattern you'll use throughout RL.

Bridge: Next we put it all together: the modified epsilon-greedy algorithm with incremental updates and constant step size.

Real-world connection: The constant step size approach is used in adaptive control systems, real-time pricing algorithms, and online recommendation engines. Any system that needs to track changing preferences — stock trading bots, dynamic pricing on e-commerce sites, adaptive difficulty in games — uses some form of recency-weighted averaging.

3.5 Modified Epsilon-Greedy Algorithm

Symbol registry — Section 3.5:

$Q (a)$ — estimated value of action $a$ — scalar
$N (a)$ — number of times action $a$ has been selected — integer
$ϵ$ — exploration rate — scalar in $(0, 1)$
$α$ — step size (learning rate) — scalar in $(0, 1]$
$R$ — reward received — scalar
$A$ — selected action — integer

Hook: We've learned the pieces — epsilon-greedy for action selection, incremental updates for efficiency, constant step size for non-stationarity. Now let's assemble them into one complete algorithm.

3.5.1 Algorithm Steps

Purpose: This algorithm combines epsilon-greedy action selection with incremental value updates. It works in both stationary (step size = $1/ n$ ) and non-stationary (step size = $α$ ) environments.

Inputs:

$K$ — number of arms (integer)
$ϵ$ — exploration rate, in $(0, 1)$ (scalar)
$α$ — step size: either constant (e.g., 0.1) or $1/ n$ (scalar)

Outputs:

Action selection at each time step
Updated value estimates $Q (a)$ for all actions

The complete algorithm — step by step:

Initialize: For each action $a = 1, \dots, K$ :

$Q (a) \leftarrow 0$ (initial value estimate)
$N (a) \leftarrow 0$ (selection count)

Loop forever (each time step $t = 1, 2, 3, \dots$ ):

Select action using epsilon-greedy:
- With probability $ϵ$ : pick a random action (exploration)
- With probability $1 - ϵ$ : pick $A = ar g max_{a} Q (a)$ (exploitation)
Execute action $A$ and observe reward $R$
Update count: $N (A) \leftarrow N (A) + 1$
Update value:
$Q (A) \leftarrow Q (A) + α [R - Q (A)]$

where $α$ is either:

$1/ N (A)$ for stationary environments (sample average)
A constant (e.g., 0.1) for non-stationary environments

Trace — running the algorithm on a tiny example:

K = 3 arms, $ϵ = 0.1$ , $α = 0.2$ (constant step size).

Step	Coin flip	Action	Reward	$Q (A 1)$	$Q (A 3)$	$N (A 1)$	$N (A 3)$
0	—	—	—	0	0	0	0
1	exploit	A1 (tiebreak)	3	0.6	0	1	0
2	explore	A3	1	0.6	0.2	1	1
3	exploit	A1	2	0.68	0.2	2	1
4	exploit	A1	4	1.34	0.2	3	1

Step 1: Exploit — all Q values tied at 0, picks A1 (random tiebreak). Gets reward 3. Updates: $Q (A 1) = 0 + 0.2 (3 - 0) = 0.6$ .

Step 2: Explore — random pick lands on A3. Gets reward 1. Updates: $Q (A 3) = 0 + 0.2 (1 - 0) = 0.2$ .

Step 3: Exploit — A1 has highest Q (0.6). Gets reward 2. Updates: $Q (A 1) = 0.6 + 0.2 (2 - 0.6) = 0.6 + 0.28 = 0.88$ .

Wait — let me recompute. $Q (A 1) = 0.6 + 0.2 \times (2 - 0.6) = 0.6 + 0.28 = 0.88$ .

Step 4: Exploit — A1 still highest (0.88). Gets reward 4. Updates: $Q (A 1) = 0.88 + 0.2 (4 - 0.88) = 0.88 + 0.624 = 1.504$ .

Sense-check: A1 keeps getting pulled because it has the highest estimate. The constant step size ( $α = 0.2$ ) means each new reward moves the estimate by 20% of the gap.

Choosing $α$ vs. $1/ n$ :

Use $1/ n$ when the environment is stationary. The estimate converges to the true value.
Use constant $α$ when the environment is non-stationary. The estimate tracks changes but never fully converges.
If unsure, use constant $α$ — most real-world environments have some non-stationarity.

Common pitfall: Forgetting to update $N (A)$ before computing the step size. If using $1/ n$ , the step size is $1/ N (A)$ after incrementing. This matters at $N (A) = 0$ : the first update uses step size $1/1 = 1$ , which means the first reward replaces the initial estimate entirely.

Recap: The modified epsilon-greedy algorithm is simple: select with epsilon-greedy, update with the incremental rule. Choose step size based on whether the environment is stationary. This is the textbook's "simple bandit algorithm" — and it works surprisingly well.

Bridge: Next we explore a clever trick to encourage exploration without epsilon: optimistic initial values.

3.6 Optimistic Initial Values

Symbol registry — Section 3.6:

$Q_{0}$ — initial value estimate (set above true values) — scalar
$Q (a)$ — estimated value of action $a$ — scalar
$α$ — step size — scalar in $(0, 1]$
$q^{*} (a)$ — true expected reward for action $a$ — scalar

Hook: What if you could trick a greedy algorithm into exploring — without adding any randomness at all?

3.6.1 The Idea

Analogy — the overconfident new hire: Imagine a new employee who thinks they're amazing at everything. On their first day, they try every task confidently. After each task, they get honest feedback and adjust their self-assessment downward. By the end of the week, they've tried every task at least once and now have realistic estimates of their abilities.

Optimistic initial values work the same way: start with inflated estimates, and let reality bring them down. The agent explores naturally because every action looks "disappointing" compared to the initial optimism.

Optimistic initial values:

Instead of initializing all action values to 0, initialize them to a value higher than the true expected reward.

For example, if the true values are around 1, set $Q_{1} (a) = 5$ for all $a$ .

What happens:

All arms start with inflated estimates (e.g., $Q = 5$ ).
When you pull any arm, the reward is lower than 5 (say, reward = 1).
The update rule pulls the estimate down: $Q \leftarrow 5 + α (1 - 5) = 5 - 0.4 α$ .
Greedy selection keeps picking the arm with the highest $Q$ . But since all $Q$ values are above the true values, every arm looks "disappointing" — so the agent keeps switching to whichever arm hasn't been pulled down as far.
Eventually, all arms get explored enough that the estimates converge to the true values.

The key: the agent explores without any epsilon. Pure greedy exploration, driven by initial optimism.

Worked example:

K = 3 arms. True values: $q^{*} (A 1) = 1$ , $q^{*} (A 2) = 2$ , $q^{*} (A 3) = 1.5$ .

Initialize: $Q (a) = 5$ for all $a$ . Use greedy selection with $α = 0.1$ .

Step	Greedy choice	Reward	$Q (A 1)$	$Q (A 2)$	$Q (A 3)$
0	—	—	5.0	5.0	5.0
1	A1 (tiebreak)	1	4.6	5.0	5.0
2	A2 (highest)	2	4.6	4.7	5.0
3	A3 (highest)	1.5	4.6	4.7	4.65
4	A2 (highest)	2	4.6	4.43	4.65
5	A3 (highest)	1.5	4.6	4.43	4.415

Every arm gets explored because the initial values (5) are all above the true values. The agent is always "disappointed" and keeps trying different arms.

After many steps, all estimates converge to the true values: $Q (A 1) \to 1$ , $Q (A 2) \to 2$ , $Q (A 3) \to 1.5$ . Greedy then correctly exploits A2 forever.

3.6.2 How It Works

The mechanism:

Initialize all $Q (a)$ to a high value $Q_{0}$ (e.g., $Q_{0} = 5$ ).
True values are much lower (e.g., $q^{*} (a) \approx 1$ ).
Pull any arm — the reward is less than $Q_{0}$ .
Update: $Q (a) \leftarrow Q (a) + α [R - Q (a)]$ . Since $R < Q_{0}$ , the estimate moves downward.
Greedy picks the arm with the highest $Q$ . Since all $Q$ values are still above the true values, the agent keeps exploring.
As each arm's $Q$ slowly comes down to its true value, all arms get tried. Exploration happens naturally.

Why greedy works here: The agent never uses epsilon. It always picks the arm with the highest estimate. But because the estimates are inflated, the "highest" arm keeps changing as each arm's estimate drops. This creates automatic exploration.

3.6.3 Limitations

The exploration is temporary. Once all estimates have settled to their true values, the agent stops exploring. If the environment then changes (non-stationarity), the agent has no mechanism to re-explore.

The professor's warning: "If for example, after 1000 steps, the true value actually drifts a bit, this approach will fail miserably. It won't actually continue to explore forever."

When to use optimistic initial values:

Good for: Stationary environments where you want to force initial exploration without tuning $ϵ$ .
Bad for: Non-stationary environments. Once the estimates settle, there's no ongoing exploration pressure.
The textbook's verdict: "A simple trick that can be quite effective on stationary problems, but it is far from being a generally useful approach to encouraging exploration."

3.6.4 Test Bed Results

Test bed comparison (10-armed testbed):

Optimistic initial values ( $Q_{0} = 5$ , $ϵ = 0$ ): Quickly finds optimal actions. Early performance is worse (because it explores everything), but eventually outperforms.
Realistic initial values ( $Q_{0} = 0$ , $ϵ = 0.1$ ): More consistent from the start. Over time, catches up to the optimistic method.

The optimistic method's advantage: it explores thoroughly in the beginning, then settles into exploitation. The $ϵ = 0.1$ method explores consistently throughout but never as efficiently.

Pitfall: Don't use optimistic initial values with constant $α$ in non-stationary problems. The initial bias is permanent with constant $α$ (unlike sample averaging, where the bias disappears once all arms are tried). The textbook notes: "For methods with constant $α$ , the bias is permanent, though decreasing over time."

Recap: Optimistic initial values trick greedy algorithms into exploring by starting with inflated estimates. Reality brings the estimates down, and every arm gets tried. It's a neat trick for stationary problems, but fails in non-stationary settings because the exploration pressure is temporary.

Bridge: Next we look at UCB — a smarter exploration method that uses uncertainty estimates to decide which arm to try, without needing epsilon at all.

Real-world connection: Optimistic initialization is used in game tree search algorithms. In Monte Carlo Tree Search (MCTS), unvisited nodes are assigned high initial values to encourage exploration. This is similar to optimistic initial values — the algorithm explores new branches first, then refines estimates as it gathers data. AlphaGo's MCTS component uses a variant of this approach.

3.7 Upper Confidence Bound (UCB) Action Selection

Symbol registry — Section 3.7:

$Q_{t} (a)$ — estimated value of action $a$ at time $t$ — scalar
$N_{t} (a)$ — number of times action $a$ selected prior to time $t$ — integer
$t$ — total time steps — integer
$c$ — confidence level constant — scalar (typically 1 or 2)
$ln t$ — natural logarithm of $t$ — scalar
$A_{t}$ — action selected at time $t$ — integer

Hook: Epsilon-greedy explores randomly — it doesn't care which arm to explore. What if we could explore smartly, focusing on arms we're most uncertain about?

3.7.1 Motivation

The problem with epsilon-greedy: Epsilon forces exploration by a fixed random rate. Even when you've found the true best arm, epsilon still makes you explore random arms 10% of the time. And it doesn't distinguish between arms you've tried a lot (high confidence) and arms you've barely tried (low confidence).

The professor's critique: "Epsilon greedy forces by the parameter by the choice of epsilon, the choice of epsilon drives non-greedy action to be selected. The problem: even if the true values are actually obtained, epsilon still requires manual control."

The question: Can we explore deterministically — without randomness — by choosing arms based on how uncertain we are about them?

3.7.2 Intuition

Analogy — the underdog in class: There's a topper in the class who always gets picked for competitions. But there's also a quiet student who's only been tested once and scored well. Shouldn't we give the quiet student another chance? Maybe they're even better than the topper.

UCB is the teacher who says: "I'll pick students based on both their scores AND how many times I've tested them. Students tested fewer times get a bonus — they deserve another chance."

The two factors in UCB:

Consider four actions with their values and selection counts:

Action	Value $Q (a)$	Times Selected $N (a)$
A1	7	10
A2	9	30
A3	1	5
A4	20	15

Total time steps $t = 60$ .

The professor observes: "You think A3 deserves a little more attention because you've been treating him so unfairly. You've given only 5 opportunities. Whereas you chose A2 30 times already."

UCB balances two things:

How good the arm looks (the value $Q (a)$ )
How uncertain we are (how few times we've tried it)

An arm with a high value or high uncertainty gets a high score.

3.7.3 The UCB Formula

UCB action selection:

$A_{t} = ar g a max [Q_{t} (a) + c \frac{ln t}{N _{t} ( a )}]$

where:

$Q_{t} (a)$ — estimated value of action $a$ at time $t$ (scalar)
$N_{t} (a)$ — number of times action $a$ has been selected prior to time $t$ (integer)
$t$ — total number of time steps so far (integer)
$c$ — confidence level constant, typically $c = 1$ or $c = 2$ (scalar)
$ln t$ — natural logarithm of $t$
$\frac{l n t}{N _{t} ( a )}$ — the uncertainty measure

If $N_{t} (a) = 0$ (action never selected), treat it as a maximizing action — select it first.

How the uncertainty measure works:

When $N_{t} (a)$ is small (arm rarely tried), the uncertainty term is large → the arm gets a bonus.
When $N_{t} (a)$ is large (arm tried many times), the uncertainty term is small → the bonus shrinks.
As $t$ grows, $ln t$ grows — but slowly. This means the bonus increases over time, but at a decreasing rate.
The natural logarithm scales down the total time steps: $ln (1000) \approx 6.9$ , so even after 1000 steps, the uncertainty term is still manageable.

The professor explains why $ln$ : "You would run the problem, you would continue to learn forever. The time step $t$ will be forever. So you want to scale it down because you are trying to give an uncertainty measure."

The constant $c$ : Controls how much weight to give to uncertainty. Higher $c$ = more exploration. Typically $c = 1$ or $c = 2$ in experiments.

3.7.4 UCB Action Selection Process

Steps:

For each action $a$ , compute the UCB score:
$score (a) = Q_{t} (a) + c \frac{ln t}{N _{t} ( a )}$
Select the action with the highest score:
$A_{t} = ar g a max score (a)$

Why UCB explores intelligently: The professor explains: "If this quantity is higher, it means the corresponding action's value is an uncertain value. When the sum becomes higher, if the uncertainty is higher and the value is higher, it will be higher."

UCB naturally balances:

Arms with high value → selected for exploitation
Arms with high uncertainty → selected for exploration
Arms with both → selected most often

Over time, as all arms get tried enough, the uncertainty terms shrink and UCB converges to greedy exploitation of the true best arm.

UCB vs. epsilon-greedy: The professor notes: "In experiments, even without worrying about setting epsilon value throughout — epsilon value setting throughout and maintaining this value, increasing it, decreasing it, it has got its own effort. But UCB with some constant actually gives you a much higher value."

UCB's advantage: no random exploration parameter to tune. The exploration is deterministic — it always picks the arm with the highest upper confidence bound.

3.7.5 UCB Worked Example 1 (Two Actions with Value Update)

Setup:

2 actions: $a_{1}$ and $a_{2}$
Time step $t = 20$ , exploration parameter $c = 2$
Action 1: $Q_{t} (a_{1}) = 1.0$ , $N_{t} (a_{1}) = 10$
Action 2: $Q_{t} (a_{2}) = 0.8$ , $N_{t} (a_{2}) = 2$

Step 1: Compute UCB score for Action 1.

$score (a_{1}) = 1.0 + 2 \frac{ln 20}{10} \approx 1.0 + 2 \frac{2.9957}{10} = 1.0 + 2 (0.5473) = 1.0 + 1.095 = 2.095$

Step 2: Compute UCB score for Action 2.

$score (a_{2}) = 0.8 + 2 \frac{ln 20}{2} \approx 0.8 + 2 \frac{2.9957}{2} = 0.8 + 2 (1.2239) = 0.8 + 2.448 = 3.248$

Step 3: Action Selection & Value Update.

UCB selects action $a_{2}$ because $score (a_{2}) = 3.248 > 2.095 = score (a_{1})$ . The method chooses $a_{2}$ even though its value estimate (0.8) is lower than $a_{1}$ 's (1.0), because $a_{2}$ has been sampled far fewer times (2 vs 10).

Suppose the observed reward from selecting $a_{2}$ is $R = 1.4$ . The sample-average update for its 3rd selection is:

$Q (a_{2}) \leftarrow 0.8 + \frac{1}{3} (1.4 - 0.8) = 0.8 + \frac{1}{3} (0.6) = 1.0$

Key Insight: UCB selects actions using an uncertainty-aware score, while action values are still updated using the observed rewards.

3.7.6 UCB Worked Example 2 (Four Actions Selection)

Setup: Time step $t = 50$ , exploration parameter $c = 1$ , with 4 candidate actions:

Action	Estimate $Q_{t} (a)$	Count $N_{t} (a)$	Uncertainty $\frac{l n 50}{N _{t} ( a )}$	UCB Score $Q_{t} (a) + c \frac{l n 50}{N _{t} ( a )}$
$a_{1}$	1.10	25	$3.912/25 \approx 0.395$	$1.10 + 0.395 = 1.495 \approx 1.50$
$a_{2}$	1.20	20	$3.912/20 \approx 0.442$	$1.20 + 0.442 = 1.642 \approx 1.64$
$a_{3}$	0.70	4	$3.912/4 \approx 0.989$	$0.70 + 0.989 = 1.689 \approx 1.69$
$a_{4}$	0.90	1	$3.912/1 \approx 1.978$	$0.90 + 1.978 = 2.878 \approx 2.88$

Selection: UCB selects action $a_{4}$ (Score $\approx 2.88$ ).

Analysis: Although $a_{4}$ is not greedy according to $Q_{t} (a)$ alone ( $0.90 < 1.20$ ), it has been selected only once, so its uncertainty term is large ( $1.98$ ), boosting its score above all other actions.

3.7.7 UCB vs Epsilon-Greedy: Performance Comparison

Test bed results: On the 10-armed testbed, UCB generally outperforms epsilon-greedy, especially in the long run.

But there's an exception in the early phase (first 250 steps).

Q: In the initial iterations, before step 250, epsilon-greedy was higher and UCB is lower. Is there any specific reason?

A: In the early steps, there aren't enough data points to distinguish good arms from bad ones. All arms have similar uncertainty. UCB's uncertainty terms are all roughly equal, so it just picks the arm with the highest current value — essentially greedy with no real exploration benefit.

Epsilon-greedy, meanwhile, forces random exploration from the start. This gives it an early advantage: it quickly finds which arms are good through random sampling.

After about 250 steps, UCB's intelligent exploration kicks in. It focuses on uncertain arms, refines estimates efficiently, and pulls ahead of epsilon-greedy.

Key insight: UCB is better in the long run, but epsilon-greedy can be better in the very early phase. In practice, this early phase is a small fraction of the total runtime.

When UCB struggles:

Non-stationary environments: UCB's uncertainty measure assumes the true values are fixed. If they change, the uncertainty estimates become stale. More complex methods are needed.
Large state spaces: UCB requires tracking $N_{t} (a)$ for every action. With many actions (e.g., continuous action spaces), this becomes impractical.
The textbook notes: "UCB often performs well, but is more difficult than epsilon-greedy to extend beyond bandits to the more general reinforcement learning settings."

Recap: UCB selects actions by maximizing $Q (a) + c ln t / N (a)$ . It balances exploitation (high $Q$ ) with exploration (high uncertainty). It's deterministic — no random $ϵ$ parameter — and generally outperforms epsilon-greedy after the initial phase.

Bridge: Next we briefly introduce policy-based approaches — learning action selection directly without estimating values — and then contextual bandits.

Real-world connection: UCB-style algorithms are used in recommendation systems (YouTube, Netflix) to balance showing popular content with exploring new content. In clinical trials, UCB-like methods help allocate patients to treatments that are both effective and under-studied. AlphaGo's Monte Carlo Tree Search uses a UCB-like formula to balance exploring new game states with exploiting known good moves.

3.8 Policy-Based Approaches & Gradient Bandits

Symbol registry — Section 3.8:

$H_{t} (a)$ — numerical preference for action $a$ at time step $t$ — scalar
$π_{t} (a)$ — probability of selecting action $a$ at time step $t$ — scalar in $[0, 1]$
$A_{t}$ — action selected at time step $t$ — integer
$R_{t}$ — reward received at time step $t$ — scalar
$R ˉ_{t}$ — average reward (baseline) up to time step $t$ — scalar
$α$ — step-size parameter — scalar in $(0, 1]$

Hook: So far we've estimated expected values $Q (a)$ and selected actions based on those estimates. What if we skip value estimation entirely and learn action selection probabilities directly?

3.8.1 Value-Based vs Policy-Based

Two roads diverge in RL: Think of choosing a restaurant. The value-based approach rates every restaurant with an estimated score $Q (a)$ , then picks the highest-rated one. The policy-based approach learns action selection probabilities directly — learning a preference distribution without assigning explicit monetary or score values to each restaurant.

Value-based approach:

Estimate the action value $Q (a)$ for each action.
Use estimated values to select actions (greedy, $ϵ$ -greedy, UCB).

Policy-based approach:

Learn a numerical preference $H (a)$ for each action directly.
Convert preferences to action probabilities via a softmax distribution $π (a)$ .
Select actions stochastically based on $π (a)$ .

3.8.2 Gradient Bandit Formulation

Preference Softmax Distribution:

A gradient bandit algorithm maintains a numerical preference $H_{t} (a)$ for each action $a$ . The preference is not an estimate of expected reward; it is a relative measure. Action selection probabilities are computed using a softmax (Gibbs) distribution:

$Pr {A_{t} = a} ≐ \frac{e ^{H_{t} (a)}}{\sum _{b = 1}^{k} e ^{H_{t} (b)}} ≐ π_{t} (a)$

Initially, all action preferences are equal (e.g., $H_{1} (a) = 0$ ), so all actions have equal probability $π_{1} (a) = 1/ k$ .

3.8.3 Preference Update Equations

Stochastic Gradient Ascent Update Rule:

After action $A_{t}$ is selected and reward $R_{t}$ is observed, action preferences are updated as follows:

For the selected action $A_{t}$ :

$H_{t + 1} (A_{t}) = H_{t} (A_{t}) + α (R_{t} - R ˉ_{t}) (1 - π_{t} (A_{t}))$

For all other actions $a \neq = A_{t}$ :

$H_{t + 1} (a) = H_{t} (a) - α (R_{t} - R ˉ_{t}) π_{t} (a)$

where $R ˉ_{t}$ is the reward baseline, typically the average of all rewards received up to time step $t$ :

$R ˉ_{t} = \frac{1}{t} i = 1 \sum t R_{i}$

Interpretation of the Baseline $R ˉ_{t}$ :

If $R_{t} > R ˉ_{t}$ (reward above baseline): preference $H_{t + 1} (A_{t})$ increases, and non-selected action preferences decrease.
If $R_{t} < R ˉ_{t}$ (reward below baseline): preference $H_{t + 1} (A_{t})$ decreases, and non-selected action preferences increase.

3.8.4 Worked Example 1: Reward Above Baseline

Setup: 3 actions $a_{1}, a_{2}, a_{3}$ . Initial preferences $H_{t} (a_{1}) = H_{t} (a_{2}) = H_{t} (a_{3}) = 0$ , so $π_{t} (a_{i}) = 1/3$ .

Parameters: step-size $α = 0.1$ , selected action $A_{t} = a_{2}$ , reward $R_{t} = 2.0$ , baseline $R ˉ_{t} = 1.0$ .

Calculation:

Reward baseline difference: $R_{t} - R ˉ_{t} = 2.0 - 1.0 = + 1.0$ .

Update for selected action $a_{2}$ :

$Δ H (a_{2}) = 0.1 \times (+ 1.0) \times (1 - \frac{1}{3}) = 0.1 \times 1.0 \times \frac{2}{3} \approx + 0.0667$

Update for unselected actions $a_{1}$ and $a_{3}$ :

$Δ H (a_{1}) = Δ H (a_{3}) = - 0.1 \times (+ 1.0) \times \frac{1}{3} \approx - 0.0333$

Outcome: $H_{t + 1} (a_{2}) = + 0.0667$ , $H_{t + 1} (a_{1}) = H_{t + 1} (a_{3}) = - 0.0333$ . Action $a_{2}$ becomes more likely to be selected in future steps because its reward exceeded the baseline.

3.8.5 Worked Example 2: Reward Below Baseline

Setup: 3 actions with current probabilities $π_{t} (a_{1}) = 0.5$ , $π_{t} (a_{2}) = 0.3$ , $π_{t} (a_{3}) = 0.2$ .

Parameters: $α = 0.1$ , selected action $A_{t} = a_{1}$ , reward $R_{t} = 0.4$ , baseline $R ˉ_{t} = 1.0$ .

Calculation:

Reward baseline difference: $R_{t} - R ˉ_{t} = 0.4 - 1.0 = - 0.6$ .

Update for selected action $a_{1}$ :

$Δ H (a_{1}) = 0.1 \times (- 0.6) \times (1 - 0.5) = - 0.06 \times 0.5 = - 0.0300$

Update for unselected action $a_{2}$ :

$Δ H (a_{2}) = - 0.1 \times (- 0.6) \times 0.3 = + 0.06 \times 0.3 = + 0.0180$

Update for unselected action $a_{3}$ :

$Δ H (a_{3}) = - 0.1 \times (- 0.6) \times 0.2 = + 0.06 \times 0.2 = + 0.0120$

Outcome: Selected action $a_{1}$ 's preference drops because its reward was below average, while unselected actions $a_{2}$ and $a_{3}$ see their preferences increase.

Exam Note: Gradient bandits serve as a conceptual precursor to policy gradient methods (REINFORCE, Actor-Critic). While marked optional in intro bandit lectures, understanding how baseline subtraction drives stochastic policy updates is foundational for deep RL.

Recap: Value-based methods estimate action values and use them to select actions. Policy-based methods learn action selection probabilities directly. Gradient bandit algorithms adjust numerical preferences via baseline-subtracted reward signals.

Bridge: Next we introduce contextual bandits — the middle ground between vanilla MAB and full RL.

3.9 Contextual Bandits

Hook: Vanilla MAB ignores context — it treats every pull as identical. But real decisions depend on situation. You pick an umbrella based on the weather, not a fixed rule. What happens when we add context to the bandit?

3.9.1 Associative vs Non-Associative Learning

Analogy — the weather and the umbrella: You decide whether to carry an umbrella every morning. In vanilla MAB, you'd just pick "umbrella" or "no umbrella" based on past rewards, ignoring the weather entirely. That's non-associative — no link between situation and action.

But you know better. You check the weather (the context) and decide accordingly. That's associative — you link the context (weather) to the action (umbrella).

Non-associative learning: No context or state. Action selection based only on estimated values. This is pure MAB.

Associative learning: Action selection depends on a context — some observed information about the current situation. Given context X, take action A; given context Y, take action B.

3.9.2 Contextual Bandit Definition

A contextual bandit is a middle ground between pure MAB and full RL:

Like MAB: each action affects only the immediate reward (no state transitions).
Like RL: there is a context (state) that influences which action is best.

The key distinction: In contextual bandits, the context does NOT change based on your action. You observe the context, take an action, get a reward, and the context for the next step is independent of your action.

The professor's examples:

Weather and umbrella: You decide based on weather. Taking an umbrella does not change the weather.
Epidemic treatment: You treat a patient based on their symptoms. Treating one patient does not change the symptoms of the next patient.

3.9.3 Contextual Bandit vs Full RL

The critical difference — does the action change the state?

Feature	Pure MAB	Contextual Bandit	Full RL
Context/State	None	Yes	Yes
Action affects state?	N/A	No	Yes
Associative?	No	Yes	Yes
Example	Slot machine	Weather + umbrella	Driving a car

The professor's battery example — why this distinction matters:

"You're driving a car with a battery. When the battery level is low, your choice of actions will be different. When the battery level is high, your choice of actions will be different. Your choice of actions will affect the battery level as well. You see the cycle completely? That is what full Reinforcement Learning is all about."

In a contextual bandit, the context (battery level) is observed but not affected by your actions. In full RL, your actions change the state (draining the battery), which affects future decisions. This feedback loop is what makes full RL fundamentally harder.

3.9.4 Real-World Formulations & Application Matrix

Comprehensive Matrix of Contextual Bandit Applications:

Application Domain	Observed Context $x_{t}$	Candidate Actions $A_{t}$	Reward Signal & Contextual Rationale
Online Advertising	User profile, device type, query, page type, time of day	Candidate advertisements	Click, purchase, or revenue signal. Optimal ad depends on observed user/page context, but serving an ad does not change the user's demographic profile.
News / Content Recommendation	User interests, recent browsing history, location, session features	Articles, videos, or posts	Click, dwell time, or completion. Different users require different recommendations, but serving an article does not immediately change permanent user context.
Clinical Decision Support	Patient record, symptoms, history, age, risk indicators	Candidate treatments or interventions	Recovery indicator or improvement score. Treatment choice depends on patient-specific context (in a one-shot evaluation setting).
Information Retrieval	Search query, intent features, previous interaction signals	Ranking policy or selected result group	Click satisfaction or relevance signal. Useful ranking depends on query and intent context.
Adaptive Tutoring	Learner profile, recent answers, estimated mastery level	Next exercise, hint, or explanation type	Correctness or learning gain. Best instructional choice depends on student's current mastery level context.

Worked example — online advertising as contextual bandit:

Context: User profile, device type, search query, page type, time of day
Action: Which ad to show
Reward: User clicks (1) or doesn't (0)
Key: Showing an ad does not change the user's profile, device, query, page type, or time of day. The context for the next user is independent of what ad you showed.

This is a contextual bandit: context influences which ad is best, but actions don't change the context.

Worked example — clinical decision support:

Context: Patient's record, symptoms, history, age, risk indicators
Action: Suggest treatment
Reward: Patient outcome

The professor cautions: "This is a particular problem where you actually can look at it as a full RL problem. You want to continuously treat the patient. Or you were actually talking about looking at each patient and addressing his needs."

The modeling choice depends on the scenario:

If each patient is treated independently (no follow-up) → contextual bandit
If you continuously engage with the same patient over time → full RL (actions change the patient's state)

Scope — when to use contextual bandits:

Good fit: Online ads, news recommendation, search results, one-shot medical decisions. Context matters, but actions don't change the context.

Bad fit: Game playing, robot control, autonomous driving, long-term medical treatment. Here, actions change the state, creating a feedback loop that requires full RL.

The professor's warning: "These examples must be taken with a right state of understanding, blindly taking it and then it may not actually work." Don't assume a problem is a contextual bandit just because it has context — check whether actions affect the state.

Q: Can we use two agents — one for exploration and one for exploitation — sharing the same policy, applied to a contextual bandit problem?

A: No. Each agent needs its own exploration-exploitation balance. You can't split these roles across agents. This question leads into multi-agent RL (MARL), which is a separate topic. For now, treat each contextual bandit agent as a single entity that explores and exploits on its own.

Q: Is chess a contextual bandit or full RL?

A: Chess is full RL, not a contextual bandit. In chess, your move changes the board state, and the opponent's response changes it further. This action-state feedback loop is what defines full RL. In a contextual bandit, the context doesn't change based on your action — like the weather not changing because you carried an umbrella.

Recap: Contextual bandits add context to the MAB problem. The agent observes a context, takes an action, and gets a reward — but the context doesn't change based on the action. This is the bridge between pure MAB and full RL. The key question to ask: "Does my action change the state?" If yes, it's full RL. If no, it might be a contextual bandit.

Bridge: Next we address student questions about multi-agent RL and confirm that chess is a full RL problem.

Real-world connection: Contextual bandits power many modern systems. Spotify uses contextual bandits to recommend songs based on listening history and time of day. Google uses them for search result ranking. Clinical trials increasingly use contextual bandit designs to allocate patients to treatments based on their individual characteristics, improving outcomes while still learning which treatments work best.

3.10 Student Q&A: Multi-Agent RL

3.10.1 Multi-Agent Exploration Question

Q: Can we use two agents — one for exploration and one for exploitation — sharing the same policy document?

A: No. There's a misunderstanding. For any agent to learn effectively, it needs both exploration and exploitation. You can't split these roles across agents. If you have multiple agents, each agent must handle its own exploration-exploitation tradeoff.

The professor clarifies: "You're getting into a territory known as multi-agent RL (MARL), which is a special topic we will discuss. But right now, I want you to carry this: every agent which is involved, for its effective learning, exploration-exploitation tradeoff is mandatory."

Key takeaway: Exploration and exploitation are not separate functions to delegate — they are inseparable aspects of a single learning agent.

3.10.2 Chess as Full RL

Q: Playing chess is a full RL problem, right? Because once we move, the opponent will also move.

A: Yes. Chess is full RL because each action (your move) changes the state (the board position), which affects all future decisions. The opponent's response further changes the state. This creates the sequential decision-making loop that defines full RL.

Recap: Each agent needs its own exploration-exploitation balance — you can't split them. Chess is full RL because actions change the state.

3.10.3 Summary Matrix of Action-Selection Methods

Comparison of Action-Selection Methods:

Method	Action Selection Rule & Parameters	Exploration Behavior	Suitable Use Cases
Greedy	$A_{t} = ar g max_{a} Q_{t} (a)$ Parameter: None	Pure exploitation of current estimates. Zero explicit exploration.	Baseline benchmark only; can easily settle permanently on a suboptimal action after misleading early rewards.
$ϵ$ -Greedy	Select $ar g max_{a} Q_{t} (a)$ with probability $1 - ϵ$ ; select uniformly at random with probability $ϵ$ . Parameter: $ϵ \in (0, 1)$	Simple, continual uniform random exploration. Larger $ϵ$ explores more often and sacrifices immediate reward; smaller $ϵ$ exploits more.	Standard baseline when continuing exploration is necessary, especially effective in non-stationary environments with constant step-size.
Optimistic Initial Values	Set $Q_{1} (a)$ artificially high for all actions, then select greedily. Parameter: Initial value $Q_{1} (a) ≫ q^{} (a)$*	Encourages intense early exploration because untried actions remain attractive relative to disappointed tried actions.	Stationary problems where an initial burst of exploration is sufficient. Ineffective in non-stationary settings once estimates settle.
Upper Confidence Bound (UCB)	$A_{t} = ar g max_{a} [Q_{t} (a) + c \frac{l n t}{N _{t} ( a )}]$ Parameter: $c > 0$	Deterministic, directed exploration balancing value estimates with uncertainty bonuses. Favors actions that look good or are under-sampled.	Stationary bandit problems with meaningful action counts. Outperforms $ϵ$ -greedy after initial samples, but less direct to extend to full RL.
Gradient Bandits	Select action $a$ with probability $π_{t} (a) = \frac{e ^{H_{t} (a)}}{\sum _{b = 1}^{k} e ^{H_{t} (b)}}$ . Update preferences $H_{t} (a)$ using baseline $R ˉ_{t}$ . Parameter: Step-size $α > 0$	Stochastic policy-based exploration based on preference scale rather than value estimation.	Policy-based formulation suitable for learning action preferences directly; serves as conceptual foundation for Policy Gradients and Actor-Critic.

3.11 Review Questions & Comprehensive Solutions

The following 11 review questions distill the core concepts and calculations from this lecture note. Step-by-step solutions are provided for self-assessment and exam preparation.

Question 1: Define stationary and nonstationary reward distributions in a bandit problem. Give one example of each and explain why it fits the definition.

Solution:

Stationary Reward Distribution: A reward distribution is stationary if the probability distribution generating rewards for each action $a$ remains fixed over time, so the true action value $q^{*} (a)$ is constant. Example: A calibrated slot machine with a fixed payout mechanism — repeated plays allow sample averages $Q_{t} (a)$ to converge to fixed true values $q^{*} (a)$ .
Nonstationary Reward Distribution: A reward distribution is nonstationary if the payout distribution for one or more actions changes over time, meaning true values drift ( $q_{t}^{*} (a) \neq = q_{t^{'}}^{*} (a)$ ). Example: Online advertisement click-through rates during a holiday sale or breaking news event — user attention shifts, so older click rates no longer represent current ad performance.

Question 2: Starting from $Q_{n + 1} = \frac{1}{n} \sum_{i = 1}^{n} R_{i}$ , derive the incremental form $Q_{n + 1} = Q_{n} + \frac{1}{n} [R_{n} - Q_{n}]$ . Explain the role of the target and the estimation error.

Solution:

Step-by-step algebraic derivation:

$Q_{n + 1} = \frac{1}{n} i = 1 \sum n R_{i} = \frac{1}{n} (R_{n} + i = 1 \sum n - 1 R_{i}) = \frac{1}{n} (R_{n} + (n - 1) \frac{1}{n - 1} i = 1 \sum n - 1 R_{i}) = \frac{1}{n} (R_{n} + (n - 1) Q_{n}) = \frac{1}{n} (R_{n} + n Q_{n} - Q_{n}) = Q_{n} + \frac{1}{n} [R_{n} - Q_{n}]$

Target: $R_{n}$ is the newly observed reward signal.
Estimation Error: $[R_{n} - Q_{n}]$ represents the difference between the observed target and the previous estimate. Step-size $1/ n$ determines how far the estimate updates toward the target.

Question 3: An action has current estimate $Q = 5.0$ . The next reward is $R = 9.0$ . Compute the updated estimate using (a) sample-average step-size $1/ n$ with $n = 4$ , and (b) constant step-size $α = 0.25$ .

Solution:

(a) Sample-average update ( $n = 4$ ):
$Q_{new} = 5.0 + \frac{1}{4} (9.0 - 5.0) = 5.0 + \frac{1}{4} (4.0) = 5.0 + 1.0 = 6.0$ .
(b) Constant step-size ( $α = 0.25$ ):
$Q_{new} = 5.0 + 0.25 (9.0 - 5.0) = 5.0 + 0.25 (4.0) = 5.0 + 1.0 = 6.0$ .

Note: Since $1/ n = 1/4 = 0.25$ , both rules produce an identical update for this specific single step.

Question 4: For the same action, suppose $Q_{3} = 4.0$ and the next three rewards are $8, 8, 8$ . Compute three updates using sample-average step-sizes $1/3$ , $1/4$ , and $1/5$ . What happens to the size of the correction?

Solution:

Update 1 ( $n = 3, R_{3} = 8$ ): $Q_{4} = 4.0 + \frac{1}{3} (8 - 4.0) = 4.0 + 1.333 = 5.333$ (Correction size: $+ 1.333$ ).
Update 2 ( $n = 4, R_{4} = 8$ ): $Q_{5} = 5.333 + \frac{1}{4} (8 - 5.333) = 5.333 + 0.667 = 6.000$ (Correction size: $+ 0.667$ ).
Update 3 ( $n = 5, R_{5} = 8$ ): $Q_{6} = 6.000 + \frac{1}{5} (8 - 6.000) = 6.000 + 0.400 = 6.400$ (Correction size: $+ 0.400$ ).

Observation: The correction size shrinks sequentially ( $+ 1.333 \to + 0.667 \to + 0.400$ ) as step-size $1/ n$ diminishes from $1/3$ to $1/5$ .

Question 5: Explain why a constant step-size is more suitable than a $1/ n$ step-size when reward distributions change over time.

Solution:

A $1/ n$ step-size decays toward zero as sample count grows, making the learner increasingly insensitive to recent rewards and unable to track changing true values $q_{t}^{*} (a)$ . A constant step-size $α$ assigns exponentially decaying weights $α (1 - α)^{n - i}$ to historical rewards, ensuring recent rewards retain significant influence so the agent adapts continuously to nonstationary shifts.

Question 6: Explain optimistic initial values. Why can they cause exploration even under greedy action selection? Why is this not a general exploration method?

Solution:

Concept: Initializing action values $Q_{1} (a)$ higher than expected true rewards (e.g. $Q_{1} (a) = 5$ when $q^{*} (a) \approx 1$ ).
Why greedy explores: Selecting any action yields a reward below its optimistic estimate, driving its $Q$ -value down. The greedy operator $ar g max_{a} Q (a)$ then automatically switches to remaining untried optimistic actions.
Limitation: Exploration pressure is temporary (an initial-condition effect). Once estimates settle down to realistic values, no ongoing exploration occurs, failing in nonstationary or changing environments.

Question 7: For $t = 40$ , $c = 2$ , and three actions with $(Q, N)$ values $(1.2, 20)$ , $(1.0, 5)$ , and $(0.8, 1)$ , compute the UCB score for each action and identify the selected action.

Solution:

Natural log term: $ln 40 \approx 3.6889$ .

Action 1 ( $Q = 1.2, N = 20$ ): $Score (1) = 1.2 + 2 \frac{3.6889}{20} = 1.2 + 2 0.1844 = 1.2 + 2 (0.4295) = 2.059$
Action 2 ( $Q = 1.0, N = 5$ ): $Score (2) = 1.0 + 2 \frac{3.6889}{5} = 1.0 + 2 0.7378 = 1.0 + 2 (0.8589) = 2.718$
Action 3 ( $Q = 0.8, N = 1$ ): $Score (3) = 0.8 + 2 \frac{3.6889}{1} = 0.8 + 2 (1.9206) = 0.8 + 3.841 = 4.641$

Selected Action: Action 3 is selected because it has the highest UCB score ( $4.641$ ), driven by its high uncertainty bonus ( $N = 1$ ).

Question 8: A streaming platform tests four recommendation widgets. User preference changes during a sports event. Should the learner use ordinary sample averages or a method with continuing responsiveness? Justify using the idea of stationarity.

Solution:

The environment is nonstationary because user preferences shift dynamically during the sports event ( $q_{t}^{*} (a)$ changes over time). Ordinary sample averages ( $1/ n$ ) give equal weight to old pre-event data, leading to stale estimates. The learner must use a method with continuing responsiveness (constant step-size $α$ with ongoing exploration $ϵ > 0$ ) to track shifting user preferences.

Question 9: A hospital decision-support system observes patient age, symptoms, and risk level before recommending one of several treatment options, and receives an outcome score later. Is this an ordinary bandit, contextual bandit, or full reinforcement learning problem under a one-step formulation? Justify.

Solution:

It is a contextual bandit problem under a one-step formulation. The system observes side information/context (age, symptoms, risk level) prior to action selection, determining which treatment is best. However, recommending a treatment to one patient does not change the state or symptoms of future patients (no state transition feedback loop).

Question 10: A website can choose one of five homepage banners without observing any user-specific features. It receives reward 1 for sign-up and 0 otherwise. Model this as a bandit problem by identifying arms, rewards, and the missing feedback.

Solution:

Arms (Actions): The 5 homepage banner options ( $K = 5$ ).
Rewards: Binary reward $R \in {0, 1}$ (1 for sign-up, 0 otherwise).
Missing Feedback: Partial/Bandit feedback — the system only observes whether the user signed up for the displayed banner; it receives no feedback on how the user would have responded to the remaining 4 undisplayed banners (counterfactual unobserved rewards).

Question 11 (Optional): In a gradient bandit algorithm with two actions, suppose $π_{t} (a_{1}) = 0.7$ , $π_{t} (a_{2}) = 0.3$ , $A_{t} = a_{1}$ , $R_{t} = 0.5$ , $R ˉ_{t} = 1.0$ , and $α = 0.1$ . Compute the preference updates for both actions.

Solution:

Reward baseline difference: $R_{t} - R ˉ_{t} = 0.5 - 1.0 = - 0.5$ .

Selected Action $a_{1}$ :
$Δ H (a_{1}) = α (R_{t} - R ˉ_{t}) (1 - π_{t} (a_{1})) = 0.1 \times (- 0.5) \times (1 - 0.7) = - 0.05 \times 0.3 = - 0.015$
Unselected Action $a_{2}$ :
$Δ H (a_{2}) = - α (R_{t} - R ˉ_{t}) π_{t} (a_{2}) = - 0.1 \times (- 0.5) \times 0.3 = + 0.05 \times 0.3 = + 0.015$

Result: $H_{t + 1} (a_{1}) = H_{t} (a_{1}) - 0.015$ , $H_{t + 1} (a_{2}) = H_{t} (a_{2}) + 0.015$ . Because action $a_{1}$ scored below baseline, its preference dropped while alternative action $a_{2}$ 's preference increased by an equal and opposite amount.

3.12 Required Reading & References

Primary Required Reading:

Sutton, R. S., and Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). Cambridge, MA: MIT Press. Chapter 2, Sections 2.4 to 2.9 (pages 30–44).

Supplementary Survey Reference:

Bouneffouf, D., Rish, I., and Aggarwal, C. (2020). Survey on Applications of Multi-Armed and Contextual Bandits. 2020 IEEE Congress on Evolutionary Computation (CEC), 1–8. DOI: 10.1109/CEC48606.2020.9185542

Exam Guidance Summary

Action selection methods: Be able to analyze epsilon-greedy behavior step by step. Given a sequence of actions and rewards, determine when epsilon "certainly" occurred vs "maybe" occurred. Remember: "certainly epsilon" only when a non-best arm is chosen while a strictly better arm exists.
Non-stationarity handling: Understand why constant step size ( $α$ ) works for non-stationary environments. Know the incremental update formula $Q_{n + 1} = Q_{n} + α [R_{n} - Q_{n}]$ . Be able to compute updates with real numbers.
Optimistic initial values: Understand how it works (initialize Q above true values, let reality bring them down), its limitations (temporary exploration only — fails in non-stationary environments), and when it's appropriate (stationary environments).
UCB action selection: Know the formula $A_{t} = ar g max_{a} [Q_{t} (a) + c ln t / N_{t} (a)]$ . Understand the intuition behind the uncertainty measure. Be able to compute UCB scores for given actions and select the best.
Contextual bandits: Be able to distinguish between pure MAB (no context), contextual bandit (context exists, actions don't change state), and full RL (actions change state). Know concrete examples of each.
Policy-based approaches: Understand the conceptual difference between value-based (estimate Q, then select) and policy-based (learn selection directly). Details come later in the course.
Numerical problems: Practice computing action values, epsilon-greedy analysis, and UCB scores with given data. Expect step-by-step trace problems on the exam.

Key formulas to know:

Sample average: $Q_{n} (a) = \sum R_{i} / N (a)$
Incremental update: $Q_{n + 1} = Q_{n} + α [R_{n} - Q_{n}]$
UCB: $A_{t} = ar g max_{a} [Q_{t} (a) + c ln t / N_{t} (a)]$

Key Industry Applications

Online advertising: User attention changes over time, requiring non-stationary reward handling. Context includes user profile, device, query, page type, time of day. This is a contextual bandit: showing an ad doesn't change the user's context. Companies like Google and Facebook use bandit algorithms to balance showing the best-performing ad with testing new ads.
Clinical decision support: Patient records as context, treatment suggestions as actions. Can be modeled as a contextual bandit (one-shot treatment decisions) or full RL (continuous patient engagement). The modeling choice depends on whether treatment affects future patient state.
Adaptive tutoring: Student records and learning history as context, learning path suggestions as actions. A contextual bandit if each student interaction is independent; full RL if the system tracks progress over time.
Information retrieval: Query and user history as context, search results as actions. Presenting results doesn't change the query or user context — this is a contextual bandit. UCB-style algorithms help balance showing the most relevant results with exploring new content.
Game playing: UCB is used in modern game-playing AI. AlphaGo's Monte Carlo Tree Search uses a UCB-like formula to balance exploring new game states with exploiting known good moves. This extends UCB from bandits to full RL settings.
Manager behavior in industry: Non-stationary rewards — a manager's priorities change over time. The professor's example: what gets approved one month may not get approved the next. This requires continuous adaptation, similar to constant step size in non-stationary bandits.
AI adoption in industry: Slow adaptation is not viable when the environment changes rapidly. The professor warns against taking four-year study plans when AI is transforming workplaces in months. The lesson: keep epsilon > 0 and keep learning.

DRL Lecture 3 Notes · Multi-Armed Bandit: Advanced Topics

Deep Reinforcement Learning· postgraduate· 2026-07-18

Sections Breakdown

13.1 Review: MAB Fundamentals Recap

Recap of K-armed bandits, true value $q^*(a)$, estimates $Q(a)$, and the explore-exploit tradeoff.

23.2 Stationary vs Non-Stationary Rewards

Reward variance, drift, and real-world formulations across slot-machines, ads, medicine, and cloud infra.

33.3 Epsilon-Greedy: Worked Example

Reverse-engineering an epsilon-greedy log to detect certain vs possible exploration.

43.4 Handling Non-Stationarity: Constant Step Size

Incremental updates, sample-average decay, and constant step size alpha for tracking moving targets.

53.5 Modified Epsilon-Greedy Algorithm

Combining epsilon-greedy selection with incremental value updates for stationary and non-stationary settings.

63.6 Optimistic Initial Values

Forcing exploration without epsilon by initializing estimates above the true values.

73.7 Upper Confidence Bound (UCB) Action Selection

Deterministic exploration that balances value with an uncertainty bonus.

83.8 Policy-Based Approaches & Gradient Bandits

Learning action preferences H(a) directly, softmax distributions, and stochastic gradient updates.

93.9 Contextual Bandits

Adding context to bandit problems and distinguishing them from full RL.

103.10 Student Q&A & Action-Selection Summary

Multi-agent RL, chess as full RL, and a unified action-selection summary matrix.

113.11 Review Questions & Comprehensive Solutions

11 detailed exam-style review questions with complete step-by-step mathematical solutions.

Postgraduate students studying Deep Reinforcement Learning

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Multi-Armed Bandit Fundamentals

Must-know: A K-armed bandit has K actions, each with a hidden true value $q^{*} (a)$ . You estimate $Q (a)$ from the rewards you have seen. The whole problem is the tension between exploring (trying uncertain arms) and exploiting (picking the best-known arm). Vanilla MAB has no state — the best action never changes on its own.

$Q_{n} (a) = \frac{R _{1} + R _{2} + \dots + R _{N (a)}}{N ( a )}$

Top pitfall: Confusing your estimate $Q (a)$ with the true value $q^{*} (a)$ . A single lucky pull can make a rarely-tried arm look best, so always check how many times an arm was pulled.

Self-check: Why can't vanilla MAB drive a car?

Connects to: Epsilon-Greedy Action Selection, Sample-Average Estimation, Contextual Bandits.

Stationary vs Non-Stationary Rewards

Must-know: Stationary means the true value $q^{*} (a)$ is fixed; non-stationary means it drifts over time. Sample averaging gives equal weight to old and new data, so it silently breaks once the best arm moves.

$q_{t}^{*} (a) \neq = q_{t^{'}}^{*} (a) for some t \neq = t^{'}$

Top pitfall: Assuming zero variance on paper means zero variance in practice. Real systems always carry hidden measurement noise and drift, so pure greedy can lock onto the wrong arm.

Self-check: Why does sample averaging fail when the best arm changes over time?

Connects to: Constant Step Size, Epsilon-Greedy Action Selection.

Epsilon-Greedy: Reverse Engineering

Must-know: You can say 'certainly epsilon' only when a non-best arm is chosen while a strictly better arm exists. The coin flip happens before the agent looks at Q values, so a non-best pick is strong proof of exploration. You can never prove 'certainly greedy'.

$A_{t} = ar g a max Q_{t} (a) (greedy); with prob. ϵ pick a random arm$

Top pitfall: Calling 'maybe epsilon' 'probably epsilon'. At a tie or a best-arm pick you simply cannot tell which mechanism fired.

Self-check: In a behaviour log, on which time steps can you be sure epsilon was used?

Connects to: Epsilon-Greedy Action Selection, Sample-Average Estimation.

Incremental Update & Constant Step Size

Must-know: The general update is NewEstimate <- OldEstimate + StepSize x (Target - OldEstimate). A constant step size alpha gives exponential recency-weighted averaging, so new rewards keep moving the estimate — exactly what non-stationarity needs.

$Q_{n + 1} = Q_{n} + α [R_{n} - Q_{n}]$

Top pitfall: Forgetting to increment N(A) before computing 1/N(A). The first update then uses step size 1/1 = 1, which throws away the initial estimate entirely.

Self-check: Why does constant alpha never fully converge to the true value?

Connects to: Sample-Average Estimation, Modified Epsilon-Greedy Algorithm, Non-Stationary Rewards.

Modified Epsilon-Greedy Algorithm

Must-know: Combine epsilon-greedy selection with the incremental update. Use step size 1/n for stationary environments (it converges) and a constant alpha for non-stationary environments (it tracks). This is the textbook's simple bandit algorithm.

$Q (A) \leftarrow Q (A) + α [R - Q (A)]$

Top pitfall: Using constant alpha in a stationary problem wastes the convergence guarantee, or using 1/n in a non-stationary problem that adapts too slowly. Pick based on whether the environment drifts.

Self-check: When should you choose 1/n over a constant alpha?

Connects to: Epsilon-Greedy Action Selection, Constant Step Size.

Optimistic Initial Values

Must-know: Initialize Q(a) above the true values. Greedy then explores on its own, because every arm looks disappointing compared with the initial optimism. No epsilon is needed, but the exploration pressure is temporary.

$Q (a) \leftarrow Q (a) + α [R - Q (a)], Q_{0} (a) > q^{*} (a)$

Top pitfall: Using it in non-stationary settings — once estimates settle there is no ongoing exploration. With constant alpha the initial bias is permanent and never washes out.

Self-check: Why does optimistic initialization force exploration without any randomness?

Connects to: Epsilon-Greedy Action Selection, Constant Step Size.

Upper Confidence Bound (UCB)

Must-know: UCB picks the action that maximises Q_t(a) + c sqrt(ln t / N_t(a)). It balances value (exploit) with uncertainty (explore) deterministically — no random epsilon to tune. Arms tried less often get a bonus.

$A_{t} = ar g a max [Q_{t} (a) + c \frac{ln t}{N _{t} ( a )}]$

Top pitfall: Using UCB in non-stationary environments — its uncertainty measure assumes fixed true values. It also tracks N_t(a) for every action, which is hard to scale beyond bandits.

Self-check: Why does UCB favour the less-tried arm over the best-known one?

Connects to: Epsilon-Greedy Action Selection, Constant Step Size.

Policy-Based vs Value-Based Methods

Must-know: Value-based methods estimate Q(a) and then select from it. Policy-based methods learn the selection rule directly — for example, gradient bandits learn a preference H(a) per action. The detailed math is deferred to later chapters.

$π (a) = probability of selecting action a$

Top pitfall: Treating gradient bandits as exam-critical. The professor marks them optional; what matters now is the conceptual difference from value-based methods.

Self-check: What is the key difference between value-based and policy-based approaches?

Connects to: Value-Based Methods, Contextual Bandits.

Contextual Bandits

Must-know: A contextual bandit observes a context, picks an action, and gets a reward — but the context does NOT change because of the action. It is the middle ground between pure MAB and full RL.

$π (a ∣ x) = probability of action a given context x$

Top pitfall: Assuming a problem is a contextual bandit just because it has context. Always ask: does my action change the state? If yes, it is full RL, not a contextual bandit.

Self-check: Is chess a contextual bandit or full RL? Explain why.

Connects to: Full Reinforcement Learning, Value-Based Methods, Policy-Based Methods.

Multi-Agent RL and Full RL

Must-know: Each agent needs its own explore-exploit balance; you cannot split exploration and exploitation across two agents. Chess is full RL because every move changes the board state, creating a feedback loop that defines sequential decision making.

$s_{t + 1} = f (s_{t}, a_{t}) (action a_{t} changes state s_{t})$

Top pitfall: Thinking you can delegate exploration to one agent and exploitation to another. Exploration and exploitation are inseparable parts of a single learning agent.

Self-check: Why is chess full RL rather than a contextual bandit?

Connects to: Contextual Bandits, Epsilon-Greedy Action Selection.

Previous LectureLecture 02 · Elements of RL and Multi-Armed Bandits

Next LectureLecture 04 · Markov Decision Processes

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

Multi-Armed Bandit: Advanced Topics

3.1 Review: MAB Fundamentals Recap

3.1.1 Core Concepts Review

3.1.2 Action Value Methods

3.1.3 Action Selection Methods Review

3.2 Stationary vs Non-Stationary Rewards

3.2.1 Reward Variance Scenarios

3.2.2 Non-Stationary Rewards

3.2.3 Real-World Formulations: Stationary vs. Non-Stationary Settings

3.3 Epsilon-Greedy: Worked Example

3.3.1 Problem Setup

3.3.2 Step-by-Step Analysis

3.3.3 Key Takeaway

3.4 Handling Non-Stationarity: Constant Step Size

3.4.1 The Problem with Sample Averaging

3.4.2 Rewriting the Incremental Update Formula

3.4.3 Numerical Example of Incremental Update

3.4.4 General Update Form

3.4.5 Constant Step Size for Non-Stationarity

3.4.6 Student Q&A on Step Size

3.5 Modified Epsilon-Greedy Algorithm

3.5.1 Algorithm Steps

3.6 Optimistic Initial Values

3.6.1 The Idea

3.6.2 How It Works

3.6.3 Limitations

3.6.4 Test Bed Results

3.7 Upper Confidence Bound (UCB) Action Selection

3.7.1 Motivation

3.7.2 Intuition

3.7.3 The UCB Formula

3.7.4 UCB Action Selection Process

3.7.5 UCB Worked Example 1 (Two Actions with Value Update)

3.7.6 UCB Worked Example 2 (Four Actions Selection)

3.7.7 UCB vs Epsilon-Greedy: Performance Comparison

3.8 Policy-Based Approaches & Gradient Bandits

3.8.1 Value-Based vs Policy-Based

3.8.2 Gradient Bandit Formulation

3.8.3 Preference Update Equations

3.8.4 Worked Example 1: Reward Above Baseline

3.8.5 Worked Example 2: Reward Below Baseline

3.9 Contextual Bandits

3.9.1 Associative vs Non-Associative Learning

3.9.2 Contextual Bandit Definition

3.9.3 Contextual Bandit vs Full RL

3.9.4 Real-World Formulations & Application Matrix

3.10 Student Q&A: Multi-Agent RL

3.10.1 Multi-Agent Exploration Question

3.10.2 Chess as Full RL

3.10.3 Summary Matrix of Action-Selection Methods

3.11 Review Questions & Comprehensive Solutions

3.12 Required Reading & References

Exam Guidance Summary

Key Industry Applications

DRL Lecture 3 Notes · Multi-Armed Bandit: Advanced Topics

Sections Breakdown

Exam Revision Notes

Multi-Armed Bandit Fundamentals

Stationary vs Non-Stationary Rewards

Epsilon-Greedy: Reverse Engineering

Incremental Update & Constant Step Size

Modified Epsilon-Greedy Algorithm

Optimistic Initial Values

Upper Confidence Bound (UCB)

Policy-Based vs Value-Based Methods

Contextual Bandits

Multi-Agent RL and Full RL

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat