2021 重启强化学习(4) 马尔可夫决策过程(MDP)

马尔可夫决策过程

cover_001.png

马尔可夫决策过程(MDP)

可以通过马尔可夫决策过程来表示智能体和环境交互的整个过程

马尔可夫过程(Markov Process)

马尔可夫属性(Markov Property)

$\begin{aligned} p(s_{t+1}|s_t) = p(s_{t+1}|h_t)\\ p(s_{t+1}|s_t,a_t) = p(s_{t+1}|h_t,a_t) \end{aligned}$

$h_t = \{s_1,s_2,\cdots,s_t\}$
第一个性质就是当前智能体状态(agent state)只与上一个状态有关，与历史状态无关，例如在 alphaGo 棋盘对于当前状态，只需要考虑上一个状态(棋盘的布局)
$H_{1:t} \rightarrow S_t \rightarrow H_{t+1:\infty}$

$\cal{P}_{ss^{\prime}} = P(S_{t+1}=s^{\prime}|S_t = s)$

$\cal{P}= \begin{bmatrix} p(s|s)=0.6 & p(c|s)=0.3 & p(r|s) = 0.1\\ p(s|c)=0.2 & p(c|c)=0.3 & p(r|c)=0.5\\ p(s|r)=0.4 & p(c|r)=0.1 & p(r|r)=0.5\\ \end{bmatrix}$

以上就是马尔可夫链的状态转移矩阵，通过查表的形式，我们就可以了解当处于某一个状态，接下来转移到另一个状态的概率是多少。那么马尔可夫链(Markov chain) 也可以看作马尔可夫过程可以看作一个状态集合以及这些状态间转移的矩阵表示为 $(\cal{S},\cal{P})$

$\cal{S}$ 表示有限状态的集合
$\cal{P}$ 状态转移矩阵 $\cal{P}_{ss^{\prime}} = P(S_{t+1}=s^{\prime}|S_t = s)$

008.png

	c1	c2	c3	pub	facebook	sleep
c1		0.5			0.5
c2			0.8			0.2
c3				0.6	0.4
pass						1.0
pub	0.2	0.4	0.4
facebook	0.1				0.9
sleep						1.0

这就是轨迹概念，每一条链都是一条轨迹

$c_1, c_2,c_3,pass,sleep$
$c_1, facebook,facebook,c_1,c_2,c_3,pub,c_2,sleep$
$c_1, c_2,sleep$

马尔可夫奖励过程(MRPs)

马尔可夫奖励过程，就是马尔可夫链再加上一个奖励(Reward)函数

定义马尔可夫奖励过程(MRP)，可以表示为
- $\cal{S}$ 表示状态集合 $s \in \cal{S}$
- $\cal{P}$ 是动态/转移模型可以表示为 $\cal{P}_{ss^{\prime}}(S_{t+1} = s^{\prime}|S_t = s)$
- $\cal{R}$ 是奖励函数，可以表示为 $R(S_t = s) = \mathbb{E}[R_{t+1}|S_t = s]$
- Discount factor(折扣量) $\gamma \in [0,1]$

009.png

回报与价值函数

有限扩展(horizon)

在每一个 episode 存在最大有限步数

回报(Return)

根据动作和状态对未来奖励进行一定折扣累加计算来表示 t 时刻的回报(收益)
$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots + \gamma^{T-(t-1)}R_t$
$G_t = \sum_{k=0}^{\infty} \gamma^{k}R_{t+k+1}$

定义状态价值函数 $V_t(s)$

状态价值函数是最终衡量状态的获取多少奖励函数，从 s 状态开始可以计算还可以得到多少累计函数，在 AlphaGo 中有估值函数，当给系统棋牌状态，状态包括是黑方还是白方，接下来是白棋先走还是黑棋先走。
期望也就是从这个状态 s 开始向后可以获得多大价值，也可以理解为进入到当前状态之后会有多大价值
$V_t(s) = \mathbb{E}[G_t|s_t = s]$
$V_t(s) = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots + \gamma^{T-(t-1)}R_t|s_t = s]$

