强化学习 多臂赌博机

• 强化学习与其他机器学习方法最大的不同，就在于前者的训练信号是用来评估给定动作的好坏的，而不是通过给出正确动作范例来进行直接的指导。

一个$k$臂赌博机问题

• $k$个动作中的每一个在被选择时都有一个期望或者平均收益，称为这个动作的价值。将在时刻$t$时选择的动作记作$A_t$，并将对应收益记作$R_t$。任一动作$a$对应的价值，记作$q_{\ast }(a)$，是给定动作$a$时收益期望：
  $$q_{\ast }(a)=E[R_t|A_t=a]$$
  我们将对动作$a$在时刻t时的价值的估计记作$Q_t(a)$，我们希望它接近$q_{\ast }(a)$。
• 当你从这些动作中选择时，我们称为开发当前你所知道的关于动作的价值的知识。选择非贪心的动作，称为试探，因为这可以让你改善对非贪心动作的价值的估计
• 到底选择“试探”还是“开发”一种复杂的方式依赖与我们得到的函数估计、不确定性和剩余时刻的精确数值。
• 开发和试探的平衡是强化学习中的一个问题。

动作-价值方法

• 使用价值的估计来进行动作选择，这一类方法被统称为“动作-价值方法”。
• 一种自然的方式就是通过计算实际收益的平均值来估计动作的价值：
  $$Q_t(a)=\frac{t时刻前通过执行动作a得到的收益总和}{t时刻前执行动作a的次数}=\frac{{\sum }_{i=1}^{t-1}{R}_i\cdot I_{A_i=a}}{{\sum }_{i=1}^{t-1}{I}_{A_i=a}}$$
  其中，$I_{predicate}$表示随机变量，当$predicate$为真时其值为1，反之为0。当分母为0时，我们将$Q_t(a)$定义为某个默认值，比如$Q_t(a)=0$。当分母趋向于无穷大时，根据大数定律，$Q_t(a)$会收敛到$q_{\ast }(a)$
• 我们将这种估计动作价值的方法称为采样平均方法，因为每一次估计都是相关收益样本的平均。
• 最简单的动作选择规则是选择具有最高估计值的动作，如果有多个贪心动作，那就任意选择一个，比如随机挑选，我们将这种贪心动作的选择方法记作：
  $$A_t=\underset{a}{\mathrm{argmin}}{Q}_t(a)$$
  其中，$\underset{a}{\mathrm{argmin}}$是使得$Q_t(a)$值最大的动作$a$
• 贪心策略的一个简单代替策略是大部分时间都表现得很贪心，但偶尔（比如以一个很小的概率$ϵ$）以独立于动作-价值的估计方式从所有动作中等概率随机地做出选择。我们将使用这种近乎贪心的选择规则方法称为$ϵ$-贪心方法。
• $ϵ$-贪心方法的优点是，如果时刻可以无限长，则每一个动作都会被无限次采样，从而确保所有的$Q_t(a)$收敛到$q_{\ast }a$。这意味着选择最优动作的概率会收敛到大于$1-ϵ$。

10臂测试平台

• 从长远来看，贪心方法表现明显很糟糕，因为它经常陷入执行次优动作的怪圈。$ϵ$-贪心方法最终表现更好，因为他们持续地试探并且提升找到最优动作的机会。
• $ϵ=0.1$相较于$ϵ=0.01$方法试探得更多，通常更早发现最优的动作，但是在每时刻选择这个最优动作的概率却永远不会超过91%。
• $ϵ$-贪心方法相对于贪心方法的优点依赖于任务。比如，假设收益的方差更大，不是1而是10，由于收益的噪声更多，所以为了找到最优的动作需要更多次的试探，$ϵ$-贪心方法会更有优势。
• 如果收益方差为0，那么贪心方法会在尝试一次之后就知道每一个动作的真实价值。在这种情况下，贪心方法实际上可能表现最好。因为它很开就会找到最佳的动作，然后再也不会进行试探。

增量式实现

• 至今我们讨论的动作-价值方法都把动作价值作为观测到的收益的样本均值来估计。
• 令$R_i$表示这一动作被选择$i$次后获得的收益，$Q_n$表示被选择$n-1$次后它的估计的动作价值，可以简写为：
  $$Q_n=\frac{R_1+R_2+\cdots +R_{n-1}}{n-1}$$
