多臂老虎机

多臂老虎机问题

题目描述：

​ 有一个拥有 KK 根拉杆的老虎机(multi-armed bandit)，拉动每一根拉杆都对应一个关于奖励的概率分布 R\mathcal{R}。我们每次拉动其中一根拉杆，就可以从该拉杆对应的奖励概率分布中获得一个奖励 rr。我们在各根拉杆的奖励概率分布未知的情况下，从头开始尝试，目标是在操作 TT 次拉杆后获得尽可能高的累积奖励。由于奖励的概率分布是未知的， 因此我们需要在**“探索拉杆的获奖概率”和“根据经验选择获奖最多的拉杆”**中进行权衡。“采用怎样的操作策略才能使获得的累积奖励最高”便是多臂老虎机问题

多臂老虎机问题可以表示为一个元组 ⟨A,R⟩\langle \mathcal{A,R} \rangle ，其中：

  • A\mathcal{A} 为动作集合，其中一个动作表示拉动一根拉杆，若多臂老虎机一共有 KK 根拉杆，那 动作空间就是集合 {a1,a2,...,ak}\{\boldsymbol {a_1, a_2, ..., a_k} \}，我们用 at∈A\boldsymbol a_t \in \mathcal{A} 表示任意一个动作
  • R\mathcal{R} 为奖励概率分布，拉动每一根拉杆的动作 aa 都对应一个奖励概率分布 R(r∣a)\mathcal{R}(r \mid \boldsymbol a) ，拉动不同拉杆的奖励分布通常是不同的

​ 假设每个时间步只能拉动一根拉杆，多臂老虎机的目标为最大化一段时间步 TT 内累积的奖励： max∑t=1Trt, rt∼R(⋅∣at)max \sum_{t=1}^{T} r_t, \ r_t \sim \mathcal{R}(\cdot \mid \boldsymbol a_t) 。其中 at\boldsymbol a_t 表示在第 tt 时间步拉动某一拉杆的动作，rtr_t 表示动作 at\boldsymbol a_t 获得的奖励

累计懊悔与期望奖励：

​ 对于每一个动作 a\boldsymbol a，我们定义其期望奖励为 Q(a)=Er∼R(⋅∣a)[r]Q(\boldsymbol a) = E_{r \sim \mathcal{R}(\cdot \mid \boldsymbol a)} [r]。于是，至少存在一根拉杆，它的期望奖励不小于拉动其他任意一根拉杆，我们将该最优期望奖励表示为 Q∗=maxa∈AQ(a)Q^* = max_{\boldsymbol a \in \mathcal{A}} Q(\boldsymbol a)。为了观察拉动一根拉杆的期望奖励离最优拉杆期望奖励的差距，我们引入愧悔（regret）概念。懊悔被定义为拉动当前拉杆的动作 a\boldsymbol a 与最优拉杆的期望奖励差，即 $ R(\boldsymbol a)=Q^*−Q(\boldsymbol a)$。累积懊悔（cumulative regret）即操作 TT 次拉杆后累积的噢悔总量，对于一次完整的 TT 步决策 {a1,a2,...,aT}\{\boldsymbol {a_1, a_2, ..., a_T} \}，累积懊悔为 σR=∑t=1TR(ai)\sigma_R = \sum_{t=1}^T R(\boldsymbol a_i)。MAB 问题的目标为最大化累积奖励，等价于最小化累积懊悔

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

对于 $ \forall \boldsymbol a \in \mathcal{A}$，初始化计数器 $N(\boldsymbol a)=0 $ 和期望奖励估值 Q^(a)=0\hat{Q}(\boldsymbol a)=0

for t = 1 to T do
选取某根拉杆，该动作记为 $ a_t $
得到奖励 $ r_t $
更新计数器： $ N(a_t) = N(a_t) + 1 $
更新期望奖励估值： $ \hat Q(a_t) = \hat Q(a_t) + \frac{1}{N(a_t)}[r_t - \hat Q(\boldsymbol a_t)] $
end for

由以下公式导出：

Q_k = \frac{1}{k} \underset{i=1} {\overset {T}\sum} r_i = \frac{1}{k}\left( r_k + \underset{i=1} {\overset {T-1}\sum} r_i = \frac{1}{k}\right) \\ = Q_{k-1} + \frac{1}{k}[r_k -Q_{k-1}]

