吴恩达，斯坦福大学：机器学习课程
第十六讲，马尔科夫决策过程
课程视频：http://open.163.com/movie/2008/1/2/N/M6SGF6VB4_M6SGKSC2N.html
讲义下载，公众号回复：20180613
强化学习四个基本环节
1.马尔科夫决策过程，Markov decision processes (MDP)
2.值函数，value function
3.值迭代，Value iteration
4.策略迭代，policy iteration
两个典型案例
案例1：直升飞机的自主控制
强化学习可以实现高难度特技飞行的自主控制，下图是吴恩达和他的学生们编程实现的强化学习算法自主控制直升机特技飞行
案例2：下象棋、围棋等，经典的就是AlphaGo Zero
九三曾有过一篇文章关于Zero的评论和介绍：《AlphaGO Zero的大咖观点 | 附42页算法论文下载 | 前沿技术》
强化学习经典内容介绍
1.马尔科夫决策过程
马尔科夫决策过程是一个五因素集合问题
S为状态集，即每个时刻所处的状态，如位置等
A为行动集，每次所采取的行动
Psa为状态转移概率，即在s状态下采取a行动的概率
γ为贴现因子，或叫折扣因子，取值范围0~1，用于调整不同时刻对当前状态的影响权重
R为奖励函数，反映不同结果的奖励分数
典型的MDP过程如上图所示，在状态s0下以概率Ps0a0采取a0行动，转移为状态s1，再转移为状态s2…………
如上式所示，总的奖励回报为奖励函数与折扣因子的函数，定性描述为越早期的状态和行动对最终结果的影响越大。而强化学习的最终目的是最大化总的奖励汇报，如下式。
2.值函数
策略指的是状态和行动的函数集合π
一个策略的值函数定义如下，是折扣因子与奖励求和的期望函数。
给定一个策略π，其值函数满足贝尔曼方程。可以看出主要由两部分组成，初始状态行动的奖励函数，以及后续折扣奖励的求和。
通过推导，强化学习求最优值函数的过程，也就是求解最大化后续折扣奖励求和函数下的策略π的过程，如下所示。
3.值迭代
求解强化学习函数的过程主要有值迭代和策略迭代两种方法。通常来说，当求解参数较少时，如几百上千个参数，可以用值迭代方法较快计算。但通常强化学习所面临的求解参数可达到几万甚至几十万个，此时策略迭代方法更为合适。
值迭代方法的主要流程，即使用贝尔曼方程不断更新估计的值函数，直到收敛。
4.策略迭代
策略迭代方法如下所示，即使用当前的值函数不断更新策略，直到收敛。
5.一个典型的强化学习过程
定义一个马尔科夫过程如下所示。
状态转移概率定义如下：
一种经典的最优策略学习算法如下：
