Similar to the above derivation, for a positive constant $\eta_{k}$, with
$\sum_{k}\eta_{k}\leq 1$,

$\displaystyle{\Pr(n^{-1}\sum^{n}_{t=1}h_{t}\geq x)}$ $\displaystyle\leq$
$\displaystyle\Pr(n^{-1}|\sum^{\overline{K}}_{k=1}\sum^{n}_{t=1}h_{t}^{(k)}-h_{t}^{(k-1)}|\geq
x-\sqrt{n}^{-1}2^{-\overline{K}}M)$ $\displaystyle\leq$
$\displaystyle\sum^{\overline{K}}_{k=1}\Pr(|n^{-1}\sum^{n}_{t=1}h_{t}^{(k)}-h_{t}^{(k-1)}|\geq\eta_{k}(x-\sqrt{n}^{-1}2^{-\overline{K}}M))$
$\displaystyle\leq$
$\displaystyle\sum^{\overline{K}}_{k=1}\exp\\{\log\max_{t}\sup_{Q}\mathcal{N}^{2}(2^{-k}M,\mathcal{H}_{t},\|.\|_{Q,2})-\eta_{k}^{2}(nx-\sqrt{n}2^{-\overline{K}}M)^{2}/[2\\{(nx-\sqrt{n}2^{-\overline{K}}M)$
$\displaystyle+2((3\cdot 2^{-k}\cdot M)^{2}n)\\}]\\}$ $\displaystyle\leq$
$\displaystyle\sum^{\overline{K}}_{k=1}\exp(\log(K)+\log(v+1)+(v+1)(\log
4+1)+(2v)\log(\frac{2}{2^{-k}M})$
$\displaystyle-\eta_{k}^{2}(nx-\sqrt{n}2^{-\overline{K}}M))^{2}/(2((nx-\sqrt{n}2^{-\overline{K}}M)+2((3\cdot
2^{-k}\cdot M)^{2}n))),$

where the above derivation is due to the tail probability in Lemma A.1. We
pick $\eta_{k}$ and $x$ to ensure the right hand side converges to zero and
$\sum_{k}\eta_{k}\leq 1$.

We take $b_{k}=\log(\overline{K})+\log(v+1)+(v+1)(\log
4+1)+(2v)\log(\frac{2}{2^{-k}M})$,
$a_{k}=2^{-1}(nx-\sqrt{n}2^{-\overline{K}}M))^{2}/((nx-\sqrt{n}2^{-\overline{K}}M)+2((3*2^{-k}*M)^{2}n))$.
We pick $\eta_{k}\geq\sqrt{a_{k}/b_{k}}$, so that
$b_{k}\leq\eta_{k}^{2}a_{k}$. We also need to choose $x$ to ensure that
$\sum_{k}\eta_{k}\leq 1$ and $\sum_{k}\exp(b_{k}-\eta_{k}^{2}a_{k})\to 0$. We
pick $c_{n}\sqrt{v/n}\lesssim x$, and
$\eta_{k}=c_{n}^{\prime}\sqrt{b_{k}/a_{k}}$, with two slowly growing functions
$c_{n}$ and $c_{n}^{\prime}$ and $c_{n}^{\prime}\ll c_{n}$. We set
$x=\mathop{\mbox{\sf E}}(|\mathop{\mbox{\sf
E}}{{}_{n}}h|_{\mathbf{H_{n}}})+c_{n}\sqrt{v/n}$. The result then follows.

Finally, Theorem 3.1 follows from combining Lemma A.3, Lemma A.4, and $n=T-1$.

∎

###  A.4 Justifying Assumption 3.8

Here we interpret the entropy condition in Assumption 3.8. We follow the
argument of Chapter 11 in Kosorok [2008] for the functional class related to
non-i.i.d. data.

First, we illustrate the case that the random stochastic process

$\\{D_{t}\\}_{t=-\infty}^{\infty}\overset{\text{def}}{=}\\{Y_{t},W_{t},X_{t-1}\\}_{t=-\infty}^{\infty}$

is assumed to be stationary. In this case, we have for all
$t\in\\{1,2,\dots,n\\}$,

$\displaystyle h_{t}(\cdot;G)$ $\displaystyle=h(\cdot;G)$
$\displaystyle\mathcal{\text{and }H}$
$\displaystyle=\\{h(\cdot;G)=\widehat{\mathcal{W}}_{t}(G)-\bar{\mathcal{W}}_{t}(G):G\in\mathcal{G}\\}.$

For a $n$-dimensional non-negative vector
$\alpha_{n}=\\{\alpha_{n,1},\alpha_{n,2},\dots,\alpha_{n,n}\\}$, define
$Q_{\alpha_{n}}$ as a discrete measure with probability mass
$\frac{\alpha_{n,t}}{\sum_{t=1}^{n}\alpha_{n,t}}$ on the value $D_{t}$. Recall
for a function $f$, its $L_{r}(Q)-$norm is denoted by
$||f||_{Q,r}\overset{\text{def}}{=}\left[\int_{v}|f(v)|^{r}dQ(v)\right]^{1/r}$.
Thus, given a sample $\\{D_{t}\\}_{t=1}^{n}$ and $h(\cdot;G)$, we have
$||h(\cdot;G)||_{Q_{\alpha_{n}},2}=\left[\frac{1}{\sum_{t=1}^{n}\alpha_{n,t}}\sum_{t}\alpha_{n,t}h(D_{t};G)^{2}\right]^{1/2}.$

In the stationary case, we define the restricted function class
$\mathbf{H_{n}}=\\{h_{1:n}:h_{1:n}\in\mathcal{\mathcal{H}}\times\mathcal{\mathcal{H}}\times\dots\times\mathcal{\mathcal{H}},h_{1}=h_{2}=\dots=h_{n}\\}$
and the envelope function
$\overline{H}{}_{n}=(H_{1},H_{2},\cdots,H_{n})^{\prime}$. Furthermore, let
$\mathcal{Q}$ denote the class of all discrete probability measures on the
domain of the random vector $D_{t}=\\{Y_{t},W_{t},X_{t-1}\\}$. Recall for a
$n$-dimensional vector $v=\left\\{v_{1},\dots,v_{n}\right\\}$, its
$l_{2}-$norm is denoted by
$|v|_{2}\overset{\text{def}}{=}\left(\sum_{i=1}^{n}v_{i}^{2}\right)^{1/2}$.
Then, for any $\alpha_{n}\in\mathbb{R}_{+}^{n}$ and
$\tilde{\alpha}_{n,t}=\frac{\sqrt{\alpha_{n,t}}}{\sqrt{\sum_{t}\alpha_{n,t}}}$,
we have

$\mathcal{N}(\delta|\tilde{\alpha}_{n}\circ\overline{H}{}_{n}|_{2},\tilde{\alpha}_{n}\circ\mathbf{H}_{n},|.|_{2})=\mathcal{N}(\delta||H||_{Q_{\alpha_{n}},2},\mathcal{H},||.||_{Q_{\alpha_{n}},2})\leq\sup_{Q\in\mathcal{Q}}\mathcal{N}(\delta||H||_{Q,2},\mathcal{H},||.||_{Q,2}).$

In light of this relationship in the stationary case, we generalize the setup.
Let $\mathcal{K}$ to be a subset of $\\{1,\cdots,n\\}$, and its dimension is
$K=|\mathcal{K}|$. Let $\alpha_{n,K}$ denote the $K$ dimensional sub-vector of
$\alpha_{n}$ corresponding to the index set $\mathcal{K}.$ Recall that $H_{t}$
denotes the envelope function of $\mathcal{\mathcal{H}}_{t}$, the functional
class corresponding to $\\{h_{t}(.,G),G\in\mathcal{G}\\}$, and
$\mathbf{H_{n}}=\mathcal{\mathcal{H}}_{1}\times\mathcal{\mathcal{H}}_{2}\times\dots\times\mathcal{H}_{n}.$
Then, for the subset $\mathcal{K}$, we similarly define $\mathbf{H}_{n,K}$ as
the corresponding functional class, and the vector of its envelope functions
as $\overline{H}{}_{n,K}$.

Let us consider the following assumption: for any fixed $K$, the covering
number can effectively be reduced to $K$ dimension, i.e.,

$\displaystyle\mathcal{N}(\delta|\tilde{\alpha}_{n}\circ\overline{H}{}_{n}|_{2},\mathbf{\tilde{\alpha}_{n}\circ
H_{n},|.|_{2}})$
$\displaystyle\leq\max_{\mathcal{K}\subseteq\\{1:n\\}}\mathcal{N}(\delta|\tilde{\alpha}_{n,K}\circ\overline{H}{}_{n,K}|_{2},\mathbf{\tilde{\alpha}_{n,K}\circ
H_{n,K},|.|_{2}}),$
$\displaystyle\leq\max_{\mathcal{K}\subseteq\\{1:n\\}}\prod_{t\in\mathcal{K}}\mathcal{N}(\delta|\tilde{\alpha}_{n,t}\circ\overline{H}{}_{t}|_{2},\tilde{\alpha}_{n,t}\circ\mathbf{H}_{t},|.|_{2}),$
$\displaystyle\leq\sup_{Q\in\mathcal{Q}}\max_{t\in\mathcal{K}}\max_{\mathcal{K}\subseteq\\{1:n\\}}\mathcal{N}(\delta\|H_{t}\|_{Q,2},\mathcal{\mathcal{H}}_{t},\|.\|_{Q,2})^{K}.$

The first inequality of (39) in Assumption 3.8 holds by setting
$K=|\mathcal{K}|=1$. Under this assumption, it suffices to examine the one-
dimensional covering number
$\mathcal{N}(\delta\|H_{t}\|_{Q,2},\mathcal{\mathcal{H}}_{t},\|.\|_{Q,2})$.

To provide an example for the second inequality of (39), we let
$\bm{1}(X_{t-1}\in G)=\bm{1}(X_{t-1}^{\top}\theta\leq 0)$ for some
$\theta\in\Theta$, where $\Theta$ is a compact set in $\mathbb{R}^{d}$.
Without loss of generality we assume that $\Theta$ is the unit ball in
$\mathbb{R}^{d}$, i.e., for all $\theta\in\Theta$: $|\theta|_{2}\leq 1$. For
$w=0$ and 1, define
$S_{t,w}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}Y_{t}(w)\bm{1}(W_{t}=w)/\Pr(W_{t}=w|X_{t-1})$,
where $Y_{t}(w)$ is the abbreviation of $Y_{t}(W_{t-1},w)$. Under Assumption
3.7, $|Y_{t}(1)|,|Y_{t}(0)|\leq M/2$, so we have $\|H_{t}\|_{Q,r}\leq
M+M/\kappa\overset{\text{def.}}{=}M^{\prime}$, and

$\displaystyle h^{\theta}_{t}$ $\displaystyle=$
$\displaystyle\mathop{\mbox{\sf E}}(Y_{t}(1)\bm{1}(X_{t-1}^{\top}\theta\leq
0)|X_{t-1})+\mathop{\mbox{\sf
E}}(Y_{t}(0)\bm{1}(X_{t-1}^{\top}\theta>0)|X_{t-1})$ $\displaystyle-
S_{t,1}\bm{1}(X_{t-1}^{\top}\theta\leq
0)-S_{t,0}\bm{1}(X_{t-1}^{\top}\theta>0).$

The corresponding functional class can be written as

$\displaystyle\mathcal{H}_{t}=\\{h:(y_{t},w_{t},x_{t-1})\to
f_{1,1}^{\theta}+f_{1,0}^{\theta}+f_{0,1}^{\theta}+f_{0,0}^{\theta},\theta\in\Theta\\},$

where $f_{1,1}^{\theta}$ (resp. $f_{1,0}^{\theta},f_{0,1}^{\theta},$ and
$f_{0,0}^{\theta}$) corresponds to $\mathop{\mbox{\sf
E}}(Y_{t}(1)\bm{1}(X_{t-1}^{\top}\theta\leq 0)|X_{t-1})$ (resp.
$\mathop{\mbox{\sf
E}}(Y_{t}(0)\bm{1}(X_{t-1}^{\top}\theta>0)|X_{t-1}),-S_{t,1}\bm{1}(X_{t-1}^{\top}\theta\leq
0)$, and $-S_{t,0}\bm{1}(X_{t-1}^{\top}\theta>0)$). Denote the corresponding
functional class as $\mathcal{F}_{1,1}$ (resp.
$\mathcal{F}_{1,0},\mathcal{F}_{0,1},$ and $\mathcal{F}_{0,0})$. For all
finitely discrete norms $Q$ and any positive ${\varepsilon}$, we know that

$\small\sup_{Q}\mathcal{N}({\varepsilon},\mathcal{H}_{t},\|.\|_{Q,r})\leq\sup_{Q}\mathcal{N}({\varepsilon}/4,\mathcal{F}_{1,1},\|.\|_{Q,r})\mathcal{N}({\varepsilon}/4,\mathcal{F}_{1,0},\|.\|_{Q,r})\mathcal{N}({\varepsilon}/4,\mathcal{F}_{0,1},\|.\|_{Q,r})\mathcal{N}({\varepsilon}/4,\mathcal{F}_{0,0},\|.\|_{Q,r}).$
(76)

We look at the covering number of the respective functional class. According
to Lemma 9.8 of Kosorok [2008], the subgraph of the function
$\bm{1}(X_{t-1}^{\top}\theta\leq 0)$ is of VC dimension less than $d+2$ since
the class $\\{x\in\mathbb{R}^{d},x^{\top}\theta\leq 0,\theta\in\Theta\\}$ is
of VC dimension less than $d+2$ (see the proof of Lemma 9.6 of Kosorok
[2008]). Therefore, we have
$\sup_{Q}\mathcal{N}({\varepsilon}/4,\mathcal{F}_{0,1},\|.\|_{Q,r})\vee\mathcal{N}({\varepsilon}/4,\mathcal{F}_{0,0},\|.\|_{Q,r})\lesssim(4/({\varepsilon}M^{\prime}))^{d+2}$.

Moreover, we impose the following Lipschitz condition on functions
$f^{\theta}_{1,1}$ and $f^{\theta}_{1,0}$: For any distinct points
$\theta,\theta^{\prime}\in\Theta$ and a positive constant $M_{d}$, it holds
that $||f^{\theta}_{1,1}-f^{\theta^{\prime}}_{1,1}||_{Q,r}\leq
M_{d}|\theta-\theta^{\prime}|_{r}$ (the similar for $f^{\theta}_{1,0})$. Then,
it falls within the type II class defined in Andrews [1994], so according to
the derivation of the (A.2) Andrews [1994] we have

$\sup_{Q}\mathcal{N}({\varepsilon}M^{\prime},\mathcal{F}_{1,1},\|.\|_{Q,r})\leq\sup_{Q}\mathcal{N}({\varepsilon}M^{\prime}/M_{d},\Theta,\|.\|_{Q,r}),$
(77)

where the latter is the covering number of a Euclidean ball with
$\|.\|_{Q,r}$. Thus, according to Equation (5.9) in Wainwright [2019],
$\sup_{Q}\mathcal{N}({\varepsilon}M^{\prime}/M_{d},\Theta,\|.\|_{Q,r})\lesssim(1+2M_{d}/{\varepsilon}M^{\prime})^{d}$.
Combining the above results, we have $\sup_{Q}\mathcal{N}(\varepsilon
M^{\prime},\mathcal{H}_{t},\|.\|_{Q,r})\lesssim(4/({\varepsilon}M^{\prime}))^{2(d+2)}(1+2M_{d}/({\varepsilon}M^{\prime}))^{2d}$.
Finally, with some rearrangement and redefinition of constant terms, we can
obtain (39).

###  A.5 Proof of Theorem 3.2

