Discounted Occupancy Measure

Problem

Compute the gamma-discounted state occupancy measure of a policy.

d(s) = (1 - gamma) * sum over t of gamma^t * Pr(state_t = s), starting from the initial distribution mu. Iterate the distribution forward, accumulating each term until the remaining weight is below 1e-15, and return the measure.

Hint

The (1 - gamma) factor makes the discounted occupancy measure sum to one.

Test cases

case 1

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

expected: [0.6666666666666661,0.33333333333333215]

case 2

in: [[[0.5,0.5],[0.25,0.75]],[1,0],0.9]

expected: [0.41935483870967416,0.5806451612903162]

case 3

in: [[[1,0],[0,1]],[0.3,0.7],0.8]

expected: [0.29999999999999866,0.6999999999999961]

Starter codePython

def discounted_occupancy(P, mu, gamma):
    # Your code here
    pass

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