动态规划求解强化学习任务——整体介绍

• 目录
• • 动态规划与强化学习任务之间的关联关系
  • • 动态规划思想
    • 动态规划在强化学习任务中的思想
    • • 有穷性
      • 不动点定理(Fixed-point Theorem)
  • 动态规划求解强化学习任务
  • • 策略迭代
    • • 策略评估
      • 策略改进
    • 价值迭代
    • • 策略迭代的缺陷：
      • 价值迭代的处理方法

目录

在贝尔曼期望方程和贝尔曼最优方程中完整介绍了马尔可夫决策过程(Markov Decision Process, MDP)在$t\to t+1$时刻状态 S t → St+1 S_t \to S_{t+1} St​→St+1​的转移过程，并对该过程进行数学方式的表达。

但是，仅仅知道某一步的最优解是远远不够的，我们最终希望得到整个过程的最优策略(全局最优策略) πmax \pi_{max} πmax​。接下来我们将介绍如何使用算法(Algorithm) 在马尔可夫决策过程中一步步地接近强化学习任务中的全局最优策略 πmax \pi_{max} πmax​。

从本节开始将介绍动态规划(Dynamic Programming,DP) 思想求解强化学习任务。本节主要介绍以下两个方面：

• 什么样的强化学习任务可以使用动态规划思想求解？
• 动态规划思想求解强化学习任务包含哪些具体方法？

动态规划与强化学习任务之间的关联关系

动态规划思想

动态规划是运筹学的一个分支，通常用于求解全局最优问题。动态规划思想和分治法(Divide and Conquer) 之间存在相似之处，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解中得到原问题的解。

不同于分治法的是，在问题分解成子问题的过程中，子问题之间往往不是相互独立的。 甚至子问题之间可能是相互嵌套的关系，你中有我，我中有你。

处理这种问题时，使用分治思想可能存在将某个子问题重复计算多次的情况。而动态规划思想是，将某个子问题计算结束后，直接将该结果存到一个表格中，一旦再出现该子问题 $\to$ 直接从表格中查找，而不是再次计算。这种操作的优点是：避免大量重复计算，节省时间。

动态规划在强化学习任务中的思想

现在面对第一个问题：什么样的强化学习任务可以使用动态规划思想求解？

我们可以从问题的问法中感觉到，并不是所有的强化学习任务都可以使用动态规划求解，而是一些强化学习任务中的某些特性和动态规划思想相契合，使用动态规划方法可能起到事半功倍的效果。
我们从两个逻辑角度回答该问题：

• 有穷性
• 不动点定理

有穷性

强化学习任务中的基础信息是有穷的。
我们这里提到的基础信息是指状态(State)，动作(Action)，奖励(Reward)。
有穷的意思自然是可数的，离散的。
这里并没有将衰减因子(gamma)算进去，有不同见解的小伙伴欢迎批评指正。
我们针对有穷的基础信息进行场景假设：
状态集合$\mathcal{S}$属于离散型随机变量，共包含3种状态；
S = {s1 ,s2 ,s3 } \mathcal S = \{s_1,s_2,s_3\} S={s1​,s2​,s3​}
动作集合 $\mathcal{A}$属于离散型随机变量，共包含3种动作；
A = {a1 ,a2 ,a3 } \mathcal A = \{a_1,a_2,a_3\} A={a1​,a2​,a3​}
奖励集合$\mathcal{R}$属于离散型随机变量，共包含3种奖励；
R = {r1 ,r2 ,r3 } \mathcal R=\{r_1,r_2,r_3\} R={r1​,r2​,r3​}
结合上述假设，我们的策略无外乎是这样的一个矩阵：
假设在每个状态下，上述3个动作均有意义

上述表格映射出一个3*3的方阵，并且该场景中所有可能发生的策略均在矩阵中有所表示：那么使用动态规划求解任务中，只需要通过矩阵查找即可；在迭代过程中，只需更新对应位置的元素即可。
相反，如果状态(State)是连续型随机变量，那么状态集合$\mathcal{S}$中将会产生无限种可能的状态信息；
S = {s1 ,s2 ,s3 , . . . } \mathcal S = \{s_1,s_2,s_3,...\} S={s1​,s2​,s3​,...}
这种情况下，策略矩阵中状态(State)对应的维度也是无穷的；
从实际角度来看，表格(矩阵)的查询操作同样是存在时间复杂度的，如果矩阵查询的时间超过了运算时间 $\to$ 动态规划在当前场景就没有意义了。

同理，上述解释的是关于策略的矩阵，我们同样可以使用类似的矩阵来描述状态价值函数等其他迭代信息。
假设给定策略矩阵$\pi$,结合上述场景，构建状态价值函数矩阵。
由于只包含1个变量，它也是一个列向量

不动点定理(Fixed-point Theorem)

