python - 马尔可夫决策过程的数据结构

Question

我已经在 Python 中实现了简单马尔可夫决策过程维基百科的值迭代算法。为了保持特定马尔可夫过程的结构（状态、动作、转换、奖励）并对其进行迭代，我使用了以下数据结构：

1. 状态和可用于这些状态的操作的字典：

   SA = { 'state A': {' action 1', 'action 2', ..}, ...}

2. 转换概率字典：

   T = {('state A', 'action 1'): {'state B': probability}, ...}

3. 奖励字典：

   R = {('state A', 'action 1'): {'state B': reward}, ...}.

我的问题是：这是正确的方法吗？最适合 MDP 的数据结构（在 Python 中）是什么？

Answer 1

我之前在 Python 中实现了马尔可夫决策过程，发现以下代码很有用。

http://aima.cs.berkeley.edu/python/mdp.html

此代码取自Stuart Russell 和 Peter Norvig的《人工智能：现代方法》 。

Answer 2

数据结构是否合适主要取决于您对数据的处理方式。您提到您想要迭代该过程，因此为此目的优化您的数据结构。

马尔可夫过程中的转换通常由矩阵乘法建模。转移概率Pa(s1,s2)和奖励Ra(s1,s2)可以由（可能是稀疏的）矩阵描述并由Pa状态Ra索引。我认为这将有几个优点：

• 如果为此使用 numpy 数组，索引可能会比使用字典更快。
• 然后状态转换也可以通过矩阵乘法简单地描述。
• 例如轮盘选择的过程模拟将更快、更清晰地实现，因为您只需选择转换矩阵的相应列。

Answer 3

有一个名为pymdptoolbox的带有 python 的 MDP 实现。它是基于使用称为MDPToolbox的 Matlab 实现而开发的。两者都值得注意。

基本上，概率转移矩阵表示为（A×× ）数组，奖励表示为（× S）矩阵，其中和表示状态数和动作数。该包对稀疏矩阵也有一些特殊处理。SSASA