1. 探索与利用

   强化学习与监督学习的不同：

   没有训练数据告诉机器应当做哪个动作，需通过尝试得出各个动作产生的结果，从而得到最终奖赏。

   最大化单步奖赏：

   • 需要知道每个动作带来的奖赏
   • 执行奖赏最大的动作

   算法背景：

   一般情况下，每个单步动作的奖赏值来自于一个概率分布，仅通过一次尝试不能确切地获得平均奖赏值。因此，单步强化学习任务对应了一个理论模型——K-摇臂赌博机。K-摇臂赌博机有K个摇臂，赌徒在投入一个硬币后可选择按下其中一个摇臂， 每个摇臂以一定的概率吐出硬币，但这个概率赌徒并不知道。赌徒的目标是通过一定的策略最大化自己的奖赏，即获得最多的硬币。

   仅探索法：

   若仅为获知每个摇臂的期望奖赏，则可将所有的尝试机会平均分配给每个摇臂（即轮流按下每个摇臂），最后以每个摇臂各自的平均吐币概率作为其奖赏期望的近似估计。仅探索法能很好的估计每个摇臂的奖赏，却会失去很多选择最优摇臂的机会。

   仅利用法：

   若仅为执行奖赏最大的动作，则可按下目前最优的（即到目前为止平均奖赏最大的）摇臂，若有多个摇臂同为最优，则从中随机选取一个。仅利用法没有很好的估计摇臂期望奖赏，很可能经常选不到最优摇臂。仅利用与仅探索这两种方法都难以使最终的累积奖赏最大化。

   探索-利用窘境：

   由于尝试次数有限，探索和利用是矛盾的，加强一方则会削弱另一方。欲累积奖赏最大，则必须在探索与利用之间达成较好的折中。

2. ε -贪心

   基于概率来对探索和利用折中：每次尝试以ε的概率进行探索，即以均匀概率随机选取一个摇臂；即选择当前平均奖赏最高的摇臂（若有多个则随机选取）以1-ε的概率进行利用。

   令Q(k)记录摇臂k的平均奖赏。若摇臂k被尝试了n次，得到的奖赏为vi，则平均奖赏为
   
   
   可见无论摇臂被尝试多少次都仅需记录两个值：已尝试次数n-1和最近平均奖赏Qn-1(k)。

   ε-贪心算法如下：

   输入：摇臂数K；
        奖赏函数R；
        尝试次数T；
        探索概率ε
   

   过程：

   r=0；
   任意i=1，2，……K：Q(i)=0， count(i) = 0;
   for t = 1,2,……,T do
       if rand()<ε then
           k = 从1，2，……K中以均匀分布随机选取
       else
           k=argmaxiQ(i)
       end if
       v = R(k);
       r = r+v;
       Q(k) = (Q(k)*count(k)+v)/count(k)+1;
       count(k) = count(k)+1;
   end for
   输出：累积奖赏r
   

   由于摇臂奖赏的不确定性较大，则概率分布较宽时需要更大的ε值，分布较集中时需要较小的ε值，一段时间后需要尝试的次数逐渐减少，可令ε=1/(t^(1/2))

3. Softmax算法

   Softmax算法基于当前已知的摇臂平均奖赏来对探索和利用进行折中。若某些摇臂的平均奖赏明显高于其他摇臂，则它们被选取的概率也明显更高。

   Softmax算法中摇臂概率的分配基于Boltzmann分布：
   
   Q(i)记录当前摇臂的平均奖赏； τ >0称为“温度”， τ 越小则平均奖赏高的摇臂被选取的概率越高。特别的， τ ->0时Softmax将趋于“仅利用”， τ ->无穷大时Softmax将趋于“仅探索”。

   Softmax算法描述：

输入：摇臂数K；
     奖赏函数R；
     尝试次数T；
     温度参数 τ 

过程：

r=0；
任意vi=1，2，K：Q(i) = 0, count(i) = 0;
for t = 1,2,3,……,T do
    k = 从1，2，……，K中根据Boltzmann分布随机选取
    v= R(k);
    r = r+v;
    Q(k) = (Q(k)*count(k) + v)/(count(k) + 1)
    count(k) = count(k)+1
end for
输出：累积奖赏r