11footnotetext: Weierstrass Institute for Applied Analysis and Stochastics,
Mohrenstr. 39, 10117 Berlin, Germany<EMAIL_ADDRESS>
# On the rates of convergence of simulation based optimization algorithms for
optimal stopping problems

Denis Belomestny${}^{1,\,}$ supported in part by the SFB 649 ‘Economic Risk’.

###### Abstract

In this paper we study simulation based optimization algorithms for solving
discrete time optimal stopping problems. This type of algorithms became
popular among practioneers working in the area of quantitative finance. Using
large deviation theory for the increments of empirical processes, we derive
optimal convergence rates and show that they can not be improved in general.
The rates derived provide a guide to the choice of the number of simulated
paths needed in optimization step, which is crucial for the good performance
of any simulation based optimization algorithm. Finally, we present a
numerical example of solving optimal stopping problem arising in option
pricing that illustrates our theoretical findings.

_Keywords:_ optimal stopping, simulation based algorithms, entropy with
bracketing, increments of empirical processes

##  1 Introduction

The theory of optimal 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 many
areas of statistics, economics, and mathematical finance. They can often be
written in the form of a Bellman equation, and are therefore often solved
using dynamic programming. Results on optimal stopping were first developed in
the discrete case. The formulation of optimal stopping problems for discrete
stochastic processes was in sequential analysis, an area of mathematical
statistics where the number of observations is not fixed in advance but is a
random number determined by the behavior of the data being observed. Snell
(1952) was the first person to come up with results on optimal stopping theory
for stochastic processes in discrete time. We refer to the book of Peskir and
Shiryaev (2006) for a comprehensive review on different aspects of optimal
stopping problems.

A huge impetus to the development of optimal stopping theory was provided by
option pricing theory, developed in the late 1960s and the 1970s. According to
the modern financial theory, pricing an American option in a complete market
is equivalent to solving an optimal stopping problem (with a corresponding
generalization in incomplete markets), the optimal stopping time being the
rational time for the option to be exercised. Due to the enormous importance
of the early exercise feature in finance, this line of research has been
intensively pursued in recent times. Solving the optimal stopping problem and
hence pricing an American option is straightforward in low dimensions.
However, many problems arising in practice have high dimensions, and these
applications have motivated the development of Monte Carlo methods for pricing
American option. Solving a high-dimensional optimal stopping problems or
pricing American style derivatives with Monte Carlo is a challenging task
because the determination of the optimal value function requires a backwards
dynamic programming algorithm that appears to be incompatible with the forward
nature of Monte Carlo simulation. Much research was focused on the development
of fast methods to compute approximations to the optimal value function.
Notable examples include mesh method of Broadie and Glasserman (1997), the
regression-based approaches of Carriere (1996), Longstaff and Schwartz (2001),
Tsitsiklis and Van Roy (1999) and Egloff (2005). All these methods aim at
approximating the so called continuation values that can be used later to
construct suboptimal strategies and to produce lower bounds for the optimal
value function. The convergence analysis for this type of methods was
performed in several papers including Egloff (2005), Egloff, Kohler and
Todorovic (2007) and Belomestny (2009). An alternative to trying to
approximate the continuation values is to find the best value function within
a class of stopping rules. This reduces the optimal stopping problem to a much
more tractable finite dimensional optimization problem. Such optimization
problems appear naturally if one considers finite dimensional or parametric
approximations for the corresponding stopping regions. The latter type of
algorithms became particularly popular among practioneers (see e.g. Andersen
(2000) or Garcia (2001)). However, the practical success of simulation-based
optimization algorithms has not been yet fully explained by existing theory,
and our analysis here represents a further step toward an improved
understanding. The main goal of this work is to provide rigorous convergence
analysis of simulation based optimization algorithms for discrete time optimal
stopping problems.

Let us start with a general stochastic programming problem

(1.1) $\displaystyle
h^{*}:=\min_{\theta\in\Theta}\operatorname{E}_{\operatorname{P}}[h(\theta,\xi)],$

where $\Theta$ is a subset of $\mathbb{R}^{m}$, $\xi$ is a $\mathbb{R}^{d}$
valued random variable on the probability space
$(\Omega,\mathcal{F},\operatorname{P})$ and
$h:\mathbb{R}^{m}\times\mathbb{R}^{d}\to\mathbb{R}.$ Draw an i.i.d. sample
$\xi^{(1)},\ldots,\xi^{(M)}$ from the distribution of $\xi$ and define

$\displaystyle
h_{M}:=\min_{\theta\in\Theta}\left[\frac{1}{M}\sum_{m=1}^{M}h(\theta,\xi^{(m)})\right].$

It is well known (see e.g. Shapiro (1993)) that under very mild conditions it
holds $h_{M}-h^{*}=O_{\operatorname{P}}(M^{-1/2}).$ In their pioneering work
Shapiro and Homem-de-Mello (2000) (see also Kleywegt, Shapiro and Homem-de-
Mello (2001)) showed that in the case of discrete random variable $\xi,$ the
convergence of $h_{N}$ to $h^{*}$ can be much faster than $M^{-1/2},$ making
Monte Carlo method particularly efficient in this situation. Turn now to the
discrete time optimal stopping problem:

(1.2) $\displaystyle V=\sup_{1\leq\tau\leq K}\operatorname{E}[Z_{\tau}],$

where $\tau$ is a stopping time taking values in the set $\\{1,\ldots,K\\}$
and $(Z_{k})_{k\geq 0}$ is a Markov chain. Since the random variable $\tau$
takes only discrete values, one can ask whether the simulation based methods
in the case of discrete time optimal stopping problem (1.2) can be as
efficient as in the case of (1.1) with discrete r.v. $\xi$. In this work we
give an affirmative answer to this question by deriving the optimal rates of
convergence for the corresponding Monte Carlo estimate of $V$ based on $M$
paths and showing that these rates are usually faster than $M^{-1/2}$.

##  2 Main setup

Let us consider a Markov chain $X=(X_{k})_{k\geq 0}$ defined on a filtered
probability space $(\Omega,\mathcal{F},(\mathcal{F}_{k})_{k\geq
0},\operatorname{P}_{x})$ and taking values in a measurable space
$(E,\mathcal{B}),$ where for simplicity we assume that $E=\mathbb{R}^{d}$ for
some $d\geq 1$ and $\mathcal{B}=\mathcal{B}(\mathbb{R}^{d})$ is the Borel
$\sigma$-algebra on $\mathbb{R}^{d}.$ It is assumed that the chain $X$ starts
at $x$ under $\operatorname{P}_{x}$ for some $x\in E$ . We also assume that
the mapping $x\mapsto P_{x}(A)$ is measurable for each $A\in\mathcal{F}$ . Fix
some natural number $K>0.$ Given a set of measurable functions
$G_{k}:E\mapsto\mathbb{R}$, $k=1,\ldots,K,$ satisfying

$\displaystyle\operatorname{E}_{x}\left[\sup_{1\leq k\leq
K}|G_{k}(X_{k})|\right]<\infty$

for all $x\in E$ , we consider the optimal stopping problems

(2.3) $\displaystyle V^{*}_{k}(x):=\sup_{k\leq\tau\leq
K}\operatorname{E}_{k,\,x}\left[G_{\tau}(X_{\tau})\right],\quad k=1,\ldots,K,$

where for any $x\in E$ the expectation in (2.3) is taken w.r.t. the measure
$\operatorname{P}_{k,\,x}$ such that $X_{k}=x$ under
$\operatorname{P}_{k,\,x}$ and the supremum is taken over all stopping times
$\tau$ with respect to $(\mathcal{F}_{n})_{n\geq 0}.$ Introduce the stopping
region
$\boldsymbol{\mathcal{S}}^{*}=\mathcal{S}^{*}_{1}\times\ldots\times\mathcal{S}^{*}_{K}$
with $\mathcal{S}^{*}_{K}=E$ and

$\mathcal{S}^{*}_{k}:=\\{x\in E:V^{*}_{k}(x)=G_{k}(x)\\}\\\ =\left\\{x\in
E:\operatorname{E}\left[\left.V^{*}_{k+1}(X_{k+1})\right|\mathcal{F}_{k}\right]\leq
G_{k}(x)\right\\},\quad k=1,\ldots,K-1.$

Introduce also the first entry times $\tau^{*}_{k}$ into
$\boldsymbol{\mathcal{S}}^{*}$ by setting

$\displaystyle\tau^{*}_{k}:=\tau_{k}(\boldsymbol{\mathcal{S}}^{*}):=\min\\{k\leq
l\leq K:X_{l}\in\mathcal{S}_{l}\\}.$

It is well known that the value functions $V^{*}_{k}(x)$ satisfy the so called
Wald-Bellman equations

$\displaystyle
V^{*}_{k}(x)=\max\\{G_{k}(x),\operatorname{E}_{n,x}[V^{*}_{k+1}(X_{k+1})]\\},\quad
k=1,\ldots,K-1,\quad x\in E$

with $V^{*}_{K}(x)\equiv G_{K}(x)$ by definition. Moreover, the stopping times
$\tau^{*}_{k}$ are optimal in (2.3), i.e.

$\displaystyle
V^{*}_{k}(x)=\operatorname{E}_{k,\,x}\left[G_{\tau^{*}_{k}}(X_{\tau^{*}_{k}})\right],\quad
k=1,\ldots,K.$

Let $(X^{(m)}_{k})_{k=0,\ldots,K},\,m=1,\ldots,M$ be $M$ independent processes
with the same distribution as $X$ all starting from the point $x\in E.$ We can
think of $(X^{(1)}_{k},\ldots,X^{(M)}_{k}),$ $k=0,\ldots,K,$ as a new process
defined on the product probability space equipped with the product measure
$\operatorname{P}_{x}^{\otimes M}.$ Let $\mathfrak{B}$ be a collection of sets
from the product $\sigma$-algebra

$\mathcal{B}^{K}:=\underbrace{\mathcal{B}\otimes\ldots\otimes\mathcal{B}}_{K}$

