线性老虎机

环境

隐藏的 $d$ 维向量 $\vec{\theta} \in \mathbb{R}^d$，$\|\vec{\theta}\|_2 \leq 1$，$n$ 个动作，时间 horizon $T$。

在时间 $t$，

1. 与动作 $i$（$\forall i \in [n]$）相关的上下文向量 $\vec{x}_{t,i} \in \mathbb{R}^d$ 被揭示给玩家，$\|\vec{x}_{t,i}\|_2 \leq 1$，

2. 玩家选择动作 $i_t \in [n]$ 并获得奖励 $r_t = \vec{x}_{t,i_t}^T \vec{\theta} + \varepsilon_t$，其中 $\varepsilon_t \sim \mathcal{N}(0,1)$ 是独立噪声（可推广至更一般的噪声）。

备注 我们首先考虑“健忘对手”，即对手在游戏开始前选择所有上下文向量。

目标

最小化遗憾 $R_T \triangleq \mathbb{E} \sum_{t=1}^T \left( \max_{i \in [n]} \vec{x}_{t,i}^T \vec{\theta} - r_t \right)$。

问题

假设在时间 $t$，玩家已执行动作 $\vec{y}_\tau = \vec{x}_{\tau, i_\tau}$（$\tau = 1, 2, 3, …, t$）并观察到奖励 $r_\tau$（$\tau = 1, 2, 3, …, t$）。如何估计 $\theta$？

线性回归（OLS）

令 $S(\vec{\theta}) \triangleq \sum_{\tau=1}^t \left( r_\tau - \vec{y}_\tau^T \vec{\theta} \right)^2$，$\widehat{\vec{\theta}} \triangleq \arg\min_{\vec{\theta}} { S(\vec{\theta}) }$。

令 $\frac{d S(\vec{\theta})}{d \vec{\theta}} = 0$：

$\begin{aligned} 2 \left( \sum_{\tau=1}^t \vec{y}_\tau \vec{y}_\tau^T \right) \vec{\theta} &= 2 \sum_{\tau=1}^t r_\tau \vec{y}_\tau
\Rightarrow \widehat{\vec{\theta}} &= \left( \sum_{\tau=1}^t \vec{y}_\tau \vec{y}_\tau^T \right)^{-1} \sum_{\tau=1}^t r_\tau \vec{y}_\tau \quad \text{（假设 } \sum_{\tau=1}^t \vec{y}_\tau \vec{y}_\tau^T \text{ 可逆）} \end{aligned} $

置信区域

目标：给定测试向量 $\vec{x}$，置信水平 $1-\Delta$，找到 $\gamma$ 使得 $\Pr[ |\vec{x}^T (\vec{\theta} - \widehat{\vec{\theta}})| \leq \gamma ] \geq 1-\Delta$。

首先，假设 $V_t \triangleq \sum_{\tau=1}^t \vec{y}_\tau \vec{y}_\tau^T$ 可逆，我们有 $\begin{aligned} \vec{x}^T (\widehat{\vec{\theta}} - \vec{\theta}) &= \vec{x}^T \left( V_t^{-1} \sum_{\tau=1}^t (\vec{y}_\tau^T \vec{\theta} + \varepsilon_\tau) \vec{y}_\tau - \vec{\theta} \right)
&= \vec{x}^T \left( V_t^{-1} \sum_{\tau=1}^t \vec{y}_\tau \vec{y}_\tau^T \vec{\theta} + V_t^{-1} \sum_{\tau=1}^t \varepsilon_\tau \vec{y}_\tau - \vec{\theta} \right) = \vec{x}^T V_t^{-1} \sum_{\tau=1}^t \vec{y}_\tau \varepsilon_\tau. \end{aligned}$

假设 ${ \varepsilon_\tau }$ 与 ${ \vec{y}_\tau }$ 独立，则 $\vec{x}^T (\widehat{\vec{\theta}} - \vec{\theta})$ 是一个中心高斯变量，方差为 $\sum_{\tau=1}^t \left( \vec{x}^T V_t^{-1} \vec{y}_\tau \right)^2 = \sum_{\tau=1}^t \vec{x}^T V_t^{-1} \vec{y}_\tau \vec{y}_\tau^T V_t^{-1} \vec{x} = \vec{x}^T V_t^{-1} \left( \sum_{\tau=1}^t \vec{y}_\tau \vec{y}_\tau^T \right) V_t^{-1} \vec{x} = \vec{x}^T V_t^{-1} \vec{x}$。

由高斯尾部性质，若设 $\gamma = c \cdot \sqrt{\vec{x}^T V_t^{-1} \vec{x} \cdot \ln \Delta^{-1}}$，则 $\Pr[ |\vec{x}^T (\vec{\theta} - \widehat{\vec{\theta}})| > \gamma ] < \Delta$。

