m e_ m#1#2_#2^(#3)

# Adaptive Principal Component Regression
with Applications to Panel Data

Anish Agarwal
Department of IEOR
Columbia University
New York, NY 10027
<EMAIL_ADDRESS>
&Keegan Harris
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
<EMAIL_ADDRESS>
&Justin Whitehouse
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
<EMAIL_ADDRESS>
&Zhiwei Steven Wu
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
<EMAIL_ADDRESS>For part of this work, Anish was a postdoc at Amazon, Core
AI.

###### Abstract

Principal component regression (PCR) is a popular technique for fixed-design
_error-in-variables_ regression, a generalization of the linear regression
setting in which the observed covariates are corrupted with random noise. We
provide the first time-uniform finite sample guarantees for online
(regularized) PCR whenever data is collected _adaptively_. Since the proof
techniques for analyzing PCR in the fixed design setting do not readily extend
to the online setting, our results rely on adapting tools from modern
martingale concentration to the error-in-variables setting. As an application
of our bounds, we provide a framework for experiment design in panel data
settings when interventions are assigned adaptively. Our framework may be
thought of as a generalization of the synthetic control and synthetic
interventions frameworks, where data is collected via an adaptive intervention
assignment policy.

##  1 Introduction

An omnipresent task in machine learning, statistics, and econometrics is that
of making predictions about outcomes of interest given an action and
conditioned on observable covariates. An often overlooked aspect of the
prediction task is that in many settings the learner only has access to
_imperfect observations_ of the covariates, due to e.g. measurement error or
inherent randomness in the problem domain. Such settings are sometimes
formulated as _error-in-variables_ regression: a _learner_ is given access to
a collection of data $(Z_{n},a_{n},Y_{n})_{n\geq 1}$, where
$Z_{n}\in\mathbb{R}^{d}$ are the _observed covariates_ ,
$a_{n}\in\\{1,\ldots,A\\}$ is the _action taken_ , and $Y_{n}\in\mathbb{R}$ is
the _outcome_ for each observation $n$. Typically, the outcomes are assumed to
be generated by a linear model
$Y_{n}:=\langle\theta(a_{n}),X_{n}\rangle+\xi_{n}$ and
$Z_{n}:=X_{n}+\epsilon_{n}$, where $X_{n}\in\mathbb{R}^{d}$ are the _true
covariates_ , $\epsilon_{n}\in\mathbb{R}^{d}$ is the covariate noise,
$\theta(a_{n})\in\mathbb{R}^{d}$ is an _unknown slope vector_ associated with
action $a_{n}$, and $\xi_{n}\in\mathbb{R}$ is the response noise. Note that
the learner does not get to see the true covariates $X_{n}$. Observe that when
$\epsilon_{n}=0$ we recover the traditional linear regression setting. Such an
error-in-variables model can encompass many forms of data corruption including
measurement error, missing values, discretization, and differential
privacy—see [10, 5] for details.

Our point of departure from previous work is that we allow the sequence of
data $(Z_{n},a_{n},Y_{n})_{n\geq 1}$ to be chosen _adaptively_. In other
words, we provide bounds for learning in the error-in-variables regression
setting when the data seen at the current round $n$ is allowed to depend on
the previously-seen data $(Z_{m},a_{m},Y_{m})_{1\leq m<n}$. Adaptive data
collection occurs when the choices of future observations can depend on the
inference from previous data, which is common in learning paradigms such as
multi-armed bandits [58, 78], active learning [74], and time-series analysis
[76, 36]. Similar to prior work on adaptive data collection that shows that
valid statistical inference can be done when the true covariates are observed
[34, 67, 43, 91, 92], our work provides the first time-uniform finite sample
guarantees for error-in-variables regression using adaptively collected data.

Concretely, we focus on analyzing _principal component regression (PCR)_ [54],
a method that has been shown to be effective for learning from noisy
covariates [10, 7] and a central tool for learning from panel data [8, 5, 7].
At a high level, PCR “de-noises” the sequence of observed covariates
$(Z_{n})_{n\geq 1}$ as $(\widehat{Z}_{n})_{n\geq 1}$ by performing hard
singular value thresholding, after which a linear model is learned using the
observed outcomes $(Y_{n})_{n\geq 1}$ and the denoised covariates
$(\widehat{Z}_{n})_{n\geq 1}$. See Section 3.2 for further technical
background on PCR.

###  1.1 Contributions

  1. 1.

We derive novel time-uniform bounds for an online variant of regularized PCR
when the sequence of covariates is chosen adaptively. The techniques used to
derive bounds for PCR in the fixed-sample regime [7] do not extend to the
setting in which data is collected adaptively; thus, we require new tools and
ideas to obtain our results. Specifically, our results rely on applying recent
advances in martingale concentration [50, 51], as well as more classical
results on self-normalized concentration [3, 32, 33] which are commonly
applied to online regression problems, to the error-in-variables setting. As
an example of the bounds we obtain, consider the task of estimating the
underlying relationship $\theta(a)$ between true (i.e. noiseless) covariates
and observations, given access to $n$ adaptively-chosen noisy covariates and
their corresponding actions and observations. The $\ell_{2}$ estimation error
of the adaptive PCR estimator $\widehat{\theta}_{n}(a)$ can be bounded as

$\|\widehat{\theta}_{n}(a)-\theta(a)\|_{2}^{2}=\widetilde{O}\left(\frac{1}{\mathrm{snr}_{n}(a)^{2}}\kappa(\mathbf{X}_{n}(a))^{2}\right)$

with high probability, where $\mathrm{snr}_{n}(a)$ is the _signal-to-noise
ratio_ associated with action $a$ at round $n$ (Definition 3.5), a measure of
how well the true covariates stand out from the noise.
$\kappa(\mathbf{X}_{n}(a))$ is the _condition number_ of the true covariates.
Intuitively, if $\mathrm{snr}_{n}(a)$ is high the true covariates can be well-
separated from the noise, and therefore PCR accurately estimates $\theta(a)$
as long as the true covariates are well-conditioned.

Despite the harder setting we consider, our PCR bounds for adaptively-
collected data largely match the bounds currently known for the fixed-sample
regime, and even improve upon them in two important ways: (1) Our bounds are
_computable_ , i.e. they depend on _known_ constants and quantities available
to the algorithm. (2) Unlike Agarwal et al. [7], our bounds do not depend on
the $\ell_{1}$-norm of $\theta(a)$, i.e., we do not require approximate
sparsity of $\theta(a)$ for the bounds to imply consistency. This is important
because PCR is a rotationally-invariant algorithm, and so its performance
guarantees should not depend on the orientation of the basis representation of
the space to be learned. The price we pay for adaptivity is that
$\mathrm{snr}_{n}(a)$ is defined with respect to a bound on the _total_ amount
of noise seen by the algorithm so far, instead of just the noise associated
with the rounds that $a$ is taken. As a result, our bound for
$\widehat{\theta}_{n}(a)$ may not be tight if $a$ is seldomly selected.

  2. 2.

We apply our PCR results to the problem of online experiment design with
_panel data_. In panel data settings, the learner observes repeated, noisy
measurements of _units_ (e.g. medical patients, subpopulations, geographic
locations) under different _interventions_ (e.g. medical treatments,
discounts, socioeconomic policies) over _time_. This is an ubiquitous method
of data collection, and as a result, learning from panel data has been the
subject of significant interest in the econometrics and statistics communities
(see Section 2). A popular framework for learning from panel data is
_synthetic control_ (SC) [1, 2], which uses historical panel data to estimate
counterfactual unit measurements under control. Synthetic interventions (SI)
[8] is a recent generalization of the SC framework which allows for
counterfactual estimation under treatment, in addition to control. By
leveraging online PCR, we can perform counterfactual estimation of unit-
specific treatment effects under both treatment and control, as in the SI
framework. However, unlike the traditional SI framework, we are the first to
establish statistical rates for counterfactual unit outcome estimates under
different interventions _while allowing for both units and interventions to be
chosen adaptively_. Such adaptivity may naturally occur when treatments are
prescribed to new units based on the outcomes of previous units. For example,
this is the case when the intervention chosen for each unit is the one which
appears to be best based on observations in the past.

##  2 Related work

#### Error-in-variables regression

There is a rich literature on error-in-variables regression (e.g. [42, 57, 28,
44, 84, 47, 41]), with research focusing on topics such as high-dimensional
[62, 56, 31, 72] and Bayesian settings [70, 81, 40]. Principal component
regression (PCR) [54, 22, 10, 7] is a popular method for error-in-variables
regression. The results of Agarwal et al. [7] are of particular relevance to
us, as they provide finite sample guarantees for the fixed design (i.e. non-
adaptive) version of the setting we consider.

#### Self-normalized concentration

There has been a recent uptick in the application of self-normalized,
martingale concentration to online learning problems. In short, self-
normalized concentration aims to control the growth of processes that have
been normalized by a random, or empirical, measure of accumulated variance
[32, 33, 50, 51, 88]. Self-normalized concentration has led to breakthroughs
in wide-ranging areas of machine learning such as differential privacy [85,
86], PAC-Bayesian learning [30], convex divergence estimation [63], and online
learning [87, 29, 3]. Of particular importance for our work are the results of
Abbasi-Yadkori et al. [3], which leverage self-normalized concentration
results for vector-valued processes [32, 33] to construct confidence
ellipsoids for online regression tasks. We take inspiration from these results
when constructing our estimation error bounds for PCR in the sequel.

#### Learning in panel data settings

Our application to panel data builds off of the SI framework [8, 9], which
itself is a generalization of the canonical SC framework for learning from
panel data [1, 2, 52, 35, 17, 60, 89, 13, 14, 59, 16, 20, 23, 27, 39]. In both
frameworks, a _latent factor model_ is often used to encode structure between
units and time-steps [25, 61, 15, 18, 19, 68, 64, 65]. Specifically, it is
assumed that unit outcomes are the product of unit- and time/intervention-
specific latent factors, which capture the heterogeneity across time-steps,
units, and interventions, and allows for the estimation of unit-specific
counterfactuals under treatment and control. Other extensions of the SI
framework include applications in biology [79], network effects [11],
combinatorially-many interventions [4], and intervening under incentives [45,
66]. Finally, there is a growing line of work at the intersection of online
learning and panel data. Chen [26] views the problem of SC as an instance of
online linear regression, which allows them to apply the regret guarantees of
the online learning algorithm _follow-the-leader_ [55] to show that the
predictions of SC are comparable to those of the best-in-hindsight weighted
average of control unit outcomes. Farias et al. [38] build on the SC framework
to estimate treatment effects in adaptive experimental design, while
minimizing the regret associated with experimentation. The results of Farias
et al. [38] are part of a growing line of work on counterfactual estimation
and experimental design using multi-armed bandits [69, 77, 90, 24].

##  3 Setting and background

#### Notation

We use boldface symbols to represent matrices. For $N\in\mathbb{N}$, we use
the shorthand $[N]:=\\{1,\ldots,N\\}$. Unless specified otherwise, $\|v\|$
denotes the $\ell_{2}$-norm of a vector $v$, and $\|\mathbf{A}\|_{op}$ the
operator norm of matrix $\mathbf{A}$. We use
$\mathrm{diag}(a_{1},\ldots,a_{k})$ to represent a $k\times k$ diagonal matrix
with entries $a_{1},\ldots,a_{k}$. For two numbers $a,b\in\mathbb{R}$, we use
$a\land b$ as shorthand for $\min\\{a,b\\}$, and $a\vee b$ to mean
$\max\\{a,b\\}$. Finally, $\mathbb{S}^{d-1}$ denotes the $d$-dimensional unit
sphere.

###  3.1 Problem setup

We now describe our error-in-variables setting. We consider a _learner_ who
interacts with an _environment_ over a sequence of rounds. At the start of
each round $n\geq 1$, the environment generates covariates $X_{n}\in
W^{\ast}\subset\mathbb{R}^{d}$, where $W^{\ast}$ is a low-dimensional linear
subspace of dimension $\dim(W^{\ast})=r<d$. We assume that $r$ (but not
$W^{\ast}$) is known to the learner. Such “low rank” assumptions are
reasonable whenever, e.g. data is generated according to a _latent factor
model_ , a popular assumption in high-dimensional statistical settings [53,
12, 48]. As we will see in Section 5, analogous assumptions are often also
made in panel data settings. The learner then observes _noisy_ covariates
$Z_{n}:=X_{n}+\epsilon_{n}$, where $\epsilon_{n}\in\mathbb{R}^{d}$ is a random
noise vector. Given $Z_{n}$, the learner selects an _action_ $a_{n}\in[A]$ and
observes $Y_{n}:=\langle\theta(a_{n}),X_{n}\rangle+\xi_{n}$, where $\xi_{n}$
is random noise and $\theta(a)$ for $a\in[A]$ are unknown slope vectors in
$W^{*}$ that parameterize action choices such that $\|\theta(a)\|_{2}\leq L$
for some $L\in\mathbb{R}$. We require that the covariate noise is “well-
behaved” according to one of the two the following assumptions:

######  Assumption 3.1 (SubGaussian Covariate Noise).

For any $n\geq 1$, the noise variable $\epsilon_{n}$ satisfies (a)
$\epsilon_{n}$ is $\sigma$-subGaussian, (b) $\mathbb{E}\epsilon_{n}=0$, and
(c) $\|\mathbb{E}\epsilon_{n}\epsilon_{n}^{\top}\|_{op}\leq\gamma$, for some
constant $\gamma>0$.

######  Assumption 3.2 (Bounded Covariate Noise).

For any $n\geq 1$, the noise variable $\epsilon_{n}$ satisfies (a)
$\|\epsilon_{n}\|\leq\sqrt{Cd}$, (b) $\mathbb{E}\epsilon_{n}=0$, and (c)
$\mathbb{E}\epsilon_{n}\epsilon_{n}^{\top}=\Sigma$, for some positive-definite
matrix $\Sigma$ satisfying $\|\Sigma\|_{op}\leq\gamma$, for some constant
$\gamma>0$.

Note that 3.2 is a special case of 3.1, which allows us to get stronger
results in some settings. We also impose the following constraint on the noise
in the outcomes.

######  Assumption 3.3 (SubGaussian Outcome Noise).

For any $n\geq 1$, the noise variable $\xi_{n}$ satisfies (a)
$\mathbb{E}\xi_{n}=0$, (b) $\xi_{n}$ is $\eta$-subGaussian, and (c)
$\mathbb{E}\xi_{n}^{2}\leq\alpha$, for some constant $\alpha$.

Under this setting, the goal of the learner is to estimate $\theta(a)$ for
$a\in[A]$ given an (possibly adaptively-chosen) observed sequence
$(Z_{n},a_{n},Y_{n})_{n\geq 1}$. For $n\geq 1$, we define the matrix
$\mathbf{Z}_{n}\in\mathbb{R}^{n\times d}$ to be the matrix of _observed_ (i.e.
noisy) covariates, with $Z_{1},\dots,Z_{n}$ as its rows. Similarly,
$\mathbf{X}_{n}=(X_{1},\dots,X_{n})^{T}\in\mathbb{R}^{n\times d}$ is the
matrix of _noiseless_ covariates (which are unobserved), and
$\mathcal{E}_{n}=(\epsilon_{1},\dots,\epsilon_{n})^{T}\in R^{n\times
d},\mathbf{Y}_{n}=(Y_{1},\ldots,Y_{n})^{T}\in\mathbb{R}^{n\times 1},$ and
$\Xi_{n}=(\xi_{1},\dots,\xi_{n})^{T}\in\mathbb{R}^{n\times 1}$ are defined
analogously. For any action $a\in[A],$ let $N_{n}(a):=\\{s\leq n:a_{s}=n\\}$
be the _set of rounds_ up to and including round $n$ on which action $a$ was
chosen. Likewise, let $c_{n}(a):=|N_{n}(a)|$ denote the _number of rounds_ by
round $n$ on which action $a$ was chosen. For $a\in[A]$, we enumerate
$N_{n}(a)$ in increasing order as $i_{1}\leq\cdots\leq i_{c_{n}(a)}$. Finally,
we define $\mathbf{Z}_{n}(a)\in\mathbb{R}^{c_{n}(a)\times d}$ to be
$\mathbf{Z}(a)=(Z_{i_{1}},\dots,Z_{i_{c_{n}(a)}})^{T}$, and define
$\mathbf{X}_{n}(a),\mathcal{E}_{n}(a),\mathbf{Y}_{n}(a),$ and $\Xi_{n}(a)$
analogously.

###  3.2 Principal component regression

#### Background on singular value decomposition

Any matrix $\mathbf{A}\in\mathbb{R}^{n\times d}$ may be written in terms of
its singular value decomposition $\mathbf{A}=\mathbf{U}\Sigma\mathbf{V}^{T}$,
where $\mathbf{U}\in\mathbb{R}^{n\times d\land n}$ and
$\mathbf{V}\in\mathbb{R}^{d\times d\land n}$ are matrices with orthonormal
columns, and $\Sigma=\mathrm{diag}(\sigma_{1}(\mathbf{A}),\dots,\sigma_{d\land
n}(\mathbf{A}))\in\mathbb{R}^{(d\land n)\times(d\land n)}$ is a diagonal
matrix containing the singular values of $\mathbf{A}$, where we assume
$\sigma_{1}(\mathbf{A})\geq\dots\geq\sigma_{d\land n}(\mathbf{A})\geq 0$.
Given a _truncation level_ $k$, we define the truncation of $\mathbf{A}$ onto
its top $k$ principal components as
$\mathbf{A}_{k}:=\mathbf{U}_{k}\mathrm{diag}(\sigma_{1}(\mathbf{A}),\dots,\sigma_{k\land
d\land n}(\mathbf{A}))\mathbf{V}^{T}_{k}$, where
$\mathbf{U}_{k}\in\mathbb{R}^{n\times k\land d\land n}$ is the matrix with the
first $k\land d\land n$ columns of $\mathbf{U}$, and
$\mathbf{V}_{k}\in\mathbb{R}^{n\times k\land d\land n}$ is defined
analogously. Given such a singular value decomposition, we can define the
projection matrix onto the subspace spanned by the top $k$ right singular
vectors as $\mathbf{P}_{k}\in\mathbb{R}^{d\times d}$ given by
$\mathbf{P}_{k}:=\mathbf{V}_{k}\mathbf{V}_{k}^{T}$.

For $n\geq 1$, $a\in[A]$, and $\mathbf{Z}_{n}(a)$ as defined above, we write
the $k$-truncated singular value decomposition of $\mathbf{Z}_{n}(a)$ as
$\mathbf{Z}_{n,k}(a)=\widehat{\mathbf{U}}_{n,k}(a)\mathrm{diag}(\sigma_{1}(\mathbf{Z}_{n}(a)),\dots,\sigma_{k\land
n\land d}(\mathbf{Z}_{n}(a)))\widehat{\mathbf{V}}^{T}_{n,k}(a)$, and the
corresponding projection onto the top $k$ right singular vectors of
$\mathbf{Z}_{n}(a)$ as $\widehat{\mathbf{P}}_{n,k}(a)$. When $k=r$, we
leverage the simplified notation
$\widehat{\mathbf{P}}_{n}(a):=\widehat{\mathbf{P}}_{n,r}(a)$. (Recall
$r=\dim(W^{*})$.) By $\mathbf{P}$, we denote the projection matrix onto the
true, underlying subspace $W^{\ast}$. While $\mathbf{P}$ is never known, our
results leverage the fact that $\widehat{\mathbf{P}}_{n}(a)$ converges to
$\mathbf{P}$ nicely over time. We define the projected noisy covariate matrix
matrix to be
$\widehat{\mathbf{Z}}_{n}(a):=\mathbf{Z}_{n}(a)\widehat{\mathbf{P}}_{n}(a)$,
and define $\widehat{\mathbf{X}}_{n}(a),\widehat{\mathcal{E}}_{n}(a)$
similarly. Any quantity with a “ $\widecheck{\cdot}$ ” is defined equivalently
to quantities with “ $\widehat{\cdot}$ ”, except with $\mathbf{P}$ in place of
$\widehat{\mathbf{P}}_{n}(a)$. We are now ready to introduce our procedure for
estimating $\theta(a)$ for $a\in[A]$, called _adaptive_ (or _online_)
principal component regression.

