对抗多臂老虎机Exp3算法的指数加权策略

在对抗性多臂老虎机问题中，环境会主动让你的选择变差。你需要一个即使对手（环境）不断调整，也能持续优化决策的策略。Exp3（Exponential-weight algorithm for Exploration and Exploitation）算法正是为此设计。它的核心是指数加权策略，本指南将一步步拆解其工作原理与实现方法。

1. 理解问题：对抗性多臂老虎机

多臂老虎机问题好比面前有K台不同的老虎机（即“臂”），每轮你需要选择一个臂拉动，然后获得该臂给出的奖励。你的目标是：在多次尝试后，让总奖励尽可能高。

在对抗性环境中，每轮每个臂的奖励不是随机分布的，而是由对手（或环境）在你做出选择后直接设定。对手的目标是让你的总奖励尽可能低。这意味着，你过去经验中奖励高的臂，未来可能会变得很差。

传统的随机策略（如$\epsilon$-贪心）在此类问题中效果不佳，因为奖励分布不稳定。Exp3算法通过同时探索和利用，并给予每个臂一个基于历史表现的指数级增长的权重来应对这一挑战。

2. Exp3算法核心逻辑

Exp3算法每轮执行三个基本动作：

1. 计算：根据当前每个臂的权重，计算选择它的概率。
2. 选择与奖励：根据计算出的概率随机选择一个臂，然后观察并记录该轮获得的奖励。
3. 更新：根据获得的奖励，更新被选中臂的权重（通常以指数方式增加其权重）。

算法的关键在于“指数加权”。表现越好的臂，其权重增长越快，从而被选中的概率也越高。同时，探索机制确保了即使当前看起来较差的臂，仍有非零概率被尝试，以防环境发生有利于它的变化。

3. 指数加权策略详解：权重与概率的计算

这是Exp3算法的“大脑”。我们为每个臂i维护一个正数权重w_i。算法通过以下公式计算选择臂i的概率p_i。

首先，给定一个参数$\eta > 0$，称为学习率。它控制了我们根据新证据更新权重的速度。$\eta$越大，对最近结果的反应越激烈。

计算概率p_i的核心公式是：

$$p_i = (1 - \gamma) \frac{w_i}{\sum_{j=1}^{K} w_j} + \frac{\gamma}{K}$$

这个公式由两部分组成：

1. 利用部分：(1 - γ) * (w_i / 总权重和)。这部分是纯粹的利用，权重w_i越大的臂，从这部分获得的选择概率越高。γ是一个介于0和1之间的参数，用于平衡探索与利用。
2. 探索部分：γ / K。这部分为每个臂都均匀地增加一个最小概率，确保每个臂都有机会被尝试，这是对抗环境变化的关键保障。

因此，最终的选择概率是“按权重分配的利用概率”与“均匀分布的探索概率”的混合体。

4. 指数加权策略详解：权重的更新

在第t轮，我们根据计算出的概率p_i(t)随机选择了臂i(t)，并获得了奖励$x_i(t)$（通常将奖励标准化到[0,1]区间）。接下来，需要更新权重。

只更新被选中的那个臂的权重。更新规则如下：

$$w_i(t+1) = w_i(t) \cdot \exp\left( \frac{\eta \cdot \hat{x}_i(t)}{K \cdot p_i(t)} \right) \quad \text{仅当} i = i(t)$$

其中，$\hat{x}_i(t)$ 是对原始奖励$x_i(t)$的一个估计。由于我们只观察了被选中臂的奖励，对于未被选中的臂，我们什么都不知道。因此，我们使用以下估计量：

$$\hat{x}_i(t) = \begin{cases} \frac{x_i(t)}{p_i(t)} & \text{如果 } i = i(t) \\ 0 & \text{否则} \end{cases}$$

这个估计的意义在于：虽然未被选中的臂获得了0奖励，但被选中的臂的奖励被“放大”了，放大倍数是1/p_i(t)。这是一种反概率加权技巧，目的是在只知道部分信息的情况下，构造出对整体期望的一个无偏估计。

因此，权重的更新公式可以直观理解为：根据估计奖励，以指数方式调整被选中臂的权重。估计奖励越高（即$x_i(t)/p_i(t)$越大），权重w_i增长得越快。学习率$\eta$控制了增长的速度。

5. 实践步骤：实现Exp3算法

以下是实现Exp3算法的具体操作步骤。

1. 初始化参数与权重。

   • 确定臂的数量K。
   • 设置学习率η（例如，可设为$\sqrt{\frac{\ln K}{T \cdot K}}$，其中T是总轮数）。
   • 设置探索参数γ（例如，$\gamma = \min\{1, \sqrt{\frac{K \ln K}{(e-1)T}}\}$）。
   • 将每个臂的初始权重w_i设为1。

2. 开始循环（对于每一轮t = 1, 2, ..., T）。

   • 计算：根据当前所有臂的权重{w_1, ..., w_K}和公式，计算出每个臂的选择概率{p_1, ..., p_K}。
   • 选择：根据概率分布{p_1, ..., p_K}，随机选择一个臂i(t)。
   • 观察：获取该轮被选中臂i(t)的奖励$x_i(t)$。
   • 估计：计算该臂的估计奖励：$\hat{x}_{i(t)}(t) = x_i(t) / p_{i(t)}(t)$。其他臂的估计奖励为0。
   • 更新：更新被选中臂i(t)的权重：$w_{i(t)}(t+1) = w_{i(t)}(t) \cdot \exp\left( \frac{\eta \cdot \hat{x}_{i(t)}(t)}{K \cdot p_{i(t)}(t)} \right)$。其他臂的权重保持不变。

3. 结束循环。
   算法结束。你可以分析整个过程中各个臂被选择的频率以及累积奖励，来评估策略的有效性。

通过以上步骤，Exp3算法利用指数加权策略，在对抗性环境中实现了探索与利用的平衡。其数学保证是，无论对手如何设置奖励，你的策略所产生的总奖励与在知道所有未来奖励情况下的最优固定臂策略的总奖励之间的差距，被控制在$O(\sqrt{KT \ln K})$的量级内。