# Estimation of Optimal Dynamic Treatment Assignment Rules under Policy
Constraints††thanks: I would like to thank Toru Kitagawa, Aleksey Tetenov, Ryo
Okui, Jeff Rowley, and participants in semianrs at UCL and University of Tokyo
and Cemmap/WISE Workshop on Advances in Econometrics in Xiamen, the 2019 Asian
Meeting of the Econometric Society in Xiamen, and the 2020 World Congress of
the Econometric Society for their comments and suggestions. I acknowledge
financial support from ERC Grant (number 715940).

Shosei Sakaguchi Faculty of Economics, The University of Tokyo, 7-3-1 Hongo,
Bunkyo-ku, Tokyo 113-0033, Japan. Email<EMAIL_ADDRESS>
(August 27, 2024)

###### Abstract

This paper studies statistical decisions for dynamic treatment assignment
problems. Many policies involve dynamics in their treatment assignments where
treatments are sequentially assigned to individuals across multiple stages and
the effect of treatment at each stage is usually heterogeneous with respect to
the prior treatments, past outcomes, and observed covariates. We consider
estimating an optimal dynamic treatment rule that guides the optimal treatment
assignment for each individual at each stage based on the individual’s
history. This paper proposes an empirical welfare maximization approach in a
dynamic framework. The approach estimates the optimal dynamic treatment rule
from panel data taken from an experimental or quasi-experimental study. The
paper proposes two estimation methods: one solves the treatment assignment
problem at each stage through backward induction, and the other solves the
whole dynamic treatment assignment problem simultaneously across all stages.
We derive finite-sample upper bounds on the worst-case average welfare-regrets
for the proposed methods and show $n^{-1/2}$-minimax convergence rates. We
also modify the simultaneous estimation method to incorporate intertemporal
budget/capacity constraints.
Keywords: Dynamic treatment effect, dynamic treatment regime, individualized
treatment rule, empirical welfare maximization.
JEL codes: C22, C44, C54.

###  1 Introduction

Many policies involve dynamics in their treatment assignments. Some policies
assign a series of treatments to each individual across multiple stages, e.g.,
job training programs that consist of multiple stages (e.g., Lechner (2009);
Rodríguez et al. (2018)). Some policies are characterized by when to start or
stop consecutive treatment assignment, e.g., unemployment insurance programs
with reduced benefit level after unemployment duration exceeds a certain
length (e.g., Meyer (1995); Kolsrud et al. (2018)). Examples of dynamic
treatment assignment also include sequential medical interventions,
educational interventions, and online advertisements, among others.

For a dynamic treatment policy, the effect of treatment at each stage is
usually heterogenous with respect to the past treatments, past outcomes, and
individual characteristics. Thus, when implementing a dynamic treatment
policy, a policy-maker wants to know how to assign a series of treatments
across multiple stages to maximize social welfare. The decision of treatment
assignment to an individual at each stage should depend upon his/her
accumulated information at the corresponding stage. In the context of the
sequential job training program, the policy-maker’s interest is in which
training regimen to assign to each individual at each stage depending on
his/her history of prior training participation, associated labor outcomes,
and other observed characteristics. In the context of the unemployment
insurance policy, an important question is when and whom to reduce the
insurance level given a recipient’s characteristics and past effort towards
job search.

This paper proposes a statistical decision approach to solve dynamic treatment
choice problems using panel data from experimental or quasi-experimental
study. We assume dynamic unconfoundedness (Robins (1997)) holds, meaning that
the treatment assignment at each stage is independent of current and future
potential outcomes given the history of treatment assignments, associated
outcomes, and observed covariates. Under this assumption, we construct an
approach to estimate the optimal Dynamic Treatment Regime (DTR)111Borrowing
the terminology of statistics literature, we call the dynamic treatment
assignment rule DTR. building on the idea of Empirical Welfare Maximization
(EWM) (Kitagawa and Tetenov (2018)). The EWM approach is based on similarity
between treatment choice by maximizing empirical welfare and classification by
minimizing empirical misclassification risk. We call the proposed approach
Dynamic Empirical Welfare Maximization (DEWM) approach. The DEWM appraoch
estimates the optimal DTR by maximizing empirical welfare, which is expressed
in terms of a sample mean of propensity score weighted outcomes and a given
DTR, over a pre-specified class of feasible DTRs. True (estimated) propensity
scores are used in the experimental (observational) data setting.

The DEWM approach can accommodate exogenous policy constraints (e.g.,
interpretability or fairness) by restricting the class of feasible DTRs.
Moreover, the DEWM approach can be applied to different types of dynamic
treatment choice problems, such as start/stop time decision problems, where
the interest is in when consecutive treatment assignment should be started or
stopped for each individual, and one-shot decision problem, where the interest
is in when each individual should receive a one-shot treatment. Various types
of dynamic treatment assignment problems can be specified by constraining the
relationship of treatment assignments across stages.

Adapting the EWM approach to the dynamic treatment framework is a nontrivial
task. In the dynamic framework, the effect of treatment at each stage can vary
with respect to the past treatments and outcomes. Hence, the treatment at each
stage should be decided by taking account of not only the direct effect of the
treatment on current and future outcomes but also its indirect effect on
future outcomes through changing the effects of future treatments. We solve
this problem by providing two approaches. One approach is to estimate the
optimal DTR through backward induction, which solves the treatment choice
problem from the final stage to the first stage supposing at each stage that
the optimal treatments are chosen in subsequent stages. The other approach is
to estimate the optimal DTR simultaneously over all stages, solving the whole
empirical welfare maximization problem at once with respect to the entire DTR.

The two approaches are complementary each other. The backward estimation
method is computationally efficient; however, consistency is ensured only when
the pre-specified class of DTRs contains the first-best policy that assigns
the best treatment to any individual with any history at all stages (except
for the first stage). In contrast, the simultaneous estimation method can
consistently estimate the optimal DTR on the pre-specified class of DTRs
irrespective of the feasibility of the first-best policy, at the cost of
computational efficiency.

Practically, some dynamic policies have budget/capacity constraints on their
treatment assignments, and these constraints are often imposed
intertemporally. Then a favorable DTR should effectively allocate the limited
budget/capacity to each stage so that welfare is maximized subject to the
limited budget/capacity. For this reason, the simultaneous estimation method
is modified in a way that the estimated DTR maximizes the empirical welfare
criteria under empirical budget/capacity constraints.

The statistical performance of the DEWM approach is evaluated in terms of
average welfare-regret that is the average welfare loss relative to the
maximum welfare achievable in the pre-specified class of DTRs. We derive
finite-sample and distribution-free upper bounds on the average welfare-
regrets of the backward and simultaneous estimation methods, which depend on
the sample size $n$ and a measure of complexity of the class of DTRs. Our main
theorem shows that the average welfare-regrets of the two methods converge to
zero at rate $n^{-1/2}$ in the experimental data setting. This rate is shown
to be the optimal convergence rate. In the observational data setting, the
rate of convergence depends on that of the estimated propensity scores. When
the budget/capacity constraints are imposed, we also analyze the excess
implementation cost of the estimated DTR over the actual budget/capacity. We
derive finite sample and distribution-free upper bounds on both the welfare-
regret and the excess cost of the estimated DTR which hold with high
probability.

#### Related Literature

This paper is related to the econometric literature on the statistical
decision of treatment choice, although most works in that literature focus on
the static treatment assignment problem. A partial list of works in that
literature is Manski (2004), Dehejia (2005), Hirano and Porter (2009), Stoye
(2009, 2012), Bhattacharya and Dupas (2012), Chamberlain (2012), Tetenov
(2012), Kitagawa and Tetenov (2018), Athey and Wager (2021), Kitagawa et al.
(2021), and Mbakop and Tabord-Meehan (2021). The policy learning methods of
Kitagawa and Tetenov (2018), Athey and Wager (2021), and Mbakop and Tabord-
Meehan (2021) build on the similarity of the empirical welfare maximizing
treatment choice and the empirical risk minimizing classification. Mbakop and
Tabord-Meehan (2021) propose penalization methods to control the complexity of
a treatment choice model and derive relevant finite sample upper bounds on the
average welfare-regret of the estimated treatment rules. Athey and Wager
(2021) apply doubly-robust estimators to the static policy learning, and show
that an $n^{-1/2}$-upper bound on regret can be achieved even in the
observational data setting.

In the dynamic treatment framework, Han (2020a) relaxes the sequential
randomization assumption, allowing for noncompliance, and studies point
identification of the average dynamic treatment effects and optimal non-
additive DTR, in which treatment assignment at each stage does not depend on
the history. Han (2020b) proposes a way to characterize the sharp partial
ordering of the counterfactual welfares of DTRs and the sharp set of the
optimal DTRs in an instrumental variable setting by using a set of linear
programs. Heckman and Navarro (2007) and Heckman et al. (2016) use exclusion
restrictions to identify the dynamic treatment effect by extending the
literature on the marginal treatment effect, but do not study identification
of the optimal DTRs.

Estimation of the optimal DTR has been widely studied in the biostatistics and
statistics literatures under the labels of dynamic treatment regime, adaptive
strategies, and adaptive interventions. Chakraborty and Moodie (2013),
Chakraborty and Murphy (2014), Laber et al. (2014), and Tsiatis et al. (2019)
review the developments in this field. There are some dominant approaches:
G-estimation (Robins (1989); Robins et al. (1992)) and Q-learning (Murphy
(2005); Moodie et al. (2012)). The G-estimation method specifies the
Structural Nested Mean Model (SNMM) that is the stage-specific difference of
the conditional mean of outcomes between two treatments. The G-estimation
method estimates the parameters of the SNMM, and then predicts the optimal DTR
from the estimated model (see, e.g., Murphy (2003), Vansteelandt and
Goetghebeur (2003), and Robins (2004) for further details about G-estimation).
The Q-learning method models the so-called Q-function, a function of the
stage-specific expected reward with respect to the current treatment and
history given that the optimal treatment is assigned in subsequent stages. The
Q-learning method estimates the parameters of the Q-function via backward
induction, and then estimates the optimal DTR as the sequence of stage-
specific treatment assignment rules that maximize the estimated Q-functions. A
potential drawback of these approaches is the risk of misspecification of the
models relevant to the counterfactual outcomes. In contrast, the DEWM approach
does not need to specify any model relevant to the counterfactual outcomes;
instead, it specifies the propensity scores, which are known in the
experimental data setting.

Several works have proposed estimation methods of the optimal DTR based on the
similarlity between the statistical treatment choice and machine learning
classification problems. Zhao et al. (2015) develop estimation methods of the
optimal DTR using the Support Vector Machine with propensity score weighted
outcomes. They show the convergence of the welfare-regret towards zero. Their
approach is computationally efficient because of the use of a convex surrogate
loss function. However, their approach is not consistent if the pre-specified
class of DTRs does not contain the first-best treatment for every stage. Zhang
et al. (2018) propose estimating the list form of the optimal DTR, converting
an unconstrained treatment rule estimated by Q-learning to the list form of
the decision rule at each stage. Nie et al. (2020) propose an estimation
method for the start/stop time decision problem based on the doubly-robust
estimator, and show that an $n^{-1/2}$ welfare-regret bound can be achieved
even in the observational data setting. While they focus on the start/stop
time decision problem, this paper covers a wider class of dynamic treatment
choice problems.

Finally, we note that the dynamic framework studied in this paper is different
from the framework of the bandit problem studied by, for example, Kock and
Thyrsgaard (2018). In the bandit problem framework, different individuals
arrive at each stage and each of them receives treatment only once. In
contrast, in the dynamic framework studied in this paper, the same individuals
arrive at each stage and each of them receives multiple treatments across
stages.

#### Structure of the Paper

The remainder of the paper is structured as follows. Section 2 describes the
dynamic treatment framework and defines the dynamic treatment choice problem.
Section 3 presents the two types of DEWM methods (backward and simultaneous
estimation methods) and shows their statistical properties. Section 4 extends
the simultaneous estimation method to accommodate the intertemporal
budget/capacity constraints. Section 5 modifies the backward and simultaneous
methods for the observational data setting. Section 6 presents a simulation
study to evaluate the finite sample performance of the proposed methods. In
Section 7, the proposed methods are applied to the Project STAR (Steps to
Achieving Resilience) data, where we estimate an optimal DTR to allocate each
student to a class with or without a full-time teacher aide in kindergarten
and first grade. We conclude this paper with some remarks in Section 8. All
proofs are given in Appendix A.

###  2 Setup

We first introduce the dynamic treatment framework, following Robins’s dynamic
counterfactual outcomes framework (Robins (1986, 1997)), in Section 2.1.
Subsequently, we define the dynamic treatment choice problem in Section 2.2.
Throughout the paper, we denote by $E_{P}\left[\cdot\right]$ the expectation
with respect to a distribution function $P$ and by $E_{n}\left[\cdot\right]$
the sample average.

####  2.1 Dynamic Treatment Framework

We suppose that there are $T$ $(T\geq 2)$ stages of binary treatment
assignment. Let $D_{t}\in\left\\{0,1\right\\}$, for $t=1,\ldots,T$, denote the
binary treatment at stage $t$. Throughout this paper, for any variable
$A_{t}$, we denote by
$\text{$\text{$\underline{A}$}$}_{t}\equiv\left(A_{1},\ldots,A_{t}\right)$ a
history of the variable up to stage $t$, and denote by
$\text{$\underline{A}$}_{t:s}\equiv\left(A_{s},\ldots,A_{t}\right)$, for
$s\leq t$, a partial history of the variable from stage $s$ up to stage $t$.
For example, the history of treatment up to stage $t$ is denoted by
$\text{$\underline{D}$}_{t}=\left(D_{1},\ldots,D_{t}\right)$. Depending on the
history of treatment up to stage $t$, we observe an outcome $Y_{t}$ at each
stage $t$. Let $Y_{t}\left(\text{$\underline{d}$}_{t}\right)$ be a potential
outcome at stage $t$ that is realized when the history of treatment up to
stage $t$ coincides with
$\text{$\underline{d}$}_{t}\in\left\\{0,1\right\\}^{t}$. The observed outcome
at each stage $t$ is

$\displaystyle
Y_{t}\equiv\sum_{\text{$\underline{d}$}_{t}\in\left\\{0,1\right\\}^{t}}\left(1\left\\{\text{$\underline{D}$}_{t}=\text{$\underline{d}$}_{t}\right\\}\cdot
Y_{t}\left(\text{$\underline{d}$}_{t}\right)\right),$

where $1\left\\{\cdot\right\\}$ denotes the indicator function. Let $X_{t}$ be
a $k$-dimensional vector of covariates that are observed before a treatment is
assigned at stage $t$. The distribution of $X_{t}$ may depend on the past
treatments, outcomes, and covariates. The covariates at the first stage,
$X_{1}$, represent pre-treatment information, which contain individuals’
demographic characteristics observed prior to the policy implementation. Let
$H_{t}\equiv\left(\text{$\underline{D}$}_{t-1},\text{$\underline{Y}$}_{t-1},\text{$\underline{X}$}_{t}\right)$
denote the history of all the observed variables up to stage $t$. $H_{t}$ is
available information for the policy-maker when she chooses a treatment
assignment at stage $t$. Note that $H_{s}\subseteq H_{t}$ for any $s\leq t$
and that $H_{1}=\left(X_{1}\right)$. We denote the support of $H_{t}$ and
$Z\equiv(D_{t},X_{t},Y_{t})_{t=1}^{T}$, respectively, by ${\cal H}_{t}$ and
$\mathcal{Z}$, and denote by $P$ the distribution of all the defined variables
$\left(D_{t},\left\\{Y_{t}\left(\text{$\underline{d}$}_{t}\right)\right\\}_{\text{$\underline{d}$}_{t}\in\left\\{0,1\right\\}^{t}},X_{t}\right)_{t=1}^{T}$.

From an experimental or observational study, we observe
$Z_{i}\equiv\left(D_{it},X_{it},Y_{it}\right)_{t=1}^{T}$ for individuals
$i=1,\ldots,n$, where
$Y_{it}=\sum_{\text{$\underline{d}$}_{t}\in\left\\{0,1\right\\}^{t}}\left(1\left\\{\text{$\underline{D}$}_{it}=\text{$\underline{d}$}_{t}\right\\}\cdot
Y_{it}\left(\text{$\underline{d}$}_{t}\right)\right)$ with
$Y_{it}(\underline{d}_{t})$ being a potential outcome for individual $i$ at
stage $t$ that is realized when $\underline{D}_{it}=\underline{d}_{t}$. We
suppose that the vectors of random variables
$\left(D_{it},\left\\{Y_{it}\left(\text{$\underline{d}$}_{t}\right)\right\\}_{\text{$\underline{d}$}_{t}\in\left\\{0,1\right\\}^{t}},X_{it}\right)_{t=1}^{T}$,
$i=1,\ldots,n$, are independent and identically distributed (i.i.d) under the
distribution $P$. Let $P^{n}$ denote the join distribution of
$\left\\{\left(D_{it},\left\\{Y_{it}\left(\text{$\underline{d}$}_{t}\right)\right\\}_{\text{$\underline{d}$}_{t}\in\left\\{0,1\right\\}^{t}},X_{it}\right)_{t=1}^{T}:i=1,\ldots,n\right\\}$
generated by $P$.

Let $e_{t}\left(d_{t},h_{t}\right)\equiv\Pr\left(D_{t}=d_{t}\mid
H_{t}=h_{t}\right)$ be a propensity score of treatment at stage $t$ given the
history up to that point. We suppose that the propensity scores are known
under the experimental study, but they are unknown and need to be estimated
under the observational study. We consider the experimental and observational
study settings in Sections 3-4 and Section 5, respectively.

Throughout the paper, we suppose that the following assumptions hold.

######  Assumption 2.1 (Sequential Independence Assumption).

For any $t=1,\ldots,T$ and
$\text{$\underline{d}$}_{T}\in\left\\{0,1\right\\}^{T}$,
$D_{t}\perp\left(Y_{t}\left(\text{$\underline{d}$}_{t}\right),\dots,Y_{T}\left(\text{$\underline{d}$}_{T}\right)\right)\mid
H_{t}$ holds.

######  Assumption 2.2 (Bounded Outcomes).

There exists $M_{t}<\infty$ such that the support of $Y_{t}$ is contained in
$\left[-M_{t}/2,M_{t}/2\right]$ for $t=1,\ldots,T$.

Assumption 2.1 is what is called a dynamic unconfoundedness assumption or
sequential/dynamic conditional independence assumption elsewhere, which is
commonly used in the literature on dynamic treatment effect analysis (Robins
(1997); Murphy (2003)). This assumption means that the treatment assignment at
each stage is independent of the contemporaneous and future potential outcomes
conditional on the history up to that point. This is usually satisfied in
sequential randomization experiments. In observational studies, this
assumption is often controversial, but can hold if a sufficient set of
confounders is available. Assumption 2.2 is a common assumption in the
literature on treatment effect analysis.

####  2.2 Dynamic Treatment Choice Problem

The goal of this paper is to provide methods to estimate the optimal DTR from
experimental or observational panel data. We denote a treatment rule at each
stage $t$ by $g_{t}:{\cal H}_{t}\mapsto\left\\{0,1\right\\}$, a mapping from
the history up to stage $t$ to the binary treatment. We define the DTR by
$g\equiv\left(g_{1},\ldots,g_{T}\right)$, a sequence of stage-specific
treatment rules. The DTR guides the policy-maker to choose a treatment for
each individual at each stage depending on the individual’s history up to that
point.

We suppose that the welfare that the policy-maker wants to maximize is the
population mean of a weighted sum of outcomes:
$E_{P}\left[\sum_{t=1}^{T}\gamma_{t}Y_{t}\right]$, where the weight
$\gamma_{t}$, for $t=1,\ldots,T$, lies in $\left[0,1\right]$ and is chosen by
the policy-maker. If the policy-maker targets a time-discounted welfare, the
weight at each stage is $\gamma_{t}=\gamma^{T-t}$, where $\gamma$ is a time-
discount factor and lies in $\left(0,1\right)$. If the policy-maker targets
the outcome at the last stage only, the weights are $\gamma_{T}=1$ and
$\gamma_{t}=0$ for all $t\neq T$.

Under a DTR $g$, the realized welfare takes the following form:

$\displaystyle W\left(g\right)$ $\displaystyle\equiv
E_{P}\left[\sum_{\text{$\underline{d}$}_{T}\in\left\\{0,1\right\\}^{T}}\left(\left(\prod_{t=1}^{T}1\left\\{g_{t}\left(H_{t}\right)=d_{t}\right\\}\right)\cdot\sum_{t=1}^{T}\gamma_{t}Y_{t}\left(\text{$\underline{d}$}_{t}\right)\right)\right]$
$\displaystyle=\sum_{t=1}^{T}E_{P}\left[\sum_{\text{$\underline{d}$}_{t}\in\left\\{0,1\right\\}^{t}}\left(\left(\prod_{s=1}^{t}1\left\\{g_{s}\left(H_{s}\right)=d_{s}\right\\}\right)\cdot\gamma_{t}Y_{t}\left(\text{$\underline{d}$}_{t}\right)\right)\right].$