######  Definition 3.4 (Adaptive Principal Component Regression).

Given _regularization parameter_ $\rho\geq 0$ and _truncation level_
$k\in\mathbb{N}$, for $a\in[A]$ and $n\geq 1$ let
$\widehat{\mathbf{Z}}_{n}(a):=\mathbf{Z}_{n}(a)\widehat{\mathbf{P}}_{n,k}(a)$
and
$\widehat{\mathcal{V}}_{n}(a):=\widehat{\mathbf{Z}}_{n}(a)^{T}\widehat{\mathbf{Z}}_{n}(a)+\rho\widehat{\mathbf{P}}_{n,k}(a)$.
Regularized principal component regression estimates $\theta(a)$ as

$\widehat{\theta}_{n}(a):=\widehat{\mathcal{V}}_{n}(a)^{-1}\widehat{\mathbf{Z}}_{n}(a)\mathbf{Y}_{n}(a).$

Setting $\rho=0$ recovers the version of PCR used in Agarwal et al. [7]. In
words, (unregularized) PCR “denoises” the observed covariates by projecting
them onto the subspace given by their $k$-truncation, before estimating
$\theta(a)$ via linear regression using the projected covariates. We choose to
regularize since it is known that regularization increases the stability of
regression-style algorithms. This added stability from regularization allows
us to exploit the online regression bounds of Abbasi-Yadkori et al. [3] to
measure the performance of our estimates. Throughout the sequel, we only
consider adaptive PCR with truncation level $k=r$.

###  3.3 Signal to noise ratio

We now introduce the concept of signal to noise ratio, which will be integral
in stating and proving our results. The signal to noise ratio provides a
measure of how strongly the true covariates (this is the “signal” of the
problem, measured through $\sigma_{r}(\mathbf{X}_{n}(a))$) stand out
sequentially with respect to the “noise” induced by $\mathcal{E}_{n}$ (which
we will measure through the relevant high probability bounds on
$\|\mathcal{E}_{n}\|_{op}$).

######  Definition 3.5 (Signal to Noise Ratio).

We define the signal to noise ratio associated with an action $a\in[A]$ at
round $n$ as

$\mathrm{snr}_{n}(a):=\frac{\sigma_{r}(\mathbf{X}_{n}(a))}{U_{n}},$

where $(U_{n})_{n\geq 1}$ is a noise-dependent sequence growing as
$U_{n}=O\left(\sqrt{n}+\sqrt{d}+\sqrt{\log\left(\frac{1}{\delta}\log(n)\right)}\right)$.

The price we pay for adaptivity is encoded directly into the definition of the
signal to noise ratio, $\mathrm{snr}_{n}(a)$. While one may imagine defining
$\mathrm{snr}_{n}(a)$ as the ratio between $\sigma_{r}(\mathbf{X}_{n}(a))$ and
$\|\mathcal{E}_{n}(a)\|_{op}$, bounding $\|\mathcal{E}_{n}(a)\|_{op}$ is a
nontrivial task as the rows of $\mathcal{E}_{n}(a)$ may be strongly
correlated. To circumvent this, we apply the trivial bound
$\|\mathcal{E}_{n}(a)\|_{op}\leq\|\mathcal{E}_{n}\|_{op}$. Thus, _the price of
adaptivity in our setting is that the signal from covariates associated with
an action $a$ must stand out with respect to the total covariate noise by time
$n$_. The growth condition on $U_{n}$ presented in Definition 3.5 is motivated
as follows: w.h.p
$\mathbb{E}\left\|\mathcal{E}_{n}\right\|_{op}\approx\sqrt{d}+\sqrt{n}$, and
the extra additive $\sqrt{\log\left(\frac{1}{\delta}\log(n)\right)}$ factor is
the price we pay for having high probability control of
$\|\mathcal{E}_{n}\|_{op}$ uniformly over rounds. Below we provide an exact
definition for $U_{n}$, as this choice leads to bounds with known constants
and simple conditions on $\mathrm{snr}_{n}(a)$ for validity.

We consider the following two sequences $(U_{n})_{n\geq 1}$ in defining signal
to noise ratio, which both satisfy $\|\mathcal{E}_{n}\|_{op}\leq U_{n},\forall
n\geq 1$ with probability at least $1-\delta$, per Lemma B.3.

$U_{n}^{2}:=\begin{cases}\beta\left(3\sqrt{n\ell_{\delta/2\mathcal{N}}(n)}+5\ell_{\delta/2\mathcal{N}}(n)\right)+n\gamma\quad\text{when
Assumption~{}\ref{ass:noise1} holds}\\\
\frac{3}{2}\sqrt{nCd\gamma\ell_{\delta}(n)}+\frac{7}{3}Cd\ell_{\delta}(n)+n\gamma\quad\text{when
Assumption~{}\ref{ass:noise2} holds}.\end{cases}$

In the above, $\delta\in(0,1)$,
$\ell_{\delta}(n):=2\log\log(2n)+\log\left(\frac{d\pi^{2}}{12\delta}\right)$,
$\beta=32\sigma^{2}e^{2}$, and $\mathcal{N}=17^{d}$ is an upper bound on the
$1/8$-covering number of $\mathbb{S}^{d-1}$. While the exact forms of the
above sequences $(U_{n})_{n\geq 1}$ may appear complicated, it is helpful to
realize that, under either Assumption 3.1 or 3.2, we have
$U_{n}=O\left(\sqrt{n}+\sqrt{d}+\sqrt{\log\left(\frac{1}{\delta}\log(n)\right)}\right)$,
i.e., the growth condition on $U_{n}$ presented in Definition 3.5 is
satisfied.

We can likewise define the empirical signal to noise ratio associated with
action $a$ as
$\widehat{\mathrm{snr}}_{n}(a):=\frac{\sigma_{r}(\mathbf{Z}_{n}(a))}{U_{n}}$.
Note that unlike the (true) signal to noise ratio $\mathrm{snr}_{n}(a)$, the
empirical version $\widehat{\mathrm{snr}}_{n}(a)$ is _computable_ by the
learner. Thus, it will be integral in stating our empirical-style bounds in
the section that follows.

We conclude this section by comparing our notion of signal to noise ratio to
that of Agarwal et al. [7], who define $\mathrm{snr}_{n}(a)$ instead as
$\frac{\sigma_{r}(\mathbf{X}_{n}(a))}{\sqrt{n}+\sqrt{d}}$, i.e. the ratio of
the “signal” in the covariates to the _expected_ operator norm of covariate
noise $\mathbb{E}\|\mathcal{E}_{n}\|_{op}$. Since the goal of our work is
high-probability (not in-expectation) estimation guarantees for PCR, we
believe using high probability bounds on $\|\mathcal{E}_{n}\|_{op}$ is more
natural when defining $\mathrm{snr}_{n}(a)$.

##  4 Adaptive bounds for online (regularized) PCR

We now present the main results of this work—high-probability, time- and
action-uniform bounds measuring the convergence of the PCR estimates
$\widehat{\theta}_{n}(a)$ to the true slope vectors $\theta(a)$. Unlike
existing results [6, 7, 8], our bounds are valid when the covariates
$(X_{n})_{n\geq 1}$ and actions $(a_{n})_{n\geq 1}$ are determined in an
online (potentially adversarial) manner.

We first point out why the analysis of Agarwal et al. [7, 8] breaks down in
the setting of adaptive (or online) PCR. First, many of the concentration
inequalities leveraged in Agarwal et al. [7] do not hold in the adaptive
design setting. As a particular example, the authors leverage the Hanson-
Wright inequality [82, 73] for quadratic forms to study how the noisy
covariate matrix $\mathbf{Z}_{n}$ concentrates around the true matrix
$\mathbf{X}_{n}$. This inequality fails to hold when the design points
$(X_{n})_{n\geq 1}$ depend on the previous observations. Second, the
techniques leveraged by Agarwal et al. [8] to extend the convergence
guarantees of PCR to the multiple action setting fail to hold when the $n$-th
action $a_{n}$ is selected based on previous observations. Lastly, the bounds
presented in [7] are are inherently fixed-time in nature—a simple way to
convert existing fixed-time bounds to time-uniform ones would be to perform a
union bound over time steps, but that introduces looseness in the bounds.

We are able to construct our bounds by exploiting connections between online
PCR and self-normalized martingale concentration [50, 51, 32, 33]. In
particular, we combine martingale-based results for constructing confidence
ellipsoids for online regression [3, 32, 33] with methods for high-dimensional
covariance estimation [83, 80] to prove our results. Exploiting this
connection is what allows us to extend the results of Agarwal et al. [7] to
the adaptive design, time-uniform setting. We begin with a bound which, up to
constants and polylogarthmic factors, captures the rate of convergence of
online PCR in terms of (a) the underlying signal to noise ratio and (b) the
conditioning of the observed data.

######  Theorem 4.1 (Rate of Convergence for Online PCR).

Let $\delta\in(0,1)$ be an arbitrary confidence parameter. Let $\rho>0$ be
chosen to be sufficiently small, as detailed in Appendix F. Further, assume
that there is some $n_{0}\geq 1$ such that
$\mathrm{rank}(\mathbf{X}_{n_{0}}(a))=r$ and $\mathrm{snr}_{n}(a)\geq 2$ for
all $n\geq n_{0}$. Then, with probability at least $1-O(A\delta)$,
simultaneously for all actions $a\in[A]$ and time steps $n\geq n_{0}$, we have

$\|\widehat{\theta}_{n}(a)-\theta(a)\|_{2}^{2}=\widetilde{O}\left(\frac{1}{\mathrm{snr}_{n}(a)^{2}}\kappa(\mathbf{X}_{n}(a))^{2}\right),$

where
$\kappa(\mathbf{X}_{n}(a)):=\frac{\sigma_{1}(\mathbf{X}_{n}(a))}{\sigma_{r}(\mathbf{X}_{n}(a))}$
is the condition number (ignoring zero singular values) of
$\mathbf{X}_{n}(a)$.

Theorem 4.1 is proved in Appendix E. We begin by comparing our bounds to those
of Agarwal et al. [7, 8]. At any fixed time, our bounds take on roughly the
same form as those of the aforementioned authors, having an inverse quadratic
dependence on the signal to noise ratio. To make their bounds non-vacuous, the
authors need to make the “soft sparsity” assumption of
$\|\theta(a)\|_{1}=O(\sqrt{d})$. Our bound, on the other hand, suffers no
dependence on the $\ell_{1}$-norm of the $\theta(a)$’s. This makes intuitive
sense, as the specific choice of a basis should not impact the rate of
convergence of PCR. However, our bounds pay a price for adaptivity—in
particular, the signal to noise ratio associated with an action is defined
with respect to a bound on the total operator norm of the matrix
$\mathcal{E}_{n}$. If an action is selected very infrequently, the above bound
may become loose.

While the above bound is stated in terms of signal to noise ratio, if we make
additional assumptions, we can obtain bounds directly in terms of $d,n,$ and
$r$. In particular, the following “well-balancing” assumptions suffice.

######  Assumption 4.2 (Well-balancing assumptions).

For all $n\geq n_{0}$, the following hold: (a)
$\sigma_{i}(\mathbf{X}_{n}(a))=\Theta\left(\sqrt{\frac{c_{n}(a)d}{r}}\right)$
for all $i\in[r]$, (b) $c_{n}(a)=\Theta(c_{n}(a^{\prime}))$ for all
$a,a^{\prime}\in[A]$, and (c) $A=O(r)$.

######  Corollary 4.3.

Assume the same setup as Theorem 4.1, and further assume Assumption 4.2 holds.
Then with probability at least $1-O(A\delta)$, simultaneously for all actions
$a\in[A]$ and time steps $n\geq n_{0}$, we have

$\|\widehat{\theta}_{n}(a)-\theta(a)\|_{2}^{2}=\widetilde{O}\left(\frac{r^{2}}{d\land
n}\right).$

Corollary 4.3 shows that Theorem 4.1 obtains the same estimation rate as
Theorem 4.1 of Agarwal et al. [7] if assumption Assumption 4.2 holds. This
“well-balancing” assumption says roughly that all non-zero singular values of
$\mathbf{X}_{n}$ are of the same order, each action is selected with the same
frequency, and that the number of actions is, at most, proportional to
dimension of the true, unknown subspace. As noted by Agarwal et al. [7], the
assumption of a “well-balanced spectrum” (for $\mathbf{X}_{n}$) is common in
many works in econometrics and robust statistics, and additionally holds with
high probability if the entries of $\mathbf{X}_{n}$ are i.i.d.[62, 21, 37].
Further, it is often the case that there only few available actions (for
instance, in the synthetic control literature there are only two actions [2,
1, 38]), justifying the assumption that $A=O(r)$. Lastly, ensuring that each
action is played (very roughly) the same number of times can be viewed as a
price for adaptivity.

The proof of Theorem 4.1 is immediate as a corollary from the following, more
complicated bound. Theorem 4.4 below measures the convergence of
$\widehat{\theta}_{n}(a)$ to $\theta(a)$ in terms of empirical (i.e. observed)
quantities. We imagine this bound to be the most practically relevant of our
results, as, unlike the results of Agarwal et al. [7], it is directly
computable by the learner, involves known constants, and places minimal
conditions on the signal to noise ratio.

######  Theorem 4.4 (Empirical Guarantees for Online PCR).

Let $\delta\in(0,1)$ be an arbitrary confidence parameter. Let $\rho>0$ be
chosen to be sufficiently small, as detailed in Appendix F. Further, assume
that there is some $n_{0}\geq 1$ such that
$\mathrm{rank}(\mathbf{X}_{n_{0}}(a))=r$ and $\mathrm{snr}_{n}(a)\geq 2$ for
all $n\geq n_{0}$. Then, with probability at least $1-O(A\delta)$,
simultaneously for all actions $a\in[A]$ and time steps $n\geq n_{0}$, we have

$\displaystyle\left\|\widehat{\theta}_{n}(a)-\theta(a)\right\|_{2}^{2}\leq\frac{L^{2}}{\widehat{\mathrm{snr}}_{n}(a)^{2}}\left[74+216\kappa(\mathbf{Z}_{n}(a))^{2}\right]+\frac{2\mathrm{err}_{n}(a)}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}},$

where
$\kappa(\mathbf{Z}_{n}(a)):=\frac{\sigma_{1}(\mathbf{Z}_{n}(a))}{\sigma_{r}(\mathbf{Z}_{n}(a))}$,
$\|\theta(a)\|_{2}\leq L$, and in the above we define the “error” term
$\mathrm{err}_{n}(a)$ to be

$\displaystyle\mathrm{err}_{n}(a)$ $\displaystyle:=32\rho
L^{2}+64\eta^{2}\left(\log\left(\frac{A}{\delta}\right)+r\log\left(1+\frac{\sigma_{1}(\mathbf{Z}_{n}(a))^{2}}{\rho}\right)\right)$
$\displaystyle+6\eta^{2}\sqrt{2c_{n}(a)\ell_{\delta}(c_{n}(a))}+10\eta^{2}\ell_{\delta}(c_{n}(a))+6c_{n}(a)\alpha.$

We see that the above bound, with the exception of the third term, more or
less resembles the bound presented in Theorem 4.1, just written in terms of
the observed covariates $\mathbf{Z}_{n}(a)$ instead of the true covariates
$\mathbf{X}_{n}(a)$. We view the third term as a slowly growing “error” term.
In particular, all terms in the quantity $\mathrm{err}_{n}(a)$ are either
constant, logarithmic in the singular values of $\mathbf{Z}_{n}(a)$, or linear
in $c_{n}(a)$, the number of times by round $n$ action $a$ has been selected.
This implies that $\mathrm{err}_{n}(a)=\widetilde{O}(n+d)$, ensuring
$\mathrm{err}_{n}(a)$ is dominated by other terms in the asymptotic analysis.
We now provide the proof of Theorem 4.4. The key application of self-
normalized, martingale concentration comes into play in bounding the
quantities that appear in the upper bounds of terms $T_{1}$ and $T_{2}$ (to be
defined below).

###### Proof.

Observe the decomposition, for any $n\geq 1$ and $a\in[A]$

$\widehat{\theta}_{n}(a)-\theta(a)=\widehat{\mathbf{P}}_{n}(a)(\widehat{\theta}_{n}(a)-\theta(a))+(\mathbf{P}^{\perp}-\widehat{\mathbf{P}}_{n}^{\perp}(a))\theta(a),$

where $\mathbf{P}^{\perp}$ is the projection onto the subspace orthogonal to
$W^{*}$ and $\widehat{\mathbf{P}}_{n}^{\perp}(a)$ is the projection onto the
subspace orthogonal to the learned subspace (i.e. that spanned by
$\mathbf{Z}_{n,r}(a)$). Since
$\widehat{\mathbf{P}}_{n}(a)(\widehat{\theta}_{n}(a)-\theta(a))$ and
$(\mathbf{P}^{\perp}-\widehat{\mathbf{P}}_{n}^{\perp}(a))\theta(a)$ are
orthogonal vectors, we have

$\left\|\widehat{\theta}_{n}(a)-\theta(a)\right\|_{2}^{2}=\left\|\widehat{\mathbf{P}}_{n}(a)(\widehat{\theta}_{n}(a)-\theta(a))\right\|^{2}_{2}+\left\|(\widehat{\mathbf{P}}_{n}^{\perp}(a)-\mathbf{P}^{\perp})\theta(a)\right\|_{2}^{2}.$

We bound these two terms separately, beginning with the second term. Going
forward, fix an action $a\in[A]$. Observe that with probability at least
$1-\delta$, simultaneously for all $n\geq n_{0}(a)$,

$\displaystyle\left\|(\widehat{\mathbf{P}}_{n}^{\perp}(a)-\mathbf{P}^{\perp})\theta(a)\right\|_{2}^{2}$
$\displaystyle\leq\left\|\widehat{\mathbf{P}}_{n}^{\perp}(a)-\mathbf{P}^{\perp}\right\|_{op}^{2}\left\|\theta(a)\right\|_{2}^{2}$
$\displaystyle\leq
L^{2}\left\|\widehat{\mathbf{P}}_{n}^{\perp}(a)-\mathbf{P}^{\perp}\right\|_{op}^{2}=L^{2}\left\|\widehat{\mathbf{P}}_{n}(a)-\mathbf{P}\right\|_{op}^{2}$
$\displaystyle\leq\frac{4L^{2}U_{n}^{2}}{\sigma_{r}(\mathbf{X}_{n}(a))^{2}}\leq\frac{6L^{2}U_{n}^{2}}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}},$

