Online Learning 对抗性多臂老虎机

本文研究了对抗性多臂老虎机问题，其中对手在每个时间步自适应地选择隐藏的奖励向量，玩家选择一个动作并获得相应奖励，目标是最小化相对于最佳固定动作的累积奖励损失（即遗憾）。在仅能观测所选动作奖励的经典老虎机设置中，存在下界 Ω(√nT)；而在能观测全部奖励的全信息设置中，遗憾可降至 O(√T log n)。文章的核心是提出并分析 EXP3 算法：该算法通过维护动作权重、构造奖励的无偏估计量来应对部分观测信息，并采用指数加权更新策略。分析表明，EXP3 算法在多臂老虎机设置中实现了 $O(T log n)$ 的遗憾上界，该结果通过乘法权重框架的分析技术得以证明，为对抗性环境下的在线学习提供了经典解决方案。

对抗性多臂老虎机

设置

$n$ 个动作，时间范围 $T$

FOR $t=1,2,3,\cdots,T$ DO

  1. 对手选择奖励向量 $(r_{t,1}, r_{t,2}, \dots, r_{t,n}) \in [0,1]^n$。（对玩家隐藏）

  2. 玩家选择一个动作 $a_t$，执行 $a_t$。

  3. 玩家观测并获得奖励 $r_t = r_{t,a_t}$（多臂老虎机设置）
    或
    玩家观测完整的奖励向量并获得 $r_t = r_{t,a_t}$（全信息设置）

损失
\[R_T \triangleq \mathbb{E}\left[ \max_{a \in [n]} \left\{ \sum_{t=1}^T r_{t,a} \right\} - \sum_{t=1}^T r_t \right] \quad \text{（期望取自玩家和对手的随机性）}\]
观察1

玩家策略必须是随机的，才能实现 $o(T)$ 的损失。

观察2

随机老虎机下界 $\Rightarrow$ 对抗性老虎机下界。
即：对任意玩家策略 $\pi$，存在对手使得 $R_T^\pi \geq \Omega(\sqrt{nT})$

主要定理

在多臂老虎机设置中，存在玩家策略 $\pi$，使得 $R_T^\pi \leq O(\sqrt{nT \log n})$。

乘法权重法：专家问题
热身问题

$n$ 个专家，时间范围 $T$。
每个时间步：

  1. 每个专家给出“是/否”建议。

  2. 玩家决定“是/否”。

  3. 玩家若决策错误则遭受损失。

问题1

若存在一个专家始终给出正确建议。最佳的玩家策略是什么？（在最坏情况下，玩家遭受损失的最小次数是多少？）

答案

$\lceil \log_2 n \rceil$。玩家始终跟随多数意见，并淘汰给出错误建议的专家。
$\Rightarrow$ 玩家每次遭受损失时，至少淘汰一半剩余专家
$\Rightarrow$ 玩家最多遭受 $\lceil \log_2 n \rceil$ 次损失。

问题2

若存在一个专家最多给出 $M$ 次错误建议。最佳玩家策略是什么？

简单方法

$M \lceil \log_2(n+1) \rceil + \lceil \log_2 n \rceil$。
使用多数策略直到所有专家被淘汰，然后重新招募并重复此过程，最多执行 $(M+1)$ 次。

更优方法（软惩罚/乘法权重）

为每个专家分配权重，初始权重为 $w_i^{(0)} = 1 \; \forall i \in [n]$。
在时间 $t$，根据权重 ${w_i^{(t)}}_{i \in [n]}$ 采取加权多数决策。
更新权重： \(w_i^{(t+1)} = \begin{cases} w_i^{(t)} & \text{专家 } i \text{ 正确} \\ w_i^{(t)}/2 & \text{专家 } i \text{ 错误} \end{cases}\)

分析

使用势函数 $W^{(t)} = \sum_{i=1}^n w_i^{(t)}$。我们有 $W^{(0)} = n$。

命题

若玩家在时间 $t$ 遭受损失，则 $W^{(t+1)} \leq \frac{3}{4} W^{(t)}$。

令 $R$ 为玩家遭受损失的次数，则 $W^{(T+1)} \leq \left(\frac{3}{4}\right)^R W^{(0)} = \left(\frac{3}{4}\right)^R \cdot n$。