Given the propensity scores
$\left\\{e_{t}\left(d_{t},h_{t}\right)\right\\}_{t=1}^{T}$ and Assumption 2.1,
the welfare function can be expressed by the observables only:

$\displaystyle W\left(g\right)$
$\displaystyle=\sum_{t=1}^{T}E_{P}\left[\frac{\left(\prod_{s=1}^{t}1\left\\{g_{s}\left(H_{s}\right)=D_{s}\right\\}\right)\gamma_{t}Y_{t}}{\prod_{s=1}^{t}e_{s}\left(D_{s},H_{s}\right)}\right].$
(1)

We suppose that the policy-maker chooses a DTR from a pre-specified class of
feasible DTRs, which we denote by ${\cal G}\equiv{\cal
G}_{1}\times\cdots\times{\cal G}_{T}$, where ${\cal G}_{t}$ is a class of
feasible treatment rules at stage $t$ (i.e., a class of measurable functions
$g_{t}:\mathcal{H}_{t}\rightarrow\\{0,1\\}$). Then the ultimate goal of the
analysis is to choose an optimal DTR that maximizes the welfare
$W\left(\cdot\right)$ over $\mathcal{G}$.

In this paper, we restrict the complexity of the class of feasible DTRs in
terms of VC-dimension. The following definition gives the definition of VC-
dimension of a class of indicator functions and relevant concepts.

######  Definition 2.1 (VC-dimension of a Class of Indicator Functions).

Let $\mathcal{Z}$ be an arbitrary space and $\mathcal{F}$ be a class of
indicator functions from $\mathcal{Z}$ to $\\{0,1\\}$. For a finite sample
$S=\left(z_{1},\ldots,z_{m}\right)$ of $m\geq 1$ points in $\mathcal{Z}$, we
define the set of dichotomies by
$\Pi_{\mathcal{F}}\left(S\right)\equiv\left\\{\left(f\left(z_{1}\right),\ldots,f\left(z_{m}\right)\right):f\in\mathcal{F}\right\\}$,
which is all possible assignments of $S$ by functions in $\mathcal{F}$. We say
that $S$ is shattered by $\mathcal{F}$ when
$\left|\Pi_{\mathcal{F}}\left(S\right)\right|=2^{m}$; that is, $\mathcal{F}$
realizes all possible dichotomies of $S$. Then the VC-dimension of
$\mathcal{F}$, denoted by $VC(\mathcal{F})$, is defined to be the size of the
largest sample $S$ shattered by $\mathcal{F}$, i.e.,

$\displaystyle
VC(\mathcal{F})\equiv\max\left\\{m:\max_{S=\left(z_{1},\ldots,z_{m}\right)\subseteq\mathcal{Z}}\left|\Pi_{\mathcal{F}}\left(S\right)\right|=2^{m}\right\\}.$

We say that $\mathcal{F}$ is a VC-class of indicator functions if
$VC(\mathcal{F})<\infty$.

The following assumption restricts the complexity of the class of feasible
DTRs $\mathcal{G}$ in terms of the VC-dimension of $\mathcal{G}_{t}$ for each
$t=1,\ldots,T$.

######  Assumption 2.3 (VC-class).

For $t=1,\ldots,T$, ${\cal G}_{t}$ is a VC-class of functions and has VC-
dimension $v_{t}<\infty$.

This assumption restricts the complexity of the class of whole DTRs
$\mathcal{G}$ by restricting the class of feasible treatment rules
$\mathcal{G}_{t}$ at each stage. By restricting the complexity, we can choose
a simple to explain/interpret DTR and keep estimated DTRs from overfitting to
the data. We can also incorporate arbitrary exogenous policy constraints from
ethical or political reasons into DTRs by specifying the form of
$\mathcal{G}_{t}$ for each $t$. Some examples of practically relevant classes
of DTRs are linear eligibility score rules and decision tree rules.

######  Example 2.2 (Linear Eligibility Score).

The class of DTRs based on the Linear Eligibility Score is ${\cal G}={\cal
G}_{1}\times\cdots\times{\cal G}_{T}$ with ${\cal G}_{t}$, $t=1,\ldots,T$,
having the following form:

$\displaystyle{\cal
G}_{t}=\left\\{1\left\\{\beta_{1t}^{\prime}\text{x}_{t}+\beta_{2t}^{\prime}\text{$\underline{d}$}_{t-1}+\beta_{3t}^{\prime}\text{$\underline{y}$}_{t-1}\geq
c_{t}\right\\}:\left(\beta_{1t}^{\prime},\beta_{2t}^{\prime},\beta_{3t}^{\prime},c_{t}\right)^{\prime}\in\mathbb{R}^{k+2t-1}\right\\}.$

Under this class of DTRs, treatment assignment at each stage is decided based
on whether or not the linear eligibility score (
$\beta_{1t}^{\prime}\text{x}_{t}+\beta_{2t}^{\prime}\text{$\underline{d}$}_{t-1}+\beta_{3t}^{\prime}\text{$\underline{y}$}_{t-1}$)
exceeds a certain threshold value $c_{t}$. The main objective of data analysis
using this class is to construct an eligibility score (i.e., to decide
$\left(\beta_{1t}^{\prime},\beta_{2t}^{\prime},\beta_{3t}^{\prime},c_{t}\right)_{t=1,\ldots,T}$)
such that the obtained DTR maximizes the welfare $W(\cdot)$ over
$\mathcal{G}$. In this example, each ${\cal G}_{t}$ has VC-dimension at most
$k+2t-1$.

######  Example 2.3 (Decision Tree).

The decision tree representation of $g_{t}$ is a tree representing partition
of $\mathcal{H}_{t}$, which predicts treatment $0$ or $1$ by traveling from a
root node to a leaf node of a tree . For any integer $L\geq 1$, a depth-$L$
decision tree has $L$ layers, in which the first $L-1$ layers consist of
branch nodes, and the $L$-th layer consists of leaf nodes. Let $p_{t}$ denote
the dimension of $H_{t}$. Each branch node in the $\ell$-th layer is specified
by a splitting variable $H_{tj}\in H_{t}$ for some $j=1,\ldots,p_{t}$, a
threshold value $c\in\mathbb{R}$, and left and right child nodes in the
$(\ell+1)$-th layer. If $H_{tj}\geq c$, the left child node is followed;
otherwise, the right child node is followed. Every path terminates at a leaf
node, each of which assigns $g(h_{t})=0$ or $1$. From Lemma 4 of Zhou et al.
(2018), the depth-$L$ decision tree class of $\mathcal{G}_{t}$ on
$\mathcal{H}_{t}$ has VC-dimension bounded on the order of
$VC(\mathcal{G}_{t})=\widetilde{\mathcal{O}}(2^{L}log(p_{t}))$.222The notation
$f(n)=\widetilde{\mathcal{O}}(g(n))$ means that there is a function $h(\cdot)$
that scales poly-logarithmically in its argument for which $f(n)\leq
h(g(n))g(n)$. See Zhou et al. (2018) and Athey and Wager (2021) for detail.

Aside from the constraint on the functional form, by restricting the
intertemporal relationship of treatment rules across stages, we can specify a
type of dynamic treatment choice problem.

######  Example 2.4 (One-shot Treatment).

If the policy-maker wants to decide when to assign a one-shot treatment to
each individual, the analyst should impose the restriction
$\sum_{s=1}^{t-1}d_{s}+g_{t}(\cdot)\leq 1$ on ${\cal G}_{t}$ for each $t$.

######  Example 2.5 (Start/Stop Time Decision).

If the problem is to decide when to start or stop consecutive treatment
assignment for each individual, the restriction $d_{s}\leq g_{t}(\cdot)$ or
$d_{s}\geq g_{t}(\cdot)$, for all $s\leq t$, should be imposed on ${\cal
G}_{t}$, respectively.

Note that the VC-dimension of an additionally restricted class is not larger
than that of the original class.

Given a possibly constrained class of DTRs $\mathcal{G}$, we suppose that the
following overlap condition holds on the propensity scores
$\\{e_{t}(d_{t},h_{t})\\}_{t=1}^{T}$.

######  Assumption 2.4 (Overlap Condition).

For $t=1,\ldots,T$, there exists $\kappa_{t}\in(0,1)$ for which
$\kappa_{t}\leq e_{t}(d_{t},h_{t})$ holds for any pair
$(d_{t},h_{t})\in\\{0,1\\}\times\mathcal{H}_{t}$ such that there exists
$g_{t}\in\mathcal{G}_{t}$ that satisfies $g_{t}(h_{t})=d_{t}$.

When $\mathcal{G}$ is structurally constrained, Assumption 2.4 requires less
strict overlap condition than a common overlap condition which requires
$e_{t}(d_{t},h_{t})\in(0,1)$ for all
$(d_{t},h_{t})\in\\{0,1\\}\times\mathcal{H}_{t}$ and $t=1,\ldots,T$.333For
example, when the problem is to decide when to start consecutive treatment
assignment, Assumption 2.4 does not require $e_{t}(d_{t},h_{t})>0$ for any
$(d_{t},h_{t})\in\\{0,1\\}\times\mathcal{H}_{t}$ such that
$d_{s}>g_{t}(h_{t})$ for some $d_{s}\in\underline{d}_{t-1}$ and any
$g_{t}\in\mathcal{G}_{t}$.

We denote the highest welfare that is attainable on the class of feasible DTRs
${\cal G}$ by

$\displaystyle W_{{\cal G}}^{\ast}\equiv\max_{g\in{\cal G}}W\left(g\right).$
(2)

We consider estimating the optimal DTR that maximizes the welfare $W(\cdot)$
over $\mathcal{G}$ from the sample $\left\\{Z_{i}\right\\}_{i=1}^{n}$. In the
following section, We provide two methods to estimate the optimal DTR and
evaluate their statistical properties in terms of the maximum average welfare-
regret.

###  3 Dynamic Empirical Welfare Maximization

This section proposes two DEWM methods. One is based on backward induction
(dynamic programming) to solve the dynamic treatment choice problem,
sequentially, from the final stage to the initial stage. The other is based on
simultaneous optimization of $W\left(\cdot\right)$ over the whole class of
DTRs $\mathcal{G}$. The backward estimation method is computationally
efficient, but it can consistently estimate the optimal DTR only when
$\mathcal{G}_{t}$ contains the first-best treatment rule for all $t\geq 2$. In
contrast, the simultaneous estimation method can consistently estimate the
optimal DTR irrespective of whether $\mathcal{G}_{t}$ contains the first-best
treatment rule at each stage $t$, though it is computationally less efficient.
We explain the backward and simultaneous estimation methods in Sections 3.1
and 3.2, respectively. We subsequently evaluate the statistical properties of
these methods in terms of the maximum welfare-regret in Section 3.3.

####  3.1 Backward Dynamic Empirical Welfare Maximization

We first explain the backward estimation method. To guarantee consistent
estimation with a given distribution $P$, the following assumption requires
that the first-best treatment rule is attainable at all but the first stage.

######  Assumption 3.1 (First-Best Treatment Rule).

For any $t=2,\ldots,T$, there exists $g_{t,FB}^{\ast}\in{\cal G}_{t}$ such
that

$\displaystyle
E_{P}\left[\sum_{s=t}^{T}\gamma_{s}Y_{s}\left(\text{\text@underline{D}}_{t-1},g_{t,FB}^{\ast}(H_{t}),\ldots,g_{T,FB}^{\ast}(H_{T})\right)\mid
H_{t}=h_{t}\right]$ $\displaystyle\geq
E_{P}\left[\sum_{s=t}^{T}\gamma_{s}Y_{s}\left(\text{\text@underline{D}}_{t-1},1-g_{t,FB}^{\ast}(H_{t}),g_{t+1,FB}^{\ast}(H_{t+1}),\ldots,g_{T,FB}^{\ast}(H_{T})\right)\mid
H_{t}=h_{t}\right]$

for all $h_{t}\in{\cal H}_{t}$.

We call $g_{t,FB}^{\ast}$ that satisfies Assumption 3.1 the first-best
treatment rule at stage $t$. This assumption is satisfied when
$\mathcal{G}_{t}$, $t=2,\ldots,T$, are rich enough or are correctly specified
in the sense that they contain the first-best treatment rule. Note that the
treatment class for the first stage $\mathcal{G}_{1}$ is not required to
contain the first-best treatment rule.

To present the idea of the backward estimation method, we now suppose that the
generative distribution function $P$ is known and that the pair $\left(P,{\cal
G}\right)$ satisfies Assumptions 2.1 and 3.1. Then we can solve the dynamic
treatment choice problem with dynamic programming. Firstly, for the final
stage $T$, let

$\displaystyle g_{T}^{\ast}\left(h_{T}\right)$ $\displaystyle\in\mathop{\rm
arg\leavevmode\nobreak\ max}\limits_{g_{T}\in{\cal
G}_{T}}Q_{T}\left(h_{T},g_{T}\right)$

for any $h_{T}\in{\cal H}_{T}$, where

$\displaystyle Q_{T}\left(h_{T},g_{T}\right)\equiv
E_{P}\left[\gamma_{T}Y_{T}\mid
H_{T}=h_{T},D_{T}=g_{T}\left(h_{t}\right)\right]$

is the conditional mean of the weighted final outcome $\gamma_{T}Y_{T}$ given
that the history is $h_{T}$ and that the treatment rule $g_{T}$ is followed.
Under Assumptions 2.1 and 3.1, $g_{T}^{\ast}\left(h_{T}\right)$ is an optimal
treatment assignment for any $h_{T}\in{\cal H}_{T}$, meaning that the function
$g_{T}^{\ast}:{\cal H}_{T}\mapsto\left\\{0,1\right\\}$ coincides with the
first-best treatment rule (i.e., $g_{T}^{\ast}=g_{T,FB}^{\ast}$). Thus, under
Assumptions 2.1 and 3.1, the first-best treatment rule $g_{T}^{\ast}$ can be
obtained by solving

$\displaystyle g_{T}^{\ast}$ $\displaystyle\in\mathop{\rm
arg\leavevmode\nobreak\ max}\limits_{g_{T}\in{\cal
G}_{T}}E_{P}\left[Q_{T}\left(H_{T},g_{T}\right)\right],$ (3)

where the objective function is the expectation of
$Q_{T}\left(H_{T},g_{T}\right)$ over ${\cal H}_{T}$.

Recursively, from $t=T-1$ to $1$, we obtain

$\displaystyle g_{t}^{\ast}$ $\displaystyle\in\mathop{\rm
arg\leavevmode\nobreak\ max}\limits_{g_{t}\in{\cal
G}_{t}}E_{P}\left[Q_{t}\left(H_{t},g_{t}\right)\right],$ (4)

where

$\displaystyle Q_{t}\left(h_{t},g_{t}\right)$ $\displaystyle\equiv
E_{P}\left[\gamma_{t}Y_{t}+\max_{g_{t+1}\in{\cal
G}_{t+1}}Q_{t+1}\left(H_{t+1},g_{t+1}\right)\mid
H_{t}=h_{t},D_{t}=g_{t}\left(h_{t}\right)\right]$
$\displaystyle=E_{P}\left[\gamma_{t}Y_{t}+Q_{t+1}\left(H_{t+1},g_{t+1}^{\ast}\right)\mid
H_{t}=h_{t},D_{t}=g_{t}\left(h_{t}\right)\right].$

The function $Q_{t}\left(h_{t},g_{t}\right)$ represents the expected welfare
that realizes when the history is $h_{t}$, $g_{t}$ is followed at stage $t$,
and the optimal treatment rules are followed at the subsequent stages. Under
Assumptions 2.1 and 3.1, $g_{t}^{\ast}$ corresponds to the first-best
treatment rule $g_{t,FB}^{\ast}$ for $t=2,\ldots,T-1$, and $g_{1}^{\ast}$ is
the optimal treatment rule that maximizes
$W(g_{1},g_{2,FB}^{\ast},\cdots,g_{T,FB}^{\ast})$ over
$g_{1}\in\mathcal{G}_{1}$.

This procedure obtains the optimal treatment rule at each stage by solving the
welfare maximization problem given that the optimal treatment rules at the
subsequent stages are known and followed. Since $g_{t}^{\ast}$ corresponds to
the first-best treatment rule $g_{t,FB}^{\ast}$ for all $t=2,\ldots,T$ and
$g_{1}^{\ast}$ is also the optimal treatment rule given
$(g_{2}^{\ast},\ldots,g_{T}^{\ast})$, the sequentially identified DTR
$g^{\ast}\equiv(g_{1}^{\ast},\ldots,g_{T}^{\ast})$ corresponds to the solution
of the whole welfare maximization problem (2).

If the first-best treatment rule is not achievable in $\mathcal{G}_{t}$ for
some stage $t\geq 2$, then $g_{s}^{\ast}$ for $s\leq t$ do not necessary
correspond to the optimal treatment rule. We illustrate this problem in the
following remark with a simple example and in simulation study in Section 6.

######  Remark 3.1.

Suppose that $T=3$ and that the data generating process $P$ satisfies the
following:

$\displaystyle E_{P}[Y_{2}(0,0,0)]=0.2,\ E_{P}[Y_{2}(1,0,0)]=0.3,\
E_{P}[Y_{2}(0,1,0)]=0.4,\ E_{P}[Y_{2}(1,1,0)]=0.5;$ $\displaystyle
E_{P}[Y_{2}(0,0,1)]=0,\ E_{P}[Y_{2}(1,0,1)]=0,\ E_{P}[Y_{2}(0,1,1)]=0,\
E_{P}[Y_{2}(1,1,1)]=1;$ $\displaystyle\mbox{$D_{1}$, $D_{2}$, and $D_{3}$ are
independently distributed as $Ber(1/2)$}.$

We suppose $H_{1}=\emptyset$, $H_{2}=(D_{1})$, and $H_{3}=(D_{1},D_{2})$. We
use a class of DTRs
$\mathcal{G}=\mathcal{G}_{1}\times\mathcal{G}_{2}\times\mathcal{G}_{3}$ with
classes of constants $\mathcal{G}_{t}=\\{0,1\\}$ for $t=1,2,3$. The target
welfare to maximize is

$\displaystyle W(g)=E_{P}\left[Y_{3}(D_{1},D_{2},D_{3})\mid
D_{1}=g_{1}(H_{1}),D_{2}=g_{2}\left(H_{2}\right),D_{3}=g_{3}\left(H_{3}\right)\right].$

In this setting, the first best DTR
$g_{FB}^{\ast}=(g_{1,FB}^{\ast},g_{2,FB}^{\ast}(d_{1}),g_{3,FB}^{\ast}(d_{1},d_{2}))$
satisfies $g_{1,FB}^{\ast}=1$, $g_{2,FB}^{\ast}(1)=1$, and
$g_{3,FB}^{\ast}(1,1)=1$; however, such a DTR is not contained by
$\mathcal{G}$. The optimal DTR over $\mathcal{G}$ is
$g_{opt}^{\ast}=(g_{opt,1}^{\ast},g_{opt,2}^{\ast},g_{opt,3}^{\ast})=(1,1,1)$
and leads to $W(g_{opt}^{\ast})=1$.

We next consider to solve the population welfare maximization problem by the
backward induction approach. Firstly, solving (3) with $T=3$ leads to
$g_{3}^{\ast}=0$. Second, given $g_{3}^{\ast}=0$, solving (4) with $t=2$ leads
to $g_{2}^{\ast}=1$. Third, given $g_{3}^{\ast}=0$ and $g_{2}^{\ast}=1$,
solving (4) with $t=1$ leads to $g_{1}^{\ast}=1$. Hence the backward induction
solution is $g^{\ast}=(1,1,0)$ which differs from the optimal solution
$g_{opt}^{\ast}$ and leads to a lower welfare 0.5.

The above example implies that when the first best rule is not feasible in
$\mathcal{G}_{t}$ ($t\geq 2$), the backward induction solution $g_{t}^{\ast}$
is subject to the data generating process from an experiment. This data
generating process is different from data generating processes that arise when
the treatment assignments except for stage $t$ follow the optimal treatment
rules. This discrepancy causes the suboptimality of the backward induction
approach. When the first best rule is feasible in $\mathcal{G}_{t}$ for each
$t\geq 2$, the backward induction solution $g_{t}^{\ast}$ can be the optimal
rule irrespective of the data generating process from an experiment, because
the first best rule leads to the best treatment assignment for any history
information.

Given the propensity scores
$\left\\{e_{t}\left(D_{t},H_{t}\right)\right\\}_{t=1}^{T}$ and under
Assumption 2.1, $E_{P}\left[Q_{t}\left(H_{t},g_{t}\right)\right]$ can be
written equivalently as