In this proof, we show the concentration of
$I=\frac{1}{T-1}\sum_{t=1}^{T-1}\tilde{S}_{t}(G)+\frac{1}{T-1}\sum_{t=1}^{T-1}\overline{S}_{t}(G)$.
Under Assumptions 3.8 and 3.13 and with similar arguments as those for Lemma
A.4, we have

$\displaystyle\mbox{sup}_{G\in\mathcal{G}}\frac{1}{T-1}\sum_{t=1}^{T-1}\overline{S}_{t}(G)\lesssim_{p}M\sqrt{v}/{\sqrt{T-1}}.$
(78)

For $\frac{1}{T-1}\sum_{t=1}^{T-1}\tilde{S}_{t}(G)$, we first show
(i) For a finite function class $\mathcal{G}$ with
$|\mathcal{G}|=\tilde{M}<\infty$ and under Assumptions 3.10\- 3.12,

$\sup_{G\in\mathcal{G}}\frac{1}{T-1}\sum_{t=1}^{T-1}\tilde{S}_{t}(G)\lesssim\frac{c_{T}[\log\tilde{M}2e\gamma]^{1/\gamma}\Phi_{\phi_{\tilde{v}},F}}{\sqrt{T-1}},$
(79)

with probability $1-\exp(-c_{T}^{\gamma})$, where $c_{T}$ is a large enough
constant, and $\Phi_{\phi_{\tilde{v}},F}$ is defined in Assumption 3.12.

Then, we extend the above result to obtain Theorem 3.2:
(ii) Let $\mathcal{G}$ be a function class with infinite elements, and its
complexity is subject to Assumption 3.13. Under Assumptions 3.10\- 3.13, we
have

$\sup_{G\in\mathcal{G}}\frac{1}{T-1}\sum_{t=1}^{T-1}\tilde{S}_{t}(G)\lesssim_{p}\frac{c_{T}[V\log
T2e\gamma]^{1/\gamma}\Phi_{\phi_{\tilde{v}},F}}{\sqrt{T-1}}.$

###### Proof.

By Assumption 3.1 and 3.11(i), we have $\mathop{\mbox{\sf
E}}(S_{t}(G)|\mathcal{F}_{t-2})=\mathop{\mbox{\sf E}}(S_{t}(G)|X_{t-2})$. By
Assumption 3.10, $\mathop{\mbox{\sf E}}(S_{t}(G)|X_{t-2})$ are continuously
differentiable with respect to the underlying i.i.d. innovations. Denote
$\tilde{{\varepsilon}}_{t-l-2}$ as a point between ${\varepsilon}_{t-l-2}$ and
${\varepsilon}_{t-l-2}^{*}$ such that the following equation holds.

$\displaystyle\tilde{S}_{t}(G)-\tilde{S}_{t,l}^{*}(G)$ $\displaystyle=$
$\displaystyle\mathop{\mbox{\sf E}}(S_{t}(G)|X_{t-2})-\mathop{\mbox{\sf
E}}(S_{t}(G)|X_{t-2,l}^{*})$ $\displaystyle=$
$\displaystyle\partial\mathop{\mbox{\sf
E}}(S_{t}(G)|X_{t-2})/\partial{\varepsilon}_{t-l-2}|_{{\varepsilon}_{t-l-2}=\tilde{{\varepsilon}}_{t-l-2}}({\varepsilon}_{t-l-2}-{\varepsilon}_{t-l-2}^{*})$
$\displaystyle\leq$
$\displaystyle|F_{t,l}(X_{t-2},{\varepsilon}_{t-l-1})({\varepsilon}_{t-l-2}-{\varepsilon}_{t-l-2}^{*})|.$

Thus, the dependence adjusted norm satisfies $\theta_{x,q}\leq\sum_{l\geq
0}\max_{t}\|F_{t,l}(X_{t-2},{\varepsilon}_{t-l-1})({\varepsilon}_{t-l-2}-{\varepsilon}_{t-l-2}^{*})\|_{q}$,
and