that contains all sets $\boldsymbol{\mathcal{S}}\in\mathcal{B}^{K}$ of the
form
$\boldsymbol{\mathcal{S}}=\mathcal{S}_{1}\times\ldots\times\mathcal{S}_{K-1}\times
E$ with $\mathcal{S}_{k}\in\mathcal{B},\,k=1,\ldots,K-1.$ Here we take into
account the fact that the stopping set $\mathcal{S}_{K}$ must coincide with
$E.$ Let $\mathfrak{S}$ be a subset of $\mathfrak{B}.$ Define

$\displaystyle\boldsymbol{\mathcal{S}}_{M}:=\arg\max_{\boldsymbol{\mathcal{S}}\in\mathfrak{S}}\left\\{\frac{1}{M}\sum_{m=1}^{M}G_{\tau_{1}(\boldsymbol{\mathcal{S}})}\left(X^{(m)}_{\tau_{1}(\boldsymbol{\mathcal{S}})}\right)\right\\}.$

The stopping rule

$\displaystyle\tau_{M}:=\tau_{1}(\boldsymbol{\mathcal{S}}_{M})=\min\\{1\leq
k\leq K:X_{k}\in\mathcal{S}_{M,k}\\}.$

is generally suboptimal and therefore the corresponding Monte Carlo estimate

(2.4) $\displaystyle
V_{M,N}:=\frac{1}{N}\sum_{n=1}^{N}G_{\tau^{(n)}_{M}}\left(\widetilde{X}^{(n)}_{\tau^{(n)}_{M}}\right)$

with

$\displaystyle\tau^{(n)}_{M}:=\min\\{1\leq k\leq
K:\widetilde{X}^{(n)}_{k}\in\mathcal{S}_{M,k}\\},\quad n=1,\ldots,N$

based on a new, independent of $(X^{(1)},\ldots,X^{(M)})$ set of trajectories

$(\widetilde{X}^{(n)}_{0},\ldots,\widetilde{X}^{(n)}_{K}),\quad n=1,\ldots,N,$

fulfills

(2.5) $\displaystyle
V_{M}:=\operatorname{E}_{x}\left[V_{M,N}|X^{(1)},\ldots,X^{(M)}\right]$
$\displaystyle\leq$
$\displaystyle\sup_{\boldsymbol{\mathcal{S}}\in\mathfrak{S}}\operatorname{E}_{x}\left[G_{\tau_{1}(\boldsymbol{\mathcal{S}})}\left(X_{\tau_{1}(\boldsymbol{\mathcal{S}})}\right)\right].$

If the set $\mathfrak{S}$ is rich enough, then

$\displaystyle\sup_{\boldsymbol{\mathcal{S}}\in\mathfrak{S}}\operatorname{E}_{x}\left[G_{\tau_{1}(\boldsymbol{\mathcal{S}})}\left(X_{\tau_{1}(\boldsymbol{\mathcal{S}})}\right)\right]=:\operatorname{E}_{x}\left[G_{\tau_{1}(\bar{\boldsymbol{\mathcal{S}}})}\left(X_{\tau_{1}(\bar{\boldsymbol{\mathcal{S}}})}\right)\right]\approx\operatorname{E}_{x}\left[G_{\tau_{1}(\boldsymbol{\mathcal{S}}^{*})}\left(X_{\tau_{1}(\boldsymbol{\mathcal{S}}^{*})}\right)\right]$

and $V_{M,N}$ can serve as a good approximation for $V^{*}$ for large enough
$M$ and $N.$ In the next section we are going to study the question: how fast
does $V_{M}$ converge to $V^{*}=V^{*}_{1}$ as $M\to\infty$ ? We will show that
the corresponding rates of convergence are always faster than usual rates
$M^{-1/2}.$ This fact has a practical implication since it indicates that $M$,
the number of simulated paths used in the optimization step, can be taken much
smaller than $N,$ the number of paths used to compute the final estimate
$V_{M,N}$.

##  3 Main results

#### Definition

Let $\delta>0$ be a given number and $d_{X}(\cdot,\cdot)$ be a pseudedistance
between two elements of $\mathfrak{B}$ defined as

(3.6) $\displaystyle d_{X}(G_{1}\times\ldots\times
G_{K},G^{\prime}_{1}\times\ldots\times
G^{\prime}_{K})=\sum_{k=1}^{K}\operatorname{P}_{x}(X(t_{k})\in G_{k}\triangle
G^{\prime}_{k}),$

where $\\{G_{k}\\}$ and $\\{G^{\prime}_{k}\\}$ are subsets of $E.$ Define
$N(\delta,\mathfrak{S},d_{X})$ be the smallest value $n$ for which there exist
pairs of sets

$(G_{j,1}^{L}\times\ldots\times G_{j,K}^{L},G_{j,1}^{U}\times\ldots\times
G_{j,K}^{U}),\quad j=1,\ldots,n,$

such that $d_{X}(G_{j,1}^{L}\times\ldots\times
G_{j,K}^{L},G_{j,1}^{U}\times\ldots\times G_{j,K}^{U})\leq\delta$ for all
$j=1,\ldots,n,$ and for any $G\in\mathfrak{S}$ there exists
$j(G)\in\\{1,\ldots,n\\}$ for which

$G^{L}_{j(G),k}\subseteq G_{k}\subseteq G^{U}_{j(G),k},\quad k=1,\ldots,K.$

Then the value
$\mathcal{H}(\delta,\mathfrak{S},d):=\log[N(\delta,\mathfrak{S},d_{X})]$ is
called the $\delta$-entropy with bracketing of $\mathfrak{S}$ for the
pseudedistance $d_{X}$.

#### Assumption

We assume that the family of stopping regions $\mathfrak{S}$ is such that

(3.7) $\displaystyle\mathcal{H}(\delta,\mathfrak{S},d_{X})\leq
A\delta^{-\rho}$

for some constant $A>0$, any $0<\delta<1$ and some $\rho>0$.

#### Example

Let $\mathfrak{S}=\mathfrak{S}_{\gamma}$, where $\mathfrak{S}_{\gamma}$ is a
class of subsets of
$\overbrace{\mathbb{R}^{d}\times\ldots\times\mathbb{R}^{d}}^{K}$ with
boundaries of Hölder smoothness $\gamma>0$ defined as follows. For given
$\gamma>0$ and $d\geq 2$ consider the functions $b(x_{1},\ldots,x_{d-1}),$
$b:\mathbb{R}^{d-1}\to\mathbb{R}$ having continuous partial derivatives of
order $l$, where $l$ is the maximal integer that is strictly less than
$\gamma$. For such functions $b$, we denote the Taylor polynomial of order $l$
at a point $x\in\mathbb{R}^{d-1}$ by $\pi_{b,x}$. For a given $H>0$, let
$\Sigma(\gamma,H)$ be the class of functions $b$ such that

$\displaystyle|b(y)-\pi_{b,x}(y)|\leq H\|x-y\|^{\gamma},\quad
x,y\in\mathbb{R}^{d-1},$

where $\|y\|$ stands for the Euclidean norm of $y\in\mathbb{R}^{d-1}.$ Any
function $b$ from $\Sigma(\gamma,H)$ determines a set

$\displaystyle S_{b}:=\\{(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}:0\leq x_{d}\leq
b(x_{1},\ldots,x_{d-1})\\}.$

Define the class

(3.8) $\displaystyle\mathfrak{S}_{\gamma}:=\\{S_{b_{1}}\times\ldots\times
S_{b_{K-1}}\times E:\,b_{1},\ldots,b_{K-1}\in\Sigma(\gamma,H)\\}.$

It can be shown (see Dudley, 1999, Section 8.2) that the class
$\mathfrak{S}_{\gamma}$ fulfills

$\mathcal{H}(\delta,\mathfrak{S}_{\gamma},d_{X})\leq
A\delta^{-(K-1)(d-1)/\gamma}$

for some $A>0$ and all $\delta>0$ small enough. Now we are in the position to
formulate the main result of our study.

######  Theorem 3.1.

Let $\mathfrak{S}$ be a subset of $\mathfrak{B}$ such that assumption (3.7) is
fulfilled with some $0<\rho\leq 1$ and

(3.9)
$\displaystyle\operatorname{E}_{x}\left[G_{\tau_{1}(\boldsymbol{\mathcal{S}}^{*})}\left(X_{\tau_{1}(\boldsymbol{\mathcal{S}}^{*})}\right)\right]-\bar{V}\leq
DM^{-1/(1+\rho)}$

with
$\bar{V}:=\sup_{\boldsymbol{\mathcal{S}}\in\mathfrak{S}}\operatorname{E}_{x}\left[G_{\tau_{1}(\boldsymbol{\mathcal{S}})}\left(X_{\tau_{1}(\boldsymbol{\mathcal{S}})}\right)\right]$
and some constant $D>0.$ Assume that all functions $G_{k}$ are uniformly
bounded and the inequalities

(3.10)
$\displaystyle\operatorname{P}_{x}(|G_{k}(X_{k})-\operatorname{E}[V^{*}_{k+1}(X_{k+1})|\mathcal{F}_{k}]|<\delta)\leq
A_{0,k}\delta^{\alpha},\quad\delta<\delta_{0}$

hold for some $\alpha>0$, $A_{0,k}>0,$ $k=1,\ldots,K-1$, and $\delta_{0}>0$.
Then for any $U>U_{0}$ and $M>M_{0}$

(3.11) $\displaystyle\operatorname{P}^{\otimes
M}_{x}\left(V^{*}-V_{M}\geq(U/M)^{\frac{1+\alpha}{2+\alpha(1+\rho)}}\right)\leq
C\exp(-\sqrt{U}/B).$

with some constants $U_{0}>0$, $M_{0}>0$, $B>0$ and $C>0.$

######  Remark 3.2.

Without condition (3.9) the inequality (3.11) continues to hold with $V^{*}$
replaced by $\bar{V}$, the best approximation of $V^{*}$ within the class of
stopping regions $\mathfrak{S}.$

######  Remark 3.3.

