批量_bandits

问题设定

给定批次数量 $M$，玩家首先确定一个网格 $\mathcal{J} = {t_0, t_1, \dots, t_M}$，其中 $0 = t_0 < t_1 < \dots < t_M = T$，使得第 $j$ 个批次覆盖时间区间 $[t_{j-1}+1, t_j]$。对于每个批次 $j$，玩家在批次开始时确定一个策略 $\pi_j(t, \cdots)$，使得 $\pi_j$ 仅依赖于截至时间 $t_{j-1}$ 的观测数据。然后，对于每个时间 $t \in [t_{j-1}+1, t_j]$，玩家执行动作 $\pi_j(t)$（若上下文信息 $X_t$ 可用，则为 $\pi_j(t, X_t)$）。玩家的目标是最小化遗憾（如常）。

问题

1. 每个 $M$ 的最优极小极大遗憾是多少？

2. 在无批次约束下，达到最优极小极大遗憾所需的最小 $M$ 是多少？

备注

1. 该问题源于临床试验等实际场景。

2. 也可研究“自适应网格”，其中 $t_j$ 在第 $j$ 个批次开始时自适应确定。当前设定称为“静态网格”。

3. 本讲将聚焦于问题2。

多臂 bandits 的批量相继消除算法

算法

1. $A_0 \leftarrow [n]$，令 $M \leftarrow \lceil \log_2 \log_2 T \rceil + 1$，$t_j = n^{\frac{1}{2^j}} \cdot T^{(1 - \frac{1}{2^j})}$，$\forall j \in {1, 2, \dots, M-1}$

2. FOR $j \leftarrow 1, 2, \dots, M$ DO

   1. 在时间区间 $[t_{j-1}+1, t_j]$ 内，对 $A_{j-1}$ 中的每个臂执行相同次数的抽取

   2. 令 $\tau_j \leftarrow \frac{t_j}{n}$，$\hat{\mu}_j^\ast \leftarrow \max_{i \in A_{j-1}} {\hat{\mu}_{j,i}}$（$\hat{\mu}_{j,i}$：臂 $i$ 在批次 $1 \sim j$ 中采样得到的经验均值）

   3. 消除：令 $A_j \leftarrow \left\{ i \in A_{j-1} : \hat{\mu}_{j,i} \geq \hat{\mu}_j^\ast - c \cdot \sqrt{\ln(nT)/t_j} \right\} \quad (c>0 \text{ 为固定常数})$

分析

令事件 $E = \left\{ \hat{\mu}_{j,i} \in \mu_i \pm \frac{c}{2} \sqrt{\ln(nT)/t_j}, \; \forall j \in [M-1], i \in A_{j-1} \right\}$。我们可以选择常数 $c > 0$，使得 $\mathbb{P}[E] \geq 1 - \frac{1}{T}$。当 $E$ 发生时，$\forall j \in [M-1]$，$A_j$ 中所有臂均为 $2c\sqrt{n \cdot \ln(nT)/t_{j-1}}$-最优。现在我们估计每批次的遗憾：

• 批次 $j=1$：$\text{遗憾} \leq t_1 = \sqrt{nT}$

• 批次 $j, j \in {2,3,\dots,M-1}$：$\text{遗憾} \leq t_j \cdot 2c \sqrt{\frac{n \cdot \ln(nT)}{t_{j-1}}} = 2c \sqrt{\ln(nT)} \cdot \sqrt{n} \cdot n^{\frac{1}{2^j}} \cdot T^{(1-\frac{1}{2^j})} \cdot n^{-\frac{1}{2^{j-1}}} \cdot T^{-\frac{1}{2}(1-\frac{1}{2^{j-1}})} = 2c \cdot \sqrt{nT \ln(nT)}$

• 批次 $j=M$：$\text{遗憾} \leq T \cdot 2c \sqrt{n \cdot \ln(nT) / t_{M-1}} \leq 2c \cdot \sqrt{\ln(nT)} \cdot \sqrt{nT} / \sqrt{T^{1 - \frac{1}{\log_2 T}}} \leq 4c \sqrt{nT \ln(nT)}$。

