上下文老虎机

动机

额外的上下文信息有助于做出更好的决策。然而，上下文信息[不]{.underline}依赖于过去的行为。

对抗性上下文老虎机

策略类： $\Pi = { \pi : X \to A }$

游戏开始时：
对手为每个 $t \in [T]$ 选取 $x_t \in X$ 和奖励向量 $(r_{t,1}, r_{t,2}, …, r_{t,n}) \in [0,1]^n$。

在每个时间步 $t$：

1. 玩家观察到 $x_t$，并选择 $a_t$。

2. 玩家观察并获得奖励 $r_t = r_{t,a_t}$。

目标： 最小化后悔值 $R_T \triangleq \mathbb{E}\left[ \max_{\pi \in \Pi} \left\{ \sum_{t=1}^T r_{t,\pi(x_t)} \right\} - \sum_{t=1}^T r_t \right]$。（期望值取自玩家的随机性）

EXP4算法

乘法权重： $w^{(t)}: \Pi \to \mathbb{R}^{>0}$，初始化：对每个 $\pi \in \Pi$，$w^{(0)}(\pi) \leftarrow 1$。

在时间 $t$：

1. 以概率 $p_a^{(t)} \triangleq \sum_{\pi: \pi(x_t)=a} \frac{w^{(t)}(\pi)}{W^{(t)}}$ 选择 $a \in [n]$，其中 $W^{(t)} \triangleq \sum_{\pi} w^{(t)}(\pi)$。

2. 更新权重：$w^{(t+1)}(\pi) = w^{(t)}(\pi) \cdot \exp(\lambda \cdot \hat{r}_{t,\pi(x_t)})$，其中 $\lambda \in (0,1]$，且 $\hat{r}_{t,a} = 1 - \mathbf{1}[a_t=a] \cdot (1-r_t)/p_a^{(t)}$（当 $p_a^{(t)} > 0$ 时）。

分析

首先，我们有：1) $W^{(0)} = |\Pi|$。2) $\forall \pi \in \Pi$，$w^{(T+1)}(\pi) \ge w^{(T+1)}(\pi) = \exp(\lambda \sum_{t=1}^T \hat{r}_{t,\pi(x_t)})$。

对每个 $t$：

\[\begin{aligned} W^{(t+1)} &= \sum_{\pi} w^{(t+1)}(\pi) = \sum_{a} \sum_{\pi: \pi(x_t)=a} w^{(t)}(\pi) \cdot \exp(\lambda \cdot \hat{r}_{t,a}) \\ &= W^{(t)} \cdot \sum_{a} p_a^{(t)} \cdot \exp(\lambda \cdot \hat{r}_{t,a}) \\ &\le W^{(t)} \cdot \sum_{a} p_a^{(t)} \left(1 + \lambda \hat{r}_{t,a} + \lambda^2 \hat{r}_{t,a}^2 \right) \quad \text{（因为 } \lambda \hat{r}_{t,a} \le 1 \text{ 且 } \exp(x) \le 1+x+x^2 \text{ 当 } x \le 1\text{）} \\ &= W^{(t)} \left[1 + \sum_{a} \left(\lambda \hat{r}_{t,a} + \lambda^2 \hat{r}_{t,a}^2 \right) \cdot p_a^{(t)} \right] \\ &\le W^{(t)} \cdot \exp\left( \sum_{a} \left(\lambda \hat{r}_{t,a} + \lambda^2 \hat{r}_{t,a}^2 \right) \cdot p_a^{(t)} \right) \quad \text{（因为 } 1+x \le e^x\text{）} \end{aligned}\]

因此，$\ln W^{(t+1)} - \ln W^{(t)} \le \sum_{a} \left(\lambda \hat{r}_{t,a} + \lambda^2 \hat{r}_{t,a}^2 \right) \cdot p_a^{(t)}$。

