Guan and Mišić

Randomized Policy Optimization for Optimal Stopping

Randomized Policy Optimization for Optimal Stopping

Xinyi Guan UCLA Anderson School of Management, University of California, Los
Angeles, California 90095, United States<EMAIL_ADDRESS>Velibor V. Mišić UCLA Anderson School of Management, University of California,
Los Angeles, California 90095, United States<EMAIL_ADDRESS>
Optimal stopping is the problem of determining when to stop a stochastic
system in order to maximize reward, which is of practical importance in
domains such as finance, operations management and healthcare. Existing
methods for high-dimensional optimal stopping that are popular in practice
produce deterministic linear policies – policies that deterministically stop
based on the sign of a weighted sum of basis functions – but are not
guaranteed to find the optimal policy within this policy class given a fixed
basis function architecture. In this paper, we propose a new methodology for
optimal stopping based on _randomized_ linear policies, which choose to stop
with a probability that is determined by a weighted sum of basis functions. We
motivate these policies by establishing that under mild conditions, given a
fixed basis function architecture, optimizing over randomized linear policies
is equivalent to optimizing over deterministic linear policies. We formulate
the problem of learning randomized linear policies from data as a smooth non-
convex sample average approximation (SAA) problem. We theoretically prove the
almost sure convergence of our randomized policy SAA problem and establish
bounds on the out-of-sample performance of randomized policies obtained from
our SAA problem based on Rademacher complexity. We also show that the SAA
problem is in general NP-Hard, and consequently develop a practical heuristic
for solving our randomized policy problem. Through numerical experiments on a
benchmark family of option pricing problem instances, we show that our
approach can substantially outperform state-of-the-art methods.

optimal stopping, approximate dynamic programming, randomization, non-convex
optimization, option pricing.

##  1 Introduction

Optimal stopping is the problem of deciding at what time to stop a stochastic
system in order to maximize the expected reward. Specifically, we are given a
stochastic system, that starts at an initial state and transitions randomly
from one state to another in discrete time, and a reward function, which maps
each state at each time to a real value. In each period, we must decide
whether to stop the system, or allow it to continue for one more period. If we
choose to stop the system, we obtain the reward given by the reward function
for the current state; otherwise, we obtain no reward, but we may potentially
stop the system at a later period for a higher reward. Our goal is to find a
policy, which is a mapping from the state at each period to the decision to
stop or continue, so as to maximize the expected reward.

Optimal stopping problems are found in many application domains, such as
finance, operations and healthcare. For example, in finance, an important
application of optimal stopping is the problem of option pricing. In this
problem, an option holder has the right to buy an asset (if it is a call
option) or to sell an asset (if it is a put option) at some strike price. The
stochastic system corresponds to the asset, and the system state corresponds
to the asset’s current price. The option holder’s problem is to decide when to
exercise the option, which is akin to stopping, so as to garner the greatest
expected payoff. The price that an option writer should charge for the option
is exactly the highest expected payoff that one can obtain from an optimal
exercise policy of the option. As another example, in operations management,
consider a firm that needs to decide when to introduce a new product to a
market. In this problem, the system corresponds to market conditions, and the
system state would correspond to (say) the unit production cost and the
predicted market share that the product would capture, which evolve
stochastically over time as more and more competitors enter this market. At
each period, the firm can decide to introduce the product into the market,
which corresponds to stopping the system, and the reward corresponds to the
profit obtained from this market. The problem is then to find a policy that
determines whether to introduce the product or wait, so as to maximize the
profit from introducing the product.

High-dimensional optimal stopping problems can in theory be solved exactly by
dynamic programming. This approach involves obtaining the optimal value
function, which maps the state at each period to the highest possible expected
reward that can be attained conditional on starting at that state in that
period, or the optimal continuation value function, which maps the state at
each period to the highest possible expected reward that can be attained
conditional on choosing to continue out of that state in that period. An
optimal policy can then be found by considering the greedy policy with respect
to the optimal value function or optimal continuation value function. However,
this approach is untenable in practice for high-dimensional optimal stopping
problems due to the curse of dimensionality.

As a result, a number of approaches based on approximate dynamic programming
(ADP) have been proposed to solve high-dimensional optimal stopping problems,
wherein one considers a policy that is greedy with respect to an approximate
value function or continuation value function. Of these methods, the most
prevalent ADP method is the least squares Monte Carlo (LSM) approach proposed
by Longstaff and Schwartz (2001). This approach involves simulating a set of
sample paths or trajectories of the system, and then iterating from the last
period in the horizon to the first. At each period $t$, one uses least squares
to obtain a regression model that predicts the continuation value based on the
current state, using the sample of trajectories. One then compares the
prediction with the reward from stopping in the current period in each
trajectory. If the reward from stopping is higher than the predicted
continuation value, we choose to stop; otherwise, we choose to continue. Based
on this decision, we update the continuation value, and we repeat the process
again at period $t-1$. The algorithm continues in this way, until we reach the
first period. The resulting policy is then to take the action that is greedy
with respect to the approximate continuation value function.

From a theoretical standpoint, if one were given an infinite sample of
trajectories and one could solve the least squares problem at each stage of
the LSM algorithm over an unrestricted function class, then the regression
model that one would obtain would exactly coincide with the optimal
continuation value function. This is due to the fact that the conditional
expectation function $m(x)=\mathbb{E}[Y\mid X=x]$ minimizes squared error,
i.e., it solves the optimization problem $\min_{m}\mathbb{E}[(Y-m(X))^{2}]$.
In such an idealized situation, the policy produced by LSM would indeed be
optimal.

In practice, one must work with a finite sample of trajectories, and the
regression function is constrained to be within the span of a finite
collection of basis functions that are specified by the decision maker. Thus,
the policy that is produced by LSM is a policy in which one decides to stop or
continue by comparing the reward to a weighted sum of basis functions. This is
significant for two reasons: (i) it is no longer the case that the policy
produced by LSM is an optimal policy; and (ii) even when we restrict our focus
to the corresponding policy class that LSM operates in – policies that stop if
and only if the reward is greater than a weighted combination of basis
functions – the policy produced by LSM may not be optimal within that class.
This occurs because in LSM, the approximate continuation value function is
obtained by minimizing squared loss, which does not account for the fact that
this approximation will be used as part of a policy, and ultimately does not
guarantee good out-of-sample policy performance.

This motivates the following question: _how can one obtain LSM-like policies
that perform better than LSM_? The policy produced by LSM belongs to a broader
family of policies that we refer to as _deterministic linear policies_ :
policies that deterministically recommend to stop or continue at each period
depending on whether a weighted sum of basis functions is positive or
negative. (This class subsumes LSM policies if one includes the immediate
reward at each period as a basis function.) Given a sample of trajectories, an
immediate approach to obtaining a good policy from this class would be to
formulate a sample average approximation (SAA) problem: optimize over the
weights defining the deterministic linear policy, so as to maximize the sample
average estimate of the expected reward of the policy. The drawback of this
approach is that due to the discrete nature of how this family of policies
works, the SAA problem is a challenging discrete optimization problem. Such a
problem would be infeasible to solve for the sample sizes that are typically
found in practical optimal stopping applications.

As an alternative to deterministic linear policies, one can also consider
_randomized linear policies_. These are policies that probabilistically choose
to stop or continue at each period, where the probability of stopping is given
by a logistic probability and the logit that defines this probability is a
weighted sum of basis functions. Just like the deterministic linear policy
case, one can also formulate an SAA problem to maximize the sample average
reward with respect to the weights that define this randomized policy.
Although the resulting SAA problem is still a challenging non-convex problem,
the objective function is now smooth and from a computational standpoint, one
can now at least solve the problem heuristically using any of a number of
practically successful gradient-based methods.

In this paper, we propose a new methodology for solving optimal stopping
problems from data that is based on optimizing over the class of randomized
linear policies. We make the following specific contributions:

  1. 1.

Model: We propose the class of randomized linear policies for optimal stopping
problems, and formulate the problem of learning such a policy from data as an
SAA problem with a smooth, non-convex objective function. We prove that under
mild conditions, solving the randomized linear policy SAA problem is
equivalent to solving the deterministic linear policy SAA problem, in that the
optimal objectives of the two problems are equivalent; under an additional
condition, we also show that the true randomized linear policy problem and the
true deterministic linear policy problem, where sample averages are replaced
by expectations, are also equivalent in objective value.

  2. 2.

Statistical guarantees: We provide two statistical guarantees for our
randomized policy SAA problem. First, we show that our learning problem is
consistent: as the number of trajectories in our training sample grows, the
optimal objective value and optimal solution converge almost surely to the
optimal objective value and optimal solution set, respectively, of the true
stochastic optimization problem, where sample averages are replaced with
expectations. Second, we develop a generalization bound on the out-of-sample
objective value of a randomized policy obtained from our SAA problem based on
Rademacher complexity, and develop several different bounds on the Rademacher
complexity for different choices of the set of feasible weights.

  3. 3.

Heuristic: We prove that in general, our randomized policy SAA problem is NP-
Hard, which follows from a reduction from the MAX-3SAT problem. Consequently,
we propose a backward optimization algorithm for solving the problem
heuristically, which optimizes the weights defining the randomized policy in
stages, starting with the weights corresponding to the last period and working
its way to the first stage.

  4. 4.

Numerical experiments: Using a benchmark family of Bermudan max-call option
pricing instances used in the recent literature, we show that our approach
yields policies that in general are substantially better than policies
produced by LSM, and are as good or better than policies produced by the
pathwise optimization method (Desai et al. 2012), a state-of-the-art method
based on martingale duality.

The rest of this paper is organized as follows. In Section 2, we review the
relevant literature in optimal stopping, as well as other recent related work.
In Section 3, we formally define the optimal stopping problem, define the
deterministic linear policy problem in its sample average and true stochastic
forms, define the randomized linear policy problem in its sample average and
true stochastic forms, and prove that the randomized linear policy problem and
deterministic linear problem are equivalent. In Section 4, we prove that our
randomized policy SAA problem is consistent and develop our generalization
guarantees. In Section 5, we show that our randomized policy SAA problem is
NP-Hard, and present our backward optimization algorithm for solving it. In
Section 6, we present the results of our numerical study on option pricing
instances. Lastly, in Section 7, we conclude and discuss some potential
directions for future research.

##  2 Literature Review

Our paper is closely related to three streams of research: the optimal
stopping and ADP literature; prediction-and-optimization literature; and non-
convex optimization literature.

Optimal stopping and approximate dynamic programming (ADP). Optimal stopping
problems have been extensively studied in many fields such as statistics,
operations research and mathematical finance. In theory, optimal stopping
problems can be solved by dynamic programming, but in practice, the curse of
dimensionality renders this approach infeasible for all but the simplest
optimal stopping problems. As a result, there has been much attention towards
developing good approximate dynamic programming (ADP) methods for optimal
stopping.

In the context of optimal stopping, the most popular family of ADP methods is
that of simulation-regression. The idea of simulation-regression methods is to
simulate a sample of trajectories of the system state and use least squares
regression to approximate the optimal continuation value function (i.e., the
optimal expected reward from choosing to continue for a given current state)
at each step. The paper of Carriere (1996) was the first to introduce this
type of approach for the valuation of American options, using non-parametric
regression; later, Longstaff and Schwartz (2001) and Tsitsiklis and Van Roy
(2001) independently considered this approach in the setting where the
continuation value function is approximated as a linear combination of basis
functions.

Besides simulation-regression, another important stream of ADP methods for
optimal stopping is based on the idea of martingale duality. The main idea in
this body of work is to relax the non-anticipativity of the policy, but to
then penalize the use of future information through a martingale process. In
doing so, one obtains an upper bound on the optimal reward, and in some cases
one can also obtain policies that perform well. We refer the reader to Rogers
(2002), Andersen and Broadie (2004), Haugh and Kogan (2004), Chen and
Glasserman (2007), Brown et al. (2010), Desai et al. (2012) for salient
examples of this methodology, and to the recent review paper of Brown and
Smith (2022) for a detailed overview of this technique as it applies to
stochastic dynamic programming more broadly.

Lastly, other recent research has considered approaches distinct from the
above two streams. The paper of Ciocan and Mišić (2022) considers a method for
directly obtaining optimal stopping policies from a sample of trajectories in
the form of a binary tree. In a different direction, the paper of Sturt (2021)
proposes a method for obtaining threshold policies for low-dimensional optimal
stopping problems using robust optimization.

Our methodology is most closely related to the simulation-regression approach
and in particular, the least-squares Monte Carlo (LSM) approach of Longstaff
and Schwartz (2001). There are several differences between our methodology and
LSM. One difference is that our methodology involves the use of randomized
policies, whereas the policy produced by LSM is deterministic. Aside from
this, the key philosophical difference between our work and the LSM approach
is that while LSM produces a policy in an indirect way – by approximating the
continuation value function using least squares – our methodology involves
formulating an SAA problem and obtaining a policy that _directly_ maximizes an
estimate of the expected reward obtained with respect to a sample of
trajectories. In terms of algorithms, the backward algorithm for heuristically
solving our SAA problem that we present in Section 5 is reminiscent of the LSM
algorithm, but instead of solving a least squares problem, one solves a non-
convex problem where the objective function is given by a weighted sum of
logistic response functions.

Predict-then-optimize. Outside of optimal stopping, our paper relates to the
literature on combining prediction and optimization. In many analytics
problems, the “predict-then-optimize” paradigm is often used: one first builds
a predictive model by minimizing a loss function that measures predictive
performance (for example, squared error), and then utilizes that predictive
model in a subsequent optimization problem to obtain a decision. There are
many papers that apply this type of approach (see, for example, Ferreira et
al. 2016, Cohen et al. 2017, Bertsimas and Kallus 2020).

However, as pointed out in the recent paper of Elmachtoub and Grigas (2021),
this type of predict-then-optimize paradigm can lead to suboptimal decisions,
since the predictive model is trained using a loss function that does not
account for how the predictive model will be used in the downstream
optimization problem. The paper of Elmachtoub and Grigas (2021) proposes a
Smart Predict-then-Optimize (SPO) framework, where the predictive model is
estimated so as to minimize decision/prescriptive loss rather than predictive
loss, and numerically shows that the SPO framework can result in significantly
better out-of-sample performance.

Our paper is partially inspired by the observation that the LSM algorithm
bears a resemblance to the standard predict-then-optimize paradigm. In the LSM
approach, one first predicts the continuation value based on squared error and
then uses that prediction within a greedy policy. However, minimizing squared
error does not necessarily translate into good prescriptive performance of the
prediction model. Therefore, in order to find a good policy, we consider the
problem of directly optimizing in-sample reward over the space of randomized
linear policies.

Non-convex optimization. Lastly, our paper is related to the growing
literature on non-convex optimization. In the machine learning community,
there has been considerable interest in how to solve non-convex optimization
problems, since many learning tasks can be naturally expressed as non-convex
optimization problems. Since non-convex optimization problems are in general
NP-Hard, a popular approach for tackling such problems is based on convex
relaxation, where one relaxes the problem in some way to obtain a convex
problem that is more tractable. However, as pointed out by Jain and Kar
(2017), such convex relaxations generally change the problem drastically, and
thus the solution of relaxation can perform poorly for the original problem.
Because of this, there has been much recent work on directly solving the non-
convex problems via approximate algorithms. Efficient techniques used in non-
convex optimization approach include generalized projected gradient descent
(Candes et al. 2015), generalized alternating minimization (Netrapalli et al.
2015), and stochastic optimization techniques (Ge et al. 2015). Although these
approaches are not guaranteed to find the global optimum in general, it has
been empirically observed that approximately optimal solutions to the true
non-convex problem are often better than exactly optimal solutions to a convex
relaxation of the problem (Jain and Kar 2017).

In our paper, the optimal stopping problem of learning randomized policies
from sample data is formulated as a non-convex optimization problem. We follow
the spirit of non-convex optimization approaches and propose a backward
optimization heuristic to directly work with this non-convex problem, which
sequentially optimizes over the weights in each time period. In our
implementation of this method, the weights in each time period are
approximately optimized using the Adam algorithm (Kingma and Ba 2014), a
first-order method that is widely used for non-convex optimization problems,
particularly those arising in the training of deep neural networks. Although
our heuristic is not guaranteed to find a globally optimal solution, we find
numerically that the resulting policies can significantly outperform those
obtained by LSM.

