Deep Reinforcement Learning

Elements of RL and Multi-Armed Bandits

📅 Published: 2026-07-20

🎓 Level: postgraduate

👥 Audience: Postgraduate students in Deep Reinforcement Learning

Elements of RL and Multi-Armed Bandits

2.1 Recap of the Previous Class and the Agent-Environment Interface

2.1.1 Definition and Explanation

Hook: How do you learn to ride a bicycle without someone handing you a manual? You try, wobble, fall, adjust — and eventually ride. That trial-and-error loop is the beating heart of reinforcement learning.

Reinforcement learning is a learning paradigm that is different from both supervised and unsupervised learning, and it is the one that most closely matches the way humans actually learn — by trying things, seeing what works, and adjusting. The first class established this contrast and introduced the *agent-environment interface*, the loop at the centre of every RL problem.

Intuition: Think of the agent-environment interface like a conversation. The agent speaks "I'll do action

a

" and the environment replies with two pieces of information: "here's where you are now" (the new state

s^{'}

) and "here's how good that was" (the reward

r

). The agent cannot directly see everything about the world — only the state the environment chooses to report.

The interface works as follows. The *agent* is the learner and decision-maker. The *environment* is everything outside the agent that the agent interacts with. The *agent* acts on the environment through an *action*. The environment responds in two ways: it changes its internal situation and returns a new *state* telling the agent "this is how I look now", and it optionally returns a *reward*, a number telling the agent how good the just-completed action was. So the four elementary entities are agent, environment, action, and (state, reward) — the agent talks to the environment via actions and the environment talks back via states and rewards.

Formal summary: At each discrete time step

t

Agent observes state $s_{t}$ .
Agent selects action $a_{t}$ .
Environment transitions to a new internal situation and returns:

New state $s_{t + 1}$
Reward $r_{t + 1}$

This cycle repeats. The agent's goal is to maximise cumulative reward over time.

2.1.2 Symbol Registry

$s$ — state — $s$ — what the environment reports after an action; domain depends on problem
$a$ — action — $a$ — the agent's choice at a state
$r$ — reward — $r$ — a scalar the environment returns
$t$ — time step — $t \in N$ — discrete decision point

Scope: The state

s

reported to the agent is not necessarily everything the environment knows internally — it may be partial or noisy. This is a crucial distinction: the agent sees what the environment *tells* it, not necessarily the full reality.

2.1.3 The Five (or Six) Core Elements of RL

The five core elements of RL are:

Element	What it is	Example (tic-tac-toe)
Agent	The learner and decision-maker	Your program playing X
Environment	Everything outside the agent	The board + opponent + rules
Policy ( $π$ )	The agent's rule for choosing actions	"If board looks like this, play there"
Value function	How desirable each state is	Board score: 0.9 = likely win
Model (optional)	The agent's representation of how the environment works	"If I play here, opponent will probably do that"

A sixth element — the reward signal — is sometimes listed separately from the environment. The professor listed agent, environment, value function, policy, and (optionally) model.

The previous class discussed four of them but did not really develop the *model of the environment*; we cover that in section 2.3. The *value function* carries the notion of *long-term desirability of a state*: a high value state is one the agent is happy to be in, because from there it expects high future reward. In the tic-tac-toe example used previously, the value function was initialised to numbers and then iteratively updated and improved as the agent played.

Pitfall: Beginners often confuse "reward" with "value". Reward

r

is the immediate feedback from one action. Value

V (s)

is the *long-term* expected cumulative reward starting from state

s

. A state can have low immediate reward but high long-term value (e.g., sacrificing a chess piece to win later).

2.1.4 Intuition for the Value Number

If the agent is playing crosses in tic-tac-toe and the board is in a configuration from which five winning replies are possible, the value of that state might be $0.9$ . That is high (the cap is $1$ ), so the state represents a configuration from which the agent will likely win. The successor move with the highest value is the move the agent should pick. At any state the agent asks: "What are all the possible actions, which states do they lead to, and what is the value of each of those resulting states?" The best action is the one that takes the agent to the highest-value state. So *having good values is the most important job of an RL learner*. This is the single most important takeaway from the previous class.

Visual intuition: Imagine a topographic map where each cell (state) has an altitude (value). Gold is a tall peak (value 1.0), losing positions are valleys (value 0). The agent always walks uphill — climbing toward the peak. The value function is the altitude map; the policy is the rule "always step toward higher ground."

Worked example — tic-tac-toe value lookup:

Suppose the board has three possible successor states after X's move:

State A (play centre): value = 0.85
State B (play top-left): value = 0.60
State C (play bottom-right): value = 0.70

The greedy agent compares: $max (0.85, 0.60, 0.70) = 0.85$ , so it plays centre.

Sense-check: The centre cell in tic-tac-toe is indeed the strongest opening move — it participates in the most winning lines (4 out of 8: two diagonals, middle row, middle column), which aligns with the highest value.

Recap: The agent-environment interface is a loop: agent acts, environment responds with (state, reward). The five core elements are agent, environment, policy, value function, and (optionally) a model. *Good value estimates drive good decisions.* Next we unpack two flavours of the value function —

V (s)

and

Q (s, a)

— and why that distinction matters.

2.2 The Two Value Functions: State-Value $V (s)$ and Action-Value $Q (s, a)$

2.2.1 Why Two Flavours of Value

Hook: When you stand at a crossroads, do you ask "how good is it to be here?" or "how good is it to go left?" These are two different questions — and RL formalises both.

There are two types of value function. The *state-value function* $V (s)$ tells the agent how desirable it is to *be* in a given state, irrespective of which action it picks next. The *action-value function* $Q (s, a)$ tells the agent how desirable it is to *take a specific action* $a$ *in* a specific state $s$ . The convention is strict: when we write $V$ , we mean value of a *state*; when we write $Q$ , we mean value of a *state-action pair*.

Formal definitions:

The *state-value function* under policy $π$ is: $V^{π} (s) = E_{π} [k = 0 \sum \infty γ^{k} r_{t + k + 1} s_{t} = s]$ This is the expected cumulative discounted reward starting from state $s$ and following policy $π$ thereafter. Here $γ \in [0, 1]$ is the discount factor that trades off immediate vs. future reward.

The *action-value function* under policy $π$ is: $Q^{π} (s, a) = E_{π} [k = 0 \sum \infty γ^{k} r_{t + k + 1} s_{t} = s, a_{t} = a]$ Same idea, but conditioned on taking a specific action $a$ first, then following $π$ .

Notation note: In the MAB problem (sections 2.6–2.17), since there is no state, the state argument is dropped:

Q (a)

2.2.2 Symbol Registry