我们回顾一下求解状态价值函数的贝尔曼期望方程(Bellman Expectation Equation)：
Vπ ( s ) =∑ a ∈ A π ( a ∣ s )∑ s ′, r p (s′ , r ∣ s , a ) ( r + γVπ (s′ ) ) V_\pi(s) = \sum_{a \in \mathcal A}\pi(a \mid s)\sum_{s',r}p(s',r \mid s,a)(r + \gamma V_\pi(s')) Vπ​(s)=a∈A∑​π(a∣s)s′,r∑​p(s′,r∣s,a)(r+γVπ​(s′))

发现贝尔曼期望方程是满足不动点方程条件的 $\to$ 使用价值函数做变量，表示价值函数本身。即：
$$x=f(x)$$
我们将这种 利用状态 s′ s' s′的状态价值函数 Vπ (s′ ) V_\pi(s') Vπ​(s′)表示状态$s$的状态价值函数 Vπ ( s ) V_\pi(s) Vπ​(s) 的方法称为自举法(Bootstrapping)

在已知动态特性函数 p ( s ′ , r ∣ s , a ) p(s',r \mid s,a) p(s′,r∣s,a)和对应期望奖励$r(a,s)$的情况下，给定当前策略$\pi (a\mid s)$，我们可以通过 s ′ s' s′状态的价值函数更新s状态的价值函数并不断迭代下去，根据不动点定理最终将所有状态在当前策略$\pi$下对应的价值函数均收敛到最优。
V k + 1 ( s ) =∑ a ∈ A π ( a ∣ s ) [ r ( a , s ) + γ∑ s ′∈ S p (s′ , r ∣ s , a )Vk (s′ ) ] V_{k+1}(s) = \sum_{a \in \mathcal A} \pi(a \mid s)[r(a,s) + \gamma \sum_{s' \in \mathcal S}p(s',r \mid s,a)V_k(s')] Vk+1​(s)=a∈A∑​π(a∣s)[r(a,s)+γs′∈S∑​p(s′,r∣s,a)Vk​(s′)]
自举法(Boostrapping)和迭代求解 -> 我们会在后续“策略评估——使用迭代方式求解最优价值函数”部分详细讲解传送门
期望奖励(Expected Reward)是马尔克夫决策过程(MDP)中一个知识点，但在贝尔曼期望方程的推导中使用的是回报(Return)而不是期望奖励 -> 我们会在后续"策略评估——使用解析方式求解最优价值函数"部分详细讲解传送门

对不动点定理证明感兴趣的小伙伴点击这里,欢迎在评论区内进行讨论。

动态规划求解强化学习任务

动态规划求解强化学习任务本质上是通过迭代(Strategy)的方式得到最优策略。迭代主要包含两大方法：

• 策略迭代(Policy Iteration)
• 价值迭代(Value Iteration)

策略迭代

策略迭代通过构建策略的价值函数( V π ( s ) , q π ( s , a ) V_\pi(s),q_\pi(s,a) Vπ​(s),qπ​(s,a))来评估当前策略，并利用这些价值函数给出改进后的新策略。策略迭代主要包括2个部分：

• 策略评估(Policy Evaluation,PE)
• 策略改进(Policy Improvement,PI)

策略评估

策略评估本质上做了一件事情：对于$\forall s\in \mathcal{S}$，已知动态特性函数p (s′ , r ∣ s , a ) p(s',r \mid s,a) p(s′,r∣s,a)，在给定策略$\pi (a\mid s)$的条件下，如何通过计算得到状态价值函数 Vπ ( s ) V_\pi(s) Vπ​(s)/状态动作价值函数 qπ ( s , a ) q_\pi(s,a) qπ​(s,a)。
策略评估具体包含两种方式：

• 直接求解价值函数的解析解。
• 使用迭代方式求解价值函数的迭代解。

策略改进

在已经获取价值函数的基础上，如何利用价值函数对策略进行改进，并最终得到最优策略。
常用方式是对每个状态采用贪心策略对当前策略进行改进。

价值迭代

策略迭代的缺陷：

上面介绍到，策略迭代的策略评估包含解析解和迭代解两种方式，在环境完备的情况下，状态价值函数的贝尔曼期望方程就是一个包含$|\mathcal{S}|$个未知量的$|\mathcal{S}|$元方程组($|\mathcal{S}|$表示状态数量)。而解析解的方式就是直接对上述方程组进行求解。
但如果状态较多，甚至无穷多的情况下，很难使用方程组方法直接求解强化学习问题(时间复杂度极高 → ∣ S ∣ 3 \to |\mathcal S|^3 →∣S∣3 )。
上述时间复杂度的产生在“策略评估——使用解析方式求解价值函数”部分详细讲解

针对解析解方式解方程组难的问题，我们使用迭代解方法简化求解过程，在策略迭代中，每一轮策略改进之前都要执行一次策略评估，即便使用迭代解方法 $\to$ 仍然需要多次遍历才能保证状态价值函数在一定程度上进行收敛。

价值迭代的处理方法

尝试考虑 执行一次策略评估之后，直接进行策略改进的迭代状态；

迭代到什么程度呢？
迭代到所有状态的价值函数都被迭代一遍之后(所有状态的价值函数结果都被更新过，而不是预先设置的初始值)，停止策略评估；$\to$ 随后进行策略改进；

下一节从策略评估——使用解析方式求解价值函数开始，对采用动态规划求解强化学习任务进行详细介绍。

相关参考：
动态规划 - 百度百科
强化学习——动态规划(策略评估，策略改进)
【强化学习】动态规划【白板推导系列】
强化学习中无处不在的贝尔曼最优性方程，背后的数学原理知多少？
深度强化学习原理、算法pytorch实战 —— 刘全，黄志刚编著