Multi-Armed Bandit

Definition

$k$-Armed Bandit Problem

A simplified RL problem with only one state. At each time step, you choose one of $k$ actions (“arms”), and receive a reward drawn from a stationary probability distribution that depends on the action selected. The goal: maximize total reward over time.

The Name

Named after slot machines (“one-armed bandits”) in casinos. Imagine facing $k$ slot machines, each with an unknown payoff distribution. Which do you play, and how do you decide?

Action Values

True Action Value

$q_{\ast }(a)=\mathbb{E}[R_t\mid A_t=a]$

The true expected reward for action $a$. Unknown to the agent.

Sample-Average Estimate

$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}}$

Average of rewards received for action $a$ so far. Converges to $q_{\ast }(a)$ by Law of Large Numbers.

Action Selection Methods

Greedy

$A_t=\arg {\max }_a{Q}_t(a)$ Pure exploitation. Can get stuck on suboptimal action.

ε-Greedy

Pick greedy action with probability $1-\epsilon$, random action with probability $\epsilon$.

UCB

$A_t=\arg {\max }_a\left[Q_t(a)+c\sqrt{\frac{\ln t}{N_t(a)}}\right]$ Adds an exploration bonus that shrinks as an action is tried more often. $c$ controls exploration degree. More principled than ε-greedy — preferentially explores uncertain actions.

Optimistic Initial Values

Initialize $Q_0(a)$ high (e.g., +5 when rewards are around 0). Encourages initial exploration because early actual rewards will be “disappointing,” causing the agent to try other actions.

Gradient Bandit

Learn a preference $H_t(a)$ for each action, select via softmax: ${\pi }_t(a)=\frac{e^{H_t(a)}}{{\sum }_b{e}^{H_t(b)}}$

Update: $H_{t+1}(a)=H_t(a)+\alpha (R_t-{\bar{R}}_t)(1_{A_t=a}-{\pi }_t(a))$ where ${\bar{R}}_t$ is the average reward baseline.

Incremental Update

Incremental Action-Value Update

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

General form: $\text{NewEstimate}\leftarrow \text{OldEstimate}+\text{StepSize}\times [\text{Target}-\text{OldEstimate}]$

For nonstationary problems, use constant step-size $\alpha$ instead of $1/n$: $Q_{n+1}=Q_n+\alpha [R_n-Q_n]$ This gives exponentially decaying weights to old rewards (more weight on recent).

Relation to Full RL

Bandits as Special Case

A bandit is a 1-state MDP. There’s no state transition, no delayed reward, no sequential planning. It isolates the Exploration vs Exploitation problem.

Connections

• Special case of: Markov Decision Process (single state)
• Core problem: Exploration vs Exploitation
• Selection methods: Epsilon-Greedy Policy, Upper Confidence Bound
• Extended to: Contextual bandits (state-dependent), full MDPs

Appears In

• RL-L01 - Intro, MDPs & Bandits
• RL-Book Ch2 - Multi-Armed Bandits
• RL-ES01 - Exercise Set Week 1