最优策略
对策略定义一个偏序关系，称策略 $\pi$ 优于 $\pi’$（记作 $\pi\succeq\pi’$）当且仅当
定理. 对任何一个马尔可夫决策过程
- 存在最优策略 $\pi_{\star}$ 比其它任何一个策略都不差，即 $\pi_{\star}\succeq\pi,\forall\pi$。
- 所有最优策略都达到了最优值函数，记为 $v_{\pi_{\star}}(s)=v_{\star}(s)$。
- 所有最优策略都达到了最优策略函数，记为 $q_{\pi_{\star}}(a,s)=q_{\star}(a,s)$。
最优策略可以通过最大化 $q_{\star}(s,a)$ 来实现，即
于是我们只要知道 $q_{\star}(s,a)$ 就可以马上得到最优策略。
贝尔曼方程（最优策略）
根据上一节介绍的贝尔曼方程（MDP），最优行动值函数与最优状态值函数的关系如下
又因为 $v_{\star}(s)=\max\limits_a q_{\star}(s,a)$，所以
这是最优策略下的状态值函数和行动值函数满足的贝尔曼方程，但此时由于存在最大值截断，因此不能通过之前介绍的矩阵形式来求解，即函数没有显式表达，但可以通过迭代的方法来求解（值迭代、策略迭代、Q-Learning、Sarsa等）。
值迭代算法
值迭代算法求 $v_t^{\star}$ 序列，借助于辅助 $q_t(s,a)$，其直观含义是：在状态 $s$ 执行行动 $a$，然后执行 $t-1$ 步的最优策略所产生的预期回报。
- 对所有 $s\in\mathcal S$，$v_0(s)=0$，$t=0$
- 循环开始
- $t=t+1$
- 对所有 $s\in\mathcal S$ 循环
- 对所有 $a\in\mathcal A$ 循环
- $q_t(s,a)=\mathcal R_s^a+\gamma\sum\limits_{s’\in\mathcal S}\mathcal P_{ss’}^a v_{t-1}(s’)$
- 结束循环
- $v_t(s)=\max\limits_{a\in\mathcal A}q_t(s,a)$
- 对所有 $a\in\mathcal A$ 循环
- 结束循环
- 直到 $|v_t(s)-v_{t-1}(s)|<\varepsilon$ 对所有 $s\in\mathcal S$ 成立
根据不动点理论，值迭代算法最终将收敛到最优值并且是唯一最优值，其中每一步迭代的计算复杂度是 $O(|\mathcal A||\mathcal S|^2)$，而收敛到最优值所需的迭代次数为 $\text{poly}(|\mathcal S|,|\mathcal A|,1/(1-\gamma))$。
策略迭代算法
策略迭代算法求 $\pi_t^{\star}$ 序列，是通过迭代策略实现的。
-
先给定初始策略 $\pi$，求解线性方程，计算出 $\pi$ 相应的值函数
$\displaystyle v(s)=\mathcal R_s^\pi+\gamma\sum_{s'\in\mathcal S}\mathcal P_{ss'}^av(s').$ -
基于计算出的值函数，按下式更新策略
$\displaystyle\pi(s)\leftarrow\underset{a\in\mathcal A}{\arg\max}\left[\mathcal R_s^a+\gamma\sum_{s'\in\mathcal S}\mathcal P_{ss'}^av(s')\right].$ -
不断重复上述两步骤，直到收敛
策略迭代算法最终也能收敛到最优值，且收敛到最优值所需的迭代次数不大于 $|\mathcal A|^{|\mathcal S|}$（即确定性策略的总数目）。
部分可观测的MDP
MDP刻画了行动的不确定性：事先不知道，而事后知道；一般而言，观察是确定的，并且知道行动的效果。对于部分可观测的（Partially Observable）MDP，行动和观察都是不确定的。
定义(部分可观测的MDP) 一个部分可观测的MDP是一个七元组 $\langle\mathcal S,\mathcal A, \mathcal O,\mathcal P,\mathcal R,\mathcal Z,\gamma\rangle$，其中：
- $\mathcal S$ 是状态的集合；
- $\mathcal A$ 是行动的集合；
- $\mathcal O$ 是观察的集合；
- $\mathcal P$ 是状态转移概率矩阵，$\mathcal P_{ss’}^a=\mathbb P(S_{t+1}=s’\mid S_t=s,A_t=a)$；
- $\mathcal R$ 是奖励函数，$\mathcal R_s^a=\mathbb E(R_{t+1}\mid S_t=s,A_t=a)$；
- $\mathcal Z$ 是观察函数，$\mathcal Z_{s’o}^a=\mathbb P(O_{t+1}=o\mid S_{t+1}=s’,A_t=a)$；
- $\gamma$ 是折扣率，$\gamma\in[0,1]$。
在POMDP中，历史 $H_t$ 是AOR序列，而不是MDP中的SAR序列，即
定义(信念状态) 一个信念状态 $b(h)$ 是已知历史 $h$ 的条件下状态的分布，即
令 $\mathcal B=\Pi(\mathcal S)$ 为 $\mathcal S$ 上所有状态分布的集合。给定一个POMDP模型，一个 $b\in\mathcal B$，一个 $a\in\mathcal A$ 和一个 $o\in\mathcal O$，可以计算在 $b$ 下执行 $a$ 得到 $o$ 时，环境处于状态 $s’\in\mathcal S$ 的概率
称之为状态估计函数，记为 $b’=\text{SE}(b,a,o)$。注意到
实际上是不考虑观察而得到的下一状态为 $s’$ 的概率，而 $b’(s’)$ 是考虑了观察而得出的下一状态的概率。两者的关系是：
所以若 $\mathcal Z_{s’o}^a>\mathbb P(o\mid a,b)$，即在 $s’$ 下出现 $o$ 的概率，高于出现 $o$ 的平均概率，则 $b’(s’)>\mathbb P(s’\mid a,b)$。
后记
本文内容来自中国科学技术大学《强化学习》（2022Fall）课件。
如对本文内容有任何疑问，请联系 watthu@mail.ustc.edu.cn。