$\Phi_{\phi_{\tilde{v}}}(\tilde{S}_{.}(G))\leq\sup_{q\geq 2}(\sum_{l\geq
0}\max_{t}\|F_{t,l}(X_{t-2},{\varepsilon}_{t-l-1}))({\varepsilon}_{t-l-2}-{\varepsilon}_{t-l-2}^{*})\|_{q})/q^{\tilde{v}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\Phi_{\phi_{\tilde{v}},F}$
(80)

holds for any $G\in\mathcal{G}$. Following Assumption 3.12, we have
$\Phi_{\phi_{\tilde{v}}}(\tilde{S}_{.}(G))<\infty$. Recall
$\gamma=1/(1+2\tilde{v})$, and for a finite $\mathcal{G}$ with
$|\mathcal{G}|=\tilde{M}$, the next exponential bound follows by Theorem 3 of
Wu and Wu [2016].

$\Pr(\sup_{G\in\mathcal{G}}\sum_{t=1}^{T-1}\tilde{S}_{t}(G)\geq
x)\leq\tilde{M}\exp\left[-\left(\frac{x}{\sqrt{T-1}\Phi_{\phi_{\tilde{v}}}(\tilde{S}_{.}(G))}\right)^{\gamma}\frac{1}{2e\gamma}\right].$
(81)

Set
$x=c_{T}[\log\tilde{M}2e\gamma]^{1/\gamma}\Phi_{\phi_{\tilde{v}}}(\tilde{S}_{.}(G))\sqrt{T-1}$,
where $c_{T}$ is a sufficiently large constant, then

$\sup_{G\in\mathcal{G}}\frac{1}{T-1}\sum_{t=1}^{T-1}\tilde{S}_{t}(G)\lesssim
c_{T}[\log\tilde{M}2e\gamma]^{1/\gamma}\Phi_{\phi_{\tilde{v}},F}/\sqrt{T-1},$
(82)

with probability $1-\exp(-c_{T}^{\gamma})$.

We now verify (ii), where $\mathcal{G}$ is not finite. We define
$\mathcal{G}^{(1)\delta}$ to be a
$\delta\max_{t}\mbox{sup}_{Q}\|\tilde{F}_{t}\|_{Q,2}$-net of $\mathcal{G}$. We
denote $\pi(G)$ as closest component of $G$ in the net
$\mathcal{G}^{(1)\delta}$. Then,

$\displaystyle\sup_{G}\frac{1}{T-1}\sum_{t}\tilde{S}_{t}(G)$
$\displaystyle\leq$
$\displaystyle\sup_{G\in\mathcal{G}}\frac{1}{T-1}\sum_{t=1}^{T}(\tilde{S}_{t}(G)-\tilde{S}_{t}(\pi(G)))+\sup_{G\in\mathcal{G}^{(1)\delta}}|\frac{1}{T-1}\sum_{t=1}^{T-1}(\tilde{S}_{t}(G))|$
$\displaystyle\leq$
$\displaystyle\delta\mbox{max}_{t}\mbox{sup}_{Q}\|\tilde{F}_{t}\|_{Q,2}+\sup_{G\in\mathcal{G}^{(1)\delta}}|\frac{1}{T-1}\sum_{t=1}^{T-1}(\tilde{S}_{t}(G))|$
$\displaystyle\lesssim_{p}$
$\displaystyle\delta\mbox{max}_{t}\mbox{sup}_{Q}\|\tilde{F}_{t}\|_{Q,2}+c_{T}[V\log(1/\delta)4e\gamma]^{1/\gamma}\Phi_{\phi_{\tilde{v}},F}/\sqrt{T-1},$

where $V$ and $\delta$ following the first $\lesssim_{p}$ are the constants in
the first statement of Assumption 3.13. $\Phi_{\phi_{\tilde{v}},F}$ is defined
in Assumption 3.12. Finally, by setting $\delta=\frac{1}{T}$,

$\sup_{G}\frac{1}{T-1}\sum_{t=1}\tilde{S}_{t}(G)\lesssim_{p}c_{T}[V\log
T2e\gamma]^{1/\gamma}\Phi_{\phi_{\tilde{v}},F}/\sqrt{T-1}.$ (83)

∎

###  A.6 Accounting for the Lucas critique

Here we solve the VAR reduced form of the three-equation New Keynesian model
discussed in Section 4.2.

We seek the solution to

$(\begin{array}[]{c}\mathop{\mbox{\sf E}}_{t}x_{t+1}\\\ \mathop{\mbox{\sf
E}}_{t}\pi_{t+1}\end{array})=(\begin{array}[]{cc}\kappa/\beta+1&\delta/\sigma-1/(\sigma\beta)\\\
-\kappa/\beta&1/\beta\end{array})(\begin{array}[]{c}x_{t}\\\
\pi_{t}\end{array})+(\begin{array}[]{c}v_{t}/\sigma\\\
\varepsilon_{t}/\beta\end{array}).$

Denote

$N=(\begin{array}[]{cc}\kappa/\beta+1&\delta/\sigma-1/(\sigma\beta)\\\
-\kappa/\beta&1/\beta\end{array}),$ $\tilde{Y}_{t}=(\begin{array}[]{c}x_{t}\\\
\pi_{t}\end{array}).$

Assuming $N$ is invertible, we set

$A=N^{-1}.$

Let $\Gamma_{t}=N^{-1}(\begin{array}[]{c}v_{t}/\sigma\\\
\varepsilon_{t}/\beta\end{array})=ACd_{t}$, with
$C=\text{diag}[\sigma^{-1},\beta^{-1}]$. In addition, define

$d_{t}=(\begin{array}[]{c}v_{t}\\\ \varepsilon_{t}\end{array}),$

and

$d_{t}=Fd_{t-1}+\eta_{t},$ (84)

where $F=[\begin{array}[]{cc}\rho&0\\\ 0&\gamma\end{array}]\text{ for
}(\rho,\gamma\neq 0).$ Then

$\tilde{Y}_{t}=A\mathop{\mbox{\sf E}}{{}_{t}}\tilde{Y}_{t+1}+\Gamma_{t}.$

Solving forward, we obtain

$\tilde{Y}_{t}=\lim_{L\to\infty}(A^{L}\mathop{\mbox{\sf
E}}{{}_{t}}(\tilde{Y}_{t+L})+\sum_{l\geq 0}A^{l}\mathop{\mbox{\sf
E}}{{}_{t}}\Gamma_{t+l}).$

Let $\rho(A)<1$, $\rho(F)<1$, then

$\lim_{L\to\infty}A^{L}\mathop{\mbox{\sf
E}}{{}_{t}}(\tilde{Y}_{t+L})\to_{a.s.}0,$

and

$\mathop{\mbox{\sf E}}{{}_{t}}\Gamma_{t+l}=ACF^{l}d_{t}.$

Thus,

$\tilde{Y}_{t}=AC(I-F)^{-1}d_{t}.$ (85)

Combining (84) and (85), we can solve the VAR reduced form for
$\tilde{Y}_{t}:=(x_{t},\pi_{t})^{\prime}$

$\tilde{Y}_{t+1}=AC(I-F)^{-1}F(AC(I-F)^{-1})^{-1}\tilde{Y}_{t}+AC(I-F)^{-1}\eta_{t+1}.$

###  A.7 Additional Figures for the empirical application

####  A.7.1 Time series plots of the raw data

Figure 3: Weekly cases and deaths from 4-2020 to 1-2022 Figure 4: Restriction
level and economic condition from 4-2020 to 1-2022 Figure 5: Vaccine coverage
from 4-2020 to 1-2022

The vaccine coverage is calculated by summing up the coverage rate of each
dose.

####  A.7.2 Estimated propensity scores

Figure 6: Estimated propensity scores

####  A.7.3 Policy choices based on increased number of variables

Figure 7:  Optimal policies based on
$X_{T-1}^{P}=\left(\text{change in cases}_{T-1},\text{restriction
stringency}_{T-1},\text{vaccine coverage}_{T-1}\right)$

In the left panel, the $x$-axis is the change in deaths at week $T-1$, and the
$y$-axis is the stringency of restrictions at week $T-1$; in the right panel,
the $x$-axis is the stringency of restrictions at week $T-1$, and the $y$-axis
is the vaccine coverage at week $T-1$.

Figure 8:  Optimal policy based on
$X_{T-1}^{P}=(\text{change in deaths}_{T-1},\text{restriction
stringency}_{T-1},\text{vaccine coverage}_{T-1},$ $\text{change in
cases}_{T-1})$

In the left panel, the $x$-axis is the change in deaths at week $T-1$, and the
$y$-axis is the stringency of restrictions at week $T-1$; in the right panel,
the $x$-axis is the vaccine coverage at week $T-1$, and the $y$-axis is the
change in cases at week $T-1$.

###  A.8 Nonparametric method to bound the conditional regret

In Section 3.2, we showed that we can bound conditional regret by
unconditional regret if the unconditional first best policy is feasible. In
Appendix A.8.1, we present examples where this method is applicable, and
examples where it is not. More examples can be found in and Appendix B.2. When
Assumption 3.4 does not hold, we proceed to the nonparametric method of
Appendix A.8.2.

####  A.8.1 Motivation

In this subsection, we discuss the relationship between the optimal policy
solutions in terms of conditional and unconditional welfare. This relationship
is not straightforward. In some cases, unconditional welfare does bound
conditional welfare, and the methods and results in Section 3.2 directly
apply. However, in other cases, when the first best policy is not feasible, we
shall use the kernel estimator. This motivates us to present the kernel
estimator as an important alternative to the method of Section 3.2.

######  Example A.1.

Observing
$X_{T-1}=\left(Y_{T-1},W_{T-1},Z_{T-1}\right)^{\prime}\in\mathbb{R}\times\\{0,1\\}\times\mathbb{R}^{2}$
at time $T-1$, the planner chooses $W_{T}$ based on the last two continuous
variables. The feasible policy class is rectangles in $\mathbb{R}^{2}$:

$\mathcal{G}=\left\\{z\in[a_{1},a_{2}]\times[b_{1},b_{2}]:a_{1},a_{2},b_{1},b_{2}\in\mathbb{R}\right\\}.$

The corresponding unconditional problem is
$\underset{G\in\mathcal{G}}{\mbox{max }}\mathcal{W}_{T}(G).$ Suppose the
planner is interested in maximizing the welfare conditional on
$Z_{T-1}=z:=(z^{(1)},z^{(2)})$. The conditional problem is to find

$\arg\max_{G\in\mathcal{G}}\mathcal{W}_{T}(G|Z_{T-1}=z),$ (86)

We illustrate how the policy solutions can differ between conditional and
unconditional welfare functions. In Figures 9 and 10, the shaded area
represents the region where the conditional average treatment effect is
positive. The first best unconditional policy assigns $W_{T}=1$ to any value
of $Z_{T-1}$ inside this region, and $W_{T}=0$ to any point outside it. This
policy is also the solution to (86). The red rectangle is the best feasible
(i.e. rectangular) unconditional policy. This policy assigns $W_{T}=1$ to any
realization of $Z_{T-1}$ inside the rectangle. The conditional policy concerns
what policy to assign only at a particular value of $Z_{T-1}$ corresponding to
its realized value in the data (blue point in the right-hand side panel of
Figure 9). If the best feasible unconditional policy (red rectangle) agrees
with the first best unconditional policy (shared area), then the policy choice
informed by the unconditional policy is guaranteed to be optimal in terms of
the conditional policy at any conditioning value of $Z_{T-1}$.

Figure 9:  $G_{\text{FB}}^{*}\in\mathcal{G}$

The dashed red line is the same as the dashed blue line.

Figure 10:  $G_{\text{FB}}^{*}\notin\mathcal{G}$

The dashed red line is different to the dashed blue line.

Figure 10 shows a case where the first best unconditional policy is not
contained in the class of feasible policies: it is not possible to implement
the policy choice that coincides with the shaded area. In this case, the
policy chosen by the unconditionally optimal feasible policy (red rectangle in
the left-hand side panel) does not coincide with the optimal policy choice of
the conditional policy. The highlighted point $(z^{(1)},z^{(2)})$ lies outside
the red rectangle, so the best feasible unconditional policy would set
$W_{t}=0$. However, it lies within the shaded region, so the conditional
average treatment effect given $Z_{T-1}=(z^{(1)},z^{(2)})$ is positive, and
the optimal policy conditional on $Z_{T-1}=(z^{(1)},z^{(2)})$ is to set
$W_{t}=1$.

These two examples show the importance of the first best unconditional policy:
when it is included in the set of feasible unconditional policies, the
solution to the conditional problem corresponds to the solution to the
unconditional problem. When it is not included, we do not have this
correspondence. In Appendix B.2.1, we show that the feasibility of the first
best solution to the unconditional problem is a sufficient condition. A
sufficient and necessary condition is given by Assumption 3.4.

####  A.8.2 Nonparametric estimator of the optimal conditional policy

If the solution to the conditional problem cannot be obtained from the
unconditional problem, the conditional problem must be solved directly. That
is, the SP should estimate an optimal policy from the empirical analogue of
the conditional welfare function. If the conditioning variables are
continuous, some type of nonparametric smoothing is unavoidable. Here we use a
kernel-based method to estimate the optimal conditional policy. Recall that
welfare conditional on $X_{T-1}=x$ can be written as

$\mathcal{W}_{T}(G|x)=\mathop{\mbox{\sf
E}}\left\\{Y_{T}(W_{T-1},1)1(X_{T-1}\in G)+Y_{t}(W_{T-1},0)1(X_{T-1}\notin
G)|X_{T-1}=x\right\\}.$

For simplicity, we let $X_{T-1}\in\mathbb{R}$. Then (27) can be rewritten as
121212If the set of conditioning variables $X_{T-1}$ contains both continuous
and discrete components, we can adapt a hyper method to construct a valid
sample analogue combing kernel-smoothing (for continuous variables) and
subsamples (for discrete variables). In this section, we focus on the case
where the target welfare function is conditional on a univariate continuous
variable

$\displaystyle\widehat{\mathcal{W}}(G|x)=\frac{\sum_{t=1}^{T-1}K_{h}(X_{t-1},x)\widehat{\mathcal{W}}_{t}(G)}{\sum_{t=1}^{T-1}K_{h}(X_{t-1},x)},$
(87)

where
$\widehat{\mathcal{W}}_{t}(G):=\frac{Y_{t}W_{t}}{e_{t}(X_{t-1})}1(X_{t-1}\in
G)+\frac{Y_{t}(1-W_{t})}{1-e_{t}(X_{t-1})}1(X_{t-1}\notin G)$, and
$K_{h}(a,b):=\frac{1}{h}K(\frac{a-b}{h})$ with $K(\cdot)$ assumed to be a
bounded kernel function with a bounded support.

Recall that $\mathcal{G}$ is the set of feasible policies conditional on
$X_{T-1}=x$. We define

$\displaystyle G_{x}^{*}$ $\displaystyle\in$
$\displaystyle\mbox{argmax}_{G\in\mathcal{G}}\mathcal{W}(G|x)$
$\displaystyle\hat{G}_{x}$ $\displaystyle\in$
$\displaystyle\mbox{argmax}_{G\in\mathcal{G}}\widehat{\mathcal{W}}(G|x)$

to be the maximizers of $\mathcal{W}(G|x)$ and $\widehat{\mathcal{W}}(G|x)$,
and

$\displaystyle\bar{\mathcal{W}}_{h}(G|x)$ $\displaystyle=$
$\displaystyle\frac{\sum_{t=1}^{T-1}K_{h}(X_{t-1},x)\mathcal{W}_{t}(G|x)}{\sum_{t=1}^{T-1}K_{h}(X_{t-1},x)},$
(88)

where the second equality follows from Assumption 3.3.

The invariance of welfare ordering assumption is modified to,

######  Assumption A.1 (Invariance of welfare ordering).

For any $G\in\mathcal{G}$ and $x\in\mathcal{X}$, there exists some constant
$c$

$\mathcal{W}_{T}(G_{x}^{*}|x)-\mathcal{W}_{T}(G_{|}x)\leq
c\big{[}\bar{\mathcal{W}}_{h}(G_{x}^{*}|x)-\bar{\mathcal{W}}_{h}(G|x)\big{]}.$
(89)

Similar to Assumption 2.4, (89) holds if the stochastic process
$S_{t}(x):=Y_{T}(W_{T-1},1)1(X_{T-1}\in G)+Y_{t}(W_{T-1},0)1(X_{T-1}\notin
G)|_{X_{T-1}=x}$ is weakly stationary.

The following theorem shows an upper bound for conditional regret in the one
dimensional covariate case (i.e., $X_{t}\in\mathbb{R}$). This result can be
readily extended to the multiple covariate case.

######  THEOREM A.1.

Under Assumption A.1 and A.2 specified in Appendix A.8.3, we will have

$\underset{P_{T}\in\mathcal{P}_{T}(M,\kappa)}{\sup}\sup_{G\in\mathcal{G}}\sup_{x\in\mathcal{X}}\mathop{\mbox{\sf
E}}{{}_{P_{T}}}[\mathcal{W}_{T}(G|x)-\mathcal{W}_{T}(\hat{G}_{x}|x)]\leq
c_{1}(\sqrt{(T-1)h}^{-1}+{(T-1)}^{-1}+h^{2}).$

Setting $h=O(T^{-1/5})$, the right hand side bound is $O(T^{-2/5})$.

A proof is presented in Appendix A.8.3.

####  A.8.3 Proof of Theorem A.1

For simplicity, we maintain Assumption 3.1, and one of its implication is
which implies (26)

In addition to (87) and (88), we define

$\displaystyle\widetilde{\mathcal{W}}_{h}(G,x)$ $\displaystyle=$
$\displaystyle\frac{\sum_{t=1}^{T-1}K_{h}(X_{t-1},x)\mathop{\mbox{\sf
E}}\big{[}\frac{Y_{t}W_{t}}{e_{t}(X_{t-1})}1(X_{t-1}\in
G)+\frac{Y_{t}(1-W_{t})}{1-e_{t}(X_{t-1})}1(X_{t-1}\notin
G)|\mathcal{F}_{t-1}\big{]}}{\sum_{t=1}^{T-1}K_{h}(X_{t-1},x)}$
$\displaystyle=$
$\displaystyle\frac{\sum_{t=1}^{T-1}K_{h}(X_{t-1},x)\mathcal{W}_{t}(G|\mathcal{F}_{t-1})}{\sum_{t=1}^{T-1}K_{h}(X_{t-1},x)},$

where $K(\cdot)$ is a bounded kernel with a bounded support,
$K_{h}(a,b):=\frac{1}{h}K(\frac{a-b}{h})$. The second equality follows from
Assumption 3.3.

Our strategy is to show for any $x\in\mathcal{X}$ and any $G\in\mathcal{G}$:

$\displaystyle\mathcal{W}_{T}(G|x)-\mathcal{W}_{T}(\hat{G}|x)$
$\displaystyle\leq
c\big{[}\bar{\mathcal{W}}_{h}(G|x)-\bar{\mathcal{W}}_{h}(\hat{G}|x)\big{]}$
$\displaystyle\leq
c\big{[}\widetilde{\mathcal{W}}_{h}(G,x)-\widetilde{\mathcal{W}}_{h}(\hat{G},x)\big{]}+O_{p}(h^{2})+O_{p}(c_{w}^{-1}(\sqrt{(T-1)h})^{-1})$
$\displaystyle\leq\sup_{G\in\mathcal{G}}2c|\widetilde{\mathcal{W}}_{h}(G,x)-\widehat{\mathcal{W}}(G|x)|+O_{p}(h^{2})+O_{p}(c_{w}^{-1}(\sqrt{(T-1)h})^{-1})$
$\displaystyle=O_{p}(h^{2})+O_{p}(c_{w}^{-1}(\sqrt{(T-1)h})^{-1})$

where the first inequality follows from Assumption A.1. The second inequality
follows from Lemma A.5 below. The third inequality follows from similar
arguments to (2.3). The last equality follows from Lemma A.6 stated below.

We present these two lemmas and their proofs. First, let us impose

######  Assumption A.2.

$X_{t}$ is one dimensional covariate. Let $c_{m}$, $c_{k}$, and $c_{w}$ be
positive constants. (i) The kernel function $K(x)$ is bounded and has bounded
support: $K(x)=0$ if $|X|>c_{k}$. $\mathop{\mbox{\sf
E}}(K^{2}(\frac{X_{t}-x}{h})|\mathcal{F}_{t-1})\leq c_{m}$, and
$\mbox{min}_{t,x}\mathop{\mbox{\sf E}}(K((X_{t}-x)/h)|\mathcal{F}_{t-1})\geq
c_{w}$; (ii) $\mathcal{W}_{t}(G|x)$ is second order differentiable w.r.t $x$
that is in the interior point of its support $\mathcal{X}$, which is also
bounded; (iii) $\int K(u)^{2}du$ is bounded.

######  LEMMA A.5.

Under Assumption A.2 For any $G\in\mathcal{G}$ and $x\in\mathcal{X}$,

$\widetilde{\mathcal{W}}_{h}(G,x)-\bar{\mathcal{W}}_{h}(G|x)=O_{p}(h^{2})+O_{p}(c_{w}^{-1}(\sqrt{(T-1)h})^{-1}).$

###### Proof.

Under Assumption A.2,

$\displaystyle\bigg{[}\widetilde{\mathcal{W}}_{h}(G,x)-\bar{\mathcal{W}}_{h}(G|x)\bigg{]}\bigg{[}\frac{1}{T-1}\sum_{t=1}^{T-1}K_{h}(X_{t-1},x)\bigg{]}$
$\displaystyle=\frac{1}{T-1}\sum_{t=1}^{T-1}K_{h}(X_{t-1},x)(\mathcal{W}_{t}(G|X_{t-1})-\mathcal{W}_{t}(G|x))$
$\displaystyle=\frac{1}{T-1}\sum_{t=1}^{T-1}\bigg{\\{}K_{h}(X_{t-1},x)(\mathcal{W}_{t}(G|X_{t-1})-\mathcal{W}_{t}(G|x))$
$\displaystyle-\mathop{\mbox{\sf
E}}[K_{h}(X_{t-1},x)(\mathcal{W}_{t}(G|X_{t-1})-\mathcal{W}_{t}(G|x))|\mathcal{F}_{t-2}]\bigg{\\}}$
$\displaystyle+\frac{1}{T-1}\sum_{t=1}^{T-1}\bigg{\\{}\mathop{\mbox{\sf
E}}[K_{h}(X_{t-1},x)(\mathcal{W}_{t}(G|X_{t-1})-\mathcal{W}_{t}(G|x))|\mathcal{F}_{t-2}]\bigg{\\}}.$

Rearranging the equation we have

$\displaystyle\widetilde{\mathcal{W}}_{h}(G,x)-\bar{\mathcal{W}}_{h}(G|x)=O_{p}(c_{1}^{-1}(\sqrt{(T-1)h})^{-1})+O_{p}(h^{2}),$

where the first term on the right hand side follows from Theorem 3.1 and the
second term follows from the standard result concerning the bias of the kernel
estimator. ∎

######  LEMMA A.6.

Under Assumption A.2,

$\sup_{G\in\mathcal{G}}\sup_{x\in\mathcal{X}}|\widehat{\mathcal{W}}(G|x)-\widetilde{\mathcal{W}}_{h}(G,x)|\lesssim_{p}c_{w}^{-1}(\sqrt{(T-1)h}^{-1}).$
(90)

###### Proof.

Note

$\displaystyle\sup_{G\in\mathcal{G}}\sup_{x\in\mathcal{X}}|\widehat{\mathcal{W}}(G|x)-\widetilde{\mathcal{W}}_{h}(G,x)|$
$\displaystyle\leq$
$\displaystyle\sup_{G\in\mathcal{G}}\sup_{x\in\mathcal{X}}\sum_{t=1}^{T-1}K_{h}(X_{t-1},x)(\widehat{\mathcal{W}}_{t}(G)-\mathcal{W}_{t}(G|\mathcal{F}_{t-1}))/\sum_{t=1}^{T-1}K_{h}(X_{t-1},x)$

We just look at the numerator,
$\sup_{G\in\mathcal{G}}\sup_{x\in\mathcal{X}}\sum_{t=1}^{T-1}K_{h}(X_{t-1},x)(\widehat{\mathcal{W}}_{t}(G)-\mathcal{W}_{t}(G|\mathcal{F}_{t-1}))$.

Suppose the order statistics of $X_{t}$ is $X_{(1)},\cdots,X_{(T-1)}$.
$B_{x,h}=\\{t:|(x-x_{t})/h|\leq c_{k}\\}$.

Because of summation by part, the numerator is bounded by

$\displaystyle\sup_{G\in\mathcal{G}}\sup_{x\in\mathcal{X}}|\sum_{t}^{T-1}K_{h}(X_{(t)},x)-K_{h}(X_{(t-1)},x)|$
$\displaystyle\max_{1\leq l\leq T-1,t\in B_{x,h}}|\sum^{l}_{t=1,t\in
B_{x,h}}(\widehat{\mathcal{W}}_{t}(G)-\mathcal{W}_{t}(G|\mathcal{F}_{t-1}))|$
$\displaystyle+\sup_{G\in\mathcal{G}}\sup_{x\in\mathcal{X}}|K_{h}(X_{(T-1)},x)||\sum_{t\in
B_{x,h}}(\widehat{\mathcal{W}}_{t}(G)-\mathcal{W}_{t}(G|\mathcal{F}_{t-1}))|$
$\displaystyle\lesssim_{p}h^{-1}\sup_{G}|\sum_{t\in
B_{x,h}}(\widehat{\mathcal{W}}_{t}(G)-\mathcal{W}_{t}(G|\mathcal{F}_{t-1}))|.$

$|\sum_{t}^{T-1}[K_{h}(X_{(t)},x)-K_{h}(X_{(t-1)},x)]|\lesssim_{p}h^{-1}$ if
the total variation of the function $hK_{h}(.,x)$ is bounded.
$\sup_{G\in\mathcal{G}}(T-1)^{-1}|\sum_{t\in
B_{x,h}}(\widehat{\mathcal{W}}_{t}(G)-\mathcal{W}_{t}(G|\mathcal{F}_{t-1}))|\lesssim_{p}(\sqrt{h}/{\sqrt{T-1}}),$
where $\lesssim_{p}$ follows from $|\widehat{\mathcal{W}}_{t}(G)|\leq M$.

For the denominator,
$(T-1)^{-1}\sum_{t=1}^{T-1}\\{K_{h}(X_{t-1},x)-\mathop{\mbox{\sf
E}}(K_{h}(X_{t-1},x)|X_{t-2})\\}\lesssim_{p}1/\sqrt{h(T-1)}+(T-1)^{-1},$ where
$\lesssim_{p}$ follows from $c_{m}$, $\int K(u)^{2}du$ and the bound on the
kernel function as assumed in Assumption A.2. Due to the boundedness of
$\mathop{\mbox{\sf E}}(K_{h}(X_{t-1},x)|\mathcal{F}_{t-2})$ from the
Assumption A.2, by following similar steps to the proof of (22), we have

$\sup_{G\in\mathcal{G}}\sup_{x\in\mathcal{X}}|\widehat{\mathcal{W}}(G|X_{T-1}=x)-\bar{\mathcal{W}}(G|X_{T-1}=x)|\lesssim_{p}c_{w}^{-1}(\sqrt{(T-1)h}^{-1}).$
(91)

∎

###  A.9 Proof of Theorem 4.1

###### Proof.

Under policy $G$, we use (restate) the following notation:

$\widetilde{\mathcal{W}}(G)$ is defined in (3.2).

$\widehat{\mathcal{W}}(G)$ represents the estimated welfare defined in (32).

$\widehat{\mathcal{W}}^{\hat{e}}(G)$ represents the estimated welfare, with
the estimated propensity score $\hat{e}(\cdot)$,

$\displaystyle\widehat{\mathcal{W}}^{\hat{e}}(G)=\frac{1}{T-1}\sum_{t=1}^{T-1}\left[\frac{Y_{t}W_{t}}{\hat{e}_{t}(X_{t-1})}1(X_{t-1}\in
G)+\frac{Y_{t}(1-W_{t})}{1-\hat{e}_{t}(X_{t-1})}1(X_{t-1}\notin G)\right],$

We let $G_{*}$ denote an arbitrary element in $\mathcal{G}$. Let
$\hat{G}^{\hat{e}}$ be the optimal policy estimated using the estimated
propensity score $\hat{e}(\cdot)$,

$\hat{G}^{\hat{e}}\overset{\text{def}}{=}\underset{G\in\mathcal{G}}{\text{argmax
}}\widehat{\mathcal{W}}^{\hat{e}}(G).$ (92)

Recall
$\tau_{t}=\frac{Y_{t}W_{t}}{e_{t}(W_{t-1})}-\frac{Y_{t}(1-W_{t})}{1-e_{t}(W_{t-1})}$
and
$\hat{\tau}_{t}=\frac{Y_{t}W_{t}}{\hat{e}_{t}(W_{t-1})}-\frac{Y_{t}(1-W_{t})}{1-\hat{e}_{t}(W_{t-1})}$.
Similar to (A.29) in the supplementary material for Kitagawa and Tetenov
[2018]

$\displaystyle\widetilde{\mathcal{W}}(G_{*})-\widetilde{\mathcal{W}}(\hat{G}^{\hat{e}}),$
$\displaystyle=\widetilde{\mathcal{W}}(G_{*})-\widetilde{\mathcal{W}}(\hat{G}^{\hat{e}})+\left[\widehat{\mathcal{W}}^{\hat{e}}(G_{*})-\widehat{\mathcal{W}}^{\hat{e}}(G_{*})\right]+\left[\widehat{\mathcal{W}}(\hat{G}^{\hat{e}})-\widehat{\mathcal{W}}(\hat{G}^{\hat{e}})\right]+\left[\widehat{\mathcal{W}}(G_{*})-\widehat{\mathcal{W}}(G_{*})\right]$
$\displaystyle\leq\widetilde{\mathcal{W}}(G_{*})-\widetilde{\mathcal{W}}(\hat{G}^{\hat{e}})+\left[\widehat{\mathcal{W}}^{\hat{e}}(\hat{G}^{\hat{e}})-\widehat{\mathcal{W}}^{\hat{e}}(G_{*})\right]+\left[\widehat{\mathcal{W}}(\hat{G}^{\hat{e}})-\widehat{\mathcal{W}}(\hat{G}^{\hat{e}})\right]+\left[\widehat{\mathcal{W}}(G_{*})-\widehat{\mathcal{W}}(G_{*})\right]$
$\displaystyle=\left[\widehat{\mathcal{W}}(G_{*})-\widehat{\mathcal{W}}^{\hat{e}}(G_{*})-\widehat{\mathcal{W}}(\hat{G}^{\hat{e}})+\widehat{\mathcal{W}}^{\hat{e}}(\hat{G}^{\hat{e}})\right]+\left[\widetilde{\mathcal{W}}(G_{*})-\widetilde{\mathcal{W}}(\hat{G}^{\hat{e}})-\widehat{\mathcal{W}}(G_{*})+\widehat{\mathcal{W}}(\hat{G}^{\hat{e}})\right]$
$\displaystyle=I^{\hat{e}}+II^{\hat{e}},$ (93)

where the first inequality comes from
$\widehat{\mathcal{W}}^{\hat{e}}(\hat{G}^{\hat{e}})\geq\widehat{\mathcal{W}}^{\hat{e}}(G_{*})$,
which is implied by the definition (92).

For $II^{\hat{e}}$, we know $II^{\hat{e}}\leq
2\sup_{G\in\mathcal{G}}|\widetilde{\mathcal{W}}(G)-\widehat{\mathcal{W}}(G)|$.
Similar arguments to Section 3.2 can then be used to bound it.

For $I^{\hat{e}}$, Note that for any $G\in\mathcal{G}$

$\displaystyle\widehat{\mathcal{W}}(G)$
$\displaystyle=\frac{1}{T-1}\sum_{t=1}^{T-1}[\frac{Y_{t}W_{t}}{e_{t}(X_{t-1})}1(X_{t-1}\in
G)+\frac{Y_{t}(1-W_{t})}{1-e_{t}(X_{t-1})}1(X_{t-1}\notin G)]$ (94)
$\displaystyle=\frac{1}{T-1}\sum_{t=1}^{T-1}[\tau_{t}1(X_{t-1}\in
G)+\frac{Y_{t}(1-W_{t})}{1-e_{t}(X_{t-1})}]$

Similarly,

$\displaystyle\widehat{\mathcal{W}}^{\hat{e}}(G)=\frac{1}{T-1}\sum_{t=1}^{T-1}[\hat{\tau}_{t}1(X_{t-1}\in
G)+\frac{Y_{t}(1-W_{t})}{1-\hat{e}_{t}(X_{t-1})}]$ (95)

Combining (94) and (95) with $I^{\hat{e}}$,

$\displaystyle\widehat{\mathcal{W}}(G_{*})-\widehat{\mathcal{W}}(\hat{G}^{\hat{e}})$
$\displaystyle=\frac{1}{T-1}\sum_{t=1}^{T-1}\tau_{t}\left[\mathbf{1}\\{X_{t-p-1}\in
G_{*}\\}-\mathbf{1}\\{X_{t-p-1}\in\hat{G}^{\hat{e}}\\}\right]$
$\displaystyle\widehat{\mathcal{W}}^{\hat{e}}(G_{*})-\widehat{\mathcal{W}}^{\hat{e}}(\hat{G}^{\hat{e}})$
$\displaystyle=\frac{1}{T-1}\sum_{t=1}^{T-1}\hat{\tau}_{t}\left[\mathbf{1}\\{X_{t-p-1}\in
G_{*}\\}-\mathbf{1}\\{X_{t-p-1}\in\hat{G}^{\hat{e}}\\}\right].$

Then,

$\displaystyle I^{\hat{e}}$
$\displaystyle=\widehat{\mathcal{W}}(G_{*}){\normalcolor-\widehat{\mathcal{W}}(\hat{G}^{\hat{e}})-[\widehat{\mathcal{W}}}^{\hat{e}}(G_{*})-{\color[rgb]{0,.5,.5}{\normalcolor\widehat{\mathcal{W}}^{\hat{e}}(\hat{G}^{\hat{e}})]}},$
$\displaystyle=\frac{1}{T-1}\sum_{t=1}^{T-1}\left[\left(\tau_{t}-\hat{\tau}_{t}\right)\cdot
1\\{X_{i}\in G_{*}\\}-\left(\tau_{t}-\hat{\tau}_{t}\right)\cdot
1\\{X_{i}\in\hat{G}^{\hat{e}}\\}\right],$
$\displaystyle=\frac{1}{T-1}\sum_{t=1}^{T-1}\left[\left(\tau_{t}-\hat{\tau}_{t}\right)\left(1\\{X_{i}\in
G_{*}\\}-1\\{X_{i}\in\hat{G}^{\hat{e}}\\}\right)\right],$
$\displaystyle\leq\frac{1}{T-1}\sum_{t=1}^{T-1}|\tau_{t}-\hat{\tau}_{t}|.$

Finally, we have that the rate of convergence is bounded by the accuracy of
propensity score estimation and the bound with known propensity scores,

$\displaystyle\mathop{\mbox{\sf
E}}{{}_{P_{T}}}[\mathcal{W}_{T}(G_{*})-\mathcal{W}_{T}(\hat{G}^{\hat{e}})]$
$\displaystyle\leq\mathop{\mbox{\sf
E}}{{}_{P_{T}}}\left[\frac{1}{T-1}\sum_{t=1}^{T-1}|\tau_{t}-\hat{\tau}_{t}|\right]$
$\displaystyle+2\mathop{\mbox{\sf
E}}{{}_{P_{T}}}\left[\sup_{G\in\mathcal{G}}|\widetilde{\mathcal{W}}(G)-\widehat{\mathcal{W}}(G)|\right].$

The statement of Theorem 4.1 follows by (56) and Theorem 3.3.

∎

##  Appendix B Online Appendix: other Results and Extensions

###  B.1 Link to Markov decision problems

In this section, we show the connection between our T-EWM setup and models of
Markov Decision Processes (MDP). For MDP, we adapt the notation of Kallenberg
[2016], an online lecture notes by Lodewijk Kallenberg (LK hereafter). As
described in LK, MDP are models for making decisions for dependent data. A MDP
typically has components $\\{[p_{ij}(a)]_{i,j},r_{i}^{t}(a),W_{t-1}\\}$. In
period $t$, $W_{t-1}$ is the state and $W_{t}$ is the action. The agent
chooses their decision according to a policy (a map from the state $W_{t-1}$
to an action $a$). They then receive a reward $r_{i}^{t}(a)$. The reward
function depends on the transition probabilities of a Markov process, which
are determined by the action $a$. Thus their action affects the reward via its
effect on the transition probability matrix. The optimal policy is estimated
by optimizing an aggregated reward function. We show a formal link between our
T-EWM framework and an MDP. In particular, we show that the MDP’s reward
function corresponds to our welfare function, and the optimal mapping between
states and actions corresponds to the EWM policy in our framework.

In the following equations, the left-hand sides are the notation for MDP in
LK, and the right-hand sides are notation for T-EWM from this paper. We
consider the model of Section 2.2. For $i,j,a\in\\{0,1\\}$, at time $t$:
First, we link the transition probability with the propensity score.

$\displaystyle p_{ij}^{t}(a)$
$\displaystyle=P(W_{t}=j|W_{t-1}=i;\text{choosing }W_{t}=a),$

The left-hand side is the Markov transition probability between states $i$ and
$j$ under policy $a$. The right-hand side is a propensity score under policy
$a$: the probability $W_{t}=j$, conditional on $W_{t-1}=i$, given $W_{t}=a$.
Note that, in this simple model, the state at time $t$ is the previous
treatment $W_{t-1}$, and the current policy and the next-period state are both
$W_{t}$. In our setting, after time $T-1$, the SP implements a deterministic
policy, so the probability only takes values in $\\{0,1\\}$, i.e.,

$\displaystyle p_{ij}^{t}(a)$ $\displaystyle=1\text{ if }j=a.$ $\displaystyle
p_{ij}^{t}(a)$ $\displaystyle=0\text{ if }j\neq a.$ (96)

Secondly, we connect the reward function with the expected conditional
counterfactual outcome. We denote the reward associated with action $a$ for
state $i$ at time $t$ as

$\displaystyle r_{i}^{t}(a)$ $\displaystyle=\mathop{\mbox{\sf
E}}\left[Y_{t}(a)|W_{t-1}=i\right],$ (97)

The left-hand side is the reward in state $i$ under action $a$. The right-hand
side is the conditional expected counterfactual outcome of $Y_{t}(a)$, (recall
$a\in\\{0,1\\}$) conditional on $W_{t-1}=i$.

Thirdly, we link the expected reward function and the expected unconditional
counterfactual outcome.

$\displaystyle\left\\{\sum_{i}\beta_{i}r_{i}^{t}(a)=r^{t}(a)\right\\}$
$\displaystyle=\mathop{\mbox{\sf E}}\left[Y_{t}(a)\right],$

The left-hand side is the expected reward for action $a$, with $\beta_{i}$ as
the initial probability of state $i$. The right-hand side is the unconditional
expected counterfactual outcome.

Finally, we show the link between the total expected reward over a finite
horizon and the finite-period welfare function

$\displaystyle\left\\{v_{i}^{T:T+1}(R):=\mathop{\mbox{\sf
E}}{{}_{i,R}}\left[\sum_{k=T}^{T+1}r_{X_{k}}^{k}(Y_{k})\right]\right\\}$
$\displaystyle=\mathop{\mbox{\sf
E}}\bigg{\\{}Y_{T}(1)p_{i1}^{T}\left(g_{1}(W_{T-1})\right)+Y_{T}(0)p_{i0}^{T}\left(g_{1}(W_{T-1})\right)$
$\displaystyle+Y_{T+1}(1)p_{i1}^{T+1}\left(g_{2}(W_{T})\right)+Y_{T+1}(0)p_{i0}^{T+1}\left(g_{2}(W_{T})\right)|W_{T-1}=i\bigg{\\}}$
$\displaystyle=\mathop{\mbox{\sf
E}}\left\\{Y_{T}(1)g_{1}(W_{T-1})+Y_{T}(0)\left[1-g_{1}(W_{T-1})\right]|W_{T-1}=i\right\\}$
$\displaystyle+\mathop{\mbox{\sf
E}}\left\\{Y_{T+1}(1)g_{2}\left(W_{T}\right)+Y_{T+1}(0)\left[1-g_{2}\left(W_{T}\right)\right]|W_{T}=g_{1}(i)\right\\},$
(98)

The left-hand side is the total expected reward over the planning horizon from
$T$ to $T+1$ under the policy $R=(g_{1},g_{2})$, with the initial state $i$.
The last equality follows from (96) and the exclusion condition.

With these connections established, we can regard EMW as an MDP with a finite
period reward and a non-stationary solution. According to LK, in this case the
policy $R$ is usually obtained by using a backward induction algorithm.

Note that, for multi-period welfare functions, if the welfare function has a
finite horizon (as in the case discussed in here), the optimal policy is often
nonstationary. See Chapter 2 of Kallenberg [2016] for more details about
finite horizon MDPs.

###  B.2 The relationship between the conditional and unconditional cases

In this section, we present further examples to illustrate that
$G_{\text{FB}}^{*}\in\mathcal{G}$ is a sufficient but not necessary condition
for equivalence between the unconditional and conditional problems. Finally,
we extend Example A.1 to show how Assumption 3.4 ensures this equivalence.

####  B.2.1 $G_{\text{FB}}^{*}\in\mathcal{G}$ is sufficient: a discrete and a
continuous case

Let $X_{t-1}=W_{t-1}\in\\{0,1\\}$. $\mathcal{G}$ be a subclass of the power
set of $\\{0,1\\}$,
$\mathcal{P}=\left\\{\emptyset,\\{0\\},\\{1\\},\\{0,1\\}\right\\}$.

For compactness, suppress $W_{T-1}$ in $Y_{T}(W_{T-1},1)$. Unconditional
welfare can be written as:

$\displaystyle\mathcal{W}_{T}(G)=$
$\displaystyle\mathsf{E}\left\\{Y_{T}(1)\mathbf{1}(W_{T-1}\in
G)+Y_{T}(0)\mathbf{1}(W_{T-1}\notin G)\right\\}$ $\displaystyle=$
$\displaystyle\mathsf{E}\left\\{\left[Y_{T}(1)-Y_{T}(0)\right]\mathbf{1}(W_{T-1}\in
G)+Y_{T}(0)\right\\}$ $\displaystyle=$
$\displaystyle\mathsf{E}\left[\tau(W_{T-1})\mathbf{1}(W_{T-1}\in
G)\right]+\mathsf{E}\left[Y_{T}(0)\right],$ (99)

where
$\tau(w_{T-1})=\mathsf{E}\left[Y_{T}(1)-Y_{T}(0)|W_{T-1}=w_{T-1}\right]$, and
the last equality follows from the law of iterated expectations.

The first best unconditional policy is

$G_{\text{FB}}^{*}\equiv\\{w_{T-1}\in\\{0,1\\}:\tau(w_{T-1})\geq 0\\}.$ (100)

By the assumption that $G_{\text{FB}}^{*}\in\mathcal{G}$

$G_{\text{FB}}^{*}=\mbox{argmax}_{G\in\mathcal{G}}\mathcal{W}_{T}(G).$ (101)

The SP’s conditional objective function can be written as:

$\displaystyle\mathcal{W}_{T}(G|W_{T-1})$
$\displaystyle=\mathsf{E}\left\\{Y_{T}(1)\mathbf{1}(W_{T-1}\in
G)+Y_{T}(0)\mathbf{1}(W_{T-1}\notin G)|W_{T-1}\right\\}$
$\displaystyle=\mathsf{E}\left\\{\left[Y_{T}(1)-Y_{T}(0)\right]\mathbf{1}(W_{T-1}\in
G)+Y_{T}(0)|W_{T-1}\right\\}$
$\displaystyle=\mathsf{E}\left\\{\left[Y_{T}(1)-Y_{T}(0)\right]\mathbf{1}(W_{T-1}\in
G)|W_{T-1}\right\\}+\mathsf{E}\left[Y_{T}(0)|W_{T-1}\right]$
$\displaystyle=\mathsf{E}\left[\tau(W_{T-1})\mathbf{1}(W_{T-1}\in
G)|W_{T-1}\right]+\mathsf{E}\left[Y_{T}(0)|W_{T-1}\right].$ (102)

To check whether $G_{\text{FB}}^{*}$ is optimal in the conditional problem, we
need to study this problem w.r.t. $\mathcal{P}$

$\displaystyle\underset{G\in\mathcal{\mathcal{P}}}{\mbox{max
}}\mathcal{W}_{T}(G|W_{T-1}=w_{T-1})$ $\displaystyle=$
$\displaystyle\underset{G\in\mathcal{\mathcal{P}}}{\mbox{max
}}\mathsf{E}\left[\tau(W_{T-1})\mathbf{1}(W_{T-1}\in
G)|W_{T-1}=w_{T-1}\right]$ $\displaystyle=$
$\displaystyle\underset{G\in\mathcal{\mathcal{P}}}{\mbox{max
}}\tau(w_{T-1})\mathbf{1}(w_{T-1}\in G)$ $\displaystyle=$
$\displaystyle\tau(w_{T-1})\mathbf{1}(w_{T-1}\in G_{\text{FB}}^{*}),$ (103)

The first equality follows from (102). The last follows from the definition of
$G_{\text{FB}}^{*}$ in (100).

Equivalence follows by combining (101) and (103).

We now turn the continuous conditioning variable case.

The SP’s unconditional welfare function can be rewritten as (suppressing
$W_{T-1}$ in $Y_{T}(W_{T-1},1).$)

$\displaystyle\mathcal{W}_{T}(G)=$
$\displaystyle\mathsf{E}\left\\{Y_{T}(1)\mathbf{1}(X_{T-1}\in
G)+Y_{T}(0)\mathbf{1}(X_{T-1}\notin G)\right\\}$ $\displaystyle=$
$\displaystyle\mathsf{E}\left\\{\left[Y_{T}(1)-Y_{T}(0)\right]\mathbf{1}(X_{T-1}\in
G)+Y_{T}(0)\right\\}$ $\displaystyle=$
$\displaystyle\mathsf{E}\left[\tau(X_{T-1})\mathbf{1}(X_{T-1}\in
G)\right]+\mathsf{E}\left[Y_{T}(0)\right],$

where
$\tau(x_{T-1})=\mathsf{E}\left[Y_{T}(1)-Y_{t}(0)|X_{T-1}=x_{T-1}\right]$, and
the last equality follows from the law of iterated expectations.

The first best policy is

$G_{\text{FB}}^{*}\equiv\\{x_{T-1}\in\mathbb{R}^{2}:\tau(x_{T-1})\geq 0\\}.$
(104)

(For simplicity, we assume that $G_{\text{FB}}^{*}$ is measurable, i.e.,
$G_{\text{FB}}^{*}\in\mathfrak{B}(\mathbb{R}^{2})\subset\mathcal{P}(\mathbb{R}^{2})$.
This means that we don’t have to deal with the outer probability and
expectation.) By assumption $G_{\text{FB}}^{*}\in\mathcal{G}$,

$G_{\text{FB}}^{*}\in\mbox{argmax}_{G\in\mathcal{G}}\mathcal{W}_{T}(G).$ (105)

We now introduce some notation. Let
$X_{t-1}=[X_{t-1}^{(1)},X_{t-1}^{(2)}]^{\prime}\in\mathbb{R}^{2}$.
$X_{t-1}^{(1)}$ and $X_{t-1}^{(2)}$ can be continuous or discrete, e.g., one
of them can be the treatment $W_{t-1}.$ Let $\mathcal{G}$ be a class of
subsets of $\mathbb{R}^{2}$, and $\mathcal{G}^{(1)}$ a class of subsets of
$\mathbb{R}.$ The SP’s conditional objective function can be written as:

$\displaystyle\mathcal{W}_{T}(G^{(1)}|X_{T-1}^{(2)})$ $\displaystyle=$
$\displaystyle\mathsf{E}\left\\{Y_{T}(1)\mathbf{1}(X_{T-1}^{(1)}\in
G^{(1)})+Y_{T}(0)\mathbf{1}(X_{T-1}^{(1)}\notin
G^{(1)})|X_{T-1}^{(2)}\right\\}$ $\displaystyle=$
$\displaystyle\mathsf{E}\left\\{\left[Y_{T}(1)-Y_{T}(0)\right]\mathbf{1}(X_{T-1}^{(1)}\in
G^{(1)})+Y_{T}(0)|X_{T-1}^{(2)}\right\\}$ $\displaystyle=$
$\displaystyle\mathsf{E}\left\\{\left[Y_{T}(1)-Y_{T}(0)\right]\mathbf{1}(X_{T-1}^{(1)}\in
G^{(1)})|X_{T-1}^{(2)}\right\\}+\mathsf{E}\left[Y_{T}(0)|X_{T-1}^{(2)}\right]$
$\displaystyle=$
$\displaystyle\mathsf{E}\left\\{\mathsf{E}\left[\tau(X_{T-1})\mathbf{1}(X_{T-1}^{(1)}\in
G^{(1)})|X_{T-1}\right]|X_{T-1}^{(2)}\right\\}+\mathsf{E}\left[Y_{T}(0)|X_{T-1}^{(2)}\right],$
(106)

where the last equality follows from the law of iterated expectations.

We also assume that the conditional first-best policy $G_{\text{CFB}}^{*}$ is
measurable, i.e.,
$G_{\text{CFB}}^{*}(X_{T-1}^{(2)}=x_{T-1}^{(2)})\in\mathfrak{B}(\mathbb{R})$,
for every $x_{T-1}^{(2)}\in\mathbb{R}.$ Note
$\tau(x_{t-1})=\tau(x_{t-1}^{(1)},x_{t-1}^{(2)}).$ Following the last row of
(106), the optimal conditional policy is defined to be

$\displaystyle\text{argmax}_{G^{(1)}\in\mathfrak{B}(\mathbb{R})}\mathcal{W}_{T}(G^{(1)}|X_{T-1}^{(2)}=x_{T-1}^{(2)})$
$\displaystyle=$
$\displaystyle\text{argmax}_{G^{(1)}\in\mathfrak{B}(\mathbb{R})}\mathsf{E}\left\\{\mathsf{E}\left[\tau(X_{T-1})\mathbf{1}(X_{T-1}^{(1)}\in
G^{(1)})|X_{T-1}\right]|X_{T-1}^{(2)}=x_{T-1}^{(2)})\right\\}$
$\displaystyle=$
$\displaystyle\text{argmax}_{G^{(1)}\in\mathfrak{B}(\mathbb{R})}\mathsf{E}\left\\{\mathsf{E}\left[\tau(X_{T-1}^{(1)},x_{T-1}^{(2)})\mathbf{1}(X_{T-1}^{(1)}\in
G^{(1)})|X_{T-1}^{(1)}\right]\right\\}$ $\displaystyle=$
$\displaystyle\text{argmax}_{G^{(1)}\in\mathfrak{B}(\mathbb{R})}\mathsf{E}\left[\tau(X_{T-1}^{(1)},x_{T-1}^{(2)})\mathbf{1}(X_{T-1}^{(1)}\in
G^{(1)})\right].$

