Deep Recurrent Optimal Stopping
Authors: NIRANJAN DAMERA VENKATA
Chiranjib Bhattacharyya
Venue: NeurIPS 2023 poster (2023)
Keywords: optimal stopping
recurrent neural networks
probabilistic graphical models
policy gradient methods
TL;DR: We introduce an optimal stopping policy gradient algorithm (OSPG) that can leverage RNNs effectively in non-Markovian settings. OSPG works offline and eliminates expensive Monte Carlo policy rollouts.

Abstract: Deep neural networks (DNNs) have recently emerged as a powerful paradigm for solving Markovian optimal stopping problems. However, a ready extension of DNN-based methods to non-Markovian settings requires significant state and parameter space expansion, manifesting the curse of dimensionality. Further, efficient state-space transformations permitting Markovian approximations, such as those afforded by recurrent neural networks (RNNs), are either structurally infeasible or are confounded by the curse of non-Markovianity. Considering these issues, we introduce, for the first time, an optimal stopping policy gradient algorithm (OSPG) that can leverage RNNs effectively in non-Markovian settings by implicitly optimizing value functions without recursion, mitigating the curse of non-Markovianity. The OSPG algorithm is derived from an inference procedure on a novel Bayesian network representation of discrete-time non-Markovian optimal stopping trajectories and, as a consequence, yields an offline policy gradient algorithm that eliminates expensive Monte Carlo policy rollouts.