在给定前 $(t-1)$ 个时间步的条件下， \(\begin{aligned} \mathbb{E}[\ln W^{(t+1)} - \ln W^{(t)}] &\le \sum_{a} \lambda \cdot p_a^{(t)} \cdot \mathbb{E}[\hat{r}_{t,a}] + \sum_{a} \lambda^2 \cdot p_a^{(t)} \cdot \mathbb{E}[\hat{r}_{t,a}^2] \\ &\le \lambda \cdot \sum_{a} p_a^{(t)} \cdot r_{t,a} + \lambda^2 (n+1) \quad \text{（与EXP3相同）} \\ \text{因此，} \quad \mathbb{E}[\ln W^{(T+1)}] - \mathbb{E}[\ln W^{(0)}] &\le \lambda \cdot \sum_{t=1}^T \mathbb{E}[r_t] + \lambda^2 T (n+1) \end{aligned}\)

综上：$\mathbb{E}[\ln W^{(T+1)}] - \mathbb{E}[\ln W^{(0)}] \le \lambda \cdot \sum_{t=1}^T \mathbb{E}[r_t] + \lambda^2 T (n+1)$

结合1)和2)：$\forall \pi \in \Pi, \quad \lambda \cdot \sum_{t=1}^T \mathbb{E}[r_t] \ge \lambda \cdot \sum_{t=1}^T r_{t,\pi(x_t)} - \ln |\Pi| - \lambda^2 T (n+1)$

因此，$R_T \le \frac{1}{\lambda} \ln |\Pi| + \lambda T (n+1)$。令 $\lambda = \sqrt{\frac{\ln |\Pi|}{T(n+1)}}$，可得 $O(\sqrt{nT \ln |\Pi|})$。

注： $\sum_{a} p_a^{(t)} \mathbb{E}[\hat{r}_{t,a}^2]$ 也可上界为 $|\Pi|+1$。

定理： EXP4的后悔值 $\le O(\sqrt{T \cdot \min\{n, |\Pi|\} \cdot \ln |\Pi|})$。

随机性上下文老虎机

在时间 $t$，$(x_t, r_{t,1}, …, r_{t,n}) \sim \mathcal{D}$（随机分布，$\mathcal{D}$ 对玩家不可见）。

EXP4在此设定下仍有效，但我们考虑另一种方法。

计划： 对每个 $\pi \in \Pi$ 估计 $\mu(\pi) \triangleq \mathbb{E}_{(x,r_1,…,r_n)\sim \mathcal{D}}[r_{\pi(x)}]$，并采用UCB/消除法。

• 假设我们以分布 $P$ 在 $\Pi$ 上进行探索，即选择 $\pi \sim P$，执行 $\pi(x_t)$ 并观察 $r_{t,\pi(x_t)}$。

• 定义 $W_P(x,a) \triangleq \Pr[a_t = a \mid x_t = x] = \sum_{\pi \in \Pi: \pi(x)=a} P(\pi)$。

• 构造无偏估计量 $\hat{r}_{t,a} \triangleq \frac{r_t \cdot \mathbf{1}[a_t=a]}{W_P(x_t,a)}$，验证：$\mathbb{E}_{a_t \sim W_P(x,\cdot)}[\hat{r}_{t,a}] = r_{t,a}$。

• 给定探索期 $Z$，对每个 $\pi \in \Pi$，构造无偏估计量 $\hat{\mu}(\pi) \triangleq \sum_{t \in Z} \hat{r}_{t,\pi(x_t)} / |Z|$，验证：$\mathbb{E}_{{a_t}_{t \in Z}}[\hat{\mu}(\pi)] = \mu(\pi)$。

关于偏差？ 回忆Bernstein不等式：

引理： 设 $x_1, x_2, …, x_n$ 独立，$x_i \in [0,M]$ 几乎必然 $\forall i$，则 $\forall \varepsilon > 0$，$\Pr\left[ \left| \sum_{i=1}^n x_i - \sum_{i=1}^n \mathbb{E}[x_i] \right| > \varepsilon \right] < 2 \exp\left( -\frac{\varepsilon^2/2}{\sum_{i=1}^n \mathrm{Var}[x_i] + \frac{1}{3} M \varepsilon} \right)$。

