Estimation of Optimal Dynamic Treatment Assignment Rules under Policy Constraints

Estimation of Optimal Dynamic Treatment Assignment Rules under Policy Constraints

\setstretch{1.2}

\setstretch{1.5}

Introduction

Many policies involve dynamics in their treatment assignments. Some policies assign a series of treatments to each individual across multiple stages, such as job training programs consisting of multiple stages Lechner_2009,Rodriguez_et_al_2018. Some policies are characterized by when to start/stop consecutive treatment assignment, such as unemployment insurance programs that reduce benefit level after a certain duration Meyer_1995,Kolsrud_et_al_2018. Examples of dynamic treatment assignments also include sequential medical interventions, educational programs, and marketing strategies.

When implementing a dynamic policy, policymakers aim to optimize treatment assignments across multiple stages to maximize its social impact. The effects of treatment at each stage are usually heterogeneous with respect to past treatments, intermediate outcomes, and individual characteristics. Hence, to maximize its social impact, treatment assignment to each individual at each stage should depend on the individual's accumulated information up to the corresponding stage.\footnote{ For example, in the context of a sequential job training program, the interest is in which training regimen to be assigned to each individual at each stage depending on their history of prior training participation, associated labor outcomes, and other observed characteristics. An important question in the unemployment insurance policy context is when and to whom to reduce the insurance level, given a recipient's characteristics and past effort toward a job search. }

This paper proposes a statistical decision approach to solve dynamic treatment choice problems using data from an experimental or quasi-experimental study. We assume dynamic unconfoundedness Robins_1997, meaning that the treatment assignment at each stage is independent of current and future potential outcomes given the history of treatment assignments and state variables. Under this assumption, we construct an approach to estimate the optimal dynamic treatment regime (DTR)\footnote{Borrowing from the terminology of statistics literature, we call the dynamic treatment assignment rule DTR.} building upon the concept of empirical welfare maximization (EWM) Kitagawa_Tetenov_2018a. We call it the dynamic empirical welfare maximization (DEWM). The DEWM approach estimates the optimal DTR by maximizing empirical welfare, a sample mean of propensity-score-weighted outcomes, over a pre-specified class of feasible DTRs. True (estimated) propensity scores are used in the experimental (observational) data setting.

When designing public policy, considering external constraints such as interpretability or fairness in treatment allocation is crucial. The DEWM approach offers favorable features to accommodate exogenous policy constraints by restricting the class of feasible DTRs. Moreover, it can be applied to various dynamic treatment choice problems, such as optimal starting and stopping problems, by properly constraining the class of DTRs.

We present two approaches to estimate the optimal DTR. The first estimates the optimal DTR through backward induction, which solves the treatment choice problem from the final to the first stage, supposing at each stage that the optimal treatments are chosen in future stages. The second estimates the optimal DTR simultaneously across all stages, solving the empirical welfare maximization problem at once for the entire DTR.\footnote{Without specifying the direct and indirect effects of the treatment on future outcomes, each approach accounts for these effects within its EWM process.}

We reveal that the two approaches complement each other. The backward estimation method is computationally efficient; however, its consistency is ensured only when a pre-specified class of DTRs contains the first-best rule that assigns the best treatment for any history at each stage (except the first stage). Conversely, the simultaneous estimation method consistently estimates the optimal DTR on a pre-specified class of DTRs, irrespective of the feasibility of the first-best rule, at the cost of computational efficiency.

In practical terms, dynamic policies often impose budget or capacity constraints on treatment allocation over time. An ideal DTR should allocate limited resources effectively across stages to maximize welfare. We extend the simultaneous estimation method to problems with intertemporal budget/capacity constraints. We show that the resulting DTR approximately maximizes welfare while satisfying these constraints.

