随机最优控制理论2: 不确定的系统
前面的一篇文章讲述了如何在确定性的问题下进行动态规划，现在我们把确定性的弄到不确定的体系里面。首先看一下马尔科夫链。
Markov Chain
定义1. 离散时间的马尔科夫链
设\(\mathcal{X}\)为一可数集，表示所有可能的状态集合，\(\lambda=(\lambda_x:x\in\mathcal{X})\)为一初始概率分布，也就是 \[ \sum_{x\in\mathcal{X}}\lambda_x=1 \] 对于任意两个状态\(x,y\in\mathcal{X}\)，我们定义转移矩阵\(P\), 其中\(P_{xy}\)代表从状态\(x\)转移到状态\(y\)的概率，也就是 \[ \sum_{y\in\mathcal{X}}P_{xy} = 1 \] 一个离散时间的马尔科夫链为一个时间的随机变量\(X=X_t\in\mathcal{X}, t\in \mathbb{Z}^+\), 在\(t=0\)有初始分布: \[ \mathbb{P}(X_0=x_0) = \lambda_{x_0} \] 并且满足 \[ \begin{aligned} \mathbb{P}(X_{t+1}=x_{t+1}|X_t = x_t,...,X_0=x_0) &= \mathbb{P}(X_{t+1}=x_{t+1}|X_t = x_t) \\ &=P_{x_tx_{t+1}} \end{aligned} \] 上面的性质称为马尔可夫性，也就一个马尔科夫链的未来\(X_{t+1}\)在当前\(X_t\)，与过去\((X_{1},...x_{t-1})\)条件独立，换句话说就是未来每个状态的概率分布只由当前\(X_t=x_t\)决定。
根据上面这个性质，我们可以找出一个生成马尔科夫链的方法：
定理1. 设 \(\mathcal{U}=U_t\in[0,1]\) 为均匀分布的随机变量, \(X_0\in\mathcal{X}\)为一个随机变量。通过函数 \(f:\mathcal{X}\times \mathcal{U}\rightarrow \mathcal{X}\) 递推生成的随机变量\(X_t\) \[ X_{t+1}=f(X_t,U_t) \] 是一个马尔科夫链.
Markov Decision Process
现在我们来把动态规划问题带进马尔科夫链中。如果一个动态规划问题中，其状态的演化是一个马尔科夫链，那么我们就称之为Markov Decision Process (MDP).
定义2. Markov Decision Process
考虑一个离散的时间过程 \(t=0,1,...T\) ，有可数的状态集合 \(x\in\mathcal{X}\) ，操作集合 \(a\in\mathcal{A}\) 以及在给定状态 \(x\) 后采取操作 \(a\) 的回报 \(r(x,a)\). 如果从动态规划函数 \(f\) 是随机的，并且满足马尔可夫性： \[ X_{t+1}=f(X_t,a_t;U_t)\equiv f(X_t,a_t) \] 我们称这个过程为Markov Decision Process。其中 \(U_t \in [0,1]\) 是一个均匀分布的随机过程。
与确定性的系统类似，我们的动态规划目标仍然是找到一个策略 \(\pi\), 使得效用函数\(R(x_0,\pi)\) 达到最大。但由于 \(f\) 的随机性，我们在定义效用函数的时候，就只能取其期望值： \[ \begin{equation} V(X_0)=\left\{ \begin{aligned} \text{maximize }& R(X_0,\Pi) = \mathbb{E}\left[ r(X_T) + \sum_{i=0}^{T-1}r(X_i,\pi_i) \right]\\ \text{over }& \Pi \in \mathcal{P} \end{aligned} \right. \end{equation} \] 接下来我们来看其对应的Bellman Equation。仿照确定的体系，考虑从终止时间 \(T\) 往前数 \(\tau\) 个时间，考虑从\(t=T-\tau\)以后的未来回报： \[ \begin{equation} \begin{aligned} R(X_{T-\tau},\pi) &= \mathbb{E}_{\tau}\left[ r(X_T) + \sum_{i=T-\tau}^{T-1}r(X_i,\pi_i) \right] \end{aligned} \end{equation} \] 这一段时间的未来回报，也对应了一个动态规划 \(V(\tau,X_{T-\tau})\) : \[ \begin{aligned} V(\tau,X_{T-\tau}) &= \max_{\pi} R(X_{T-\tau}, \pi) \\ &=\max_{\pi} \mathbb{E}_{\tau}\left[ r(X_T) + \sum_{i=T-(\tau-1)}^{T-1}r(X_i,\pi_i) + r(X_\tau,\pi_\tau) \right] \\ &=\max_{\pi}\left\{ \mathbb{E}_{\tau}\left[ r(X_T) + \sum_{i=T-(\tau-1)}^{T-1}r(X_i,\pi_i)\right] + r(X_\tau,\pi_\tau) \right\}\\ &=\max_{\pi}\left\{ \mathbb{E}_{\tau}\left[ \max_\pi\left\{ \mathbb{E}_{\tau-1}\left[ r(X_T) + \sum_{i=T-(\tau-1)}^{T-1}r(X_i,\pi_i)\right]\right\}\right] + r(X_\tau,\pi_\tau) \right\}\\ &= \max_{\pi}\left\{ \mathbb{E}_{\tau}\left[V_{\tau-1}(X_{\tau-1}) \right] + r(X_\tau,\pi_\tau)\right\} \\ &= \max_{\pi}\left\{ \mathbb{E}_{\tau}\left[V_{\tau-1}(f(X_{\tau},\pi_\tau)) \right] + r(X_\tau,\pi_\tau)\right\} \end{aligned} \]