The optimal policy conditional on $X_{T-1}^{(2)}=x_{T-1}^{(2)}$ is

$G_{\text{CFB}}^{*}(X_{T-1}^{(2)}=x_{T-1}^{(2)})=\\{x_{T-1}^{(1)}\in\mathbb{R}:\tau(x_{T-1}^{(1)},x_{T-1}^{(2)})\geq
0\\}.$ (107)

Comparing (104) and (107), we see
$G_{\text{CFB}}^{*}(X_{T-1}^{(2)}=x_{T-1}^{(2)})$ is given by the intersection
of $G_{\text{FB}}^{*}$ with the line $X_{T-1}^{(2)}=x_{T-1}^{(2)}$.

####  B.2.2 $G_{\text{FB}}^{*}\in\mathcal{G}$ is not a necessary condition

Here we show that $G_{\text{FB}}^{*}\in\mathcal{G}$ is sufficient but not
necessary for correspondence between the optimal conditional policy and the
first-best unconditional policy.

######  Example B.1.

Univariate covariates

We set $X_{t-1}=W_{t-1}\in\\{0,1\\}$ and
$\mathcal{G}=\left\\{\emptyset,\\{1\\}\right\\}\subset\mathcal{P}=\left\\{\emptyset,\\{0\\},\\{1\\},\\{0,1\\}\right\\}.$
Suppose

