Abstract: 在强化学习中，平衡Exploitation和Exploration将会是一个从始至终的问题，我们本章用简单的k臂赌博机问题来从具体的每一步来分析和研究这个问题，本节先介绍下问题的描述和大概的解决思路，为本章后面的问题解决做好铺垫
Keywords: 强化学习，k臂赌博机，多臂赌博机，利用，探索，Exploitation，Exploration

赌博机，说到赌博，大家都觉得这是一个非常不好的活动，但是说回来，赌博是催生数理统计和概率的主要动力，具体可以看未完成的系列：数理统计学简史
作为不赌博的好孩子，大部分人对k臂赌博机可能不是很了解，首先我们来介绍一下这种赌博机：

这就是为什么是k臂赌博机，那个臂就是旁边的控制器，通过拉动控制器就能出发机器开关，当出现指定的图案就会有相应的奖励，这是1臂赌博机，如果有多个这种机器放在一排，那么这就是k臂赌博机。

k臂赌博机问题描述

下面我们来从学术的角度描述一下这个问题，描述如下：
我们面对的选择包含 $k$ 个选项，或者 $k$ 种可选的行为，每一个选择或者行为都对应了一个奖励信号(rewarding signal，忘记了回到前面看看) 每种选择对应的奖励信号是随机的，但是都来自固定的分布，当然来自不同选择的奖励信号服从的分布都不同，但是不会随时间改变，比如，$k$ 种可选的行为中 $f_1$ 表示第一种行为的奖励信号的随机分布，其可以不同于 $f_2$ 也就是第二种行为的奖励信号的随机分布，但是为了简化问题，我们目前研究的问题中 $f_1,f_2,\dots,f_k$ 都不随时间变化。
我们的目的是通过每一步观察，选择，执行不同行为来最大化我们的奖励信号，当然这个过程需要长时间，或者是多步以后来观察结果，一次或者两次的观察是没有研究意义的。

k臂赌博机

经过上面的描述，我们就可以把描述和赌博机联系在一起了，首先我们对赌博机进行如下假设：

1. 赌博机出现的结果都是满足某种随机分布的，当然这个可能是赌场老板设定的，也可以是自然产生的
2. 赌场里面有很多赌博机可以供我们选择，如果赌场就一个赌博机，我们就要换一家研究k-armed bandits problem了
3. 赌博机的内的设置不会随时间改变，也就是1中的分布不随时间改变，没有幕后黑手操控比赛

有上面三点假设，我们就可以解释为什么我们本章研究的问题的是k臂赌博机了，我们面对 $k$ 个赌博机，我们的目的是最大化我们的收益，所以我们的做法是选择一个赌博机，然后下注（假定从始至终都不变）启动所有机器，获得结果，观察其他机器的行为，决定下一局是否换别的机器下注，对应上面的问题：

• 奖励信号 对应 单次赌博收益
• 可选行为 对应 本次使用哪台机器
• 每个行为对应的奖励信号的随机分布 对应 每台赌博机出现不同结果的随机分布

所以这就是我们上面描述的问题的生活中的例子，或者说我们可以通过生活中这个例子来得到问题。

上面的例子是赌博机的例子，下面还有一个类似的类比，就是医生看病的例子，医生每天要面对一些列的病人，每个病人用什么样的治疗方案就是一个选择的过程，而每种选择都对应着不同效果，而治疗效果就是奖励信号，当医生面对络绎不绝的病人时，医生的目标就是把奖励信号最大化，也就是最大程度的让更多人康复，这个类比也符合上面我们的问题描述

• 奖励信号 对应 病人康复程度
• 可选行为 对应 可选的治疗方案
• 每个行为对应的奖励信号的随机分布 对应 每种治疗方案对当前患者的效果的随机分布

数学描述

把上面的语言描述转换成数学描述就是如下了：
当前为第 $t$ 次选择(对应赌博中的第 $t$ 局，医生的第 $t$ 个患者), 有 $k$ 中选择，我们在此次选择的行为是： $A_t$ 对应获得的奖励信号是 $R_t$ ，那么对于这一轮选择，假设我们选择了 $a$ 我们获得奖励信号的期望 $q_*$ 就是：
$$
q_{\ast}(a)\doteq\mathbb{E}[R_t|A_t=a]
$$