由于存在一个专家最多给出 $M$ 次错误建议，因此 $w_i^{(T+1)} \geq \left(\frac{1}{2}\right)^M \Rightarrow W^{(T+1)} \geq \left(\frac{1}{2}\right)^M$。

综上：$\left(\frac{1}{2}\right)^M \leq \left(\frac{3}{4}\right)^R \cdot n \Rightarrow R \leq \log_{\frac{4}{3}} n + M \log_{\frac{4}{3}} 2$。

将 MW 应用于全信息设置（Hedge 策略 [Freund-Schapire’97]）

在时间 $t$：以概率 $p_a^{(t)} \triangleq \frac{w_a^{(t)}}{W^{(t)}}$ 选择动作 $a_t = a$。

更新权重：$w_a^{(t+1)} \leftarrow w_a^{(t)} \cdot \exp(\lambda \cdot r_{t,a}) \quad (\lambda \in (0,1)) \text{ 对每个 } a \in [n]$

分析

我们仍有：1) $W^{(0)} = n$，2) 对每个 $a$，$W^{(T+1)} \geq w_a^{(T+1)} = \exp(\lambda \sum_{t=1}^T r_{t,a})$。

对每个 $t$： \(\begin{aligned} W^{(t+1)} &= \sum_a w_a^{(t+1)} = \sum_a w_a^{(t)} \cdot \exp(\lambda \cdot r_{t,a}) \\ &\leq \sum_a w_a^{(t)} \cdot (1 + \lambda r_{t,a} + \lambda^2 r_{t,a}^2) \quad \text{（因为 } e^x \leq 1+x+x^2 \text{ 当 } |x| \leq 1\text{）} \\ &\leq \sum_a w_a^{(t)} \cdot (1 + \lambda r_{t,a} + \lambda^2) \\ &= (1+\lambda^2)W^{(t)} + \lambda W^{(t)} \sum_a p_a^{(t)} \cdot r_{t,a} = W^{(t)} \left[ 1 + \lambda^2 + \lambda \sum_a p_a^{(t)} \cdot r_{t,a} \right] \\ &\leq W^{(t)} \cdot \exp\left( \lambda^2 + \lambda \sum_a p_a^{(t)} \cdot r_{t,a} \right) \quad \text{（因为 } 1+x \leq e^x\text{）} \end{aligned}\)

综上：$W^{(T+1)} \leq W^{(0)} \cdot \exp\left( \lambda^2 T + \lambda \sum_{t=1}^T \sum_a p_a^{(t)} \cdot r_{t,a} \right)$

$\Rightarrow \sum_{t=1}^T \sum_a p_a^{(t)} \cdot r_{t,a} \geq \frac{1}{\lambda} \cdot \ln \frac{W^{(T+1)}}{W^{(0)}} - \lambda T$

结合 1) 和 2)：对每个 $a$，$\text{LHS（期望奖励）} \geq \frac{1}{\lambda} \left( \lambda \sum_{t=1}^T r_{t,a} - \ln n \right) - \lambda T = \sum_{t=1}^T r_{t,a} - \frac{1}{\lambda} \ln n - \lambda T$

因此，$R_T \leq \frac{1}{\lambda} \ln n + \lambda T \stackrel{\text{令 } \lambda = \sqrt{\frac{\ln n}{T}}}{=} O(\sqrt{T \ln n})$。

多臂老虎机设置：EXP3 算法
思路

对每个 $r_{t,a}$ 使用无偏估计，例如 $\hat{r}_{t,a} \triangleq \mathbf{1}[a_t = a] \cdot r_t / p_a^{(t)}$

可验证：$\mathbb{E} \hat{r}_{t,a} = \sum_{a’} p_{a’}^{(t)} \cdot \mathbf{1}[a’=a] \cdot r_{t,a} / p_a^{(t)} = r_{t,a}$。

EXP3 算法

使用略有不同的估计：$\hat{r}_{t,a} \triangleq 1 - \mathbf{1}[a_t = a] \cdot (1 - r_t) / p_a^{(t)}$。

验证：1) $\mathbb{E} \hat{r}_{t,a} = r_{t,a}$，2) $\hat{r}_{t,a} \leq 1$ 几乎必然成立。

更新规则：$w_a^{(t+1)} \leftarrow w_a^{(t)} \cdot \exp(\lambda \cdot \hat{r}_{t,a}) \quad (\lambda \in (0,1)) \text{ 对每个 } a \in [n]$。

分析