The requirement that functions $G_{k}$ are uniformly bounded can be replaced
by the existence of all moments of $G_{k}(X_{k}),\,k=1,\ldots,K-1,$ under
$\operatorname{P}.$ In this case on can reformulate Theorem 6.1 using
generalized entropy with bracketing instead of usual entropy with bracketing
(see Chapter 5.4 in Van de Geer (2000)).

The above convergence rates can not be in general improved as shown in the
next theorem.

######  Proposition 3.4.

Consider the problem (2.3) with $k=1$ and two possible stopping dates, i.e.
$\tau\in\\{1,2\\}$. Fix a pair of non-zero functions $G_{1},G_{2}$ such that
$G_{2}:\mathbb{R}^{d}\to\\{0,1\\}$ and $0<G_{1}(x)<1$ on $[0,1]^{d}.$ Fix some
$\gamma>0$ and $\alpha>0$ and let $\mathcal{P}_{\alpha,\gamma}$ be a class of
pricing measures such that the condition (3.10) is fulfilled and for any
$\operatorname{P}\in\mathcal{P}_{\alpha,\gamma}$ the corresponding stopping
set $\boldsymbol{\mathcal{S}}^{*}_{\operatorname{P}}$ is in
$\mathfrak{S}_{\gamma}.$ Then there exist a subset $\mathcal{P}$ of
$\mathcal{P}_{\alpha,\gamma}$ and a constant $B>0$ such that for any $M\geq
1$, any stopping time $\tau_{M}\in\\{1,2\\}$ measurable w.r.t.
$\mathcal{F}^{\otimes M}$

$\displaystyle\sup_{\operatorname{P}\in\mathcal{P}}\left\\{\sup_{\tau\in\\{1,2\\}}\operatorname{E}_{\operatorname{P}}[G_{\tau}(X_{\tau})]-\operatorname{E}_{\operatorname{P}^{\otimes
M}}[\operatorname{E}_{\operatorname{P}}G_{\tau_{M}}(X_{\tau_{M}})]\right\\}\geq
BM^{-\frac{1+\alpha}{2+\alpha(1+(d-1)/\gamma)}}.$

#### Discussion

It follows from Theorem 3.1 that

$\displaystyle
V^{*}-V_{M}=O_{\operatorname{P}}\left(M^{-\frac{1+\alpha}{2+\alpha(1+\rho)}}\right)=o_{\operatorname{P}}(M^{-1/2})$

as long as $\alpha>0.$ Using the decomposition

$\displaystyle V^{*}-V_{M,N}=V^{*}-V_{M}+V_{M}-V_{M,N}$

and the fact that $V_{M}-V_{M,N}=O_{\operatorname{P}}(1/\sqrt{N})$ for any
$M>0$, we conclude that

$\displaystyle
V^{*}-V_{M,N}=O_{\operatorname{P}}\left(M^{-\frac{1+\alpha}{2+\alpha(1+\rho)}}+N^{-\frac{1}{2}}\right).$

Hence, given $N$, a reasonable choice of $M$, the number of Monte Carlo paths
used in the optimization step, can be defined as $M\asymp
N^{\frac{2+\alpha(1+\rho)}{2(1+\alpha)}}.$ In the case when there exists a
parametric family of stopping regions satisfying (3.9) (see Section 4 for some
examples), one gets

(3.12) $\displaystyle M\asymp N^{\frac{2+\alpha}{2(1+\alpha)}}$

since any parametric family of stopping regions with finite dimensional
parameter set fulfills (3.7) for arbitrary small $\rho>0.$ Let us also make a
few remarks on the condition (3.10) and the parameter $\alpha$. If each
function
$G_{k}(x)-\operatorname{E}_{k,x}[V^{*}_{k+1}(X_{k+1})],\,k=1,\ldots,K-1,$ has
a non-vanishing Jacobian in the vicinity of the stopping boundary
$\partial\mathcal{S}_{k}$ and $X_{k}$ has continuous distribution, then (3.10)
is fulfilled with $\alpha=1.$ In fact, it is not difficult to construct
examples showing that the parameter $\alpha$ can take any value from
$\mathbb{R}_{+}$. If $\alpha=1$ (the most common case) (3.12) simplifies to
$M\asymp N^{3/4}$, the choice supported by our numerical example.

Finally, we would like to mention an interesting methodological connection
between our analysis and the analysis of statistical discrimination problem
performed in Mammen and Tsybakov (1999) (see also Devroye, Györfi and Lugosi
(1996)). In particular, we need similar results form the theory of empirical
processes and the condition (3.10) formally resembles the so called “margin”
condition often encountered in the literature on discrimination analysis.

##  4 Applications

In this section we illustrate our theoretical results by some financial
applications. Namely, we consider the problem of pricing Bermudan options. The
pricing of American-style options is one of the most challenging problems in
computational finance, particularly when more than one factor affects the
option values. Simulation based methods have become increasingly attractive
compared to other numerical methods as the dimension of the problem increases.
The reason for this is that the convergence rates of simulation based methods
are generally independent of the number of state variables. In the context of
our paper we consider the so called parametric approximation algorithms (see
Glasserman, 2003, Section 8.2). In essence, these algorithms represent the
optimal stopping sets $\mathcal{S}^{*}_{k}$ by a finite numbers of parameters
and then find the Bermudan option price by maximizing, over the parameter
space, a Monte Carlo approximation of the corresponding value function. The
important question here is wether on can parametrize the optimal stopping
region $\boldsymbol{\mathcal{S}}^{*}$ by a finite dimensional set of
parameters, i.e.
$\boldsymbol{\mathcal{S}}^{*}=\boldsymbol{\mathcal{S}}(\theta),\,\theta\in\Theta,$
where $\Theta$ is a compact finite dimensional set. It turns out that that
this is possible in many situations (see Garcia (2001)). The assumption (3.7)
and (3.9) are then automatically fulfilled with arbitrary small $\rho>0.$

###  4.1 Numerical example: Bermudan max call

This is a benchmark example studied in Broadie and Glasserman (1997) and
Glasserman (2003) among others. Specifically, the model with $d$ identically
distributed assets is considered, where each underlying has dividend yield
$\delta$. The risk-neutral dynamic of the asset
$X(t)=(X^{1}(t),\ldots,X^{d}(t))$ is given by

$\frac{dX^{l}(t)}{X^{l}(t)}=(r-\delta)dt+\sigma dW^{l}(t),\quad
X^{l}(0)=x_{0},\quad l=1,...,d,$

where $W^{l}(t),\,l=1,...,d$, are independent one-dimensional Brownian motions
and $x_{0},r,\delta,\sigma$ are constants. At any time
$t\in\\{t_{1},...,t_{K}\\}$ the holder of the option may exercise it and
receive the payoff

$G_{k}(X_{k}):=\left(\max\left(X^{1}_{k},...,X^{d}_{k}\right)-\kappa\right)^{+},$

where $X_{k}:=X(t_{k})$ for $k=1,\ldots,K.$ We take $d=2$, $r=5\%$,
$\delta=10\%$, $\sigma=0.2$, $\kappa=100$, $x_{0}=90$ and
$t_{k}=kT/K,\,k=1,\ldots,K$, with $T=3,\,K=9$ as in Glasserman (2003, Chapter
8).

To describe the optimal early exercise region at date $t_{k},\,k=1,\ldots,K,$
one can divide $\mathbb{R}^{2}$ into three different connected sets: one
exercise region and two continuation regions (see Broadie and Detemple (1997)
for more details). All these regions can be parameterized by using two
functions depending on two dimensional parameter
$\theta_{k}\in\mathbb{R}^{2}.$ Making use of this characterization, we define
a parametric family of stopping regions as in Garcia (2001) via

$\displaystyle\mathcal{S}_{k}(\theta_{k}):=\\{(x_{1},x_{2}):\max(\max(x_{1},x_{2})-K,0)>\theta^{1}_{k};\,|x_{1}-x_{2}|>\theta^{2}_{k}\\},$

where $\theta_{k}\in\Theta,\,k=1,\ldots,K$ and $\Theta$ is a compact subset of
$\mathbb{R}^{2}.$ Furthermore, we simplify the corresponding optimization
problem by setting $\theta_{1}=\ldots=\theta_{K}.$ This will introduce an
additional bias and hence may increase the left hand side of (3.9) (see Remark
3.2). However, this bias turns out to be rather small in practice. In order to
implement and analyze the simulation based optimization based algorithm in
this situation, we perform the following steps:

  * •

Simulate $L$ independent sets of trajectories of the process $(X_{k})$ each of
the size $M$:

$\displaystyle(X^{(l,m)}_{1},\ldots,X^{(l,m)}_{K}),\quad m=1,\ldots,M,$

where $l=1,\ldots,L.$

  * •

Compute estimates $\theta_{M}^{(1)},\ldots,\theta_{M}^{(L)}$ via

$\displaystyle\theta_{M}^{(l)}:=\arg\max_{\theta\in\Theta}\left\\{\frac{1}{M}\sum_{m=1}^{M}G_{\tau_{1}(\boldsymbol{\mathcal{S}}(\theta))}\left(X^{(l,m)}_{\tau_{1}(\boldsymbol{\mathcal{S}}(\theta))}\right)\right\\}.$

  * •

Simulate a new set of trajectories of size $N$ independent of
$(X^{(l,m)}_{k}):$

$(\widetilde{X}^{(n)}_{1},\ldots,\widetilde{X}^{(n)}_{K}),\quad n=1,\ldots,N.$

  * •

Compute $L$ estimates for the optimal value function $V^{*}_{1}$ as follows

$\displaystyle
V^{(l)}_{M,N}:=\frac{1}{N}\sum_{n=1}^{N}G_{\tau^{(l,n)}_{M}}\left(\widetilde{X}^{(n)}_{\tau^{(l,n)}_{M}}\right),\quad
l=1,\ldots,L,$

with

$\displaystyle\tau^{(l,n)}_{M}:=\min\left\\{1\leq k\leq
K:\widetilde{X}^{(n)}_{k}\in\mathcal{S}_{k}\left(\theta^{(l)}_{M}\right)\right\\},\quad
n=1,\ldots,N.$