We evaluate the statistical properties of the DEWM approaches in terms of average welfare regret.\footnote{The average welfare regret 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 regret of the DTR estimated by each of the backward-induction and simultaneous optimization methods. The resulting bounds depend on the sample size $n$ and a measure of complexity of the class of DTRs. Our main theorem shows that the average welfare regret for each method converges to zero at rate $n^{-1/2}$ in the experimental data setting. Furthermore, we show that this convergence rate is optimal.\footnote{To my knowledge, this is the first work to formally show the minimax rate optimality of welfare regrets in estimating optimal DTRs.} For the budget/capacity constrained problem, we also analyze the excess implementation cost of the estimated DTR relative to 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.

Related Literature

This paper contributes to the literature on statistical decision of treatment choice, although much of existing work focuses on the static problem.\footnote{A partial list of works in that literature includes Manski_2004, Dehejia_2005, Hirano_Porter_2009, Stoye_2009,Stoye_2012, Bhattacharya_Dupas_2012, Chamberlain_2012, Tetenov_2012, Kitagawa_Tetenov_2018a, Athey_Wager_2020, Kitagawa_Tetenov_2018b, Mbakop_Tabord-Meehan_2019, and kitagawa_et_al_2021.} Policy learning methods by Kitagawa_Tetenov_2018a, Athey_Wager_2020, and Mbakop_Tabord-Meehan_2019 build on the similarity of the empirical welfare maximizing treatment choice and the empirical risk-minimizing classification. Athey_Wager_2020 apply doubly robust estimators to static policy learning, and show that an $n^{-1/2}$-asymptotic upper bound on regret can be achieved even in the observational data setting.

In the dynamic treatment framework, Han_2018 relaxes the sequential randomization assumption, allowing for noncompliance, and studies point identification of the average dynamic treatment effects and optimal non-additive DTR. Han_2019 proposes a method to characterize the sharp partial ordering of the counterfactual welfares of DTRs in an instrumental variable setting. Heckman_Navarro_2007 and Heckman_et_al_2016 use exclusion restrictions to identify the dynamic treatment effect, but their focus do not extend to the identification of the optimal DTRs.

Estimation of the optimal DTRs has been widely studied in the biostatistics and statistics literature.\footnote{Chakraborty_Moodie_2013, Chakraborty_Murphy_2014, Laber_et_al_2014, and Tsiatis_et_al_2019 review the developments in this field.} Some dominant approaches exist, such as G-estimation Robins_1989,Robins_et_al_1992 and Q-learning Murphy_2005,Moodie_et_al_2012. A potential drawback of these approaches is the risk of misspecification of the models relevant to the counterfactual outcomes. By contrast, the DEWM approach does not need to specify any model relevant to the counterfactual outcomes.

Building on the similarity between treatment choice and classification, Zhao_et_al_2015 develop estimation methods for the optimal DTRs using the support vector machine with propensity score weighted outcomes. Their approach is computationally efficient because it uses a convex surrogate loss. However, it cannot accommodate exogenous constraints on a class of DTRs.\footnote{The hinge loss approach in Zhao_et_al_2015 loses consistency and computational efficiency, for example, under budget or fairness constraints. Moreover, Laha_et_al_2024 show that using a smooth convex surrogate loss or hinge loss in the simultaneous maximization approach can fail to consistently estimate the optimal DTRs.} In contrast, our focus lies on estimating the optimal DTRs with exogenous constraints on the class of DTRs, a scenario more commonly encountered in public policy-making.\footnote{In the static setting, kitagawa_et_al_2021 show that the surrogate hinge loss approach has consistency in constrained treatment choice problems, which could be extended to our dynamic setting. Their main result for consistency applies when constraints are imposed on the level set of a treatment rule, whereas we consider more general constraints on the functional form of treatment rules.} Beyond the results of Zhao_et_al_2015, we reveal a tradeoff between imposing constraints on the dynamic treatment choice and the consistency of the backward-induction approach, and formally show the minimax rate optimality of the proposed methods in the context of dynamic treatment choice.

This work is also related to the literature on optimal stopping van_1976,Rust_1987,Jacka_1991,Goel_et_al_2017,Nie_et_al_2019. Most works in the literature rely either on a known stochastic model van_1976,Rust_1987,Jacka_1991 or on a generator of system dynamics Goel_et_al_2017.\footnote{Nie_et_al_2019 propose doubly robust estimation method for the optimal stopping/starting problem.} The methods proposed in our study can estimate the optimal stopping/starting policies from batch data by properly specifying the class of DTRs.

Finally, the dynamic treatment framework we study differs from the bandit problem, for example, studied by Kock_Thyrsgaard_2018. In the bandit problem, different individuals receive treatment at different stages. By contrast, in our dynamic framework, the same individuals progress through different stages and receive sequential treatment interventions across these stages. Additionally, in bandit problems, the treatment effect is explored and exploited across sequential stages, whereas, in our framework, the effects of sequential treatments are estimated before the allocation task.\footnote{The bandit problem is an online learning problem, whereas we study an off-line learning problem.}\footnote{Kallus_2020 study the bandit problem with DTRs, considering the problem of developing and exploiting the optimal DTR in an online setting.}

Structure of the Paper

The remainder of this paper proceeds as follows. Section (ref) defines the dynamic treatment choice problem. Section (ref) presents the two DEWM methods and shows their statistical properties. Section (ref) extends the simultaneous estimation method to accommodate intertemporal budget/capacity constraints. Section (ref) proposes estimation methods for the observational data setting. Section (ref) shows the results of a simulation study. In Section (ref), we apply the proposed methods 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 teacher aide in multiple grades. Section (ref) concludes this paper.

Setup

Section (ref) introduces the dynamic treatment framework, following Robins's dynamic counterfactual outcomes framework Robins_1986,Robins_1997. Subsequently, we define the dynamic treatment choice problem in Section (ref). In this study, we denote by $E_{P}\left[\cdot\right]$ the expectation with respect to a distribution function $P$.

Dynamic Treatment Framework

We suppose $T$ $(T < \infty)$ 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$. At the end of each stage $t$, we observe an outcome $Y_{t}$. Let $X_{t}$ be a $k$-dimensional vector of covariates observed before treatment assignment at stage $t$. The distribution of $X_{t}$ may depend on past treatments, outcomes, and covariates. $X_{1}$ represents pre-treatment information, containing individuals' demographic characteristics observed before policy implementation. Throughout this paper, for any time-dependent object $A_{t}$, we denote by $\text{\ensuremath{\text{\ensuremath{\underline{A}}}}}_{t}\equiv \left(A_{1},\ldots,A_{t}\right)$ a history of the object up to stage $t$, and denote by $\text{\ensuremath{\underline{A}}}_{s:t} \equiv \left(A_{s},\ldots,A_{t}\right)$, for $s\leq t$, a partial history of the object from stage $s$ up to stage $t$. For example, the treatment history up to stage $t$ is denoted by $\text{\ensuremath{\underline{D}}}_{t}=\left(D_{1},\ldots,D_{t}\right)$. Let $Z \equiv \left(\underline{D}_T,\underline{Y}_T,\underline{X}_T\right)$ be the vector containing all observed variables. We define the history in stage $t$ by $H_{t} \equiv \left(\underline{D}_{t-1},\underline{Y}_{t-1},\underline{X}_t\right)$, which is available information for the policymaker when she chooses a treatment assignment at stage $t$. Note that $H_{s}\subseteq H_{t}$ for any $s\leq t$, and $H_{1}=\left(X_{1}\right)$. We denote the support of $H_{t}$ and $Z$ by ${\cal H}_{t}$ and $\mathcal{Z}$, respectively.

We illustrate the dynamic treatment framework with an example of a sequential job training from Rodriguez_et_al_2018. They study the effect of sequential training in Chile's “Franquicia Tributaria” program, where a worker can sequentially participate in multiple training sessions. They consider two stages ($T=2$) with “$D_1=1$” and “$D_2=1$” indicating participation in the first and second stages, respectively. $Y_1$ and $Y_2$ are the monthly salaries observed after training for each stage. $X_1$ includes age, gender, initial wage, and education variables, while there are no time-varying covariates $X_2$.

To formalize our results, we employ the framework of dynamic potential outcomes Robins_1986,Murphy_2003. Let $Y_{t}\left(\text{\ensuremath{\underline{d}}}_{t}\right)$ denote the potential outcome of $\underline{d}_t \in \{0,1\}^t$ at stage $t$, representing the outcome for stage $t$ that is realized when the history of treatment up to stage $t$ coincides with $\underline{d}_{t}$. We implicitly assume that the potential outcomes are not influenced by future treatments, that is, a no-anticipation condition. Given that the covariates $X_t$ may be influenced by past treatments, we define potential covariates as $X_t(\underline{d}_{t-1})$ for each $t \geq 2$ and $\underline{d}_{t-1} \in \{0,1\}^{t-1}$. We denote $X_{1}(\underline{d}_{0})=X_1$ when $t=1$. The observed outcomes and covariates are defined as $Y_t \equiv Y_t(\underline{D}_t)$ and $X_t \equiv X_t(\underline{D}_{t-1})$, respectively. Denoting $\underline{Y}_{t}(\underline{d}_{t}) \equiv (Y_1(d_1),\ldots,\underline{Y}_{t}(\underline{d}_{t}))$ and $\underline{X}_{t}(\underline{d}_{t-1}) \equiv (X_1,X_2(d_1),\ldots,\underline{X}_{t}(\underline{d}_{t-1})$, a vector $H_t(\underline{d}_{t-1}) \equiv \left(\underline{d}_{t-1},\underline{Y}_{t-1}(\underline{d}_{t-1}),\underline{X}_{t}(\underline{d}_{t-1})\right)$ represents the potential history that is realized when prior treatments are $\underline{d}_{t-1}$. We denote $H_{1}(\underline{d}_{0}) = H_1$ when $t=1$. The observed history is defined as $H_{t} \equiv H_t(\underline{D}_{t-1})$. Let $P$ be the distribution of all underlying variables $\left(\underline{D}_T,\{\underline{Y}_{T}(\underline{d}_{T})\}_{\underline{d}_{T} \in \{0,1\}^{T}},\{\underline{X}_{T}(\underline{d}_{T-1})\}_{\underline{d}_{T-1} \in \{0,1\}^{T-1}}\right)$.

From an experimental or observational study, we observe $Z_{i}\equiv \left(D_{it},Y_{it},X_{it}\right)_{t=1}^{T}$ for individuals $i=1,\ldots,n$, where $Y_{it} \equiv Y_{it}(\underline{D}_{it})$ and $X_{it} \equiv X_{it}(\underline{D}_{i,t-1})$ with $Y_{it}(\underline{d}_{t})$ and $X_{it}(\underline{d}_{t-1})$ being a potential outcome and covariates for individual $i$ at stage $t$. We suppose that the vectors of underlying random variables $V_i \equiv \left(\underline{D}_{iT},\{\underline{Y}_{iT}(\underline{d}_{T})\}_{\underline{d}_{T} \in \{0,1\}^{T}},\{\underline{X}_{iT}(\underline{d}_{T-1})\}_{\underline{d}_{T-1} \in \{0,1\}^{T-1}}\right)$, $i=1,\ldots,n$, are independent and identically distributed (i.i.d) with the distribution $P$. We denote by $P^{n}$ the joint distribution of $\left\{V_i:i=1,\ldots,n\right\}$.

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 in the experimental study but are unknown in the observational study. These settings are considered in Sections (ref)-(ref) and Section (ref), respectively.

In this study, we suppose that the following assumptions hold.

Assumption (ref) is known as a dynamic unconfoundedness assumption or sequential/dynamic conditional independence assumption elsewhere, and 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 current and future potential outcomes and future covariates conditional on the history up to that point. This is typically satisfied in sequential randomization experiments. In observational studies, this assumption is often controversial but can be satisfied if a sufficient set of confounders is available. Assumption (ref) is a common assumption in the literature on statistical treatment choice Manski_2004,Stoye_2009,Kitagawa_Tetenov_2018a.

Dynamic Treatment Choice Problem

We aim to develop methods to estimate the optimal DTRs from experimental or observational data with sequential treatment assignment. We denote a treatment rule for each stage $t$ by $g_{t}:{\cal H}_{t}\mapsto\left\{ 0,1\right\} $, a map from the history up to stage $t$ to a 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 policymakers in selecting treatment for each individual at each stage based on their history up to that point.

We define the counterfactual outcome of a sequence of treatment rules $\underline{g}_t$ for each stage $t$ as $\widetilde{Y}_t\left(\underline{g}_t \right) \equiv \sum_{\underline{d}_{t} \in \{0,1\}^t} Y_t(\underline{d}_t)\cdot \prod_{s=1}^{t}1\left\{g_s\left(H_{s}(\underline{d}_{s-1})\right) = d_s\right\}$. This is the counterfactual outcome for stage $t$ that is realized when the sequential treatment assignment up to stage $t$ follows the sequence of treatment rules $\underline{g}_t$.

We then define the welfare of a DTR $g$ by the population mean of a weighted sum of outcomes as follows:

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 policymaker targets a time-discounted welfare, the weight at each stage is $\gamma_{t}=\gamma^{T-t}$ with $\gamma$ being a time-discount factor that lies in $\left(0,1\right)$. If the policymaker targets the outcome for the last stage only, $\gamma_{T}=1$ and $\gamma_{t}=0$ for all $t \neq T$.

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

We suppose that the policymaker chooses a DTR from a pre-specified class of feasible DTRs, denoted 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\}$). Therefore, the ultimate goal of the analysis is to choose an optimal DTR that maximizes the welfare function $W\left(\cdot\right)$ over $\mathcal{G}$. \footnote{ In the context of sequential job training Lechner_2009,Rodriguez_et_al_2018, $g_t(h_t)$ decides whether an individual with history $h_t$ should receive job training at stage $t$. The history $h_t$ may include information on past trainings, pre-training and intermediate wages, and educational backgrounds. When $Y_t$ represents the wage at stage $t$, the optimal DTR is the optimal sequence of treatment rules for determining participation in job training at each stage, to maximize the population mean of the total weighted wages $W(g)$. }