折扣因子 $\gamma$ 存在的意义

也可以看作对于未来可以获得多少奖励当前价值的一个表现解释 $\gamma$

避免在带环马尔可夫过程出现无穷奖励的问题
也希望把不确定表示出来，尽快得到奖励而不是在未来某一个点得到奖励
对于有价值的奖励，我们希望立刻得到奖励，而不是在未来得到奖励(例如股票)
立刻得到奖励也是符合人的行为
关于超参数的取值意义
- 系数设置 0 则只关注当前奖励
- 设置为 1 ，也就是表示未来奖励并没有折扣，则表示关心未来的奖励

009.png

$\begin{aligned} c1,c2,c3,pass,sleep\\ c1,facebook,facebook,c1,c2,c3,pub,c2,sleep\\ c1,c2,sleep \end{aligned}$

计算状态价值函数

$\begin{aligned} v_1 = -2 -2 \frac{1}{2} -2 +10\frac{1}{8} = -2.25\\ v_1 = -2-\frac{1}{2}-\frac{1}{4}+\cdots = -3.125\\ v_1 = -2-2\frac{1}{2}-0\frac{1}{4} =-3\\ =-2.9 \end{aligned}$

马尔可夫奖励过程贝尔曼方程

$\begin{aligned} V(s) = \mathbb{E}[G_t|S_t=s]\\ = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} \cdots|S_t=s]\\ = \mathbb{E}[R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4}) \cdots|S_t=s]\\ = \mathbb{E}[R_{t+1} + \gamma (G_{t+1})|S_t=s]\\ = \mathbb{E}[R_{t+1} + \gamma V(S_{t+1})|S_t=s]\\ \end{aligned}$

$\mathbb{E}[x] = \sum_{i=1}^{\infty} x_i p_i$

$V(s) = \cal{R}_s + \gamma \sum_{s^{\prime} \in \cal{S}} \cal{P}_{ss^{\prime}}V(s^{\prime})$

$\begin{bmatrix} V(s_1)\\ V(s_2)\\ \vdots \\ V(s_N)\\ \end{bmatrix} = \begin{bmatrix} R(s_1)\\ R(s_2)\\ \vdots \\ R(s_N)\\ \end{bmatrix} + \gamma \begin{bmatrix} P(s_1|s_1) & P(s_2|s_1) & \cdots & P(s_N|s_1) \\ P(s_1|s_2) & P(s_2|s_2) & \cdots & P(s_N|s_2) \\ \vdots & \vdots & \cdots & \vdots \\ P(s_1|s_N) & P(s_2|s_N) & \cdots & P(s_N|s_N) \\ \end{bmatrix} \begin{bmatrix} V(s_1)\\ V(s_2)\\ \vdots \\ V(s_N)\\ \end{bmatrix}$

$\begin{aligned} v = \cal{R} + \gamma \cal{P}v\\ (I - \gamma \cal{P})v = \cal{R}\\ v = (I - \gamma \cal{P})^{-1}\cal{R} \end{aligned}$

011.png

$v(s) = \cal{R}_s + \gamma \sum_{s^{\prime} \in \cal{S}} \cal{P}_{ss^{\prime}} v(s^{\prime}) = -2 + 0.5 \times(0.6 \times 10 + 0.4 \times 0.8) = 0.6$

马尔可夫决策过程(MDP)

马尔可夫决策过程(MDP)，当我们买了某只股票，或者投掷硬币进行下注，之后我们就能等待结果，根据结果来得到回报。马尔可夫决策过程(MDP) 会根据不同状态进行不同动作。可以表示为 $< \cal{S},\cal{A},\cal{P},\cal{R},\gamma >$