如果你对 $A_t$ 和 $a$ 搞不清楚，我可以大概说一下，$A_t$ 是一个总称，本轮的所有选择的总称， 而 $a$ 是特定的一个行为，所以期望的公式就可以解释的清楚了，因为不同行为对应不同的分布，而我们希望使用期望来衡量这个行为的奖励信号。
如果我们明确知道每一步(局)每个行为(机器)将会出什么结果，那么我们就不需要选择了，直接选最大的那个就好了，所以我们这里假定我们不知道，也许你大概知道期望，但是对结果还是无法确定的（你可以一直观察某个赌博机的结果，利用大数定理通过采样结果来估计原始分布的结果）
这里我们对 $t$ 步的特定行为 $a$ 的评价(前面说的value function中value，和rewarding signal直接相关)的期望进行定义：
$$
Q_t(a)\approx q_*(a)
$$

这样就可以利用我们上面对问题的分析，以及使用前面提到的value function来解决这个问题了

强化学习解决k臂赌博机问题

上面我们应该已经能从整体上掌握k臂赌博机的问题过程了，那么我们接下来就要用我们前面提到的一些概念来解决这个问题了。
如果从我们自身出发，我们希望每一步都能最大化我们的收益（或者叫做奖励信号），我们自身会对所有赌博机都有一个评估，无论是感性的还是理性的，我们都会认为某个或者某几个赌博机获得高回报的可能性大一些，那么我们就有很多种玩法了：

1. 贪婪的我 —— 每次都玩那个我认为回报高的赌博机
2. 任性的我 —— 每次随便玩，就是不选我认为回报高的
3. 会强化学习的我 —— 每贪婪若干次后任性一次（玩自认为回报高的机器几次后，随机玩一次别的机器，看看是否会改变自己前面的观点）

前面我们反复说过两个单词（第一次考托福的时候我还用这两个单词写过作文😜）”exploitation” or “exploration” ，上面1中的贪婪也被称为 “greedy actions” 当你选择这种action的时候，你的action对应的就是”exploitation”；相反，如果我们就是不选我们认为回报高的，也就是2的这种行为，我们称为 “exploration”，如果我们还是想赢点钱，这种行为也不是完全傻瓜的，因为我们可以通过这种行为来纠正我们对每台机器回报高低的期望（有可能你对机器回报高低的判断是错误的，实际上也是这样的），换句话说，每台机器回报高低我们根本就是乱猜，所以1中的贪婪也有可能执迷不悟，而通过偶尔的”2”一下，没准会得到更多的收获，也就是3中给出的做法，会有更多收获。
Exploitation的做法肯定是正确的，但是从长期来看Exploration可能会产生更高的收益(短期来看exploration的收益大概率不如exploitation)，因为exploration很有可能找到比当前执行的action收益更高的其他action。但是具体怎么安排或者说怎么平衡Exploitation和exploration就是我们今后要一直研究的问题了。我们经常会用 “conflict” 来形容Exploitation和Exploration之间的选择。
是Exploitation还是Exploration这个问题理论上是没有通用解的，每一个环境，每一个问题，每一步都是不一样的，也无法确定，对于k臂赌博机问题，目前有一些专用的数学公式可以比较好的平衡Exploitation和Exploration之间的关系，但是这些公式或多或少都对问题的某些方面进行了限制和假设，这就使得这些方法在相似问题的不同环境下可能会失效。在后面章节我们研究的全面的强化学习(Fall Reinforcement Learning Problem, k臂赌博机 问题是简化后的问题)的时候，对应的环境会变得不同，一些假设条件也会不成了，这时候这些方法也会失效。这时候(某些假设不成立的时候)算法对应的收敛性和收敛边界都会失效。
我们目前的研究不关心是否以一种高效，漂亮的（sophisticated）方法来平衡Exploitation和Exploration，而是只要能平衡就行，不管漂不漂亮，高不高效，本章我们就列举几个简单的方法来平衡他们来获得比只 exploitation更好的结果。

总结

在强化学习中，平衡Exploitation和Exploration将会是一个从始至终的问题，我们本章用简单的k臂赌博机问题来从具体的每一步来分析和研究这个问题，从而获得更直观，更详细的理解。

References

1. Sutton R S, Barto A G. Reinforcement learning: An introduction[J]. 2011.

原文地址: https://face2ai.com/RL-RSAB-2-1-A-k-armed-Bandit-Problem