##  3 Problem Definition

In this section, we begin by defining our optimal stopping problem (Section
3.1). We then define the family of deterministic linear policies, and the
problems of optimizing over deterministic linear policies given complete
knowledge of the stochastic process (Section 3.2) and given a sample of
trajectories (Section 3.3). In Section 3.4, we define the family of randomized
linear policies and analogously to the deterministic linear policy case, we
define the true stochastic optimization problem for this policy class and its
finite sample counterpart. Finally, in Section 3.5, we state our main
equivalence results, which assert that (i) the sample average approximation
problems over deterministic and randomized linear policies are equivalent and
(ii) the true stochastic optimization problems over deterministic and
randomized linear policies are equivalent.

###  3.1 Optimal stopping problem

We consider a stochastic system that evolves over a discrete time horizon of
$T$ periods. Each period is denoted by $t$, and ranges in $[T]$, where we use
the notation $[n]$ to denote the set $\\{1,\dots,n\\}$ for any integer $n$. We
use $\mathbf{x}$ to denote the state of the system, and $\mathbf{x}(t)$ to
denote the state of the system in each period, which belongs to a state space
$\mathcal{X}$. At each period, we can choose to stop the system or to continue
for one more period. If we choose to stop, we receive a nonnegative reward
$g(t,\mathbf{x})$ that is a function of the period $t$ and the current state
$\mathbf{x}$. If we continue, we do not receive a reward. The action space of
the problem is therefore $\mathcal{A}=\\{\textbf{stop},\textbf{continue}\\}$.

The decision maker has the ability to specify a deterministic policy
$\pi:[T]\times\mathcal{X}\to\mathcal{A}$, which is a mapping from the current
period and state we are in to one of the two actions. The policy $\pi$ defines
a stopping time $\tau_{\pi}$, which is a random variable that represents the
time in $[T]$ at which the decision maker stops:

$\tau_{\pi}=\min\\{t\in[T]\mid\pi(t,\mathbf{x}(t))=\textbf{stop}\\}.$ (1)

We denote the case that the system is never stopped by $\tau_{\pi}=+\infty$,
and we assume that the reward is zero in this case, i.e.,
$g(+\infty,\mathbf{x})=0$ for all $\mathbf{x}\in\mathcal{X}$.

Letting $\Pi$ denote the set of all policies, the decision maker’s goal is to
specify the policy $\pi$ that maximizes the expected discounted reward, which
can be written as the following optimization problem:

$\underset{\pi\in\Pi}{\text{supremum}}\
\mathbb{E}[g(\tau_{\pi},\mathbf{x}(\tau_{\pi}))].$ (2)

We make two important remarks regarding our optimal stopping problem (2).
First, we note that our formulation does not include a discount factor, which
is common in the optimal stopping literature. Our motivation for this modeling
choice was to simplify the mathematical exposition and to make certain
expressions that appear later on less cumbersome. We also note that this is
not a restrictive modeling choice, as the reward function $g$ is time
dependent, and so one can specify it so as to incorporate discounting. Second,
for the entirety of the paper, we shall assume that $g$ is uniformly bounded,
which we formalize in the following assumption.

There exists a finite upper bound $\bar{G}$ such that for any $t\in[T]$,
$\mathbf{x}\in\mathcal{X}$, $0\leq g(t,\mathbf{x})\leq\bar{G}$.

###  3.2 Deterministic linear policies

The optimal stopping problem (2) is a challenging problem to solve because the
set of policies is unrestricted. Rather than working with the set of all
policies, we will consider the set of policies that can be described using a
linear combination of basis functions. Specifically, let us define
$\phi_{1},\dots,\phi_{K}:\mathcal{X}\to\mathbb{R}$ to be a collection of basis
functions, which map a state to a real number; for convenience, we will use
$\Phi(\mathbf{x})=(\phi_{1}(\mathbf{x}),\dots,\phi_{K}(\mathbf{x}))$ to denote
the vector of basis functions. Let us also define
$\mathbf{b}_{t}=(b_{t,1},\dots,b_{t,K})\in\mathbb{R}^{K}$ to be a
$K$-dimensional vector of weights corresponding to the policy at period
$t\in[T]$, and additionally, let us use $\mathbf{b}$ to denote the collection
of $\mathbf{b}_{t}$ vectors, i.e.,
$\mathbf{b}=(\mathbf{b}_{1},\dots,\mathbf{b}_{T})$. We can then define the
policy $\pi_{\mathbf{b}}$ as the policy that recommends stopping whenever the
weighted combination of basis functions, where the weights come from
$\mathbf{b}$, is positive:

$\pi_{\mathbf{b}}(t,\mathbf{x})=\left\\{\begin{array}[]{llll}\textbf{stop}&&&\text{if}\
\sum_{k=1}^{K}b_{t,k}\phi_{k}(\mathbf{x}(t))>0,\\\
\textbf{continue}&&&\text{otherwise}.\end{array}\right.$ (3)

We let $\mathcal{B}\subseteq\mathbb{R}^{KT}$ be the set of feasible weight
vectors, and let $\Pi_{\mathcal{B}}$ be the corresponding set of linear
policies:

$\Pi_{\mathcal{B}}=\\{\pi_{\mathbf{b}}\mid\mathbf{b}\in\mathcal{B}\\}.$

The linear policy optimal stopping problem can then be written as:

$\underset{\pi\in\Pi_{\mathcal{B}}}{\text{supremum}}\
\mathbb{E}[g(\tau_{\pi},\mathbf{x}(\tau_{\pi}))].$ (4)

Note that we can re-write this problem without the use of the stopping time
$\tau_{\pi}$, and to make the dependence on $\mathbf{b}$ more explicit, as
follows:

$\underset{\mathbf{b}\in\mathcal{B}}{\text{supremum}}\
\mathbb{E}\left[\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))\leq
0\\}\cdot\mathbb{I}\\{\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t))>0\\}\right],$
(5)

where we use $\mathbb{I}\\{\cdot\\}$ to denote the indicator function (i.e.,
$\mathbb{I}\\{A\\}=1$ if $A$ is true, and 0 if $A$ is false), and for
notational convenience, we use $\bullet$ to denote inner products, i.e., for
$\mathbf{a},\mathbf{b}\in\mathbb{R}^{n}$,
$\mathbf{a}\bullet\mathbf{b}=\sum_{i=1}^{n}a_{i}b_{i}$. Note that the term
$\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))\leq
0\\}\cdot\mathbb{I}\\{\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t))>0\\}$ is equal
to 1 if and only if $\tau_{\pi}=t$; thus, this problem is equivalent to
problem (4). We also use $J_{D}(\mathbf{b})$ to denote the objective value of
problem (5) at a fixed weight vector $\mathbf{b}$.

###  3.3 Data-driven optimization over deterministic linear policies

While problem (5) is a simplification of the general optimal stopping problem
(2), it is still challenging to solve as it requires one to compute
expectations over the stochastic process $\\{\mathbf{x}(t)\\}_{t=1}^{T}$
exactly. More specifically, this problem is challenging because the stochastic
process is sufficiently complicated that optimizing over the objective
function of problem (5) is computationally difficult, or because the
stochastic process itself is not known exactly. Thus, rather than considering
the exact version of the problem, one can consider solving a sample-average
approximation (SAA) version of the problem, wherein one has access to a set of
trajectories of the stochastic process.

To define this problem, we assume that we have access to a set of $\Omega$
trajectories and that each trajectory is indexed by $\omega$, which ranges
from 1 to $\Omega$. Each trajectory $\omega$ corresponds to a sequence of
states $\mathbf{x}(\omega,1),\mathbf{x}(\omega,2),\dots,\mathbf{x}(\omega,t)$.
Given a policy and a trajectory $\omega$, we define the stopping time for
policy $\pi$ in trajectory $\omega$ as

$\tau_{\pi,\omega}=\min\\{t\in[T]\mid\pi(t,\mathbf{x}(\omega,t))=\textbf{stop}\\}.$

Our SAA problem to determine the optimal linear policy is then

$\underset{\pi\in\Pi_{\mathcal{B}}}{\text{supremum}}\
\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}g(\tau_{\pi,\omega},\mathbf{x}(\omega,\tau_{\pi,\omega})).$
(6)

Similarly to problem (5), we can re-write problem (6) as an optimization
problem over $\mathbf{b}$ as follows:

$\underset{\mathbf{b}\in\mathcal{B}}{\text{supremum}}\
\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}\sum_{t=1}^{T}g(t,\mathbf{x}(\omega,t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime}))\leq
0\\}\cdot\mathbb{I}\\{\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))>0\\}.$
(7)

Note that the term
$\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime}))\leq
0\\}\cdot\mathbb{I}\\{\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))>0\\}$ is
equal to 1 if and only if $\tau_{\pi_{\mathbf{b}},\omega}=t$. Additionally, we
use $\hat{J}_{D}(\mathbf{b})$ to denote the objective value of problem (7) at
a fixed weight vector $\mathbf{b}$.

By re-writing problem (6) as problem (7), we can see that the deterministic
policy SAA problem (7) can be regarded as a type of discrete optimization
problem over the weight vector $\mathbf{b}$. (Note that the supremum in
problem (7) is always attainable and can be replaced by a maximum, since the
objective function $\hat{J}_{D}(\cdot)$ only takes finitely many values.)
While this problem can be further re-formulated as a mixed-integer
optimization problem, it is unlikely that one would be able to solve such a
formulation to provable full or near optimality at a large scale (with tens of
thousands or hundreds of thousands of trajectories). Moreover, the gradient of
the objective function in problem (7), when it is defined, is always zero due
to the presence of the indicator function. This precludes the use of gradient-
based methods, such as stochastic gradient descent, for solving the problem.

###  3.4 Randomized linear policies

Rather than solving problems (5) and (7), which optimize over deterministic
linear policies, we can instead consider a problem where we optimize over
randomized linear policies. In particular, given a collection of coefficients
$\mathbf{b}=(\mathbf{b}_{1},\dots,\mathbf{b}_{T})$ where
$\mathbf{b}_{1},\dots,\mathbf{b}_{T}\in\mathbb{R}^{K}$ we consider randomized
linear policies of the form

$\tilde{\pi}_{\mathbf{b}}(t,\mathbf{x})=\left\\{\begin{array}[]{llll}\textbf{stop}&&&\text{with
probability}\ \sigma(\mathbf{b}_{t}\bullet\Phi(\mathbf{x})),\\\
\textbf{continue}&&&\text{with probability}\
1-\sigma(\mathbf{b}_{t}\bullet\Phi(\mathbf{x})),\end{array}\right.$

where $\sigma(u)=e^{u}/(1+e^{u})$ corresponds to the logistic response
function, and where the decision to stop in period $t$ is independent of
periods $1,\dots,t-1$. Thus, given the coefficients in $\mathbf{b}$, the
randomized policy $\tilde{\pi}_{\mathbf{b}}$ randomly chooses to stop with a
logistic probability that depends on a weighted sum of basis functions.

The stopping time $\tau_{\tilde{\pi}}$ of a randomized policy $\tilde{\pi}$ is
defined as follows. Conditional on a fixed trajectory
$\\{\mathbf{x}(t)\\}_{t=1}^{T}$, the stopping time $\tau_{\tilde{\pi}}$ is a
random variable, whose probability distribution is given by

$\displaystyle\mathbb{P}(\tau_{\tilde{\pi}}=t\mid\mathbf{x}(1),\dots,\mathbf{x}(T))$
$\displaystyle=\prod_{t^{\prime}=1}^{t-1}(1-\sigma(\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))))\cdot\sigma(\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t))),\quad
t=1,\dots,T,$
$\displaystyle\mathbb{P}(\tau_{\tilde{\pi}}=+\infty\mid\mathbf{x}(1),\dots,\mathbf{x}(T))$
$\displaystyle=\prod_{t^{\prime}=1}^{T}(1-\sigma(\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime})))).$

With a slight abuse of notation, let $\mathcal{B}\subseteq\mathbb{R}^{KT}$
denote the set of feasible weight vectors for randomized policies, and define
$\tilde{\Pi}_{\mathcal{B}}$ to be the set of feasible randomized policies:

$\tilde{\Pi}_{\mathcal{B}}=\\{\tilde{\pi}_{\mathbf{b}}\mid\mathbf{b}\in\mathcal{B}\\}.$

Thus, the expected reward of the randomized policy $\tilde{\pi}_{\mathbf{b}}$,
where the expectation is taken over both the stochastic process
$\\{\mathbf{x}(t)\\}_{t=1}^{T}$ and the random stopping decisions can be
written as

$\underset{\tilde{\pi}\in\tilde{\Pi}_{\mathcal{B}}}{\text{supremum}}\
\mathbb{E}[g(\tau_{\tilde{\pi}},\mathbf{x}(\tau_{\tilde{\pi}}))],$ (8)

or equivalently, as

$\underset{\mathbf{b}\in\mathcal{B}}{\text{supremum}}\
\mathbb{E}\left[\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}(1-\sigma(\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))))\cdot\sigma(\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t)))\right],$
(9)

where the expectation in problem (9) is now taken only over the stochastic
process $\\{\mathbf{x}(t)\\}_{t=1}^{T}$. We shall use $J_{R}(\mathbf{b})$ to
denote the objective function of problem (9) at a fixed
$\mathbf{b}\in\mathcal{B}$.

Similarly to the deterministic problem, we can also consider a sample-average
approximation of the true stochastic optimization problem (9). Given a sample
of $\Omega$ trajectories as in Section 3.3, we can define the randomized
policy SAA problem as

$\underset{\mathbf{b}\in\mathcal{B}}{\text{supremum}}\
\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}\sum_{t=1}^{T}g(t,\mathbf{x}(\omega,t))\cdot\prod_{t^{\prime}=1}^{t-1}(1-\sigma(\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime}))))\cdot\sigma(\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))).$
(10)

In other words, we seek to find the coefficients
$\mathbf{b}=(\mathbf{b}_{1},\dots,\mathbf{b}_{T})$ so as to maximize the
expected sample-average reward that arises from using these coefficients to
effect randomized stopping decisions. We note that in problem (10), the
optimization problem is formulated using the supremum. This is necessary,
because although the objective function of (10) is continuous and bounded, the
set $\mathcal{B}$ may not be compact, and therefore there may not have an
attainable maximum. We shall use $\hat{J}_{R}(\mathbf{b})$ to denote the
objective function of the randomized policy at a fixed weight vector
$\mathbf{b}\in\mathcal{B}$.

###  3.5 Equivalence of deterministic and randomized policies

In this section, we investigate the connection between the deterministic
policy problems laid out in Sections 3.2 and 3.3, and the randomized policy
problems in Section 3.4. It turns out that under a small set of conditions, it
is possible to show that the optimal objective values of the deterministic
policy SAA problem (7) and the randomized policy SAA problem (10) are
equivalent. With one additional assumption, it is also possible to show that
the optimal objective values of the deterministic and randomized policy true
problems (problems (5) and (9) respectively) are also equivalent.

Recall that $J_{D}(\cdot)$, $\hat{J}_{D}(\cdot)$ $J_{R}(\cdot)$ and
$\hat{J}_{R}(\cdot)$ are the respective objective functions of the
deterministic policy true problem (5), the deterministic policy SAA problem
(7), the randomized policy true problem (9) and the randomized policy SAA
problem (10). For the purposes of the exposition of this section, we will use
$\tilde{\mathbf{b}}$ to denote a vector of weights for the randomized policy
problem, while $\mathbf{b}$ will be used to denote a vector of weights for the
deterministic policy problem. We will also further disambiguate the sets of
feasible weight vectors for the two problems by using $\mathcal{B}$ to denote
the set of feasible weight vectors for the deterministic problem, and
$\tilde{\mathcal{B}}$ the set of feasible weight vectors for the randomized
problem.

Before stating our first result, we make two assumptions. Our first assumption
is that the set of feasible weight vectors for the deterministic policy and
randomized policy SAA problems are the same.
$\mathcal{B}=\tilde{\mathcal{B}}=\mathbb{R}^{KT}$. Our second assumption
concerns the collection of basis functions. The first basis function
$\phi_{1}(\cdot)$ is the constant basis function, i.e.,
$\phi_{1}(\mathbf{x})=1$ for all $\mathbf{x}\in\mathcal{X}$. With these two
assumptions, we state our first main result.