$\cal{S}$ 表示状态的集合
$\cal{A}$ 表示动作的集合，对于任意 $s \in \cal{S}$ 通常来用 $A(s)$ 表示动作集合是针对于某一个状态来说
$\cal{P}$ 是 Action 是动态/转移模型 $P_{ss^{\prime}}^a = P(S_{t+1} = s^{\prime}|S_t = s,A_t = a)$ ，也就是 MDP 动态特性
P 状态转移函数 $P(S_{t+1} = s^{\prime}|S_t = s,A_t = a) = \sum_{r \in R} p(s^{\prime},r|s,a)$
R 是奖励函数 $R(S_t = s,A_t = a) = \mathbb{E}[R_{t+1}|S_t = s,A_t = a]$
折扣系数 $\gamma \in [0,1]$
MDP 是 $< \cal{S},\cal{A},\cal{P},\cal{R},\gamma >$ 表现形式

MRP 更像一种自由经济，充分相信市场能力，并不进行人为干涉。

MDP 中的策略(Policy)

策略函数(Policy)在每一个状态都会给出一个动作，是一个状态到动作映射的函数
策略函数(Policy)输出是的在当前状态所有可能动作的概率分布
策略函数(Policy) 变现形式为:
$\pi(a|s) = P(A_t=a|S_t=s)$
还有这里有一个假设就是策略函数是静态，不同时间上概率分布是独立的

MP、MRP 和 MDP 之间相互关系

$MDP(S,A,P,R,\gamma)$ 和策略函数 $\pi$ 这些构成了马尔可夫决策过程
在马尔可夫过程表示 $(S,P_{\pi})$ 具体来说就是状态序列 $S_1,S_2,\cdots,$
在马尔可夫奖励过程表示 $(S,P_{\pi},R_{\pi},\gamma)$ 具体来说就是状态序列 $S_1,R_1,S_2,R_2\cdots,$

他们之间相互转换为
$P_{\pi}(s^{\prime}|s) = \sum_{a \in A} \pi(a|s) P_{\pi}(s^{\prime}|s,a)$

在 MDP 过程中是根据当前状态和采取动作来转移到下一个状态
因为 $\pi(a|s)$ 可以给出当前状态下可能采取动作的概率分布所以通过求边缘概率可以将 a 去掉从而得到马尔可夫过程

$R_{\pi}(s^{\prime}|s) = \sum_{a \in A} \pi(a|s) R_{\pi}(s,a)$

001.png

002.png

价值函数

状态价值函数(state-value function)

其实 $G_t$ 是由随机变量 $A_{t+1},A_{t+2},\cdots$ 和 $S_{t+1},S_{t+2},\cdots$ ，所以会有很多重可能，每种 $A$ 和 $S$ 组合都会得到不同 $G_t$ ,每一个种可能可以看成一个路径。

$V_{\pi}(s) = \mathbb{E}_{\pi}[G_t|S_t = s]$

动作价值函数(action-value function)

$Q_{\pi}(s,a) = \mathbb{E}_{\pi}[G_t|S_t = s,A_t = a]$

这里的自变量 $S_t$ 和 $A_t$ 都是自变量，并不是存在任何特定的关系，不是成对出现。

状态价值函数和动作价值函数之间关系

在 $Q_{\pi}(s,a)$ 对 $s$ 是没有约束，这一点跟上面 $V_{\pi}(s)$ 有所不同的，这一点需要大家注意一下。在 $V_{\pi}(s)$ 就是反应一个 $s$ 会对应一个 $a$ 的概率分布

$\begin{aligned} \pi(a_1|s)Q_{\pi}(s,a_1)\\ + \pi(a_2|s)Q_{\pi}(s,a_2)\\ + \pi(a_3|s)Q_{\pi}(s,a_3)\\ \end{aligned}$

$V_{\pi}(s) = \sum_{a \in A} \pi(a|s)Q_{\pi}(s,a)$

贝尔曼期望方程(Bellman Expectation Equation)

价值函数:返回状态 s 随后得到回报
$\begin{alignedat} V_{\pi}(s) = \mathbb{E}_{\pi}[G_t|S_t=s]\\ = \mathbb{E}_{\pi}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots|S_t=s]\\ = \mathbb{E}_{\pi}[R_{t+1} + \gamma V_{\pi}(S_{t+1})|S_t=s]\\ V_{\pi}(s) = \sum_{a \in \cal{A}} \pi(a|s) Q_{\pi}(s,a) \end{alignedat}$

