Characterizing the Structure of Optimal Stopping Policies

Abstract

This paper studies a stochastic model of optimal stopping processes, which arise frequently in operational problems (e.g., when a manager needs to determine an optimal epoch to stop a process). For such problems, we propose an effective method of characterizing the structure of the optimal stopping policy for the class of discrete-time optimal stopping problems. Using this method, we also derive a set of metatheorems that can help identify when a threshold or control-band type stopping policy is optimal. We show that our proposed method can determine the structure of the optimal policy for some stopping problems that conventional methods fail to do so. In some cases, our method also simplifies the analysis of some existing results. Moreover, the metatheorems we propose help identify sufficient conditions that yield simple optimal policies when such policies are not generally optimal. We demonstrate these benefits by applying our method to several optimal stopping problems frequently encountered in, for example, the operations, marketing, finance, and economics literatures. We note that with structural results, optimal-stopping policies are easier to follow, describe, and compute and hence implement. They also help determine how a stopping policy should be adjusted in response to changes in the operational environment. In addition, as structural results are critical for the development of efficient algorithms to solve optimal stopping problems numerically, we hope that the method and results provided in the study will contribute to that effort.