where the equality in the above comes from observing
$\|\widehat{\mathbf{P}}_{n}^{\perp}(a)-\mathbf{P}^{\perp}\|_{op}=\|\widehat{\mathbf{P}}_{n}(a)-\mathbf{P}\|_{op}$,
the second-to-last last inequality comes from applying Lemma B.4, and the last
inequality follows from the second part of Lemma B.6.

We now bound the first term. Observe that we can write

$\displaystyle\left\|\widehat{\mathbf{P}}_{n}(a)\left(\widehat{\theta}_{n}(a)-\theta(a)\right)\right\|_{2}^{2}\leq\frac{1}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}\left\|\widehat{\mathbf{Z}}_{n}(a)\left(\widehat{\theta}_{n}(a)-\theta(a)\right)\right\|_{2}^{2}$
(1)
$\displaystyle\leq\frac{2}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}\left[\underbrace{\left\|\widehat{\mathbf{Z}}_{n}(a)\widehat{\theta}_{n}(a)-\mathbf{X}_{n}(a)\theta(a)\right\|_{2}^{2}}_{T_{1}}+\underbrace{\left\|\mathbf{X}_{n}(a)\theta(a)-\widehat{\mathbf{Z}}_{n}(a)\theta(a)\right\|_{2}^{2}}_{T_{2}}\right],$

where the first inequality follows from the fact that
$\widehat{\mathbf{P}}_{n}(a)\preceq\frac{1}{\sigma_{r}(\widehat{\mathbf{Z}}_{n}(a))^{2}}\widehat{\mathbf{Z}}_{n}(a)^{\top}\widehat{\mathbf{Z}}_{n}(a)$
and $\sigma_{r}(\mathbf{Z}_{n}(a))=\sigma_{r}(\widehat{\mathbf{Z}}_{n}(a))$,
and the second inequality comes from applying the parallelogram inequality.
First we bound $T_{1}$. We have, with probability at least $1-O(\delta)$,
simultaneously for all $n\geq n_{0}(a)$

$\displaystyle T_{1}$ $\displaystyle\leq
8\left\|\widecheck{\mathcal{V}}_{n}(a)^{1/2}\left(\widecheck{\theta}_{n}(a)-\theta(a)\right)\right\|_{2}^{2}+6\left\|\Xi_{n}(a)\right\|_{2}^{2}+8\left\|\widehat{\mathbf{Z}}_{n}(a)\theta(a)-\mathbf{X}_{n}(a)\theta(a)\right\|_{2}^{2}$
(2) $\displaystyle\leq 32\rho
L^{2}+64\eta^{2}\left(\log\left(\frac{A}{\delta}\right)+r\log\left(1+\frac{\sigma_{1}(\mathbf{Z}_{n}(a))^{2}}{\rho}\right)\right)+16L^{2}U_{n}^{2}$
$\displaystyle+6\eta^{2}\sqrt{2c_{n}(a)\ell_{\delta}(c_{n}(a))}+10\eta^{2}\ell_{\delta}(c_{n}(a))+6c_{n}(a)\alpha+8T_{2},$

where the first inequality follows from Lemma D.1, and the second inequality
follows from applying Lemmas C.1 and D.3.
$\ell_{\delta}(n)=2\log\log(2n)+\log\left(\frac{d\pi^{2}}{12\delta}\right)$,
as defined in Lemma A.2. We now bound $T_{2}$. With probability at least
$1-O(\delta)$ simultaneously for all $n\geq n_{0}$, we have

$\displaystyle T_{2}$ $\displaystyle\leq
2L^{2}\sigma_{1}(\mathbf{Z}_{n}(a))^{2}\left\|\mathbf{P}-\widehat{\mathbf{P}}_{n}(a)\right\|_{op}^{2}+2L^{2}\left\|\mathcal{E}_{n}\right\|_{op}^{2}$
(3)
$\displaystyle\leq\frac{8L^{2}\sigma_{1}(\mathbf{Z}_{n}(a))^{2}U_{n}^{2}}{\sigma_{r}(\mathbf{X}_{n}(a))^{2}}+2L^{2}U_{n}^{2}$
$\displaystyle\leq\frac{12L^{2}\sigma_{1}(\mathbf{Z}_{n}(a))^{2}U_{n}^{2}}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}+2L^{2}U_{n}^{2}.$

The first inequality follows from Lemma D.2, the second inequality follows
from applying Lemmas B.4 and B.3, and the final inequality follows from Lemma
B.6.

Piecing the above inequalities together yields the desired result, which can
be checked via the argument at the end of Appendix D. A union bound over
actions then yields that the desired inequality holds over all actions
$a\in[A]$ with probability at least $1-O(A\delta)$. ∎

##  5 Application to causal inference with panel data

We now apply our bounds for adaptive PCR to online experiment design in the
context of panel data. In this setting, the learner is interested in
estimating _unit-specific counterfactuals_ under different _interventions_ ,
given a sequence of unit _outcomes_ (or _measurements_) over _time_. Units can
range from medical patients, to subpopulations or geographic locations.
Examples of interventions include medical treatments, discounts, and
socioeconomic policies. _Synthetic control (SC)_ is a popular framework used
to estimate counterfactual unit outcomes in panel data settings, had they not
been treated (i.e. remained under _control_) [1, 2]. In SC, there is a notion
of a _pre-intervention_ time period in which all units are under control,
followed by a _post-intervention_ time period, in which every unit undergoes
one of several interventions (including control). At a high level, SC fits a
model of a unit’s pre-treatment outcomes using pre-treatment data from units
who remained under control in the post-intervention time period. It then
constructs a “synthetic control” by using the learned model to predict the
unit’s post-intervention outcomes, had they remained under control. _Synthetic
interventions (SI)_ is a recent generalization of the SC framework, which
allows for counterfactual estimation of unit outcomes under different
interventions, in addition to control [8]. Using our bounds from Section 4, we
show how to generalize the SI framework of Agarwal et al. [8] to settings
where interventions are assigned via an _adaptive intervention assignment
policy_.

As a motivating example, consider an online e-commerce platform (learner)
which assigns discounts (interventions) to users (units) with the goal of
maximizing total user engagement on the platform. For concreteness, suppose
that the e-commerce platform assigns discounts _greedily_ with respect to the
discount level which appears to be best at the current round (i.e. maximizes
total engagement for the current user), given the sequence of previously
observed (user, discount level, engagement level) tuples. Under such a
setting, the intervention assigned at the current round $n$ will be correlated
with the observed engagement levels at previous rounds, thus breaking the
requirement of the SI framework [8] that the intervention assignment is not
adaptive to previously observed outcomes.

Formally, we consider a panel data setting in which the principal observes
units over a sequence of rounds. In each round $n$, the learner observes a
unit $n$ under _control_ for $T_{0}\in\mathbb{N}$ time steps, followed by one
of $A$ _interventions_ (including control, which we denote by $0$) for the
remaining $T-T_{0}$ time steps, where $T\in\mathbb{N}$. Overloading notation
to be consistent with the literature on panel data, we denote the potential
outcome of unit $n$ at time $t$ under intervention $a$ by
$\pv{Y}{a}_{n,t}\in\mathbb{R}$, the set of unit $n$’s pre-treatment outcomes
(under control) by
$Y_{n,pre}:=[Y_{n,1}^{(0)},\ldots,Y_{n,T_{0}}^{(0)}]^{T}\in\mathbb{R}^{T_{0}}$,
and their post-intervention potential outcomes under intervention $a$ by
$\pv{Y}{a}_{n,post}:=[Y_{n,T_{0}+1}^{(a)},\ldots,Y_{n,T}^{(a)}]^{T}\in\mathbb{R}^{T-T_{0}}$.
We use $a$ to refer to an arbitrary intervention in $\\{0,\ldots,A-1\\}$ and
$a_{n}$ to denote the _realized_ intervention unit $n$ actually receives in
the post-intervention time period. We posit that potential outcomes are
generated by the following _latent factor model_ over units, time steps, and
interventions.

######  Assumption 5.1 (Latent Factor Model).

Suppose the outcome for unit $n$ at time step $t$ under treatment
$a\in\\{0,\ldots,A-1\\}$ takes the form

$\pv{Y}{a}_{n,t}=\langle U_{t}^{(a)},V_{n}\rangle+\epsilon_{n,t}^{(a)},$

where $U_{t}^{(a)}\in\mathbb{R}^{r}$ is a latent factor which depends only on
the time step $t$ and intervention $a$, $V_{n}\in\mathbb{R}^{r}$ is a latent
factor which only depends on unit $n$, and $\epsilon_{n,t}^{(a)}$ is zero-mean
SubGaussian random noise with variance at most $\sigma^{2}$. We assume,
without loss of generality, that $|\langle U_{t}^{(a)},V_{n}\rangle|\leq 1$
for all $n\geq 1$, $t\in[T]$, $a\in\\{0,\ldots,A-1\\}$.

Note that the learner observes $\pv{Y}{a}_{n,t}$ _for only the intervention
$a_{n}$ that unit $n$ is under at time step $t$_, and never observes
$U_{t}^{(a)}$, $V_{n}$, or $\epsilon_{n,t}^{(a)}$. Such “low rank” assumptions
are ubiquitous within the panel data literature (see references in Section 2).
We assume that $r$ is known to the learner, although principled heuristics
exist for estimating $r$ in practice from data (see, e.g. Section 3.2 of
Agarwal et al. [8]). Additionally, we make the following “causal
transportability” assumption on the latent factors.

######  Assumption 5.2 (Linear span inclusion).

For any post-intervention time step $t\in[T_{0}+1,T]$ and intervention
$a\in\\{0,\ldots,A-1\\}$, we assume that
$\pv{U}{a}_{t}\in\mathrm{span}(\\{\pv{U}{0}_{t}:t\in[T_{0}]\\})$.

Intuitively, 5.2 allows for information to be inferred about the potential
outcomes in the post-intervention time period using pre-treatment
observations. The goal of the learner is to estimate unit-specific
counterfactual outcomes under different interventions _when the sequence of
units and interventions is chosen adaptively_. In line with previous work in
SI and SC, our target causal parameter is the (counterfactual) _average
expected post-intervention outcome_.

######  Definition 5.3.

The average expected post-intervention outcome of unit $n$ under intervention
$a$ is

$\mathbb{E}\pv{\bar{Y}}{a}_{n,post}:=\frac{1}{T-T_{0}}\sum_{t=T_{0}+1}^{T}\mathbb{E}\pv{Y}{a}_{n,t},$

where the expectation is taken with respect to
$(\epsilon_{n,t}^{(a)})_{T_{0}<t\leq T}$.

While we consider the _average_ post-intervention outcome, our results may be
readily extended to settings in which the target causal parameter is any
_linear_ combination of post-intervention outcomes. Next we show that under
5.1 and 5.2, $\mathbb{E}\pv{\bar{Y}}{a}_{n,post}$ may be written as a linear
combination of unit $n$’s _pre_ -intervention outcomes. We note that similar
observations have previously been made in the panel data literature (e.g.
[46]), but we include the following lemma for completeness’ sake.

######  Lemma 5.4 (Reformulation of average expected post-intervention
outcome).

Under 5.1 and 5.2, there exists slope vector $\theta(a)\in\mathbb{R}^{T_{0}}$,
such that the average expected post-intervention outcome of unit $n$ under
intervention $a$ is expressible as

$\mathbb{E}\pv{\bar{Y}}{a}_{n,post}=\frac{1}{T-T_{0}}\langle\theta(a),\mathbb{E}Y_{n,pre}\rangle.$

$\theta(a)$ may be interpreted as a unit-independent measure of the causal
relationship between pre- and post-intervention outcomes. Using this
reformulation, adaptive guarantees for the estimation of causal effects over
time may now be obtained by applying our online PCR results of Section 4.
Overloading the notation of Section 3, we let
$\mathbf{X}_{n}=(\mathbb{E}Y_{1,pre},\ldots,\mathbb{E}Y_{n,pre})^{T}$,
$\mathbf{Z}_{n}=(Y_{1,pre},\ldots,Y_{n,pre})^{T}$,
$\epsilon_{n,pre}=(\pv{\epsilon}{0}_{n,1},\ldots,\pv{\epsilon}{0}_{n,T_{0}})^{T}$,
$\mathcal{E}_{n}=(\epsilon_{1,pre},\ldots,\epsilon_{n,pre})^{T}$
$\xi_{n}=\sum_{t=T_{0}+1}^{T}\pv{\epsilon}{a_{n}}_{n,t}$,
$\Xi_{n}=(\xi_{1},\ldots,\xi_{n})^{T}$, and

$\mathbf{Y}_{n}=\left(\frac{1}{T-T_{0}}\sum_{t=1}^{T_{0}}\pv{Y}{a_{1}}_{1,t},\ldots,\frac{1}{T-T_{0}}\sum_{t=1}^{T_{0}}\pv{Y}{a_{n}}_{n,t}\right)^{T}.$

Finally, we define quantities such as $\mathbf{Z}_{n}(a)$,
$\mathbf{X}_{n}(a)$, $\mathbf{Y}_{n}(a)$ analogously to Section 3. We now turn
to bounding our primary quantity of interest in the panel data setting:
prediction error for the average expected post-intervention outcome.

######  Theorem 5.5 (Prediction error of average expected post-intervention
outcome).

Let $\delta\in(0,1)$ be an arbitrary confidence parameter and $\rho>0$ be
chosen to be sufficiently small, as detailed in Appendix F. Further, assume
that Assumptions 5.1 and 5.2 are satisfied, there is some $n_{0}\geq 1$ such
that $\mathrm{rank}(\mathbf{X}_{n_{0}}(a))=r$, and $\mathrm{snr}_{n}(a)\geq 2$
for all $n\geq n_{0}$. If $T_{0}\leq\frac{1}{2}T$ and $r\leq\sqrt{T_{0}\wedge
n}$, then under 4.2 with probability at least $1-O(A\delta)$, simultaneously
for all interventions $a\in\\{0,\ldots,A-1\\}$

$|\widehat{\mathbb{E}}\pv{\bar{Y}}{a}_{n,post}-\mathbb{E}\pv{\bar{Y}}{a}_{n,post}|=\widetilde{O}\left(\frac{L}{\sqrt{T-T_{0}}}+\frac{r}{\sqrt{T_{0}\wedge
n}}+\frac{r(L\vee 1)}{\sqrt{(T-T_{0})(T_{0}\wedge n)}}\right)$

where
$\widehat{\mathbb{E}}\pv{\bar{Y}}{a}_{n,post}:=\frac{1}{T-T_{0}}\cdot\langle\widehat{\theta}_{n}(a),Y_{n,pre}\rangle$
is the estimated average post-intervention outcome for unit $n$ under
intervention $a$.

A more complicated expression which does not require 4.2 or
$T_{0}\leq\frac{1}{2}T$ may be found in Appendix G. Observe that
$|\widehat{\mathbb{E}}\pv{\bar{Y}}{a}_{n,post}-\mathbb{E}\pv{\bar{Y}}{a}_{n,post}|\rightarrow
0$ with high probability as $T,T_{0},n\rightarrow\infty$.

We conclude this section by comparing our results with those of the (non-
adaptive) synthetic interventions framework of Agarwal et al. [8]. Since we
are regressing over _time_ , our method for estimating
$\widehat{\mathbb{E}}\pv{\bar{Y}}{a}_{n,post}$ is known as a _horizontal_
regression method in the panel data literature. This is in contrast to
_vertical_ regression methods, which regress over _units_. See Shen et al.
[75] for more details on the similarities and differences between horizontal
and vertical regression methods in panel data settings. While we do not
exactly match the bound of Agarwal et al. [8] since their synthetic
interventions framework of uses a vertical regression method, the two bounds
are similar, with the notable differences being as follows: (1) The bound of
[8] contains a “slow” $\widetilde{O}(r^{1/2}T_{0}^{-1/4})$ term which does not
appear in our analysis. (2) The non-adaptive SI bound also contains a term
which scales as $\widetilde{O}(\frac{\sqrt{n}}{\sqrt{T-T_{0}}})$ in the worst
case, while our bound has no such dependence. However, this comes at the price
of slow rate whenever $L$ is large compared to $\sqrt{T-T_{0}}$.

##  6 Conclusion

We obtain the first adaptive bounds for principal component regression and
apply them to the problem of online experiment design in the context of panel
data, where we allow for interventions to be assigned according to an adaptive
policy. Exciting directions for future work include applications of our
results to domains such as differential privacy, and using our bounds to
obtain contextual bandit algorithms (e.g. based on LinUCB [3]) capable of
regret minimization when given access to noisy contexts.

## Acknowledgements

KH is supported in part by an NDSEG Fellowship. KH, JW, and ZSW are supported
in part by NSF FAI Award #1939606. The authors would like to thank the
anonymous NeurIPS reviewers for valuable feedback.