In this study, we constrain the complexity of the class of feasible DTRs in terms of VC-dimension.\footnote{The definition of VC-dimension is given in Definition (ref) in Appendix along with some examples.} 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$.

This assumption restricts the complexity of the class of DTRs $\mathcal{G}$ by restricting the class of feasible treatment rules $\mathcal{G}_{t}$ for each specific stage. By restricting the complexity, we can select a DTR that is simple to explain/interpret DTR, and can keep estimated DTRs from overfitting the data. Although Assumption (ref) excludes nonparametric classes of $\mathcal{G}_t$, our framework can accommodate nonparametric approaches by appropriately controlling the growth rate of VC-dimension with the sample size $n$.

We can incorporate arbitrary exogenous policy constraints for ethical or political reasons into DTRs by specifying the form of $\mathcal{G}_{t}$ for each $t$.\footnote{Although a treatment rule $g_{t}(h_t)$ depends on the full-history of covariates $\underline{x}_{t}$ from stage 1 to t, we can also consider treatment rules that do not depend on the past covariates $\underline{x}_{t-1}$ by restricting the class $\mathcal{G}_t$ such that for any $g_t \in \mathcal{G}_t$, $g_{t}(h_t) = g_{t}(h_{t}^\prime)$ for any $h_t$ and $h_{t}^{\prime}$ such that $h_{t} \backslash \underline{x}_{t-1} = h_{t}^{\prime} \backslash \underline{x}_{t-1}^{\prime}$. Similar constraints can also be imposed for the treatment history $\underline{d}_t$ and outcome history $\underline{y}_{t}$.} Some examples of practically relevant classes of DTRs are linear treatment rules and decision tree rules.

