强化学习理论及算法推导

理论的介绍

假如我们在种一个盆栽，那么定期浇水，晒太阳，松土壤等，在经过一段时间的悉心照料后，盆栽长出来或者没变化（或者早就夭折了，只是我们不知道而已）假若盆栽长很好看的花来的话会得到奖赏，那么我们在照顾盆栽时，采取一系列动作时我们并不知道这样做是对是错，因为没有任何的奖赏说明。（盆栽还没长出来，甚至我们还得定一个时间，如果还没长出来那就是死了）所以我们就需要不断去栽种很多很多相同的盆栽，通过固定变量法来确定啥时候浇水效果最好，什么时候浇水会浇死盆栽，或者确定一次浇多少比较合适。通过不断地试验中学习到经验，总结出好的种瓜策略，这个过程抽象出来就是强化学习

基本的表示：

通常强化学习任务一般都会用马尔科夫决策过程（MDP, Markov Decision Process）描述，机器处于一个环境E中，状态空间为X，其中每一个状态都是对环境的描述，可以表示为x，形象化就是指盆栽的生长情况，有没有掉叶子，叶子颜色的环境特征描述等。同时还假设了一个动作空间A（这个可以无限也可以有限，比如浇水的量用ml单位去计量你的动作，可以浇1.1ml,1.11ml,1.111ml无限且连续的动作，如果用一个小杯子的量作为计量就好一些，可以根据先验确定上限毕竟不可能浇100杯水，那么选择就是有限的离散的。）这时就可以通过马尔科夫的概念，也就是我们当前的状态只和上一个状态有关，故而当我们采取每一个动作a都有可能触发一定的转移概率，也就是p(x1->x2|a)意义就是采取a动作的情况下，由状态x1转移到x2的概率。同时通过设定一个Reward奖赏函数来确定跳转到这个状态的奖赏，然后记录下来。

总结来说，强化学习对应了一个四元组<X,A,P,R>，而我们的目的是根据这个四元组得到一个很好地策略π，需要求的主要是转移概率，奖赏函数。（基本上都不会给）

目标： 策略π

求得策略之后，只要代入当前的环境状态x，就可以得到动作a=π（x），而一般我们训练出来的模型我们更倾向于让π映射到选择a动作的概率上或者分数，也就是说p（a)=π（x,a)（也可以称为Q值函数）。

策略的优劣判别：

只要一段时间内一直执行某一策略就可以得到累计的奖赏，比如执行其中一个策略一段时间后能让盆栽长出花来，那么肯定这个策略在这些策略里最好（这依然是一个近似最优的可行解）。为什么不去计算一步的奖赏，很明显仅仅一步很可能你无法收到收益，或者你买股票可能当前你收益比较少甚至亏损，但之后的收益可能会呈指数上涨，也就是一步步的贪婪算法是无法用的，所以这里常用的是T步奖赏，和γ折扣累积奖赏。（都得设定超参数，既然将其假设为马尔科夫决策过程，是否是可以通过dp算法进行计算？答案当然是可以，后面正是用dp来计算相应的值函数，然后再计算最优的策略）

K-摇臂赌博机问题探讨：（开胃小菜）

• 问题：
  有一个k个按钮的赌博机，投入硬币后，按下k个按钮之中的一个，机器就会以一定的概率掉落一定的硬币。（不同机器不一样）

• 方法：
  首先在所有的先验知识都没有的情况下，我们要先进行探索（扔进硬币）然后再进行投资才能够让我们的收益最大化，但是如果我们尝试步数是有限的，探索的步数和投资的步数我们该如何去分配，很明显一个强自然削弱另一个，这就是“探索-利用窘境”（Exporation-Exploitation dilemma）

  • e-贪心和softmax-τ
    e-贪心，softmax-τ（实验表明softmax在步数较少的情况下优于e-贪心，不过e-贪心在长远而言更好。）e-贪心在e的概率情况下随机选择一个方向进行探索，如果要探索N次才能探索出分布来，那么就需要进行N/e步之后，e-贪心能趋于稳定，相比而言softmax是通过计算前期状态获得的收益来根据softmax来计算选择相应动作的概率，可能在短期上倾向于选择表现更好的，也就是说很可能对一些开始表现较差的会选择忽略掉，这样因为没有探索完全就相当于会有一个上界，也就表现在长期收益效果上来看不如e-贪心。

  • 马尔科夫类型强化学习
    相比于前面的k摇臂赌博机问题，我们平常的强化学习目标更加倾向于一种马尔科夫决策式的过程，也就是说当前的决定仅与当前的状态相关。

* 有模型的强化学习 （前菜）

• 条件：假设我们能够知道在x状态下执行动作a转移到x2的概率，也就是知道转移概率，而且我们还需知道从x1到x2转移带来的奖赏是多少，也就是奖赏函数。

• 目标：训练最优的策略函数

训练目标的前提是： 获得策略的评价函数（根据最优化评价函数来训练出最优的策略）

• 具体推导方法：

1. 评价策略函数：

