Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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]| < θ
share|improve this question
You can extend the recursion depth in python 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).

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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