这个问题似乎直接在您在问题下方的评论中链接到的幻灯片中得到解决。

基本思想是：

• 假设您有一个完整的 MDP 模型（转换、奖励等）。

• 对于任何给定的状态，我们假设该状态的真实值反映在：

  $$V^*(s) = r + \gamma \max_{a \in A}\sum_{s' \in S} P(s' | s,a) \cdot V^*(s')$$

也就是说，状态的真正价值是我们在其中获得的奖励，加上从现在到无限远的未来采取最佳行动的预期未来奖励，减去因子$\gamma$，它抓住了未来的奖励不如现在的奖励好的想法。

• 在线性规划中，我们在一组约束条件下找到某个函数的最小值或最大值。如果函数可以采用连续值，我们可以有效地做到这一点，但如果值是离散的，问题就变成了 NP-Hard。您通常会使用Branch & Bound algorithm之类的方法来执行此操作。这些在快速实现中被广泛使用。GLPK 是一个不错的免费库。IBM 的 CPLEX 速度更快，但价格昂贵。

• 我们可以将寻找给定状态值的问题表示为：

  $$\text{minimize}_V \ V(s)$$ 受限于： $$V(s) \geq r + \gamma\sum_{s' \in S} P(s' | s,a)*V(s'),\; \forall a\in A, s \in S$$ 很明显，如果我们找到最小值$V(s)$符合此要求，则该值将使约束中的一个严格。
  • 如果您通过为每个状态编写类似于上述程序的程序来制定线性程序，然后最小化$\sum_{s\in S} V(s)$，受制于所有这些子问题的所有约束的联合，您将学习价值函数的问题简化为求解 LP。