RVI Convergence Check

Problem

Check convergence of relative value iteration using the span semi-norm.

Two successive value vectors agree in relative terms when |(V_new[s] - V_new[ref]) - (V_old[s] - V_old[ref])| is below tol for every state. Return True when the largest such difference is strictly below tol.

Hint

Subtracting the reference state removes the arbitrary constant that value iteration adds each sweep.

Test cases

case 1

in: [[0,1,2],[10,11,12],0,0.000001]

expected: true

case 2

in: [[0,1,2],[5,6,6],0,0.000001]

expected: false

case 3

in: [[1,2,3],[2,3,4.0000001],1,0.000001]

expected: true

case 4

in: [[1,2,3],[2,3,4.0001],1,0.000001]

expected: false

Starter codePython

def rvi_converged(V_old, V_new, ref, tol):
    # Your code here
    pass

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