• 为了计算每个新的收益，很容易设计增量式公式以小而恒定的计算来更新平均值。给定$Q_n$和第$n$次的收益$R_n$，所有$n$个收益的新均值：
  Q n + 1 = 1 n ∑ i = 1 n R i = 1 n ( R n + ∑ i = 1 n − 1 R i ) = 1 n ( R n + ( n − 1 ) 1 n − 1 ∑ i = 1 n − 1 R i ) = 1 n ( R n + ( n − 1 ) Q n ) = 1 n ( R n + n Q n − Q n ) = Q n + 1 n [ R n − Q n ]
  Qn+1=1n∑i=1nRi=1n(Rn+∑i=1n−1Ri)=1n(Rn+(n−1)1n−1∑i=1n−1Ri)=1n(Rn+(n−1)Qn)=1n(Rn+nQn−Qn)=Qn+1n[Rn−Qn]" role="presentation" style="position: relative;">Qn+1=1n∑i=1nRi=1n(Rn+∑i=1n−1Ri)=1n(Rn+(n−1)1n−1∑i=1n−1Ri)=1n(Rn+(n−1)Qn)=1n(Rn+nQn−Qn)=Qn+1n[Rn−Qn]$$\begin{array}{rl}{Q}_{n+1}& =\frac{1}{n}\sum _{i=1}^n{R}_i\\ & =\frac{1}{n}(R_n+\sum _{i=1}^{n-1}{R}_i)\\ & =\frac{1}{n}(R_n+(n-1)\frac{1}{n-1}\sum _{i=1}^{n-1}{R}_i)\\ & =\frac{1}{n}(R_n+(n-1)Q_n)\\ & =\frac{1}{n}(R_n+n{Q}_n-Q_n)\\ & =Q_n+\frac{1}{n}[R_n-Q_n]\end{array}$$
  Qn+1​​=n1​i=1∑n​Ri​=n1​(Rn​+i=1∑n−1​Ri​)=n1​(Rn​+(n−1)n−11​i=1∑n−1​Ri​)=n1​(Rn​+(n−1)Qn​)=n1​(Rn​+nQn​−Qn​)=Qn​+n1​[Rn​−Qn​]​​
• 更新公式的一般形式为：
  $$新估计值\leftarrow 旧估计值+步长\times [目标-旧估计值]$$
  表达式$[目标-旧估计值]$是估计值的误差。误差会随着向“目标”靠近的每一步而减小。虽然“目标中可能充满噪声”，但我们还是假定“目标”会告诉我们可行的前进方向。
• 增量式方法中的“步长”会随着时间而变化。处理动作$a$对应的第$n$个收益的方法用的步长是$\frac{1}{n}$。

跟踪一个非平稳问题

• 取平均方法对平稳的赌博机问题是合适的，即收益的概率分布不随着时间变化。但如果赌博机的收益概率是随着时间变化的该方法就不合适。
• 给近期的收益赋予比过去很久的收益更高的权值就是一种合理的处理方式，最流行的方法之一是使用固定步长。比如，用于更新$n-1$个过去的收益均值Q_{n}的增量更新规则可以改为：
  $$Q_{n+1}=Q_n+\alpha [R_n-Q_n]$$
• 随机逼近理论中的一个著名结果给出了保证收敛概率为1所需的条件：
  $$\sum _{n=1}^{\infty }{\alpha }_n(a)=\infty 且\sum _{n=1}^{\infty }{a}_n^2(a)<\infty$$
  第一个条件是要求保证有足够大的步长，最终客服任何初始条件或随机波动。第二个条件保证最终步长变小，以保证收敛。

练习2.5

• 参考代码地址，对代码中各函数做了详细注解

testbed.py

import numpy as np
from numpy.random import normal as GaussianDistribution


class K_armed_testbed():
    # k个可能动作中每一个的值开始相等
    # 然后进行独立的随机行走

    def __init__(self, k_actions):
        self.k = k_actions
        # np.full返回指定形状、类型和数值的数组
        self.action_values = np.full(self.k, fill_value=0.0)

    def random_walk_action_values(self):
        # 返回均值为0标准差为0.01的正态分布，形状为k的数组
        increment = GaussianDistribution(loc=0, scale=0.01, size=self.k)
        # 将每一步动作收益加上正态分布增量
        self.action_values += increment

    def sample_action(self, action_i):
        # 生成符合正态分布的随机数
        return GaussianDistribution(loc=self.action_values[action_i], scale=1, size=1)[0]

    def get_optimal_action(self):
        # 返回数组中最大值索引
        return np.argmax(self.action_values)

    def get_optimal_action_value(self):
        # 返回动作的最大收益
        return self.action_values[self.get_optimal_action()]

    def is_optimal_action(self, action_i):
        # 是否为最优动作
        return float(self.get_optimal_action_value() == self.action_values[action_i])

    def __str__(self):
        return "\t".join(["A%d: %.2f" % (action_i, self.action_values[action_i]) for action_i in range(self.k)])
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

estimators.py

import numpy as np

