F7EasyPart F · Alignment & Reinforcement Learning

Multi-Armed Bandit: epsilon-Greedy & UCB1

Mastery Status

Industrial-grade implementation and mathematical foundations of Multi-Armed Bandit: epsilon-Greedy & UCB1.

⏱️ Time Complexity: O(K) 决策单步

💾 Space Complexity: O(K)

💡

Core Mental Anchor / Mnemonic

Master Multi-Armed Bandit: epsilon-Greedy & UCB1: enforce numerical stability, check tensor shapes, and eliminate redundant memory allocations.

📐 Mathematical Derivation & Core Formula

\mathrm{UCB1}(k) = \hat{\mu}_k + c \sqrt{\frac{2 \ln t}{N_k(t)}}

### Mathematical Derivation & Theoretical Principles
Detailed first-principles formulation and architectural mechanics for Multi-Armed Bandit: epsilon-Greedy & UCB1.

Refer to the LaTeX equation above for the core operator definition. The operator is designed to ensure strict numerical bounds, avoiding floating-point overflows and gradient anomalies.

🔄 Tensor Dimensions & Shape Flow

counts, values -> ucb = values + c * sqrt(2*ln(t)/counts) -> argmax -> arm 选择

🛡️ Industrial Numerical Stability & Pitfalls

Ensure proper multi-dimensional tensor broadcasting and keepdims retention.
Enforce numerical guards (eps clamping and overflow thresholds) during exponentiation and division.
Verify train versus eval mode behavioral distinctions (e.g. frozen running statistics and dropout bypass).

💻 Industrial 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 to verify correctness:

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 Architecture Follow-up Q&A

Q1:What are the key trade-offs and memory bottlenecks when deploying Multi-Armed Bandit: epsilon-Greedy & UCB1 in high-throughput inference?

Memory bandwidth (HBM to SRAM I/O) is the primary latency factor. Fusing element-wise operations and avoiding intermediate tensor materialization significantly outperforms naive implementations.

Q2:How does Multi-Armed Bandit: epsilon-Greedy & UCB1 handle extreme numerical boundaries or precision reduction (FP16/BF16/INT8)?

Under low precision, operations must be upcasted to FP32 during accumulation to prevent underflow/overflow, followed by proper scaling and clamping before converting back to the target format.

←Prev: KL Divergence & Adaptive Penalty All 69 Kernels Next: Conv2d from Scratch with Stride & Padding→