Denote by $\sigma_{M,N,l}$ the standard deviation computed from the sample
$(G_{\tau^{(l,n)}_{M}},\,n=1,\ldots,N)$ and set
$\sigma_{M,N}=\min_{l}\sigma_{M,N,l}.$

  * •

Compute

$\displaystyle\mu_{M,N,L}:=\frac{1}{L}\sum_{l=1}^{L}V^{(l)}_{M,N},\quad\vartheta_{M,N,L}:=\sqrt{\frac{1}{L-1}\sum_{l=1}^{L}\left(V^{(l)}_{M,N}-\mu_{M,N,L}\right)^{2}}.$

By the law of large numbers

(4.13) $\displaystyle\mu_{M,N,L}$
$\displaystyle\stackrel{{\scriptstyle\operatorname{P}}}{{\to}}$
$\displaystyle\operatorname{E}_{\operatorname{P}^{\otimes
M}}\left[V_{M,N}\right],\quad L\to\infty,$ (4.14)
$\displaystyle\vartheta_{M,N,L}$
$\displaystyle\stackrel{{\scriptstyle\operatorname{P}}}{{\to}}$
$\displaystyle\operatorname{Var}_{\operatorname{P}^{\otimes
M}}\left[V_{M,N}\right],\quad L\to\infty,$

where

$\displaystyle
V_{M,N}:=\frac{1}{N}\sum_{n=1}^{N}G_{\tau^{(n)}_{M}}\left(\widetilde{X}^{(n)}_{\tau^{(n)}_{M}}\right).$

The difference $\bar{V}-V_{M,N}$ with

$\displaystyle\bar{V}:=\max_{\theta\in\Theta}\operatorname{E}[G_{\tau_{1}(\boldsymbol{\mathcal{S}}(\theta))}(X_{\tau_{1}(\boldsymbol{\mathcal{S}}(\theta))})]$

can be decomposed into the sum of three terms

(4.15) $\displaystyle(\bar{V}-\operatorname{E}_{\operatorname{P}^{\otimes
M}}\left[V_{M}\right])+(\operatorname{E}_{\operatorname{P}^{\otimes
M}}\left[V_{M}\right]-V_{M})+V_{M}-V_{M,N}.$

The first term in (4.15) is deterministic and can be approximated by
$Q_{1}(M):=\mu_{M^{*},N^{*},L^{*}}-\mu_{M,N^{*},L^{*}}$ with large enough
$L^{*}$, $M^{*}$ and $N^{*}.$ The variability of the second, zero mean,
stochastic term can be measured by
$\sqrt{\operatorname{Var}_{\operatorname{P}^{\otimes M}}\left[V_{M}\right]}$
which in turn can be estimated by
$Q_{2}(M):=\sqrt{\vartheta_{M,N^{*},L^{*}}}$, due to (4.14). The standard
deviation of $V_{M}-V_{M,N}$ for any $M$ can be approximated by
$Q_{3}(N)=\sigma_{M^{*},N}/\sqrt{N}$. In our simulation study we take
$N^{*}=1000000,\,L^{*}=500,\,M^{*}=10000$ and obtain
$\bar{V}\approx\mu_{M^{*},N^{*},L^{*}}=7.96$ (note that $V^{*}=8.07$ according
to Glasserman (2003)). In the left-hand side of Figure 1 we plot both
quantities $Q_{1}(M)$ and $Q_{2}(M)$ as functions of $M.$ Note that $Q_{2}(M)$
dominates $Q_{1}(M)$, especially for large $M.$ Hence, by comparing $Q_{2}(M)$
with $Q_{3}(N)$ and approximately solving the equation $Q_{2}(M)=Q_{3}(N)$ in
$N$, one can infer on the optimal relation between $M$ and $N$. In Figure 1
(on the right-hand side) the resulting empirical relation is depicted by
crosses. Additionally, we plotted two benchmark curves $N=M^{4/3}$ and
$N=M^{4.5/3}$. As one can see the choice $M=N^{3/4}$ is likely to be
sufficient in this situation since it always leads to the inequality
$Q_{1}(M)+\sigma Q_{2}(M)\leq\sigma Q_{3}(N)$ for any $\sigma>1.$ As a
consequence, for $M=N^{3/4}$ and any $N$, $\bar{V}$ lies with high probability
in the interval $[\mu_{M,N,L^{*}}-\sigma Q_{3}(N),\mu_{M,N,L^{*}}+\sigma
Q_{3}(N)],$ provided that $\sigma$ is large enough.

Figure 1:  Left: functions $Q_{1}(M)$ and $Q_{2}(M)$; Right: optimal empirical
relationship between $M$ and $N$ (crosses) together with benchmark curves
$N=M^{4/3}$ (dashed line) and $N=M^{4.5/3}$ (dotted line).

##  5 Proof of main results

###  5.1 Proof of Theorem 3.1

Define

$\displaystyle\Delta_{M}(\boldsymbol{\mathcal{S}})$ $\displaystyle:=$
$\displaystyle\sqrt{M}\sum_{m=1}^{M}\left\\{G_{\tau_{1}(\boldsymbol{\mathcal{S}})}\left(X^{(m)}_{\tau_{1}(\boldsymbol{\mathcal{S}})}\right)-\operatorname{E}\left[G_{\tau_{1}(\boldsymbol{\mathcal{S}})}\left(X_{\tau_{1}(\boldsymbol{\mathcal{S}})}\right)\right]\right\\}$

and
$\Delta_{M}(\boldsymbol{\mathcal{S}}^{\prime},\boldsymbol{\mathcal{S}}):=\Delta_{M}(\boldsymbol{\mathcal{S}}^{\prime})-\Delta_{M}(\boldsymbol{\mathcal{S}})$
for any
$\boldsymbol{\mathcal{S}}^{\prime},\boldsymbol{\mathcal{S}}\in\mathfrak{S}.$
Since

$\frac{1}{M}\sum_{m=1}^{M}G_{\tau_{1}(\bar{\boldsymbol{\mathcal{S}}})}\left(X^{(m)}_{\tau_{1}(\bar{\boldsymbol{\mathcal{S}}})}\right)\leq\frac{1}{M}\sum_{m=1}^{M}G_{\tau_{1}(\boldsymbol{\mathcal{S}}_{M})}\left(X^{(m)}_{\tau_{1}(\boldsymbol{\mathcal{S}}_{M})}\right)$

with probability $1$, it holds

(5.16) $\displaystyle\Delta(\boldsymbol{\mathcal{S}}_{M})$ $\displaystyle\leq$
$\displaystyle\Delta(\bar{\boldsymbol{\mathcal{S}}})+\frac{\left[\Delta_{M}(\boldsymbol{\mathcal{S}}^{*},\bar{\boldsymbol{\mathcal{S}}})+\Delta_{M}(\boldsymbol{\mathcal{S}}_{M},\boldsymbol{\mathcal{S}}^{*})\right]}{\sqrt{M}}$

with
$\Delta(\boldsymbol{\mathcal{S}}):=\operatorname{E}[G_{\tau^{*}_{1}}(X_{\tau^{*}_{1}})]-\operatorname{E}[G_{\tau_{1}(\boldsymbol{\mathcal{S}})}(X_{\tau_{1}(\boldsymbol{\mathcal{S}})})].$
Set $\varepsilon_{M}=M^{-1/2(1+\rho)}$ then

$\displaystyle\Delta(\boldsymbol{\mathcal{S}}_{M})$ $\displaystyle\leq$
$\displaystyle\Delta(\bar{\boldsymbol{\mathcal{S}}})+\frac{2}{\sqrt{M}}\sup_{\boldsymbol{\mathcal{S}}\in\mathfrak{S}:\,\Delta_{G}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})\leq\varepsilon_{M}}|\Delta_{M}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})|$
$\displaystyle+2\times\frac{\Delta_{G}^{(1-\rho)}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}}_{M})}{\sqrt{M}}\times\sup_{\boldsymbol{\mathcal{S}}\in\mathfrak{S}:\,\Delta_{G}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})>\varepsilon_{M}}\left[\frac{|\Delta_{M}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})|}{\Delta_{G}^{(1-\rho)}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})}\right].$

Define

$\displaystyle\mathcal{W}_{1,M}:=\sup_{\boldsymbol{\mathcal{S}}\in\mathfrak{S}:\,\Delta_{G}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})\leq\varepsilon_{M}}|\Delta_{M}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})|,$
$\displaystyle\mathcal{W}_{2,M}:=\sup_{\boldsymbol{\mathcal{S}}\in\mathfrak{S}:\,\Delta_{G}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})>\varepsilon_{M}}\frac{|\Delta_{M}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})|}{\Delta_{G}^{(1-\rho)}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})}$

and set $\mathcal{A}_{0}:=\\{\mathcal{W}_{1,M}\leq
U\varepsilon_{M}^{1-\rho}\\}$ for $U>U_{0}.$ Note that under assumption (3.7)
the condition (6.17) of Theorem 6.1 is fulfilled with $\nu=2\rho$ due to
Corollary 6.3. Hence Theorem 6.1 yields
$\operatorname{P}(\bar{\mathcal{A}}_{0})\leq
C\exp(-U\varepsilon_{M}^{-2\rho}/C^{2}).$ Denote

$\displaystyle\Delta_{G}(\boldsymbol{\mathcal{S}},\boldsymbol{\mathcal{S}}^{\prime}):=\left\\{\operatorname{E}\left[G_{\tau_{1}(\boldsymbol{\mathcal{S}})}\left(X_{\tau_{1}(\boldsymbol{\mathcal{S}})}\right)-G_{\tau_{1}(\boldsymbol{\mathcal{S}}^{\prime})}\left(X_{\tau_{1}(\boldsymbol{\mathcal{S}}^{\prime})}\right)\right]^{2}\right\\}^{1/2}$

for any
$\boldsymbol{\mathcal{S}},\boldsymbol{\mathcal{S}}^{\prime}\in\mathfrak{B}.$
Since $\Delta(\bar{\boldsymbol{\mathcal{S}}})\leq DM^{-1/(1+\rho)}$ and
$\varepsilon^{1-\rho}_{M}/\sqrt{M}=M^{-1/(1+\rho)}$, we get on
$\mathcal{A}_{0}$