###### Theorem 3.1

Under Assumptions 3.5 and 3.5 the objective values of problems (7) and (10)
are equal, that is,

$\sup_{\mathbf{b}\in\mathcal{B}}\hat{J}_{D}(\mathbf{b})=\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}\hat{J}_{R}(\tilde{\mathbf{b}}).$

The proof of Theorem 3.1 (see Section 8.1 of the ecompanion) is based on two
key ideas: (1) given a weight vector $\mathbf{b}$ of a deterministic policy,
the same weight vector scaled by an arbitrarily large positive constant
$\alpha$ would result in the randomized policy behaving in the same
(deterministic) way, since $\sigma(u)\to 1$ as $u\to\infty$ and $\sigma(u)\to
0$ as $u\to-\infty$; and (2) given a weight vector $\tilde{\mathbf{b}}$ of a
randomized policy, one can view $\hat{J}_{R}(\tilde{\mathbf{b}})$ as the
expectation of a deterministic policy with a particular basis function weight
chosen randomly, so applying the probabilistic method implies the existence of
a weight vector for a deterministic policy that performs at least as well as
the randomized policy. With regard to the assumptions, Assumption 3.5 is a
technical assumption that is necessary to be able to scale a deterministic
weight vector into an appropriate randomized policy, as in idea (1), while
Assumption 3.5 is a technical assumption that is necessary to avoid
pathological cases where $\mathbf{b}_{t}\bullet\Phi(\mathbf{x})=0$ and to be
able to appropriately apply the probabilistic method as in idea (2). From a
practical perspective, Assumption 3.5 is not too restrictive, as it is common
to use a constant basis function in implementations of ADP for optimal
stopping.

Theorem 3.1 asserts that the SAA formulations of the two policy optimization
problems are essentially equivalent. To establish equivalence of the true
deterministic and randomized policy optimization problems (5) and (9), we need
the following additional assumption, which concerns the stochastic process
itself. We defer our discussion of this assumption until the statement of
Theorem 3.2. To state this assumption, we let
$\Phi_{2:K}:\mathcal{X}\to\mathbb{R}^{K-1}$ be defined as
$\Phi_{2:K}(\mathbf{x})=(\phi_{2}(\mathbf{x}),\dots,\phi_{K}(\mathbf{x}))$,
which is just the vector-valued mapping of the state $\mathbf{x}$ to the basis
function values $\phi_{2}(\mathbf{x})$ through $\phi_{K}(\mathbf{x})$ (in
other words, it is just the mapping $\Phi$, only with the first basis function
$\phi_{1}(\cdot)$ omitted). For any hyperplane $A\subseteq\mathbb{R}^{K-1}$,
i.e., a set of the form
$A=\\{\mathbf{y}\in\mathbb{R}^{K-1}\mid\mathbf{c}\bullet\mathbf{y}+d=0\\}$ for
some $\mathbf{c}\in\mathbb{R}^{K-1}$, $d\in\mathbb{R}$, and any $t\in[T]$,
$\mathbb{P}(\Phi_{2:K}(\mathbf{x}(t))\in A)=0$. We can now state our
counterpart of Theorem 3.1 for the true stochastic optimization problems (9)
and (5).

###### Theorem 3.2

Under Assumptions 3.5, 3.5 and 3.1 the objective values of the randomized
problem (9) and the deterministic problem (5) are equal, that is,

$\sup_{\mathbf{b}\in\mathcal{B}}J_{D}(\mathbf{b})=\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}J_{R}(\tilde{\mathbf{b}}).$

The proof of Theorem 3.2 (see Section 8.2 of the ecompanion) is similar to the
proof of Theorem 3.1, but with several key differences. The most significant
difference is that in the proof of Theorem 3.1, we show that a given
deterministic linear policy can be approximated arbitrarily closely by a
randomized policy. This is facilitated by Assumption 3.5, which allows one to
avoid situations where the inner product of $\mathbf{b}_{t}$ and
$\Phi(\mathbf{x}(\omega,t))$ is exactly zero in a given $\omega$ and $t$
(since there are finitely many trajectories, one can perturb a given
deterministic weight vector $\mathbf{b}$ into a new deterministic weight
vector $\mathbf{b}^{\prime}$ that has the same stopping behavior but never
satisfies $\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))=0$ for any $\omega$
and any $t$). In the true stochastic optimization problem setting, this is no
longer possible. For this reason, we introduce Assumption 3.1, which requires
that $\Phi_{2:K}(\mathbf{x}(t))$ has probability zero of being in any given
hyperplane. This assumption allows us to avoid the aforementioned pathological
cases where the stochastic process is such that, for a given non-zero weight
vector $\mathbf{b}$ for the randomized policy problem, the inner product
$\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t))$ may be exactly zero, which would
mean the randomized policy would choose to stop or continue with equal
probability.

With regard to Assumption 3.1, we note that this assumption holds for many,
though not all, problem instances. For example, suppose that
$\mathcal{X}\subseteq\mathbb{R}^{n}$ and
$\phi_{2}(\mathbf{x}),\dots,\phi_{K}(\mathbf{x})$ are polynomials of
$\mathbf{x}\in\mathcal{X}$. In this case, the set
$\\{\mathbf{x}\in\mathcal{X}\mid\mathbf{c}\bullet\Phi_{2:K}(\mathbf{x})+d=0\\}$
is the set of zeros of a polynomial function of $\mathbf{x}$, which is a
measure zero set (Okamoto 1973). If we further assume that $\mathbf{x}(t)$ at
each $t$ has a bounded density, which is the case for many commonly used
stochastic processes (e.g., geometric Brownian motion), then it immediately
follows that $\mathbb{P}(\Phi_{2:K}(\mathbf{x}(t))\in A)=0$ for any hyperplane
$A\subseteq\mathbb{R}^{K-1}$. As another example, suppose that
$\mathcal{X}=\mathbb{R}^{K-1}$, and define $E$ as $E=\Phi_{2:K}(\mathcal{X})$,
the image of $\mathcal{X}$ under $\Phi_{2:K}(\cdot)$, which we assume to be an
open subset of $\mathbb{R}^{K-1}$. Suppose also that the inverse function
$\Phi^{-1}_{2:K}(\cdot)$ is defined on $E$ and is continuously differentiable.
Then the event $\Phi_{2:K}(\mathbf{x}(t))\in A$ for a hyperplane
$A\subseteq\mathbb{R}^{K-1}$ is equivalent to the event
$\Phi_{2:K}(\mathbf{x}(t))\in A\cap E$, which is equivalent to the event
$\mathbf{x}(t)\in\Phi^{-1}_{2:K}(A\cap E)$. If $A$ is a hyperplane in
$\mathbb{R}^{K-1}$, it has measure zero, and so does $A\cap E$; and since
$\Phi^{-1}_{2:K}(\cdot)$ is continuously differentiable,
$\Phi^{-1}_{2:K}(A\cap E)$ is also a measure zero set in $\mathbb{R}^{K-1}$
(see Lemma 18.1 of Munkres 1991). If we again assume that each $\mathbf{x}(t)$
has a bounded density, then it again follows that
$\mathbb{P}(\mathbf{x}(t)\in\Phi^{-1}_{2:K}(A\cap E))=0$ or equivalently,
$\mathbb{P}(\Phi_{2:K}(\mathbf{x}(t))\in A)=0$. Where Assumption 3.1 could
potentially fail is when the basis function mapping $\Phi_{2:K}(\cdot)$
collapses subsets of $\mathcal{X}$ to singletons, which could cause the
probability of $\Phi_{2:K}(\mathbf{x}(t))$ being in certain hyperplanes to be
non-zero.

We conclude this section by offering two remarks on Theorems 3.1 and 3.2.
First, the significance of these two theorems is that in a certain sense, the
problem of optimizing over deterministic policies and the problem of
optimizing over randomized policies are the same. In the case of the true
stochastic optimization problems, by solving the randomized problem (9), we
can obtain a policy that performs as well as the one we would obtain by
solving the deterministic problem (5). Similarly, in the case when we are
working with a finite sample of trajectories, solving the randomized SAA
problem (10) allows us to obtain a policy that performs as well as the one we
would obtain by solving the deterministic SAA problem (7). From a practical
perspective, the advantage of solving the randomized policy SAA problem (10),
as opposed to the deterministic policy SAA problem (7), is that the objective
function $\hat{J}_{R}(\cdot)$ is a differentiable function. Although
$\hat{J}_{R}(\cdot)$ is non-convex due to the presence of the logistic
response function $\sigma(\cdot)$, it is at least possible to approximately
optimize $\hat{J}_{R}(\cdot)$ using gradient-based methods. The specific
structure of $\hat{J}_{R}(\cdot)$ lends itself to an iterative algorithm that
optimizes the weight vector $\tilde{\mathbf{b}}$ one period at a time,
starting with the last period, that is reminiscent of the least-squares Monte
Carlo (LSM) method; we defer our presentation of this algorithm to Section
5.2.

Second, we comment a little more on the motivation of our randomized policy
optimization approach, in light of Theorems 3.1 and 3.2. Our interest in
randomized linear policies does not stem from some fundamental operational
benefit that a randomized policy provides over a deterministic policy; stated
differently, we do not wish to argue that in practice, a decision maker would
want to make stopping decisions randomly as opposed to deterministically.
Instead, our motivation for studying randomized policies is that the use of
the logistic response function $\sigma$ allows use to view the randomized
policy true problem (9) and the SAA problem (10) as differentiable or “soft”
counterparts to the deterministic policy problems (5) and (7), respectively,
which are formulated using the indicator function $\mathbb{I}\\{\cdot\\}$ and
involve making “hard” stopping decisions. Theorems 3.1 and 3.2 show that in
general, this view is justified, as the deterministic and randomized problems
are equal in objective value. As we will shortly see, the randomized policy
SAA problem is amenable to an analysis of its convergence and generalization
properties, and as we have already mentioned, is amenable to an intuitive
heuristic for approximately solving it. Later, in Section 6, we will see
numerically that using an approximate solution of the randomized policy SAA
problem within a deterministic policy performs very well and can result in
significant improvements over existing approaches.

##  4 Statistical properties

In this section, we investigate the statistical properties of the randomized
policy SAA problem (10). In Section 4.1 we show that the objective value and
optimal solution set of the randomized policy SAA problem converge almost
surely to those of the true randomized policy problem. In Section 4.2, we
establish guarantees on the out-of-sample performance of the solution obtained
from the randomized policy SAA problem by characterizing the Rademacher
complexity of the expected reward generated by a given set of weight vectors.

###  4.1 Convergence of randomized policy SAA problem

It is natural to expect that the optimal value and optimal solutions of the
SAA problem (10) converge to their counterparts of the true optimization
problem as the number of sample trajectories $\Omega\rightarrow\infty$. In
this section, we provide Theorems 4.1 and 4.3 to establish these two
convergence properties of our randomized policy SAA problem.

We first make the following two mild assumptions to facilitate the proofs of
Theorems 4.1 and 4.3. There exists a constant $Q>0$ such that for any
$\mathbf{x}\in\mathcal{X}$, $\|\Phi(\mathbf{x})\|_{\infty}\leq Q$.

$\mathcal{B}$ is a compact subset of $\mathbb{R}^{KT}$.

Note that we no longer carry Assumptions 3.5, 3.5 and 3.1. In particular,
Assumption 3.5 is not relevant to Theorems 4.1 and 4.3, and Assumptions 3.5
and 3.1 are not required to establish our results here.

With these two assumptions, we can establish the following theorem which shows
the almost sure uniform convergence of $\hat{J}_{R}(\cdot)$ to $J_{R}(\cdot)$
over the set $\mathcal{B}$.

###### Theorem 4.1

Suppose that Assumptions 4.1 and 4.1 both hold. Then with probability one,

$\lim_{\Omega\to\infty}\sup_{\mathbf{b}\in\mathcal{B}}\
|\hat{J}_{R}(\mathbf{b})-J_{R}(\mathbf{b})|=0.$ (11)

The proof of Theorem 4.1 is provided in Section 8.3 of the ecompanion. It
relies on the fact that the objective function $J_{R}(\cdot)$ in the true
problem (9) and the objective function $\hat{J}_{R}(\cdot)$ in the SAA problem
(10) have bounded Lipschitz constants, and the compactness of $\mathcal{B}$.
Thus, we can use these two properties, together with the strong law of large
numbers, to show uniform convergence.

Now, using Theorem 4.1, it is straightforward to derive the convergence of the
SAA optimal objective value, which is stated in the following corollary.

###### Corollary 4.2

Suppose that Assumptions 4.1 and 4.1 both hold. Then with probability one,

$\lim_{\Omega\to\infty}\sup_{\mathbf{b}\in\mathcal{B}}\hat{J}_{R}(\mathbf{b})=\sup_{\mathbf{b}\in\mathcal{B}}J_{R}(\mathbf{b}).$
(12)

For the convergence of the SAA optimal solutions, let us define the sets
$\mathbf{B}^{*}$ and $\hat{\mathbf{B}}$ as

$\displaystyle\mathbf{B}^{*}=\arg\max_{\mathbf{b}\in\mathcal{B}}J_{R}(\mathbf{b}),$
$\displaystyle\hat{\mathbf{B}}=\arg\max_{\mathbf{b}\in\mathcal{B}}\hat{J}_{R}(\mathbf{b}),$

that is, $\mathbf{B}^{*}$ is the set of optimal solutions of the true
stochastic problem (9) while $\hat{\mathbf{B}}$ is the set of optimal
solutions to the SAA problem (10). In addition, let
$\mathbb{D}(\hat{\mathbf{B}},\mathbf{B}^{*})$ be the _deviation_ (see Chapter
7 of Shapiro et al. 2014) of the set $\hat{\mathbf{B}}$ from $\mathbf{B}^{*}$,
that is,

$\mathbb{D}(\hat{\mathbf{B}},\mathbf{B}^{*})=\sup_{\mathbf{b}\in\hat{\mathbf{B}}}\inf_{\mathbf{b}^{\prime}\in\mathbf{B}^{*}}\|\mathbf{b}-\mathbf{b}^{\prime}\|_{2}.$

In the above definition, the inner infimum measures the distance between a
given optimal solution $\mathbf{b}$ of the SAA problem (10) and the closest
optimal solution of the true problem (9); the outer supremum then takes the
largest such distance, over all optimal solutions of the SAA problem.

With these definitions, we can now apply Theorem 5.3 in Shapiro et al. (2014)
to establish the following theorem:

###### Theorem 4.3

Suppose that Assumptions 4.1 and 4.1 both hold. Then with probability one,
$\mathbb{D}(\hat{\mathbf{B}},\mathbf{B}^{*})\to 0$ as $\Omega\to\infty$.

Corollary 4.2 and Theorem 4.3 indicate that, given a sufficiently large sample
size, the weight vector obtained by solving the SAA optimization problem (10)
can be arbitrarily close to the optimal weight vector set of the true problem
(9), and the corresponding optimal value of the SAA problem can be arbitrarily
close to the optimal value of true problem.

###  4.2 Rademacher Complexity

In Section 4.1, we have seen from Theorem 4.1 that the optimal SAA objective
value $\sup_{\mathbf{b}\in\mathcal{B}}\hat{J}_{R}(\mathbf{b})$ converges with
probability one to the true optimal objective value
$\sup_{\mathbf{b}\in\mathcal{B}}J_{R}(\mathbf{b})$ as the number of
trajectories goes to infinity. However, in practice, we can only have access
to a finite number of sample trajectories; in other words, there always exists
some gap between $J_{R}(\mathbf{b})$ and $\hat{J}_{R}(\mathbf{b})$. Therefore,
it is important to investigate how far $\hat{J}_{R}(\mathbf{b})$ could be away
from $J_{R}(\mathbf{b})$ for a finite sample size and find good bounds on this
gap. In this section, we will use a classical data-dependent complexity
estimate of a function class, Rademacher complexity, to lower-bound the value
of $J_{R}(\mathbf{b})-\hat{J}_{R}(\mathbf{b})$, and provide three upper bounds
on the Rademacher complexity term, corresponding to different choices of the
weight vector set $\mathcal{B}$.