$\tau(1)=\tau(0)=1>0.$

For the unconditional problem (99), the first best policy is then

$G_{\text{FB}}^{*}=\\{0,1\\}.$

Note that $G_{\text{FB}}^{*}\notin\mathcal{G}$, so the solution to the
unconditional problem is

$G_{*}\equiv\underset{G\in\mathcal{G}}{\mbox{argmax
}}\mathcal{W}_{T}(G)=\\{1\\}.$

Consider the conditional problem for $W_{T-1}=1$.

$\displaystyle\underset{G\in\mathcal{\mathcal{P}}}{\mbox{max
}}\mathcal{W}_{T}(G|W_{T-1}=1)$ $\displaystyle=$
$\displaystyle\underset{G\in\mathcal{\mathcal{P}}}{\mbox{max
}}\mathsf{E}\left[\tau(W_{T-1})\mathbf{1}(W_{T-1}\in G)|W_{T-1}=1\right]$
$\displaystyle=$ $\displaystyle\underset{G\in\mathcal{\mathcal{P}}}{\mbox{max
}}\tau(1)\mathbf{1}(1\in G)$ $\displaystyle=$
$\displaystyle\tau(1)\mathbf{1}(1\in G_{*}).$ (108)

Therefore, the solution to the unconditional problem is also the solution to
the conditional problem. (This is only the case for $W_{T-1}=1.$)

######  Example B.2.

Two dimensional discrete covariates

Set
$X_{t-1}=\left(W_{t-1},Z_{t-1}\right)^{\prime}\in\\{0,1\\}\times\\{i\\}_{i=0}^{10}$.
Suppose

$G_{\text{FB}}^{*}=\\{0,1\\}\times\\{1,3,5,7,9\\}.$

and

$\mathcal{G}=\left\\{\begin{array}[]{c}\left\\{\left(w,z\right):w\in\\{0,1\\},z\in\\{i\\}_{i=0}^{10}\text{,
and }z\in[0,a)\right\\},\\\ a\in\mathbb{R}^{+}\end{array}\right\\}.$

For example, if $G\in\mathcal{G}$ and $a=4.5$, $(0,4)\in G$, so $(0,0)$,
(0,1), (0,2), and (0,3) are also in $G$.

Note that $G_{\text{FB}}^{*}\notin\mathcal{G}$. Suppose the best feasible
unconditional policy is

$\displaystyle G_{*}$
$\displaystyle\equiv\underset{G\in\mathcal{G}}{\mbox{argmax
}}\mathcal{W}_{T}(G)=\\{0,1\\}\times\\{0,1,2,3,4,5\\},$

We can always construct a data generating process with a certain type of
conditional treatment effect $\tau$ to achieve that. For example, let
$\tau(x_{t-1})=\tau(w_{t-1},z_{t-1})$, set $P(Z_{t-1}=i)=1/10$, $Z_{t-1}\perp
W_{t-1}$, and for any $w\in\\{0,1\\}$ assume

$\tau(w,z)=\begin{cases}2&z\in\\{1,3,5\\}\\\ 0.1&z\in\\{7,9\\}\\\ -1.5&z\text{
is even}\end{cases}$

For example, a policy $G_{a}$ with $a=5.5$ will include $\\{w,2\\}$ and
$\\{w,4\\}$, which has a welfare cost of $2\times-1.5$.

The conditional problem is

$\displaystyle\underset{G^{z}\in\mathcal{G}^{z}}{\mbox{max
}}\mathcal{W}_{T}(G^{z}|W_{T-1}=w)$

where $\mathcal{G}^{z}=\left\\{z:z\in\\{i\\}_{i=1}^{10}\text{, and
}z\in[0,a),a\in\mathbb{R}^{+}\right\\}$. Here

$\displaystyle\underset{G^{z}\in\mathcal{G}^{z}}{\mbox{argmax
}}\mathcal{W}_{T}(G^{z}|W_{T-1}=w)$ $\displaystyle=$
$\displaystyle\\{1,2,3,4,5\\},$

which is the intersection of $G_{*}$ with $\text{Supp}(Z_{T-1})$. We have the
conclusion.

####  B.2.3 An illustration of Assumption 3.4

Recall Assumption 3.4

$\arg\sup_{G\in\mathcal{G}}\mathcal{W}_{T}(G)\subset\arg\sup_{G\in\mathcal{G}}\mathcal{W}_{T}(G|x).$

We extend Example A.1 to show why Assumption 3.4 ensures equivalence between
the unconditional and conditional problems.

Example A.1, continued.

Figure 11:  $G_{\text{FB}}^{*}\notin\mathcal{G}_{0}$ but Assumption 3.4 is
satisfied

Figure 11 shows a case where the solutions coincide even though the first best
unconditional policy is not available. The red square is differs from the
shaded area (the first best), but the red point is inside the red square, and
the blue point is inside the shaded area. The social planner will set
$W_{T}=1$ in both cases. Hence, the feasibility of the first best solution is
sufficient but not necessary for conditional and unconditional welfare to
coincide.

Thus, there exist situations where the first best solution is not feasible,
but we can still achieve correspondence. This example confirms the validity of
Assumption 3.4.

###  B.3 Improved rates with margin assumption

In this section, we show special cases where we can improve the rate by
imposing additional margin assumptions. Here we maintain the setting and
method of Section 3.2. In particular, we assume that the first best policy is
feasible, and we bound conditional regret with unconditional regret.

For simplicity, we assume that $X_{t}=\\{Y_{t},W_{t}\\}$ are strictly
stationary. We also use the compact notation $Y_{t}(W_{1:t-1},1)=Y_{t}(1)$ and
$Y_{t}(W_{1:t-1},0)=Y_{t}(0)$. Define

$\tau(W_{t-1})=\mathop{\mbox{\sf E}}((Y_{t}(1)-Y_{t}(0))|W_{t-1}).$

If we are willing to make stronger assumption on observations to have a very
small probability to fall into a small region near the margin of the above
optimal classification region, we can potentially achieve a better rate. For
detailed insight in the i.i.d. case, see, for example, Boucheron et al.
[2005]. Let

$\displaystyle\bar{\mathcal{W}}(g,W_{t-2})$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$
$\displaystyle(T-1)^{-1}\sum_{1\leq t\leq T-1}\mathop{\mbox{\sf
E}}\left\\{Y_{t}(W_{t-1},1)g(W_{t-1})+Y_{t}(W_{t-1},0)\left[1-g(W_{t-1})\right]|W_{t-2}\right\\}.$