若 $V_t$ 不满秩怎么办？

考虑 $\widehat{\vec{\theta}} \triangleq (I + V_t)^{-1} \sum_{\tau=1}^t r_\tau \vec{y}_\tau$，此时我们有

$\begin{aligned} \vec{x} (\widehat{\vec{\theta}} - \vec{\theta}) &= \vec{x}^T \left[ (I + V_t)^{-1} \sum_{\tau=1}^t (\vec{y}_\tau^T \vec{\theta} + \varepsilon_\tau) \vec{y}_\tau - \vec{\theta} \right]
&= \vec{x}^T \left[ \left( (I + V_t)^{-1} V_t - I \right) \vec{\theta} + \sum_{\tau=1}^t (I + V_t)^{-1} \vec{y}_\tau \varepsilon_\tau \right] = \vec{x}^T \left[ (I + V_t)^{-1} \vec{\theta} + \sum_{\tau=1}^t (I + V_t)^{-1} \vec{y}_\tau \varepsilon_\tau \right]. \end{aligned}$

假设 ${ \varepsilon_\tau }$ 与 ${ \vec{y}_\tau }$ 独立，则 $\vec{x}^T (I + V_t)^{-1} \sum_{\tau=1}^t \vec{y}_\tau \varepsilon_\tau$ 是一个中心高斯变量，方差为 $\sum_{\tau=1}^t \vec{x}^T (I + V_t)^{-1} \vec{y}_\tau \vec{y}_\tau^T (I + V_t)^{-1} \vec{x} = \vec{x}^T (I + V_t)^{-1} V_t (I + V_t)^{-1} \vec{x} \leq \vec{x}^T (I + V_t)^{-1} \vec{x}$。

因此，以概率 $1-\Delta$，

\[\begin{aligned} |\vec{x} (\vec{\theta} - \widehat{\vec{\theta}})| &\leq |\vec{x}^T (I + V_t)^{-1} \vec{\theta}| + c \cdot \sqrt{\vec{x}^T (I + V_t)^{-1} \vec{x} \cdot \ln \Delta^{-1}} \\ &\leq \sqrt{\vec{x}^T (I + V_t)^{-1} \vec{x}} \cdot \sqrt{\vec{\theta}^T (I + V_t)^{-1} \vec{\theta}} + c \cdot \sqrt{\vec{x}^T (I + V_t)^{-1} \vec{x} \cdot \ln \Delta^{-1}} \\ &\leq c \cdot \sqrt{\vec{x}^T (I + V_t)^{-1} \vec{x} \cdot \ln \Delta^{-1}}。 \end{aligned}\]

引理

存在一个普适常数 $c>0$，使得对 $\Delta \in (0, \frac{1}{2})$，且 ${ \varepsilon_\tau }$ 与 ${ \vec{y}_\tau }$ 独立，对所有 $\vec{x} \in \mathbb{R}^d$，有 $\Pr[ |\vec{x}^T (\vec{\theta} - \widehat{\vec{\theta}})| \leq c \cdot \sqrt{\vec{x}^T (I + V_t)^{-1} \vec{x} \cdot \ln \Delta^{-1}} ] \geq 1-\Delta$。

LinUCB 算法

在时间 $t$，

1. 设 $U_{t-1} = I + \sum_{\tau=1}^{t-1} \vec{y}_\tau \vec{y}_\tau^T$，$\widehat{\vec{\theta}}_t = U_{t-1}^{-1} \sum_{\tau=1}^{t-1} r_\tau \vec{y}_\tau$，

2. 选择动作 $i_t = \arg\max_{i \in [n]} \left\{ \widehat{\vec{\theta}}_t^T \vec{x}_{t,i} + CI_{t,i} \right\}$，其中 $CI_{t,i} = c \sqrt{\vec{x}_{t,i}^T U_{t-1}^{-1} \vec{x}_{t,i} \ln(T^2 n)}$。

分析

令 $E$ 为事件：对所有 $t \in [T]$，$i \in [n]$，CI 成立。

由引理 1，“$\Pr[E] \geq 1 - \frac{1}{T}$”（由于相关性，这不精确）。

但让我们暂时假设它是正确的，之后再修正。在条件 $E$ 下，我们有