## References

  * Abadie and Gardeazabal [2003] Alberto Abadie and Javier Gardeazabal.  The economic costs of conflict: A case study of the basque country.  _American economic review_ , 93(1):113–132, 2003\.
  * Abadie et al. [2010] Alberto Abadie, Alexis Diamond, and Jens Hainmueller.  Synthetic control methods for comparative case studies: Estimating the effect of california’s tobacco control program.  _Journal of the American statistical Association_ , 105(490):493–505, 2010.
  * Abbasi-Yadkori et al. [2011] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  _Advances in neural information processing systems_ , 24, 2011.
  * Agarwal et al. [2023] Abhineet Agarwal, Anish Agarwal, and Suhas Vijaykumar.  Synthetic combinations: A causal inference framework for combinatorial interventions.  _arXiv preprint arXiv:2303.14226_ , 2023.
  * Agarwal and Singh [2021] Anish Agarwal and Rahul Singh.  Causal inference with corrupted data: Measurement error, missing values, discretization, and differential privacy.  _arXiv preprint arXiv:2107.02780_ , 2021.
  * Agarwal et al. [2019] Anish Agarwal, Devavrat Shah, Dennis Shen, and Dogyoon Song.  On robustness of principal component regression.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Agarwal et al. [2020a] Anish Agarwal, Devavrat Shah, and Dennis Shen.  On principal component regression in a high-dimensional error-in-variables setting.  _arXiv preprint arXiv:2010.14449_ , 2020a.
  * Agarwal et al. [2020b] Anish Agarwal, Devavrat Shah, and Dennis Shen.  Synthetic interventions.  _arXiv preprint arXiv:2006.07691_ , 2020b.
  * Agarwal et al. [2021a] Anish Agarwal, Munther Dahleh, Devavrat Shah, and Dennis Shen.  Causal matrix completion.  _arXiv preprint arXiv:2109.15154_ , 2021a.
  * Agarwal et al. [2021b] Anish Agarwal, Devavrat Shah, Dennis Shen, and Dogyoon Song.  On robustness of principal component regression.  _Journal of the American Statistical Association_ , 116(536):1731–1745, 2021b.  doi: 10.1080/01621459.2021.1928513.
  * Agarwal et al. [2022] Anish Agarwal, Sarah Cen, Devavrat Shah, and Christina Lee Yu.  Network synthetic interventions: A framework for panel data with network interference.  _arXiv preprint arXiv:2210.11355_ , 2022.
  * Agarwal and Chen [2009] Deepak Agarwal and Bee-Chung Chen.  Regression-based latent factor models.  In _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 19–28, 2009.
  * Amjad et al. [2018] Muhammad Jehangir Amjad, Devavrat Shah, and Dennis Shen.  Robust synthetic control.  _Journal of Machine Learning Research_ , 19:1–51, 2018\.
  * Amjad et al. [2019] Muhummad Amjad, Vishal Mishra, Devavrat Shah, and Dennis Shen.  mrsc: Multi-dimensional robust synthetic control.  _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ , 3(2), 2019.
  * Arellano and Honore [2000] Manuel Arellano and Bo Honore.  Panel data models: Some recent developments.  _Handbook of Econometrics_ , 02 2000.
  * Arkhangelsky et al. [2020] Dmitry Arkhangelsky, Susan Athey, David A. Hirshberg, Guido W. Imbens, and Stefan Wager.  Synthetic difference in differences, 2020.
  * Athey et al. [2021] Susan Athey, Mohsen Bayati, Nikolay Doudchenko, Guido Imbens, and Khashayar Khosravi.  Matrix completion methods for causal panel data models.  _Journal of the American Statistical Association_ , 116(536):1716–1730, 2021.
  * Bai [2003] Jushan Bai.  Inferential theory for factor models of large dimensions.  _Econometrica_ , 71(1):135–171, 2003.  ISSN 00129682, 14680262.  URL http://www.jstor.org/stable/3082043.
  * Bai [2009] Jushan Bai.  Panel data models with interactive fixed effects.  _Econometrica_ , 77(4):1229–1279, 2009.  ISSN 00129682, 14680262.  URL http://www.jstor.org/stable/40263859.
  * Bai and Ng [2020] Jushan Bai and Serena Ng.  Matrix completion, counterfactuals, and factor analysis of missing data, 2020.
  * Bai and Ng [2021] Jushan Bai and Serena Ng.  Matrix completion, counterfactuals, and factor analysis of missing data.  _Journal of the American Statistical Association_ , 116(536):1746–1763, 2021.
  * Bair et al. [2006] Eric Bair, Trevor Hastie, Debashis Paul, and Robert Tibshirani.  Prediction by supervised principal components.  _Journal of the American Statistical Association_ , 101(473):119–137, 2006.
  * Ben-Michael et al. [2020] Eli Ben-Michael, Avi Feller, and Jesse Rothstein.  The augmented synthetic control method, 2020.
  * Carranza et al. [2023] Aldo Gael Carranza, Sanath Kumar Krishnamurthy, and Susan Athey.  Flexible and efficient contextual bandits with heterogeneous treatment effect oracles.  In _International Conference on Artificial Intelligence and Statistics_ , pages 7190–7212. PMLR, 2023.
  * Chamberlain [1984] Gary Chamberlain.  Panel data.  In Z. Griliches† and M. D. Intriligator, editors, _Handbook of Econometrics_ , volume 2, chapter 22, pages 1247–1318. Elsevier, 1 edition, 1984\.  URL https://EconPapers.repec.org/RePEc:eee:ecochp:2-22.
  * Chen [2023] Jiafeng Chen.  Synthetic control as online linear regression.  _Econometrica_ , 91(2):465–491, 2023.
  * Chernozhukov et al. [2020] Victor Chernozhukov, Kaspar Wuthrich, and Yinchu Zhu.  Practical and robust $t$-test based inference for synthetic control and related methods, 2020.
  * Chesher [1991] Andrew Chesher.  The effect of measurement error.  _Biometrika_ , 78(3):451–462, 1991.
  * Chowdhury and Gopalan [2017] Sayak Ray Chowdhury and Aditya Gopalan.  On kernelized multi-armed bandits.  In _International Conference on Machine Learning_ , pages 844–853. PMLR, 2017.
  * Chugg et al. [2023] Ben Chugg, Hongjian Wang, and Aaditya Ramdas.  A unified recipe for deriving (time-uniform) pac-bayes bounds.  _arXiv preprint arXiv:2302.03421_ , 2023.
  * Datta and Zou [2017] Abhirup Datta and Hui Zou.  Cocolasso for high-dimensional error-in-variables regression.  2017\.
  * de la Peña et al. [2004] Victor H de la Peña, Michael J Klass, and Tze Leung Lai.  Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws.  2004\.
  * de la Peña et al. [2007] Victor H de la Peña, Michael J Klass, and Tze Leung Lai.  Pseudo-maximization and self-normalized processes.  2007\.
  * Deshpande et al. [2018] Yash Deshpande, Lester Mackey, Vasilis Syrgkanis, and Matt Taddy.  Accurate inference for adaptive linear models.  In _International Conference on Machine Learning_ , pages 1194–1203. PMLR, 2018.
  * Doudchenko and Imbens [2016] N. Doudchenko and G. Imbens.  Balancing, regression, difference-in-differences and synthetic control methods: A synthesis.  _NBER Working Paper No. 22791_ , 2016.
  * Enders [2008] Walter Enders.  _Applied econometric time series_.  John Wiley & Sons, 2008.
  * Fan et al. [2018] Jianqing Fan, Weichen Wang, and Yiqiao Zhong.  An $\ell_{\infty}$ eigenvector perturbation bound and its application to robust covariance estimation.  _Journal of Machine Learning Research_ , 18(207):1–42, 2018.
  * Farias et al. [2022] Vivek Farias, Ciamac Moallemi, Tianyi Peng, and Andrew Zheng.  Synthetically controlled bandits.  _arXiv preprint arXiv:2202.07079_ , 2022.
  * Fernández-Val et al. [2020] Iván Fernández-Val, Hugo Freeman, and Martin Weidner.  Low-rank approximations of nonseparable panel models, 2020.
  * Figueroa-Zúñiga et al. [2022] Jorge I Figueroa-Zúñiga, Cristian L Bayes, Víctor Leiva, and Shuangzhe Liu.  Robust beta regression modeling with errors-in-variables: a bayesian approach and numerical applications.  _Statistical Papers_ , pages 1–24, 2022.
  * Fuller [2009] Wayne A Fuller.  _Measurement error models_.  John Wiley & Sons, 2009.
  * Griliches and Ringstad [1970] Zvi Griliches and Vidar Ringstad.  Error-in-the-variables bias in nonlinear contexts.  _Econometrica: Journal of the Econometric Society_ , pages 368–370, 1970.
  * Hadad et al. [2021] Vitor Hadad, David A Hirshberg, Ruohan Zhan, Stefan Wager, and Susan Athey.  Confidence intervals for policy evaluation in adaptive experiments.  _Proceedings of the national academy of sciences_ , 118(15):e2014602118, 2021.
  * Hall [2008] Daniel B Hall.  Measurement error in nonlinear models: a modern perspective, 2008.
  * Harris et al. [2022a] Keegan Harris, Anish Agarwal, Chara Podimata, and Zhiwei Steven Wu.  Strategyproof decision-making in panel data settings and beyond.  _arXiv preprint arXiv:2211.14236_ , 2022a.
  * Harris et al. [2022b] Keegan Harris, Dung Daniel T Ngo, Logan Stapleton, Hoda Heidari, and Steven Wu.  Strategic instrumental variable regression: Recovering causal relationships from strategic responses.  In _International Conference on Machine Learning_ , pages 8502–8522. PMLR, 2022b.
  * Hausman [2001] Jerry Hausman.  Mismeasured variables in econometric analysis: problems from the right and problems from the left.  _Journal of Economic perspectives_ , 15(4):57–67, 2001.
  * Hoff [2009] Peter D Hoff.  Multiplicative latent factor models for description and prediction of social networks.  _Computational and mathematical organization theory_ , 15(4):261, 2009.
  * Honorio and Jaakkola [2014] Jean Honorio and Tommi Jaakkola.  Tight bounds for the expected risk of linear classifiers and pac-bayes finite-sample guarantees.  In _Artificial Intelligence and Statistics_ , pages 384–392. PMLR, 2014.
  * Howard et al. [2020] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon.  Time-uniform chernoff bounds via nonnegative supermartingales.  2020\.
  * Howard et al. [2021] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon.  Time-uniform, nonparametric, nonasymptotic confidence sequences.  2021\.
  * Hsiao et al. [2012] Cheng Hsiao, H. Steve Ching, and Shui Ki Wan.  A panel data approach for program evaluation: Measuring the benefits of political and economic integration of hong kong with mainland china.  _Journal of Applied Econometrics_ , 27(5):705–740, 2012.  doi: https://doi.org/10.1002/jae.1230.
  * Jenatton et al. [2012] Rodolphe Jenatton, Nicolas Roux, Antoine Bordes, and Guillaume R Obozinski.  A latent factor model for highly multi-relational data.  _Advances in neural information processing systems_ , 25, 2012.
  * Jolliffe [1982] Ian T Jolliffe.  A note on the use of principal components in regression.  _Journal of the Royal Statistical Society Series C: Applied Statistics_ , 31(3):300–303, 1982.
  * Kalai and Vempala [2005] Adam Kalai and Santosh Vempala.  Efficient algorithms for online decision problems.  _Journal of Computer and System Sciences_ , 71(3):291–307, 2005.
  * Kaul and Koul [2015] Abhishek Kaul and Hira L Koul.  Weighted l1-penalized corrected quantile regression for high dimensional measurement error models.  _Journal of Multivariate Analysis_ , 140:72–91, 2015.
  * Kim et al. [1990] In-Won Kim, Michael J Liebman, and Thomas F Edgar.  Robust error-in-variables estimation using nonlinear programming techniques.  _AIChE Journal_ , 36(7):985–993, 1990.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Li [2018] Kathleen T. Li.  Inference for factor model based average treatment effects.  _Available at SSRN 3112775_ , 2018.
  * Li and Bell [2017] Kathleen T. Li and David R. Bell.  Estimation of average treatment effects with panel data: Asymptotic theory and implementation.  _Journal of Econometrics_ , 197(1):65 – 75, 2017\.  ISSN 0304-4076.  doi: https://doi.org/10.1016/j.jeconom.2016.01.011.
  * Liang and Zeger [1986] Kung-Yee Liang and Scott L. Zeger.  Longitudinal data analysis using generalized linear models.  _Biometrika_ , 73(1):13–22, 04 1986.  ISSN 0006-3444.  doi: 10.1093/biomet/73.1.13.  URL https://doi.org/10.1093/biomet/73.1.13.
  * Loh and Wainwright [2011] Po-Ling Loh and Martin J Wainwright.  High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity.  _Advances in neural information processing systems_ , 24, 2011.
  * Manole and Ramdas [2023] Tudor Manole and Aaditya Ramdas.  Martingale methods for sequential estimation of convex functionals and divergences.  _IEEE Transactions on Information Theory_ , 2023.
  * Moon and Weidner [2015] Hyungsik Roger Moon and Martin Weidner.  Linear regression for panel with unknown number of factors as interactive fixed effects.  _Econometrica_ , 83(4):1543–1579, 2015.  ISSN 00129682, 14680262.  URL http://www.jstor.org/stable/43616977.
  * Moon and Weidner [2017] Hyungsik Roger Moon and Martin Weidner.  Dynamic linear panel regression models with interactive fixed effects.  _Econometric Theory_ , 33(1):158–195, 2017.  doi: 10.1017/S0266466615000328.
  * Ngo et al. [2023] Daniel Ngo, Keegan Harris, Anish Agarwal, Vasilis Syrgkanis, and Zhiwei Steven Wu.  Incentive-aware synthetic control: Accurate counterfactual estimation via incentivized exploration.  2023\.
  * Nie et al. [2018] Xinkun Nie, Xiaoying Tian, Jonathan Taylor, and James Zou.  Why adaptively collected data have negative bias and how to correct for it.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1261–1269. PMLR, 2018.
  * Pesaran [2006] M. Hashem Pesaran.  Estimation and inference in large heterogeneous panels with a multifactor error structure.  _Econometrica_ , 74(4):967–1012, 2006.  ISSN 00129682, 14680262.  URL http://www.jstor.org/stable/3805914.
  * Qin and Russo [2022] Chao Qin and Daniel Russo.  Adaptivity and confounding in multi-armed bandit experiments.  _arXiv preprint arXiv:2202.09036_ , 2022.
  * Reilly and Patino-Lea1 [1981] Park M Reilly and Hugo Patino-Lea1.  A bayesian study of the error-in-variables model.  _Technometrics_ , 23(3):221–231, 1981.
  * Roman et al. [2005] Steven Roman, S Axler, and FW Gehring.  _Advanced linear algebra_ , volume 3.  Springer, 2005.
  * Rosenbaum and Tsybakov [2010] Mathieu Rosenbaum and Alexandre B Tsybakov.  Sparse recovery under matrix uncertainty.  _The Annals of Statistics_ , pages 2620–2651, 2010.
  * Rudelson and Vershynin [2013] Mark Rudelson and Roman Vershynin.  Hanson-wright inequality and sub-gaussian concentration.  2013\.
  * Settles [2009] Burr Settles.  Active learning literature survey.  2009\.
  * Shen et al. [2022] Dennis Shen, Peng Ding, Jasjeet Sekhon, and Bin Yu.  A tale of two panel data regressions.  _arXiv preprint arXiv:2207.14481_ , 2022.
  * Shumway et al. [2000] Robert H Shumway, David S Stoffer, and David S Stoffer.  _Time series analysis and its applications_ , volume 3.  Springer, 2000.
  * Simchi-Levi and Wang [2023] David Simchi-Levi and Chonghuan Wang.  Multi-armed bandit experimental design: Online decision-making and adaptive inference.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3086–3097. PMLR, 2023.
  * Slivkins et al. [2019] Aleksandrs Slivkins et al.  Introduction to multi-armed bandits.  _Foundations and Trends® in Machine Learning_ , 12(1-2):1–286, 2019.
  * Squires et al. [2022] Chandler Squires, Dennis Shen, Anish Agarwal, Devavrat Shah, and Caroline Uhler.  Causal imputation via synthetic interventions.  In _Conference on Causal Learning and Reasoning_ , pages 688–711. PMLR, 2022.
  * Tropp et al. [2015] Joel A Tropp et al.  An introduction to matrix concentration inequalities.  _Foundations and Trends® in Machine Learning_ , 8(1-2):1–230, 2015.
  * Ungarala and Bakshi [2000] Sridhar Ungarala and Bhavik R Bakshi.  A multiscale, bayesian and error-in-variables approach for linear dynamic data rectification.  _Computers & Chemical Engineering_, 24(2-7):445–451, 2000.
  * Vershynin [2018] Roman Vershynin.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Wainwright [2019] Martin J Wainwright.  _High-dimensional statistics: A non-asymptotic viewpoint_ , volume 48.  Cambridge university press, 2019.
  * Wansbeek and Meijer [2001] Tom Wansbeek and Erik Meijer.  Measurement error and latent variables.  _A companion to theoretical econometrics_ , pages 162–179, 2001.
  * Whitehouse et al. [2022] Justin Whitehouse, Aaditya Ramdas, Steven Z Wu, and Ryan M Rogers.  Brownian noise reduction: Maximizing privacy subject to accuracy constraints.  _Advances in Neural Information Processing Systems_ , 35:11217–11228, 2022.
  * Whitehouse et al. [2023a] Justin Whitehouse, Aaditya Ramdas, Ryan Rogers, and Steven Wu.  Fully-adaptive composition in differential privacy.  In _International Conference on Machine Learning_ , pages 36990–37007. PMLR, 2023a.
  * Whitehouse et al. [2023b] Justin Whitehouse, Zhiwei Steven Wu, and Aaditya Ramdas.  On the sublinear regret of GP-UCB.  _Advances in Neural Information Processing Systems_ , 2023b.
  * Whitehouse et al. [2023c] Justin Whitehouse, Zhiwei Steven Wu, and Aaditya Ramdas.  Time-uniform self-normalized concentration for vector-valued processes.  _arXiv preprint arXiv:2310.09100_ , 2023c.
  * Xu [2017] Yiqing Xu.  Generalized synthetic control method: Causal inference with interactive fixed effects models.  _Political Analysis_ , 25(1):57–76, 2017.  doi: 10.1017/pan.2016.2.
  * Zhang et al. [2022a] Jingwen Zhang, Yifang Chen, and Amandeep Singh.  Causal bandits: Online decision-making in endogenous settings.  _arXiv preprint arXiv:2211.08649_ , 2022a.
  * Zhang et al. [2021] Kelly Zhang, Lucas Janson, and Susan Murphy.  Statistical inference with m-estimators on adaptively collected data.  _Advances in neural information processing systems_ , 34:7460–7471, 2021.
  * Zhang et al. [2022b] Kelly W Zhang, Lucas Janson, and Susan A Murphy.  Statistical inference after adaptive sampling in non-markovian environments.  _arXiv preprint arXiv:2202.07098_ , 2022b.

##  Appendix A Results on martingale concentration

In this section, we discuss the basics of martingale concentration that will
be used ubiquitously throughout this work. Recall that a process
$(M_{n})_{n\geq 0}$ is a martingale with respect to some filtration
$(\mathcal{F}_{n})_{n\geq 0}$ if (a) $(M_{n})_{n\geq 0}$ is adapted to
$(\mathcal{F}_{n})_{n\geq 0}$, (b) $\mathbb{E}|M_{n}|<\infty$ for all $n\geq
0$, and (c) $\mathbb{E}(M_{n+1}\mid\mathcal{F}_{n})=M_{n}$ for all $n\geq 0$.
We denote the “increments” of a martingale as $\Delta M_{n}:=M_{n}-M_{n-1}$.
Results on martingale concentration yield a means of providing tight, time-
uniform concentration for statistical tasks in which data is adaptively
collected. Recent advances in martingale concentration have allowed for
advances in disparate fields of statistical theory such as PAC-Bayesian
learning [30], composition in differential privacy [86, 85], and the
estimation of convex statistical divergences [63].

Martingale concentration emerges naturally in our work in two ways. First,
martingale concentration plays an integral role in bounding the deviations
between $\widecheck{\theta}_{t}(a)$, the ridge estimate in the true low-
dimensional subspace, and $\theta(a)$. In bounding these deviations, we
leverage results on the concentration of self-normalized martingale processes,
particularly those of de la Peña et al. [32, 33]. These results have long
proven useful for calibrating confidence in online linear regression tasks [3,
29], but to the best of our knowledge, we are the first to couple these
results with the low-dimensional estimation innate to PCR.

Second, we leverage martingale methods to control the rate at which PCR’s
estimate of the projection operator onto the unknown subspace converges. To
accomplish this, we couple recent breakthroughs on time-uniform, self-
normalized concentration for scalar-valued processes [50, 51] with the
covering and matrix-CGF approaches for bounding the error in estimates of
covariance matrices [83, 71, 80]. While this aspect of our analysis is, more
or less, a straightforward merging of two techniques for concentration of
measure, it nonetheless requires care due to the technical nature of the
machinery being used.

We start by recounting the time-uniform concentration inequality we leverage
for controlling the error in the ridge estimate in the true, low-dimensional
subspace. The following result is from Abbasi-Yadkori et al. [3], but is a
special case of more general, self-normalized concentration results from de la
Peña et al. [32, 33].

######  Lemma A.1 (Method of Mixtures).

Let $(\mathcal{F}_{t})_{t\geq 0}$ be a filtration. Let
$S_{t}=\sum_{s=1}^{t}\epsilon_{s}X_{s}$ where $(\epsilon_{t})_{t\geq 1}$ is an
$(\mathcal{F}_{t})_{t\geq 0}$-adapted $\mathbb{R}$-valued process of
$\sigma$-subGaussian random variables and $(X_{t})_{t\geq 1}$ is an
$(\mathcal{F}_{t})_{t\geq 1}$-predictable $\mathbb{R}^{d}$-valued process. Let
$\rho>0$ be arbitrary, and let

