第 278 题：实现多臂老虎机的UCB，探索参数的自动调整。
题目
实现多臂老虎机的UCB，探索参数的自动调整。
完整讲解
一、多臂老虎机与 UCB
- 多臂老虎机：每轮选一个臂（动作），获得随机奖励；目标在探索（尝试未知臂）与利用（选当前估计最好的臂）间平衡，最大化累积奖励。UCB（Upper Confidence Bound） 给每个臂一个「乐观上界」，选上界最大的臂，实现探索-利用平衡。
二、UCB 公式
- 设臂 $a$ 当前被选了 $n_a$ 次、平均奖励为 $\hat{\mu}_a$。UCB1：$\text{UCB}(a) = \hat{\mu}_a + c \sqrt{\frac{\ln N}{n_a}}$，其中 $N$ 为总轮数。选 $\arg\max_a \text{UCB}(a)$。根号项随 $n_a$ 增大而减小，未充分选的臂上界高，自然被探索。
- 探索参数 $c$：$c$ 大则更倾向探索。可固定（如 2），或随 $N$ 变化；也可用 UCB-tuned 等变体，用方差估计替代固定 $c$。
三、探索参数的自动调整
- 自适应 $c$：根据当前 regret 或置信区间宽度动态调 $c$；若估计已稳定可减小 $c$ 偏向利用。
- Thompson 采样：不直接调 UCB 的 $c$，而是为每个臂维护奖励分布的后验（如 Beta），每轮采样后选最大采样值；等价于概率性探索，无需显式 $c$，也可视为「自动」探索。
- 上下文 bandit：若带特征 $x$，可用 LinUCB、Thompson 与线性模型结合，探索参数可设为与 uncertainty（如 $(x^\top (X^\top X+\lambda I)^{-1} x)^{1/2}$）成比例，实现基于不确定性的自动探索。
- 实践：先设 UCB 的 $c$ 为 1～2，观察探索程度；再结合 A/B 或 regret 曲线调参或切到 Thompson/上下文方法。
面试要点
- 能写出 UCB1 公式 $\hat{\mu}_a + c\sqrt{\ln N / n_a}$ 并解释各项含义；能说明为何能平衡探索与利用。
- 能说清探索参数 $c$ 的作用及自动调整思路（自适应 $c$、Thompson、上下文 uncertainty）。
记忆要点
- UCB：$\text{UCB}(a)=\hat{\mu}_a + c\sqrt{\ln N/n_a}$；选上界最大，$c$ 控探索。
- 自动调整：自适应 $c$、Thompson 采样、上下文 bandit 的 uncertainty；实践先固定 $c$ 再调或换方法。