Box 8.1： 马尔可夫决策过程的平稳分布

整理自 链接

分析平稳分布的关键工具是 $P_{\pi }\in {\mathbb{R}}^{n\times n}$，它是给定策略 $\pi$ 下的概率转移矩阵。
如果状态被索引为 $s_1,\cdots ,s_n$，则定义 $[P_{\pi }{]}_{ij}$ 为 agent 从 $s_i$ 转换成 $s_j$ 的概率。
$P_{\pi }$ 的定义可以在 2.6 节 中找到。

关于 $P_{\pi }^k(k=1,2,3,\cdots )$

$p_{ij}^{(k)}=\text{Pr}(S_{t_k}=j|S_{t_0}=i)$： agent 从 $s_i$ 到 $s_j$ 恰好经过 $k$ 个时间步的概率。

• $t_0$ 和 $t_k$ 分别表示初始 和 第 $k$ 个时间步

$[P_{\pi }{]}_{ij}=p_{ij}^{(1)}$： $[P_{\pi }{]}_{ij}$ 表示 agent 从 $s_i$ 到 $s_j$ 恰好经过一个时间步的概率。

$[P_{\pi }^2{]}_{ij}=[P_{\pi }{P}_{\pi }{]}_{ij}=\sum _{q=1}^n[P_{\pi }{]}_{iq}[P_{\pi }{]}_{qj}=p_{ij}^{(2)}$： agent 从 $s_i$ 到 $s_j$ 恰好经过两个时间步的概率。

类似的， $[P_{\pi }^k{]}_{ij}=p_{ij}^{(k)}$： agent 从 $s_i$ 到 $s_j$ 恰好经过 $k$ 个时间步的概率。

平稳分布的定义

设 $d_0\in {\mathbb{R}}^n$ 表示初始时间步状态概率分布的向量。
例如，如果总是选择 $s$ 作为起始状态，则 $d_0(s)=1$, $d_0$ 的其他条目为 0。
设 $d_k\in {\mathbb{R}}^n$ 为表示从 $d_0$ 开始 $k$ 步后得到的概率分布的向量。然后，我们有

$d_k(s_i)=\sum _{j=1}^n{d}_0(s_j)[P_{\pi }^k{]}_{ji},i=1,2,\cdots$

这个方程表明，智能体在第 $k$ 个时间步访问 $s_i$ 的概率等于智能体恰好 在 第 $k$ 个时间步从 { s j } j = 1 n \{s_j\}_{j=1}^n {sj​}j=1n​ 过渡到 $s_i$ 的概率之和。上式的矩阵向量形式为：

$d_k^T=d_0^T{P}_{\pi }^k(8.7)$

考虑马尔可夫过程的长期行为，有 $\underset{k\to \infty }{\lim }{P}_{\pi }^k=1_n{d}_{\pi }^T(8.8)$ ！！！后面证明要用

其中 $1_n=[1,\cdots ,1{]}^T\in {\mathbb{R}}^n$
$1_n{d}_{\pi }^T$ 是一个所有行都等于 $d_{\pi }^T$ 的常数矩阵。(8.8)成立的条件将在后面讨论。将 (8.8) 代入 (8.7) 得到

$\underset{式(8.7)}{\underbrace{\underset{k\to \infty }{\lim }{d}_k^T=d_0^T\underset{k\to \infty }{\lim }{P}_{\pi }^k}}\stackrel{代入式(8.8)}{=}\underset{1}{\underbrace{d_0^T{1}_n}}{d}_{\pi }^T=d_{\pi }^T(8.9)$

式 (8.9) 表示状态分布 $d_k$ 收敛于恒定值 $d_{\pi }$，称为极限分布。
极限分布取决于 系统模型 和 策略 $\pi$。

• 它与初始分布 $d_0$ 无关。也就是说，无论 agent 从哪个状态开始，在足够长的一段时间后，智能体的概率分布总是可以用极限分布来描述。

$d_{\pi }^T=d_{\pi }^T{P}_{\pi }(8.10)$ ！！！后面证明要用

因此，$d_{\pi }$ 是与特征值 1 相关联的 $P_{\pi }$ 的左特征向量。
式 (8.10) 的解称为平稳分布。
它认为对于所有 $s\in \mathcal{S}，{\sum }_{s\in \mathcal{S}}{d}_{\pi }(s)=1$ 且 $d_{\pi }(s)>0$。【！！！没有等于 0】

如果存在一个有限的整数 $k$，使得 $[P_{\pi }{]}_{ij}^k>0$，则从状态 $s_i$ 到 状态 $s_j$ 是可达的，这意味着从 $s_i$ 开始的智能体经过有限次转移后可能到达 $s_j$。

如果两个状态 $s_i$ 和 $s_j$ 是可相互访问的，那么这两个状态就被称为通信。communicate

如果马尔可夫过程的所有状态相互通信，则称其为 不可约irreducible。
换句话说，从任意状态出发的代理可以在有限的步数内到达任何其他状态。
数学上，它表明，对于任意 $s_i$ 和 $s_j$，存在 $k\ge 1$ 使得 $[P_{\pi }^k{]}_{ij}>0(k$ 的值可以随 $i,j$ 的不同而变化)。

如果一个马尔可夫过程对所有 $i,j>0$， 存在 $k\ge 1$ 使得 $[P_{\pi }^k{]}_{ij}$，则称为正则regular。
同样地，存在 $k>1$ 使得 $P_{\pi }^k>0$，其中 > 是元素级。
因此，每个状态都可以在最多 $k$ 步内从任何其他状态到达。
正则马尔可夫过程也是不可约的，但反之则不成立。
然而，如果一个马尔可夫过程不可约且存在 $i$ 使得 $[P_{\pi }{]}_{ii}>0$，那么它也是正则的。
而且，如果 $P_{\pi }^k>0$，由于 $P_{\pi }\ge 0$，则对任意 $k^{\prime }\ge k$，有 $P_{\pi }^{k^{\prime }}>0$。由式 8.9 可知，对于每一个 $s$，$d_{\pi }(s)>0$。

可能导致唯一平稳分布的策略。
一旦策略给定，马尔可夫决策过程就成为马尔可夫过程，其长期行为是由给定的策略和系统模型共同决定的。
那么，一个重要的问题是什么样的策略可以导致规则的马尔可夫过程?
一般来说，答案是探索性策略，如 $ϵ$-贪婪策略。
这是因为探索性策略在任何状态下采取任何行动的概率都是正的。
因此，当系统模型允许时，状态可以相互通信。