$\mathcal{V}_{t}:=\sum_{s=1}^{t}X_{s}X_{s}^{T}+\rho I_{d}.$

Let $\delta\in(0,1)$ be any confidence parameter. Then we have with
probability at least $1-\delta$, simultaneously for all $t\geq 1$,

$\left\|\mathcal{V}_{t}^{-1/2}S_{t}\right\|_{2}\leq\sigma\sqrt{2\log\left(\frac{1}{\delta}\sqrt{\det(\rho^{-1}\mathcal{V}_{t})}\right)}.$

We make several brief comments about the above lemma. First, note that while
the word “martingale” doesn’t directly appear, the process $(S_{n})_{n\geq 0}$
is, in fact, a martingale with respect to the filtration
$(\mathcal{F}_{n})_{n\geq 0}$. The concentration inequality follows from
“mixing” a family of martingales based on $(S_{n})_{n\geq 0}$ with respect to
some suitable probability measure. Second, how we leverage Lemma A.1 in
conjunction with the low-dimensional structure of the problem comes through
the presence of $\det(\rho^{-1}\mathcal{V}_{n})$ in the bound. In particular,
if the sequence $(X_{n})_{n\geq 0}$ lies in some low-dimensional subspace $W$,
with $\dim(W)=r$, then $\rho^{-1}\mathcal{V}_{n}$ will have at most $r$ non-
unit eigenvalues, and hence $\log\det(\rho^{-1}\mathcal{V}_{n})\approx
r\log(\|\rho^{-1}\mathcal{V}_{n}\|_{op})$. We exploit this idea further in the
sequel.

Now, we discuss the scalar-valued martingale concentration results from Howard
et al. [50, 51] that will be used in our work. Before this, recall that a
random variable $X$ is said to be $\sigma$-subGaussian if
$\log\mathbb{E}e^{\lambda X}\leq\frac{\lambda^{2}\sigma^{2}}{2}$ for all
$\lambda\in\mathbb{R}$. Likewise, we say $X$ is $(\sigma,c)$-subExponential if
$\log\mathbb{E}e^{\lambda X}\leq\frac{\lambda^{2}\sigma^{2}}{2}$ for all
$|\lambda|<\frac{1}{c}$, and we say $X$ is $(\sigma,c)$-subGamma if
$\log\mathbb{E}e^{\lambda X}\leq\sigma^{2}\psi_{G,c}(\lambda)$ for all
$|\lambda|<\frac{1}{c}$, where
$\psi_{G,c}(\lambda):=\frac{\lambda^{2}}{2(1-c\lambda)}$. A particularly
useful fact in the sequel is that if $X$ is $(\sigma,c)$-subExponential, it is
also $(\sigma,c)$-subGamma [50].

######  Lemma A.2.

Suppose $(X_{n})_{n\geq 1}$ is a sequence of independent,
$(\sigma,c)$-subGamma random variables. Let $(S_{n})_{n\geq 0}$ be given by
$S_{n}:=\sum_{m=1}^{n}X_{n}$, and let $\delta\in(0,1)$ be arbitrary. Then,
with probability at least $1-\delta$, simultaneously for all $n\geq 0$, we
have

$S_{n}\leq\frac{3}{2}\sigma\sqrt{n\ell_{\delta}(n)}+\frac{5}{2}c\ell_{\delta}(n),$

where
$\ell_{\delta}(n):=2\log\log(2n)+\log\left(\frac{d\pi^{2}}{12\delta}\right)$.

Note that we have simplified above bound from Howard et al. [51] in several
ways. First, the bound as presented in Howard et al. [51] applies to general
classes of processes with potentially correlated increments. We have
simplified the bound to the setting of independent, subGamma increments to
suit our setting. Further, the original bound has many parameters, each of
which can be fine-tuned to fit an application. We have pre-selected parameters
so that (a) the bound is legible and (b) constants remain relatively small.

We can couple the above bound with a standard argument for bounding error in
covariance estimation [83] to obtain high-probability, time-uniform results.
The following result will prove useful in measuring the rapidity at which PCA
can learn the true, low-dimensional subspace in which the noiseless contexts
and slope vectors lie.

######  Lemma A.3.

Let $(\epsilon_{n})_{n\geq 1}$ be a sequence of independent,
$\sigma$-subGaussian random vectors in $\mathbb{R}^{d}$. Then, for any
$\delta\in(0,1)$, with probability at least $1-\delta$, simultaneously for all
$n\geq 1$, we have

$\left\|\sum_{m=1}^{n}\epsilon_{m}\epsilon_{m}^{\top}-\mathbb{E}\epsilon_{m}\epsilon_{m}^{\top}\right\|_{op}\leq\beta\left(3\sqrt{n\ell_{\delta/2\mathcal{N}}(n)}+5\ell_{\delta/2\mathcal{N}}(n)\right),$

where $\ell_{\delta}$ is as defined in Lemma A.2, $\beta=32\sigma^{2}e^{2}$,
and $\mathcal{N}=17^{d}$ is an upper bound on the $1/8$-covering number of
$\mathbb{S}^{d-1}$.

###### Proof.

Define the process $(M_{n})_{n\geq 0}$ by
$M_{n}:=\sum_{m=1}^{n}\epsilon_{m}\epsilon_{m}^{\top}-\mathbb{E}\epsilon_{m}\epsilon_{m}^{\top}$.
Using a standard covering argument (more or less verbatim from Wainwright
[83]), we have that, if $K\subset\mathbb{S}^{d-1}$ is a minimal $1/8$-covering
of $\mathbb{S}^{d-1}$, then

$\|M_{n}\|_{op}\leq 2\max_{\nu\in K}\langle\nu,M_{n}\nu\rangle$ (4)

It is clear that $(M_{n})_{n\geq 0}$ is a Hermitian matrix-valued martingale
with respect to the natural filtration $(\mathcal{F}_{n})_{n\geq 0}$ given by
$\mathcal{F}_{n}:=\sigma(\epsilon_{m}:m\leq n)$. It is thus straightforward to
see that, for any $\nu\in\mathbb{S}^{d-1}$, the process $(M_{n}^{\nu})_{n\geq
0}$ given by $M_{n}^{\nu}:=\nu^{T}M_{n}\nu$ is a real-valued martingale with
respect to this same filtration.

Moreover, a standard argument (see the proof of Theorem 6.5 in Wainwright
[83]) yields that

$\log\left[\mathbb{E}e^{\lambda\langle\nu,\Delta
M_{n}\nu\rangle}\right]\leq\frac{\lambda^{2}\beta^{2}}{2}\qquad\text{for all
}|\lambda|<\frac{1}{\beta},$ (5)

where $\beta:=32e^{2}\sigma^{2}$. In other words, for any
$\nu\in\mathbb{S}^{d-1}$, the random variable $\langle\nu,\Delta
M_{n}\nu\rangle$ is $\left(\beta,\beta\right)$-sub-Exponential, as outlined
above. In particular, per the results of Howard et al. [50, 51], this implies
that the random variable $\langle\nu,\Delta M_{n}\nu\rangle$ is
$(\beta,\beta)$-subGamma. Applying Lemma A.2, we have, with probability at
least $1-\delta$, simultaneously for all $n\geq 1$ and $\nu\in K$, that

$|\langle\nu,M_{n}\nu\rangle|\leq\frac{3}{2}\beta\sqrt{n\ell_{\delta/2\mathcal{N}}(n)}+\beta\frac{5}{2}\ell_{\delta/2\mathcal{N}}(n).$

Plugging this into Inequality 4, we have that, with probability at least
$1-\delta$, simultaneously for all $n\geq 1$,

$\|M_{n}\|_{op}\leq\beta\left(3\sqrt{n\ell_{\delta/2\mathcal{N}}(n)}+5\ell_{\delta/2\mathcal{N}}(n)\right).$

∎

In the case that the sequence of independent noise variables
$(\epsilon_{n})_{n\geq 1}$ satisfies
$\mathbb{E}\epsilon_{n}\epsilon_{n}^{\top}=\Sigma$ and
$\|\epsilon_{n}\|_{2}\leq\sqrt{B}$ uniformly in $n$, we can obtain
signifcantly tighter bounds (in terms of constants). Of particular import is
the following bound from Howard et al. [51], which combines their “stitching
approach” to time-uniform concentration with matrix chernoff techniques [50,
80, 83] to obtain time-uniform bounds on covariance estimation.

######  Lemma A.4.

Let $(\epsilon_{n})_{n\geq 1}$ be a sequence of mean zero, independent random
vectors in $\mathbb{R}^{d}$ such that, for all $n\geq 1$, we have
$\mathbb{E}\epsilon_{n}\epsilon_{n}^{\top}=\Sigma$ and
$\|\epsilon_{n}\|_{2}\leq\sqrt{Cd}$ almost surely. Further assume
$\|\Sigma\|_{op}\leq\gamma$. Then, for any $\delta\in(0,1)$, we have, with
probability at least $1-\delta$, simultaneously for all $n\geq 1$

$\left\|\sum_{m=1}^{n}\left\\{\epsilon_{m}\epsilon_{m}^{\top}-\Sigma\right\\}\right\|_{op}\leq\frac{3}{2}\sqrt{nCd\gamma\ell_{\delta}(n)}+\frac{7}{3}Cd\ell_{\delta}(t)$

where
$\ell_{\delta}(n):=2\log\log(2n)+\log\left(\frac{d\pi^{2}}{12\delta}\right)$.

##  Appendix B Convergence results for PCA and singular values

In this appendix, we discuss time-uniform convergence results for adaptive
principal component analysis — one half of the principal component regression
(PCR) algorithm. In addition, we analyze how singular values of
$\mathbf{Z}_{n}$, the noisy covariate matrix, cluster around those of
$\mathbf{X}_{n}$, the true covariate matrix. We, in the style of Agarwal et
al. [7], reduce our study of these quantities to the study of the operator
norm of $\mathcal{E}_{n}$, which we control using the martingale concentration
results outlined in Appendix A.

Before continuing, we enumerate several linear algebraic facts that are useful
in bounding deviations in singular values.

######  Lemma B.1 (Weyl’s Inequality).

Let $\mathbf{A},\mathbf{B}\in\mathbb{R}^{t\times n}$. Then, for any
$i\in[t\land n]$, we have

$\left|\sigma_{i}(\mathbf{A})-\sigma_{i}(\mathbf{B})\right|\leq\left\|\mathbf{A}-\mathbf{B}\right\|_{op}.$

######  Lemma B.2 (Wedin’s Lemma).

Let $\mathbf{A},\mathbf{B}\in\mathbb{R}^{t\times n}$, and suppose $\mathbf{A}$
and $\mathbf{B}$ have spectral decompositions

$\mathbf{A}=\mathbf{U}\Sigma\mathbf{V}^{T}\qquad\text{and}\qquad\mathbf{B}=\widehat{\mathbf{U}}\widehat{\Sigma}\widehat{\mathbf{V}}^{T}.$

Then, for any $r\leq n\land d$, we have

$\max\left\\{\left\|\mathbf{U}_{r}\mathbf{U}_{r}^{T}-\widehat{\mathbf{U}}_{r}\widehat{\mathbf{U}}_{r}^{T}\right\|_{op},\left\|\mathbf{V}_{r}\mathbf{V}_{r}^{T}-\widehat{\mathbf{V}}_{r}\widehat{\mathbf{V}}_{r}^{T}\right\|_{op}\right\\}\leq\frac{2\left\|\mathbf{A}-\mathbf{B}\right\|_{op}}{\sigma_{r}-\sigma_{r+1}},$

where $\sigma_{r}$ (resp. $\sigma_{r+1}$) is the $r$-th (resp. $r+1$-st)
largest singular value of $\mathbf{A}$.

We now prove a time-uniform, high probability bound on the operator norm of
$\mathcal{E}_{n}$. (Recall
$\mathcal{E}_{n}=(\epsilon_{1},\ldots,\epsilon_{n})^{T}$.) In particular, we
prove a bound for two settings — a looser bound (in terms of constants) which
holds when the noise variables $\epsilon_{n}$ are assumed to be subGaussian,
and a tighter, more practically relevant bound that holds when $\epsilon_{n}$
are assumed to be bounded.

######  Lemma B.3 (Covariance Noise Bound).

Let $(\epsilon_{n})_{n\geq 1}$ be a sequence of independent, mean zero random
vectors in $\mathbb{R}^{d}$ such that
$\|\mathbb{E}\epsilon_{n}\epsilon_{n}^{\top}\|_{op}\leq\gamma$ for all $n\geq
1$. Let $\delta\in(0,1)$ be an arbitrary confidence parameter. Then, with
probability at least $1-\delta$, simultaneously for all $n\geq 1$ we have

$\displaystyle\|\mathcal{E}_{n}\|_{op}^{2}\leq\begin{cases}\beta\left(3\sqrt{n\ell_{\delta/2\mathcal{N}}(n)}+5\ell_{\delta/2\mathcal{N}}(n)\right)+n\gamma\quad\text{when
Assumption~{}\ref{ass:noise1} holds}\\\
\frac{3}{2}\sqrt{nCd\gamma\ell_{\delta}(n)}+\frac{7}{3}Cd\ell_{\delta}(n)+n\gamma\quad\text{when
Assumption~{}\ref{ass:noise2} holds}.\end{cases}$

where $\ell_{\delta}$ is as defined in Lemma A.2, $\beta=32\sigma^{2}e^{2}$,
and $\mathcal{N}=17^{d}$ is an upper bound on the $1/8$-covering number of
$\mathbb{S}^{d-1}$.

###### Proof.

Observe the following basic chain of reasoning.

$\|\mathcal{E}_{n}\|_{op}^{2}=\|\mathcal{E}_{n}^{\top}\mathcal{E}_{n}\|_{op}\leq\|\mathcal{E}_{n}^{\top}\mathcal{E}_{n}-\mathbb{E}\mathcal{E}_{n}^{\top}\mathcal{E}_{n}\|_{op}+\|\mathbb{E}\mathcal{E}_{n}^{\top}\mathcal{E}_{n}\|_{op}.$

Now, both Assumption 3.1 and 3.2 imply that
$\|\mathbb{E}[\epsilon_{n}\epsilon_{n}^{\top}]\|_{op}\leq\gamma$ for all
$n\geq 1$. Consequently, noting that
$\mathcal{E}_{n}^{\top}\mathcal{E}_{n}=\sum_{m=1}^{n}\epsilon_{m}\epsilon_{m}^{\top}$,
we have that

$\|\mathbb{E}\mathcal{E}_{n}^{\top}\mathcal{E}_{n}\|_{op}\leq\sum_{m=1}^{n}\|\mathbb{E}\epsilon_{m}\epsilon_{m}^{\top}\|_{op}\leq
n\gamma.$

Likewise, we have, applying Lemma A.3 in the case the $\epsilon_{n}$ satisfy
the subGaussian assumption and Lemma A.4 in the case the noise satisfies the
bounded assumption, that, with probability at least $1-\delta$, simultaneously
for all $n\geq 1$,

$\|\mathcal{E}_{n}^{\top}\mathcal{E}_{n}-\mathbb{E}\mathcal{E}_{n}^{\top}\mathcal{E}_{n}\|_{op}\leq\begin{cases}\beta\left(3\sqrt{n\ell_{\delta/2\mathcal{N}}(n)}+5\ell_{\delta/2\mathcal{N}}(n)\right)\quad\text{
when Assumption~{}\ref{ass:noise1} holds}\\\
\frac{3}{2}\sqrt{nCd\gamma\ell_{\delta}(n)}+\frac{7}{3}Cd\ell_{\delta}(n)\quad\text{
when Assumption~{}\ref{ass:noise2} holds}.\end{cases}$

Adding these two lines of reasoning together yields the desired conclusion.

∎

We can now apply Lemma B.3 to bound the rate at which
$\widehat{\mathbf{P}}_{n},$ the projection operator onto the learned subspace
at time $n$, converges to the projection operator $\mathbf{P}$ onto the true,
low-dimensional subspace.

######  Lemma B.4 (Projection Convergence).

Let $\widehat{\mathbf{P}}_{n}$ denote the projection operator onto the learned
subspace. Further, let $\mathbf{P}$ denote the projection operator onto the
true unknown subspace $W^{\ast}$. Assume $\mathrm{rank}(\mathbf{X}_{n_{0}})=r$
for some $n_{0}\geq 1$. Then, for any $\delta\in(0,1)$, we have with
probability at least $1-\delta$, simultaneously for all $n\geq n_{0}$,

$\|\widehat{\mathbf{P}}_{n}-\mathbf{P}\|_{op}^{2}\leq\begin{cases}\frac{4\beta\left(3\sqrt{n\ell_{\delta/2\mathcal{N}}(n)}+5\ell_{\delta/2\mathcal{N}}(n)\right)+4n\gamma}{\sigma_{r}(\mathbf{X}_{n})^{2}}\quad\text{when
Assumption~{}\ref{ass:noise1} holds}\\\
\frac{6\sqrt{nCd\gamma\ell_{\delta}(n)}+\frac{14}{3}Cd\ell_{\delta}(n)+4n\gamma}{\sigma_{r}(\mathbf{X}_{n})^{2}}\quad\text{when
Assumption~{}\ref{ass:noise2} holds}.\par\end{cases}$

###### Proof.

We write the singular value decompositions of $\mathbf{Z}_{n}$ and
$\mathbf{X}_{n}$ respectively as

$\mathbf{Z}_{n}=\widehat{\mathbf{U}}_{n}\widehat{\Sigma}_{n}\widehat{\mathbf{V}}_{n}^{\top}\quad\text{and}\quad\mathbf{X}_{n}=\widecheck{\mathbf{U}}_{n}\widecheck{\Sigma}_{n}\widecheck{\mathbf{V}}_{n}^{\top}.$

Since we have assumed $\mathrm{rank}(\mathbf{X}_{n_{0}})=r$ for some
$n_{0}\geq 1$, we have, for all $n\geq n_{0}$,

$\widehat{\mathbf{P}}_{n}=\widehat{\mathbf{V}}_{n,r}\widehat{\mathbf{V}}_{n,r}^{T}\quad\text{and}\quad\mathbf{P}=\widecheck{\mathbf{V}}_{n,r}\widecheck{\mathbf{V}}_{n,r}^{T}.$

Now, applying Lemma B.2 and Lemma B.3 we have that, with probability at least
$1-\delta$, simultaneously for all $n\geq n_{0}$,

$\displaystyle\left\|\widehat{\mathbf{P}}_{n}-\mathbf{P}\right\|_{op}^{2}$
$\displaystyle=\left\|\widehat{\mathbf{V}}_{n,r}\widehat{\mathbf{V}}_{n,r}^{T}-\widecheck{\mathbf{V}}_{n,r}\widecheck{\mathbf{V}}_{n,r}^{T}\right\|_{op}^{2}$
$\displaystyle\leq\frac{4\left\|\mathbf{X}_{n}-\mathbf{Z}_{n}\right\|_{op}^{2}}{\sigma_{r}(\mathbf{X}_{n})^{2}}$
$\displaystyle=\frac{4\|\mathcal{E}_{n}\|_{op}^{2}}{\sigma_{r}(\mathbf{X}_{n})^{2}}$
$\displaystyle\leq\begin{cases}\frac{4\beta\left(3\sqrt{n\ell_{\delta/2\mathcal{N}}(n)}+5\ell_{\delta/2\mathcal{N}}(n)\right)+4n\gamma}{\sigma_{r}(\mathbf{X}_{n})^{2}}\quad\text{when
Assumption~{}\ref{ass:noise1} holds}\\\
\frac{6\sqrt{nCd\gamma\ell_{\delta}(n)}+\frac{14}{3}Cd\ell_{\delta}(n)+4n\gamma}{\sigma_{r}(\mathbf{X}_{n})^{2}}\quad\text{when
Assumption~{}\ref{ass:noise2} holds}.\end{cases}$