Deep Recurrent Optimal Stopping
Niranjan Damera Venkata
Chiranjib Bhattacharyya Dept. of CSA and RBCCPS Indian Institute of Science, Bangalore, India chiru@iisc acc..a.cin
Digital and Transformation Organization HP Inc., Chennai, India niranjan. damera. venkata@hp.co com
Abstract
Deep neural networks (DNNs) have recently emerged powerful paradigm for solving Markovian optimal stopping problems. However, ready extension of DNN-based methods to non-Markovian settings requires significant state and parameter space expansion, manifesting the curse of dimensionality. Further, ef- ficient state-space transformations permitting Markovian approximations, such as those afforded by recurrent neural networks (RNNs), are either structurally infeasible
confounded by the curse of non- Mor-aaavovia Considering these issues, we introduce, for the first time, an optimal stopping policy gradient algo- rithm (OSPG) that can leverage RNNs effectively in non-Markovian settings by implicitly optimizing value functions without recursion, mitigating the curse non-Markovianity. The OSPG algorithm is derived from inference procedure on a novel Bayesian network representation of discrete-ting non-Markovian opti- mal stopping trajectories and, consequence, yields offline policy gradient algorithm that eliminates expensive Monte Carlo policy rollouts.
Introduction
In the classic optimal stopping setting, agent monitors the trajectory of stochastic process, with the opportunity to either continue observing or stop and claim a reward (or suffer a cost), which is generally function of process history. Once the agent decides stop, further actions possible, and no further reward can be claimed (or cost suffered). The agent's 's goal is to produce stopping decisions based the process observations to maximize the expected reward (or minimize the expected cost). For example, whether to exercise a stock option or not at any time is an optimal stopping problem where the goal maximize expected exercise value, as is the decision of when to replace a degrading machine. Optimal stopping methods have wide array of applications in finance [5] 22 operations research 17 24 10,, disorder/change -pinnt detection 36 32), early classification
of time-series 13 among others.
In this paper,
concerned with the discrete-time, finitehhoriznn model-free setting, where the process evolves over discrete time-steps, and decision to stop must occur by given finite horizon. Further, the dynamics of process evolution
unknown. This setting is in contrast with classic approaches [8] (28] (35 14 (36] which assume that the dynamics of process evolution are known and characterized with simplified and usually Markovian stochastic models. Note that continuous- time optimal stopping problems, including the pricing of American options, may often be reduced the discrete-time setting by suitable discretization (18] Solving optimal stopping problems in non-Markovian settings is challenging due to the following curses:
The curse of dimensionality 3 extending state space with process history. However, such an extension significantly increases the problem's dimensionality, complicating function approximation. Estimating high-dimensional value functions directly rules out conventional approaches that approximate value functions with linear combination of basis functions 44 23
A non-Markovian process may be made Markovian by
39
40 43
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

The curse of non-Markovianity 44 6]: One may mitigate the curse of dimensionality by ap- proximating a Mon-Maakovinn process by Markovian process with a transformed state-space. For example, RNNs can learn to summarize relevant process history into Markovian hidden-state pro- cess efficiently. However, state-of-the-art Markovian optimal stopping methods [99 20 2 16 rely
on the recursive computation of value functions (see Section 2 which propagates approximation bias in non Man-ovaavvinn settings, a phenomenon known as the curse of -on-Markovianity (6]
Existing deep neural network approaches: Deep neural network approaches to optimal stopping 19 20 2 T6 have emerged as a powerful way of handling high-dimensional Markovian optimal
stopping problems. Existing model-free methods compute value function approximations relying on a recursive temporal relationship between value functions at successive time-steps in Markovian settings embodied by the Wald-Bellman equation [6]] or closely related equivalent (see Section
Backward Induction methods [9 20 16 start from the last time-step and recurse backward sequentially through time. Non-Markovian settings force Backward Induction methods to augment their state space with process history 2 significantly exacerbating the curse of dimensionality since elegant approaches such as RNNS, which share parameters across time-steps are not an option for backward induction methods. If the value function of time-step j 1 is already optimized, it cannot change when we fit the value function at time-step j. Further, the inability to share parameters across time-steps means parameter space grows linearly with the time-steps processed, thereby reducing sample efficiency. A notable exception is the method of Herrera et al. [16], which uses an RNN. However. the RNN weights are random and not learnable to permit backward induction to proceed. Only the final hidden-layer weights are fit, and these are not shareable across time-steps.
Fitted Q-Iteration (FQI) methods [3 16 start with bootstrapped value functions at all time-steps and recursively update these for temporal consistency with the Wald-Bellman equation. While they can use RNN-based function approximators, they suffer from the curse of non-Markovianity.
We note that a body of work uses deep neural networks to solve continuous-time optimal stopping problems by formulating them as free-boundary Partial Differential Equations (PDE). These include methods such as the deep Galerkin method (37] and the backward stochastic differential equation method 77]. We consider such methods model-based since they start with specific PDE to be solved that assumes prior knowledge of process evolution.
The above context points to (1) using suitable characterization of state space (as afforded by RNNs) to mitigate the curse of dimensionality and (2) direct policy estimation methods such as policy gradients to mitigate the curse of non- non-Markovianity. Our approach brings together, for the first time, probabilistic graphical models, policy gradient methods [42), and RNNs to design effective stopping policies for non-Markovian settings. policy gradient methods are notably missing from the optimal stopping literature. We make the following contributions:
Outline of contributions:
We present reward augmented trajectory model (RATM) (see Section 3). novel Bayes net parameterization of Mon-Maakovinn state-action-rewarr trajectories encountered in optimal stop- ping. where conditional probability distributions (CPDs) encode stochastic policy actions and reward possibilities (Section 3). In particular, this formulation allows the stochastic policy to share parameters across time-steps, allowing ANNN-ased CPD approximations, which mitigate the curse of dimensionality issues discussed earlier. Also, the problem of finding an optimal stopping policy reduces to a direct policy optimization procedure based on the E-M algorithm (Theorem 3.1 and Corollary 3.1.I) that leverages inference over the Bayes net. This mitigates the curse of non-Markovianityy associated with recursive value function estimation. Further, modeling optimal stopping with graphical models opens new avenues. As noted by Levine (22), in the context of reinforcement learning. "The extensibility and compositionality of graphical models can likely be leveraged to produce more sophisticated reinforcement learning methods, and the framework of probabilistic inference can offer a powerful toolkit for deriving effective and convergent learn- ing algorithms for the corresponding models"; for instance, augmentation with additional latent variables may be explored to model process disorders such as change-points
Inference on the RATM yields policy gradient algorithm when we take an incremental view of the E-M algorithm (see Section 4 Theorem 4.1 and Proposition D. We call this algorithm the optimal stopping policy gradient (OSPG) method, the first policy gradient algorithm, to the best of our knowledge, for computing optimal stopping policies suitable for Mor-Markovian settings. A key benefit of OSPG is that unlike classic policy gradients [42). it is offline algorithm and does

---

not require Monte-Care Carlo policy rollouts, Crucially, we show (Corollary 4.1.1) that our procedure is learning a policy that implicitly optimizes value functions at every time-step without requiring recursive value function computation, thereby mitigating the curse of non-Markovianity.
We introduce new loss function based OSPG that is well-suited for learning RNN-based stopping policies with mini-batch stochastic gradient descent (A (Algorithm[]] T This makes OSPG (unlike E-M) practical for large datasets while leveraging powerful off ffffthe-shelf optimizers such as Adam. The OSPG loss considers an entire process trajectory and does not decompose across time- steps, allowing policy decisions across trajectory to be evaluated jointly rather than independently,
2 Discrete-time finite-horizon optimal stopping
We represent the stochastic process monitored by d-dimensional random fully observable environment state variables }. Process history until and including time-step is represented by the d x random matrix Sj := [So S1, S...... Sy].
S.]. Associated with state history is a reward process {Ry} with R = (S,), where 9N : Rdx; + IR+ is a reward function that maps observation history to a reward for stopping at time-step j. Uppercase letters denote random variables, while lowercase letters represent their realizations. Bold font is used to indicate histories. Thus Sy is an observed partial trajectory from Sy. Also, in case we need to refer to specific trajectory, we use extra index i, so for example, raj refers to the observed reward for stopping at time-step j when monitoring the 2th process trajectory.
Definition 2.1 (stopping policy). A stopping policy is defined as a sequence of fuunctions &0 (f9), 1P2,- ............................... ..j....), where (P : _dxj + {0, 1} maps the history of observations time-step j to a decision of whether to stop (py )- = 1) or not (s)(s,) = =).
Definition 2.2 (stochastic stopping policy). A stochastic stopping policy is defined as a sequence of functions = (01,02,:1 ..2....... ..... (,...)), where Φ5 Rddx + [o, 1] maps the history of observations at a time-step j to probability of stopping at time j.
Note that a stochastic policy may be converted to deterministic stopping policy make stopping decisions by augmenting the state space with i.i.d. virtual observations from a random variable U uniformly distributed in [0, 1] Thus, the equivalent deterministic policy is (s,) [())(s;) u,).
This paper considers the finite horizon setting where j H E N, so decision to stop must be made at or before finite horizon H. Thus we define 4 (Sn) := The decision to stop is based on stochastic process, making the stopping time a random variable.
Definition 2.3 (policy stopping time 3I),. Stopping occurs when the policy first triggers a stop action. This occurs at random time r m0 < j S H (S,) = 1}, called the stopping time")
With this background, can formally define the optimal stopping problem:
Definition 2.4 (optimal stopping problem [36). Solve for the optimal stopping time 7" (if one exists) for which E R = sup- E [R+] where R (S,) ) is a reward process, is stopping time random variable, and {S,} is stochastic process.
Following Shiryaev and Peskir [3 28,, in the finite-horizon, discrete-time setting, the existence of finite optimal stopping-time time is guaranteed when E [sup,<H |R The optimal stopping time can then be determined by the method of backward induction which recursively constructs the Snell-emvelope comprising random variables {U,} given by:
Un RH U, max (Ry, E (S - H 1.... j=
(Snell-envelope)
The optimal stopping time is given by 7* = min < j S H U, R,). From a practical perspective, the expectations in the recursion are hard to estimate since they depend on process history, manifesting the curse of dimensionality. The assumption of Markovian state evolution, i.e. P(S)+1[S,) = 1S5)) and reward process expressable as function G, of the current state,
'This is equivalent (see 115 to the classic definition (36 of a stopping time w.r.t filtration (Fr) ) RV such that {r j} E Fj Since (F,) is the minimal filtration generated by {S,) ) our setting, we can determine if 7 = j or not hy considering sy. We use lowercase to represent 7 for consistency with literature. "The Snell-envelope also the smallest super-martingale that dominatessenvelopes the reward process [36).
3

---

Zr
Ao
A1
Ar
Ro
Ao
R1
A
R
A
Rh
So
S
S
SH
So
S
S
Sh
state-action trajectory model
reward augmented Bayesian network model
Figure 1: Bayesian networks representing (a) state-history (S,) and action (A,) trajectories and (b) corresponding reward augmented trajectory model for optimal stopping.
i.c R2 G,())), directly leads to the much more tractable Wald-Bellman equation
28 35
36
Tr(s)==Grl( (+)+) = max (1)+)))))))) j < H (Wald-Bellmal equation)
The value functions (*) give the maximum expected reward obtainable from time having observed state s. Thus (s) = sup,>, E. [R,] Vj. The operator T₃ is defined by Fs)(s) == Ey,s (F())+1)) for any function of the state. The Snell-envelope reduces to U, = Vj(S,) in this case. We define (s)s)= := Tj ()) can obtain by choosing to continue at step j having observed state s. The optimal stopping policy is given by:
the continuation value-function, which is the maximum expected reward one
(S,) == 1, (S,) (S)( 2 K,(S)), j = 0,
(1)
The value functions are, therefore, related the optimal policy follows:
= (S))),,)) + -1-
(5))))
(2)
Thus, if we estimate the continuation value functions Kj. decisions using equation [ Note that this requires knowledge of reward function Gj at inference
trigger optimal stopping
time. Backward induction approaches typically, first estimate K - to approximate K K#-1(Sp (S++111
(SH) and then use either the Wald-Bellman equation 440 19 or equations (I) and 2 23 20
to produce approximation targets ( which are used targets to H (S
VH-1(SH-22 and the process continues backwards recursively. As a variation on this theme,
Becker et [2] first set (
G (SH) and then estimate yp} (s) in equation (2) by
maximizing the RHS of equation (2) with j H - 1 and 9 replacing ( HH-1' Then equation is used to compute VH V which is in turn used to set K (S
V V and the 40 4 use bootstrapped continuation
process proceeds recursively. Fitted Q-iteration methods 39
value functions K2 to produce (S,) at all time-steps using the Wald- Beld-Bellman equation. Then, updated continuation value-function K, are fit simultaneously across all time-steps to approximate (S+1(S)+1), and the process continues recursively until convergence. If Markovian assumptions do not hold, states S, need be replaced with S, exploding the state space and significantly complicating function approximation (the curse of dimensionality). The recursive procedures discussed above propagate bias across time-steps when using Markovian approximations, since bias in value estimation at one time-step infects the preceding time-step (the curse of non-Markovianity).
3 A Bayesian network view of optimal stopping
This section presents a new Bayesian network view of optimal stopping. While we draw inspiration from corresponding view of general reinforcement learning (RL) [22], the resulting modeling choices needed to capture the structure of optimal stopping make the approaches distinct.
State-action trajectory model: Figure a[a shows Bayes net model of state-action trajectories in optimal stopping. An action Ay at any time-step depends on the state history S, up to that time-step. permitting general Mar-Miaoni stopping policies. Further, actions are restricted to 0 (continue) or 1 (stop), with the stop action terminating the action trajectory. Therefore, a key feature of optimal stopping problems is that, unlike general reinforcement learning, actions do not impact the probability distribution the following states over the control horizon, conditioned on state history. We do not model the stopping time explicitly. Instead, it is consequence of stochastic policy actions over

---

the horizon. The action trajectory stops at a random stopping time = 1. Therefore, we have the special structure A, 1 and A, 0. vj т. Note that Figure a) represents family of stopping trajectories A,, each member stopping at a specific value of т. We denote a specific stopping trajectory by A,. Consider stochastic policies, given by the functions (S,))) == P(A, = [.)) We define (),(s)) == Pr(r = j|5,) to represent the stopping-ting distribution. We have the following key relationship between action trajectories and the stopping -ime random variable encapsulated in the following lemma, adapted from [J4], proved in Appendix A. Lemma 3.1 (trajectory reparameterization lemma).
@u (Sa)
i
(S,)) II (1 (S,)),
if0 <
P(T = j|Sn) (S,) (S,))
n=0
H-1
II ( (. n=
ijj
Reward augmented trajectory model: Figure shows an augmentation of the basic state action trajectory model to bring the notion of stopping rewards into the model. The variables R, represent the reward process, which are functions of state history: recall R gj (S (S,). We introduce Z, as family of binary random variables representing if reward is obtained (7,- 1) not (Z, 0) when we stop at various values of T. Thus stopping at j no longer guarantees reward Rg. The idea is to random variables Z, to transform absolute rewards which are not readily interpreted as probabilities into probabilities (in this case, probabilities of obtaining reward at any time-step) that may be represented in the Bayes net. We parameterize the conditional probability distribution of Z, with Bernoulli distributions defined as follows:
P(Z = 1| A,) = R == F(T, RH) P(Z, = A,)
(3)
where F: (0, 1, H) ( [0, 1] is function that transforms real-valued stopping rewards into probabilities that encode the notion of the relative possibility of obtaining rewards over a trajectory by stopping at particular time-step of the trajectory. We may write the joint distribution of a trajectory stopping at time T as:
H P(A,, L,, SH) = P(R.) II ((S))))-))()
II PAA. P(Z)),, RH) n=0
P(S.) P(RW)S)
P(A, (S,)
A., RH)
(4)
We have used the reparameterization lemma 3.J to replace the probability distribution over actions with the corresponding induced probability distribution over stopping times. Conditioning on R and Sy we have:
(5) Optimal policy estimation: We are particularly interested in the conditional probability of getting
(A Z, RR. SH) P(r[S PP R,))
reward when we stop. We can obtain this by using Bayes net inference to obtain equation (5) and then marginalizing over the family of stopping trajectories A, Since there is one-to-one correspondence between A, and stopping time т, we just need to sum over all possible stopping times. Thus, if we ZH. where @ is the XOR operator we have, from equation (
define Z := Zo + Z1 ①
H
P(Z 1 RH. SH) P(r== (Sr=j(Sa)P222 P(Z = 1 RH) RH)
Σ 3 (S,)
(6)
Ideally, we would want policy to maximize this conditional probability. To this end, con- sider parameterized policy functions of and induced stopping time distributions vi and define the conditional likelihood function over sample trajectory
((0 SH. rH) IP(Z 1|sH 0)
Σ v (s)
We use the XOR operator since exactly one of the { } can be equal to one. The reward for a trajectory only be claimed by stop action single time-step.
5

---

However, maximizing this likelihood over samples while allowing optimal stopping decisions on any trajectory ignores the relative magnitude of rewards between different trajectories. Thus, we seek to weight the likelihood of each trajectory. Therefore, considering a dataset 'D of environment trajectories and using index for the 7th trajectory in the sample, we have:
N II 1(0 S. Fi,H) with Σ -
wmi (0)
where Wi is the relative weight for the tth sample, Taking logarithms, we have the following objective to maximize:
H
JWML (0)
W log w9 (s.))
j=0
We may use the following Expectation-Maxiine Maximization (E-M) procedure to maximize this objective: Theorem 3.1 (E-M procedure for optimal stopping policy). The following iterative procedure converges to a local maximum of (wMI(O) with monotonic increase in the objective with iteration
index (k), starting with an initial value 0 = (0)
(si) Mis
4ij
OSiSH, ISigN
(B-step)
Σ
H
(si))
j=
N
H
(k)
(0)
(k) (k) w lig
log 15 (8.g), 0(++1) arg max ((k] (0)
(M-step)
0
:=1
where W. W Vk. The proof follows from an application of Jensen's 's inequality and is given in Appendix A. Dayan and Hinton pioneered using E-M methods for RL policy search [12].
Specification of (7g) and w: řig specification of the relative intra-trajectory probability of obtaining a reward when stopping time-step j of the 7th trajectory. natural choice (and one that we
Fi where Fay is a realization of R, = (,,s)) corresponding adopt in this paper) is to set Pi5 == Σ Tiy
the 7th trajectory. This formulation encourages stopping at time-steps of the trajectory, proportional exp(r.)
to achievable reward. Alternatively, formulations such as Fig := maxx or fij == Σt_ exp(ra)
could be used express different stopping preferences within a trajectory. The weights w, on the other hand, express relative inter-traeectory importance. One plausible choice would be to set Σ" Σn
w; r; Σو Ey the relative reward available for extraction from trajectory. Similarly,
max; Pej one could weight trajectories by the maximum reward achievable: w; F. Σ, max, Tej" We may also consider reweighting schemes that vary weights over rounds of the E-M algorithm. In the RL literature, neward--wighhted regression [30] takes such approach.
weighted regression typically conducts rollouts of the current policy and weights each resulting sample trajectory with the relative reward achieved by the current policy on that trajectory. However, the trajectory reward is unknown since we do not perform policy rollouts. Instead, we weight each trajectory offline by its relative expected reward under the current policy. Specifically, we compute weights at each round according to a W-step:
DH 15
(stg)r
W
ISiSN
(W-step)
E v0rr (sig)ris
This weighting is not arbitrary as it leads to a surprising equivalence with policy gradient method, established in the next section. Further, we have the following Corollary (proof in Appendix A):
Using the reweighting scheme of the W-step in the E-M procedure of Theorem 3.1 Machivves a local maximum of:
Corollary 3.1.1 (Reweighted E-M). Leri, EN
Ei Tis
N
H (o
N
JwMI W. 0) = Σ
wi log Σ j=0
-
Wc log
(10)
Fz
with monotonic increase in the objective, starting with an initial value o = 000) The second term is the KL-divergence between distributions w and F.

---

4 Optimal stopping policy gradients (OSPG)
In this section we show that an incremental version of the E-M algorithm described in the previous section, with a single gradient step replacing a full M-step, is equivalent to a policy gradient method that maximizes expected reward. We call this the optimal stopping policy gradient (OSPG) method.
Consider a direct maximization of the optimal stopping objective Jos = E[R,]] from definition 2.4 where the expectation is over state-action trajectories. We state-action trajectories without reward augmentation shown in Figure Ia to obtain:
our Bayes net model of
H P((S,, A- = (S.) II P(S)(S)-1)
II F(An 0) (P( 0)
(11)
where we have used the trajectory reparameterizatioon lemma reparameterize in terms of stopping times. Therefore, we may write:
Jos (0) PPar) [Er-B(Tss.00
[R.]]] Eng
Σ 3 s))r,
(12)
We leverage methods used to establish the policy gradient theorem 42
38 to derive a convenient
form for the gradient of the optimal stopping objective w.r.t policy parameters O.
Theorem 4.1 (Optimal stopping policy gradient theorem). For any differentiable stopping policy & The gradient of the objective Jos(O) E[Rr] w.r.l. policy parameters O, where {R₃} is a risk process and is a stopping time random variable, is given by:
Jos ((s
Σ rr
Vo log v (s;)
Vo
where the v9(ss) (s)) are functions of eb obtained by Lemma
3.1
The proof an application of the log-derivation trick 42 and is given in Appendix Note that optimal stopping policy gradients are estimated using offline state trajectories only. Unlike the general RL case, we never need to do policy rollouts to sample trajectories. Instead, we explicitly calculate the probability distribution over all possible stopping actions (or stopping times) and use this to average over all possible stop-continue decisions. Also, an update to the policy parameters can be done without fresh data collection since the impact of the updated policy on the loss using the already sampled environment trajectories. Appendix B describes specialization settings with costs instead of rewards.
correctly (due to explicit Bayes net modeling) model
We now establish a surprising equivalence between the reweighted E-M algorithm of Corollary [3I.J] and the policy gradient method derived in this section when an incremental E-M solution approach 27 is used. Although the objective functions JWML (w, 0) and Jos(O) are different general, the same procedure maximizes both.
Proposition 4.1 (Incremental E-M as a policy gradient method). If a partial M-step is used in the reweighted E-M approach of Corollary I.I.I comprising of a single gradient- step, then the resulting incremental E-M procedure is equivalent the optimal stopping policy gradient method of Theorem each converging to a local maximum of both Jw MT.(W.. (w, 0) and (os
4.1
The proof is given in Appendix A. Thus, we may view the incremental E-M approach that optimizes a weighted maximum likelihood objective as a generalization of the policy gradient method that seeks to optimize the expected reward objective. The two are equivalent for particular weighting scheme and Bayes net specification (as in Corollary [.I.T.. Further, the OSPG gradient has the following insightful form, obtained by applying Lemma 3.1 to the M-step objective of Theorem
3.1
Corollary 4.1.1 (Value form of the OSPG gradient). Let Vij := v99 (Sis) kis == En j+1 Vin
En
We may rewrite the policy gradient of Theorem 4.7 as:
1 VeJos(
H
Uay (s1r)) (
Vod)(ss)
(13)
N
() 09 (S1;))
7

---

The proof is given in Appendix A. Jij is an empirical estimate of immediate reward, while kyy is an empirical estimate of continuation value under the current policy. The term the bracket is the the derivative of the objective w.r.t. the policy output, evaluated at Sij. This is positive, and hence calls for
og (RE)
kiy I- (m.,)) i.e. when the ratio of immediate continuation value exceeds the current odds of stopping. Of course, the policy is updated considering expected immediate reward and continuation values at all time-steps. The updated policy produces new estimates of immediate reward and continuation value from which new OSPG gradient is computed, and process proceeds until convergence to an optimal policy. Thus, this process implicitly uses value functions at all time-steps to update the policy which implicitly further improves value functions. Since there is no recursion across time-steps OSPG is able to mitigate the curse of non- Non-Markovianity.
increasing stopping probability, if 212
Temporal loss functions for learning RNN stopping policies: We may directly adopt the M-step objective of Theorem 3.1 as a loss function for learning an RNN-based policy with mini-batch stochastic gradient-descent (SGD), effective in nan-Markovian settings. Algorithm [ shows the pseudocode for computing our OSPG loss. This loss is idcally suited for learning stopping policies with RNNs since it takes input stopping probabilities at every time-step of (s:,) that are each function of process observation up to that point. An RNN performs this mapping naturally since maps input history to hidden state each time-step with recurrent computation. So, for example, return_ sequences=True, coupled with a TimeDistributed Dense layer in Keras, returns a complete trajectory of RNN predictions for input into the loss. Note also that this is temporal loss that considers the entire process trajectory and does not decompose across time-steps.
Algorithm Pseudocode for mini-batch computation of our temporal OSPG loss
Input: R : [ru]. &- = [o9 (s:))] } (1 < i S No, 0 j s H, No is batch size}
V.. = 0. WH = exp (2)10 log(1 k.))) (numerically stable computation of w (siz)
1 = exp (log(1 - U + log -1) (U unit upper triangular, CUMSUM)
V == stop-gradient R a) v) (held constant, so no gradient. @ denotes Schur product)
Output: J= = 1 [ @ log V
5
Experiments
We compare our OSPG algorithm using deep neural networks (DNN-OSPG) and recurrent neural networks (RNN-OSPG) against the following model-free discrete-time optimal stopping approaches.
Backward Induction: Deep Optimal Stopping (DOS) 2 including an extension of state space with process history (DOS-ES) 2 and Randomized Recurrent Least Square Monte Carlo (RRLSM) (16].
While fitted Q-Iteration (FQI) approaches in the optimal stopping literature rely on linear approximation with chosen basis functions [39 40) break down in high-dimensional settings, they may be readily extended to leverage deep neural network (DNN-FQI) and recurrent neural network (RNN-FQI) function approximators. Appendix C' provides details of our corresponding DNN-FQI and RNN-FQI baselines.
Fitted Q-iteration:
We conduct experiments with both Markovian and non-Main Markovian datasets. Markovian data include the pricing of sige-diiennional Bermudan max-call options and American geometric-call options (relegated to Appendix D due to space). Non-Markovian data includes stopping a fractional Brownian motion and the early stopping of a sequential multi-class classifier. Except for the American option pricing experiment, all DNN function approximators use two hidden layers of 20 hidden units each, while all RNN function approximators leverage RNN/GRU with single hidden layer of 20 units. Backward induction methods (DOS, RRLSM) require independent networks at each time-step, while other approaches share network parameters across time-steps. Details of hyper-paramede settings, model size, and compute times are provided in Appendix D.
Exercise of a Bermudan max-call option: In this Markovian setting, we seek optimal strategies to maximize the returns of Bermudan max-call option, a scenario described 22). Bermudan options may be exercised only at fixed times, unlike American options which may be exercised at any time prior to option expiration. The payoff of these options depends on the maximum of underlying dynamics and the strike price K. The dynamics and
assets with multi--immensioal
8

