F7EasyPart F · Alignment & Reinforcement Learning

Multi-Armed Bandit: epsilon-Greedy & UCB1

⚡Flashcard Drill➔

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?
Next: Conv2d from Scratch with Stride & Padding →
💡

Core Mental Anchor / Mnemonic

Rank arms by empirical mean + sqrt(2 ln t / N_k) exploration bonus.

📐 Mathematical Derivation & Core Formula

UCB1(k)=μ^k+c2ln⁡tNk(t)\mathrm{UCB1}(k) = \hat{\mu}_k + c \sqrt{\frac{2 \ln t}{N_k(t)}}
### Optimism in the Face of Uncertainty
Unlike ϵ\epsilon-greedy exploration (uniform random choice with probability ϵ\epsilon), UCB1 builds a confidence upper bound from Hoeffding's inequality:
Scorek=μ^k+2ln⁡tNk\mathrm{Score}_k = \hat{\mu}_k + \sqrt{\frac{2 \ln t}{N_k}}
Arms with few pulls (NkN_k 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.
🎯 Drill This Card Now➔
← Prev: KL Divergence & Adaptive PenaltyBack to Part F & All 105Next: Conv2d from Scratch with Stride & Padding →