$\displaystyle E_{P}\left[Q_{t}\left(H_{t},g_{t}\right)\right]$
$\displaystyle=E_{P}\left[q_{t}\left(Z,g_{t};g_{t+1}^{\ast},\ldots,g_{T}^{\ast}\right)\right],$

where

$\displaystyle
q_{t}\left(Z,g_{t};g_{t+1},\ldots,g_{T}\right)\equiv\sum_{s=t}^{T}\left\\{\frac{\left(\prod_{\ell=t}^{s}1\left\\{g_{\ell}\left(H_{\ell}\right)=D_{\ell}\right\\}\right)\gamma_{s}Y_{s}}{\prod_{\ell=t}^{s}e_{\ell}\left(D_{\ell},H_{\ell}\right)}\right\\}.$

Hence, the objective function $E_{P}[Q_{t}(H_{t},g_{t})]$ is expressible in
terms of the observables.

Using the propensity score weighting, the first estimation method we propose
is based on the empirical analogue of the above backward induction procedure.
We call this method the Backward DEWM method. The Backward DEWM method first
estimates $g_{T}^{\ast}$ by

$\displaystyle\hat{g}_{T}^{B}$ $\displaystyle\in\mathop{\rm
arg\leavevmode\nobreak\ max}\limits_{g_{T}\in{\cal
G}_{T}}\frac{1}{n}\sum_{i=1}^{n}q_{T}\left(Z_{i},g_{T}\right).$

Then, recursively, from $t=T-1$ to $1$, $g_{t}^{\ast}$ is estimated by

$\displaystyle\hat{g}_{t}^{B}$ $\displaystyle\in\mathop{\rm
arg\leavevmode\nobreak\ max}\limits_{g_{t}\in{\cal
G}_{t}}\frac{1}{n}\sum_{i=1}^{n}q_{t}\left(Z_{i},g_{t};\hat{g}_{t+1}^{B},\ldots,\hat{g}_{T}^{B}\right).$
(5)

We denote by
$\hat{g}^{B}\equiv\left(\hat{g}_{1}^{B},\ldots,\hat{g}_{T}^{B}\right)$ the DTR
obtained from this procedure.

######  Remark 3.2.

The Q-learning method is also based on the idea of backward induction (Murphy
(2005); Moodie et al. (2012)). Q-learning uses regression models to estimate
the Q-functions that correspond to $Q_{t}\left(h_{t},g_{t}\right)$ for
$t=1,\ldots,T$, and then predicts the optimal DTR from the estimated
Q-functions. Q-learning specifies the Q-functions but not the class of
feasible DTRs. Linear models are typically used to approximate the
Q-functions.

####  3.2 Simultaneous Dynamic Empirical Welfare Maximization

The second approach is a sample analogue of the whole welfare maximization
problem (2). We call the proposed method Simultaneous DEWM method as it
simultaneously estimates the optimal treatment rules across all stages. Let
$\underline{g}_{t}\equiv(g_{1},\ldots,g_{t})\in\mathcal{G}_{1}\times\cdots\times\mathcal{G}_{t}$
be the vector of treatment rules up to stage $t$. The Simultaneous DEWM method
estimates the optimal DTR though the maximization of the sample analogue of
(1):

$\displaystyle\left(\hat{g}_{1}^{S},\dots,\hat{g}_{T}^{S}\right)$
$\displaystyle\in\mathop{\rm arg\leavevmode\nobreak\
max}\limits_{g\in{\cal{\cal
G}}}\sum_{t=1}^{T}\left[\frac{1}{n}\sum_{i=1}^{n}w_{t}^{S}(Z_{i},\text{$\underline{g}$}_{t})\right],$
(6)

where

$\displaystyle w_{t}^{S}(Z_{i},\text{$\underline{g}$}_{t})$
$\displaystyle\equiv\frac{\left(\prod_{s=1}^{t}1\left\\{g_{s}\left(H_{is}\right)=D_{is}\right\\}\right)\gamma_{t}Y_{it}}{\prod_{s=1}^{t}e_{s}\left(D_{is},H_{is}\right)}.$

In the maximization problem (6),
$n^{-1}\sum_{i=1}^{n}w_{t}^{S}(Z_{i},\text{$\underline{g}$}_{t})$ corresponds
to the sample analogue of the $t$-th term in (1). We denote by
$\hat{g}^{S}\equiv\left(\hat{g}_{1}^{S},\ldots,\hat{g}_{T}^{S}\right)$ the DTR
obtained from this procedure. Theorem 3.4 below shows that this method can
consistently estimate the optimal DTR on $\mathcal{G}$ even when the class of
treatment rule $\mathcal{G}_{t}$ does not contain the first-best treatment
rule for some $t$ (i.e., Assumption 3.1 does not hold).

######  Remark 3.3.

When $\mathcal{G}_{t}$ ($t=1,\ldots,T$) are classes of the linear eligibility
scores, the optimization problems (5) for the Backward DEWM and (6) for the
Simultaneous DEWM can be formulated as Mixed Integer Linear Programming (MILP)
problems. See Appendix B for details.

####  3.3 Statistical Properties

As in much of the literature that follows Manski (2004), we evaluate the
statistical properties of the two DEWM methods in terms of the maximum average
welfare-regret that is the maximum average welfare loss relative to the
maximum feasible welfare $W_{\mathcal{G}}^{\ast}$. Following Kitagawa and
Tetenov (2018), we focus on the non-asymptotic upper bounds of the worst-case
average welfare-regret, $\sup_{P\in{\cal
P}\left(M,\kappa,\mathcal{G}\right)}E_{P^{n}}\left[W_{{\cal
G}}^{\ast}-W\left(\hat{g}\right)\right]$, for the Backward DEWM method
($\hat{g}=\hat{g}^{B}$) and the Simultaneous DEWM method
($\hat{g}=\hat{g}^{S}$), where ${\cal P}\left(M,\kappa,\mathcal{G}\right)$ is
a class of distributions of
$\left(D_{t},\left\\{Y_{t}\left(\text{$\underline{d}$}_{t}\right)\right\\}_{\text{$\underline{d}$}_{t}\in\left\\{0,1\right\\}^{t}},X_{t}\right)_{t=1}^{T}$
that satisfy Assumptions 2.1, 2.2, and 2.4 with
$M\equiv\left(M_{1},\ldots,M_{T}\right)^{\prime}$,
$\kappa\equiv\left(\kappa_{1},\ldots,\kappa_{T}\right)^{\prime}$, and a fixed
$\mathcal{G}$.

The following theorem provides a finite-sample upper bound on the worst-case
average welfare-regret and shows its dependence on the sample size $n$, the
VC-dimension of $\mathcal{G}_{t}$ for each $t$, and the number of stages $T$.

######  Theorem 3.4.

Suppose that Assumptions 2.1, 2.2, and 2.4 hold for any distribution
$P\in{\cal P}\left(M,\kappa,\mathcal{G}\right)$ and Assumption 2.3 holds for
$\mathcal{G}$.
(i) For the Simultaneous DEWM method, there holds

$\displaystyle\sup_{P\in{\cal
P}\left(M,\kappa,\mathcal{G}\right)}E_{P^{n}}\left[W_{{\cal
G}}^{\ast}-W\left(\hat{g}^{S}\right)\right]$ $\displaystyle\leq
C\sum_{t=1}^{T}\left\\{\frac{\gamma_{t}M_{t}}{\prod_{s=1}^{t}\kappa_{s}}\sqrt{\frac{\sum_{s=1}^{t}v_{s}}{n}}\right\\},$

where $C$ is some universal constant.
(ii) Suppose, in addition, that Assumption 3.1 holds for a pair of
$\mathcal{G}$ and any $P\in{\cal P}\left(M,\kappa,\mathcal{G}\right)$. Then,
for the Backward DEWM method, there holds

$\displaystyle\sup_{P\in{\cal
P}\left(M,\kappa,\mathcal{G}\right)}E_{P^{n}}\left[W_{{\cal
G}}^{\ast}-W\left(\hat{g}^{B}\right)\right]$ $\displaystyle\leq
C\sum_{t=1}^{T}\left\\{\frac{\gamma_{t}M_{t}}{\prod_{s=1}^{t}\kappa_{s}}\sqrt{\frac{\sum_{s=1}^{t}v_{s}}{n}}\right\\}$
$\displaystyle+C\sum_{t=2}^{T}\frac{2^{t-2}}{\prod_{s=1}^{t-1}\kappa_{s}}\left(\sum_{s=t}^{T}\left\\{\frac{\gamma_{s}M_{s}}{\prod_{\ell=t}^{s}\kappa_{\ell}}\sqrt{\frac{\sum_{\ell=t}^{s}v_{\ell}}{n}}\right\\}\right),$

where $C$ is the same universal constant.

###### Proof.

See Appendix A.1. ∎

This theorem shows that the convergence rates of the worst-case average
welfare-regrets of the two methods are not slower than $n^{-1/2}$. The upper
bounds increase with the VC-dimension of $\mathcal{G}_{t}$, implying that as
the candidate treatment rules become more complex in terms of VC-dimension,
the estimated DTR tends to overfit the data (the distribution of welfare-
regret becomes more dispersed). The upper bound corresponding to the the
Backward DEWM method is greater than the upper bound corresponding to the
Simultaneous DEWM method, though neither bound is necessarily sharp.
Technically, the difference between these upper bounds arises because the
optimization problem (5) in each step of the Backward DEWM method depends on
the previous estimators $\hat{g}_{t+1}^{B},\ldots,\hat{g}_{T}^{B}$, which
leads to additional uncertainty in the estimation.

The next theorem shows a lower bound on the maximum average welfare-regret for
any data-driven DTR. To present the theorem formally, let $v_{s:t}$, for
$s\leq t$, denote the VC-dimension of the following class of indicator
functions on $\mathcal{Z}$:

$\displaystyle\left\\{f(z)=1\left\\{g_{s}\left(h_{s}\right)=d_{s},\ldots,g_{t}\left(h_{t}\right)=d_{t}\right\\}:\left(g_{s},\ldots,g_{t}\right)\in\mathcal{G}_{s}\times\cdots\times\mathcal{G}_{t}\right\\}.$

Note that $v_{s:t}\leq\sum_{\ell=s}^{t}v_{\ell}$ holds (see Lemma A.3 in
Appendix A).

######  Theorem 3.5.

Suppose that Assumptions 2.1, 2.2, and 2.4 hold for any distribution
$P\in{\cal P}\left(M,\kappa,\mathcal{G}\right)$ and Assumption 2.3 holds for
${\cal G}$. Then, for any DTR $\hat{g}\in\mathcal{G}$ as a function of
$\left(Z_{1},\ldots,Z_{n}\right)$, there holds

$\displaystyle\sup_{P\in{\cal
P}\left(M,\kappa,\mathcal{G}\right)}E_{P^{n}}\left[W_{{\cal
G}}^{\ast}-W\left(\hat{g}\right)\right]$
$\displaystyle\geq\frac{1}{2}\exp\left(-4\right)\max_{t\in\\{1,\ldots,T\\}}\left\\{\gamma_{t}M_{t}\sqrt{\frac{v_{1:t}}{n}}\right\\}$

for all $n\geq 16v_{1:T}$. This result holds irrespective of whether or not
Assumption 3.1 additionally holds for a pair of $\mathcal{G}$ and any
$P\in\mathcal{P}(M,\kappa,\mathcal{G})$.

###### Proof.

See Appendix A.1. ∎

This theorem, along with Theorem 3.4, shows that both $\hat{g}^{S}$ and
$\hat{g}^{B}$ are minimax rate optimal over the class of data generating
processes $\mathcal{P}\left(M,\kappa,\mathcal{G}\right)$. Optimality is in the
sense that the convergence rates of the upper bounds of the worst-case average
welfare-regrets in Theorem 3.4 agree with the convergence rate of the
universal lower bound with respect to the sample size $n$. The convergence
rate is also optimal with respect to the VC-dimension if the largest VC-
dimension $v_{1:T}$ in Theorem 3.5 corresponds to $\sum_{s=1}^{T}v_{s}$ in
Theorem 3.4. In Theorem 3.5, the maximum of $\gamma_{t}M_{t}\sqrt{v_{1:t}/n}$
over $t=1,\ldots,T$, rather than its summation over $t=1,\ldots,T$, appears in
the lower bound. This is due to the simplicity of the derivation of the lower
bound in the proof.

######  Remark 3.6.

The finite sample optimization problems (5) and (6) are not invariant to
adding a constant. This can be problematic in applied work because the
researcher can change the estimated DTR by manipulating the outcome variables
(as pointed out by Kitagawa and Tetenov (2018)). Let
$Y_{t}^{dm}=Y_{t}-E_{n}\left[Y_{t}\right]$, for $t=1,\ldots,T$, be the
outcomes less their sample means. The demeaned outcomes $Y_{t}^{dm}$ are
invariant to adding a constant to the original outcomes $Y_{t}$. Following
Kitagawa and Tetenov (2018), we suggest using the demeaned outcomes
$Y_{t}^{dm}$ instead of the original ones $Y_{t}$ in the optimization problems
(5) and (6). The same suggestion is also applied to all estimation methods
given later.

###  4 Budget/Capacity Constraints

We consider budget/capacity constraints that restrict the proportion of the
population to receive treatment at each stage. In the dynamic treatment
policy, the budget/capacity constraints may be imposed intertemporally,
meaning that the constraints are imposed on treatment rules across multiple
stages. The policy-maker faces an intertemporal budget/capacity constraint if
she has a budget that can be expended across multiple stages or limited amount
of treatment that can be allocated across multiple stages. These constraints
are formalized as follows.

We suppose that the policy-maker faces the following $B$ constraints:

$\displaystyle\sum_{t=1}^{T}K_{tb}E_{P}\left[g_{t}\left(H_{t}\right)\mid
D_{1}=g_{1}\left(H_{1}\right),\ldots,D_{t-1}=g_{t-1}\left(H_{t-1}\right)\right]$
$\displaystyle\leq C_{b}\ \mbox{for }b=1,\ldots,B,$ (7)

where $K_{tb}\in\left[0,1\right]$ and $C_{b}\geq 0$. As a scale normalization,
we assume $\sum_{t=1}^{T}K_{tb}=1$ for all $b$. The weights
$K_{1b},\ldots,K_{Tb}$ represent the relative costs of treatments across
stages, and $C_{b}$ represents the total budget or capacity. If at least two
of $K_{1b},\cdots,K_{Tb}$ take non-zero values, the $b$-th constraint is an
intertemporal budget/capacity constraint (otherwise, the $b$-th constraint is
an temporal budget/capacity constraint).

We suppose that the policy-maker wants to maximize the welfare under the
budget/capacity constraints (7) and over the class of feasible DTRs
$\mathcal{G}$. Then the population welfare maximization problem is formulated
as

$\displaystyle W_{{\cal G}}^{\ast}=\max_{g\in{\cal G}}W\left(g\right)$ (8)
s.t. $\displaystyle\sum_{t=1}^{T}K_{tb}E_{P}\left[g_{t}\left(H_{t}\right)\mid
D_{1}=g_{1}\left(H_{1}\right),\ldots,D_{t-1}=g_{t-1}\left(H_{t-1}\right)\right]\leq
C_{b}\ \mbox{for }b=1,\ldots,B.$

The goal of the analysis is then to choose a DTR from ${\cal G}$ that
maximizes the welfare $W(\cdot)$ subject to the budget/capacity constraints
(7).

To this end, we incorporate the sample analogues of the budget/capacity
constraints (7) into the Simultaneous DEWM. The Simultaneous DEWM method with
the budget/capacity constraints solves the following problem:

$\displaystyle\left(\hat{g}_{1}^{S},\dots,\hat{g}_{T}^{S}\right)\in\mathop{\rm
arg\leavevmode\nobreak\ max}\limits_{g\in{\cal{\cal
G}}}\frac{1}{n}\sum_{i=1}^{n}\sum_{t=1}^{T}w_{t}^{S}\left(Z_{i},\underline{g}_{t}\right)$
(9) s.t.
$\displaystyle\sum_{t=1}^{T}K_{tb}\hat{E}\left[g_{t}\left(H_{t}\right)\mid
D_{1}=g_{1}\left(H_{1}\right),\ldots,D_{t-1}=g_{t-1}\left(H_{t-1}\right)\right]\leq
C_{b}+\alpha_{n}$ (10) $\displaystyle\mbox{for }b=1,\ldots,B,$

where

$\displaystyle\hat{E}\left[g_{t}\left(H_{t}\right)\mid
D_{1}=g_{1}\left(H_{1}\right),\ldots,D_{t-1}=g_{t-1}\left(H_{t-1}\right)\right]\equiv\frac{\sum_{i=1}^{n}\left(\prod_{s=1}^{t-1}1\left\\{D_{is}=g_{s}\left(H_{is}\right)\right\\}\right)g_{t}\left(H_{it}\right)}{\sum_{i=1}^{n}\left(\prod_{s=1}^{t-1}1\left\\{D_{is}=g_{s}\left(H_{is}\right)\right\\}\right)}.$

The inequality constraints (10) are empirical budget/capacity constraints, in
which $\alpha_{n}$ is a tuning parameter that takes a non-negative value,
depends on the sample size $n$, and converges to zero as $n$ becomes large. As
$\alpha_{n}$ becomes small, the empirical budget/capacity constraints become
tighter. A sufficiently large value of $\alpha_{n}$ ensures that the optimal
DTR (a solution of (8)) is attainable under the sample budget/capacity
constraints with high probability. When $\mathcal{G}_{t}$ is the class of
linear eligibility scores for all $t=1,\ldots,T$, the optimization problem (9)
can be also formulated as a MILP problem (see Appendix B).

The following theorem shows the finite-sample properties of the worst-case
welfare-regret of the modified Simultaneous DEWM method as well as the excess
implementation costs of the estimated DTR over the actual budget/capacity.

######  Theorem 4.1.

Suppose that Assumptions 2.1, 2.2, and 2.4 hold for any distribution
$P\in{\cal P}\left(M,\kappa,\mathcal{G}\right)$ and Assumption 2.3 holds for
${\cal{G}}$. Let $W_{{\cal G}}^{\ast}$ be defined in (8) and $\hat{g}^{S}$ be
a solution of (9) subject to (10). Let $\delta$ be any value in $(0,1)$ and
$C$ be the same constant as in Theorem 3.4.
(i) If $\alpha_{n}\geq\sqrt{\log\left(6B/\delta\right)/\left(2n\right)}$, then
the following holds for any distribution
$P\in\mathcal{P}(M,\kappa,\mathcal{G})$ with probability at least $1-\delta$:

$\displaystyle\left|W_{{\cal
G}}^{\ast}-W\left(\hat{g}^{S}\right)\right|\leq\frac{1}{\sqrt{n}}\sum_{t=1}^{T}\left[\left(\frac{\gamma_{t}M_{t}}{\prod_{s=1}^{t}\kappa_{s}}\right)\left(4C\sqrt{\sum_{s=1}^{t}v_{s}}+\sqrt{8\log\left(6/\delta\right)}\right)\right]$

and, for any $b\in\\{1,\ldots,B\\}$,

$\displaystyle\sum_{t=1}^{T}K_{tb}E_{P}\left[\hat{g}_{t}^{S}\left(H_{t}\right)\mid
D_{1}=\hat{g}_{1}^{S}\left(H_{1}\right),\ldots,D_{t-1}=\hat{g}_{t-1}^{S}\left(H_{t-1}\right)\right]-C_{b}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\sqrt{n}}\sum_{t=1}^{T}\left[K_{tb}\left(2C\sqrt{\sum_{s=1}^{t}v_{s}}+\sqrt{2\log\left(2B/\delta\right)}\right)\right]+\alpha_{n}.$
(11)

(ii) Let $k_{n}=\sqrt{\log(6B/\delta)/(2n)}$, and
$\tilde{W}_{\mathcal{G},k_{n}}^{\ast}$ be the optimal value of the
optimization problem (8) with $C_{b}$ replaced by $C_{b}-k_{n}$. If
$\alpha_{n}=0$, the following holds for any distribution
$P\in\mathcal{P}(M,\kappa,\mathcal{G})$ with probability at least $1-\delta$:

$\displaystyle\left|W_{{\cal G}}^{\ast}-W\left(\hat{g}^{S}\right)\right|$
$\displaystyle\leq\left(W_{{\cal
G}}^{\ast}-\tilde{W}_{\mathcal{G},k_{n}}^{\ast}\right)$
$\displaystyle+\frac{1}{\sqrt{n}}\sum_{t=1}^{T}\left[\left(\frac{\gamma_{t}M_{t}}{\prod_{s=1}^{t}\kappa_{s}}\right)\left(4C\sqrt{\sum_{s=1}^{t}v_{s}}+\sqrt{8\log\left(6/\delta\right)}\right)\right]$
(12)

and, for any $b\in\\{1,\ldots,B\\}$,