This proves the desired result. ∎

We can obtain the following empirical version of Lemma B.4. The proof of the
following is identical—the only difference is that, in the application of
Wedin’s theorem (Lemma B.2), we put the singular values of $\mathbf{Z}_{n}$ is
the denominator instead of $\mathbf{X}_{n}$. This inequality is, in practice,
more useful in computing confidence bounds, as the singular values of
$\mathbf{Z}_{n}$ are computable, whereas the singular values of
$\mathbf{X}_{n}$ are not.

######  Lemma B.5 (Projection Convergence).

Let $\widehat{\mathbf{P}}_{n}$ denote the projection operator onto the learned
subspace. Further, let $\mathbf{P}$ denote the projection operator onto the
true unknown subspace $W^{\ast}$. Assume $\mathrm{rank}(\mathbf{X}_{n_{0}})=r$
for some $n_{0}\geq 1$. Then, for any $\delta\in(0,1)$, we have with
probability at least $1-\delta$, simultaneously for all $n\geq n_{0}$,

$\|\widehat{\mathbf{P}}_{n}-\mathbf{P}\|_{op}\leq\begin{cases}\frac{4\beta\left(3\sqrt{n\ell_{\delta/2\mathcal{N}}(n)}+5\ell_{\delta/2\mathcal{N}}(n)\right)+4n\gamma}{(\sigma_{r}(\mathbf{Z}_{n})-\sigma_{r+1}(\mathbf{Z}_{n}))^{2}}\quad\text{when
Assumption~{}\ref{ass:noise1} holds}\\\
\frac{6\sqrt{nCd\gamma\ell_{\delta}(n)}+\frac{14}{3}Cd\ell_{\delta}(n)+2n\gamma}{(\sigma_{r}(\mathbf{Z}_{n})-\sigma_{r+1}(\mathbf{Z}_{n}))^{2}}\quad\text{when
Assumption~{}\ref{ass:noise2} holds}.\par\end{cases}$

What remains is to provide a concentration inequality bounding the deviations
between the singular values of the noisy covariate matrix $\mathbf{Z}_{n}$ and
the true, low rank covariate matrix $\mathbf{X}_{n}$. We have the following
inequality.

######  Lemma B.6.

Let $\delta\in(0,1)$ be arbitrary. Then with probability at least $1-\delta$
we have, simultaneously for all $i\in[r]$ and $n\geq 1$,

$\left|\sigma_{i}(\mathbf{Z}_{n})-\sigma_{i}(\mathbf{X}_{n})\right|^{2}\leq\begin{cases}\beta\left(3\sqrt{n\ell_{\delta/2\mathcal{N}}(n)}+5\ell_{\delta/2\mathcal{N}}(n)\right)+n\gamma\quad\text{when
Assumption~{}\ref{ass:noise1} holds}\\\
\frac{3}{2}\sqrt{nCd\gamma\ell_{\delta}(n)}+\frac{7}{3}Cd\ell_{\delta}(n)+n\gamma\quad\text{when
Assumption~{}\ref{ass:noise2} holds}.\par\end{cases}$

In addition, on the same probability at least $1-\delta$ event, for all $n\geq
1$ such that $\mathrm{snr}_{n}\geq 2$, we have

$\frac{\sigma_{r}(\mathbf{X}_{n})}{2}\leq\sigma_{r}(\mathbf{Z}_{n})\leq\frac{3\sigma_{r}(\mathbf{X}_{n})}{2}.$

Note that the same holds if $\mathrm{snr}_{n}$ is replaced with the action-
specific signal to noise ratio $\mathrm{snr}_{n}(a)$.

###### Proof.

By Lemma B.1, we know that for any $i\in[r]$,

$\left|\sigma_{i}(\mathbf{Z}_{n})-\sigma_{i}(\mathbf{X}_{n})\right|\leq\left\|\mathbf{Z}_{n}-\mathbf{X}_{n}\right\|_{op}=\left\|\mathcal{E}_{n}\right\|_{op}.$

Thus, applying Lemma B.3 yields the first part of the theorem.

Now, suppose $\mathrm{snr}_{n}\geq 2$. Let $U_{n}^{2}$ denote either the first
or second line of the already-shown inequality (depending on whether
Assumption 3.1 or Assumption 3.2 holds). Then with probability at least
$1-\delta$,

$\displaystyle\sigma_{i}(\mathbf{Z}_{n})$
$\displaystyle\geq\sigma_{i}(\mathbf{X}_{n})-U_{n}$
$\displaystyle=\sigma_{i}(\mathbf{X}_{n})-\sigma_{i}(\mathbf{X}_{n})\frac{U_{n}}{\sigma_{i}(\mathbf{X}_{n})}$
$\displaystyle\geq\sigma_{i}(\mathbf{X}_{n})-\sigma_{i}(\mathbf{X}_{n})\frac{U_{n}}{\sigma_{r}(\mathbf{X}_{n})}$
$\displaystyle=\sigma_{i}(\mathbf{X}_{n})-\sigma_{i}(\mathbf{X}_{n})\frac{1}{\mathrm{snr}_{n}}$
$\displaystyle\geq\frac{\sigma_{i}(\mathbf{X}_{n})}{2}.$

∎

##  Appendix C Convergence results for regression in the true subspace

In this section, we construct confidence ellipsoids bounding the error between
$\widecheck{\theta}_{n}(a)$ and $\theta(a)$, where

$\widecheck{\theta}_{n}(a):=\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\mathbf{Y}_{n}(a),$

i.e. $\widecheck{\theta}_{n}(a)$ is the estimate of $\theta(a)$ given access
to the true, underlying subspace $W^{\ast}$. While the learner never has
direct access to $W^{\ast}$, the quantity $\widecheck{\theta}_{n}(a)$ proves
useful in bounding $\|\widehat{\theta}_{n}(a)-\theta(a)\|_{2}^{2}$, the
$\ell_{2}$ error between the PCR estimate of $\theta(a)$ and $\theta(a)$
itself. In other words, the bounds proved in this section provide a
theoretical tool for understanding the convergence of PCR in adaptive
settings. The main lemma in this appendix is the following.

######  Lemma C.1 (Error bound in true subspace).

Let $\delta\in(0,1)$ be an arbitrary confidence parameter. Then, with
probability at least $1-2\delta$, simultaneously for all $a\in[A]$ and $n\geq
1$, we have

$\displaystyle\left\|\widecheck{\mathcal{V}}_{n}(a)^{1/2}\left(\widecheck{\theta}_{n}(a)-\theta(a)\right)\right\|_{2}^{2}\leq
4\rho
L^{2}+8\eta^{2}\left[\log\left(\frac{A}{\delta}\right)+r\log\left(1+\frac{\sigma_{1}(\mathbf{Z}_{n}(a))^{2}}{\rho}\right)\right]$
$\displaystyle+2L^{2}\begin{cases}\beta\left(3\sqrt{n\ell_{\delta/2\mathcal{N}}(n)}+5\ell_{\delta/2\mathcal{N}}(n)\right)+n\gamma\quad\text{when
Assumption~{}\ref{ass:noise1} holds}\\\
\frac{3}{2}\sqrt{nCd\gamma\ell_{\delta}(n)}+\frac{7}{3}Cd\ell_{\delta}(n)+n\gamma\quad\text{when
Assumption~{}\ref{ass:noise2} holds}.\end{cases}$

where $\beta$, $\ell_{\delta}$, and $\mathcal{N}$ are as defined in Lemma A.3
and A.4.

To make the proof of the above lemma more modular, we introduce several
lemmas. The first of these lemmas simply provides an alternative, easier-to-
bound representation of the difference (or error) vector
$\widecheck{\theta}_{n}(a)-\theta(a)$

######  Lemma C.2.

For any $n\in[N]$ and $a\in[A],$ we have

$\widecheck{\theta}_{n}(a)-\theta(a)=\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\Xi_{n}(a)+\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\widecheck{\mathcal{E}}_{n}(a)\theta(a)-\rho\widecheck{\mathcal{V}}_{n}(a)^{-1}\theta(a).$

###### Proof.

A straightforward computation yields

$\displaystyle\widecheck{\theta}_{n}(a)-\theta(a)$
$\displaystyle=\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\mathbf{Y}_{n}(a)-\theta(a)$
$\displaystyle=\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)(\mathbf{X}_{n}(a)\theta(a)+\Xi_{n}(a))-\theta(a)$
$\displaystyle=\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)\mathbf{X}_{n}(a)\theta(a)+\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\Xi_{n}(a)-\theta(a)$
$\displaystyle\qquad\pm\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)\widecheck{\mathcal{E}}_{n}(a)\theta(a)\pm\rho\widecheck{\mathcal{V}}_{n}(a)^{-1}\theta(a)$
$\displaystyle=\widecheck{\mathcal{V}}_{n}(a)^{-1}\left[\widecheck{\mathbf{Z}}_{n}(a)^{\top}(\mathbf{X}_{n}(a)+\widecheck{\mathcal{E}}_{n}(a))+\rho
I_{d}\right]\theta(a)+\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\Xi_{n}(a)-\theta(a)$
$\displaystyle\qquad-\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)\widecheck{\mathcal{E}}_{n}(a)\theta(a)-\rho\widecheck{\mathcal{V}}_{n}(a)^{-1}\theta(a)$
$\displaystyle=\widecheck{\mathcal{V}}_{n}(a)^{-1}\left[\widecheck{\mathbf{Z}}_{n}(a)^{\top}\widecheck{\mathbf{Z}}_{n}(a)+\rho
I_{d}\right]\theta(a)+\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\Xi_{n}(a)-\theta(a)$
$\displaystyle\qquad-\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)\widecheck{\mathcal{E}}_{n}(a)\theta(a)-\rho\widecheck{\mathcal{V}}_{n}(a)^{-1}\theta(a)$
$\displaystyle=\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\Xi_{n}(a)-\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\widecheck{\mathcal{E}}_{n}(a)\theta(a)-\rho\widecheck{\mathcal{V}}_{n}(a)^{-1}\theta(a),$

which proves the desired result. ∎

We leverage the following technical lemma in bounding the determinant of
$\widecheck{\mathcal{V}}_{n}(a)$, the projection of the covariance matrix
$\mathcal{V}_{n}(a)$ onto the true, unknown subspace $W^{\ast}$.

######  Lemma C.3 (Determinant-Trace Inequality).

Let $\mathbf{A}\in\mathbb{R}^{d\times d}$ be a positive-semidefinite matrix of
rank $r$. Then, for any $\rho>0$, we have

$\log\det(I_{d}+\rho^{-1}\mathcal{A})\leq
r\log\left(1+\frac{\sigma_{1}(\mathbf{A})}{\rho}\right).$

###### Proof.

We have

$\displaystyle\log\det(I_{d}+\rho^{-1}\mathbf{A})$
$\displaystyle=r\log\left[\det(I_{d}+\rho^{-1}\mathbf{A})^{1/r}\right]$
$\displaystyle=r\log\prod_{i=1}^{r}\left(1+\rho^{-1}\sigma_{i}(\mathbf{A})\right)^{1/r}$
$\displaystyle\leq
r\log\left(\sum_{i=1}^{r}\frac{1+\rho^{-1}\sigma_{i}(\mathbf{A})}{r}\right)$
$\displaystyle\leq r\log\left(1+\frac{\sigma_{1}(\mathbf{A})}{\rho}\right).$

∎

######  Lemma C.4.

Let $\mathbf{A}\in\mathbb{R}^{t\times d}$ be a matrix, and let $\rho>0$ be
arbitrary. Suppose $\mathbf{A}$ has $1\leq k\leq t\land d$ non-zero singular
values. Then,

$\left\|(\mathbf{A}^{T}\mathbf{A}+\rho
I_{d})^{-1/2}\mathbf{A}^{T}\right\|_{op}\leq\frac{\sigma_{k}(\mathbf{A})}{\sqrt{\sigma_{k}(\mathbf{A})^{2}+\rho}}\leq
1$

###### Proof.

Let us write the singular value decomposition of $\mathbf{A}$ as

$\mathbf{A}=\mathbf{U}\Sigma\mathbf{V}^{T}=\mathbf{U}_{k}\Sigma_{k}\mathbf{V}_{k}^{T},$

where the second equality follows from the fact that $\mathbf{A}$ has exactly
$k$ non-zero singular values. We have the equality

$\mathbf{A}^{T}\mathbf{A}+\rho I_{d}=\mathbf{V}(\Sigma_{k}^{2}+\rho
I_{k})\mathbf{V}^{T}.$

Thus, we see

$\displaystyle\left\|(\mathbf{A}^{T}\mathbf{A}+\rho
I_{d})^{-1/2}\mathbf{A}^{T}\right\|_{op}$
$\displaystyle=\left\|\mathbf{V}_{k}(\Sigma_{k}^{2}+\rho
I_{k})^{-1/2}\mathbf{V}_{k}^{T}\mathbf{V}_{k}\Sigma_{k}\mathbf{U}_{k}^{T}\right\|_{op}$
$\displaystyle=\left\|(\Sigma_{k}^{2}+\rho
I_{k})^{-1/2}\Sigma_{k}\right\|_{op}$
$\displaystyle=\max_{i=1}^{k}\frac{\sigma_{i}(\mathbf{A})}{\sqrt{\rho+\sigma_{i}(\mathbf{A})^{2}}}\leq\frac{\sigma_{k}(\mathbf{A})}{\sqrt{\rho+\sigma_{k}(\mathbf{A})^{2}}}.$

∎

With the aforementioned technical lemmas, alongside the time-uniform
martingale bounds presented in Appendix A and the singular value concentration
results proved in Appendix B, we can now prove Lemma C.1.

###### Proof of Lemma C.1.

First, by Lemma C.2, we see that we have, for any $a\in[A]$ and $n\geq 1$,

$\widecheck{\theta}_{n}(a)-\theta(a)=\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\Xi_{n}(a)+\widecheck{\mathcal{V}}_{n}(a)^{-1}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\widecheck{\mathcal{E}}_{n}(a)\theta(a)-\rho\widecheck{\mathcal{V}}_{n}(a)^{-1}\theta(a).$

With this decomposition in hand, we can apply the parallelogram inequality
($\|x-y\|^{2}_{2}+\|x+y\|^{2}_{2}\leq 2\|x\|_{2}^{2}+2\|y\|_{2}^{2}$) twice to
see that

$\displaystyle\left\|\widecheck{\mathcal{V}}_{n}(a)^{1/2}\left(\widecheck{\theta}_{n}(a)-\theta(a)\right)\right\|_{2}^{2}$
$\displaystyle\leq
4\left\|\widecheck{\mathcal{V}}_{t}(a)^{-1/2}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\Xi_{n}(a)\right\|_{2}^{2}+4\rho^{2}\left\|\widecheck{\mathcal{V}}_{n}(a)^{-1/2}\theta(a)\right\|_{2}^{2}+2\left\|\widecheck{\mathcal{V}}_{n}(a)^{-1/2}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\widecheck{\mathcal{E}}_{n}(a)\theta(a)\right\|_{2}^{2}$
$\displaystyle\leq
4\left\|\widecheck{\mathcal{V}}_{n}(a)^{-1/2}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\Xi_{n}(a)\right\|_{2}^{2}+4\rho
L^{2}+2\left\|\widecheck{\mathcal{V}}_{n}(a)^{-1/2}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\widecheck{\mathcal{E}}_{n}(a)\theta(a)\right\|_{2}^{2}.$

We bound the first and last terms separately. Applying Lemma A.1 for each
$a\in[A]$ and taking a union bound over actions yields that, with probability
at least $1-\delta$, simultaneously for all $n\geq 1$ and $a\in[A]$,

$\displaystyle\left\|\widecheck{\mathcal{V}}_{n}(a)^{-1/2}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\Xi_{n}(a)\right\|_{2}$
$\displaystyle\leq\eta\sqrt{2\log\left(\frac{A}{\delta}\sqrt{\det\left(\rho^{-1}\widecheck{\mathcal{V}}_{n}(a)\right)}\right)}$
$\displaystyle\leq\eta\sqrt{2\left[\log\left(\frac{A}{\delta}\right)+r\log\left(1+\frac{\sigma_{1}(\widecheck{\mathbf{Z}}_{n}(a))^{2}}{\rho}\right)\right]}$
$\displaystyle\leq\eta\sqrt{2\left[\log\left(\frac{A}{\delta}\right)+r\log\left(1+\frac{\sigma_{1}(\widehat{\mathbf{Z}}_{n}(a))^{2}}{\rho}\right)\right]},$

where the second inequality comes from applying Lemma C.3 and the third
inequality comes from the fact that
$\sigma_{i}(\widehat{\mathbf{Z}}_{n}(a))\geq\sigma_{i}(\widecheck{\mathbf{Z}}_{n}(a))$
for all $i\in[r]$.

Next, we bound the final term in the above expansion. Observe that

$\displaystyle\left\|\widecheck{\mathcal{V}}_{n}(a)^{-1/2}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\widecheck{\mathcal{E}}_{n}(a)\theta(a)\right\|_{2}$
$\displaystyle\leq\left\|\widecheck{\mathcal{V}}_{n}(a)^{-1/2}\widecheck{\mathbf{Z}}_{n}(a)^{\top}\right\|_{op}\left\|\widecheck{\mathcal{E}}_{n}(a)\right\|_{op}\left\|\theta(a)\right\|_{2}.$

First, note that $\|\theta(a)\|_{2}\leq L$ by assumption. Next, Lemma C.4
yields

$\left\|\widecheck{\mathcal{V}}_{n}(a)^{-1/2}\widecheck{Z}_{n}(a)^{\top}\right\|_{op}\leq
1.$

Lastly, note that by Lemma B.3, we have that, with probability at least
$1-\delta$, simultaneously for all $n\geq 1$

$\displaystyle\|\widecheck{\mathcal{E}}_{n}(a)\|_{op}^{2}$
$\displaystyle\leq\|\mathcal{E}_{n}\|^{2}$
$\displaystyle\leq\begin{cases}\beta\left(3\sqrt{n\ell_{\delta/2\mathcal{N}}(n)}+5\ell_{\delta/2\mathcal{N}}(n)\right)+n\gamma\quad\text{when
Assumption~{}\ref{ass:noise1} holds}\\\
\frac{3}{2}\sqrt{nCd\gamma\ell_{\delta}(n)}+\frac{7}{3}Cd\ell_{\delta}(n)+n\gamma\quad\text{when
Assumption~{}\ref{ass:noise2} holds}.\end{cases}$

This proves the desired inequality. ∎

##  Appendix D Technical lemmas for Theorem 4.4

In this appendix, we present several additional technical lemmas that are
needed for bounding terms in the main theorem.

######  Lemma D.1.

Assuming the setup of Theorem 4.4, we have, for all $n\geq 1$,

