In mathematics, the theory of optimal stopping or early stopping is concerned with the problem of choosing a time to take a particular action, in order to maximise an expected reward or minimise an expected cost. Optimal stopping problems can be found in areas of statistics, economics, and mathematical finance (related to the pricing of American options). A key example of an optimal stopping problem is the secretary problem. Optimal stopping problems can often be written in the form of a Bellman equation, and are therefore often solved using dynamic programming.
Definition
Discrete time case Stopping rule problems are associated with two objects:
A sequence of random variables X 1 , X 2 , … {\displaystyle X_{1},X_{2},\ldots } , whose joint distribution is something assumed to be known A sequence of 'reward' functions ( y i ) i ≥ 1 {\displaystyle (y_{i})_{i\geq 1}} which depend on the observed values of the random variables in 1:
y i = y i ( x 1 , … , x i ) {\displaystyle y_{i}=y_{i}(x_{1},\ldots ,x_{i})}
Given those objects, the problem is as follows:
You are observing the sequence of random variables, and at each step i {\displaystyle i} , you can choose to either stop observing or continue If you stop observing at step i {\displaystyle i} , you will receive reward y i {\displaystyle y_{i}}
You want to choose a stopping rule to maximize your expected reward (or equivalently, minimize your expected loss)
Continuous time case Consider a gain process G = ( G t ) t ≥ 0 {\displaystyle G=(G_{t})_{t\geq 0}} defined on a filtered probability space ( Ω , F , ( F t ) t ≥ 0 , P ) {\displaystyle (\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} )} and assume that G {\displaystyle G} is adapted to the filtration. The optimal stopping problem is to find the stopping time τ ∗ {\displaystyle \tau ^{*}} which maximizes the expected gain
V t T = E G τ ∗ = sup t ≤ τ ≤ T E G τ {\displaystyle V_{t}^{T}=\mathbb {E} G_{\tau ^{*}}=\sup _{t\leq \tau \leq T}\mathbb {E} G_{\tau }}
where V t T {\displaystyle V_{t}^{T}} is called the value function. Here T {\displaystyle T} can take value ∞ {\displaystyle \infty } . A more specific formulation is as follows. We consider an adapted strong Markov process X = ( X t ) t ≥ 0 {\displaystyle X=(X_{t})_{t\geq 0}} defined on a filtered probability space ( Ω , F , ( F t ) t ≥ 0 , P x ) {\displaystyle (\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} _{x})} where P x {\displaystyle \mathbb {P} _{x}} denotes the probability measure where the stochastic process starts at x {\displaystyle x} . Given continuous functions M , L {\displaystyle M,L} , and K {\displaystyle K} , the optimal stopping problem is
… excerpt ends here. Continue reading the full article.