综上，批量相继消除算法的总遗憾为 $R_T \leq O(\sqrt{nT \ln(nT)} \log \log T)$，且可通过 $M = \lceil \log_2 \log_2 T \rceil + 1$ 个批次实现。

定理（下界）

存在一个通用常数 $c’ > 0$，使得对所有 $n, T, M$，$n$ 臂、时间 horizon $T$ 的 $M$ 批次 MAB 问题的极小极大遗憾 $\geq c’ \cdot \sqrt{n} \cdot T^{\frac{1}{2 - 2^{1-M}}}$。因此，需 $\log_2 \log_2 T$ 个批次才能实现 $\widetilde{O}(\sqrt{nT})$ 遗憾。

批量线性 bandits

定理（下界，Han 等，2020）

对于任意固定网格 $\mathcal{J} = {t_0, t_1, t_2, \dots, t_M}$ 及其上的任意批量策略，存在一个 $n=2$ 的线性 bandit 实例，使得该策略的遗憾为 $\Omega(\sqrt{dT} + \min{T\sqrt{d}/M, T/\sqrt{M}})$。（$\forall T, d$ 满足 $T \geq d^2$）

备注

根据上述下界，需 $\Omega(\sqrt{T})$ 个批次才能实现 $\widetilde{O}(\sqrt{dT})$ 遗憾。

策略切换稀少

在线性 bandit 游戏中，策略切换次数为 $\left| \left\{ t \in [T-1] : \pi_t \neq \pi_{t+1} \right\} \right|$，其中 $\pi_t(t, X_t)$ 为玩家在时间 $t$ 采用的策略。

问题

在无策略切换稀少约束下，达到极小极大最优遗憾所需的最少策略切换次数是多少？

具有 $O(d \log T)$ 次策略切换的算法

回忆 LinUCB 中，时间 $t$ 的策略依赖于 $\widehat{\theta}_t$ 和 $U_t = I + \sum_{\tau=1}^{t} \vec{y}_\tau \vec{y}_\tau^\top$ 来计算 UCB。为限制策略切换次数，我们使用更早时间 $t’$ 的估计 $\widehat{\theta}_{t’}$ 和 $U_{t’}$，仅在 $\det(U_t) > 2 \cdot \det(U_{t’})$ 时才更新 $t’ \leftarrow t$。

断言

经上述修改后，置信区间不会缩小，且最多增加一次。因此，遗憾最多翻倍。

证明

我们需要证明：$\forall \vec{x} \in \mathbb{R}^d$，$\sqrt{\vec{x}^\top U_t^{-1} \vec{x}} \leq \sqrt{\vec{x}^\top U_{t’}^{-1} \vec{x}} \leq \sqrt{2 \vec{x}^\top U_t^{-1} \vec{x}}$。第一个不等式源于 $U_{t’} \preceq U_t$（因 $t’ \leq t$ 且由 $U_t$ 定义）。

对于第二个不等式，我们应用以下事实：若 $A \succeq 0$、$B \succeq 0$ 且 $A - B \succeq 0$，则对所有 $\vec{x} \neq \vec{0}$，有 $\frac{\vec{x}^\top A \vec{x}}{\vec{x}^\top B \vec{x}} \leq \frac{\det(A)}{\det(B)}$。为应用该事实，令 $A = U_{t’}^{-1}$、$B = U_t^{-1}$，则 $\frac{\det(A)}{\det(B)} = \frac{\det(U_t)}{\det(U_{t’})} \leq 2$，我们只需验证 $A - B = U_{t’}^{-1} - U_t^{-1} \succeq 0$。

