不确定性下的乐观原则

原则 ​

算法维护置信集合 $C_t$，在高概率事件上真实参数 ${\theta }^{\ast }\in C_t$，并选择

$$a_t\in \arg \underset{a}{max}\underset{\theta \in C_t}{sup}{V}_{\theta }(a).$$

“乐观”不是盲目选经验均值最大的动作，而是把统计不确定性纳入可证明覆盖的上界。已充分观测的动作区间变窄；少观测动作上界仍高，因而会被主动探索。

在随机 bandit 中，可为臂 $i$ 使用 ${\hat{\mu }}_i(t)+r_i(t)$。分析分两步：先用集中界与并集界证明所有臂、时刻的真实均值都在区间内；再在该好事件上证明若次优臂仍被选择，其半径必与 gap 同量级，选择次数因此受控。

置信集失配会破坏整个链条。重尾、非平稳或自适应选择若未被构造区间的方法处理，乐观值只是数值较大的启发式。该原则也不绑定某个 UCB 公式；线性 bandit 与强化学习使用不同几何的 $C_t$，共同点是“覆盖 + 乐观选择 + 被选择后收缩”。

考虑两臂当前经验均值分别为 $0.55$ 与 $0.40$，半径为 $0.05$ 与 $0.25$。贪心会选第一臂；乐观上界分别为 $0.60$ 与 $0.65$，因此先试观测少的第二臂。若它实际较差，新增样本会缩小半径并让其退出；若实际更好，这次探索避免了长期锁定错误臂。

证明中通常在失败概率上分配预算，例如让第 $t$ 时刻每个臂的失败概率为 $O(\delta /(K{t}^2))$，再利用 $\sum _{t}1/t^2<\mathrm{\infty }$ 对无限时刻求并。只为每个固定 $t$ 建一个 $95\mathrm{\%}$ 区间，并不能推出“所有时刻同时覆盖 $95\mathrm{\%}$”；选择偏差也要求区间适配自适应采样。

乐观原则的遗憾证明通常利用一条“夹逼”：在置信好事件上，真实最优动作的价值不超过其乐观值，而算法选择动作的乐观值又不小于它；因此瞬时遗憾至多是所选动作置信宽度的若干倍。随后只需累计这些宽度，并证明被选择次数越多宽度越小。覆盖失败事件则至多贡献 $\delta T$ 量级的期望损失。

它与 Thompson sampling 的接口不同：后者从后验或代理分布采样参数，不逐轮最大化置信集上界。两者都以不确定性驱动探索，但“随机概率匹配”不能被重述成确定的 UCB 乐观选择；各自保证依赖不同的校准条件。

参考资料

• Auer, Cesa-Bianchi, Fischer, 2002.
• Lattimore, Szepesvári, Bandit Algorithms, 2020.