强化学习的核心就是一个最优函数使得总回报达到最大，这个最优方程又称为Bellman方程，而解决这种最优问题常用的思路就是动态规划（详见：RL（一）——马尔科夫决策过程，我对动态规划算法的理解（一）），如果不使用动态规划算法的话，那么后果就是计算量变得异常庞大，例如一个大小为5*5的棋盘，如果按照上一期中提到的状态空间去搜索的话，一共有3^25个状态空间，因此计算量是非常庞大的，而且随着棋盘大小的扩增，计算量将呈指数增长。
这就带来另外一个核心问题，我们在运用强化学习过程中肯定不可能涵盖到所有的状态空间，换句话说，我们要在exploration和exploitation中做一个平衡，正如上一期所说（详见：基于强化学习开发人机对弈五子棋游戏），exploration是基于随机算法，而exploitation是基于贪婪算法。是不是一直使用贪婪算法就行了呢？短期看是可以，但是长期看是不行的，就好比陷入了局部最优一样，因此，本系列将通过n-Armed Bandit Problem来讲解如何在exploration与expoitation之间做出权衡，从而使得强化学习的决策达到最优。
n-Armed Bandit Problem是一个很通用的模型（以下简称Bandit Problem），该问题的原型是：假如你每次面对n个不同的选择，你每次做出一个选择之后都会随机产生一定的回报值，每种选择的回报值都是服从一个稳定的概率分布，要优化的参量是经过一段时间后，使得回报值达期望达到最大。前提是我们事先并不知道每个决策在特定时刻会产生什么样的回报值。
为了解决这个问题，首先我们看一种最常见的算法，这种算法就是e-贪婪算法，e通常是一个处在0~1之间的小数，从决策的角度来说，e反映的其实就是在exploration和exploitation之间的折中程度。例如，假设Bandit Problem共有10种选择，而我们现在一共要进行10000次Bandit Problem尝试，目的要使得总回报达到最大。
如果e为0，那么就是纯粹的贪婪算法，这种算法的做法是一开始设定所有10种选择的期望价值均为0，并且我们让每种决策的价值服从均值为0方差为1的高斯分布，然后我们的每次决策都是找到一个最优价值的决策，这个最优价值的计算是：V(a)=Mean(a)+random_variable，其中Mean(a)就是该决策过往的所有价值的平均，而random_variable也是一个均值为0方差为1的高斯变量。基于这个贪婪规则，每次选择价值最大的那个决策，它的核心思想其实就是基于大数定律，在抽样了一定的次数以后，样本平均值放映了期望值。
而当e为不等于0的一个小数时，我们并非任意时刻都做贪婪决策，而是具有e的概率进行随机决策，也就是说这里要设置一个随机变量，当变量值小于e时，就进行随机决策，而当变量值大于e时，就进行贪婪决策。这种e-贪婪算法的好处就是可以搜索到更多可能性，从长期来看，对总回报是有利的。
虽然e-贪婪算法在exploration和exploitation之间做出了一定的取舍，但是经常会发生的情况是随机决策的时候选择了一个看起来很差的决策，有一个对于e-贪婪算法的优化方案就是在随机决策的时候使用softmax决策：
exp(Q(a)/t)/SUM_i{exp(Q(ai)/t)}，a是指某个决策
也就是说，对于e-贪婪算法，在随机变量值小于e的时候，不是进行随机决策，而是寻找根据下面的公式算出最大值的那个决策。但是，这种方案的缺点是无法事先知道t的大小，因问题而异，因此应用起来与原始的e-贪婪算法的性能无法直接比较孰优孰劣。
最后我们再来看一下贪婪算法的计算效率问题，前面提到每次决策都是基于各个决策的历史平均价值，那么随着决策次数的增多，存储历史价值（V[1],V[2],...,V[k]）的空间消耗也会越来越多大，与此同时，计算历史平均价值（Q[k+1]=(V[1]+V[2]+...+V[k])/k）的计算量也会越来越大，这样显然是低效的，对于Q[k+1]的计算公式，我们可以做出以下变形：
Q[k+1]=(V[1]+...+V[k])/k
=(V[1]+...+V[k])*(k-1)/[k*(k-1)]
=Q[k]*(k-1)/k + V[k]/k
=Q[k]+(V[k]-Q[k])/k
这样变形以后，每次只用存储Q[k]和k的值了，并且计算量也就变小了很多。这种更新规则似曾相识，它的一般形式就是：
NewEstimate=OldEstimate+stepSize*(Target-OldEstimate)
值得注意的是，括号中描述的量可以看作一种误差，因此整个更新方式也可以看作一种“梯度下降”，stepSize就是步长，它是随着时间的推移在逐步衰减的。
来源：张泽旺 深度学习每日摘要
智造家