$\left\|\widehat{\mathbf{Z}}_{n}(a)\widehat{\theta}_{n}(a)-\mathbf{X}_{n}(a)\theta(a)\right\|_{2}^{2}\leq
8\left\|\widecheck{\mathcal{V}}_{n}(a)^{1/2}\left(\widecheck{\theta}_{n}(a)-\theta(a)\right)\right\|_{2}^{2}+6\left\|\Xi_{n}(a)\right\|_{2}^{2}+8\left\|\widehat{\mathbf{Z}}_{n}(a)\theta(a)-\mathbf{X}_{n}(a)\theta(a)\right\|_{2}^{2}$

###### Proof.

A relatively straightforward computation yields

$\displaystyle\left\|\widehat{\mathbf{Z}}_{n}(a)\widehat{\theta}_{n}(a)-\mathbf{X}_{t}(a)\theta(a)\right\|_{2}^{2}$
$\displaystyle=\left\|\widehat{\mathbf{Z}}_{n}(a)\widehat{\theta}_{n}(a)-\mathbf{X}_{n}(a)\theta(a)+\Xi_{n}(a)-\Xi_{n}(a)\right\|_{2}^{2}$
$\displaystyle\leq
2\left\|\widehat{\mathbf{Z}}_{n}(a)\widehat{\theta}_{n}(a)-\mathbf{Y}_{n}(a)\right\|_{2}^{2}+2\left\|\Xi_{n}(a)\right\|_{2}^{2}$
$\displaystyle\leq
2\left\|\widehat{\mathbf{Z}}_{n}(a)\widecheck{\theta}_{n}(a)-\mathbf{Y}_{n}(a)\right\|_{2}^{2}+2\left\|\Xi_{n}(a)\right\|_{2}^{2}$
$\displaystyle\leq
4\left\|\widehat{\mathbf{Z}}_{n}(a)\widecheck{\theta}_{n}(a)-\mathbf{X}_{n}(a)\theta(a)\right\|_{2}^{2}+6\left\|\Xi_{n}(a)\right\|^{2}_{2}$
$\displaystyle\leq
8\left\|\widehat{\mathbf{Z}}_{n}(a)\left(\widecheck{\theta}_{n}(a)-\theta(a)\right)\right\|_{2}^{2}+6\left\|\Xi_{n}(a)\right\|_{2}^{2}+8\left\|\widehat{\mathbf{Z}}_{n}(a)\theta(a)-\mathbf{X}_{n}(a)\theta(a)\right\|_{2}^{2}$
$\displaystyle=8\left\|\widehat{\mathbf{Z}}_{n}(a)\mathbf{P}\left(\widecheck{\theta}_{n}(a)-\theta(a)\right)\right\|_{2}^{2}+6\left\|\Xi_{n}(a)\right\|_{2}^{2}+8\left\|\widehat{\mathbf{Z}}_{n}(a)\theta(a)-\mathbf{X}_{n}(a)\theta(a)\right\|_{2}^{2}$
$\displaystyle\leq
8\left\|\widecheck{\mathbf{Z}}_{n}(a)\left(\widecheck{\theta}_{n}(a)-\theta(a)\right)\right\|_{2}^{2}+6\left\|\Xi_{n}(a)\right\|_{2}^{2}+8\left\|\widehat{\mathbf{Z}}_{n}(a)\theta(a)-\mathbf{X}_{n}(a)\theta(a)\right\|_{2}^{2}$
$\displaystyle\leq
8\left\|\widecheck{\mathcal{V}}_{n}(a)^{1/2}\left(\widecheck{\theta}_{n}(a)-\theta(a)\right)\right\|_{2}^{2}+6\left\|\Xi_{n}(a)\right\|_{2}^{2}+8\left\|\widehat{\mathbf{Z}}_{n}(a)\theta(a)-\mathbf{X}_{n}(a)\theta(a)\right\|_{2}^{2}$

where we apply the the parallelogram inequality to obtain the first and third
inequalities. The second inequality follows from the characterization of ridge
regression in Fact F.2 and the fact $\rho$ is chosen sufficiently small. ∎

######  Lemma D.2.

Assuming the setup of Theorem 4.4, we have, for all $n\geq 1$,

$\left\|\mathbf{X}_{n}(a)\theta(a)-\widehat{\mathbf{Z}}_{n}(a)\theta(a)\right\|_{2}^{2}\leq
2L^{2}\sigma_{1}(\mathbf{Z}_{n}(a))^{2}\left\|\mathbf{P}-\widehat{\mathbf{P}}_{n}(a)\right\|_{op}^{2}+2L^{2}\left\|\mathcal{E}_{n}\right\|_{op}^{2}$

###### Proof.

A relatively simple computation yields

$\displaystyle\left\|\mathbf{X}_{n}(a)\theta(a)-\widehat{\mathbf{Z}}_{n}(a)\theta(a)\right\|_{2}^{2}$
$\displaystyle=\left\|\mathbf{X}_{n}(a)\theta(a)-\widecheck{\mathbf{Z}}_{n}(a)\theta(a)+\widecheck{\mathbf{Z}}_{n}(a)\theta(a)-\widehat{\mathbf{Z}}_{n}(a)\theta(a)\right\|_{2}^{2}$
$\displaystyle\leq
2\left\|\widecheck{\mathbf{Z}}_{n}(a)\theta(a)-\widehat{\mathbf{Z}}_{n}(a)\theta(a)\right\|_{2}^{2}+2\left\|\widecheck{\mathbf{Z}}_{n}(a)\theta(a)-\mathbf{X}_{n}(a)\theta(a)\right\|_{2}^{2}$
$\displaystyle=2\left\|\widecheck{\mathbf{Z}}_{n}(a)\theta(a)-\widehat{\mathbf{Z}}_{n}(a)\theta(a)\right\|_{2}^{2}+2\left\|\widecheck{\mathcal{E}}_{n}(a)\theta(a)\right\|_{2}^{2}$
$\displaystyle=2\left\|\mathbf{Z}_{n}(a)(\mathbf{P}-\widehat{\mathbf{P}}_{n}(a))\theta(a)\right\|_{2}^{2}+2\left\|\widecheck{\mathcal{E}}_{n}(a)\theta(a)\right\|_{2}^{2}$
$\displaystyle\leq
2L^{2}\sigma_{1}(\mathbf{Z}_{n}(a))^{2}\left\|\mathbf{P}-\widehat{\mathbf{P}}_{n}(a)\right\|_{op}^{2}+2L^{2}\left\|\widecheck{\mathcal{E}}_{n}\right\|_{op}^{2},$

where we have applied the parallelogram inequality to obtain the first
inequality. ∎

######  Lemma D.3.

Suppose $(\xi_{n})_{n\geq 1}$ is a sequence of independent, $\eta$-subGaussian
random variables. Then, for any $\delta\in(0,1)$, we have simultaneously for
all $n\geq 1$

$\|\Xi_{n}\|_{2}^{2}\leq
6\eta^{2}\sqrt{2n\ell_{\delta}(n)}+10\eta^{2}\ell_{\delta}(n)+n\alpha,$

where we recall $\Xi_{n}:=(\xi_{1},\dots,\xi_{n})^{\top}$.

###### Proof.

First, observe that by the appendix of Honorio and Jaakkola [49], since
$\xi_{n}$ is $\eta$-subGaussian, $\xi_{n}^{2}-\mathbb{E}\xi_{n}^{2}$ is
$(4\sqrt{2}\eta^{2},4\eta^{2})$-subExponential, and thus by our discussion in
Appendix A $\xi_{n}^{2}-\mathbb{E}\xi_{n}^{2}$ is also
$(4\sqrt{2}\eta^{2},4\eta^{2})$-subGamma. Further, by Assumption 3.3, we have
$\sum_{m=1}^{n}\mathbb{E}\xi_{m}^{2}\leq n\alpha$. Recall that Lemma A.2
yields that, with probability at least $1-\delta$,

$\sum_{m=1}^{n}\xi_{m}^{2}-\mathbb{E}\xi_{m}^{2}\leq
6\eta^{2}\sqrt{2n\ell_{\delta}(n)}+10\eta^{2}\ell_{\delta}(n).$

Piecing everything together, we have that

$\displaystyle\|\Xi_{n}\|_{2}^{2}$ $\displaystyle=\sum_{m=1}^{n}\xi_{m}^{2}$
$\displaystyle=\sum_{m=1}\xi_{m}^{2}-\mathbb{E}\xi_{m}^{2}+\sum_{m=1}^{n}\mathbb{E}\xi_{m}^{2}$
$\displaystyle\leq
6\eta^{2}\sqrt{2n\ell_{\delta}(n)}+10\eta^{2}\ell_{\delta}(n)+n\alpha.$

∎

We now mention the finishing steps in proving Theorem 4.4, carrying over from
where the proof in the paper ended. We see, with the previously addressed
inequalities that, with probability at least $1-O(A\delta)$, simultaneously
for all $n\geq n_{0}$ and $a\in[A]$,

$\displaystyle\left\|\widehat{\theta}_{n}(a)-\theta(a)\right\|_{2}^{2}\leq\frac{6L^{2}U_{n}^{2}}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}+\frac{2}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}(T_{1}+T_{2})$
$\displaystyle=\frac{6L^{2}U_{n}^{2}}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}+\frac{2}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}\Bigg{[}32\rho
L^{2}+64\eta^{2}\left(\log\left(\frac{A}{\delta}\right)+r\log\left(1+\frac{\sigma_{1}(\mathbf{Z}_{n})^{2}}{\rho}\right)\right)$
$\displaystyle+16L^{2}U_{n}^{2}+6\eta^{2}\sqrt{2c_{n}(a)\ell_{\delta}(c_{n}(a))}+10\eta^{2}\ell_{\delta}(c_{n}(a))+6c_{n}(a)\alpha++\frac{108L^{2}\sigma_{1}(\mathbf{Z}_{n}(a))^{2}U_{n}^{2}}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}+18L^{2}U_{n}^{2}\Bigg{]}$
$\displaystyle=\frac{6L^{2}}{\widehat{\mathrm{snr}}_{n}(a)^{2}}+\frac{L^{2}}{\widehat{\mathrm{snr}}_{n}(a)^{2}}\left[68+\frac{216\sigma_{1}(\mathbf{Z}_{n}(a))^{2}}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}\right]+\frac{2}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}\Bigg{[}32\rho
L^{2}$
$\displaystyle\quad+64\eta^{2}\left(\log\left(\frac{A}{\delta}\right)+r\log\left(1+\frac{\sigma_{1}(\mathbf{Z}_{n}(a))^{2}}{\rho}\right)\right)+6\eta^{2}\sqrt{2c_{n}(a)\ell_{\delta}(c_{n}(a))}+10\eta^{2}\ell_{\delta}(c_{n}(a))+6c_{n}(a)\alpha\Bigg{]}$

##  Appendix E Proof of Theorem 4.1

In this section, we prove Theorem 4.1. All that is required in proving this
bound is simplifying the results of Theorem 4.4, given we allow ourselves
slack to control the bound up to universal constants and poly-logarithmic
factors.

###### Proof of Theorem 4.1.

Recall that by Theorem 4.4, we have with probability at least $1-O(A\delta)$,
simultaneously for all $n\geq n_{0}$

$\displaystyle\left\|\widehat{\theta}_{n}(a)-\theta(a)\right\|_{2}^{2}\leq\frac{L^{2}}{\widehat{\mathrm{snr}}_{n}(a)^{2}}\left[74+216\kappa(\mathbf{Z}_{n}(a))^{2}\right]+\frac{2\mathrm{err}_{n}(a)}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}.$

where in the above we define the “error” term $\mathrm{err}_{n}(a)$ to be

$\displaystyle\mathrm{err}_{n}(a)$ $\displaystyle:=\underbrace{24\rho
L^{2}+64\eta^{2}\left(\log\left(\frac{A}{\delta}\right)+r\log\left(1+\frac{\sigma_{1}(\mathbf{Z}_{n}(a))^{2}}{\rho}\right)\right)}_{T_{1}}$
$\displaystyle+\underbrace{6\eta^{2}\sqrt{2c_{n}(a)\ell_{\delta}(c_{n}(a))}+10\eta^{2}\ell_{\delta}(c_{n}(a))+6c_{n}(a)\alpha}_{T_{2}}.$

First, by the second part of Lemma B.6 coupled with the assumption that
$\mathrm{snr}_{n}(a)\geq 2$ for all $n\geq n_{0}$ and $a\in[A]$, we have that
$\mathrm{snr}_{n}(a)=\Theta(\widehat{\mathrm{snr}}_{n}(a))$. Further, by this
same result, we have that
$\kappa(\mathbf{Z}_{n}(a))=\Theta(\kappa(\mathbf{X}_{n}(a)))$. From this, it
is clear that
$\frac{L^{2}}{\widehat{\mathrm{snr}}_{n}(a)^{2}}\left[74+216\kappa(\mathbf{Z}_{n}(a))^{2}\right]=O\left(\frac{1}{\mathrm{snr}_{n}(a)^{2}}\kappa(\mathbf{X}_{n}(a))^{2}\right)$.
What remains is to show that
$\frac{2\mathrm{err}_{n}(a)}{\sigma_{r}(\widehat{\mathbf{Z}}_{n}(a))^{2}}=\widetilde{O}\left(\frac{1}{\mathrm{snr}_{n}(a)^{2}}\right)$.
To this end, it suffices to show that
$\mathrm{err}_{n}(a)=\widetilde{O}(n+d)$. But this is trivial, as it is clear
that $T_{1}=\widetilde{O}(1)$ and
$T_{2}=\widetilde{O}(c_{n}(a))=\widetilde{O}(n+d)$. Thus, we have proved the
desired result.

∎

##  Appendix F Equivalent formulations of ridge regression

We begin by discussing properties and equivalent formulations of ridge
regression, as the estimate produced by (regularized) PCR,
$\widehat{\theta}_{n}(a)$, is precisely the ridge estimate of the unknown
parameter $\theta(a)$ when restricted the subspace associated with the
projection matrix $\widehat{\mathbf{P}}_{n}$.

######  Fact F.1 (Ridge regression formulation).

Let $\widehat{W}_{n}$ be the subspace associated with the projection matrix
$\widehat{\mathbf{P}}_{n}$. Then, $\widehat{\theta}_{n}(a)$ satisfies

$\widehat{\theta}_{n}(a)=\arg\min_{\theta\in\widehat{W}_{n}}\left\\{\left\|\mathbf{Z}_{n}(a)\theta-\mathbf{Y}_{n}(a)\right\|_{2}^{2}+\frac{\rho}{2}\|\theta\|_{2}^{2}\right\\}.$

That is, $\widehat{\theta}_{n}(a)$ is the solution to $\rho$-regularized ridge
regression when estimates are restricted to $\widehat{W}_{n}$.

Ridge regression may also be represented in the following, constrained
optimization format.

######  Fact F.2 (Constrained formulation of ridge regression).

Let $\widehat{W}_{n}$ be the subspace associated with the projection matrix
$\widehat{\mathbf{P}}_{n}$. Then, $\widehat{\theta}_{n}(a)$ satisfies

$\widehat{\theta}_{n}(a)=\arg\min_{\theta\in\widehat{W}_{n}:\|\theta\|_{2}\leq
R_{\rho}}\left\|\mathbf{Z}_{n}(a)\theta-\mathbf{Y}_{n}(a)\right\|_{2}^{2},$

where $R_{\rho}$ is some constant only depending on $\rho$.

The larger $\rho$ is, the smaller $R_{\rho}$ must become. Since we know
$\|\theta(a)\|_{2}\leq L$, for all $a\in[A]$, throughout the main body and
appendix of this paper, we assume that $\rho$ is chosen to be sufficiently
small such that our estimates $\widehat{\theta}_{n}(a)$ satisfy
$\|\widehat{\theta}_{n}(a)\|_{2}\leq L$, i.e. we select $\rho>0$ satisfying
$R_{\rho}\leq L$.

##  Appendix G Proofs for application to panel data

######  Lemma G.1 (Reformulation of average expected post-intervention
outcome).

Under 5.1 and 5.2, the average expected post-intervention outcome of unit $n$
under intervention $a$ may be written as

$\mathbb{E}[\pv{\bar{Y}}{a}_{n,post}]=\frac{1}{T-T_{0}}\cdot\langle\theta(a),\mathbb{E}[Y_{n,pre}]\rangle,$

for some slope vector $\theta(a)\in\mathbb{R}^{T_{0}}$.

###### Proof.

Similar observations have been made in [45, 75]. For completeness, we include
the proof here as well. From 5.1 and Definition 5.3,

$\displaystyle\mathbb{E}[\pv{\bar{Y}}{a}_{n,post}]=\frac{1}{T-T_{0}}\cdot\left\langle\sum_{t=T_{0}+1}^{T}U_{t}^{(a)},V_{n}\right\rangle.$

Applying 5.2, we see that

$\displaystyle\mathbb{E}[\pv{\bar{Y}}{a}_{n,post}]=\frac{1}{T-T_{0}}\cdot\left\langle\sum_{t=1}^{T_{0}}\theta(a)_{t}\cdot
U_{t}^{(0)},V_{n}\right\rangle$

for some
$\theta(a)=[\theta_{1}(a),\ldots,\theta_{T_{0}}(a)]^{T}\in\mathbb{R}^{T_{0}}$.
∎

The following lemma follows straightforwardly from translating the notation of
Theorem 4.4 to the panel data setting. Note that in the panel data setting,
$d=T_{0}$, $\eta=\sigma\sqrt{T-T_{0}}$, and $\alpha=\sigma^{2}(T-T_{0})$.
Additionally, 3.1 is satisfied with $\gamma=\sigma^{2}$.

######  Lemma G.2.

Let $\delta\in(0,1)$ be an arbitrary confidence parameter. Let $\rho>0$ be
chosen to be sufficiently small, as detailed in Appendix F. Further, assume
that there is some $n_{0}\geq 1$ such that
$\mathrm{rank}(\mathbf{X}_{n_{0}})=r$ and $\mathrm{snr}_{n}\geq 2$ for all
$n\geq n_{0}$. Then, with probability at least $1-O(A\delta)$, simultaneously
for all actions $a\in[A]$ and time steps $n\geq n_{0}$, we have

$\displaystyle\left\|\widehat{\theta}_{n}(a)-\theta(a)\right\|_{2}^{2}\leq\frac{L^{2}}{\widehat{\mathrm{snr}}_{n}(a)^{2}}\left[74+216\kappa(\mathbf{Z}_{n}(a))^{2}\right]+\frac{2(T-T_{0})\mathrm{err}_{n}(a)}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}},$

where
$\kappa(\mathbf{Z}_{n}(a)):=\frac{\sigma_{1}(\mathbf{Z}_{n}(a))}{\sigma_{r}(\mathbf{Z}_{n}(a))}$,
$\|\theta(a)\|_{2}\leq L$, and in the above we define the “error” term
$\mathrm{err}_{n}(a)$ to be

$\displaystyle\mathrm{err}_{n}(a)$ $\displaystyle:=\frac{32\rho
L^{2}}{T-T_{0}}+64\sigma^{2}\left(\log\left(\frac{A}{\delta}\right)+r\log\left(1+\frac{\sigma_{1}(\mathbf{Z}_{n}(a))^{2}}{\rho}\right)\right)$
$\displaystyle+6\sigma^{2}\sqrt{2c_{n}(a)\ell_{\delta}(c_{n}(a))}+10\sigma^{2}\ell_{\delta}(c_{n}(a))+6\sigma^{2}c_{n}(a).$

######  Theorem G.3 (Prediction error of average expected post-intervention
outcome).