To establish this result, we require some additional definitions. We use $Y$
to denote a system realization, which is a pair consisting of the sequence of
states and the sequence of rewards, that is,
$Y=(\\{\mathbf{x}(t)\\}_{t=1}^{T},\\{g(t,\mathbf{x}(t))\\}_{t=1}^{T})$. We use
$Y_{1},\dots,Y_{\Omega}$ to denote the sample of system realizations. We
define the function $\Gamma:\mathbb{R}^{T}\times[0,\bar{G}]^{T}\to\mathbb{R}$
as

$\Gamma(\mathbf{u},\mathbf{v})=\sum_{t=1}^{T}v_{t}\prod_{t^{\prime}=1}^{t-1}(1-\sigma(u_{t^{\prime}}))\sigma(u_{t}),$
(13)

where $\mathbf{u},\mathbf{v}\in\mathbb{R}^{T}$. For a fixed weight vector
$\mathbf{b}\in\mathcal{B}$, we define the function
$\psi_{\mathbf{b}}:\mathcal{X}^{T}\times\mathbb{R}^{T}\to\mathbb{R}^{2T}$
which maps a system realization $Y$ to a $2T$-dimensional vector as

$\psi_{\mathbf{b}}(Y)=\left[\begin{array}[]{c}\mathbf{b}_{1}\bullet\Phi(\mathbf{x}(1))\\\
\vdots\\\ \mathbf{b}_{T}\bullet\Phi(\mathbf{x}(T))\\\ g(1,\mathbf{x}(1))\\\
\vdots\\\ g(T,\mathbf{x}(T))\end{array}\right].$ (14)

We define
$\mathcal{F}=\\{\Gamma\circ\psi_{\mathbf{b}}\mid\mathbf{b}\in\mathcal{B}\\}$
as the class of realization-to-reward functions. Note that for a fixed weight
vector $\mathbf{b}$, the function value $(\Gamma\circ\psi_{\mathbf{b}})(Y)$
gives exactly the expected reward of the randomized policy, where the
expectation is taken over the stopping/continuation decisions, but conditional
on the fixed system realization $Y$.

Lastly, we define the empirical Rademacher complexity $\hat{R}(\mathcal{F})$
as

$\hat{R}(\mathcal{F})=\frac{1}{\Omega}\mathbb{E}_{\boldsymbol{\epsilon}}\left[\sup_{f\in\mathcal{F}}\sum_{\omega=1}^{\Omega}\epsilon_{\omega}f(Y_{\omega})\right],$
(15)

where $\epsilon_{1},\dots,\epsilon_{\Omega}$ are independent Rademacher random
variables, that is, each $\epsilon_{\omega}$ is equal to -1 or +1 with
probability 1/2, and $\boldsymbol{\epsilon}$ is used to denote the vector of
these random variables. We define the (ordinary) Rademacher complexity
$R(\mathcal{F})$ as
$R(\mathcal{F})=\mathbb{E}_{Y_{1},\dots,Y_{\Omega}}[\hat{R}(\mathcal{F})]$.

Having set up the definitions of empirical Rademacher complexity and
(ordinary/non-empirical) Rademacher complexity, Proposition 17 establishes the
lower bounds of $J_{R}(\mathbf{b})-\hat{J}_{R}(\mathbf{b})$ in terms of these
two complexity terms.

###### Proposition 4.4

Let $S=\\{Y_{1},\dots,Y_{\Omega}\\}$ be a collection of independent and
identically distributed system realizations. For all $\delta>0$, with
probability at least $1-\delta$ over the sample $S$:

$J_{R}(\mathbf{b})\geq\hat{J}_{R}(\mathbf{b})-2R(\mathcal{F})-\bar{G}\sqrt{\frac{\log(1/\delta)}{2\Omega}},\qquad\forall\
\mathbf{b}\in\mathcal{B}$ (16)
$J_{R}(\mathbf{b})\geq\hat{J}_{R}(\mathbf{b})-2\hat{R}(\mathcal{F})-3\bar{G}\sqrt{\frac{\log(2/\delta)}{2\Omega}},\qquad\forall\
\mathbf{b}\in\mathcal{B}$ (17)

The proof of Proposition 17 is given in Section 8.6 of the ecompanion; it
follows the standard proof of generalization error bounds based on Rademacher
complexity in statistical learning theory. We remark here that the
generalization bounds established in Proposition 17 are different from those
in classical statistical learning. Proposition 17 provides lower bounds on the
true reward $J_{R}(\mathbf{b})$ in the form of the sample-based estimate
$\hat{J}_{R}(\mathbf{b})$ minus a penalty term related to the complexity of
our model; whereas in classical statistical learning problems, Rademacher
complexity is used to upper-bound the true error in the form of the training
error plus the complexity term. The reason for this difference is that our
problem is to maximize the expected reward, while the goal of classical
statistical learning problem is to minimize some loss function.

The key quantities in Proposition 17 are the empirical and ordinary Rademacher
complexities $R(\mathcal{F})$ and $\hat{R}(\mathcal{F})$. To understand how
these quantities scale in the problem primitives and the structure of the
admissible weight vector set $\mathcal{B}$, we have the following result,
which provides deterministic bounds on $\hat{R}(\mathcal{F})$. (Note that
since these bounds on $\hat{R}(\mathcal{F})$ hold almost surely, they are also
valid bounds on $R(\mathcal{F})$.)

###### Theorem 4.5

Suppose that Assumption 4.1 holds. Let $B\geq 0$. Then we have the following
deterministic bounds for the empirical Rademacher complexity
$\hat{R}(\mathcal{F})$:

  1. a)

If $\mathcal{B}=\\{\mathbf{b}\in\mathbb{R}^{KT}\mid\|\mathbf{b}\|_{1}\leq
B\\}$, then
$\hat{R}(\mathcal{F})\leq\sqrt{2}(\bar{G}+1)\cdot\frac{BQ\sqrt{2\log(2KT)}}{\sqrt{\Omega}}$.

  2. b)

If $\mathcal{B}=\\{\mathbf{b}\in\mathbb{R}^{KT}\mid\|\mathbf{b}\|_{2}\leq
B\\}$, then
$\hat{R}(\mathcal{F})\leq\sqrt{2}(\bar{G}+1)\cdot\frac{BQ\sqrt{KT}}{\sqrt{\Omega}}$.

  3. c)

If $\mathcal{B}=\\{\mathbf{b}\in\mathbb{R}^{KT}\mid\|\mathbf{b}\|_{\infty}\leq
B\\}$, then
$\hat{R}(\mathcal{F})\leq\sqrt{2}(\bar{G}+1)\cdot\frac{BQKT}{\sqrt{\Omega}}$.

The proof of Theorem 4.5 (see Section 8.7 of the ecompanion) consists of two
main steps. The first step is relating the Rademacher complexity of
$\mathcal{F}$ to the Rademacher complexity of the class
$\\{\psi_{\mathbf{b}}\mid\mathbf{b}\in\mathcal{B}\\}$. This involves the
application of Maurer’s vector contraction inequality (Maurer 2016), which is
useful when a class of vector-valued functions is composed with a collection
of scalar-valued Lipschitz functions, and can be used to relate the Rademacher
complexity of the class of composite functions to the Rademacher complexity of
the class of vector-valued functions. The outcome of this is that the
Rademacher complexity of $\mathcal{F}$ can be written in terms of the
Rademacher complexity of
$\\{\psi_{\mathbf{b}}\mid\mathbf{b}\in\mathcal{B}\\}$; in the second step, we
analyze the Rademacher complexity of this latter class by exploiting the
structure of $\mathcal{B}$.

From this result, we can see that in all three cases, the Rademacher
complexity scales gracefully with the problem dimension. In the worst case
(when $\mathcal{B}$ is equal to the $L_{\infty}$ norm ball; part c), it scales
at most linearly with $K$ and with $T$. This is partially driven by the fact
that the function $\Gamma$ is Lipschitz continuous (with respect to the
$L_{2}$ norm) with constant $\bar{G}+1$. Importantly, this constant does not
depend on $T$. This is not obvious, because the probability of stopping at
period $t$ is the product of $t$ Lipschitz continuous and bounded functions,
and so by standard properties of Lipschitz functions one should expect the
Lipschitz constant to depend on $T$. It turns out that one can avoid a
dependence on $T$ because the products terms of the form
$\prod_{t^{\prime}=1}^{t-1}(1-\sigma(\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))))\sigma(\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t)))$
form a probability distribution. Consequently, the dependence on $T$ in the
bounds in Theorem 4.5 arises from the structure of the set $\mathcal{B}$, and
not from the function $\Gamma$.

##  5 Solution Methodology

We now turn our attention to how one can actually solve the randomized policy
SAA problem (10). In Section 5.1, we show that the randomized policy SAA
problem is in general NP-Hard. Motivated by this, in Section 5.2 we propose an
algorithm for approximately solving the SAA problem, based on backward
induction. We conclude in Section 5.3 by comparing our proposed heuristic
algorithm with the LSM algorithm.

###  5.1 Complexity of randomized policy SAA problem

Our main theoretical result on the solvability of the randomized policy SAA
problem (10) is unfortunately a negative one.

###### Theorem 5.1

The randomized policy SAA problem (10) is NP-Hard.

We make a few remarks about this result. First, our proof of Theorem 5.1 (see
Section 9 of the ecompanion) involves considering the decision form of the
randomized policy SAA problem (10), which asks whether there exists a weight
vector $\mathbf{b}$ that achieves at least a certain target sample-average
reward. By considering this decision problem, we show that for any instance of
the decision form of the MAX-3SAT problem, a well-known NP-Complete problem,
we can construct a corresponding instance of the randomized policy SAA problem
such that the answers to the two decision problems are identical. We note that
the proof is not trivial, as the randomized policy SAA problem is in general a
continuous problem, whereas MAX-3SAT is inherently discrete. In particular,
showing that a positive answer to the SAA decision problem implies a positive
answer to the MAX-3SAT problem involves viewing expressions involving
$\sigma(\cdot)$ as expected values of expressions defined using a certain
collection of i.i.d. random variables, and applying the probabilistic method
to guarantee the existence of values for those random variables that can then
be used to construct a solution to the MAX-3SAT problem. Most importantly, our
proof does not achieve this equivalence by restricting the set of feasible
weight vectors $\mathcal{B}$ to be a discrete set: the only restriction we
place is to restrict the weight vectors be equal across time (i.e.,
$b_{t,k}=b_{t^{\prime},k}$ for $t\neq t^{\prime}$), which still results in
$\mathcal{B}$ being uncountably infinite.

Second, we note that from an intuition standpoint, it is not reasonable to
expect the randomized policy SAA problem (10) to be tractable. As alluded to
before, this problem is a non-convex optimization problem, due to the presence
of the function $\sigma(\cdot)$ that is neither convex nor concave. In
addition, as $\sigma(u)$ can be viewed as a continuous approximation of the
step function $\mathbb{I}\\{u\geq 0\\}$, one can expect the function
$\hat{J}_{R}(\cdot)$ to have many local optima. In the next section, we
consider a heuristic approach for solving the problem.

###  5.2 Backward optimization algorithm

Motivated by the fact that our randomized policy SAA problem (10) is
theoretically intractable, we develop an iterative heuristic algorithm for
solving the problem.

The high level idea of our heuristic is to solve problem (10) by optimizing
over the weights one period at a time, starting from the last one. In
particular, recall that $\mathbf{b}=(\mathbf{b}_{1},\dots,\mathbf{b}_{T})$ and
with a slight abuse of notation, let
$\hat{J}_{R}(\mathbf{b}_{1},\dots,\mathbf{b}_{T})$ denote the SAA objective
value for the given collection of time-specific weight vectors. Assume also
that that the set of feasible weight vectors is the Cartesian product of $T$
period-wise weight vector sets, that is,
$\mathcal{B}=\mathcal{B}_{1}\times\dots\times\mathcal{B}_{T}$, where
$\mathcal{B}_{1},\dots,\mathcal{B}_{T}\subseteq\mathbb{R}^{K}$. The $t$th
iteration of the algorithm involves solving the single-period problem

$\max_{\mathbf{b}^{\prime}_{t}\in\mathcal{B}_{t}}\hat{J}_{R}(\mathbf{b}_{1},\dots,\mathbf{b}_{t-1},\mathbf{b}^{\prime}_{t},\mathbf{b}_{t+1},\dots,\mathbf{b}_{T})$
(18)

and updating the $t$th weight vector in $\mathbf{b}$, which is
$\mathbf{b}_{t}$, with the new solution $\mathbf{b}^{*}_{t}$. This process
goes on from period $t=T$ all the way to $t=1$; after the $t=1$ iteration, the
algorithm terminates. We formally define our procedure as Algorithm 1 below.

Initialize $\mathbf{b}_{t}\leftarrow\mathbf{0}$ for all $t\in[T]$.

Initialize $c_{T}(\omega)=0$ for all $\omega\in[\Omega]$.

for $t=T,\dots,1$ do

Compute $p_{t}(\omega)$ as
$p_{t}(\omega)=\prod_{t^{\prime}=1}^{t-1}(1-\sigma(\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime})))).$
(19)

Solve the problem
$\max_{\mathbf{b}_{t}\in\mathcal{B}_{t}}\sum_{\omega=1}^{\Omega}\frac{1}{\Omega}\cdot
p_{t}(\omega)\cdot[g(t,\mathbf{x}(\omega,t))\cdot\sigma(\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t)))+c_{t}(\omega)\cdot(1-\sigma(\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))))]$
(20) to obtain an optimal solution $\mathbf{b}^{*}_{t}$.

Compute $c_{t-1}(\omega)$ as
$c_{t-1}(\omega)=g(t,\mathbf{x}(\omega,t))\cdot\sigma(\mathbf{b}^{*}_{t}\bullet\Phi(\mathbf{x}(\omega,t)))+c_{t}(\omega)\cdot(1-\sigma(\mathbf{b}^{*}_{t}\bullet\Phi(\mathbf{x}(\omega,t)))).$
(21)

end for

Algorithm 1 Backwards optimization algorithm for approximately solving the
randomized policy SAA problem (10).

We pause to make several comments about Algorithm 1. First, observe that the
period $t$ problem solved in Algorithm 1, problem (20), is of a different form
from problem (18). The two problems are equivalent in that problem (20) is a
simplification of problem (18). In particular, $p_{t}(\omega)$ can be regarded
as the probability, conditional on the weight vectors
$\mathbf{b}_{1},\dots,\mathbf{b}_{t-1}$, of not having stopped by period $t$
in trajectory $\omega$. By using this term, we can simplify the problem and
remove the appearance of the weight vectors for periods prior to $t$.
Similarly, $c_{t}(\omega)$ can be regarded as the expected continuation value
at period $t$ in trajectory $\omega$, i.e., given that we have not stopped by
period $t$, what is the expected reward (where the expectation is with respect
to the randomness of the stopping decisions) from not stopping at period $t$,
for the trajectory $\omega$. Using both of these, and using the fact that
$\hat{J}_{R}(\cdot)$ includes terms that only depend on
$\mathbf{b}_{t^{\prime}}$ for $t^{\prime}<t$, we can boil problem (18) down to
problem (20), which is of the form
$\sum_{\omega}(c_{\omega}+d_{\omega}\cdot\sigma(\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))))$.

Second, we note that problem (20) is still a challenging problem to solve, as
the objective function is still non-convex. It is an instance of the sum-of-
sigmoids problem (a sigmoid function being an S-shaped function, such as the
logistic response function $\sigma(\cdot)$), which Udell and Boyd (2013) show
to be NP-Hard in general. Similarly, Akçakuş and Mišić (2021) show that a
related problem, of finding a binary product attribute vector that maximizes
the expected market share under a mixture-of-logits model, is NP-Hard.
However, problem (20) is more manageable to solve than the complete randomized
policy SAA problem (10), as it involves only the weight variables for a single
period ($K$ variables) as opposed to all $T$ periods ($KT$ variables). In our
implementation of Algorithm 1, we use the Adam algorithm (Kingma and Ba 2014)
to approximately solve problem (20).