$\displaystyle\sum_{t=1}^{T}K_{tb}E_{P}\left[\hat{g}_{t}^{S}\left(H_{t}\right)\mid
D_{1}=\hat{g}_{1}^{S}\left(H_{1}\right),\ldots,D_{t-1}=\hat{g}_{t-1}^{S}\left(H_{t-1}\right)\right]-C_{b}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\sqrt{n}}\sum_{t=1}^{T}\left[K_{tb}\left(2C\sqrt{\sum_{s=1}^{t}v_{s}}+\sqrt{2\log\left(2B/\delta\right)}\right)\right].$
(13)

###### Proof.

(ii) follows immediately from (i) by noting that
$|W_{\mathcal{G}}^{\ast}-W(\hat{g}^{S})|\leq(W_{\mathcal{G}}^{\ast}-\tilde{W}_{\mathcal{G},k_{n}}^{\ast})+|\tilde{W}_{\mathcal{G},k_{n}}^{\ast}-W(\hat{g}^{S})|$
and that
$|\tilde{W}_{\mathcal{G},k_{n}}^{\ast}-W(\hat{g}^{S})|\leq|W_{\mathcal{G}}^{\ast}-W(\hat{g}^{S})|$.
For the proof of (i), see Appendix A.2. ∎

The left-hand sides of (11) and (13) represent the excess implementation costs
of the estimated DTR over the $b$-th budget/capacity. The theorem implies that
when the sample size is large, the worst-case welfare-regret and the worst-
case budget excess is likely to be small. They diminish at the rate of
$n^{-1/2}$. Note that, in contrast to Theorem 3.4, this theorem evaluates
actual values of the welfare-regret and the budget excess rather than the
expected values of them. We do this because the actual value of the budget
excess should be practically of greater concern than its expected value. The
result also guides how to choose the sample size $n$ in a way that the budget
excess is constrained to a certain level with a particular probability. When
we set $\alpha_{n}=0$, the upper bound on the budget excess in (13) no longer
depends on $\alpha_{n}$, while the upper bound on the welfare-regret in (12)
depends on $W_{\mathcal{G}}^{\ast}-\tilde{W}_{\mathcal{G},k_{n}}^{\ast}$, the
difference in the maximum feasible welfare under the budgets $C_{b}$ and
$C_{b}-k_{n}$ ($b=1,\ldots,B$), for which a remark is given below.

######  Remark 4.2.

Whether $W_{\mathcal{G}}^{\ast}-\tilde{W}_{\mathcal{G},k_{n}}^{\ast}$ in (12)
converges to zero or not depends on the properties of the class of DTR
$\mathcal{G}$ and distribution $P$. Suppose for simplicity that
$K_{1b}=\cdots=K_{Tb}=1$ for all $b=1,\ldots,B$. If the difference
$W_{\mathcal{G}}^{\ast}-\tilde{W}_{\mathcal{G},k_{n}}^{\ast}$ is not greater
than the product of the budget difference $k_{n}$ and the maximum feasible
value of unit-welfare loss
$\sum_{t=1}^{T}\left(\gamma_{t}M_{t}/\prod_{s=1}^{t}\kappa_{s}\right)$, i.e.,

$\displaystyle
W_{\mathcal{G}}^{\ast}-\tilde{W}_{\mathcal{G},k_{n}}^{\ast}\leq\sum_{t=1}^{T}\left(\gamma_{t}M_{t}/\prod_{s=1}^{t}\kappa_{s}\right)\cdot
k_{n},$

then $W_{\mathcal{G}}^{\ast}-\tilde{W}_{\mathcal{G},k_{n}}^{\ast}$ has an
$n^{-1/2}$-upper bound because $k_{n}$ converges to zero at rate $n^{-1/2}$.
However, not all pairs $(P,\mathcal{G})$ let
$W_{\mathcal{G}}^{\ast}-\tilde{W}_{\mathcal{G},k_{n}}^{\ast}$ converge to
zero. For example, when $\mathcal{G}$ consists of a finite number of
functions, the maximum welfare subject to budget constraints may not be
continuous with respect to the budget $C_{b}$ under some $P$, and
$W_{\mathcal{G}}^{\ast}-\tilde{W}_{\mathcal{G},k_{n}}^{\ast}$ may not converge
to zero.

###  5 Estimated Propensity Score

In this section, we consider the case where the propensity scores are not
known and must be estimated from data. This case occurs when the analyst has
access to data from an observational study rather than an experimental study.
We modify the Backward and Simultaneous DEWM methods to use the estimated
propensity scores based on the e-hybrid EWM rule proposed by Kitagawa and
Tetenov (2018). For the static case, Athey and Wager (2021) argue that
estimating the welfare objective using the doubly robust estimator can improve
the convergence rate of the welfare-regret relative to the e-hybrid EWM rule.
Nie et al. (2020) extend this approach to the problem of deciding when to
start/stop a consecutive treatment assignment.444Nie et al. (2020) also
discuss the difficulty in extending this approach to the more general dynamic
treatment setting considered in this paper. The difficulty comes from the fact
that the Q-function, $Q_{t}(h_{t},g_{t})$, depends on the treatment rules not
only of the corresponding stage but also of future stages.

Let $\hat{e}_{t}\left(d_{t},h_{t}\right)$ be an estimated version of the
propensity score $e_{t}\left(d_{t},h_{t}\right)$. For the estimators of the
propensity scores, we suppose that the following high-level assumption holds.

######  Assumption 5.1.

(i) Define

$\displaystyle\tau_{t}\left(\underline{d}_{t},H_{t}\right)\equiv\left\\{\frac{\left(\prod_{s=1}^{t}1\left\\{D_{s}=d_{s}\right\\}\right)\gamma_{t}Y_{t}}{\prod_{s=1}^{t}e_{s}\left(d_{s},H_{s}\right)}\right\\}\mbox{
and }\
\hat{\tau}_{t}\left(\underline{d}_{t},H_{t}\right)\equiv\left\\{\frac{\left(\prod_{s=1}^{t}1\left\\{D_{s}=d_{s}\right\\}\right)\gamma_{t}Y_{t}}{\prod_{s=1}^{t}\hat{e}_{s}\left(d_{s},H_{s}\right)}\right\\},$

where $\hat{e}_{t}\left(d_{t},H_{t}\right)$ is an estimated propensity score
taking a value in $\left(0,1\right)$. For a class of data generating processes
${\cal P}_{e}$, there exists a sequence $\phi_{n}\rightarrow\infty$ such that

$\displaystyle\underset{P\in{\cal
P}_{e}}{\sup}\sup_{t\in\left\\{1,\ldots,T\right\\}}\sum_{\text{$\underline{d}$}_{t}\in\left\\{0,1\right\\}^{t}}E_{P^{n}}\left[\frac{1}{n}\sum_{i=1}^{n}\left|\hat{\tau}_{t}\left(\text{$\underline{d}$}_{t},H_{it}\right)-\tau_{t}\left(\text{$\underline{d}$}_{t},H_{it}\right)\right|\right]=O\left(\phi_{n}^{-1}\right).$

(ii) Define

$\displaystyle\eta_{t}\left(\text{$\underline{d}$}_{t:T},H_{T}\right)\equiv$
$\displaystyle\sum_{s=t}^{T}\left\\{\frac{\left(\prod_{\ell=t}^{s}1\left\\{D_{\ell}=d_{\ell}\right\\}\right)\gamma_{s}Y_{s}}{\prod_{\ell=t}^{s}e_{\ell}\left(d_{\ell},H_{\ell}\right)}\right\\},$
$\displaystyle\hat{\eta}_{t}\left(\text{$\underline{d}$}_{t:T},H_{T}\right)\equiv$
$\displaystyle\sum_{s=t}^{T}\left\\{\frac{\left(\prod_{\ell=t}^{s}1\left\\{D_{\ell}=d_{\ell}\right\\}\right)\gamma_{s}Y_{s}}{\prod_{\ell=t}^{s}\hat{e}_{\ell}\left(d_{\ell},H_{\ell}\right)}\right\\}.$

For a class of data generating processes $\widetilde{\mathcal{P}}_{e}$, there
exists a sequence $\psi_{n}\rightarrow\infty$ such that

$\displaystyle\underset{P\in\widetilde{\mathcal{P}}_{e}}{\sup}\sup_{t\in\left\\{1,\ldots,T\right\\}}\sum_{\text{$\underline{d}$}_{t:T}\in\left\\{0,1\right\\}^{T-t+1}}E_{P^{n}}\left[\frac{1}{n}\sum_{i=1}^{n}\left|\hat{\eta}_{t}\left(\text{$\underline{d}$}_{t:T},H_{iT}\right)-\eta_{t}\left(\text{$\underline{d}$}_{t:T},H_{iT}\right)\right|\right]=O\left(\psi_{n}^{-1}\right).$

Note that

$\displaystyle
E_{P}\left[\tau_{t}\left(\text{$\underline{d}$}_{t},H_{t}\right)\right]$
$\displaystyle=E_{P}\left[\gamma_{t}Y_{t}(\underline{d}_{t})\right],$
$\displaystyle
E_{P}\left[\eta_{t}\left(\text{$\underline{d}$}_{t:T},H_{T}\right)\right]$
$\displaystyle=E_{P}\left[\sum_{s=t}^{T}\gamma_{s}Y_{s}(\underline{d}_{s})\right]$

hold under Assumption 2.1 and that
$n^{-1}\sum_{i=1}^{n}\hat{\tau}_{t}\left(\text{$\underline{d}$}_{t}\right)$
and
$n^{-1}\sum_{i=1}^{n}\hat{\eta}_{t}\left(\text{$\underline{d}$}_{t:T}\right)$
are estimators of these, respectively. We do not explore lower-level
conditions that satisfy the conditions in Assumption 5.1. When the propensity
scores are parametrically specified, they are estimated at rate $n^{-1/2}$.

When the estimated propensity scores are used, the Backward DEWM method solves
the following problem, recursively, from $t=T$ to $1$:

$\displaystyle\hat{g}_{t,e}^{B}$ $\displaystyle\in\mathop{\rm
arg\leavevmode\nobreak\ max}\limits_{g_{t}\in{\cal
G}_{t}}\frac{1}{n}\sum_{i=1}^{n}\hat{q}_{t}\left(H_{it},g_{t};\hat{g}_{t+1,e}^{B},\ldots,\hat{g}_{T,e}^{B}\right),$

where

$\displaystyle\hat{q}_{t}\left(h_{t},g_{t};g_{t+1},\ldots,g_{T}\right)\equiv\sum_{s=t}^{T}\left\\{\frac{\left(\prod_{\ell=t}^{s}1\left\\{g_{\ell}\left(H_{\ell}\right)=D_{\ell}\right\\}\right)\cdot\gamma_{s}Y_{s}}{\prod_{\ell=t}^{s}\hat{e}_{\ell}\left(D_{\ell},H_{\ell}\right)}\right\\}.$

The difference between $\hat{q}_{t}\left(\cdot\right)$ and
$q_{t}\left(\cdot\right)$ given in Section 3.1 is that the estimated
propensity scores are used instead of the true ones. We denote by
$\hat{g}_{e}^{B}\equiv\left(\hat{g}_{1,e}^{B},\ldots,\hat{g}_{T,e}^{B}\right)$
the DTR obtained by this procedure.

Similarly, the Simultaneous DEWM method solves the following problem:

$\displaystyle\left(\hat{g}_{1,e}^{S},\dots,\hat{g}_{T,e}^{S}\right)$
$\displaystyle\in\mathop{\rm arg\leavevmode\nobreak\
max}\limits_{g\in{\cal{\cal
G}}}\sum_{t=1}^{T}\left[\frac{1}{n}\sum_{i=1}^{n}\hat{w}_{t}^{S}(Z_{i},\text{$\underline{g}$}_{t})\right],$

where

$\displaystyle\hat{w}_{t}^{S}(Z_{i},\text{$\underline{g}$}_{t})$
$\displaystyle\equiv\frac{\left(\prod_{s=1}^{t}1\left\\{g_{s}\left(H_{is}\right)=D_{is}\right\\}\right)\cdot\gamma_{t}Y_{it}}{\prod_{s=1}^{t}\hat{e}_{s}\left(D_{is},H_{is}\right)}$

uses the estimated propensity scores instead of the true ones. We denote the
estimated DTR by
$\hat{g}_{e}^{S}\equiv\left(\hat{g}_{1,e}^{S},\ldots,\hat{g}_{T,e}^{S}\right)$.

The following theorem shows the uniform convergence rate bounds on the worst-
case average welfare-regret for the two estimation methods.

######  Theorem 5.1.

Suppose that Assumptions 2.1, 2.2, and 2.4 hold for any distribution
$P\in{\cal P}\left(M,\kappa,\mathcal{G}\right)$ and that Assumption 2.3 holds
for ${\cal{G}}$.
(i) Suppose further that Assumption 5.1 (i) holds for any distribution
$P\in\mathcal{P}_{e}$. For the Simultaneous DEWM method, there holds

$\displaystyle\sup_{P\in\mathcal{P}_{e}\bigcap{\cal
P}\left(M,\kappa,\mathcal{G}\right)}E_{P^{n}}\left[W_{{\cal
G}}^{\ast}-W\left(\hat{g}_{e}^{S}\right)\right]$ $\displaystyle\leq
C\sum_{t=1}^{T}\left\\{\frac{\gamma_{t}M_{t}}{\prod_{s=1}^{t}\kappa_{s}}\sqrt{\frac{\sum_{s=1}^{t}v_{s}}{n}}\right\\}+O\left(\phi_{n}^{-1}\right),$

where $C$ is the same universal constant as that introduced in Theorem 3.4.
(ii) Suppose further that Assumption 5.1 (ii) holds for any distribution
$P\in\widetilde{\mathcal{P}}_{e}$ and that Assumption 3.1 holds for a pair
$\left(P,{\cal{G}}\right)$ for any $P\in{\cal
P}\left(M,\kappa,\mathcal{G}\right)$. Then, for the Backward DEWM method,
there holds

$\displaystyle\sup_{P\in\widetilde{\mathcal{P}}_{e}\bigcap{\cal
P}\left(M,\kappa,\mathcal{G}\right)}E_{P^{n}}\left[W_{{\cal
G}}^{\ast}-W\left(\hat{g}_{e}^{B}\right)\right]$ $\displaystyle\leq
C\sum_{t=1}^{T}\left\\{\frac{\gamma_{t}M_{t}}{\prod_{s=1}^{t}\kappa_{s}}\sqrt{\frac{\sum_{s=1}^{t}v_{s}}{n}}\right\\}$
$\displaystyle+C\sum_{t=2}^{T}\frac{2^{t-2}}{\prod_{s=1}^{t-1}\kappa_{s}}\left(\sum_{s=t}^{T}\left\\{\frac{\gamma_{s}M_{s}}{\prod_{\ell=t}^{s}\kappa_{\ell}}\sqrt{\frac{\sum_{\ell=t}^{s}v_{\ell}}{n}}\right\\}\right)$
$\displaystyle+O\left(\psi_{n}^{-1}\right).$

###### Proof.

See Appendix A.1. ∎

The theorem implies that the convergence rate of the worst-case average
welfare-regret for each method depends on that of the estimators of the
propensity scores. If parametric estimators are used to estimate the
propensity scores, both methods achieve an $n^{-1/2}$-convergence rate of the
worst-case average welfare-regret.

###  6 Simulation Study

We conduct a simulation study to examine the finite sample performance of the
proposed estimation methods. We compare the performance of the Backward DEWM,
Simultaneous DEWM, and Q-learning.

We consider data generating processes (DGPs) that consist of two stages of
treatment assignment ($D_{1},D_{2}$), associated potential outcomes
$\left(Y_{1}\left(d_{1}\right),Y_{2}\left(d_{1},d_{2}\right)\right)_{\left\\{d_{1},d_{2}\right\\}\in\left\\{0,1\right\\}^{2}}$,
and a covariate $X_{1}$ observed at the first stage. The potential outcomes
are generated as

$\displaystyle Y_{1}\left(d_{1}\right)$
$\displaystyle=\phi_{01}+\phi_{11}X_{1}+\left(\psi_{01}+\psi_{11}X_{1}\right)d_{1}+U_{1},$
$\displaystyle Y_{2}\left(d_{1},d_{2}\right)$
$\displaystyle=\phi_{02}+\phi_{12}Y_{1}\left(d_{1}\right)+\left(\psi_{02}+\psi_{12}d_{1}+\sum_{j=1}^{3}\psi_{j+1,2}\left(Y_{1}\left(d_{1}\right)\right)^{j}\right)d_{2}+U_{2}$

for $(d_{1},d_{2})\in\\{0,1\\}^{2}$. We consider three DGPs labeled DGPs 1-3.
In all the DGPs, $X_{1}$, $U_{1}$, and $U_{2}$ are independently drawn from
$N\left(0,1\right)$; $D_{1}$ and $D_{2}$ are independently drawn from
$Ber\left(1/2\right)$; and
$\left(\phi_{01},\phi_{11},\psi_{01},\psi_{11}\right)=\left(0.5,-1.0,1.0,1.5\right)$
and
$\left(\phi_{02},\phi_{12},\psi_{02},\psi_{12}\right)=\left(0.5,0.5,0.5,0.5\right)$.
Regarding the other parameters, we set
$\left(\psi_{22},\psi_{32},\psi_{42}\right)=\left(0,0,0\right)$ in DGP1,
$\left(\psi_{22},\psi_{32},\psi_{42}\right)=\left(1,0,0\right)$ in DGP2, and
$\left(\psi_{22},\psi_{32},\psi_{42}\right)=\left(0.3,0.3,-0.4\right)$ in
DGP3. We suppose that the target welfare to maximize is

$\displaystyle W(g_{1},g_{2})=E_{P}\left[Y_{2}(D_{1},D_{2})\mid
D_{1}=g_{1}\left(H_{1}\right),D_{2}=g_{2}\left(H_{2}\right)\right].$

Note that the treatment effect of $D_{2}$ does not depends on the past outcome
in DGP1, but it does in DGPs 2 and 3.

For the Backward and Simultaneous DEWM methods, we use a class of DTRs
$\mathcal{G}=\mathcal{G}_{1}\times\mathcal{G}_{2}$ that consists of the
following linear index classes of treatment rules:

$\displaystyle{\cal G}_{1}$
$\displaystyle=\left\\{1\left\\{\left(1,X_{1}\right)^{\prime}\boldsymbol{\beta}_{1}\geq
0\right\\}:\boldsymbol{\beta}_{1}=\left(\beta_{01},\beta_{11}\right)^{\prime}\in\mathbb{R}^{2}\right\\},$
$\displaystyle{\cal G}_{2}$
$\displaystyle=\left\\{1\left\\{\left(1,D_{1},Y_{1}\right)^{\prime}\boldsymbol{\beta}_{2}\geq
0\right\\}:\boldsymbol{\beta}_{2}=\left(\beta_{02},\beta_{12},\beta_{22}\right)^{\prime}\in\mathbb{R}^{3}\right\\}.$

$\mathcal{G}_{1}$ contains the first-best treatment rule only under DGP1;
$\mathcal{G}_{2}$ does under DGPs 1 and 2, but not under DGP3. Thus, the
Backward DEWM method can consistently estimate the optimal DTR under DGPs 1
and 2, but cannot under DGP3.

For Q-learning, we assume that the conditional outcomes are specified as

$\displaystyle E\left[Y_{1}\mid
H_{1},D_{1};\boldsymbol{\alpha}_{1},\boldsymbol{\gamma}_{1}\right]$
$\displaystyle=\alpha_{01}+\alpha_{11}X_{1}+\left(\gamma_{01}+\gamma_{11}X_{1}\right)D_{1},$
$\displaystyle E\left[Y_{2}\mid
H_{2},D_{2};\boldsymbol{\alpha}_{2},\boldsymbol{\gamma}_{2}\right]$
$\displaystyle=\alpha_{02}+\alpha_{12}Y_{1}+\left(\gamma_{02}+\gamma_{12}D_{1}+\gamma_{22}Y_{1}\right)D_{2},$

where
$\boldsymbol{\alpha}_{t}^{\prime}=\left(\alpha_{0t},\alpha_{1t}\right)^{\prime}$
for each $t=1,2$,
$\boldsymbol{\gamma}_{1}^{\prime}=\left(\gamma_{01},\gamma_{11}\right)^{\prime}$,
and
$\boldsymbol{\gamma}_{2}^{\prime}=\left(\gamma_{02},\gamma_{12},\gamma_{22}\right)^{\prime}$.
This specification is correct under DGPs 1 and 2, but is not under DGP3.

