多臂老虎机 “Multi-armed Bandits”

将强化学习与机器学习、深度学习区分开的最重要的特征为：它通过训练中信息来评估所采取的动作，而不是给出正确的动作进行指导，这极大地促进了寻找更优动作的需求。

1、多臂老虎机（Multi-armed Bandits）问题

赌场的老虎机有一个绰号叫单臂强盗（single-armed bandit），因为它即使只有一只胳膊，也会把你的钱拿走。而一排老虎机就引申出多臂强盗（多臂老虎机）。

多臂老虎机（Multi-armed Bandits）问题可以描述如下：一个玩家走进一个赌场，赌场里有 $k$ 个老虎机，每个老虎机的期望收益不一样。假设玩家总共可以玩 $t$ 轮， 在每一轮中，玩家可以选择这 $k$ 个老虎机中的任一个，投入一枚游戏币，拉动摇杆，观察是否中奖以及奖励的大小。
问题，玩家采取怎么样的策略才能最大化这 $t$ 轮的总收益？

$k$ 个老虎机（对应 $k$ 个动作选择），每一个动作都有其预期的奖励，称其为该动作的价值。记第 $t$ 轮选择的动作为 $A_t$，相应的奖励为 $R_t$，那么任意动作 $a$ 的价值记为 $q_{?}(a)$，即动作 $a$ 的期望奖励：
$$q_{?}(a)?\mathbb{E}[R_t|A_t=a]$$

如果知道每个动作的价值，那么问题就简单了：总是选择价值最高的动作。如果不知道的话，我们需要对其进行估计，令动作 $a$ 在时间步长为 $t$ 的价值估计为 $Q_t(a)$，我们希望 $Q_t(a)$ 尽可能地接近 $q_{?}(a)$。

2、动作价值方法

通过估计动作价值，然后依据动作价值作出动作选择的方法，统称为动作价值方法。某个动作的真实价值应当是该动作被选择时的期望奖励，即
$$Q_t(a)?\frac{t时刻之前，a被选中的总奖励}{t时刻之前，a被选中的次数}=\frac{{\sum }_{i=1}^{t?1}{R}_i?{\mathbb{I}}_{A_i=a}}{{\sum }_{i=1}^{t?1}{\mathbb{I}}_{A_i=a}}$$

其中，若 $A_i=a$，则 ${\mathbb{I}}_{A_i=a}=1$，否则 ${\mathbb{I}}_{A_i=a}=0$，若分母为 0，则定义 $Q_t(a)$ 为一默认值（例如 0），根据大数定律，当分母趋于无穷时，$Q_t(a)$ 收敛于 $q_{?}(a)$，称这种方法为样本平均法（sample-average method），这是估计动作价值的一种方法，当然并不一定是最好的方法，下面我们使用该方法来解决问题。

最简单的动作选择就是选择价值估计值最大的动作，称为贪心方法，其数学表示为：
$$A_t?\underset{a}{\mathrm{argmax}}{Q}_t(a)$$

另一种替代的方法是，大多数情况是贪心的，偶尔从动作空间中随机选择，称为 $?$ -贪心方法。这种方法的优点是，随着步数增加，每个动作会被无限采样，则 $Q_t(a)$ 会逐渐收敛到 $q_{?}(a)$，也意味着选择最优动作的概率收敛到 $1??$。

3、贪心动作价值方法有效性

在 2000 个随机生成的 10 臂老虎机问题中，其动作价值 $q_{?}(a),a=1,?,10$，服从期望为 0，方差为 1的正态分布；另外每次动作 $A_t$ 的实际奖励 $R_t$ 服从期望为 $q_{?}(A_t)$ ，方差为 1 的正态分布。

部分代码

import numpy as np

step = 1000
q_true = np.random.normal(0, 1, 10)  # 真实的动作价值
q_estimate = np.zeros(10)  # 估计的动作价值
epsilon = 0.9  # 贪心概率
action_space = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
action_count = np.zeros(10)
reward_sum = 0
for i in range(step):
    if (np.random.uniform() > epsilon1) or (q_estimate1.all() == 0):
        machine_name = np.random.choice(action_space)
        reward_sum += np.random.normal(q_true[machine_name], 1, 1)
        action_count[machine_name] += 1
        q_estimate[machine_name] = reward_sum / action_count[machine_name]
    else:
	    machine_name = np.argmax(q_estimate)
	    reward_sum += np.random.normal(q_true[machine_name], 1, 1)
	    action_count[machine_name] += 1
	    q_estimate[machine_name] = reward_sum / action_count[machine_name]