Let $\delta\in(0,1)$ be an arbitrary confidence parameter and $\rho>0$ be
chosen to be sufficiently small, as detailed in Appendix F. Further, assume
that Assumptions 5.1 and 5.2 are satisfied, there is some $n_{0}\geq 1$ such
that $\mathrm{rank}(\mathbf{X}_{n_{0}})=r$, and $\mathrm{snr}_{n}(a)\geq 2$
for all $n\geq n_{0}$. Then with probability at least $1-O(A\delta)$,
simultaneously for all interventions $a\in\\{0,\ldots,A-1\\}$

$\displaystyle|\widehat{\mathbb{E}}\pv{\bar{Y}}{a}_{n,post}-\mathbb{E}\pv{\bar{Y}}{a}_{n,post}|$
$\displaystyle\leq\frac{3\sqrt{T_{0}}}{\widehat{\mathrm{snr}}_{n}(a)}\left(\frac{L(\sqrt{74}+12\sqrt{6}\kappa(\mathbf{Z}_{n}(a)))}{(T-T_{0})\cdot\widehat{\mathrm{snr}}_{n}(a)}+\frac{\sqrt{2\mathrm{err}_{n}(a)}}{\sqrt{T-T_{0}}\cdot\sigma_{r}(\mathbf{Z}_{n}(a))}\right)$
$\displaystyle+\frac{2L\sqrt{24T_{0}}}{(T-T_{0})\cdot\widehat{\mathrm{snr}}_{n}(a)}+\frac{12L\kappa(\mathbf{Z}_{n}(a))\sqrt{3T_{0}}}{(T-T_{0})\cdot\widehat{\mathrm{snr}}_{n}(a)}+\frac{2\sqrt{\mathrm{err}_{n}(a)}}{\sqrt{T-T_{0}}\cdot\sigma_{r}(\mathbf{Z}_{n}(a))}$
$\displaystyle+\frac{L\sigma\sqrt{\log(A/\delta)}}{\sqrt{T-T_{0}}}+\frac{L\sigma\sqrt{74\log(A/\delta)}}{\widehat{\mathrm{snr}}_{n}(a)\sqrt{T-T_{0}}}+\frac{12\sigma\kappa(\mathbf{Z}_{n}(a))\sqrt{6\log(A/\delta)}}{\widehat{\mathrm{snr}}_{n}(a)\sqrt{T-T_{0}}}$
$\displaystyle+\frac{\sigma\sqrt{2\mathrm{err}_{n}(a)\log(A/\delta)}}{\sigma_{r}(\mathbf{Z}_{n}(a))},$

where
$\widehat{\mathbb{E}}\pv{\bar{Y}}{a}_{n,post}:=\frac{1}{T-T_{0}}\cdot\langle\widehat{\theta}_{n}(a),Y_{n,pre}\rangle$
is the estimated average post-intervention outcome for unit $n$ under
intervention $a$.

###### Proof.

$\displaystyle\widehat{\mathbb{E}}\pv{\bar{Y}}{a}_{n,post}-\mathbb{E}\pv{\bar{Y}}{a}_{n,post}$
$\displaystyle:=\frac{1}{T-T_{0}}(\langle\widehat{\theta}_{n}(a),Y_{n,pre}\rangle-\langle\theta(a),Y_{n,pre}\rangle)$
$\displaystyle=\frac{1}{T-T_{0}}(\underbrace{\langle\widehat{\theta}_{n}(a)-\theta(a),\mathbb{E}Y_{n,pre}\rangle}_{T_{1}}+\underbrace{\langle\theta(a),\epsilon_{n,pre}\rangle}_{T_{2}}$
$\displaystyle+\underbrace{\langle\widehat{\theta}_{n}(a)-\theta(a),\epsilon_{n,pre}\rangle}_{T_{3}})$

We begin by bounding $T_{1}$. By assumption we have that
$\mathbb{E}Y_{n,pre}\in\mathrm{span}(\mathbb{E}Y_{1,pre},\ldots,\mathbb{E}Y_{n-1,pre})$
for all $n\geq n_{0}$. Therefore,

$\displaystyle\langle\widehat{\theta}_{n}(a)-\theta(a),\mathbb{E}Y_{n,pre}\rangle$
$\displaystyle=\langle\widehat{\theta}_{n}(a)-\theta(a),\mathbb{E}Y_{n,pre}\mathbf{P}\rangle$
$\displaystyle=\langle\mathbf{P}\widehat{\theta}_{n}(a)-\theta(a),\mathbb{E}Y_{n,pre}\rangle$
$\displaystyle\leq\|\mathbb{E}Y_{n,pre}\|_{2}\|(\mathbf{P}-\widehat{\mathbf{P}}_{n}(a)+\widehat{\mathbf{P}}_{n}(a))(\widehat{\theta}_{n}(a)-\theta(a))\|_{2}$
$\displaystyle\leq\underbrace{\sqrt{T_{0}}\cdot\|(\mathbf{P}-\widehat{\mathbf{P}}_{n}(a))(\widehat{\theta}_{n}(a)-\theta(a))\|_{2}}_{T_{1.1}}+\underbrace{\sqrt{T_{0}}\cdot\|\widehat{\mathbf{P}}_{n}(a)(\widehat{\theta}_{n}(a)-\theta(a))\|_{2}}_{T_{1.2}}$

By Lemma B.4 and the second part of Lemma B.6, term $T_{1.1}$ may be upper-
bounded as

$\displaystyle T_{1.1}$
$\displaystyle\leq\sqrt{T_{0}}\cdot\|\mathbf{P}-\widehat{\mathbf{P}}_{n}(a)\|_{op}\cdot\|\widehat{\theta}_{n}(a)-\theta(a)\|_{2}$
$\displaystyle\leq\sqrt{T_{0}}\cdot\frac{\sqrt{4\beta\left(3\sqrt{n\ell_{\delta/2\mathcal{N}}(n)}+5\ell_{\delta/2\mathcal{N}}(n)\right)+4n\gamma}}{\sigma_{r}(\mathbf{X}_{n}(a))}\cdot\|\widehat{\theta}_{n}(a)-\theta(a)\|_{2}$
$\displaystyle\leq\sqrt{T_{0}}\cdot\frac{\sqrt{4\beta\left(3\sqrt{n\ell_{\delta/2\mathcal{N}}(n)}+5\ell_{\delta/2\mathcal{N}}(n)\right)+4n\gamma}}{\frac{2}{3}\sigma_{r}(\mathbf{Z}_{n}(a))}\cdot\|\widehat{\theta}_{n}(a)-\theta(a)\|_{2}$
$\displaystyle=\frac{3\sqrt{T_{0}}}{\widehat{\mathrm{snr}}_{n}(a)}\cdot\|\widehat{\theta}_{n}(a)-\theta(a)\|_{2}$

Applying Lemma G.2, we see that

$\displaystyle\frac{1}{T-T_{0}}T_{1.1}$
$\displaystyle\leq\frac{3\sqrt{T_{0}}}{(T-T_{0})\cdot\widehat{\mathrm{snr}}_{n}(a)}\left(\frac{L^{2}}{\widehat{\mathrm{snr}}_{n}(a)^{2}}\left[74+216\kappa(\mathbf{Z}_{n}(a))^{2}\right]+\frac{2(T-T_{0})\mathrm{err}_{n}(a)}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}\right)^{1/2}$
$\displaystyle\leq\frac{3\sqrt{T_{0}}}{(T-T_{0})\cdot\widehat{\mathrm{snr}}_{n}(a)}\left(\frac{L}{\widehat{\mathrm{snr}}_{n}(a)}\sqrt{74+216\kappa(\mathbf{Z}_{n}(a))^{2}}+\frac{\sqrt{2(T-T_{0})\mathrm{err}_{n}(a)}}{\sigma_{r}(\mathbf{Z}_{n}(a))}\right)$
$\displaystyle=\frac{3\sqrt{T_{0}}}{\widehat{\mathrm{snr}}_{n}(a)}\left(\frac{L(\sqrt{74}+12\sqrt{6}\kappa(\mathbf{Z}_{n}(a)))}{(T-T_{0})\cdot\widehat{\mathrm{snr}}_{n}(a)}+\frac{\sqrt{2\mathrm{err}_{n}(a)}}{\sqrt{T-T_{0}}\cdot\sigma_{r}(\mathbf{Z}_{n}(a))}\right).$

Turning our attention to $T_{1.2}$ and using a line of reasoning nearly
identical to equations (1), (2), (3) in the proof of Theorem 4.4, we get that
with probability at least $1-\mathcal{O}(A\delta)$,

$\displaystyle\frac{1}{T-T_{0}}T_{1,2}$
$\displaystyle\leq\frac{2\sqrt{T_{0}}}{(T-T_{0})\cdot\sigma_{r}(\mathbf{Z}_{n}(a))}\left(\left\|\widehat{\mathbf{Z}}_{n}(a)\widehat{\theta}_{n}(a)-\mathbf{X}_{n}(a)\theta(a)\right\|_{2}^{2}+\left\|\mathbf{X}_{n}(a)\theta(a)-\widehat{\mathbf{Z}}_{n}(a)\theta(a)\right\|_{2}^{2}\right)^{1/2}$
$\displaystyle\leq\frac{2\sqrt{T_{0}}}{(T-T_{0})\cdot\sigma_{r}(\mathbf{Z}_{n}(a))}\left(32\rho
L^{2}+64\sigma^{2}(T-T_{0})\left(\log\left(\frac{A}{\delta}\right)+r\log\left(1+\frac{\sigma_{1}(\mathbf{Z}_{n}(a))^{2}}{\rho}\right)\right)\right.$
$\displaystyle+\left.16L^{2}U_{n}^{2}+6\sigma^{2}(T-T_{0})\sqrt{2c_{n}(a)\ell_{\delta}(c_{n}(a))}+10\sigma^{2}(T-T_{0})\ell_{\delta}(c_{n}(a))\right.$
$\displaystyle+\left.6\sigma^{2}(T-T_{0})c_{n}(a)+\frac{108L^{2}\sigma_{1}(\mathbf{Z}_{n}(a))^{2}U_{n}^{2}}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}+18L^{2}U_{n}^{2}\right)^{1/2}$
$\displaystyle=\frac{2\sqrt{T_{0}}}{(T-T_{0})\cdot\sigma_{r}(\mathbf{Z}_{n}(a))}\left(34L^{2}U_{n}^{2}+\frac{108L^{2}\sigma_{1}(\mathbf{Z}_{n}(a))^{2}U_{n}^{2}}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}+(T-T_{0})\mathrm{err}_{n}(a)\right)^{1/2}$
$\displaystyle\leq\frac{2LU_{n}\sqrt{24T_{0}}}{(T-T_{0})\cdot\sigma_{r}(\mathbf{Z}_{n}(a))}+\frac{12L\kappa(\mathbf{Z}_{n}(a))U_{n}\sqrt{3T_{0}}}{(T-T_{0})\cdot\sigma_{r}(\mathbf{Z}_{n}(a))}+\frac{2\sqrt{\mathrm{err}_{n}(a)}}{\sqrt{T-T_{0}}\cdot\sigma_{r}(\mathbf{Z}_{n}(a))}$
$\displaystyle=\frac{2L\sqrt{24T_{0}}}{(T-T_{0})\cdot\widehat{\mathrm{snr}}_{n}(a)}+\frac{12L\kappa(\mathbf{Z}_{n}(a))\sqrt{3T_{0}}}{(T-T_{0})\cdot\widehat{\mathrm{snr}}_{n}(a)}+\frac{2\sqrt{\mathrm{err}_{n}(a)}}{\sqrt{T-T_{0}}\cdot\sigma_{r}(\mathbf{Z}_{n}(a))}$

Putting our bounds for $T_{1.1}$ and $T_{1.2}$ together, we get that

$\displaystyle\frac{\langle\widehat{\theta}_{n}(a)-\theta(a),\mathbb{E}Y_{n,pre}\rangle}{T-T_{0}}$
$\displaystyle\leq\frac{3\sqrt{T_{0}}}{\widehat{\mathrm{snr}}_{n}(a)}\left(\frac{L(\sqrt{74}+12\sqrt{6}\kappa(\mathbf{Z}_{n}(a)))}{(T-T_{0})\cdot\widehat{\mathrm{snr}}_{n}(a)}+\frac{\sqrt{2\mathrm{err}_{n}(a)}}{\sqrt{T-T_{0}}\cdot\sigma_{r}(\mathbf{Z}_{n}(a))}\right)$
$\displaystyle+\frac{2L\sqrt{24T_{0}}}{(T-T_{0})\cdot\widehat{\mathrm{snr}}_{n}(a)}+\frac{12L\kappa(\mathbf{Z}_{n}(a))\sqrt{3T_{0}}}{(T-T_{0})\cdot\widehat{\mathrm{snr}}_{n}(a)}+\frac{2\sqrt{\mathrm{err}_{n}(a)}}{\sqrt{T-T_{0}}\cdot\sigma_{r}(\mathbf{Z}_{n}(a))}$

Next we bound $T_{2}$. Note that $\langle\theta(a),\epsilon_{n,pre}\rangle$ is
a $\|\theta(a)\|_{2}\sqrt{T-T_{0}}\sigma$-subGaussian random variable.
Therefore via a Hoeffding bound, simultaneously for all actions $a\in[A]$,
with probability at least $1-\mathcal{O}(A\delta)$,

$\frac{\langle\theta(a),\epsilon_{n,pre}\rangle}{T-T_{0}}\leq
L\sigma\sqrt{\frac{\log(A/\delta)}{T-T_{0}}}$

Similarly for $T_{3}$,
$\langle\widehat{\theta}_{n}(a)-\theta(a),\epsilon_{n,pre}\rangle$ is a
$\|\widehat{\theta}_{n}(a)-\theta(a)\|_{2}\sqrt{T-T_{0}}\sigma$-subGaussian
random variable which, after applying a Hoeffding bound and our bound on
$\|\widehat{\theta}_{n}(a)-\theta(a)\|_{2}$, becomes

$\displaystyle\frac{\langle\widehat{\theta}_{n}(a)-\theta(a),\epsilon_{n,pre}\rangle}{T-T_{0}}$
$\displaystyle\leq\sigma\sqrt{\frac{\log(A/\delta)}{T-T_{0}}}\left(\frac{L^{2}}{\widehat{\mathrm{snr}}_{n}(a)^{2}}\left[74+216\kappa(\mathbf{Z}_{n}(a))^{2}\right]+\frac{2(T-T_{0})\mathrm{err}_{n}(a)}{\sigma_{r}(\mathbf{Z}_{n}(a))^{2}}\right)^{1/2}$
$\displaystyle\leq\sigma\sqrt{\frac{\log(A/\delta)}{T-T_{0}}}\left(\frac{\sqrt{74}L}{\widehat{\mathrm{snr}}_{n}(a)}+\frac{12\sqrt{6}\kappa(\mathbf{Z}_{n}(a))}{\widehat{\mathrm{snr}}_{n}(a)}+\frac{\sqrt{2(T-T_{0})\mathrm{err}_{n}(a)}}{\sigma_{r}(\mathbf{Z}_{n}(a))}\right)$
$\displaystyle=\frac{L\sigma\sqrt{74\log(A/\delta)}}{\widehat{\mathrm{snr}}_{n}(a)\sqrt{T-T_{0}}}+\frac{12\sigma\kappa(\mathbf{Z}_{n}(a))\sqrt{6\log(A/\delta)}}{\widehat{\mathrm{snr}}_{n}(a)\sqrt{T-T_{0}}}+\frac{\sigma\sqrt{2\mathrm{err}_{n}(a)\log(A/\delta)}}{\sigma_{r}(\mathbf{Z}_{n}(a))}$

Putting everything together, we see that with probability at least
$1-O(A\delta)$,

$\displaystyle|\widehat{\mathbb{E}}\pv{\bar{Y}}{a}_{n,post}-\mathbb{E}\pv{\bar{Y}}{a}_{n,post}|$
$\displaystyle\leq\frac{3\sqrt{T_{0}}}{\widehat{\mathrm{snr}}_{n}(a)}\left(\frac{L(\sqrt{74}+12\sqrt{6}\kappa(\mathbf{Z}_{n}(a)))}{(T-T_{0})\cdot\widehat{\mathrm{snr}}_{n}(a)}+\frac{\sqrt{2\mathrm{err}_{n}(a)}}{\sqrt{T-T_{0}}\cdot\sigma_{r}(\mathbf{Z}_{n}(a))}\right)$
$\displaystyle+\frac{2L\sqrt{24T_{0}}}{(T-T_{0})\cdot\widehat{\mathrm{snr}}_{n}(a)}+\frac{12L\kappa(\mathbf{Z}_{n}(a))\sqrt{3T_{0}}}{(T-T_{0})\cdot\widehat{\mathrm{snr}}_{n}(a)}+\frac{2\sqrt{\mathrm{err}_{n}(a)}}{\sqrt{T-T_{0}}\cdot\sigma_{r}(\mathbf{Z}_{n}(a))}$
$\displaystyle+\frac{L\sigma\sqrt{\log(A/\delta)}}{\sqrt{T-T_{0}}}+\frac{L\sigma\sqrt{74\log(A/\delta)}}{\widehat{\mathrm{snr}}_{n}(a)\sqrt{T-T_{0}}}+\frac{12\sigma\kappa(\mathbf{Z}_{n}(a))\sqrt{6\log(A/\delta)}}{\widehat{\mathrm{snr}}_{n}(a)\sqrt{T-T_{0}}}$
$\displaystyle+\frac{\sigma\sqrt{2\mathrm{err}_{n}(a)\log(A/\delta)}}{\sigma_{r}(\mathbf{Z}_{n}(a))}$

Applying 4.2, the expression simplifies to

$\displaystyle|\widehat{\mathbb{E}}\pv{\bar{Y}}{a}_{n,post}-\mathbb{E}\pv{\bar{Y}}{a}_{n,post}|$
$\displaystyle=\widetilde{O}\left(\frac{r\sqrt{T_{0}}}{\sqrt{T_{0}\wedge
n}}\left(\frac{Lr}{(T-T_{0})\sqrt{T_{0}\wedge
n}}+\frac{r}{\sqrt{(T-T_{0})(T_{0}\wedge n)}}\right)\right.$
$\displaystyle+\frac{Lr\sqrt{T_{0}}}{(T-T_{0})\sqrt{T_{0}\wedge
n}}+\frac{Lr\sqrt{T_{0}}}{(T-T_{0})\sqrt{T_{0}\wedge
n}}+\frac{r}{\sqrt{(T-T_{0})(T_{0}\wedge n)}}$
$\displaystyle+\frac{L}{\sqrt{T-T_{0}}}+\frac{Lr}{\sqrt{(T-T_{0})(T_{0}\wedge
n)}}+\frac{r}{\sqrt{(T-T_{0})(T_{0}\wedge
n)}}+\left.\frac{r}{\sqrt{T_{0}\wedge n}}\right).$

Under the assumptions that $T_{0}\leq\frac{1}{2}T$ and $r\leq\sqrt{T_{0}\wedge
n}$, we get that

$|\widehat{\mathbb{E}}\pv{\bar{Y}}{a}_{n,post}-\mathbb{E}\pv{\bar{Y}}{a}_{n,post}|=\widetilde{O}\left(\frac{L}{\sqrt{T-T_{0}}}+\frac{r}{\sqrt{T_{0}\wedge
n}}+\frac{r(L\vee 1)}{\sqrt{(T-T_{0})(T_{0}\wedge n)}}\right)$

∎