$\begin{aligned} \text{时间 } t \text{ 的遗憾} &\xrightarrow[\text{对噪声 } \varepsilon_t]{\text{取期望}} \max_{i \in [n]} \vec{x}_{t,i}^T \vec{\theta} - \vec{y}_t^T \vec{\theta} \quad \text{令 } i^\ast \text{ 为最大化者}
&\leq \vec{x}_{t,i^\ast}^T \widehat{\vec{\theta}}_t + | \vec{x}_{t,i^\ast}^T (\widehat{\vec{\theta}}_t - \vec{\theta}) | - \vec{y}_t^T \vec{\theta}
&\leq \vec{x}_{t,i^\ast}^T \widehat{\vec{\theta}}_t + CI_{t,i^\ast} - \vec{y}_t^T \vec{\theta} \quad \text{（由 E）}
&\leq \vec{x}_{t,i_t}^T \widehat{\vec{\theta}}_t + CI_{t,i_t} - \vec{y}_t^T \vec{\theta} \quad \text{（由 UCB 策略）}
&\leq 2 \cdot CI_{t,i_t} \quad \text{（由 E）} \end{aligned}$

因此，$R_T \leq \sum_{t=1}^T \mathbb{E} \left[ 2 CI_{t,i_t} \right] + 2 \cdot T \cdot \Pr[\bar{E}] \leq 2 + 2c \cdot \sqrt{\ln(T^2 n)} \cdot \mathbb{E} \sum_{t=1}^T \sqrt{\vec{y}_t^T U_{t-1}^{-1} \vec{y}_t}$。

引理

[椭球势能] $\sum_{t=1}^T \sqrt{\vec{y}_t^T U_{t-1}^{-1} \vec{y}_t}^2 \leq 2d \ln \left( \frac{T}{d} + 1 \right)$。

因此，由柯西-施瓦茨不等式，$\sum_{t=1}^T \sqrt{\vec{y}_t^T U_{t-1}^{-1} \vec{y}_t} \leq \sqrt{2dT \ln \left( \frac{T}{d} + 1 \right)}$。

我们“几乎”证明了 LinUCB 的遗憾为 $R_T \leq O \left( \sqrt{dT \ln \left( \frac{T}{d} + 1 \right) \ln(Tn)} \right)$。

引理 2 的证明

对每个 $t \geq 1$，我们有 $U_{t-1} \succeq I$，因此 $\vec{y}_t^T U_{t-1}^{-1} \vec{y}_t \leq \vec{y}_t^T \vec{y}_t \leq 1$。

由于 $U_t = U_{t-1} + \vec{y}_t \vec{y}_t^T = U_{t-1}^{1/2} \left( I + U_{t-1}^{-1/2} \vec{y}_t \vec{y}_t^T U_{t-1}^{-1/2} \right) U_{t-1}^{1/2}$，我们有 $\det(U_t) = \det(U_{t-1}) \det \left( I + U_{t-1}^{-1/2} \vec{y}_t \vec{y}_t^T U_{t-1}^{-1/2} \right)$。

断言 $\det(I + \vec{w} \vec{w}^T) = 1 + |\vec{w}|_2^2$

证明

由于 $(I + \vec{w} \vec{w}^T) \vec{w} = \vec{w} + (\vec{w}^T \vec{w}) \cdot \vec{w} \Rightarrow \lambda \vec{w} (I + \vec{w} \vec{w}^T) = 1 + \vec{w}^T \vec{w}$。

且 $\forall \vec{w}’ \perp \vec{w}, (I + \vec{w} \vec{w}^T) \vec{w}’ = \vec{w}’ \Rightarrow \lambda \vec{w}’ (I + \vec{w} \vec{w}^T) = 1$。

由断言，我们有 $\det(U_t) = \det(U_{t-1}) \cdot (1 + | U_{t-1}^{-1/2} \vec{y}_t |_2^2)$ $\Rightarrow \det(U_t) \geq \det(U_0) \cdot \exp \left( \sum_{t=1}^T \frac{1}{2} | U_{t-1}^{-1/2} \vec{y}_t |_2^2 \right) \quad \text{（因为 } 1+x \geq e^{x/2} \; \forall x \in [0,1] \text{）}$

因此 $\sum_{t=1}^T \| U_{t-1}^{-1/2} \vec{y}_t \|_2^2 \leq 2 \ln \frac{\det(U_T)}{\det(U_0)} = 2 \ln \det(U_T)$ $\xrightarrow{\text{(AM-GM)}} 2 \ln \left( \left( \frac{\mathrm{Tr}(U_T)}{d} \right)^d \right) = 2d \ln \left( \mathrm{Tr}(U_T)/d \right) \leq 2d \ln \left( \frac{d+T}{d} \right)$。

修复依赖问题：SupLinUCB 算法

在时间 $t$，构造 ${1,2,3,…,t-1}$ 的划分：${ \Psi_t^s }_{s \in {1,2,…,\lceil \log_2 \sqrt{T} \rceil}}$。

令 $\widehat{\vec{\theta}}_t^s \triangleq (U_t^s)^{-1} \sum_{\tau \in \Psi_t^s} r_\tau \vec{y}_\tau$，其中 $U_t^s \triangleq I + \sum_{\tau \in \Psi_t^s} \vec{y}_\tau \vec{y}_\tau^T$。

