强化学习—— 2 多臂老虎机

可爱可倾2024-09-172025-05-29

2 多臂老虎机

多臂老虎机中的探索与利用（exploration vs. exploitation）问题一直以来都是一个特别经典的问题，理解它能够帮助我们学习强化学习。与强化学习不同，多臂老虎机不存在状态信息，只有动作和奖励，算是最简单的“和环境交互中的学习”的一种形式。

2.1 问题介绍

2.1.1 问题定义

有一个拥有\(K\)根拉杆的老虎机，拉动每一根拉杆都对应一个关于奖励的概率分布\(R\)。我们需要在“探索拉杆的获奖概率”和“根据经验选择获奖最多的拉杆”中进行权衡。“采用怎样的操作策略才能使获得的累积奖励最高”便是多臂老虎机问题。

2.1.2 形式化描述

多臂老虎机问题可以表示为一个元组 \((A, R)\)

\(A\) 表示动作集合，一个动作表示拉动一根拉杆，\(A = \{a_1, a_2, ..., a_K\}\)
\(R\) 表示奖励概率分布，\(R(r|a)\) 表示当动作\(a\) 作用在环境上后得到的奖励\(r\)的概率分布

多臂老虎机的目标为最大化一段时间步内累积的奖励

2.1.3 累计懊悔

至少存在一根拉杆，它的期望奖励不小于拉动其他任意一根拉杆的期望奖励。我们称这个拉杆为最优拉杆，对应的期望奖励为最优期望奖励。我们可以定义累计懊悔（cumulative regret）为我们在一段时间内获得的奖励与最优期望奖励之间的差值总额。

MAB 问题的目标为最大化累积奖励，等价于最小化累积懊悔。

2.1.4 估计期望奖励

为了知道拉动哪一根拉杆能获得更高的奖励，我们需要估计拉动这根拉杆的期望奖励。由于只拉动一次拉杆获得的奖励存在随机性，所以需要多次拉动一根拉杆，然后计算得到的多次奖励的期望。

更新期望奖励通常采用增量法，即

\[ Q_{t+1} = Q_t + \frac{1}{t+1} \left( r_t - Q_t \right) \]

如果将所有数求和再除以次数，其缺点是每次更新的时间复杂度和空间复杂度均为 \(O(n)\)。而采用增量式更新，时间复杂度和空间复杂度均为 \(O(1)\)。

2.2 探索与利用的权衡

在多臂老虎机问题中，设计策略时就需要平衡探索和利用的次数，使得累积奖励最大化。一个比较常用的思路是在开始时做比较多的探索，在对每根拉杆都有比较准确的估计后，再进行利用。目前已有一些比较经典的算法来解决这个问题，例如 \(\epsilon\)-贪婪算法、上置信界算法和汤普森采样算法等。

2.3 \(\epsilon\)-贪婪算法

\(\epsilon\)-贪婪算法即在完全贪婪的基础上添加了噪声，以\(\epsilon\)的概率进行探索(随机选择一根拉杆)，以\(1-\epsilon\)的概率进行利用(选择以往经验中期望奖励估值最大的那根拉杆)。

随着探索次数的增加，可以让\(\epsilon\)逐渐减小，从而逐渐增加利用的次数。因为随着探索次数的增加，我们对各个动作的评估会越来越准，因此也就可以不必多次尝试同一个动作。

注意，\(\epsilon\) 不会在有限步数内减小到 0(因为基于有限步数观测的完全贪婪算法仍然是一个局部信息的贪婪算法，永远距离最优解有一个固定的差距)。

2.4 上置信界算法

一根拉杆被拉取的次数越少，它的不确定性就越大；一根拉杆的不确定性越大，它就越具有探索的价值，因为探索之后我们可能发现它的期望奖励很大。引入不确定性度量 \(U(a)\) ，它会随着一个动作被尝试次数的增加而减小。

上置信界算法（Upper Confidence Bound, UCB）是一种经典的基于不确定性的策略算法，它的思想用到了一个非常著名的数学原理：霍夫丁不等式。

UCB 算法在每次选择拉杆前，先估计每根拉杆的期望奖励的上界，使得拉动每根拉杆的期望奖励只有一个较小的概率超过这个上界，接着选出期望奖励上界最大的拉杆，从而选择最有可能获得最大期望奖励的拉杆。

2.5 汤普森采样算法

汤普森采样算法使用采样的方式，即根据当前每个动作 \(a\)的奖励概率分布进行一轮采样，得到一组各根拉杆的奖励样本，再选择样本中奖励最大的动作。

怎样得到当前每个动作\(a\)的奖励概率分布并且在过程中进行更新？在实际情况中，我们通常用 Beta 分布对当前每个动作的奖励概率分布进行建模。例如若某个拉杆被拉取了 \(K\) 次，其中 \(m_1\) 次奖励为 1，\(m_2\) 次奖励为 0，那么该动作的奖励服从参数为 \((m_1+1, m_2+1)\) 的 Beta 分布。