跳转至

动态规划方法

对于简单的强化学习环境,如果环境的状态转移完全可知,则可以使用动态规划方法对问题进行求解。

概念定义

价值函数

状态-价值映射又称为价值函数\(V_\pi(s)\),指智能体按照策略\(\pi\)执行,处于状态\(s\)时所能获得的期望回报。

\[ V_\pi(s) \triangleq \mathbb{E}_\pi \left[ \sum_{t=0}^{\infty} \gamma^t r_t \middle | s_0 = s \right] \]
Q函数

Q函数是动作-价值映射\(Q_\pi (s, a)\),指智能体从状态\(s\)采取动作\(a\)开始,之后按照策略\(\pi\)执行,所能得到的期望回报。

\[ Q_\pi(s, a) \triangleq \mathbb{E}_\pi \left[ \sum_{t=0}^{\infty} \gamma^t r_t \middle | s_0 = s, a_0 = a \right] \]
提升函数

提升函数是智能体在当前状态采取动作\(a\),相较于严格按照策略\(\pi\)执行所能获得的期望回报的提升。

\[ A_\pi (s, a) \triangleq Q_\pi(s, a) - V_\pi(s) \]

提升函数满足

\[ E_{\pi(s\mid a)} \left[ A_\pi (s, a) \right] = 0 \]

最优策略是能够最大化所有状态的价值函数的策略,即\(V^*(s) \geq V_\pi(s), \forall \pi\)。状态-价值映射和动作-价值映射最优,当且仅当满足Bellman最优性或Bellman方程:

\[ \begin{aligned} V^*(s) &= \max_{a} \left[R(s, a) + \gamma \sum_{s'} P(s'|s, a)V^*(s')\right] \\ Q^*(s, a) &= R(s, a) + \gamma \sum_{s'} P(s'|s, a)V^*(s') \end{aligned} \]

Bellman方程可以写成向量形式:

\[ \begin{aligned} & \bsv = \bsr_{\pi} + \gamma \bsP_{\pi} \bsv \\ \text{where} & \left\{\begin{aligned} \bsv_s &= V^*(s) \\ \bsr_{\pi, s} &= \sum_a \pi(a|s) R(s, a) \\ \bsP_{\pi, s, s'} &= \sum_a \pi(a|s) P(s'|s, a) \end{aligned}\right. \end{aligned} \]

最优策略可以通过动作-价值函数导出。

\[ \pi^*(s) = \arg \max_a Q^*(s, a) \]

更新策略的过程称为策略优化,根据策略计算状态价值函数和动作价值函数的过程称为策略评估。

价值迭代

价值迭代是动态规划方法中最简单的一种。它的基本思想是通过迭代更新状态价值函数,直到收敛为止。价值迭代的步骤如下:

\[ V_{s + 1}(s) = \max_{a} \left[R(s, a) + \gamma \sum_{s'} P(s'|s, a)V_s(s')\right] \]

计算贝尔曼残差\(\Delta_k = \max_s |V^*(s) - V_k(s)|\),满足

\[ \begin{aligned} \Delta_k &= \max_s [V^*(s) - V_k(s)] \\ \Delta_{k + 1} &= \max_s [V^*(s) - V_{k + 1}(s)] \\ &= \max_s \left[\max_{a} \left[R(s, a) + \gamma \sum_{s'} P(s'|s, a)V^*(s')\right] - \max_{a} \left[R(s, a) + \gamma \sum_{s'} P(s'|s, a)V_k(s')\right]\right] \\ &\leq \max_s \left[ \max_a \gamma \sum_{s'} P(s'|s, a)(V^*(s') - V_k(s')) \right] \\ &=\max_s \left[V^*(s) - V_k(s)\right] \\ &\leq \gamma \Delta_k \end{aligned} \]

因此,价值迭代算法能保证对价值函数的估计逐渐趋近最优。价值迭代无论是同时更新所有状态的价值函数,还是逐个更新状态的价值函数,都是收敛的。

策略迭代

策略迭代是一种常用的求解动态规划问题的方法。它包含两个步骤,即策略评估和策略提升。在策略评估阶段,算法根据当前策略和上一次迭代的状态价值函数,计算当前的状态价值函数。

\[ \bsv_{k + 1} = \bsr_{\pi_k} + \gamma \bsP_{\pi_k} \bsv_k \]

在策略提升阶段,算法根据当前的状态价值函数,计算出一个新的策略。

\[ \pi_{k + 1}(s) = \arg \max_a \left[R(s, a) + \gamma \sum_{s'} P(s'|s, a)V_k(s')\right] \]

可以证明,\(\bsv_{k + 1}\geq \bsv_k\)

评论