定义 CI 参数 $\omega_{t,i}^s \triangleq c \cdot \sqrt{\vec{x}_{t,i}^T (U_t^s)^{-1} \vec{x}_{t,i} \ln(T^2 n)} \quad \forall i \in [n]$，

估计均值 $\widehat{r}_{t,i}^s \triangleq (\widehat{\vec{\theta}}_t^s)^T \vec{x}_{t,i} \quad \forall i \in [n]$。

现在使用以下过程选择 $i_t$：

1. $s \leftarrow 1$；$A_s \leftarrow A = [n]$；

2. 重复

3. 若 $2^{-s} \leq \frac{1}{T}$，则 $i_t \leftarrow \arg\max_{i \in A_{s-1}} { \widehat{r}_{t,i}^{s-1} }$（情况 1）

4. 否则若 $\exists i \in A_s, \omega_{t,i}^s > 2^{-s}$，则 $i_t \leftarrow \text{任意 } i \in A_s \text{ 使得 } \omega_{t,i}^s > 2^{-s}$（情况 2）

5. 否则设 $A_{s+1} \leftarrow { i \in A_s : \widehat{r}_{t,i}^s + \omega_{t,i}^s \geq \max_{j \in A_s} { \widehat{r}_{t,j}^s + \omega_{t,j}^s } - 2^{1-s} }$，$s \leftarrow s+1$，直到找到 $i_t$。

最后，定义时间 $t+1$ 的划分：$\Psi_{t+1}^{s’} = \begin{cases} \Psi_t^{s’} \cup {t} & \text{当 } s’ = s
\Psi_t^{s’} & \text{否则} \end{cases} \quad \forall s’$。

观察 设 $s_t$ 为重复循环后的 $s$ 值，则它仅依赖于噪声 $\varepsilon_\tau$，其中 $\tau \in \Psi_t^1 \cup \cdots \cup \Psi_t^{s_t-1}$，但不依赖于其他噪声。

引理

$\forall t,s$，${ \varepsilon_\tau }_{\tau \in \Psi_t^s}$ 与 ${ \vec{y}_\tau }_{\tau \in \Psi_t^s}$ 独立。

现在，我们可以应用引理 1 并得到：

引理

$\Pr[ \forall t,s, \left| \vec{\theta}^T \vec{x}_{t,i} - \widehat{r}_{t,i}^s \right| \leq \omega_{t,i}^s ] \geq 1 - \frac{\log T}{T}$。

在条件期望事件 $E$ 下，我们有：

1. $F_1 = { \forall t, s \leq s_t, \; \forall i \in A_{s,t}, \; \left| \vec{\theta}^T \vec{x}_{t,i} - \max_{j \in A_{s,t}} \vec{\theta}^T \vec{x}_{t,j} \right| \leq 2^{2-s} }$（其中 $A_{s,t}$ 是时间 $t$ 的 $A_s$ 集合）

2. $F_2 = { \forall t, s \leq s_t, \; i_t^\ast \in A_{s,t} }$（其中 $i_t^\ast = \arg\max_{i \in [n]} \vec{\theta}^T \vec{x}_{t,i}$）

引理

给定 $E \land F_1 \land F_2$，对每个 $t$，$\left| \vec{\theta}^T \vec{x}_{t,i_t} - \vec{\theta}^T \vec{x}_{t,i_t^\ast} \right| \leq O(1) \cdot \max { \frac{1}{T}, \omega_{t,i_t}^{s_t} }$。

证明

若 $i_t$ 由情况 2 选择，由 $F_1$ 和 $F_2$：$\left| \vec{\theta}^T \vec{x}_{t,i_t^\ast} - \vec{\theta}^T \vec{x}_{t,i_t} \right| \leq 2^{2-s_t} \leq 4 \cdot \omega_{t,i_t}^{s_t} \quad \text{（由情况 2 的 IF 条件）}$

若 $i_t$ 由情况 1 选择，由 $E$ 我们有 $\forall i \in A_{s_t-1}, \; \left| \vec{\theta}^T \vec{x}_{t,i} - \widehat{r}_{t,i}^{s_t-1} \right| \leq \omega_{t,i}^{s_t-1} \leq O(1) \cdot 2^{-s_t} \leq O(\frac{1}{T})$。

本情况下引理得证，因为 $F_2$。

因此，我们可以界定 SupLinUCB 算法的遗憾：