class Estimator(object):
    def __init__(self, action_value_initial_estimates):
        self.action_value_estimates = action_value_initial_estimates
        # 确定动作种类
        self.k_actions = len(action_value_initial_estimates)
        # 动作选择表，初始化为0，类型为整型
        self.action_selected_count = np.full(self.k_actions, fill_value=0, dtype="int64")

    def select_action(self):
        # 引发异常提示语
        raise NotImplementedError("Need to implement a method to select actions")

    def update_estimates(self):
        # 引发异常提示语
        raise NotImplementedError("Need to implement a method to update action value estimates")

    def select_greedy_action(self):
        # 返回动作收益最大数组索引
        return np.argmax(self.action_value_estimates)

    def select_action_randomly(self):
        # 随机选择动作
        return np.random.choice(self.k_actions)


# 平均采样方法类
class SampleAverageEstimator(Estimator):
    def __init__(self, action_value_initial_estimates, epsilon):
        # 继承父类
        super(SampleAverageEstimator, self).__init__(action_value_initial_estimates)
        self.epsilon = epsilon

    def update_estimates(self, action_selected, r):
        # 选择次数+1
        self.action_selected_count[action_selected] += 1
        # 动作收益
        qn = self.action_value_estimates[action_selected]
        # 选择次数
        n = self.action_selected_count[action_selected]
        # 更新Q值，学习率为变化步长1/n
        self.action_value_estimates[action_selected] = qn + (1.0 / n) * (r - qn)

    def select_action(self):
        # 取随机数
        probability = np.random.rand()
        # 是否采用贪心算法
        if probability >= self.epsilon:
            # 采用贪心算法
            return self.select_greedy_action()
        # 随机选择动作
        return self.select_action_randomly()


# 增量计算方法类
class WeightedEstimator(SampleAverageEstimator):
    def __init__(self, action_value_initial_estimates, epsilon=0, alpha=0.5):
        # 继承父类
        super(WeightedEstimator, self).__init__(action_value_initial_estimates, epsilon)
        # 学习率
        self.alpha = alpha

    def update_estimates(self, action_selected, r):
        # 动作收益
        qn = self.action_value_estimates[action_selected]
        # 更新Q值，学习率为固定步长alpha
        self.action_value_estimates[action_selected] = qn + self.alpha * (r - qn)
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

Exercise 2.5.py

import numpy as np
import matplotlib.pyplot as plt
from tqdm import tqdm
from estimators import SampleAverageEstimator, WeightedEstimator
from testbed import K_armed_testbed

# 固定随机数种子
np.random.seed(250)


# 绘图函数
def plot_performance(estimator_names, rewards, action_optimality):
    for i, estimator_name in enumerate(estimator_names):
        average_run_rewards = np.average(rewards[i], axis=0)
        plt.plot(average_run_rewards, label=estimator_name)

    plt.legend()
    plt.xlabel("Steps")
    plt.ylabel("Average reward")
    plt.show()

    for i, estimator_name in enumerate(estimator_names):
        average_run_optimality = np.average(action_optimality[i], axis=0)
        plt.plot(average_run_optimality, label=estimator_name)
    plt.legend()
    plt.xlabel("Steps")
    plt.ylabel("% Optimal action")
    plt.show()


if __name__ == "__main__":
    # 10臂老虎机
    K = 10
    # 10000个时刻
    N_STEPS = 10000
    # 2000个不同赌博机问题
    N_RUNS = 2000
    N_ESTIMATORS = 2

    # 收益矩阵，形状为2 * 2000 * 10000，元素置0
    rewards = np.full((N_ESTIMATORS, N_RUNS, N_STEPS), fill_value=0.)
    # 最优选择矩阵，形状为2 * 2000 * 10000，元素置0
    optimal_selections = np.full((N_ESTIMATORS, N_RUNS, N_STEPS), fill_value=0.)

    # 2000个赌博机
    for run_i in tqdm(range(N_RUNS)):
        # 实例化类
        testbed = K_armed_testbed(k_actions=K)
        # 动作价值估计表，形状1*10
        action_value_estimates = np.full(K, fill_value=0.0)
        # 实例化采样平均方法类
        sample_average_estimator = SampleAverageEstimator(action_value_estimates.copy(), epsilon=0.1)
        # 实例化增量式方法类，学习率为0.1
        weighted_estimator = WeightedEstimator(action_value_estimates.copy(), epsilon=0.1, alpha=0.1)

        estimators = [sample_average_estimator, weighted_estimator]

        # 10000个时刻
        for step_i in range(N_STEPS):
            # 两种方法
            for estimator_i, estimator in enumerate(estimators):
                # 根据贪心算法选择动作
                action_selected = estimator.select_action()
                # 是否为最优收益
                is_optimal = testbed.is_optimal_action(action_selected)
                # 收益为正态分布随机数
                reward = testbed.sample_action(action_selected)
                # 更新Q值
                estimator.update_estimates(action_selected, reward)
                # 记录收益
                rewards[estimator_i][run_i][step_i] = reward
                # 记录是否选择最大收益
                optimal_selections[estimator_i][run_i][step_i] = is_optimal
            # 将每一步动作收益加上正态分布增量
            testbed.random_walk_action_values()

    plot_performance(["Ɛ=0.1", "Ɛ=0.1 α=0.1"], np.array(rewards), np.array(optimal_selections))
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