$\displaystyle\Delta(\boldsymbol{\mathcal{S}}_{M})$ $\displaystyle\leq$
$\displaystyle
C_{0}M^{-1/(1+\rho)}+2\times\frac{\Delta_{G}^{(1-\rho)}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}}_{M})}{\sqrt{M}}\mathcal{W}_{2,M}$

with $C_{0}=D+2U$. Combining Corollary 6.3 with Corollary 6.4 leads to the
inequality

$\displaystyle\Delta_{G}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}}_{M})\leq
2\sqrt{2}A_{G}v^{-\alpha/2(1+\alpha)}_{\alpha}\Delta^{\alpha/2(1+\alpha)}(\boldsymbol{\mathcal{S}}_{M})$

which holds on the set
$\mathcal{A}_{1}:=\\{\Delta_{X}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}}_{M})\leq\delta_{\alpha}\\},$
where $\delta_{\alpha}$ and $v_{\alpha}$ are defined in Corollary 6.4. Denote

$\displaystyle\mathcal{A}_{2}:=\left\\{\Delta(\boldsymbol{\mathcal{S}}_{M})>C_{0}(1+\varkappa)M^{-1/(1+\rho)}\right\\}$

with some $\varkappa>0.$ It then holds on
$\mathcal{A}_{0}\cap\mathcal{A}_{1}\cap\mathcal{A}_{2}$

$\displaystyle\Delta(\boldsymbol{\mathcal{S}}_{M})\leq
2\frac{\Delta^{\alpha(1-\rho)/(2(1+\alpha))}(\boldsymbol{\mathcal{S}}_{M})}{\varkappa\sqrt{M}}\mathcal{W}_{2,M}$

and therefore

$\displaystyle\Delta(\boldsymbol{\mathcal{S}}_{M})\leq(\varkappa/2)^{-\nu}M^{-\nu/2}\mathcal{W}^{\nu}_{2,M}$

with $\nu=\frac{2(1+\alpha)}{2+\alpha(1+\rho)}.$ Let us now estimate
$\operatorname{P}(\bar{\mathcal{A}}_{1}).$ Using Corollary 6.4, we get

$\operatorname{P}_{x}^{\otimes
M}(\Delta_{X}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}}_{M})>\delta_{\alpha})\leq\\\
\operatorname{P}_{x}^{\otimes
M}\left(\left(\frac{2^{1/\alpha}}{\delta_{0}}\right)\Delta(\boldsymbol{\mathcal{S}}_{M})+\frac{\delta_{\alpha}}{2(1+\alpha)}>\delta_{\alpha}\right)\\\
=\operatorname{P}_{x}^{\otimes
M}(\Delta(\boldsymbol{\mathcal{S}}_{M})>c_{\alpha})$

with
$c_{\alpha}=\delta_{0}\delta_{\alpha}2^{-1/\alpha}\left(1-\frac{1}{2(1+\alpha)}\right).$
Furthermore, due to (5.16)

$\displaystyle\operatorname{P}_{x}^{\otimes
M}(\Delta(\boldsymbol{\mathcal{S}}_{M})>c_{\alpha})$ $\displaystyle\leq$
$\displaystyle\operatorname{P}_{x}^{\otimes
M}\left(DM^{-1/(1+\rho)}+2M^{-1/2}\sup_{\boldsymbol{\mathcal{S}}\in\mathfrak{S}}|\Delta_{M}(\boldsymbol{\mathcal{S}})|>c_{\alpha}\right)$
$\displaystyle\leq$ $\displaystyle\operatorname{P}^{\otimes
M}_{x}\left(\sup_{\boldsymbol{\mathcal{S}}\in\mathfrak{S}}|\Delta_{M}(\boldsymbol{\mathcal{S}})|>c_{\alpha}\sqrt{M}/4\right)$

for large enough $M.$ Theorem 6.1 implies

$\displaystyle\operatorname{P}^{\otimes
M}_{x}\left(\sup_{\boldsymbol{\mathcal{S}}\in\mathfrak{S}}|\Delta_{M}(\boldsymbol{\mathcal{S}})|>c_{\alpha}\sqrt{M}/4\right)\leq
B_{1}\exp(-MB_{2})$

with some constants $B_{1}>0$ and $B_{2}=B_{2}(\alpha)>0.$ Applying Theorem
6.1 to $\mathcal{W}^{\nu}_{2,M}$ and using the fact that $\nu/2\leq
1/(1+\rho)$ for all $0<\rho\leq 1,$ we finally obtain the inequality

$\displaystyle\operatorname{P}^{\otimes
M}_{x}\left(\Delta(\boldsymbol{\mathcal{S}}_{M})>(V/M)^{\nu/2}\right)$
$\displaystyle\leq$ $\displaystyle C\exp(-\sqrt{V}/B_{3})$
$\displaystyle+C\exp\left(-\frac{U\varepsilon_{M}^{-2\rho}}{C^{2}}\right)+B_{1}\exp(-MB_{2})$

which holds for all $V>V_{0}$ and $M>M_{0}$ with some constant $B_{3}$
depending on $\varkappa.$

###  5.2 Proof of Proposition 3.4

For simplicity, we give the proof only for the case $d=2$ (an extension to
higher dimensions is straightforward). In the case of two exercise dates the
corresponding optimal stopping problem is completely specified by the
distribution of the vector $(X_{1},G_{2}(X_{2})).$ Because of a digital
structure of $G_{2}$ the distribution of $(X_{1},G_{2}(X_{2}))$ would be
completely determined if the marginal distribution of $X_{1}$ and the
probability $\operatorname{P}(G_{2}(X_{2})=1|X_{1}=x)$ are defined. Taking
into account this, we now construct a family of distributions for
$(X_{1},G_{2}(X_{2}))$ indexed by elements of the set $\Omega=\\{0,1\\}^{m}.$
First, the marginal distribution of $X_{1}$ is supposed to be the same for all
$\omega\in\Omega$ and posseses a density $p(x)$ satisfying

$0<p_{\ast}\leq p(x)\leq p^{\ast}<\infty,\quad x\in[0,1]^{2}.$

Let us now construct a family of conditional distributions
$\operatorname{P}_{\omega}(G_{2}(X_{2})=1|X_{1}=x)$, $\omega\in\Omega.$ To
this end let $\phi$ be an infinitely many times differentiable function on
$\mathbb{R}$ with the following properties: $\phi(z)=0$ for $|z|\geq 1,$
$\phi(z)\geq 0$ for all $z$ and $\sup_{z\in\mathbb{R}}[\phi(z)]\leq 1.$ For
$j=1,\ldots,m$ put

$\phi_{j}(z):=\delta
m^{-\gamma}\phi\left(m\left[z-\frac{2j-1}{m}\right]\right),\quad
z\in\mathbb{R}$

with some $0<\delta<1.$ For vectors $\omega=(\omega_{1},\ldots,\omega_{m})$ of
elements $\omega_{j}\in\\{0,1\\}$ and for any $z\in\mathbb{R}$ define

$b(z,\omega):=\sum_{j=1}^{m}\omega_{j}\phi_{j}(z).$

Put for any $\omega\in\Omega$ and any $x\in\mathbb{R}^{2},$

$\displaystyle C_{\omega}(x)$ $\displaystyle:=$
$\displaystyle\operatorname{P}_{\omega}(G_{2}(X_{2})=1|X_{1}=x)=$
$\displaystyle=$ $\displaystyle
G_{1}(x)-Am^{-\gamma/\alpha}\mathbf{1}\left\\{0\leq x_{2}\leq
b(x_{1},\omega)\right\\}$
$\displaystyle+Am^{-\gamma/\alpha}\mathbf{1}\left\\{b(x_{1},\omega)<x_{2}\leq\delta
m^{-\gamma}\right\\},$

where $A$ is a positive constant. Due to our assumptions on $G_{1}(x)$, there
are constants $0<G_{-}<G_{+}<1$ such that

$G_{-}\leq G_{1}(x)\leq G_{+},\quad x\in[0,1]^{2}.$

Hence, the constant $A$ can be chosen in such a way that $C_{\omega}(x)$
remains positive and strictly less than $1$ on $[0,1]^{2}$ for any
$\omega\in\Omega.$ The stopping set

$\mathcal{S}_{\omega}:=\left\\{x:C_{\omega}(x)\leq
G_{1}(x)\right\\}=\left\\{(x_{1},x_{2}):0\leq x_{2}\leq
b(x_{1},\omega)\right\\}$

belongs to $\mathfrak{S}_{\gamma}$ since $b(\cdot,\omega)\in\Sigma(\gamma,L)$
for $\delta$ small enough. Moreover, for any $\eta>0$

$\displaystyle\operatorname{P}_{\omega}\left(|G_{1}(X_{1})-C_{\omega}(X_{1})|\leq\eta\right)$
$\displaystyle=$ $\displaystyle\operatorname{P}_{\omega}(0\leq
X_{1}^{2}\leq\delta m^{-\gamma})\mathbf{1}(Am^{-\gamma/\alpha}\leq\eta)$
$\displaystyle\leq$ $\displaystyle\delta
p^{\ast}m^{-\gamma}\mathbf{1}(Am^{-\gamma/\alpha}\leq\eta)\leq\delta
p^{\ast}A^{-\alpha}\eta^{\alpha}$

and the condition (3.10) is fulfilled. Let $\tau_{M}$ be a stopping time
w.r.t. $\mathcal{F}^{\otimes M}$, then the identity (see Lemma 6.2)