我们仍有：

\[\begin{cases} W^{(0)} = n \\ W^{(T+1)} \geq w_a^{(T+1)} = \exp(\lambda \cdot \sum_{t=1}^T \hat{r}_{t,a}) \text{ 对每个 } a \in [n] \end{cases}\]

对每个 $t$，有 \(\begin{aligned} W^{(t+1)} &= \sum_a w_a^{(t+1)} = \sum_a w_a^{(t)} \exp(\lambda \cdot \hat{r}_{t,a}) \leq \sum_a w_a^{(t)} (1 + \lambda \hat{r}_{t,a} + \lambda^2 \hat{r}_{t,a}^2) \quad \text{（因为 } e^x \leq 1+x+x^2 \text{ 当 } x \leq 1\text{）} \\ &= W^{(t)} \sum_a p_a^{(t)} (1 + \lambda \hat{r}_{t,a} + \lambda^2 \hat{r}_{t,a}^2) = W^{(t)} \left[ 1 + \sum_a p_a^{(t)} (\lambda \hat{r}_{t,a} + \lambda^2 \hat{r}_{t,a}^2) \right] \\ &\leq W^{(t)} \exp\left( \sum_a p_a^{(t)} (\lambda \hat{r}_{t,a} + \lambda^2 \hat{r}_{t,a}^2) \right) \quad \text{（因为 } 1+x \leq e^x\text{）}. \end{aligned}\)

因此，\(\ln W^{(t+1)} - \ln W^{(t)} \leq \sum_a p_a^{(t)} (\lambda \hat{r}_{t,a} + \lambda^2 \hat{r}_{t,a}^2)\)

$\Rightarrow$ 在给定前 $(t-1)$ 个时间步的条件下， \(\begin{aligned} \mathbb{E} \ln W^{(t+1)} - \ln W^{(t)} &\leq \sum_a p_a^{(t)} (\lambda \cdot \mathbb{E} \hat{r}_{t,a} + \lambda^2 \cdot \mathbb{E} \hat{r}_{t,a}^2) \\ &= \lambda \cdot \sum_a p_a^{(t)} \cdot r_{t,a} + \lambda^2 \cdot \sum_a p_a^{(t)} \mathbb{E} \hat{r}_{t,a}^2. \end{aligned} \tag{*}\)

注意 \(\begin{aligned} \sum_a p_a^{(t)} \mathbb{E} \hat{r}_{t,a}^2 &= \sum_a p_a^{(t)} \cdot \sum_{a'} p_{a'}^{(t)} \cdot \left[ 1 - \mathbf{1}[a'=a] (1 - r_{t,a'}) / p_a^{(t)} \right]^2 \\ &= \sum_a p_a^{(t)} \cdot \left[ (1 - p_a^{(t)}) + p_a^{(t)} \cdot \left(1 - \frac{1 - r_{t,a}}{p_a^{(t)}} \right)^2 \right] \\ &\leq 1 + \sum_a \left( p_a^{(t)} - 1 + r_{t,a} \right)^2 \leq n+1 \end{aligned}\)

因此，(*) $\Rightarrow \mathbb{E} \ln W^{(t+1)} - \ln W^{(t)} \leq \lambda \cdot \sum_a p_a^{(t)} \cdot r_{t,a} + \lambda^2 \cdot (n+1)$（在给定前 $(t-1)$ 个时间步的条件下）

$\Rightarrow \mathbb{E} \ln W^{(T+1)} - \mathbb{E} \ln W^{(0)} \leq \lambda \cdot \mathbb{E} \sum_{t=1}^T r_t + \lambda^2 T \cdot (n+1)$

综上：$\mathbb{E} W^{(T+1)} - \mathbb{E} W^{(0)} \leq \lambda \cdot \mathbb{E} \sum_{t=1}^T r_t + \lambda^2 T \cdot (n+1) \Rightarrow \forall a, \; \lambda \sum_{t=1}^T \mathbb{E} r_t + \lambda^2 T (n+1) \geq \lambda \sum_{t=1}^T \mathbb{E} r_{t,a} - \ln n$

因此，$R_T \leq \lambda T (n+1) + \frac{1}{\lambda} \ln n \stackrel{\text{令 } \lambda = \sqrt{\frac{\ln n}{T(n+1)}}}{=} O(\sqrt{T n \ln n})$。

Written on March 1, 2026