在之前的一篇文章中讲到了多臂老虎机问题，这是强化学习中探索-利用困境的经典案例。这篇文章将更多从理论上来探讨如何解决探索-利用困境。
1. 多臂老虎机问题回顾
多个拉杆的赌博机，每一个拉杆的中奖几率是不一样的，问题是：如何在有限次数内，选择拉不同的拉杆，获得最多的收益。
将这个问题用强化学习的数学模型进行描述
- 每个拉杆相互独立，只有一个Episode，拉一次就结束这个Episode.
- 一个Episode由一个行为和奖励构成<A, R>，与状态无关.
- A的行为个数等于拉杆的个数
- 在t时刻，从空间A中选择一个行为at，环境产生奖励rt.
- 环境产生奖励的概率分布Ra(r) = P[r|a]是未知的。
- 目标是获取最多的总奖励
- 为方便描述我们定义某一行为的价值函数Q(a) = E[r|a]
同样的问题在现实生活中也有很多，比如如何选择餐馆，是去你最喜欢的餐馆(利用)还是探索新的餐馆？如何投放广告，是用已知最成功的方式投放(利用)还是探索新的广告方式？如何挖矿，是去挖已知出产量最大的矿点*(利用)还是去探索新的矿点？
对于解决探索-利用困境，有如下几种方法：朴素探索(Naive Exploration)，乐观初始估计(Optimistic Initialization)，不确定优先(Optimism in the Face of Uncertainty)，概率匹配（Probability Matching)，信息状态搜索(Information State Search)。
2. 朴素探索方法(Naive Exploration)
这种方法之前的文章，已经在后面介绍Q-learning 和其他强化学习算法中，提到很多次了，其中应用最广的就是ε贪婪方法(ε -Greedy)，ε值是用来指导到底是Explore 还是 Exploit。比如将ε设定为0.1，以保证将10%的次数投入在探索（Explore）,90%的次数用于利用(Exploit)。
如何选择ε值是一个很大的学问，当然最简单粗暴的方式就是固定一个数值。但是随着探索的次数增多，我们对每个拉杆的奖励概率的估算也应该越准确，这个时候应该增加利用，减少探索，衰减ε值。如何衰减ε将会在后文提到。
3. 乐观初始估计(Optimistic Initialization)
其"利用"(Exploit)的部分，用预设中奖概率"天花板"的方法来解决探索——利用困境
首先, 将老虎机每个拉杆都设置一个比较高的预估中奖概率（比如都是100%），然后每拉一次选中的拉杆, 这个拉杆的的预估概率就会改变。
比如，我第一次选择拉第一个拉杆，发现没有中奖，那这个拉杆的预估中奖概率就从100%变成了50%了。下一次Exploite选择拉杆的时候，第一个拉杆的预估概率就不是最高了，我们就去找这个时候预估概率最高的拉杆来拉，每拉一次更新一下这个拉杆的预估中奖概率。
理论上来说真实概率高的拉杆其预估概率下降的速度会比真实概率低的拉杆慢，所以多试几次之后就能找到真实概率最高的那个拉杆。
4.不确定优先(Optimism in the Face of Uncertainty)
我们先假设老虎机有三个拉杆，蓝、红，绿，中奖概率符合正态分布，经过有限次的探索，我们发现拉杆符合下面这个分布：
因为探索次数有限，上图的分布并不是最终的分布，随着探索的次数增加，分布应该“收拢”。可看出蓝色的的拉杆分布最“平”，说明其不确定性最大，因为它虽然平均值最小，但是“尾巴”最长。也就意味着，我们需要优先尝试更多的蓝色单臂，以更准确地估计其行为价值，即尽可能缩小其奖励分布的方差。
这种优先探索不确定性高的拉杆，而不是单纯看平均值的方法就是不确定性优先方法。
置信区间上界(Upper Confidence Bound, UCB)
当然我们不能仅凭肉眼观察分别的“尾巴”来判定探索的拉杆，而是需要定一个置信区间(Confidence)U(a).
U(a)如下图，相当于平均值的一个偏移量，确保能覆盖一定面积的概率分布，比如95%
于是我们可以选择置信区间上界(UCB)最大的拉杆
Chernoff-Hoeffding bound理论
对于正太分布，确定置信区间的大小(比如95%)我们很容易就能算出UCB的位置，对于一般性的分布我们就要用到Chernoff-Hoeffding bound理论的不等式了。
通过解这个不等式
我们可以得到UCB的位置
5.概率匹配（Probability Matching)
概率匹配算法是基于一个非常简单和直观的思想：评估每一个行为可能是最佳行为的概率，然后根据这个概率选择后续行为。
越不确定性的行为有越高的几率被选中和执行，这样就能提高不确定行为的采样率，从而减少其不确定性，进而调整后续行为。
Thompson Sampling 就是基于概率匹配的算法：
(以多臂老虎机为例)
- 根据历史记录计算出各个拉杆奖励分布(与上一个方法类似)。
- 在每一个分布中进行采样。
- 选取最大采样值的拉杆执行对应的行为
该算法采样的时候利用了历史信息获得概率分布，通过选择性的执行行为得到真实奖励，同时更新分布。
6.信息状态搜索(Information State Search)。
前面介绍的关于多臂老虎机算法实际上包含了两个假设，
- 是我们假设拉杆的机会可以是无穷的。
- 基于第一个假设，拉杆过程被看成了只有一步的决策过程。
然而对于只有有限次“拉杆”机会的多臂老虎机问题，每一步决策并不是相互独立的。
举一个只有两个拉杆的老虎机例子，比如你知道拉杆A的奖励是100块钱，拉杆B的奖励可能只有70块，但由于拉的次数不够多也有可能获得更高的奖励。如果你只剩下1次机会，你肯定会选择拉杆A获得一个更加确定性的奖励，如果你还剩下1000次机会，你肯定会多试几次拉杆B，没准这个拉杆的奖励会更高呢。
拉杆B不不确定性高，探索拉杆B就会获得更多的信息，量化信息的价值从而基于价值构建多步的MDP，我们就可以使用熟悉的强化方法(Q-Learning)来进行学习了。
图片来自于David Silver 的课件
同步到我的简书
https://www.jianshu.com/u/bd506afc6fc1