事实上，我们只需验证 $U_{t-1}^{-1} - U_t^{-1} \succeq 0$。由 Sherman-Morrison 公式： $\begin{aligned} U_{t-1}^{-1} - U_t^{-1} &= U_{t-1}^{-1} - (U_{t-1} + \vec{y}_{t-1} \vec{y}_{t-1}^\top)^{-1}
&= U_{t-1}^{-1} - \left( U_{t-1}^{-1} - \frac{U_{t-1}^{-1} \vec{y}_{t-1} \vec{y}_{t-1}^\top U_{t-1}^{-1}}{1 + \vec{y}_{t-1}^\top U_{t-1}^{-1} \vec{y}_{t-1}} \right) \succeq 0. \end{aligned}$

断言

$\#\text{策略切换} \leq O(d \log T)$。

证明

每次更新 $t’$ 时，$\det(U_{t’})$ 加倍。因此，$\#\text{策略切换} = \#\text{更新} \leq \log_2 \frac{\det(U_{T+1})}{\det(U_1)} \leq \log_2 \left( \frac{\text{Tr}(\det(U_{T+1}))^d}{d} \right) \leq d \log_2 (1 + \frac{T}{d})$。

定理（有限动作集，Ruan-Yang-Zhou’2021）

对于有限动作集（$n$ 个动作）和非自适应对手，对 SupLinUCB 的改进算法在 $O(d \log d \log T)$ 次策略切换下实现 $O(\sqrt{dT} \log d \log T \log(dnT))$ 遗憾。

定理（下界，Ruan-Yang-Zhou’2021）

即使 $n=2$ 且为非自适应对手，为实现 $\widetilde{O}(\sqrt{dT})$ 遗憾，仍需 $\Omega(\frac{d \log T}{\log(d \log T)})$ 次策略切换。

固定上下文的批量线性 bandits

固定上下文

$X_t = {\vec{x}_{t,1}, \dots, \vec{x}_{t,n}} \equiv X = {\vec{x}_1, \dots, \vec{x}_n}$

最优实验设计

给定（可能无限）$X \subseteq \mathbb{R}^d$，$X$ 上的分布 $\varphi: X \to [0,1]$ 称为一个设计。我们定义其[信息]{.underline}和[g 值]{.underline}为 $V(\varphi) \triangleq \mathbb{E}_{\vec{x} \sim \varphi}[\vec{x} \vec{x}^\top], \qquad g(\varphi) = \max_{\vec{x} \in X} \left\{ \vec{x}^\top V(\varphi)^\dagger \vec{x} \right\}$。若 $\varphi^\ast$ 最小化 $g$，则称 $\varphi^\ast$ 为[G-最优设计]{.underline}；若 $\varphi^\ast$ 最大化 $f(\varphi) \triangleq \ln \det V(\varphi)$，则称 $\varphi^\ast$ 为[D-最优设计]{.underline}。

定理（Kiefer-Wolfowitz’1960）

假设 $X \subset \mathbb{R}^d$ 紧致且 $\text{span}(X) = \mathbb{R}^d$。以下条件等价：(a) $\varphi^\ast$ 是 G-最优设计，(b) $\varphi^\ast$ 是 D-最优设计，(c) $g(\varphi^\ast) = d$。此外，存在这样的 $\varphi^\ast$ 使得 $|\text{supp}(\varphi^\ast)| \leq d(d+1)/2$。

备注

一般地，若 $\dim(\text{span}(X)) = m \leq d$，则存在 G-最优 $\varphi^\ast$ 使得 $g(\varphi^\ast) = m$ 且 $|\text{supp}(\varphi^\ast)| \leq \frac{m(m+1)}{2}$。

基于 G-最优探索的批量消除算法

算法

假设 $n = |X|$ 有限且 $T \geq 100d^2$

1. $X_0 \leftarrow X$，令 $M \leftarrow \lceil \log_2 \log_2 T \rceil$，$t_j = T^{(1 - \frac{1}{2^j})}$，$\forall j \in {1, 2, \dots, M-1}$

