Polynomial-Time Algorithm for Optimal Stopping with Fixed Accuracy

The authors gratefully acknowledge Kaidong Zhang and Di Wu, for their tremendous help with a numerical implementation, and Bobby Kleinberg, for pointing out that the median trick could be applied in our setting. The authors also thank the organizers and participants of the 2018 Symposium on Optimal Stopping in honor of Larry Shepp held at Rice University.