2021 重启强化学习(5) 马尔可夫决策过程和动态规划

cover_001.png

如果想观看相关视频可以在西瓜视频(账号zidea)或者哔哩哔哩(账号zidea2015)找到我发布视频解说，注意头像和简书使用头像一致。

在 MDP 中策略估计(Policy evaluation)

目标: 评估一个给定了定策略 $\pi$ 的马尔可夫决策过程(MDP)
输出: 计算出一个策略价值函数 $v_{\pi}$
解决方案: 通过贝尔曼期望方程回溯进行迭代
算法: 同步回溯
考虑所有在 t+1 时刻的状态可能，这里状态 $s \in \cal{S}$ ，可以通过一个 s 状态的后续装 $s^{\prime}$ 的价值函数来更新 $v_{t+1}(s)$ 从而形成迭代
$v_{t+1}(s) = \sum_{a \in \cal{A}} \pi(a|s) \left( R(s,a) + \gamma \sum_{s^{\prime} \in \cal{S}} P(s^{\prime}|s,a) v_t(s^{\prime}) \right)$
逐渐收敛 $v_1,v_2,v_{\pi}$

通过马尔可夫奖励过程 $<\cal{S},\cal{P}_{\pi},\cal{R}_{\pi},\gamma>$

$v_{t+1}(s) = R_{\pi}(s) + \gamma P_{\pi}(s^{\prime}|s)v_t(s^{\prime})$

通过边缘概率将动作 $a$ 去掉，从而得到一个简化马尔可夫奖励过程。

这里价值函数只跟状态和价值有关，也就是未来进入某一个状态会得到多少奖励
引入动作(Action)就是其实就是引入智能体对状态转移的控制，状态转移不再是根据上一个状态的随机转移，而是引入了动作(Action)来控制状态的转移。

005.png

$V_{\pi}(s) = \sum_{a \in \cal{A}} \pi(a|s)\left( R(s,a) + \gamma \sum_{s^{\prime} \in \cal{S}} P(s^{\prime}|s,a) V_{\pi}(s^{\prime}) \right)$

$v^{\pi} = \sum_{a\in \cal{A}} \pi(a|s)R(s,a) + \gamma \sum_{s^{\prime} in \cal{S}}P(s^{\prime}|s)v_{\pi}(s^{\prime})$

006.png

策略迭代(Policy iteration)

最优策略和最优值函数

在强化学习中，假设马尔可夫决策过程是有限马尔可夫决策过程，状态和动作的集合是有限的。这样的马尔可夫决策过程也是有限马尔可夫决策过程。所以在策略中一定存在一个最优策略，可以表示为 $\pi^{*}$ 我们是根据价值函数来评估一个策略的好坏。其实很简单，强化学习的最终目标就是尽可能地多获得回报值 $v_{\pi}^{\prime} > v_{\pi}$ 时也就有 $\pi^{\prime} > \pi$

而对于最优策略，其值函数的值也必然是最大的。

$v^{*}(s) = \max_{\pi} v_{\pi}(s)$

搜索遍历 $\pi$ ，
首先要清楚价值函数对每个状态评估，因为状态转移会受到采取什么样的动作所决定。我们要找到一个可以让每一个状态值最大的策略，对应于状态值最大的策略就是我们要找的最优策略。这里最优策略就用

$\pi^{*}(s) = \argmax_{\pi} v_{\pi} (s)$

所以当我们说某一个 MDP 被解就是我们找到了可以状态值最大所对应的 $\pi^{*}(s)$ 策略函数。

获取最优策略

Q 函数状态和动作的函数，直接在 Q 函数获取最大化值
当 $a = \argmax_{a \in \cal{A}} Q^*(s,a)$ 是 $\pi^{*}(a|s) = 1$ 否则为 0

策略搜索

遍历所有可能的策略
所有的策略为 $|\cal{A}|^{|\cal{S}|}$
这样列举所有可能动作是非常没有效率的，这里其他方法如策略迭代(Policy Iteration)和价值迭代(Value Iteration)
寻找最佳策略过程

策略迭代(Policy Iteration)

策略评估
改进策略

策略评估

$\pi^{*}(s) = \argmax_{\pi} v^{\pi} (s)$

确定性
静态(这里静态是相对于时间而言)
不唯一

007.png

也就是优化现有的策略函数 $\pi$ ，先保证这个策略函数 $\pi$ 然后计算当前 $\pi$ 的价值函数，当计算出 $v_{\pi}$ 函数，从而推断其 $q_{\pi}$ 函数，最后直接在 $q_{\pi}$

$\pi^{\prime} = greedy(v^{\pi})$

