线性老虎机 下界

回顾线性老虎机（$n$ 个臂）的遗憾上界：$O(\sqrt{d T \ln^2 T (\min{d, \ln n} + \ln T)})$。

事实 $D_{\mathrm{KL}}(\mathcal{N}(\mu_1, \sigma^2) | \mathcal{N}(\mu_2, \sigma^2)) = \frac{1}{2\sigma^2} (\mu_1 - \mu_2)^2$。

现在我们关注标准高斯噪声（$\sigma^2=1$）的老虎机实例。

定理 1 给定 $T, d$（满足 $T \geq d^2$），令动作集（$\forall t \in [T]$）$A_t \equiv A = \left\{ \pm \sqrt{\frac{4}{T}} \right\}^d$。对于任意策略 $\pi$，存在 $\vec{\theta} \in \left\{ \pm \sqrt{\frac{4}{T}} \right\}^d$，使得 $R_{T,\vec{\theta}}^\pi \geq \Omega(d\sqrt{T})$。

证明 令 $P_{\pi, \vec{\theta}, t}$ 表示由策略 $\pi$ 生成、当隐藏向量为 $\vec{\theta}$ 时前 $t$ 个时间步的历史的概率测度。我们首先计算： \(\begin{aligned} D_{\mathrm{KL}}(P_{\pi, \vec{\theta}, t} \| P_{\pi, \vec{\theta}', t}) &= \mathop{\mathbb{E}}_{h \sim P_{\pi, \vec{\theta}, t-1}} \mathop{\mathbb{E}}_{\vec{a}_t \sim \pi(\cdot | h)} \mathop{\mathbb{E}}_{r_t \sim \mathcal{N}(\langle \vec{a}_t, \vec{\theta} \rangle)} \ln \frac{P_{\pi, \vec{\theta}, t}(h, \vec{a}_t, r_t)}{P_{\pi, \vec{\theta}', t}(h, \vec{a}_t, r_t)} \\ &= \mathop{\mathbb{E}}_{h \sim P_{\pi, \vec{\theta}, t-1}} \mathop{\mathbb{E}}_{\vec{a}_t \sim \pi(\cdot | h)} \mathop{\mathbb{E}}_{r_t \sim \mathcal{N}(\langle \vec{a}_t, \vec{\theta} \rangle)} \ln \frac{P_{\pi, \vec{\theta}, t-1}(h) \cdot \pi(\vec{a}_t | h) \cdot \mathcal{N}(r_t | \langle \vec{a}_t, \vec{\theta} \rangle)}{P_{\pi, \vec{\theta}', t-1}(h) \cdot \pi(\vec{a}_t | h) \cdot \mathcal{N}(r_t | \langle \vec{a}_t, \vec{\theta}' \rangle)} \\ &= \mathop{\mathbb{E}}_{h \sim P_{\pi, \vec{\theta}, t-1}} \ln \frac{P_{\pi, \vec{\theta}, t-1}(h)}{P_{\pi, \vec{\theta}', t-1}(h)} + \mathop{\mathbb{E}}_{h \sim P_{\pi, \vec{\theta}, t-1}} \mathop{\mathbb{E}}_{\vec{a}_t \sim \pi(\cdot | h)} \mathop{\mathbb{E}}_{r_t \sim \mathcal{N}(\langle \vec{a}_t, \vec{\theta} \rangle)} \ln \frac{\mathcal{N}(r_t | \langle \vec{a}_t, \vec{\theta} \rangle)}{\mathcal{N}(r_t | \langle \vec{a}_t, \vec{\theta}' \rangle)} \\ &= D_{\mathrm{KL}}(P_{\pi, \vec{\theta}, t-1} \| P_{\pi, \vec{\theta}', t-1}) + \mathop{\mathbb{E}}_{h \sim P_{\pi, \vec{\theta}, t-1}} \mathop{\mathbb{E}}_{\vec{a}_t \sim \pi(\cdot | h)} \frac{1}{2} \left( \vec{a}_t^T (\vec{\theta} - \vec{\theta}') \right)^2 \\ &= \sum_{\tau=1}^{t} \mathop{\mathbb{E}}_{P_{\pi, \vec{\theta}, \tau}} \frac{1}{2} \left( \vec{a}_\tau^T (\vec{\theta} - \vec{\theta}') \right)^2. \end{aligned}\)

令 $\vec{\theta}^{\oplus i}$ 表示将 $\vec{\theta}$ 的第 $i$ 个分量符号翻转后得到的向量。对任意 $\vec{a} \in A$、任意 $i \in [d]$ 和任意 $\vec{\theta} \in \left\{ \pm \sqrt{\frac{4}{T}} \right\}^d$，注意到 $\left( \vec{a}^T (\vec{\theta} - \vec{\theta}^{\oplus i}) \right)^2 = \left( \sqrt{\frac{4}{T}} \cdot 2\sqrt{\frac{4}{T}} \right)^2 = \frac{4}{T}$。因此，$D_{\mathrm{KL}}(P_{\pi, \vec{\theta}, t} | P_{\pi, \vec{\theta}^{\oplus i}, t}) = \frac{2t}{T}, \quad \quad \forall i \in [d], \vec{\theta} \in \left\{ \pm \sqrt{\frac{4}{T}} \right\}^d$。

令 $E_{i,b}$（$i \in [d], b \in {\pm 1}$）为事件 $\left\{ \left| { t \in [T] : \mathrm{sgn}(\vec{a}_t)_i \neq b } \right| \geq T/2 \right\}$。注意 $E_{i,-b} = \left\{ \left| { t \in [T] : \mathrm{sgn}(\vec{a}_t)_i = b } \right| \geq T/2 \right\} \supseteq \left\{ \left| { t \in [T] : \mathrm{sgn}(\vec{a}_t)_i \neq b } \right| < T/2 \right\} = \overline{E_{i,b}}$。因此，对每个 $i \in [d], b \in {\pm 1}, \vec{\theta} \in \left\{ \pm \sqrt{\frac{4}{T}} \right\}^d$，有： \(\begin{aligned} \Pr[E_{i,b} | \vec{\theta}] + \Pr[E_{i,-b} | \vec{\theta}^{\oplus i}] &\geq \Pr[E_{i,b} | \vec{\theta}] + \Pr[\overline{E_{i,b}} | \vec{\theta}^{\oplus i}] \\ &\geq 1 - \left| \Pr[E_{i,b} | \vec{\theta}] - \Pr[E_{i,b} | \vec{\theta}^{\oplus i}] \right| \geq 1 - \Delta(P_{\pi, \vec{\theta}, T}, P_{\pi, \vec{\theta}^{\oplus i}, T}) \\ &\geq \frac{1}{2} \exp(-D_{\mathrm{KL}}(P_{\pi, \vec{\theta}, T} \| P_{\pi, \vec{\theta}^{\oplus i}, T})) = \frac{1}{2} e^{-2}. \end{aligned}\) （回顾高概率 Pinsker 不等式：$\Delta(P,Q) \leq 1 - \frac{1}{2} \exp(-D_{\mathrm{KL}}(P|Q))$）。

因此，若令 $q_{i,\vec{\theta}} = \Pr[E_{i,\vec{\theta}_i} \mid \vec{\theta}]$，我们有 $q_{i,\vec{\theta}} + q_{i,\vec{\theta}^{\oplus i}} \geq \frac{1}{2} e^{-2} \quad \quad \forall i \in [d], \vec{\theta} \in \left\{ \pm \sqrt{\frac{4}{T}} \right\}^d$。注意 $R_{T,\vec{\theta}}^\pi \geq \sum_{i=1}^{d} q_{i,\vec{\theta}} \cdot \frac{T}{2} \cdot \frac{2}{\sqrt{T}} = \sqrt{T} \sum_{i=1}^{d} q_{i,\vec{\theta}}$。因此，

\[\begin{aligned} \frac{1}{2^d} \sum_{\vec{\theta} \in \\{ \pm \sqrt{\frac{4}{T}} \\}^d} R_{T,\vec{\theta}}^\pi &\geq \frac{\sqrt{T}}{2^d} \sum_{\vec{\theta}} \sum_{i=1}^{d} q_{i,\vec{\theta}} = \frac{\sqrt{T}}{2^d} \sum_{i=1}^{d} ( \sum_{\vec{\theta}} q_{i,\vec{\theta}} + \sum_{\vec{\theta}} q_{i,\vec{\theta}^{\oplus i}} ) \cdot \frac{1}{2} \\ &= \frac{\sqrt{T}}{2^d} \sum_{i=1}^{d} \sum_{\vec{\theta}} \frac{1}{2} (q_{i,\vec{\theta}} + q_{i,\vec{\theta}^{\oplus i}}) \geq \frac{\sqrt{T}}{2^d} \sum_{i=1}^{d} \sum_{\vec{\theta}} \frac{1}{2} \cdot \frac{1}{2} e^{-2} \\ &= \frac{\sqrt{T}}{2^d} \cdot d \cdot 2^d \cdot \frac{1}{4} e^{-2} = \frac{e^{-2}}{4} d\sqrt{T}. \end{aligned}\]

因此，存在 $\vec{\theta} \in \left\{ \pm \sqrt{\frac{4}{T}} \right\}^d$，使得 $R_{T,\vec{\theta}}^\pi \geq \frac{e^{-2}}{4} d\sqrt{T}$。

推论 2 对任意 $n=2^k, k \in {1,2,\cdots,d}$，对任意策略 $\pi$，存在一个线性 bandit 实例 $I$（$\vec{\theta} \in \mathbb{R}^d$，${\vec{x}_{t,i} \in \mathbb{R}^d}_{t \in [T], i \in [n]}$），使得 $R_{T,I}^\pi \geq \Omega(\sqrt{d T \cdot k}) = \Omega(\sqrt{d T \log n})$。

证明 令 $\beta = \lfloor \frac{d}{k} \rfloor$。给定 $k$ 维、$n$ 个臂、时长为 $T_\beta$ 的实例 $I_1, I_2, \cdots, I_\beta$，我们构造 $I = I(I_1, \cdots, I_\beta)$ 如下：

• 将 $d$ 个维度划分为 $\beta$ 个连续块，每块包含 $k$ 个维度。
• 将 $T$ 个时间步划分为 $\beta$ 个连续块，每块包含 $T_\beta$ 个时间步。
• 隐藏向量 $\vec{\theta} = (\vec{\theta}_1, \vec{\theta}_2, \cdots, \vec{\theta}_\beta)$，其中 $\vec{\theta}_i$ 是 $I_i$ 的隐藏向量。
• 在时间步 $(i-1)\cdot T_\beta + t$（第 $i$ 块中的第 $t$ 步）中，提供 $I_i$ 中第 $t$ 步对应的臂。
  • 将向量放入第 $i$ 个维度块，其余部分补零。

根据上述构造，对任意策略 $\pi$，存在 $\pi_1$ 使得对任意 $I_1$，存在 $\pi_2$ 使得对任意 $I_2$，存在 $\pi_3$ 使得对任意 $I_3$，……，对任意 $I_{\beta-1}$，存在 $\pi_\beta$ 使得对任意 $I_\beta$，令 $I = I(I_1, \cdots, I_\beta)$，有 $R_{T,I}^\pi = \sum_{i=1}^{\beta} R_{T_\beta, I_i}^{\pi_i}$。由定理 1，我们逐步构造 $I_1, I_2, \cdots, I_\beta$（同时构造 $\pi_1, \pi_2, \cdots, \pi_\beta$），使得 $R_{T_\beta, I_i}^{\pi_i} \geq \frac{e^{-2}}{4} k \sqrt{T_\beta} \quad (\forall i \in [\beta])$。由此可构造 $I = (I_1, I_2, \cdots, I_\beta)$，使得 $R_{T,I}^\pi \geq \frac{e^{-2}}{4} k \sqrt{T_\beta} \cdot \beta = \frac{e^{-2}}{4} k \sqrt{T_\beta} = \Omega(k \cdot \sqrt{T \cdot d/k}) = \Omega(\sqrt{T d k})$。

改进的下界：（无意识对手）

定理 3（Li-Wang-Zhou’2024） 对任意 $n, T, d$ 满足 $n \leq 2^{d/2}$，$T \geq d (\log_2 n)^{1.1}$，对任意策略 $\pi$，存在一个具有 $d$ 维、$n$ 个臂、时长 $T$ 的线性 bandit 实例 $I$，使得 $R_{T,I}^\pi \geq \Omega(1) \cdot \sqrt{d T \log n \log(T/d)}$。

证明定理 3 的一个关键观察是关于椭圆势引理的紧致性。（即使当 $d=1$）

引理 4 对任意 $T \geq 1$，存在序列 $z_1, z_2, \cdots, z_T \in [0,1]$，若令 $V_0=1$，$V_t = V_{t-1} + z_t z_t^T$ 对 $t \geq 1$，则 $\sum_{t=1}^{T} \sqrt{z_t^2 / V_{t-1}} \geq \sqrt{\frac{T \ln T}{2}}$。

证明 令 $S_t = \left(1 + \frac{\ln T}{2T}\right)^t$ 对所有 $t \geq 0$。令 $z_t = \sqrt{\frac{S_{t-1} \ln T}{2T}}$ 对所有 $t \geq 1$。注意 $z_t$ 关于 $t$ 单调递增。同时，$S_{T-1} = \left(1 + \frac{\ln T}{2T}\right)^{T-1} \leq \sqrt{T}$。因此，对所有 $t \leq T$，有 $0 \leq z_t \leq \sqrt{\frac{S_{T-1} \ln T}{2T}} \leq \sqrt{\frac{\sqrt{T} \ln T}{2}} \leq 1$，即 $z_t \in [0,1]$。此外，注意 $V_t = 1 + \sum_{j=1}^{t} z_j^2 = 1 + \frac{\ln T}{2T} \sum_{j=1}^{t} \left(1 + \frac{\ln T}{2T}\right)^{j-1} = \left(1 + \frac{\ln T}{2T}\right)^t = S_t$。因此， \(\sum_{t=1}^{T} \sqrt{z_t^2 / V_{t-1}} = \sum_{t=1}^{T} \sqrt{V_{t-1}^{-1}} z_t = \sum_{t=1}^{T} \sqrt{\frac{\ln T}{2T}} = \sqrt{\frac{T \ln T}{2}}。\)

改进的上界：（无意识对手）

定理 5（Li-Wang-Zhou’2024） 可设计一种策略，实现最小最大遗憾 $R_T \leq \mathrm{poly}(\log \log(nT)) \cdot \sqrt{d T (\log T) (\log n)}$。