Bandit Algorithms Multi-Armed Bandits Exploration

# Bandit Algorithms: Multi-Armed Bandits & Exploration

## Introduction & Motivation

Bandits: sequential decision problem. K arms; exploit-explore. UCB, Thompson Sampling, epsilon-greedy. Applications: A/B testing, recommendations, online learning.

Motivation: Balance exploration and exploitation optimally.

Applications: Online learning, A/B testing, recommendations.

---

## Core Concepts & Theory

### Regret

Cumulative suboptimality measure.

### Upper Confidence Bound (UCB)

Optimistic arm selection.

### Thompson Sampling

Bayesian posterior sampling.

---

## Mathematical Formulation

Epsilon-greedy:
$$a_t = \begin{cases} \arg\max_a \mu_a & ext{w.p. } 1-\epsilon \\ ext{random} & ext{w.p. } \epsilon \end{cases}$$

UCB:
$$a_t = \arg\max_a (\mu_a + \sqrt{\frac{\ln t}{N_a}})$$

Thompson Sampling:
$$ heta_a \sim ext{Posterior}(D_a), \quad a = \arg\max_a \mathbb{E}[ heta_a]$$

---

## Advanced Theory & Extensions

### Contextual Bandits

Features influence rewards.

### Dueling Bandits

Pairwise feedback.

### Restless Bandits

Changing rewards.

---

## Computational Considerations

Epsilon-greedy: O(1).

UCB: O(K).

Thompson: O(sample_complexity).

---

## Practical Implementation Strategies

### Epsilon Schedule

Decay exploration.

### Confidence Intervals

Uncertainty quantification.

### Batching

Group decisions.

---

## Benchmark Problems

Synthetic Bandits: Controlled settings.

Online Ads: CTR prediction.

News Recommendation: Contextual bandits.

---

## Key Challenges & Limitations

### Exploration-Exploitation

Hard to balance optimally.

### Regret Bounds

Prove theoretical limits.

### Non-Stationary

Rewards change over time.

---

## Hyperparameter Tuning

Epsilon: 0.01-0.1.

UCB coefficient: sqrt(ln(t)/N).

Thompson priors: Beta, Gaussian.

---

## Summary & Key Takeaways

Bandit Algorithms via UCB and Thompson Sampling enable optimal exploration-exploitation through confidence bounds and posterior sampling.

Principles:
1. Exploit: best arm.
2. Explore: uncertain arms.
3. UCB: optimistic selection.
4. Thompson: posterior sampling.
5. Regret: performance measure.

---

---

## Appendix: Practical Labs

### Lab 1: Epsilon-Greedy

import numpy as np

def epsilon_greedy_bandit(rewards, epsilon=0.1, episodes=1000):
 """Epsilon-greedy bandit strategy"""
 num_arms = len(rewards)
 estimates = np.zeros(num_arms)
 counts = np.zeros(num_arms)
 
 for _ in range(episodes):
 if np.random.rand() < epsilon:
 arm = np.random.randint(num_arms)
 else:
 arm = np.argmax(estimates)
 
 reward = rewards[arm] + np.random.randn()
 counts[arm] += 1
 estimates[arm] += (reward - estimates[arm]) / counts[arm]
 
 return estimates

# Test
np.random.seed(42)
true_rewards = np.array([0.1, 0.5, 0.3, 0.2])

estimates = epsilon_greedy_bandit(true_rewards)

assert estimates.shape == true_rewards.shape, "Estimates shape"
print("✓ Epsilon-greedy working")

if __name__ == "__main__":
 print("Lab 1: EpsilonGreedy - PASSED")

### Lab 2: UCB Algorithm

import numpy as np

def ucb_bandit(rewards, episodes=1000):
 """Upper Confidence Bound bandit"""
 num_arms = len(rewards)
 counts = np.zeros(num_arms)
 estimates = np.zeros(num_arms)
 
 for t in range(1, episodes + 1):
 # UCB
 ucb_values = estimates + np.sqrt(np.log(t) / (counts + 1e-8))
 arm = np.argmax(ucb_values)
 
 reward = rewards[arm] + np.random.randn()
 counts[arm] += 1
 estimates[arm] += (reward - estimates[arm]) / counts[arm]
 
 return estimates

# Test
np.random.seed(42)
true_rewards = np.array([0.1, 0.5, 0.3])

estimates = ucb_bandit(true_rewards)

assert estimates.shape == true_rewards.shape, "Estimates shape"
print("✓ UCB working")

if __name__ == "__main__":
 print("Lab 2: UCB - PASSED")

### Lab 3: Regret Computation

import numpy as np

def compute_regret(arm_rewards, true_best):
 """Compute cumulative regret"""
 regret = 0
 for reward in arm_rewards:
 regret += true_best - reward
 return regret

# Test
np.random.seed(42)
rewards = np.random.rand(100)
best_reward = 0.9

regret = compute_regret(rewards, best_reward)

assert regret >= 0, "Regret non-negative"
print("✓ Regret computation working")

if __name__ == "__main__":
 print("Lab 3: Regret - PASSED")

### Lab 4: Thompson Sampling

import numpy as np

def thompson_sampling_beta(episodes=1000, num_arms=3):
 """Thompson Sampling with Beta priors"""
 alpha = np.ones(num_arms) # Beta params
 beta = np.ones(num_arms)
 
 for _ in range(episodes):
 # Sample from posterior
 theta = np.random.beta(alpha, beta)
 arm = np.argmax(theta)
 
 # Simulate reward (Bernoulli)
 reward = np.random.rand() < theta[arm]
 
 # Update posterior
 if reward:
 alpha[arm] += 1
 else:
 beta[arm] += 1
 
 return alpha / (alpha + beta)

# Test
np.random.seed(42)

posterior = thompson_sampling_beta(episodes=100)

assert posterior.shape == (3,), "Posterior shape"
assert np.all((posterior >= 0) & (posterior <= 1)), "Valid probabilities"
print("✓ Thompson Sampling working")

if __name__ == "__main__":
 print("Lab 4: ThompsonSampling - PASSED")