$\begin{aligned} R_T &\leq T \cdot \Pr[\bar{E}] + O(1) \mathbb{E} \sum_{t=1}^T \left( \frac{1}{T} + \omega_{t,i_t}^{s_t} \right) \leq O(\frac{1}{T}) + O(1) \cdot \mathbb{E} \sum_{s=1}^{\lceil \log_2 \sqrt{T} \rceil} \sum_{t \in \Psi_{T+1}^s} \omega_{t,i_t}^s
&\leq O(\frac{1}{T}) + O(1) \cdot \mathbb{E} \sum_{s=1}^{\lceil \log_2 \sqrt{T} \rceil} \sqrt{d |\Psi_{T+1}^s| \ln T \ln(nT)} \quad \text{（由椭球势能引理）}
&\leq O(\frac{1}{T}) + O(\log T) \cdot \sqrt{dT \log T \log(nT)} \leq O \left( \sqrt{dT (\log T)^2 \log(nT)} \right)。 \end{aligned}$

处理无穷多臂：覆盖方法

令 $D_t \subseteq \mathbb{R}^d$ 为时间 $t$ 的动作集合。

定义 $\widetilde{D}$ 是 $D$ 的 $\varepsilon$-覆盖，若 $\widetilde{D} \subseteq D$，且 $\forall \vec{x} \in D, \exists \vec{x}’ \in \widetilde{D}$ 满足 $\| \vec{x} - \vec{x}’ \|_2 \leq \varepsilon$。

引理

$\forall D \subseteq { \vec{x} \in \mathbb{R}^d : \|\vec{x}\|_2 \leq 1 }$，存在 $\widetilde{D}$ 是 $D$ 的 $\varepsilon$-覆盖且 $|\widetilde{D}| \leq \left( \frac{3}{\varepsilon} \right)^d$。

证明

（通过构造）从 $\widetilde{D} = \emptyset$ 开始。当 $D \neq \emptyset$ 时，任选 $\vec{x} \in D$，添加 $\vec{x}$ 到 $\widetilde{D}$，并从 $D$ 中移除所有满足 $\|\vec{y} - \vec{x}\|_2 \leq \varepsilon$ 的 $\vec{y}$。

显然 $\widetilde{D}$ 是 $D$ 的 $\varepsilon$-覆盖。只需上界 $|\widetilde{D}|$。注意

1. $\forall \vec{x}, \vec{x}’ \in \widetilde{D}$ 且 $\vec{x} \neq \vec{x}’$，有 $\| \vec{x} - \vec{x}’ \|_2 > \varepsilon$。即 $B_{\frac{\varepsilon}{2}}(\vec{x}) \cap B_{\frac{\varepsilon}{2}}(\vec{x}’) = \emptyset$。

2. $\bigcup_{\vec{x} \in \widetilde{D}} B_{\frac{\varepsilon}{2}}(\vec{x}) \subseteq B_{1+\frac{\varepsilon}{2}}(\vec{0})$。

因此，$\sum_{\vec{x} \in \widetilde{D}} \mathrm{Vol}(B_{\frac{\varepsilon}{2}}(\vec{x})) \leq \mathrm{Vol}(B_{1+\frac{\varepsilon}{2}}(\vec{0})) \Rightarrow |\widetilde{D}| \leq \frac{\mathrm{Vol}(B_{1+\frac{\varepsilon}{2}})}{\mathrm{Vol}(B_{\frac{\varepsilon}{2}})} = \frac{(1+\frac{\varepsilon}{2})^d}{(\frac{\varepsilon}{2})^d} \leq \left( \frac{3}{\varepsilon} \right)^d$。

回到线性-bandit：

• 设 $\varepsilon = \frac{1}{T}$，则存在 $\vec{u}_t^\ast \in \widetilde{D}_t$ 使得（记 $D_t$ 中的最优动作为 $\vec{u}_t^\ast$）$| \vec{\theta}^T (\vec{u}_t^\ast - \vec{u}_t^\ast) | \leq \| \vec{u}_t^\ast - \vec{u}_t^\ast \|_2 \leq \varepsilon = \frac{1}{T} \Rightarrow \text{额外总遗憾} \leq T \cdot \frac{1}{T} = 1$。

• 将 SupLinUCB 应用于动作集合 ${ \widetilde{D}_t }$：$R_T \leq O \left( \sqrt{dT (\log T)^2 \left( \log T + \log \left( (3T)^d \right) \right)} \right) \leq O \left( d \sqrt{T \log^3 T} \right)$。

处理无穷多臂：自归一化尾界方法

在 LinUCB 中，令 ${ \mathcal{F}_t }_{t=0}^T$ 为自然滤波。假设噪声 $\varepsilon_t$ 是 $\mathcal{F}_{t-1}$-可测且 $\mathbb{E}[\varepsilon_t \mid \mathcal{F}_{t-1}] = 0$，选定的动作 $\vec{y}_t$ 也是 $\mathcal{F}_{t-1}$-可测的。在时间 $t$，记 $U = U_{t-1} = I + \sum_{\tau=1}^{t-1} \vec{y}_\tau \vec{y}_\tau^T, \quad \widehat{\vec{\theta}} = \widehat{\vec{\theta}}_t = U_{t-1}^{-1} \sum_{\tau=1}^{t-1} r_\tau \vec{y}_\tau = U^{-1} \sum_{\tau=1}^{t-1} (\vec{\theta}^T \vec{y}_\tau + \varepsilon_\tau) \vec{y}_\tau$。