$\begin{aligned} Q_{\pi}(s,a) =\mathbb{E}_{\pi}[G_t|S_t=s,A_t=a]\\ = \mathbb{E}_{\pi}[R_{t+1} + \gamma Q_{\pi}(S_{t+1},A_{t+1})|S_t=s,A_t=a]\\ = \cal{R}_s^a + \gamma \sum_{s^{\prime} \in \cal{S}} \cal{P}_{ss^{\prime}}^a V_{\pi}(s^{\prime}) \end{aligned}$

建立关系

$\begin{aligned} V_{\pi}(s) = \sum_{a \in \cal{A}} \pi(a|s) Q_{\pi}(s,a)\\ = \sum_{a \in \cal{A}} \pi(a|s) \left( \cal{R}_s^a + \gamma \sum_{s^{\prime} \in \cal{S}} \cal{P}_{ss^{\prime}}^a V_{\pi}(s^{\prime}) \right) \end{aligned}$

MDP 求解

预测(prediction)

对于给定策略，判断每个状态下的奖励是多少，通过状态价值函数来预测当前策略会产生多少价值

输入 $MDP <\cal{S},\cal{A},\cal{P},\cal{R},\gamma>$ 和策略函数 $\pi$ 或者 $MRP <\cal{S},\cal{P}_{\pi},\cal{R}_{\pi},\gamma>$
输出为 $V_{\pi}$ 函数

控制(control)

寻找最优策略，得到最优价值函数

输入 $MDP <\cal{S},\cal{A},\cal{P},\cal{R},\gamma>$
输出: 最优价值函数 $v^*$ 和最优策略函数 $\pi^*$

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

处于无限扩展问题(infinite horizon proble)的 MDP 过程的优化策略通常具有以下性质

确定性
静态的
并不唯一

预测和控制在 MDP 可以通过动态规划来计算

计算马尔可夫迭代方法

动态规划
蒙特卡洛估计
Temporal-Difference 学习，结合以上算法

最优策略和最优值函数

在强化学习中，假设马尔可夫决策过程是有限马尔可夫决策过程，状态和动作的集合是有限的。这样的马尔可夫决策过程也是有限马尔可夫决策过程。所以在策略中一定存在一个最优策略，可以表示为 $\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)$ 策略函数。

最优策略

当 $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$ ，先保证这个策略函数 $\pi$ 然后计算当前 $\pi$ 的价值函数，当计算出 $v_{\pi}$ 函数，从而推断其 $q_{\pi}$ 函数，最后直接在 $q_{\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)$

MDP 中策略(Policy)评估

其实我们说了这么多，MDP 主要就是帮助我们做策略得到最优效果，那么 Action 就是策略。如果有这样策略，当状态 $s_t = s$ 就确定性选择某一个动作 $a_1$ 这样就和时间没有关系，只要遇到 $s_t = s$ , 那么随机性策略就是 $s_t = s$ 可能选择 $a_1$ 、 $a_2$ 或者 $a_3$ 选择不同概率。所以策略可以分为两种

确定性策略 $a = \pi(s)$
随机性策略 $\pi(a|s)$

用奖励作为策略量化后，我们如何找到一个好的策略，作成 $a_t$ 其实动作会有带来后续影响，不仅仅需要考虑当时得到 $r_{t}$ ，还需要考虑当前动作对后续奖励的影响，所以提出了回报 Return 的概念。

$U_t = R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots +$

Policy 表示在每一个状态(步骤)应该采取什么样行为,给定一个状态，就会输出一个动作概率分布
$\pi(a|s) = P(a_t = a | s_t = s)$ 根据当前状态采取什么行为的概率分布
这个概率函数是稳定的，静态的， $A_t$ 近似 $\pi(a|s)$

$V_{\pi}(s) = \mathbb{E}_{\pi}[G_t|S_t=s]$

从上面公式来看，一切建立于 $\pi$ $V_{\pi}$ 表示在 $G_t$ 在 $\pi$ 上的加权平均。对于 $\forall s \in \cal{S}$ 其实有多少状态就有多少个 $V_{\pi}(s)$

