Module 2

Bandit Problem
Content
• Bandit Problems: k-armed bandit, Stochastic rewards,
• Action-value methods
• Exploration vs Exploitation,
• Bandit Algorithms:
• ε-greedy method,
• Optimistic initial values,
• Softmax / Boltzmann exploration,
• Upper Confidence Bound (UCB),
• Thompson Sampling
• Variant of Bandit: Non-stationary bandits, Stationary vs non-stationary environments
• Relationship between MAB and RL Non-stationary bandits,
• Real-world applications:
• Online advertising: A/B testing,
• Recommendation systems,
• Clinical trials.
Bandit Problems

• Introduction to Bandit Problems

• Multi-Armed Bandit (MAB)
• k-armed bandit problem
• Stochastic rewards
Bandit Problem
Bandit problems are problems in the area of sequential selection of
experiments, and they are related to stopping rule problems through the
theorem of Gittins and Jones
A bandit problem is a simplified RL setting where:
• There is only one state
• The agent repeatedly chooses from k actions (arms)
• Each action gives a stochastic reward
• Goal: maximise cumulative reward
Example: Slot machines in a casino
Slot Machines
 Aspect Single-armed Bandit Multi-armed Bandit
Number of actions 1 Multiple
When / how long to Which action to
Decision involved
act choose
Exploration needed No Yes
Balancing exploration
Main challenge Estimating reward
& exploitation
Estimation, stopping ε-greedy, UCB,
Typical algorithms
rules Thompson Sampling
Single-armed bandit: “How good is this one option?”
Multi-armed bandit: “Which option should I pick right now?”
MAB
• A Multi-Armed Bandit (MAB) problem consists of:
• Multiple actions (arms)
• Each action provides a reward drawn from an unknown
probability distribution
• The agent must learn which arm gives the highest reward
• MAB is Important because:
• It captures the exploration vs exploitation dilemma
• Forms the foundation of Reinforcement Learning
• Used in many real-world online decision problems
Key Characteristics

Feature Description
States Single state
Actions Multiple (arms)
Reward Random (stochastic)
Transitions None
Learning goal Maximize total reward
 k-Armed Bandit Problem
• The k-armed bandit problem is a special case of MAB where:
• The agent has exactly k possible actions
• Each action corresponds to pulling one arm
𝐴={𝑎1,𝑎2,...,𝑎𝑘}
• In K-arm Bandit,
1. Agent selects one of the k arms
2. Environment returns a reward
3. Reward is observed, but the reward distribution is unknown
4. Process repeats
Eg:
• k = 5 slot machines
• Each machine gives a different average reward
• Agent must discover the best machine by trial and error
Mathematical Representation

•Let:
• 𝑅𝑡 be the reward at time t
• Q(a) be the expected reward of action a
Stochastic Reward
• A stochastic reward means that:
• The reward is random
• The same action may give different rewards at different times
• Rewards follow an unknown probability distribution
• Example: Pulling the same slot machine:
• First time → reward = 5
• Second time → reward = 2
• Third time → reward = 7

But the expected value remains constant (stationary case).

 Concept Explanation
MAB General framework
k-armed bandit Specific case with k actions
Reward uncertainty in each
Stochastic reward
arm

Each arm in a k-armed bandit has its own stochastic reward

distribution.
IMP
• Bandit problem: A learning problem where an agent selects
actions to maximize cumulative reward without state
transitions.
• Multi-Armed Bandit: A problem involving multiple actions
with unknown stochastic rewards.
• k-armed bandit: A bandit problem with exactly k possible
actions.
• Stochastic reward: A reward that is random and drawn from a
probability distribution.
Greedy and Non-Greedy Actions
At any time step, based on current estimates:
• The action with the highest estimated value is called the greedy action
• Other actions are called non-greedy actions
Exploitation
• Selecting the greedy action
• Maximizes immediate (one-step) reward
• Uses current knowledge
Exploration
• Selecting a non-greedy action
• Improves knowledge of uncertain actions
• May reduce short-term reward
 Exploration vs Exploitation Conflict

Aspect Exploration Exploitation

Purpose Learn more Earn more now
Reward Lower short-term Higher short-term
Benefit Higher long-term Immediate gain
Risk Uncertain Limited learning

Exploring may reduce reward now, but increase total reward in

the long run.
Time and Uncertainty
Whether exploration or exploitation is better depends on:
• Accuracy of action-value estimates
• Uncertainty in estimates
• Number of remaining time steps
If many time steps remain, exploration becomes more valuable
because the knowledge gained can be exploited repeatedly
later.
Methods for Balancing Exploration and
Exploitation

• ε-greedy methods
• Upper Confidence Bound (UCB)
• Bayesian approaches (Thompson Sampling)
Revision for done so far
• The n-armed bandit problem involves choosing among
n actions with unknown stochastic rewards.
• Each action has a fixed but unknown expected value.
• The main challenge is balancing exploration and
exploitation.
• The goal is to maximize cumulative reward over time.
• The n-armed bandit is a simplified but fundamental
reinforcement learning problem.
Mathematical Details of Bandit Algorithms
Let:
• 𝐴 = 1 2 … 𝑛 be the set of actions (arms)
• 𝑅𝑡 be the reward at time 𝑡
• 𝑄𝑡 𝑎 be the estimated value of action 𝑎at time 𝑡
• 𝑁𝑡 𝑎 be the number of times action 𝑎has been selected up to time 𝑡
ε-Greedy Method
Action Selection Rule
At each time step 𝑡:

• 𝜀 ∈ 0 1 controls exploration
• Small 𝜀→ more exploitation
• Large 𝜀→ more exploration
ε-Greedy Method: Action-Value Update Rule
• Using sample-average method:

