Multi-Armed Bandits

Multi-Armed Bandit vs Full MDP

  FULL MARKOV DECISION PROCESS (MDP)            MULTI-ARMED BANDIT (MAB)
  State s_t ──► Action a_t ──► Reward r_{t+1}   Action a_t ──► Reward r_t (Stateless!)
                └──────► Next State s_{t+1}

Multi-Armed Bandits are Stateless Single-Step MDPs:

• No state transitions $P(s' \mid s, a)$.
• Focuses entirely on finding the optimal arm $a^*$ among $K$ candidate choices under stochastic reward distributions $P(R \mid a)$.

Why Bandits Replace Static A/B Testing

  STATIC A/B TEST (Fixed 50/50 Allocation for 14 Days):
  Variation A (Winning):  50% Traffic ──► 10,000 Conversions
  Variation B (Losing):   50% Traffic ──► 2,000 Conversions  <-- Wasted 50% traffic on losing B!

  BANDIT ALGORITHM (Dynamic Traffic Allocation):
  Day 1: 50% A / 50% B ──► Day 3: 75% A / 25% B ──► Day 7: 95% A / 5% B
  Minimizes Opportunity Cost & Cumulative Regret!

Regret Bounds

Let $\mu^* = \max_{a} \mu_a$ be the expected reward of the true optimal arm.

Suboptimal arm gap $\Delta_a = \mu^* - \mu_a$.

$$\text{Cumulative Regret}(T) = \sum_{a=1}^K \mathbb{E}[N_a(T)] \cdot \Delta_a$$

• Naive Random Search: Regret scales linearly $O(T)$ (infinite opportunity cost).
• Optimal Bandit (UCB / Thompson): Regret scales logarithmically $O(\ln T)$ (Lai & Robbins lower bound).

Say this out loud

"Multi-Armed Bandits model stateless decision-making across K choices to maximize cumulative reward. Bandits replace static A/B testing by dynamically routing traffic to winning variations in real-time, minimizing cumulative regret. Optimal algorithms like Thompson Sampling and UCB achieve logarithmic O(ln T) regret bounds."

Follow-ups to expect

• What is Non-Stationary Bandit? A bandit setting where arm reward distributions change over time (e.g., news trends). Solved using Discounted UCB or Sliding-Window Thompson Sampling, giving higher weight to recent observations.
• What is Contextual Bandit? A bandit extension where action rewards depend on an observed user context vector $x_t$ (e.g. user age, location, device), bridging MABs and full RL recommendation engines.