参考资料

[1] 做大饼馅儿的韭菜：经典算法思想5——贪心（greedy algorithm）

[2] StanleyFoo：强化学习初探 - 从多臂老虎机问题说起

[3] 周志华：《机器学习》

[4] 搬砖的旺财：《RL——An Introduction》第二章笔记——多臂赌博机问题

[5] 华师数据学院·王嘉宁：强化学习（二）：贪心策略（ε-greedy & UCB）

[6] xyk_hust：David Silver《强化学习RL》第九讲 探索与利用

目录

• 贪心算法
• 探索与开发
• 多臂赌博机
• ε−贪心算法
• 最大置信区间上界算法
• Softmax-贪心算法（Softmax-greedy）/ 梯度赌博算法（Gradient Bandit Algorithms）
• 汤普森采样算法（Thompson Sampling）
• 上下文赌博机（Contextual Bandits）

1 贪心算法（Greedy Algorithms）

1.1 概念

贪心算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。

选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

1.2 基本思路

• 建立数学模型来描述问题
• 把求解的问题分成若干个子问题
• 对每一子问题求解，得到子问题的局部最优解
• 把子问题的解局部最优解合成原来解问题的一个解

2 探索（Exploration）与开发（Exploitation）

2.1 概念

探索是随机选择一个未知的动作，开发是选择已知的最优动作，简称EE问题。

开发对于最大化当前时刻期望收益是正确的做法，而探索则是从长远角度讲可能带来最大化总收益。

然而不幸的是，在某一个状态下，智能体只能执行一个动作，要么开发，要么探索，二者无法同时进行，因此这就是强化学习重点突出的矛盾——如何权衡开发与探索。

2.2 几种基本的探索方法

根据搜索过程中使用的数据结构，可以将搜索分为：依据状态行为空间的探索(State-Action Exploration)和参数化搜索（Parameter Exploration)。

前者指针对每一个当前的状态，以一定的算法尝试之前该状态下没有尝试过的行为。后者则直接针对策略的函数近似，此时策略用各种形式的参数表达，探索即表现为尝试不同的参数设置。

后者的优点是：得到基于某一策略的一段持续性的行为；其缺点是对个体曾经到过的状态空间毫无记忆，也就是个体也许会进入一个之前曾经进入过的状态而并不知道其曾到过该状态，不能利用已经到过这个状态这个信息。

3 多臂赌博机问题（Multi-armed Bandits）

3.1 问题描述

赌博机有k个摇臂，玩家投一个游戏币以后可以按下任意一个摇臂，每个摇臂以一定的概率吐出硬币作为回报，且每个摇臂的中奖概率不同。玩家的目标是通过一定的策略获得最大化的累积回报。

3.2 相关概念

•  —— 在时间步  时选择的动作；
•  —— 在时间步  时获得的回报；
•  —— 动作  的期望回报（真实值）；
•  —— 动作  在  时刻估计值（平均回报值）；
• 贪心动作 —— 在  时选择估计值最大的动作 

多臂赌博机本质上是一类简化的强化学习问题，这类问题具有非关联的状态（每次只从一种情况输或赢中学习），而且只研究可评估的反馈。每次行动的结果只和当前的状态关联而不受历史行动的结果影响（每次拉摇臂的回报只和老虎机设置的概率相关，之前输赢的结果不会影响本次行动）。我们可以定义这种问题是具有单一状态的马尔科夫决策过程。

3.3 求解方法

• 全能全知（Omniscient）
  即已经知道回报概率，那最直接的策略就是一直玩这一台，每一轮玩1000次后回报应该是800。先明确一下平均回报总数的上界，后面的每个策略的探索表现都会和这个上界值来比较。
• 随机算法（Random）
  随机策略是最直接的一种方法，像一个无知的赌徒一样每一轮随机地去拉一个摇臂。
• 贪心算法（Greedy）
  先把所有的摇臂都拉一次，然后选择回报最好的老虎机一直玩下去。这种策略很明显不鼓励进行探索，而且很容易被每个摇臂第一遍的回报结果误导。
• 其他优化算法
  从前面可以知道，只探索或者只开发都是不够明智的行为，要在二者之间达到权衡，需要另寻新的方法，例如ε−贪心算法（ε-greedy）、Softmax-贪心算法（Softmax-greedy）、ε−下降算法（ε-decreasing）、汤普森采样（Thompson sampling）。

4 ε−贪心算法（ε-greedy）

4.1 概念

在权衡开发与探索二者之间，ε-greedy是一种常用的策略。其表示在智能体做决策时，有一很小的正数 ε（<1） 的概率非贪心地随机选择一个动作（包括所有动作），剩下 1 − ε 的概率选择一个贪心策略。

具体操作就是，每次玩的时候就抽一个0到1的随机数，如果这个数大于 ε ，则玩你认为中奖概率（预估中奖概率）最大的那个拉杆。如果小于 ε ，则随机再选择一个拉杆（也包括中奖概率最大的那个拉杆），得到收益后，更新这个拉杆的预估中奖概率，以便于下次选择做参考。