改进策略

计算策略函数 $\pi$ 的状态动作(state-action)价值函数
$Q_{\pi_i}(s,a) = R(s,a) + \gamma \sum_{s^{\prime} \in \cal{S}} P(s^{\prime}|s,a) V_{\pi_i}(s^{\prime})$
计算新的策略 $\pi_{i+1}$
$\pi_{i+1}(s) = \argmax_a Q_{\pi_i}(s,a)$

然后根据贝尔曼等式满足

策略单调递增

条件是策略是确定性策略 $a = \pi(s)$
我们通过下面的公式来优化策略
也就是整个状态已经收敛之后

贝尔曼优化等式(Bellman Optimality Equation)

$V_{\pi}(s) = max_{a \in \cal{A}} Q_{\pi}(s,a)$

$Q_{\pi}(s,\pi^{\prime}(s)) = \max_{a \in \cal{A}} Q_{\pi}(s,a) \ge Q_{\pi} (s,\pi(s)) = V_{\pi}(s)$

这个式子成立原因: 若 $\pi$ 为确定即每一步 a 不是随机， $\pi(a|s)$ 只能在一个 a 上取 1 其他为 0 因此

对于 $\pi$ 是确定，也就是最大

$\begin{aligned} V_{\pi}(s) = E_{\pi}[R_{t+1} + \gamma V_{\pi}(S_{t+1})|S_t = s]\\ Q_{\pi}(s,a) = E_{\pi}[R_{t+1} + \gamma Q_{\pi}(s_{t+1},a_{t+1})|S_t = s,A_t=a]\\ \end{aligned}$

$\begin{aligned} V_{\pi}(s) \le Q_{\pi}(s,\pi^{\prime}(s))\\ = \mathbb{E}[R_{t+1} + \gamma V_{\pi}(S_{t+1})|S_t = s,A_t = \pi^{\prime}(a)]\\ = \mathbb{E}_{\pi^{\prime}}[R_{t+1} + \gamma V_{\pi}(S_{t+1})|S_t = s]\\ \le \mathbb{E}_{\pi^{\prime}}[R_{t+1} + \gamma Q_{\pi}(s_{t+1},\pi^{\prime}(s_{t+1}))|S_t = s]\\ \mathbb{E}_{\pi^{\prime}}[R_{t+1} + \gamma \mathbb{E}_{\pi^{\prime}} [R_{t+2} + \gamma v_{\pi}(s_{t+2})]|S_t = s]\\ = \mathbb{E}_{\pi^{\prime}} [R_{t+1} + \gamma R_{t+2} + \gamma^2 v_{\pi}(s_{t+2}) |S_t = s]\\ \cdots\\ \le \mathbb{E}_{\pi^{\prime}} [R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots |S_t =s ]\\ = V_{\pi^{\prime}}(s) \end{aligned}$

$\begin{aligned} V^*(s) = \max_{a} Q^*(s,a)\\ Q^*(s,a) = R(s,a) + \gamma \sum_{s^{\prime} \in \cal{S}} P(s^{\prime}|s,a)v^*(s^{\prime}) \end{aligned}$

$\begin{aligned} V^*(s) = \max_{a} R(s,a) + \gamma \sum_{s^{\prime} \in \cal{S}} P(s^{\prime}|s,a)v*^*(s^{\prime})\\ Q^*(s,a) = R(s,a) + \gamma \sum_{s^{\prime} \in \cal{S}} P(s^{\prime}|s,a) \max_{a^{\prime}} Q^*(s^{\prime},a^{\prime}) \end{aligned}$

价值迭代(value iteration)

带有备忘录的递归
贝尔曼期望方程(bellman equation)递归
价值函数用于存储

$v(s) \leftarrow \max_{a \in \cal{A}} \left( R(s,a) + \gamma \sum_{s^{\prime} \in \cal{S}} P(s^{\prime}|s,a)v(s^{\prime}) \right)$

目标

找到一个最优的策略函数 $\pi$

求解

迭代贝尔曼最优方程(Bell optimality)回溯

价值迭代算法

对于所有状态初始化 k=1 和 $v_0(s) = 0$
遍历每一个状态
$Q_{k+1} = R(s,a) + \gamma \sum_{s^{\prime} \in \cal{S}} P(s^{\prime}|s,a)v_k(s^{\prime})$
$v_{k+1} = \max_{a} Q_{k+1}(s,a)$

$\pi(s) = \arg \max_{a} R(s,a) + \gamma \sum_{s^{\prime} \in \cal{S}} P(s^{\prime}|s,a)v_{k+1}(s^{\prime})$