Bellman Residual

Problem

Measure how far V is from satisfying the Bellman expectation equation under a policy.

For each state compute the one-step backup sum of p * (r + gamma * V[next]) using policy[s], take the absolute difference from V[s], and return the largest difference. An empty MDP returns 0.0.

Hint

The residual is zero exactly when V is the fixed point of the policy's Bellman operator.

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,[10,10]]

expected: 1

case 2

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

expected: 0.9000000000000004

case 3

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

expected: 2

case 4

in: [[],[],[],0.9,[]]

expected: 0

Starter codePython

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

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