Bellman Equation Check

Problem

Check the Bellman optimality equation at a single state.

With deterministic transitions, the right-hand side is rewards[s] + gamma * max(V[ns] for ns in transitions[s]), or rewards[s] when there are no successors. Return True when V[s] matches within tol.

Hint

Compare the stored value with one Bellman backup at the state.

Test cases

case 1

in: [[1,2,3],[0,0,1],[[1],[2],[]],0.9,1,1e-9]

expected: false

case 2

in: [[1,2,3],[0,0,1],[[1],[2],[]],0.9,0,1e-9]

expected: false

case 3

in: [[0.5,1],[0.5,0.5],[[],[0]],1,1,1e-9]

expected: true

Starter codePython

def bellman_check(V, rewards, transitions, gamma, s, tol):
    # Your code here
    pass

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