有限折扣马尔可夫决策过程最优策略求解方法的正确性验证问询
我一直在找一种不需要求解线性规划对偶问题，就能确定**有限折扣马尔可夫决策过程（MDP）**最优策略的方法。目前我自己想到了一个看起来可行的方法，但不确定自己做的证明是否正确，而且翻了不少书籍和论文都没见过类似的方法，所以想请教大家：我的思路有没有遗漏的地方？如果有的话是哪里？还有，我该怎么找到这类方法呢？
相关符号与问题定义
先明确MDP的核心符号定义：
- $S$：每阶段系统可能处于的状态集合
- $D(i)$：状态$i \in S$下的可选决策集合
- $R_i^k$：在状态$i$选择决策$k \in D(i)$获得的即时奖励
- $\beta \in (0,1)$：折扣因子
对于任意平稳策略$\pi$，其期望奖励向量定义为：
$$
v_i^{\pi} = R_i^\pi + \sum_{n=1} ^{\infty} \sum_{j \in S} \betanp_{ij}\pi(n)R_j^\pi
$$
其中$p_{ij}^\pi(n)$是从状态$i \in S$出发，经过$n$阶段转移到状态$j \in S$的概率。
已知最优期望奖励向量$w = \max_{\pi} v^\pi$是如下线性规划问题的解：
$$
\begin{equation*}
\begin{array}{ll@{}ll}
\text{minimize} & \sum\limits_{i=1}^{N} w_{i}\
\text{subject to}& w_i \geq R_{i}^k +\sum\limits_{ j \in S} \beta p_{ij}^kw_j, &i \in S, k\in D(i)\
& w_{i} \in \mathbb{R}
\end{array}
\end{equation*}
$$
记该问题的解为$w^* = g$。
我提出的求解方法
我提出的方法步骤如下：
- 对每个状态$i \in S$，选择一个决策$k \in D(i)$，使得对应的线性规划约束取等号
- 如果某个状态$i$有多个这样的决策，仅选择其中一个
- 最终得到的平稳策略（每个状态对应所选决策）即为最优策略
我的证明过程
我是这样证明这个方法正确性的：
假设$\pi$是一个最优平稳策略，根据策略评估方程，有$v^\pi = \beta P^\pi v^\pi + R\pi$，其中$P\pi = (p_{ij}^\pi)$是策略$\pi$对应的转移矩阵。由此可知，对于状态-决策对$(i, \pi(i))$，对应的线性规划约束在$w^* = v^\pi$处取等号，也就是说每个状态$i \in S$至少存在一个满足条件的决策$k \in D(i)$。
进一步，如果存在某个状态$l_0 \in S$，$\pi(l_0)=k_1$，同时存在另一个决策$k_2 \in D(l_0)$（$k_1 \neq k_2$）满足：
$$
w_{l_0}^{} = R_{l_0}^{k_2} +\sum\limits_{ j \in S} \beta p_{l_0j}{k_2}w_j
$$
那么我们可以构造一个新的平稳策略$\delta$：当$i \neq l_0$时$\delta(i)=\pi(i)$，当$i=l_0$时$\delta(l_0)=k_2$。此时对于所有状态-决策对$(i, \delta(i))$，都有：
$$
w^{} = \beta P ^\delta w^{} + R^\delta
$$
这意味着$w^* = v^\delta$，即$\delta$也是一个最优策略——这种情况下存在多个最优策略。
我的疑问
我觉得这个证明是对的，但找了很久都没在文献里看到类似方法，所以想确认：我的思路有没有遗漏的地方？如果有，具体是什么？如果我的方法不对，那有没有其他不需要求解线性规划对偶问题的最优策略求解方法？
提前谢谢大家的解答！
备注：内容来源于stack exchange，提问作者chitranjan_iyengar_01