引理

[自归一化尾界] 以概率 $\geq 1-\Delta$，有 $\| \vec{\theta} - \widehat{\vec{\theta}} \|_U = \sqrt{(\vec{\theta} - \widehat{\vec{\theta}})^T U (\vec{\theta} - \widehat{\vec{\theta}})} \leq O(\sqrt{d \log(T/\Delta)})$。

Remark 利用上述引理，对任意 $\vec{x} \in \mathbb{R}^d$，有 $| \vec{x}^T (\vec{\theta} - \widehat{\vec{\theta}}) | = | \vec{x}^T U^{-1/2} U^{1/2} (\vec{\theta} - \widehat{\vec{\theta}}) | \leq \| \vec{x} \|_{U^{-1}} \cdot \| \vec{\theta} - \widehat{\vec{\theta}} \|_U \leq O(\sqrt{d \log(T/\Delta)}) \cdot \sqrt{\vec{x}^T U^{-1} \vec{x}}$。我们可以设 $\Delta = \frac{1}{T^2}$ 并令 $CI_{t,i} = c \cdot \sqrt{d \vec{x}_{t,i}^T U_{t-1}^{-1} \vec{x}_{t,i} \ln(T/\Delta)}$，从而推导出 LinUCB 的遗憾为 $R_T \leq O(d \sqrt{T \ln(\frac{T}{d}+1) \ln T})$。

Remark 上述分析同样适用于自适应对手，即对手根据 ${ \vec{y}_\tau, r_\tau }_{\tau < t}$ 选择上下文向量 ${ \vec{x}_{t,i} }_{i \in A}$。

自归一化尾界的证明

注意到

$\begin{aligned} \| \vec{\theta} - \widehat{\vec{\theta}} \|_U^2 &= (\vec{\theta} - \widehat{\vec{\theta}})^T U (\vec{\theta} - \widehat{\vec{\theta}}) = (\vec{\theta} - \widehat{\vec{\theta}})^T (U \vec{\theta} - \sum_{\tau=1}^{t-1} (\vec{\theta}^T \vec{y}_\tau + \varepsilon_\tau) \vec{y}_\tau)
&= (\vec{\theta} - \widehat{\vec{\theta}})^T (U \vec{\theta} - (U - I) \vec{\theta} - \sum_{\tau=1}^{t-1} \varepsilon_\tau \vec{y}_\tau) = (\vec{\theta} - \widehat{\vec{\theta}})^T (\vec{\theta} - \sum_{\tau=1}^{t-1} \varepsilon_\tau \vec{y}_\tau)
&\leq | (\vec{\theta} - \widehat{\vec{\theta}})^T \vec{\theta} | + \left| \sum_{\tau=1}^{t-1} (\vec{\theta} - \widehat{\vec{\theta}})^T \vec{y}_\tau \cdot \varepsilon_\tau \right|。 \end{aligned}$

因此，

$\begin{aligned} \| \vec{\theta} - \widehat{\vec{\theta}} \|_U &\leq \frac{| (\vec{\theta} - \widehat{\vec{\theta}})^T \vec{\theta} |}{\| \vec{\theta} - \widehat{\vec{\theta}} \|_U} + \left| \sum_{\tau=1}^{t-1} \frac{(\vec{\theta} - \widehat{\vec{\theta}})^T \vec{y}_\tau}{\| \vec{\theta} - \widehat{\vec{\theta}} \|_U} \cdot \varepsilon_\tau \right|
&\leq \sup_{\vec{\varphi} : \| \vec{\varphi} \|_U \leq 1} \left\{ | \vec{\varphi}^T \vec{\theta} | + \left| \sum_{\tau=1}^{t-1} \vec{\varphi}^T \vec{y}_\tau \cdot \varepsilon_\tau \right| \right\}。 \end{aligned}$

断言

以概率 $\geq 1-\Delta$，$\forall \vec{\varphi} : \| \vec{\varphi} \|_2 \leq 1, \left| \sum_{\tau=1}^{t-1} (\vec{\varphi}^T \vec{y}_\tau) \varepsilon_\tau \right| \leq O\left( \sqrt{d \log(T/\Delta)} \right) \cdot \sqrt{ \sum_{\tau=1}^{t-1} (\vec{\varphi}^T \vec{y}_\tau)^2 }$。

证明