因此，我们需要对方差和 $M$ 进行上界估计。

稍有不同的估计量。 对于 $\lambda \in (0, \frac{1}{2}]$，使用以下分布进行探索：$\begin{cases} \text{选择 } \pi \sim P \text{ 并执行 } \pi(x_t) & \text{概率为 } 1-\lambda
\text{选择 } a_t \sim \mathrm{Unif}(A) \text{ 并执行 } a_t & \text{概率为 } \lambda \end{cases}$

即，$\Pr[a_t = a \mid x_t = x] = W_P’(x,a) \triangleq (1-\lambda) W_P(x,a) + \lambda/n$。然后构造我们的估计量：$\hat{r}_{t,a} \triangleq \frac{r_t \cdot \mathbf{1}[a_t=a]}{W_P’(x_t,a)} \in \left[0, \frac{n}{\lambda}\right]$ 几乎必然 $\Rightarrow$ 可设 $M = n/\lambda$。

引理（方差）： 存在 $\Pi$ 上的分布 $P$，使得若我们相应定义 $P’$，则 $\forall \pi \in \Pi, \; \mathbb{E}_{x_t \sim \mathcal{D}} \left[ \frac{1}{W_{P’}(x_t, \pi(x_t))} \right] \le 2n$。

注： 上述引理意味着：$\forall \pi \in \Pi, \; \mathrm{Var}_{\mathcal{D},P}[\hat{r}_{t,\pi(x_t)}] \le \mathbb{E}_{\mathcal{D},P}[\hat{r}_{t,\pi(x_t)}^2] \le \mathbb{E}_{x_t \sim \mathcal{D}} \left[ \frac{1}{W_{P’}(x_t, \pi(x_t))} \right] \le 2n$。

方差引理的证明： 我们只需证明：$\min_{P \in \Delta\Pi} \max_{Q \in \Delta\Pi} \mathbb{E}_{\substack{x \sim \mathcal{D} \ \pi \sim Q}} \left[ \frac{1}{W_{P’}(x, \pi(x))} \right] \le 2n$，其中 $W_{P’}(x, \pi(x)) = \mathbb{E}_{\sigma \sim P} \left[ \mathbf{1}[\sigma(x) = \pi(x)] \cdot (1-\lambda) + \lambda/n \right]$。

令 $f(P,Q) = \mathbb{E}_{\substack{x \sim \mathcal{D} \ \pi \sim Q}} \left( \mathbb{E}_{\sigma \sim P} \left[ \mathbf{1}[\sigma(x) = \pi(x)] \cdot (1-\lambda) + \lambda/n \right] \right)^{-1}$。我们验证：

1. $f$ 关于 $Q$ 是线性的

2. $f$ 关于 $P$ 是凸的：$\forall P_1, P_2, Q, a,b : a,b \ge 0, a+b=1$，$af(P_1,Q) + bf(P_2,Q) \ge f(aP_1 + bP_2, Q)$。（归结为 $\frac{1}{c_1 x + c_2}$ 的凸性，$x \ge 0$，$c_1,c_2 > 0$）

应用冯·诺依曼极小极大定理：

定理： 设 $X,Y$ 为紧集，$f: X \times Y \to \mathbb{R}$ 连续，且

1. $f(\cdot,y): x \mapsto \mathbb{R}$ 对所有 $y \in Y$ 为凹函数，

2. $f(x,\cdot): Y \to \mathbb{R}$ 对所有 $x \in X$ 为凸函数，

则 $\max_{x \in X} \min_{y \in Y} f(x,y) = \min_{y \in Y} \max_{x \in X} f(x,y)$。

因此，$\min_{P \in \Delta\Pi} \max_{Q \in \Delta\Pi} f(P,Q) = \max_{Q \in \Delta\Pi} \min_{P \in \Delta\Pi} f(P,Q)$。

