Optimal Stopping Threshold

Problem

Find the optimal stopping time by backward induction.

Compute V[t] = max(exercise[t], continuation[t] + gamma * V[t + 1]) from the end, then scan forward and stop at the first t where exercise[t] >= continuation[t] + gamma * V[t + 1] (with no successor at the last index). Return [stop_index, stopped_value].

Hint

The stopping region is where exercising beats the discounted continuation value.

Test cases

case 1

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

expected: [2,5]

case 2

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

expected: [2,1]

case 3

in: [[3],[2],0.9]

expected: [0,3]

Starter codePython

def optimal_stopping_threshold(exercise, continuation, gamma):
    # Returns [stop_index, value]
    # Your code here
    pass

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