上下文多臂老虎机问题的简单遗憾最小化.
- paper：Second-order Attention Network for Single Image Super-Resolution
- arXiv：link
本文的主要贡献在于：
- 建立了一个新颖的问题模型：上下文多臂老虎机问题的简单遗憾最小化模型。
- 提出了一个选择策略：Contextual-Gap 算法。
1. 问题建模
本文所研究的问题可以建模为上下文多臂老虎机（Contextual Multi-Armed Bandit，cMAB）模型。
（1）符号说明
记上下文空间为$X \in \Bbb{R}^d$，即将观测到的上下文序列(context)表示为一系列$d$维向量\(\{x_t\}^∞_{t=1}\)。假设共有$A$个臂(arm)，在任意$t$时刻，得到观测结果$x_t$，学习者(learner)需要选择一个臂$a$。
记$f_a : X → \Bbb{R}$为将上下文向量映射为奖励（reward）的函数。对于$t$时刻，选择臂$a_t$，并引入噪声$ζ_t$，根据当前上下文向量$x_t$得到此时的奖励$r_t$：
\[r_t = f_{a_t}(x_t) + ζ_t\]记$D_{a,t}$为$t$时刻前臂$a$被选择的时刻集合，$N_{a,t}$为其大小；$X_{a,t}$为其对应的上下文向量矩阵，$Y_{a,t}$为其对应的奖励向量。
（2）问题陈述
前$T$轮属于探索（exploration）阶段，学习者观察上下文向量，选择臂并得到奖励，记录实验数据用于学习上下文向量到奖励的映射$f_a$；$T$轮后属于利用（exploitation）阶段，学习者观察上下文向量，选择能使奖励最大或使简单遗憾最小的臂。
给定上下文向量$x$，选择臂$a$的简单遗憾（simple regret）定义为：
\[R_a(x) = \mathop{\max}_{i \in A} f_i(x) - f_a(x)\]记将给定上下文向量选择臂的策略（policy）为$Ω$，则目标可表示为通过探索选择合适的策略，使得对于$ε>0$，$t>T$时：
\[P(R_{Ω(x_t)}(x_t) ≥ ε \mid x_t) ≤ b_ε(T)\]其中$b_ε(T)$表示当$T→∞$时衰减到$0$的表达式。
2. 算法流程
设置探索轮数为$T$，总共$A$个臂。算法先对每个臂同样探索$N_λ$次，再使用Contextual-Gap策略探索直至$T$次。之后进行利用阶段。
⚪$t = 1:AN_λ$
- Exploration I：Burn-in Period
这一阶段对每个臂$a$探索$N_λ$次，记录$x_t$和返回的$r_t$；
⚪$t = AN_λ+1:T$
- Exploration II：Contextual-Gap Policy
这一阶段根据上下文向量选择臂进行探索，记录$x_t$和返回的$r_t$；主要步骤如下：
① 首先观察当前上下文向量$x_t$；
② 根据之前记录的实验结果，使用核岭回归估计在当前上下文向量下选择每一个臂能得到的奖励：
\[\hat{f}_{a,t}(x) = \mathop{\arg \max}_{f_a \in H} \sum_{j \in D_{a,t}}^{} {(f_a(x_j)-r_j)^2} + λ\mid\mid f_a \mid\mid^2\]上式表示对臂$a$在希尔伯特空间中寻找一个映射函数$f_a$，能够拟合之前在臂$a$上获得的实验结果，并且进行了L2正则化限制。
根据上面的拟合结果可以得到$t$时刻，观察到上下文向量$x_t$时，选择臂$a$得到的奖励估计值$\hat{f}_{a,t}(x_t)$。
③ 对奖励估计值\(\hat{f}_{a,t}(x_t)\)进行区间估计，可得到其置信区间，记置信区间宽度为\(s_{a,t}(x_t)\)。进一步计算置信上界\(U_{a,t}(x_t) = \hat{f}_{a,t}(x_t) + \frac{s_{a,t}(x_t)}{2}\)，置信下界\(L_{a,t}(x_t) = \hat{f}_{a,t}(x_t) - \frac{s_{a,t}(x_t)}{2}\)。
④ 选择两个候选臂$J_t(x_t)$和$j_t(x_t)$;
$J_t(x_t)$表示在最坏情况下奖励最高的臂。即在选择该臂并情况最坏（取置信下界）时，与选择其他臂并情况最好（取置信上界），奖励差距最小的臂。
\[J_t(x_t) = \mathop{\arg \min}_{a} (\mathop{\max}_{i≠a} U_{i,t}(x_t) - L_{a,t}(x_t))\]$j_t(x_t)$表示在乐观情况下奖励最高的臂。即除$J_t(x_t)$外置信上界最大的臂。
\[j_t(x_t) = \mathop{\arg \max}_{a≠J_t(x_t)} U_{a,t}(x_t)\]⑤ 最终选择两个候选臂中置信区间范围大的臂。
\[a_t = \mathop{\arg \max}_{a \in \{J_t(x_t),j_t(x_t)\}} s_{a,t}(x_t)\]⚪$t > T$
- Exploitation
这一阶段根据之前探索记录的实验结果，选择当前最坏情况下奖励最高的臂$J_t(x_t)$。
3. 一个例子
如上图所示，有$3$个臂并且已经分别计算出在当前上下文向量中其估计的奖励置信区间。
则由计算可得$J_t(x_t)=2$，$j_t(x_t)=1$，最终选择$a_t=1$。
3. 算法特点
作者提出的Contextual-Gap算法在探索阶段首先选择两个候选臂（在最坏情况下奖励最高的臂和在乐观情况下奖励最高的臂），再从其中选择最终的臂。而之前的算法如UCB算法，则是直接选择在乐观情况下奖励最高的臂（置信上界最大的臂）。前者扩大了探索范围，增加了获得更高奖励上限的可能性。与此同时相比于Uniform Sampling算法（等可能选择每个臂），将搜索集中于更可能提供更多奖励的臂上，避免了不必要的搜索。
作者对比了不同算法对不同臂的搜索次数：
作者对比了在合成数据集上不同算法的简单遗憾下降曲线：