$V (s)$ — state-value function — scalar in some bounded range (here $[0, 1]$ for tic-tac-toe, larger for the grid below)
$Q (s, a)$ — action-value function — scalar denoting expected reward for doing $a$ in $s$
$s$ — current state; $s^{'}$ — next state
$a$ — action selected in $s$
$γ$ — discount factor — scalar in $[0, 1]$ — controls how much future rewards matter relative to immediate ones

2.2.3 Worked Example: 4×4 Grid World

Setup: Picture a 4×4 grid. Each cell is a state. One corner is the *gold* (the goal, value 100); a different cell is the *start* state. The agent is a coin that moves one cell at a time trying to reach gold.

We assign each state a number representing its desirability, for example (quick illustrative figures): start = 0, neighbour cells carried values of 1, 6, 7, 8, 9, 10, 20, and so on up to gold at 100. These are teaching numbers, not a learned solution.

Step-by-step greedy decision:

From the start state, the available actions are *up* (leading to a state with value 6) and *right* (leading to a state with value 9):

Look at up → successor value = 6
Look at right → successor value = 9
Compare: $9 > 6$
Pick *right*
Land in the value-9 cell, repeat the process with its neighbours.

What $V$ alone requires: To decide, the agent must look *one step ahead*: for each candidate action it must inspect the resulting state's value and then compare. That one-step look-ahead is small here, but in many problems it is not cheap. What $Q$ would provide instead: If we pre-compute

Q (start, up) = 6

and

Q (start, right) = 9

, the agent just reads the higher Q-value and picks immediately — no look-ahead needed.

2.2.4 The Simplification Q Provides

If instead of just $V (s)$ we attach a number to every *state-action pair* — say $Q (s, up) = 10$ and $Q (s, right) = 11$ — then the agent already knows, without any look-ahead, which action is better *from this state*. It can simply read off the Q-values and pick. The action-value function *summarises* the look-ahead into a single number attached to each arrow. In grid problems the saving is small; in problems where the outcome of an action is stochastic and produces several possible next states, the saving is large.

Scope: The convenience of

Q

over

V

depends on whether the environment is stochastic. In deterministic environments (like chess, where moving a piece uniquely determines the next board state),

V

with one-step look-ahead is perfectly fine and uses less storage (

∣ S ∣

values instead of

∣ S ∣ \times ∣ A ∣

). In stochastic environments,

Q

is strongly preferred because it pre-bakes the expectation.

2.2.5 The Braking-Car Analogy (Why Q Is Preferred)

Analogy: A *really* good example of when

V

becomes clumsy is driving a car. Suppose there is an action called *brake*. Its outcome is not deterministic: with probability 0.9 the car stops cleanly, with probability 0.07 it skids, and with probability 0.03 the brake fails.

If we only had $V$ , the agent would brake, observe the resulting state (stop / skid / fail), and only *then* see how valuable that state is. To choose an action intelligently *before* braking, the agent would need to enumerate all three possible next states, look up each resulting $V$ , and form an expectation.

If we instead teach the agent $Q (s, brake)$ directly, the agent already has a single expectation baked into that arrow — a weighted average of "stops (value 10), skids (value 3), fails (value $- 10$ )" with weights $0.9, 0.07, 0.03$ . The agent can simply compare the $Q$ -arrows of all available actions and pick the largest one without any further look-ahead.

Worked computation for the braking-car example:

$Q (s, brake) = 0.9 \times 10 + 0.07 \times 3 + 0.03 \times (- 10) = 9 + 0.21 - 0.3 = 8.91$

Suppose we also have:

$Q (s, accelerate) = 5$
$Q (s, turn) = 7$

Then $max (8.91, 5, 7) = 8.91$ — brake is the best action. No need to enumerate successor states.

Q: In the grid example, if we always take the greedy move, we could end up stuck in a cycle. Are we doing duplicate detection? Are the values fixed? A: The numbers shown are *initial*, not yet learned. The whole point of learning is to *update* those values so that following them leads to the goal. If you only ever look at the current table and navigate greedily, you learn nothing. You must explore — make some random moves — to discover where you actually go. The randomness breaks the cycle. So exploration-versus-exploitation is exactly what addresses your worry. A concrete discussion of that, called *epsilon-greedy*, is coming up later in this lecture.

The student was asked to hold the further question on exploration-exploitation until section 2.11, where epsilon-greedy is introduced.

Q: From the explanation, action-value functions seem to make more sense, because they consider the situation and the action together. What are the practical implications for using state-value functions at all? A: In many real problems the outcome of an action is *deterministic* — for example, in chess, if you move a piece from one square to another, you know the resulting state for certain, so a

V

-function with light look-ahead is perfectly adequate. Whenever an action's outcome is stochastic (like braking) and you must *observe* it to even know the next state,

V

becomes costly and you should use

Q

. So the choice is problem-specific.

Q: Is the goal always to reach the goal state with minimum cost? Is cost a factor? A: Problem-dependent. Rewards were not factored into the grid example purely — sometimes rewards are uniform (so the agent naturally wants to reach the goal as quickly as possible); sometimes there are intermediate rewards ("hidden gems") worth collecting, which changes the optimum. The strategy depends on the reward design, which you the problem designer control.

2.2.6 Intuition for V vs Q

Side-by-side contrast:

	$V (s)$	$Q (s, a)$
Tells you	"I would like to be here"	"I would like to do this here"
Requires look-ahead?	Yes — one step to compare successor values	No — value is pre-baked per action
Storage	One number per state: $∣ S ∣$	One number per (state, action) pair: $∣ S ∣ \times ∣ A ∣$
Best when	Deterministic outcomes	Stochastic outcomes
Industry usage	Used in some policy-evaluation settings	Dominates practical algorithms

Action values compress the one-step look-ahead into a single number per arrow, which is a real win when the look-ahead is wide or stochastic. Exam note: in textbook problems you will often be shown how to compute *both* $V$ and $Q$ ; in industry practice $Q$ is the one most algorithms actually use. Keep that distinction in mind.

Pitfall: Assuming

V (s)

and

Q (s, a)

are interchangeable. They serve different purposes.

V (s)

is needed for certain theoretical analyses and policy-gradient methods;

Q (s, a)

drives action selection directly. Knowing which one a given algorithm uses is essential.

Recap:

V (s)

asks "how good is it to be here?" while

Q (s, a)

asks "how good is it to do *this* here?"

Q

eliminates the one-step look-ahead and is preferred in stochastic environments. Both are central to RL; most practical algorithms (Q-learning, DQN) use

Q

. Next we introduce the *model of the environment* — the optional sixth element.

2.3 Model of the Environment

2.3.1 Definition and Explanation

Hook: If you could predict exactly what the world would do next — every state change, every reward — you would never need to "learn" by trial and error. You could plan perfectly on paper. The *model of the environment* is precisely that predictive blueprint.

A *model of the environment* is an abstract summary of the environment's behaviour — what it returns as the next state and reward for every possible (state, action) the agent might choose. If you know, for every state $s$ and action $a$ , the probability of observing a particular next state $s^{'}$ with a particular reward $r$ , then you have a complete model of the environment. Mathematically this means you can evaluate $p (s^{'}, r ∣ s, a)$ for any $(s, a)$ .

Formal definition: The environment model is the joint transition-reward probability distribution:

$p (s^{'}, r ∣ s, a) = Pr (s_{t + 1} = s^{'}, r_{t + 1} = r s_{t} = s, a_{t} = a)$

This is a conditional probability distribution over next states $s^{'}$ and rewards $r$ , given the current state $s$ and action $a$ . It satisfies: $s^{'} \in S \sum r \in R \sum p (s^{'}, r ∣ s, a) = 1 for all s \in S, a \in A (s)$

If the model is known, the environment is *fully characterised* — you can simulate it without ever interacting with it.

Notation note: The textbook (Sutton & Barto) uses this exact form

p (s^{'}, r ∣ s, a)

throughout. Some texts decompose it as

p (s^{'} ∣ s, a)

for transitions and

r (s, a)

r (s, a, s^{'})

for rewards; the joint form is more general.

2.3.2 Symbol Registry

$p (s^{'}, r ∣ s, a)$ — environment model — scalar in $[0, 1]$ — probability of landing in $s^{'}$ with reward $r$ given action $a$ was taken in state $s$
$s$ , $a$ , $s^{'}$ , $r$ — already defined in 2.1.2
$S$ — the set of all possible states
$A (s)$ — the set of actions available in state $s$

2.3.3 Why a Model Is Useful

Analogy: A model is like a GPS navigation app. Without a model, you'd have to drive every road to learn which routes are fastest. With a model (the map + traffic data), the GPS plans the optimal route *before* you start driving. In RL terms: the model lets you *plan* instead of purely *learn by doing*.

With a good model you no longer have to *estimate* values from interaction — you can compute *theoretically optimal* values using an algorithmic procedure (this will later be *dynamic programming*). The agent can plan extensively on paper before executing anything, much like an engineer or manager who exhaustively lists outcomes and probabilities before committing to a decision.

A model is not available for every problem. Real-world environments often defeat attempts to model them explicitly. But when a model exists (or can be learned), it is a powerful asset.

Scope: A model is useful when:

The state space is small enough to enumerate (tic-tac-toe, small grids).
The transition dynamics are known or can be learned from data.
The environment is stationary (the dynamics don't change over time).

A model becomes impractical when:

The state space is enormous (Go: $1 0^{170}$ board positions).
The dynamics are too complex to model accurately (real-world robotics).
The environment is non-stationary and the model would need constant updating.

2.3.4 Student Doubt: Is It Still RL If You Have a Model?

Q: If the environment is already modelled, do we still call this reinforcement learning? I know the probabilities that take me from state to goal already. A: Two clarifications. (1) Even in problems where modelling is theoretically possible — tic-tac-toe, chess — the state space is huge and an exhaustive computation of the optimal policy is impractical, so we still interact with the environment to learn a *policy* that is "good enough" in finite time, rather than carry out an exhaustive proof. So yes, RL is not defined by the absence of a model. (2) "Reinforcement learning" is the framing of a problem as a *Markov Decision Process* — state, action, reward, model (or not) — and *any* approach used to solve that MDP counts as a reinforcement-learning approach. It could be an exact algorithm like dynamic programming, or an approximate method like Q-learning. RL is the *problem class*, not one specific algorithm family.

We will discuss this distinction at length later. For now, the takeaway is: a model is a fancy thing useful for toy problems, and even when you have one you may not want to use it because the optimal solution is too expensive to compute.

Pitfall: Assuming "having a model" means "solving the problem is easy." Even with a perfect model, finding the optimal policy in a large state space can be computationally intractable. Chess has a perfect model (the rules), but no computer can enumerate all possible games.

Recap: The model

p (s^{'}, r ∣ s, a)

captures the environment's dynamics. Having a model enables planning (computing optimal actions without interaction), but not all problems admit a tractable model. RL is defined as the MDP problem class, not by the absence of a model. Next we split RL into model-based vs. model-free approaches.

2.4 Model-Based vs Model-Free RL

2.4.1 Definition and Explanation

Hook: Some people plan every detail of a trip before leaving (model-based). Others just show up at the airport and figure it out (model-free). Both can work — but in very different ways.

RL algorithms split into two broad categories by how they treat the model. *Model-based algorithms* assume a model of the environment is given, *or* learn a model and then use it. *Model-free algorithms* — such as policy-gradient methods and Q-learning — do not use a model; they learn directly from interaction.

Side-by-side contrast:

	Model-Based	Model-Free
Uses a model?	Yes (given or learned)	No
Learns from	Planning with the model	Direct interaction with environment
Examples	Dynamic programming, MCTS	Q-learning, SARSA, policy gradient
Strength	Sample-efficient (fewer interactions needed)	Simpler, no model required
Weakness	Model can be wrong or expensive to build	Requires many interactions

When to pick which: If a model is available and the state space is manageable, model-based methods can be sample-efficient. If the environment is hard to model or the state space is huge, model-free methods are simpler and more robust.

2.4.2 A Quick Map

Model-based: model given (then plan) or model learned (then use it to plan)
Model-free: Q-learning, policy-optimisation methods, etc.

This lecture will not develop these in detail because doing so hand-waves too much; we revisit them once the foundations are solid.

2.4.3 Named Reference

The standard RL textbook — Sutton & Barto, *Reinforcement Learning: An Introduction* — was described as *by far the best in RL* and *the textbook for this course*. Even for deep RL, its foundations remain foundational. The rest of the course material comes from research papers.

Recap: Model-based methods use a model to plan; model-free methods learn directly from interaction. The choice depends on whether a model is available and how expensive it is to build or compute with. The course textbook is Sutton & Barto. Next we cover course logistics and preview how RL becomes *deep* RL.

2.5 Course Logistics, Assessment, and Deep RL Preview

2.5.1 Course Structure

The course is conceptual and mathematical, deliberately rooted in foundations rather than rushing to deep RL. About 60% of the course is on conceptual RL; deep RL is layered on top once foundations are in place. Exam note: the journey can feel theory-heavy but the payoff is well worth it according to past student feedback.

Scope: This course intentionally delays deep RL. Do not expect neural networks in the first half. The foundations (value functions, MAB, MDPs, dynamic programming, Monte Carlo, TD learning) are the prerequisite machinery.

2.5.2 Assessment

Two quizzes, each worth 5%; the final grade uses the *better* of the two. (Technically two 5% quizzes are conducted; the higher of the two counts.) No make-up exams, so plan around the 5-day live window for each quiz.
Two group assignments; combined weight 25%; split roughly 10–12% before midterm and 13–14% after.
Webinars delivered by senior teaching assistants give hands-on practical exposure; reach out to them for practical doubts.

Q: Are the assignments individual or in groups? A: Group assignments.

Exam note: No make-up quizzes. Mark the quiz windows in your calendar now.

2.5.3 From RL to Deep RL with a Toy Example

Hook: You already know tabular RL from the tic-tac-toe example — one value per state, stored in a lookup table. What happens when the state space is too large for a table? You replace the table with a neural network. That single swap turns RL into *deep* RL.

To show how a tabular RL solution becomes *deep* RL, take the tic-tac-toe value function from the previous lecture. The value function is a map: $state \to real number$ . Originally that map is a *table*, with one entry per state. Now *parameterise* the same function with a *neural network*: a network takes a state as input, applies parameters $θ$ , and returns a value $V_{θ} (s)$ . The goal of learning becomes: adjust $θ$ so that $V_{θ} (s)$ returns good estimates of the true value of $s$ for every state $s$ . If you swap the value table for a neural network — and learn the parameters — you have a *deep RL* solution to tic-tac-toe.

Worked example — table vs. network: Tabular (classic RL):

Board state = "XO_\_X\_\_O\_" → look up table entry → $V = 0.65$
One entry per possible board configuration.

Neural network (deep RL):

Board state encoded as a vector (e.g., $X = 1, O = - 1,_= 0$ ) → feed into network with weights $θ$ → output $V_{θ} (s) = 0.63$
Same network generalises across *all* states, even ones never seen in training.

Key difference: The table stores each value independently; the network *shares* parameters across states, so it can generalise to new states from patterns in seen states.

2.5.4 Symbol Registry — Parameterised Value Function

$θ$ — parameters of the value network — vector — learned by gradient descent
$V_{θ} (s)$ — parameterised state-value function — scalar
$s$ — already defined in 2.1.2

More generally, in a classic RL framework, if you bring deep-learning components into one or more of the agent's pieces (value function, policy, or model), the result is a *deep reinforcement learning* solution.

Pitfall: Assuming deep RL is fundamentally different from tabular RL. It is the *same* problem (maximise cumulative reward) with the *same* elements (agent, environment, policy, value function, model) — the only change is that the value function (or policy, or model) is now represented by a parameterised function approximator (a neural network) instead of a table.

Recap: Deep RL = tabular RL + a neural network as function approximator. The parameterised value function

V_{θ} (s)

generalises across states. This is the bridge the course will build toward. Next: the multi-armed bandit problem, the simplest RL-like setting.

2.6 Multi-Armed Bandit Problem (MAB): Setup and Motivation

2.6.1 The Casino Analogy

Hook: You walk into a casino with K slot machines. You have a limited budget. Which machine do you pull — and how long do you keep pulling it before trying another? That decision problem is the *multi-armed bandit*.

Picture walking into a casino with K slot machines — say four machines, each with one arm (a lever). You pay for coins, choose one machine, insert a coin, and pull the lever. With high probability the machine swallows your coin; occasionally it pays back, sometimes substantially more than what you spent. The *one-armed bandit* is one such machine; a *multi-armed bandit* is the K-armed version where you must decide which arm to pull at each step.

This is why the term is used: the bandit *takes everything* — almost 99% of players leave with nothing; a tiny fraction gets a payout. Hence the name "bandit".

Intuition: The name captures the essence: the machines rob you. Your job is to figure out which one robs you *least* — and then exploit that knowledge for all it's worth.

2.6.2 Symbol Registry

$K$ — number of arms — positive integer (e.g., 4 or 10)
$A$ — the action of choosing arm $a$ , $a \in {1, \dots, K}$
$t$ — discrete time-step index, $t \in N$
$R_{t}$ — reward obtained at time $t$ — scalar
$q^{*} (a)$ or $Q^{*} (a)$ — *true* (unknown) expected reward of arm $a$ — scalar
$Q_{t} (a)$ — our *estimate* of $q^{*} (a)$ at time $t$ — scalar

2.6.3 Formal Setup

The MAB problem is defined by:

$K$ arms; choosing arm $i$ is the action $a = i$ .
Each arm $a$ has a *reward distribution* — an unknown probability distribution from which its reward is sampled.
Pulling arm $a$ at time $t$ gives a reward $R_{t}$ drawn from that arm's distribution.
The reward distribution of each arm is NOT known to the learner. If it were known, the problem would be like sitting an exam with the question paper already released — no learning necessary.
The objective is to maximise the expected total reward over a horizon of $T$ pulls:

$max E [t = 1 \sum T R_{t}]$

Equivalently, minimise *regret* — the gap between your cumulative reward and the reward you'd have earned by always pulling the best arm.

Evaluative vs. Instructive Feedback: The bandit setting isolates a defining core difficulty of RL — feedback is evaluative, not instructive. Instructive feedback (like supervised learning targets) tells the agent what action it should have taken. Evaluative feedback (reward

R_{t}

) indicates how good the taken action was, but does not reveal if it was the optimal action or what rewards unselected arms would have yielded.

2.6.4 Strategy and the Two Key Questions

The strategy has two halves: (i) you must *identify* the arm with the highest expected reward (the "best" arm), then (ii) keep *pulling* that lever to maximise your cumulative score. This raises two questions:

How do you *identify* the best arm in the first place without knowing the distributions?
How do you define "best"?

Pitfall: Assuming you can identify the best arm by pulling each arm once. A single pull gives one noisy sample — the arm that paid out once may not be the best on average. You need *multiple* samples per arm to get reliable estimates.

2.6.5 Why This Topic Matters in an RL Course

Domain connection: MAB is studied in this course because it isolates the core RL challenge — exploration vs. exploitation — in its simplest form. Every full RL algorithm (Q-learning, policy gradient, etc.) faces the same trade-off; MAB lets us study it cleanly before adding the complexity of states and transitions. It also appears directly in clinical trials, A/B testing, ad placement, and recommendation systems.

MAB is a *precursor* to a full RL problem. It is a deliberately simple, *stateless* setup that lets us study the same elements — action selection, estimation, exploration vs exploitation, learning from rewards — without the additional machinery of states. Once we are comfortable here, the jump to full RL is much easier.

Recap: The MAB problem has K arms with unknown reward distributions. Your goal: maximise cumulative reward by balancing exploration (trying arms to learn their values) and exploitation (pulling the arm you currently believe is best). Next we clarify the notation exception: in MAB, we write

Q (a)

instead of

Q (s, a)

2.7 MAB Is "Stateless": Action-Value Without State

2.7.1 The Notation Exception

Hook: In section 2.2 we established that

Q (s, a)

always has *two* arguments — state and action. Now watch me break that rule on purpose.

In a full RL problem, the action-value function is $Q (s, a)$ — a function of *both* state and action, paired. The state-value function is $V (s)$ . This was a hard rule in the previous lecture.

In the *multi-armed bandit* problem, the standard form drops the state argument: we write simply $Q (a)$ . This is a *deliberate exception for this lecture only* because the MAB problem has no state.

Q: In an earlier slide Q was an (action, state) function, V was (state). But here you wrote Q of an action without a state — did you make a mistake or does it actually need a state? A: Good catch. The reason is that MAB is a *stepping stone* to full RL — its defining feature is that it has *no state*. So I drop the

s

index *only for this MAB problem*. Every other RL problem we discuss will use

Q (s, a)

Notation clarification:

Problem	Action-value	State-value
Full RL	$Q (s, a)$ — value of doing $a$ in state $s$	$V (s)$ — value of being in state $s$
MAB only	$Q (a)$ — value of pulling arm $a$	Not defined (no state)

The dropping of the state index is a notational convenience, not a mathematical change. It reflects the fact that in MAB, the "state" is always the same (the casino hasn't changed), so conditioning on it is meaningless.

2.7.2 Symbol Registry — MAB Notation

$Q (a)$ — action-value function *in MAB only* — scalar; the estimate $Q_{t} (a)$ is the running average of rewards from arm $a$
$V (s)$ — state-value function (full RL only) — not used in this lecture
$s$ — state — not used in this lecture (the exception)

2.7.3 When Could a State Creep In?

Analogy: Imagine the casino was run by a classmate who reconfigures machines depending on mood, promotion, or festive season. Then the same arm could have a different reward distribution depending on *who* runs it — and that "who" or "when" is a *state*. The vanilla MAB assumes no such state: the arm always behaves the same way.

This is the seam that *contextual bandits* (section 2.17) will later widen. In a contextual bandit, the agent observes some context (a "state") before choosing an arm, but the action does not affect future contexts. In full RL, the action *does* affect the next state.

Pitfall: Writing

Q (s, a)

in an MAB problem or using

V (s)

in a bandit setting. Both are undefined because there is no state. Check whether the problem has a state before choosing notation.

Recap: MAB drops the state from

Q (s, a)

to get

Q (a)

— a deliberate exception for this stateless problem only. If a "context" exists that changes the reward distribution, you have a contextual bandit, not vanilla MAB. Next: what

Q (a)

actually represents and why we must estimate it.

2.8 The True Value of an Action and Why It Is Unknown

2.8.1 Definition of $q^{*} (a)$

Hook: Every slot machine in the casino has a *hidden personality* — on average it pays back a certain amount. You can never see that number written on the machine. You can only discover it by pulling the lever many times and watching what happens.

The *true value* (sometimes written $Q^{*} (a)$ or $q^{*} (a)$ ) of arm $a$ is:

$q^{*} (a) = E [R_{t} ∣ A_{t} = a]$

That is, the *expected reward* of choosing arm $a$ . The wording used in class was "expected reward if that action is chosen". If $Q^{*} (a) = 10$ dollars, it means: sometimes the arm pays 0, sometimes 1, sometimes 5, sometimes 3, sometimes 20, but *on average over many pulls* you receive 10 dollars. The expectation is the steady-state average of the arm's reward distribution.

Formal definition:

$q^{*} (a) = E [R_{t} ∣ A_{t} = a] = \int_{- \infty}^{\infty} r p_{a} (r) d r$

where $p_{a} (r)$ is the (unknown) probability density of rewards for arm $a$ . If the rewards are discrete with possible values $r_{1}, r_{2}, \dots$ : $q^{*} (a) = i \sum r_{i} Pr (R = r_{i} ∣ arm a)$

The expectation is taken over the *reward distribution* of arm $a$ , which is assumed to be stationary (fixed) unless stated otherwise.

2.8.2 Symbol Registry

$q^{*} (a)$ , $Q^{*} (a)$ — true (unknown) expected reward of arm $a$ — scalar
$R_{t}$ — reward observed at time $t$ — scalar
$A_{t}$ — action chosen at time $t$ — element of ${1, \dots, K}$
$E [\cdot]$ — expectation under the arm's reward distribution
$p_{a} (r)$ — reward probability density for arm $a$

Worked example — understanding the expectation:

Suppose arm 3 has the following reward distribution:

Payout = 0 with probability 0.6
Payout = 5 with probability 0.3
Payout = 20 with probability 0.1

Then: $q^{*} (3) = 0 \times 0.6 + 5 \times 0.3 + 20 \times 0.1 = 0 + 1.5 + 2.0 = 3.5$

So on average, each pull of arm 3 yields \$3.50. But any single pull might give \$0, \$5, or \$20 — you never observe the \$3.50 directly.

2.8.3 Why Estimation Is Needed

You cannot read $q^{*} (a)$ off the machine. The casino conceals the reward distribution forever; only by pulling repeatedly and observing rewards can you draw closer to it. Hence our *learning target* is a sequence of estimates $Q_{t} (a)$ that converge to $q^{*} (a)$ .

Pitfall: Confusing

q^{*} (a)

(the true, unknown, fixed value) with

Q_{t} (a)

(our current estimate, which changes over time).

q^{*} (a)

is a property of the environment;

Q_{t} (a)

is a property of our knowledge.

Recap:

q^{*} (a) = E [R_{t} ∣ A_{t} = a]

is the true expected reward of arm

a

— a fixed but hidden number. We estimate it from samples:

Q_{t} (a)

is our running guess, which should converge to

q^{*} (a)

as we pull the arm more. Next: the simplest estimator — the sample average.

2.9 Sample-Average Estimation

2.9.1 The Idea

Hook: You've pulled arm 3 ten times and got: 2, 0, 5, 1, 3, 0, 4, 2, 1, 6. What's your best guess for what arm 3 will pay next? The simplest answer: the average so far.

The simplest estimator of $q^{*} (a)$ is the *sample average*: every time you pull arm $a$ , record the reward; the running average of the rewards is your current estimate. So if two friends jointly take turns pulling arms and pass the slot machine back and forth, the second friend simply averages the rewards each arm has produced and reports "this is what we expect from each arm" — that average is the estimate.

Formal definition: At current time

t

, the *sample-average* estimate of

Q_{t} (a)

is:

$Q_{t} (a) = \frac{\sum _{i = 1}^{t - 1} R _{i} \cdot 1 [ A _{i} = a ]}{\sum _{i = 1}^{t - 1} 1 [ A _{i} = a ]}$

where:

The numerator is the sum of all rewards obtained from pulling arm $a$ before time $t$ .
The denominator is the number of times arm $a$ was pulled before time $t$ .
The *indicator* $1 [A_{i} = a]$ equals 1 if action $a$ was chosen at step $i$ , and 0 otherwise. It acts as a filter: only rewards from arm $a$ contribute to the sum.

This is the arithmetic mean of the rewards observed for arm $a$ .

The Repeated Estimation Cycle (4-Step Loop):

Action-value methods operate in a continuous 4-step loop at every decision point $t$ :

Maintain estimates: Keep a current action-value estimate $Q_{t} (a)$ for each of the $K$ arms.
Select an action: Choose action $A_{t}$ using an action-selection rule (e.g., greedy or $ε$ -greedy).
Observe reward: Receive numerical reward $R_{t}$ generated by arm $A_{t}$ 's reward distribution.
Update only the selected action: Revise the estimate $Q_{t + 1} (A_{t})$ using $R_{t}$ . Unselected arms retain their previous estimates.

2.9.2 Symbol Registry

$Q_{t} (a)$ — running estimate of $q^{*} (a)$ at time $t$ — scalar
$R_{i}$ — reward obtained at step $i$ — scalar
$A_{i}$ — action chosen at step $i$ — element of ${1, \dots, K}$
$1 [\cdot]$ — indicator function: 1 if condition true, 0 otherwise

2.9.3 Incremental Update Formula

Storing all past rewards wastes memory. The textbook (Sutton & Barto, Eq. 2.3) gives an *incremental* form that updates the estimate with constant memory and computation per step:

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

where $n$ is the number of times this arm has been pulled, $Q_{n}$ is the current estimate, and $R_{n}$ is the latest reward.

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) Q_{n}) = \frac{1}{n} (R_{n} + n Q_{n} - Q_{n}) = Q_{n} + \frac{1}{n} [R_{n} - Q_{n}]$

Interpretation: The new estimate is the old estimate plus a correction term:

\frac{1}{n} [target - old estimate]

. The correction shrinks as

n

grows, so early pulls have more influence and later pulls fine-tune.

This is an instance of the general form: $NewEstimate \leftarrow OldEstimate + StepSize [Target - OldEstimate]$ which recurs throughout RL.

2.9.4 Concrete Numerical Mini-Example

Setup: Four arms pulled over 10 steps:

Arm	Pulls	Rewards	Average
1	3	$- 1, - 1, + 5$	$Q (1) = \frac{- 1 - 1 + 5}{3} = \frac{3}{3} = 1.0$
2	3	$0.5, 0.5, - 1.5$	$Q (2) = \frac{0.5 + 0.5 - 1.5}{3} = \frac{- 0.5}{3} \approx - 0.2$
3	3	$- 1, 0, - 0.5$	$Q (3) = \frac{- 1 + 0 - 0.5}{3} = \frac{- 1.5}{3} = - 0.5$
4	1	$- 2$	$Q (4) = \frac{- 2}{1} = - 2.0$

Total pulls = 3 + 3 + 3 + 1 = 10, so the next decision is at $t = 11$ .

The estimated values at $t = 11$ :

$Q_{11} (1) = 1.0$
$Q_{11} (2) = - 0.2$
$Q_{11} (3) = - 0.5$
$Q_{11} (4) = - 2.0$

A *greedy* agent picks $ar g max_{a} Q_{11} (a) = arm 1$ .

Sense-check: Arm 1 looks best with the highest average, but it had a lucky +5 in only 3 pulls — we might be misled.

Q: Are we averaging across all arms, or per arm? A: Per arm only. If arm 1 gave rewards 1, 2, 3 then

Q (1) = (1 + 2 + 3) /3 = 2

. Other arms get their own estimates computed only from their own observed rewards.

Numerical Illustration of Tied Sample-Average Estimates:

Suppose three candidate actions yield the following observed sequence of rewards:

Action	Observed Rewards	Sample-Average Estimate $Q (a)$
$a_{1}$	$2, 4, 3$	$Q (a_{1}) = \frac{2 + 4 + 3}{3} = 3.00$
$a_{2}$	$5, 1$	$Q (a_{2}) = \frac{5 + 1}{2} = 3.00$
$a_{3}$	$0, 2, 1, 1$	$Q (a_{3}) = \frac{0 + 2 + 1 + 1}{4} = 1.00$

Insight: Here $a_{1}$ and $a_{2}$ are tied at an estimated value of $3.00$ . Under a greedy selection rule, ties are broken arbitrarily. Further exploration is necessary to determine which action is truly superior.

2.9.5 Second Numerical Story: The "Secret Truth"

The hidden reality: Suppose the *true* (unknown) expected rewards of the four arms are:

$q^{*} (a_{1}) = - 0.5, q^{*} (a_{3}) = + 1$

(The true values of $a_{2}$ and $a_{4}$ are not specified in the lecture.)

Our estimates at $t = 11$ tell a very different story:

$Q_{11} (a_{1}) = + 1.0$ but $q^{*} (a_{1}) = - 0.5$ → over-optimistic by 1.5
$Q_{11} (a_{3}) = - 0.5$ but $q^{*} (a_{3}) = + 1.0$ → over-pessimistic by 1.5

A *greedy* agent would keep pulling $a_{1}$ (it looks best) and *never* discover that $a_{3}$ is actually the best arm. The agent has been misled by the limited sample.

Key insight: With only 3 pulls per arm, the sample averages are noisy. Arm 1 happened to get a lucky +5; arm 3 happened to get unlucky draws. A pure greedy strategy locks in these early, unrepresentative impressions.

Pitfall: Assuming the sample average converges instantly. With only a few pulls, the estimate is highly variable. This is why exploration is essential — you need enough samples from each arm to get reliable estimates before committing.

Recap: The sample average

Q_{t} (a) = \frac{\sum R _{i} \cdot 1 [ A _{i} = a ]}{\sum 1 [ A _{i} = a ]}

is the simplest estimator of

q^{*} (a)

. It can be computed incrementally with

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

. Early estimates are noisy — a pure greedy strategy can lock onto a lucky arm. Next: what *is* greedy action selection, and why is it flawed?

2.10 Greedy Action Selection

2.10.1 Definition

Hook: If you've tried four restaurants and one of them gave you the best meal so far, would you ever go back to the others? The greedy agent says: never.

*Greedy action selection* always picks the action with the currently highest estimated value:

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

This is exploitation without exploration. If all estimates are tied (e.g., all zeros at $t = 0$ ), the tie is broken arbitrarily.

Formal rule:

$A_{t} = ar g a max Q_{t} (a)$ where $ar g max_{a}$ returns the action $a$ that maximises $Q_{t} (a)$ . Ties are broken arbitrarily (e.g., uniformly at random among tied actions).

Worked example: At

t = 11

with the estimates from section 2.9.4:

$Q_{11} (1) = 1.0$ , $Q_{11} (2) = - 0.2$ , $Q_{11} (3) = - 0.5$ , $Q_{11} (4) = - 2.0$
$ar g max = 1$ , so $A_{11} = 1$ (pull arm 1)
At $t = 12$ , if arm 1 returns reward 0, the new estimate: $Q_{12} (1) = Q_{11} (1) + \frac{1}{4} [0 - 1.0] = 1.0 - 0.25 = 0.75$
Still the highest, so greedy pulls arm 1 again. And again. Forever.

Pitfall: The weakness of pure greedy, established in section 2.9.5, is that once an action's estimate leads the pack (perhaps by luck), greedy keeps pulling it and never tries the others. The agent gets *stuck* — not because it made a bad choice initially, but because it *never revisits* the other options.

In the 10-armed testbed (section 2.14), the greedy method finds the optimal action in only about one-third of problems. In the other two-thirds, its initial samples of the optimal action were disappointing, and it *never returns to it*.

Recap: Greedy = always exploit, never explore. It's simple but dangerous: early lucky or unlucky samples determine the agent's fate forever. Next: ε-greedy, which fixes this by occasionally exploring at random.

2.11 $ε$ -Greedy Action Selection

2.11.1 Definition and Explanation

Hook: Pure greedy says "never explore." ε-greedy says "explore *just enough*." The single number

ε

controls the entire trade-off.

$ε$ -greedy (read "epsilon-greedy") *behaves greedily most of the time, but with a small probability $ε$ , chooses an action uniformly at random*. Here $ε$ is a hyperparameter in $[0, 1]$ : with probability $1 - ε$ take the greedy action; with probability $ε$ pick uniformly among *all* arms (including the greedy one). The wording used in class: "behave greedily most of the time, but once in a while, with a small probability, choose actions randomly independent of their estimated value so far".

Formal definition:

$A_{t} = {ar g max_{a} Q_{t} (a) uniform random from {1, \dots, K} with probability 1 - ε (exploit) with probability ε (explore)$

Key properties:

Every arm has a nonzero probability of being selected at every step.
As $t \to \infty$ , every arm is sampled infinitely often, so all $Q_{t} (a)$ converge to $q^{*} (a)$ .
The probability of selecting the optimal action converges to at least $1 - ε + ε / K$ (see section 2.12).

2.11.2 Symbol Registry

$ε$ — exploration rate — scalar in $[0, 1]$ (e.g., 0.4, 0.1, 0.05, 0.01)
$Q_{t} (a)$ — current estimate of $q^{*} (a)$
$ar g max_{a}$ — the action with the highest estimated value
$1 - ε$ — fraction of steps that exploit (greedy)

2.11.3 Interpretation of Common $ε$ Values

What different $ε$ values mean in practice (100 steps):

$ε$	Exploit steps (approx.)	Explore steps (approx.)	Behaviour
0	100	0	Pure greedy — no exploration
0.01	99	1	Minimal exploration — very slow learning
0.1	90	10	Moderate exploration — good balance
0.4	60	40	Heavy exploration — lots of random actions

$ε$ itself can be tuned — start larger and decay to smaller over time.

2.11.4 Why ε-Greedy Is Popular

Intuition: ε-greedy is popular because it is *dead simple*: one number

ε

controls the entire exploration-exploitation trade-off. No complex optimality calculations, no prior knowledge required. Just set

ε

and go.

$ε$ -greedy is one of the most popular ways to balance exploration and exploitation. The single number $ε$ controls all the trade-off you need. Keep that idea in mind.

Pitfall: Setting

ε

too high (e.g., 0.9) wastes most steps on random actions. Setting

ε

too low (e.g., 0.001) explores so slowly that the agent may never find the best arm in a reasonable horizon. The "right"

ε

depends on the problem — but

ε = 0.1

is a common starting point.

Recap: ε-greedy balances exploration and exploitation with one hyperparameter. With probability

1 - ε

exploit (pick best arm), with probability

ε

explore (pick randomly). Next: worked examples computing the probability of selecting the greedy arm.

2.12 Worked Examples: Probability the Greedy Arm Is Selected

2.12.1 Example 1 — Two Actions, $ε = 0.5$

Setup: Two actions

A_{1}, A_{2}

; assume

A_{1}

is the greedy one (has the higher estimated value).

ε = 0.5

. Step-by-step computation:

The ε-greedy rule splits into two branches:

Branch 1 — Greedy (probability $1 - ε = 0.5$ ):

We always pick the greedy action $A_{1}$ .
Contribution to $P (A_{1})$ : $1 \times 0.5 = 0.5$

Branch 2 — Explore (probability $ε = 0.5$ ):

We pick uniformly among both arms, so each gets $1/2 = 0.5$ of the exploration probability.
Contribution to $P (A_{1})$ : $0.5 \times 0.5 = 0.25$
Contribution to $P (A_{2})$ : $0.5 \times 0.5 = 0.25$

Total probabilities:

$P (A_{1}) = greedy branch 0.5 + explore branch 0.25 = 0.75$ $P (A_{2}) = greedy branch 0 + explore branch 0.25 = 0.25$

Sense-check: The greedy action gets 75% of the probability — it's favoured but not guaranteed.

2.12.2 Example 2 — Four Actions, $ε = 0.4$

Setup: Four actions

A_{1}, \dots, A_{4}

; assume

A_{1}

greedy.

ε = 0.4

. Step-by-step: Greedy branch (probability $1 - ε = 0.6$ ):

Contribution to $P (A_{1})$ : $1 \times 0.6 = 0.6$

Explore branch (probability $ε = 0.4$ ):

Pick uniformly among *all four arms* (including $A_{1}$ ):
Each arm gets $0.4/4 = 0.1$

Total probabilities:

$P (A_{1}) = 0.6 + 0.1 = 0.7, P (A_{i}) = 0.1 for i = 2, 3, 4$

Sense-check:

0.7 + 0.1 + 0.1 + 0.1 = 1.0

. ✓

Common student mistake: The lecturer flagged that *despite many discussions, students often make a mistake here*: when exploring, "the greedy arm is also eligible" — that is why the 0.4 must be split *four ways*, not three. The greedy action still receives one share of exploration. Do NOT compute

0.6 + 0

for the greedy arm.

2.12.3 Example 3 — Detailed 4-Armed Bandit with $ε = 0.20$

Setup: A 4-armed bandit (

K = 4

) with current action-value estimates:

Q_{t} (a_{1}) = 1.5, Q_{t} (a_{2}) = 2.1, Q_{t} (a_{3}) = 1.2, Q_{t} (a_{4}) = 0.9

The greedy action is

a_{2}

(

ar g max Q_{t} (a)

). We select actions using

ε

-greedy with

ε = 0.20

Selection Component	Probability & Meaning
Random Exploration Probability	$ε = 0.20$ (Random action chosen 20% of the time)
Direct Greedy Choice Probability	$1 - ε = 0.80$ ( $a_{2}$ directly chosen 80% of the time)
Per-Action Exploration Share	$\frac{ε}{K} = \frac{0.20}{4} = 0.05$ (Each arm receives 5% prob via exploration)
Total Probability of Greedy Arm $a_{2}$	$(1 - ε) + \frac{ε}{K} = 0.80 + 0.05 = 0.85$ (85%)
Total Probability of Each Non-Greedy Arm ( $a_{1}, a_{3}, a_{4}$ )	$\frac{ε}{K} = 0.05$ (5% each)

Takeaway: The greedy arm $a_{2}$ can also be picked during the random exploration phase. Thus its overall selection probability is $1 - ε + \frac{ε}{K} = 0.85$ .

2.12.3 Symbol Registry

$A_{1}, A_{2}, \dots, A_{K}$ — the $K$ candidate actions (arms)
$A^{*}$ — the greedy arm (the arg-max) — single element
$ε$ — exploration rate (already defined in 2.11.2)
$P (A)$ — selection probability of action $A$ — scalar in $[0, 1]$
$K$ — number of arms (already defined in 2.6.2)

2.12.4 Probability of Greedy Action — Formal Derivation

Let $A^{*}$ be the unique greedy action among $K$ arms. Using the law of total probability:

$P (A^{*}) = P (A^{*} ∣ greedy branch) P (greedy branch) + P (A^{*} ∣ explore branch) P (explore branch) = 1 \cdot (1 - ε) + \frac{1}{K} \cdot ε = 1 - ε + \frac{ε}{K}$

For any *non-greedy* action $A_{i} \neq = A^{*}$ : $P (A_{i}) = 0 \cdot (1 - ε) + \frac{1}{K} \cdot ε = \frac{ε}{K}$

Verification with earlier examples:

Example	$K$	$ε$	$P (A^{*}) = 1 - ε + ε / K$	Matches?
Example 1	2	0.5	$1 - 0.5 + 0.25 = 0.75$	✓
Example 2	4	0.4	$1 - 0.4 + 0.1 = 0.7$	✓

General formula:

P (A^{*}) = 1 - ε + ε / K

. This is the *minimum* probability of selecting the greedy arm at any single step.

Recap: The greedy arm is selected with probability

1 - ε + ε / K

; non-greedy arms each get

ε / K

. The greedy arm is always *more likely* to be chosen, but every arm has a nonzero chance. Next: the formal ε-greedy algorithm as pseudocode.

2.13 Formal ε-Greedy Algorithm (Pseudocode)

2.13.1 Procedure

ε-Greedy Action Selection Algorithm:

Set $ε$ small (e.g., 0.05). At each time step:

Draw a uniform random number $u \sim U (0, 1)$ .
If $u > ε$ : exploit — select $A = ar g max_{a} Q (a)$ .
If $u \leq ε$ : explore — select $A$ uniformly at random from all arms.

function get_action(Q, ε):    u ← random.random()            # uniform in [0, 1)    if u > ε:        A ← argmax_a Q(a)          # exploit    else:        A ← random over all actions # explore    return A

Trace with $ε = 0.05$ :

Step	$u$	$u > 0.05$ ?	Action
1	0.82	Yes	exploit: pick argmax
2	0.03	No	explore: pick random arm
3	0.91	Yes	exploit: pick argmax
4	0.67	Yes	exploit: pick argmax
5	0.01	No	explore: pick random arm

About 5% of steps explore, 95% exploit — matching $ε = 0.05$ .

2.13.2 Symbol Registry

$u$ — sample from $U (0, 1)$ — scalar
argmax_a Q(a) — action with the maximum current estimate
random — uniform distribution over arms
$ε$ — threshold below which we explore (e.g., 0.05 → 5% of the time)

2.13.3 Student Doubt on the Random Function

Q: Since random can return *any* value in

[0, 1]

, what if it returns the *same* number every step (e.g., always 0.8)? Doesn't that break the 60/40 split we expect? A: No — the expectation of random.random() is *uniform* over

[0, 1]

. Every real number in that interval has an equal chance of being returned. Hence the *fraction* of draws falling in

[0, ε]

is exactly

ε

, and the fraction in

(ε, 1]

1 - ε

, *in expectation over many draws*. If your RNG did *not* have this uniform property the algorithm would break, which is why it must be a proper uniform RNG. Of course, in a *single* draw any value can come up; the guarantee is statistical, not deterministic.

Intuition: Think of

ε

as a coin flip each step. The coin lands "explore" with probability

ε

and "exploit" with probability

1 - ε

. Over 1000 steps with

ε = 0.05

, expect about 50 explore flips and 950 exploit flips — but any single flip can go either way.

Pitfall: Confusing the *threshold*

ε

with the *probability of exploring*. They are the same thing. The algorithm draws

u

and explores if

u \leq ε

. Since

u

is uniform,

Pr (u \leq ε) = ε

Recap: The ε-greedy algorithm is a simple if-else: draw a uniform random number, exploit if it's above

ε

, explore otherwise. The threshold

ε

directly equals the exploration probability. Next: empirical results comparing greedy, ε=0.1, and ε=0.01 on the 10-armed testbed.

2.14 The 10-Armed Testbed and Empirical Comparison

2.14.1 Setting Up the Testbed

Hook: How do you prove that ε-greedy is better than greedy? You run the same experiment 2000 times and average the results. The *10-armed testbed* is RL's standard laboratory bench.

The 10-armed bandit is a standard testbed for comparing action-selection algorithms. Each arm has its own reward distribution (so its own $q^{*} (a)$ ). We generate 2000 different *testbeds* (2000 independent 10-armed problems); for each testbed we run the algorithm for 1000 steps; we average the per-step reward across all 2000 testbeds. This gives a clean empirical curve showing how each algorithm performs over a horizon.

How the testbed is built (from Sutton & Barto §2.3):

For each of 2000 independent runs:

Draw 10 true action values: $q^{*} (a) \sim N (0, 1)$ for $a = 1, \dots, 10$ .
These are the *hidden* expected rewards of the 10 arms.

At each time step $t = 1, \dots, 1000$ :

The algorithm selects arm $A_{t}$ .
The reward is drawn: $R_{t} \sim N (q^{*} (A_{t}), 1)$ — the actual reward is noisy, centred on the true value.

After all 2000 runs, average the reward at each time step across runs.

This setup ensures that:

Each arm has a different, unknown true value.
Rewards are noisy (variance 1), so single pulls are unreliable.
Averaging over 2000 runs gives a statistically stable performance curve.

2.14.2 Symbol Registry

$K = 10$ — fixed number of arms for this testbed
$T = 1000$ — horizon (steps per run)
2000 — number of independent testbeds averaged
$Q_{1} (a) = 0$ — initial estimate for every arm
$ε \in {0, 0.01, 0.1}$ — the three settings compared

2.14.3 Initialisation

Each algorithm begins with $Q_{1} (a) = 0$ for all arms. Whichever arm we sample first returns some reward — say $- 1$ or $+ 1$ — and that arm's estimate is updated to the running average from then on.

2.14.4 The Three Algorithms Compared

Visual description of the textbook figure (Figure 2.2):

The figure has two panels:

Upper panel — Average reward vs. steps:

Algorithm	Colour	Behaviour	At step 1000
Greedy ( $ε = 0$ )	Green	Rises quickly at first, then plateaus at ~1.0	Low plateau
$ε = 0.01$	Red	Rises slowly, still climbing at step 1000	~1.3, still rising
$ε = 0.1$	Blue	Rises steadily, clear winner at step 1000	~1.5 (near optimal ~1.55)

Lower panel — % Optimal action vs. steps:

Algorithm	At step 1000
Greedy	~33% — found optimal in only 1/3 of problems
$ε = 0.01$	~70% and still climbing
$ε = 0.1$	~91% — nearly always picking the best arm

Key observation: The greedy method improved slightly faster at the very beginning (no wasted random moves), but then levelled off. The ε=0.1 method overtook it by about step 200 and never looked back.

Exam note: these colours (green/blue/red) and their shapes are how the textbook figure is drawn and were used in the lecture — know the *ordering* of curves (greedy plateaus, ε=0.1 wins at 1000, ε=0.01 still climbing).

2.14.5 Takeaways on Tuning ε

Pitfall: The lecturer emphasised that ε should never reach exactly 0. Even with a near-perfect policy, if

ε = 0

you stop exploring altogether and become permanently fixated on what you currently believe is best. In a non-stationary environment, the "best" arm can change — and the agent must keep probing to detect that.

The practical advice from the lecture is:

Start with a larger $ε$ (more exploration) when you know little.
Decay $ε$ as your estimates stabilise.
Never bring $ε$ down to exactly 0. Even with a near-perfect policy, if $ε = 0$ you stop exploring altogether and become permanently fixated on what you currently believe is best.
In a non-stationary environment where the underlying reward distribution changes with time (your user's tastes change), you must keep $ε$ at a small positive number *forever* to react to those changes.

If the rewards are truly stationary, you can in principle drive $ε$ close to zero — but never to zero, because you can rarely say with absolute certainty that you have cracked the distribution.

Four Core Lessons from the 10-Armed Testbed:

Early estimates can mislead: A genuinely optimal action may look poor if its initial reward sample happens to be low due to environmental noise.
Greedy selection settles prematurely: Once a greedy agent commits to an early leader, it stops testing alternatives and never returns to actions that were initially underestimated.
$ε$ -greedy restores reliability: Periodic random actions ensure that less-tested options get evaluated, allowing the agent to correct early misleading estimates.
Exploration has a short-term cost for long-term gain: Random actions may reduce immediate reward in early steps, but they yield significantly higher cumulative reward over long horizons by discovering the optimal arm.

Recap: The 10-armed testbed (2000 runs, 1000 steps, K=10) shows ε=0.1 outperforms greedy at step 1000. Greedy plateaus at ~33% optimal action; ε=0.1 reaches ~91%. The rule: never set ε=0, especially under non-stationarity. Next: what *is* stationarity, and why does it matter?

2.15 Stationary vs Non-Stationary Rewards

2.15.1 Definition and Explanation

Hook: A restaurant that was great five years ago might be terrible today. The recipe didn't change — your taste did. In RL terms: the reward distribution *shifted*.

A *stationary* reward distribution is one that does not change over time; the underlying $q^{*} (a)$ is fixed. A *non-stationary* reward distribution is one that drifts, even if the agent and the environment are unchanged.

Formal distinction:

	Stationary	Non-stationary
$q^{*} (a)$ over time	Fixed: $q^{*} (a) = const$	Drifting: $q^{} (a) = q_{t}^{} (a)$ changes with $t$
Sample average	Converges to true value	May converge to a stale value
Exploration needed?	Eventually $ε \to 0^{+}$ is OK	$ε > 0$ forever
Example	Fair die (always 1/6 per face)	User preferences (shift with life stage)

2.15.2 Intuition: Same User, Different Tastes

Analogy: Suppose an e-commerce account has been used by the same user for fifteen years. While they lived in Campus A they bought certain items; after moving they bought other items; after marriage, after having a child — each life-stage shifted their purchase pattern. The *person is the same* but the reward distribution the merchant must learn has shifted. Amazon could not "crack" the user once and for all at year one; the distribution itself evolves.

This is the proper definition of non-stationarity — even in a single-user model:

Stationary: assume reward distribution is fixed; once you learn it you are done (mostly).
Non-stationary: rewards drift over time, so to keep current you must *continue to explore at a small rate forever*.

Scope — when sample averages fail under non-stationarity:

The sample average gives equal weight to all past rewards. In a non-stationary environment, old rewards become stale — a reward from 3 years ago may be irrelevant to today's distribution. The fix is to use a *constant step size* $α \in (0, 1)$ instead of $1/ n$ :

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

This gives exponentially decaying weight to old rewards: recent observations dominate. With $α = 0.1$ , a reward from 10 steps ago contributes only $0. 9^{10} \approx 0.35$ as much as the most recent reward.

Pitfall: Setting

ε = 0

in a non-stationary environment. If the best arm changes and the agent has stopped exploring, it will never notice. The lecturer's rule: ε must stay positive forever in non-stationary settings.

Recap: Stationary = fixed reward distributions; non-stationary = drifting distributions. Under non-stationarity, use constant step size

α

instead of sample averages, and keep

ε > 0

forever. Most real-world problems are non-stationary. Next: real-world applications of MAB.

2.16 Real-World Applications of MAB

2.16.1 Online Advertising and Product Recommendation

Hook: Every time Amazon shows you a product banner, it's pulling an arm of a multi-armed bandit. Your click is the reward. The bandit is learning what you like — one impression at a time.

A simplified "naive Amazon" recommendation banner shows 10 products at a time from a catalogue of millions. A click is one reward; a purchase is a higher reward. Each candidate item is an *arm*; its reward distribution depends on the user and is unknown to the platform. The platform iteratively tries items, updates each item's average click/reward rate, and survives by pushing items with higher observed rates. Items never clicked get pruned; new items keep entering. The platform *doesn't know* what *I* will click on next — my reward distribution is unknown and is being learned from interaction.

Mapping MAB to ad/recommendation:

MAB Concept	Ad/Recommendation Analogue
Arm	A candidate product or ad
Pull	Showing the product to the user
Reward	Click (small reward) or purchase (large reward)
$q^{*} (a)$	True click-through rate of product $a$
Exploration	Trying new or rarely-shown items
Exploitation	Showing the product with the highest observed CTR

2.16.2 Cloud Configuration and Resource Allocation

A cloud platform regularly selects server, cache, or database configurations for microservices. Candidate configurations represent arms ( $c_{1}, c_{2}, c_{3}$ ), and the numerical reward is measured as throughput, negative latency, or cost-adjusted performance score. The system learns which configuration yields the best average performance without shutting down services for exhaustive benchmark testing.

Worked Example — Cloud Cache Configuration Selection:

A platform tests three cache configurations with observed performance scores:

$c_{1}$ : $72, 76, 74 ⟹ Q (c_{1}) = \frac{72 + 76 + 74}{3} = 74.0$
$c_{2}$ : $70, 80 ⟹ Q (c_{2}) = \frac{70 + 80}{2} = 75.0$
$c_{3}$ : $68, 69, 71 ⟹ Q (c_{3}) = \frac{68 + 69 + 71}{3} = 69.33$

A greedy selection rule picks $c_{2}$ (score 75.0). Continuous $ε$ -greedy exploration ensures configuration $c_{1}$ is re-tested periodically in case workload patterns shift.

The Missing Counterfactual Information Principle: In online ads, web layout tests, clinical trials, and cloud tuning alike, the learner only observes reward feedback for the action actually taken. The unselected alternatives yield no counterfactual observations. This missing information is the fundamental reason why active exploration is mandatory in reinforcement learning.

2.16.3 Detecting a Biased Coin

A student proposed a "biased coin" as a 1-armed bandit: toss the same coin repeatedly, label heads as 1 and tails as 0, and average. If the long-run average is exactly 0.5 the coin is unbiased; if it stays above 0.5 it is biased toward heads and below 0.5 toward tails. The lecturer noted this is *technically* a K-armed bandit with $K = 1$ (a "one-armed bandit"). Strictly speaking it is trivial, because there is only one action and hence no choice — proper MABs need at least two arms.

Worked example — biased coin estimation:

Flip a coin 10 times: H, H, T, H, T, H, H, T, H, H → 7 heads, 3 tails. Running average after $n$ flips: $Q_{10} = 7/10 = 0.7$ .

Is the coin biased? With only 10 samples we can't be sure. After 1000 flips with 700 heads, we'd be much more confident that $q^{*} \approx 0.7$ .

Connection to MAB: This is a single-arm estimation problem — there's no choice to make, just estimation. It illustrates the *estimation* component of MAB without the *selection* component.

2.16.3 Clinical Trials

Suppose you have several candidate drugs/treatments to try, a limited number of patients, and you do not yet know which treatment is best. Each regimen is an *arm*; patient response is the *reward*. You keep trying until you accumulate enough evidence to push the bulk of trials to the treatment with the highest response — but you *still* must keep exploring to refine estimates.

Domain connection: Clinical trials are one of the most impactful applications of MAB. The "reward" is patient health — a wrong choice has serious consequences. This is why exploration in MAB is not just about efficiency; in medicine, it can be about saving lives. Adaptive trial designs using MAB principles have been used in cancer treatment studies and COVID-19 vaccine trials.

2.16.4 Simple Portfolio Management

A simplified portfolio of 10 stocks where you have actions *buy / sell / hold* producing rewards. Each action is an arm and we learn its expected reward. Without context this is rather toy; full portfolio management is a more complex agent with state.

Q: In stock/portfolio problems, isn't there a notion of time? Doesn't that make it stateful? A: Time can be a context — so in *some* framings the problem becomes stateful; in a deliberate toy framing where action selection is independent of context you can still pose it as an MAB.

2.16.5 Why Amazon Can Sometimes Surprise Us

Amazon might model my *account*, but my account is used by me, my spouse, my child, my parents; my purchase patterns shift as life stages change. Exam note: the lecturer emphasised these illustrate *why exploration is forever*, not a one-time startup phase — even when you think you have "nailed" a user.

2.16.6 When Is MAB Not Enough? Sports, Games, Driving

Q: Could we model board games like chess, football, or driving as multi-armed bandits? A: No — the lecturer explicitly rejected all three. In each case, the action's worth depends on the *current state* (the board configuration, the position of the ball, the road situation). A move that's brilliant in one chess position is terrible in another. The vanilla MAB is appropriate for *stateless* problems where the action's worth does not depend on context. If it does, you have crossed into *contextual bandit* territory (next section) or a *full RL* setup with state.

Recap: MAB applies to stateless problems: ad selection, clinical trials, A/B testing. It does *not* apply when action value depends on state (games, driving). The key diagnostic: does the value of an action change with context? If yes → contextual bandit or full RL.

2.17 Contextual Bandits and the Bridge to Full RL

2.17.1 Definition and Explanation

Hook: Vanilla MAB says "every arm is the same every time." But what if the casino has a mood ring that changes the odds? Now you need to *read the room* before pulling.

A *contextual bandit* extends MAB by adding a *context* — extra information observed before each action — but *still without* the agent's action affecting future contexts. The reward distribution of an arm depends on this context; the agent learns a policy $π (context) \to arm$ .

Formal definition:

In a contextual bandit, at each step $t$ :

The agent observes a *context* $x_{t}$ (also called "side information" or "features").
The agent selects arm $a_{t}$ .
The agent receives reward $r_{t}$ drawn from a distribution that depends on *both* $x_{t}$ and $a_{t}$ .
Crucially: the agent's action does *not* affect the next context $x_{t + 1}$ . Contexts arrive exogenously.

The policy is a mapping: $π : x \to a$ , where $x$ is the context.

2.17.2 Why It Differs From MAB and Full RL

Three-way comparison:

Feature	Vanilla MAB	Contextual Bandit	Full RL
State/context?	None	Yes ( $x_{t}$ )	Yes ( $s_{t}$ )
Action affects next state?	N/A	No	Yes
Reward depends on	Arm only	Arm + context	Arm + state
Policy	$π : \emptyset \to a$ (fixed)	$π : x \to a$	$π : s \to a$
Example	Slot machine	Ad recommendation given user features	Chess, driving
Sequential?	No	No (each step independent)	Yes (current action changes future)

Key insight: Contextual bandits sit between MAB and full RL. They add context (like RL) but keep the single-step structure (like MAB). The missing piece — actions influencing future states — is what makes full RL *sequential*.

Q: Couldn't Amazon just use recommendation based on history, location, similar users, etc. (lots of context)? A: Yes — if you bring in that context you are no longer solving a vanilla MAB. You are solving a contextual bandit, which is the bridge to full RL. We will discuss it next class.

2.17.3 Why This Matters

Domain connection: Contextual bandits power many real-world systems:

News recommendation: context = user profile + time of day; arms = articles; reward = click.
Personalised medicine: context = patient demographics + history; arms = treatments; reward = outcome.
Dynamic pricing: context = demand + competitor prices; arms = price points; reward = revenue.

MAB is studied partly to learn the basic RL elements — action-selection, value estimation, exploration vs exploitation, stationary vs non-stationary — in the simplest possible setup, *before* the full MDP machinery. Once you can handle MAB confidently, full RL with states becomes much easier to reason about.

Recap: Contextual bandits add context to MAB but keep the single-step structure (actions don't affect future contexts). They bridge vanilla MAB (no state) and full RL (sequential state transitions). The course will revisit them after building MDP foundations. The progression: MAB → contextual bandits → full RL.

2.18 Self-Assessment & Numerical Practice Questions

Test your understanding of multi-armed bandits, sample-average updates, and $ε$ -greedy action selection with these end-of-topic review problems adapted from Sutton & Barto and course material.

Question 1: Multi-Armed Bandit Setup & One-Situation Rationale

Problem: Define the $k$ -armed bandit problem. State the learner’s objective and explain why the problem is described as a "one-situation" decision problem.

Solution / Answer:

Definition: A $k$ -armed bandit problem is a simplified evaluative-feedback decision problem where a learner repeatedly chooses one action from a set of $k$ available actions (arms) over discrete time steps $t = 1, 2, \dots, T$ . Each action $a$ yields a numerical reward $R_{t}$ drawn from an unknown reward probability distribution.
Objective: To maximize expected total cumulative reward $E [\sum_{t = 1}^{T} R_{t}]$ (or minimize total expected regret) over the decision horizon.
Why "One-Situation": It is stateless. The environment stays in a single static situation across all time steps. The choice of action at time $t$ has no influence on future situations, states, or future reward distributions.

Question 2: Evaluative vs. Instructive Feedback

Problem: Explain why the feedback in a bandit problem is evaluative rather than instructive. Why does the received reward not directly reveal the best action?

Solution / Answer:

Evaluative Feedback: Indicates how good the action taken was, but does not indicate whether it was the best action available or what rewards unselected actions would have produced.
Instructive Feedback: Directly specifies the correct/optimal action regardless of the action taken (as in supervised target labels).
Why reward doesn't reveal the best action: Rewards are stochastic samples. A single reward $R_{t}$ is drawn from a distribution with noise. An optimal action might yield a low reward by chance on a single pull, while a suboptimal action might yield a high reward. Without counterfactual feedback for unselected arms, repeated sampling is required to estimate expected values $q^{*} (a)$ .

Question 3: True Value vs. Estimated Value

Problem: Explain the difference between the true action value $q^{*} (a)$ and the estimate $Q_{t} (a)$ . What kind of experience is needed for $Q_{t} (a)$ to become reliable?

Solution / Answer:

$q^{*} (a) = E [R_{t} ∣ A_{t} = a]$ is the true, fixed, unknown expected reward of action $a$ . It is a property of the environment's reward distribution.
$Q_{t} (a)$ is the learner's estimate of $q^{*} (a)$ at time step $t$ , calculated from past observed rewards. It is a property of the learner's current knowledge.
Reliability Requirement: By the Law of Large Numbers, $Q_{t} (a)$ becomes a reliable estimate of $q^{*} (a)$ only when action $a$ has been selected and sampled a large number of times ( $N_{t} (a) \to \infty$ ).

Question 4: Sample-Average Computation & Greedy Identification

Problem: A bandit has three actions. The observed rewards are: $a_{1} : [2, 4, 3], a_{2} : [1, 5], a_{3} : [0, 2, 2, 4]$ Compute the sample-average estimate for each action and identify the greedy action.

Solution / Answer:

$Q (a_{1}) = \frac{2 + 4 + 3}{3} = \frac{9}{3} = 3.00$
$Q (a_{2}) = \frac{1 + 5}{2} = \frac{6}{2} = 3.00$
$Q (a_{3}) = \frac{0 + 2 + 2 + 4}{4} = \frac{8}{4} = 2.00$

Greedy Action: Actions $a_{1}$ and $a_{2}$ are tied with the highest estimated value of $3.00$ . A greedy action selection rule will break ties arbitrarily between $a_{1}$ and $a_{2}$ .

Question 5: 5-Armed Bandit Selection Probabilities

Problem: In a 5-armed bandit ( $K = 5$ ), suppose $ε = 0.20$ and there is a single unique greedy action. What is the probability of random exploration? What is the total probability that the greedy action is selected?

Solution / Answer:

Probability of random exploration: $ε = 0.20$ (20%).
Probability of selecting greedy action $A^{*}$ : $P (A^{*}) = (1 - ε) + \frac{ε}{K} = (1 - 0.20) + \frac{0.20}{5} = 0.80 + 0.04 = 0.84 (84%)$
Each non-greedy action gets probability $\frac{ε}{K} = \frac{0.20}{5} = 0.04$ (4%).

Question 6: 2-Armed Bandit Selection Probability

Problem: In $ε$ -greedy action selection with two actions ( $K = 2$ ) and $ε = 0.50$ , what is the total probability that the greedy action is selected? Show the calculation.

Solution / Answer:

Exploitation branch probability: $1 - ε = 1 - 0.50 = 0.50$
Exploration branch share per arm: $\frac{ε}{K} = \frac{0.50}{2} = 0.25$
Total probability for greedy action: $P (A^{*}) = (1 - ε) + \frac{ε}{K} = 0.50 + 0.25 = 0.75 (75%)$

Question 7: Sequence Exploration Trace Problem

Problem: A 4-armed bandit uses $ε$ -greedy action selection and sample-average estimates with initial values $Q_{1} (a) = 0$ for all actions. Ties are broken by choosing the smallest action index. The first observations are: $A_{1} = 1, R_{1} = - 1; A_{2} = 2, R_{2} = 1; A_{3} = 2, R_{3} = - 2; A_{4} = 2, R_{4} = 2; A_{5} = 3, R_{5} = 0$ Identify the time steps on which random exploration definitely occurred, and time steps on which it could have occurred.

Solution / Answer:

Let's trace estimates step-by-step:

Step 1 ( $t = 1$ ): Initial estimates $Q_{1} = [0, 0, 0, 0]$ . All arms tied at 0. Greedy choice with smallest index is arm 1. Action taken: $A_{1} = 1, R_{1} = - 1$ . Update: $Q_{2} = [- 1, 0, 0, 0]$ .
Exploration status: $A_{1} = 1$ could be greedy (tie-break) or random exploration.
Step 2 ( $t = 2$ ): Current estimates $Q_{2} = [- 1, 0, 0, 0]$ . Greedy action is any of ${2, 3, 4}$ (tied at 0). Action taken: $A_{2} = 2, R_{2} = 1$ . Update: $Q_{3} = [- 1, 1, 0, 0]$ .
Exploration status: Arm 2 was tied-highest, so could be greedy or exploration.
Step 3 ( $t = 3$ ): Current estimates $Q_{3} = [- 1, 1, 0, 0]$ . Unique greedy action is arm 2 ( $Q_{3} (2) = 1$ ). Action taken: $A_{3} = 2$ .
Exploration status: Selected greedy arm 2. Could be exploitation or exploration. Result: $R_{3} = - 2$ , so $Q_{4} (2) = \frac{1 - 2}{2} = - 0.5$ . Update: $Q_{4} = [- 1, - 0.5, 0, 0]$ .
Step 4 ( $t = 4$ ): Current estimates $Q_{4} = [- 1, - 0.5, 0, 0]$ . Greedy actions are arms 3 and 4 (tied at 0). Action taken: $A_{4} = 2$ .
Exploration status: DEFINITE EXPLORATION! Arm 2 had estimate $- 0.5$ , while arms 3 and 4 had higher estimate $0$ . Choosing arm 2 at $t = 4$ could only happen via random exploration! Result: $R_{4} = 2$ , new $Q_{5} (2) = \frac{1 - 2 + 2}{3} = \frac{1}{3} \approx 0.33$ . Update: $Q_{5} = [- 1, 0.33, 0, 0]$ .
Step 5 ( $t = 5$ ): Current estimates $Q_{5} = [- 1, 0.33, 0, 0]$ . Unique greedy action is arm 2 ( $Q_{5} (2) = 0.33$ ). Action taken: $A_{5} = 3$ .
Exploration status: DEFINITE EXPLORATION! Arm 3 had estimate $0$ , which is lower than greedy arm 2 ( $0.33$ ). Selecting arm 3 at step 5 was a non-greedy choice, so it definitely occurred via random exploration.

Summary:

Definitely explored: Steps $t = 4$ and $t = 5$ .
Could have explored (or exploited): Steps $t = 1, 2, 3$ .

Question 8: Website Banner Formulation & Unobserved Counterfactuals

Problem: A website can show one of four banners to a visitor. A click gives reward 1 and no click gives reward 0. Identify the arms and rewards in this bandit formulation. What is not observed after a banner is selected?

Solution / Answer:

Arms ( $K = 4$ ): The 4 banner variants available to display.
Reward ( $R_{t}$ ): Binary indicator — $1$ if visitor clicks, $0$ if visitor leaves without clicking.
Unobserved Counterfactuals: The rewards (click or no click) that would have occurred if any of the other 3 banners had been displayed to this specific visitor are completely unobserved.

Question 9: Cloud Cache Configuration Action Values

Problem: A cloud platform tests three cache configurations. The observed performance scores are: $c_{1} : [72, 76, 74], c_{2} : [70, 80], c_{3} : [68, 69, 71]$ Compute the current action-value estimate for each configuration and identify the greedy configuration.

Solution / Answer:

$Q (c_{1}) = \frac{72 + 76 + 74}{3} = \frac{222}{3} = 74.0$
$Q (c_{2}) = \frac{70 + 80}{2} = \frac{150}{2} = 75.0$
$Q (c_{3}) = \frac{68 + 69 + 71}{3} = \frac{208}{3} \approx 69.33$

Greedy Configuration: Configuration $c_{2}$ has the highest current estimate ( $75.0$ ), so it is the greedy choice.

Question 10: Early Fast Improvement vs. Long-Run Plateau

Problem: Based on the 10-armed testbed performance curves, explain why the greedy method can improve quickly at first but still perform poorly in the long run.

Solution / Answer:

Early fast improvement: Greedy immediately exploits whichever arm gives a positive early reward, avoiding exploratory steps on arms that yield low initial rewards.
Long-run plateau: Because greedy never explores, if the true optimal arm initially receives an unluckily low reward sample, greedy locks onto a suboptimal leader and never samples the optimal arm again. In the 10-armed testbed, greedy gets stuck on suboptimal arms in roughly 2/3 of all problems, leading to a low long-run average reward plateau (~1.0 vs ~1.55 optimal).

Question 11: Comparing $ε = 0.1$ vs. $ε = 0.01$

Problem: Compare $ε = 0.1$ and $ε = 0.01$ in the 10-armed testbed. Which one explores more often, and how does that affect early discovery of the optimal action vs. long-term performance?

Solution / Answer:

$ε = 0.1$ explores 10% of the time, while $ε = 0.01$ explores only 1% of the time.
Early discovery: $ε = 0.1$ finds the optimal action much faster early on because it samples alternative arms 10 times more frequently.
Long-term performance: $ε = 0.1$ levels off at choosing the optimal action ~91% of the time (because 10% of the time it still chooses randomly). $ε = 0.01$ improves more slowly, but over very long horizons ( $t > 10, 000$ ) it will eventually reach ~99% optimal action selection because its asymptotic penalty for random exploration is much smaller (1% vs 10%).

Exam Guidance Summary

Course structure and assessment:

Lecture structure: ~60% of the course is conceptual RL foundations; deep RL comes later. The course journey may feel theoretical but is well worth it.
Quizzes: Two quizzes, each 5%, best of two counted. No make-ups — plan around the 5-day live window for each quiz.
Assignments: Two group assignments, 25% total split as ~10–12% pre-midterm and ~13–14% post-midterm.

Exam-ready topics from this lecture:

The $V$ vs. $Q$ distinction: $V (s)$ asks "how good is this state?", $Q (s, a)$ asks "how good is this action in this state?"
The notation exception: MAB uses $Q (a)$ instead of $Q (s, a)$ because there is no state.
Sample-average estimation formula $Q_{t} (a) = \frac{\sum R _{i} \cdot 1 [ A _{i} = a ]}{\sum 1 [ A _{i} = a ]}$ and its incremental form $Q_{n + 1} = Q_{n} + \frac{1}{n} [R_{n} - Q_{n}]$ .
The $ε$ -greedy probability calculation: $P (A^{*}) = 1 - ε + ε / K$ .
Formal ε-greedy pseudocode: draw $u \sim U (0, 1)$ , exploit if $u > ε$ , explore otherwise.
The 10-armed testbed comparison: greedy plateaus (~33% optimal), $ε = 0.1$ wins at 1000 steps (~91% optimal), $ε = 0.01$ still climbing.
$ε$ should never reach 0, especially under non-stationary rewards.
Classification of scenarios as MAB / contextual bandit / full RL.

Question patterns to expect:

Numerical worked problems on ε-greedy selection probabilities (given $K$ and $ε$ , compute $P (greedy arm)$ ).
Short derivations (sample-average formula, incremental update).
Conceptual questions on stationary vs. non-stationary rewards and why $ε$ must stay positive.
Application-oriented classification: given a scenario, identify whether it's MAB, contextual bandit, or full RL — and justify.

Key Industry Applications

Domain connection: MAB is not just a textbook curiosity — it drives billions of dollars of decisions in industry. Here are the major application areas.

Recommendation and ad platforms (Amazon-style): viewing each candidate product/ad as an arm and the click or purchase as a stochastic reward. The platform maintains running estimates of each item's click-through rate and shifts traffic toward higher-performing items.

Clinical trial design: experimental arms compared with limited patient budget; balance exploration (treating new candidates) vs exploitation (using the currently best estimate). Adaptive MAB-based trials have been used in oncology and vaccine development.

Simple portfolio management (toy framing): buy/sell/hold as actions with stochastic returns. A simplified MAB abstraction; real portfolio management requires state (market conditions, time, holdings).

A/B testing / web layout optimisation: different layouts or treatments as arms; MAB generalises A/B testing by continually shifting traffic toward better variants rather than committing fixed 50/50 splits. This is sometimes called "adaptive experimentation."

Detecting a biased coin: a one-armed verification benchmark requiring many samples to estimate a Bernoulli parameter from a running average. Useful as a teaching tool and as a component of more complex systems.

Production system monitoring under non-stationarity: adaptive agents maintaining a small but positive exploration rate permanently so they react to drifts. Cloud systems use MAB-based approaches for load balancing, feature flagging, and canary deployments.

Named references:

The standard RL textbook — Sutton & Barto, *Reinforcement Learning: An Introduction* — is described as the *best book in RL* and is the course textbook; even deep RL rests on what it covers.
Course research papers (cited across remaining lectures) were mentioned but not specifically named this session.

DRL Lecture 2 Notes · Elements of RL and Multi-Armed Bandits

Deep Reinforcement Learning· postgraduate· 2026-07-20

Sections Breakdown

12.1 Recap of the Previous Class and the Agent-Environment Interface

2.1 Recap of the Previous Class and the Agent-Environment Interface

22.2 The Two Value Functions: State-Value $V(s)$ and Action-Value $Q(s,a)$

2.2 The Two Value Functions: State-Value $V(s)$ and Action-Value $Q(s,a)$

32.3 Model of the Environment

2.3 Model of the Environment

42.4 Model-Based vs Model-Free RL

2.4 Model-Based vs Model-Free RL

52.5 Course Logistics, Assessment, and Deep RL Preview

2.5 Course Logistics, Assessment, and Deep RL Preview

62.6 Multi-Armed Bandit Problem (MAB): Setup and Motivation

2.6 Multi-Armed Bandit Problem (MAB): Setup and Motivation

72.7 MAB Is "Stateless": Action-Value Without State

2.7 MAB Is "Stateless": Action-Value Without State

82.8 The True Value of an Action and Why It Is Unknown

2.8 The True Value of an Action and Why It Is Unknown

92.9 Sample-Average Estimation

2.9 Sample-Average Estimation

102.10 Greedy Action Selection

2.10 Greedy Action Selection

112.11 $\varepsilon$-Greedy Action Selection

2.11 $\varepsilon$-Greedy Action Selection

122.12 Worked Examples: Probability the Greedy Arm Is Selected

2.12 Worked Examples: Probability the Greedy Arm Is Selected

132.13 Formal ε-Greedy Algorithm (Pseudocode)

2.13 Formal ε-Greedy Algorithm (Pseudocode)

142.14 The 10-Armed Testbed and Empirical Comparison

2.14 The 10-Armed Testbed and Empirical Comparison

152.15 Stationary vs Non-Stationary Rewards

2.15 Stationary vs Non-Stationary Rewards

162.16 Real-World Applications of MAB

2.16 Real-World Applications of MAB

172.17 Contextual Bandits and the Bridge to Full RL

2.17 Contextual Bandits and the Bridge to Full RL

182.18 Self-Assessment and Numerical Practice Problems

2.18 Self-Assessment and Numerical Practice Problems

19Exam Guidance Summary

Exam Guidance Summary

20Key Industry Applications

Key Industry Applications

Postgraduate students in 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.

Recap of the Previous Class and the Agent-Environment Interface

Must-know: The agent-environment interface loop: agent sends action, environment returns (state, reward). The five core elements. Good value estimates are the most important job of an RL learner.

⚠️ Top pitfall: Confusing immediate reward r with long-term value V(s). A state can have low immediate reward but high long-term value.

Self-check: Name the five core elements of RL.

Connects to: 2.2, 2.3

The Two Value Functions: State-Value \(V(s)){} and Action-Value \(Q(s,a)){}

Must-know: V(s) vs Q(s,a): V requires one-step look-ahead, Q does not. Q is preferred in stochastic environments. In practice, Q dominates industry algorithms.

$Q^{π} (s, a) = E_{π} [Σ γ^{k} r_{t + k + 1} ∣ s_{t} = s, a_{t} = a]$

⚠️ Top pitfall: Confusing V and Q. V(s) asks 'how good is this state?', Q(s,a) asks 'how good is this action in this state?'. They are not interchangeable.

Self-check: In the braking-car example, compute Q(s, brake) given P(stop)=0.9 (value 10), P(skid)=0.07 (value 3), P(fail)=0.03 (value -10).

Connects to: 2.7, 2.8, 2.9

Model of the Environment

Must-know: The model p(s',r|s,a) is the joint transition-reward distribution. RL is the MDP problem class; having a model does not mean the problem is solved — planning can still be intractable.

$p (s^{'}, r ∣ s, a) = P r (s_{t + 1} = s^{'}, r_{t + 1} = r ∣ s_{t} = s, a_{t} = a)$

⚠️ Top pitfall: Assuming 'having a model' means 'solving the problem is easy'. Even with a perfect model (e.g., chess rules), optimal policy can be intractable.

Self-check: What is the environment model, and what does it allow you to do?

Connects to: 2.4, 2.1

Model-Based vs Model-Free RL

Must-know: Model-based vs model-free: model-based uses a model (given or learned) to plan; model-free learns directly from interaction. Examples: DP (model-based), Q-learning (model-free).

⚠️ Top pitfall: Assuming model-free means 'no planning at all' — some model-free methods still perform limited planning through learned value functions.

Self-check: Is Q-learning model-based or model-free? Explain.

Connects to: 2.3, 2.5

Course Logistics, Assessment, and Deep RL Preview

Must-know: Course structure: two quizzes (5% each, best of two, no make-ups), two group assignments (25% total). Deep RL = tabular RL + neural network function approximator.

$V_{θ} (s) — p a r am e t er i se d s t a t e - v a l u e f u n c t i o n u s in g n e u r a l n e tw or k w i t h w e i g h t s θ$

⚠️ Top pitfall: Assuming deep RL is fundamentally different from tabular RL. Same problem, same elements — just a different representation.

Self-check: What is the single change that turns tabular RL into deep RL?

Connects to: 2.6, 2.1

Multi-Armed Bandit Problem (MAB): Setup and Motivation

Must-know: MAB: K arms, unknown reward distributions, maximise cumulative reward. Core challenge: exploration vs exploitation.

⚠️ Top pitfall: Thinking one pull per arm is enough to identify the best arm. Noisy samples require multiple pulls.

Self-check: What is the objective in the MAB problem?

Connects to: 2.7, 2.8, 2.9

MAB Is "Stateless": Action-Value Without State

Must-know: MAB uses Q(a) instead of Q(s,a) because there is no state. This notation exception applies only to MAB.

⚠️ Top pitfall: Writing Q(s,a) or V(s) in an MAB problem — both are undefined without a state.

Self-check: Why does MAB write Q(a) instead of Q(s,a)?

Connects to: 2.8, 2.17

The True Value of an Action and Why It Is Unknown

Must-know: q*(a) = E[R_t | A_t = a] is the true expected reward. It is fixed but unknown; Q_t(a) is our running estimate that should converge to it.

$q * (a) = E [R_{t} ∣ A_{t} = a]$

⚠️ Top pitfall: Confusing q*(a) (true, fixed, unknown) with Q_t(a) (estimate, changes over time).

Self-check: What is the difference between q*(a) and Q_t(a)?

Connects to: 2.9, 2.6

Sample-Average Estimation

Must-know: Sample-average formula with indicator notation. Incremental update: Q_{n+1} = Q_n + (1/n)[R_n - Q_n]. Per-arm averaging. Early estimates are noisy and can mislead greedy selection.

$Q_{t} (a) = Σ R_{i} \cdot 1 [A_{i} = a] /Σ1 [A_{i} = a]$

⚠️ Top pitfall: Averaging across all arms instead of per arm. Assuming a few pulls give reliable estimates.

Self-check: Given rewards for arm 2: 0.5, 0.5, -1.5, what is Q(2)?

Connects to: 2.10, 2.11, 2.8

Greedy Action Selection

Must-know: Greedy: A_t = argmax Q_t(a). No exploration — once an arm leads, it's pulled forever.

$A_{t} = a r g ma x_{a} Q_{t} (a)$

⚠️ Top pitfall: Pure greedy gets stuck on early lucky estimates. Only finds optimal action in ~1/3 of problems in the 10-armed testbed.

Self-check: Why does pure greedy fail to find the best arm in most problems?

Connects to: 2.11, 2.12

\(\varepsilon){}-Greedy Action Selection

Must-know: ε-greedy: with prob 1-ε pick greedy action, with prob ε pick uniformly at random. All arms have nonzero selection probability. ε=0 is pure greedy.

$A_{t} = a r g ma x Q (a) w i t h p r o b 1 - ε; u ni f or m r an d o m w i t h p r o b ε$

⚠️ Top pitfall: Setting ε too high wastes steps; too low means insufficient exploration. ε=0.1 is a common starting point.

Self-check: What happens when ε=0? When ε=0.5?

Connects to: 2.12, 2.13, 2.14

Worked Examples: Probability the Greedy Arm Is Selected

Must-know: P(greedy) = 1 - ε + ε/K. P(non-greedy) = ε/K. The greedy arm is always eligible during exploration — split ε/K among all K arms, not K-1.

$P (A *) = 1 - ε + ε / K$

⚠️ Top pitfall: Splitting exploration probability among K-1 arms instead of K. The greedy arm is eligible during exploration too.

Self-check: For K=10, ε=0.1, what is P(greedy arm)?

Connects to: 2.13, 2.14

Formal ε-Greedy Algorithm (Pseudocode)

Must-know: ε-greedy pseudocode: draw u~U(0,1), if u>ε exploit (argmax), else explore (random).

⚠️ Top pitfall: Confusing the threshold ε with something other than the exploration probability — they are identical.

Self-check: Trace the ε-greedy algorithm for 3 steps with ε=0.1 and u values 0.5, 0.08, 0.95.

Connects to: 2.14

The 10-Armed Testbed and Empirical Comparison

Must-know: 10-armed testbed: 2000 runs, 1000 steps. ε=0.1 is winner at 1000 steps (~91% optimal, ~1.5 avg reward). Greedy ~33% optimal. ε=0.01 still climbing. Never set ε=0.

⚠️ Top pitfall: Thinking greedy is 'good enough'. It finds the optimal action only ~1/3 of the time in the 10-armed testbed.

Self-check: In the 10-armed testbed, which ε value performs best at step 1000? Why does ε=0.01 not win?

Connects to: 2.15, 2.11

Stationary vs Non-Stationary Rewards

Must-know: Stationary = fixed distributions. Non-stationary = drifting. Under non-stationarity: constant step size α, ε>0 forever. Sample averages give equal weight to stale data.

$Q_{n + 1} = Q_{n} + α [R_{n} - Q_{n}] (co n s t an t s t e p s i z e f or n o n - s t a t i o na r y)$

⚠️ Top pitfall: Setting ε=0 in non-stationary environments. Using sample averages when rewards drift.

Self-check: Why can't you set ε=0 in a non-stationary environment?

Connects to: 2.16, 2.14

Real-World Applications of MAB

Must-know: Applications: ads, clinical trials, A/B testing. MAB is for stateless problems. Board games, driving, sports require state → contextual bandit or full RL.

⚠️ Top pitfall: Applying MAB to stateful problems (chess, driving). If action value depends on context, MAB is insufficient.

Self-check: Why is chess not a suitable MAB problem?

Connects to: 2.17, 2.15

Contextual Bandits and the Bridge to Full RL

Must-know: MAB: no context. Contextual bandit: context exists, action doesn't affect future context. Full RL: action affects future state. Contextual bandits bridge MAB and full RL.

⚠️ Top pitfall: Confusing contextual bandits with full RL. In contextual bandits, the next context is independent of the action taken.

Self-check: What is the key difference between a contextual bandit and full RL?

Connects to: 2.7, 2.6

Exam Guidance Summary

Must-know: V vs Q, sample-average formula, ε-greedy probability P(A*)=1-ε+ε/K, ε never reaches 0, MAB vs contextual bandit vs full RL classification.

$P (A *) = 1 - ε + ε / K$

⚠️ Top pitfall: Splitting ε among K-1 arms instead of K. Setting ε=0.

Self-check: For K=5, ε=0.2, what is P(greedy arm)?

Connects to: 2.12, 2.14, 2.15

Key Industry Applications

Must-know: Applications: ads, clinical trials, A/B testing, production monitoring. Key reference: Sutton & Barto.

⚠️ Top pitfall: Confusing toy MAB applications (portfolio) with the real thing (which requires state).

Self-check: Name two real-world applications of MAB and explain why each is a stateless problem.

Connects to: 2.16, 2.17

Previous LectureLecture 01 · Introduction to Reinforcement Learning

Next LectureLecture 03 · Multi-Armed Bandit: Advanced Topics

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.

Elements of RL and Multi-Armed Bandits

2.1 Recap of the Previous Class and the Agent-Environment Interface

2.1.1 Definition and Explanation

2.1.2 Symbol Registry

2.1.3 The Five (or Six) Core Elements of RL

2.1.4 Intuition for the Value Number

2.2 The Two Value Functions: State-Value V(s) and Action-Value Q(s,a)

2.2.1 Why Two Flavours of Value

2.2.2 Symbol Registry

2.2.3 Worked Example: 4×4 Grid World

2.2.4 The Simplification Q Provides

2.2.5 The Braking-Car Analogy (Why Q Is Preferred)

2.2.6 Intuition for V vs Q

2.3 Model of the Environment

2.3.1 Definition and Explanation

2.3.2 Symbol Registry

2.3.3 Why a Model Is Useful

2.3.4 Student Doubt: Is It Still RL If You Have a Model?

2.4 Model-Based vs Model-Free RL

2.4.1 Definition and Explanation

2.4.2 A Quick Map

2.4.3 Named Reference

2.5 Course Logistics, Assessment, and Deep RL Preview

2.5.1 Course Structure

2.5.2 Assessment

2.5.3 From RL to Deep RL with a Toy Example

2.5.4 Symbol Registry — Parameterised Value Function

2.6 Multi-Armed Bandit Problem (MAB): Setup and Motivation

2.6.1 The Casino Analogy

2.6.2 Symbol Registry

2.6.3 Formal Setup

2.6.4 Strategy and the Two Key Questions

2.6.5 Why This Topic Matters in an RL Course

2.7 MAB Is "Stateless": Action-Value Without State

2.7.1 The Notation Exception

2.7.2 Symbol Registry — MAB Notation

2.7.3 When Could a State Creep In?

2.8 The True Value of an Action and Why It Is Unknown

2.8.1 Definition of q∗(a)

2.8.2 Symbol Registry

2.8.3 Why Estimation Is Needed

2.9 Sample-Average Estimation

2.9.1 The Idea

2.9.2 Symbol Registry

2.9.3 Incremental Update Formula

2.9.4 Concrete Numerical Mini-Example

2.9.5 Second Numerical Story: The "Secret Truth"

2.10 Greedy Action Selection

2.10.1 Definition

2.11 ε-Greedy Action Selection

2.11.1 Definition and Explanation

2.11.2 Symbol Registry

2.11.3 Interpretation of Common ε Values

2.11.4 Why ε-Greedy Is Popular

2.12 Worked Examples: Probability the Greedy Arm Is Selected

2.12.1 Example 1 — Two Actions, ε=0.5

2.12.2 Example 2 — Four Actions, ε=0.4

2.12.3 Example 3 — Detailed 4-Armed Bandit with ε=0.20

2.12.3 Symbol Registry

2.12.4 Probability of Greedy Action — Formal Derivation

2.13 Formal ε-Greedy Algorithm (Pseudocode)

2.13.1 Procedure

2.13.2 Symbol Registry

2.13.3 Student Doubt on the Random Function

2.14 The 10-Armed Testbed and Empirical Comparison

2.14.1 Setting Up the Testbed

2.14.2 Symbol Registry

2.14.3 Initialisation

2.14.4 The Three Algorithms Compared

2.14.5 Takeaways on Tuning ε

2.15 Stationary vs Non-Stationary Rewards

2.15.1 Definition and Explanation

2.15.2 Intuition: Same User, Different Tastes

2.16 Real-World Applications of MAB

2.16.1 Online Advertising and Product Recommendation

2.16.2 Cloud Configuration and Resource Allocation

2.16.3 Detecting a Biased Coin

2.16.3 Clinical Trials

2.16.4 Simple Portfolio Management

2.16.5 Why Amazon Can Sometimes Surprise Us

2.2 The Two Value Functions: State-Value $V (s)$ and Action-Value $Q (s, a)$

2.8.1 Definition of $q^{*} (a)$

2.11 $ε$ -Greedy Action Selection

2.11.3 Interpretation of Common $ε$ Values

2.12.1 Example 1 — Two Actions, $ε = 0.5$

2.12.2 Example 2 — Four Actions, $ε = 0.4$

2.12.3 Example 3 — Detailed 4-Armed Bandit with $ε = 0.20$

The Two Value Functions: State-Value \(V(s)){} and Action-Value \(Q(s,a)){}

\(\varepsilon){}-Greedy Action Selection