对每个固定的 $\vec{\varphi}$，由“自适应 Azuma”界（设 Cor. 第 7 页中的 $B=T$），$\Pr\left[ \left| \sum_{\tau=1}^{t-1} (\vec{\varphi}^T \vec{y}_\tau) \varepsilon_\tau \right| > c \cdot \sqrt{d \ln(T/\Delta) \cdot \sum_{\tau=1}^{t-1} (\vec{\varphi}^T \vec{y}_\tau)^2 } + \frac{1}{T} \right] < 2 \exp\left( -\frac{c’ d \ln(T/\Delta)}{2} \right)$。

现在我们构造单位球面的 $\varepsilon$-网（$\varepsilon = \frac{1}{T^2}$）并对所有 $\vec{\varphi}$ 取并界。断言通过选择足够大的常数 $c$ 得证。

由上述断言，我们有以概率 $\geq 1-\Delta$，

$\begin{aligned} \| \vec{\theta} - \widehat{\vec{\theta}} \|_U &\leq \sup_{\vec{\varphi} : \| \vec{\varphi} \|_U \leq 1} \left\{ | \vec{\varphi}^T \vec{\theta} | + O(\sqrt{d \log(T/\Delta)} \cdot \sqrt{ \vec{\varphi}^T U \vec{\varphi} }) + \frac{1}{T} \right\}
&\leq \sup_{\vec{\varphi} : \| \vec{\varphi} \|_U \leq 1} \left\{ \| \vec{\varphi} \|_2 \right\} + O(\sqrt{d \log(T/\Delta)}) + \frac{1}{T} \leq O(\sqrt{d \log(T/\Delta)}) + 2。 \end{aligned}$

稀疏线性 bandit

$\| \vec{\theta} \|_0 \leq s$，$s$ 对玩家已知。

对 LinUCB 的修改

令 $\widehat{\vec{\theta}}_t$ 为约束 OLS 优化器：$\widehat{\vec{\theta}}_t \triangleq \arg\min_{\substack{\vec{\theta} : \| \vec{\theta} \|_0 \leq s \ \| \vec{\theta} \|_2 \leq 1}} \left\{ \sum_{\tau=1}^{t-1} (\vec{\theta}^T \vec{y}_\tau - r_\tau)^2 \right\}$。

新的置信区间：$CI_{t,\vec{x}} \triangleq c \cdot \sqrt{s \ln(dT/\Delta) \cdot \vec{x}^T U_{t-1}^{-1} \vec{x}}$。（通常设 $\Delta = \frac{1}{T^2}$）

新的自归一化尾界

对任意时间 $t$，记 $U = U_{t-1}, \widehat{\vec{\theta}} = \widehat{\vec{\theta}}_t$。注意到

$\begin{aligned} \sum_{\tau=1}^{t-1} (\widehat{\vec{\theta}}^T \vec{y}_\tau - r_\tau)^2 &\leq \sum_{\tau=1}^{t-1} (\vec{\theta}^T \vec{y}_\tau - r_\tau)^2 = \sum_{\tau=1}^{t-1} \varepsilon_\tau^2
&\text{II}
\sum_{\tau=1}^{t-1} \left( (\widehat{\vec{\theta}} - \vec{\theta})^T \vec{y}_\tau + \vec{\theta}^T \vec{y}_\tau - r_\tau \right)^2 &= (\widehat{\vec{\theta}} - \vec{\theta})^T (U - I) (\widehat{\vec{\theta}} - \vec{\theta}) + \sum_{\tau=1}^{t-1} \varepsilon_\tau^2 - 2 \sum_{\tau=1}^{t-1} (\widehat{\vec{\theta}} - \vec{\theta})^T \vec{y}_\tau \cdot \varepsilon_\tau
&\underbrace{= -\varepsilon_\tau}_{\text{因为 } r_\tau = \vec{\theta}^T \vec{y}_\tau + \varepsilon_\tau} \end{aligned}$

因此，$(\widehat{\vec{\theta}} - \vec{\theta})^T (U - I) (\widehat{\vec{\theta}} - \vec{\theta}) \leq 2 \sum_{\tau=1}^{t-1} (\widehat{\vec{\theta}} - \vec{\theta})^T \vec{y}_\tau \varepsilon_\tau$。