---

Table 1: Bermudan max-call option pricing: Results
average return (standard deviation)
d
Po
DOS
DNN-FQI
DNN-OSPG
RNN-FQI
RNN-OSPG
RRLSM
20
90
37.08
(0.09)
36.98 (0.29)
37.20 (0.08)
36,98 (0.32)
37.21 (0.07)
35.99 (0.05)
20
100
50.86 (0.08)
50.92 (0.05)
51.02 (0.08)
50.76 (0.22)
50.99 (0.09)
49.68 (0.06)
20
110
64.73 (0.11)
64.75 (0.22)
64.91 (0.10)
64.67 (0.17)
64.84 (0.10)
63.42 (0.06)
50
53.30 (0.08)
53.38 (0.12)
53.46 (0.08)
53.43 (0.12)
53.36 (0.11)
$1.87 (0.09)
50
100
68.87 (0.12)
68.91 (0.17)
(0.11)
68.98 (0.11)
68.93 (0.07)
67.37 (0.09)
50
110
84.50 (0.13)
84.45 (0.28)
84.65 (0.11)
84.62 (0.19)
84.52 (0.16)
82.85 (0.
100
65.83 (0.10)
65.94 (0.13)
(0.14)
65.78 (0.15)
65.80 (0.16)
64.56 (0.08)
100
100
82.79 (0.16)
(0.17)
(0.13)
(2.8200.14)
(0.17)
81.41 (0.08)
100
110
99.73 (0.16)
99.86 (0.12)
99,93 (0.18)
09.74
(0.14)
98.28 (0.11)
200
78.23
(0.15)
78.40.0..16)
78.43 (0.12)
(0.11)
78.20
77.28 (0.07)
200
100
96.57 (0.16)
96.68 (0.13)
96.79 (0.08)
96.21 (0.28)
(0.13)
95.53 (0.08)
200
110
114.87 (0.10)
115.03 (0.25)
115.10 (0.07)
114.55 (0.27)
11..74
113.78 (0.08)
payoff (reward) are given by:
+
STn = =i exp((r 5m / oW,,, Rs = ex
ST - ISmsd
max
(14)
for m = 1.2, r the risk-free rate, x0 E (0, 20) represents the initial price, 6m E 00 oo) is the dividend yield, om E (0, oc) the volatility and W is a d-dimensional Brownian motion, with zero instantaneous correlation between its d components. The reward for exercise at time t given by R₁ We discretize into H + possible exercise opportunities, using times tj- jj/H H for is the option expiration duration in years. This procedure translates the problem into our discrete-time finite horizon optimal stopping setting: suPosrsR E[R,).
j = 0, 1,.. H.
Mirroring Becker et. al. 12 we set, K 100, r 0.05, on 0.2, 6m 3.
We generate a dataset of 40,000 sample trajectories of the underlying assets, generating different datasets for various values of d and so s Ym. We train models on ten random 50% train-test splits, holding 20% of training data as validation dataset. Means and standard deviations of the achieved exercise values by the various methods are reported in Table T DNN- -SPG consistently performs best, while the other Markovian DNN methods, DOS and DNN-FQU perform well in this setting. Among the Mon-Maakovi RNN-based methods, RLLSM fares the worst due to increased noise from prior time-steps. RNN-OSPG and RNN-FQI are still relatively competent since they can learn to ignore information from prior time-steps.
Stopping non-Markovian fractional Brownian motion: We mimic the scenario considered in (2). A fractional Brownian motion (25), (Wz)) is a centered-Gauusiia process with co-variance structure determined by its Hurst parameter E (0, 1] as E W[
0.5( -1 s/--, The increments of 4h are positively correlated for h E (0.5, 1] and negatively correlated for h E (0. 0.5) and uncorrelated (reducing to a standard Brownian motion) for h = 0.5. We discretize t in the range [0, 1] into time-steps by 1- j/H for j = 0, 1, 1.... H, and seek to solve the optimal stopping problem: suPoşr<H B.W.)). Thus, the reward function is the identity mapping in this case. For each distinct setting of the Hurst parameter h, we generate 40,000 trajectories and train models on ten random 50% train-test splits, holding 20% of training data validation dataset.
Figure Plots average returns achieved by competing methods for various values of h. RNN-OSPG dominates competing methods in this Mar-aaaov setting across all values of h. Also, note the strong outperformance of DNN-OSPG that fits an optimal policy directly vs other Markovian methods (DOS and DNI-FQI) that propagate approximation eтrors due to recursive estimation of value functions. DOS-ES seeks to adapt to Markovinn settings by extending its state space with process history. This extension, in turn, explodes the parameter space and training times (see Appendix D, Table 6 while reducing sample efficiency. RRLSM solves this issue by using an RNN but, in turn, trades model flexibility (since the RNN layer is not- nrt-trainable). The performance of DOS-ES and RRLSM is quite close in this scenario. Note that even though an RNN is used, the performance of RNN-FQI is significantly worse than RNN-OSPG for positive values of h.
Early-stopping a sequential multi-class classifier: This a non-Markovian setting where we are interested in carly stopping sequential multi-class time-series classifier. The longer one delays

---

DO5 DRRATO
DREN OSPL
mwah reguard at starging
1.0
DOS 65
AALSH
RAR-FQI ANN-OGRG
84-
0.2
02
0.4
0.6
0.8
paramotor
Figure 2: Fractional Brownian motion
Figure 3: Stopping a multi-class classifier
classification, the easier the task becomes since every new time-step reveals information about the class of the series. When deciding on the class of given series, there tradeoff between the number of observations made and classification accuracy. Early stopping of a classifier is an optimal stopping problem with costs (instead of rewards): inf, E[C,] using a cost process {C₃}
with C = [1 max; P(Y = [)) + a Here, represents the actual class of the time series, with S, representing the process history of the time series until time j. The first term represents the probability of a classification error at time j while the second term imposes a cost of delaying the classification decision, controlled by R+. In practice, the true probabilities P(YY k)S,) unknown and must be approximated by training a classifier to get a cost model. This approach is related but not equivalent to early classification literature [26 13 9 26 I where the goal is to learn both classifier and stopping decision jointly. Since our intent in this paper is to solve the optimal stopping problem, not optimize the cost/reward models, we train simple baseline RNN classifier that learns parameterized approximations P(Y = k A.S () z IP(Y = k k|S, Vdj. k with parameters Ç. limitation of this approach is that we are constrained by the quality of the trained classifier. Our classifier is an RNN with a single 20-unit hidden layer connected to a final time-distributed dense layer with softmax activation which produces probability distribution over classes at each time-step. We train this model to minimize negative likliiilloood (NLL) to produce calibrated classifier.
There are two possibilities for the cost model. Either accept the probabilities estimated by the classifier the true probabilities yielding: Cj [1 max, IP(Y k S () + a az. use empirical classifissii error, yielding: CemP I(Y * arg max, IP = k|S,, ()) + a The latter is more robust choice and is the evaluation metric used since the stopping decisions will not be blind to classifier calibration errors. However, this setting exposes a significant limitation of funetifn methods (backward induction and FQI) since they require the cost model to be available at inference time. Thus, they can only use C and not Camp, since during inference, empirical errors of the classifier are not revealed until decision to stop has been made.
We select 17 multi-class time-series classification datasets from the UCR time-series repository | (see Appendix D for details of the datasets and selection process). We use 10-random 70% 70%/30% /30% (train/test) data splits to train all models, holding out a 30% of training data as a validation set. Figure (bb) reports the average stopping costs of the policies learned by the various methods on the test set. RNN-OSPG outperforms Packward-induction and FQI methods on 15 of the 17 datascts.
Conclusions
We introduce a policy gradient algorithm well suited learning RNN-based optimal stopping policies effective in non-Markovian settings. Our optimal stopping policy gradient (OSPG) algorithm leverages a new Bayesian net formulation of non-Markovian state-action-rewarr trajectories specific to optimal stopping. This formulation leads to an offline policy gradient algorithm where Bayes net inference eliminates inefficient Monte-Carlo policy rollouts. OSPG outperforms competing methods in non-Markovian settings where existing methods must either deal with the curse of dimensionality (from extended state spaces) or the curse of non- Mom-Mkroviaanty (from recursive Markovian approximation). A limitation of OSPG is that since it uses temporal loss defined over complete trajectories, may not be suitable for scenarios with only few extremely long trajectories or when trajectories are partially observed.
10

---

Acknowledgments
We acknowledge Jerry Liu, M. Anthony Lewis, Matt Ellis, Scott Hallworth, and Jennifer Hill at HP Inc. for supporting and sponsoring this work. Finally, we thank all the reviewers for their insightful comments that have helped improve the paper.
References
[1] Youssef Achenchabe, Alexis Bondu, Antoinc" Coruuéjoss, and Asma Dachraoui. Early clas- sification of time series. In Machine Learning, volume 110, pages 1481-1504. Springer International Publishing, 2021.
[2] Sebastian Becker, Patrick Cheridito, and Arnulf Jentzen. Deep optimal stopping. Mach. Learn. Res., 20.74:1-74:25, 2019.
[3] R. Bellman and Rand Corporation. Dynamic Programming. Rand Corporation Research Study.
Princeton University Press, 1959.
[4] D. Bertsekas and J.N. Tsitsiklis. Heuro-Dynamic Programming. Athena Scientific, 1996.
[5] Bruno Bouchard and Warin Xavier. Monte-Carlo Valuation of American Options: Facts and New Algorithms Improve Existing Methods. Numerical Methods in Finance, pages 215-255, 2012.
[6] Siddharth Chandak, Pratik Shah, Vivek S Borkar, and Parth Dodhia. Reinforcement learning in non non-markovian environments. CoRR, abs/2211.01555 2023.
[7] Yangang Chen and Justin W. L. Wan. Deep neural network framework based on backward stochastic differential equations for pricing and hedging american options in high dimensions. Quantitative Finance, 21(1):45-67, 2021.
[8] Y.S. Chow, H. Robbins, and D. Siegmund. Great expectations: the theory of optimal stopping. Houghton Mifflin, 1971.
[9] Asma Dachraoui, Alexis Bondu, and Antoine Cornuéjols. Early classification of time series as a non myopic sequential decision making problem. Machine Learning and Knowledge Discovery in Databases, pages 433-447. Springer International Publishing. 2015.
[10] Niranjan Damera Venkata and Chiranjib Bhattacharyya. When to intervene: Learning optimal intervention policies for critical events. Advances in Neural Information Processing Systems, volume 35, pages 30114-30126, 2022.
[11] Hoang Anh Dau, Eamonn Keogh, Kaveh Kamgar, Chin-Chia Michael Yeh, Yan Zhu, Shaghayegh Gharghabi, Chotirat Ann Ratanamahatana, Yanping, Bing Hu, Nurjahan Begum, Anthony Bagnall, Abdullah Mueen, Gustavo Batista, and HcXagon-ML. The UCR time series classification archive, October 2018. https: /tte:://wwwwcc cs. ucr weweeedeuuoeeeeeeee mamoon//timmssreene
data 2018/
[12] Peter Dayan and Geoffrey E. Hinton. Using mnxecaatoonmmaiimizaaiino for reinforcement learning. In Neural Computation, volume 9, page 271-278, 1997.
[13] Don Dennis, Chirag Pabbaraju, Harsha Vardhan Simhadri, and Prateek Jain. Multiple instance learning for efficient sequential data classification on resource-constrained devices. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada., pages
10976-10987, 2018.
[14] T.S. Ferguson. Mathematical Statistics: A Decision Theoretic Approach. Probability and mathematical statistics. Academic Press, 1967.
[15] Tom Fischer. Stopping times are hitting times: a natural representation. Statistics & Probability Letlers, 2011.
[16] Calypso Herrera, Florian Krach, Pierre Ruyssen, and Josef Teichmann. Optimal stopping via randomized neural networks. CoRR, abs/2104.1 13669, 2021.
[17] Daniel Jiang and Warren Powell. An approximate dynamic programming algorithm for mono- tone value functions. Operations Research, 63, 01 2014.

---

[18] P.E. Kloeden and E. Platen. Numerical Solution of Stochastic Differential Equations. Applica- tions of mathematics: stochastic modelling and applied probability. Springer, 1992.
[19] Michael Kohler, Adam Krzyžak, and N Zaklina Todorovic. Pricing of High-Dimensse American Options by Neural Networks. Wiley-Blackwe Mathematical Finance, 2010.
[20] Bernard Lapeyre and Jéróme Lelong, Neural Network Regression for Bermudan Option Pricing.
Monte Carlo Methods and Applications, 2021.
[21] Jason D. Lee, Max Simchowitz, Michael I. Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1246-1257, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR.
[22] Sergey Levine. Reinforcement learning and control as probabilistic inference: Tutorial and review. CoRR, abs/1 10118050000 800500909, 2018.
[23] Francis A. Longstaff' and Eduardo S. Schwartz. Valuing American Options by Simulation: A Simple Least-Squares Approach. Review of Financial Studies, 2001.
[24] V. Makis and Xiaoyue Jiang. Optimal replacement under partial observations. Math. Oper. Res., 28:382-394 394, 05 2003.
[25] Benoit B. Mandelbrot and John W. Van Ness. Fractional brownian motions, fractional noises and applications. SIAM Review, 10(4):422-437, 1968.
[26] C. Martinez, G. Perrin, E. Ramasso, and M. Rombaut. A deep reinforcement learning approach for early classification of time series. In 2018 26th European Signal Processing Conference (EUSIPCO), pages 2030-2034. 2018.
[27] Radford M. Neal and Geoffrey E. Hinton. A View of the EM Algorithm that Justifies Incremental, Sparse, and other Variants, pages 355-368. Springer Netherlands, Dordrecht, 1998.
[28] Goran Peskir and Albert Shiryaev. Optimal stopping and free-bouddyy problems. Lectures in Mathematics ETH Zürich. Springer, Dordrecht, 2006.
[29] Jan Peters and Stefan Schaal. Policy gradient methods for robotics. In 2006 IEEE/RS) International Conference on Intelligent Robots and Systems, 2006.
[30] Jan Peters and Stefan Schaal. Reinforcement learning by reward-weighted regression for operational space control. In Proceedings of the 24th International Conference Machine Learning, ICML '07, page 745-750, 2007.
[31] H.V. Poor. An Introduction to Signal Detection and Estimation. Springer Texts in Electrical Engineering. Springer New York, 2013.
[32] H.V. Poor and O. Hadjiliadis. Quickest Detection. Cambridge University Press, 2008
[33] W. B. Powell. Approximate Dynamic Programming: Solving the Curses of Dimensionality. Wiley Series in Probability and Statistics. Wiley, 2011.
[34] Martin Ricdmiller". Neural fitted Q iteration - first experiences with a data efficient neural reinforcement learning method. In Machine Learning: ECML 2005, pages 317-328. Springer Berlin Heidelberg, 2005.
[35] A. N. Shiryaev. Optimal Stopping Rules. Stochastic Modelling and Applied Probability, Springer Berlin Heidelberg. 2007.
[36] A.N. Shiryaev. Springer International Publishing. 2019.
Stochastic Disorder Problems. Probability theory and stochastic modelling.
[37] Justin Sirignano and Konstantinos Spiliopoulos. Dgm:
deep learning algorithm for solving partial differential equations. Journal of Computational Physics, 3739133911 2018.
[38] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, volume 12, 1999.
[39] John Tsitsiklis and Benjamin Van Roy. Optimal Stopping of Markov Processes: Hilbert Space Theory, Approximation Algorithms, and an Application to Pricing High--Dmensional Financial Derivatives. IEEE Transactions Automatic Control, 44: 14:1840-185,, 1997.
12

---

[40] John Tsitsiklis and Benjamin Van Roy. Regression Methods for Pricing Complex American-
Style Options. IEEE Transactions on Neural Networks, 12(4):694-703, 2001.
[41] Steven D. Whitehead and Long-Ji Lin. Reinforcement learning of non-markov decision pro- cesses, Artificial Intelligence, 73(1):2713306, 1995.
[42] Ronald J. Williams. Simple statistical gradient- algorithms for connectionist reinforce- ment learning. Machine Learning, (33-44)229222555 may 1992.
[43] Huizhen Yu and Dimitri P. Bertsekas. Q-Learning Algorithms for Optimal Stopping Based on Least Squares. European Control Conference, 2007.
13

---

Deep Recurrent Optimal Stopping: Supplementary Material
We provide an outline of the supplement that complements our paper.
Appendix A: provides proofs of all Theorems in the paper.
Appendix B: considers formulations of stopping problems specified in terms of costs instead of rewards and shows how to transform these into a consistent reward formulation.
Appendix C: provides discussion and pseudo-code to implement the temporal loss used to learn fitted Q-iteration policies DNN-FQI and RNN-FQI
Appendix D: includes further details and discussion of the experiments, including model hyper- parameter settings, numerical results with confidence intervals, details of compute environment, model sizes, train and inference times, etc. In Appendix E.3, we also include a new experiment that compares OSPG to state-of-the-ar PDE benchmarks the pricing of American options, which is continuous-time optimal stopping problem.
Appendix E: includes treatment of baseline subtraction in the context of optimal stopping policy gradients (OSPG).
A Appendix A: Proofs
A.1 Proof of Lemma 3.1
Proof. The Lemma follows from the Bayes net trajectory model of Figure 1a, and the special structure of OS action trajectories: A, = and An = 0, vn < т. For any OS state-action trajectory, we have:
H P(A,, Sn) = PSb))) II P(S,
II (.)) = P(S.) II ((A))))) ==U
(15)
j=1
==0
P(SH)
Therefore, conditioning on the state trajectory, we have P(A,|SH) II (AA)))s) Note that by the structure finite-horizon OS trajectories A, is sequence of continue actions terminated by a stop action at Thus there is a bijective mapping between stopping times and complete action trajectories given by:
H3 + [1, 01, .......0---... 00. R: 10,1,,2
(16)
H Os
So P(A, = ((N(T))SH)) = =.) Consider a trajectory stopping at 7 j and recall that our stochastic stopping policy is defined as (S,)) P(A, 1|S,).
Thus, if = 0:
P(r 0S.)) = P(A.)Sn) = P(A. 1|Sp) = (So)
(17)
If0 <j< H::
PP(r jjsm)
P(Ao = ..... A = 1(8
P(A, 1|S
II P(An. 0/Swr
n=0
J-1
,,(,) II - d (S.))
(18)
m=0
14

---

Finally, if H:
PP(T = H|)
= P(AA- = , = 0, Ah - 1|SH)
H H-1
= IP(AH = =1|HH)
II
P(AAp =0SH)
#=0
H-1
= dh (S#)
II (1
6n (S.))
7=0
H-1
(19)
==0
where we have used the fact that in the finite horizon setting dμ (S#) 1 by definition.
We may verify - P(r j|SH) 1 since:
H-1
H-1
j-1
Σ
P(r = j|8
1 1- (So)) - Σ
(S(S))
II o..))
1=
==
n=0
H-1
(1 (oo)
(S
Σ (S)
II
on (S.))
j=1
(1 do(S))) (Si)) x
H-1
1-1
1 - 22(S2)
Σ (S,)
II (1 - (1-6 (S
3=2
n=
H-1
o1 = P(( = H(H:)
==0
Further, since 7 a stopping time random variable we have:
P(r =||0)) P( == (S,
:=
(20)
This is because stopping time random variables have the property that 1I(T = j) is a function of Sj. So can determine if = j or by only considering S, making the event (T = j} conditionally
independent of Sj+k. vk > 0 given S, [35). This completes the proof.
A.2 Proof of Theorem 3.1
Proof. We apply Jensen's 's inequality to the objective JwwI.()) to obtain lower bound:
N
(S
JWML (0) Σ w. log Σ Ve
wigy log
(21)
yi
Starting with given (0) the lower bound is maximized (Jensen's inequality becomes equality) when
where Q Q- is any row-stochastic matrix satisfying @ú 2 0, Vi,j and
# Σj qij
Q Q()) = ( such that:
(0) 1//0000 (Si))
G5 Σj=a 2. (si))
(22)
This is the E-step in Theorem 3.1. Note that the E-step does not change the objective, so JwMI (0()) J (()))) 0). By ignoring terms that do not depend on 0, maximizing (() .0)
w.r.t. O can be seen equivalent to maximizing
(0) Σ
w.dy log 699 (s
(23)
15

---

This is the M-step. By the lower bound established in equation 21 and since the M-step maximizes [(Q(), 0) to obtain g(1), we have JwML (0 ž ((Q
(QQ o JWML (0 (0))..
Therefore round E-M results either an increase or no change in the objective. Since the WML objective is upper-bounded by N log H, the monotone increasing sequence Jwmn. (omn.((()) converges to local maximum of the objective.
A.3
Proof of Corollary 3.1.1
Proof. It suffices to show that the W-step also increases the objective JwMI 0).
We maximize JWML (w, 0) w.r.t. w, subject to the constraint Em W 1, resulting the following Lagrangian.
H
L(W, A) log
log
a
W
(24)
i=1
j=U
:=1
i=1
Taking partial derivative w.r.t. Wi and X and setting zero, have:
aL(W. X)
log Σ
(st))
+ log (1 + log w;) -
(25)
Ow;;
@L(W, X) 0%
Wi = 00
(26)
1=1
Σ f1 riy
Noting that P2
and Pij. =
and simplifying. we have:
ΣN
Σ
Σn
H = y (si;) Mray
1+ log
(27)
ru;;
where r - E/=0 Tay. Exponentiation of both sides and cross-multipiicttion results in:
[rexp (1 A)] w;
Σ
(
(28)
1=0
Summing over i, have:
rexp (1 + A) Σ
w (sig)raj
(29)
i=1 ==
Substituting back in equation 28 we finally have:
E/ wi (s ris
(30)
Σ E/=o v (si))r
Thus the maximizing w is exactly the W-step. Therefore, the form of the W-step ensures Jwmi (w/t), )()) 2 JwwI,WW (w/kk)) ((k)) 2 (w g(=-1)). Thus have mono-
tone increasing and bounded sequence JwMI. (w((), ((())) converging local maximum of JwMi.(W. 0).
A.4
Proof of Theorem 4.1
Proof.
We use the log-derivative trick [42]. (orr((;)) = (5
Vo log J (s;). So:
VeJos (0) = Esn~Pisn
Σ ri Veu
ry (s, log Vo (31)
16

---

A.5
Proof of Proposition 4.1
(k) Proof. First, for given (*), substituting for 4ij yields:
(R)
from Theorem 3.1 and uū from the W-step
En n= workk)
1/0 (8is) Fis
(K) (k)
(Sin)
4i
Em= Sm= En=o ciach))
(Smn) mmm
n=0 wi (s Pi
(32)
Σ rin p2po(t) (sig)
(33)
Em 2n= (/0(())
(8mn Mmn
(Ss))ras
(34)
En v/a(())
(8mm Mmnn
2(h)
Therefore, we may write the M-step objective as
N
(
(R)
ij
log (Sis)
(35)
(k) log v (Sis) J(k] (0)
(0)
(36)
Dropping the iteration index (k), by defining constants Uyj = = (s: (s.g )ra calculated with the most recent value of 0, the M-step objective is equivalent to the following objective:
H
1
( =
Vig log 1/. (81)
(37)
1=
where May := w (s:) ray j is calculated with the most recent value of 0 and held constant. Taking the gradient w.r.t 0 we have
H
(O) 1
Us Vo log 2 (s:j)
(38)
N
1=
Now, substituting for Vij. we have:
N
H
VoJu(0) = N
Tigyy 0
(Siz
V log V6 (Si))
(39)
This can be expressed as expectation over sample trajectories as:
H Σ
VOJM(0) = Egg
r (s,) Vo log (5,
VeJos(0)
Thus the gradient of the transformed M-step objective is identical to the optimal stopping policy gradient (OSPG). Therefore, we perform the E-step, W-step and a single gradient update, the sequence of policy parameters 0,, will exactly correspond to the updated OSPG policy parameters. We may therefore appeal to literature on incremental partial M-step E-M algorithms descent (21) conclude that for small enough step-size, that increases J JM(0) (0), the policy updates converge to a local maximum of both M... ( (W 0) and (os
[27] and gradient
17

---

A.6 Proof of Corollary 4.1.1
Proof. From the proof of Proposition 4.1, the M-step objective is equivalent the following objective:
N
H
1
(M = N
Vig log w (Si))
(40)
Now, substituting for v/ (Siy) in terms of the stopping policy using the trajectory reparameterizatioo
lemma (Lemma 3.1):
#-1
(0) Jas
44 log 80
(s:o)
+
Σ
Uij
log of (8:z) +
log(1
08 (Sin))
N
==1
n=
H
log(1
(Sin))
n
N
#-1
Σ
May log 03 (8is)
N
1=0
-1/1
log(1
(8ww))
-1/2
|log(1 (s:o)) + log(1 - (sa)))
U2s
[log(1
o8 (s:o)) + log(1 - (f()) + log(1 (8(22))
H
U&H
Σ
σ (s log(1
H Σ
Σ
Viy log of (sis)
Σ log(1 (s:)))
Vin
amj+1
Vig log /3 (Sij) + log(1
0g (s:)))
Vin
カ=ド+1
Since by Proposition 4.1, we have voJos(0) (O). Setting kij above expression for JM (0) and taking the gradient, we have:
Σ Ex=j+1 Von
in the
VeJos( =
1
ΣΣ
N
H
UsJ (1 o9 0 (S,g)
Voog(sy))
(41)
N
(st) (s
I=1
j=n
This completes the proof of Corollary 4.1.1
B Dealing with costs instead of rewards
Although one could have used the negative of cost reward, this is inconsistent with our Bayesian net model since we require positive rewards to define the reward augmented trajectory model. The following result addresses this issue by transforming problem with costs to with suitable reward specification.
Proposition B.I.
Given costs Cjj 2 0 the following two problems are equivalent:
arg min
N
ΣΣ
M ciju (si))
arg
Σ
Gin
H nn
Cij
V (Sig)
0
0
Cin
18

---

Proof. Starting with the cost minimization problem. we may write:
arg min
0 N ΣΣ
Cy 2) = arg min N
1
Σ
Ciy (s,))
(42)
1m1
where Cj == "n Gy and Cij
S
Since Σj V (8.)) = 1, we may subtract the constant
a."
N 1= Gi Ej=u 1 (sig) from the objective yielding: N
=1
N
H
1
arg min
Σ
Ciy (s1))
arg min
C4
(Gz 1) v/g (siz)
N
N
0=0
j=0
H
(1 Öis) 19 (s:g)
arg im
0
N
N
H
H
= arg max
Σ
1
(s1s))
0
N
Σn=u Cin
2=0
where we have expanded o; and dz.. This completes the proof.
H
C Neural Fitted Q-iteration approaches: DNN-FQI and RNN-FQI
equation (WBE) as follows: First, given step is bootstrapped, for a batch of trajectories yielding (s,g) = m K2 (sig)) Vj < H, S i S N. Next the parameters of the continuation function are fit: 0 arg min Σ E, (K)(st)) and the process is iterated. To provide competent DNN/RNN baselines for fitted Q-iteration (FQI) methods that are missing in the literature, we introduce a temporal FQI loss (Algorithm
Fitted Q-iteration methods [39 use the
parameterized function approximations Kÿ (5,). single
()+z(+1++1))
Algorithm 2 Pseudo-code for mini-batch computation of the FQI loss
Input: R == [ry]] K == (st)) ) (1 < S No, 0 S j S H, N₂ is batch size]
V -1 = stop-gradient(maan R.. --H-HHH11 -oH-- (bootstrap WBE to get value targets)
V H R., (final target is reward for last step)
J == MSE(V...: -1) (next step value is target for current continuation function)
D Further details of the experiments
All experiments were performed on shared server configured with 2 Intel Xeon Silver 12- core, 2.10 GHz CPUs with 256GB RAM and equipped with 6 NVIDIA 2080Ti GPUs. However, experiments were run on a single GPU at a time and no computation was distributed across GPUs.
D.1 Model hyper-parameter settings
Table 2 shows general hyper-parameter settings used for experiments. We apply Batch normal- ization the input and outputs of layer activation functions at all hidden layers. Due to the dense correlation structure between assets at each time-step of the American option pricing experiment, we choose the hidden units to be greater than the input dimension d.
As with RL policy gradients, we may subtract a baseline value reduce variance. The OSPG algorithm uses baseline that does not depend on time-index j, sufficient to guarantee an unbiased OSPG estimator (see Appendix F. In our experiments, we use:
N
h
b
1
Σ
Σ
TM
(43)
NH
i=1 1=0
19

---

n/a Table model hyper- parameer settings
method
hyper-parameter
tuned range
value
DOS, DNN-FQL, DNN-OSPG RRLSM, RNN-FQL RNN-OSPG
num hidden layers
n/a
2
num hidden layers
n/a
I
All models
hidden layer units
n/a
20
All models (Am. Option pricing)
hidden layer units batch size batch size
n/a
20 + d
All models
64
All models (Am. Option pricing)
n/a
128
All models
learning rate epochs batches/epoch optimizer
{0.01, 0.001, 0.0001)
0.001
All models
early stopping n/a n/a
100
All models
200
All models
Adam
RRLSM
Kernel noise std
n/a
0.0001
RRLSM
Recurrent noise std
n/a
0.3
D.2 Pricing Bermudan options
Table 3 shows model sizes (in trainable parameters), training, and inference times (per time-step). Model sizes grow with input dimension except for RRLSM, which uses an RNN with random, non-trainable weights extract features from the input. The parameter size of DOS is about an order magnitude higher than DNN-FQI and DNN-OSPG since parameters in backward induction methods like DOS grow linearly with the number of time-steps (parameters time-steps). Training and inference times are also high since individual models must be fit and inferred each time-step.
shareable across
Table 3: model sizes and compute times for Bermudan max-call experiment
method
assets
model-size (params)
mean training time (seconds)
mean time/prediction (J-seconds)
DOS
20
9,225
271
DNN-FQI
20
1,047
23
DNN-OSPG
20
1,047
29
RRISM
20
198
14
RNN-FQI
20
2,807
32
8
RNN-OSPG
20
2,807
37
DOS
50
15,165
289
DNN-FQI
50
1,707
28
6
DNN-OSPG
50
1,707
29
RRLSM
50
198
2
14
RNN-FQI
50
4,667
32
RNN-OSPG
50
4.667
32
DOS
100
25,065
326
DNN-FQI
100
2,807
30
DNN-OSPG
100
2,807
28
RRLSM
100
198
2
14
RNN-FQI
100
7,767
33
RNN-OSPG
100
7,767
30
8
DOS
200
44,865
317
DNN-FQI
200
5,007
30
DNN-OSPG
200
5,007
27
6
RRLSM
200
198
15
RNN-FQI
200
13,967
35
8
RNN-OSPG
200
13,967
30
20

---

Table American geometric-call option pricing: Results
average return (error %)
40
g
23
PDE-DGM 37
PDE-BSDE
DNN-FQI
DNN-OSPG
90
5,9021
5.8440 (0.9
NA
5.8822 (0.34%)
5.7977 (1.77%)
5.8704 (0.54%)
100
10.2591
10.1736 83%%
NA
10.2286 (0.30%)
10.1022 (1.53%)
10.2518 (0.07%)
7
110
15.9878
15,8991 (0.55%)
NA
15.9738 (0.09%)
15.0487 (5.87%)
15.9699 (0.11%)
13
90
5.7684
5.5962 (3. 00%)
NA
5.7719 (0.06%)
5.7411 (0.47%)
5.7436 (0.43%)
13
100
10.0984
9,9336 60%)
NA
10.1148 (6.16%)
9,9673 (1.30%)
10.0691 (0.29%)
13
110
15.8200
15.6070 (1 (1.40%)
NA
15.8259 (0.04%)
14.7759 (6.60%)
15.8107 (0.06%))
20
90
5.7137
5,2023 (9 9.00%)
NA
5.7105 (0.06%)
5.6607 (0.93%)
5.6983 (0.27%)
20
100
10.0326
9.5964 (4.40%)
10.0296 (0.03%)
10.0180 15%%
9.6372 (3.94%)
10.0100 (0.23%)
20
15.7513
15,2622 (3.10%)
NA
15.7425 (0.06%)
14.9345 (5.19%)
15.7553 (0.03%)
100
90
5.6322
OOM
NA
5.6154 (0.30%)
5.3858 (4.38%%
5.6211 (0.20%)
100
100
9.9345
OOM
9.9236 (0.11%)
9.9187 (0. 16%)
9,3954 (5.43%)
9,8954 (0.40%)
100
110
15.6491
OOM
NA
15.6219 (0. 17%)
14.6335 (6.49%)
15.6301 (0. 12%)
200
100
9.9222
0OM
9,9004 (0.22%)
9,9088 (0. 14%)
9.3772 (5.49%)
9,8991 (0.23%)
D.3
Pricing American options
The scope of the paper is solving discrete-time, finitehorizon,, model-free optimal stopping problems. Bermudan options that have discrete exercise opportunities are one example application. American options, which are continuum of possible exercise times. One way to convert this to our discrete-time setting is to solve related Bermudan options. These options limit exercise opportunities
popular,
based on continuous-
asset price evolution and have
fine discrete time grid.
State-of-the art algorithms for pricing American options are based on Partial differential equation (PDE) methods. These methods are model-based since they start with PDE (such the multi- dimensional Scholes Model) defining process evolution. For example, PDE methods often assume Markovian Black-Schole Dynamies, and the PDEs to be solved require the Black-Scholes model parameters, such as covariance of the Brownian motion, volatility, risk-free interest rate, and dividend yield. In contrast, model-free methods, such FQI and OSPG algorithms, do not prior information on the evolution dynamics of the underlying stochastic process.
Nevertheless, we compare our model-free OSPG method against state-of-the-arr PDE methods such as the Deep Galerkin Method (DGM) (37 and Backward Stochastic Differential Equations method (7 by suitable discretization of the original continuous time-problem. Note that the PDE methods also require discretization of the original PDE (ex, using the Euler- Maller-Mruyymaa scheme) or random sampling (as used in DGM) but do not end up directly solving Bermudan option.
We consider multi-dimensional continuous-ting American geometric-average call options with Black- Scholes dynamics considered in (37 and [7]. The payoff of these options depends on the price of d underlying assets with dynamics are Markovian, with payoff (reward) given by:
Black Sccoles dynamies and the strike price K. The
STT s/ exp((r - 8m 6m--2 22/ + oWW R.
II
St
K
(44)
for m = 1,2, r R is the risk-free rate, si (0, oo) represents the initial price, dm [0, 2o) is the dividend yield, am E (0, oc) the volatility and W is a d-dimensional Brownian motion, with instantaneous correlation between its d components given by B[W;W?;] Piyh. The reward for exercise at time t is given by Rç. We discretize into H + -1= = 100 possible exercise opportunities, using times t; = H for j = 0, 1. H. T is the option expiration duration in years. This yields the stopping problem: suPogrsH [.[
The specific option we consider is characterized by the following parameters: K = 100, 0.0. Om 0.25, Pij = 0.75 Vi # j. 8m 0.02, T 2. The exact price of this option, p", can be determined semi cemi-analyticalyy for comparison [7] We generate 10,000 batches (with batch size of 128) for training and compute option prices on a 3, 3,000-batch test sample. We compare vs. published results from state-of-the-art model-based PDE baselines, including the Deep Galerkin Method (PDE-DGM) [77, the Backward Stochastic Differential Equation (PDE-BSDE) method (7]. We also include published results [7] from the industry standard Longstaff-Schwartz Schwartz (LS) option
21

---

Table 5: Stopping fractional Brownian motion: Results
average return (standard deviation)
h
DOS
DNN-FQI
DNN-OSPG
DOS-ES
RRLSM
RNN-FQI
RNN-OSPG
0.05
0.70 (0.01)
0.87 (0.06)
1.14 (0.00)
1.18 (0.01)
1.16 (0.00)
1.24 (0.04)
1.28 (0.01)
0.10
0.54 (0.01)
0.68 (0.04)
0.92 (0.01)
0.93 (0.01)
0.94 (0.00)
0.99 (0.03)
1.03 (0.02)
0.20
0.34 (0.01)
0.42 (0.08)
0.58 (0.00)
0.55 (0.01)
0.57 (0.00)
0.59 (0.04)
0.64
0.30
0.19 (0.00)
(0.07)
0.29 (0.10)
0.28(0.011
0.29 (0.00)
0.27 (0.08)
0.36 (0.01)
0.40
0.10 (0.01)
0.02
0.13 (0.00)
0.09 (0.01)
0.10
0.04 (0.04)
0.15 (0.00)
0,50
0.00 (0.00)
(0.00)
0.00 (0.00)
(0.00)
0..000.000
0.00 (0.00)
0.00 (0.00)
0.60
0.08 (0.01)
(003)
0.10 (0.00)
0.08 (0.01)
0.06 (0.00)
0.03 (0.03)
0.10 (0.03)
0.70
0.16 (0.01)
0.08
0.17 (0.02)
(0.01)
0.19 (0.00)
0.10 (0.07)
0.20 (0.00)
0.80
0.23 (0.01)
(0.05)
0.25 (0.00)
(0.01)
0.27 (0.00)
0.18 (0.09)
0.27 (0.01)
0.90
0.31 (0.01)
(014)
0.28 (0.10)
(0.01)
0.33 (0.00)
0.21 (0.12)
0.33 (0.00)
0.95
0.35 (0.01)
0.01 (0.05)
0.34 (0.01)
0.36 (0.00)
0.36 (0.00)
0.25 (0.08)
0.36 (0.00)
pricing algorithm (23]. which uses linear approximation with multi-dimenniooal basis functions, suitable for low dimensional settings.
Table summarizes the experiment's 's results. Published results 7 for LS, DGM, and BSDE are included. NA denotes results not reported in the literature, while OOM indicates out of memory. Our model-free DNN-OSPG algorithm compares favorably with state-of-the-art model-based PDE-based option pricing methods that have prior knowledge of process evolution. Specifically, unlike LSS whose accuracy degrades with the number of correlated assets, and DNN-FQI, whose accuracy degrades up to 6.5%, DNN-OSPG retains excellent performance (< 0.55% error) closely approaching the model- mosel- based PDE methods (< 0.35% error). Of course, a key advantage of ONN-OSPG is that can be used to price options for which no known PDE is available to describe process evolution.
D.4 Stopping a fractional Brownian motion
Table 5 provides numerical values corresponding to Figure 2 RNN-OSPG dominates competing methods across all values the Hurst parameter this non-Markovian setting.
Table 6: Stopping fractional Brownian motion: Model sizes and compute times
method
model-size (params)
mean training time (seconds)
mean time/prediction
(u-seconds)
DOS
62,900
2250
26.9
DNN-FQI
651
21
0.5
DNN-OSPG
651
29
0.5
DOS-ES
276,300
2228
25.9
RRLSM
2,200
9
5.0
RNN-FQI 1,691
1.1
RNN-OSPG
1,691
79
1.1
D.5 Early stopping sequential multi-class classifier
We start with the 34 datasets, and corresponding values of a used in the M and remove binary classification datasets. This leaves 17 datasets. However, many of these have very few series or have a large number of classes relative to series size, which might make them unsuitable for training RNN classifiers. Nevertheless, we report results on all 17 datasets. Table Irepport the experiment's mean and standard deviation (over ten random splits) results over 17 UCR time-series datasets. Figure 2 provides a graphical visualization of the same results. N denotes the number of trajectories, H denotes the length of the series, and K denotes the number of classes. a trades-off classification accuracy and earliness. RNN-OSPG achieves the best performance on 15 of the 17 datasets.
22

---

Table 7: Early stopping a sequential multi-class classifier: Results
average cost (standard deviation)
Dataset
N/H/K/a
RRLSM
RNN-FQI
RNN-OSPG
CBF
930/128/3/0 2001/00
0.192 (0.017)
0.308 (0.138)
0.186 (0,011)
ChlorineConncentratioonn
4.307/166///0.4
0,468 (0.011)
0.523 (0.073)
0.455 (0.003)
Crop
24.000/46/24/0.06
0.428 (0.005)
0.407 (0.010)
0.389 (0.008)
ECG5000
5000/140/5/0.5
0.110 (0.005)
0.217 (0.059)
0.099 (0.006)
ElevtricDevices
16,637/96/7/0.1
0.257 (0.015)
0.260 (0.012)
0.228 (0.009)
FaceAll
2,250/1 3 1//14/0.01
0,108 (0.025)
0.100 (0.010)
0.092 (0.017)
FaceUCR
22500/131/14/0
0.358 (0.035)
0.465 (0.049)
0.328 (0.028)
FiftyWords
905/270/5000.5
0.667 (0.027)
0.812 (0.041)
0.634 (0.029)
InserrWighhatSoond
2,200/256/1 1/1
0.666 (0.064)
0.897 (0.110)
0.646 (0.080)
Medicallmages
1,141/99/ 10/0.07
0.296 (0.033)
0.309 (0.031)
0.263 (0.038)
MelbournePPedestrian
3.633/2441000..8
0.591 (0.065)
0.597 (0.068)
0.487 (0.044)
MixedShappssRegllaraaaa Train
2.925/1024/5P0.1 I
0.194 (0.024)
0.194 (0.008)
0.191 (0.037)
NonttvasiveeccalEECChhoxxx2
3,765/750/42/0.06 04
0,418 (0.094)
0.343 (0.008)
0.295 (0.064)
StarLighiCurres
9,236/1024/3/0.3
0.120 (0.043)
0.315 (0.067)
0.165 (0.035)
Symbols
1.020/398/600.2
0.103 (0.013)
0.208 (0.030)
0.239 (0.070)
UWWaeeeetuurLLibrra
4.478/315/8/0.5
0.523 (0.023)
0.658 (0.026)
0.498 (0.040)
WordSynonyms
905/270/25/0.6
0.760 (0.024)
0.913 (0.043)
0.727 (0.041)
E
Baseline subtraction for variance reduction
As with RL policy gradients, we may subtract a baseline value 29 to reduce variance. However, unlike the general RL case, due to the stopinggttime-bsse formulation of the OSPG, the OSPG baseline should not be time-varying.
Proposition E.1 (baseline subtraction for OSPG). The optimal stopping policy gradient (OSPG) of Theorem 4.1 is invariant to the subtraction of a constant (w.rt. trajectory) baseline from every reward in the trajectory. Thus:
H
VeJos(0)
(an=)((H)
Σ
rr Vo log 09(ss)
j=0
Σ (ry (s, log uog
j=0
Proof. It suffices to show E(gn)(
-/H dnb Vo log v (s₁)
0. We proceed as follows:
H
H
Vows (s,)
Eay P(BH)
Σ 3 (s,) 1og
Fag
bu (8,)
v (s,)
j=0
H
= Ean=B(sn)
V
by (s,)
j=0
Eay~B(sn)
Vab
2 (ss)
1=0
(45)
23


Reviews:
[{"review_id": "S81ckwvBkx", "reviewer": "Reviewer_XsN5", "summary": "The paper proposes an RNN-based approach for optimal stopping which is based on a Bayesian inference view of optimal stopping. The proposed model can be trained with direct optimization via policy gradients, or with expectation-maximization (EM). These two appraoches are shown to be equivalent. This new RNN-based approach is shown to outperform state of the art methods on a couple of commonly used datasets.", "questions": "- In the first equation in equation 2, why is the numerator $R_\\tau$?\n- What is the justification for the paramterization of $Y_j$ in equation 2? Is this an arbitrary design decision?\n- Why is the XOR used for $Y$ on line 167?\n- In what sense is the proposed method a Bayesian interpretation of optimal stopping? Does the Bayesian interpretation still hold once the weights are introduced into the objective?", "limitations": "The authors did not adequately address the limitations of the work since there is no conclusion or discussion section.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The limitations of the existing deep neural network approaches are discussed and contributions of this work are clearly stated. The background on optimal stopping is also introduced in detail.", "weaknesses": "- **Writing and organization of the paper have much room for improvement.** \n\n**Overuse of abbreviations makes the paper difficult to read.** Although abbreviations like DNN and EM are common and inevitable, I personally would suggest against abbreviating weighted maximum likelihood as WML and policy gradiants as PG in the text. To make things worse, one of the main approaches is named DROS-OSPG, with an unnecessary repeat of \"optimal stopping\" which I find to be cumbersome and confusing.\n\n**Equations with conflicting real and dummy indices.** In equation 2 and theorem 3.1, the index $j$ is both used as a real index and a dummy index for summation. \n\n**There's too much technical detail in the main paper.** Equivalence of EM and policy gradient is interesting but probably belong better in the supplements. However I do understand that the significance of this fact might have eluded me since I am not an expert in this field. The Keras-specific implementation detail on lines 246-247 can also be saved for the supplements.\n\n**No conclusion or discussion paragraph at the end.** As a consequence, the paper does not find room to discuss its limitations, which is a requirement for NeurIPS papers.\n\n- **Ablations are missing.** Since I am not an expert in this specific field, I do not know if the improvements over the state of the art are significant enough. From the prospective of a research paper, I feel like some design decisions need to be justified by running ablations. For example, how important are the weights in the weighted maximum likelihood objective? Abalation studies like this would justify the various claims put forth throughout the paper.\n---\nOnce again I must say that it is very likely that I do not understand the significance of the paper due to lack of familiarity with the field. My main concerns with the paper lie in its presentation. I do not think the paper at its current state is doing a good job of illustrating the key ideas of the new method and of convincing me that the contributions are novel and significant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewers comments. To better help clarify the novelty and significance of the paper and approach, we have included context in the global comments to all reviewers. We hope this helps the reviewer in appreciating the contribution and to reconsider the rating.\n\nSpecific questions raised in the review are addressed below.\n\n>In the first equation in equation 2, why is the numerator $R_{\\tau}$?\n\n**Response:** This is a typo: \n\n$\\mathbb{P}(Y_j = 1 | {\\bf R}_H, A_j = 1)$ should be equal to \n\n$\\displaystyle\\frac{R_j}{\\sum_{k=0}^H R_k }$ \n\ninstead of \n\n$\\displaystyle\\frac{R_{\\tau}}{\\sum_{j=0}^H R_j}$\n\nas appeared in the paper.\n\n>What is the justification for the parameterization of $Y_j$ in equation 2? Is this an arbitrary design decision?\n\n**Response:** The formulation of this conditional probability distribution is indeed a design choice, but not arbitrary. \n\n* Since we desire to encode reward opportunities at each step in the trajectory into the BN and every node in the BN represents a conditional probability distribution (CPD), it is natural to use the relative reward at a time-step (normalized by total reward over the trajectory) to represent this reward opportunity as a CPD. \n\n* A key consequence of this choice is that it leads to an equivalence with policy gradients and minimization of the optimal stopping objective.\n\nSimilar design choices have also been made in other related work. Please see equation (3) in [15] Sergey Levine, \"Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Review\". The authors say: \"While this might at first seem like a peculiar and arbitrary choice, it leads to a very natural posterior distribution...\"\n\nNote that while we are inspired by a corresponding view of reinforcement learning [15], the resulting modeling choices needed to capture the structure of optimal stopping in our approach leads to a very different BN model. For instance in the former case, rewards may be accumulated over time-steps and trajectory lengths are not variable, rolling out to the horizon. Also that formulation leads to a maximum entropy objective.\n\n> Why is the XOR used for on line 167?\n\n**Response:** We use the XOR operator to define the random variable $Y$ from the $Y_j$'s. Since $Y=1$ if and only if exactly one of the $Y_j$'s are 1. The reward for a trajectory can only be claimed by a stop action at a single time-step. This requires only a single $Y_j = 1$, allowing us to sum the probabilities of stopping and collecting rewards at each time-step of the trajectory (equation 5)\n\n>Ablation for the weights in WML\n\n**Response:** Our intent in this paper is not to use the WML weights explicitly. We provide a particular (*and natural*) choice of weights: **weight each trajectory by the expected reward of that trajectory** which results in a particular WML objective, which then leads to equivalence between the WML and policy-gradient approaches **and** minimization of the original optimal stopping objective from definition 2.4.\n\nAlso, we feel that it is not meaningful to ablate different weight choices in this case since the WML objective itself changes with different weights. To ablate, one needs to change something and measure against a fixed target. In this case the proposed ablation would be shooting at a different target.\n\n>In what sense is the proposed method a Bayesian interpretation of optimal stopping? \n\n**Response:**  What we have shown is that the peculiar state-action trajectories in optimal stopping can be modelled explicitly by a Bayesian Network (Figure 1a) which can then be used to rewrite the classic optimal stopping objective of equation (10) in the form of equation (12). It is in this sense that we have a Bayesian Net interpretation of the optimal stopping problem. A real benefit of this view is that by computing probabilities over state-action trajectories, we avoid explicitly sampling actions (a.k.a. Monte-Carlo state-action trajectory rollouts) like policy-gradient methods typically do.\n\nA reward augmented version of the state-action trajectory network (Figure 1b) additionally captures the notion of an optimal stopping trajectory, by introducing optimality variables $Y_j$ and corresponding conditional probability distributions (equation 2) into the model. This latter approach leads to a WML problem which does not in general reduce to minimization of the classic optimal stopping objective, **unless** the CPD and weights have the specified form. In this sense, this is a generalized interpretation of optimal stopping problems.\n\n>Does the Bayesian interpretation still hold once the weights are introduced into the objective?\n\n**Response:**  The reward augmented Bayes Net model (Figure 1b) is simply a model of state-action trajectories and corresponding relative reward possibilities **inside** a  trajectory. This **interpretation does not change** by introducing weights into the objective since these weights assign importance to entire trajectories (so do not affect relative rewards inside a trajectory).\n"}, {"review_id": "TxFttIvXRq", "reviewer": "Reviewer_njDJ", "summary": "Optimal stopping is the problem of choosing a time to take a given action based on sequentially observed random variables in order to maximize an expected payoff. Previous works used Deep Neural Networks to find the optimal stopping time (e.g. Backward Induction method), however, as the authors mentioned, these approaches have several limitations in non-Markovian settings. The paper presents the Optimal Stopping Problem as an inference problem on a Bayesian Network and they use RNNs to learn the model-free optimal stopping strategies.", "questions": "- American options are the most popular in practice and is a very good case study to solve.\n- Have you tested your algorithm on different American options? If not, why not?\n", "limitations": "- From the tables 2 and 3 (Appendix C), the training time of DROS is bigger compared to the baselines.\n- The proposed method can suffer in terms of time complexity when we test it to solve problems in high dimensions.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Authors introduce a reasonable way to solve the optimal stopping problem and provide the corresponding theoretical justifications.\n- The approach is well motivated (lines 43-60).\n- The experimental results demonstrate that their method outperforms the baseline.\n- The authors compared the training and inference times for DROS and the baseline.\n- The paper is well written and organized.\n- Experiments were done on real-world benchmarks.\n", "weaknesses": "- There is a whole literature on how to use deep learning to solve partial differential equations (PDEs) in general, and more specifically option pricing problems. Many papers solve PDEs using deep learning in the context of optimal stopping time.\n- There are several papers on optimal stopping problems, I encourage the authors to include more baselines in their comparisons.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating the motivation, contribution, presentation, and organization of the paper. The main concern seems to be with regard to the vast body of work on PDE based optimal stopping approaches, specifically with regard to solving American options. \n\nWe hope that have fully addressed this concern in the specific comments below, including direct comparison of our model-free method with state-of-the-art PDE based American option solvers which are in fact model-based. \n\nConsidering the mitigation of this perceived weakness, we hope the rating will also be reconsidered.\n\n> There is a whole literature on how to use deep learning to solve partial differential equations (PDEs) in general, and more specifically option pricing problems. Many papers solve PDEs using deep learning in the context of optimal stopping time. I encourage the authors to include more baselines in their comparisons.\n\n**Response:** Indeed, there is a lot of interest in using deep-learning to solve PDEs with application to option pricing. However, feel that PDE based baselines are not appropriate baselines for this paper, for the following reasons:\n\n* **The setting of the paper is discrete-time, finite-horizon optimal stopping problems**. There is no natural PDE which describe the dynamics such systems in general, thus ruling out PDE approaches. PDE based methods, including deep learning methods are inherently designed for *continuous-time* optimal stopping problems.  Note however, that while we may approximate continuous-time problems by choosing a fine discretization grid, to our knowledge, natively discrete-time problems cannot necessarily be solved using the PDE approach.\n\n* **We consider the PDE methods to be in the category of model-based methods**, since they start with a specific PDE to be solved. Consider, for example, popular PDE based American option pricing methods such as the Deep Galerkin Method (DGM) [Sirignano and Spiliopoulos, 2018] and the Backward Stochastic Differential Equation (BSDE) method [Chen and Wan, 2020]: These assume Markovian Black-Scholes Dynamics and the PDEs to be solved require the Black-Scholes model parameters, such as covariance of the Brownian motion, volatility, risk-free interest rate, and dividend yield. In contrast, our method (and those we compare against) does not use any prior information on the evolution dynamics of the underlying stochastic process.\n\nWe will add references and discussion to reflect these points.\n\n> American options are the most popular in practice and is a very good case study to solve. Have you tested your algorithm on different American options? If not, why not?\n\n**Response:**   As stated above, this paper is about solving discrete-time, finite-horizon optimal stopping problems. Option pricing (specifically Bermudan options, that have discrete exercise opportunities) are just one example application. We did not include American options since they are continuous-time and hence we felt that they were not natural candidates to show efficacy of the developed methods.\n\nThat said, our method can indeed be used to price American options in a model-free manner, simply by solving the corresponding Bermudan option at a finer discretization (ie: increasing discrete exercise opportunities to day level, for example). Note that Continuous-time methods for American options (such as those cited above) require discretization of the original PDE (ex: using Euler-Maruyama scheme) or random sampling (as used in DGM), so often do not end-up directly solving a Bermudan option.\n\nAlthough as noted above the PDE approaches are not model-free, **we have now run our approach in pricing challenging high-dimensional American options** and compare vs. published results from state of the art PDE baselines including Deep Galerkin Method (DGM) [Sirignano and Spiliopoulos, 2018] and the Backward Stochastic Differential Equation (BSDE) method [Chen and Wan, 2020]. \n\nWe consider the 100 dimensional continuous-time **American** geometric-average call option with Black-Scholes dynamics considered in [Sirignano and Spiliopoulos, 2018] and [Chen and Wan, 2020]. The option is characterized by the following parameters: \n$r$: 0.0, $\\delta$: 0.02, $\\sigma$: 0.25,  $\\rho_{ij}$: 0.75, 'time_horizon_yrs': 2 years, 'strike_price': 100. The exact price of this option can be determined semi-analytically for comparison [Chen and Wan, 2020].\n\n| Method    | stock price | option_price | exact_price |\n| :---: | :---: | :---: | :---: | \n| [Sirignano and Spiliopoulos, 2018] | 100 | **9.9236** | 9.9345 |\n| [Sirignano and Spiliopoulos, 2018] | 110 | N/A | 15.6491 |\n| [Chen and Wan, 2020] | 100| 9.9187 | 9.9345 |\n| [Chen and Wan, 2020] | 110| 15.6219 | 15.6491 |\n| DROS-OSPG (ours) | 100| 9.8675 | 9.9345 |\n| DROS-OSPG (ours) | 110| **15.6428** | 15.6491 |\n\n\nOur model-free algorithm yields results competitive with state of the art PDE methods that assume Black-Scholes dynamics. We were surprised by the excellent performance of our method, since we did not expect it to work well in a natively continuous-time setting. This opens the door for using our approach to price American options in a model-free setting, especially when the underlying trajectories are non-Markovian and are not required to follow Black-Scholes dynamics.\n\nWe can include a more comprehensive comparison with PDE methods and American options in the supplemental material.\n\n**References**\n\n[Sirignano and Spiliopoulos, 2018] DGM: A deep learning algorithm for solving partial differential equations. Journal of Computational Physics, 375:1339–1364, 2018.\n\n[Chen and Wan, 2020] Yangang Chen & Justin W. L. Wan (2020): Deep neural network framework\nbased on backward stochastic differential equations for pricing and hedging American options in high dimensions, Quantitative Finance"}, {"review_id": "8sCphSqZuy", "reviewer": "Reviewer_vhpm", "summary": "The paper purports to develop a framework of optimal stopping that generalizes the previous approaches by incorporating non-Markovian settings and using a Bayesian network formulation.", "questions": "1. It isn’t clear why every finite stopping time (as defined in the literature as a measurable function $\\tau \\colon \\Omega \\to \\mathbb{N}$ such that $\\\\{\\tau \\le n\\\\} \\in \\mathcal{F} _ n$ for all $n \\in \\mathbb N$; here and elsewhere in the review $(\\mathcal{F})_{n \\in \\mathbb N}$ is the appropriate filtration which makes the relevant stochastic processes adapted) can be written in the form of Definition 2.3. I don’t believe it is even true — for intuitively the same reason why there are stopping times that are not hitting times. This makes me doubt that the paper is solving the desired optimal stopping problem and is limited to a rather special case.\n2. What does the notation $\\arg \\sup$ in Definition 2.4 mean? It isn’t immediately obvious that a optimal stopping time $\\tau^*$ will exist and therefore a small note showing this would be helpful. Perhaps a mention of the classical result that a finite optimal stopping time exists if and only if $\\tau_0 := \\inf \\\\{n \\in \\mathbb N : U_n = R_n\\\\} < \\infty$ a.s., where $U_n := \\text{ess sup} _ {\\tau \\in \\mathcal{T} _ n} \\mathbb{E}[R_\\tau \\mid \\mathcal{F}_n]$ and $\\mathcal{T}_n$ being the collection of all finite stopping times $\\tau$ satisfying $\\tau \\ge n$, would make this immediate. (Note: it can be shown that $U_n = V_n$ as defined in the paper.)\n3. As mentioned above $V_j$ should be\n    \n    $$\n    V_j(\\mathbf S_j) = \\text{ess sup}_{\\tau \\in \\mathcal{T}_j} \\mathbb{E}[R_\\tau \\mid \\mathcal{F}_j],\n    $$\n    \n    which is a *random variable* (see https://almostsuremath.com/2019/01/06/essential-suprema/ for the definition of essential supremum)*.* This isn’t what equation (1) says. Even the Wald-Bellman equation as written in the paper says that $V_j(\\mathbf S_j)$ is a random variable.", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The only strength of this paper in this reviewer's opinion is the fact that it tackles an important problem.", "weaknesses": "The paper is written in a manner that makes it very difficult to discern its contents. The presentation and the proofs are ridiculously long-winded even though they could they be easily written in much more succinct manner. Although the reformulation of the optimal stopping problem as a Bayesian is interesting at first sight, I don't see how it is useful unfortunately, especially given the fact that I have concerns about they are even maximizing. See the next section for more concrete examples of the problems this paper has.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's concerns regarding the definitions in the paper. Our treatment is closely related to the approach in the following references.\n\n**[27]** A. N. Shiryaev, \"Stochastic Disorder Problems\"\n\n**[Poor]** H. Vincent Poor, \"An Introduction to Signal Detection and Estimation\" \n\n**[Fischer]** Fischer, Tom. “Stopping times are hitting times: a natural representation.” Statistics & Probability Letters (2011)\n\nWe hope that the reviewer reconsiders the rating of the paper, since there were no issues other than clarifications w.r.t. definitions. Specific responses are as follows.\n\n> The reviewer expressed doubts about the definition of the optimal stopping problem in the paper, specifically, the stated concerns are:\n**a)** *It isn’t clear why every finite stopping time can be written in the form of Definition 2.3.* **b)** *I don’t believe it is even true-for intuitively the same reason  why there are stopping times that are not hitting times. This makes me doubt that the paper is solving the desired optimal stopping problem and is limited to a rather special case.*\n\n**Response:**  We clarify that the  formulation of the optimal stopping time in definition 2.3 applies to general discrete-time, finite horizon setting and is not a special case. Specific responses to a) and b) are as follows\n\n**a)** Definition 2.3 in our manuscript is the same as that in the classic textbook [Poor] \"An Introduction to Signal Detection and Estimation\" by H. Vincent Poor. Please see both page 137 and page 145 where the **policy stopping time** is defined as :\n\n$N(\\phi) = \\min$  \\{ $n | \\phi_n (Y_1, Y_2, \\cdots, Y_n) = 1$ \\}\n\nHere $N(\\phi)$ is the policy stopping time,  $\\phi$ is equivanent to our stopping policy $\\varphi$, and $Y_1, Y_2, \\cdots, Y_n$ is equivalent to ${\\bf S}_j$ in our notation.\n\n**b)** As the reviewer remarks, hitting times are stopping times (by the Debut Theorem).\n\nHowever, on a technical note, stopping times can also be interpreted as hitting times **w.r.t. a \"stopping process\"**, see for example[Fischer] para 2 on page 1: *\"Astonishingly, it seems to be less widely taught (and maybe known) that the inverse is true as well: for any stopping time there exists an adapted stochastic process and a Borel measurable set such that the corresponding hitting time will be exactly this stopping time\"*.\n\n> What does the notation in Definition 2.4 mean? It isn’t immediately obvious that a optimal stopping time will exist and therefore a small note showing this would be helpful. \n \n**Response:** The $\\arg \\sup$ notation for $\\tau^*$  in definition 2.4 simply denotes that the optimal stopping time (if one exists) satisfies $\\mathbb{E} [ R_{\\tau^*} ] = \\sup_{\\tau} \\mathbb{E} [ R_{\\tau} ]$. \n\nExistence and finiteness of $\\tau^*$ is guaranteed if $\\mathbb{E} \\sup_{k\\geq 0} | R_{k}| < \\infty$. See page 58 of [27] A. N. Shiryaev, \"Stochastic Disorder Problems\" book. We will add a short note regarding this technical condition in the revised paper as suggested by the reviewer. We agree that the condition suggested by the reviewer is indeed a sound alternative condition. However, our treatment is along the lines of [27] and easy to verify.\n \n>Use ess sup in equation (1) to define $V_j$. It is a random variable unlike what equation (1) suggests.\n\n**Response:** The issue is due to a typo in equation (1): It should be \n\n $\\mathbb{E} [ V_j({\\bf S_{\\textit j}}) ] = \\sup_{\\tau \\geq j} \\mathbb{E} [ R_{\\tau} ]$\n\n instead of\n\n $V_j({\\bf S_{\\textit j}}) = \\sup_{\\tau \\geq j} \\mathbb{E} [ R_{\\tau} ]$. \n\nThis result appears on page 60, Theorem 1 (case of a finite time horizon)  of [27] A. N. Shiryaev, \"Stochastic Disorder Problems\" book."}]

Author rebuttal:
We thank the reviewers and appreciate the concerns raised. Here we address concerns regarding the significance of our contribution. We respond to each reviewer individually in specific comments.

While there is a vast body of work on optimal stopping problems in the Markovian setting, the literature on model-free optimal stopping in **non-Markovian settings** is sparse. This is of great practical importance in areas such as finance (option pricing), operations research (predictive maintenance), early classification/detection etc. 

Two of the main challenges (mentioned in lines 43-60, 76-79) in developing effective algorithms for this setting include:

* **Explosion of state space:**.  Ready extensions of Markovian approaches to non-Markovian settings results in state space explosion rendering them impractical. Solving the problem at hand **requires efficient parameterization of state space, such as afforded by RNNs**. However, popular optimal stopping approaches either cannot use RNNs for structural reasons (backward induction) or fare poorly in non-Markovian settings even if RNNs are used (fitted Q-iteration). Thus, *one does not encounter the use of RNNs in optimal stopping settings*.

* **Lack of model-free direct RL methods:**  RL style policy-gradient algorithms are typically online algorithms and require **expensive monte carlo policy rollouts**. *Policy gradient methods are notably missing* from the optimal stopping literature.

Keeping these problems in mind, **we bring together, for the first time, RNNs, probabilistic graphical models and policy-gradient methods to design an RNN-based policy-gradient algorithm for non-Markovian optimal stopping settings**. One of the key contributions is to is to *avoid expensive Monte-Carlo rollouts in the policy gradient algorithm by performing inference* on a Bayes Net (a probabilistic graphical model) model of state-action trajectories (Section 4).

Extending the Bayes net trajectory model with reward augmentation (section 3) yields a weighted maximum likelihood (WML) policy estimation approach that is a *generalization of the optimal-stopping policy-gradient method, in the sense that we recover our policy gradient algorithm for specific design choices of CPDs and weights* (section 4.1). One of the key benefits of this generalization is that the procedure can be adapted to various settings by augmentation with additional variables/latents makes it possible to model time-dependent stochastic disorders, such as change-points etc, also permitting a readymade solution method, via incremental EM.

Meta-review: The reviewers have provided a comprehensive evaluation of the paper, which proposes an RNN-based approach for optimal stopping based on a Bayesian inference view. The reviewers have highlighted the strengths of the paper, including the clear statement of contributions, detailed introduction of optimal stopping, and the theoretical justifications provided for the proposed approach. The experimental results demonstrating the method's superiority over the baseline were also appreciated.

However, the reviewers have also pointed out several areas for improvement. The presentation of the paper, particularly the use of abbreviations and the organization of technical details, was a common concern. The lack of a conclusion or discussion section was also noted, as was the absence of ablation studies to justify design decisions.

The reviewers also raised several questions about the paper's content, including the justification for certain parameterizations and the Bayesian interpretation of optimal stopping. These questions indicate areas where the paper could provide more clarity or justification.

Despite these concerns, the reviewers generally found the paper to be technically solid and its contributions to be valuable. The paper's approach to optimal stopping is novel and its performance on commonly used datasets is promising.

In light of these evaluations, I recommend accepting this paper. However, I strongly encourage the authors to consider the reviewers' feedback in revising their paper. Improving the presentation and organization, providing a conclusion or discussion section, and addressing the questions raised by the reviewers could significantly enhance the paper's clarity and impact.
Decision: Accept (poster)