F7EasyPart F · Alignment & Reinforcement Learning
Multi-Armed Bandit: epsilon-Greedy & UCB1
Balance exploration and exploitation via Hoeffding upper-confidence exploration bonuses.
⏱️ Time:
O(K) 决策单步💾 Space:
O(K)🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
import numpy as np
class UCB1Agent:
def __init__(self, num_arms: int, c: float = 1.0):
self.num_arms = num_arms
self.c = c
self.counts = np.zeros(num_arms, dtype=int)
self.values = np.zeros(num_arms, dtype=np.float64)
self.total_steps = 0
def select_arm(self) -> int:
self.total_steps += 1
# 前 num_arms 步每个臂先试一次
for arm in range(self.num_arms):
if self.counts[arm] == 0:
return arm
# 计算每个臂的 UCB 打分
exploration =
ucb_scores = self.values + exploration
return
def update(self, arm: int, reward: float):
self.counts[arm] += 1
# 增量更新均值
n = self.counts[arm]
self.values[arm] += (reward - self.values[arm]) / n
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: What is the core philosophical difference between Thompson Sampling and UCB1?
💡
Core Mental Anchor / Mnemonic
Rank arms by empirical mean + sqrt(2 ln t / N_k) exploration bonus.
📐 Mathematical Derivation & Core Formula
### Optimism in the Face of Uncertainty
Unlike -greedy exploration (uniform random choice with probability ), UCB1 builds a confidence upper bound from Hoeffding's inequality:
Arms with few pulls ( small) receive a large exploration bonus, which shrinks naturally as evidence accumulates.
Unlike -greedy exploration (uniform random choice with probability ), UCB1 builds a confidence upper bound from Hoeffding's inequality:
Arms with few pulls ( small) receive a large exploration bonus, which shrinks naturally as evidence accumulates.
🔄 Tensor Dimensions & Shape Flow
counts, values -> ucb = values + c * sqrt(2*ln(t)/counts) -> argmax -> chosen arm
🛡️ Numerical Stability & Pitfalls Checklist
- Pull unvisited arms (
count == 0) first before applying the confidence formula. - For dynamic non-stationary click rates, Thompson Sampling provides a Bayesian posterior alternative.
💻 Reference Code Implementation
import numpy as np
class UCB1Agent:
def __init__(self, num_arms: int, c: float = 1.0):
self.num_arms = num_arms
self.c = c
self.counts = np.zeros(num_arms, dtype=int)
self.values = np.zeros(num_arms, dtype=np.float64)
self.total_steps = 0
def select_arm(self) -> int:
self.total_steps += 1
# 前 num_arms 步每个臂先试一次
for arm in range(self.num_arms):
if self.counts[arm] == 0:
return arm
# 计算每个臂的 UCB 打分
exploration = self.c * np.sqrt(2.0 * np.log(self.total_steps) / self.counts)
ucb_scores = self.values + exploration
return int(np.argmax(ucb_scores))
def update(self, arm: int, reward: float):
self.counts[arm] += 1
# 增量更新均值
n = self.counts[arm]
self.values[arm] += (reward - self.values[arm]) / n
🧪 Runnable Assertions & Validation
Copy and run directly in Python / Jupyter:
import numpy as np
agent = UCB1Agent(num_arms=3)
# 模拟拉动
for _ in range(30):
arm = agent.select_arm()
# 臂 2 真实收益最高 (0.9)
reward = 1.0 if (arm == 2 and np.random.rand() < 0.9) else 0.0
agent.update(arm, reward)
assert agent.counts[2] >= agent.counts[0], "收益最高臂应被探索更多"
print("✓ UCB1 探索策略自测通过")🎯 Core Follow-up Inquiries & Reference Answers
Q1:What is the core philosophical difference between Thompson Sampling and UCB1?
UCB1 is a deterministic frequentist upper confidence bound rule, while Thompson Sampling maintains a Bayesian posterior reward distribution (e.g., Beta) per arm and acts greedily on a single posterior draw per round.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.