1

我正在为家庭作业实施价值迭代。它进展顺利，但我对某个部分感到困惑，特别是下面指示的行

//(taken from http://aima.cs.berkeley.edu/python/mdp.html)
def value_iteration(mdp, epsilon=0.001):
  "Solving an MDP by value iteration. [Fig. 17.4]"
  U1 = dict([(s, 0) for s in mdp.states])
  R, T, gamma = mdp.R, mdp.T, mdp.gamma
  while True:
      U = U1.copy()
      delta = 0
      for s in mdp.states:
          U1[s] = R(s) + gamma * max([sum([p * U[s1] for (p, s1) in T(s, a)])
                                    for a in mdp.actions(s)])
          delta = max(delta, abs(U1[s] - U[s])) //*****THIS LINE**************//
      if delta < epsilon * (1 - gamma) / gamma:
          return U

我一般理解这条线的重点，但我是否需要将更新的实用程序与旧版本或最后更新的状态进行比较或什么？目前我所拥有的似乎正在工作（主要是：P），但我很困惑，因为其他版本的算法（例如这个）具有 k <- k + 1 和 ∀s |Vk[s]-Vk-1[s] | < θ 这让我觉得我做错了。

这是我的代码：

grid = [[0,0,0],[0,None,0],[0,0,0],[0,-1,1]]

gamma = .9
epsilon = 0.001 #difference threshold
count = 0
while(True):
   delta = 0
   #walk through the set of states

   i = 0   
   while(i < 4):
       j= 0
       while(j < 3):
          if(grid[i][j] == None or grid[i][j] == 1 or grid[i][j] == -1):
              j = j +1
              continue
          temp =  grid[i][j] 
          grid[i][j] = -0.04 + (gamma * bellman(grid, i, j))
          delta = max(delta, abs(grid[i][j] - temp))

          j = j+1
      i = i+1

  if (delta < (epsilon * (1 - gamma) / gamma)): 
      break

我得到以下输出：

0.5094143831769762  0.6495863449484525  0.795362242280654    1
0.39850269350488843 None                0.48644045209498593 -1
0.29643305379491625 0.25395638075084487 0.344787810489289    0.12994184490884678
4

0 回答 0