线性老虎机
Published:
线性老虎机算法的遗憾界推导，整理自 Peng Zhao’s Optimization course, Lec 12.
在之前几期的blog中，我们推导了多臂老虎机的遗憾上下界，并且着重介绍了最优算法置信度上界算法UCB。本期我们考虑线性老虎机，可以支持连续的动作空间。线性老虎机可以看作是统计问题中的经典线性回归在于老虎机设计下的自然推广。
Problem Setup
在线性老虎机中，我们考虑状态空空间 $X = { x \in R^d \mid \Vert x \Vert \le L}$ 为标准单位球。我们假设存在一个 $\theta^\ast$, 使得玩家每次选择动作 $x_t$ 之后，得到的奖励满足 $r_t = x_t^\top \theta^\ast +\eta_s$, 其中 $\eta_s$ 满足参数为 $R$ 的次高斯分布。 玩家的任务是找到一个策略，最小化 $T$ 轮交互后期望遗憾上界，定义为：
\[\begin{align*} \mathbb{E}[ {\rm Reg}_T] = T \max_{x \in X} x^\top \theta^\ast - \sum_{t=1}^T x_t^\top \theta^\ast. \end{align*}\]该问题相当于在线形式的最小二乘问题，自然的可以想到一个合理的算法需要做某种在线形式的最小二乘，并且根据我们在多臂老虎机下的经验，高效的算法需要构造尽可能小的置信度上界。这构成了LinUCB算法。对于每一轮交互 $t = 1,\cdots, T$, 算法流程为：
- 根据置信度上界选择 $x_t = \arg \max_{x \in X} {\rm UCB}_{t-1}(x)$.
- 观察到对应的奖励 $r_t$，并且据此更新对于参数的估计 $\hat \theta_t$.
- 使用新的估计更新置信度上界.
在步骤2中，使用带正则的最小二乘估计
\[\begin{align*} \hat \theta_t = \arg \min_{\theta \in R^d} \lambda \Vert \theta \Vert^2 + \sum_{s=1}^{t-1} (x_s^\top \theta - r_s)^2. \end{align*}\]容易知道，该估计量有如下的显示解：
\[\begin{align*} \hat \theta_t = V_{t-1}^{-1} \left(\sum_{s=1}^{t-1} r_s x_s \right), ~~{\rm where} ~~ V_{t-1} = \lambda I_d + \sum_{s=1}^{t-1} x_s x_s^\top. \end{align*}\]Regret Analysis
我们首先假定已经构造出了一个可用的置信区间满足以概率 $1-\delta$ 有
\[\begin{align*} \left \vert x^\top (\hat \theta_t - \theta^\ast) \right \vert \le \beta_{t-1} \Vert x \Vert_{V_{t-1}^{-1}}, \quad \forall x \in X. \end{align*}\]其中 $\beta_1, \cdots, \beta_T$ 为一个递增序列，而具体的值将在后节给出。根据上式，我们自然地构造置信上界UCB为
\[\begin{align*} {\rm UCB}_t(x) = x^\top \hat \theta_t + \beta_{t-1} \Vert x \Vert_{V_{t-1}^{-1}}. \end{align*}\]这里我们首先假设UCB已经被构造出来，推导算法的遗憾上界。
\[\begin{align*} \mathbb{E}[ {\rm Reg}_T] &= \sum_{t=1}^T (x^\ast - x_t)^\top \theta^\ast \\ &= \sum_{t=1}^T (x^\ast - x_t)^\top (\theta^\ast - \hat \theta_t) + \sum_{t=1}^T (x^\ast - x_t)^\top \hat \theta_t \\ &\le \sum_{t=1}^T \beta_{t-1} \Vert x_t \Vert_{V_{t-1}^{-1}} + \sum_{t=1}^T \left( \beta_{t-1} \Vert x_t \Vert_{V_{t-1}^{-1}} + (x^\ast - x_t)^\top \hat \theta_t\right) \\ &\le \sum_{t=1}^T 2 \beta_{t-1} \Vert x_t \Vert_{V_{t-1}^{-1}} \end{align*}\]最后我们调用著名的Elliptical Potential Lemma （中文可能翻译为椭球势引理）给出 $\Vert x_t \Vert_{V_{t-1}^{-1}}$的上界（在最后一节证明），可以得到遗憾上界为
\[\begin{align*} \mathbb{E}[ {\rm Reg}_T] \le 2 \beta_T \sqrt{d \log \left( 1 + \frac{L^2 T}{\lambda d} \right)}. \end{align*}\]在下一个章节中，我们将构造置信区间满足 $\beta_T = \tilde{\mathcal{O}}(\sqrt{d})$，代入上式后得到LinUCB算法的遗憾上界为 $\tilde{\mathcal{O}}(d\sqrt{T})$.
Construct UCB from Self-Normalized Concentration
定义 $S_t = \sum_{s=1}^{t} \eta_s x_s$. 根据称为Method of Mixture (或者中文名字称为混合方法）的思想，经过计算我们可以得到恒等式
\[\begin{align*} \exp \left( \frac{\Vert S_t \Vert_{V_t^{-1}}^2}{2R^2} \right) = \frac{\det(V_t)}{\det (V_0)} \int \exp \left( \frac{\langle \lambda, S_t \rangle}{R} - \frac{1}{2} \Vert \lambda \Vert^2_{V_t - V_0} \right) {\rm d} p(\lambda), \end{align*}\]其中 $\lambda \sim \mathcal{N}(0, V_0^{-1})$ 服从高斯分布。处于篇幅，我们省略上式的证明，但注意到上式本质上为在$V_0$ 处的展开再结合二次函数的共轭函数的定义。根据上式，我们定义
\[\begin{align*} M_t^\lambda = \exp \left( \frac{\langle \lambda, S_t \rangle}{R} - \frac{1}{2} \Vert \lambda \Vert^2_{V_t - V_0} \right). \end{align*}\]这里我们停下来体味一下方法的精髓：在于想办法将 $S_t$ 和 $V_t$ 分离，分离后进行简单的运算可以发现，定义后的 $M_t^\lambda$ 事实上构成了一列上鞅！那么根据著名的Doob停时定理，我们可以知道对于任意的停时 $\tau$ 成立
\[\begin{align*} \mathbb{E}[M_\tau^\lambda] \le \mathbb{E}[M_0^\lambda] =1. \end{align*}\]然后，对于通过 Method of Mixture 得到的恒等式取期望后就可以得到
\[\begin{align*} \mathbb{E} \left[ \frac{\det (V_0)}{\det (V_t)} \exp \left( \frac{\Vert S_t \Vert_{V_t^{-1}}^2}{2R^2} \right) \right] \le 1. \end{align*}\]然后，我们就可以使用本质上与 Chernoff 界相同的分析 （注意定义合适的停时) 得到以概率 $1-\delta$ 成立
\[\begin{align*} \Vert S_t \Vert_{V_t^{-1}}^2 \le 2R^2 \log \left( \frac{\det (V_t)^{1/2} \det (V_0)^{-1/2}}{\delta} \right). \end{align*}\]最后，经过直接的计算就可以得到所需要的置信区间，详细推导如下：
\[\begin{align*} \hat \theta_t - \theta^\ast &= V_{t-1}^{-1} \left( \sum_{s=1}^{t-1} r_s x_s \right) - \theta^\ast \\ &= V_{t-1}^{-1} \left( \sum_{s=1}^{t-1} (x_s^\top \theta^\ast + \eta_s) x_s \right) - V_{t-1}^{-1} \left( \lambda I_d + \sum_{s=1}^{t-1} x_s x_s^\top \right) \theta^\ast \\ &= V_{t-1}^{-1} \left( \sum_{s=1}^{t-1} \eta_s x_s - \lambda \theta^\ast \right). \end{align*}\]利用上式，我们可以得到
\[\begin{align*} & \left \vert x^\top (\hat \theta_t - \theta^\ast) \right \vert \\ \le& \Vert x \Vert_{V_{t-1}^{-1}} \Vert \hat \theta_t - \theta^\ast \Vert_{V_{t-1}} \\ \le& \Vert x \Vert_{V_{t-1}^{-1}} \left( \Vert S_t \Vert_{V_{t-1}^{-1}} + \lambda \Vert \theta^\ast \Vert_{V_{t-1}^{-1}} \right) \\ \le& \Vert x \Vert_{V_{t-1}^{-1}} \left( R \sqrt{2 \log \left( \frac{1}{\delta} \right) + d \log \left( 1 + \frac{t L^2}{\lambda d} \right) } + \sqrt{\lambda} S \right). \end{align*}\]选择 $\lambda = d$ 我们就得到了对于 $\beta_T = \tilde{\mathcal{O}}(\sqrt{d})$ 满足以概率 $1-\delta$ 有
\[\begin{align*} \left \vert x^\top (\hat \theta_t - \theta^\ast) \right \vert \le \beta_{t-1} \Vert x \Vert_{V_{t-1}^{-1}}, \quad \forall x \in X. \end{align*}\]这根据上节的分析自然地就蕴含了 $\tilde{\mathcal{O}}(d\sqrt{T})$ 的最终遗憾上界。
Elliptical Potential Lemma
本节我们证明， 对于任意满足 $\Vert x_t \Vert \le L$ 的序列 ${x_1,\cdots,x_T }$, 定义 $V_0 = \lambda I_d$ 以及 $V_t = V_{t-1} + x_t x_t^\top$. 成立着
\[\begin{align*} \sum_{t=1}^T \Vert x_t \Vert_{V_t^{-1}}^2 \le d \log \left( 1 + \frac{L^2 T}{\lambda d} \right). \end{align*}\]引理证明如下，首先根据等式
\[\begin{align*} V_{t-1} = V_t - x_t x_t^\top = V_t^{1/2} \left( I _d - V_t^{-1/2} x_t x_t^\top V_t^{-1/2} V_t^{1/2} \right), \end{align*}\]可以推出
\[\begin{align*} \det (V_{t-1}) &= \det (V_t) \det (I_d - V_t^{-1/2}x_t x_t^\top V_t^{-1/2}) \\ &= \det(V_t) \left( 1 - \left \Vert V_t^{-1/2} x_t \right \Vert^2 \right). \end{align*}\]上式等价于说
\[\begin{align*} \Vert x_t \Vert_{V_t^{-1}}^2 = 1 - \frac{\det (V_{t-1})}{\det (V_t)}. \end{align*}\]现在我们对所有的 $t =1,\cdots,T$ 求和可以得到最终的结论。
\[\begin{align*} \sum_{t=1}^T \Vert x_t \Vert_{V_t^{-1}}^2 &\le \sum_{t=1}^T \left( 1 - \frac{\det (V_{t-1})}{\det (V_t)} \right) \le \sum_{t=1}^T \log \frac{\det(V_t)}{\det(V_{t-1})} \\ &= \log \frac{\det(V_T)}{\det(V_{0})} \le d \log \frac{ {\rm tr} (V_T/d)}{\lambda} \le d \log \left( 1 + \frac{L^2 T}{\lambda d} \right). \end{align*}\]