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, 2013 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, 2013 at 15:12
  • Your could will lookdown one step further until it converges below theta
    – SlimJim
    Mar 17, 2013 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, 2013 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. Mar 17, 2013 at 19:34

1 Answer 1


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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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