$\displaystyle\bar{\mathcal{W}}(g)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$
$\displaystyle(T-1)^{-1}\sum_{1\leq t\leq T-1}\mathop{\mbox{\sf
E}}\left\\{Y_{t}(W_{t-1},1)g(W_{t-1})+Y_{t}(W_{t-1},0)\left[1-g(W_{t-1})\right]\right\\}.$

$\displaystyle{\widehat{\mathcal{W}}}(g)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$
$\displaystyle(T-1)^{-1}\sum_{1\leq t\leq
T-1}\left\\{Y_{t}(W_{t-1},1)g(W_{t-1})+Y_{t}(W_{t-1},0)\left[1-g(W_{t-1})\right]\right\\}.$

We shall assume that

######  Assumption B.1.

The first best treatment rule $g^{*}_{\text{FB}}$ defined in (29) belongs to
the class of candidate treatment rules $g$, i.e., $g^{*}_{\text{FB}}=g^{*}$.

######  Assumption B.2.

We assume that the class of treatment rules is finite and countable with
$|\mathcal{G}|=2\lesssim n^{V}$, where $V$ is a fixed integer.

######  Assumption B.3.

$Y_{t}(0),Y_{t}(1)$ belong to $[-C,C]$, where $C$ is a constant.

######  Assumption B.4.

The following margin condition is assumed. Let $\Pr_{t-1}$ be
$\Pr(.|\mathcal{F}_{t-2})$. There exists a constant $0\leq\eta\leq C$,
$0<\alpha<\infty$ and $0\leq u\leq\eta$, such that

$\displaystyle\max_{t}\Pr{{}_{t-1}}(|\tau(W_{t-1})|\leq
u)\leq(u/\eta)^{\alpha},\quad\quad\forall 0\leq u\leq\eta,$ (109)

the above assumption can be implied in the discrete case by the condition that
there exists a positive constant $c$ such that $\tau(0),\tau(1)>c$. Pick
$\eta=c$ then, we have $\alpha=\infty$, and
$\mathrm{P}_{t-1}(|\tau(W_{t-1})|\leq u)=0,\quad\forall 0\leq u\leq\eta.$
$\mathrm{P}_{{t-1}}(\cdot)=\text{Pr}(\cdot|{\mathcal{F}}_{t-2})$. Recall that
there exists a positive constant $\overline{P}$ such that
$\frac{1}{T-1}\sum_{t}\mathrm{P}_{{t-1}}(g^{*}(W_{t-1})\neq
g(W_{t-1}))\geq\overline{P}$.

######  Assumption B.5.

$\Pr(.|W_{t-2})$ and $\Pr(.|W_{t-1})$ are strictly positive.

######  THEOREM B.1.

Under Assumption B.1-B.5 and Assumption 3.3 , for a small enough positive
$\delta>0$, we have the follow bound, with probability $1-\delta$,

$\bar{\mathcal{W}}(g^{*})-\bar{\mathcal{W}}(\hat{g})\lesssim_{p}C_{\alpha,\eta,V}(\frac{\sqrt{\log(2T/\delta)}}{\sqrt{T-1}})^{2(\alpha+1)/(\alpha+2)},$

where $C_{\alpha,\eta,V}$ is a constant depending only on $\alpha$, $\eta$ and
$V$.

We can see that when $\alpha=0$, the rate becomes
$\frac{1}{\sqrt{T-1}}\sqrt{\log 2T/\delta}$, which means it has almost no
constraint. When $\alpha\to\infty$, it is approaching $\frac{1}{T-1}\sqrt{\log
2T/\delta}$ (the best rate). Then, with the arguments in Section 3.2 we can
bound the conditional regret. A proof is in Appendix B.3.1.

####  B.3.1 Proof of Theorem B.1

Recall the definitions,

$\displaystyle\bar{\mathcal{W}}(g|w)$ $\displaystyle=$ $\displaystyle
T(w)^{-1}\sum_{1\leq t\leq T-1:W_{t-1}=w}\mathop{\mbox{\sf
E}}\left\\{Y_{t}(W_{t-1},1)g(W_{t-1})+Y_{t}(W_{t-1},0)\left[1-g(W_{t-1})\right]|W_{t-1}\right\\}.$

and

$\displaystyle g^{*}(w)=\mbox{arg}\max_{g(w)\to{0,1}}\bar{\mathcal{W}}(g|w).$
(111)

$\displaystyle\bar{\mathcal{W}}(g,W_{t-2})$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$
$\displaystyle(T-1)^{-1}\sum_{1\leq t\leq T-1}\mathop{\mbox{\sf
E}}\left\\{Y_{t}(W_{t-1},1)g(W_{t-1})+Y_{t}(W_{t-1},0)\left[1-g(W_{t-1})\right]|W_{t-2}\right\\}.$

$\displaystyle{\widehat{\mathcal{W}}}(g)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$
$\displaystyle(T-1)^{-1}\sum_{1\leq t\leq
T-1}\left\\{Y_{t}(W_{t-1},1)g(W_{t-1})+Y_{t}(W_{t-1},0)\left[1-g(W_{t-1})\right]\right\\}.$

$\displaystyle{\bar{\mathcal{W}}}(g)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{def}}}{{=}}$
$\displaystyle(T-1)^{-1}\sum_{1\leq t\leq T-1}\mathop{\mbox{\sf
E}}\left\\{Y_{t}(W_{t-1},1)g(W_{t-1})+Y_{t}(W_{t-1},0)\left[1-g(W_{t-1})\right]\right\\}.$

###### Proof.

First of all, it is simple to show that,

$g^{*}(.)=\mbox{arg}\max_{g(w)\to{0,1}}\bar{\mathcal{W}}(g,W_{t-2}).$

By a similar derivation to (3.2) and assumption B.5, there exists positive
constants $c_{w},c^{\prime}$ such that

$\displaystyle\bar{\mathcal{W}}(g^{*}|w)-\bar{\mathcal{W}}(g|w)\leq
c_{w}(\bar{\mathcal{W}}(g^{*},W_{t-2})-\bar{\mathcal{W}}(g,W_{t-2})),$
$\displaystyle(\bar{\mathcal{W}}(g^{*},W_{t-2})-\bar{\mathcal{W}}(g,W_{t-2}))\leq
c^{\prime}(\bar{\mathcal{W}}(g^{*})-\bar{\mathcal{W}}(g)).$

Therefore it suffices to look at
$\hat{g}=\mbox{arg}\max_{g(w)\to{0,1}}{\widehat{\mathcal{W}}}(g)$. Throughout
this section we take $\mathop{\mbox{\sf E}}{{}_{t-1}}(\cdot)=\mathop{\mbox{\sf
E}}(\cdot|{\mathcal{F}}_{t-2})$, and
$\mathrm{P}_{{t-1}}(\cdot)=\text{Pr}(\cdot|{\mathcal{F}}_{t-2})$. $\hat{g}$ is
defined as in Section 2.2.

The first best rule is $\\{x:\tau(x)\geq 0\\}$. Recall that there exists a
positive constant $\overline{P}$ such that
$\frac{1}{T-1}\sum_{t}\mathrm{P}_{{t-1}}(g^{*}(W_{t-1})\neq
g(W_{t-1}))\geq\overline{P}$ happens with probability $1$, where
$\mathrm{P}_{{t-1}}$ is the probability conditional on $\mathcal{F}_{t-2}$. We
define the set of events $\\{A:\min_{t}|\tau(W_{t-1})|>u\\}$. Then,

$\displaystyle\bar{\mathcal{W}}(g^{*},W_{t-2})-\bar{\mathcal{W}}(g,W_{t-2})=\sum_{1\leq
t\leq T-1}\frac{1}{T-1}\mathop{\mbox{\sf
E}}{{}_{t-1}}\\{|\tau(W_{t-1})||\bm{1}(g^{*}(W_{t-1})\neq g(W_{t-1}))|\\},$
$\displaystyle\geq$ $\displaystyle u\frac{1}{T-1}\sum_{1\leq t\leq
T-1}\mathrm{P}_{{t-1}}(g^{*}(W_{t-1})\neq g(W_{t-1})\cap A),$
$\displaystyle\geq$ $\displaystyle u\\{\sum_{1\leq t\leq
T-1}\frac{1}{T-1}[\mathrm{P}_{{t-1}}(g^{*}(W_{t-1})\neq
g(W_{t-1}))-(u/\eta)^{\alpha}]\\},$

where the last inequality is due to Assumption B.4.

Set $u=\eta(1+\alpha)^{-1/\alpha}\overline{P}^{1/\alpha}\leq\eta$, then we
have

$\displaystyle\bar{\mathcal{W}}(g^{*},W_{t-2})-\bar{\mathcal{W}}(g,W_{t-2})\geq\overline{P}^{(1+\alpha)/\alpha}(1+\alpha)^{-(1+\alpha)/\alpha}\alpha\eta.$
(115)

Let $\mathop{\mbox{\sf Var}}_{t-1}(.)=\mathop{\mbox{\sf
E}}_{t-1}(.^{2})-(\mathop{\mbox{\sf E}}_{t-1}(.))^{2}$.

From this definition,

