强化学习-动态规划法

动态规划法是著名的基于贝尔曼方程的经典强化学习方法。本章先介绍动态规划的核心思想，再介绍强化学习的动态规划法。

动态规划法简介

• 核心思想

动态规划的核心思想是将原问题分解为若干个子问题，先自底向上地求解子问题，然后从子问题的解回溯得到原问题的解。

• 动态规划和分治法的区别

动态规划和分治法都是用了“分割、求解、合并”的思路，但分治法得到的子问题都是相互独立的，动态规划的子问题是嵌套的。

• 动态规划求解一个问题的步骤如下：

1. 找出最优解的性质，并刻画其结构特征
2. 递归地定义子问题和子问题的解
3. 自底向上地求解子问题
4. 根据子问题的解和解的结构回溯构造原问题的最优解

eg. 最短路径问题
A->B->C->D
A到D的最短路径=从A到C的最短路径+从C到D的最短路径
计算最优解时是按照：CD->BD->AD来计算的

值函数和贝尔曼方程

强化学习的数学模型：马尔可夫决策过程

基于马尔可夫链定义三个重要概念：

• 累积折扣奖励

一个好的策略不仅要考虑单步即时奖励，更重要的是考虑长期的累积奖励。然而，未来时间步的奖励要根据时间步逐渐久远而逐渐消减重要性。在实际任务中，通常将折扣后的即时奖励进行累积，这就是累积折扣奖励。

有了累积折扣奖励之后，强化学习的目标可以表述为选择一个能够使累积折扣奖励Gt最大的最优策略。

• 值函数

累积折扣奖励是针对某一条马尔可夫链而言的，但从同一种状态出发，不同的交互过程可能产生完全不同的马尔可夫链，所以只考虑单条链的累积折扣奖励是不够的。智能体更关心的是从某一条状态出发的累积折扣奖励的期望，也就是值函数。

image.png

根据输入的不同，值函数可以分为状态值函数和动作值函数。
状态值函数：
设当前策略为π，从状态s出发的累积折扣奖励的期望为状态s的状态值函数。

image.png

image.png

动作值函数和状态值函数的相互转化：

（2-7）

（2-8）

• 贝尔曼方程
  将式2-7和2-8相互代入可以得到著名的贝尔曼方程：

  
  
  2-9

2-10

贝尔曼方程定义了当前状态与未来状态的迭代关系，表示当前状态的价值函数可以通过下个状态的价值函数来计算。贝尔曼方程因其提出者、动态规划创始人理查德⋅贝尔曼（Richard Bellman）而得名，同时也被叫作“动态规划方程”。贝尔曼方程即 V(s)=R(s)+γ∑s′∈SP(s ′∣s)V(s′) ，特别地，其矩阵形式为 V=R+γPV。

策略评估

在环境模型已知的前提下，对任意的策略π，需要估算该策略下的累积折扣奖励的期望以衡量该策略的优劣程度，这就是策略评估(PolicyEvaluation,PE)。

策略改进

策略评估的目的是衡量策略的好坏程度，而策略改进(Policy Improvement,PI)则是为了找到更优的策略。策略改进就是利用对当前策略评估得到的状态值函数来算出一个新的更优的策略。

最优值函数和最优策略

在第1章中已经提到强化学习的目标是寻找一个最优策略π*,2.4节通过值函数概念定义了最优策略，本节讨论最优策略的存在性及最优策略和值函数的关系。

策略迭代和值迭代

策略迭代和值迭代是两个最基本的强化学习算法框架，策略迭代采用策略评估和策略改进交替进行，最终同时收敛到最优，而值迭代是状态值先收敛到最优，然后用最优动作值求出最优策略