Lastly, we comment on how we use the solution
$\mathbf{b}^{*}=(\mathbf{b}^{*}_{1},\dots,\mathbf{b}^{*}_{T})$ produced by
Algorithm 1. Although $\mathbf{b}^{*}$ corresponds to a randomized policy, in
our numerical experiments we will focus on using $\mathbf{b}^{*}$ within a
deterministic linear policy. In other words, we plug $\mathbf{b}^{*}$ into a
policy of the form of equation (3). The reason for doing this is that in
general, we have empirically observed that the deterministic policy defined
with $\mathbf{b}^{*}$ performs better than the randomized policy defined with
$\mathbf{b}^{*}$. To understand the intuition for this, let us consider
problem (20). For this problem, a good weight vector $\mathbf{b}_{t}$ at time
$t$ would be one where, for most trajectories,
$\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))$ is very positive when
$g(t,\mathbf{x}(\omega,t))$ is higher than $c_{t}(\omega)$, and where
$\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))$ is very negative when
$c_{t}(\omega)$ is higher than $g(t,\mathbf{x}(\omega,t))$. When this is true
for most trajectories, it is reasonable to expect that we could improve our
objective value by thresholding
$\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))$, i.e., rounding
$\sigma(\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t)))$ to 0 or 1, which
would have the effect of making the expression in the square brackets in
problem (20) generally (i.e., for most trajectories) equal to
$\max\\{g(t,\mathbf{x}(\omega,t)),c_{t}(\omega)\\}$, which is a higher
quantity than
$g(t,\mathbf{x}(\omega,t))\cdot\sigma(\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t)))+c_{t}(\omega)\cdot(1-\sigma(\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))))$.

Besides this consideration, as discussed in Section 3.5, optimizing over
randomized policies is equivalent to optimizing over deterministic policies,
and our motivation for optimizing over randomized policies is to ultimately
obtain good deterministic policies in a tractable manner. Lastly, we note that
using $\mathbf{b}^{*}$ within a deterministic policy is similar to how in
binary classification problems in machine learning, it is common to learn a
probabilistic model whose natural output is a probability of a target class
(for example, a logistic regression model), and to then threshold this
probability to obtain a hard classification.

###  5.3 Comparison of Algorithm 1 with least-squares Monte Carlo

Algorithm 1 shares some similarities with the least-squares Monte Carlo (LSM)
algorithm of Longstaff and Schwartz (2001). For easier comparison, we state
the basic LSM algorithm adapted to our problem setting as Algorithm 2 below.

Initialize $c_{T-1}(\omega)=g(T,\mathbf{x}(\omega,T))$ for all
$\omega\in[\Omega]$.

for $t=T-1,\dots,1$ do

Solve the least-squares problem
$\min_{\mathbf{b}_{t}\in\mathbb{R}^{K}}\frac{1}{2}\sum_{\omega=1}^{\Omega}(c_{t}(\omega)-\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t)))^{2}$
(22) to obtain an optimal solution $\mathbf{b}^{*}_{t}$.

Compute $c_{t-1}(\omega)$ as
$c_{t-1}(\omega)=\left\\{\begin{array}[]{ll}c_{t}(\omega)&\text{if}\
\mathbf{b}^{*}_{t}\bullet\Phi(\mathbf{x}(\omega,t))\geq
g(t,\mathbf{x}(\omega,t)),\\\ g(t,\mathbf{x}(\omega,t))&\text{if}\
\mathbf{b}^{*}_{t}\bullet\Phi(\mathbf{x}(\omega,t))<g(t,\mathbf{x}(\omega,t)).\end{array}\right.$
(23)

end for

Algorithm 2 Least-squares Monte Carlo (LSM) algorithm of Longstaff and
Schwartz (2001).

In particular, the LSM algorithm also involves iterating backwards in time,
and also involves updating the continuation value using the current policy.
However, a key difference is that LSM involves solving a least-squares problem
to obtain basis function weights $\mathbf{b}_{t}$, so as to predict the
continuation value using those basis function weights. The stopping policy is
then defined by comparing the current payoff to the predicted continuation
value, where stopping is prescribed if and only if the current payoff is more
than the predicted continuation value. In contrast, our algorithm involves
directly optimizing over the stopping policy at a given period: in problem
(20), we look for weights $\mathbf{b}_{t}$ for the stopping decision in the
current period so that the expected reward, which accounts for both the
current period’s reward and the continuation value $c_{t}(\omega)$ that
captures reward in future periods, is optimized.

Besides this difference, it is also important to appreciate the higher level
differences in the two approaches. In particular, LSM (Algorithm 2) produces a
policy of the form

$\pi(t,\mathbf{x})=\left\\{\begin{array}[]{ll}\textbf{stop}&\text{if}\
g(t,\mathbf{x})>\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t)),\\\
\textbf{continue}&\text{if}\
g(t,\mathbf{x})\leq\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t)).\end{array}\right.$

Note that this policy can be made equivalent to a deterministic linear policy
as we have defined it in Sections 3.2 and 3.3. Specifically, we can augment
the state variable $\mathbf{x}(t)$ to include an additional coordinate that is
equal to $g(t,\mathbf{x}(t))$ and then augment the basis function architecture
$\Phi(\mathbf{x})=(\phi_{1}(\mathbf{x}),\dots,\phi_{K}(\mathbf{x})))$ with a
$K+1$th basis function $\phi_{K+1}(\cdot)$ that is exactly equal to this new
coordinate. With these augmentations, the weight vector
$\tilde{\mathbf{b}}_{t}=(-b_{t,1},\dots,-b_{t,K},+1)$ is such that

$g(t,\mathbf{x})>\sum_{k=1}^{K}b_{t,k}\phi_{k}(\mathbf{x}(t))\ \text{if and
only if}\ \sum_{k=1}^{K+1}\tilde{b}_{t,k}\phi_{k}(\mathbf{x}(t))>0,$

i.e., the corresponding deterministic linear policy with the $K+1$ basis
functions and the weight vectors
$\tilde{\mathbf{b}}_{1},\dots,\tilde{\mathbf{b}}_{T}$ behaves identically to
the LSM policy. Thus, LSM can be viewed as a method for returning a solution
to the deterministic policy SAA problem (7).

In light of this relationship, we note that, to our knowledge, there is no
guarantee that the solution that LSM returns solves either the true
deterministic policy problem (5) or the deterministic policy SAA problem (7).
In contrast, Algorithm 1 is designed to directly (albeit approximately) solve
the randomized policy SAA problem (10). Our results in Sections 3 and 4
provide theoretical justification for why this approach is desirable: under
mild conditions, the true randomized policy problem (9) and its SAA
counterpart (10) are equivalent to the true deterministic policy problem (5)
and its SAA counterpart, respectively (guaranteed by our equivalence results,
Theorems 3.1 and 3.2); as we accumulate more data, the optimal objective value
and solution of the randomized policy SAA problem (10) converge to that of the
true randomized policy problem (9) (guaranteed by our consistency results,
Corollary 4.2 and Theorem 4.3); and optimizing the randomized policy SAA
problem directly optimizes a lower bound on the out-of-sample reward that
becomes tighter as one accumulates more data (guaranteed by our generalization
bound and Rademacher complexity results, Proposition 17 and Theorem 4.5).
Taken together, these results suggest that for a fixed basis function
architecture, our method (Algorithm 1) has the potential to obtain policies
that deliver better out-of-sample performance than LSM. In Section 6, we will
showcase one family of benchmark problem instances where this is indeed the
case.

##  6 Application to option pricing

In this section, we apply our randomized policy approach to a standard option
pricing problem, previously considered in a number of papers (e.g., Desai et
al. 2012, Ciocan and Mišić 2022). We define our option pricing problem in
Section 6.1. In Section 6.2, we illustrate the difference between our
randomized policy approach and prior approaches for obtaining deterministic
linear policies using a simple option pricing problem involving a single
asset. Then, in Section 6.3, we test our approach and compare it to prior
approaches in a higher dimensional setting with eight assets.

We implement our methods in the Julia programming language, version 0.6.4
(Bezanson et al. 2017). For the pathwise optimization method, we implement the
pathwise linear program using the JuMP package (Lubin and Dunning 2015,
Dunning et al. 2017) and solve it using Gurobi, version 9.5 (Gurobi
Optimization, Inc. 2022). All our experiments are executed on Amazon Elastic
Compute Cloud (EC2), on a single instance of type r4.8xlarge (Intel Xeon
E5-2686 v4 processor with 32 virtual CPUs and 244 GBs of memory).

###  6.1 Background

The optimal stopping problem that we will focus on is pricing a Bermudan max-
call option with a knock-out barrier, which was previously studied in Desai et
al. (2012) and later in Ciocan and Mišić (2022). We consider the same family
of problem instances used in those papers, and briefly review the details
here.

In this family of problem instance, the option is dependent on $n$ assets. The
option is exercisable over a period of 3 calendar years with $T=54$ equally
spaced exercise times. The price of each underlying asset follows a geometric
Brownian motion, with the drift set equal to the annualized risk-free rate $r$
and the annualized volatility set to $\sigma$, and each asset is assumed to
start at an initial price of $\bar{p}$. In all of the experiments that we will
present, we shall assume $r=5\%$ and $\sigma=20\%$, as in Desai et al. (2012),
and we will also assume the pairwise correlation between the assets to be
zero. We use $p_{i}(t)$ denote the price of asset $i$ at exercise time $t$.

The option has a strike price $K$ and a knock-out barrier price $B$. The
payoff of the option at any given time is determined by the strike price $K$,
the knock-out barrier value $B$ and the maximum price among the $n$ underlying
assets. If at time $t$ the maximum price of the $n$ underlying assets exceeds
the barrier price $B$, the option is “knocked out” and the payoff becomes zero
for all times $\tilde{t}\geq t$. We let $y(t)$ be an indicator variable that
is 1 if the option has not been knocked out by time $t$ and zero otherwise:

$y(t)=\mathbb{I}\left\\{\max_{1\leq i\leq n,1\leq t^{^{\prime}}\leq
t}p_{i}(t^{^{\prime}})<B\right\\}$ (24)

We let $g^{\prime}(t)$ denote the (undiscounted) payoff from exercising the
option at time $t$, which is defined as follows:

$g^{\prime}(t)=y(t)\cdot\max\left\\{0,\max_{1\leq i\leq
n}p_{i}(t)-K\right\\}.$ (25)

All payoffs are assumed to be discounted continuously according to the risk-
free rate. This implies a discrete discount factor $\beta=\exp(-r\times
3/54)=0.99723$. We can thus define the discounted reward $g(t)$ to be
$g(t)=\beta^{t}\cdot g^{\prime}(t)$, which can be thought of as the payoff
denominated in dollars corresponding to time $t=0$.

We compare three different methods: our randomized policy optimization (RPO)
approach, the least-squares Monte Carlo (LSM) method of Longstaff and Schwartz
(2001) and the pathwise optimization (PO) method of Desai et al. (2012). We
test of each of these methods with a variety of basis functions. In our
presentation of our results, we will denote the different sets of basis
functions as follows:

  * •

one: the constant basis function, equal to 1 for every state.

  * •

prices: the price $p_{i}(t)$ of asset $i$ for $i\in[n]$.

  * •

payoff: the undiscounted payoff $g^{\prime}(t)$.

  * •

KOind: the knock-out (KO) indicator variable $y(t)$.

  * •

pricesKO: the KO adjusted prices $p_{i}(t)\cdot y(t)$ for $i\in[n]$.

  * •

maxpriceKO and max2priceKO: the largest and second largest KO adjusted prices.

  * •

prices2KO: the KO adjusted second-order price terms, $p_{i}(t)\cdot
p_{j}(t)\cdot y(t)$ for $1\leq i\leq j\leq n$.

In our implementation of the RPO approach, we use the backward algorithm,
Algorithm 1. We use the coefficients obtained directly within a deterministic
policy. We solve problem (20) using a custom implementation of Adam, a
momentum-based first-order method (Kingma and Ba 2014, Goodfellow et al.
2016). We follow the parameter defaults in Kingma and Ba (2014), with the
exception of the step size, for which we use $10^{-1}$, as opposed to
$10^{-3}$. Additionally, we do not apply any minibatching, and compute the
full gradient for the entire sample of $\Omega$ trajectories. For each solve
of problem (20), we warm start the Adam algorithm using the coefficients
obtained by LSM; we describe our warm starting scheme in more detail in
Section 10.1 of the ecompanion.

In our implementation of the pathwise optimization method, we follow Desai et
al. (2012) in generating 500 inner samples.

###  6.2 Experiment #1: An illustrative example with $n=1$

In our first experiment, to demonstrate the difference between our approach
and incumbent approaches, we consider an instance of the option with $n=1$
asset; thus, the undiscounted payoff and knock-out indicators can be written
simply as

$g^{\prime}(t)=y(t)\cdot\max\left\\{0,p_{1}(t)-K\right\\},$ (26)
$y(t)=\mathbb{I}\left\\{\max_{1\leq t^{\prime}\leq
t}p_{1}(t^{^{\prime}})<B\right\\}.$ (27)

We set $K=100$ and $B=150$, and vary $\bar{p}$ in the set $\\{90,100,110\\}$.
For each initial price $\bar{p}$, we perform 10 replications, where in each
replication we generate a set of $\Omega=100,000$ trajectories to train each
policy, and 100,000 trajectories for out-of-sample testing.

We test LSM with two basis function architectures: (i) one, and (ii) one and
payoff. Note that both of these basis function architectures imply an exercise
policy that involves simply comparing the undiscounted payoff $g^{\prime}(t)$
to a constant, state-independent threshold. In particular, for (i), the
exercise policy prescribes stop if and only if

$\displaystyle g(t)$ $\displaystyle\geq b_{\textsc{one}}\cdot 1$
$\displaystyle=b_{\textsc{one}},$

which is equivalent to

$g^{\prime}(t)\geq\beta^{-t}b_{\textsc{one}}.$

For (ii), the exercise policy prescribes stop if and only if

$\displaystyle g(t)$ $\displaystyle\geq b_{\textsc{one}}\cdot
1+b_{\textsc{payoff}}\cdot g^{\prime}(t).$

Using the fact that $g(t)=\beta^{t}g^{\prime}(t)$, we can re-arrange the above
inequality into the following threshold rule in terms of the undiscounted
payoff:

$\displaystyle
g^{\prime}(t)\geq\frac{b_{\textsc{one}}}{\beta^{t}-b_{\textsc{payoff}}},$

which holds if $\beta^{t}-b_{\textsc{payoff}}>0$.

For the pathwise optimization method, we test it with the same two basis
function architectures as LSM. Since the pathwise optimization-based policy is
also a greedy policy based on an approximate continuation value function, one
can again represent the policies obtained with the architectures (i) and (ii)
as constant threshold policies. In addition to the policies, we also use the
pathwise optimization solution to compute an upper bound on the optimal reward
using an independent set of 100,000 trajectories (see Desai et al. 2012).

For the randomized policy approach, we test it with a single basis function
architecture, consisting of one and payoff. This results in an exercise policy
where stop is recommended if and only if

$b_{\textsc{one}}\times 1+b_{\textsc{payoff}}\times g^{\prime}(t)>0,$

which is equivalent to the threshold rule

$g^{\prime}(t)>-\frac{b_{\textsc{one}}}{b_{\textsc{payoff}}}$

if $b_{\textsc{payoff}}>0$.

Table 1 shows the out-of-sample performance of the different methods under the
different basis function architectures, as well as the pathwise optimization
upper bounds. For each combination of a policy (a combination of one of the
three methods – LSM, PO and RPO – and a basis function architecture) and an
initial price $\bar{p}$, we report the average out-of-sample reward over the
ten replications. We additionally report the standard error over those ten
replications in parentheses.

From this table, we can see that even though the three methods – LSM, pathwise
optimization and the randomized policy approach – produce policies within the
same policy class, there are significant differences in performance. In
particular, the policy produced by the randomized policy approach
significantly outperforms LSM and pathwise optimization. Comparing to LSM with
one, the randomized policy approach with one and payoff attains an expected
discounted reward that is as much as 89% higher. Comparing to LSM with one and
payoff, which in general performs better than LSM with one, the improvement by
the randomized policy approach is as much as 7.7%. Comparing to PO with one
and with one and payoff, the randomized policy approach attains an improvement
of up to 29% and 35%, respectively. In addition, the PO upper bounds are close
to the performance of the randomized policy approach (for all three initial
prices, the RPO lower bound is within 2.3% of the tightest PO upper bound).
This suggests that for this problem setting, the policy is nearly optimal.
This experiment highlights the fact that even for a simple problem instance
involving only a single asset and the simplest possible policy class, the LSM
method can return a policy that is substantially suboptimal.