• Guarantees exploration
• Simple but may explore too much even when estimates are accurate
Example Greedy Policy
• Suppose we have a robot that needs to navigate through a maze to reach a goal.
The robot has a value function that estimates the reward for each action (moving
up, down, left, or right).
• The value function is: Action - Reward
Up - 10
Down - 5
Left - 8
Right - 12
• A greedy policy would choose the action with the highest reward, which is "Right"
with a reward of 12.
• The robot would always move right, regardless of the current state of the maze.
 Example Greedy Policy (1)
• Epsilon is hyper parameter that controls trade-off between
exploration and exploitation
• Exploration rate: Epsilon determines the probability of choosing a
random action (exploration) instead of the greedy action
(exploitation).
• Range: Epsilon is typically set between 0 and 1.
• 1. ε = 0: Pure exploitation (always choose the greedy action).
• 2. ε = 1: Pure exploration (always choose a random action).

• Common values: Typical values for epsilon include 0.1, 0.01, or

0.001, depending on the problem and the desired level of
exploration.
• With a low epsilon value, the agent explores less and focuses on
exploiting the current knowledge.
Epsilon Greedy Policy
• To use an epsilon-greedy policy with ε = 0.1. This means that 10% of
the time, the robot will choose a random action instead of the greedy
action.
• Action - Reward
Up -10
Down - 5
Left - 8
Right - 12
• With ε = 0.1, the robot will choose the greedy action (Right) 90% of
the time and a random action 10% of the time.
Epsilon Greedy Policy (1)
• Possible scenario:
1. The robot is at the starting point of the maze.
2. It chooses the greedy action (Right) with probability 0.9.
3. With probability 0.1, it chooses a random action (say, Up).
4. If it chooses Up, it moves up and updates its value function.
5. If it chooses Right, it moves right and updates its value function.
• By using an epsilon-greedy policy, the robot balances exploration
(choosing random actions) and exploitation (choosing the greedy
action).
• This helps the robot discover new paths and avoid getting stuck in
local optima.
Epsilon Greedy Policy (1)
• Epsilon Greedy policy is a policy of choosing action using the current
Q value estimation
• with probability 1 - ε choose the action which has a highest Q value.
• with probability ε choose any action at random.
Greedy Policy & Epsilon Greedy Policy
• Greedy policies focus on exploiting current knowledge,
• while epsilon-greedy policies balance exploration and exploitation.
Note: In Epsilon Greedy policy , 0<Epsilon<1
(Epsilon  Exploration Probability, 1- Epsilon Exploitation Probability)
Solved Problem
Question: You have 3 slot machines (arms). Each arm has a different, unknown probability
of paying out a reward of 1.
Your goal is to figure out which arm is the best (has the highest payout probability) and
maximize your total reward over time.
Solution:
Setup:
Arms: A, B, C
Rewards: 0 or 1 (1 for a win, 0 for a loss)
Epsilon (ε): 0.1 (10% chance of exploring)
Q-values: Keep track of our estimated average reward for each arm in Q-values: Q(A),
Q(B), Q(C).
Initially, we set all Q-values to 0.
Update Q-value
Q(A) = Q(A) + (1/n) * (R - Q(A))
Q(A): The estimated value (average reward) of taking action A.
This is what we're updating.
A: The specific action taken (in our example, the arm pulled).
n: The number of times action A has been taken so far
(including the current time).
R: The reward received after taking action A.
Iteration 1
1. Epsilon-greedy: Generate a random number between 0 and 1. Let's say it's 0.7.

2. Exploitation: Since 0.7 > ε (0.1), we exploit. Currently, all Q-values are 0, so we
can choose any arm. Let's choose arm A arbitrarily.

3. Action: Pull arm A.

4. Reward: Let's say arm A gives a reward of 0.

5. Update Q-value: Q(A) = Q(A) + (1/1) * (0 - Q(A)) = 0 + 1 * (0 - 0) = 0 (The 1/1

is because this is the first time we've tried arm A).
Iteration 2

1. Epsilon-greedy: Generate a random number. Let's say it's 0.05.

2. Exploration: Since 0.05 < ε (0.1), we explore.
3. Action: Choose a random arm. Let's say we choose arm C.
4. Reward: Let's say arm C gives a reward of 1.
5. Update Q-value: Q(C) = Q(C) + (1/1) * (1 - Q(C)) = 0 + 1 * (1 - 0) = 1
 Iteration 3
1. Epsilon-greedy: Generate a random number. Let's say it's 0.3.
2. Exploitation: Since 0.3 > ε (0.1), we exploit.
3. Action: We choose the arm with the highest Q-value. Currently,
Q(A) = 0, Q(B) = 0, and Q(C) = 1. So we choose arm C.
4. Reward: Let's say arm C gives a reward of 0 this time.
5. Update Q-value: Q(C) = Q(C) + (1/2) * (0 - Q(C)) = 1 + 0.5 * (0 -
1) = 0.5 (The 1/2 is because this is the second time we've tried arm
C).
Iteration 4

1. Epsilon-greedy: Generate a random number. Let's say it's 0.9.

2. Exploitation: Since 0.9 > ε (0.1), we exploit.
3. Action: We choose arm C again, as it still has the highest Q-value.
4. Reward: Let's say arm C gives a reward of 1.
5. Update Q-value: Q(C) = Q(C) + (1/3) * (1 - Q(C))
= 0.5 + (1/3) * (1 - 0.5) = 0.667 (approximately)
Conclusion for Epsilon Greedy Method
• Over time, the Q-values for the better arms will tend to increase.
• The epsilon-greedy method ensures that we keep exploring even after we've
found a seemingly good arm.
• This helps us avoid getting stuck in local optima.
• The update rule for Q-values is a simplified version of the update rule used
in Q-learning.
• It's an average of the rewards received so far for that arm.