通过设定一个状态值函数Vπ，T（x）,表征的是根据π的策略在x的初始状态下进行T步之后得到的平均奖赏。当然这个是可以进行展开的，也就是可以从V0（x）开始不断遍历所有的情况然后达到Vt（x），那么我们进行T次迭代或者当Vt（x）=Vt-1（x)时之后我们就能得到这么一个Vt(x)，然后通过取π*来最大化Vt（x），x∈X。但是这么一个评价策略函数没法直接优化。如果你是从一大堆决策中找最优，可以简单的直接代入计算比较评估即可，但是想要直接最优化不太好理解，所以这时我们再引入定义一个状态-动作值函数Qπ，T（x,a)，表示在初始化状态为x下，采用动作a之后，T-1步得到的平均奖赏。这样就可以通过这个函数Q值的大小得到一个π（x）=a，这个a能使得Q值函数最大，当然也可以通过softmax（Q函数）得到在x状态下采用a动作的概率。可见状态-动作值函数是和我们要求的最优策略函数π函数是一致的。

2. 优化策略函数：

上述也提到的Q函数，只要通过优化a使得Q函数大于V（x），这样就可以接受这个优化a，反之如果怎么找都找不到这样的优化a那么结束迭代，这时候的Q函数（也即策略函数）是达到了最优的状态。同时我们也可以看到我们也可以看到在评估策略函数和优化策略是可以同时进行的过程中可以直接对a进行优化，既然这是马尔科夫，那么我们每一步计算值函数的时候不再用全概率展开的方式，即遍历所有的情况，我们只需要在每一步都对π函数优化目标最大化V（x)即可。直到最后的T+1步奖赏和T步奖赏相近，停止迭代。

* 无模型的强化学习：（正餐）

• 背景：
  现实的强化学习多是无模型的，也就是不知道转移概率，以及奖赏函数。

• 方法：
  MC 蒙特卡罗强化学习，无法得到转移概率的情况下，可以通过多次采样，来了解转移函数，或者对应的奖赏函数，比如k摇臂赌博机，就是通过探索的方式来进行摸索每一个按钮奖赏函数的分布。

• 特点：
  有限次适合使用T步累计奖赏的强化学习任务，由于策略迭代估计的是状态值函数V，不是Q函数，而且无模型的情况下无法直接知道转移概率，也就是说V不能直接转换到Q函数上，那我们就直接去计算Q函数的奖赏。

• 具体做法：
  通过执行某种策略T步，并多次执行，这样就能得到多条轨迹，然后 记录每一对状态-动作，以及t->T的奖赏值，然后进行求和取平均，就可以得到估计的Q函数。但是如果在采样的过程中我们使用的策略π是一样的，那么采样的多条路径是一样的，那么我们可以在原有策略的基础上类e贪心，也做一个概率e的情况下随机选择其他动作而不采用策略π。

同策略MC强化学习算法：

1. 通过采用更新好的e-策略π来多次采样得到的一条轨迹。然后求和平均就可以得到Q函数。

2. 对于现在的状态更新策略π使得值函数Q最大。

3. 循环N次

异策略的MC强化学习算法：

• 相对于同策略，我们更希望我们能训练的策略是不包含e的贪心策略，那么通过引入异策略的方式，就是通过引入包含e的策略和不包含e策略的概率比值=期望的比值（基于一个分布的采样来估计另一个分布下的期望，称为重要性采样。），来让最后的通过包含e的策略采样得到的累计奖赏进行修正，然后通过这个来更新计算我们想要的到最优策略。

时序差分学习：

• 因为MC强化学习的放水阀只是通过考虑采样的轨迹，一般都得完成一个采样轨迹之后才能进行更新学习。效率较低，没有应用到马尔科夫过程的特点。时序差分（temporal difference，TD）就是为了高效学习的,且更适合使用γ折扣累积奖赏。需要确定的超参数有更新步长α，奖赏折扣γ，还有转移的奖赏。

更新公式的推导过程：（因为简书不支持公式，只能自己写了）

image.png

• 同策略方法：(sarsa算法->state ,action, reward, state,action)

  • 每次根据当前的状态然后计算π-e（x）来执行动作，然后根据得到的状态转移对Q函数进行更新。

  • 由Qt+1和Qt之间转化关系求Qt+1，当t足够大的时候，Qt+1就是我们要求的结果，理论就是Qt+1在t趋向于无穷时会收敛，因为这是一个马尔科夫转移过程，可以证明马尔科夫转移过程最后一定会收敛。

• 异策略方法：（Q-learning算法）

  • 采样还是用π-e来采样，但是要获取在Qπ（x'，a'）时a'用的π是不带e的策略函数π。

  • 剩下的更新过程和同策略一致。

状态为连续值问题 （甜点）

• 如果状态是连续的而不是离散的值，那么我们就可以直接通过近似值函数的方式。将原本离散的值函数设为连续函数的f(x)=θ.T*X。然后通过我们原值函数和更新值函数的最小二乘误差求导，得到θ参数的更新梯度，进行更新就好了。

----end-----
简书不能编公式，就尽量减少一些公式的编写。尽量口述原理，可能没公式推导会比较难对号入座去理解。希望读者能参考西瓜书来理解。水平有限，如果有什么错误的地方，敬请指正。