MDP（马尔可夫决策过程）

给定当前状态\(^t\boldsymbol s\)，未来\(^{t+1}\boldsymbol s\)和过去\(^{t-1}\boldsymbol s\)是独立的。对于MDP，行动\(^{t}\boldsymbol a\)的结果\(^{t+1}\boldsymbol s\)仅取决于当前状态\(^t\boldsymbol s\)，而和过去没关系，这种特性有时被称为“无记忆性”。
这个过程可以概括为五个部分：

• \(\mathcal S\)：状态集，\(\mathcal S=\{\boldsymbol s_0,\boldsymbol s_1,\cdots\}\)；
• \(\mathcal A\)：动作集，\(\mathcal A=\{\boldsymbol a_0,\boldsymbol a_1,\cdots\}\)，在状态为\(\boldsymbol s\)时执行动作\(\boldsymbol a\)，\(\boldsymbol a=\pi(\boldsymbol s)\)；
• \(P_{\boldsymbol s,\boldsymbol a}\)：状态转换分布，\(\sum_{\boldsymbol s^\prime\in \mathcal S}P_{\boldsymbol s,\boldsymbol a}(\boldsymbol s^\prime)=1\ ,\ P_{\boldsymbol s,\boldsymbol a}(\boldsymbol s^\prime)\geq0\ ,\ \boldsymbol s^\prime\sim P_{\boldsymbol s,\boldsymbol a}\)，其描述了在状态\(\boldsymbol s\)下执行动作\(\boldsymbol a\)后进入状态\(\boldsymbol s^\prime\)的概率，如果这个概率为\(\frac{0}{0}\)则可以通过一个默认的概率分布估计一个值；
• \(\Gamma\)：\(\Gamma\in[0,1)\)，控制随着时间推移，奖励会越来越少，这个值是人为设置的；
• \(R\)：奖励函数，进行一系列动作\(\boldsymbol a_j\ ,\quad j=0,1,\cdots\) 的总奖励为\(\sum_{j}R(\boldsymbol s_j)\Gamma^j\)（这个上标是乘方），这个总奖励也是随机变量；依据实际应用中的需求设置奖励函数；

MDP试图求解\(\max \mathbb E\big[\sum_{j}R(\boldsymbol s_j)\Gamma^j\big]\)，即奖励最大化。

贝尔曼方程

当前状态\(\boldsymbol s\)的价值\(V(s)\)等于当前状态的奖励\(R(\boldsymbol s)\)和在此之后可能会获得的奖励之和（递归的，而且是无穷递归），即：

\[V(\boldsymbol s)=R(\boldsymbol s)+\Gamma \sum_{\boldsymbol s^\prime\in \mathcal S}P_{\boldsymbol s\to \boldsymbol s^\prime}V(\boldsymbol s^\prime) \]

\(\boldsymbol s\)状态下的奖励最大（最优）的动作为：

\[\boldsymbol a^*=\pi^*(\boldsymbol s)=\mathop{\arg\max}\limits_\boldsymbol a\sum_{s^\prime\in \mathcal S}P_{\boldsymbol s,\boldsymbol a}(s^\prime)V(s^\prime)=\mathop{\arg\max}\limits_\boldsymbol a\mathbb E_{s^\prime\sim P_{\boldsymbol s,\boldsymbol a}}\big[V^*(s^\prime)\big] \]

一般\(\phi(s)\)（是升维用的函数）输出\(\boldsymbol s\)。\(\boldsymbol a^*,\boldsymbol a\in \mathcal A\)，\(\boldsymbol a^*\)是从\(\boldsymbol a\)值中被挑选作为输出的一个。\(V(\boldsymbol s)=\boldsymbol{\theta}^\intercal\phi(\boldsymbol s)\)。

拟合

训练时，先随机执行动作\(\boldsymbol a\)，以此获取“经验”，这些“经验”包括统计出\(P_{\boldsymbol s,\boldsymbol a}\)的值等。然后从下面挑一种迭代方式进行拟合：

• 值迭代：
  令\(V_s=0\)；迭代更新\(V_s^{new}=R(s)+\max_\boldsymbol a\Gamma\sum_{s^\prime\in \mathcal S}P_{\boldsymbol s,\boldsymbol a}(s^\prime)V(s^\prime)\)直至收敛，当收敛时将有\(V_s\approx V^*(s)\)。这里把\(V\)当值来操作了，直接操作\(V\)。
  
  function valueIteration(\(\mathcal A\), \(\mathcal S\)){
  ?var \(V\) = zeros(\(\mathcal S\).length());??/* 初始化为0 */
  ?do{
  ??foreach(\(\boldsymbol s\) in \(\mathcal S\)){
  ???\(V_\boldsymbol s\) = \(\displaystyle R(s)+\max_{\boldsymbol a\in \mathcal A}\Gamma\sum_{s^\prime\in \mathcal S}P_{\boldsymbol s,\boldsymbol a}(s^\prime)\ V_{s^\prime}\);
  ??}
  ?}?while?(isCovergenced(\(V\)));
  ?return \(V\);
  }
