In class I am learning about value iteration and markov decision problems, we are doing through the UC Berkley pac-man project, so I am trying to write the value iterator for it and as I understand it, value iteration is that for each iteration you are visiting every state, and then tracking to a terminal state to get its value.

I have a feeling I am not right, because when I try that in python I get a recursive depth exceed. So I return to the pseudo-code, and there is a Vk[s] and Vk-1[s'], which I had thought to mean value of state, and value of newState, but I must be missing something.

So what is the significance of the k and k-1?

My Code:

 def val(i, state):
        if mdp.isTerminal(state) or i == 0:
            return 0.0
        actionCost = {}
        for action in mdp.getPossibleActions(state):
            actionCost[action] = 0
            for (nextState, probability) in mdp.getTransitionStatesAndProbs(state, action):
                reward = mdp.getReward(state, action, nextState)
                actionCost[action] += probability * reward + discount * val(i - 1, nextState)        
        return actionCost[max(actionCost, key=actionCost.get)]

    for i in range(iterations):
        for state in mdp.getStates():  
            self.values[state] = val(i, state)

Pseudo Code:

k ←0 
      k ←k+1 
      for each state s do 
          Vk[s] = maxa ∑s' P(s'|s,a) (R(s,a,s')+ γVk-1[s']) 
until ∀s |Vk[s]-Vk-1[s]| < θ
  • You can extend the recursion depth in python docs.python.org/2/library/sys.html#sys.setrecursionlimit to see if it helps. – SlimJim Mar 17 '13 at 14:44
  • Vk(s) is the expected value (could be seen as a potential) of state s if you look down k steps with an optimal policy – SlimJim Mar 17 '13 at 15:12
  • Your could will lookdown one step further until it converges below theta – SlimJim Mar 17 '13 at 15:13
  • I don't see any problems with the pseudo code so perhaps you can include more? What happens if you increase theta? Whats the printout for max(Vk[s] for s in states) foreach iteration? (does it iterate over k atleast ones?) What is the stop condition for the recursion (V0) – SlimJim Mar 17 '13 at 15:17
  • There is no error in the pseudo code, it's that I don't understand all of it. I dont know what theta is, though I imagine it is floating around somewhere in the code given to the class. I've included my code so you can see how I did it. My while loop doesn't track any theta, it stops when the k is up. – EasilyBaffled Mar 17 '13 at 19:34

Vk and Vk-1 are different iterations of the approximation of V. You could rewrite the pseudo code as:

V ← 0
V' ← 0
while true
  for each state s do
      V ← V'
      V = maxa ∑s' [ P(s'|s,a) R(s,a,s')+ γV'[s'] ]
  if ∀s |V[s]-V'[s]| < θ
      return V

Note that the pseudo-code is not recursive. This is the idea of value-iteration/dyanmic-programming which make it efficient :

  • Compute the optimal value function for 0 time step: V0=0
  • then compute the optimal value function for 1 time step: V1=H(V0)
  • then compute the optimal value function for 2 time steps: V2=H(V1)
  • then compute the optimal value function for 3 time steps: V3=H(V2)
  • ...
  • then compute the optimal value function for n time steps: Vn=H(Vn-1)

with H defined as:

 H(V) = max_a ( Pa [ Ra + γ V ] )

Your code is recursive (val calls val) which triggers some stack overflow error. Value iteration is not recursive but iterative. Your 'eval' function make this:

actionCost[action] += probability * reward + discount * val(i - 1, nextState)

which recomputes recursively a values that you have already computed at the previous iteration (k-1). val(i - 1, nextState) is in fact:


(assuming you keep a copy of previousValue).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.