MDP 和 MRP 转换

(当已知一个马尔可夫决策过程)给定 MDP $(S,A,P,R,\gamma)$ 和 policy $\pi$ 时候就是将 MDP 转化为 MRP 问题
状态序列 $S_1,S_2$ 是马尔可夫过程 $(S,P^{\pi})$
状态和奖励序列为 $S_1,R_1,S_2,R_2$ 是马尔可夫奖励过程
$P^{\pi}(s^{\prime}|s) = \sum_{a \in A} \pi(a|s)P(s^{\prime}|s,a)$
直接通过求和，或者边缘概率去掉 a
$R^{\pi}(s) = \sum_{a \in A} \pi(a|s)R(s,a)$

为什么提出价值函数呢?

MDP 中的价值函数

价值函数: 在 MDP 过程中的价值函数也给一个定义，这里期望是由 Policy 所决定的，也就是根据 Policy 进行采样之后得到期望，从而计算其价值函数，因为我们随后动作是一个概率分布，有了动作，根据当前的状态和所采取的动作下一个状态还是一个概率分布，所以我们需要通过求当前回报期望来评价 Policy 的函数是好、还是不好。

$V_{\pi}(s) = \mathbb{E}_{\pi}[G_t|s_t = s]$

Q 函数，action-value 函数定义某一个行为可能得到某一个期望，这个期望也是 policy 函数，也就是我们在某一个状态下，采取某一个动作，最终能获得多少累计奖励的函数
$Q_{\pi}(s,a) = \mathbb{E}_{\pi}[G_t|S_t = s,A_t = a]$
价值函数和Q函数关系，也就是对 Q 函数进行边缘概率求和得到 V 函数
$V_{\pi}(s) = \sum_{a \in A} \pi(a|s)Q_{\pi}(s,a)$

Bellman Expectation Equation

主要定义当前状态和外来状态之间一个关联，对于所有
$V^{\pi}(s) = \mathbb{E}_{\pi}[R_{t+1} + \gamma V^{\pi}(s_{t+1})|s_t = s] \tag{1}$

$Q^{\pi}(s,a) = E_{\pi}[R_{t+1} + \gamma Q^{\pi}(s_{t+1},A_{t+1})|s_t = s,A_t = a] \tag{2}$

Bellman Expectation Equation for $V^{\pi}$ and $Q^{\pi}$

当前价值和未来价值之间的关系
$V_{\pi}(s) = \sum_{a \in A} \pi (a|s) Q^{\pi}(s,a) \tag{3}$
价值函数和Q函数之间一个关系

$Q_{\pi}(s,a) = R_s^a + \gamma \sum_{s^{\prime} \in S} P(s^{\prime}|s,a)V_{\pi}(s^{\prime}) \tag{4}$

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

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

2021 重启强化学习(4) 马尔可夫决策过程(MDP)

马尔可夫决策过程

马尔可夫决策过程(MDP)

马尔可夫过程(Markov Process)

马尔可夫属性(Markov Property)

马尔可夫奖励过程(MRPs)

回报与价值函数

有限扩展(horizon)

回报(Return)

定义状态价值函数

折扣因子 存在的意义

马尔可夫奖励过程贝尔曼方程

马尔可夫决策过程(MDP)

MDP 中的策略(Policy)

MP、MRP 和 MDP 之间相互关系

价值函数

状态价值函数(state-value function)

动作价值函数(action-value function)

状态价值函数和动作价值函数之间关系

贝尔曼期望方程(Bellman Expectation Equation)

MDP 求解

预测(prediction)

控制(control)

计算马尔可夫迭代方法

最优策略和最优值函数

最优策略

策略搜索

Policy Iteration

优化策略

MDP 中策略(Policy)评估

MDP 和 MRP 转换

MDP 中的价值函数

Bellman Expectation Equation

Bellman Expectation Equation for and

定义状态价值函数 $V_t(s)$

折扣因子 $\gamma$ 存在的意义

Bellman Expectation Equation for $V^{\pi}$ and $Q^{\pi}$