|  | Initial price
---|---|---
Method | Basis functions | $\bar{p}=90$ | $\bar{p}=100$ | $\bar{p}=110$
LSM | one | 6.47 (0.010) | 10.82 (0.011) | 16.47 (0.008)
LSM | one, payoff | 11.37 (0.020) | 16.64 (0.024) | 22.01 (0.018)
PO | one | 9.47 (0.017) | 14.79 (0.017) | 20.67 (0.014)
PO | one, payoff | 9.07 (0.032) | 16.01 (0.029) | 22.73 (0.023)
RPO | one, payoff | 12.25 (0.018) | 17.51 (0.023) | 23.04 (0.018)
PO-UB | one | 18.26 (0.018) | 25.47 (0.012) | 32.49 (0.012)
PO-UB | one, payoff | 12.54 (0.009) | 17.88 (0.009) | 23.55 (0.005)
Table 1: Out-of-sample performance of different policies in $n=1$ experiment.

It is also interesting to consider what the thresholds produced by the
different methods look like. Figure 1 plots the thresholds for the five
different policies at each period in the time horizon, for a single
replication with $\bar{p}=110$. We can see that there are substantial
differences in the policies. The thresholds for the LSM policies are generally
lower than those of the RPO policy, which implies that the LSM policies in
general stop earlier in the time horizon, when the reward will generally be
lower. The PO policy with one also results in thresholds that are lower than
the RPO policy. On the other hand, the PO policy with one and payoff results
in thresholds that are higher than those from RPO for roughly the first 40
periods; as a result, the PO policy may miss opportunities to stop earlier in
the horizon. Interestingly, the thresholds for the LSM and PO policies begin
rapidly decaying earlier in the time horizon than RPO (for LSM with one, LSM
with one and payoff, and PO with one, this starts right around the beginning
of the horizon; for PO with one and payoff, this starts at around $t=34$). For
RPO, there is a slow and steady decrease in the threshold until about $t=48$,
where the threshold begins to decrease much more quickly.

Figure 1: Plot of thresholds for policies in $n=1$ experiment.

###  6.3 Experiment #2: multiple assets

In our second experiment, we consider instances of our option pricing problem
with more than one asset. We specifically consider instances with $n$ varying
in $\\{4,8,16\\}$. As in the previous experiment, we vary $\bar{p}$ in
$\\{90,100,110\\}$ and set the strike price $K=100$. Following Desai et al.
(2012), we set the barrier price $B=170$. For each initial price $\bar{p}$ and
each value of $n$, we perform ten replications, where in each replication we
generate a training set of $\Omega=20,000$ trajectories, and a testing set of
100,000 trajectories. In what follows, we focus on the results for $n=8$, and
relegate the performance results for $n=4$ and $n=16$ to Section 10.2 of the
ecompanion.

We again test the LSM, PO and RPO methods with a variety of basis function
architectures. We also obtain upper bounds from the PO method by reporting the
objective value of the pathwise optimization linear program, which is a biased
upper bound on the expected reward. We opt for this simpler approach over
producing an unbiased upper bound (by generating an independent set of
trajectories and the corresponding inner paths; see Desai et al. 2012) due to
the significant computation time required in generating the inner paths. We
note that this inexact approach has also been used in other work that has
implemented the PO method (Ciocan and Mišić 2022).

Table 2 reports the out-of-sample performance of the LSM, PO and RPO methods,
as well as the (biased) PO upper bound, for the different basis function
architectures. Note that the table is organized so that groups of policies
corresponding to the same policy class are grouped together. (For example,
LSM/PO with one and prices, LSM/PO with one, prices and payoff, and RPO with
one, prices and payoff appear together.)

|  | Initial price
---|---|---
Method | Basis function architecture | $\bar{p}=90$ | $\bar{p}=100$ | $\bar{p}=110$
LSM | one | 33.77 (0.023) | 38.67 (0.010) | 43.13 (0.013)
LSM | one, payoff | 41.18 (0.033) | 43.21 (0.037) | 45.00 (0.027)
PO | one | 41.08 (0.015) | 45.91 (0.021) | 48.84 (0.016)
PO | one, payoff | 22.25 (0.177) | 16.07 (0.144) | 11.57 (0.119)
RPO | one, payoff | 45.30 (0.022) | 51.10 (0.012) | 53.46 (0.053)
PO-UB | one | 52.19 (0.021) | 57.45 (0.020) | 60.35 (0.010)
PO-UB | one, payoff | 46.37 (0.024) | 52.68 (0.051) | 56.02 (0.047)
LSM | prices | 33.81 (0.024) | 38.54 (0.013) | 43.02 (0.013)
LSM | prices, payoff | 39.56 (0.030) | 41.74 (0.033) | 44.12 (0.025)
PO | prices | 40.93 (0.016) | 44.83 (0.014) | 47.49 (0.016)
PO | prices, payoff | 22.28 (0.124) | 15.89 (0.116) | 11.04 (0.091)
RPO | prices, payoff | 44.49 (0.018) | 49.77 (0.029) | 52.23 (0.035)
PO-UB | prices | 51.40 (0.023) | 57.20 (0.011) | 60.32 (0.010)
PO-UB | prices, payoff | 46.36 (0.024) | 52.64 (0.050) | 55.94 (0.045)
LSM | pricesKO | 41.42 (0.017) | 49.35 (0.017) | 53.10 (0.009)
LSM | pricesKO, payoff | 44.04 (0.017) | 49.62 (0.012) | 52.67 (0.006)
PO | pricesKO | 44.32 (0.017) | 49.82 (0.015) | 52.77 (0.018)
PO | pricesKO, payoff | 44.18 (0.017) | 50.06 (0.015) | 53.19 (0.007)
RPO | pricesKO, payoff | 44.53 (0.019) | 50.11 (0.013) | 53.27 (0.010)
PO-UB | pricesKO | 48.63 (0.015) | 53.12 (0.010) | 55.57 (0.011)
PO-UB | pricesKO, payoff | 46.15 (0.023) | 52.06 (0.034) | 55.08 (0.024)
LSM | KOind | 39.37 (0.020) | 48.09 (0.030) | 53.26 (0.017)
LSM | KOind, payoff | 44.26 (0.018) | 50.07 (0.016) | 53.19 (0.010)
PO | KOind | 43.87 (0.017) | 50.85 (0.013) | 54.35 (0.009)
PO | KOind, payoff | 44.79 (0.025) | 50.89 (0.013) | 53.91 (0.008)
RPO | KOind, payoff | 45.45 (0.023) | 51.37 (0.011) | 54.50 (0.010)
PO-UB | KOind | 49.29 (0.016) | 53.47 (0.015) | 55.69 (0.009)
PO-UB | KOind, payoff | 46.15 (0.023) | 52.07 (0.033) | 55.05 (0.021)
LSM | pricesKO, KOind | 41.84 (0.015) | 49.37 (0.021) | 53.46 (0.009)
LSM | pricesKO, KOind, payoff | 43.77 (0.019) | 49.87 (0.018) | 53.11 (0.007)
PO | pricesKO, KOind | 44.01 (0.018) | 50.91 (0.013) | 54.27 (0.008)
PO | pricesKO, KOind, payoff | 43.98 (0.021) | 50.69 (0.012) | 53.84 (0.007)
RPO | pricesKO, KOind, payoff | 44.08 (0.023) | 50.57 (0.031) | 54.23 (0.010)
PO-UB | pricesKO, KOind | 48.45 (0.020) | 53.09 (0.011) | 55.56 (0.010)
PO-UB | pricesKO, KOind, payoff | 46.14 (0.022) | 52.05 (0.033) | 55.04 (0.022)
LSM | pricesKO, prices2KO, KOind | 43.32 (0.022) | 49.86 (0.019) | 53.26 (0.013)
LSM | pricesKO, prices2KO, KOind, payoff | 44.05 (0.022) | 49.92 (0.019) | 53.14 (0.012)
PO | pricesKO, prices2KO, KOind | 44.33 (0.018) | 50.78 (0.014) | 53.93 (0.006)
PO | pricesKO, prices2KO, KOind, payoff | 44.65 (0.018) | 50.65 (0.016) | 53.77 (0.008)
RPO | pricesKO, prices2KO, KOind, payoff | 44.62 (0.015) | 50.74 (0.021) | 54.03 (0.013)
PO-UB | pricesKO, prices2KO, KOind | 47.09 (0.016) | 52.43 (0.019) | 55.25 (0.010)
PO-UB | pricesKO, prices2KO, KOind, payoff | 46.09 (0.022) | 51.98 (0.033) | 55.00 (0.022)
LSM | pricesKO, KOind, maxpriceKO, max2priceKO | 43.83 (0.018) | 49.89 (0.023) | 53.10 (0.008)
LSM | pricesKO, KOind, maxpriceKO, max2priceKO, payoff | 43.83 (0.017) | 49.88 (0.022) | 53.10 (0.008)
PO | pricesKO, KOind, maxpriceKO, max2priceKO | 43.90 (0.026) | 50.66 (0.014) | 53.83 (0.008)
PO | pricesKO, KOind, maxpriceKO, max2priceKO, payoff | 44.04 (0.023) | 50.65 (0.015) | 53.82 (0.007)
RPO | pricesKO, KOind, maxpriceKO, max2priceKO, payoff | 44.14 (0.016) | 50.55 (0.030) | 54.20 (0.010)
PO-UB | pricesKO, KOind, maxpriceKO, max2priceKO | 46.13 (0.017) | 52.04 (0.033) | 55.04 (0.022)
PO-UB | pricesKO, KOind, maxpriceKO, max2priceKO, payoff | 46.12 (0.023) | 52.04 (0.033) | 55.03 (0.021)
Table 2: Out-of-sample performance for different policies, for $n=8$ assets.

From this table, we can see that within each policy class, the RPO method in
general outperforms the LSM method. In some cases the difference can be
substantial: for example, with $\bar{p}=90$ and the policy class corresponding
to linear functions of KOind and payoff, the best LSM policy achieves a reward
of 44.26 whereas RPO achieves a reward of 45.45, which is an improvement of
2.6%. Relative to the PO method, the performance of the RPO method in most
cases is better, and in a few cases is slightly worse (for example, for
$\bar{p}=110$ and the pricesKO, KOind and payoff policy class, the best PO
policy attains a reward of 54.27 compared to 54.23 for the RPO policy).

In addition to the comparison of the methods within a fixed policy class, it
is also insightful to compare the methods across policy classes, i.e., to
think of what is the best attainable performance across any basis function
architecture. In this regard, the highest rewards for all three initial prices
are attained by the RPO method with KOind and payoff as the basis functions
(45.45 for $\bar{p}=90$, 51.37 for $\bar{p}=100$, 54.50 for $\bar{p}=110$).
The best performance for the LSM method across any of the basis function
architectures is substantially lower (44.26 for $\bar{p}=90$, 50.07 for
$\bar{p}=100$, 53.46 for $\bar{p}=110$). The best performance for the PO
method is better, but still lower (44.79 for $\bar{p}=90$, 50.91 for
$\bar{p}=100$, 54.35 for $\bar{p}=110$).

Beside the performance, it is also useful to compare the methods in terms of
computation time. Table 3 below shows the average computation time for each of
the methods. For LSM, this is just the time to apply the LSM algorithm. For
PO, this time includes the time to solve the PO linear program using Gurobi
and the time to execute the regression, as well as the time to generate the
inner paths and the time to formulate problem in JuMP. For RPO, this time is
the time to apply the backward algorithm (Algorithm 1), which includes the
time to solve the stage $t$ problem (20) using Adam, but does not include the
time to obtain the initial starting point using LSM.

|  | Initial price
---|---|---
Method | Basis function architecture | $\bar{p}=90$ | $\bar{p}=100$ | $\bar{p}=110$
LSM | one | 2.34 (0.248) | 1.45 (0.020) | 2.23 (0.245)
LSM | one, payoff | 2.22 (0.238) | 2.21 (0.219) | 2.32 (0.223)
PO | one | 737.90 (49.467) | 632.84 (39.330) | 734.50 (55.495)
PO | one, payoff | 821.11 (20.357) | 652.49 (22.014) | 727.22 (25.883)
RPO | one, payoff | 80.65 (5.193) | 332.82 (28.783) | 305.96 (21.902)
LSM | KOind | 2.32 (0.159) | 3.01 (0.207) | 2.37 (0.267)
LSM | KOind, payoff | 2.79 (0.318) | 3.73 (0.357) | 3.70 (0.335)
PO | KOind | 899.30 (21.038) | 851.05 (18.996) | 838.18 (27.319)
PO | KOind, payoff | 944.45 (26.243) | 819.51 (20.691) | 822.24 (25.099)
RPO | KOind, payoff | 4.87 (0.541) | 16.86 (1.794) | 20.41 (1.977)
LSM | prices | 2.22 (0.190) | 3.09 (0.286) | 3.02 (0.218)
LSM | prices, payoff | 3.18 (0.294) | 4.35 (0.291) | 3.25 (0.203)
PO | prices | 902.42 (27.296) | 913.33 (25.858) | 938.11 (18.843)
PO | prices, payoff | 1098.98 (21.250) | 943.94 (33.928) | 1070.94 (32.581)
RPO | prices, payoff | 174.12 (11.573) | 565.27 (21.773) | 584.55 (24.491)
LSM | pricesKO | 3.64 (0.334) | 4.32 (0.493) | 4.12 (0.383)
LSM | pricesKO, payoff | 2.43 (0.248) | 3.07 (0.367) | 3.23 (0.303)
PO | pricesKO | 1163.28 (19.574) | 1092.48 (13.862) | 1093.83 (17.630)
PO | pricesKO, payoff | 1269.60 (25.366) | 1155.69 (22.082) | 1158.41 (34.489)
RPO | pricesKO, payoff | 6.55 (0.719) | 14.52 (1.077) | 14.56 (1.329)
LSM | pricesKO, KOind | 3.90 (0.302) | 5.05 (0.347) | 4.62 (0.346)
LSM | pricesKO, KOind, payoff | 3.03 (0.454) | 3.84 (0.165) | 3.30 (0.371)
PO | pricesKO, KOind | 1268.21 (35.401) | 1099.33 (27.684) | 1114.49 (23.758)
PO | pricesKO, KOind, payoff | 1395.44 (23.614) | 1251.74 (35.740) | 1202.02 (23.449)
RPO | pricesKO, KOind, payoff | 10.46 (1.729) | 22.45 (1.831) | 22.43 (2.184)
LSM | pricesKO, prices2KO, KOind | 8.41 (0.353) | 7.96 (0.429) | 8.02 (0.552)
LSM | pricesKO, prices2KO, KOind, payoff | 6.61 (0.334) | 11.39 (1.338) | 8.59 (0.520)
PO | pricesKO, prices2KO, KOind | 4712.40 (48.063) | 4303.43 (186.668) | 4824.68 (190.066)
PO | pricesKO, prices2KO, KOind, payoff | 3347.31 (21.754) | 4884.33 (188.597) | 4787.41 (150.816)
RPO | pricesKO, prices2KO, KOind, payoff | 38.18 (2.942) | 87.08 (8.357) | 66.91 (5.050)
LSM | pricesKO, KOind, maxpriceKO, max2priceKO | 2.63 (0.136) | 4.39 (0.388) | 4.95 (0.431)
LSM | pricesKO, KOind, maxpriceKO, max2priceKO, payoff | 2.82 (0.176) | 5.48 (0.480) | 5.44 (0.513)
PO | pricesKO, KOind, maxpriceKO, max2priceKO | 1026.37 (9.217) | 1561.72 (50.908) | 1534.24 (23.832)
PO | pricesKO, KOind, maxpriceKO, max2priceKO, payoff | 1012.27 (6.559) | 1597.34 (37.282) | 1491.44 (28.252)
RPO | pricesKO, KOind, maxpriceKO, max2priceKO, payoff | 12.37 (0.710) | 37.34 (3.715) | 33.59 (3.213)
Table 3: Computation time for different policies, for $n=8$ assets.

