马尔可夫决策过程
Published:
以经典模型展现马尔可夫决策过程的求解，主要包括：
连续状态马尔可夫决策过程：线性二次最优控制
离散状态马尔可夫决策过程：最优停止理论
Markov Decision Model
马尔可夫决策模型（Markov Decision Model，MDP）,可以看作引入动作$a$到状态空间$s$的Markov过程。
也即转移概率 $P(s_{t+1} \vert s_t,a_t)$ 满足Markov性质，仅依赖于当前状态而不依赖于历史状态。
Linear Quadratic Control
我们关于与一个经典的连续MDP问题：线性二次控制模型，类似于 Kalman滤波 ，该模型在机器人控制等领域非常重要。
可以看作Kalman滤波这个隐Markov过程在MDP问题中对应的形式，给定上一时刻的状态和动作$s_t,a_t$， 下一时刻的状态$s_{t+1}$可以用高斯分布建模, 而每次决策对应的代价$r(s,a)$用二次型表示，最优的决策策略是找到最佳的策略决定每一时刻的$a_t$，使得总代价最小，
\[\begin{align} s_{t+1} &= B_t s_t + C_t a_t + W_t, W_t \sim \mathcal{N}(0,\Sigma_t) \\ r_{t}(s_t,a_t) &= s_t^T Q_t s_t + a_t^T R_t a_t \\ r_N(s_N) &= s_N^T Q_N s_N \text{ ,Terminal Reward} \end{align}\]假定该MDP过程存在终止状态，可以通过终止状态从后往前使用动态规划（Dynamic Programming，DP）的思想进行求解。
假设已知下一时刻状态的代价，$V_{t+1}(s) = E[r_{t+1}(s)] = s^T \Sigma s$, 想要求解该时刻的最优决策，
\[\begin{align} V_{t}(s_t) &= \min_a E[r_t(s_t,a_t)] \\ &= \min_a r_t(s_t,a_t) + E[r_{t+1}(s_{t+1})] \\ &= \min_a s_t^T Q_t s_t + a_t^T R_t a_t +(B_t s_t + C_t a_t + W_t)^T \Sigma_{t+1} (B_t s_t + C_t a_t + W_t) \\ &= \min_a a_t^T(R_t+C_t^T \Sigma_{t+1} C_t) a_t + 2a_t^T C_t^T \Sigma_{t+1} B_t s_t + s_t^T (Q_t+B_t^T \Sigma_{t+1} B_t) s_t+E[W_t^T \Sigma_{t+1} W_t] \\ &= -s_t^T B_t^T \Sigma_{t+1} C_t (R_t+C_t^T \Sigma_{t+1} C_t)^{-1}C_t^T \Sigma_{t+1} B_t s_t + s_t^T (Q_t+B_t^T \Sigma_{t+1} B_t) s_t+E[W_t^T \Sigma_{t+1}W_t]\\ \text{With } a_t &= -(R_t+C_t^T \Sigma_{t+1} C_t)^{-1} C_t^T \Sigma_{t+1} B_t s_t \\ \end{align}\]使用常用的 Shermann–Morrison–Woodbury 公式进行化简，
\[\begin{align} V_t(s_t) &= -s_t^T B_t^T \Sigma_{t+1} C_t (R_t+C_t^T \Sigma_{t+1} C_t)^{-1}C_t^T \Sigma_{t+1} B_t s_t + s_t^T (Q_t+B_t^T \Sigma_{t+1} B_t) s_t+E[W_t^T \Sigma_{t+1}W_t]\\ &= s_t^T B_t^T (\Sigma_{t+1}- \Sigma_{t+1} C_t (R_t+C_t^T \Sigma_{t+1} C_t)^{-1}C_t^T \Sigma_{t+1} ) B_t s_t + s_t^T Q_ts_t+E[W_t^T \Sigma_{t+1}W_t] \\ &=s_t^T B_t^T (\Sigma_{t+1}^{-1} + C_t R_t^{-1} C_t^T) B_t s_t + s_t^T Q_ts_t+E[W_t^T \Sigma_{t+1}W_t] \\ \end{align}\]由于关于$W_t$的方差项为常数，在递推更新的过程中可以忽略，递推中只要更新的变量为和期望代价相关的参数$\Sigma$和最优的决策$a$ ，
\[\begin{align} a_t &= K_t s_t \\ \Sigma_t &= B_t^T \Sigma_{t+1} (B_t - C_t K_t) +Q_t \\ \text{With } K_t &= -(R_t+C_t^T \Sigma_{t+1} C_t)^{-1} C_t^T \Sigma_{t+1 } B_t \end{align}\]上式和Kalman滤波的结果也有相似性。
Optimal Stopping Theory
本节关注于另外一个经典的模型，最佳停止问题
假设一个面试官，可以依次观测到$N$个面试者，其需要选择一个面试者，但一经选择，就不能选择后续的任何一个面试者，需要求解面试官的最佳面试策略。
下面我们将其转化为一个离散MDP问题并且进行求解。
定义状态空间为0-1状态空间，状态$s_n=1$表示第$n$个面试者是前$n$个面试者里面最佳的面试者，$s_n=0$表示其不是前$n$个面试者里面最佳的面试者，问题需要最大化选中所有$N$个面试者中最优的概率。而动作空间为选择继续或者停止，据此可以写出该MDP问题的转移方程。
利用强化学习中的符号定义$Q(s,a),V(s)$,
\[\begin{align} Q(\text{Stop} \vert s_t=0) &= 0 \\ Q(\text{Stop} \vert s_t=1) &= \frac{t}{N} \\ Q( \text{Continue} \vert s_t=0) &= \frac{1}{t+1} V(s_{t+1} = 1) + \frac{t}{t+1} V(s_{t+1} =0)\\ Q( \text{Continue} \vert s_t=1) &= \frac{1}{t+1} V(s_{t+1} = 1) + \frac{t}{t+1} V(s_{t+1} =0)\\ \end{align}\]根据$Q(s,a),V(s)$的关系，
\[\begin{align} V_t(0) &= \max (0, \frac{1}{t+1} V_{t+1} (1) + \frac{t}{t+1} V_{t+1} (0)) \\ &=\frac{1}{t+1} V_{t+1} (1) + \frac{t}{t+1} V_{t+1} (0) \\ V_t(1) &= \max (\frac{t}{N} , \frac{1}{t+1} V_{t+1} (1) + \frac{t}{t+1} V_{t+1} (0)) \\ &= \max (\frac{t}{N} , V_t(0)) \\ \end{align}\]可见，当状态为0的时候，最优的策略一定是继续；而当状态为1的时候，最优的策略取决于 $ \max (\frac{t}{N} , V_t(0))$的具体取值。
理论上根据上述转移方程，已经可以从后向前递推得到最终每个状态的决策，但其中的$\max$操作不一定很好化简，但利用该问题的特殊性质，可以得到更佳简洁的策略的表达形式。
由于遇到状态0的最佳策略一定是继续，因此我们只需要关注遇到状态1的最佳策略。
从后往前递推的过程中，一定会有某次遇到状态1且此时的最佳策略是继续而非停止，也即该状态满足，
\[\begin{align} V_t(1) &= V_t(0) \\ \text{Or }\frac{t}{N} &\le V_t(0) \end{align}\]巧妙的是我们可以发现，对于该状态之前的所有状态，遇到状态1的最佳策略都为继续，该证明可以递推进行，例如对于$t-1$时刻，
\[\begin{align} V_{t-1}(0) &= \frac{1}{t} V_{t} (1) + \frac{t-1}{t} V_{t} (0) \\ &= V_t(0) \\ &\ge \frac{t}{N}\\ &\ge \frac{t-1}{N} \\ \end{align}\]也即递推关系可以得到，
\[\begin{align} V_{t-1}(1) &= V_{t-1}(0) \\ \text{Or }\frac{t-1}{N} &\le V_t(0) \end{align}\]因此在该时间点之前的遇到状态1的所有最佳策略都为继续，而根据假设该时间点之后所有遇到状态1的最佳策略都为停止。
也即，该问题的最佳策略可以简单地表示为：首先观察前$t$个面试者，观察之后选择后面的所有面试者中当前最优的那一个，该理论就是著名的最优停止理论（Optimal Stopping Theory）
根据最优停止理论，选择该问题的最佳策略转化为选取该问题中的$t$，也即选定观察多少个面试者。
由于根据上述理论，在该分界点之后的所有遇到状态1的最佳策略都为停止，因此在分界点后转移方程可以被化简为，
\[\begin{align} V_t(0) &= \max (0, \frac{1}{t+1} V_{t+1} (1) + \frac{t}{t+1} V_{t+1} (0)) \\ &=\frac{1}{t+1} V_{t+1} (1) + \frac{t}{t+1} V_{t+1} (0) \\ V_t(1) &= \max (\frac{t}{N} , \frac{1}{t+1} V_{t+1} (1) + \frac{t}{t+1} V_{t+1} (0)) \\ &= \max (\frac{t}{N} , V_t(0)) \\ &= \frac{t}{N}, \text{By Optimal Stopping Theory} \end{align}\]简单经过归纳法可以得到, \(\begin{align} V_t(0) &= \frac{t}{N} (\frac{1}{t+1} +...+\frac{1}{N+1}) \end{align}\)
在分界点$t$处遇到状态1的最佳策略为继续，也即
\[\begin{align} V_t(1) &= \max(\frac{t}{N},V_t(0)) = V_t(0) \\ \text{Then } V_t(0) &\ge \frac{t}{N}, \frac{1}{t+1} +...+\frac{1}{N+1} \ge 1 \end{align}\]而之后的所有遇到状态1的最佳策略都为停止，也即对于这些时刻来说，
\[\begin{align} V_t(1) &= \max(\frac{t}{N},V_t(0)) = \frac{t}{N} \\ \text{Then } V_t(0) &\le \frac{t}{N}, \frac{1}{t+1} +...+\frac{1}{N+1} \le 1 \end{align}\]根据上述推理的正反两面，可以知道最优的$t$可以被表示为，
\[\begin{align} &\text{maximize } t \\ &\text{s.t.} \frac{1}{t+1} +...+\frac{1}{N+1} \ge 1 \end{align}\]当$N$趋近于无穷大的时候，根据调和级数的性质可以得到，
\[\begin{align} \log \frac{N}{t} &= 1 \\ \frac{t}{N} &= \frac{1}{e} \end{align}\]也即正好等价于观测前$\frac{1}{e}$比例的面试者，之后选择一个当前最优的面试者。