2. FOR $j \leftarrow 1, 2, \dots, M$ DO

   1. 为 $X_{j-1}$ 寻找 $\varphi_j$：G-最优设计，满足 $|\text{supp}(\varphi_j)| \leq \frac{d(d+1)}{2}$

   2. 对每个 $\vec{x} \in X_{j-1}$，令 $\tau_j(\vec{x}) = \left\lceil (t_j - t_{j-1} - |\text{supp}(\varphi_j)|) \cdot \varphi_j(\vec{x}) \right\rceil$

   3. 对每个 $\vec{x} \in X_{j-1}$，执行 $\tau_j(\vec{x})$ 次

   4. 在 $X_{j-1}$ 中任选一个动作，执行 $\left( t_j - t_{j-1} - \sum_{\vec{x} \in X_{j-1}} \tau_j(\vec{x}) \right)$ 次

   5. 令 $V_j = \sum_{t=t_{j-1}+1}^{t_j} \vec{y}_t \vec{y}_t^\top$（$\vec{y}_t$ 为时间 $t$ 执行的动作），并令 $\widehat{\theta}_j \leftarrow V_j^{-1} \sum_{t=t_{j-1}+1}^{t_j} r_t \vec{y}_t$

   6. 消除：令 $X_j \leftarrow \left\{ \vec{x} \in X_{j-1} : \max_{\vec{x}’ \in X_{j-1}} \left\{ \widehat{\theta}_j^\top (\vec{x}’ - \vec{x}) \right\} \leq \gamma \cdot \sqrt{d \cdot t_j \cdot \ln(nT)} \right\} \quad (\gamma > 0 \text{ 为固定常数})$

分析

当 $T \geq 100d^2$ 时，可推出（对每个 $j$）$t_j - t_{j-1} - |\text{supp}(\varphi_j)| \geq \frac{1}{4} t_j$。因此，$V_j \succeq \sum_{\vec{x} \in X_{j-1}} \tau_j(\vec{x}) \cdot \vec{x} \vec{x}^\top \succeq (t_j - t_{j-1} - |\text{supp}(\varphi_j)|) \cdot \sum_{\vec{x} \in X_{j-1}} \varphi_j(\vec{x}) \cdot \vec{x} \vec{x}^\top \succeq \frac{1}{4} t_j \cdot V(\varphi_j)$。由 K-W 定理，$g(\varphi_j) \leq d$，意味着 $\forall \vec{x} \in X_{j-1}, \; \vec{x}^\top V_j^{-1} \vec{x} \leq \vec{x}^\top \left( \frac{1}{4} t_j \cdot V(\varphi_j) \right)^{-1} \vec{x} \leq \frac{4}{t_j \cdot d}$。因此，我们可以选择常数 $\gamma > 0$，使得 $\forall j, \forall x \in X_{j-1}$，$\mathbb{P} \left[ \widehat{\theta}_j^\top \vec{x} \in \theta^\top \vec{x} \pm \frac{\gamma}{2} \cdot \sqrt{d \cdot t_j \cdot \ln(nT)} \right] \geq 1 - \frac{1}{(nT)^2}$。由联合界：$\mathbb{P} \left[ \forall j, \forall x \in X_{j-1}, \; \widehat{\theta}_j^\top \vec{x} \in \theta^\top \vec{x} \pm \frac{\gamma}{2} \cdot \sqrt{d \cdot t_j \cdot \ln(nT)} \right] \geq 1 - \frac{1}{T}$。其余分析类似多臂 bandits 的批量相继消除，我们可得：

定理

基于 G-最优探索的批量消除算法使用 $\lceil \log_2 \log_2 T \rceil$ 个批次，实现 $O(\sqrt{dT \log(nT)} \log \log T)$ 遗憾。

具有随机上下文的批量线性 bandits

随机上下文

$X_t = {\vec{x}_{t,1}, \dots, \vec{x}_{t,n}} \overset{\text{i.i.d.}}{\sim} \mathcal{D}$，其中 $\mathcal{D}$ 对学习者未知。