From this table, we can see that LSM in general requires the least amount of
computation time, requiring no more than 12 seconds on average. The RPO method
requires more time, but in all cases its computation time is reasonable: in
general, it requires no more than 585 seconds (approximately 10 minutes) on
average. We note that the computation time for RPO is in general not monotonic
in in the size of the basis function architecture: for example, RPO with one
and payoff (total of 2 basis functions) requires more time than RPO with
pricesKO, prices2KO, KOind, payoff (total of 46 basis functions). This is
likely due to the non-convex nature of the objective function in the period
$t$ problem of the backward algorithm. In particular, with one and payoff, the
initial starting point produced by LSM could be further away from an
approximately stationary point and Adam may require more iterations before
termination, whereas with pricesKO, prices2KO, KOind and payoff it may be
closer and Adam may terminate more quickly.

Comparing to the PO method, we can see that the PO method requires a
significantly larger amount of time than RPO, with the average computation
time ranging from about 632 seconds ($\bar{p}=100$, PO with one; just over 10
minutes) to 4884 seconds ($\bar{p}=100$, PO with pricesKO, prices2KO, KOind,
payoff; roughly 80 minutes). The majority of this time comes from the
generation of the inner paths, which is in general a computationally intensive
task. Although RPO occasionally performs slightly worse than PO as we saw in
Table 2, RPO may still be preferable to PO for obtaining good policies due to
the significant computation times required by PO.

Lastly, we note that the computation time of the RPO method is sensitive to
several implementation decisions. As alluded to above, the choice of starting
point for problem (20), as well as the number of starting points used, will
directly affect the time required for Adam to converge. Another decision is
the step size used for Adam. In our experimentation, a smaller step size would
lead to slower convergence, but would generally result in better solutions.

##  7 Conclusion

In this paper, we consider the problem of designing randomized policies for
high-dimensional optimal stopping problems. We formulate the problem as an SAA
problem, prove its convergence properties and establish generalization error
bounds on the out-of-sample reward. Based on the NP-Hardness of the SAA
problem, we develop a backward optimization heuristic for approximately
solving the SAA problem. We show in the numerical experiments that our
heuristic can achieve better performance than the LSM method and is better or
comparable to the PO method.

There are at least two interesting directions for future work. First, it would
be interesting to further understand the behavior of the non-convex objective
function of the randomized policy SAA problem and of the period $t$ problem in
the backward optimization heuristic, and to understand how one can obtain high
quality solutions to both of these problems. In particular, our
experimentation suggests that quality of the solution in the period $t$
problem is fairly sensitive to the choice of starting point, so it would be
interesting to explore other ways of selecting initial points, as well as
other methods beside Adam for solving the period $t$ problem. Second, it would
be interesting to explore whether our methodology can be generalized to other
stochastic dynamic programming problems outside of optimal stopping.

## References

  * Akçakuş and Mišić [2021] İ. Akçakuş and V. V. Mišić.  Exact logit-based product design.  _Available at SSRN 3875986_ , 2021.
  * Andersen and Broadie [2004] L. Andersen and M. Broadie.  Primal-dual simulation algorithm for pricing multidimensional American options.  _Management Science_ , 50(9):1222–1234, 2004\.
  * Bertsimas and Kallus [2020] D. Bertsimas and N. Kallus.  From predictive to prescriptive analytics.  _Management Science_ , 66(3):1025–1044, 2020\.
  * Bezanson et al. [2017] J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah.  Julia: A fresh approach to numerical computing.  _SIAM Review_ , 59(1):65–98, 2017.
  * Brown and Smith [2022] D. B. Brown and J. E. Smith.  Information relaxations and duality in stochastic dynamic programs: A review and tutorial.  _Working paper_ , 2022.
  * Brown et al. [2010] D. B. Brown, J. E. Smith, and P. Sun.  Information relaxations and duality in stochastic dynamic programs.  _Operations research_ , 58(4-part-1):785–801, 2010.
  * Candes et al. [2015] E. J. Candes, X. Li, and M. Soltanolkotabi.  Phase retrieval via wirtinger flow: Theory and algorithms.  _IEEE Transactions on Information Theory_ , 61(4):1985–2007, 2015.
  * Carriere [1996] J. F. Carriere.  Valuation of the early-exercise price for derivative securities using simulations and splines.  _Insurance: Mathematics and Economics_ , 19(1):19–30, 1996.
  * Chen and Glasserman [2007] N. Chen and P. Glasserman.  Additive and multiplicative duals for American option pricing.  _Finance and Stochastics_ , 11(2):153–179, 2007\.
  * Ciocan and Mišić [2022] D. F. Ciocan and V. V. Mišić.  Interpretable optimal stopping.  _Management Science_ , 68(3):1616–1638, 2022\.
  * Cohen et al. [2017] M. C. Cohen, N.-H. Z. Leung, K. Panchamgam, G. Perakis, and A. Smith.  The impact of linear optimization on promotion planning.  _Operations Research_ , 65(2):446–468, 2017.
  * Desai et al. [2012] V. V. Desai, V. F. Farias, and C. C. Moallemi.  Pathwise optimization for optimal stopping problems.  _Management Science_ , 58(12):2292–2308, 2012\.
  * Dunning et al. [2017] I. Dunning, J. Huchette, and M. Lubin.  JuMP: A modeling language for mathematical optimization.  _SIAM Review_ , 59(2):295–320, 2017.
  * Elmachtoub and Grigas [2021] A. N. Elmachtoub and P. Grigas.  Smart “predict, then optimize”.  _Management Science_ , 2021.
  * Ferreira et al. [2016] K. J. Ferreira, B. H. A. Lee, and D. Simchi-Levi.  Analytics for an online retailer: Demand forecasting and price optimization.  _Manufacturing & Service Operations Management_, 18(1):69–88, 2016.
  * Garey and Johnson [1979] M. R. Garey and D. S. Johnson.  _Computers and intractability_.  W. H. Freeman New York, 1979.
  * Ge et al. [2015] R. Ge, F. Huang, C. Jin, and Y. Yuan.  Escaping from saddle points—online stochastic gradient for tensor decomposition.  In _Conference on learning theory_ , pages 797–842. PMLR, 2015.
  * Goodfellow et al. [2016] I. Goodfellow, Y. Bengio, and A. Courville.  _Deep learning_.  MIT press, 2016.
  * Gurobi Optimization, Inc. [2022] Gurobi Optimization, Inc.  Gurobi Optimizer Reference Manual, 2022.  URL http://www.gurobi.com.
  * Haugh and Kogan [2004] M. B. Haugh and L. Kogan.  Pricing American options: a duality approach.  _Operations Research_ , 52(2):258–270, 2004.
  * Jain and Kar [2017] P. Jain and P. Kar.  Non-convex optimization for machine learning.  _Foundations and Trends® in Machine Learning_ , 10(3-4):142–336, 2017.
  * Kingma and Ba [2014] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Liang [2018] P. Liang.  CS229T/STAT231: Statistical Learning Theory (Winter 2016) Lecture Notes, 2018.  URL https://github.com/percyliang/cs229t/blob/master/lectures/notes.pdf.
  * Longstaff and Schwartz [2001] F. A. Longstaff and E. S. Schwartz.  Valuing American options by simulation: a simple least-squares approach.  _The Review of Financial Studies_ , 14(1):113–147, 2001.
  * Lubin and Dunning [2015] M. Lubin and I. Dunning.  Computing in operations research using Julia.  _INFORMS Journal on Computing_ , 27(2):238–248, 2015.
  * Maurer [2016] A. Maurer.  A vector-contraction inequality for rademacher complexities.  In _International Conference on Algorithmic Learning Theory_ , pages 3–17. Springer, 2016.
  * Mohri et al. [2018] M. Mohri, A. Rostamizadeh, and A. Talwalkar.  _Foundations of machine learning_.  MIT press, 2018.
  * Munkres [1991] J. R. Munkres.  _Analysis on manifolds_.  Addison-Wesley Publishing Company, 1991.
  * Netrapalli et al. [2015] P. Netrapalli, P. Jain, and S. Sanghavi.  Phase retrieval using alternating minimization.  _IEEE Transactions on Signal Processing_ , 63(18):4814–4826, 2015.
  * Okamoto [1973] M. Okamoto.  Distinctness of the eigenvalues of a quadratic form in a multivariate sample.  _The Annals of Statistics_ , pages 763–765, 1973.
  * Rogers [2002] L. C. G. Rogers.  Monte Carlo valuation of American options.  _Mathematical Finance_ , 12(3):271–286, 2002\.
  * Shapiro et al. [2014] A. Shapiro, D. Dentcheva, and A. Ruszczyński.  _Lectures on stochastic programming: modeling and theory_.  SIAM, 2014.
  * Sturt [2021] B. Sturt.  A nonparametric algorithm for optimal stopping based on robust optimization.  _arXiv preprint arXiv:2103.03300_ , 2021.
  * Tsitsiklis and Van Roy [2001] J. N. Tsitsiklis and B. Van Roy.  Regression methods for pricing complex American-style options.  _IEEE Transactions on Neural Networks_ , 12(4):694–703, 2001.
  * Udell and Boyd [2013] M. Udell and S. Boyd.  Maximizing a sum of sigmoids.  _Optimization and Engineering_ , pages 1–25, 2013.

Electronic companion for “Randomized Policy Optimization for Optimal Stopping”

##  8 Proofs

###  8.1 Proof of Theorem 3.1

We prove this result in two steps. We first show that
$\max_{\mathbf{b}\in\mathcal{B}}\hat{J}_{D}(\mathbf{b})\leq\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}\hat{J}_{R}(\tilde{\mathbf{b}})$,
and then show that
$\sup_{\mathbf{b}\in\mathcal{B}}\hat{J}_{D}(\mathbf{b})\geq\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}\hat{J}_{R}(\tilde{\mathbf{b}})$.

_Proof of
$\sup_{\mathbf{b}\in\mathcal{B}}\hat{J}_{D}(\mathbf{b})\leq\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}\hat{J}_{R}(\tilde{\mathbf{b}})$:_
To establish this, fix any deterministic policy weight vector
$\mathbf{b}\in\mathcal{B}$.

Without loss of generality, we can assume that
$\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))$ satisfies either
$\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))>0$ or
$\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))<0$ for each $\omega$ and $t$.
(Stated differently, $\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))$ cannot
be exactly equal to zero.) If this is not the case, then using Assumption 3.5,
we can modify the weight $b_{t,1}$ of the constant basis function
$\phi_{1}(\mathbf{x})=1$ for any period $t$ such that the condition is
satisfied, and the sample-average reward $\hat{J}_{D}(\mathbf{b})$ remains
unchanged.

Now, consider the randomized policy weight vector $\mathbf{b}^{\prime}$
defined as $\mathbf{b}^{\prime}=\alpha\mathbf{b}$, where $\alpha>0$. Observe
now that, since $\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))>0$ or
$\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))<0$ for each $\omega$ and $t$,
we have that

$\displaystyle\lim_{\alpha\to+\infty}\sigma(\mathbf{b}^{\prime}_{t}\bullet\Phi(\mathbf{x}(\omega,t)))$
$\displaystyle=\lim_{\alpha\to+\infty}\sigma(\alpha\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t)))$
$\displaystyle=\left\\{\begin{array}[]{ll}+1&\text{if}\
\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))>0,\\\ 0&\text{if}\
\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))\leq 0\\\ \end{array}\right.$
$\displaystyle=\mathbb{I}\\{\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))>0\\}.$

Consequently, we have that

$\displaystyle\lim_{\alpha\to+\infty}\hat{J}_{R}(\mathbf{b}^{\prime})$
$\displaystyle=\lim_{\alpha\to+\infty}\hat{J}_{R}(\alpha\mathbf{b})$
$\displaystyle=\lim_{\alpha\to+\infty}\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}\sum_{t=1}^{T}g(t,\mathbf{x}(\omega,t))\cdot\prod_{t^{\prime}=1}^{t-1}(1-\sigma(\alpha\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime}))))\cdot\sigma(\alpha\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t)))$
$\displaystyle=\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}\sum_{t=1}^{T}g(t,\mathbf{x}(\omega,t))\cdot\prod_{t^{\prime}=1}^{t-1}(1-\mathbb{I}\\{\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime}))>0\\})\cdot\mathbb{I}\\{\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))>0\\}$
$\displaystyle=\hat{J}_{D}(\mathbf{b}).$

Since $\mathbf{b}^{\prime}\in\tilde{\mathcal{B}}=\mathbb{R}^{KT}$, we have
that
$\hat{J}_{R}(\alpha\mathbf{b})\leq\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}\hat{J}_{R}(\tilde{\mathbf{b}})$
for all $\alpha>0$; as a result, the limit of $\hat{J}_{R}(\alpha\mathbf{b})$
as $\alpha\to\infty$ must also be upper bounded by
$\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}\hat{J}_{R}(\tilde{\mathbf{b}})$.
We thus have that
$\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}\hat{J}_{R}(\tilde{\mathbf{b}})$
is an upper bound on $\hat{J}_{D}(\mathbf{b})$ for any
$\mathbf{b}\in\mathcal{B}$.

By the definition of the supremum, it therefore follows that

$\sup_{\mathbf{b}\in\mathcal{B}}\hat{J}_{D}(\mathbf{b})\leq\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}\hat{J}_{R}(\tilde{\mathbf{b}}).$
(28)

_Proof of
$\sup_{\mathbf{b}\in\mathcal{B}}\hat{J}_{D}(\mathbf{b})\geq\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}\hat{J}_{R}(\tilde{\mathbf{b}})$:_
To establish this inequality, fix a randomized policy weight vector
$\tilde{\mathbf{b}}$ from $\tilde{\mathcal{B}}$. The key idea in the proof is
that the logistic response function $\sigma(\cdot)$ can also be viewed as the
cumulative distribution function (CDF) of a logistic random variable. Recall
that a logistic random variable, $\xi\sim\mathrm{Logistic}(\mu,s)$, where
$\mu$ is the location parameter and $s$ is the scale parameter, has CDF given
by

$\mathbb{P}(\xi<t)=\frac{e^{(t-\mu)/s}}{1+e^{(t-\mu)/s}}.$

Thus, the logistic response function $\sigma(\cdot)$ corresponds to a
$\mathrm{Logistic}(0,1)$ random variable.

Armed with this insight, let us define $T$ i.i.d. $\mathrm{Logistic}(0,1)$
random variables, $\xi_{1},\dots,\xi_{T}$. Observe that we can write the
reward of the randomized policy as

$\displaystyle\hat{J}_{R}(\tilde{\mathbf{b}})$
$\displaystyle=\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}\sum_{t=1}^{T}g(t,\mathbf{x}(\omega,t))\cdot\prod_{t^{\prime}=1}^{t-1}(1-\sigma(\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime}))))\cdot\sigma(\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(\omega,t)))$
$\displaystyle=\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}\sum_{t=1}^{T}g(t,\mathbf{x}(\omega,t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{P}(\xi_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime})))\cdot\mathbb{P}(\xi_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(\omega,t)))$
$\displaystyle=\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}\sum_{t=1}^{T}g(t,\mathbf{x}(\omega,t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{E}[\mathbb{I}\\{\xi_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime}))\\}]\cdot\mathbb{E}[\mathbb{I}\\{\xi_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(\omega,t))\\}]$
$\displaystyle=\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}\sum_{t=1}^{T}g(t,\mathbf{x}(\omega,t))\cdot\mathbb{E}\left[\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\xi_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime}))\\}\cdot\mathbb{I}\\{\xi_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(\omega,t))\\}\right]$
$\displaystyle=\mathbb{E}\left[\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}\sum_{t=1}^{T}g(t,\mathbf{x}(\omega,t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\xi_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime}))\\}\cdot\mathbb{I}\\{\xi_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(\omega,t))\\}\right]$
(29)

where the second equality follows by the definition of each $\xi_{t}$ as a
$\mathrm{Logistic}(0,1)$ random variable; the third by the fact that
$\mathbb{P}(A)=\mathbb{E}[\mathbb{I}\\{A\\}]$ for any event $A$; the fourth by
the fact that $\xi_{1},\dots,\xi_{T}$ are independent; and the fifth by the
linearity of expectation.

We now observe that there must exist values
$\bar{\xi}_{1},\dots,\bar{\xi}_{T}$ for which the random variable in (29) is
at least its expected value, i.e.,

