马尔可夫性

• 序贯决策：智能体状态会随时间发生转移
• 马尔可夫性：未来状态只依赖于当前状态。这里涉及到对“状态”的定义。
  $$\mathbb{P}[s_{t+1}|s_1,\cdots ,s_t]=\mathbb{P}[s_{t+1}|s_t]$$
• 部分可观测：智能体不能获得环境的全部信息s，只能获得观测量o
  $$s_t\ne o_t$$
  • 部分情况可以通过观测量推测出状态，从而将部分可观测问题转化成全观测问题
• 状态转移概率${\mathcal{P}}_{s{s}^{\prime }}=\mathbb{P}[s_{t+1}=s^{\prime }|s_t=s]$
• 状态转移矩阵：包含从所有状态s到所有状态s’的转移概率。行元素之和为1

马尔可夫过程MP

一个无记忆的随机过程，一组具有马尔可夫性的状态，用$<\mathcal{S},\mathcal{P}>$表示。

马尔可夫奖励过程MRP

马尔可夫奖励过程由$<\mathcal{S},\mathcal{P},\mathcal{R},\gamma >$组成

回报和价值

回报是一条轨迹的折扣累加奖励
$$G_t=\sum _{i=0}^{\infty }{\gamma }^i{r}_{t+i+1}$$
状态s的价值是其所有轨迹的期望
$$V(s)=\mathbb{E}[G_t|s_t=s]$$

折扣因子的意义

• 方便调整奖励的重要性
• 在连续MDPs问题中可以避免无穷回报
• 更重视近期奖励，与自然界相仿
• 在有终止状态的问题中可以采用无折扣的马尔可夫奖励过程

贝尔曼方程及其变形

$$\begin{array}{rl}V(s)& =\mathbb{E}[G_t|s_t=s]\\ & =\mathbb{E}[r_{t+1}+\gamma G_{t+1}|s_t=s]\\ & =\mathbb{E}[r_{t+1}+\gamma V(s_{t+1})|s_t=s]\\ & =\mathcal{R}(s)+\gamma \sum _{s^{\prime }\in S}{\mathcal{P}}_{s{s}^{\prime }}V(s^{\prime })\end{array}$$
贝尔曼方程的矩阵形式及其变形
$$\begin{array}{rl}\mathcal{V}& =\mathcal{R}+\gamma \mathcal{P}\mathcal{V}\\ (I-\gamma \mathcal{P})\mathcal{V}& =\mathcal{R}\\ \mathcal{V}& =(I-\gamma \mathcal{P}{)}^{-1}\mathcal{R}\end{array}$$
由于需要求状态转移矩阵的逆，因此需要$O(n^3)$的计算复杂度

马尔可夫决策过程MDP

马尔可夫决策过程$\mathcal{M}=<\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma >$

• ${\mathcal{P}}_{s{s}^{\prime }}^a=\mathbb{P}[s^{\prime }=s_{t+1}|s_t=s,a_t=a]$
• ${\mathcal{R}}_s^a=\mathbb{E}[r_{t+1}|s_t=s,a_t=a]$

策略

策略是状态到动作概率分布的映射。
$$\pi (a|s)=\mathbb{P}[a_t=a|s_t=s]$$
$\pi (s)$在不确定策略中是状态s下选取各动作的概率分布，在确定性策略中则是动作a

价值

状态价值V是从状态s出发在策略$\pi$指导下的期望回报$$V_{\pi }(s)=\mathbb{E}[G_t|s_t=s]$$
动作价值Q是从状态s出发，先采取动作a，然后在策略$\pi$指导下的期望回报
$$Q_{\pi }(s,a)=\mathbb{E}[G_t|s_t=s,a_t=a]$$

贝尔曼期望方程及其推导

$$\begin{gathered} V_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a|s)Q_{\pi }(s,a) \\ {Q}_{\pi }(s,a)={\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{V}_{\pi }(s^{\prime }) \\ {V}_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a|s)({\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{V}_{\pi }(s^{\prime })) \\ {Q}_{\pi }(s,a)={\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a\sum _{a^{\prime }\in \mathcal{A}}\pi (a^{\prime }|s^{\prime })Q_{\pi }(s^{\prime },a^{\prime }) \end{gathered}$$
矩阵形式
$$\begin{gathered} {\mathcal{V}}_{\pi }={\mathcal{R}}^{\pi }+\gamma {\mathcal{P}}^{\pi }{\mathcal{V}}_{\pi } \\ {\mathcal{V}}_{\pi }=(I-\gamma {\mathcal{P}}^{\pi }{)}^{-1}{\mathcal{R}}^{\pi } \end{gathered}$$

最优价值

$$\begin{gathered} V_{\ast }=\underset{\pi }{\max }{V}_{\pi }(s) \\ {Q}_{\ast }=\underset{\pi }{\max }{Q}_{\pi }(s,a) \end{gathered}$$

最优策略

$$\begin{gathered} \pi \ge {\pi }^{\prime }\text{ if }{V}_{\pi }(s)\ge V_{\pi }^{\prime }(s),\forall s \\ {\pi }_{\ast }\ge \pi ,\forall \pi \end{gathered}$$

最优化原理

对于最优策略而言，不论初始状态和初始决策是什么，余下的决策仍是余下问题的最优策略。
$$\begin{gathered} V_{\ast }(s)=\underset{a}{\max }({\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{V}_{\ast }(s^{\prime })) \\ {Q}_{\ast }(s,a)={\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{V}_{\ast }(s^{\prime }) \\ {V}_{\ast }(s)=\underset{a}{\max }{Q}_{\ast }(s,a) \\ {Q}_{\ast }(s,a)={\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a\underset{a^{\prime }}{\max }\pi (a^{\prime }|s^{\prime })Q_{\ast }(s^{\prime },a^{\prime }) \end{gathered}$$

寻找最优策略

$$\begin{gathered} {\pi }_{\ast }(s)=\underset{a}{\mathrm{argmax}}({\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{V}_{\ast }(s^{\prime })) \\ {\pi }_{\ast }(s)=\underset{a}{\mathrm{argmax}}{Q}_{\ast }(s,a) \end{gathered}$$

模型的不同分类

• 状态空间是否连续
• 动作空间是否连续
• 确定性模型与非确定性模型
• 连续时间与离散时间
• 奖励与惩罚，最大化奖励，最小化惩罚

不同形式的回报

• 无限时域的累加奖励$G(s_0)={\sum }_{t=0}^{\infty }{\gamma }^t{r}_{t+1}$
  • 终止状态：轨迹结束，奖励也到此时刻为止
• 无限时域的平均奖励$G(s_0)={\lim }_{T\to \infty }\frac{1}{T}{\sum }_{t=1}^T{r}_t$
  • 不存在终止状态，但存在各态遍历
• 有限时域的累加奖励$G(s_0)={\sum }_{t=0}^{T-1}{\gamma }^t{r}_{t+1}$
• 有限时域的平均奖励$G(s_0)=\frac{1}{T}{\sum }_{t=1}^T{r}_t$