$\begin{aligned} \Rightarrow \| \widehat{\vec{\theta}} - \vec{\theta} \|_U^2 &\leq \| \widehat{\vec{\theta}} - \vec{\theta} \|_2^2 + 2 \sum_{\tau=1}^{t-1} (\widehat{\vec{\theta}} - \vec{\theta})^T \vec{y}_\tau \varepsilon_\tau \leq \| \widehat{\vec{\theta}} - \vec{\theta} \|_2 \cdot 2 + 2 \sum_{\tau=1}^{t-1} (\widehat{\vec{\theta}} - \vec{\theta})^T \vec{y}_\tau \varepsilon_\tau
\Rightarrow \| \widehat{\vec{\theta}} - \vec{\theta} \|_U &\leq 2 + 2 \sum_{\tau=1}^{t-1} \frac{(\widehat{\vec{\theta}} - \vec{\theta})^T}{\| \widehat{\vec{\theta}} - \vec{\theta} \|_U} \vec{y}_\tau \varepsilon_\tau \leq 2 + 2 \cdot \sup_{\substack{\vec{\varphi} : \| \vec{\varphi} \|_U \leq 1 \ \| \vec{\varphi} \|_0 \leq 2s}} \left| \sum_{\tau=1}^{t-1} \vec{\varphi}^T \vec{y}_\tau \varepsilon_\tau \right|。 \end{aligned}$

断言

以概率 $\geq 1-\Delta$，$\forall \vec{\varphi} : \| \vec{\varphi} \|_2 \leq 1, \| \vec{\varphi} \|_0 \leq 2s$，有 $\left| \sum_{\tau=1}^{t-1} \vec{\varphi}^T \vec{y}_\tau \varepsilon_\tau \right| \leq O(\sqrt{s \log(dT/\Delta)}) \cdot \sqrt{ \sum_{\tau=1}^{t-1} (\vec{\varphi}^T \vec{y}_\tau)^2 }$。

证明

类似于前一页断言的证明。唯一区别是集合 ${ \vec{\varphi} \in \mathbb{R}^d : \| \vec{\varphi} \|_2 \leq 1, \| \vec{\varphi} \|_0 \leq 2s }$ 存在一个大小为 $\binom{d}{2s} \cdot \left( \frac{3}{\varepsilon} \right)^{2s} \leq \exp(O(s \log d + s \log \frac{1}{\varepsilon}))$ 的 $\varepsilon$-网。

因此，我们有：

引理

对任意时间 $t$，以概率 $\geq 1-\Delta$，对所有 $\vec{x} \in \mathbb{R}^d$，有 $\| (\widehat{\vec{\theta}}_t - \vec{\theta})^T \vec{x} \|_2 \leq CI_{t,\vec{x}}$。

Theorem $s$-稀疏线性 bandit 的 LinUCB 遗憾为 $R_T \leq O(\sqrt{sd \log(dT) \log T})$。

用于鞅的自适应 Azuma

引理

[引自 arXiv 0707.3715，Bercu 和 Touati，定理 2.1 的推论，思想源自 De la Peña] 设 $(M_n)$ 为适应于滤波 $(\mathcal{F}_n)$ 的局部平方可积鞅，且 $M_0=0$。

设 $(C_n)_{n \geq 1}$ 为随机变量序列，使得 $C_k$ 为 $\mathcal{F}_{k-1}$-可测，且对所有 $k \geq 1$，$\Pr\left[ |M_k - M_{k-1}| \leq C_k \mid \mathcal{F}_{k-1} \right] = 1$。

则对所有 $x,y>0$，$\Pr\left[ |M_n| \geq x, \; \sum_{i=1}^n C_i^2 \leq y \right] \leq 2 \exp\left( -\frac{x^2}{4y} \right)$。

推论

同上设置，对任意 $B>1$，$\Delta \in (0,1)$，我们有 $\Pr\left[ |M_n| \geq 4 \sqrt{ \sum_{i=1}^n C_i^2 \cdot \ln(B/\Delta) } \land |M_n| \in [\frac{1}{B}, B] \right] \leq \lceil 2 \log_2 B \rceil \cdot \Delta$。

证明

令 $X = \left\{ \frac{1}{B} \cdot 2^i : i = 0, 1, …, \lceil 2 \log_2 B \rceil - 1 \right\}$。由并界，我们有 $\Pr\left[ \exists x \in X, \; |M_n| \geq x, \; \sum_{i=1}^n C_i^2 \leq \frac{x^2}{4 \ln(B/\Delta)} \right] \leq \lceil 2 \log_2 B \rceil \cdot \Delta$。

我们通过证明 $|M_n| \geq 4 \sqrt{ \sum_{i=1}^n C_i^2 \cdot \ln(B/\Delta) } \land |M_n| \in [\frac{1}{B}, B]$ 意味着上述事件来证明推论。这是因为我们可以选择 $x$ 为不超过 $|M_n|$ 的 $X$ 中最大元素。于是我们有 $|M_n| \geq x$ 且 $4x^2 \geq M_n^2 \geq 16 \sum_{i=1}^n C_i^2 \cdot \ln(B/\Delta)$，即 $\sum_{i=1}^n C_i^2 \leq \frac{x^2}{4 \ln(B/\Delta)}$。