Table 1 reports the results of 500 simulations with sample sizes $n=$ 200,
400, and 600, where we calculate the mean and median welfare achieved by each
estimated DTR with 3,000 observations randomly drawn from the same DGP used in
the estimation. The results show that Q-learning performs better than the
Backward and Simultaneous DEWM methods in DGPs 1 and 2 in terms of the
population mean welfare. However, both the Backward and Simultaneous DEWM
methods show better performance than Q-leaning in DGP3, where the outcome
model used by Q-learning is misspecified. In DGPs 1 and 2, the Backward DEWM
method achieve slightly higher mean welfare than the Simultaneous DEWM method,
whereas in DGP3 the Simultaneous DEWM method achieves clearly higher welfare
than the Backward DEWM method.

Table 1: Monte Carlo Simulation Results

|  |  | n=200 |  |  |  | n=400 |  |  |  | n=600 |  |
---|---|---|---|---|---|---|---|---|---|---|---|---|---
| DGP | Mean | Median | SD |  | Mean | Median | SD |  | Mean | Median | SD |
Q-learning | 1 | 2.272 | 2.274 | 0.042 |  | 2.284 | 2.281 | 0.070 |  | 2.274 | 2.271 | 0.069 |
B-DEWM | 1 | 2.049 | 2.147 | 0.269 |  | 2.154 | 2.205 | 0.211 |  | 2.148 | 2.214 | 0.231 |
S-DEWM | 1 | 2.006 | 2.121 | 0.288 |  | 2.148 | 2.211 | 0.245 |  | 2.178 | 2.220 | 0.184 |
Q-learning | 2 | 3.969 | 3.972 | 0.070 |  | 3.975 | 3.971 | 0.122 |  | 3.978 | 3.977 | 0.118 |
B-DEWM | 2 | 3.560 | 3.717 | 0.498 |  | 3.711 | 3.780 | 0.383 |  | 3.694 | 3.788 | 0.426 |
S-DEWM | 2 | 3.497 | 3.666 | 0.526 |  | 3.710 | 3.795 | 0.374 |  | 3.737 | 3.823 | 0.388 |
Q-learning | 3 | 1.637 | 1.625 | 0.107 |  | 1.629 | 1.612 | 0.150 |  | 1.626 | 1.612 | 0.145 |
B-DEWM | 3 | 1.765 | 1.799 | 0.130 |  | 1.785 | 1.799 | 0.126 |  | 1.794 | 1.808 | 0.092 |
S-DEWM | 3 | 1.856 | 1.886 | 0.154 |  | 1.888 | 1.899 | 0.167 |  | 1.906 | 1.924 | 0.128 |

  * •

Note: Mean and Median represent the mean and median of the population mean
welfares achieved by the estimated DTRs across the simulations; SD is the
standard deviation of the population mean welfares across the simulations. The
population mean welfare is calculated using 3,000 observations randomly drawn
from the corresponding DGP. B-DEWM and S-DEWM mean the Backward and
Simultaneous DEWM methods, respectively.

###  7 Empirical Application

We apply the proposed methods to the data from Project STAR (e.g., Krueger
(1999); Gerber et al. (2001); Schanzenbach (2006); Chetty et al. (2011)). In
this experimental project, among 1,346 kindergarten students who did not
belong to small classes, 672 students were randomly allocated to regular-size
classes with a full-time teacher aide and the others were allocated to
regular-size classes without the teacher aide. Upon their progression to grade
1, the enrolled students were randomly shuffled to regular class-size classes
with or without a teacher aide and remained in these allocated classes until
the end of grade 3.

We study how to optimally allocate each student to the two types of classes
(regular-size classes with or without a teacher aide) in grades K and 1
depending on their socioeconomic information and intermediate academic
achievement.555We focus on allocation to a regular-size class with a teacher
aide, rather than allocation to a small-size class, because the allocation of
students to regular-size classes with or without a teacher aide in the
experiment matches the sequential randomization design, but the allocation to
small-size classes in the experiment does not. We suppose that the welfare
that the policy-maker wants to maximize is a population average of a sum of
scores of reading and mathematics tests that students take at the end of grade
1.666We focus on the test score at the end of grade 1 rather than at the end
of grade 3 because we found attending a class with a teacher aide at
kindergarten has little effect on the test score at the end of the grade 3
even when treatment effect heterogeneity is taken into account. We set the
first and second stages ($t=1$ and $2$) to grades K and 1, respectively. The
treatment variable $D_{t}$, for $t=1,2$, takes the value one if the student
belongs to a class with a teacher aide at stage $t$ and zero otherwise. The
intermediate outcome $Y_{1}$ and final outcome $Y_{2}$ are the sum of reading
and mathematics test scores at the ends of grades K and 1, respectively. In
the following estimation, we use demeaned outcomes $Y_{1}^{dm}$ and
$Y_{2}^{dm}$, instead of the original ones, as suggested in Remark 3.6. The
standard deviations (SDs) of $Y_{1}^{dm}$ and $Y_{2}^{dm}$ in the sample are
67.69 and 83.27, respectively. The socioeconomic information we use are
qualification for free or reduced price school lunch and type of school
location (rural or non-rural location). A binary variable $X_{1t}$ indicates
by $1$ that the student is eligible for free or reduced price school lunches
at stage $t$ and by $0$ otherwise; $X_{2t}$ indicates by $1$ that a school
that the student attends at stage $t$ is located in a rural area and by $0$
otherwise. We also have access to student information such as sex and race,
but use of this information in the treatment assignment decision is
discriminatory and prohibited.

As a set of class-allocation policies, we use a set of linear eligibility
scores $\mathcal{G}=\mathcal{G}_{1}\times\mathcal{G}_{2}$ where
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ have the following forms:

$\displaystyle{\cal G}_{1}$
$\displaystyle=\left\\{1\left\\{\beta_{1}x_{11}+\beta_{2}x_{21}\geq
c_{1}\right\\}:\beta_{1}\geq 0,\
\left(\beta_{2},c_{1}\right)^{\prime}\in\mathbb{R}^{2}\right\\},$
$\displaystyle{\cal G}_{2}$
$\displaystyle=\left\\{1\left\\{\gamma_{1}x_{12}+\gamma_{2}x_{22}+\gamma_{3}\left(1-d_{1}\right)y_{1}^{dm}+\gamma_{4}d_{1}y_{1}^{dm}\geq
c_{2}\right\\}:\gamma_{1}\geq 0,\
\left(\gamma_{2},\gamma_{3},\gamma_{4},c_{2}\right)^{\prime}\in\mathbb{R}^{4}\right\\}.$

In the forms of $\mathcal{G}_{1}$ and $\mathcal{G}_{1}$, the signs of the
coefficients of $x_{11}$ and $x_{12}$ are restricted to be non-negative so
that students who are eligible for free or reduced price school lunches are
not less likely to be allocated to a class with a teacher aide (given that the
other information is fixed). The interaction terms
$\left(1-d_{1}\right)y_{1}^{dm}$ and $d_{1}y_{1}^{dm}$ in $\mathcal{G}_{2}$
enables the eligibility score to evaluate the intermediate outcome differently
depending on the class allocation at kindergarten. For a DTR
$g\in\mathcal{G}$, we define the welfare gain of $g$ as
$W\left(g\right)-W\left(0,0\right)$, a welfare increase by allocating students
to each class subject to the DTR $g$ rather than allocating every student to
the regular classes without any additional teacher aide at all stages.
Applying the Backward and Simultaneous DEWM methods, we estimate the optimal
DTR over $\mathcal{G}$ and their welfare gains. The same sample (1,346
observations) is used to estimate both the optimal DTR and welfare gain.

The DTR estimated by the Backward DEWM method is
$\hat{g}^{B}=\left(\hat{g}_{1}^{B},\hat{g}_{2}^{B}\right)$ where

$\displaystyle\hat{g}_{1}^{B}(H_{1})$ $\displaystyle=1,$
$\displaystyle\hat{g}_{2}^{B}(H_{2})$
$\displaystyle=1\left\\{0.702X_{12}-0.056X_{22}-0.073\left(1-D_{1}\right)Y_{1}^{dm}+0.152D_{1}Y_{1}^{dm}\geq-0.016\right\\}.$

The DTR estimated by the Simultaneous DEWM method is
$\hat{g}^{S}=\left(\hat{g}_{1}^{S},\hat{g}_{2}^{S}\right)$ where

$\displaystyle\hat{g}_{1}^{S}(H_{1})$
$\displaystyle=1\left\\{X_{21}=1\right\\},$
$\displaystyle\hat{g}_{2}^{S}(H_{2})$
$\displaystyle=1\left\\{0.288X_{12}+0.686X_{22}+0.096D_{1}Y_{1}^{dm}\geq-0.007\right\\}.$

$\hat{g}_{1}^{B}$ assigns every student to a class with a teacher aide in
grade K, while $\hat{g}_{1}^{S}$ assigns only students in rural areas to
classes with a teacher aide in grade K. Under both treatment rules
$\hat{g}_{2}^{B}$ and $\hat{g}_{2}^{S}$, a student who attends a class with a
teacher aide and attains a high test score in grade K is more likely to be
assigned to a class with a teacher aide in grade 1.

Table 2 reports the estimated welfare gains and shares of population to be
treated at each stage by $\hat{g}^{B}$ and $\hat{g}^{S}$ and the other three
DTRs
$\left(g_{1},g_{2}\right)=\left(1,0\right),\left(0,1\right),\left(1,1\right)$.
For example, the DTR $\left(g_{1},g_{2}\right)=\left(1,0\right)$ assigns every
student to a class with a teacher aide in kindergarten but assigns no students
to a class with a teacher aide in grade 1. The results show that both the
Backward and Simultaneous DEWMs lead to higher welfare gains than the
primitive DTRs
$\left(g_{1},g_{2}\right)=\left(1,0\right),\left(0,1\right),\left(1,1\right)$.
The Simultaneous DEWM method leads to a higher welfare gain than the Backward
DEWM method. This would be because the constrained $\mathcal{G}_{2}$ does not
contain the first-best treatment rule (i.e., Assumption 3.1 does not hold).

Table 2: Estimated welfare gains

| Share of population to be treated |
---|---|---
Dynamic treatment regime | 1st stage | 2nd stage | Estimated welfare gain
$\left(g_{1},g_{2}\right)=\left(1,0\right)$ | $1$ | $0$ | $9.50$
$\left(g_{1},g_{2}\right)=\left(0,1\right)$ | $0$ | $1$ | $17.82$
$\left(g_{1},g_{2}\right)=\left(1,1\right)$ | $1$ | $1$ | $13.58$
$\left(\hat{g}_{1}^{B},\hat{g}_{2}^{B}\right)$ | $1$ | $0.50$ | $20.88$
$\left(\hat{g}_{1}^{S},\hat{g}_{2}^{S}\right)$ | $0.63$ | $0.74$ | $27.24$

  * •

Notes: The SD of $Y_{2}^{dm}$ in the sample is 83.27. The same 1,346
observations are used to calculate the DTRs $\hat{g}^{B}$ and $\hat{g}^{S}$,
shares of population to be treated, and welfare gains of $\hat{g}^{B}$ and
$\hat{g}^{S}$.

Next, we impose a restriction $g_{2}\left(h_{2}\right)\geq d_{1}$ for all
$h_{2}\in\mathcal{H}_{2}$; thereby, we consider the decision problem of when
each student should start attending a class with a teacher aide. Under this
constraint, the DTR estimated by the Backward DEWM method is
$\hat{g}^{B}=\left(\hat{g}_{1}^{B},\hat{g}_{2}^{B}\right)$ with

$\displaystyle\hat{g}_{1}^{B}(H_{1})$ $\displaystyle=0,$
$\displaystyle\hat{g}_{2}^{B}(H_{2})$
$\displaystyle=1\left\\{0.702X_{12}-0.056X_{22}-0.073\left(1-D_{1}\right)Y_{1}^{dm}+0.152D_{1}Y_{1}^{dm}\geq-0.016\right\\};$

the DTR estimated by the Simultaneous DEWM method is
$\hat{g}^{S}=\left(\hat{g}_{1}^{S},\hat{g}_{2}^{S}\right)$ with

$\displaystyle\hat{g}_{1}^{S}(H_{1})$
$\displaystyle=1\left\\{X_{21}=1\right\\},$
$\displaystyle\hat{g}_{2}^{S}(H_{2})$ $\displaystyle=1.$

Table 3 reports the estimated welfare gains and shares of population to be
treated by $\hat{g}^{B}$ and $\hat{g}^{S}$ and the other two DTRs
$(g_{1},g_{2})=(0,1),(1,1)$, which satisfy the constraint
$g_{2}\left(h_{2}\right)\geq d_{1}$ for all $h_{2}\in\mathcal{H}_{2}$. In
contrast to the results without the additional constraint in Table 2, the
Backward DEWM method leads to less welfare gains than the constant DTRs
$(g_{1},g_{2})=(0,1),(1,1)$, while the Simultanous DEWM method leads to the
highest welfare gain.

Table 3: Estimated welfare gains for the start-time decision problem

| Share of population to be treated |
---|---|---
Dynamic treatment regime | 1st stage | 2nd stage | Estimated welfare gain
$\left(g_{1},g_{2}\right)=\left(0,1\right)$ | $0$ | $1$ | $17.82$
$\left(g_{1},g_{2}\right)=\left(1,1\right)$ | $1$ | $1$ | $13.58$
$(\hat{g}_{1}^{B},\hat{g}_{2}^{B})$ | $0$ | $0.50$ | $6.78$
$(\hat{g}_{1}^{S},\hat{g}_{2}^{S})$ | $0.63$ | $1.00$ | $23.59$

  * •

Note: The SD of $Y_{2}^{dm}$ in the sample is 83.27. The same 1,346
observations are used to calculate the DTRs $\hat{g}^{B}$ and $\hat{g}^{S}$,
shares of population to be treated, and welfare gains of $\hat{g}^{B}$ and
$\hat{g}^{S}$.

Finally, we consider estimating an optimal DTR under the following fictitious
budget constraint:

$\displaystyle
E_{P}\left[g_{1}\left(H_{1}\right)\right]+E_{P}\left[g_{2}\left(H_{2}\right)\mid
D_{1}=g_{1}\left(H_{1}\right)\right]$ $\displaystyle\leq 1,$

where we suppose that the cost of a teacher aide is the same in grades K and
1. We apply the modified Simultaneous DEWM method, introduced in Section 4, to
estimate the optimal DTR under this budget constraint. In the estimation, we
conservatively set $\alpha_{n}=0$ in the empirical budget constraint (10). We
estimate the welfare gain as well as the excess implementation cost of the
estimated DTR over the budget which is $1$.

The modified Simultaneous DEWM method estimates the DTR to be
$\hat{g}^{S}=\left(\hat{g}_{1}^{S},\hat{g}_{2}^{S}\right)$ with

$\displaystyle\hat{g}_{1}^{S}(H_{1})$
$\displaystyle=1\left\\{X_{21}=1\right\\},$
$\displaystyle\hat{g}_{2}^{S}(H_{2})$
$\displaystyle=1\left\\{0.004X_{12}-0.104X_{22}+0.052\left(1-d_{1}\right)y_{1}^{dm}+0.106d_{1}y_{1}^{dm}\geq
0.817\right\\}.$

The estimates of the shares of the population that are treated in grades K and
1 are $0.63$ and $0.37$, respectively. The estimated welfare gain is $25.15$,
which is less than the welfare gain without the budget constraint, $27.52$.
The estimated excess cost of the estimated policy is $0$, meaning that the
estimated policy exhausts the budget in the sample.

###  8 Conclusion

This paper proposed empirical methods to estimate the optimal DTR over a pre-
specified class of feasible DTRs based on the empirical welfare maximization
approach. We proposed two estimation methods, the Backward DEWM method and the
Simultaneous DEWM method, which estimate the optimal DTR through backward
induction and simultaneous maximization, respectively. The former is
computationally efficient, but it can consistently estimate the optimal DTR
only when the class of feasible DTRs contains the first-best treatment rule at
all stages except for the first stage. In contrast, the Simultaneous DEWM can
consistently estimate the optimal DTR without such a condition, though it is
computationally less efficient. These methods can accommodate exogenous
constraints on the class of feasible DTRs and, furthermore, can specify
different types of dynamic treatment choice problems. The upper and lower
bounds on the worst-case average welfare-regrets for the two methods are
derived. The main result of the paper is that each method can achieve the
optimal convergence rate of $n^{-1/2}$ toward zero in the experimental data
setting. In the observational data setting, the convergence rates depend on
that of the estimated propensity scores. We also modified the Simultaneous
DEWM to accommodate intertemporal budget/capacity constraints, and derived the
$n^{-1/2}$-upper bounds on the worst-case welfare-regret and the excess
implementation cost of the estimated DTR over the actual budget that hold with
high probability. The proposed estimation methods with the linear eligibility
policy class can be formulated as MILPs (see Appendix B).

## Appendix

###  Appendix A Proofs

In this appendix, Section A.1 provides the proofs of Theorems 3.4, 3.5, and
5.1 with some auxiliary lemmas. Section A.2 provides the proof of Theorem 4.1
with some auxiliary lemmas and a proposition.

####  A.1  Proofs of Theorems 3.4, 3.5, and 5.1.

This section provides the proofs of Theorems 3.4, 3.5, and 5.1. Many concepts
and techniques used in the proofs are taken from the literature on statistical
learning theory (e.g., Devroye et al. (1996); Lugosi (2002); Mohri et al.
(2012)).

We first introduce the VC-dimension for a class of subsets. Let $\mathcal{Z}$
be any space, and let $\mathbf{z}_{\ell}=\left(z_{1},\ldots,z_{\ell}\right)$
be a finite set of $\ell\geq 1$ points in $\mathcal{Z}$. Given a class of
subsets $\mathcal{G}\subseteq 2^{\mathcal{Z}}$ and a subset
$\mathbf{\tilde{\mathbf{z}}}$ of $\mathbf{z}_{\ell}$, we say that
$\mathcal{G}$ picks out $\mathbf{\tilde{\mathbf{z}}}$ when
$\tilde{\mathbf{z}}\cap G=\tilde{\mathbf{z}}$ holds for some
$G\in\mathcal{G}$. We say that $\mathcal{G}$ shatters $\mathbf{z}_{\ell}$ when
$\left|\left\\{\mathbf{z}_{\ell}\cap
G:G\in\mathcal{G}\right\\}\right|=2^{\ell}$ holds, that is all subsets of
$\mathbf{z}_{\ell}$ are picked out by $\mathcal{G}$. The VC-dimension of the
class of subsets $\mathcal{G}$, denoted by $VC(\mathcal{G})$, is defined as
the cardinality of the largest subset $\mathbf{z}_{\ell}$ contained in
$\mathcal{Z}$ and shattered by $\mathcal{G}$, i.e.,

$\displaystyle
VC(\mathcal{G})\equiv\max\\{\ell:\max_{\mathbf{z}_{\ell}\subseteq\mathcal{Z}}\left|\left\\{\mathbf{z}_{\ell}\cap
G:G\in\mathcal{G}\right\\}\right|=2^{\ell}\\}.$

We say that a class of subsets $\mathcal{G}$ is a VC-class of subsets if
$VC(\mathcal{G})<\infty$.

We next introduce a concept of the subgraph of a real-valued function
$f:\mathcal{Z}\rightarrow\mathbb{R}$ that is the set

$\displaystyle\mbox{SG}\left(f\right)\equiv\left\\{\left(z,t\right)\in\mathcal{Z}\times\mathbb{R}:t\leq
f\left(z\right)\right\\}.$

Let
$\mbox{SG}\left(\mathcal{F}\right)\equiv\\{\mbox{SG}\left(f\right):f\in\mathcal{F}\\}$
be a collection of subgraphs over a class of functions $\mathcal{F}$. We here
consider the VC-dimension of $\mbox{SG}(\mathcal{F})$ as a complexity measure
of $\mathcal{F}$. Note that in the case of $\mathcal{F}$ being a class of
indicator functions, the VC-dimension of $\mbox{SG}\left(\mathcal{F}\right)$
corresponds to the VC-dimension of $\mathcal{F}$ in the sense of Definition
2.1. We say that a class of functions $\mathcal{F}$ is a VC-subgraph class of
functions if $VC(\mbox{SG}\left(\mathcal{F}\right))<\infty$.

We first consider establishing a link between the concepts of VC-dimension of
a class of feasible DTRs and VC-dimension of a collection of subgraphs of
functions on ${\cal Z}$. The following lemmas are auxiliary lemmas for this
purpose.

######  Lemma A.1.

(Sauer’s lemma; see, for example, Theorem 3.6.2 of Giné and Nickl (2016)) Let
$\mathcal{Z}$ be any space, and $\left(z_{1},\ldots,z_{\ell}\right)$ be a
finite set of $\ell\geq 1$ points in $\mathcal{Z}$. Let $\mathcal{G}$ be a VC-
class of subsets in $\mathcal{Z}$ with $VC(\mathcal{G})=v<\infty$. Let
$\Delta_{\ell}(\mathcal{G},(z_{1},\ldots,z_{\ell}))$ denote the number of
subsets of $(z_{1},\ldots,z_{\ell})$ that are picked out by $\mathcal{G}$,
i.e.,

