Answers.Body: <p>The issue is that in your list comprehension in def <code>V_pi(state)</code> you have</p>
  
  <pre><code>return sum(prob * (reward + mdp.discount*V[newState]) for prob, reward, newState in
          mdp.succProbReward(state))
  </code></pre>
  
  <p>whereas with the way you have defined the succProbReward output, it should be </p>
  
  <pre><code>return sum(prob * (reward + mdp.discount*V[newState]) for newState, prob, reward in
          mdp.succProbReward(state))
  </code></pre>
  
  <p>When I run this it converges immediately with a reward of 0 for all states, which I believe is correct for the policy you specified. If I change the policy it also seems to give reasonable results.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-14T03:23:21.337Z
Answers.LastActivityDate: 2020-03-14T03:23:21.337Z
Answers.UserDisplayName: Chris Cundy
Body: <p>I am trying to code out a policy evaluation algorithm to find the <span class="math-container">$V^\pi(s)$</span> for all states. The following diagram below shows the MDP. </p>
  
  <p><a href="https://i.sstatic.net/y80eU.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/y80eU.png" alt="enter image description here"></a></p>
  
  <p>In this case i let p = q = 0.5.
  the rewards for each states are independent of action. I.e <span class="math-container">$r(\sigma_0)$</span> = <span class="math-container">$r(\sigma_2)$</span> = 0,<span class="math-container">$r(\sigma_1)$</span> = 1, <span class="math-container">$r(\sigma_3)$</span> = 10. Terminal state is <span class="math-container">$r(\sigma_3)$</span></p>
  
  <p>I have the following policy, {0:1, 1:0, 2:0}, where key is the state and value is the action. 0 for <span class="math-container">$a_0$</span> and 1 for <span class="math-container">$a_1$</span>. </p>
  
  <pre><code>#Policy Iteration solver for FUN
  class PolicyEvaluation:
      def __init__(self, policies):
          self.N = 3
          self.pi = policies
          self.actions = [0, 1] # a0 and a1
          self.discount = 0.7
          self.states = [i for i in range(self.N + 1)]
  
  
      def terminalState(self, state):
          return state == 3
  
      # assume p = q = 0.5
      def succProbReward(self, state):
          # (newState, probability, reward)
          spr_list = []
          if (state == 0 and self.pi[state] == 0):
              spr_list.append([1, 1.0, 1])
          elif (state == 0 and self.pi[state] == 1):
              spr_list.append([2, 1.0, 0])
          elif (state == 1 and self.pi[state] == 0):
              spr_list.append([2, 0.5, 0])
              spr_list.append([0, 0.5, 0])
          elif (state == 2 and self.pi[state] == 0):
              spr_list.append([1, 1.0, 0])
          elif (state == 2 and self.pi[state] == 1):
              spr_list.append([3, 0.5, 10])
              spr_list.append([2, 0.5, 0])
          return spr_list
  
  
  def policyEvaluation(mdp):
      # initialize
      V = {} 
      for state in mdp.states:
          V[state] = 0
  
      def V_pi(state):
          return sum(prob * (reward + mdp.discount*V[newState]) for prob, reward, newState in
          mdp.succProbReward(state))
  
      while True:
      # compute new values (newV) given old values (V)
          newV = {}
          for state in mdp.states:
              if mdp.terminalState(state):
                  newV[state] = 0
              else:
                  newV[state] = V_pi(state)
  
          if max(abs(V[state] - newV[state]) for state in mdp.states) &lt; 1e-10:
              break
          V = newV
          print(V)
      print(V)
  
  
  
  pE = PolicyEvaluation({0:1, 1:0, 2:0})
  print(pE.states)
  print(pE.succProbReward(0))
  policyIteration(pE)
  </code></pre>
  
  <p>I've tried to run the code above to find the values for each state, however, I am not converging with my values. </p>
  
  <p>Is there something wrong that I did?</p>
  