Aside from the constraint on the functional form, we can specify various dynamic treatment choice problem by restricting the intertemporal relationship of treatment rules across stages. Some examples are as follows.

The VC-dimension of an additionally restricted class does not exceed that of the original class.

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

When $\mathcal{G}$ is structurally constrained, Assumption (ref) is weaker than a common overlap condition that requires the overlap $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$.\footnote{For example, in the optimal stopping problem, Assumption (ref) does not require $e_{t}(1,h_{t})>0$ for any $h_t$ such that $d_s$ in $h_t$ is equal to $0$ for some $s < t$.} This assumption also guides how to design experiments given $\mathcal{G}$; that is, in an experiment, the treatment $d_t$ does not need to be assigned to individuals with any $h_t$ such that $d_t$ is not achievable by $g_t(h_t)$ for any $g_t \in \mathcal{G}_t$ (i.e., $d_t \neq g_{t}(h_t)$ for any $g_t \in \mathcal{G}_t$).\footnote{For example, in the optimal stopping problem, $d_t = 1$ does not need to be assigned to any individuals who were already untreated (i.e., individuals with $d_s = 0$ for some $s < t$).} Assumption (ref) is satisfied in the experimental data setting, for example, when the treatment $D_t$ is randomly assigned without any dependence on the history $H_t$.

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

We consider estimating the optimal DTR that maximizes the welfare $W(\cdot)$ over $\mathcal{G}$ from the sample $\left\{ Z_{i}:i=1,\ldots,n\right\} $. In the subsequent section, we present two methods to estimate the optimal DTR, and show their statistical properties.

Dynamic Empirical Welfare Maximization

This section proposes two DEWM methods. One method employs backward induction to solve the dynamic treatment choice problem sequentially from the final to initial stage. The other method involves the simultaneous maximization of $W\left(\cdot \right)$ over the entire class of DTRs $\mathcal{G}$ across all stages. The backward-induction approach is computationally efficient; however, we will see that it may not consistently estimate the optimal DTR when $\mathcal{G}_{t}$ does not contain the first-best treatment rule for all $t \geq 2$. By contrast, the simultaneous maximization method can consistently estimate the optimal DTR irrespective of whether $\mathcal{G}_{t}$ contains the first-best rule at each stage $t$, though it is computationally less efficient.\footnote{It is worth noting that our study, focused on the consistent estimation of the optimal DTR, differs from the literature on “dynamic (in)consistency” in economics Epstein_et_al_2003,Hansen_Sargent_2022, because the notions of consistency are different between our work and works regarding “dynamic (in)consistency” in economics.} We explain the backward-induction and simultaneous-maximization methods in Sections (ref) and (ref), respectively.

Backward Dynamic Empirical Welfare Maximization

We first explain the backward-induction approach. To present the idea, we here suppose that the generative distribution function $P$ is known and the pair $\left(P,{\cal G}\right)$ satisfies Assumptions (ref) and (ref).

The backward-induction approach in the population problem proceeds as follows. First, for the final stage $T$, we obtain

where $Q_{T}\left(h_{T},d_{T}\right)\equiv E_{P}\left[\gamma_{T}Y_{T}\mid H_{T}=h_{T},D_{T}=d_{T}\right]$ is the conditional mean of the weighted final outcome $\gamma_{T}Y_{T}$ given the history $h_{T}$ and treatment $d_T$.

Then, recursively, from $t=T-1$ to $1$, we obtain

with $Q_{t}\left(h_{t},d_{t}\right) \equiv E_{P}\left[\gamma_{t}Y_{t}+Q_{t+1}\left(H_{t+1},g_{t+1}^{\ast}(H_{t+1})\right)\mid H_{t}=h_{t},D_{t}=d_{t}\right].$ The function $Q_{t}\left(h_{t},d_{t}\right)$ is the action value function for stage $t$ and represents the expected welfare that is realized when the history is $h_{t}$, the treatment at stage $t$ is $d_t$, and the future treatments follow $(g_{t+1}^{\ast},\ldots,g_{T}^{\ast})$.

Given the propensity scores $\left\{ e_{t}\left(d_{t},h_{t}\right)\right\} _{t=1}^{T}$ and under Assumption (ref), $E_{P}\left[Q_{t}\left(H_{t},g_{t}(H_t)\right)\right]$ can be identified as

where

Hence, the objective function $E_P[Q_t(H_t,g_t)]$ can be expressed by the observables only.

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

Then, recursively, from $t=T-1$ to $1$, the method estimates $g_{t}^{\ast}$ by

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

The resulting DTR $\hat{g}^{B}$ does not necessarily have consistency to the optimal one, $g_{opt}^{\ast} \in \mathop{\rm arg~max}\limits_{g \in \mathcal{G}} W(g)$, unless the class $\mathcal{G}_t$ of treatment rules for each $t\geq 2$ contain the first-best rule that globally maximizes $E_{p}[Q_t(H_t,g_t(H_t))]$ over all measurable functions of $g_t$. For any $s<t$, let

which is the outcome in stage $t$ that is realized when the treatment assignments from stage $1$ to stage $s$ are fixed to $\underline{d}_{s}$, and the subsequent sequential treatment assignment follows $\underline{g}_{(s+1):t}$.\footnote{We denote $\widetilde{Y}_{t}\left(\underline{d}_{t},\underline{g}_{(t+1):t}\right) = Y_{t}\left(\underline{d}_{t}\right)$ when $s=t$.} To ensure 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.

