適當的數據結構

Question

我必須實現價值迭代算法，以找到使用Bellman方程的MDP的每個狀態的最優策略。 （a1 s1 0.5）（a2 s1 1.0） s2 0（a1 s2 1.0）（a2 s1 0.5）（a2 s3 0.5） s3 10（a1 s1 0.5） a1 s2 1.0）（a2 s3 0.5）（a2 s4 0.5）

其中s1是狀態0是與s1相關的回報。在採取行動a1後，我們以概率0.5保持s1。在採取行動a1後，我們以概率0.5進入s2。採取行動a2後，我們以概率1.0停留在s1。 和其他類似。

讀取輸入文件後，我必須將其存儲在某個數據結構中。在PYTHON中這將是合適的數據結構，因此遍歷它很容易。

Answer 1

s1 0 (a1 s1 0.5) (a1 s2 0.5) (a2 s1 1.0) 
s2 0 (a1 s2 1.0) (a2 s1 0.5) (a2 s3 0.5) 
s3 10 (a1 s2 1.0) (a2 s3 0.5) (a2 s4 0.5) 

是這樣的嗎？

data = { 's1': { 'reward': 0, 
       'action': { 'a1': { 's1': 0.5, 
            's2': 0.5 }, 
          'a2': { 's1': 1.0 } 
          }, 
       }, 
     's2': { 'reward': 0, 
       'action': { 'a1': { 's1': 1.0 }, 
          'a2': { 's1': 0.5, 
            's2': 0.5 }, 
          }, 
       }, 
     's3': { 'reward': 10, 
       'action': { 'a1': { 's2': 1.0 }, 
          'a2': { 's3': 0.5, 
            's4': 0.5 }, 
          } 
       } 
     } 

Answer 2

通常對於離散（和有限）狀態MDP，HMM或POMDP，最有用的表示形式是一組稀疏矩陣。然後，運動的概率分佈可以通過矩陣 - 向量計算來計算（並且隨機貝爾曼方程可以簡單而有效地實現）。該矩陣將被稱爲隨機矩陣。

http://en.wikipedia.org/wiki/Stochastic_matrix

我建議你看SciPy的庫稀疏矩陣，如果你在Python工作。

http://docs.scipy.org/doc/scipy/reference/sparse.html