<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>

CC BY-SA 4.0
2020-03-14T03:23:21.337Z
2020-03-14T03:23:21.337Z
Chris Cundy
<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>

<reinforcement-learning><markov-decision-process><implementation><convergence><policy-evaluation>
Why isn't the implementation of my policy evaluation for a simple MDP converging?
calveeen
# 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. 

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.


---