We refer to $g_{t,FB}^{\ast}$, which satisfies Assumption (ref), as the first-best treatment rule at stage $t$. The first-best rule $g_{t,FB}^{\ast}$ always chooses the best treatment for any history $h_t$ given that the first-best rules are followed in the future stages. Assumption (ref) 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 rule. Note that there is a trade-off between the simplicity of a class of DTRs and the feasibility of Assumption (ref); while a simpler class of DTRs is often preferable in practice, it is less likely to contain the first-best rule.\footnote{A tension also exists between restrictions on information sets versus restrictions on functional classes. Imposing functional restrictions can restrict the information set, potentially causing dynamic inconsistency.} Assumption (ref) does not require the class of treatment rules for the first stage $\mathcal{G}_1$ to contain the first-best.

When the first-best rule is not attainable in $\mathcal{G}_{t}$ for some $t\geq 2$, the solution $g_{s}^{\ast}$ of the backward induction for $s\leq t$ does not necessarily correspond to the optimal treatment rule. We illustrate this issue with a simple example in the following remark (and also in the simulation study in Section (ref)).

Simultaneous Dynamic Empirical Welfare Maximization

The second approach is a sample analogue of the entire welfare maximization problem ((ref)). We refer to the proposed method as the simultaneous DEWM method, as it simultaneously estimates the optimal treatment rules across all stages. The method estimates the optimal DTR through the maximization of the sample analogue of ((ref)):

where $\underline{g}_{t} \equiv (g_1,\ldots,g_{t})$ is the vector of treatment rules up to stage $t$ and

In equation ((ref)), $n^{-1}\sum_{i=1}^{n}w_{t}^{S}(Z_{i},\text{\ensuremath{\underline{g}}}_{t})$ corresponds to the sample analogue of the $t$-th term in ((ref)). 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 (ref) below shows that this method can consistently estimate the optimal DTR on $\mathcal{G}$ even when $\mathcal{G}_t$ does not contain the first-best rule for some $t$ (i.e., Assumption (ref) does not hold).

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 average welfare regret, that is, the average welfare loss relative to the maximum feasible welfare $W_{\mathcal{G}}^{\ast}$. Following Kitagawa_Tetenov_2018a, 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]$, where ${\cal P}\left(M, \kappa, \mathcal{G}\right)$ is a class of distributions of $\left(\underline{D}_T,\{\underline{Y}_{T}(\underline{d}_{T})\}_{\underline{d}_{T} \in \{0,1\}^{T}},\{\underline{X}_{T}(\underline{d}_{T-1})\}_{\underline{d}_{T-1} \in \{0,1\}^{T-1}}\right)$ that satisfy Assumptions (ref), (ref), and (ref) 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$.

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, the estimated DTR tends to overfit the data (the distribution of welfare regret becomes more dispersed).\footnote{ When the VC-dimension $v_t$ increases with the sample size $n$, Theorem (ref) implies that the rate of convergence of the welfare regrets depends on this growth rate.} The upper bound for the backward DEWM method is greater than that for the simultaneous DEWM method, though neither bound is necessarily sharp. Technically, the difference between these bounds arises from the property of the sequential estimation of the backward DEWM, 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}$:

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

This theorem, along with Theorem (ref), shows that both $\hat{g}^{S}$ and $\hat{g}^{B}$ are minimax rate optimal over the class of DGPs $\mathcal{P}\left(M, \kappa, \mathcal{G}\right)$. Optimality here means that the convergence rates of the upper bounds of the worst-case average welfare regrets in Theorem (ref) align with the convergence rate of the universal lower bound concerning the sample size $n$. The convergence rate is also optimal with respect to the VC-dimension $v_{t}$ for each $t$. In Theorem (ref), 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, which is due to the simplicity of the derivation of the lower bound in its proof.

Budget/Capacity Constraints

We consider budget/capacity constraints that limit the proportion of the population receiving treatment. In dynamic treatment policy, these constraints may be imposed intertemporally, meaning that they affect treatment assignment across multiple stages. A policymaker faces an intertemporal budget/capacity constraint when managing a budget that spans across multiple stages or a fixed amount of treatment to distribute over multiple stages.\footnote{In the static setting, Bhattacharya_Dupas_2012 propose a method to estimate the optimal treatment rule under a budget constraint. As its application, they estimate the optimal allocation policy for subsidies of anti-malaria bed nets under budget constraints.} For instance, the job training program studied by Rodriguez_et_al_2018 subsidizes training courses at off-site providers across multiple stages, where, when the subsidy budget is limited, the program faces intertemporal budget constraints, limiting the number of individuals participating in training across multiple stages.

Similar to the definition of $\widetilde{Y}_{t}\left(\underline{g}_{t}\right)$, we define a counterfactual history as

which is the counterfactual history in stage $t$ that is realized when the prior treatments $\underline{d}_{t-1}$ are decided by $\underline{g}_{t-1}$. We denote $\widetilde{H}_{1}\left(\underline{g}_0\right) = H_1$ when $t=1$. We suppose that the policymaker faces the following $B$ constraints:

where $K_{tb}\in\left[0,1\right]$ and $C_{b}\geq0$. As a scale normalization, we assume $\sum_{t=1}^{T}K_{tb}=1$ for all $b$. The left-hand side of equation ((ref)) represents the implementation cost of the DTR $g$, where 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 a temporal one. In the context of the two-stage job training program with an intertemporal budget constraint ($B=1$), $k_{11}$ and $k_{21}$ represent costs of job training for the first and second stages, respectively, and $C_{1}$ represents the intertemporal budget of the program.\footnote{In reality, the time periods of individuals receiving the treatment would not be aligned. For example, different individuals take job training (for each stage) at different times. In such cases, the formulation ((ref)) of budget constraints can be considered as follows. Suppose that a provider of the treatments (e.g., government) has a fixed budget that can be expended in a fixed fiscal period. The provider (correctly) predicts the number of participants of the program during the fiscal period. We also suppose that the budget can be expended on treatment for any stage for those who participate in the program in any time during the fiscal period. Subsequently, given the budget, the provider can decide the fraction of people who can receive treatment at each stage, as formulated as ((ref)).}

Our aim is to maximize the welfare $W(g)$ under the budget/capacity constraints ((ref)) across the class of feasible DTRs $\mathcal{G}$. The population welfare maximization problem is then formulated as

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

