Policy Evaluation Sweep

Problem

Apply one synchronous sweep of policy evaluation on a small MDP and return the new state values.

transitions[s][a] is a list of [probability, next_state] pairs, rewards[s][a] is the expected immediate reward, and policy[s] is the chosen action. Compute V_new[s] = sum over outcomes of p * (r + gamma * V[next]). Return a new list and do not mutate V.

Hint

For each state use its policy action, average over the transition outcomes, and bootstrap from the old V.

Test cases

case 1

in: [[[[[1,1]],[[0.5,0],[0.5,1]]],[[[1,0]],[[1,1]]]],[[2,1],[3,0]],[0,1],0.9,[4,10]]

expected: [11,9]

case 2

in: [[[[[1,1]],[[0.5,0],[0.5,1]]],[[[1,0]],[[1,1]]]],[[2,1],[3,0]],[1,0],0.9,[4,10]]

expected: [7.3,6.6]

case 3

in: [[[[[1,1]]],[[[1,1]]]],[[1],[2]],[0,0],0.5,[0,0]]

expected: [1,2]

case 4

in: [[[[[1,0]]],[[[1,0]]]],[[3],[4]],[0,0],0,[9,9]]

expected: [3,4]

Starter codePython

def policy_evaluation_sweep(transitions, rewards, policy, gamma, V):
    # Your code here
    pass

4 test cases · run your code against them in the editor