1
$\begingroup$

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

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?

$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.