马尔科夫决策过程的数据结构

Question

在Python中实现了简单Markov决策过程Wikipedia的值迭代算法。为了保持特定Markov过程的结构（状态、操作、转换、回报）并在其上迭代，我使用了以下数据结构：

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

数据结构是否合适主要取决于您对数据的处理方式。你提到你想在这个过程中迭代，所以为此优化你的数据结构。

马尔可夫过程中的跃迁通常用矩阵乘法来模拟。过渡概率Pa(s1,s2)和回报Ra(s1,s2)可以用（潜在稀疏的）矩阵Pa和Ra来描述，矩阵由状态索引。我认为这有几个好处：

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

Answer 2

有一个用python实现的MDP称为pymdptoolbox。它是在用Matlab实现MDPToolbox的基础上开发的。两者都值得注意。

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

Answer 3

我以前在Python中实现过Markov决策过程，发现下面的代码很有用。

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

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