$\displaystyle\Delta_{\ell}\left(\mathcal{G},(z_{1},\ldots,z_{\ell})\right)\equiv\left|\left\\{(z_{1},\ldots,z_{\ell})\cap
G:G\in\mathcal{G}\right\\}\right|.$

Then the following holds:

$\displaystyle\max_{(z_{1},\ldots,z_{\ell})\subseteq\mathcal{Z}}\Delta_{\ell}\left(\mathcal{G},\left(z_{1},\ldots,z_{\ell}\right)\right)\leq\sum_{j=0}^{v}\left(\begin{array}[]{c}\ell\\\
j\end{array}\right)\leq\left(\frac{\ell e}{v}\right)^{v}.$

######  Lemma A.2.

Let $\mathcal{Z}=\mathcal{Z}_{1}\times\mathcal{Z}_{2}$ be any product space,
and $\mathcal{G}$ be a class of indicator functions from $\mathcal{Z}_{2}$ to
$\\{0,1\\}$. Suppose that $\mathcal{G}$ has VC-dimension $v\geq 0$ in the
sense of Definition 2.1. Fix a function $f$ on $\mathcal{Z}$, and define a
class of functions on $\mathcal{Z}$:

$\displaystyle\mathcal{F}_{\mathcal{G}}=\left\\{f\cdot
g:g\in\mathcal{G}\right\\}.$

Then $\mathcal{F}_{\mathcal{G}}$ is a VC-subgraph class of functions with
$VC(\mbox{SG}(\mathcal{F}_{\mathcal{G}}))\leq v$.

###### Proof.

We prove the statement by contradiction. Suppose that there exist some
$(v+1)$-points
$\left\\{\left(z_{1},t_{1}\right),\ldots,\left(z_{v+1},t_{v+1}\right)\right\\}\equiv\left\\{\left(z_{1,1},z_{2,1},t_{1}\right),\ldots,\left(z_{1,v+1},z_{2,v+1},t_{v+1}\right)\right\\}\subset\mathcal{Z}_{1}\times\mathcal{Z}_{2}\times\mathbb{R}$
that are shattered by $\mbox{SG}\left(\mathcal{F}_{\mathcal{G}}\right)$.

