Basic idea

基本想法是在状态空间和可能的行动空间都足够小的情况下（能够通过表格或者是数列存下的情况下），通常能够找到精确解

多臂老虎机(`k-armed bandit problem`)

问题描述

现在有 k 种选择，每次可以从 k 种选择种选择一个，每种选择给出的奖励都是基于一个未知但是确定的分布的，学习的目标是在有限的次数中最大化所有的奖励的和。

符号定义

: 在时刻选择的动作
: 对应的reward
: 在该时刻动作的 value：
: 在时刻估计的动作的 value

样本均值法

此时对于动作的估计是：
$$
Q_t(a) = \frac{\mathrm{在t时刻之前采取动作a获得的奖励之和}}{在t时刻之前采取动作a的次数} = \frac{\sum_{i = 1}^{t - 1}\limits R_i \cdot \mathbb{1}{A_i = a}}{\sum{i = 1}^{t - 1}\limits \mathbb{1}{A_i = a}}
$$
这里的 $\mathbb{1}{A_i = a}$ 是指示函数，在相等时取1否则为0

那么每次的决策就是取

-greedy 策略

为了平衡 exploration-exploitation 问题，每次按照一个较小的概率来选取非当前最优解

从另一个视角看待样本均值

公式推导：

考虑一般的参数更新公式：

即通过选取一个步长每次通过步长乘以误差来更新估计的变量，那么这里的样本均值就可以看做是步长为的学习。

应对变化的问题

对于样本随时间变化的问题，直接使用作为步长，会导致所有样本的重要性与出现的时间无关，这无法很好的处理变化的对象，因为我们希望越近的样本占的比重更大，所以这里考虑加权平均。

选取一个得到更新公式

通过类似的推导可以发现

所以当越接近的时候越后面出现的样本所站的权重就越重。

关于a的选取

记每一项前面的系数为通常要求数列是条件收敛的，即

第一个保证了系数足够大可以应对任何特殊的初始值和随机情况，第二个保证了最终可以收敛。

这里我个人认为第二个条件是不能保证收敛的，因为这个条件还需要考虑原问题每次更新进来的值是什么。

乐观地选取初始值

在问题一开始初始化的时候，可以适当选取一个比较乐观的初始值，比如超过可能最大值的值，这样会促使算法去更多地尝试不同的可能性，平衡 exploration and exploitation 的问题。

基于梯度的更新方式

首先记侧率在时刻选取动作的倾向为，通过 sorftmax 来计算出选取动作的概率即为

通过一系列推导可以得到梯度下降的更新公式：

对于在时刻被选择的动作：

对于其他动作：

关于证明上面这个式子，最重要的要点就是需要注意到所以对这个求导的和是0，那么就可以加入一个 baseline 而不影响整个式子的值