乐观初始值

• 目前为止我们讨论的所有方法都在一定程度上依赖于初始动作值$Q_1(a)$的选择。
• 初始动作的价值提供了一种简单的试探方式。比如一个10臂测试平台，我们将初始值全部设为+5，因为$q_{\ast }(a)$是按照均值为0方差为1的正态分布选择的。因此无论哪一种动作被选择，收益都比最开始的估计值要小；因此学习器会对得到的收益感到“失望”，从而转向另一个动作。
• 我们把这种鼓励试探的技术叫作乐观初始价值，在平稳问题中非常有效，但它远非鼓励试探的普遍有用方法。例如它不太适合非平稳问题，因为它试探的驱动力天生是暂时的。

基于置信度上界的动作选择

• $ϵ$-贪心方法会尝试选择非贪心的动作，但是这是一种盲目的选择，因为它不大会去选择接近贪心或者不确定性特别大的动作。
• 在非贪心动作中，最好是根据它们的潜力来选择可能事实上是最优的动作，在就要考虑到它们的估计有多接近最大值，以及这些估计的不确定性。
• 一个有效的方法是按照以下公式选择动作：
  $$A_t\doteq \underset{a}{\mathrm{argmin}}\left[Q_t(a)+c\sqrt{\frac{lnt}{N_t(a)}}\right]$$
  其中$lnt$表示$t$的自然对数，$N_t(a)$表示在时刻$t$之前动作$a$被选择的次数。$c$是一个大于0的数，它控制试探的程度。如果$N_t(a)=0$，则$a$就被任务是满足最大化条件的动作。
• 这种基于置信度上界的动作选择的思想是，平方根项是对$a$动作值估计的不确定性或方差的度量。
• UCB（置信度上界）算法比较难处理非平稳问题，另一方面难处理打的状态空间。

梯度赌博机算法

• 在本节中，我们针对每个动作$a$考虑学习一个数值化的偏好函数$H_t(a)$。
• 偏好函数越大，动作就越频繁地被选择，但偏好函数的概率并不是从“收益”的意义上提出的。只有一个动作对另一个动作的相对偏好才是重要的。
• 如果我们给每一个动作的偏好函数都加上1000，那么对于按照softmax分布确定的动作概率没有任何影响：
  P r { A t = a } ≐ e H t ( a ) ∑ b = 1 k e H t ( a ) ≐ π t ( a ) Pr\{A_t = a\}\doteq\frac{e^{H_t(a)}}{\sum_{b=1}^{k}e^{H_t(a)}}\doteq\pi_t(a) Pr{At​=a}≐∑b=1k​eHt​(a)eHt​(a)​≐πt​(a)
  其中，${\pi }_t(a)$是一个新的且重要的定义，用来表示动作$a$在时刻$t$时被选择的概率。所有偏好函数的初始值都是一样的，所以每个动作被选择的概率是相同的。
• 基于梯度上升思想，提出一种自然学习算法。在每个步骤中，在选择动作$A_t$并获得$R_t$之后，偏好函数将会按如下方式更新：
  $$\begin{gathered} H_{t+1}(A_t)\doteq H_t(A_t)+\alpha (R_t-{\overline{R}}_t)(1-{\pi }_t(A_t)),以及 \\ {H}_{t+1}(a)\doteq H_t(a)-\alpha (R_t-{\overline{R}}_t){\pi }_t(a),对所有a\ne A_t \end{gathered}$$
  其中，$\alpha$是一个大于0的数，表示步长。${\overline{R}}_t$项作为比较收益的一个基准项。如果收益高于它，那么在未来选择动作$A_t$的概率就会增加，反之概率就会降低。未选择的动作被选择的概率上升。
• 对非关联任务，当任务是平稳的时候，学习器会试图寻找一个最佳的动作；当任务是非平稳的时候，最佳动作会随着时间的变化而改变，此时它会试着去追踪最佳动作。
• 在一般的强化学习任务中，往往有不止一种情境，它们的目标是学习一种策略：一个从特定情境到最优动作的映射。

本章小节

• $ϵ$-贪心方法在一小段时间内进行随机的动作选择。
• 而UCB方法虽然采用确定的动作选择，却可以通过在每个时刻对那些具有较少样本的动作进行优先选择来实现试探。
• 梯度赌博机算法则不估计动作价值，而上利用偏好函数，使用softmax分布来以一种分级的、概率式的方式选择更优的动作。
• 贝叶斯方法假定已知动作价值的初始分布，然后在每步之后更新分布（假定真实的动作价值是平稳的）