To this end, we incorporate the sample analogues of the budget/capacity constraints ((ref)) into the simultaneous DEWM.\footnote{We here do not consider the backward DEWM with the budget/capacity constraints because the first-best rule is likely to be unachievable under such constraints.} The simultaneous DEWM method with the budget/capacity constraints solves the following problem:

where

We denote $\hat{g}^{bdgt} \equiv \left(\hat{g}_{1}^{bdgt},\dots,\hat{g}_{T}^{bdgt}\right)$.

The inequality constraints ((ref)) are empirical budget/capacity constraints, where $\alpha_{n}$ is a tuning parameter dependent on the sample size $n$. $\alpha_{n}$ may be either positive or negative, and converges to zero as $n$ increases. As $\alpha_{n}$ decreases, the empirical budget/capacity constraints become tighter. A sufficiently large value of $\alpha_{n}$ ensures that the optimal DTR (a solution of ((ref))) is attainable under the empirical budget/capacity constraints with high probability. When $\mathcal{G}_{t}$ is the class of linear treatment rules for all $t$, the optimization problem ((ref)) can be formulated as an MILP problem (see Appendix (ref)).

Subsequently, we evaluate the resulting welfare regret $W_{{\cal G}}^{\ast,bdgt}-W\left(\hat{g}^{bdgt}\right)$ and the budget excess $\sum_{t=1}^{T}K_{tb}E_{P}\left[\hat{g}_{t}^{bdgt}\left(H_{t}\left(\underline{\hat{g}}_{t-1}^{bdgt}\right)\right)\right]-C_b$ of the estimated DTR with high probability, rather than evaluating their expected values, $E_{P^n}\left[W_{{\cal G}}^{\ast,bdgt}-W\left(\hat{g}^{bdgt}\right)\right]$ and $\sum_{t=1}^{T}K_{tb}E_{P^{n}}\left[E_{P}\left[\hat{g}_{t}^{bdgt}\left(H_{t}\left(\underline{\hat{g}}_{t-1}^{bdgt}\right)\right)\right]\right]-C_b$.\footnote{Note that $W\left(\hat{g}^{bdgt}\right)$ and $E_{P}\left[\hat{g}^{bdgt}\left(H_{t}\left(\underline{\hat{g}}_{t-1}^{S}\right)\right)\right]$ are random variables depending on the random sample $\{Z_i:i=1,\ldots,n\}$. } We adopt this approach because the actual value of the budget excess is typically of greater concern than its expected value in practice.

The following theorem shows the finite-sample properties of the welfare regret and the budget excess of $\hat{g}^{bdgt}$.

Equations ((ref)) and ((ref)) evaluate the welfare regret and the budget excess of the estimated DTR over the $b$-th budget/capacity, respectively. In equation ((ref)), $W_{{\cal G}}^{\ast,bdgt}-W_{\mathcal{G},\alpha_{n}}^{\ast,bdgt} \leq 0$ holds when $\alpha_n \leq k_{(B,n,\delta)}$, and $W_{{\cal G}}^{\ast,bdgt}-W_{\mathcal{G},\alpha_{n}}^{\ast,bdgt} \geq 0$ holds otherwise. Hence, when we set $\alpha_n$ such that $\alpha_n \leq k_{(B,n,\delta)}$, the results in Theorem (ref) holds with equation ((ref)) replaced by

where the welfare regret converges to zero as $n$ increases. The theorem suggests that with sufficiently large sample sizes, both the welfare regret and the budget excess are likely to be small, diminishing at the rate of $1/\sqrt{n}$ when $\alpha_{n}$ is chosen such that $\alpha_n = O(1/\sqrt{n})$ and that $\alpha_n \leq k_{(B,n,\delta)}$.\footnote{When $\alpha_n - k_{(B,n,\delta)} \searrow 0$, whether $W_{\mathcal{G}}^{\ast} - W_{\mathcal{G},\alpha_{n}}^{\ast,bdgt}$ in ((ref)) converges to zero depends on the properties of the class of DTR $\mathcal{G}$ and distribution $P$. 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 under some $P$, and hence $W_{\mathcal{G}}^{\ast} - W_{\mathcal{G},\alpha_{n}}^{\ast}$ may not converge to zero when $\alpha_n - k_{(B,n,\delta)} \searrow 0$.}

The tuning parameter $\alpha_{n}$ decides the strictness of the budget constraint. A smaller $\alpha_{n}$ implies that the estimated DTR tightly satisfies the budget constraint, as seen in ((ref)), but leads to lower welfare. Conversely, a larger $\alpha_{n}$ results in less strict adherence to the budget constraint and higher welfare. Thus, the choice of $\alpha_n$ involves a trade-off between maximizing welfare and minimizing budget excess.

We here propose two approaches to choose $\alpha_n$. When aiming to satisfy the budget constraints with a certain level of budget excesses and a particular probability, we can analytically choose the proper value of $\alpha_n$ through Theorem (ref). For example, for any $\varepsilon \in (0,1)$, Theorem (ref) guarantees that the excess budget for the $b$-th constraint is equal to or smaller than $\varepsilon$ with probability at least $1-\delta$ when we choose $\alpha_n = \varepsilon - \frac{1}{\sqrt{n}} \sum_{t=1}^{T}\left[K_{tb}\left(C\sqrt{\sum_{s=1}^{t}v_{s}}+\sqrt{\log\left(2B/\delta\right)/2}\right)\right]$. We can also use cross-validation to choose $\alpha_n$, wherein the validation data evaluates the welfare and budget excess for each DTR estimated with candidate values of $\alpha_n$. Note that $k_{(B,n,\delta)}$ is not a tuning parameter to be selected. Theorem (ref) also guides the selection of the sample size $n$ so that the budget excess is constrained to a certain level with a particular probability.

Observational Study

We consider the observational data setting where the propensity scores are not known but can be estimated from data. We modify the backward and simultaneous DEWM methods to use the estimated propensity scores, following the e-hybrid EWM rule proposed by Kitagawa_Tetenov_2018a. We also discuss construction of a doubly robust approach for estimating the optimal DTRs with technical exposition and theoretical results presented.

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 the following high-level assumption.

