无人车智能决策：马尔科夫决策过程

马尔科夫决策过程（MPD）由五元组（S，A，P，R，γ）定义，其中：

（1）S表示有限状态集。

（2）A表示有限动作集。

（3）P表示马尔科夫转移函数，P（s，a，s′）表示在状态s（s→as′）下执行a，状态转移到s′的概率。

（4）：S×A×S→IR是奖励或者成本函数，R（s，a，s′）表示s→as′在下的奖励值。

（5）γ∈［0，1）表示折扣因子，未来的奖励值成γ的指数折减。

为简化符号，状态动作对（s，a）的期望奖励值R：S×A↔IR为R（s，a）：

强化学习算法利用环境反馈的奖励值，逐渐学习使得在状态s0下采取动作获得的累计奖励最大：

马尔科夫决策过程的策略π：S→A是由状态到动作的映射，π（s）表示在状态s下采取的动作。(www.xing528.com)

状态值函数Vπ（s）表示从状态s出发，使用给定策略π带来的累计奖励。任何策略的状态动作值函数Qπ（s，a）包含所有状态和动作的可能组合，表示状态s下采取动作a的累计奖励。

根据贝尔曼方程可以得出状态值函数和动作值函数：

用矩阵形式，系统可以描述为：

其中Qπ和R是大小为｜S｜｜A｜的向量；P是大小为（｜S｜｜A｜×｜S｜）的随机矩阵，包括过程的转移模型；Ππ用来描述策略π，是一个大小为（｜S｜×｜S｜｜A｜）的随机矩阵。

针对每一个MDP，存在一个最优的确定策略π*，使期望的总奖励V*（s），Q*（s，a）最大化。

评价给定的策略或者寻找更优的策略就是强化学习问题。给定任意的策略π，估计出状态值函数Vπ（s），就是策略评估过程。对某个策略进行评估主要是为了寻求更好的策略，当发现评估的策略并非最优策略时，则进行策略改进。理想的策略应该使期望奖励最大化：

策略评估与策略改进交替迭代进行，直到π′与π满足收敛阈值，则找到了最优决策π*＝π′，这种方法叫作策略迭代。策略迭代算法在每次改进策略后都需要重新进行策略评估，比较耗时，而值迭代算法直接以最优策略为目标，以迭代形式计算最优策略的值函数，可用于离策略（Off-policy）条件下最优策略的寻找。策略迭代方法经常用于策略（On-policy）强化学习中，必须用目标策略产生训练样本，这对目标策略形成了一定的限制。