$\displaystyle\operatorname{E}_{\operatorname{P}_{\omega}}[G_{\tau^{\ast}}(X_{\tau^{\ast}})]-\operatorname{E}_{\operatorname{P}_{\omega}}[G_{\tau_{M}}(X_{\tau_{M}})]$
$\displaystyle=$ $\displaystyle\newline
\operatorname{E}_{\operatorname{P}_{\omega}}\left[(G_{1}(X_{1})-G_{2}(X_{2}))\mathbf{1}(\tau^{\ast}=1,\tau_{M}=2)\right]\newline
$
$\displaystyle+\operatorname{E}_{\operatorname{P}_{\omega}}\left[(G_{2}(X_{2})-G_{1}(X_{1}))\mathbf{1}(\tau^{\ast}=2,\tau_{M}=1)\right]\newline
$ $\displaystyle=$
$\displaystyle\operatorname{E}_{\operatorname{P}_{\omega}}\left[|G_{1}(X_{1})-\operatorname{E}(G_{2}(X_{2})|\mathcal{F}_{1})|\mathbf{1}\\{\tau_{M}\neq\tau^{\ast}\\}\right]$

leads to

$\operatorname{E}_{\operatorname{P}_{\omega}}[G_{\tau^{\ast}}(X_{\tau^{\ast}})]-\operatorname{E}_{\operatorname{P}_{\omega}^{\otimes
M}}\left\\{\operatorname{E}_{\operatorname{P}_{\omega}}[G_{\tau_{M}}(X_{\tau_{M}})]\right\\}=\operatorname{E}_{\operatorname{P}_{\omega}^{\otimes
M}}\operatorname{E}_{\operatorname{P}_{\omega}}\left[|\Delta_{\omega}(X_{1})|\mathbf{1}\\{\tau_{M}\neq\tau^{\ast}\\}\right]$

with $\Delta_{\omega}(x):=G_{1}(x)-C_{\omega}(x)$. By conditioning on $X_{1}$
we get

$\displaystyle\operatorname{E}_{\operatorname{P}^{\otimes
M}}\operatorname{E}_{\operatorname{P}_{\omega}}\left[|\Delta_{\omega}(X_{1})|\mathbf{1}\\{\tau_{M}\neq\tau^{\ast}\\}\right]$
$\displaystyle=$ $\displaystyle Am^{-\gamma/\alpha}\operatorname{P}(0\leq
X_{1}^{2}\leq\delta m^{-\gamma})\operatorname{P}_{\omega}^{\otimes
M}\left(\tau_{M}\neq\tau^{\ast}\right)$ $\displaystyle\geq$ $\displaystyle
Am^{-\gamma/\alpha}p_{\ast}\delta
m^{-\gamma}\operatorname{P}_{\omega}^{\otimes
M}\left(\tau_{M}\neq\tau^{\ast}\right).$

Using now a well known Birgé’s or Huber’s lemma, (see, e.g. Devroye, Györfi
and Lugosi, 1996, p. 243), we get

$\sup_{\omega\in\\{0,1\\}^{m}}\operatorname{P}_{\omega}^{\otimes
M}(\widehat{\tau}_{M}\neq\tau^{\ast})\geq\left[0.36\wedge\left(1-\frac{MK_{\mathcal{H}}}{\log(\left|\mathcal{H}\right|)}\right)\right],$

where $K_{\mathcal{H}}:=\sup_{P,Q\in\mathcal{H}}K(P,Q),$
$\mathcal{H}:=\\{\operatorname{P}_{\omega},\,\omega\in\\{0,1\\}^{m}\\}$ and
$K(P,Q)$ is a Kullback-Leibler distance between two measures $P$ and $Q$.
Since for any two measures $P$ and $Q$ from $\mathcal{H}$ with $Q\neq P$

$\displaystyle K(P,Q)$ $\displaystyle\leq$
$\displaystyle\sup_{\begin{subarray}{c}\omega_{1},\omega_{2}\in\\{0,1\\}^{m}\\\
\omega_{1}\neq\omega_{2}\end{subarray}}\operatorname{E}\left[C_{\omega_{1}}(X_{1})\log\left\\{\frac{C_{\omega_{1}}(X_{1})}{C_{\omega_{2}}(X_{1})}\right\\}\right.$
$\displaystyle\left.+(1-C_{\omega_{1}}(X_{1}))\log\left\\{\frac{1-C_{\omega_{1}}(X_{1})}{1-C_{\omega_{2}}(X_{1})}\right\\}\right]$
$\displaystyle\leq$ $\displaystyle(1-G_{+}-A)^{-1}(G_{-}-A)^{-1}$
$\displaystyle\times\operatorname{P}(0\leq X_{1}^{2}\leq\delta
m^{-\gamma})\left[A^{2}m^{-2\gamma/\alpha}\right]$ $\displaystyle\leq$
$\displaystyle CMm^{-\gamma-2\gamma/\alpha-1}$

with some constant $C>0$ for small enough $A$, and
$\log(|\mathcal{H}|)=m\log(2)$, we get

$\sup_{\omega\in\\{0,1\\}^{m}}\operatorname{P}_{\omega}^{\otimes
M}(\widehat{\tau}_{M}\neq\tau^{\ast})\geq\left[0.36\wedge\left(1-CMm^{-\gamma-2\gamma/\alpha-1}\right)\right]\quad$

with some constant $C>0.$ Hence,

$\sup_{\omega\in\\{0,1\\}^{m}}\operatorname{P}_{\omega}^{\otimes
M}(\widehat{\tau}_{M}\neq\tau^{\ast})>0$

provided that $m=qM^{1/(\gamma+2\gamma/\alpha+1)}$ for small enough real
number $q>0$. In this case

$\sup_{\omega\in\\{0,1\\}^{m}}\left\\{\operatorname{E}_{\operatorname{P}_{\omega}}[G_{\tau^{\ast}}(X_{\tau^{\ast}})]-\operatorname{E}_{\operatorname{P}_{\omega}^{\otimes
M}}\left\\{\operatorname{E}_{\operatorname{P}_{\omega}}[G_{\tau_{M}}(X_{\tau_{M}})]\right\\}\right\\}\\\
\geq Ap_{\ast}\delta
q^{-\gamma/\alpha-\gamma}M^{-(\gamma/\alpha+\gamma)/(\gamma+2\gamma/\alpha+1)}=BM^{-\frac{(1+\alpha)}{2+\alpha(1+1/\gamma)}}$

with $B=Ap_{\ast}\delta q^{-\gamma/\alpha-\gamma}.$

##  6 Auxiliary results

We have

$\displaystyle\Delta_{M}(\boldsymbol{\mathcal{S}})$ $\displaystyle:=$
$\displaystyle\sqrt{M}\sum_{m=1}^{M}\left\\{g_{\boldsymbol{\mathcal{S}}}(X^{(m)}_{1},\ldots,X^{(m)}_{K})-\operatorname{E}\left[g_{\boldsymbol{\mathcal{S}}}(X_{1},\ldots,X_{K})\right]\right\\}$

with functions
$g_{\boldsymbol{\mathcal{S}}}:\underbrace{\mathbb{R}^{d}\times\ldots\times\mathbb{R}^{d}}_{K}\to\mathbb{R}$
defined as

$g_{\boldsymbol{\mathcal{S}}}(x_{1},\ldots,x_{K}):=\sum_{k=0}^{K-1}G_{k+1}(x_{k+1})\mathbf{1}_{\\{x_{1}\not\in\mathcal{S}_{1},\ldots,x_{k}\not\in\mathcal{S}_{k},x_{k+1}\in\mathcal{S}_{k+1}\\}}.$

Denote
$\mathcal{G}=\\{g_{\boldsymbol{\mathcal{S}}}:\boldsymbol{\mathcal{S}}\in\mathfrak{S}\\}.$
Obviously $\mathcal{G}$ is a class of uniformly bounded functions provided
that all functions $G_{k}$ are uniformly bounded.

#### Definition

Let $\mathcal{N}_{B}(\delta,\mathcal{G},\operatorname{P})$ be the smallest
value of $n$ for which there exist pairs of functions
$\\{[g_{j}^{L},g_{j}^{U}]\\}_{j=1}^{n}$ such that
$\|g_{j}^{U}-g_{j}^{L}\|_{L_{2}(\operatorname{P})}\leq\delta$ for all
$j=1,\ldots,n,$ and such that for each $g\in\mathcal{G},$ there is
$j=j(g)\in\\{1,\ldots,n\\}$ such that

$\displaystyle g_{j}^{L}\leq g\leq g_{j}^{U}.$

Then
$\mathcal{H}_{B}(\delta,\mathcal{G},\operatorname{P})=\log\left[\mathcal{N}_{B}(\delta,\mathcal{G},\operatorname{P})\right]$
is called the entropy with bracketing of $\mathcal{G}$. The following theorem
follows directly from Theorem 5.11 in Van de Geer (2000).

######  Theorem 6.1.

Assume that there exists a constant $A>0$ such that

(6.17) $\displaystyle\mathcal{H}_{B}(\delta,\mathcal{G},\operatorname{P})\leq
A\delta^{-\nu}$

for any $\delta>0$ and some $\nu>0$, where
$\mathcal{H}_{B}(\delta,\mathcal{G},\operatorname{P})$ is the $\delta$-entropy
with bracketing of $\mathcal{G}.$ Fix some
$\boldsymbol{\mathcal{S}}_{0}\in\mathfrak{S}$ then for any $\varepsilon\geq
M^{-1/(2+\nu)}$

$\displaystyle\operatorname{P}\left(\sup_{\boldsymbol{\mathcal{S}}\in\mathfrak{S},\,\|g_{\boldsymbol{\mathcal{S}}}-g_{\boldsymbol{\mathcal{S}}_{0}}\|_{L_{2}(\operatorname{P})}\leq\varepsilon}|\Delta_{M}(\boldsymbol{\mathcal{S}})-\Delta_{M}(\boldsymbol{\mathcal{S}}_{0})|>U\varepsilon^{1-\frac{\nu}{2}}\right)\leq
C\exp(-U\varepsilon^{-\nu}/C^{2}),$
$\displaystyle\operatorname{P}\left(\sup_{\boldsymbol{\mathcal{S}}\in\mathfrak{S},\,\|g_{\boldsymbol{\mathcal{S}}}-g_{\boldsymbol{\mathcal{S}}_{0}}\|_{L_{2}(\operatorname{P})}\leq\varepsilon}\frac{|\Delta_{M}(\boldsymbol{\mathcal{S}})-\Delta_{M}(\boldsymbol{\mathcal{S}}_{0})|}{\|g_{\boldsymbol{\mathcal{S}}}-g_{\boldsymbol{\mathcal{S}}_{0}}\|_{L_{2}(\operatorname{P})}^{1-\nu/2}}>U\right)\leq
C\exp(-U/C^{2}).$