$\displaystyle\mathbb{E}\left[\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}\sum_{t=1}^{T}g(t,\mathbf{x}(\omega,t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\xi_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime}))\\}\cdot\mathbb{I}\\{\xi_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(\omega,t))\\}\right]$
$\displaystyle\leq\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}\sum_{t=1}^{T}g(t,\mathbf{x}(\omega,t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\bar{\xi}_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime}))\\}\cdot\mathbb{I}\\{\bar{\xi}_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(\omega,t))\\}.$

Finally, let us define a deterministic policy weight vector $\mathbf{b}$ as

$b_{t,k}=\left\\{\begin{array}[]{ll}\tilde{b}_{t,k}-\bar{\xi}_{t}&\text{if}\
k=1,\\\ \tilde{b}_{t,k}&\text{if}\ k\neq 1,\end{array}\right.$

for each $t$ and $k$. In other words, we decrease the weight on the constant
basis function exactly by $\bar{\xi}_{t}$, the realized value of the $t$th
logistic random variable. (Note that this construction is made possible by
Assumption 3.5.) By constructing $\mathbf{b}$ in this way, we obtain that

$\displaystyle\bar{\xi}_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(\omega,t))$
$\displaystyle\Leftrightarrow\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(\omega,t))-\bar{\xi}_{t}>0$
$\displaystyle\Leftrightarrow\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))>0$

for each $\omega$ and $t$. We thus have that

$\displaystyle\hat{J}_{R}(\tilde{\mathbf{b}})$
$\displaystyle=\mathbb{E}\left[\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}\sum_{t=1}^{T}g(t,\mathbf{x}(\omega,t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\xi_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime}))\\}\cdot\mathbb{I}\\{\xi_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(\omega,t))\\}\right]$
$\displaystyle\leq\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}\sum_{t=1}^{T}g(t,\mathbf{x}(\omega,t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\bar{\xi}_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime}))\\}\cdot\mathbb{I}\\{\bar{\xi}_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(\omega,t))\\}$
$\displaystyle=\frac{1}{\Omega}\sum_{\omega=1}^{\Omega}\sum_{t=1}^{T}g(t,\mathbf{x}(\omega,t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(\omega,t^{\prime}))\leq
0\\}\cdot\mathbb{I}\\{\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(\omega,t))>0\\}$
$\displaystyle=\hat{J}_{D}(\mathbf{b})$

As a result, the reward of a randomized policy weight vector
$\tilde{\mathbf{b}}$ can be bounded by the reward of a deterministic policy
weight vector $\mathbf{b}$. Thus,
$\sup_{\mathbf{b}\in\mathcal{B}}\hat{J}_{D}(\mathbf{b})$ is a valid upper
bound on $\hat{J}_{R}(\tilde{\mathbf{b}})$ for any
$\tilde{\mathbf{b}}\in\mathcal{B}$. By the definition of the supremum as the
least upper bound, we consequently have

$\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}\hat{J}_{R}(\tilde{\mathbf{b}})\leq\sup_{\mathbf{b}\in\mathcal{B}}\hat{J}_{D}(\mathbf{b}).$
(30)

Since we have shown both inequalities, it follows
$\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}\hat{J}_{R}(\tilde{\mathbf{b}})=\sup_{\mathbf{b}\in\mathcal{B}}\hat{J}_{D}(\mathbf{b})$,
as required. $\square$

###  8.2 Proof of Theorem 3.2

We prove this in two steps: first, by showing that
$\sup_{\mathbf{b}\in\mathcal{B}}J_{D}(\mathbf{b})\leq\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}J_{R}(\tilde{\mathbf{b}})$,
and then by showing that
$\sup_{\mathbf{b}\in\mathcal{B}}J_{D}(\mathbf{b})\geq\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}J_{R}(\tilde{\mathbf{b}})$.

_Step 1:
$\sup_{\mathbf{b}\in\mathcal{B}}J_{D}(\mathbf{b})\leq\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}J_{R}(\tilde{\mathbf{b}})$_.
Let $\mathbf{b}\in\mathcal{B}$. Let $\alpha>0$ be a constant, and define
$\tilde{\mathbf{b}}$ as follows:

$\tilde{\mathbf{b}}_{t}=\left\\{\begin{array}[]{ll}\alpha\mathbf{b}_{t}&\text{if}\
\mathbf{b}_{t}\neq\mathbf{0},\\\ -\alpha\mathbf{e}_{1}&\text{if}\
\mathbf{b}_{t}=\mathbf{0},\end{array}\right.$

where $\mathbf{0}$ is a $K$-dimensional vector of zeros and
$\mathbf{e}_{1}=(1,0,\dots,0)$ is the first standard basis vector for
$\mathbb{R}^{K}$.

Let $I=\\{t\in[T]\mid\mathbf{b}_{t}\neq\mathbf{0}\\}$, and for each $t\in I$,
define the set $Q_{t}$ as

$Q_{t}=\\{(y_{2},\dots,y_{K})\in\mathbb{R}^{K-1}\mid
b_{t,1}+\sum_{k=2}^{K}y_{k}b_{t,k}=0\\}.$ (31)

Observe that $Q_{t}$ is a hyperplane in $\mathbb{R}^{K-1}$, so by Assumption
3.1, we have that

$\mathbb{P}(\Phi_{2:K}(\mathbf{x}(t))\in Q_{t})=0.$ (32)

We note that the event $\Phi_{2:K}(\mathbf{x}(t))\in Q_{t}$ is exactly the
event that the inner product of $\mathbf{b}_{t}$ and $\Phi(\mathbf{x}(t))$ is
equal to zero (i.e., we are on the boundary between choosing to stop or to
continue): in particular, we have that

$\displaystyle\Phi_{2:K}(\mathbf{x}(t))\in Q_{t}$
$\displaystyle\Leftrightarrow
b_{t,1}+\sum_{k=2}^{K}\phi_{k}(\mathbf{x}(t))b_{t,k}=0$
$\displaystyle\Leftrightarrow\sum_{k=1}^{K}\phi_{k}(\mathbf{x}(t))b_{t,k}=0$
$\displaystyle\Leftrightarrow\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t))=0$

where the third step follows because $\phi_{1}(\mathbf{x})=1$ for all
$\mathbf{x}\in\mathcal{X}$ (this is Assumption 3.5).

Let $E$ be the event defined as

$E=\bigcup_{t\in I}\\{\Phi_{2:K}(\mathbf{x}(t))\in Q_{t}\\}.$ (33)

Observe that $\mathbb{P}(E)=0$ since

$\displaystyle\mathbb{P}(E)$ $\displaystyle=\mathbb{P}\left(\bigcup_{t\in
I}\\{\Phi_{2:K}(\mathbf{x}(t))\in Q_{t}\\}\right)$
$\displaystyle\leq\sum_{t\in I}\mathbb{P}(\Phi_{2:K}(\mathbf{x}(t))\in Q_{t})$
$\displaystyle=0,$

where the inequality follows by the countable subadditivity of $\mathbb{P}$.

Observe also that for any $(\mathbf{x}(1),\dots,\mathbf{x}(T))\notin E$, we
have the following behavior: if $\mathbf{b}_{t}\neq\mathbf{0}$, then

$\displaystyle\lim_{\alpha\to+\infty}\sigma(\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t)))$
$\displaystyle=\lim_{\alpha\to+\infty}\sigma(\alpha\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t)))$
$\displaystyle=\left\\{\begin{array}[]{ll}1&\text{if}\
\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t))>0,\\\ 0&\text{if}\
\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t))\leq 0,\end{array}\right.$
$\displaystyle=\mathbb{I}\\{\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t))>0\\}.$

Otherwise, if $\mathbf{b}_{t}=\mathbf{0}$, then

$\displaystyle\lim_{\alpha\to+\infty}\sigma(\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t)))$
$\displaystyle=\lim_{\alpha\to+\infty}\sigma(-\alpha\mathbf{e}_{1}\bullet\Phi(\mathbf{x}(t)))$
$\displaystyle=\lim_{\alpha\to+\infty}\sigma(-\alpha)$ $\displaystyle=0$
$\displaystyle=\mathbb{I}\\{\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t))>0\\}.$

Therefore, for any $(\mathbf{x}(1),\dots,\mathbf{x}(T))\notin E$, we have

$\displaystyle\lim_{\alpha\to+\infty}\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}(1-\sigma(\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t^{\prime}))))\cdot\sigma(\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t)))$
$\displaystyle=\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))\leq
0\\}\cdot\mathbb{I}\\{\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t))>0\\}.$

In addition, for all $(\mathbf{x}(1),\dots,\mathbf{x}(T))$, the term in the
limit obeys the bound

$\displaystyle\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}(1-\sigma(\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t^{\prime}))))\cdot\sigma(\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t)))$
$\displaystyle\leq\sum_{t=1}^{T}g(t,\mathbf{x}(t))$ $\displaystyle\leq
T\cdot\bar{G},$

where the first inequality holds because $0\leq\sigma(u)\leq 1$ for any real
$u$, and the second holds by Assumption 3.1.

Therefore, by applying the bounded convergence theorem, we can assert that

$\displaystyle\lim_{\alpha\to+\infty}J_{R}(\tilde{\mathbf{b}})$
$\displaystyle=\lim_{\alpha\to+\infty}\mathbb{E}\left[\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}(1-\sigma(\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t^{\prime}))))\cdot\sigma(\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t)))\right]$
(34)
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\mathbf{b}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))\leq
0\\}\cdot\mathbb{I}\\{\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t))>0\\}\right]$
(35) $\displaystyle=J_{D}(\mathbf{b}).$

Note that in our application of the bounded convergence theorem, we are using
the fact that the functions of $(\mathbf{x}(1),\dots,\mathbf{x}(T))$ whose
expectation defines $J_{R}(\tilde{\mathbf{b}})$ in (34) converge pointwise to
the function of $(\mathbf{x}(1),\dots,\mathbf{x}(T))$ whose expectation
defines $J_{D}(\mathbf{b})$ in (35) almost everywhere with respect to the
probability measure of $(\mathbf{x}(1),\dots,\mathbf{x}(T))$. (The only set of
values of $(\mathbf{x}(1),\dots,\mathbf{x}(T))$ on which the pointwise
convergence does not hold is $E$, for which we have already established that
$\mathbb{P}(E)=0$.)

Thus, $\lim_{\alpha\to+\infty}J_{R}(\tilde{\mathbf{b}})=J_{D}(\mathbf{b})$.
Since
$J_{R}(\tilde{\mathbf{b}})\leq\sup_{\mathbf{b}^{\prime}\in\tilde{\mathcal{B}}}J_{R}(\mathbf{b}^{\prime})$
by the definition of the supremum, it then follows that for any $\alpha>0$,

$\displaystyle\lim_{\alpha\to+\infty}J_{R}(\tilde{\mathbf{b}})\leq\sup_{\mathbf{b}^{\prime}\in\tilde{\mathcal{B}}}J_{R}(\mathbf{b}^{\prime}),$

which implies that

$\displaystyle
J_{D}(\mathbf{b})\leq\sup_{\mathbf{b}^{\prime}\in\tilde{\mathcal{B}}}J_{R}(\mathbf{b}^{\prime}).$

Since $\mathbf{b}$ was arbitrary, we thus have that

$\displaystyle\sup_{\mathbf{b}\in\mathcal{B}}J_{D}(\mathbf{b})\leq\sup_{\mathbf{b}^{\prime}\in\tilde{\mathcal{B}}}J_{R}(\mathbf{b}^{\prime})$

as required.

_Step 2:
$\sup_{\mathbf{b}\in\mathcal{B}}J_{D}(\mathbf{b})\geq\sup_{\tilde{\mathbf{b}}\in\tilde{\mathcal{B}}}J_{R}(\tilde{\mathbf{b}})$_.
To show this, let $\tilde{\mathbf{b}}$ be any set of random policy weights in
$\tilde{\mathcal{B}}$. As in the proof of Theorem 3.1, let us define random
variables $\xi_{1},\dots,\xi_{T}$ that are i.i.d. standard logistic random
variables, that is, for each $t\in[T]$, we have:

$\mathbb{P}(\xi_{t}<s)=\sigma(s)$

for all $s\in\mathbb{R}$. Then observe that for a fixed trajectory
$\mathbf{x}(1),\dots,\mathbf{x}(T)$, we can write the reward of the randomized
policy with weights $\tilde{\mathbf{b}}$ as

$\displaystyle=\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}(1-\sigma(\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))))\cdot\sigma(\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t)))$
$\displaystyle=\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{P}(\xi_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime})))\cdot\mathbb{P}(\xi_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t)))$
$\displaystyle=\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{E}[\mathbb{I}\\{\xi_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))\\}]\cdot\mathbb{E}[\mathbb{I}\\{\xi_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t))\\}]$
$\displaystyle=\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\mathbb{E}_{\xi_{1},\dots,\xi_{T}}\left[\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\xi_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))\\}\cdot\mathbb{I}\\{\xi_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t))\\}\right]$
$\displaystyle=\mathbb{E}_{\xi_{1},\dots,\xi_{T}}\left[\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\xi_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))\\}\cdot\mathbb{I}\\{\xi_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t))\\}\right].$
(36)

We thus have that

$\displaystyle J_{R}(\tilde{\mathbf{b}})$
$\displaystyle=\mathbb{E}_{\mathbf{x}(1),\dots,\mathbf{x}(T)}\left[\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}(1-\sigma(\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))))\cdot\sigma(\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t)))\right]$
$\displaystyle=\mathbb{E}_{\mathbf{x}(1),\dots,\mathbf{x}(T)}\left[\mathbb{E}_{\xi_{1},\dots,\xi_{T}}\left[\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\xi_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))\\}\cdot\mathbb{I}\\{\xi_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t))\\}\right]\right]$
$\displaystyle=\mathbb{E}_{\xi_{1},\dots,\xi_{T}}\left[\mathbb{E}_{\mathbf{x}(1),\dots,\mathbf{x}(T)}\left[\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\xi_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))\\}\cdot\mathbb{I}\\{\xi_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t))\\}\right]\right]$

where the interchange of expectations in the last step follows by Fubini’s
theorem, since the random variable (36) is always nonnegative.

By the definition of expected value, there must exist a realization
$\xi^{\prime}_{1},\dots,\xi^{\prime}_{T}$ such that

$\displaystyle\mathbb{E}_{\xi_{1},\dots,\xi_{T}}\left[\mathbb{E}_{\mathbf{x}(1),\dots,\mathbf{x}(T)}\left[\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\xi_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))\\}\cdot\mathbb{I}\\{\xi_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t))\\}\right]\right]$
$\displaystyle\leq\mathbb{E}_{\mathbf{x}(1),\dots,\mathbf{x}(T)}\left[\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\xi^{\prime}_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))\\}\cdot\mathbb{I}\\{\xi^{\prime}_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t))\\}\right].$

Now, let us define a weight vector $\mathbf{b}$ for the deterministic probelm
as follows:

$b_{t,k}=\left\\{\begin{array}[]{ll}\tilde{b}_{t,k}&\text{if}\ k\neq 1,\\\
\tilde{b}_{t,1}-\xi^{\prime}_{t}&\text{if}\ k=1,\end{array}\right.$ (37)

where we recall that the index $k=1$ corresponds to the constant basis
function $\phi_{1}(\cdot)=1$. Observe that by the manner in which we have
defined $\mathbf{b}$, we have that

$\displaystyle\mathbb{I}\\{\xi_{t}\geq\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t))\\}$
$\displaystyle=\mathbb{I}\\{0\geq\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t))-\xi_{t}\\}$
$\displaystyle=\mathbb{I}\\{0\geq\mathbf{b}_{t}\bullet\Phi(\mathbf{x}(t))\\}.$

Thus, we have that

$\displaystyle J_{R}(\tilde{\mathbf{b}})$
$\displaystyle\leq\mathbb{E}_{\mathbf{x}(1),\dots,\mathbf{x}(T)}\left[\sum_{t=1}^{T}g(t,\mathbf{x}(t))\cdot\prod_{t^{\prime}=1}^{t-1}\mathbb{I}\\{\xi^{\prime}_{t^{\prime}}\geq\tilde{\mathbf{b}}_{t^{\prime}}\bullet\Phi(\mathbf{x}(t^{\prime}))\\}\cdot\mathbb{I}\\{\xi^{\prime}_{t}<\tilde{\mathbf{b}}_{t}\bullet\Phi(\mathbf{x}(t))\\}\right]$