无限期强化学习中的随机最短路径问题解析
在强化学习领域，无限期问题是一类重要的研究对象。我们将聚焦于随机最短路径（SSP）问题展开探讨，深入了解其基本概念、相关理论和算法。
基本概念
在一个系统中，系统状态的转移依赖于当前状态 (i) 以及所采取的控制 (u)。当在状态 (i) 采用控制 (u) 时，会确定转移到下一个状态 (j) 的概率 (p_{ij}(u))，同时产生相应的代价 (g(i, u, j))。
给定一个可允许策略 (\pi = {\mu_0, \mu_1, \ldots})（其中 (\mu_k(i) \in U(i)) 对所有的 (i) 和 (k) 都成立）以及一个初始状态 (i_0)，系统就构成了一个马尔可夫链。在策略 (\pi) 下生成的轨迹 ({i_0, i_1, \ldots}) 具有明确的概率分布。与初始状态 (i) 相关的总期望代价为：
[J_{\pi}(i) = \lim_{N \to \infty} E\left(\sum_{k = 0}^{N - 1} \alpha^k g(i_k, \mu_k(i_k), i_{k + 1}) \mid i_0 = i, \pi\right)]
其中，(\alpha) 在随机最短路径（SSP）问题中取值为 1，在折扣问题中小于 1。期望是针对状态 (i_1, i_2, \ldots) 的联合分布计算的，条件是 (i_0 = i) 且采用策略 (\pi)。从状态 (i) 出发的最优代价，即所有策略 (\pi) 下 (J_{\pi}(i)) 的最小值，记为 (J^*(i))。
对于静态策略 (\pi = {\mu, \mu, \ldots})，其代价函数记为 (J_{\mu}