for all $U>C$ and $M>M_{0},$ where $C$ and $M_{0}$ are two positive constants.
Moreover, for any $z>0$

$\displaystyle\operatorname{P}\left(\sup_{\boldsymbol{\mathcal{S}}\in\mathfrak{S}}|\Delta_{M}(\boldsymbol{\mathcal{S}})-\Delta_{M}(\boldsymbol{\mathcal{S}}_{0})|>z\sqrt{M}\right)\leq
C\exp(-Mz^{2}/C^{2}B)$

with some positive constant $B>0$.

Let us define a pseudedistance $\Delta_{X}$ between any two sets
$\boldsymbol{\mathcal{S}},\boldsymbol{\mathcal{S}}^{\prime}\in\mathfrak{B}$ in
the following way

$\Delta_{X}(\mathcal{S}_{1}\times\ldots\times\mathcal{S}_{K},\mathcal{S}^{\prime}_{1}\times\ldots\times\mathcal{S}^{\prime}_{K}):=\sum_{k=1}^{K}\operatorname{P}\left(X_{k}\in(\mathcal{S}_{k}\triangle\mathcal{S}^{\prime}_{k})\setminus\left(\bigcap_{l=k}^{K-1}\mathcal{S}^{\prime}_{l}\right)\right).$

It obviously holds
$\Delta_{X}(\boldsymbol{\mathcal{S}},\boldsymbol{\mathcal{S}}^{\prime})\leq
d_{X}(\boldsymbol{\mathcal{S}},\boldsymbol{\mathcal{S}}^{\prime})$ for the
pseudodistance $d_{X}$ defined in The following Lemma will be frequently used
in the sequel.

######  Lemma 6.2.

For any
$\boldsymbol{\mathcal{S}},\boldsymbol{\mathcal{S}}^{\prime}\in\mathfrak{B}$ it
holds with probability one

(6.18)
$\left|G_{\tau_{k}(\boldsymbol{\mathcal{S}})}\left(X_{\tau_{k}(\boldsymbol{\mathcal{S}})}\right)-G_{\tau_{k}(\boldsymbol{\mathcal{S}}^{\prime})}\left(X_{\tau_{k}(\boldsymbol{\mathcal{S}}^{\prime})}\right)\right|\\\
\leq\sum_{l=k}^{K-1}|G_{l}(X_{l})-G_{\tau_{l+1}(\boldsymbol{\mathcal{S}})}(X_{\tau_{l+1}(\boldsymbol{\mathcal{S}})})|\mathbf{1}_{\left\\{X_{l}\in(\mathcal{S}_{l}\triangle\mathcal{S}^{\prime}_{l})\setminus\left(\bigcap_{l^{\prime}=l}^{K-1}\mathcal{S}^{\prime}_{l^{\prime}}\right)\right\\}}$

and

(6.19)
$V^{*}_{k}(X_{k})-\operatorname{E}\left[G_{\tau_{k}(\boldsymbol{\mathcal{S}})}(X_{\tau_{k}(\boldsymbol{\mathcal{S}})})|\mathcal{F}_{k}\right]\\\
=\operatorname{E}\left[\left.\sum_{l=k}^{K-1}\left|G_{l}(X_{l})-\operatorname{E}[V^{*}_{l+1}(X_{l+1})|\mathcal{F}_{l}]\right|\mathbf{1}_{\left\\{X_{l}\in(\mathcal{S}^{*}_{l}\triangle\mathcal{S}_{l})\setminus\left(\bigcap_{l^{\prime}=l}^{K-1}\mathcal{S}_{l^{\prime}}\right)\right\\}}\right|\mathcal{F}_{k}\right]$

for $k=1,\ldots,K-1$.

###### Proof.

We prove (6.19) by induction. The inequality (6.18) can be proved in a similar
way. For $k=K-1$ we get

(6.20) $V^{*}_{K-1}(X_{K-1})-V_{K-1}(X_{K-1})=\\\
=\operatorname{E}\left[\left.(G_{K-1}(X_{K-1})-G_{K}(X_{K}))\mathbf{1}_{\\{\tau^{*}_{K-1}=K-1,\,\tau_{K-1}=K\\}}\right|\mathcal{F}_{K-1}\right]\\\
+\operatorname{E}\left[\left.(G_{K}(X_{K})-G_{K-1}(X_{K-1}))\mathbf{1}_{\\{\tau^{*}_{K-1}=K,\,\tau_{K-1}=K-1\\}}\right|\mathcal{F}_{K-1}\right]\\\
=|G_{K-1}(X_{K-1})-\operatorname{E}[G_{K}(X_{K})|\mathcal{F}_{K-1}]|\mathbf{1}_{\\{\tau_{K-1}\neq\tau^{*}_{K-1}\\}}$

since events $\\{\tau^{*}_{K-1}=K\\}$ and $\\{\tau_{K-1}=K\\}$ are measurable
w.r.t. $\mathcal{F}_{K-1}$ and
$G_{K-1}(X_{K-1})\geq\operatorname{E}[G_{K}(X_{K})|\mathcal{F}_{K-1}]$ on the
set $\\{\tau^{*}_{K-1}=K-1\\}.$ Thus, (6.19) holds with $k=K-1$. Suppose that
(6.19) holds with $k=K^{\prime}+1$. Let us prove it for $k=K^{\prime}$.
Consider a decomposition

(6.21) $\displaystyle
G_{\tau^{*}_{K^{\prime}}}(X_{\tau^{*}_{K^{\prime}}})-G_{\tau_{K^{\prime}}}(X_{\tau_{K^{\prime}}})$
$\displaystyle=$ $\displaystyle S_{1}+S_{2}+S_{3}$

with

$\displaystyle S_{1}$ $\displaystyle:=$
$\displaystyle\left(G_{\tau^{*}_{K^{\prime}}}(X_{\tau^{*}_{K^{\prime}}})-G_{\tau_{K^{\prime}}}(X_{\tau_{K^{\prime}}})\right)\mathbf{1}_{\\{\tau^{*}_{K^{\prime}}>K^{\prime},\,\tau_{K^{\prime}}>K^{\prime}\\}},$
$\displaystyle S_{2}$ $\displaystyle:=$
$\displaystyle\left(G_{\tau^{*}_{K^{\prime}}}(X_{\tau^{*}_{K^{\prime}}})-G_{\tau_{K^{\prime}}}(X_{\tau_{K^{\prime}}})\right)\mathbf{1}_{\\{\tau^{*}_{K^{\prime}}>K^{\prime},\,\tau_{K^{\prime}}=K^{\prime}\\}},$
$\displaystyle S_{3}$ $\displaystyle:=$
$\displaystyle\left(G_{\tau^{*}_{K^{\prime}}}(X_{\tau^{*}_{K^{\prime}}})-G_{\tau_{K^{\prime}}}(X_{\tau_{K^{\prime}}})\right)\mathbf{1}_{\\{\tau^{*}_{K^{\prime}}=K^{\prime},\,\tau_{K^{\prime}}>K^{\prime}\\}}.$

Using the fact that $\tau_{k}=\tau_{k+1}$ if $\tau_{k}>k$ for any
$k=1,\ldots,K-1$, we get

$\displaystyle\operatorname{E}\left[S_{1}|\mathcal{F}_{K^{\prime}}\right]$
$\displaystyle=$
$\displaystyle\operatorname{E}\left[\left.\left(V^{*}_{K^{\prime}+1}(X_{K^{\prime}+1})-V_{K^{\prime}+1}(X_{K^{\prime}+1})\right)\mathbf{1}_{\\{\tau^{*}_{K^{\prime}}>K^{\prime},\,\tau_{K^{\prime}}>K^{\prime}\\}}\right|\mathcal{F}_{K^{\prime}}\right],$
$\displaystyle\operatorname{E}\left[S_{2}|\mathcal{F}_{K^{\prime}}\right]$
$\displaystyle=$
$\displaystyle\left(\operatorname{E}\left[\left.G_{\tau^{*}_{K^{\prime}+1}}(X_{\tau^{*}_{K^{\prime}+1}})\right|\mathcal{F}_{K^{\prime}}\right]-G_{K^{\prime}}(X_{K^{\prime}})\right)\mathbf{1}_{\\{\tau^{*}_{K^{\prime}}>K^{\prime},\,\tau_{K^{\prime}}=K^{\prime}\\}}$
$\displaystyle=$
$\displaystyle\left(\operatorname{E}\left[\left.V^{*}_{K^{\prime}+1}(X_{K^{\prime}+1})\right|\mathcal{F}_{K^{\prime}}\right]-G_{K^{\prime}}(X(t_{K^{\prime}}))\right)\mathbf{1}_{\\{\tau^{*}_{K^{\prime}}>K^{\prime},\,\widehat{\tau}_{K^{\prime}}=K^{\prime}\\}}$

and

$\displaystyle\operatorname{E}\left[S_{3}|\mathcal{F}_{K^{\prime}}\right]$
$\displaystyle=$
$\displaystyle\left(G_{K^{\prime}}(X_{K^{\prime}})-\operatorname{E}\left[G_{\tau_{K^{\prime}+1}}(X_{\tau_{K^{\prime}+1}})|\mathcal{F}_{K^{\prime}}\right]\right)\mathbf{1}_{\\{\tau^{*}_{K^{\prime}}=K^{\prime},\,\tau_{K^{\prime}}>K^{\prime}\\}}$
$\displaystyle=$
$\displaystyle\left(G_{K^{\prime}}(X_{K^{\prime}})-\operatorname{E}[V^{*}_{K^{\prime}+1}(X_{K^{\prime}+1})|\mathcal{F}_{K^{\prime}}]\right)\mathbf{1}_{\\{\tau^{*}_{K^{\prime}}=K^{\prime},\,\tau_{K^{\prime}}>K^{\prime}\\}}$
$\displaystyle+\operatorname{E}\left[\left.\left(V^{*}_{K^{\prime}+1}(X_{K^{\prime}+1})-V_{K^{\prime}+1}(X_{K^{\prime}+1})\right)\mathbf{1}_{\\{\tau^{*}_{K^{\prime}}=K^{\prime},\,\tau_{K^{\prime}}>K^{\prime}\\}}\right|\mathcal{F}_{K^{\prime}}\right],$

