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

Question

我已经在Python中为简单的Markov决策过程Wikipedia实现了值迭代算法.为了保持特定马尔可夫过程的结构(状态,动作,转换,奖励)并迭代它,我使用了以下数据结构:

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中实现了Markov Decision Processes,发现以下代码很有用.

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

此代码取自Stuart Russell和Peter Norvig的人工智能:现代方法.

Answer 2

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

马尔可夫过程中的过渡通常通过矩阵乘法建模.转变概率Pa(s1,s2)和奖励Ra(s1,s2)可以通过(潜在稀疏)矩阵来描述Pa和Ra编入索引的状态.我认为这会有一些优点:

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