马尔科夫决策过程解法(Solution to MDP)

2018-08-24 本文已影响81人海街diary

1. 马尔科夫决策过程

马尔科夫决策过程(Markov Decision Process) 是一个由4个元素组成的元祖 $(S, A, P, R)$ 组成。

$S$ 为状态; $A$ 为动作; $P$ 为概率转移，指定 $Pr{(x^\prime|x, a)}$ ; R为奖励函数，指定 $R(s)$ ；也可以指定为 $R(s,a)$ 。

马尔科夫决策过程

很容易定义状态函数 $V^\pi(s)$ 为折扣奖励的累计期望，折扣比例 $0 \leq\gamma < 1$ 。
$V^\pi(s)= E[\sum_{t=0}^{\infty} \gamma^t R(s_t) | s_0=s, a_t=\pi(s_t)]$

从后向传播的观点——当前的价值函数为及时奖励和未来奖励的期望之和，有：
$V^\pi(s)= R(s) + \gamma\sum_{s^\prime}\Pr(s^\prime|s, a)V^\pi(s^\prime)$

写成矩阵的形式，求解 $V(s)$ 即为求解线性方程组：
$\begin{align*} V^\pi(s) &= R(s) + \gamma \Pr(s^\prime|s, a)V^\pi(s^\prime) \\ (I_{|S|} - \gamma \Pr(s^\prime|s,a)) V^{\pi}(s) &= R(s) \end{align*}$

最优的价值函数 $V^\star(s) = \max_\pi V^\pi(s)$ ，满足：
$V^\star(s)= R(s) + \gamma\max_a\sum_{s^\prime}\Pr(s^\prime|s, a)V^\star(s^\prime)$

2. 价值迭代算法

价值迭代的算法如下：

初始化 $\hat{V}(s)=0$

不断迭代更新
$\hat{V}(s)\leftarrow R(s)+\gamma \max_a\sum_{s^\prime}\Pr(s^\prime|s, a)V^\pi(s^\prime) \quad \forall s\in S$

理解价值迭代，需要理解 $Bellman$ 最优算子是个压缩映射。定义 $Bellman$ 最优算子 $B: \mathbb{R}^{S} \rightarrow \mathbb{R}^{S}$ 如下，
$B\, \hat{V}(s) = R(s) + \gamma \max_a\sum_{s^\prime}\Pr(s^\prime|s, a)V^\pi(s^\prime)$

由于 $B$ 是压缩映射，存在唯一的不动点 $V^\star(s)$ 。这就是上述价值迭代算法的收敛原理，对 $V(s)$ 进行多次迭代后，会收敛到最优价值函数 $V^\star(s)$ 。

压缩映射具有如下性质: 对任意 $V_1(s)$ 和 $V_2(s)$ ，有
$\max_{s \in S}{| B\, V_1(s) - B\, V_2(s)| \leq \gamma \max_{s \in S}|V_1(s)-V_2(s)|}$

上述性质说明了这样一个事情: 对于 $V^k(s)$ 进行迭代后，更新后的 $V^{k+1}(s) = B\,V^{k}(s)$ 与原来的 $V^k(s)$ ，最大误差不超过 $\gamma \max_{s \in S}|V_1(s)-V_2(s)| < \max_{s \in S}|V_1(s)-V_2(s)|$ （因为 $\gamma < 1$ ）。也就是每次迭代后，误差以比例 $\gamma$ 减小。

利用上面压缩性质，可以证明价值迭代算法的收敛性。(下面方框中的内容，可以暂时跳过)

首先，假设马尔科夫决策过程中的奖励 $R$ 是有界的，即 $R\leq R_{max}$ 。根据等比数列性质，那么 $V(s)$ 也是有上界的。
$V(s)= \sum_{t=0}^{\infty} \gamma^t R(s_t) \leq \sum_{t=0}^{\infty} \gamma^t R_{max} = \frac{R_{max}}{1-\gamma}$
那么，任意一次迭代过程中的值 $V^k(s)$ 与 $V^{\star}(s)$ 之间的差最大为 $\frac{R_{max}}{1-\gamma}$ 。利用压缩性质有，
$\max_{s \in S}|V^0(s) - V^{\star}(s) | \leq \gamma \frac{R_{max}}{1-\gamma}$
对初值 $V^0(s)$ 进行一次迭代后，
$\begin{align*} \max_{s \in S}|V^1(s) - V^\star(s)| &\leq \max_{s \in S}|B\, V^0(s) - V^\star(s)| \\ &\leq \gamma \max_{s \in S} | V^0(s) - V^{\star}(s)| (压缩性质) \\ &\leq \gamma^2 \frac{R_{max}}{1-\gamma} (最大误差) \end{align*}$
可以看到，每次迭代后，最大误差以比例 $\gamma < 1$ 减小。

3. 策略迭代算法

策略迭代算法如下：

初始化 $\hat{V}(s)=0$ .

策略评估：(一般而言，下式中 $\pi(s,a)$ 为固定策略由于策略更新)
$V^{(k+1)}(s) \leftarrow \sum_{a \in A} \pi(s, a) \sum_{s^\prime \in S}\Pr(s^\prime | s, a)(r(s,a) + V^{k}(s^\prime)) \quad \forall s \in S$

策略更新：
$\pi(s) \leftarrow \arg \max_{a} (R(s) + \gamma \sum_{s^\prime \in S} \Pr(s^\prime|s, a) V^\pi(s)) \quad \forall s \in S$

如果 $\pi(s)$ 与上次迭代相比没有变化，则停止；否则，转回2。

更多关于策略迭代的分析，请看这里。

4. 线性规划算法

线性规划算法如下：

$\begin{align*} minimize \quad &\sum_s V(s) \\ subject \,\,\, to \quad & V(s) \ge R(s) + \gamma \sum_{s^\prime \in S} \Pr(s^\prime | s, a) V(s^\prime) \quad \quad \forall s \in S, a \in A \end{align*}$

理解如下，假设不等式约束以等式成立，那么满足 $Bellman$ 最优算子；如果存在某个 $V(s)$ 使得不等式约束存在严格大于，优化目标一定会使得这个 $V(s)$ 继续减小，直至不等式约束以等式存在。所以最终的目标，使得 $V(s)$ 满足 $Bellman$ 方程最优解。

5. 附录

$Bellman$ 最优算子收缩性质证明

$\begin{align*} |B V_1(s) - B V_2(s)| &= |R(s) + \gamma\max_a\sum_{s^\prime}\Pr(s'|s,a) V_1(s^\prime)- R(s) - \gamma\max_a \sum_{s^\prime}\Pr({s^\prime}|s, a)V_2(s^\prime) | \\ &= \gamma|\max_a\sum_{s^\prime}[\Pr(s^\prime|s,a)(V_1(s^\prime) - V_2(s^\prime))]| \\ &\leq \gamma \max_s| V_1(s) - V_2(s)| \quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \forall s \in S \end{align*}$
Thus,
$\max_s|BV_1(s) - BV_2(s)| \leq \gamma \max_s| V_1(s) - V_2(s)|$