with probability one. Hence

$\displaystyle
V^{*}_{K^{\prime}}(X_{K^{\prime}})-V_{K^{\prime}}(X_{K^{\prime}})$
$\displaystyle=$
$\displaystyle\left|G_{K^{\prime}}(X_{K^{\prime}})-\operatorname{E}[V^{*}_{K^{\prime}+1}(X_{K^{\prime}+1})|\mathcal{F}_{K^{\prime}}]\right|\mathbf{1}_{\\{\tau_{K^{\prime}}\neq\tau^{*}_{K^{\prime}}\\}}$
$\displaystyle+\operatorname{E}\left[\left.\left(V^{*}_{K^{\prime}+1}(X_{K^{\prime}+1})-V_{K^{\prime}+1}(X_{K^{\prime}+1})\right)\right|\mathcal{F}_{K^{\prime}}\right]\mathbf{1}_{\\{\tau_{K^{\prime}}>K^{\prime}\\}}$

since
$G_{K^{\prime}}(X_{K^{\prime}})-\operatorname{E}[V^{*}_{K^{\prime}+1}(X_{K^{\prime}+1})\geq
0$ on the set $\\{\tau^{*}_{K^{\prime}}=K^{\prime}\\}.$ Our induction
assumption implies now that

$V_{K^{\prime}}^{*}(X_{K^{\prime}})-V_{K^{\prime}}(X_{K^{\prime}})=\\\
\operatorname{E}\left[\sum_{k=K^{\prime}}^{K-1}|G_{l}(X_{l})-\operatorname{E}[V^{*}_{l+1}(X_{l+1})|\mathcal{F}_{l}]|\mathbf{1}_{\\{\tau_{k}\neq\tau^{*}_{k},\tau_{k}>k,\ldots,\tau_{K-1}>K-1\\}}|\mathcal{F}_{K^{\prime}}\right]$

and hence (6.19) holds with $k=K^{\prime}$. ∎

######  Corollary 6.3.

If $\max_{k=1,\ldots,K}\|G_{k}\|_{\infty}<A_{G}$ with some constant $A_{G}>0$,
then

$\displaystyle\Delta_{G}(\boldsymbol{\mathcal{S}},\boldsymbol{\mathcal{S}}^{\prime})\leq
2A_{G}\sqrt{2\Delta_{X}(\boldsymbol{\mathcal{S}},\boldsymbol{\mathcal{S}}^{\prime})}$

for any
$\boldsymbol{\mathcal{S}},\boldsymbol{\mathcal{S}}^{\prime}\in\mathfrak{B}.$

###### Proof.

Follows directly from (6.18) since $G_{\tau}(X_{\tau})\leq A_{G}$ a.s. for any
stopping time $\tau$ taking values in $\\{1,\ldots,K\\}.$ ∎

######  Corollary 6.4.

Assume that (3.10) holds for $\delta<\delta_{0}<1/2$, then there exist
constants $\upsilon_{\alpha}$ and $\delta_{\alpha}$ such that

(6.22)
$\displaystyle\Delta(\boldsymbol{\mathcal{S}})\geq\upsilon_{\alpha}\Delta^{(1+\alpha)/\alpha}_{X}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})$

for all $\boldsymbol{\mathcal{S}}\in\mathfrak{B}$ satisfying
$\Delta_{X}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})\leq\delta_{\alpha}$.
Moreover it holds

(6.23)
$\displaystyle\Delta_{X}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})\leq\left(\frac{2^{1/\alpha}}{\delta_{0}}\right)\Delta(\boldsymbol{\mathcal{S}})+\frac{\delta_{\alpha}}{2(1+\alpha)}.$

for any $\boldsymbol{\mathcal{S}}\in\mathfrak{B}.$

###### Proof.

For any $\delta\leq\delta_{0}$ define the sets

$\mathcal{A}_{k}:=\left\\{x\in\mathbb{R}^{d}:\left|\operatorname{E}[V^{*}_{k+1}(X_{k+1})|X_{k}=x]-G_{k}(x)\right|>\delta\right\\},\quad
k=1,\ldots,K-1.$

Due to (6.19) we have

(6.24) $\displaystyle\Delta(\boldsymbol{\mathcal{S}})$ $\displaystyle\geq$
$\displaystyle\delta\sum_{k=1}^{K-1}\operatorname{P}\left(X_{k}\in(\mathcal{S}^{*}_{k}\triangle\mathcal{S}_{k})\setminus\left(\bigcap_{l=k}^{K-1}\mathcal{S}_{k}\right)\bigcap\mathcal{A}_{k}\right)$
$\displaystyle\geq$
$\displaystyle\delta\sum_{k=1}^{K-1}\left\\{\operatorname{P}\left(X_{k}\in(\mathcal{S}^{*}_{k}\triangle\mathcal{S}_{k})\setminus\left(\bigcap_{l=k}^{K-1}\mathcal{S}_{k}\right)\right)-\operatorname{P}(\bar{\mathcal{A}}_{k})\right\\}$
$\displaystyle\geq$
$\displaystyle\delta[\Delta_{X}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})-A_{0}\delta^{\alpha}]$

with $A_{0}=\sum_{k=1}^{K-1}A_{k,0},$ where $A_{k,0}$ were defined in (3.10).
The maximum of (6.24) is attained at
$\delta^{*}=[\Delta_{X}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})/(\alpha+1)A_{0}]^{1/\alpha}$.
Since $\delta^{*}\leq\delta_{0}$ for
$\Delta_{X}(\boldsymbol{\mathcal{S}}^{*},\boldsymbol{\mathcal{S}})\leq
A_{0}(\alpha+1)\delta^{\alpha}_{0}$ the inequality (6.22) holds with
$\upsilon_{\alpha}:=A_{0}^{-1/\alpha}\alpha(1+\alpha)^{-1-1/\alpha}$ and
$\delta_{\alpha}:=A_{0}(\alpha+1)\delta^{\alpha}_{0}$. The inequality (6.23)
follows directly from (6.24) by taking $\delta=\delta_{0}/2^{1/\alpha}.$ ∎

## References

  * Andersen (2000) L. Andersen (2000). A simple approach to the pricing of Bermudan swaptions in the multi-factor Libor Market Model. Journal of Computational Finance, 3, 5-32.
  * Belomestny (2009) D. Belomestny (2009). Pricing Bermudan options using nonparametric regression: optimal rates of convergence for lower estimates, http://arxiv.org/abs/0907.5599, forthcoming in Finance and Stochastics.
  * Broadie and Glasserman (1997) M. Broadie and P. Glasserman (1997). Pricing American-style securities using simulation. J. of Economic Dynamics and Control, 21, 1323-1352.
  * Broadie and Detemple (1997) M. Broadie and J. Detemple (1997). The valuation of American options on multiple assets. Mathematical Finance, 7(3), 241-286.
  * Carriere (1996) J. Carriere (1996). Valuation of early-exercise price of options using simulations and nonparametric regression. Insuarance: Mathematics and Economics, 19, 19-30.
  * Devroye, Györfi and Lugosi (1996) L. Devroye, L. Györfi and G. Lugosi (1996). A probabilistic theory of pattern recognition. Application of Mathematics (New York), 31, Springer.
  * Dudley (1999) R.M. Dudley (1999). Uniform central limit theorems. Cambridge University Press.
  * Egloff (2005) D. Egloff (2005). Monte Carlo algorithms for optimal stopping and statistical learning. Ann. Appl. Probab., 15, 1396-1432.
  * Egloff, Kohler and Todorovic (2007) D. Egloff, M. Kohler and N. Todorovic (2007). A dynamic look-ahead Monte Carlo algorithm for pricing Bermudan options, Ann. Appl. Probab., 17, 1138-1171.
  * Garcia (2001) D. Garcia (2001). Convergence and biases of Monte Carlo estimates of American option prices using a parametric exercise rule. Working paper.
  * Glasserman (2003) P. Glasserman (2003). Monte Carlo Methods in Financial Engineering. Springer.
  * Kleywegt, Shapiro and Homem-de-Mello (2001) A.J. Kleywegt, A. Shapiro and T. Homem-de-Mello (2001). The sample average approximation method for stochastic discrete optimization, SIAM J. Optim., 12, 479-502.
  * Longstaff and Schwartz (2001) F. Longstaff and E. Schwartz (2001). Valuing American options by simulation: a simple least-squares approach. Review of Financial Studies, 14, 113-147.
  * Mammen and Tsybakov (1999) E. Mammen and A. Tsybakov (1999). Smooth discrimination analysis. Ann. Statist., 27, 1808-1829.
  * Peskir and Shiryaev (2006) G. Peskir and A. Shiryaev (2006). Optimal Stopping and Free-Boundary Problems. LM - Lectures in Mathematics ETH Z rich.
  * Shapiro (1993) A. Shapiro (1993). Asymptotic behavior of optimal solutions in stochastic programming, Math. Oper. Res., 18, 829-845.
  * Shapiro and Homem-de-Mello (2000) A. Shapiro and T. Homem-de-Mello (2000). On the rate of convergence of optimal solutions of Monte Carlo approximations of stochastic programs. SIAM J. Optim., 11(1), 70-86.
  * Snell (1952) J. L. Snell (1952). Applications of martingale system theorems. Trans. Amer. Math. Soc. 73, 293–312.
  * Tsitsiklis and Van Roy (1999) J. Tsitsiklis and B. Van Roy (1999). Regression methods for pricing complex American style options. IEEE Trans. Neural. Net., 12, 694-703.
  * Van de Geer (2000) S. Van de Geer (2000). Applications of Empirical Process Theory. Cambridge Univ. Press.