背景

马尔科夫决策过程是安德烈马尔科夫动作序列的扩展，它将动作结果序列的可能性可视化为有向无环图。通过无环图的一条路径，如果它满足马尔可夫性质，则称为马尔可夫链。

马尔可夫特性要求仅根据当前状态评估无环图中任意点未来状态的概率分布。

因此，马尔可夫链是理论上代表一组可能路径的随机模型。动作-结果序列是一个状态转换列表，对应于每个动作的前一个状态单独选择的动作，以及预期的后续状态最有可能导致预期结果的预期。

Andrey Markov 的工作基于 Gustav Kirchhoff 关于生成树的工作，该工作基于 Euler 最初的有向图工作。

练习

练习 3.2 分为两部分。

MDP 框架是否足以有效地代表所有目标导向的学习任务？

你能想到任何明显的例外吗？

第一个问题是主观的，因为它询问有用性，但没有定义它的含义。如果“有用”意味着 MDP 将通过随机选择每个状态的动作来提高实现目标的机会，那么除非在没有获胜的情况下或所有动作都具有相同分布的可能结果的最人为的情况下，那么 MDP 是有用。

如果“有用”意味着最佳，那么还有其他方法，它们具有额外的复杂性并且需要额外的计算资源来提高目标实现的几率。这些其他方法克服了纯 MDP 的一个或多个限制。

进步和替代品

数以百计的 MDP 和 MDP 替代品的进步包括这些。

• 目标实现不可行的逻辑检测（无获胜场景）
• 当只有关于当前状态的部分信息可用时的概率计算
• 在任何时候调用决策（实时系统中使用的连续 MDP）
• 概率是未知的，必须从过去使用简单 Q 学习的经验中学习
• 过去的经验通过将动作状态细节与从过去的动作结果序列或获取或共享的此类信息中得出的概括进行统计相关联来使用
• 在更改或不可靠应用规则的未知系统的上下文中做出的动作状态决策可用于调整模糊逻辑容器中的一组模糊规则，并在决策中利用模糊推理
• 虚张声势和欺诈检测

纸牌游戏

典型纸牌游戏的游戏玩法可以使用 MDP，因此 MDP 将是严格有用的，但不是最佳的。上述一些决策特征会更加优化，尤其是那些处理未知数和使用规则的决策特征，因为纸牌游戏有它们。

随机或解耦

两个明显的情况是（a）一个真正随机的动作结果世界，其中无论移动顺序如何，目标实现的概率都是相等的，或者（b）目标实现与参与者可以采取的行动完全脱钩的场景。在这些情况下，对于所选择的特定目标没有任何用处。

挑战

但是，从练习中最好地学习的方法是找到一个 MDP 无用的场景，并且需要上面列出的进步和替代方案之一，而不是简单地首选。如果您查看列表，最终会想到一些案例。我建议你考虑清楚，因为目标是从书中学习。

根据http://tianlinliu.com/files/notes_exercise_RL.pdf，MDP 对于多目标任务可能不可行。

相比之下，基于 EA 的方法，如 NSGA-II、NSGA-III，可以解决多目标任务。

而且，需要多个状态来预测下一步动作的任务也不适合使用 MDP。例如，当我们预测一个刚刚在聚会上遇到你的陌生人会做的下一个动作时，我们需要考虑他在过去几分钟内所做的所有行为。这将比使用 MDP 方式更合适，后者将简单地将陌生人标记为“好”人或“坏人”（或好坏之间的连续数字）。