Tags: <reinforcement-learning><markov-decision-process><implementation><convergence><policy-evaluation>
Title: Why isn't the implementation of my policy evaluation for a simple MDP converging?
UserDisplayName: calveeen
ThreadText: # Why isn't the implementation of my policy evaluation for a simple MDP converging?
  
  (Asked by: username_0 on 2020-03-14)
  
  I am trying to code out a policy evaluation algorithm to find the $V^\pi(s)$ for all states. The following diagram below shows the MDP.
  
  [![enter image description here](https://i.sstatic.net/y80eU.png)](https://i.sstatic.net/y80eU.png)
  
  In this case i let p = q = 0.5.
  the rewards for each states are independent of action. I.e $r(\sigma\_0)$ = $r(\sigma\_2)$ = 0,$r(\sigma\_1)$ = 1, $r(\sigma\_3)$ = 10. Terminal state is $r(\sigma\_3)$
  
  I have the following policy, {0:1, 1:0, 2:0}, where key is the state and value is the action. 0 for $a\_0$ and 1 for $a\_1$.
  
  ```
  #Policy Iteration solver for FUN
  class PolicyEvaluation:
      def __init__(self, policies):
          self.N = 3
          self.pi = policies
          self.actions = [0, 1] # a0 and a1
          self.discount = 0.7
          self.states = [i for i in range(self.N + 1)]
  
      def terminalState(self, state):
          return state == 3
  
      # assume p = q = 0.5
      def succProbReward(self, state):
          # (newState, probability, reward)
          spr_list = []
          if (state == 0 and self.pi[state] == 0):
              spr_list.append([1, 1.0, 1])
          elif (state == 0 and self.pi[state] == 1):
              spr_list.append([2, 1.0, 0])
          elif (state == 1 and self.pi[state] == 0):
              spr_list.append([2, 0.5, 0])
              spr_list.append([0, 0.5, 0])
          elif (state == 2 and self.pi[state] == 0):
              spr_list.append([1, 1.0, 0])
          elif (state == 2 and self.pi[state] == 1):
              spr_list.append([3, 0.5, 10])
              spr_list.append([2, 0.5, 0])
          return spr_list
  
  def policyEvaluation(mdp):
      # initialize
      V = {} 
      for state in mdp.states:
          V[state] = 0
  
      def V_pi(state):
          return sum(prob * (reward + mdp.discount*V[newState]) for prob, reward, newState in
          mdp.succProbReward(state))
  
      while True:
      # compute new values (newV) given old values (V)
          newV = {}
          for state in mdp.states:
              if mdp.terminalState(state):
                  newV[state] = 0
              else:
                  newV[state] = V_pi(state)
  
          if max(abs(V[state] - newV[state]) for state in mdp.states) < 1e-10:
              break
          V = newV
          print(V)
      print(V)
  
  pE = PolicyEvaluation({0:1, 1:0, 2:0})
  print(pE.states)
  print(pE.succProbReward(0))
  policyIteration(pE)
  
  ```
  
  I've tried to run the code above to find the values for each state, however, I am not converging with my values.
  
  Is there something wrong that I did?
  
  **Tags:** reinforcement-learning, markov-decision-process, implementation, convergence, policy-evaluation
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-03-14. Score: 2 | Accepted answer
  
  The issue is that in your list comprehension in def `V_pi(state)` you have
  
  ```
  return sum(prob * (reward + mdp.discount*V[newState]) for prob, reward, newState in
          mdp.succProbReward(state))
  
  ```
  
  whereas with the way you have defined the succProbReward output, it should be
  
  ```
  return sum(prob * (reward + mdp.discount*V[newState]) for newState, prob, reward in
          mdp.succProbReward(state))
  
  ```
  
  When I run this it converges immediately with a reward of 0 for all states, which I believe is correct for the policy you specified. If I change the policy it also seems to give reasonable results.
  
  
  ---
  
  