Value Iteration One Sweep

Problem

Apply one synchronous sweep of value iteration (Bellman optimality backup) and return the updated values.

For each state s compute the action value of every action as sum of p * (r + gamma * V[next]), then take the maximum over actions. The transition and reward layout is the same as in policy evaluation.

Hint

Backup every action with the old V, then keep the largest one per state.

Test cases

case 1

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

expected: [3.8,3.9]

case 2

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

expected: [2,3]

case 3

in: [[[[[1,1]],[[0.5,0],[0.5,1]]],[[[1,0]],[[1,1]]]],[[2,1],[3,0]],0,[5,7]]

expected: [2,3]

Starter codePython

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

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