Note that $E_{P}\left[\tau_{t}\left(\text{\ensuremath{\underline{d}}}_{t},H_{t}\right)\right]=E_{P}\left[\gamma_{t}Y_{t}(\underline{d}_{t})\right]$ and $E_{P}\left[\eta_{t}\left(\text{\ensuremath{\underline{d}}}_{t:T},H_{T}\right)\right]=E_{P}\left[\sum_{s=t}^{T}\gamma_{s}Y_{s}(\underline{d}_{s})\right]$ hold under Assumption (ref) and $n^{-1}\sum_{i=1}^{n}\hat{\tau}_{t}\left(\text{\ensuremath{\underline{d}}}_{t}\right)$ and $n^{-1}\sum_{i=1}^{n}\hat{\eta}_{t}\left(\text{\ensuremath{\underline{d}}}_{t:T}\right)$ are estimators of these, respectively. We do not explore lower-level conditions that satisfy Assumption (ref). When the propensity scores are consistently estimated with parametric estimators, 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$:

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:

where $\hat{w}_{t}^{S}(Z_{i},\text{\ensuremath{\underline{g}}}_{t}) \equiv \left\{\left(\prod_{s=1}^{t}1\left\{ D_{is} = g_{s}\left(H_{is}\right)\right\}\right) \cdot\gamma_{t}Y_{it}\right\}/\left\{\prod_{s=1}^{t}\hat{e}_{s}\left(D_{is},H_{is}\right)\right\}$ uses the estimated propensity scores. We denote the resulting 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.

The theorem implies that the convergence rate of the worst-case average regret for each method depends on that of the propensity scores' estimators. If the propensity scores are correctly specified and parametrically estimated, both methods achieve the optimal $n^{-1/2}$-convergence rate of the worst-case average regret.

When the propensity scores are not consistently estimated, the IPW approaches do not consistently estimate the optimal DTRs. We hence propose a doubly robust approach; it is robust to misspecification of either propensity scores or models relevant to outcomes, and can achieve the optimal $n^{-1/2}$-rate of the welfare regret even when nuisance components are nonparametrically estimated. The following remark briefly discusses this approach while technical exposition and theoretical results are presented in Appendix (ref).

Simulation Study

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

We consider 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

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 set the target welfare to maximize as $W(g_1,g_2)=E_{P}\left[Y_{2}(g_{1},g_{2})\right]$. The treatment effect of $D_{2}$ does not depend 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 classes of linear treatment rules:

$\mathcal{G}_{2}$ contains the first-best rule 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. We solve the optimization problems for each DEWM method through MILPs as discussed in Remark (ref).

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

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 (ref) presents the results of 500 simulations with sample sizes $n=$ 200, 500, and 800. The table shows the mean and median welfare achieved by each estimated DTR calculated with 3,000 observations randomly drawn from the same DGP. 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 exhibit superior performance to Q-learning in DGP3, where the outcome model used by Q-learning is misspecified. In DGPs 1 and 2, the backward and simultaneous DEWM methods demonstrate similar welfare performance. However, in DGP3, the simultaneous DEWM method achieves higher welfare than the backward DEWM method. Table (ref) also presents the average CPU time to calculate DTR per simulation iteration.\footnote{We use Julia version 1.8.1 with Gurobi Optimizer version 9.5.2. The hardware is 12th Gen Intel(R) Core(TM) i7-12700 2.10 GHz.} The simultaneous DEWM takes the longest time but remains feasible at these scales of simulation. Appendix (ref) provides additional simulation results for DGPs where $D_1$ and $D_2$ are not independent of $U_1$ and $U_2$ (i.e., the sequential independence assumption (Assumption (ref)) does not hold).

Empirical Application

We apply the proposed methods to data from Project STAR krueger_1999, Gerber_et_al_2001, Schanzenbach_2006, Chetty_et_al_2011. In this experimental project, out of 1,346 kindergarten students not belonging 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 a teacher aide. Upon their progression to grade 1, the enrolled students were randomly shuffled into regular class-size classes with or without a teacher aide and remained in the allocated classes until the end of grade 3.

We study optimal allocation of students to two types of classes (regular-size classes with or without a teacher aide) in grades $K$ and $1$, based on their socioeconomic information and intermediate academic performance.\footnote{We focus on allocating students to regular-size classes with a teacher aide, rather than small-size classes, because the allocation of students to regular-size classes with or without a teacher aide in the experiment matches the sequential randomization design; however, the allocation to small-size classes in the experiment does not.} We aim to maximize the population average of scores from mathematics test that students took at the end of grade 1.\footnote{We 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 in kindergarten has little effect on the test score at the end of grade 3 even when treatment effect heterogeneity is considered.} 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 is assigned to a class with a teacher aide at stage $t$ and zero otherwise. The potential intermediate outcome $Y_{1}(d_1)$ and final outcome $Y_{2}(d_1,d_1)$ represent the mathematics test scores at the end of grades K and 1 for treatments $d_1$ and $d_2$.

Because it is plausible that assignment to a class with a teacher aide outperforms assignment to a class without one, we consider the cost of having a teacher aide. We consider a fictitious cost for teacher aide. This cost for each grade is set as $c \equiv E[Y_2(1,1) - Y_2(0,0) ]/2$, half of the expected welfare gain of assigning every student to teacher-aide classes in both grades. We use the estimate of $E[Y_2(1,1) - Y_2(0,0) ]/2$, which is $13.57$, for the cost $c$. Letting $Y_{2}^{c}(d_1,d_2) := Y_2(d_1,d_2) - c(d_1 + d_2)$ represent the individual welfare contribution, we aim to maximize welfare defined as $$W(g_1,g_2) = E\left[ \sum_{(d_1,d_2) \in \{0,1\}^2} Y_{2}^{c}(d_1,d_2)\cdot 1\left\{g_1(H_1)=d_1,g_2(H_2(d_1))=d_2\right\}\right],$$ which represents the average of the total test score at the end of grade 1 with subtraction of the cost. Note that in this setting, uniformly assigning every student to a class with a teacher aide in both grades results in zero welfare gain.

The socioeconomic information we use for treatment choice are the qualification for free or reduced-price school lunches and school location (rural or non-rural).\footnote{While we have access to student information such as sex and race, using such information in treatment choice is discriminatory and prohibited.} A binary variable $X_{Lunch,t}$ takes $1$ if the student is eligible for free or reduced-price school lunch at stage $t$ and $0$ otherwise. A binary variable $X_{Rural,t}$ takes $1$ if the student attends a school located in a rural area at stage $t$ and $0$ otherwise.

