CMSC 5728 Decision Analysis & Game Theory - Lecture 10
- Stochastic MAB: Explore-then-Exploit (ETE or ETC)
- Regret of ETE
Stochastic MAB: Explore-then-Exploit (ETE or ETC)
- 我们讨论了我们需要平衡 exploration 与 exploitation
- 定义 m ∈ N 为我们需要发现一个 arm 的次数
- 两个阶段
- 阶段1：发现每个 arm 次数为 m ≥ 1（exploration）
- 阶段2：在阶段1的结尾选择能够给我们最大 reward 的 arm，并且我们会一直选择这个 arm 直到轮数 T
- 令 rt 为学习者在时间点 t 获得的 reward 的随机变量，并且 ni(t) 为学习者在时间点 t 结束之前选择 arm i 的总次数
- 我们有
Regret of ETE
假设 arm 1 是最好的 arm （
）cumulative reward A(T) 与 regret R(T) 是
取 E[R(T)] 的期望，我们有
如果我们能上限
，那么我们就可以上限 
Theorem 3.1
对于上面的 ETE 算法，假设 reward Vi 是 1-sub-Gaussian (或 Vi~SG(1)，即 σ = 1)，对于 i ∈ [N]，期望 regret E[R(T)] 的上限是
- 假设 reward Vi 是 1-sub-Gaussian 并不是一个限制，因为 Vi ∈ [0, 1]。否则，我们总是可以通过最大可能的 positive reward 来扩展所有的 Vi，并且我们可以使用 sub-Gaussian 随机变量的 scaling 属性来限制每个 scaled reward
现在，主要的任务是限制 
。注意：
考虑随机变量，
，是简单的 
。应用 Corollary 2.1 与 Lemma 2.4 的结论，随机变量 
是
，或者
。此外，
是
。通过使用 Theorem 2.1，我们可以声明
- Theorem 3.1 说明了 exploration 参数 N 的灵敏度
- 如果 m 很大，那么第一项
就会很大 - 另一方面，如果 exploration 参数 m 很小，那么我们可能无法发现最好的 arm，所以第二项会很大
- 在 Theorem 3.1 中的 bound 也称为 instance dependent bound，因为它取决于参数 △i，i ∈ [N] 的特定实例（△i = μ* - μi）
Corollary 2.1：如果 X1, X2, …, Xn 是 IID RVs 并且 每个都是σ-sub-Gaussian随机变量，那么 X1 + X2 + ··· + Xn 是
Lemma 2.4：如果 Xi - μ 是独立的，则是 σ-sub-Gaussian RVs。令
，那么对于任意 ε ≥ 0，我们有
使用 union bound，我们有
- Theorem 2.1：如果 X 是一个 σ-sub-Gaussian R.V.，那么对于任意 ε ≥ 0，我们有
