多臂赌博机

Posted on

多臂赌博机

一台赌博机有多个摇臂，每个摇臂摇出的奖励（reward）大小不确定，玩家希望摇固定次数的臂所获得的期望累计奖励最大。

1. 问题形式化

  • 行为：摇哪个臂
  • 奖励：每次摇臂获得的奖金
  • \(A_t\)表示第\(t\)轮的行为，\(R_t\)表示第\(t\)轮获得的奖励
  • 采取行为\(a\)的期望奖励为：\(q_*(a) \doteq E[R_t | A_t = a]\)

2. 贪心策略

一般情况下，\(q_*(a)\)对于玩家而言是未知的或具有不确定性，玩家在第\(t\)轮时只能依赖于当时对\(q_*(a)\)的估值\(Q_t(a)\)进行选择。

贪心策略是在第\(t\)轮选择\(Q_t(a)\)最大的\(a\)。

3. Exploitation vs. Exploration

Exploitation:

  • 按照贪心策略进行选择，即选择\(Q_t(a)\)最大的行为\(a\)；
  • 优点：最大化即时奖励；
  • 缺点：由于\(Q_t(a)\)只是对\(q_*(a)\)的估计，估计的不确定性导致按照贪心策略选择的行为不一定是使\(q_*(a)\)最大的行为。

Exploration:

  • 选择贪心策略之外的行为（non-greedy actions）；
  • 缺点：短期奖励会比较低；
  • 优点：长期奖励会比较高，因为Exploration可以找到奖励更大的行为，供后续选择。

每一步的选择只能在exploitation和exploration之间选择，如何平衡exploitation和exploration是关键问题。

4. 行为估值方法

根据历史观测样本的均值对\(q_*(a)\)进行估计： \[Q_t(a) \doteq \frac{ \text{sum of rewards when a taken prior to t}}{\text{number of times a taken prior to t}} = \frac{\sum_{i=1}^{t-1} R_i \cdot \mathbf{1}_{A_i = a}}{\sum_{i=1}^{t-1} \mathbf{1}_{A_i=a}}\]

  • 当分母等于0时，\(Q_t(a) = 0\)；
  • 当分母趋于无穷大时，\(Q_t(a)\)收敛到\(q_*(a)\)。

5. 贪心策略和\(\varepsilon\)贪心策略

贪心策略形式化地表示为 \[A_t \doteq \mathop{\arg\max}_a Q_t(a)\] 当有多个行为的\(Q_t(a)\)同时为最大时，随机选择一个。

\(\varepsilon\)贪心策略：

  • 以概率\(\varepsilon\)按照贪心策略进行行为选择——exploitation；
  • 以概率\(1 - \varepsilon\)在所有行为中随机选择一个——exploration；
  • \(\varepsilon\)的取值取决于\(q_*(a)\)的方差，方差越大\(\varepsilon\)取值越大。

6. 贪心策略的增量式实现

行为估值时，一个行为被选择了\(n\)次后的估值记为 \[Q_n \doteq \frac{R_1 + R_2 + \cdots + R_{n-1}}{n-1}\] 该估值方式需要记录\(n-1\)个奖励值。

增量式实现： \[\begin{align} Q_{n+1} &= \frac{1}{n} \sum_{i=1}^n R_i \nonumber \\ &= \frac{1}{n} (R_n + \sum_{i=1}^{n-1}R_i) \nonumber \\ &= \frac{1}{n} (R_n + (n-1) \frac{1}{n-1} \sum_{i=1}^{n-1}R_i) \nonumber \\ &= \frac{1}{n} (R_n + (n-1)Q_n) \nonumber \\ &= \frac{1}{n} (R_n + n Q_n - Q_n) \nonumber \\ &= Q_n + \frac{1}{n} [R_n - Q_n] \nonumber \end{align}\]

此时只需要记录\(Q_n\)和\(n\)两个值。

伪代码：

bandit(A)：采取行动A，返回这次行动获得的奖励。

行为估值更新
更新公式： \[ NewEstimate \gets OldEstimate + StepSize [Target - OldEstimate]\] \((Target - OldEstimate)\)表示估计误差。

  • 对于贪心策略的增量实现而言，步长为\(\frac{1}{n}\)；
  • 更一般的情况：步长用参数\(\alpha\)或\(\alpha_t(a)\)表示。

7. 非平稳问题

平稳问题：

  • \(q_*(a)\)是稳定的，不随时间而变化；
  • 随着观测样本的增加，平均值估计方法最终收敛于\(q_*(a)\)。

