Korean, Edit

第 11-1 章。多臂强盗

推荐帖子：【算法】【算法目录】(https://jb243.github.io/pages/1278)

1. 概述

2. UCB

3. 汤普森采样

4. 提前停止问题

1.概述

⑴ 概述

① 问题定义：选择收益最高的最优臂

② 以下情况尤其必要

○ 目标函数计算困难时（黑盒算法）

○ 当没有明确的解析形式时

○ 存在奇异值时

○ 当函数不可微时

○ 当数据噪声很大时

⑵ 两种策略的权衡

① 利用： 使用从当前数据得出的经验平均值最大化奖励

② 探索： 改进经验均值以匹配真实均值

③ 如果初始数据偏离真实分布而忽视探索，则错误的判断无法得到纠正

⑶ 类型 1. 贝叶斯优化

① 【贝叶斯定理】(https://jb243.github.io/pages/1623#:-,,-(Bayestheroem))

○ 给出各臂的奖励分布的先验分布（代理模型）

○ 高斯过程常被用作先验模型

○ 每次观察到奖励时都会获得后验分布

② 获取功能：进行采样以最大化下一个奖励

○ 所有采集函数根据后验分布计算均值μ(x)和方差σ2(x)，通过此设计探索策略

○ 类型 1. EI（预期改进）：EI(x) 的第二个公式仅在使用高斯过程时成立

○ 注意，Φ和𝜙是标准正态分布的CDF和PDF，Z标准化x

○ λ 越高，探索越多

○ 类型 2. MPI（最大改进概率）

○类型 3. UCB

③ 高斯过程：贝叶斯优化时假设正态分布

受保护_0

④ 超参数优化

○ 使用最大似然估计 (MLE) 探索最大化边际似然（数据 X 和 y 出现的概率）的超参数

○ 边际似然和高斯过程超参数定义如下

○ 优点：改善欠拟合和过拟合

⑷ 类型 2. 随机多臂老虎机

① 特征1. 在线决策：每次t = 1,…,T时从N个臂中选择第i个臂> ② 特征2. 随机反馈：每只手臂提供的奖励遵循固定但未知的分布

③ 功能3. Bandit Feedback：在每个时间步，只有所选手臂的奖励可见

④ 目标：在T步内最大化累积预期奖励

⑤ 最大化奖励相当于最小化后悔 = μ* - μ_t

⑥ 强盗：指失败后夺走的意思，像强盗一样

⑦ 示例 1. N 个臂中选择第 n 个臂时的置信状态更新方程

⑧ 示例 2. 汤普森采样

2. UCB

⑴ 与 Thompson Sampling 一起，是使用最广泛的老虎机算法之一

⑵配方

① 时间 t 期间第 i 组的经验平均值

○ 分子：第 i 臂获得的总奖励

○ I{is = i}：只有当is = i时才输出1，否则输出0

○ ni,t: 直到时间 t 为止 i 被选择的次数

② UCB（置信上限）

○ 乐观： 意思是大概率认为高于实际预期值

○ 高概率：99.9%以上

③ 选择每一步UCB最大的手臂

④ 在每个时间步更新经验均值和 UCB：UCB 表示的不确定性随着每次观察而减小

⑶ 收敛性证明

①定理

对于所有 N > 1，如果策略 UCB 在具有任意奖励分布 P₁, …, P_N 且支持 [0, 1] 的 N 个臂上运行，则在任意次数的 T 次游戏后其预期后悔

最多是

其中 μ₁, …, μ_N 是分布 P₁, …, P_N 的均值。

② 证明

令 c_t,s := √(2log(t) / s)。还定义如下 X̄_nⁱ = (1/n) Σ_{t=1 to n} X_t 其中 {X_tⁱ}_t∈ℕ 是连续播放时第 i 组奖励的随机过程。对于任何手臂 i，我们在任何比赛序列上设置 UCB_i(T) 的上限。令 I_t 表示在时间 t 玩的手臂，那么我们可以得到 ℓ 是任意正整数

» 现在我们观察到 X̄_s* + c_t,s ≤ X̄_siⁱ + c_t,si 意味着至少必须满足以下条件之一： X̄_s* ≤ μ* - c_t,s， X̄_siⁱ ≤ μ_i + c_t,si, μ* < μ_i + 2c_t,si。否则，存在矛盾：X̄_s* + c_t,s > μ* ≥ μ_i + 2c_t,si > X̄_siⁱ + c_t,si。我们可以通过使用 Azuma-Hoeffding 不等式的版本来限制前两个事件的概率，因为 sX̄_s* - sμ* 和 s_iX̄_siⁱ - s_iμ_i 在 0 处的边际为零，增量为 [-μ, 1分别为 - μ] 和 [-μ_i, 1 - μ_i]。然后产生以下结果

另请注意，我们有

s_i ≥ 8 log(T) / Δ_i² （因为 T ≥ t）。因此，如果我们取 ℓ = ⌈8 log(T) / Δ_i²⌉，那么我们就不能得到 μ* < μ_i + 2c_t,si 并且只有前两个不等式成立。这样，我们得到

因此，根据 𝔼[n_i,T] ≤ 𝔼[UCB_i(T)] ≤ 8log(T) / Δ_i² + C，我们得到 Regret(T) ≤ 8 log(T) / Δ_i + CΣΔ_i。

③结论

○ 每次后悔收敛到0：意味着每一个选择都成为最好的选择

○ 仅使用经验平均值并不能保证最佳臂选择

○ 可能导致永远无法尝试最佳手臂

⑷ UCB 与 Thompson 抽样比较

① **共性 1. **总遗憾为 O(log T)：每次遗憾收敛到 0，为 O(log T / T)

② 差异 1. Thompson 采样通常优于 UCB：UCB 是一种稍微保守的算法，收敛速度较慢

③ 差异 2. UCB 是确定性的，而 Thompson 采样是概率性的（随机的）

3.汤普森采样

⑴ 概述

①最古老的老虎机算法：Thompson于1933年提出

② 自然高效的启发式算法

⑵ 工艺流程

① 保持对每个手臂参数的信念（例如，平均奖励）

○ 使用先验分布，例如 Beta 分布 或 高斯分布

② 从每个先验分布中提取估计奖励

○ 简单抽样，不提取期望值

○ 观测值越少，方差越大，提取越容易

③ 选择估计奖励最大的arm，观察其后验奖励

○ 后验分布必须始终由研究人员维护

④ 使用贝叶斯方法用后验更新先验信念

⑤ 两种模式下也能正常工作

⑶ 示例： 使用 Beta 分布进行 Thompson 抽样

① 以 Beta(1, 1) 作为所有臂的先验信念

② 对于每个时间 t，

○ 先验：Beta(α, β)

○ 每臂独立采样 θi,t

○ 选择它 = argmaxi θi,t

○ Beta(α+1, β)：观察到 1 时

○ Beta(α, β+1): 观测到 0 时

⑷ 示例： 使用高斯分布的 Thompson 采样

① 以 N(0, ν2) 作为所有臂的先验信念> ② 对于每个时间 t，

○ 先验：N(0, ν2)

○ 每臂独立采样 θi,t

○ 选择它 = argmaxi θi,t

○ 更新所选臂的经验平均值 µˆ（后验）：其中 n 是独立观测值的数量

⑸ 收敛性

① 经过一定数量的步骤后，两个手臂之间的良好分离最终会产生最佳手臂

② 贝塔分布

③ 高斯分布：基于Azuma-Hoeffding不等式

⑹ UCB 与 Thompson 抽样比较

① 共性 1. 总后悔是 O(log T)：每次后悔收敛到 0，为 O(log T / T)

② 差异 1. Thompson 采样通常优于 UCB：UCB 是一种稍微保守的算法，收敛速度较慢

③ 差异 2. UCB 是确定性的，而 Thompson 采样是概率性的（随机的）

4.提前停止问题

⑴ 秘书问题

① 问题

受保护_1

② 证明

⑵ 未应用贝叶斯优化的提前停止（最优停止）问题

输入：2021.12.10 00:52

编辑时间：2024.11.21 15:30