sheng的学习笔记-AI-K-摇臂赌博机（K-armed bandit）

AI目录：sheng的学习笔记-AI目录-CSDN博客

强化学习 sheng的学习笔记-AI-强化学习（Reinforcement Learning, RL）-CSDN博客

基础知识

单步强化学习任务

先考虑比较简单的情形：最大化单步奖赏，即仅考虑一步操作。需注意的是，即便在这样的简化情形下，强化学习仍与监督学习有显著不同，因为机器需通过尝试来发现各个动作产生的结果，而没有训练数据告诉机器应当做哪个动作

欲最大化单步奖赏需考虑两个方面：

一是需知道每个动作带来的奖赏，
二是要执行奖赏最大的动作。

若每个动作对应的奖赏是一个确定值，那么尝试一遍所有的动作便能找出奖赏最大的动作。然而，更一般的情形是，一个动作的奖赏值是来自于一个概率分布，仅通过一次尝试并不能确切地获得平均奖赏值。

K-摇臂老虎机

“K-摇臂赌博机”(K-armed bandit)，亦称“K-摇臂老虎机”，是一种单步强化学习任务

K-摇臂赌博机有K个摇臂，赌徒在投入一个硬币后可选择按下其中一个摇臂，每个摇臂以一定的概率吐出硬币，但这个概率赌徒并不知道（奖励的概率分布是未知）。赌徒的目标是通过一定的策略最大化自己的奖赏，即获得最多的硬币：需要在“探索拉杆的获奖概率”和“根据经验选择获奖最多的拉杆”中进行权衡。“采用怎样的操作策略才能使获得的累积奖励最高”

奖赏策略

仅探索(explorationonly)

若仅为获知每个摇臂的期望奖赏，则可采用“仅探索”(explorationonly)法：将所有的尝试机会平均分配给每个摇臂（即轮流按下每个摇臂），最后以每个摇臂各自的平均吐币概率作为其奖赏期望的近似估计。

仅利用(exploitation-only)

若仅为执行奖赏最大的动作，则可采用“仅利用”(exploitation-only)法：按下目前最优的（即到目前为止平均奖赏最大的）摇臂，若有多个摇臂同为最优，则从中随机选取一个。

探索和利用两种策略对比

仅探索”法能很好地估计每个摇臂的奖赏，却会失去很多选择最优摇臂的机会；“仅利用”法则相反，它没有很好地估计摇臂期望奖赏，很可能经常选不到最优摇臂。因此，这两种方法都难以使最终的累积奖赏最大化。

“探索”（即估计摇臂的优劣）和“利用”（即选择当前最优摇臂）这两者是矛盾的，因为尝试次数（即总投币数）有限，加强了一方则会自然削弱另一方，这就是强化学习所面临的“探索-利用窘境”(Exploration-Exploitation dilemma)。显然，欲累积奖赏最大，则必须在探索与利用之间达成较好的折中。

贪心法

期望奖励与采样次数之间存在以下关系：

为了减少计算的空间复杂度，可以改为增量式的计算：

基于以上情况，代码如下

Softmax

Softmax算法基于当前已知的摇臂平均奖赏来对探索和利用进行折中。若各摇臂的平均奖赏相当，则选取各摇臂的概率也相当；若某些摇臂的平均奖赏明显高于其他摇臂，则它们被选取的概率也明显更高。

贪心法和softmax对比

贪心算法与Softmax算法孰优孰劣，主要取决于具体应用。举例：

假定2-摇臂赌博机的摇臂1以0.4的概率返回奖赏1，以0.6的概率返回奖赏0；
摇臂2以0.2的概率返回奖赏1，以0.8的概率返回奖赏0。

图16.6显示了不同算法在不同参数下的平均累积奖赏，其中每条曲线对应于重复1000次实验的平均结果。可以看出，Softmax(t=0.01)的曲线与“仅利用”的曲线几乎重合。

对于离散状态空间、离散动作空间上的多步强化学习任务，一种直接的办法是将每个状态上动作的选择看作一个K-摇臂赌博机问题，用强化学习任务的累积奖赏来代替K-摇臂赌博机算法中的奖赏函数，即可将赌博机算法用于每个状态：对每个状态分别记录各动作的尝试次数、当前平均累积奖赏等信息，基于赌博机算法选择要尝试的动作。

然而这样的做法有很多局限，因为它没有考虑强化学习任务马尔可夫决策过程的结构。若能有效考虑马尔可夫决策过程的特性，则可有更聪明的办法