代表全部可选的动作，代表未知动作被选中的概率，贪心动作被选中的概率为 （为什么会加？因为探索的时候也可能选择它）

4.2 算法思路

其中，为选择最优的，记录摇臂的平均回报，记录摇臂的选中次数，的计算结果是次的平均回报。

4.3 缺点及优化点

• 缺点：
  收敛较慢；不适用于非平稳的分布。
• 优化的方法：
  ① Ɛ-下降算法（Ɛ-decreasing）—— 让 ε 随着时间减小；
  ② 乐观初始估计（Optimistic Initialization） —— 初始值设置大一点，鼓励探索（encourage exploration）；
  ③ 在 ε 随机选择时，可以更有目的性地选择，而不是盲目选择，一个简单的办法就是尽量选择之前选择少的摇臂，因为它们潜在奖励可能更高。改进这一点，可以用到新的算法——最大置信区间上界算法（Upper Confidence Bound）。
  ④ 目前我们所讨论的动作值方法中，所有估计的动作值都是所观察到的样本平均值。为了更有效计算平均值，我们会利用连续记忆和连续时间步长计算，使得，只需要记录和就可以得到。
  但是，这个平均法只适用于稳定的赌博机问题，其回报分布不会随时间的变化而变化，但强化学习问题通常是不稳定的。因此，为了解决不稳定问题，我们可以固定步数参数，令为步长因子。式子变为：，估计值不会完全收敛于真实值，但会不断变化影响最近的回报，在不稳定的环境中是可信赖的。

5 最大置信区间上界算法（Upper Confidence Bound）

5.1 概念

置信区间是概率统计和统计推断比较重要的概念，其衡量一个随机变量分布的置信水平。置信区间越大，越说明这个随机变量不确定因素更大。UCB则是采用置信水平来实现对开发与探索之间的平衡。

首先引入一个思想：不确定行为优先。

如上图，如果我们选择绿色的可以获得最大回报，但不确定性为优先会选择蓝色的动作。的动作-奖励分布曲线置信区间大，分布跨度大，方差大，说明对应的采样样本数量较少，不确定较大。

前文说道，ε-greedy 贪心动作选择面临着非贪心动作的选取，但它的选取不是根据动作的潜力值（成为最有动作的潜力）来，而是等概率选择所有动作。

为了改进这一点，采用UCB这种偏向于对不确定性大的动作进行试探的算法，增加采样样本少（被执行次数低的动作）被选中的概率。

5.2 算法思路

UCB值包括两项，。

表示当前动作-回报的实际分布，也就是实际的Q函数。

表示对该动作不确定的一种度量。

其中，（>0）是对探索力度的控制系数，一个小正数，决定了置信指数；是动作在时刻时被选择的次数，可见当该值增大时，会减小，而如果没选择动作，随着增大，会增大。

6 Softmax-贪心算法（Softmax-greedy）/ 梯度赌博算法（Gradient Bandit Algorithms）

6.1 概念

目前我们讨论的几种方法都是估计动作值，并且用这些估计值来选择动作。

现在我们可以换个思路，我们用一个类似 的值表示自己对不同摇臂的喜好，每次都根据这些值生成的概率分布来进行对摇臂的选择，每次选择后再根据奖励高低修改概率分布直到最后收敛。

6.2 算法思路

用  表示  时刻对动作  的喜好，该值越大则动作被选择的概率越大。动作选择的概率分布可以用Softmax函数写作：

 表示在  时刻选择动作  的概率。

基于随机梯度上升的思想，更新分布的公式如下：

其中，是一个步长参数；是时间  范围内动作的平均值，相当于一个基准线（baseline）。

如果  高于 ，那么将来获取的概率增加，未选择的动作概率减少。

如果  低于 ，那么将来获取的概率减少，未选择的动作概率增加。

7 汤普森采样算法（Thompson Sampling）

知乎上有一篇回答写得很详细了：

王腾云：什么是汤普森采样（Thompson sampling）？

8 上下文赌博机（Contextual Bandits）

在上文讨论的多臂赌博机问题中，我们可以认为只有一个赌博机。agent可能的动作就是拉动赌博机中一个机臂，通过这种方式以不同的频率得到+1或者-1的奖励。在这个问题中，agent会永远选择同一个机械臂，该臂带来的回报最多。因此，我们设计的agent完全忽略环境状态，环境状态不会影响我们采取的动作和回报，所以对于所有的动作来说只有一种给定的状态。

上下文赌博机问题中带来了状态的概念。状态包含agent能够利用的一系列环境的描述和信息。在这个例子中，有多个赌博机而不是一个赌博机，状态可以看做我们正在操作哪个赌博机。我们的目标不仅仅是学习单一赌博机的操作方法，而是很多赌博机。在每一个赌博机中，转动每一个机臂带来的回报都会不一样，我们的agent需要学习到在不同状态下（赌博机）执行动作所带来的回报。为了实现这个功能，我们可以基于tensorflow构造一个简单的神经网络，输入状态并且得到动作的权重。通过策略梯度更新方法，我们的agent就可以学习到不同状态下如何获得最大的回报。

（待完善）