对每个 $Q \in \Delta\Pi$， \(\begin{aligned} \min_{P \in \Delta\Pi} f(P,Q) &\le f(Q,Q) = \mathbb{E}_{\substack{x \sim \mathcal{D} \\ \pi \sim Q}} \left( \mathbb{E}_{\sigma \sim Q} \left[ \mathbf{1}[\sigma(x) = \pi(x)] \cdot (1-\lambda) + \lambda/n \right] \right)^{-1} \\ &= \mathbb{E}_{x \sim \mathcal{D}} \sum_{a} \frac{W_Q(x,a)}{W_Q(x,a) \cdot (1-\lambda) + \lambda/n} \le \mathbb{E}_{x \sim \mathcal{D}} \sum_{a} \frac{1}{1-\lambda} \le \mathbb{E}_{x \sim \mathcal{D}} \sum_{a} 2 = 2n. \end{aligned}\)

现在，我们可以应用Bernstein不等式： \(\begin{aligned} \Pr\left[ |\hat{\mu}(\pi) - \mu(\pi)| > \varepsilon \right] &< 2 \exp\left( -\frac{\varepsilon^2 \cdot |Z|/2}{2n \cdot |Z| + \frac{1}{3} \frac{n}{\lambda} \cdot \varepsilon |Z|} \right) = 2 \exp\left( -\frac{\varepsilon^2 \cdot |Z|/2}{2n + \frac{1}{3} \frac{n}{\lambda} \cdot \varepsilon} \right) \\ &\le 2 \exp\left( -\frac{\varepsilon^2 |Z|}{6n} \right) \quad \text{（只要 } \frac{\varepsilon}{\lambda} \le 3\text{）} \end{aligned}\)

算法：策略消除

对轮次 $\tau = 1,2,3,\ldots$ 执行：

1. 从 $\Pi_\tau$ 开始：$\varepsilon_\tau$-优策略集合（$\varepsilon_\tau \triangleq 2^{1-\tau}$，$\Pi_1 = \Pi$）

2. 寻找满足方差引理的 $P_\tau \in \Delta\Pi_\tau$，其中 $\lambda_\tau = \varepsilon_\tau / 2$。

3. 使用 $W_{P_\tau’}$ 进行 $m_\tau = \Theta(\varepsilon_\tau^{-2} n \ln(|\Pi| \cdot T))$ 个时间步的执行。

4. 消除：$\Pi_{\tau+1} \leftarrow \left\{ \pi \in \Pi_\tau : \hat{\mu}_\tau(\pi) \ge \max_{\sigma \in \Pi_\tau} \hat{\mu}_\tau(\sigma) - \frac{\varepsilon_\tau}{2} \right\}$。

注： 由于 $\mathcal{D}$ 未知，必须进行估计，因此实现步骤2需要额外努力。

分析

以高概率（例如 $1 - \frac{1}{T}$），$\forall \tau, \pi, \left| \hat{\mu}_\tau(\pi) - \mu(\pi) \right| \le \frac{\varepsilon_\tau}{4}$。

第 $\tau$ 轮的后悔值：$\varepsilon_\tau \cdot m_\tau = O(\varepsilon_\tau^{-1} \cdot n \ln(|\Pi| \cdot T))$。

令 $\tau^\ast$ 为最后一轮：$m_{\tau^\ast} \le O(T) \Rightarrow \varepsilon_{\tau^\ast} \cdot m_{\tau^\ast} \le O(\sqrt{nT \ln(|\Pi| \cdot T)})$。

因此，总后悔值 $\le O(\sqrt{nT \ln(|\Pi| \cdot T)})$。

优势？

1. 当问题“可分离”时，可获得 $O(\frac{n \ln(|\Pi| T)}{\Delta})$ 的后悔值。

2. 假设 $\Pi$ 具有结构性质，可实现计算高效（在 $\mathrm{poly}(n, T, \log|\Pi|)$ 时间内）。