非平稳问题：

  • \(q_*(a)\)是关于时间的函数；
  • 对\(q_*(a)\)的估计需要更关注最近的观测样本。

8. 非平稳情形下的行为估值

行为估值的更新公式： \[Q_{n+1} \doteq Q_n + \alpha [R_n - Q_n]\]

递推得到： \[\begin{align} Q_{n+1} &= Q_n + \alpha [R_n - Q_n] \nonumber \\ &= \alpha R_n + (1-\alpha) Q_n \nonumber \\ &= \alpha R_n + (1-\alpha)[\alpha R_{n-1} + (1-\alpha) Q_{n-1}] \nonumber \\ &= \alpha R_n + (1 - \alpha) \alpha R_{n-1} + (1-\alpha)^2 Q_{n-1} \nonumber \\ &= \alpha R_n + (1 - \alpha) \alpha R_{n-1} + \cdots + (1-\alpha)^{n-1} \alpha R_1 + (1-\alpha)^n Q_1 \nonumber \\ &= (1-\alpha)^n Q_1 + \sum_{i=1}^n \alpha (1-\alpha)^{n-i} R_i \nonumber \end{align}\]

对应于指数“新近”带权平均。

更新步长的选择：

并不是所有的步长选择\(\alpha_n(a)\)都保证收敛：

  • \(\alpha_n(a) = \frac{1}{n}\)收敛；
  • \(\alpha_n(a) = \alpha\)不收敛。

收敛条件： \[\sum_{n=1}^{\infty} \alpha_n(a) = \infty \quad and \quad \sum_{n=1}^{\infty} \alpha_n^2(a) < \infty\]

  • 第一个条件保证步长足够大，克服初值或随机扰动的影响；
  • 第二个条件保证步长最终会越来越小，小到保证收敛。

行为选择策略：

  • 平衡exploitation和exploration，应对行为估值的不确定性；
  • 关键：确定每个行为被选择的概率。

9. 乐观初值法

行为的初始估值：

  • 前述贪心策略中，每个行为的初始估值为0；
  • 每个行为的初始估值可以帮助我们引入先验知识；
  • 初始估值还可以帮助我们平衡exploitation和exploration。

乐观初值法（Optimistic Initial Values）：

  • 为每个行为赋一个高的初始估值；
  • 好处：初期每个行为都有较大机会被explore。

10. UCB行为选择策略

UCB：Upper-Confidence-Bound： \[A_t \doteq \mathop{\arg \max}_a [Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}}]\] 其中\(N_t(a)\)表示时刻\(t\)之前行为\(a\)被选择的次数。

公式解读：

  • 选择潜力大的行为：依据估值的置信上界进行行为选择；
  • 第一项表示当前估值要高，即接近greedy action；
  • 第二项表示不确定性要高，即被选择的次数少；
  • 参数用来控制exploration的程度。

UCB策略一般会优于\(\varepsilon\)贪心策略，不过最初几轮相对较差。

UCB策略实现起来比\(\varepsilon\)贪心策略要复杂，在多臂赌博机之外的强化学习场景中使用较少。

11. 梯度赌博机算法

  • 目标：优化每轮的期望奖励大小； \[E[R_t] = \sum_b \pi_t(b) q_*(b)\]
  • 使用\(H_t(a)\)表示在第\(t\)轮对行为\(a\)的偏好程度；
  • 在第\(t\)轮选择行为\(a\)的概率为 \[Pr \{A_t = a\} \doteq \frac{e^{H_t(a)}}{\sum_{b=1}^k e^{H_t(b)}} \doteq \pi_t(a)\]
  • 更新公式： \[\begin{equation} H_{t+1}(A_t) \doteq H_t(A_t) + \alpha(R_t - \bar{R}_t)(1 - \pi_t(A_t)), \quad and \nonumber \\ H_{t+1}(a) \doteq H_t(a) - \alpha (R_t - \bar{R}_t) \pi_t(a), \quad \text{for all} \quad a \neq A_t \nonumber \end{equation}\]

等价于随机梯度上升。

12. 不同策略对比

UCB策略表现相对较好。

13. 多臂赌博机的应用案例

手机客户端新闻或广告的投放。

14. 小结

多臂赌博机是强化学习的一个简化场景：

  • 行为和状态之间没有关联关系；

扩展情形——有上下文的多臂赌博机：

  • 存在多个多臂赌博机，状态表示赌博机；
  • 学习状态到行为的映射；
  • 但行为不改变状态。

更一般的情形：

  • 马尔科夫决策过程。