定理（Ruan-Yang-Zhou’2021）

存在一种算法，使用 $O(\log \log T)$ 个批次，在线性 bandits 随机上下文下实现 $O(\sqrt{dT} \log d \log(dnT) \cdot \log \log T)$ 遗憾。

备注

上述定理证明的关键步骤包括：

1. 存在良好的“分布性 G-最优设计”：对于任意上下文分布 $\mathcal{D}$，存在一个设计（策略）$\varphi$，将任意上下文 $X$ 映射到 $\Delta_X$ 中的分布，使得分布性 g 值 $g(\varphi) \triangleq \mathbb{E}_{X \sim \mathcal{D}} \max_{\vec{x} \in X} \left\{ \vec{x}^\top V(\varphi(X))^\dagger \vec{x} \right\} \leq O(d \log d)$；

2. 一种从 $\mathcal{D}$ 的独立样本中学习此类设计的学习算法。

Kiefer-Wolfowitz 定理第一部分的证明

我们仅证明 $X$ 有限的情形。证明可推广至无限情形。我们将 $\varphi$ 视为 $\mathbb{R}^X$ 中的向量，有

断言（习题） $f(\varphi)$ 是凹函数，且 $(\nabla f(\varphi))_{\vec{x}} = \vec{x}^\top V(\varphi)^\dagger \vec{x}$（$\forall \vec{x} \in X$）。

此外，我们注意到 $\begin{aligned} \sum_{\vec{x} \in X} \varphi(\vec{x}) \cdot \vec{x}^\top V(\varphi)^\dagger \vec{x} &= \text{Tr} \left( \sum_{\vec{x} \in X} \varphi(\vec{x}) \cdot \vec{x}^\top V(\varphi)^\dagger \vec{x} \right) = \text{Tr} \left( \sum_{\vec{x} \in X} \varphi(\vec{x}) \cdot \vec{x} \vec{x}^\top V(\varphi)^\dagger \right)
&= \text{Tr} \left( I \right) = d. \end{aligned}$

证明 (b) $\Rightarrow$ (a)

设 $\varphi^\ast$ 是 $f$ 的最大值点。则对任意 $\varphi \in \Delta_X$，有 $\begin{aligned} 0 &\geq \langle \nabla f(\varphi^\ast), \varphi - \varphi^\ast \rangle = \sum_{\vec{x} \in X} \varphi(\vec{x}) \cdot \vec{x}^\top V(\varphi^\ast)^\dagger \vec{x} - \sum_{\vec{x} \in X} \varphi^\ast(\vec{x}) \cdot \vec{x}^\top V(\varphi^\ast)^\dagger \vec{x}
&= \sum_{\vec{x} \in X} \varphi(\vec{x}) \cdot \vec{x}^\top V(\varphi^\ast)^\dagger \vec{x} - d. \end{aligned}$ 对任意 $\vec{x} \in X$，考虑 $\varphi$ 为 $\vec{x}$ 处的单点分布，则有 $\vec{x}^\top V(\varphi^\ast)^\dagger \vec{x} - d \leq 0$。因此，$g(\varphi^\ast) \leq d$。另一方面，由 (\ast) 得 $\forall \varphi \in \Delta_X$，$g(\varphi) \geq d$。故 $\varphi^\ast$ 是 $g$ 的最小值点，且 $g(\varphi^\ast) = d$。

证明 (a) $\Rightarrow$ (c)

这直接由上述论证得出。

证明 (c) $\Rightarrow$ (b)

假设 $g(\varphi^\ast) = d$。则对任意 $\varphi \in \Delta_X$，$\langle \nabla f(\varphi^\ast), \varphi - \varphi^\ast \rangle = \sum_{\vec{x} \in X} \varphi(\vec{x}) \cdot \vec{x}^\top V(\varphi^\ast)^\dagger \vec{x} - d \leq 0$。因此，由于 $f$ 是凹函数，$\varphi^\ast$ 是 $f$ 的最大值点。