UCB1 乐观估计

UCB1 是频率派乐观的探索算法:每轮选择置信上界最大的臂 $a_t = \arg\max_a \left[ \hat{\mu}_a + \sqrt{\frac{2\ln t}{n_a}} \right]$,其中 $\hat{\mu}_a$ 是臂 $a$ 的经验均值、$n_a$ 是其被选次数、$t$ 是总轮数。探索项 (confidence bonus) $\sqrt{2\ln t / n_a}$ 由 Hoeffding 不等式导出,随 $n_a$ 增大而收缩、随 $t$ 增大而扩张:被充分探索的臂上界接近均值(利用),被冷落的臂上界高(探索),从而自动平衡探索-利用。

推荐/广告冷启动、多臂实验、任何需要无参、实现简单且带理论保证的在线决策;面试高频考"手算 UCB 选臂"和 $O(\ln T)$ regret 推导。

ε-greedy 的探索与反馈无关、以固定概率浪费样本;UCB 用置信上界把探索集中在"可能最优"的臂上,regret 达到最优的 $O(\ln T)$(与 Thompson 采样同量级),且不需要贝叶斯先验,纯频率派即可部署。

UCB1 公式中每项的含义?为何 $\sqrt{2\ln t / n_a}$ 是最优探索量 (Hoeffding)?

数值题: $t=100$, 3 臂统计 $(n_a, \hat{\mu}_a)$: 臂1 (60, 0.6)、臂2 (30, 0.5)、臂3 (10, 0.4), 手算 UCB 值并指出选哪个臂?

推导 UCB regret $O(\ln T)$ 的思路:为什么坏臂被选的次数有 $O(\ln T)$ 上界?

UCB 与 Thompson 采样、ε-greedy 的探索方式本质区别?

UCB1 的局限与扩展:非平稳环境、奖励分布假设、UCB1-tuned / sliding-window UCB?