$\displaystyle\frac{1}{T-1}\sum_{t}\mathop{\mbox{\sf
Var}}{{}_{t-1}}\\{(Y_{t}(1)-Y_{t}(0))\bm{1}(g^{*}(W_{t-1})\neq g(W_{t-1})\\},$
(116) $\displaystyle\leq$
$\displaystyle\frac{1}{T-1}2\sum_{t}\mathop{\mbox{\sf
E}}{{}_{t-1}}\\{(Y_{t}^{2}(1)+Y_{t}^{2}(0))\bm{1}(g^{*}(W_{t-1})\neq
g(W_{t-1})\\}$ $\displaystyle-\frac{1}{T-1}\sum_{t}[\mathop{\mbox{\sf
E}}{{}_{t-1}}\\{(Y_{t}(1)-Y_{t}(0))\bm{1}(g^{*}(W_{t-1})\neq
g(W_{t-1})\\}]^{2},$ $\displaystyle\leq$
$\displaystyle\frac{1}{T-1}\sum_{t}2\mathop{\mbox{\sf
E}}{{}_{t-1}}\\{(Y_{t}^{2}(1)+Y_{t}^{2}(0))\bm{1}(g^{*}(W_{t-1})\neq
g(W_{t-1})\\},$ $\displaystyle\leq$ $\displaystyle(4C^{2})(\overline{P}),$
$\displaystyle\leq$
$\displaystyle(4C^{2})(1/\eta\alpha)^{\alpha/(1+\alpha)}(1+\alpha)(\bar{\mathcal{W}}(g^{*},W_{t-2})-\bar{\mathcal{W}}(g,W_{t-2}))^{\alpha/(1+\alpha)},$

where the second to last line follows from the bounds imposed on
$Y_{t}(0),Y_{t}(1)$ in Assumption B.3, and Assumption B.5. The last line is
due to Assumption B.4.

Next from the Freedman inequality we have, with probability $1-\delta$, for a
positive constant $C>2$,

$\displaystyle\bar{\mathcal{W}}(g^{*},W_{t-2})-\bar{\mathcal{W}}(\hat{g},W_{t-2})$
$\displaystyle\leq$
$\displaystyle(\widehat{\mathcal{W}}(g^{*})-\widehat{\mathcal{W}}(\hat{g}))+\max_{g}|\bar{\mathcal{W}}(g^{*},W_{t-2})-\bar{\mathcal{W}}({g},W_{t-2})-(\widehat{\mathcal{W}}(g^{*})-\widehat{\mathcal{W}}({g}))|$
$\displaystyle\leq$
$\displaystyle\frac{2\max_{g}\sqrt{\frac{1}{T-1}\sum_{t}C\mathop{\mbox{\sf
Var}}_{t-1}\\{(Y_{t}(1)-Y_{t}(0))\bm{1}(g^{*}(W_{t-1})\neq
g(W_{t-1})\\}}}{\sqrt{T-1}}\sqrt{\log(2M/\delta)}$
$\displaystyle+\log(2M/\delta)2C/(T-1),$ $\displaystyle\leq$ $\displaystyle
2\sqrt{(4C^{3}))(1/\eta\alpha)^{\alpha/(1+\alpha)}(1+\alpha)\max_{g}(\bar{\mathcal{W}}(g^{*},W_{t-2})-\bar{\mathcal{W}}({g},W_{t-2}))^{\alpha/(1+\alpha)}}\sqrt{\log(2M/\delta)}/\sqrt{T-1}$
$\displaystyle+\log(2M/\delta)4C/(T-1).$

The second inequality is due to
$\widehat{\mathcal{W}}(g^{*})-\widehat{\mathcal{W}}(\hat{g})\leq 0$, which
follows from the definition of $\hat{g}$. The third line is based on (116).
Solving the inequality on both side with respect to
$\bar{\mathcal{W}}(g^{*},W_{t-2})-\bar{\mathcal{W}}(\hat{g},W_{t-2})$, we have
with probability $1-\delta$, and there exists a positive constant
$c_{w}^{\prime}$ such that,

$\displaystyle\bar{\mathcal{W}}(g^{*})-\bar{\mathcal{W}}(\hat{g})\leq
c_{w}^{\prime}(\bar{\mathcal{W}}(g^{*},W_{t-2})-\bar{\mathcal{W}}(\hat{g},W_{t-2}))\lesssim_{p}C_{\alpha,\eta,V}(\frac{\sqrt{\log(2/\delta)})}{\sqrt{T-1}})^{2(\alpha+1)/(\alpha+2)},$

Under the stationarity of $X_{t}=\\{Y_{t},W_{t}\\}$, $C_{\alpha,\eta,V}$ is a
constant depending only on $\alpha$, $\eta$, $C$ and $V$. ∎

###  B.4 Minimax lower bound

We now prove the lower bound of the risk of the method proposed in Section. We
follow the proof strategy of Theorem 3 in Devroye and Lugosi [1995], which is
based on Hellinger distances.

######  THEOREM B.2.

Assume Assumptions 2.3, 2.2, 3.2 and 3.8 , we have the following lower bound,

$\underset{P_{T}\in\mathcal{P}(M,\kappa)}{\text{sup}}{\mathop{\mbox{\sf
E}}}_{P_{T}}\\{\mathcal{W}(G_{*})-\mathcal{W}(\hat{G})\\}\geq\sqrt{v/(T-1)}\exp(-1).$
(117)

A proof is presented in Appendix B.4.1. This theorem and Theorem 3.3 together
show the minimax optimality of the proposed T-EWM method.

####  B.4.1 Proof of Theorem B.2

###### Proof.

We can assume a specific data generating process. Let
$Y_{t}(W_{0:t})=Y_{t}(W_{t})$ with $W_{t}$ i.i.d. over time with
$\mathrm{P}(W_{t}=1)=1/2$ and $\mathrm{P}(W_{t}=0)=1/2$. Let $v$ be an
integer. Let $\mathbf{b}=(b_{1},b_{2},\cdots,b_{v})$ be the class of models
indexed by a $v$ dimensional $0,1$ vector, which will have $2^{v}$ elements.
$j=1,\cdots,v$ corresponds to $j$ different partitions of $X_{t}$ related to
the set $G_{j}$. Next, we assume that $Y_{t}(1)$ has a binary distribution,
with a positive constant $0<r<1/2$,

$Y_{t}(1)=\begin{cases}1/2,&\text{with probability}\ 1/2+r\quad\text{if}\quad
b_{j}=1,X_{t-1}\in G_{j},\\\ -1/2,&\text{with probability}\
1/2-r\quad\text{if}\quad b_{j}=1,X_{t-1}\in G_{j}.\end{cases}$ (118)
$Y_{t}(1)=\begin{cases}1/2,&\text{with probability}\ 1/2\quad\text{if}\quad
b_{j}=1,X_{t-1}\not\in G_{j},\\\ -1/2,&\text{with probability}\
1/2\quad\text{if}\quad b_{j}=1,X_{t-1}\not\in G_{j}.\end{cases}$ (119)

Otherwise,

$Y_{t}(1)=\begin{cases}1/2,&\text{with probability}\ 1/2\quad\text{if}\quad
b_{j}=0,X_{t-1}\not\in G_{j},\\\ -1/2,&\text{with probability}\
1/2\quad\text{if}\quad b_{j}=0,X_{t-1}\not\in G_{j}.\end{cases}$ (120)
$Y_{t}(1)=\begin{cases}1/2,&\text{with probability}\ 1/2-r\quad\text{if}\quad
b_{j}=0,X_{t-1}\in G_{j},\\\ -1/2,&\text{with probability}\
1/2+r\quad\text{if}\quad b_{j}=0,X_{t-1}\in G_{j}.\end{cases}$ (121)

and $Y_{t}(0)=0$ if $W_{t}=0$. Let $X_{t}$ be a stationary Markovian process
of order one. There exists $G_{j}$ ($j=1,\cdots,v$), such that $X_{t}\in
G_{j}$ corresponds to $b_{j}$ and $\Pr(X_{t}\in G_{j})>0$ for all $j$.
$\cup_{j}G_{j}=G$ is contained in the compact set from which $X_{t}$ takes its
value. Thus $\Pr(Y_{t}(1)=1/2|X_{t-1}\in G_{j},b_{j}=1)=1/2+r$. We also assume
that $X_{t}$ only causes $Y_{t}(.)$ via $X_{t-1}$, not directly. There exists
a compact support of $x_{t-1:t}$ containing $G_{j}$ and $G$, denoted as
$B_{x}$. We abbreviate $Y_{0:T}(.)$ to $Y_{0:T}$. As $\hat{G}$ is estimated
based on the whole sample $(Y_{0:T},W_{0:T})$, we denote
$g_{T}(i,X_{0:T},Y_{0:T})=\bm{1}(X_{t-1}\in\hat{G},X_{t-1}\in G_{i})$ and
$f_{\mathbf{b}}(i)=\bm{1}(X_{t-1}\in G_{i},b_{i}=1)$,
$\bm{1}(X_{t-1}\in\hat{G}\Delta
G^{*}(\mathbf{b}))=\sum_{i}\bm{1}(g_{T}(i,X_{0:T},Y_{0:T})=1-f_{\mathbf{b}}(i))$.
We assume $\mathbf{b}$ is uniformly distributed over $2^{v}$ elements.
Moreover, $\mathop{\mbox{\sf E}}(Y_{t}(1)|b_{j}=1,X_{t-1}\in
G_{j})=1/2((1/2+r)-(1/2-r))=r$. Then,

$\displaystyle\mathcal{W}_{T}(G^{*}(\mathbf{b}))-\mathcal{W}_{T}(\hat{G}),$
$\displaystyle\geq$ $\displaystyle r\mathop{\mbox{\sf
E}}(\bm{1}(X_{t-1}\in\hat{G}\Delta G^{*}(\mathbf{b}))),\quad\quad\text{where
}\widehat{G}\Delta G^{*}(\mathbf{b})=(\hat{G}\cap
G^{*}(\mathbf{b})^{c})\cup(G^{*}(\mathbf{b})\cap\hat{G}^{c}),$
$\displaystyle\geq$ $\displaystyle\frac{r}{v}\sum_{i=1}^{v}\mathop{\mbox{\sf
E}}\\{\bm{1}(g_{T}(i,X_{0:T},Y_{0:T})=1-f_{\mathbf{b}}(i))\\}.$

We let $y_{0:T}$ denote any particular realized path of $Y_{0:T}(w_{0:T})$.
The likelihood of the model given one $\mathbf{b}$ can be written as

$\mathrm{P}_{\mathbf{b}}(x_{0},x_{1},x_{2},\cdots,x_{T},y_{0},y_{1},y_{2},\cdots,y_{T},w_{0:T})=\Pi_{t=1}^{T-1}\\{p(x_{t}|x_{t-1})\mathrm{P}_{\mathbf{b}}(y_{t}|x_{t-1},w_{t})\mathrm{P}(w_{t})\\}p(x_{0},y_{0},w_{0}),$
(122)

where $\mathrm{P}_{\mathbf{b}}(y_{t}|x_{t-1},w_{t})$ is the conditional
density of $y_{t}$ on $x_{t-1},w_{t}$ and $\mathbf{b}$. We let
$\mathop{\mbox{\sf
E}}\\{\bm{1}(g_{T}(i,X_{0:T},Y_{0:T})=1-f_{\mathbf{b}}(i))\\}=E_{i}$.

We proceed to bound the value of $E_{i}$. Let
$\mathrm{P}_{b_{i+}}(y_{t}|x_{t-1})$ denote the probability conditional on
$b_{i}=1$, and $\mathrm{P}_{b_{i-}}(y_{t}|x_{t-1})$ denote the probability
conditonal on $b_{i}=0$. We let

$p_{+}(x_{0:T},y_{0:T})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}[\Pi_{t=1}^{T-1}\\{p(x_{t}|x_{t-1})\mathrm{P}_{b_{i+}}(y_{t}|x_{t-1},w_{t})\mathrm{P}(w_{t})\\},p(x_{0},y_{0},w_{0})],$

and

$p_{-}(x_{0:T},y_{0:T})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}[\Pi_{t=1}^{T-1}\\{p(x_{t}|x_{t-1})\mathrm{P}_{b_{i-}}(y_{t}|x_{t-1},w_{t})\mathrm{P}(w_{t})\\}p(x_{0},y_{0},w_{0})].$

Then we have,

$\displaystyle
E_{i}=2^{-v}\sum_{y_{0:T},w_{0:T}}\sum_{\mathbf{b}}\int_{x_{0:T}}\bm{1}(g_{T}(i,x_{0:T},y_{0:T})=1-f_{\mathbf{b}}(i))$
$\displaystyle\Pi_{t=0}^{T-1}\\{p(x_{t}|x_{t-1})\mathrm{P}_{\mathbf{b}}(y_{t}|x_{t-1},w_{t})\mathrm{P}(w_{t})\\}p(x_{0},y_{0},w_{0})dx_{0:T},$
$\displaystyle\geq$ $\displaystyle
2^{-v}\sum_{y_{0:T},w_{0:T}}\sum_{\mathbf{b}}\int_{x_{0:T}}1/2[\bm{1}(g_{T}(i,x_{0:T},y_{0:T})=1)p_{+}(x_{0:T},y_{0:T})$
$\displaystyle+\bm{1}(g_{T}(i,x_{0:T},y_{0:T})=0)p_{-}(x_{0:T},y_{0:T})]dx_{0:T},$
$\displaystyle\geq$ $\displaystyle
2^{-v}\sum_{y_{0:T},w_{0:T}}\sum_{\mathbf{b}}\int_{x_{0:T}}(1/2\\{\bm{1}(g_{T}(i,x_{0:T},y_{0:T})=1)+\bm{1}(g_{T}(i,x_{0:T},y_{0:T})=0)\\}$
$\displaystyle\min[p_{+}(x_{0:T},y_{0:T}),p_{-}(x_{0:T},y_{0:T})])dx_{0:T}.$

There exists a sequence of $x_{t,min,i}\in G_{i}$ ($t=1:T-1$) such that the
following lower bound holds,

$\displaystyle\geq$ $\displaystyle
2^{-(v+1)}\sum_{y_{0:T},w_{0:T}}\sum_{\mathbf{b}}\int_{x_{0:T}}\min[p_{+}(x_{0:T},y_{0:T}),p_{-}(x_{0:T},y_{0:T})]dx_{0:T},$
$\displaystyle\geq$ $\displaystyle
2^{-(v+1)}\sum_{\mathbf{b}}(\sum_{y_{0:T},w_{0:T}}\int_{x_{0:T}}[p_{+}(x_{0:T},y_{0:T})p_{-}(x_{0:T},y_{0:T})]^{1/2}dx_{0:T})^{2},$
$\displaystyle\geq$ $\displaystyle
2^{-(v+2)}\sum_{\mathbf{b}}p_{0}(\sum_{y_{t},w_{t}}\int_{x_{t}}\mathrm{P}(w_{t})p(x_{t}|x_{t-1,min,i})\sqrt{\mathrm{P}_{b_{i-}}(y_{t}|x_{t-1,min,i},w_{t})\mathrm{P}_{b_{i+}}(y_{t}|x_{t-1,min,i},w_{t})}dx_{t})^{2(T-1)},$

where the second to last line is due to the LeCam’s Inequality: for any
positive sequence of $a_{i}$ and $b_{i}$,

$\sum_{i}\min(a_{i},b_{i})\geq 1/2(\sum_{i}\sqrt{a_{i}b_{i}})^{2}.$ (123)

The last line follows from $p(x_{0},y_{0},w_{0})\geq p_{0}$ for any
$x_{t-1}\in G$, which holds as
$\sqrt{\mathrm{P}_{b_{i-}}(y_{t}|x_{t-1})\mathrm{P}_{b_{i+}}(y_{t}|x_{t-1})}$
takes the value $\sqrt{1/4-r^{2}}$ only for $x_{t-1}\in G_{i}$ and has value
$1/2$ otherwise.

For $r\geq 0$,

$\displaystyle\sum_{y_{t}\in\\{1/2,-1/2,0\\},w_{t}\in\\{0,1\\}}\int_{x_{t}}\mathrm{P}(w_{t})p(x_{t}|x_{t-1,min,i})\sqrt{\mathrm{P}_{b_{i-}}(y_{t}|x_{t-1,min,i})\mathrm{P}_{b_{i+}}(y_{t}|x_{t-1,min,i})}dx_{t}$
$\displaystyle\geq$
$\displaystyle\min\\{1/2\bigg{(}\int_{x_{t}}p(x_{t}|x_{t-1,min,i})dx_{t}\\{1/2+1/2\\}+2\int_{x_{t}}p(x_{t}|x_{t-1,min,i})dx_{t}\sqrt{1/4-r^{2}}\bigg{)},$
$\displaystyle
1/2\bigg{(}\int_{x_{t}}p(x_{t}|x_{t-1,min,i})dx_{t}+\int_{x_{t}}p(x_{t}|x_{t-1,min,i})dx_{t}\bigg{)}\\}$
$\displaystyle\geq$ $\displaystyle(1/2+1/2\sqrt{1-4r^{2}}).$

Thus, as $\sqrt{1-4r^{2}}\geq-4r^{2}+1$, we have

$\displaystyle E_{i}\geq p_{0}(1-2r^{2})^{2(T-1)}.$

So

$\displaystyle
W_{T}(G^{*}(\mathbf{b}))-W_{T}(\hat{G})\geq(r/v)p_{0}(1-2r^{2})^{2(T-1)}.$

We maximize the right hand side with respect to $r$. Take logs to obtain,
$\log(r)+\log(p_{0}/v)+2(T-1)\log(1-2r^{2})$. The first derivative is
$r^{-1}+2(T-1)(1-2r^{2})^{-1}(-4r)=0$. $r$ is thus of order $\sqrt{T-1}^{-1}$.

We take $r=\sqrt{v/(2(T-1))}$, then $E_{i}\geq p_{0}(1-v/(T-1))^{2(T-1)}\geq
p_{0}\\{\exp\\{-(v/(T-1))/(1-\frac{v}{T-1})\\}\\}^{2(T-1)}$, so
$r\sum_{i=1}^{v}E_{i}\geq\sqrt{v/(2(T-1))}\exp(-1)$. ∎

###  B.5 Multi-period welfare with continuous covariates

In this section, we extend the results in the previous sections to a multi-
period setup. We focus on a simple off-line decision problem with
deterministic treatment rules. Namely, we do not update policy in between the
multiple periods considered, but we allow the welfare function to include the
updated realized observations. A social planner is faced with a finite multi-
period welfare target and a set of continuous policy variables is available.
Without loss of generality, we focus on the case of a two-period policy
assignment, and it can be similarly extended to cases of a multi-period
decision problem.

The SP’s decision making procedure can be described as follows. Based on a
sample collected from time 0 to $T-1$, the SP chooses (or estimates) a
decision rule that will be implemented on $T$ and $T+1$. The rule is
characterized by two sets defined on $\mathcal{X}$, and we write them as
$G_{1:2}=\\{G_{1},G_{2}\\}\in\mathcal{X}^{2}$ . At the beginning of time $T$,
the SP makes the decision by $W_{T}=1(X_{T-1}\in G_{1})$, then she/he will
observe the outcome $Y_{T}$ as well as $X_{T}=(Y_{T},W_{T},Z_{T})$ at the end
of time $T$. At the beginning of time $T+1$, the SP will make the decision by
$W_{T+1}=1(X_{T}\in G_{2})$. Since we focus on an offline problem, $G_{2}$ is
chosen (estimated) at the end of $T-1$ and implemented at $T+1$ after $X_{T}$
is revealed. Also, the class of subsets of $\mathcal{X}^{2}$ where $G_{1:2}$
is chosen from, i.e. $\mathcal{G}_{1:2}$, is assumed to be of polynomial
classification and with finite VC dimension.

Recall that

$\displaystyle S_{t}(G)$ $\displaystyle=Y_{t}(W_{t-1},1)1(X_{t-1}\in
G)+Y_{t}(W_{t-1},0)1(X_{t-1}\notin G)$
$\displaystyle\mathcal{W}_{t}(G|X_{t-1})$ $\displaystyle=\mathop{\mbox{\sf
E}}\left[S_{t}(G)|X_{t-1}\right]$ $\displaystyle\widehat{\mathcal{W}}_{t}(G)=$
$\displaystyle\frac{Y_{t}W_{t}}{e_{t}(X_{t-1})}1(X_{t-1}\in
G)+\frac{Y_{t}\left(1-W_{t}\right)}{1-e_{t}(X_{t-1})}1(X_{t-1}\notin G).$

Let us define

$\displaystyle\mathcal{\bar{W}}_{t}(G)$
$\displaystyle=\mathsf{E}\left[S_{t}(G)|\mathcal{F}_{t-1}\right].$

We maintain Assumption 3.1, the Markovian condition of order 1. Then, the
conditional two-period welfare function is defined as

$\displaystyle\mathcal{W}_{T:T+1}(G_{1:2}|\mathcal{F}_{T-1})$ $\displaystyle=$
$\displaystyle\mathcal{W}_{T}(G_{1}|X_{T-1})+\mathsf{E}\left[S_{T+1}(G_{2})|\mathcal{F}_{T-1}\right]$
$\displaystyle=$
$\displaystyle\mathcal{W}_{T}(G_{1}|X_{T-1})+\mathsf{E}\left(\mathsf{E}\left[S_{T+1}(G_{2})|\mathcal{F}_{T}\right]|\mathcal{F}_{T-1}\right)$
$\displaystyle=$
$\displaystyle\mathcal{W}_{T}(G_{1}|X_{T-1})+\mathsf{E}\left\\{\mathsf{E}\left[S_{T+1}(G_{2})|X_{T}\right]|X_{T-1}\right\\}$
$\displaystyle=$
$\displaystyle\mathcal{W}_{T}(G_{1}|X_{T-1})+\mathsf{E}\left\\{\mathsf{E}\left[S_{T+1}(G_{2})|Y_{T}(W_{T-1},1(X_{T-1}\in
G_{1})),W_{T}=1(X_{T-1}\in G_{1})\right]|X_{T-1}\right\\},$ (124)

where the third equality follows from Assumption 3.1. It shall be noted that
in this case, the welfare function is conditional on the information available
up to time $T-1$, and we fixed the conditioning value of $X_{T-1}$ at the
observed one.

####  B.5.1 Direct estimation of the conditional welfare function.

With the defined two-period welfare function on hand, we can discuss how to
estimate the welfare function. Similar to that discussed in Section 3.2 for
the single-period welfare target, we can either directly estimate the
conditional welfare functions or the regret bounds by the unconditional
welfare function. In this subsection, we directly estimate the two-period
conditional welfare function proposed. Without loss of generality, we start
with the case $X_{t}=\left(Y_{t},W_{t}\right)\in\mathbb{R}\times\\{0,1\\}$,
i.e, $Y_{t}$ is the only continuous variable in $X_{t}$. It can be easily
extended to the case with other continuous variable(s)
$X_{t}=\left(Y_{t},W_{t},Z_{t}\right)\in\mathbb{R}\times\\{0,1\\}\times\mathbb{R}^{k}$.

Again, we apply the abbreviation: $(\cdot|x)=(\cdot|X_{T-1}=x)$, where
$x=(y,w).$

$\displaystyle\mathcal{W}_{T:T+1}(G_{1:2}|x)$
$\displaystyle=\mathcal{W}_{T}(G_{1}|x)+\mathsf{E}\left(\mathcal{W}_{T+1}(G_{2}|X_{T},W_{T}=1(X_{T-1}\in
G_{1}))|X_{T-1}=x\right).$

Let $\mathcal{G}_{1:2}$ be the class of feasible policies, which is a sub-
class of the class of all the measurable functions defined on
$\mathcal{X}\times\mathcal{X}\to\\{0,1\\}^{2}$. Conditional on $X_{T-1}=x$, we
define

$G_{1:2}^{*}\in\text{argmax}_{G_{1:2}\in\mathcal{G}_{1:2}}\mathcal{W}_{T:T+1}(G_{1:2}|x).$

Note $G_{1:2}^{*}$ might depend on $x$, but we suppress this dependence in the
notation.

Similarly to Section 3.2, for any policy $G_{1}$ and $G_{2}$, define

$\displaystyle\widehat{\mathcal{W}}(G_{1:2}|x)$
$\displaystyle=\frac{\sum_{t=1}^{T-1}\mathbf{1}\left(W_{t-1}=w\right)K_{h}(Y_{t-1},y)\widehat{\mathcal{W}}_{t}(G_{1})}{\sum_{t=1}^{T-1}\mathbf{1}\left(W_{t-1}=w\right)K_{h}(Y_{t-1},y)}$
$\displaystyle+\frac{\sum_{t=1}^{T-2}K_{h}(Y_{t-1},y)\mathbf{1}\left(W_{t-1}=w\right)\mathbf{1}\left(W_{t}=1(X_{t-1}\in
G_{1})\right)\widehat{\mathcal{W}}_{t+1}(G_{2})}{\sum_{t=1}^{T-2}K_{h}(Y_{t-1},y)\mathbf{1}\left(W_{t-1}=w\right)\mathbf{1}\left(W_{t}=1(X_{t-1}\in
G_{1})\right)},$

where $K_{h}(a,b)=\frac{1}{h}K(\frac{a-b}{h})$ with $K(\cdot)$ assumed to be a
bounded kernel function with a bounded support. Since we have
$\mathcal{F}_{t-1}\subset\mathcal{F}_{t}$, we have the
$\mathbf{1}\left(W_{t}=1(X_{t-1}\in G_{1})\right)$ can be removed from the
above sum since $W_{t}$ is determined by $X_{t-1}$.

Let $\mathcal{G}^{2}$ denote the class of feasible unconditional decision
sets, which is a class of subsets of $\mathcal{X}\times\mathcal{X}$. And

$\hat{G}_{1:2}\in\text{argmax}_{G_{1:2}\in\mathcal{G}_{1:2}}\widehat{\mathcal{W}}(G_{1:2}|x).$

Define
$\mathcal{{EW}}_{t+1}(G_{1:2}|x)=\mathsf{E}\left\\{\mathsf{E}\left[S_{T+1}(G_{2})|Y_{T}(W_{T-1},1(X_{T-1}\in
G_{1})),W_{T}=1(X_{T-1}\in G_{1})\right]|X_{T-1}=x\right\\}$ and
$\mathcal{{EW}}_{t+1}(G_{1:2}|X_{T-1})=\mathsf{E}\left\\{\mathsf{E}\left[S_{T+1}(G_{2})|Y_{T}(W_{T-1},1(X_{T-1}\in
G_{1})),W_{T}=1(X_{T-1}\in G_{1})\right]|X_{T-1}\right\\}$. First of all $x$
is a vector of values consisting of $w$ and $y$. To construct an MDS, we shall
define an intermediate counterpart,

$\displaystyle\bar{\mathcal{W}}_{h}(G_{1:2}|x)$
$\displaystyle=\frac{\sum_{t=1}^{T-1}\mathbf{1}\left(W_{t-1}=w\right)K_{h}(Y_{t-1},y)\mathcal{W}_{t}(G_{1}|x)}{\sum_{t=1}^{T-1}\mathbf{1}\left(W_{t-1}=w\right)K_{h}(Y_{t-1},y)}$
$\displaystyle+\frac{\sum_{t=1}^{T-2}K_{h}(Y_{t-1},y)\mathbf{1}\left(W_{t-1}=w\right)\mathbf{1}\left(W_{t}=1(X_{t-1}\in
G_{1})\right)\mathcal{EW}_{t+1}(G_{1:2}|x)}{\sum_{t=1}^{T-2}K_{h}(Y_{t-1},y)\mathbf{1}\left(W_{t-1}=w\right)\mathbf{1}\left(W_{t}=1(X_{t-1}\in
G_{1})\right)}.$

Note that

$\displaystyle
E(K_{h}(Y_{t-1},y)\mathbf{1}\left(W_{t-1}=w\right)\mathbf{1}\left(W_{t}=1(X_{t-1}\in
G_{1})\right){\widehat{\mathcal{W}}}_{t+1}(G_{2})|\mathcal{F}_{t-1})$
$\displaystyle=K_{h}(Y_{t-1},y)\mathbf{1}\left(W_{t-1}=w\right)\mathbf{1}\left(W_{t}=1(X_{t-1}\in
G_{1})\right)E({\widehat{\mathcal{W}}}_{t+1}(G_{2})|X_{t-1}),$

so
$K_{h}(Y_{t-1},y)\mathbf{1}\left(W_{t-1}=w\right)\mathbf{1}\left(W_{t}=1(X_{t-1}\in
G_{1})\right)(\widehat{\mathcal{W}}_{t+1}(G_{2})-\mathcal{EW}_{t+1}(G_{2}|X_{T-1}))$
is an MDS with respect to $\mathcal{F}_{t-1}$. Then with similar steps to
those in the proof of Theorem A.1, we can achieve the closeness between
$K_{h}(Y_{t-1},y)\mathbf{1}(W_{t-1}=w)\mathbf{1}(W_{t}=1(X_{t-1}\in
G_{1}))\mathcal{EW}_{t+1}(G_{2}|X_{T-1})$ and
$K_{h}(Y_{t-1},y)\mathbf{1}(W_{t-1}=w)\mathbf{1}(W_{t}=1(X_{t-1}\in
G_{1}))\mathcal{EW}_{t+1}(G_{2}|X_{T-1}=x)$ by a bias term of order
$O_{p}(h^{2})$. Thus, with similar assumptions assumed in Theorem A.1, we can
achieve the regret bound of the rate $\sqrt{(T-1)h}^{-1}+{(T-1)}^{-1}+h^{2}$.

####  B.5.2 Bounding the conditional regret by the unconditional one

Similar to Section 3.2, under the correct specification assumption, we can
bound the conditional regret by unconditional regret. For the multivariate
case, the unconditional welfare is defined as

$\mathcal{W}_{T:T+1}(G_{1:2})=\mathcal{W}_{T}(G_{1})+\mathop{\mbox{\sf
E}}\\{\mathop{\mbox{\sf E}}\left[S_{T+1}(G_{2})|W_{T}=1(X_{T-1}\in
G_{1})\right]\\}.$ (125)

Note that we have
$\mathop{\mbox{\sf E}}\\{\mathop{\mbox{\sf
E}}\left[S_{T+1}(G_{2})|W_{T}=\mathbf{1}(X_{t-1}\in
G_{1})\right]\\}=\mathop{\mbox{\sf
E}}\left[S_{T+1}(G_{2})\mathbf{1}(W_{T}=\mathbf{1}(X_{t-1}\in
G_{1}))\right]/\Pr(W_{T}=1(X_{t-1}\in G_{1}))$. Note that slightly different
from the one-period welfare function, in this unconditional welfare, the
second part is still conditioning on $W_{T}=1(X_{t-1}\in G_{1})$ since the
treatment $W_{T}$ is determined by the SP’s policy $G_{1}$.

The optimal unconditional policy within the class $\mathcal{G}_{1:2}$ is
defined as

$G_{1:2}^{*}\in\text{argmax}_{G_{1:2}\in\mathcal{G}_{1:2}}\mathcal{W}_{T:T+1}(G_{1:2}).$
(126)

To bound the conditional regret with the unconditional one we also need

######  Assumption B.6.

Let $\mathcal{W}_{T:T+1}(G_{1:2}|x)$ be the conditional welfare defined in
(B.5),

$\text{argsup}_{G_{1:2}\in\mathcal{G}_{1:2}}\mathcal{W}_{T:T+1}(G_{1:2})\subset\text{argsup}_{G_{1:2}\in\mathcal{G}_{1:2}}\mathcal{W}_{T:T+1}(G_{1:2}|x).$

######  Proposition B.1.

Under Assumption 3.1 and (B.6),

$G_{1:2}^{*}\in\text{argsup}_{G_{1:2}\in\mathcal{G}_{1:2}}\mathcal{W}_{T:T+1}(G_{1:2}|X_{T-1}).$

Similarly, unconditional regret can be expressed as an integral of conditional
regret

$\displaystyle R_{T:T+1}(G_{1:2}|x)$
$\displaystyle:=\mathcal{W}_{T:T+1}(G_{1:2}^{*}|x)-\mathcal{W}_{T:T+1}(G_{1:2}|x).$

The unconditional welfare and regret are

$\displaystyle\mathcal{W}_{T:T+1}(G_{1:2})$
$\displaystyle=\int\mathcal{W}_{T:T+1}(G_{1:2}|x)dF_{X_{T-1}}(x),$
$\displaystyle R_{T:T+1}(G_{1:2})$
$\displaystyle=\mathcal{W}_{T:T+1}(G_{1:2}^{*}|x)-\mathcal{W}_{T:T+1}(G_{1:2})$
$\displaystyle=\int R_{T:T+1}(G_{1:2}|x)dF_{X_{T-1}}(x).$

For $x^{\prime}\in\mathcal{X}$

$\displaystyle A(x^{\prime},G_{1:2})$
$\displaystyle=\\{x:x\in\mathcal{X}\text{ and }R_{T:T+1}(G_{1:2}|x)\geq
R_{T:T+1}(x^{\prime},G_{1:2})\\},$ $\displaystyle p_{T-1}(x^{\prime},G_{1:2})$
$\displaystyle=\text{Pr}(X_{T-1}\in A(x^{\prime},G_{1:2}))=\int_{x\in
A(x^{\prime},G_{1:2})}dF_{X_{T-1}}(x)$

We assume the following:

######  Assumption B.7.

For $x^{obs}\in\mathcal{X}$ and any $G_{1:2}\in\mathcal{G}_{1:2}$

$p_{T-1}(x^{obs},G_{1:2})\geq\underline{p}>0.$ (127)

For some positive constant $\underline{p}$.

######  LEMMA B.1.

Under Assumption B.7

$R_{T:T+1}(G_{1:2}|x^{obs})\leq\frac{1}{\underline{p}}R_{T:T+1}(G_{1:2}).$

Now under Assumptions B.7 and Lemma B.1, we can specify the sample counterpart

$\displaystyle\widehat{\mathcal{W}}(G_{1:2})=\frac{1}{T}\sum_{t=1}^{T-1}\widehat{\mathcal{W}}_{t}(G_{1})+\frac{1}{T(G_{1})}\sum_{t=1}^{T-2}\mathbf{1}\left(W_{t}=\mathbf{1}(X_{t-1}\in
G_{1})\right)S_{t+1}(G_{2}),$

where $T(G_{1})$ is a random number defined as
$T(G_{1}):=|\\{t:W_{t}=\mathbf{1}(X_{t-1}\in G_{1})\\}|$. We define the
estimated welfare policy,

$\hat{G}_{1:2}\in\text{argmax}_{G_{1:2}\in\mathcal{G}_{1:2}}\widehat{\mathcal{W}}(G_{1:2}).$

To prove the bound we can proceed with similar steps as in the proof of
Theorem 3.1. Namely, we define a smoothed conditional welfare function to form
an MDS as follows,

$\displaystyle\mathcal{\bar{W}}(G_{1:2})$
$\displaystyle=\frac{1}{T}\sum_{t=1}^{T-1}\mathcal{W}_{t}(G_{1}|\mathcal{F}_{t-2})$
$\displaystyle+\frac{1}{\mathop{\mbox{\sf
E}}(T(G_{1}))}\sum_{t=1}^{T-1}\mathsf{E}\\{\left[\mathbf{1}\left(W_{t}=\mathbf{1}(X_{t-1}\in
G_{1})\right)S_{t+1}(G_{2})|W_{t}=\mathbf{1}(X_{t-1}\in
G_{1})\right]|\mathcal{F}_{t-2}\\}.$

Then the unconditional population counterpart is as follows,

$\displaystyle\mathcal{\widetilde{\mathcal{W}}}(G_{1:2})$
$\displaystyle=\frac{1}{T}\sum_{t=1}^{T-1}\mathcal{W}_{t}(G_{1})$
$\displaystyle+\frac{1}{\mathop{\mbox{\sf
E}}(T(G_{1}))}\sum_{t=1}^{T-1}\mathop{\mbox{\sf
E}}(\mathbf{1}\left[W_{t}=\mathbf{1}(X_{t-1}\in G_{1})S_{t+1}(G_{2})\right].$
(128)

Assumption 3.6’. For $G_{1:2}^{*}$ defined in (126) and any
$G_{1:2}\in\mathcal{G}_{1:2}$, there exist some constant $c$

$\mathcal{W}_{T:T+1}(G_{1:2}^{*})-\mathcal{W}_{T:T+1}(G_{1:2})\leq
c\left(\mathcal{\widetilde{\mathcal{W}}}(G_{1:2}^{*})-\mathcal{\widetilde{\mathcal{W}}}(G_{1:2})\right).$

Then, the conditional regret can be bounded by

$\displaystyle\mathcal{W}_{T:T+1}(G_{1:2}^{*}|x^{obs})-\mathcal{W}_{T:T+1}(G_{1:2}x^{obs})$
$\displaystyle\leq\frac{1}{\underline{p}}\left[\mathcal{W}_{T:T+1}(G_{1:2}^{*})-\mathcal{W}_{T:T+1}(G_{1:2})\right]$
$\displaystyle\leq\frac{c}{\underline{p}}\left[\mathcal{\widetilde{\mathcal{W}}}(G_{1:2}^{*})-\mathcal{\widetilde{\mathcal{W}}}(G_{1:2})\right]$
$\displaystyle\leq\frac{c}{\underline{p}}\sup_{G_{1:2}\in\mathcal{\mathcal{G}}_{1:2}}\left[\widehat{\mathcal{W}}(G_{1:2})-\mathcal{\widetilde{\mathcal{W}}}(G_{1:2})\right].$

And

$\displaystyle\widehat{\mathcal{W}}(G_{1:2})-\mathcal{\widetilde{\mathcal{W}}}(G_{1:2})$
$\displaystyle=\left[\mathcal{\bar{W}}(G_{1:2})-\mathcal{\widetilde{\mathcal{W}}}(G_{1:2})\right]+\left[\widehat{\mathcal{W}}(G_{1:2})-\mathcal{\bar{W}}(G_{1:2})\right]$
$\displaystyle:=I+II$

Similarly to Section 3, we can drive upper bounds for I and II.