Value Iteration To Convergence

Problem

Run value iteration until convergence and return the final value function.

Use synchronous updates V_new[s] = max_a sum of p * (r + gamma * V[next]), starting from V = 0. Stop when the maximum absolute change across states is below tol, or after 10000 sweeps, and return V.

Hint

Compare the largest change between the old and new value vectors to decide when to stop.

Test cases

case 1

in: [[[[[1,1]]],[[[0.8,0],[0.2,1]]]],[[2],[1]],0.9]

expected: [14.76744185221068,14.186046503373474]

case 2

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

expected: [2.8,2,0]

case 3

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

expected: [5.3333333330228925,2.666666666045785]

case 4

in: [[[[[1,1]]],[[[1,1]]]],[[3],[5]],0]

expected: [3,5]

Starter codePython

def value_iteration(transitions, rewards, gamma, tol=1e-9):
    # Your code here
    pass

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