We employ a set of class-allocation policies represented by treatment rules $\mathcal{G}=\mathcal{G}_{1}\times\mathcal{G}_{2}$, where $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ constitute a class of linear treatment rules:\footnote{It is testable whether $\mathcal{G}_2$ contains the first-best rule or not. For example, we can estimate the first-best rule for the second stage as $\hat{g}_{2}^{\ast,FB}(h_{2}) = 1\{\hat{\tau}_{2}(h_2) \geq 2\}$ with $\hat{\tau}_{2}(h_2)$ being a (nonparametric) estimator of the conditional average treatment effect $\tau_{2}(h_2) = E[Y_{2}(D_1,1) - Y_2(D_1,0) | H_2 = h_2]$. We can then check whether $\mathcal{G}_2$ contains the first-best rule by examining if the optimal policy in $\mathcal{G}_2$ achieves the same expected outcome value as $\hat{g}_{2}^{\ast,FB}(h_{2})$.}

In the formulations of $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, the coefficients of $x_{Lunch,1}$ and $x_{Lunch,2}$ are constrained to be non-negative. This ensures that students 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}$ and $d_{1}y_{1}$ in $\mathcal{G}_{2}$ enable the eligibility score to evaluate the intermediate outcome differently based on class allocation at kindergarten. We solve the optimization problems for the backward and simultaneous DEWM through MILPs as discussed in Remark (ref).

For a DTR $g\in\mathcal{G}$, we define the welfare gain of $g$ as $W\left(g\right)-E[Y_{2}^{c}(0,0)]$, the welfare increase achieved by allocating students according to the DTR $g$ rather than allocating every student to regular classes without teacher aides at all stages.\footnote{Two factors enhance the students' academic achievement in classroom allocation: optimal matching between each student and classroom type (with or without a teacher aide) and peer effects among students. The optimal DTR considered here exploits the former but not the latter, as it does not utilize peer effects among students to determine classroom allocation.} Applying the backward and simultaneous DEWM methods, we estimate the optimal DTR over $\mathcal{G}$ and its welfare gain as well as the treatment ratio at each stage. To avoid overfitting biases, we adopt two-fold random sample splitting with a fixed seed: one third of the sample is used as the training set to estimate the optimal DTRs, and the remaining is used as the test set to estimate the welfare gains and treatment ratios.

The DTR estimated by the backward DEWM method is $\hat{g}^{B}=\left(\hat{g}_{1}^{B},\hat{g}_{2}^{B}\right)$ where $\hat{g}_{1}^{B}(h_{1})= 1$ and $\hat{g}_{2}^{B}(h_{2})= 1\left\{-0.104\left(1-d_{1}\right)y_{1}+0.382d_{1}y_{1}\geq - 0.449\right\}$. The DTR estimated by the simultaneous DEWM method is $\hat{g}^{S}=\left(\hat{g}_{1}^{S},\hat{g}_{2}^{S}\right)$ where $\hat{g}_{1}^{S}(h_{1}) = 1\left\{x_{Rural,1}= 1\right\}$ and $\hat{g}_{2}^{S}(h_{2}) = 1\left\{ 0.985x_{Rural,2} + 0.148d_{1}y_{1}\geq 0\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 teacher aides in grade K. Under both treatment rules $\hat{g}_{2}^{B}$ and $\hat{g}_{2}^{S}$ for grade 1, 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 (ref) reports the estimated welfare gains and shares of the population to be treated at each stage for the estimated DTRs $\hat{g}^{B}$ and $\hat{g}^{S}$ and three uniform DTRs $\left(g_{1},g_{2}\right)=\left(1,0\right),\left(0,1\right),\left(1,1\right)$. \footnote{With some abuse of notation, we denote by $(g_1,g_2)=(d_1,d_2)$ the uniform DTR that allocates every student to class types $d_1$ and $d_2$ in stages 1 and 2, respectively.} 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 none in grade 1. The results indicate that both the backward and simultaneous DEWM methods lead to higher welfare gains than all the uniform DTRs.

Next, we consider the decision problem of when each student should begin attending a class with a teacher aide. To this aim, we impose a constraint $g_{2}\left(h_{2}\right)\geq d_{1}$ for all $h_{2}\in\mathcal{H}_{2}$ on $\mathcal{G}_2$. 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 $\hat{g}_{1}^{B}(h_{1}) = 0$ and $\hat{g}_{2}^{B}(h_{2}) = 1\left\{ -0.104\left(1-d_{1}\right)y_{1} + 0.382 d_{1}y_{1}\geq -0.449\right\}$; the DTR estimated by the simultaneous DEWM method is $\hat{g}^{S}=\left(\hat{g}_{1}^{S},\hat{g}_{2}^{S}\right)$ with $\hat{g}_{1}^{S}(h_{1}) = 1\left\{ x_{Rural,1}= 1\right\}$ and $\hat{g}_{2}^{S}(h_{2}) = 1$.

Table (ref) reports the estimated welfare gains and shares of population to be treated by $\hat{g}^{B}$ and $\hat{g}^{S}$ and two uniform DTRs $(g_{1},g_{2})=(0,1),(1,1)$, which satisfy the monotonicity constraint. Both the Simultaneous and backward DEWM methods lead to higher welfare gains than the uniform DTRs. The simultaneous DEWM method leads to a slightly higher welfare gain than the backward DEWM method.

Conclusion

This study proposes empirical methods to estimate the optimal DTR over a pre-specified class of feasible DTRs based on the EWM approach. We proposed two estimation methods, the backward DEWM and simultaneous DEWM methods, which estimate the optimal DTR through backward induction and simultaneous maximization, respectively. The former is computationally efficient, but it may not consistently estimate the optimal DTR when the class of feasible DTRs does not include the first-best rule at all stages except for the first stage. Conversely, the latter method can consistently estimate the optimal DTR irrespective of the feasibility of the first-best rule, though it is computationally less efficient. These methods can accommodate exogenous constraints on the class of DTRs and specify different types of dynamic treatment choice problems. We show that each method can achieve the optimal $n^{-1/2}$ rate of convergence of the regret in the experimental data setting. We also modified the simultaneous DEWM to accommodate intertemporal budget/capacity constraints.