强化学习读书笔记（2）| K摇臂赌博机问题

上一次的强化学习简介中我们提到了强化学习是一种试错学习，没有直接的指导信息，需要用户不断地与环境进行交互，通过试错的方式获得最佳策略。这一节我们将从一个简单的单步强化学习模型进行进一步理解。

K摇臂赌博机简介

K-armed Bandit（也叫Multi-Armed Bandit）是赌场里的一种赌具。如下图所示：

游戏设定：有K个摇臂，投币后摇动任一摇臂，会有一定的概率吐出金币。每个摇臂的吐币概率和数量有所不同。

目标：在有限的摇臂次数下，使得获得的金币累积奖励最大。

两种简单思路：

• 1) 利用（exploitation）：每次选择时选择之前摇过的摇臂中掉金币最多的摇臂。这种策略可以使我们保守的获得相对较多的金币，但很可能使我们错过那些还没有被摇过的摇臂中掉金币更多的。
• 2) 探索（exploration）：把每一个摇臂都摇几次，这样就可以知道哪个掉金币平均值最多，然而总的摇臂次数是有限的，这样做的弊端是会浪费较多机会在掉金币少的摇臂上。

由于总的摇臂次数是有限的，所以“利用”和“探索”之间是存在矛盾的，这就是强化学习中所面临的“探索—利用窘境” （Exploration-Exploitation Dilemma）。所以，想要最后得到最多的累积金币，我们需要在“利用”和“探索”之间寻找一个平衡。

ε-贪心算法

• 基本思路：在每次进行选择摇臂时，以ε的概率进行“探索”，即在所有的摇臂中随机选择一个；以1-ε的概率进行“利用”，即选择所有摇臂中已知奖励均值最大的那一个（若不唯一，随机选择一个即可）。当ε=0时，该算法也被称为greedy算法，也就是纯利用策略。
• 算法流程

• 算法实现

• 算法结果

可以从图中看出，ε-贪心算法的最终表现相对greedy算法更好。在利用的过程中探索可以提高智能体识别最佳行为的机会。

UCB（Upper-Confidence-Bound）算法

• 基本思路：上一部分ε-greedy贪心算法中的“探索”是傻瓜式等概率地在所有行为中选择，而不会根据行为的潜力值（成为最优行为的潜力）来选取。UCB算法是通过行为的潜力来选择的一种有效方式。

• 算法流程

• 算法实现

• 算法结果

总体来说，在这问题上UCB相对表现更好。但UCB方法相对存在局限性，在处理不稳定问题（奖励概率随时间变化）以及状态空间很大的情况时，UCB动作选择通常是不实用的（我们后面介绍的函数近似中提到）。

上述的两种方法是按照估算行动对应奖励并使用这些估算值来选择行动的方法。下面将介绍两种按照概率选择行动的方法。

Soft-max方法

• 基本思路：基于概率选择下一次的摇臂序号，探索和利用同时选择。若各摇臂的平均奖赏相当，则选取各摇臂的概率也相当；若某些摇臂的平均奖赏明显高于其他摇臂，则它们被选取的概率也明显更高。其中摇臂对应的选择概率是基于Boltzmann分布的：

• 算法流程

• 算法实现

Gradient-Bandit算法

同样是通过概率选择行为，可以看作Soft-max算法的变形。表示在第t步选择行为a的概率。表示对行为a的偏好，偏好越大，采取行动a的次数越多。

在每个步骤中，在选择动作并接收奖励之后，动作偏好被更新。，表示时间t内时行为的平均奖励；，为步长参数。

• 算法实现

• 算法结果

小结

本文介绍了四种简单的平衡探索和利用的方法。那么问题来了，这些方法中哪个最好呢？实际上很难说哪个方法最优，对比的难点在于参数。下图显示了每种算法和参数设置随时间学习的过程，即参数学习。

可以看出，所有算法在其参数的中间值上表现最佳，然而我们不仅应该评估其在最优参数下的表现，还要看其对参数的敏感度。所有这些算法对参数值都相当不敏感，在一系列参数值上表现良好，这些参数值变化大约一个数量级。总的来说，在这个问题上，UCB策略表现最佳。

参考：

[1]R.Sutton et al. Reinforcement learning:An introduction,1998

[2]https://blog.csdn.net/lanlian123/article/details/79180324

[3]https://blog.csdn.net/antkillerfarm/article/details/79441890

转载自 | 公众号 老薛带你学Python

还有更多算法学习课件分享哟