​ 以一个拉杆数为 10 的多臂老虎机为例。其中拉动每根拉杆的奖励服从伯努利分布（Bernoulli distribution），即每次拉下拉杆有 pp 的概率获得的奖励为 1，有 1−p1 − p 的概率 获得的奖励为 0

​ 用一个 Solver 基础类来实现上述的多臂老虎机的求解方案。我们需要实现下列函数功能：根据策略选择动作、根据动作获取奖励、更新期望奖励估值、 更新累积懊悔和计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class BernoulliBandit:
    """ 伯努利多臂老虎机,输入K表示拉杆个数 """
    def __init__(self, K):
        self.probs = np.random.uniform(size=K)
        self.best_idx = np.argmax(self.probs)
        self.best_prob = self.probs[self.best_idx]
        self.K = K

    def step(self, k):
        if np.random.rand() < self.probs[k]:
            return 1
        else:
            return 0

class Solver:
    """ 多臂老虎机算法基本框架 """
    def __init__(self, bandit):
        self.bandit = bandit
        self.counts = np.zeros(self.bandit.K)
        self.regret = 0.
        self.actions = []
        self.regrets = []

    def update_regret(self, k):
        self.regret += self.bandit.best_prob - self.bandit.probs[k]
        self.regrets.append(self.regret)

    def run_one_step(self):
        # 返回当前动作选择哪一根拉杆,由每个具体的策略实现
        # 具体策略全部继承于这个类
        raise NotImplementedError

    def run(self, num_steps):
        for _ in range(num_steps):
            k = self.run_one_step()
            self.counts[k] += 1
            self.actions.append(k)
            self.update_regret(k)

​ 代码来自动手学强化学习，这本书的代码风格还是很好的，代码结构很值得一学，我们要定义这么多的类的原因是为了高度的可扩展性，通过Slover这个类，我们可以随意地添加新的概率分布的老虎机，也可以随意添加新的策略算法实现

策略算法实现：

​ 设计策略时就需要平衡探索和利用的次数，使得累积奖励最大 化。一个比较常用的思路是在开始时做比较多的探索，在对每根拉杆都有比较准确的估计后， 再进行利用

贪婪算法：

​ 完全贪婪算法即在每一时刻采取期望奖励估值最大的动作（拉动拉杆），这就是纯粹的利用， 而没有探索，所以我们通常需要对完全贪婪算法进行一些修改，其中比较经典的一种方法为ϵ\epsilon -贪婪 （ϵ\epsilon -Greedy）算法。它在完全贪婪算法的基础上添加了噪声，每次以概率1−ϵ1−\epsilon 选择以往经验中期望奖励估值最大的那根拉杆（利用），以概率 ϵ\epsilon 随机选择一根拉杆（探索）

at{argmax⁡a∈AQ^(a) 采样概率: 1−ϵ从A中随机选择，采样概率: ϵ\boldsymbol{a}_t \left\{ \begin{array}{c} arg\underset{\boldsymbol{a}\in \mathcal{A}}{\max}\hat Q(\boldsymbol a) \ \text{采样概率:}\ 1-\epsilon \\ \text{从} \mathcal{A} \text{中随机选择，采样概率:} \ \epsilon \\ \end{array} \right.

​ 随着探索次数的不断增加，我们对各个动作的奖励估计得越来越准，此时就没必要继续花大力气进行探索。所以具体实现中，我们可以令 ϵ\epsilon 随时间衰减。但是请注意，ϵ\epsilon 不会在有限的步数内衰减至 0，因为基于有限步数观测的完全贪婪算法仍然是一个局部信息的贪婪算法，永远距离最优解有一个固定的差距

上置信界算法

​ 我们引入不确定性度量 U(a)U(a) ，它会随着一个动作被尝试次数的增加而减小。我们使用一种基于不确定性的策略来综合考虑现有的期望奖励估值和不确定性，其核心问题是如何估计不确定性。

​ 上置信界（upper confidence bound，UCB）算法是一种经典的基于不确定性的策略算法， 它用到了霍夫丁不等式（Hoeffding’s inequality）：

​ 令 X1,X2,...,XnX_1, X_2, ..., X_n 为 nn 个独立同分布的随机变量，取值范围为 [0,1][0,1]，其经验期望为 xˉn=1n∑j=1nXj\bar x_n = \frac{1}{n} \sum_{j=1}^n X_j ，则有：

P(E[x]≥xˉt+u)≤e−2nu2P(E[x] \geq \bar x_t + u) \leq e^{-2nu^2}