漫谈强化学习之n-armed bandit

从本期开始，我将逐一介绍强化学习的知识，并附其TensorFlow代码实现。

n-armed bandit问题是一种非关联式的强化学习，它不是完全的强化学习，但是可以为我们提供一点强化学习的入门知识。n-armed bandit问题的原始描述如下：

假如现在有n个不同的选择，每次做出一个选择之后都会得到一个随机的回报值，每一种选择的回报值都是基于某个稳定的概率分布产生的。解决的问题是希望在一段时间之后，回报值期望可以达到最大。前提是我们事先并不知道每个决策在特定时刻会产生多大的回报值。

n-armed bandit问题是基于决策的，而每一步的决策是根据价值估计来确定的，t时刻、决策a的价值估计记为Qt(a)，而决策a的真实价值记为q*(a)。

价值估计是根据之前的每一步回报值来计算的，随着决策的次数越来越多，估计的价值会越来越逼近于真实价值。价值估计是基于sampe-average方法，即对以往所有回报取平均得到。

有了价值估计之后，如何采取相应的决策（action）呢？这里就要提到强化学习中的expoitation和exploration了，为了在二者之间做一个权衡，使用的是e-greedy算法，即保持e的概率进行随机决策，1-e的概率进行贪婪决策。文末附的代码中会有比较greedy算法与e-greedy算法对回报的影响。

除了greedy算法和e-greedy算法以外，softmax算法也可以用来进行决策。softmax算法相比e-greedy算法的好处就是其可以有区分地随机选择决策，而e-greedy是纯随机的选取。softmax算法选取决策是基于玻尔兹曼概率分布公式的，由于softmax在有监督深度学习中使用频次非常高，这里便不再对它深入介绍。不同的是，这里引入了一个温度系数t，温度系数的选取因不同问题而异。

在进行了决策之后，决策的回报期望也就会随之更新。关于一个决策在t时刻的回报期望值的计算，我们可以使用t时刻之前该决策的所有回报值的平均值来代替期望值，这也符合统计规律。再写一遍上面提到的平均值公式：

但是这种做法对计算量以及存储空空间都是耗费，原因是每一步的回报值都需要扩大内存来存储，并且每次计算回报期望的复杂度都会提高。

我们可以通过简单的代数式变形从而减小计算量和存储消耗：

由上可知，计算一个决策第k+1次的期望值，只需要代入第k次的期望值和回报值即可。仔细看上面的表达式，仿佛有“梯度下降”的影子，回报期望值Q是待更新的参数，而这里的1/k可以看作是每次更新的步长，或者也可以自定义步长的大小。这种更新方法我们称为sample average算法。

除了sample average算法以外，也可以采取前面所述的softmax算法，设置步长大小，然后根据不同决策的概率值不同来更新其回报期望。