• 策略迭代：
  随机化\(\pi\)；迭代更新\(\pi(\boldsymbol s)=\displaystyle\mathop{\arg\max}\limits_\boldsymbol a\sum_{s^\prime\in \mathcal S}P_{\boldsymbol s,\boldsymbol a}(s^\prime)V^\pi(s^\prime)\)直至收敛（这里每一步假设\(\pi\)就是\(\pi^*\)，实际上当收敛时这个假设已经基本成立）。
  
  function policyIteration(\(\mathcal A\), \(\mathcal S\)){
  ?var \(\pi\) = new π(randoms(\(\mathcal S\).length()));??/* 这个\(\pi\)是可以执行的 */
  ?do{
  ??foreach(\(\boldsymbol s\) in \(\mathcal S\)){
  ???/* 声明决策函数为\(\pi\)时的表达式，策略评估 */
  ???lambda \(V^\pi(s)\) = \(\displaystyle R(s)+\Gamma\sum_{s^\prime\in \mathcal S}P_{\boldsymbol s,\boldsymbol a}(s^\prime)\ V^\pi(s^\prime)\);
  ???/* 策略改进，哪个动作可以达到价值\(V\)最大，哪个就是最优策略，于是求了个期望 */
  ???\(\pi(\boldsymbol s)\) = \(\displaystyle\mathop{\arg\max}\limits_{\boldsymbol a\in \mathcal A}\sum_{s^\prime\in \mathcal S}P_{\boldsymbol s,\boldsymbol a}(s^\prime)\ V^\pi(s^\prime)\);
  ??}
  ?}?while?(isCovergenced(\(\pi\)));
  ?return \(\pi\);
  }

可以用指定最大递归层数等方式来解决无穷递归难以实现的问题。

连续的状态

\(\mathcal S\)可能是无限集。对于随机\(m\)个状态，先计算近似值\(y_i\)，然后用监督学习让\(V\)逼近\(y\)。\(\mathbb E_{\boldsymbol s^\prime\sim P_{\boldsymbol s,\boldsymbol a}}[V^*(\boldsymbol s)]\approx V^*(\mathbb E[\boldsymbol s^\prime])=V^*(f(\boldsymbol s,\boldsymbol a))\)，这里\(\boldsymbol s^\prime=f(\boldsymbol s,\boldsymbol a)+\varepsilon\)，\(\varepsilon\)是高斯噪声，这些噪声淹没在期望中。

function valueIteration(\(\boldsymbol\theta\), \(\mathcal A\), \(\mathcal S_全\), \(m\)){
?var \(\mathcal S\) = new RandomSubSet(\(\mathcal S_全\));??/* 随机选取\(m\)个状态 */
?do{
??var \(\mathcal y\) = new List(\(m\));
??foreach(\(i\) in \(\mathcal S\).sample(\(m\))){
???var \(\boldsymbol s\) = \(\mathcal S_i\);
???var \(q\) = new Q();
???foreach(\(\boldsymbol a\) in \(\mathcal A\)){
????var \(\mathcal S^\prime\) = filter(\(\mathcal S\), \(P_{\boldsymbol s,\boldsymbol a}\));??/* \(\forall \boldsymbol s^\prime \in \mathcal S^\prime,\boldsymbol {s}^\prime\sim P_{\boldsymbol s^i,\boldsymbol a}\) */
????var \(k\) = \(\mathcal S^\prime\).length();
????/* 故\(q(\boldsymbol a)\)是\(R(\boldsymbol s)+\Gamma\mathbb E_{\boldsymbol s^\prime\sim P_{\boldsymbol s,\boldsymbol a}}\big[V(\boldsymbol s^\prime)\big]\)的估计 */
????\(q(\boldsymbol a)\)=\(\displaystyle R(\boldsymbol s)+\frac{\Gamma}{k}\sum_{\boldsymbol s^\prime \in\mathcal S}V(\boldsymbol s^\prime)\);
???}
???/* \(\mathcal y_i\)是\(R(\boldsymbol s)+\Gamma\displaystyle\max_{\boldsymbol a\in\mathcal A}\mathbb E_{\boldsymbol s^\prime\sim P_{\boldsymbol s,\boldsymbol a}}\big[V(\boldsymbol s^\prime)\big]\)的近似，最后\(V(\boldsymbol s)\approx \mathcal y_i\) */
???\(\mathcal y_i\) = \(\displaystyle\max_{\boldsymbol a\in\mathcal A}q(\boldsymbol a)\);
??}
??/* 在最初的迭代算法（在离散状态下）中，我们根据\(V(\boldsymbol s):=\mathcal y_i\)更新值函数\(V\)。再使用监督学习（线性回归）来实现\(V(\boldsymbol s)\approx \mathcal y_i\)。 */
??\(\boldsymbol\theta\) = \(\displaystyle\mathop{\arg\min}\limits_{\boldsymbol\theta}\frac{1}{2}\sum_{i=1}^{m}\Big(\boldsymbol\theta^\intercal\phi(\boldsymbol s_i)-\mathcal y_i\Big)\);
?}?while?(isCovergenced(\(\boldsymbol \theta\)));
}

转载声明