When $t\leq f\left(z\right)\wedge 0$ or $t>f\left(z\right)\vee 0$ for some
$\left(z,t\right)\in\left\\{\left(z_{1},t_{1}\right),\ldots,\left(z_{v+1},t_{v+1}\right)\right\\}$,
$\mbox{SG}\left(\mathcal{F}_{\mathcal{G}}\right)$ cannot pick out
$\left\\{\left(z_{1},t_{1}\right),\ldots\left(z_{v+1},t_{v+1}\right)\right\\}\backslash\\{\left(z,t\right)\\}$
or $\left\\{\left(z,t\right)\right\\}$. Thus, we need to consider only the
case that $\left(f\left(z\right)\wedge 0\right)<t\leq\left(f\left(z\right)\vee
0\right)$ for all
$\left(z,t\right)\in\left\\{\left(z_{1},t_{1}\right),\ldots\left(z_{v+1},t_{v+1}\right)\right\\}$.
In the remaining case, we indicate $\delta_{j}=1$ if $t_{j}\leq f(z_{j})$ and
$\delta_{j}=0$ otherwise. Since the VC-dimension of $\mathcal{G}$ is at most
$v$ in the sense of Definition 2.1, there exists a subset
$S\equiv(\tilde{z}_{2,1},\ldots,\tilde{z}_{2,m})$ (for some $m>0$) of
$\left\\{z_{2,1},\ldots,z_{2,v+1}\right\\}$ such that
$(g(\tilde{z}_{2,1}),\ldots,g(\tilde{z}_{2,m}))\neq(1,\ldots,1)$ and
$(g(z_{2,1}),\ldots,g(z_{2,v+1})\backslash(g(\tilde{z}_{2,1}),\ldots,g(\tilde{z}_{2,m}))\neq(0,\ldots,0)$
for any $g\in\mathcal{G}$. Then
$\mbox{SG}\left(\mathcal{F}_{\mathcal{G}}\right)$ cannot pick out the
following subset:

$\displaystyle\left\\{\left(z_{j},t_{j}\right):\left(z_{2,j}\in S\mbox{ and
}\delta_{j}=1\right)\mbox{ or }\left(z_{2,j}\notin S\mbox{ and
}\delta_{j}=0\right)\right\\},$

because this set of points could be contained in $\mbox{SG}\left(f\cdot
g\right)$ only when
$\mbox{sign}(t_{j})=\mbox{sign}(g\left(z_{2,j}\right)-1/2)$ for all
$j=1,\ldots,v+1$. This contradicts the assumption that
$\left\\{\left(z_{1},t_{1}\right),\ldots\left(z_{v+1},t_{v+1}\right)\right\\}\subset\mathcal{Z}\times\mathbb{R}$
is shattered by $\mbox{SG}\left(\mathcal{F}_{\mathcal{G}}\right)$. ∎

The following lemma establishes the link between the VC-dimension of a class
of feasible DTRs and the VC-dimension of a class of subgraphs of functions on
${\cal Z}$.

######  Lemma A.3.

Suppose that Assumption 2.3 holds. Let $r:\mathcal{Z}\rightarrow\mathbb{R}$ be
any function. For any integers $s,t$ with $1\leq s\leq t\leq T$, a class of
functions from ${\cal Z}$ to $\mathbb{R}$

$\displaystyle\mathcal{F}_{s:t}\equiv\left\\{f\left(z\right)=1\left\\{g_{s}\left(h_{s}\right)=d_{s},\ldots,g_{t}\left(h_{t}\right)=d_{t}\right\\}\cdot
r(z):\left(g_{s},\ldots,g_{t}\right)\in\mathcal{G}_{s}\times\cdots\times\mathcal{G}_{t}\right\\}$

is a VC-subgraph class of functions with
$VC(\mbox{SG}(\mathcal{F}_{s:t}))\leq\sum_{j=s}^{t}v_{j}$.

###### Proof.

We prove for the case that $s=1$ and $t=T$. The result follows for the
remaining cases by a similar argument. Let $m$ be an arbitrary integer and
$\left(z_{1},\ldots,z_{m}\right)$ be $m$ arbitrary points on $\mathcal{Z}$.
For each $t$, fixing $g_{s}\in\mathcal{G}_{s}$ for all $s\neq t$, define a
class of functions

$\displaystyle\widetilde{{\cal
F}}_{t}\equiv\left\\{f\left(z\right)=1\left\\{g_{1}\left(h_{1}\right)=d_{1},\ldots,g_{T}\left(h_{T}\right)=d_{T}\right\\}\cdot
r(z):g_{t}\in\mathcal{G}_{t}\right\\},$

and, fixing $g_{s}\in\mathcal{G}_{s}$ for all $s>t$, define

$\displaystyle\widetilde{{\cal F}}_{1:t}\equiv$
$\displaystyle\left\\{f\left(z\right)=1\left\\{g_{1}\left(h_{1}\right)=d_{1},\ldots,g_{T}\left(h_{T}\right)=d_{T}\right\\}\cdot
r(z):\left(g_{1},\ldots,g_{t}\right)\in\mathcal{G}_{1}\times\cdots\times\mathcal{G}_{t}\right\\}.$

We first consider $\widetilde{\mathcal{F}}_{1}$, or equivalently
$\widetilde{\mathcal{F}}_{1:1}$. Applying Lemma A.2 to
$\widetilde{\mathcal{F}}_{1}$ shows that $\widetilde{\mathcal{F}}_{1}$ is a
VC-subgraph of functions with $VC(\mbox{SG}(\widetilde{\mathcal{F}}_{1}))\leq
v_{1}$. Therefore, from Lemma A.1, SG$(\widetilde{\mathcal{F}_{1}})$ can pick
out at most $O(m^{v_{1}})$ subsets from $(z_{1},\ldots,z_{m})$.

Next we study $\widetilde{\mathcal{F}}_{2}$ and then
$\widetilde{\mathcal{F}}_{1:2}$. Let $(z_{1},\ldots,z_{m^{\prime}})$ be an
arbitrary subset picked out by $\mbox{SG}(\tilde{f_{1}})$ where
$\tilde{f}_{1}\in\widetilde{\mathcal{F}}_{1:1}$ has a fixed $g_{1}\in{\cal
G}_{1}$. Lemmas A.1 and A.2 show that SG$(\widetilde{\mathcal{F}}_{2})$ can
pick out at most $O(m^{v_{2}})$ subsets from $(z_{1},\ldots,z_{m^{\prime}})$.
Because SG$(\widetilde{\mathcal{F}}_{2})$ can pick out at most $O(m^{v_{2}})$
subsets from each subset of $(z_{1},\ldots,z_{m})$ and SG$(\widetilde{{\cal
F}}_{1:1})$ can pick out at most $O(m^{v_{1}})$ subsets from
$(z_{1},\ldots,z_{m})$, by varying $(g_{1},g_{2})$ over
$\mathcal{G}_{1}\times\mathcal{G}_{2}$, SG$(\widetilde{\mathcal{F}}_{1:2})$
picks out at most $O(m^{v_{1}+v_{2}})$ subsets from $(z_{1},\ldots,z_{m})$.

For $s\geq 2$, suppose that $\widetilde{\mathcal{F}}_{1:s-1}$ can pick out at
most $O(m^{\sum_{t=1}^{s-1}v_{t}})$ subsets from $(z_{1},\ldots,z_{m})$. Let
$(z_{1},\ldots,z_{m^{\prime}})$ be an arbitrary subset picked out by
SG$(\tilde{f}_{s-1})$ where
$\tilde{f}_{s-1}\in\widetilde{\mathcal{F}}_{1:s-1}$ has fixed
$g_{1},\ldots,g_{s-1}$. From $(z_{1},\ldots,z_{m^{\prime}})$,
SG$(\tilde{\mathcal{F}}_{s})$ can pick out at most $O(m^{v_{s}})$ subsets.
Combining this result with the fact that $\widetilde{\mathcal{F}}_{1:s-1}$ can
pick out at most $O(m^{\sum_{t=1}^{s-1}v_{t}})$ subsets from
$(z_{1},\ldots,z_{m})$ leads to the conclusion that
$\widetilde{\mathcal{F}}_{1:s}$ picks out at most $O(m^{\sum_{t=1}^{s}v_{t}})$
subsets from $(z_{1},\ldots,z_{m})$.

Recursively, we can prove that $\widetilde{\mathcal{F}}_{1:T}$ picks out at
most $O(m^{\sum_{t=1}^{T}v_{t}})$ subsets from $(z_{1},\ldots,z_{m})$. Hence,
SG$(\widetilde{\mathcal{F}}_{1:T})$ is a VC-subgraph class of functions with
VC-dimension less than or equal to $\sum_{t=1}^{T}v_{t}$. ∎

The next lemma, which corresponds to Lemma A.4 of Kitagawa and Tetenov (2018),
gives a uniform upper bound for the mean of a supremum of centered empirical
processes indexed by a VC-subgraph class of functions. This is a fundamental
result in the literature on empirical process theory and its proof can be
found, for example, in van der Vaart and Wellner (1996) and Kitagawa and
Tetenov (2018). The following lemma will be used in the proofs of Lemmas A.5
and A.7 below.

######  Lemma A.4.

Let ${\cal F}$ be a class of uniformly bounded functions on $\mathcal{Z}$,
that is, there exists $\bar{F}<\infty$ such that
$\left\|f\right\|_{\infty}\leq\bar{F}$ for all $f\in{\cal F}$. Assume that
${\cal F}$ is a VC-subgraph of functions with VC-dimension $v<\infty$. Then
there is a universal constant $C$ such that

$\displaystyle E_{P^{n}}\left[\sup_{f\in{\cal
F}}\left|E_{n}\left(f\right)-E_{P}\left(f\right)\right|\right]$
$\displaystyle\leq C\bar{F}\sqrt{\frac{v}{n}}$

holds for all $n\geq 1$.

Before proceeding to the proofs of the main theorems, we define

$\displaystyle\tilde{Q}_{t}\left(g_{t},\ldots,g_{T}\right)$
$\displaystyle\equiv E_{P}\left[q_{t}\left(Z,g_{t},\ldots,g_{T}\right)\right]$
$\displaystyle=E_{P}\left[\sum_{s=t}^{T}\left\\{\frac{(\prod_{\ell=t}^{s}1\left\\{g_{\ell}\left(H_{\ell}\right)=D_{\ell}\right\\})\gamma_{s}Y_{s}}{\prod_{\ell=t}^{s}e_{\ell}\left(D_{\ell},H_{\ell}\right)}\right\\}\right]$
(14)

and

$\displaystyle\tilde{Q}_{nt}\left(g_{t},\ldots,g_{T}\right)$
$\displaystyle\equiv E_{n}\left[q_{t}\left(Z,g_{t},\ldots,g_{T}\right)\right]$
$\displaystyle=E_{n}\left[\sum_{s=t}^{T}\left\\{\frac{(\prod_{\ell=t}^{s}1\left\\{g_{\ell}\left(H_{\ell}\right)=D_{\ell}\right\\})\gamma_{s}Y_{s}}{\prod_{\ell=t}^{s}e_{\ell}\left(D_{\ell},H_{\ell}\right)}\right\\}\right].$

We further define

$\displaystyle\Delta\tilde{Q}_{t}$
$\displaystyle\equiv\tilde{Q}_{t}\left(g_{t}^{\ast},\ldots,g_{T}^{\ast}\right)-\tilde{Q}_{t}\left(\hat{g}_{t}^{B},\ldots,\hat{g}_{T}^{B}\right),$
$\displaystyle\Delta\tilde{Q}_{t}^{\dagger}$
$\displaystyle\equiv\tilde{Q}_{t}\left(g_{t}^{\ast},\hat{g}_{t+1}^{B},\ldots,\hat{g}_{T}^{B}\right)-\tilde{Q}_{t}\left(\hat{g}_{t}^{B},\ldots,\hat{g}_{T}^{B}\right).$

The following lemma will be used in the proof of Theorem 3.4 (ii) for the
Backward DEWM method.

######  Lemma A.5.

Suppose that Assumptions 2.1, 2.4, and 3.1 hold for a pair $(P,\mathcal{G})$.
Then the following hold:

  * (i)

for any $t=1,\ldots,T$,

$\displaystyle
E_{P^{n}}\left[\left|\Delta\tilde{Q}_{t}^{\dagger}\right|\right]$
$\displaystyle\leq
C\left(\sum_{s=t}^{T}\frac{\gamma_{s}M_{s}}{\prod_{\ell=t}^{s}\kappa_{\ell}}\right)\sqrt{\frac{\sum_{s=t}^{T}v_{s}}{n}},$

where $C$ is the same constant term introduced in Lemma A.4;

  * (ii)

for any $t=1,\ldots,T-1$ and $s=t+1,\ldots,T$,

$\displaystyle\tilde{Q}_{t}\left(g_{t}^{\ast},\ldots,g_{T}^{\ast}\right)-\tilde{Q}_{t}\left(g_{t}^{\ast},\ldots,g_{s}^{\ast},\hat{g}_{s+1}^{B},\ldots,\hat{g}_{T}^{B}\right)$
$\displaystyle\leq\frac{1}{\prod_{\ell=t}^{s}\kappa_{\ell}}\Delta\tilde{Q}_{s+1};$

  * (iii)

$\displaystyle\Delta\tilde{Q}_{1}$
$\displaystyle\leq\Delta\tilde{Q}_{1}^{\dagger}+\sum_{s=1}^{T-1}\frac{2^{s-1}}{\prod_{t=1}^{s}\kappa_{t}}\Delta\tilde{Q}_{s+1}^{\dagger}.$

###### Proof.

(i) It follows that

$\displaystyle\Delta\tilde{Q}_{t}^{\dagger}$
$\displaystyle=\tilde{Q}_{t}\left(g_{t}^{\ast},\hat{g}_{t+1}^{B},\ldots,\hat{g}_{T}^{B}\right)-\tilde{Q}_{t}\left(\hat{g}_{t}^{B},\ldots,\hat{g}_{T}^{B}\right)$
$\displaystyle=\tilde{Q}_{t}\left(g_{t}^{\ast},\hat{g}_{t+1}^{B},\ldots,\hat{g}_{T}^{B}\right)-\tilde{Q}_{nt}\left(g_{t}^{\ast},\hat{g}_{t+1}^{B},\ldots,\hat{g}_{T}^{B}\right)$
$\displaystyle+\tilde{Q}_{nt}\left(g_{t}^{\ast},\hat{g}_{t+1}^{B},\ldots,\hat{g}_{T}^{B}\right)-\tilde{Q}_{t}\left(\hat{g}_{t}^{B},\ldots,\hat{g}_{T}^{B}\right)$
$\displaystyle\leq\tilde{Q}_{t}\left(g_{t}^{\ast},\hat{g}_{t+1}^{B},\ldots,\hat{g}_{T}^{B}\right)-\tilde{Q}_{nt}\left(g_{t}^{\ast},\hat{g}_{t+1}^{B},\ldots,\hat{g}_{T}^{B}\right)+\tilde{Q}_{nt}\left(\hat{g}_{t}^{B},\ldots,\hat{g}_{T}^{B}\right)-\tilde{Q}_{t}\left(\hat{g}_{t}^{B},\ldots,\hat{g}_{T}^{B}\right)$
$\displaystyle\leq 2\sup_{\left(g_{t},\ldots,g_{T}\right)\in{\cal
G}_{t}\times\cdots\times{\cal
G}_{T}}\left|\tilde{Q}_{nt}\left(g_{t},\ldots,g_{T}\right)-\tilde{Q}_{t}\left(g_{t},\ldots,g_{T}\right)\right|,$
(15)

where the first inequality follows from the fact that $\hat{g}_{t}^{B}$
maximizes
$\tilde{Q}_{nt}\left(\cdot,\hat{g}_{t+1}^{B},\ldots,\hat{g}_{T}^{B}\right)$
over ${\cal G}_{t}$. Because

$\displaystyle\left\|\tilde{Q}_{t}\left(g_{t},\ldots,g_{T}\right)\right\|_{\infty}\leq\sum_{s=t}^{T}\frac{\gamma_{s}M_{s}/2}{\prod_{\ell=t}^{s}\kappa_{\ell}}$

holds under Assumptions 2.2 and 2.4, by applying Lemmas A.3 and A.4 to the
following class of functions:

$\displaystyle\left\\{\sum_{s=t}^{T}\left\\{\frac{\left(\prod_{\ell=t}^{s}1\left\\{g_{\ell}\left(H_{\ell}\right)=D_{\ell}\right\\}\right)\gamma_{s}Y_{s}}{\prod_{\ell=t}^{s}e_{\ell}\left(D_{\ell},H_{\ell}\right)}\right\\}:\left(g_{t},\ldots,g_{T}\right)\in\mathcal{G}_{t}\times\cdots\times\mathcal{G}_{T}\right\\},$

we have

$\displaystyle E_{P^{n}}\left[\sup_{\left(g_{t},\ldots,g_{T}\right)\in{\cal
G}_{t}\times\cdots\times{\cal
G}_{T}}\left|\tilde{Q}_{nt}\left(g_{t},\ldots,g_{T}\right)-\tilde{Q}_{t}\left(g_{t},\ldots,g_{T}\right)\right|\right]$
$\displaystyle\leq
C\left(\sum_{s=t}^{T}\frac{\gamma_{s}M_{s}/2}{\prod_{\ell=t}^{s}\kappa_{\ell}}\right)\sqrt{\frac{\sum_{s=t}^{T}v_{s}}{n}}.$

Combining this with equation (15) leads to the result.

(ii) For any integers $s$ and $t$ such that $1\leq t<s\leq T$, it follows that

$\displaystyle\tilde{Q}_{t}\left(g_{t}^{\ast},\ldots,g_{T}^{\ast}\right)-\tilde{Q}_{t}\left(g_{t}^{\ast},\ldots,g_{s}^{\ast},\hat{g}_{s+1}^{B},\ldots,\hat{g}_{T}^{B}\right)$
$\displaystyle=$ $\displaystyle
E_{P}\left[\frac{\prod_{\ell=t}^{s}1\left\\{D_{\ell}=g_{\ell}^{\ast}\left(H_{\ell}\right)\right\\}}{\prod_{\ell=t}^{s}e_{\ell}\left(D_{\ell},H_{\ell}\right)}E_{P}\left[\tilde{Q}_{s+1}\left(g_{s+1}^{\ast},\ldots,g_{T}^{\ast}\right)-\tilde{Q}_{s+1}\left(\hat{g}_{s+1}^{B},\ldots,\hat{g}_{T}^{B}\right)\mid
H_{s+1}\right]\right].$ (16)

Since

$\displaystyle
E_{P}\left[\tilde{Q}_{s+1}\left(g_{s+1}^{\ast},\ldots,g_{T}^{\ast}\right)-\tilde{Q}_{s+1}\left(\hat{g}_{s+1}^{B},\ldots,\hat{g}_{T}^{B}\right)\mid
H_{s+1}=h_{s+1}\right]$ $\displaystyle\geq 0$

holds for all $h_{s+1}\in{\cal H}_{s+1}$ under Assumptions 2.1 and 3.1, and

$\displaystyle\left\|\frac{\prod_{\ell=t}^{s}1\left\\{D_{\ell}=g_{\ell}^{\ast}\left(H_{\ell}\right)\right\\}}{\prod_{\ell=t}^{s}e_{\ell}\left(D_{\ell},H_{\ell}\right)}\right\|_{\infty}\leq\frac{1}{\prod_{\ell=t}^{s}\kappa_{\ell}}$

holds from Assumption 2.4, the following holds:

$\displaystyle
E_{P}\left[\frac{\prod_{\ell=t}^{s}1\left\\{D_{\ell}=g_{\ell}^{\ast}\left(H_{\ell}\right)\right\\}}{\prod_{\ell=t}^{T}e_{\ell}\left(D_{\ell},H_{\ell}\right)}E_{P}\left[\tilde{Q}_{s+1}\left(g_{s+1}^{\ast},\ldots,g_{T}^{\ast}\right)-\tilde{Q}_{s+1}\left(\hat{g}_{s+1}^{B},\ldots,\hat{g}_{T}^{B}\right)\mid
H_{s+1}\right]\right]$ $\displaystyle\leq$
$\displaystyle\frac{1}{\prod_{\ell=t}^{s}\kappa_{\ell}}E_{P}\left[E_{P}\left[\tilde{Q}_{s+1}\left(g_{s+1}^{\ast},\ldots,g_{T}^{\ast}\right)-\tilde{Q}_{s+1}\left(\hat{g}_{s+1}^{B},\ldots,\hat{g}_{T}^{B}\right)\mid
H_{s+1}\right]\right]$ $\displaystyle=$
$\displaystyle\frac{1}{\prod_{\ell=t}^{s}\kappa_{\ell}}\Delta\tilde{Q}_{s+1}.$

Combining this with (16) leads to the result.

(iii) Note that it holds that

$\displaystyle\Delta\tilde{Q}_{T}$
$\displaystyle=\tilde{Q}_{T}\left(g_{T}^{\ast}\right)-\tilde{Q}_{T}\left(\hat{g}_{T}^{B}\right)=\Delta\tilde{Q}_{T}^{\dagger}.$

Then, for $t=T-1$, we have

$\displaystyle\Delta\tilde{Q}_{T-1}$
$\displaystyle=\tilde{Q}_{T-1}\left(g_{T-1}^{\ast},g_{T}^{\ast}\right)-\tilde{Q}_{T-1}\left(\hat{g}_{T-1}^{B},\hat{g}_{T}^{B}\right)$
$\displaystyle=\tilde{Q}_{T-1}\left(g_{T-1}^{\ast},g_{T}^{\ast}\right)-\tilde{Q}_{T-1}\left(g_{T-1}^{\ast},\hat{g}_{T}^{B}\right)+\tilde{Q}_{T-1}\left(g_{T-1}^{\ast},\hat{g}_{T}^{B}\right)-\tilde{Q}_{T-1}\left(\hat{g}_{T-1}^{B},\hat{g}_{T}^{B}\right)$
$\displaystyle\leq\frac{1}{\kappa_{T-1}}\Delta\tilde{Q}_{T}^{\dagger}+\Delta\tilde{Q}_{T-1}^{\dagger},$

where the inequality follows from Lemma A.5 (ii).

Generally, for any $k=1,\ldots,T-1$, it follows that

$\displaystyle\Delta\tilde{Q}_{T-k}$
$\displaystyle=\tilde{Q}_{T-k}\left(g_{T-k}^{\ast},\ldots,g_{T}^{\ast}\right)-\tilde{Q}_{T-k}\left(\hat{g}_{T-k}^{B},\ldots,\hat{g}_{T}^{B}\right)$
$\displaystyle=\sum_{s=T-k}^{T}\left[\tilde{Q}_{T-k}\left(g_{T-k}^{\ast},\ldots,g_{s}^{\ast},\hat{g}_{s+1}^{B},\ldots,\hat{g}_{T}^{B}\right)-\tilde{Q}_{T-k}\left(g_{T-k}^{\ast},\ldots,g_{s-1}^{\ast},\hat{g}_{s}^{B},\ldots,\hat{g}_{T}^{B}\right)\right]$
$\displaystyle\leq\sum_{s=T-k}^{T}\left[\tilde{Q}_{T-k}\left(g_{T-k}^{\ast},\ldots,g_{T}^{\ast}\right)-\tilde{Q}_{T-k}\left(g_{T-k}^{\ast},\ldots,g_{s-1}^{\ast},\hat{g}_{s}^{B},\ldots,\hat{g}_{T}^{B}\right)\right]$
$\displaystyle=\sum_{s=T-k+1}^{T}\left[\tilde{Q}_{T-k}\left(g_{T-k}^{\ast},\ldots,g_{T}^{\ast}\right)-\tilde{Q}_{T-k}\left(g_{T-k}^{\ast},\ldots,g_{s-1}^{\ast},\hat{g}_{s}^{B},\ldots,\hat{g}_{T}^{B}\right)\right]+\Delta\tilde{Q}_{T-k}^{\dagger}$
$\displaystyle\leq\sum_{s=T-k+1}^{T}\frac{1}{\prod_{\ell=T-k}^{s-1}\kappa_{\ell}}\Delta\tilde{Q}_{s}+\Delta\tilde{Q}_{T-k}^{\dagger},$

where the second line follows by taking a telescope sum; the third line
follows from the fact that $\left(g_{s+1}^{\ast},\ldots,g_{T}^{\ast}\right)$
maximizes
$\tilde{Q}_{T-k}\left(g_{T-k}^{\ast},\ldots,g_{s}^{\ast},\cdot,\ldots,\cdot\right)$
over ${\cal G}_{s+1}\times\cdots\times{\cal G}_{T}$ under Assumption 3.1; the
last line follows from Lemma A.5 (ii).

Then, recursively, the following hold:

$\displaystyle\Delta\tilde{Q}_{T-1}$
$\displaystyle\leq\frac{1}{\kappa_{T-1}}\Delta\tilde{Q}_{T}+\Delta\tilde{Q}_{T-1}^{\dagger}=\frac{1}{\kappa_{T-1}}\Delta\tilde{Q}_{T}^{\dagger}+\Delta\tilde{Q}_{T-1}^{\dagger},$
$\displaystyle\Delta\tilde{Q}_{T-2}$
$\displaystyle\leq\frac{1}{\kappa_{T-2}}\Delta\tilde{Q}_{T-1}+\frac{1}{\kappa_{T-2}\kappa_{T-1}}\Delta\tilde{Q}_{T}+\Delta\tilde{Q}_{T-2}^{\dagger}$
$\displaystyle\leq\frac{2}{\kappa_{T-2}\kappa_{T-1}}\Delta\tilde{Q}_{T}^{\dagger}+\frac{1}{\kappa_{T-2}}\Delta\tilde{Q}_{T-1}^{\dagger}+\Delta\tilde{Q}_{T-2}^{\dagger},$
$\displaystyle\vdots$ $\displaystyle\Delta\tilde{Q}_{T-k}$
$\displaystyle\leq\sum_{s=1}^{k}\frac{2^{k-s}}{\prod_{t=T-k}^{T-s}\kappa_{t}}\Delta\tilde{Q}_{T-s+1}^{\dagger}+\Delta\tilde{Q}_{T-k}^{\dagger}.$

Therefore, when $k=T-1$, we have

$\displaystyle\Delta\tilde{Q}_{1}$
$\displaystyle\leq\Delta\tilde{Q}_{1}^{\dagger}+\sum_{s=1}^{T-1}\frac{2^{T-1-s}}{\prod_{t=1}^{T-s}\kappa_{t}}\Delta\tilde{Q}_{T-s+1}^{\dagger}$
$\displaystyle=\Delta\tilde{Q}_{1}^{\dagger}+\sum_{s=1}^{T-1}\frac{2^{s-1}}{\prod_{t=1}^{s}\kappa_{t}}\Delta\tilde{Q}_{s+1}^{\dagger}.$

∎

We are now prepared to give the proof of Theorem 3.4. We first give the proof
for the Simultaneous DEWM method.

###### Proof of Theorem 3.4 (i):.

Let $P\in{\cal P}\left(M,\kappa,\mathcal{G}\right)$ be fixed. Define

$\displaystyle W_{t}(\text{$\underline{g}$}_{t})\equiv
E_{P}\left[\sum_{\text{$\underline{d}$}_{t}\in\left\\{0,1\right\\}^{t}}\left\\{\left(\prod_{s=1}^{t}1\left\\{g_{s}\left(H_{s}\right)=d_{s}\right\\}\right)\cdot\gamma_{t}Y_{t}\left(\text{$\underline{d}$}_{t}\right)\right\\}\right].$

Note that
$W_{t}(\text{$\underline{g}$}_{t})=E_{P}\left[w_{t}^{S}(Z,\text{$\underline{g}$}_{t})\right]$
and $W\left(g\right)=\sum_{t=1}^{T}W_{t}(\text{$\underline{g}$}_{t})$ hold,
where $w_{t}^{S}(Z,\underline{g}_{t})$ is defined in Section 3.2. Let
$W_{nt}(\underline{g}_{t})$ and $W_{n}\left(g\right)$ be sample analogues of
$W_{t}(\underline{g}_{t})$ and $\sum_{t=1}^{T}W_{t}(\underline{g}_{t})$,
respectively:

$\displaystyle W_{nt}(\text{$\underline{g}$}_{t})$
$\displaystyle\equiv\frac{1}{n}\sum_{i=1}^{n}w_{t}^{S}(Z_{i},\text{$\underline{g}$}_{t})$
$\displaystyle W_{n}\left(g\right)$
$\displaystyle\equiv\sum_{t=1}^{T}W_{nt}(\text{$\underline{g}$}_{t}).$

It follows, for any $g\in\mathcal{G}$, that

$\displaystyle
E_{P^{n}}\left[\left|W\left(g\right)-W\left(\hat{g}^{S}\right)\right|\right]$
$\displaystyle=E_{P^{n}}\left[\left|W\left(g\right)-W_{n}\left(g\right)+W_{n}\left(g\right)-W\left(\hat{g}^{S}\right)\right|\right]$
$\displaystyle\leq
E_{P^{n}}\left[\left|W\left(g\right)-W_{n}\left(g\right)+W_{n}\left(\hat{g}^{S}\right)-W\left(\hat{g}^{S}\right)\right|\right]$
$\displaystyle\leq 2E_{P^{n}}\left[\sup_{g\in{\cal
G}}\left|W_{n}\left(g\right)-W\left(g\right)\right|\right]$
$\displaystyle=2E_{P^{n}}\left[\sup_{g\in{\cal
G}}\left|\sum_{t=1}^{T}\left(W_{nt}(\underline{g}_{t})-W_{t}(\underline{g}_{t})\right)\right|\right]$
$\displaystyle\leq
2\sum_{t=1}^{T}E_{P^{n}}\left[\sup_{\text{$\underline{g}$}_{t}\in\mathcal{G}_{1}\times\cdots\times\mathcal{G}_{t}}\left|W_{nt}(\text{$\underline{g}$}_{t})-W_{t}(\text{$\underline{g}$}_{t})\right|\right],$
(17)

where the second line follows from the fact that $\hat{g}^{S}$ maximizes
$W_{n}\left(\cdot\right)$ over ${\cal G}$, and the fourth line follows from
the definition of $W_{n}\left(\cdot\right)$ and equation (1).

Applying Lemma A.4, combined with Lemma A.3, to each term in (17) leads to the
following: for each $t=1,\ldots,T$,

$\displaystyle
E_{P^{n}}\left[\sup_{\text{$\underline{g}$}_{t}\in\mathcal{G}_{1}\times\cdots\times\mathcal{G}_{t}}\left|W_{nt}(\text{$\underline{g}$}_{t})-W_{t}(\text{$\underline{g}$}_{t})\right|\right]$
$\displaystyle\leq
C\frac{\gamma_{t}M_{t}/2}{\prod_{s=1}^{t}\kappa_{s}}\sqrt{\frac{\sum_{s=1}^{t}v_{s}}{n}},$

where $C$ is the same universal constant that appears in Lemma A.4. Combining
this result with (17), we obtain

$\displaystyle E_{P^{n}}\left[\left|W_{{\cal
G}}^{\ast}-W\left(\hat{g}^{S}\right)\right|\right]$ $\displaystyle\leq
C\sum_{t=1}^{T}\left\\{\frac{\gamma_{t}M_{t}}{\prod_{s=1}^{t}\kappa_{s}}\sqrt{\frac{\sum_{s=1}^{t}v_{s}}{n}}\right\\}.$

Since this upper bound does not depend on $P\in{\cal
P}\left(M,\kappa,\mathcal{G}\right)$, the upper bound is uniform over ${\cal
P}\left(M,\kappa,\mathcal{G}\right)$. ∎

We next provide the proof for the Backward DEWM method.

######  Proof of Theorem 3.4 (ii):.

Let $P\in{\cal P}\left(M,\kappa,\mathcal{G}\right)$ be fixed. Let $g^{\ast}$
be defined in Section 3.1. It follows under Assumptions 2.1 and 3.1 that

$\displaystyle
W_{\mathcal{G}}^{\ast}-W\left(\hat{g}^{B}\right)=\tilde{Q}_{1}\left(g^{\ast}\right)-\tilde{Q}_{1}\left(\hat{g}^{B}\right)\leq\Delta\tilde{Q}_{1}.$

Then, from Lemma A.5 (iii),

$\displaystyle W_{\mathcal{G}}^{\ast}-W\left(\hat{g}^{B}\right)$
$\displaystyle\leq\Delta\tilde{Q}_{1}^{\dagger}+\sum_{s=1}^{T-1}\frac{2^{s-1}}{\prod_{t=1}^{s}\kappa_{t}}\Delta\tilde{Q}_{s+1}^{\dagger}.$

Thus, we have

$\displaystyle E_{P^{n}}\left[\left|W_{{\cal
G}}^{\ast}-W\left(\hat{g}^{B}\right)\right|\right]$ $\displaystyle\leq
E_{P^{n}}\left[\left|\Delta\tilde{Q}_{1}^{\dagger}\right|\right]+\sum_{s=1}^{T-1}\frac{2^{s-1}}{\prod_{t=1}^{s}\kappa_{t}}E_{P^{n}}\left[\left|\Delta\tilde{Q}_{s+1}^{\dagger}\right|\right].$
(18)

Since

$\displaystyle
E_{P^{n}}\left[\left|\Delta\tilde{Q}_{t}^{\dagger}\right|\right]\leq
E_{P^{n}}\left[\sup_{g_{t}\in{\cal
G}_{t}}\left|\tilde{Q}_{t}\left(g_{t},\hat{g}_{t+1}^{B},\ldots,\hat{g}_{T}^{B}\right)-\tilde{Q}_{t}\left(\hat{g}_{t}^{B},\ldots,\hat{g}_{T}^{B}\right)\right|\right]$

for each $t$, applying Lemma A.5 (i) to each term in (18) leads to

$\displaystyle E_{P^{n}}\left[\left|W_{{\cal
G}}^{\ast}-W\left(\hat{g}^{B}\right)\right|\right]$ $\displaystyle\leq
C\sum_{t=1}^{T}\left\\{\frac{\gamma_{t}M_{t}}{\prod_{s=1}^{t}\kappa_{s}}\sqrt{\frac{\sum_{s=1}^{t}v_{s}}{n}}\right\\}$
$\displaystyle+\sum_{t=2}^{T}\frac{2^{t-2}}{\prod_{s=1}^{t-1}\kappa_{s}}\left(C\sum_{s=t}^{T}\left\\{\frac{\gamma_{s}M_{s}}{\prod_{\ell=t}^{s}\kappa_{\ell}}\sqrt{\frac{\sum_{\ell=t}^{s}v_{\ell}}{n}}\right\\}\right),$

where $C$ is the same universal constant that appears in Lemma A.4. Since this
upper bound does not depend on $P\in{\cal
P}\left(M,\kappa,\mathcal{G}\right)$, the upper bound is uniform over ${\cal
P}\left(M,\kappa,\mathcal{G}\right)$. ∎

The following is an auxiliary lemma for the proof of Theorem 3.5, where we use
the same strategy as the proofs of Theorem 2 of Massart et al. (2006) and
Theorem 2.2 of Kitagawa and Tetenov (2018), but extend it to the dynamic
treatment setting.

######  Lemma A.6.

Suppose that Assumptions 2.1, 2.2, and 2.4 hold for any distribution
$P\in{\cal P}\left(M,\kappa,\mathcal{G}\right)$ and Assumption 2.3 holds for
${\cal G}$. Fix $t\in\\{1,\ldots,T\\}$, and let $\gamma_{t}=1$ and
$\gamma_{s}=0$ for all $s\neq t$. Then, for any DTR $\hat{g}\in\mathcal{G}$ as
a function of $\left(Z_{1},\ldots,Z_{n}\right)$,

$\displaystyle\sup_{P\in{\cal
P}\left(M,\kappa,\mathcal{G}\right)}E_{P^{n}}\left[W_{{\cal
G}}^{\ast}-W\left(\hat{g}\right)\right]$ $\displaystyle\geq
2^{-1}\exp\left(-2\right)M_{t}\sqrt{\frac{v_{1:t}}{n}}$

holds for all $n\geq 16v_{1:t}$. This result holds irrespective of whether
Assumption 3.1 additionally holds for a pair of $\mathcal{G}$ and any
$P\in\mathcal{P}(M,\kappa,\mathcal{G})$ or not.

###### Proof.

The proof follows by constructing a specific subclass of ${\cal
P}\left(M,\kappa,\mathcal{G}\right)$, for which the worst-case average
welfare-regret can be bounded from below. We here prove the statement for the
lemma in the case that $t=T$ (i.e., $\gamma_{T}=1$ and $\gamma_{s}=0$ for
$s\neq T$). The proof follows for the remaining cases by a similar argument.
For simplicity, we normalize the support of the potential outcomes to
$Y_{t}\left(\text{$\underline{d}$}_{t}\right)\in\left[-1/2,1/2\right]$ for all
$\underline{d}_{t}\in\\{0,1\\}^{t}$ and $t=1,\ldots,T$. Let $\mathbf{1}_{T}$
denote a $T$-dimensional vector of ones.

We construct a specific subclass $\mathcal{P}^{\ast}\subset{\cal
P}(\mathbf{1}_{T},\kappa)$ as follows. Let
$\tilde{Z}\equiv((D_{t},X_{t},Y_{t})_{t=1}^{T-1},D_{T},X_{T})$, which is a
vector of all the observed variables excluding $Y_{T}$, and denote its space
by $\widetilde{\mathcal{Z}}$. Let $\tilde{z}_{1},\ldots,\tilde{z}_{v_{1:T}}$
be $v_{1:T}$ points in $\widetilde{\mathcal{Z}}$ such that a set
$\left\\{(\tilde{z}_{1},1/2),\ldots,(\tilde{z}_{v_{1:T}},1/2)\right\\}$ is
shattered by a collection of indicator functions

$\displaystyle\left\\{f\left(z\right)=1\left\\{g_{1}\left(h_{1}\right)=d_{1},\cdots,g_{T}\left(h_{T}\right)=d_{T}\right\\}:\left(g_{1},\ldots,g_{T}\right)\in\mathcal{G}_{1}\times\cdots\times\mathcal{G}_{T}\right\\}$

in the sense of Definition 2.1. For $j=1,\ldots,v_{1:T}$, denote
$\tilde{z}_{j}=\left(\left(d_{tj},x_{tj},y_{tj}\right)_{t=1}^{T-1},d_{Tj},x_{Tj}\right)\in\widetilde{\mathcal{Z}}$.
For any $P\in{\cal P}^{\ast}$, we suppose for the marginal distributions of
$\tilde{Z}$ on $\widetilde{\mathcal{Z}}$ that
$P\left(\tilde{Z}=\tilde{z}_{j}\right)=1/v_{1:T}$ for each
$j=1,\ldots,v_{1:T}$. Let
$\mathbf{b}=\left(b_{1},\ldots,b_{v_{1:T}}\right)\in\left\\{0,1\right\\}^{v_{1:T}}$
be a bit vector that indexes a member of ${\cal P}^{\ast}$. Hence ${\cal
P}^{\ast}$ consists of $2^{v_{1:T}}$ distinct DGPs. For each
$j=1,\ldots,v_{1:T}$, depending on $\mathbf{b}$, we construct the following
conditional distribution of $Y_{T}\left(\text{$\underline{d}$}_{T}\right)$
given $\tilde{Z}=\tilde{z}_{j}$: if $b_{j}=1$,

$\displaystyle Y_{T}\left(\text{$\underline{d}$}_{Tj}\right)=$
$\displaystyle\begin{cases}\begin{array}[]{c}1/2\\\
-1/2\end{array}&\begin{array}[]{c}\mbox{w.p. }1/2+\delta\\\ \mbox{w.p.
}1/2-\delta\end{array}\end{cases},$

otherwise

$\displaystyle Y_{T}\left(\text{$\underline{d}$}_{Tj}\right)=$
$\displaystyle\begin{cases}\begin{array}[]{c}1/2\\\
-1/2\end{array}&\begin{array}[]{c}\mbox{w.p. }1/2-\delta\\\ \mbox{w.p.
}1/2+\delta\end{array}\end{cases},$

where $\underline{d}_{Tj}$ is the history of the realized treatments from
stage $1$ to $T$ when $\tilde{Z}=\tilde{z}_{j}$, and
$\delta\in\left[0,1/2\right]$ is chosen properly in a later step of the proof.
When $b_{j}=1$,
$E_{P}\left[Y_{T}\left(\text{$\underline{d}$}_{Tj}\right)\mid\tilde{Z}=\tilde{z}_{j}\right]=\delta$;
otherwise,
$E_{P}\left[Y_{T}\left(\text{$\underline{d}$}_{Tj}\right)\mid\tilde{Z}=\tilde{z}_{j}\right]=-\delta$.
For conditional distributions of the other potential outcomes
$Y_{T}\left(\text{$\underline{d}$}_{T}\right)$ given
$\tilde{Z}=\tilde{z}_{j}$, we set
$Y_{T}\left(\text{$\underline{d}$}_{T}\right)=0$ with probability 1 if
$\text{$\underline{d}$}_{T}\neq\text{$\underline{d}$}_{Tj}$.

When $\mathbf{b}$ is known, an optimal DTR, denoted by
$g_{\mathbf{b}}^{\ast}=\left(g_{1,\mathbf{b}}^{\ast},\ldots,g_{T,\mathbf{b}}^{\ast}\right)$,
is such that

$\displaystyle(g_{1,\mathbf{b}}^{\ast}(h_{1j}),\ldots,g_{T,\mathbf{b}}^{\ast}(h_{Tj}))=$
$\displaystyle\begin{cases}\begin{array}[]{c}\text{$\underline{d}$}_{Tj}\\\
\left(1-d_{1j},\cdots,1-d_{Tj}\right)\end{array}&\begin{array}[]{c}\mbox{if
}b_{j}=1\\\ \mbox{otherwise}\end{array}\end{cases}$

for $j=1,\ldots,v_{1:T}$, where $h_{tj}$ is the history information in
$\tilde{z}_{j}$ up to stage $t$. Such a DTR is feasible in ${\cal G}$. Then,
the optimized social welfare given $\mathbf{b}$ is

$\displaystyle
W\left(g_{\mathbf{b}}^{\ast}\right)=\frac{1}{v_{1:T}}\delta\sum_{j=1}^{v_{1:T}}b_{j}.$

Let $\hat{g}=\left(\hat{g}_{1},\ldots,\hat{g}_{T}\right):{\cal
H}_{1}\times\cdots\times{\cal H}_{T}\mapsto\left\\{0,1\right\\}^{T}$ be an
arbitrary DTR depending on the sample $\left(Z_{1},\ldots,Z_{n}\right)$, and
let $\hat{\mathbf{b}}\in\left\\{0,1\right\\}^{v_{1:T}}$ be a binary vector
such that its $j$-th element is given by

$\displaystyle\hat{b}_{j}=1\left\\{\hat{g}_{1}\left(h_{1j}\right)=d_{1j},\ldots,\hat{g}_{T}\left(h_{Tj}\right)=d_{Tj}\right\\}.$

We define by $\pi\left(\mathbf{b}\right)$ a prior of $\mathbf{b}$ such that
$b_{1},\ldots,b_{v_{1:T}}$ are i.i.d and
$b_{1}\sim\mbox{Ber}\left(1/2\right)$.

Then the maximum average welfare-regret on
$\mathcal{P}\left(\mathbf{1}_{T},\kappa\right)$ satisfies the following:

$\displaystyle\sup_{P\in\mathcal{P}\left(\mathbf{1}_{T},\kappa\right)}E_{P^{n}}\left[W_{{\cal
G}}^{\ast}-W\left(\hat{g}\right)\right]$ $\displaystyle\geq$ $\displaystyle\
\sup_{P_{\mathbf{b}}\in{\cal
P}^{\ast}}E_{P_{\mathbf{b}}^{n}}\left[W\left(g_{\mathbf{b}}^{\ast}\right)-W\left(\hat{g}\right)\right]\geq\int_{\mathbf{b}}E_{P_{\mathbf{b}}^{n}}\left[W\left(g_{\mathbf{b}}^{\ast}\right)-W\left(\hat{g}\right)\right]d\pi(\mathbf{b})$
$\displaystyle\geq$ $\displaystyle\
\delta\int_{\mathbf{b}}\int_{Z_{1},\ldots,Z_{n}}P_{\tilde{Z}}\left(\left\\{b(\tilde{Z})\neq\hat{b}(\tilde{Z})\right\\}\right)dP_{\mathbf{b}}^{n}\left(Z_{1},\ldots,Z_{n}\right)d\pi(\mathbf{b})$
$\displaystyle\geq$ $\displaystyle\
\inf_{\hat{g}\in\mathcal{G}}\delta\int_{\mathbf{b}}\int_{Z_{1},\ldots,Z_{n}}P_{\tilde{Z}}\left(\left\\{b(\tilde{Z})\neq\hat{b}(\tilde{Z})\right\\}\right)dP_{\mathbf{b}}^{n}\left(Z_{1},\ldots,Z_{n}\right)d\pi(\mathbf{b}),$

where $P_{\tilde{Z}}$ is a probability measure of $\tilde{Z}$, and
$b(\tilde{Z})$ and $\hat{b}(\tilde{Z})$ are elements of $\mathbf{b}$ and
$\hat{\mathbf{b}}$ such that $b\left(\tilde{z}_{j}\right)=b_{j}$ and
$\hat{b}\left(\tilde{z}_{j}\right)=\hat{b}_{j}$, respectively. Note that the
above minimization problem can be seen as the minimization of the Bayes risk
when the loss function corresponds to the classification error for predicting
the binary random variable $b(\tilde{Z})$. Hence, the risk is minimized by the
Bayes classifier such that for each $j=1,\ldots,J$,

$\displaystyle\hat{b}^{\ast}\left(\tilde{z}_{j}\right)=$
$\displaystyle\begin{cases}\begin{array}[]{c}1\\\
0\end{array}&\begin{array}[]{c}\mbox{if }\pi\left(b_{j}=1\mid
Z_{1},\ldots,Z_{n}\right)\geq 1/2\\\ \mbox{otherwise}\end{array}\end{cases},$

where $\pi\left(b_{j}=1\mid Z_{1},\ldots,Z_{n}\right)$ is the posterior
distribution for $b_{j}=1$. This Bayes classifier is achieved by a DTR
$\hat{g}^{\ast}\equiv\left(\hat{g}_{1}^{\ast},\ldots,\hat{g}_{T}^{\ast}\right)$
that satisfies for $j=1,\ldots,j$,

$\displaystyle\left(\hat{g}_{1}^{\ast}\left(h_{1j}\right),\ldots,\hat{g}_{T}^{\ast}\left(h_{Tj}\right)\right)=\begin{cases}\begin{array}[]{c}\text{$\underline{d}$}_{Tj}\\\
\left(1-d_{1j},\ldots,1-d_{Tj}\right)\end{array}&\begin{array}[]{c}\mbox{if
}\pi\left(b_{j}=1\mid Z_{1},\ldots,Z_{n}\right)\geq 1/2\\\
\mbox{otherwise}\end{array}\end{cases}.$

Note that $\hat{g}^{\ast}$ is feasible in $\mathcal{G}$.

Then, using $\hat{g}^{\ast}$, the minimized risk is given by

$\displaystyle\delta\int_{Z_{1},\ldots,Z_{n}}E_{\tilde{Z}}\left[\min\left\\{\pi\left(b\left(\tilde{Z}\right)=1\mid
Z_{1},\ldots,Z_{n}\right),1-\pi\left(b\left(\tilde{Z}\right)=1\mid
Z_{1},\ldots,Z_{n}\right)\right\\}\right]d\tilde{P}^{n}$ $\displaystyle=$
$\displaystyle\frac{1}{v_{1:T}}\delta\int_{Z_{1},\ldots,Z_{n}}\sum_{j=1}^{v_{1:T}}\left[\min\left\\{\pi\left(b_{j}=1\mid
Z_{1},\ldots,Z_{n}\right),1-\pi\left(b_{j}=1\mid
Z_{1},\ldots,Z_{n}\right)\right\\}\right]d\tilde{P}^{n},$ (19)

where $\tilde{P}$ is the marginal likelihood of
$\left\\{\left\\{Y_{it}\left(\text{$\underline{d}$}_{t}\right)\right\\}_{\text{$\underline{d}$}_{t}\in\left\\{0,1\right\\}^{t}},\left\\{D_{it},X_{it}\right\\}\right\\}_{i=1,\ldots,n;t=1,\ldots,T}$
with prior $\pi(\mathbf{b})$.

For each $j=1,\ldots,v_{1:T}$, let

$\displaystyle k_{j}^{+}$
$\displaystyle=\\#\left\\{i:\tilde{Z}_{i}=\tilde{z}_{j},Y_{iT}=\frac{1}{2}\right\\},$
$\displaystyle k_{j}^{-}$
$\displaystyle=\\#\left\\{i:\tilde{Z}_{i}=\tilde{z}_{j},Y_{iT}=-\frac{1}{2}\right\\}.$

Then the posteriors for $b_{j}=1$ can be written as

$\displaystyle\pi\left(b_{j}=1\mid
Z_{1},\ldots,Z_{n}\right)=\begin{cases}\begin{array}[]{c}\frac{1}{2}\\\
\frac{\left(\frac{1}{2}+\delta\right)^{k_{j}^{+}}\left(\frac{1}{2}-\delta\right)^{k_{j}^{-}}}{\left(\frac{1}{2}+\delta\right)^{k_{j}^{+}}\left(\frac{1}{2}-\delta\right)^{k_{j}^{-}}+\left(\frac{1}{2}+\delta\right)^{k_{j}^{-}}\left(\frac{1}{2}-\delta\right)^{k_{j}^{+}}}\end{array}&\begin{array}[]{c}\mbox{if
}k_{j}^{+}+k_{j}^{-}=0\\\ \mbox{otherwise}.\end{array}\end{cases}$

Hence, the following holds:

$\displaystyle\min\left\\{\pi\left(b_{j}=1\mid
Z_{1},\ldots,Z_{n}\right),1-\pi\left(b_{j}=1\mid
Z_{1},\ldots,Z_{n}\right)\right\\}$ $\displaystyle=$
$\displaystyle\frac{\min\left\\{\left(\frac{1}{2}+\delta\right)^{k_{j}^{+}}\left(\frac{1}{2}-\delta\right)^{k_{j}^{-}},\left(\frac{1}{2}+\delta\right)^{k_{j}^{-}}\left(\frac{1}{2}-\delta\right)^{k_{j}^{+}}\right\\}}{\left(\frac{1}{2}+\delta\right)^{k_{j}^{+}}\left(\frac{1}{2}-\delta\right)^{k_{j}^{-}}+\left(\frac{1}{2}+\delta\right)^{k_{j}^{-}}\left(\frac{1}{2}-\delta\right)^{k_{j}^{+}}}$
$\displaystyle=$
$\displaystyle\frac{\min\left\\{1,\left(\frac{\frac{1}{2}+\delta}{\frac{1}{2}-\delta}\right)^{k_{j}^{+}-k_{j}^{-}}\right\\}}{1+\left(\frac{\frac{1}{2}+\delta}{\frac{1}{2}-\delta}\right)^{k_{j}^{+}-k_{j}^{-}}}$
$\displaystyle=$
$\displaystyle\frac{1}{1+a^{\left|k_{j}^{+}-k_{j}^{-}\right|}},\mbox{ where
}a=\frac{1+2\delta}{1-2\delta}>1.$ (20)

Since

$\displaystyle k_{j}^{+}-k_{j}^{-}$
$\displaystyle=\sum_{i:\tilde{Z}_{i}=\tilde{z}_{j}}2Y_{Ti},$

plugging (20) into (19) yields

$\displaystyle(\ref{eq:proof-lower
bound-1})=\frac{1}{v_{1:T}}\delta\sum_{j=1}^{v_{1:T}}E_{\tilde{P}^{n}}\left[\frac{1}{1+a^{\left|\sum_{i:\tilde{Z}_{i}=\tilde{z}_{j}}2Y_{iT}\right|}}\right]$
$\displaystyle\geq\frac{\delta}{2v_{1:T}}\sum_{j=1}^{v_{1:T}}E_{\tilde{P}^{n}}\left[\frac{1}{a^{\left|\sum_{i:\tilde{Z}_{i}=\tilde{z}_{j}}2Y_{iT}\right|}}\right]$
$\displaystyle\geq\frac{\delta}{2v_{1:T}}\sum_{j=1}^{v_{1:T}}a^{-E_{\tilde{P}^{n}}\left|\sum_{i:\tilde{Z}_{i}=\tilde{z}_{j}}2Y_{iT}\right|},$

where $E_{\tilde{P}^{n}}\left[\cdot\right]$ is the expectation with respect to
the marginal likelihood of

$\displaystyle\left\\{\left\\{Y_{it}\left(\text{$\underline{d}$}_{t}\right)\right\\}_{\text{$\underline{d}$}_{t}\in\left\\{0,1\right\\}^{t}},D_{it},X_{it}\right\\}_{i=1,\ldots,n;t=1,\ldots,T}.$

The first inequality follows by $a>1$, and the second inequality follows by
Jensen’s inequality. Given our prior distribution for $\mathbf{b}$, for each
$\text{$\underline{d}$}_{T}\in\left\\{0,1\right\\}^{T}$, the marginal
distribution of $Y_{iT}\left(\underline{d}_{T}\right)$ is
$P\left(Y_{iT}\left(\text{$\underline{d}$}_{T}\right)=1/2\right)=P\left(Y_{iT}\left(\text{$\underline{d}$}_{T}\right)=-1/2\right)=1/2$
if there exist $\text{$\underline{d}$}_{Tj}$ among
$\text{$\underline{d}$}_{T1},\ldots,\text{$\underline{d}$}_{Tv_{1:T}}$ such
that $\text{$\underline{d}$}_{Tj}=\text{$\underline{d}$}_{T}$; otherwise,
$P\left(Y_{iT}\left(\text{$\underline{d}$}_{T}\right)=0\right)=1$. Thus, we
have

$\displaystyle
E_{\tilde{P}^{n}}\left|\sum_{i:\tilde{Z}_{i}=\tilde{z}_{j}}2Y_{iT}\right|$
$\displaystyle=E_{\tilde{P}^{n}}\left|\sum_{i:\tilde{Z}_{i}=\tilde{z}_{j}}2Y_{iT}\left(\text{$\underline{d}$}_{Tj}\right)\right|$
$\displaystyle=\sum_{k=0}^{n}\left(\begin{array}[]{c}n\\\
k\end{array}\right)\left(\frac{1}{v_{1:T}}\right)^{k}\left(1-\frac{1}{v_{1:T}}\right)^{n-k}E\left|B\left(k,\frac{1}{2}\right)-\frac{k}{2}\right|,$

where $B\left(k,1/2\right)$ is the binomial random variable with parameters
$k$ and $1/2$. By the Cauchy-Schwarz inequality, it follows that

$\displaystyle
E\left|B\left(k,\frac{1}{2}\right)-\frac{1}{2}\right|\leq\sqrt{E\left(B\left(k,\frac{1}{2}\right)-\frac{k}{2}\right)^{2}}=\sqrt{\frac{k}{4}}.$

Thus, we obtain

$\displaystyle
E_{\tilde{P}^{n}}\left|\sum_{i:\tilde{Z}_{i}=\tilde{z}_{j}}2Y_{iT}\right|$
$\displaystyle\leq\sum_{k=0}^{n}\left(\begin{array}[]{c}n\\\
k\end{array}\right)\left(\frac{1}{v_{1:T}}\right)^{k}\left(1-\frac{1}{v_{1:T}}\right)^{n-k}\sqrt{\frac{k}{4}}$
$\displaystyle=E\sqrt{\frac{B\left(n,\frac{1}{v_{1:T}}\right)}{4}}$
$\displaystyle\leq\sqrt{\frac{n}{4v_{1:T}}},$

where the last inequality follows by Jensen’s inequality. Hence, the Bayes
risk is bounded from below by

$\displaystyle\frac{\delta}{2}a^{-\sqrt{\frac{n}{4v_{1:T}}}}$
$\displaystyle\geq\frac{\delta}{2}\exp\left\\{-\left(a-1\right)\sqrt{\frac{n}{4v_{1:T}}}\right\\}$
$\displaystyle=\frac{\delta}{2}\exp\left\\{-\frac{4\delta}{1-2\delta}\sqrt{\frac{n}{4v_{1:T}}}\right\\},$

where the inequality follows from the fact that $1+x\leq e^{x}$ for any $x$.
This lower bound on the Bayes risk has the slowest convergence rate when
$\delta$ is set to be proportional to $n^{-1/2}$. Specifically, letting
$\delta=\sqrt{v_{1:T}/n}$, we have

$\displaystyle\frac{\delta}{2}\exp\left\\{-\frac{4\delta}{1-2\delta}\sqrt{\frac{n}{4v_{1:T}}}\right\\}$
$\displaystyle=\frac{1}{2}\sqrt{\frac{v_{1:T}}{n}}\exp\left\\{-\frac{2}{1-2\delta}\right\\}\geq\frac{1}{2}\sqrt{\frac{v_{1:T}}{n}}\exp\left(-4\right)\mbox{
if }1-2\delta\geq\frac{1}{2}.$

The condition $1-2\delta\geq 1/2$ is equivalent to $n\geq 16v_{1:T}$.
Multiplying the lower bound by $M_{T}$ gives

$\displaystyle\sup_{P\in{\cal
P}\left(M,\kappa,\mathcal{G}\right)}E_{P^{n}}\left[W_{{\cal
G}}^{\ast}-W\left(\hat{g}\right)\right]$
$\displaystyle\geq\frac{1}{2}\exp\left(-4\right)M_{T}\sqrt{\frac{v_{1:T}}{n}}$

for all $n\geq 16v_{1:T}$.

The proof is valid irrespective of whether Assumption 3.1 holds for a pair
$(P,\mathcal{G})$ with any $P\in\mathcal{P}(M,\kappa,\mathcal{G})$ or not. ∎

###### Proof of Theorem 3.5.

The result immediately follows by setting

$\displaystyle t=\underset{s\in\left\\{1,\ldots,T\right\\}}{\mathop{\rm
arg\leavevmode\nobreak\ max}\limits}\gamma_{s}M_{s}\sqrt{\frac{v_{1:s}}{n}}$

in the statement of Lemma A.6. ∎

In the rest of this section, We derive uniform upper bounds on the worst-case
average welfare-regrets of the two DEWM methods in the case where estimated
propensity scores are used instead of true ones.

###### Proof of Theorem 5.1 (i):.

Let $P\in\mathcal{P}_{e}\cap\mathcal{P}(M,\kappa,\mathcal{G})$ be fixed.
Define $\hat{W}_{nt}(\text{$\underline{g}$}_{t})\equiv
n^{-1}\sum_{i=1}^{n}\hat{w}_{t}^{S}(Z_{i},\text{$\underline{g}$}_{t})$ and
$\hat{W}_{n}\left(g\right)\equiv\sum_{t=1}^{T}\hat{W}_{nt}(\text{$\underline{g}$}_{t})$,
which are estimators of $W_{t}(\text{$\underline{g}$}_{t})$ and
$W\left(g\right)$, respectively. It follows for any $g\in{\cal G}$ that

$\displaystyle W\left(g\right)-W\left(\hat{g}_{e}^{S}\right)$
$\displaystyle\leq
W_{n}\left(g\right)-\hat{W}_{n}\left(g\right)-W_{n}\left(\hat{g}_{e}^{S}\right)+\hat{W}_{n}\left(\hat{g}_{e}^{S}\right)$
$\displaystyle+W\left(g\right)-W\left(\hat{g}_{e}^{S}\right)+W_{n}\left(\hat{g}_{e}^{S}\right)-W_{n}\left(g\right)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{\text{$\underline{d}$}_{t}\in\left\\{0,1\right\\}^{t}}\left[\left(\frac{\gamma_{t}Y_{it}\cdot