mathx”17

# Stochastic Online Instrumental Variable Regression:
Regrets for Endogeneity and Bandit Feedback

Riccardo Della Vecchia
Université de Lille, Inria, CNRS,
Centrale Lille, UMR 9189- CRIStAL, France
<EMAIL_ADDRESS>Debabrota Basu
Université de Lille, Inria, CNRS,
Centrale Lille, UMR 9189- CRIStAL, France
<EMAIL_ADDRESS>
###### Abstract

Endogeneity, i.e. the dependence between noise and covariates, is a common
phenomenon in real data due to omitted variables, strategic behaviours,
measurement errors etc. In contrast, the existing analyses of stochastic
online linear regression with unbounded noise and linear bandits depend
heavily on exogeneity, i.e. the independence between noise and covariates.
Motivated by this gap, we study the over- and just-identified Instrumental
Variable (IV) regression for stochastic online learning. IV regression and the
Two-Stage Least Squares approach to it are widely deployed in economics and
causal inference to identify the underlying model from an endogenous dataset.
Thus, we propose to use an online variant of Two-Stage Least Squares approach,
namely $\mathsf{O\text{2}SLS}$, to tackle endogeneity in stochastic online
learning. Our analysis shows that $\mathsf{O\text{2}SLS}$ achieves
$\text{O}(d_{\boldsymbol{x}}d_{\boldsymbol{z}}\log^{2}T)$ identification and
$\widetilde{\text{O}}(\gamma\sqrt{d_{\boldsymbol{z}}T})$ oracle regret after
$T$ interactions, where $d_{\boldsymbol{x}}$ and $d_{\boldsymbol{z}}$ are the
dimensions of covariates and IVs, and $\gamma$ is the bias due to endogeneity.
For $\gamma=0$, i.e. under exogeneity, $\mathsf{O\text{2}SLS}$ achieves
$\text{O}(d_{\boldsymbol{x}}^{2}\log^{2}T)$ oracle regret, which is of the
same order as that of the stochastic online ridge. Then, we leverage
$\mathsf{O\text{2}SLS}$ as an oracle to design $\mathsf{OFUL\text{-}IV}$, a
stochastic linear bandit algorithm that can tackle endogeneity and achieves
$\widetilde{\text{O}}(\sqrt{d_{\boldsymbol{x}}d_{\boldsymbol{z}}T})$ regret.
For different datasets with endogeneity, we experimentally show efficiencies
of $\mathsf{O\text{2}SLS}$ and $\mathsf{OFUL\text{-}IV}$ in terms of regrets.

###  1 Introduction

######  Example 1.1 (Learning price-consumption dynamics).

A market analyst wants to learn how price of a food item at a given day $t$
affects the sales of the item, given a daily stream of data of food prices and
sales. The further goal is to help any restaurant or food production company
to understand how setting price of a food item is going to increase the sales.
The analyst decides to run _online linear regression_ to learn the relation
$\mathrm{Price}\rightarrow\mathrm{Sales}$ (Fig. 1(a)). This is equivalent to
learning $\beta$ in the second-stage
$\mathrm{Sales}_{t}=\beta\times\mathrm{Price}_{t}+\eta_{t}$ (Figure 1(b)). The
analyst considers $\eta_{t}$ to be an i.i.d. sub-Gaussian noise due to
unintentional external factors. They are independent of the covariates in this
regression, i.e. $\mathrm{MaterialCost}$ and $\mathrm{Price}$. After running
the regression, she learns that increasing the price decreases sale of the
food item, i.e. $\beta=-1$.

Like this example, online regression is a founding component of online
learning (Kivinen et al.,, 2004), sequential testing (Kazerouni and Wein,,
2021), contextual bandits (Foster and Rakhlin,, 2020), and reinforcement
learning (Ouhamma et al.,, 2022). Especially, online linear regression is
widely used and analysed to design efficient algorithms with theoretical
guarantees (Greene,, 2003; Abbasi-Yadkori et al., 2011b, ; Hazan and Koren,,
2012). In linear regression, the outcome (or output variable)
$Y\in\mathbb{R}$, and the input features (or covariates, or treatments)
$\mathbf{X}\in\mathbb{R}^{d}$ are related by a structural equation:
$Y=\boldsymbol{\beta}^{T}\mathbf{X}+\eta$, where $\boldsymbol{\beta}$ is the
true parameter and $\eta$ is the observational noise with variance
$\sigma^{2}$. The goal is to estimate $\boldsymbol{\beta}$ from an
observational dataset. Two common assumptions in the analysis of linear
regression are (i) bounded observations and covariates (Vovk,, 1997; Bartlett
et al.,, 2015; Gaillard et al.,, 2019), and (ii) exogeneity, i.e. independence
of the noise $\eta$ and the input features $\mathbf{X}$
($\mathbb{E}[\eta|\mathbf{X}]=0$) (Abbasi-Yadkori et al., 2011b, ; Ouhamma et
al.,, 2021). Under exogeneity, researchers have studied scenarios where the
observational noise is unbounded and has only bounded variance $\sigma^{2}$.
But this setting asks for a different technical analysis than the bounded
adversarial setting popular in online regression literature. For example,
Ouhamma et al., (2021) analyse online forward regression and online ridge
regression in the unbounded stochastic setting.

######  Example 1.1 (Continued).

If a big festival happens in a city, a restaurant owner can increase price of
the food knowing still the sales will increase. This event contradicts the
analyst’s previously learnt parameter. Thus, as she incorporates the price-
sales data of this city, the estimated $\beta$ changes to $-0.5$. Because her
algorithm assumes exogeneity of noise and covariates, while in reality the
omitted variable $\mathrm{Event}_{t}$ affects both price and sales (Fig.
1(a)). Hence, the covariate $\mathrm{Price}_{t}$, gets correlated with the
noise, $\eta_{t}=\rho_{s}\mathrm{Event}_{t}+\eta_{S,t}$ (Fig. 1(b)). Here,
$\mathrm{Price}_{t}$ is called an endogeneous variable.

Similar to this example, in real-life, endogeneity, i.e. dependence between
noise and covariates ($\mathbb{E}[\eta|X]\neq 0$) (Greene,, 2003; Angrist et
al.,, 1996) is often observed due to omitted explanatory variables, strategic
behaviours during data generation, measurement errors, the dependence of the
output and the covariates on unobserved confounding variables etc. (Wald,,
1940; Mogstad et al.,, 2021; Zhu et al.,, 2022). Motivated by such scenarios,
we analyse online linear regression that aims to estimate $\boldsymbol{\beta}$
accurately from endogenous observational data, where the noise is stochastic
and unbounded.

(a) Graphical Model of Example 1.1

(b) Two-stages of IV Regression

(c) DAG of $\mathsf{\text{2}SLS}$ at $t$

Figure 1: Relations between IVs (green), Covariates (blue), and Outcome (blue)
in Example 1.1 and in general for Online Two-stage Regression. Unobserved
noises and variables are in dotted circles. Observed quantities are in solid
circles.

Instrumental Variable (IV) regression. Historically, IVs are introduced to
identify and quantify the causal effects of endogenous covariates (Newey and
Powell,, 2003). IVs are widely used in economics (Wright,, 1928; Mogstad et
al.,, 2021), causal inference (Rubin,, 1974; Hernan and Robins,, 2020; Harris
et al.,, 2022), bio-statistics and epidemiology (Burgess et al.,, 2017). One
popular framework is to choose IVs which heavily influence the covariates but
are independent of the exogeneous noise. Following that, one aims to learn the
relations between IVs and covariates in one-stage, and then uses the predicted
values of covariates to learn the relation between covariates and the outrcome
variables in the next-stage. This approach to conduct two stages of linear
regression using IVs is called Two Stage Least Squares Regression
($\mathsf{\text{2}SLS}$) (Angrist and Imbens,, 1995; Angrist et al.,, 1996).
$\mathsf{\text{2}SLS}$ has become the standard tool in economics, social
sciences, and statistics to study the effect of treatments on outcomes
involving endogeneity. Recently, in machine learning, researchers have
extended traditional $\mathsf{\text{2}SLS}$ to nonlinear structures, non-
compliant instruments, and corrupted observations using deep learning (Liu et
al.,, 2020; Xu et al.,, 2020, 2021), graphical models (Stirn and Jebara,,
2018), and kernel regression (Zhu et al.,, 2022).

######  Example 1.1 (Continued).

To rectify the error due to endogeneity, the analyst further studies the main
factors behind pricing and observes that $\mathrm{Price}_{t}$ depends on
material cost of the required components $\mathrm{MaterialCost}_{t}$. She also
observes that $\mathrm{MaterialCost}_{t}$ is independent of the omitted
variable $\mathrm{Event}_{t}$. To rectify the error due to endogeneity, the
analyst observes that $\mathrm{MaterialCost}_{t}$ is independent of the
omitted variable $\mathrm{Event}_{t}$. Thus, she chooses
$\mathrm{MaterialCost}_{t}$ to be an Instrumental Variable (IV). She runs an
online linear regression to learn the relation between $\mathrm{Price}_{t}$
and $\mathrm{MaterialCost}_{t}$. This is equivalent to learning $\theta$ in
the first-stage
$\mathrm{Price}_{t}=\theta\times\mathrm{MaterialCost}_{t}+\epsilon_{t}$, where
exogeneity is obeyed. She learns that an increase in material cost increases
the price, say $\theta=1$. Now, she uses the prices predicted at time $t$, by
the first-stage regressor, as the covariates in the second-stage, and use them
further the relation between price and sales in the second-stage. This leads
her to an estimate of the second-stage parameter $\beta$ as $-1.01$, which is
accurate even under endogeneity.

Thus, we are interested in studying the $\mathsf{\text{2}SLS}$ approach for
online learning. But the existing analyses of $\mathsf{\text{2}SLS}$ are
asymptotic, i.e. what can be learned if we have access to an infinite number
of samples in an offline setting (Singh et al.,, 2020; Liu et al.,, 2020;
Nareklishvili et al.,, 2022). In applications, this analysis is vacuous as one
has access to only finite samples. Additionally, in practice, it is natural to
acquire the data sequentially as treatments are chosen on-the-go and then to
learn the structural equation from the sequential data (Venkatraman et al.,,
2016). This setting motivates us to analyse the online extension of
$\mathsf{\text{2}SLS}$, named $\mathsf{O\text{2}SLS}$.

Additionally, as stated in Example 1.1, the goal of the analyst might be to
aid a restaurant owner or food supplier to strategically decide on a price of
the food item from a price range and also corresponding raw material cost
among multiple suppliers to improve the sales as much as possible. At this
point, the estimation of the first- and second-stage parameters aid in
sequential decision making leading to the maximisation of accumulated outcomes
over time. This is exactly a linear bandit problem. In this case, the analyst
only observes the outcome corresponding to the choice of price and material
cost. This is referred to as bandit feedback in online learning literature and
studied under the linear bandit formulation (Abbasi-Yadkori et al., 2011a, ).
This motivates us to extend $\mathsf{O\text{2}SLS}$ to linear bandits, where
both bandit feedback and endogeneity occur. In this paper, we investigate two
questions:

1\. What is the upper bound on the loss in performance for deploying
parameters estimated by $\mathsf{O\text{2}SLS}$ instead of the true parameters
$\boldsymbol{\beta}$? How does estimating the true parameters
$\boldsymbol{\beta}$ influence different performance metrics under
endogeneity?

2\. Can we design efficient algorithms for linear bandits with endogeneity by
using $\mathsf{O\text{2}SLS}$?

Our contributions. Our investigation has led to

1\. A non-asymptotic analysis of $\mathsf{O\text{2}SLS}$: First, we identify
three notions of regret: identification regret, oracle regret, and population
regret. Though all of them are of same order under endogeneity, we show that
the relations are more nuanced under endogeneity and unbounded noise. We focus
specifically on the identification regret, i.e. the sum of differences between
the estimated parameters $\\{\boldsymbol{\beta}_{t}\\}_{t=1}^{T}$, and the
true parameter $\boldsymbol{\beta}$, and oracle regret, i.e. the sum of
differences between the losses incurred by the estimated parameters
$\\{\boldsymbol{\beta}_{t}\\}_{t=1}^{T}$, and the true parameter
$\boldsymbol{\beta}$. In Section 3, we theoretically show that
$\mathsf{O\text{2}SLS}$ achieve
$\text{O}(d_{\boldsymbol{x}}d_{\boldsymbol{z}}\log^{2}T)$ identification
regret and
$\text{O}(d_{\boldsymbol{x}}d_{\boldsymbol{z}}\log^{2}T+\gamma\sqrt{d_{\boldsymbol{z}}T\log
T})$ oracle regret after receiving $T$ samples from the observational data.
Identification regret of $\mathsf{O\text{2}SLS}$ is $d_{\boldsymbol{z}}$
multiplicative factor higher than regret of online linear regression under
exogeneity, and oracle regret is $\text{O}(\gamma\sqrt{d_{\boldsymbol{z}}T\log
T})$ additive factor higher. These are the costs that $\mathsf{O\text{2}SLS}$
pay for tackling endogeneity in two stages. In our knowledge, we are the first
to propose a non-asymptotic regret analysis of $\mathsf{O\text{2}SLS}$ with
stochastic and unbounded noise. We also experimentally demonstrate efficiency
of $\mathsf{O\text{2}SLS}$ on synthetic and real-data with endoegeneity
(Section 5, Appendix D).

2\. $\mathsf{OFUL\text{-}IV}$ for linear bandits with endogeneity: In Section
4, we study the linear bandit problem with endogeneity. We design an extension
of OFUL algorithm used for linear bandit with exogeneity, namely
$\mathsf{OFUL\text{-}IV}$, to tackle this problem. $\mathsf{OFUL\text{-}IV}$
uses $\mathsf{O\text{2}SLS}$ to estimate the parameters, and corresponding
confidence bounds on $\boldsymbol{\beta}$ to balance exploration–exploitation.
We show that $\mathsf{OFUL\text{-}IV}$ achieve
$\text{O}(\sqrt{d_{\boldsymbol{x}}d_{\boldsymbol{z}}T}\log T)$ regret after
$T$ interactions. We further experimentally validate that
$\mathsf{OFUL\text{-}IV}$ incurs lower regret under endeogeneity than
$\mathsf{OFUL}$ (Abbasi-Yadkori et al., 2011a, ) (Section 5, Appendix D).

Related work: Online regression without endogeneity. Our analysis of
$\mathsf{O\text{2}SLS}$ extends the tools and techniques of online linear
regression without endogeneity. Analysis of online linear regression began
with (Foster,, 1991; Littlestone et al.,, 1991). Vovk, (1997, 2001) show that
forward and ridge regressions achieve
$\text{O}(d_{\boldsymbol{x}}Y_{\max}^{2}\log T)$ for outcomes with bound
$Y_{\max}$. Bartlett et al., (2015) generalise the analysis further by
considering the features known in hindsight. Gaillard et al., (2019) improve
the analysis further to propose an optimal algorithm and a lower bound. These
works perform an adversarial analysis with bounded outcomes, covariates, and
observational noise, while we focus on the stochastic setting. Ouhamma et al.,
(2021) study the stochastic setting with bounded input features and unbounded
noise. But they need to assume independence of noise and input features. In
this paper, we analyse online $\mathsf{\text{2}SLS}$ under endogeneity and
unbounded (stochastic) noise. We do not assume to know the bound on the
outcome and derive high probability bounds for any bounded sequence of
features. Previously, Venkatraman et al., (2016) studied
$\mathsf{O\text{2}SLS}$ for system identification but provided only an
asymptotic analysis.

Related Work: Linear bandits without endogeneity. Linear bandits generalise
the setting of online linear regression under bandit feedback (Abbasi-Yadkori
et al., 2011a, ; Abbasi-Yadkori et al.,, 2012; Foster and Rakhlin,, 2020). To
be specific, in bandit feedback, the algorithm observes only the outcomes for
the input features that it has chosen to draw during an interaction. Popular
algorithm design techniques, such as optimism-in-the-face-of-uncertainty and
Thompson sampling, are extended to propose OFUL (Abbasi-Yadkori et al.,, 2012)
and LinTS (Abeille and Lazaric,, 2017), respectively. OFUL and LinTS
algorithms demonstrate $\text{O}(d\sqrt{T}\log T)$ and
$\text{O}(d^{1.5}\sqrt{T}\log T)$ regret under exogeneity assumption. Here, we
use $\mathsf{O\text{2}SLS}$ as a regression oracle to develop
$\mathsf{OFUL\text{-}IV}$ for linear bandits with endogeneity. We prove that
$\mathsf{OFUL\text{-}IV}$ achieves $\text{O}(d\sqrt{T}\log T)$ regret.

Related Work: Instrument-armed bandits. Kallus, (2018) is the first to study
endogeneity and instrumental variables in a stochastic bandit setting. Stirn
and Jebara, (2018) propose a Thompson sampling-type algorithm for stochastic
bandits, where endogeneity arises due to non-compliant actions. But both
Kallus, (2018) and Stirn and Jebara, (2018) study only the finite-armed bandit
setting where arms are independent of each other. In this paper, we study the
stochastic linear bandit setting with endogeneity, which requires different
techniques for analysis and algorithm design.

Notations: Matrices and vectors are denoted by bold capital and bold small
letters (e.g. $\mathbf{A}$ and $\mathbf{a}$). $\lVert\cdot\rVert_{p}$ is
$l_{p}$ norm of a vector. $\sigma_{\min}(\cdot)$ is minimum singular value and
$\vvvert\cdot\vvvert_{2}$ is operator norm of a matrix.

###  2 Preliminaries: Instrumental variables and offline two-stage least
squares

We are given an observational dataset
$\\{\boldsymbol{x}_{i},y_{i}\\}_{i=1}^{n}$ consisting of $n$ pairs of input
features and outcomes. Here, $y_{i}\in\mathbb{R}$ and
$\boldsymbol{x}_{i}\in\mathbb{R}^{d_{\boldsymbol{x}}}$. Inputs and outcomes
are stochastically generated using a linear model

$y_{i}=\boldsymbol{\beta}^{\top}\boldsymbol{x}_{i}+\eta_{i},$ (Second stage)

where $\boldsymbol{\beta}\in\mathbb{R}^{d_{\boldsymbol{x}}}$ is the unknown
true parameter vector of the linear model, and
$\eta_{i}\sim\mathcal{N}(0,\sigma_{\eta}^{2})$ is the unobserved error term
representing all causes of $y_{i}$ other than $\boldsymbol{x}_{i}$. It is
assumed that the error terms $\eta_{i}$ are independently and identically
distributed, and have bounded variance $\sigma_{\eta}^{2}$. The parameter
vector $\boldsymbol{\beta}$ quantifies the causal effect on $y_{i}$ due to a
unit change in a component of $\boldsymbol{x}_{i}$, while retaining other
causes of $y_{i}$ constant. The goal of linear regression is to estimate
$\boldsymbol{\beta}$ by minimising the square loss over the dataset (Brier,,
1950), i.e.
$\widehat{\boldsymbol{\beta}}\triangleq\operatorname*{argmin}_{\boldsymbol{\beta}^{\prime}}\sum_{i=1}^{n}(y_{i}-\boldsymbol{\beta}^{\prime\top}\boldsymbol{x}_{i})^{2}$.

The obtained solution is called the Ordinary Least Square (OLS) estimate of
$\boldsymbol{\beta}$ (Wasserman,, 2004), and used as a corner stone of online
regression (Gaillard et al.,, 2019) and linear bandit algorithms (Foster and
Rakhlin,, 2020). Specifically, if we define the input feature matrix to be
$\mathbf{X}_{n}\triangleq[\boldsymbol{x}_{1},\boldsymbol{x}_{2},\ldots,\boldsymbol{x}_{n}]^{\top}\in\mathbb{R}^{n\times
d_{\boldsymbol{x}}}$, the outcome vector to be
$\boldsymbol{y}_{n}\triangleq[y_{1},\ldots,y_{n}]^{\top}$, and the noise
vector is $\boldsymbol{\eta}_{n}\triangleq[\eta_{1},\ldots,\eta_{n}]^{\top}$,
the OLS estimator is

$\displaystyle{\widehat{\boldsymbol{\beta}}}_{\mathrm{OLS}}$
$\displaystyle\triangleq(\mathbf{X}_{n}^{\top}\mathbf{X}_{n})^{-1}\mathbf{X}_{n}^{\top}\boldsymbol{y}_{n}=\boldsymbol{\beta}+(\mathbf{X}_{n}^{\top}\mathbf{X}_{n})^{-1}\mathbf{X}_{n}^{\top}\boldsymbol{\eta}_{n}$

If $\boldsymbol{x}_{i}$ and $\eta_{i}$ are independent, i.e. under exogeneity,
the OLS estimator is unbiased:
$\mathbb{E}[\widehat{\boldsymbol{\beta}}_{\mathrm{OLS}}]=\boldsymbol{\beta}$.
Furthermore, it is also asymptotically consistent since
$\mathbf{X}_{n}^{\top}\boldsymbol{\eta}_{n}\overset{p}{\rightarrow}0$ implies
${\widehat{\boldsymbol{\beta}}}_{\mathrm{OLS}}\overset{p}{\rightarrow}\boldsymbol{\beta}$
(Greene,, 2003).

In practice, the input features $\boldsymbol{x}$ and the noise $\eta$ are
often correlated (Greene,, 2003, Chapter 8). As in Figure 1(c), this
dependence, called endogeneity, is modelled with a confounding unobserved
random variable $\boldsymbol{\epsilon}$. To compute an unbiased estimate of
$\boldsymbol{\beta}$ under endogeneity, the Instrumental Variables (IVs)
$\boldsymbol{z}$ are introduced (Angrist et al.,, 1996; Newey and Powell,,
2003). IVs are chosen such that they are highly correlated with endogenous
components of $\boldsymbol{x}$ (relevance condition) but are independent of
noise $\eta$ (exogeneity of $\boldsymbol{z}$). This leads to Two-stage Least
Squares ($\mathsf{\text{2}SLS}$) approach to IV regression (Angrist and
Imbens,, 1995; Angrist et al.,, 1996). We further assume that IVs,
$\mathbf{Z}_{n}\triangleq[\boldsymbol{z}_{1},\ldots,\boldsymbol{z}_{n}]^{\top}\in\mathbb{R}^{n\times
d_{\boldsymbol{z}}}$, cause linear effects on the endogenous covariates

$\mathbf{X}_{n}=\mathbf{Z}_{n}\boldsymbol{\Theta}+\mathbf{E}_{n}.$ (First
stage)

$\boldsymbol{\Theta}\in\mathbb{R}^{d_{\boldsymbol{z}}\times
d_{\boldsymbol{x}}}$ is the unknown first-stage parameter matrix and
$\mathbf{E}_{n}\triangleq[\boldsymbol{\epsilon}_{1},\ldots,\boldsymbol{\epsilon}_{n}]^{\top}\in\mathbb{R}^{n\times
d_{\boldsymbol{x}}}$ is the unobserved noise matrix leading to confounding in
the second stage. First-stage is a “classic” _multiple regression_ with
covariates $\boldsymbol{z}$ independent of the noise
$\boldsymbol{\epsilon}\sim\mathcal{N}(0,\sigma_{\boldsymbol{\epsilon}}^{2}\mathbf{I}_{d_{\boldsymbol{x}}})$
(Wasserman,, 2004, Ch. 13). Thus, OLS regression in first-stage yields an
estimate
$\widehat{\boldsymbol{\Theta}}_{n}\triangleq(\mathbf{Z}_{n}^{\top}\mathbf{Z}_{n})^{-1}\mathbf{Z}_{n}^{\top}\mathbf{X}_{n}$,
leading to the $\mathsf{\text{2}SLS}$ estimator:

$\widehat{\boldsymbol{\beta}}_{\mathrm{2SLS}}\triangleq\left(\widehat{\boldsymbol{\Theta}}^{\top}_{n}\mathbf{Z}_{n}^{\top}\mathbf{Z}_{n}\widehat{\boldsymbol{\Theta}}_{n}\right)^{-1}\widehat{\boldsymbol{\Theta}}^{\top}_{n}\mathbf{Z}_{n}^{\top}\boldsymbol{y}_{n}=\left(\widehat{\mathbf{X}}_{n}^{\top}\widehat{\mathbf{X}}_{n}\right)^{-1}\widehat{\mathbf{X}}_{n}^{\top}\boldsymbol{y}_{n}.$
(2SLS)

Here, $\widehat{\mathbf{X}}_{n}$ is the predicted covariate from first-stage.
Given $\mathbb{E}[\boldsymbol{z}_{i}\eta_{i}]=0$ in the true model, we observe
that
$\widehat{\boldsymbol{\beta}}_{\mathrm{2SLS}}=\left(\widehat{\mathbf{X}}_{n}^{\top}\widehat{\mathbf{X}}_{n}\right)^{-1}\widehat{\mathbf{X}}_{n}^{\top}\mathbf{X}_{n}\boldsymbol{\beta}+\left(\widehat{\mathbf{X}}_{n}^{\top}\widehat{\mathbf{X}}_{n}\right)^{-1}\widehat{\mathbf{X}}_{n}^{\top}\boldsymbol{\eta}_{n}\overset{p}{\rightarrow}\boldsymbol{\beta},$
as $n\to\infty$. Since $\boldsymbol{x}$ and $\boldsymbol{\eta}$ are
correlated, $\mathsf{\text{2}SLS}$ estimator is not unbiased in finite-time.
When $d_{\boldsymbol{x}}=d_{\boldsymbol{z}}$, we call $\boldsymbol{z}$ just-
identified IVs. When $d_{\boldsymbol{x}}<d_{\boldsymbol{z}}$, we call
$\boldsymbol{z}$ over-identified IVs. In this paper, we analyse both of the
conditions.

######  Assumption 2.1.

The assumptions for conducting $\mathsf{\text{2}SLS}$ are (Greene,, 2003):

  1. 1.

Endogeneity of $\boldsymbol{x}$. The second stage input features
$\boldsymbol{x}$ and noise $\eta$ are not independent:
$\boldsymbol{x}\not\perp\\!\\!\\!\perp\eta$.

  2. 2.

Exogeneity of $\boldsymbol{z}$. IV random variables are independent of the
noise in the second stage: $\boldsymbol{z}\perp\\!\\!\\!\perp\eta$.

  3. 3.

Relevance Condition of IVs. For every $t\in\mathbb{N}$, the variables
$\boldsymbol{z}$ and $\boldsymbol{x}$ are correlated:
$\boldsymbol{z}\not\perp\\!\\!\\!\perp\boldsymbol{x}$, i.e.

$\sigma_{\min}\left(\mathrm{Cov}(\mathbf{Z}_{t},\mathbf{X}_{t})\right)=\sigma_{\min}\left(\frac{1}{t}\sum_{s=1}^{t}\boldsymbol{z}_{s}\boldsymbol{x}_{s}^{\top}\right)\geq{\mathfrak{r}}>0.$
(1)

###  3 $\mathsf{O\text{2}SLS}$: Online two-stage least squares regression

In this section, we describe the problem setting and schematic of Online Two-
Stage Least Squares Regression, in brief $\mathsf{O\text{2}SLS}$. Following
that, we first define two notions of regret: identification and oracle,
measuring accuracy of estimating the true parameter and the predicted
outcomes, respectively. We provide a theoretical analysis of
$\mathsf{O\text{2}SLS}$ and upper bound the two types of regret (Section 3.2).
$\mathsf{O\text{2}SLS}$. In the online setting of IV regression, the data
$(\boldsymbol{x}_{1},\boldsymbol{z}_{1},y_{1}),\ldots,(\boldsymbol{x}_{t},\boldsymbol{z}_{t},y_{t}),\ldots$
arrives in a stream. Following the $\mathsf{\text{2}SLS}$ model (Figure 1(c)),
data is generated endogeneously

$\displaystyle\boldsymbol{x}_{t}=\boldsymbol{\Theta}^{\top}\boldsymbol{z}_{t}+\boldsymbol{\epsilon}_{t}$
$\displaystyle y_{t}=\boldsymbol{\beta}^{\top}\boldsymbol{x}_{t}+\eta_{t},$
(2)

such that $\boldsymbol{x}_{t}\not\perp\\!\\!\\!\perp\eta_{t}$ and
$\boldsymbol{z}_{t}\perp\\!\\!\\!\perp\eta_{t}$ for all $t\in\mathbb{N}$. At
each step $t$, the online IV regression algorithm is served with a new input
feature $\boldsymbol{x}_{t}$ and an IV $\boldsymbol{z}_{t}$. The algorithm
aims to yield an estimate of the parameter $\boldsymbol{\beta}_{t}$ and
predict an outcome
$\widehat{y}_{t}\triangleq\boldsymbol{\beta}_{t}^{\top}\boldsymbol{x}_{t}\in\mathbb{R}$
using the data $\\{(\boldsymbol{x}_{s},\boldsymbol{z}_{s},y_{s})\\}_{s=1}^{t}$
observed so far. Following the prediction, Nature reveals the true outcome
$y_{t}$.

In order to address endogeneity in this problem, we propose an online form of
the $\mathsf{\text{2}SLS}$ estimator. Modifying Equation (2SLS), we obtain the
$\mathsf{O\text{2}SLS}$ estimator that is computed for the prediction at time
$t$, using information up to time $t-1$:

$\displaystyle\boldsymbol{\beta}_{t-1}$
$\displaystyle\triangleq\left(\widehat{\mathbf{X}}_{t-1}^{\top}\widehat{\mathbf{X}}_{t-1}\right)^{-1}\widehat{\mathbf{X}}_{t-1}^{\top}\boldsymbol{y}_{t-1}=\left(\widehat{\boldsymbol{\Theta}}_{t-1}^{\top}\mathbf{Z}_{t-1}^{\top}\mathbf{Z}_{t-1}\widehat{\boldsymbol{\Theta}}_{t-1}\right)^{-1}\widehat{\boldsymbol{\Theta}}^{\top}_{t-1}\mathbf{Z}_{t-1}^{\top}\boldsymbol{y}_{t-1}$
($\mathsf{O\text{2}SLS}$)

Here,
$\widehat{\boldsymbol{\Theta}}_{t-1}\triangleq(\mathbf{Z}_{t-1}^{\top}\mathbf{Z}_{t-1})^{-1}\mathbf{Z}_{t-1}^{\top}\mathbf{X}_{t-1}$
is the estimate of the first-stage parameter (Appendix B). We use the
$\mathsf{O\text{2}SLS}$ estimator at step $t-1$ for the prediction
$\widehat{y}_{t}=\boldsymbol{\beta}_{t-1}^{\top}\boldsymbol{x}_{t}$, as in
Algorithm 1.

Algorithm 1 $\mathsf{O\text{2}SLS}$

1:Input: Initialisation parameters
$\boldsymbol{\beta}_{0},\widehat{\boldsymbol{\Theta}}_{0}$

2:for $t=1,2,\ldots,T$ do

3: Observe $\boldsymbol{z}_{t}$ generated i.i.d. by Nature, and
$\boldsymbol{x}_{t}$ sampled from Eq. (2) given $\boldsymbol{z}_{t}$

4: Compute first-stage and second-stage estimates
$\widehat{\boldsymbol{\Theta}}_{t-1}$ and $\boldsymbol{\beta}_{t-1}$ (Equation
$\mathsf{O\text{2}SLS}$)

5: Predict $\widehat{y}_{t}=\boldsymbol{\beta}_{t-1}^{\top}\boldsymbol{x}_{t}$

6: Observe $y_{t}$ generated by Nature

7:end for

Computational complexity. For a given $t$, Eq. (2SLS) yields
$\boldsymbol{\beta}_{t}=(\sum_{s=1}^{t}\widehat{\boldsymbol{x}}_{s}\widehat{\boldsymbol{x}}_{s}^{\top})^{-1}\,\sum_{s=1}^{t}\widehat{\boldsymbol{x}}_{s}y_{s}=\boldsymbol{\beta}_{t-1}-\mathbf{G}_{\widehat{\boldsymbol{x}},t}^{-1}\widehat{\boldsymbol{x}}_{t}\widehat{\boldsymbol{x}}_{t}^{\top}\boldsymbol{\beta}_{t-1}+\mathbf{G}_{\widehat{\boldsymbol{x}},t}^{-1}{\widehat{\boldsymbol{x}}}_{t}y_{t},$
where
$\mathbf{G}_{\widehat{\boldsymbol{x}},t}\triangleq\sum_{s=1}^{t}\widehat{\boldsymbol{x}}_{s}\widehat{\boldsymbol{x}}_{s}^{\top}=\mathbf{G}_{\widehat{\boldsymbol{x}},t-1}+\widehat{\boldsymbol{x}}_{t}\widehat{\boldsymbol{x}}_{t}^{\top}$.
We just need $\widehat{\boldsymbol{x}}_{t}$, $y_{t}$ for the iterative update
of $\boldsymbol{\beta}_{t}$ given the estimates at previous time
$\boldsymbol{\beta}_{t-1}$ and $\mathbf{G}_{\widehat{\boldsymbol{x}},t-1}$. We
can compute inverse of $\mathbf{G}_{\widehat{\boldsymbol{x}},t}$ using the
inverse of $\mathbf{G}_{\widehat{\boldsymbol{x}},t-1}$ in
$O(d_{\boldsymbol{x}}^{2})$ time using the Sherman–Morrison formula. We store
$\mathbf{G}_{\widehat{\boldsymbol{x}},t}^{-1}$ after each step, which requires
$O(d_{\boldsymbol{x}}^{2})$ memory. However, we made use of
$\widehat{\boldsymbol{x}}_{t}$, which can be derived from a similar iterative
update rule for $\widehat{\boldsymbol{\Theta}}_{t}$ from
$\widehat{\boldsymbol{\Theta}}_{t-1}$ by using $\boldsymbol{z}_{t}$,
$\boldsymbol{x}_{t}$, i.e.
$\widehat{\boldsymbol{\Theta}}_{t}=\widehat{\boldsymbol{\Theta}}_{t-1}-\mathbf{G}_{{\boldsymbol{z}},t}^{-1}\boldsymbol{z}_{t}\boldsymbol{z}_{t}^{\top}\widehat{\boldsymbol{\Theta}}_{t-1}+\mathbf{G}_{{\boldsymbol{z}},t}^{-1}{\boldsymbol{z}}_{t}\boldsymbol{x}_{t}^{\top}.$
This update has
$O(d_{\boldsymbol{z}}^{2}+d_{\boldsymbol{z}}d_{\boldsymbol{x}})$ time
complexity and requires $O(d_{\boldsymbol{z}}^{2})$ memory. Thus, overall,
$\mathsf{O\text{2}SLS}$ has quadratic space and time complexity.

######  Remark 3.1 (Proper online learning).

As in improper online learning algorithms, we could use $\boldsymbol{x}_{t}$
and $\boldsymbol{z}_{t}$ that we observe before committing to the estimate
$\boldsymbol{\beta}_{t}$, and use it to predict $\widehat{y}_{t}$ (Vovk,,
2001). Since we cannot use $y_{t}$ for this estimate, we have to modify
$\mathsf{\text{2}SLS}$ to incorporate this additional knowledge. We avoid this
modification, and follow a proper online learning approach to use
$\boldsymbol{\beta}_{t-1}$ to predict.

####  3.1 Characterising regrets for estimation and prediction: Identification
and oracle regrets

To analyse the online regression algorithms, it is essential to define proper
performance metrics, specifically regrets. Typically, regret quantifies what
an online (or sequential) algorithm cannot achieve as it does not have access
to the whole dataset rather observes it step by step. Here, we discuss and
define different regrets that we leverage in our analysis of
$\mathsf{O\text{2}SLS}$.

In econometrics and bio-statistics, where $\mathsf{\text{2}SLS}$ is popularly
used the focus is the accurate identification of the underlying structural
model $\boldsymbol{\beta}$. Identifying $\boldsymbol{\beta}$ leads to
understanding of the underlying economic or biological causal relations and
their dynamics. In ML, Venkatraman et al., (2016) applied
$\mathsf{O\text{2}SLS}$ for online linear system identification. Thus, given a
sequence of estimators $\\{\boldsymbol{\beta}_{t}\\}_{t=1}^{T}$ and a sequence
of covariates $\\{\boldsymbol{x}_{t}\\}_{t=1}^{T}$, the cost of identifying
the true parameter $\boldsymbol{\beta}$ can be quantified by

$\displaystyle\widetilde{R}_{T}(\boldsymbol{\beta})\triangleq\sum\nolimits_{t=1}^{T}(\boldsymbol{x}_{t}^{\top}\boldsymbol{\beta}_{t-1}-\boldsymbol{x}_{t}^{\top}\boldsymbol{\beta})^{2}.$
(3)

We refer to $\widetilde{R}_{T}(\boldsymbol{\beta})$ as identification regret
over horizon $T$. In the just identified setting that we are considering, the
identification regret is equivalent to the regret of counterfactual prediction
(Eqn. 5, Hartford et al., (2016)). Counterfactual predictions are important to
study the causal questions: what would have changed in the outcome if
Treatment $a$ had been used instead of treatment $b$? One of the modern
applications of IVs is to facilitate such counterfactual predictions (Hartford
et al.,, 2016; Bennett et al.,, 2019; Zhu et al.,, 2022).

Alternatively, one might be interested in evaluating and improving the quality
of prediction obtained using an estimator
$\\{\boldsymbol{\beta}_{t}\\}_{t=1}^{T}$ with respect to an underlying oracle
(or expert), which is typically the case in statistical learning theory and
forecasting (Foster,, 1991; Cesa-Bianchi and Lugosi,, 2006). If the oracle has
access to the true parameters $\boldsymbol{\beta}$, the cost in terms of
prediction that the estimators pay with respect to the oracle is
$\bar{r}_{t}\triangleq(y_{t}-\boldsymbol{x}_{t}^{\top}\boldsymbol{\beta}_{t-1})^{2}-(y_{t}-\boldsymbol{x}_{t}^{\top}\boldsymbol{\beta})^{2}$.
Thus, the regret in terms of the quality of prediction is defined as

$\displaystyle\overline{R}_{T}(\boldsymbol{\beta})\triangleq\sum\nolimits_{t=1}^{T}(y_{t}-\boldsymbol{x}_{t}^{\top}\boldsymbol{\beta}_{t-1})^{2}-\sum\nolimits_{t=1}^{T}(y_{t}-\boldsymbol{x}_{t}^{\top}\boldsymbol{\beta})^{2}.$
(4)

We refer to $\overline{R}_{T}(\boldsymbol{\beta})$ as the oracle regret. This
regret is studied for stochastic analysis of online regression (Ouhamma et
al.,, 2021) and is also useful for analysing bandit algorithms (Foster and
Rakhlin,, 2020).

As $\mathsf{O\text{2}SLS}$ is interesting for learning causal structures
(Hartford et al.,, 2016; Bennett et al.,, 2019), we focus on the
identification regret. On the other hand, to compare with the existing results
in online linear regression, we also analyse the oracle regret of
$\mathsf{O\text{2}SLS}$. Though we know that they are of similar order (w.r.t.
$T$) in the exogenous setting, we show that they differ significantly for
$\mathsf{O\text{2}SLS}$ under endogeneity (App. B).

######  Remark 3.2 (Hardness of exogeneity vs. endogeneity for prediction).

In online learning theory focused on Empirical Risk Minimisation (ERM),
another type of regret is considered where the oracle has access to the best
offline estimator
$\boldsymbol{\beta}_{T}\triangleq\operatorname*{argmin}_{\boldsymbol{\beta}}\sum_{t=1}^{T}(y_{t}-\boldsymbol{x}_{t}^{\top}\boldsymbol{\beta})^{2}$
given the observations over $T$ steps Cesa-Bianchi and Lugosi, (2006). Thus,
the new formulation of regret becomes
$R_{T}=\sum_{t=1}^{T}(y_{t}-\boldsymbol{x}_{t}^{\top}\boldsymbol{\beta}_{t-1})^{2}-\min_{\boldsymbol{\beta}}\sum_{t=1}^{T}(y_{t}-\boldsymbol{x}_{t}^{\top}\boldsymbol{\beta})^{2}.$
We refer to it as the population regret. Under exogeneity, Ouhamma et al.,
(2021) show that oracle regret and population regret differs by
$o(\log^{2}T)$. We show that under endogeneity, their expected values differ
by $\Omega(T)$. Thus, we avoid studying this notion of regret in this paper.
More details are in Appendix B.

####  3.2 Theoretical analysis

Confidence set. The central result in our analysis is concentration of
$\mathsf{O\text{2}SLS}$ estimates $\boldsymbol{\beta}_{t}$ around
$\boldsymbol{\beta}$.

######  Lemma 3.3 (Confidence ellipsoid for the second-stage parameters).

Let us define the _design matrix of IVs_ to be
$\mathbf{G}_{\boldsymbol{z},t}=\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}+\lambda\mathbf{I}_{d_{\boldsymbol{z}}}$
for some $\lambda>0$. Then, for some $\sigma_{\eta}$-sub-Gaussian first stage
noise $\eta_{t}$ and for all $t>0$, the true parameter $\boldsymbol{\beta}$
belongs to the confidence set

$\mathcal{E}_{t}\triangleq\left\\{\boldsymbol{\beta}\in\mathbb{R}^{d_{\boldsymbol{x}}}:\|\boldsymbol{\beta}_{t}-\boldsymbol{\beta}\|_{\widehat{\mathbf{H}}_{t}}\leq\sqrt{\mathfrak{b}_{t}(\delta)}\right\\},$
(5)

with probability at least $1-\delta\in(0,1)$. Here,
${\mathfrak{b}_{t}(\delta)}\triangleq\frac{d_{\boldsymbol{z}}\sigma_{\eta}^{2}}{4}{\log\left(\frac{1+tL^{2}_{z}/\lambda{d_{\boldsymbol{z}}}}{\delta}\right)}$,
$\widehat{\mathbf{H}}_{t}\triangleq\widehat{\boldsymbol{\Theta}}_{t}^{\top}\mathbf{G}_{\boldsymbol{z},t}\widehat{\boldsymbol{\Theta}}_{t}$,
and $\widehat{\boldsymbol{\Theta}}_{t}$ is the estimate of the first-stage
parameter at time $t$.

Lemma 3.3 extends the well-known elliptical lemma for OLS and Ridge estimators
under exogeneity to the $\mathsf{O\text{2}SLS}$ estimator under endogeneity.
It shows that the size of the confidence intervals induced by
$\mathsf{O\text{2}SLS}$ estimate at time $T$ is
$\text{O}(\sqrt{d_{\boldsymbol{z}}\log T})$, which is of the same order as
that of the exogenous elliptical lemma but while applied on IVs (Abbasi-
Yadkori et al., 2011a, ).

Identification regret bound. Now, we state the identification regret upper
bound of $\mathsf{O\text{2}SLS}$.

######  Theorem 3.4 (Identification regret of $\mathsf{O\text{2}SLS}$).

If Assumption 2.1 holds true, then for bounded IVs
$\|\boldsymbol{z}\|_{2}^{2}\leq L_{z}^{2}$ and bounded first-stage parameters
$\vvvert\boldsymbol{\Theta}\vvvert_{2}\leq L_{\boldsymbol{\Theta}}^{2}$, the
$\sigma_{\eta}$-sub-Gaussian second stage noise $\eta_{t}$ and the component-
wise $\sigma_{\boldsymbol{\epsilon}}$-sub-Gaussian first stage noise
$\boldsymbol{\epsilon}_{t}$, the regret of $\mathsf{O\text{2}SLS}$ satisfies
with probability at least $1-\delta$

$\displaystyle\centering\widetilde{R}_{T}\@add@centering$
$\displaystyle\leq\sum_{t=1}^{T}\underset{\text{Estimation}}{\underbrace{\|\boldsymbol{\beta}_{t}-\boldsymbol{\beta}\|^{2}_{\widehat{\mathbf{H}}_{t}}}}\times\underset{\begin{subarray}{c}\text{Second-
stage}\\\ \text{feature
norm}\end{subarray}}{\underbrace{\lVert\boldsymbol{x}_{t}\rVert^{2}_{\widehat{\mathbf{H}}_{t}^{-1}}}}\leq\underset{\text{O}(d_{\boldsymbol{z}}\log
T)}{\underbrace{\mathfrak{b}_{T-1}(\delta)}}\times\underset{\text{O}(d_{\boldsymbol{x}}\log
T)}{\underbrace{\sum_{t=1}^{T}\lVert\boldsymbol{x}_{t}\rVert^{2}_{\widehat{\mathbf{H}}_{t}^{-1}}}}=\text{O}\left(d_{\boldsymbol{x}}d_{\boldsymbol{z}}\log^{2}(T)\right).$

Theorem 3.4 entails a regret
$\widetilde{R}_{T}=\text{O}\left(d_{\boldsymbol{x}}d_{\boldsymbol{z}}\log^{2}(T)\right)$.
This regret bound is $d_{\boldsymbol{z}}\log T$ more than the regret of online
ridge regression, i.e. $\text{O}(d_{\boldsymbol{x}}\log T)$ (Gaillard et al.,,
2019). This is due to the fact that we perform $d_{\boldsymbol{x}}$ linear
regressions in the first-stage and use the predictions of the first-stage for
the second-stage regression. These two regression steps in cascade induce the
proposed regret bound.

Oracle regret bound. Now, we bound the oracle regret, i.e. the goodness of
predictions yielded by $\mathsf{O\text{2}SLS}$. Detailed proof is deferred to
Appendix B.

######  Theorem 3.5 (Oracle regret of $\mathsf{O\text{2}SLS}$).

Under the same hypothesis of Theorem 3.4, the Oracle Regret of
$\mathsf{O\text{2}SLS}$ at step $T>1$, i.e. $\overline{R}_{T}$ is upper
bounded by (ignoring $\log\log$ terms)

$\displaystyle\centering\underset{\begin{subarray}{c}\text{Identif.}\\\
\text{Regret}\\\
\text{O}(d_{\boldsymbol{x}}d_{\boldsymbol{z}}\log^{2}T)\end{subarray}}{\underbrace{\widetilde{R}_{T}}}+\underset{\begin{subarray}{c}\text{Estimation}\\\
\text{O}(\sqrt{d_{\boldsymbol{z}}\log
T})\end{subarray}}{\underbrace{\sqrt{\mathfrak{b}_{T-1}(\delta)}}}\underset{\begin{subarray}{c}\text{First-
stage}\\\ \text{feature norm}\\\ \text{O}(\sqrt{\log
T})\end{subarray}}{\left(\underbrace{C_{1}\sqrt{f(T)}}\right.}+\underbrace{C_{2}\sqrt{2d_{\boldsymbol{x}}f(T)}+\sqrt{d_{\boldsymbol{x}}}C_{3}}_{\begin{subarray}{c}\text{Correlated
noise}\\\ \text{Concentration term}\\\ \text{O}(\sqrt{d_{\boldsymbol{x}}\log
T})\end{subarray}}+\underset{\begin{subarray}{c}\text{Correlated noise}\\\
\text{Bias term}\\\
\text{O}(\gamma\sqrt{T})\end{subarray}}{\left.\underbrace{\gamma
C_{4}\sqrt{T}\operatorname{\lambda_{min}}\left(\boldsymbol{\Sigma}_{\boldsymbol{z}}\right)^{-1/2}}\right)}\@add@centering$

with probability at least $1-\delta\in(0,1)$. Here,
$\gamma\triangleq\|\boldsymbol{\gamma}\|_{2}=\|\mathbb{E}[\eta_{s}\boldsymbol{\epsilon}_{s}]\|_{2}$.
$C_{1}$, $C_{2}$, $C_{3}$, and $C_{4}$ are $d_{\boldsymbol{z}}$,
$d_{\boldsymbol{x}}$ and $T$-independent positive constants.
$\operatorname{\lambda_{min}}\left(\boldsymbol{\Sigma}_{\boldsymbol{z}}\right)$
is the minimum eigenvalue of IVs’ design matrix, and $f(T)=\text{O}(\log T)$
as defined in Corollary B.7.

Discussion. 1\. Hardness of endogeneity vs. exogeneity. Under exogeneity and
unbounded stochastic noise, the oracle regret of online linear regression is
$\text{O}(d^{2}\log^{2}T)$ (Ouhamma et al.,, 2021). If we take the just-
identified IVs, i.e. $d_{\boldsymbol{x}}=d_{\boldsymbol{z}}=d$, due to
endogeneity, $\mathsf{O\text{2}SLS}$ incurs an additive factor of
$\text{O}(\gamma\sqrt{d_{\boldsymbol{z}}T\log T})$ in the oracle regret. This
term appears due to the correlation between the second and the first-stage
noises, and it is proportional to the degree of correlation between the noises
in these two stages. Thus, the bias introduced by the correlation of noises
acts as the dominant term. In $\mathsf{\text{2}SLS}$ literature, this
phenomenon is called the self-fulfilling bias (Li et al.,, 2021). But we did
not find any explicit bound on it in a stochastic and non-asymptotic analysis.

2\. Tightness of analysis. In existing literature, we do not have any lower
bound for online regression with exogeneity. But we can indicate tightness of
the proposed analysis by observing two things. (i) Our identification regret
under endoegeneity is of the same order as that of exogeneous case (Abbasi-
Yadkori et al.,, 2012). (ii) If we assume $\gamma=0$, i.e. the noises are
independent, and we retrieve also the oracle regret of the same order as that
of the exogenous case (Ouhamma et al.,, 2021).

3\. Bounded vs. unbounded noise. For bounded noise and covariates, the
adversarial setting would subsume the endogeneous setting where the responses
are sampled according to dependent bounded noise since covariates and
responses are adversarially chosen sequences. If we consider the adversarial
linear regression for bounded responses $y_{t}\leq Y$ and covariates, the the
Vovk-Azoury-Warmuth Regressor (VAWR) achieves almost optimal
$\mathcal{O}(Y^{2}\log T)$ regret (Orabona,, 2019). Thus, the $\gamma\sqrt{T}$
term disappears as we obtain in our oracle regret bound with unbounded and
stochastic noise. This contrast indicates nontriviality of analysis for the
unbounded noise and unbounded outcomes that we study.

###  4 Linear bandits with endogeneity: $\mathsf{OFUL\text{-}IV}$

######  Example 1.1 (Pricing with price-consumption dynamics).

Let revisit the price-consumption dynamics. Now, on a day $t$, a restaurant
owner wants to decide on a price $x_{t}$ among a feasible set of prices
$\mathcal{X}_{t}$ to increase the sales $y_{t}$. The owner also has access to
a set of suppliers such that each price correspond to compatible a material
cost $z_{t}$. If the restaurant owner wants the analyst to develop an
algorithm to decide on the price dynamically such that the total sales over a
year is maximised, her problem is exactly a linear bandit with endoegeneity,
where a price corresponds to an arm (action).

We formulate stochastic Linear Bandits with Endogeneity (LBE) with a two-stage
linear model of data generation (Equation (2)). Here, we illustrate the
interactive protocol of LBE.

At each round $t=1,2,\ldots,T$, the agent 1. Observes a sample
$\boldsymbol{x}_{t,a}\in\mathcal{X}_{t}$ of contexts for all
$a\in\mathcal{A}_{t}$ 2. Chooses an arm $A_{t}\in\mathcal{A}_{t}$ 3. Observes
a sample $\boldsymbol{z}_{t,A_{t}}\in\mathcal{Z}_{t}$, and obtains a reward
$y_{t}$ 4. Updates the parameter estimates $\widehat{\boldsymbol{\Theta}}_{t}$
and $\boldsymbol{\beta}_{t}$

Here, $\mathcal{X}_{t}\subset\mathbb{R}^{d_{\boldsymbol{x}}}$ and
$\mathcal{Z}_{t}\subset\mathbb{R}^{d_{\boldsymbol{z}}}$ are the sets of IVs
and covariates corresponding to $\mathcal{A}_{t}$, i.e. the set of feasible
actions at time $t$. Similar to regression under endoegenity,
$\boldsymbol{\epsilon}_{t}\perp\\!\\!\\!\perp\boldsymbol{z}_{t}$ and
$\boldsymbol{\epsilon}_{t}\not\perp\\!\\!\\!\perp\eta_{t}$ (Eq. (2)). True
parameters $\boldsymbol{\beta}\in\mathbb{R}^{d_{\boldsymbol{x}}}$ and
$\boldsymbol{\Theta}\in\mathbb{R}^{d_{\boldsymbol{z}}\times
d_{\boldsymbol{x}}}$ are unknown to the agents. This is an extension of
stochastic linear bandit (Lattimore and Szepesvári,, 2020, Ch. 19) to the
endeogenous setting.

######  Remark 4.1 (Alternative protocol of LBE).

We can alternatively represent the protocol, where at every step $t$, the
agent observes covariates $\boldsymbol{x}_{t,a}$ and IVs
$\boldsymbol{z}_{t,a}$ for all the arms $a\in\mathcal{A}_{t}$. In that case,
the agent can use all this information to choose an arm $A_{t}$ and observes
the corresponding outcome $y_{t}$. But we do not require
$\boldsymbol{z}_{t,a}$ except $\boldsymbol{z}_{t,A_{t}}$ to update the
parameters and select the arms. Thus, this alternative can be reduced to the
protocol above, which requires less information to be known.

$\mathsf{OFUL\text{-}IV}$: Algorithm design. If the agent had full information
in hindsight, she could infer the best arm (a.k.a. action or intervention) in
$\mathcal{A}_{t}$ as
$a^{*}_{t}=\operatorname*{argmax}_{a\in\mathcal{A}_{t}}\mathbb{E}[\boldsymbol{x}_{t,a}^{\top}\boldsymbol{\beta}].$
Choosing $a_{t}^{*}$ is equivalent to choosing $\boldsymbol{z}_{t,a_{t}^{*}}$
and $\boldsymbol{x}_{t,a_{t}^{*}}$. But the agent does not know them and aims
to select $\\{a_{t}\\}_{t=1}^{T}$ to minimise regret:
$R_{T}\triangleq\mathbb{E}[\sum_{t=1}^{T}\boldsymbol{\beta}^{\top}(\boldsymbol{x}_{t,a_{t}^{*}}-\boldsymbol{x}_{t,a_{t}})]$.
Now, we extend the $\mathsf{OFUL}$ algorithm minimising regret in linear
bandits with exogeneity (Abbasi-Yadkori et al., 2011a, ). The core idea is
that the algorithm maintains a confidence set
$\mathcal{B}_{t-1}\subset\mathbb{R}^{d_{\boldsymbol{x}}}$ around the estimated
parameter $\boldsymbol{\beta}_{t-1}$, which is computed only using the
observed data. In order to tackle endogeneity, we choose to use the
$\mathsf{O\text{2}SLS}$ estimate $\boldsymbol{\beta}_{t-1}$ computed using
data observed till $t-1$. Then, we build an ellipsoid $\mathcal{B}_{t-1}$
around it, such that
$\mathcal{B}_{t-1}\triangleq\left\\{\boldsymbol{\beta}\in\mathbb{R}^{d_{\boldsymbol{x}}}:\|\boldsymbol{\beta}_{t}-\boldsymbol{\beta}\|_{\widehat{\mathbf{H}}_{t}}\leq\sqrt{\mathfrak{b}^{\prime}_{t}(\delta)}\right\\}$,
where $\mathfrak{b}^{\prime}_{t}(\delta)\triangleq
2\sigma_{\eta}^{2}\log\left(\nicefrac{{\operatorname{det}\left(\mathbf{G}_{\boldsymbol{z},t}\right)^{1/2}\lambda^{-d_{\boldsymbol{z}}/2}}}{{\delta}}\right).$
Then, the algorithm chooses an optimistic estimate
$\widetilde{\boldsymbol{\beta}}_{t-1}$ from that confidence set:
$\widetilde{\boldsymbol{\beta}}_{t-1}\triangleq\operatorname*{argmax}_{\boldsymbol{\beta}^{\prime}\in\mathcal{B}_{t-1}}\left(\max_{\boldsymbol{x}\in\mathcal{X}_{t}}\boldsymbol{x}^{\top}\boldsymbol{\beta}^{\prime}\right).$
Then, she chooses the action $A_{t}$ corresponding to
$\boldsymbol{x}_{t,A_{t}}=\operatorname*{argmax}_{\boldsymbol{x}\in\mathcal{X}_{t}}\boldsymbol{x}^{\top}\widetilde{\boldsymbol{\beta}}_{t}$,
which maximises the reward according to the estimate
$\widetilde{\boldsymbol{\beta}}_{t}$. In brief, the algorithm chooses the pair
$(\boldsymbol{x}_{t,A_{t}},\widetilde{\boldsymbol{\beta}}_{t-1})=\operatorname*{argmax}\nolimits_{{(\boldsymbol{x},\boldsymbol{\beta}^{\prime})\in\mathcal{X}_{t}\times\mathcal{B}_{t-1}}}\boldsymbol{x}^{\top}\boldsymbol{\beta}^{\prime}.$
Given this confidence interval, we optimistically choose

$\displaystyle
A_{t}=\operatorname*{argmax}_{a\in\mathcal{A}_{t}}\left\\{\left\langle\boldsymbol{x}_{t,a},\boldsymbol{\beta}_{t-1}\right\rangle+\sqrt{\mathfrak{b}^{\prime}_{t-1}(\delta)}\left\|\boldsymbol{x}_{t,a}\right\|_{\widehat{\mathbf{H}}_{t-1}^{-1}}\right\\}$
(6)

This arm selection index together with the $\mathsf{O\text{2}SLS}$ estimator
of $\boldsymbol{\beta}_{t-1}$ constitute $\mathsf{OFUL\text{-}IV}$ (Algo. 2).

Algorithm 2 $\mathsf{OFUL\text{-}IV}$

1:Input: Initialisation parameters
$\boldsymbol{\beta}_{0},\widehat{\boldsymbol{\Theta}}_{0},\mathfrak{b}^{\prime}_{0}$

2:for $t=1,2,\ldots,T$ do

3: Observe $\boldsymbol{x}_{t,a}\in\mathcal{X}_{t}$ for $a\in\mathcal{A}_{t}$

4: Compute $\boldsymbol{\beta}_{t-1}$ according to Equation
$\mathsf{O\text{2}SLS}$

5: Choose action $A_{t}$ that solves Equation 6

6: Observe $\boldsymbol{z}_{t,A_{t}}$ and $y_{t}$

7: Update
$\boldsymbol{\beta}_{t}\leftarrow\boldsymbol{\beta}_{t-1},\widehat{\boldsymbol{\Theta}}_{t}\leftarrow\widehat{\boldsymbol{\Theta}}_{t-1},\mathfrak{b}^{\prime}_{t}\leftarrow\mathfrak{b}^{\prime}_{t-1}$

8:end for

######  Theorem 4.2 (Regret upper bound of $\mathsf{OFUL\text{-}IV}$).

Under the same assumptions and notations of Theorem 3.4 and 3.5, with
probability $1-\delta$ and for horizon $T>1$, Algorithm 2 incurs regret

$\displaystyle R_{T}$ $\displaystyle\leq
2\sqrt{T}\underbrace{\sqrt{\mathfrak{b}_{T-1}(\delta)}}_{\begin{subarray}{c}\text{Estimation}~{}\text{O}(\sqrt{d_{\boldsymbol{z}}\log
T)}\end{subarray}}\underset{\begin{subarray}{c}\text{Second-stage feature
norm}~{}\text{O}(\sqrt{d_{\boldsymbol{x}}\log
T})\end{subarray}}{\underbrace{\left(\sum_{t=1}^{T}\lVert\boldsymbol{x}_{t,A_{t}}\rVert^{2}_{\widehat{H}_{t}^{-1}}\right)^{1/2}}}=\text{O}(\sqrt{d_{\boldsymbol{x}}d_{\boldsymbol{z}}T}\log
T)$

For just-identified IVs, i.e. $d_{\boldsymbol{x}}=d_{\boldsymbol{z}}=d$,
$\mathsf{OFUL\text{-}IV}$ achieves regret of similar order under endogeneity
as $\mathsf{OFUL}$ achieves under exogeneity, i.e.
$\widetilde{\text{O}}(d\sqrt{T})$. The proof details are deferred to Appendix
C.

1\. Incorporating unbounded outcomes. We do not require bounded outcomes,
$\boldsymbol{\beta}^{\top}\boldsymbol{x}\in[-1,1]$, as original OFUL (Abbasi-
Yadkori et al., 2011a, ). Similar to (Ouhamma et al.,, 2021), which removes
this assumption for exoegeneous setting, our analysis works for unbounded
outcomes reinstating that the bounded outcome assumption is not also needed
under endogeneity.
2\. Two-stage OFUL-IV vs. one-stage OFUL under endogeneity. An alternative
proposal than using a two-stage approach for LBE is to reduce it to a one-
level linear bandit, i.e.
$y_{t}=(\boldsymbol{\Theta}\boldsymbol{\beta})^{\top}\boldsymbol{z}_{t}+\boldsymbol{\beta}^{\top}\boldsymbol{\epsilon}_{t}+\eta_{t}$.
This leads to a composite unknown parameter
$\boldsymbol{\Theta}\boldsymbol{\beta}$, and a new sub-Gaussian noise with
component-wise variance
$\sigma_{new}^{2}=2(\|\boldsymbol{\beta}\|_{2}^{2}\sigma_{\boldsymbol{\epsilon}}^{2}+\sigma_{\eta}^{2})$.
Now, if we apply OFUL to this setup, we observe that the confidence bound
around the new hidden parameter $\boldsymbol{\Theta}\boldsymbol{\beta}$ is
proportional to $\sigma_{new}$. Thus, the confidence interval blows up by
$\|\boldsymbol{\beta}\|_{2}$. Also, using this interval in Equation (6)
requires us to know either $\|\boldsymbol{\beta}\|_{2}^{2}$ or a tight upper
bound on it. In real-life, we cannot assume access to such knowledge.
Additionally, $\|\boldsymbol{\beta}\|_{2}^{2}$ grows linearly with
$d_{\boldsymbol{x}}$. Thus, this approach can incur significantly higher
regret for high-dimensional covariates. In contrast, $\mathsf{OFUL\text{-}IV}$
does not require to know either $\|\boldsymbol{\beta}\|_{2}$ or any bound on
it. Additionally, the confidence interval of $\mathsf{OFUL\text{-}IV}$ depends
on $\sigma_{\eta}^{2}$, which is significantly smaller than
$\sigma_{new}^{2}$. These observations demonstrate the benefit of using
$\mathsf{OFUL\text{-}IV}$ under endogeneity than $\mathsf{OFUL}$ with a
single-stage reduction.

Figure 2: Regression: Identification regret after $T=10^{3}$ steps of Online
Ridge (left) and $\mathsf{O\text{2}SLS}$ (right), for different combination of
$\rho_{F}$ and $\rho_{S}$ in $[0,200]$. $\mathsf{O\text{2}SLS}$ attains lower
regret than $\mathsf{Ridge}$ for a wide range of parameters.

Figure 3: Regression: Identification regret of Online Ridge and
$\mathsf{O\text{2}SLS}$ over $T=10^{3}$ steps, and for
$\rho_{F}=\rho_{S}=5,10$. With increase in $\rho_{S}$, i.e. endoegenity,
$\mathsf{O\text{2}SLS}$ performs better.

Figure 4: LBE: Instantaneous regrets of $\mathsf{OFUL}$ and
$\mathsf{OFUL\text{-}IV}$ over $T=10^{3}$ steps. $\mathsf{OFUL\text{-}IV}$
incurs lower instantaneous regret.

###  5 Experimental analysis

Here, we present experimental results for both the regression and bandit
settings. We deploy the online regression and bandit experiments in Python3,
on an internal cluster of approximately 30 CPUs Intel(R) Xeon(R) CPU
<EMAIL_ADDRESS>in order to exploit code parallelisation. Further
experimental details and results are deferred to Appendix D. We denote the
normal distribution of $n$ dimensions with mean $\boldsymbol{\mu}$ and
standard deviation $\boldsymbol{\Sigma}$ as
$\mathcal{N}_{n}(\boldsymbol{\mu},\boldsymbol{\Sigma})$.

Regression experiments. In Figure 4, we compare the identification regrets
$\widetilde{R}_{T}$ of Online Ridge (left) and $\mathsf{O\text{2}SLS}$
(right), for $T=10^{3}$, and different combinations of $\rho_{F}$ and
$\rho_{S}$ in $[0,200]^{2}$. The data-generating process is the one detailed
in Figure 1(b), where $\text{Event}_{t}\sim\text{Bernoulli}(0.01)$,
$\text{MaterialCost}_{t}\sim\mathcal{N}_{1}(0,1)$,
$\epsilon_{F,t}\sim\mathcal{N}_{1}(5,1)$,
$\eta_{S,t}\sim\mathcal{N}_{1}(100,1)$, parameters $\theta=1$ and $\beta=-1$.
For each combination, we average the final regret $\widetilde{R}_{T}$ over 30
runs of the algorithms with different seeds. $\mathsf{O\text{2}SLS}$
outperforms $\mathsf{Ridge}$ in the whole parameter space under study. In
Figure 4, we plot the learning curves (mean$\pm$ standard deviation over 30
runs) for parameters $\rho_{S}=\rho_{F}=5$ and $10$. Higher
$(\rho_{S},\rho_{F})$ indicates higher endogeneity. $\mathsf{O\text{2}SLS}$
outperforms $\mathsf{Ridge}$, and the performance-gain increases with
increasing values of the two parameters, i.e. with increasing level of
endogeneity.

Bandit experiments. In Figure 4, we compare performance of
$\mathsf{OFUL\text{-}IV}$ and $\mathsf{OFUL}$ (Abbasi-Yadkori et al., 2011a, )
for LBE setting. $\mathsf{OFUL}$ builds a confidence ellipsoid centered at
$\boldsymbol{\beta}^{{\mathsf{Ridge}}}_{t}$, while $\mathsf{OFUL\text{-}IV}$
uses $\mathsf{O\text{2}SLS}$ to build an accurate estimate and an ellipsoid
that with high probability contains $\boldsymbol{\beta}$. For each algorithm,
we report the means and standard deviations of instantaneous regrets averaged
over 100 runs. For each experiment, we sample the true parameters in our model
once according to
$\boldsymbol{\beta}\sim\mathcal{N}_{50}(\vec{10},\mathbf{I}_{50})$ and
$\boldsymbol{\Theta}_{i,j}\sim\mathcal{N}_{1}(0,1)$ for each component. Then
we sample at each time $t$ the vectors
$\boldsymbol{z}_{t,a}{\sim}\mathcal{N}_{50}(\vec{0},\mathbf{I}_{50})$,
$\boldsymbol{\epsilon}_{t,a}{\sim}\mathcal{N}_{50}(\vec{0},\mathbf{I}_{50})$,
and the scalar noise
$\eta_{t,a}=\sqrt{0.1}(\widetilde{\eta}_{t,a}+\sum_{i=1}^{10}\boldsymbol{\epsilon}_{t,a,i})$
where $\widetilde{\eta}_{t,a}{\sim}\mathcal{N}_{1}(0,1)$. We run the
algorithms with the same regularisation parameters equal to $10^{-1}$. Thus,
$\mathsf{OFUL\text{-}IV}$ leads to lower regret than $\mathsf{OFUL}$ for
linear bandits with endogeneity (Figure 4).

###  6 Conclusions and future works

We study online IV regression, specifically the online $\mathsf{\text{2}SLS}$
algorithm, for unbounded noise and endogenous data. We analyse the finite-time
identification and oracle regrets of $\mathsf{O\text{2}SLS}$. We observe that
$\mathsf{O\text{2}SLS}$ incurs
$\text{O}(d_{\boldsymbol{x}}d_{\boldsymbol{z}}\log^{2}T)$ identification
regret, and $\text{O}(\gamma\sqrt{d_{\boldsymbol{z}}T\log T})$ oracle regret
as the correlation between the noises in the two-stages dominate the
identification regret. For just-identified case, identification regret are of
the same order for exogeneity and endogeneity. Following that, we propose
$\mathsf{OFUL\text{-}IV}$ for stochastic linear bandits with endogeneity that
uses $\mathsf{O\text{2}SLS}$ to estimate the model parameters. We show that
$\mathsf{OFUL\text{-}IV}$ achieves
$\text{O}(\sqrt{d_{\boldsymbol{x}}d_{\boldsymbol{z}}T}\log T)$ regret. We
experimentally show that $\mathsf{O\text{2}SLS}$ and $\mathsf{OFUL\text{-}IV}$
are more accurate than Ridge and $\mathsf{OFUL}$, respectively. In future, it
would be interesting to extend the stochastic analysis of online IV regression
and bandits with endogeneity to non-parametric (Newey and Powell,, 2003) and
non-linear settings (Xu et al.,, 2020).

### References

  * (1) Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011a).  Improved algorithms for linear stochastic bandits.  Advances in neural information processing systems, 24.
  * (2) Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011b).  Online least squares estimation with self-normalized processes: An application to bandit problems.  arXiv preprint arXiv:1102.2670.
  * Abbasi-Yadkori et al., (2012) Abbasi-Yadkori, Y., Pal, D., and Szepesvari, C. (2012).  Online-to-confidence-set conversions and application to sparse stochastic bandits.  In Artificial Intelligence and Statistics, pages 1–9. PMLR.
  * Abeille and Lazaric, (2017) Abeille, M. and Lazaric, A. (2017).  Linear thompson sampling revisited.  In AISTATS.
  * Angrist and Imbens, (1995) Angrist, J. D. and Imbens, G. W. (1995).  Two-stage least squares estimation of average causal effects in models with variable treatment intensity.  Journal of the American statistical Association, 90(430):431–442.
  * Angrist et al., (1996) Angrist, J. D., Imbens, G. W., and Rubin, D. B. (1996).  Identification of causal effects using instrumental variables.  Journal of the American statistical Association, 91(434):444–455.
  * Bartlett et al., (2015) Bartlett, P. L., Koolen, W. M., Malek, A., Takimoto, E., and Warmuth, M. K. (2015).  Minimax fixed-design linear regression.  In Conference on Learning Theory, pages 226–239. PMLR.
  * Bennett et al., (2019) Bennett, A., Kallus, N., and Schnabel, T. (2019).  Deep generalized method of moments for instrumental variable analysis.  Advances in neural information processing systems, 32.
  * Brier, (1950) Brier, G. W. (1950).  Verification of forecasts expressed in terms of probability.  Monthly Weather Review, 78:1–3.
  * Burgess et al., (2017) Burgess, S., Small, D. S., and Thompson, S. G. (2017).  A review of instrumental variable estimators for mendelian randomization.  Statistical methods in medical research, 26(5):2333–2355.
  * Cesa-Bianchi and Lugosi, (2006) Cesa-Bianchi, N. and Lugosi, G. (2006).  Prediction, learning, and games.  Cambridge university press.
  * Foster and Rakhlin, (2020) Foster, D. and Rakhlin, A. (2020).  Beyond UCB: Optimal and efficient contextual bandits with regression oracles.  In International Conference on Machine Learning, pages 3199–3210. PMLR.
  * Foster, (1991) Foster, D. P. (1991).  Prediction in the worst case.  The Annals of Statistics, pages 1084–1090.
  * Gaillard et al., (2019) Gaillard, P., Gerchinovitz, S., Huard, M., and Stoltz, G. (2019).  Uniform regret bounds over $\mathbb{R}^{d}$ for the sequential linear regression problem with the square loss.  In Algorithmic Learning Theory, pages 404–432. PMLR.
  * Greene, (2003) Greene, W. H. (2003).  Econometric analysis.  Pearson Education India.
  * Harris et al., (2022) Harris, K., Ngo, D. D. T., Stapleton, L., Heidari, H., and Wu, S. (2022).  Strategic instrumental variable regression: Recovering causal relationships from strategic responses.  In International Conference on Machine Learning, pages 8502–8522. PMLR.
  * Hartford et al., (2016) Hartford, J., Lewis, G., Leyton-Brown, K., and Taddy, M. (2016).  Counterfactual prediction with deep instrumental variables networks.  arXiv preprint arXiv:1612.09596.
  * Hazan and Koren, (2012) Hazan, E. and Koren, T. (2012).  Linear regression with limited observation.  In 29th International Conference on Machine Learning, ICML 2012, pages 807–814.
  * Heij et al., (2004) Heij, C., Heij, C., de Boer, P., Franses, P. H., Kloek, T., van Dijk, H. K., et al. (2004).  Econometric methods with applications in business and economics.  Oxford University Press.
  * Hernan and Robins, (2020) Hernan, M. and Robins, J. (2020).  Causal Inference: What if.  Boca Raton: Chapman & Hill/CRC.
  * Kallus, (2018) Kallus, N. (2018).  Instrument-armed bandits.  In Algorithmic Learning Theory, pages 529–546. PMLR.
  * Kazerouni and Wein, (2021) Kazerouni, A. and Wein, L. M. (2021).  Best arm identification in generalized linear bandits.  Operations Research Letters, 49(3):365–371.
  * Kivinen et al., (2004) Kivinen, J., Smola, A. J., and Williamson, R. C. (2004).  Online learning with kernels.  IEEE transactions on signal processing, 52(8):2165–2176.
  * Lattimore and Szepesvári, (2020) Lattimore, T. and Szepesvári, C. (2020).  Bandit algorithms.  Cambridge University Press.
  * Li et al., (2021) Li, J., Luo, Y., and Zhang, X. (2021).  Self-fulfilling bandits: Dynamic selection in algorithmic decision-making.  arXiv preprint arXiv:2108.12547.
  * Littlestone et al., (1991) Littlestone, N., Long, P. M., and Warmuth, M. K. (1991).  On-line learning of linear functions.  In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 465–475.
  * Liu et al., (2020) Liu, R., Shang, Z., and Cheng, G. (2020).  On deep instrumental variables estimate.  arXiv preprint arXiv:2004.14954.
  * Maillard, (2016) Maillard, O.-A. (2016).  Self-normalization techniques for streaming confident regression.
  * Mogstad et al., (2021) Mogstad, M., Torgovitsky, A., and Walters, C. R. (2021).  The causal interpretation of two-stage least squares with multiple instrumental variables.  American Economic Review, 111(11):3663–98.
  * Nareklishvili et al., (2022) Nareklishvili, M., Polson, N., and Sokolov, V. (2022).  Deep partial least squares for iv regression.  arXiv preprint arXiv:2207.02612.
  * Newey and Powell, (2003) Newey, W. K. and Powell, J. L. (2003).  Instrumental variable estimation of nonparametric models.  Econometrica, 71(5):1565–1578.
  * Orabona, (2019) Orabona, F. (2019).  A modern introduction to online learning.  arXiv preprint arXiv:1912.13213.
  * Ouhamma et al., (2022) Ouhamma, R., Basu, D., and Maillard, O.-A. (2022).  Bilinear exponential family of mdps: Frequentist regret bound with tractable exploration and planning.  arXiv preprint arXiv:2210.02087.
  * Ouhamma et al., (2021) Ouhamma, R., Maillard, O., and Perchet, V. (2021).  Stochastic online linear regression: the forward algorithm to replace ridge.  arXiv preprint arXiv:2111.01602.
  * Rubin, (1974) Rubin, D. B. (1974).  Estimating causal effects of treatments in randomized and nonrandomized studies.  Journal of educational Psychology, 66(5):688.
  * Singh et al., (2020) Singh, A., Hosanagar, K., and Gandhi, A. (2020).  Machine learning instrument variables for causal inference.  In Proceedings of the 21st ACM Conference on Economics and Computation, pages 835–836.
  * Stirn and Jebara, (2018) Stirn, A. and Jebara, T. (2018).  Thompson sampling for noncompliant bandits.  arXiv preprint arXiv:1812.00856.
  * Venkatraman et al., (2016) Venkatraman, A., Sun, W., Hebert, M., Bagnell, J., and Boots, B. (2016).  Online instrumental variable regression with applications to online linear system identification.  In Proceedings of the AAAI Conference on Artificial Intelligence.
  * Vershynin, (2018) Vershynin, R. (2018).  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press.
  * Vovk, (1997) Vovk, V. (1997).  Competitive on-line linear regression.  Advances in Neural Information Processing Systems, 10.
  * Vovk, (2001) Vovk, V. (2001).  Competitive on-line statistics.  International Statistical Review, 69(2):213–248.
  * Wainwright, (2019) Wainwright, M. J. (2019).  High-dimensional statistics: A non-asymptotic viewpoint, volume 48.  Cambridge University Press.
  * Wald, (1940) Wald, A. (1940).  The fitting of straight lines if both variables are subject to error.  The annals of mathematical statistics, 11(3):284–300.
  * Wasserman, (2004) Wasserman, L. (2004).  All of statistics: a concise course in statistical inference, volume 26.  Springer.
  * Wright, (1928) Wright, P. G. (1928).  Tariff on animal and vegetable oils.  Macmillan Company, New York.
  * Xu et al., (2020) Xu, L., Chen, Y., Srinivasan, S., de Freitas, N., Doucet, A., and Gretton, A. (2020).  Learning deep features in instrumental variable regression.  arXiv preprint arXiv:2010.07154.
  * Xu et al., (2021) Xu, L., Kanagawa, H., and Gretton, A. (2021).  Deep proxy causal learning and its application to confounded bandit policy evaluation.  arXiv preprint arXiv:2106.03907.
  * Zhu et al., (2022) Zhu, Y., Gultchin, L., Gretton, A., Kusner, M. J., and Silva, R. (2022).  Causal inference with treatment measurement error: a nonparametric instrumental variable approach.  In Uncertainty in Artificial Intelligence, pages 2414–2424. PMLR.

## Appendix

###  Appendix A Notations and useful results

####  A.1 Notations

##### Notations for scalars, vectors, matrices:

We indicate in bold vectors and matrices, e.g. the vector and matrix (matrices
are also usually capitalised)
$\boldsymbol{v}\in\mathbb{R}^{d},\mathbf{A}\in\mathbb{R}^{d\times d}$; while
scalars do not use the bold notation, e.g. the scalar $s\in\mathbb{R}$. We
indicate the determinant of matrix $\mathbf{A}$ with
$\operatorname{det}(\mathbf{A})$ and its trace with
$\operatorname{Tr}(\mathbf{A})$. For a $x\in\mathbb{R}_{\geq 0}$, we indicate
the function that takes as input $x$, and gives as output the least integer
greater than or equal to $x$ as $\lceil x\rceil$ (ceiling function). We
indicate the identity matrix of dimension $d$ with $\mathbf{I}_{d}$.

We dedicate the following table to index all the notations used in this paper.
Note that every notation is defined, when it is introduced as well.

Table 1: Notations $\boldsymbol{x}_{t}$ | $\triangleq$ | Covariates
---|---|---
$\boldsymbol{z}_{t}$ | $\triangleq$ | Instrumental Variables (IVs)
$y_{t}$ | $\triangleq$ | Outcome variable
$d_{\boldsymbol{z}}$ | $\triangleq$ | Dimension of the IVs
$d_{\boldsymbol{x}}$ | $\triangleq$ | Dimension of the covariates
$\boldsymbol{\beta}$ | $\triangleq$ | True parameter for the second-stage
$\boldsymbol{\Theta}$ | $\triangleq$ | True parameter for the first-stage
$\boldsymbol{\beta}_{t}$ | $\triangleq$ |  $\mathsf{O\text{2}SLS}$ estimate of parameter for the second-stage at time $t$
$\widehat{\boldsymbol{\Theta}}_{t}$ | $\triangleq$ | Estimate of parameter for the second-stage at time $t$
$\mathfrak{r}$ | $\triangleq$ | Relevance parameter
$L_{\boldsymbol{\Theta}}$ | $\triangleq$ | Bound on the operator norm of the true first-stage parameter
$L_{\boldsymbol{z}}$ | $\triangleq$ | Bound on the $\ell_{2}$ norms of IVs
$\sigma_{\eta}^{2}$ | $\triangleq$ | Bound on the variance of the second-stage noise $\eta$
$\sigma_{\boldsymbol{\epsilon}}^{2}$ | $\triangleq$ | Bound on the variance of the components of the first-stage noise $\boldsymbol{\epsilon}$
$C_{1}$ | $\triangleq$ |  $\sqrt{2\left(1+L_{\boldsymbol{\Theta}}^{2}\mathfrak{r}^{2}\right)}$.
$C_{2}$ | $\triangleq$ | $8e^{2}\left(\sigma_{\eta}^{2}+\sigma_{\boldsymbol{\epsilon}}^{2}\right)\frac{\mathfrak{r}}{L_{\boldsymbol{z}}}\sqrt{\log\frac{2}{\delta}}$
$C_{3}$ | $\triangleq$ | $8e^{2}\left(\sigma_{\eta}^{2}+\sigma_{\boldsymbol{\epsilon}}^{2}\right)\frac{\mathfrak{r}}{L_{\boldsymbol{z}}}\sqrt{\max\left\\{\frac{1}{\lambda},\frac{2}{\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})}\right\\}}\log\frac{2}{\delta}$
$C_{4}$ | $\triangleq$ | $\frac{\mathfrak{r}}{L_{\boldsymbol{z}}}\left(T_{0}\sqrt{\frac{\operatorname{\lambda_{min}}\left(\boldsymbol{\Sigma}\right)}{\lambda}}+2\sqrt{2}\right)$
$C_{5}$ | $\triangleq$ | A $T$-independent constant of $\text{O}(d_{\boldsymbol{x}}\sigma_{\boldsymbol{\epsilon}}^{2})$ (Equation (22))
$\mathbf{G}_{\boldsymbol{z},t}$ | $\triangleq$ | First-stage design matrix $\mathbf{G}_{\boldsymbol{z},0}+\sum_{s=1}^{t}\boldsymbol{z}_{s}\boldsymbol{z}_{s}^{\top}$
$\widehat{\mathbf{H}}_{t}$ | $\triangleq$ | Second-stage design matrix $\widehat{\boldsymbol{\Theta}}_{t}^{\top}\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\widehat{\boldsymbol{\Theta}}_{t}$
$\mathbf{\boldsymbol{\Sigma}}$ | $\triangleq$ | The true covariance matrix of IVs $\mathbb{E}[\boldsymbol{z}\boldsymbol{z}^{\top}]$
$\mathfrak{b}_{t}(\delta)$ | $\triangleq$ | Radius of the second-stage confidence ellipsoid at time $t$ (Equation (15))
$\lambda$ | $\triangleq$ | Minimum eigenvalue of $\mathbf{G}_{\boldsymbol{z},0}$, i.e. the (positive-valued) regularisation parameter
$\boldsymbol{\gamma}$ | $\triangleq$ | Covariance vector of the first-and second-stage noises $\mathbb{E}\left[\boldsymbol{\epsilon}\eta\right]$
$\gamma$ | $\triangleq$ |  $\ell_{2}$ norm of the covariance vector $\boldsymbol{\gamma}$
$f(T)$ | $\triangleq$ | Bound on the sum of maximum eigenvalues of the inverse of first-stage design
|  | matrices till time $T$, i.e. $\mathcal{O}(\log(T))$ (Corollary B.7)

####  A.2 Vectors, matrices, and norms

######  Definition A.1 ($\ell_{p}$-norms).

For a vector $\boldsymbol{v}\in\mathbb{R}^{n}$, we express its $\ell_{p}$-norm
as $\lVert\boldsymbol{v}\rVert_{p}$ for $p\geq 0$. A special case is the
Euclidean $\ell_{2}$-norm denoted as $\lVert\cdot\rVert_{2}$, which is induced
by classical scalar product on $\mathbb{R}^{n}$ denoted by
$\langle\cdot,\cdot\rangle$.

Given a rectangular matrix $\mathbf{A}\in\mathbb{R}^{n\times m}$ with $n\geq
m$, we write its ordered singular values as

$\sigma_{\max}(\mathbf{A})=\sigma_{1}(\mathbf{A})\geq\sigma_{2}(\mathbf{A})\geq\cdots\geq\sigma_{m}(\mathbf{A})=\sigma_{\min}(\mathbf{A})\geq
0$

The minimum and maximum singular values have the variational characterisation

$\sigma_{\max}(\mathbf{A})=\max_{\boldsymbol{v}\in\mathbb{S}^{m-1}}\|\mathbf{A}\boldsymbol{v}\|_{2}\quad\text{
and
}\quad\sigma_{\min}(\mathbf{A})=\min_{\boldsymbol{v}\in\mathbb{S}^{m-1}}\|\mathbf{A}\boldsymbol{v}\|_{2},$

where
$\mathbb{S}^{d-1}\triangleq\left\\{\boldsymbol{v}\in\mathbb{R}^{d}\mid\|\boldsymbol{v}\|_{2}=1\right\\}$
is the Euclidean unit sphere in $\mathbb{R}^{d}$.

######  Definition A.2 ($\ell_{2}$-operator norm).

The spectral or $\ell_{2}$-operator norm of $\mathbf{A}$ is defined as

$\vvvert\mathbf{A}\vvvert_{2}\triangleq\sigma_{\max}(\mathbf{A})\;.$ (7)

Since covariance matrices are symmetric, we also focus on the set of symmetric
matrices in $\mathbb{R}^{d}$, denoted $\mathcal{S}^{d\times
d}=\left\\{\mathbf{Q}\in\mathbb{R}^{d\times
d}\mid\mathbf{Q}=\mathbf{Q}^{\mathrm{T}}\right\\}$, as well as the subset of
positive semidefinite matrices given by

$\mathcal{S}_{+}^{d\times
d}\triangleq\left\\{\mathbf{Q}\in\mathcal{S}^{d\times d}\mid\mathbf{Q}\succeq
0\right\\}.$

From standard linear algebra, we recall the facts that any matrix
$\mathbf{Q}\in\mathcal{S}^{d\times d}$ is diagonalisable via a unitary
transformation, and we use $\lambda(\mathbf{Q})\in\mathbb{R}^{d}$ to denote
its vector of eigenvalues, ordered as

$\lambda_{\max}(\mathbf{Q})=\lambda_{1}(\mathbf{Q})\geq\lambda_{2}(\mathbf{Q})\geq\cdots\geq\lambda_{d}(\mathbf{Q})=\lambda_{\min}(\mathbf{Q}).$

Note that a matrix $\mathbf{Q}$ is positive semidefinite-written
$\mathbf{Q}\succeq 0$ for short-if and only if $\lambda_{\min}(\mathbf{Q})\geq
0$.

######  Remark A.3 (Rayleigh-Ritz variational characterisation of
eigenvalues).

We remind also the Rayleigh-Ritz variational characterisation of the minimum
and maximum eigenvalues-namely

$\lambda_{\max}(\mathbf{Q})=\max_{\boldsymbol{v}\in\mathbb{S}^{d-1}}\boldsymbol{v}^{\top}\mathbf{Q}\boldsymbol{v}\quad\text{
and
}\quad\lambda_{\min}(\mathbf{Q})=\min_{\boldsymbol{v}\in\mathbb{S}^{d-1}}\boldsymbol{v}^{\top}\mathbf{Q}\boldsymbol{v}.$

######  Remark A.4.

For any symmetric matrix $\mathbf{Q}$, the $\ell_{2}$-operator norm can be
written as

$\vvvert\mathbf{Q}\vvvert_{2}=\max\left\\{\lambda_{\max}(\mathbf{Q}),\left|\lambda_{\min}(\mathbf{Q})\right|\right\\},$

by virtue of which it inherits the variational representation
$\vvvert\mathbf{Q}\vvvert_{2}=\max_{\boldsymbol{v}\in\mathbb{S}^{d-1}}\left|\boldsymbol{v}^{\top}\mathbf{Q}\boldsymbol{v}\right|.$

######  Corollary A.5.

Given a rectangular matrix $\mathbf{A}\in\mathbb{R}^{n\times m}$ with $n\geq
m$, suppose that we define the $m$ dimensional symmetric matrix
$\mathbf{R}=\mathbf{A}^{\mathrm{T}}\mathbf{A}$. We then have the relationship

$\lambda_{j}(\mathbf{R})=\left(\sigma_{j}(\mathbf{A})\right)^{2}\quad\text{
for }j=1,\ldots,m$

We now introduce norms that are induced by positive semi-definite matrices in
the following way.

######  Definition A.6.

For any vector $y\in\mathbb{R}^{n}$ and matrix
$\mathbf{A}\in\mathcal{S}_{+}^{n\times n}$, let us define the norm
$\|\boldsymbol{y}\|_{\mathbf{A}}\triangleq\sqrt{\boldsymbol{y}^{T}\mathbf{A}\boldsymbol{y}}=\sqrt{\langle\boldsymbol{y},\mathbf{A}\boldsymbol{y}\rangle}$.

Throughout the paper we will need often to bound matrix induced norms using
$\ell_{2}$-norms for operators, the following results show how this can be
done easily for generic matrices. We specialise this result as we need in the
text.

######  Proposition A.7.

Take $\mathbf{A},\mathbf{B}\in\mathbb{R}^{n\times n}$, with $\mathbf{B}\succeq
0$ positive semi-definite and $\boldsymbol{x}\in\mathbb{R}^{n}$

$\lVert\mathbf{A}\boldsymbol{x}\rVert_{\mathbf{B}}^{2}=\lVert\boldsymbol{x}\rVert_{\mathbf{A}^{\top}\mathbf{B}\mathbf{A}}^{2}\leq\vvvert\mathbf{B}\vvvert_{2}\vvvert\mathbf{A}\vvvert_{2}^{2}\lVert\boldsymbol{x}\rVert_{2}^{2}$
(8)

###### Proof.

The equality holds since we can rewrite

$\displaystyle\lVert\mathbf{A}\boldsymbol{x}\rVert_{\mathbf{B}}^{2}=\langle\mathbf{A}\boldsymbol{x},\mathbf{B}\mathbf{A}\boldsymbol{x}\rangle=\langle\boldsymbol{x},\mathbf{A}^{\top}\mathbf{B}\mathbf{A}\boldsymbol{x}\rangle=\lVert\boldsymbol{x}\rVert_{\mathbf{A}^{\top}\mathbf{B}\mathbf{A}}^{2}.$

The inequality follows by the definition of $\ell_{2}$-norms, where we further
substitute $\boldsymbol{y}=\mathbf{A}\boldsymbol{x}$, to get

$\displaystyle\langle\mathbf{A}\boldsymbol{x},\mathbf{B}\mathbf{A}\boldsymbol{x}\rangle$
$\displaystyle=\frac{\langle\mathbf{A}\boldsymbol{x},\mathbf{B}\mathbf{A}\boldsymbol{x}\rangle}{\lVert\mathbf{A}\boldsymbol{x}\rVert_{2}^{2}}\frac{\lVert\mathbf{A}\boldsymbol{x}\rVert_{2}^{2}}{\lVert\boldsymbol{x}\rVert_{2}^{2}}\lVert\boldsymbol{x}\rVert_{2}^{2}=\frac{\langle\boldsymbol{y},\mathbf{B}\boldsymbol{y}\rangle}{\lVert\boldsymbol{y}\rVert_{2}^{2}}\frac{\lVert\mathbf{A}\boldsymbol{x}\rVert_{2}^{2}}{\lVert\boldsymbol{x}\rVert_{2}^{2}}\lVert\boldsymbol{x}\rVert_{2}^{2}\leq\vvvert\mathbf{B}\vvvert_{2}\vvvert\mathbf{A}\vvvert_{2}^{2}\lVert\boldsymbol{x}\rVert_{2}^{2}.$

We note that the inequality holds trivially for $x$ in the null space of
$\mathbf{A}$, therefore, in the previous case, we can safely divide by
$\lVert\mathbf{A}\boldsymbol{x}\rVert_{2}$ and
$\lVert\boldsymbol{x}\rVert_{2}$. ∎

######  Lemma A.8 (Determinant-Trace Inequality).

Suppose
$\boldsymbol{z}_{1},\boldsymbol{z}_{2},\ldots,\boldsymbol{z}_{t}\in\mathbb{R}^{d}$
and for any $1\leq s\leq t$, $\left\|\boldsymbol{z}_{s}\right\|_{2}\leq
L_{z}$. Let
$\mathbf{G}_{\boldsymbol{z},t}=\lambda\mathbf{I}_{d_{\boldsymbol{z}}}+\sum_{s=1}^{t}\boldsymbol{z}_{s}\boldsymbol{z}_{s}^{\top}$
for some $\lambda>0$. Then,

$\operatorname{det}\left(\mathbf{G}_{\boldsymbol{z},t}\right)\leq\left(\lambda+tL^{2}_{z}/d_{\boldsymbol{z}}\right)^{d_{\boldsymbol{z}}}$
(9)

###### Proof.

Let $\alpha_{1},\alpha_{2},\ldots,\alpha_{d_{\boldsymbol{z}}}$ be the
eigenvalues of $\mathbf{G}_{\boldsymbol{z},t}$. Since
$\mathbf{G}_{\boldsymbol{z},t}$ is positive definite, its eigenvalues are
positive. Also, note that
$\operatorname{det}(\mathbf{G}_{\boldsymbol{z},t})=\prod_{s=1}^{{d_{\boldsymbol{z}}}}\alpha_{s}$
and
$\operatorname{Tr}\left(\mathbf{G}_{\boldsymbol{z},t}\right)=\sum_{s=1}^{{d_{\boldsymbol{z}}}}\alpha_{s}$.
By inequality of arithmetic and geometric means,

$\sqrt[d_{\boldsymbol{z}}]{\alpha_{1}\alpha_{2}\cdots\alpha_{d_{\boldsymbol{z}}}}\leq\frac{\alpha_{1}+\alpha_{2}+\cdots+\alpha_{d_{\boldsymbol{z}}}}{{d_{\boldsymbol{z}}}}.$

Therefore,
$\operatorname{det}\left(\mathbf{G}_{\boldsymbol{z},t}\right)\leq\left(\operatorname{Tr}\left(\mathbf{G}_{\boldsymbol{z},t}\right)/{d_{\boldsymbol{z}}}\right)^{{d_{\boldsymbol{z}}}}$.
Now, it remains to upper bound the trace:

$\operatorname{Tr}\left(\mathbf{G}_{\boldsymbol{z},t}\right)=\operatorname{Tr}(\lambda\mathbf{I}_{d_{\boldsymbol{z}}})+\sum_{s=1}^{t}\operatorname{Tr}\left(\boldsymbol{z}_{s}\boldsymbol{z}_{s}^{\top}\right)={d_{\boldsymbol{z}}}\lambda+\sum_{s=1}^{t}\left\|\boldsymbol{z}_{s}\right\|_{2}^{2}\leq{d_{\boldsymbol{z}}}\lambda+tL^{2}_{z}.$

∎

As a direct corollary of Weyl’s theorem for eigenvalues, we have the following
(Wainwright,, 2019).

######  Lemma A.9.

For two symmetric matrices $\mathbf{A}$ and $\mathbf{B}$

$\left|\operatorname{\lambda_{min}}(\mathbf{A})-\operatorname{\lambda_{min}}(\mathbf{B})\right|\leq\left\vvvert\mathbf{A}-\mathbf{B}\right\vvvert_{2}.$
(10)

####  A.3 Random variables and concentration bounds

Random variables follow the previous convention if they are scalar, vectors,
or random matrix variables. We adopt the following convention when we talk
about sub-Gaussians and sub-exponential random variables.

######  Definition A.10 (Sub-Gaussian r.v.).

A random variable $X$ with mean $\mu=\mathbb{E}[X]$ is sub-Gaussian if there
is a positive number $\sigma$ such that

$\mathbb{E}\left[e^{\lambda(X-\mu)}\right]\leq
e^{\sigma^{2}\lambda^{2}/2}\quad\text{ for all }\lambda\in\mathbb{R}\text{. }$

######  Definition A.11 (Sub-exponential r.v.).

A random variable $X$ with mean $\mu=\mathbb{E}[X]$ is sub-exponential if
there are non-negative parameters $(\nu,\alpha)$ such that

$\mathbb{E}\left[e^{\lambda(X-\mu)}\right]\leq
e^{\nu^{2}\lambda^{2}/2}\quad\text{ for all }|\lambda|<\frac{1}{\alpha}$

######  Lemma A.12 (Square and product of non-independent sub-Gaussian random
variables).

Given two non-independent random variables $X\sim$ sub-Gaussian$(\sigma_{X})$
and $Y\sim$ sub-Gaussian$(\sigma_{Y})$, we have the following properties:
1\. the squared random variable $X^{2}$ is sub-
exp$\left(4\sqrt{2}\sigma^{2},4\sigma^{2}\right);$
2\. the recentered random variable $XY$ is sub-
exp$\left(4\sqrt{2}\left(\sigma_{X}^{2}+\sigma_{Y}^{2}\right),2\left(\sigma_{X}^{2}+\sigma_{Y}^{2}\right)\right)$.

###### Proof.

We establish the proof for both statements sequentially, leveraging the first
result to demonstrate the second in the scenario of non-independent random
variables. This distinction gives rise to distinct constants compared to the
outcome observed for independent random variables.

For the first point we bound the rescaled $p$-th power of $X$

$\displaystyle\mathbb{E}\left[\left|\nicefrac{{X}}{{\sigma_{X}\sqrt{2}}}\right|^{p}\right]$
$\displaystyle=\int_{0}^{\infty}\mathbb{P}\left\\{\left|\nicefrac{{X}}{{\sigma_{X}\sqrt{2}}}\right|^{p}\geq
u\right\\}du$ (integral identity for positive r.v.)
$\displaystyle=\frac{1}{\sqrt{2}\sigma_{X}}\int_{0}^{\infty}\mathbb{P}\left\\{|X|\geq
t\sqrt{2}\sigma_{X}\right\\}pt^{p-1}dt$ (change of variable $u=t^{p}$)
$\displaystyle\leq\int_{0}^{\infty}2e^{-t^{2}}pt^{p-1}dt$ (by
$\sigma_{X}$-sub-Gaussianity) $\displaystyle=p\Gamma(p/2)$ ( set $t^{2}=s$ and
use definition of Gamma function) )

By multiplying both sides by $(\sqrt{2}\sigma)^{p}$ we obtain
${\mathbb{E}\left[\left|X\right|^{p}\right]}\leq
p2^{\frac{p}{2}}\sigma^{p}\Gamma(p/2).$

Let $W=X^{2}$ and $\mu_{W}=\mathbb{E}[W]$. By power series expansion and since
$\Gamma(r)=(r-1)!$ for an integer $r$, we have:

$\displaystyle\mathbb{E}\left[e^{\lambda\left(W-\mu_{W}\right)}\right]$
$\displaystyle=1+\lambda\mathbb{E}\left[W-\mu_{W}\right]+\sum_{r=2}^{\infty}\frac{\lambda^{r}\mathbb{E}\left[\left(W-\mu_{W}\right)^{r}\right]}{r!}\leq
1+\sum_{r=2}^{\infty}\frac{\lambda^{r}\mathbb{E}\left[|X|^{2r}\right]}{r!}$
$\displaystyle\leq
1+\sum_{r=2}^{\infty}\frac{\lambda^{r}2r2^{r}\sigma^{2r}\Gamma(r)}{r!}=1+\sum_{r=2}^{\infty}\lambda^{r}2^{r+1}\sigma^{2r}=1+\frac{8\lambda^{2}\sigma^{4}}{1-2\lambda\sigma^{2}}$

By making $|\lambda|\leq 1/\left(4\sigma^{2}\right)$, we have
$1/\left(1-2\lambda\sigma^{2}\right)\leq 2$. Finally, since
$(\forall\alpha)1+\alpha\leq e^{\alpha}$, we have that a sub-Gaussian variable
$X$ with parameter $\sigma$ is sub-exponential with parameters
$(4\sqrt{2}\sigma^{2},4\sigma^{2})$, in fact we have:

$\displaystyle\mathbb{E}\left[e^{\lambda\left(X^{2}-\mathbb{E}\left[X^{2}\right]\right)}\right]\leq
e^{16\lambda^{2}\sigma^{4}}\quad\forall|\lambda|\leq
1/\left(4\sigma^{2}\right).$

To prove the second point we define
$Z_{1}\triangleq\left(\frac{X-Y}{2}\right)^{2}-\mathbb{E}\left[\left(\frac{X-Y}{2}\right)^{2}\right]$
and
$Z_{2}\triangleq\left(\frac{X+Y}{2}\right)^{2}-\mathbb{E}\left[\left(\frac{X+Y}{2}\right)^{2}\right]$,
then $XY-\mathbb{E}[XY]=Z_{1}-Z_{2}$. We take care of the dependence between
$X$ and $Y$ using Cauchy-Schwarz inequality instead of the product rule for
expectations of independent random variables:

$\displaystyle\mathbb{E}\left[e^{\lambda(X+Y)}\right]{\leq}\sqrt{\mathbb{E}\left[e^{2\lambda
X}\right]}\sqrt{\mathbb{E}\left[e^{2\lambda
Y}\right]}\leq\sqrt{e^{\frac{4\lambda^{2}\sigma_{X}^{2}}{2}}}\sqrt{e^{\frac{4\lambda^{2}\sigma_{X}^{2}}{2}}}=e^{\frac{\lambda^{2}}{2}\left[2\left(\sigma_{X}^{2}+\sigma_{Y}^{2}\right)\right]}$

where we used the sub-Gaussianity of $X$ and $Y$ separately. This proves for
rescaled variables that both $X+Y$ and $X-Y$ are sub-
Gaussian$(\sqrt{2}\sqrt{\sigma_{X}^{2}+\sigma_{Y}^{2}})$, therefore their
rescaled versions $\nicefrac{{(X+Y)}}{{2}}$ and $\nicefrac{{(X-Y)}}{{2}}$ are
sub-Gaussian$(\nicefrac{{\sqrt{\sigma_{X}^{2}+\sigma_{Y}^{2}}}}{{\sqrt{2}}})$.
We use the previous result on the square of sub-Gaussian random variables to
show that $Z_{1}$ and $Z_{2}$ are both $\text{sub-
exp}\left(2\sqrt{2}(\sigma_{X}^{2}+\sigma_{Y}^{2}),2(\sigma_{X}^{2}+\sigma_{Y}^{2})\right).$
We use again Cauchy-Schwarz since it holds also for dependent $Z_{1}$ and
$Z_{2}$

$\mathbb{E}\left[e^{\lambda(XY-E[XY)]}\right]=\mathbb{E}\left[e^{\lambda\left(Z_{1}-Z_{2}\right)}\right]\leq\sqrt{\mathbb{E}\left[e^{2\lambda
Z_{1}}\right]\mathbb{E}\left[e^{-2\lambda Z_{2}}\right]}\leq
e^{+\frac{4\lambda^{2}}{2}8\left(\sigma_{X}^{2}+\sigma_{Y}^{2}\right)^{2}}$

which holds for
$\lambda\leq\nicefrac{{1}}{{2\left(\sigma_{X}^{2}+\sigma_{Y}^{2}\right)}}$.
This proves that the sub-exponential parameters are indeed
$\nu=4\sqrt{2}\left(\sigma_{X}^{2}+\sigma_{Y}^{2}\right)$ and
$\alpha=2\left(\sigma_{X}^{2}+\sigma_{Y}^{2}\right)$. ∎

The following are known concentration results, see (Wainwright,, 2019).

######  Theorem A.13 (Concentration of martingale difference sequences).

Let $\left\\{\left(D_{k},\mathcal{F}_{k}\right)\right\\}_{k=1}^{\infty}$ be a
martingale difference sequence, and suppose that $\mathbb{E}\left[e^{\lambda
D_{k}}\mid\mathcal{F}_{k-1}\right]\leq e^{\lambda^{2}\nu_{k}^{2}/2}$ almost
surely for any $|\lambda|<1/\alpha_{k}$. Then the following hold:
1\. the sum $\sum_{k=1}^{n}D_{k}$ is sub-
exponential$(\sqrt{\sum_{k=1}^{n}\nu_{k}^{2}},\alpha_{*})$ where
$\alpha_{*}\triangleq\max\nolimits_{k=1,\ldots,n}\alpha_{k}$;
2\. the sum satisfies the concentration inequality

$\mathbb{P}\left[\left|\sum_{k=1}^{n}D_{k}\right|\geq
t\right]\leq\begin{cases}2e^{-\frac{r^{2}}{2\sum_{k=1}^{n}\nu_{k}^{2}}}&\text{if}\quad
0\leq t\leq\frac{\sum_{k=1}^{n}\nu_{k}^{2}}{\alpha_{*}}\\\
2e^{-\frac{1}{2\alpha_{*}}}&\text{if}\quad
t>\frac{\sum_{k=1}^{n}\nu_{k}^{2}}{\alpha_{*}}\end{cases}.$

######  Theorem A.14 (Estimation of covariance matrices).

Let $\boldsymbol{z}_{1},\ldots,\boldsymbol{z}_{t}$ be i.i.d. zero-mean random
vectors with covariance $\boldsymbol{\Sigma}$ such that
$\left\|\boldsymbol{z}_{s}\right\|_{2}\leq L_{\boldsymbol{z}}$ almost surely.
Then for all $\delta>0$, the sample covariance matrix
$\widehat{\boldsymbol{\Sigma}}_{t}=\frac{1}{t}\sum_{s=1}^{t}\boldsymbol{z}_{s}\boldsymbol{z}_{s}^{\top}$
satisfies

$\mathbb{P}\left[\left\vvvert\widehat{\boldsymbol{\Sigma}}_{t}-\boldsymbol{\Sigma}\right\vvvert_{2}\geq\delta\right]\leq
2d\exp\left(-\frac{t\delta^{2}}{\left(2L_{\boldsymbol{z}}^{2}\left\vvvert\boldsymbol{\Sigma}\right\vvvert_{2}+\delta\right)}\right),$

this means that with probability at least $1-\delta$

$\left\vvvert\widehat{\boldsymbol{\Sigma}}_{t}-\boldsymbol{\Sigma}\right\vvvert_{2}\leq\frac{4L_{\boldsymbol{z}}^{2}}{t}\log\left(\frac{2d}{\delta}\right)+2\sqrt{\frac{2L_{\boldsymbol{z}}^{2}}{t}\log\left(\frac{2d_{\boldsymbol{z}}}{\delta}\right)\left\vvvert\boldsymbol{\Sigma}\right\vvvert_{2}}.$

Finally, we have two important theorems whose proofs can be found in (Abbasi-
Yadkori et al., 2011a, ).

######  Theorem A.15 (Self-Normalised Bound for Vector-Valued Martingales).

Let $\left\\{\mathcal{F}_{t}\right\\}_{t=0}^{\infty}$ be a filtration. Let
$\left\\{\eta_{t}\right\\}_{t=1}^{\infty}$ be a real-valued stochastic process
such that $\eta_{t}$ is $\mathcal{F}_{t}$-measurable and $\eta_{t}$ is
conditionally $\sigma_{\eta}$-sub-Gaussian for some $\sigma_{\eta}\geq 0$ i.e.
$\forall\lambda\in\mathbb{R}$ holds
$\mathbb{E}\left[e^{\lambda\eta_{t}}\mid\mathcal{F}_{t-1}\right]\leq\exp\left(\nicefrac{{\lambda^{2}\sigma_{\eta}^{2}}}{{2}}\right).$
Let $\left\\{\boldsymbol{z}_{t}\right\\}_{t=1}^{\infty}$ be an
$\mathbb{R}^{d}$-valued stochastic process such that $\boldsymbol{z}_{t}$ is
$\mathcal{F}_{t-1}$-measurable. For any $t\geq 0$, define
$\boldsymbol{v}_{t}=\sum_{s=1}^{t}\eta_{s}\boldsymbol{z}_{s}.$ Then, for any
$\delta>0$, with probability at least $1-\delta$, for all $t\geq 0$,

$\left\|\boldsymbol{v}_{t}\right\|_{\mathbf{G}_{\boldsymbol{z},t}^{-1}}\leq\sqrt{2\sigma_{\eta}^{2}\log\left(\frac{\operatorname{det}\left(\mathbf{G}_{\boldsymbol{z},t}\right)^{1/2}\lambda^{-d/2}}{\delta}\right)}\leq\sqrt{2{d_{\boldsymbol{z}}\sigma_{\eta}^{2}}\log\left(\frac{1+tL^{2}_{z}/d_{\boldsymbol{z}}\lambda}{\delta}\right)}$

######  Theorem A.16 (Self-normalised Bound for Scalar Valued Martingales).

Under the same assumptions as the previous theorem, let
$\left\\{\mathcal{F}_{t}\right\\}_{t=0}^{\infty}$ be a filtration. Let
$\left\\{\eta_{t}\right\\}_{t=1}^{\infty}$ be a real-valued stochastic process
such that $\eta_{t}$ is $\mathcal{F}_{t}$-measurable and $\eta_{t}$ is
conditionally $\sigma_{\eta}$-sub-Gaussian for some $\sigma_{\eta}\geq 0$ i.e.
$\forall\lambda\in\mathbb{R}$ holds
$\mathbb{E}\left[e^{\lambda\eta_{t}}\mid\mathcal{F}_{t-1}\right]\leq\exp\left(\nicefrac{{\lambda^{2}\sigma_{\eta}^{2}}}{{2}}\right).$
Let $\left\\{w_{t}\right\\}_{t=1}^{\infty}$ be a scalar-valued stochastic
process such that $w_{t}$ is $\mathcal{F}_{t-1}$-measurable. Then, for any
$\delta>0$, with probability at least $1-\delta$, for all $t\geq 0$,

$\left|\sum_{s=1}^{t}\eta_{t}w_{t}\right|\leq\sigma_{\eta}\sqrt{2\left(1/\sigma_{\eta}^{2}+\sum_{s=1}^{t}w_{s}\right)\log\left(\frac{\sqrt{1+\sigma_{\eta}^{2}\sum_{s=1}^{t}w_{s}^{2}}}{\delta}\right)}$
(11)

###  Appendix B Regret analysis of $\mathsf{O\text{2}SLS}$

Instrumental variables is a powerful technique employed in econometrics to
address endogeneity concerns when estimating causal relationships between
variables. One computational approach commonly used is $\mathsf{\text{2}SLS}$.
In the first stage of 2SLS, each endogenous covariate in the equation of
interest is regressed on all exogenous variables in the model, including both
exogenous covariates within the equation of interest and the excluded
instruments. This step aims to establish the relationship between the
endogenous variables and the instruments. In the second stage, the regression
of interest is estimated, wherein each endogenous covariate is substituted
with the predicted values obtained from the first stage. By employing this
two-stage procedure, 2SLS effectively addresses endogeneity issues and
provides consistent estimates of the causal effects of interest.

In the following we show the relation between the just-identified and over-
identified case of IVs and show the form that the $\mathsf{\text{2}SLS}$
assumes in the two cases.

####  B.1 A primer on just-identified and over-identified IVs and
$\mathsf{\text{2}SLS}$

##### Just-identified case [$d_{\boldsymbol{x}}=d_{\boldsymbol{z}}=d$]:

In the just-identified case, instruments and covariates have the same
dimension $d$, i.e. for each covariate, there is an instrument that is
correlated to it. Given an observational dataset
$\\{\boldsymbol{x}_{s},y_{s}\\}_{s=1}^{t}$ consisting of $t$ pairs of input
features and outcomes, such that $y_{s}\in\mathbb{R}$ and
$\boldsymbol{x}_{s}\in\mathbb{R}^{d}$. These inputs and outcomes are
stochastically generated using a linear model

$y_{s}=\boldsymbol{\beta}^{\top}\boldsymbol{x}_{s}+\eta_{s},$

It is assumed that the error terms $\eta_{i}$ are independently and
identically distributed and have bounded variance $\sigma^{2}$. In the
presence of endogeneity ($\boldsymbol{x}$ and the noise $\boldsymbol{\eta}$
are correlated) Ordinary Least Square $\boldsymbol{\beta}$ (Wasserman,, 2004)
defined as
$\widehat{\boldsymbol{\beta}}\triangleq\operatorname*{argmin}_{\boldsymbol{\beta}^{\prime}}\sum_{s=1}(y_{s}-\boldsymbol{\beta}^{\prime\top}\boldsymbol{x}_{s})^{2}$
is biased and asymptotically inconsistent. To compute an unbiased estimate of
$\boldsymbol{\beta}$ under endogeneity, a popular technique is to introduce
the Instrumental Variables (IVs). IVs are chosen such that they are highly
correlated with endogenous components of $\boldsymbol{x}$ (relevance
condition) but are independent of the noise $\eta$ (exogeneity condition for
$\boldsymbol{z}$). In practice, this dependence is modelled with a confounding
unobserved random variable $\boldsymbol{\epsilon}$ by

$\mathbf{X}_{t}=\mathbf{Z}_{t}\boldsymbol{\Theta}+\mathbf{E}_{t},$

where $\boldsymbol{\Theta}\in\mathbb{R}^{d\times d}$ is an unknown first-stage
parameter matrix and
$\mathbf{E}_{t}\triangleq[\boldsymbol{\epsilon}_{1},\ldots,\boldsymbol{\epsilon}_{t}]^{\top}$
is the unobserved noise matrix leading to confounding in the second stage. The
most common IV specification uses the following estimator:

$\widehat{\boldsymbol{\beta}}_{\mathrm{IV},t}\triangleq\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\boldsymbol{y}_{t}.$
(IV)

As long as $\mathbb{E}[\boldsymbol{z}_{i}\eta_{i}]=\boldsymbol{0}$ in the true
model,
$\widehat{\boldsymbol{\beta}}_{\mathrm{IV},t}=\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\boldsymbol{\beta}+\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\boldsymbol{\eta}_{t}\overset{p}{\rightarrow}\boldsymbol{\beta},$
as $t\to\infty$. This works because IV solves for the unique parameter that
satisfies
$\frac{1}{n}\mathbf{Z}_{t}^{\top}\boldsymbol{\eta}_{t}\overset{p}{\rightarrow}\boldsymbol{0}$.
Since $\boldsymbol{x}$ and $\boldsymbol{\eta}$ are correlated, IV estimator is
not unbiased in finite-time.

##### Over-identified case [$d_{\boldsymbol{x}}<d_{\boldsymbol{z}}$]:

Suppose that there are more instruments than there are covariates in the
equation of interest, so that $\mathbf{Z}_{t}$ is a $t\times
d_{\boldsymbol{z}}$ matrix with $d_{\boldsymbol{z}}>d_{\boldsymbol{x}}$. This
is often called the over-identified case. In this case, the generalised method
of moments (GMM) can be used. The GMM IV estimator is

$\displaystyle{\boldsymbol{\beta}}_{\mathrm{GMM},t}\triangleq\left(\mathbf{X}_{t}^{\top}\mathbf{P}_{t,\mathbf{Z}_{t}}\mathbf{X}_{t}\right)^{-1}\mathbf{X}_{t}^{\top}\mathbf{P}_{t,\mathbf{Z}_{t}}\boldsymbol{y}_{t},$
(GMM IV)

where $\mathbf{P}_{t,\mathbf{Z}_{t}}$ refers to the projection matrix
$\mathbf{P}_{t,\mathbf{Z}_{t}}\triangleq\mathbf{Z}_{t}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}$.
This expression collapses to the first when the number of instruments is equal
to the number of covariates in the equation of interest. The over-identified
IV is, therefore a generalisation of the just-identified IV. Defining GMM IV
estimator requires an additional well-behavedness assumption on IVs.

######  Assumption B.1 (Well-behaved IVs).

For any $t>0$, the matrix $\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}$ is full rank
with $\lambda_{\min}(\mathbf{G}_{\boldsymbol{z},0})\triangleq\lambda_{0}>0$.

######  Proposition B.2.

If $d_{\boldsymbol{x}}=d_{\boldsymbol{z}}$, i.e. in the just-identified case,
$\boldsymbol{\beta}_{\mathrm{GMM},t}$ reduces to
$\boldsymbol{\beta}_{\mathrm{IV},t}$ .

###### Proof.

Expanding the $\boldsymbol{\beta}_{GMM}$ expression:

${\boldsymbol{\beta}}_{\mathrm{GMM},t}=\left(\mathbf{X}_{t}^{\top}\mathbf{Z}_{t}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)^{-1}\mathbf{X}_{t}^{\top}\mathbf{Z}_{t}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\boldsymbol{y}_{t}$

In the just-identified case, we have as many instruments as covariates, so
that the dimension of $\mathbf{X}_{t}$ is the same as that of
$\mathbf{Z}_{t}$. Hence,
$\mathbf{X}_{t}^{\top}\mathbf{Z}_{t},\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}$ and
$\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}$ are all squared matrices of the same
dimension. We can expand the inverse, using the fact that, for any invertible
$n$-by-n matrices $A$ and $B,(AB)^{-1}=B^{-1}A^{-1}$:

$\displaystyle{\boldsymbol{\beta}}_{\mathrm{GMM},t}$
$\displaystyle=\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)^{-1}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)\left(\mathbf{X}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{X}_{t}^{\top}\mathbf{Z}_{t}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\boldsymbol{y}_{t}$
$\displaystyle=\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)^{-1}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\boldsymbol{y}_{t}$
$\displaystyle=\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\boldsymbol{y}_{t}$
$\displaystyle=\boldsymbol{\beta}_{\mathrm{IV},t}$

∎

##### Interpretation as two-stage least-squares.

One computational method which can be used to calculate IV estimates is two-
stage least squares $\mathsf{\text{2}SLS}$. In the first stage, each
explanatory variable that is an endogenous covariate in the equation of
interest is regressed on all of the exogenous variables in the model,
including both exogenous covariates in the equation of interest and the
excluded instruments. The predicted values from these regressions are
obtained. Then, in the second stage, the regression of interest is estimated
as usual, except that in this stage each endogenous covariate is replaced with
the predicted values from the first stage.

######  Proposition B.3.

For $d_{\boldsymbol{x}}\leq d_{\boldsymbol{z}}$, i.e. in both just- and over-
identified cases,
$\boldsymbol{\beta}_{\mathrm{GMM},t}=\boldsymbol{\beta}_{\textrm{2SLS},t}$.

###### Proof.

The proof follows in two steps by simple substitution of the relevant
quantities.

Stage 1: Regress each column of $\mathbf{X}_{t}$ on $\mathbf{Z}_{t},$ in the
first stage

$\mathbf{X}_{t}=\mathbf{Z}_{t}\boldsymbol{\Theta}+\mathbf{E}_{t}$

which gives:

$\displaystyle\widehat{\boldsymbol{\Theta}}_{t}\triangleq\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}$
(12)

and save the predicted values:

$\widehat{\mathbf{X}}_{t}\triangleq\mathbf{Z}_{t}\widehat{\boldsymbol{\Theta}}_{t}=\mathbf{Z}_{t}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}=\mathbf{P}_{t,\mathbf{Z}_{t}}\mathbf{X}_{t}.$

Stage 2: Regress $\boldsymbol{y}_{t}$ on the predicted values from the first
stage:

$\boldsymbol{y}_{t}=\widehat{\mathbf{X}}_{t}\boldsymbol{\beta}+\boldsymbol{\eta}_{t}$

which gives:

$\boldsymbol{\beta}_{\textrm{2SLS},t}=\left(\widehat{\mathbf{X}}_{t}^{\top}\widehat{\mathbf{X}}_{t}\right)^{-1}\widehat{\mathbf{X}}_{t}^{\top}\boldsymbol{y}_{t}=\left(\mathbf{X}_{t}^{\top}\mathbf{P}_{t,\mathbf{Z}_{t}}\mathbf{X}_{t}\right)^{-1}\mathbf{X}_{t}^{\top}\mathbf{P}_{t,\mathbf{Z}_{t}}\boldsymbol{y}_{t}$

where the second equality follows from the fact that the usual OLS estimator
is:
$(\widehat{\mathbf{X}}_{t}^{\top}\widehat{\mathbf{X}}_{t})^{-1}\widehat{\mathbf{X}}_{t}^{\top}\boldsymbol{y}_{t}$,
and replacing
$\widehat{\mathbf{X}}_{t}=\mathbf{P}_{t,\mathbf{Z}_{t}}\mathbf{X}_{t}$ and
noting that $\mathbf{P}_{t,\mathbf{Z}_{t}}$ is a symmetric and idempotent
matrix, so that
$\mathbf{P}_{t,\mathbf{Z}_{t}}^{\top}\mathbf{P}_{t,\mathbf{Z}_{t}}=\mathbf{P}_{t,\mathbf{Z}_{t}}\mathbf{P}_{t,\mathbf{Z}_{t}}=\mathbf{P}_{t,\mathbf{Z}_{t}}$
we have

$\displaystyle\boldsymbol{\beta}_{\textrm{2SLS},t}$
$\displaystyle=\left(\widehat{\mathbf{X}}_{t}^{\top}\widehat{\mathbf{X}}_{t}\right)^{-1}\widehat{\mathbf{X}}_{t}^{\top}\boldsymbol{y}_{t}=\left(\mathbf{X}_{t}^{\top}\mathbf{P}_{t,\mathbf{Z}_{t}}^{\top}\mathbf{P}_{t,\mathbf{Z}_{t}}\mathbf{X}_{t}\right)^{-1}\mathbf{X}_{t}^{\top}\mathbf{P}_{t,\mathbf{Z}_{t}}^{\top}\boldsymbol{y}_{t}$
$\displaystyle=\left(\mathbf{X}_{t}^{\top}\mathbf{P}_{t,\mathbf{Z}_{t}}\mathbf{X}_{t}\right)^{-1}\mathbf{X}_{t}^{\top}\mathbf{P}_{t,\mathbf{Z}_{t}}\boldsymbol{y}_{t}$
$\displaystyle=\boldsymbol{\beta}_{\textrm{GMM},t}$

∎

For brevity, in the proofs hereafter, we denote an $\mathsf{O\text{2}SLS}$
estimate at time $t$, i.e. $\boldsymbol{\beta}_{\text{2SLS},t}$ as
$\boldsymbol{\beta}_{t}$.

####  B.2 Parameter estimation and concentration in the first-stage

The first stage consists of a set of multiple regressions, which with the
choice of regularizer
$\lambda\operatorname{Tr}(\boldsymbol{\Theta}^{\prime\top}\boldsymbol{\Theta}^{\prime})$,
keeps the $d_{\boldsymbol{x}}$ regressions independent and corresponds to a
ridge regularization for each of them. The derivation of the confidence set is
an extension of the results from (Abbasi-Yadkori et al., 2011a, ) for the
first stage parameter and uses techniques from self-normalized processes to
estimate the confidence ellipsoid. Define

$L_{t}(\boldsymbol{\Theta}^{\prime})=\lambda\operatorname{Tr}\left(\boldsymbol{\Theta}^{\prime\top}\boldsymbol{\Theta}^{\prime}\right)+\sum_{s=1}^{t}\operatorname{Tr}\left(\left(\boldsymbol{x}_{s}-\boldsymbol{\Theta}^{\prime\top}\boldsymbol{z}_{s}\right)\left(\boldsymbol{x}_{s}-\boldsymbol{\Theta}^{\prime\top}\boldsymbol{z}_{s}\right)^{\top}\right).$

Let $\widehat{\boldsymbol{\Theta}}_{t}$ be the $\ell^{2}$-regularized least-
squares estimate of $\boldsymbol{\Theta}$ with regularization parameter
$\lambda>0$ :

$\displaystyle\widehat{\boldsymbol{\Theta}}_{t}=\underset{\boldsymbol{\Theta}^{\prime}}{\operatorname{argmin}}\,L_{t}(\boldsymbol{\Theta}^{\prime})=\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\>.$
(13)

######  Theorem B.4 (Confidence ellipsoid for columns in first-stage).

Consider the $\ell^{2}$-regularized least-squares parameter estimate
$\widehat{\boldsymbol{\Theta}}_{t}$ with regularization coefficient
$\lambda>0$. Let
$\mathbf{G}_{\boldsymbol{z},t}=\lambda\mathbf{I}_{d_{\boldsymbol{z}}}+\sum_{s=1}^{t}\boldsymbol{z}_{s}\boldsymbol{z}_{s}^{\top}$
be the regularized design matrix of the IVs and
$\operatorname{Tr}\left(\boldsymbol{\Theta}^{\top}\boldsymbol{\Theta}\right)\leq
S^{2}$. Define

$\sqrt{\beta_{t}(\delta)}=d_{\boldsymbol{x}}\sigma_{\boldsymbol{\epsilon}}\sqrt{2\log\left(\frac{\operatorname{det}\left(\mathbf{G}_{\boldsymbol{z},t}\right)^{1/2}\operatorname{det}(\lambda\mathbf{I}_{d_{\boldsymbol{z}}})^{-1/2}}{\delta}\right)}+\lambda^{1/2}S.$

Then, for any $0<\delta<1$, with probability at least $1-\delta$,

$\operatorname{Tr}\left(\left(\widehat{\boldsymbol{\Theta}}_{t}-\boldsymbol{\Theta}\right)^{\top}\mathbf{G}_{\boldsymbol{z},t}\left(\widehat{\boldsymbol{\Theta}}_{t}-\boldsymbol{\Theta}\right)\right)\leq\beta_{t}(\delta).$

In particular,
$\mathbb{P}\left(\boldsymbol{\Theta}\in\mathcal{C}_{t}(\delta),t=1,2,\ldots\right)\geq
1-\delta$, where

$\mathcal{C}_{t}(\delta)=\left\\{\boldsymbol{\Theta}\in\mathbb{R}^{d_{\boldsymbol{z}}\times
d_{\boldsymbol{x}}}:\operatorname{Tr}\left(\left(\boldsymbol{\Theta}-\widehat{\boldsymbol{\Theta}}_{t}\right)^{\top}\mathbf{G}_{\boldsymbol{z},t}\left(\boldsymbol{\Theta}-\widehat{\boldsymbol{\Theta}}_{t}\right)\right)\leq\beta_{t}(\delta)\right\\}.$

####  B.3 Elliptical lemma for the second-stage in endogeneous setting

######  Lemma 3.3 (Second-stage confidence ellipsoid for endogeneous setting).

Given an $\mathsf{O\text{2}SLS}$ estimate $\boldsymbol{\beta}_{t}$ at step
$t>0$, the true parameter $\boldsymbol{\beta}$ with probability at least
$1-\delta$ belongs to

$\mathcal{E}_{t}=\left\\{\boldsymbol{\beta}\in\mathbb{R}^{d_{\boldsymbol{x}}}:\|\boldsymbol{\beta}_{t}-\boldsymbol{\beta}\|_{\widehat{\mathbf{H}}_{t}}\leq\sqrt{\mathfrak{b}_{t}(\delta)}\right\\},$
(14)

Here, we define the second-stage design matrix to be
$\widehat{\mathbf{H}}_{t}\triangleq\widehat{\boldsymbol{\Theta}}_{t}^{\top}\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\widehat{\boldsymbol{\Theta}}_{t}$,
and the first-stage design matrix to be
$\mathbf{G}_{\boldsymbol{z},t}\triangleq\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}=\sum_{s=1}^{t}\boldsymbol{z}_{s}\boldsymbol{z}_{s}^{\top}+\mathbf{G}_{\boldsymbol{z},0}$
with $\mathbf{G}_{\boldsymbol{z},0}=\lambda\mathbf{I}_{d_{\boldsymbol{z}}}$
for any $t>0$, and

$\displaystyle\mathfrak{b}_{t}(\delta)$ $\displaystyle\triangleq
2{d_{\boldsymbol{z}}\sigma^{2}_{\eta}}\log\left(\frac{1+tL^{2}_{\boldsymbol{z}}/d_{\boldsymbol{z}}\lambda}{\delta}\right)\>.$
(15)

###### Proof.

Step 1: First, we start by observing the $\mathsf{O\text{2}SLS}$ estimate of
the second-stage parameter $\boldsymbol{\beta}$:

$\displaystyle\boldsymbol{\beta}_{t}$
$\displaystyle=\left(\mathbf{X}_{t}^{\top}\mathbf{Z}_{t}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)^{-1}\mathbf{X}_{t}^{\top}\mathbf{Z}_{t}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\boldsymbol{y}_{t}$
$\displaystyle=\boldsymbol{\beta}+\left(\mathbf{X}_{t}^{\top}\mathbf{Z}_{t}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)^{-1}\mathbf{X}_{t}^{\top}\mathbf{Z}_{t}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\boldsymbol{\eta}_{t}$

We would like to remind that following the classical GMM estimator, we assume
$\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}$ is invertible for any $t>0$, and
$\lambda_{\min}(\mathbf{Z}_{0}^{\top}\mathbf{Z}_{0})=\lambda>0$.

Step 2: Thus, for any vector
$\boldsymbol{x}\in\mathbb{R}^{d_{\boldsymbol{x}}}$, we can express

$\displaystyle\boldsymbol{x}^{\top}\left(\boldsymbol{\beta}_{t}-\boldsymbol{\beta}\right)$
$\displaystyle=\boldsymbol{x}^{\top}\left(\mathbf{X}_{t}^{\top}\mathbf{Z}_{t}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)^{-1}\left(\mathbf{X}_{t}^{\top}\mathbf{Z}_{t}\right)\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\boldsymbol{\eta}_{t}$
$\displaystyle=\boldsymbol{x}^{\top}\left(\widehat{\boldsymbol{\Theta}}_{t}^{\top}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{\top}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)\widehat{\boldsymbol{\Theta}}_{t}\right)^{-1}\left(\mathbf{X}_{t}^{\top}\mathbf{Z}_{t}\right)\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\boldsymbol{\eta}_{t}$
$\displaystyle=\boldsymbol{x}^{\top}\left(\widehat{\boldsymbol{\Theta}}_{t}^{\top}\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\widehat{\boldsymbol{\Theta}}_{t}\right)^{-1}\left(\mathbf{X}_{t}^{\top}\mathbf{Z}_{t}\right)\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\mathbf{Z}_{t}^{\top}\boldsymbol{\eta}_{t}$
$\displaystyle=\langle\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)\underbrace{(\widehat{\boldsymbol{\Theta}}_{t}^{\top}\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\widehat{\boldsymbol{\Theta}}_{t}}_{\widehat{\mathbf{H}}_{t}})^{-\top}\boldsymbol{x},(\underbrace{\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}}_{\mathbf{G}_{\boldsymbol{z},t}})^{-1}\mathbf{Z}_{t}^{\top}\boldsymbol{\eta}_{t}\rangle$
$\displaystyle=\left\langle\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)\widehat{\mathbf{H}}_{t}^{-\top}\boldsymbol{x},\mathbf{G}_{\boldsymbol{z},t}^{-1}\mathbf{Z}_{t}\boldsymbol{\eta}_{t}\right\rangle$
$\displaystyle\underset{(a)}{\leq}\lVert\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)\widehat{\mathbf{H}}_{t}^{-\top}\boldsymbol{x}\rVert_{{\mathbf{G}_{\boldsymbol{z},t}}^{-1}}\lVert{\mathbf{G}_{\boldsymbol{z},t}}^{-1}\mathbf{Z}_{t}\boldsymbol{\eta}_{t}\rVert_{{\mathbf{G}_{\boldsymbol{z},t}}}$
$\displaystyle\underset{(b)}{=}\lVert\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)\widehat{\mathbf{H}}_{t}^{-\top}\boldsymbol{x}\rVert_{{\mathbf{G}_{\boldsymbol{z},t}}^{-1}}\lVert\mathbf{Z}_{t}\boldsymbol{\eta}_{t}\rVert_{{\mathbf{G}_{\boldsymbol{z},t}}^{-1}}$
$\displaystyle=\left(\boldsymbol{x}^{\top}\widehat{\mathbf{H}}_{t}^{-1}(\mathbf{X}_{t}^{\top}\mathbf{Z}_{t})\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)\widehat{\mathbf{H}}_{t}^{-\top}\boldsymbol{x}\right)\lVert\mathbf{Z}_{t}\boldsymbol{\eta}_{t}\rVert_{{\mathbf{G}_{\boldsymbol{z},t}}^{-1}}$
$\displaystyle\underset{(c)}{=}\left(\boldsymbol{x}^{\top}\widehat{\mathbf{H}}_{t}^{-1}(\mathbf{X}_{t}^{\top}\mathbf{Z}_{t})\widehat{\boldsymbol{\Theta}}_{t}^{\top}\widehat{\mathbf{H}}_{t}^{-\top}\boldsymbol{x}\right)\lVert\mathbf{Z}_{t}\boldsymbol{\eta}_{t}\rVert_{{\mathbf{G}_{\boldsymbol{z},t}}^{-1}}$
$\displaystyle=\left(\boldsymbol{x}^{\top}\widehat{\mathbf{H}}_{t}^{-1}\widehat{\boldsymbol{\Theta}}_{t}^{\top}(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t})^{-1}\widehat{\boldsymbol{\Theta}}_{t}\widehat{\mathbf{H}}_{t}^{-\top}\boldsymbol{x}\right)\lVert\mathbf{Z}_{t}\boldsymbol{\eta}_{t}\rVert_{{\mathbf{G}_{\boldsymbol{z},t}}^{-1}}$
$\displaystyle=\left(\boldsymbol{x}^{\top}\widehat{\mathbf{H}}_{t}^{-1}\widehat{\mathbf{H}}_{t}\widehat{\mathbf{H}}_{t}^{-1}\boldsymbol{x}\right)\lVert\mathbf{Z}_{t}\boldsymbol{\eta}_{t}\rVert_{{\mathbf{G}_{\boldsymbol{z},t}}^{-1}}$
$\displaystyle=\lVert\boldsymbol{x}\rVert_{\widehat{\mathbf{H}}_{t}^{-1}}\lVert\mathbf{Z}_{t}\boldsymbol{\eta}_{t}\rVert_{{\mathbf{G}_{\boldsymbol{z},t}}^{-1}}$

Here, we define the first-stage design matrix to be
$\mathbf{G}_{\boldsymbol{z},t}\triangleq\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}$,
and the second-stage design matrix to be
$\widehat{\mathbf{H}}_{t}\triangleq\widehat{\boldsymbol{\Theta}}_{t}^{\top}\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\widehat{\boldsymbol{\Theta}}_{t}=\widehat{\boldsymbol{\Theta}}_{t}^{\top}\mathbf{G}_{\boldsymbol{z},t}\widehat{\boldsymbol{\Theta}}_{t}$
for any $t>0$.

Inequality (a) is obtained from the Cauchy-Schwartz inequality. Equality (b)
is due to the fact that
$\lVert\mathbf{A}^{-1}\boldsymbol{x}\rVert_{\mathbf{A}}=\lVert\boldsymbol{x}\rVert_{\mathbf{A}^{-1}}$.
Equality (c) is due to the definition of $\widehat{\boldsymbol{\Theta}}_{t}$
(Eq. (12)).

Step 3: Now, let us choose
$\boldsymbol{x}\triangleq\widehat{\mathbf{H}}_{t}\left(\boldsymbol{\beta}_{t}-\boldsymbol{\beta}\right)$.

This leads to

$\displaystyle\mathrm{LHS}=\left(\boldsymbol{\beta}_{t}-\boldsymbol{\beta}\right)^{\top}\widehat{\mathbf{H}}_{t}\left(\boldsymbol{\beta}_{t}-\boldsymbol{\beta}\right)=\left\|\boldsymbol{\beta}_{t}-\boldsymbol{\beta}\right\|^{2}_{\widehat{\mathbf{H}}_{t}},$

and

$\displaystyle\mathrm{RHS}$
$\displaystyle=\lVert\widehat{\mathbf{H}}_{t}(\boldsymbol{\beta}_{t}-\boldsymbol{\beta})\rVert_{\widehat{\mathbf{H}}_{t}^{-1}}\vvvert\mathbf{Z}_{t}\boldsymbol{\eta}_{t}\vvvert_{{\mathbf{G}_{\boldsymbol{z},t}}^{-1}}$
$\displaystyle=\lVert\boldsymbol{\beta}_{t}-\boldsymbol{\beta}\rVert_{\widehat{\mathbf{H}}_{t}}\vvvert\mathbf{Z}_{t}\boldsymbol{\eta}_{t}\vvvert_{{\mathbf{G}_{\boldsymbol{z},t}}^{-1}}$

Step 4: Combining the two results above lead to

$\displaystyle\left\|\boldsymbol{\beta}_{t}-\boldsymbol{\beta}\right\|_{\widehat{\mathbf{H}}_{t}}$
$\displaystyle\leq\left\|\mathbf{Z}_{t}\boldsymbol{\eta}_{t}\right\|_{\mathbf{G}_{\boldsymbol{z},t}^{-1}}$

We bound the last term assigning $\eta_{0}=0$, using Theorem A.15 for the
first inequality, and Lemma A.8 in the second inequality.

$\displaystyle\left\lVert\mathbf{Z}_{t}^{\top}\boldsymbol{\eta}_{t}\right\rVert_{\mathbf{G}_{\boldsymbol{z},t}^{-1}}=\left\lVert\sum_{s=1}^{t}\eta_{s}\boldsymbol{z}_{s}\right\rVert_{\mathbf{G}_{\boldsymbol{z},t}^{-1}}$
$\displaystyle\leq\sqrt{2\sigma_{\eta}^{2}\log\left(\frac{\operatorname{det}\left(\mathbf{G}_{\boldsymbol{z},t}\right)^{1/2}\lambda^{-d_{\boldsymbol{z}}/2}}{\delta}\right)}$
$\displaystyle\leq\sqrt{2{d_{\boldsymbol{z}}\sigma_{\eta}^{2}}\log\left(\frac{1+tL^{2}_{z}/d_{\boldsymbol{z}}\lambda}{\delta}\right)}.$

The second inequality is obtained from the concentration of the vector-valued
martingales with probability at least $1-\delta$. The final inequality is
obtained by assuming
$\mathbf{G}_{\boldsymbol{z},0}=\lambda\mathbf{I}_{d_{\boldsymbol{z}}}$. ∎

######  Remark B.5 ($t$ and $d$ dependence.).

We note that the ellipsoid bound has the following order in $d$ and $t$ while
neglecting the constants:

$\displaystyle\mathfrak{b}_{t}(\delta)$
$\displaystyle=\mathcal{O}\left(d_{\boldsymbol{z}}\log(t)\right).$

Thus, $\mathfrak{b}_{t}(\delta)$ is monotonically increasing with $t$. We
widely leverage this property in the proofs.

####  B.4 Concentration of the minimum eigenvalue of the design matrices

The aim of the section is to find a concentration result for the minimum
eigenvalue of the design matrix, which, in turn, gives us a concentration of
the $\ell_{2}$-norm of the inverse of the design matrix
$\left\vvvert\mathbf{G}_{\boldsymbol{z},t}^{-1}\right\vvvert_{2}$. We use a
classical concentration result for the covariance matrix Theorem A.14 together
with the bound on the difference of the minimum eigenvalues of two symmetric
matrices Lemma A.9 in order to bound the maximum eigenvalue of the inverse of
the design matrix.

######  Lemma B.6 (Well-behavedness of First-stage Design Matrix).

Let $\boldsymbol{z}_{1},\ldots,\boldsymbol{z}_{t}$ be i.i.d. zero-mean random
vectors with covariance $\boldsymbol{\Sigma}$ such that
$\left\|\boldsymbol{z}_{s}\right\|_{2}\leq L_{\boldsymbol{z}}$ almost surely.
We denote the regularised design matrix as
$\mathbf{G}_{\boldsymbol{z},t}=\lambda\mathbf{I}_{d_{\boldsymbol{z}}}+\sum_{s=1}^{t}\boldsymbol{z}_{s}\boldsymbol{z}_{s}^{\top}$.
For all $\delta>0$ and regularisation parameter $\lambda>0$, we observe that

$\displaystyle\left\vvvert\mathbf{G}_{\boldsymbol{z},t}^{-1}\right\vvvert_{2}=\operatorname{\lambda_{max}}\left(\mathbf{G}_{\boldsymbol{z},t}^{-1}\right)\leq\begin{cases}\frac{1}{\lambda}\text{
if }t\leq T_{0}\\\
\frac{2}{t\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})}\text{ if
}t>T_{0}\end{cases}.$

Here, $T_{0}>0$ is a constant defined by Equation (17) and
$\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})$ is the minimum
eigenvalue of the true covariance matrix of $\boldsymbol{z}$, i.e.
$\boldsymbol{\Sigma}\triangleq\mathbb{E}[\boldsymbol{z}\boldsymbol{z}^{\top}]$.

###### Proof.

First, we aim to find a lower bound for the smallest eigenvalue of the design,
matrix where we set the regularisation parameter $\lambda$ to zero. We denote
the ‘non-regularised’ design matrix as
$\mathbf{G}_{\boldsymbol{z},t}^{\lambda=0}$. For $t\geq 1$, we observe that
$\mathbf{G}_{\boldsymbol{z},t}^{\lambda=0}/t\triangleq\widehat{\boldsymbol{\Sigma}}_{t}$.
Thus, by applying Equation (10), we obtain

$\displaystyle\left|\operatorname{\lambda_{min}}\left(\nicefrac{{\mathbf{G}_{\boldsymbol{z},t}^{\lambda=0}}}{{t}}\right)-\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})\right|\leq\frac{4L_{\boldsymbol{z}}^{2}}{t}\log\left(\frac{2d_{\boldsymbol{z}}}{\delta}\right)+2\sqrt{\frac{2L_{\boldsymbol{z}}^{2}}{t}\log\left(\frac{2d_{\boldsymbol{z}}}{\delta}\right)\left\vvvert\boldsymbol{\Sigma}\right\vvvert_{2}}\,.$

Further substituting $A\triangleq
2L_{\boldsymbol{z}}^{2}\log\left(\frac{2d_{\boldsymbol{z}}}{\delta}\right)$
leads to the following lower bound for the minimum eigenvalue

$\displaystyle\operatorname{\lambda_{min}}\left(\mathbf{G}_{\boldsymbol{z},t}^{\lambda=0}\right)\geq\max\left\\{0,t\left(\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})-\nicefrac{{2A}}{{t}}-2\sqrt{\nicefrac{{A\operatorname{\lambda_{max}}\left(\boldsymbol{\Sigma}\right)}}{{t}}}\right)\right\\}.$

Here, $\operatorname{\lambda_{max}}(\mathbf{\boldsymbol{\Sigma}})$ and
$\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})$ is the maximum
and minimum eigenvalues of the true covariance matrix of $\boldsymbol{z}$,
i.e.
$\boldsymbol{\Sigma}\triangleq\mathbb{E}[\boldsymbol{z}\boldsymbol{z}^{\top}]$.

Now, from the variational definition of the minimum eigenvalues, we have
$\operatorname{\lambda_{min}}\left(\mathbf{G}_{\boldsymbol{z},t}\right)\geq\operatorname{\lambda_{min}}\left(\mathbf{G}_{\boldsymbol{z},t}^{\lambda=0}\right)+\lambda,$
which implies that
$\operatorname{\lambda_{min}}\left(\mathbf{G}_{\boldsymbol{z},t}\right)\geq\lambda$
for all $t\geq 0$, with equality for $t=0$. Thus, we have

$\displaystyle\operatorname{\lambda_{min}}\left(\mathbf{G}_{\boldsymbol{z},t}\right)$
$\displaystyle\geq\max\left\\{\lambda,\lambda+t\left(\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})-\nicefrac{{2A}}{{t}}-2\sqrt{\nicefrac{{A\operatorname{\lambda_{max}}\left(\boldsymbol{\Sigma}\right)}}{{t}}}\right)\right\\}.$
(16)

Let us consider the second term inside the maximum of Equation (16), and we
split it in the following way

$\displaystyle\lambda+t\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})-2A-2\sqrt{tA\operatorname{\lambda_{max}}\left(\boldsymbol{\Sigma}\right)}$
$\displaystyle=t\underbrace{\frac{\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})}{2}}_{\text{Term
(A)}}+\underbrace{\left(\frac{t\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})}{2}-2\sqrt{tA\operatorname{\lambda_{max}}\left(\boldsymbol{\Sigma}\right)}+\lambda-2A\right)}_{\text{Term
(B)}}$

Now we study for which values Term (B) is non-negative. The corresponding
second-order polynomial equation is obtained substituting $u=\sqrt{t}$, and is
$u^{2}\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})-4u\sqrt{A\operatorname{\lambda_{max}}\left(\boldsymbol{\Sigma}\right)}+2(\lambda-2A)=0\;,$
which has two solutions given by
$u_{\pm}=\nicefrac{{2\sqrt{A\operatorname{\lambda_{max}}\left(\boldsymbol{\Sigma}\right)}\pm\sqrt{4A\operatorname{\lambda_{max}}\left(\boldsymbol{\Sigma}\right)+2(2A-\lambda)\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})}}}{{\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})}}\;.$
In particular for $t>\lceil u_{+}\rceil$, $\text{Term (B)}\geq 0$, and
Equation 16 simplifies in

$\displaystyle\operatorname{\lambda_{min}}\left(\mathbf{G}_{\boldsymbol{z},t}\right)$
$\displaystyle\geq\max\left\\{\lambda,t\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})/2\right\\}.$

Therefore, for $t>\lceil
2\lambda/\operatorname{\lambda_{min}}(\boldsymbol{\Sigma})\rceil$ and
$t>\lceil u_{+}\rceil$ we have that
$\operatorname{\lambda_{min}}\left(\mathbf{G}_{\boldsymbol{z},t}\right)\geq
t\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})/2$.

Putting the results together, we conclude that

$\operatorname{\lambda_{min}}\left(\mathbf{G}_{\boldsymbol{z},t}\right)\geq
t\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})/2\quad\text{for}\quad
t>T_{0}\triangleq\max\left\\{\lceil
2\lambda/\operatorname{\lambda_{min}}(\boldsymbol{\Sigma})\rceil,\lceil
u_{+}\rceil\right\\},$ (17)

while for $t\leq T_{0}$, we retain the trivial lower bound of the minimum
eigenvalue, i.e. $\lambda$.

In summary, we have

$\displaystyle\operatorname{\lambda_{min}}\left(\mathbf{G}_{\boldsymbol{z},t}\right)\geq\begin{cases}\lambda\text{
if }t\leq T_{0}\\\
t\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})/2\text{ if
}t>T_{0}\end{cases}\iff\operatorname{\lambda_{max}}\left(\mathbf{G}_{\boldsymbol{z},t}^{-1}\right)\leq\begin{cases}\frac{1}{\lambda}\text{
if }t\leq T_{0}\\\
\frac{2}{t\operatorname{\lambda_{min}}(\mathbf{\boldsymbol{\Sigma}})}\text{ if
}t>T_{0}\end{cases}.$

∎

######  Corollary B.7 (Bound on the sum of maximum eigenvalues of the inverses
of the first-stage design matrices).

For every $T>0$, we have

$\displaystyle\sum_{s=0}^{T}\left\vvvert\mathbf{G}_{\boldsymbol{z},s}^{-1}\right\vvvert_{2}\leq
f(T)=\mathcal{O}(\log(T))\>,$

where
$f(t)\triangleq\frac{T_{0}+1}{\lambda}+\frac{2(\log(T)+1)}{\operatorname{\lambda_{min}}\left(\boldsymbol{\Sigma}\right)}$.

###### Proof.

For $T\leq T_{0}$,

$\sum_{s=0}^{T}\left\vvvert\mathbf{G}_{\boldsymbol{z},s}^{-1}\right\vvvert_{2}=\sum_{s=0}^{T}\frac{1}{\lambda}\leq\frac{T_{0}+1}{\lambda}=\mathcal{O}(1).$
(18)

If $T>T_{0}$

$\sum_{s=0}^{T}\left\vvvert\mathbf{G}_{\boldsymbol{z},s}^{-1}\right\vvvert_{2}=\sum_{s=0}^{T_{0}}\frac{1}{\lambda}+\sum_{s=T_{0}+1}^{T}\frac{2}{\operatorname{\lambda_{min}}\left(\boldsymbol{\Sigma}\right)s}\leq\frac{T_{0}+1}{\lambda}+\frac{2(\log(T)+1)}{\operatorname{\lambda_{min}}\left(\boldsymbol{\Sigma}\right)}=\mathcal{O}(\log(T))$
(19)

where the last inequality follows from
$\sum_{k=1}^{n}\frac{1}{k}\leq\int_{1}^{n}\frac{dx}{x}+1=\log(n)+1$. ∎

####  B.5 Upper bounding the feature norms

In this section, we present some useful Lemmas that we used in the proofs of
the regret bounds of $\mathsf{O\text{2}SLS}$ and $\mathsf{OFUL\text{-}IV}$.

######  Remark B.8.

In Section B.2, we describe that the first stage regression in
$\mathsf{O\text{2}SLS}$ can be expressed as running $d$ independent ridge
regressions for each column of $\boldsymbol{\Theta}$ (Equation (13)). Since
the standard analysis of each of the ridge regressions assume independent and
sub-Gaussian noise added in the linear model (cf. Theorem B.4; (Ouhamma et
al.,, 2021)), we assume that each component of the first stage noise, i.e.
$\boldsymbol{\epsilon}_{t,i}$, corresponding to the $i$-th ridge regression is
$\operatorname{sub-Gauss(\sigma_{\boldsymbol{\epsilon}})}$. Thus, we obtain
that $\mathbb{E}\lVert\boldsymbol{\epsilon}_{t}\rVert^{2}_{2}\leq
d_{\boldsymbol{x}}\sigma_{\boldsymbol{\epsilon}}^{2}$. We use this result
throughout this section.

######  Lemma B.9 (Bounding the First-stage Estimates).

Under Assumptions 2.1 and IVs being bounded $\|\boldsymbol{z}\|_{2}^{2}\leq
L_{\boldsymbol{z}}^{2}$, the minimum singular value of the estimated parameter
in the first-stage regression (Equation 13) is lower bounded by:

$\displaystyle\sigma_{\min}(\widehat{\boldsymbol{\Theta}}_{t})\geq\frac{\mathfrak{r}^{2}}{L_{\boldsymbol{z}}^{2}}$
(20)

###### Proof.

We start with the variational definition of the minimum singular value and
then we lower bound this quantity:

$\displaystyle\sigma_{\min}(\widehat{\boldsymbol{\Theta}}_{t})$
$\displaystyle=\sigma_{\min}\left(\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)\right)$
$\displaystyle=\min_{\boldsymbol{v}\in\mathbb{S}^{d_{\boldsymbol{x}}-1}}\lVert\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)\boldsymbol{v}\rVert_{2}$
$\displaystyle\underset{(a)}{=}\min_{\boldsymbol{v}\in\mathbb{S}^{d_{\boldsymbol{x}}-1}}\frac{\lVert\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)\boldsymbol{v}\rVert_{2}}{\lVert\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)\boldsymbol{v}\rVert_{2}}\lVert\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)\boldsymbol{v}\rVert_{2}$
$\displaystyle\geq\sigma_{\min}\left(\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\right)\sigma_{\min}\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)$
$\displaystyle=\lambda_{\min}\left(\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)^{-1}\right)\sigma_{\min}\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)$
$\displaystyle=\frac{\sigma_{\min}\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)}{\lambda_{\max}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)}\>.$

$(a)$ holds because according to 2.1 it is assumed that
$\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)$ has maximum rank and
therefore we are not dividing by a zero norm vector. Then, by the variational
definition of the biggest eigenvalue

$\displaystyle\lambda_{\max}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)$
$\displaystyle=\max_{\boldsymbol{v}\in\mathbb{S}^{d_{\boldsymbol{z}}-1}}\left\langle\boldsymbol{v},\sum_{s=1}^{t}\boldsymbol{z}_{s}\boldsymbol{z}_{s}^{\top}\boldsymbol{v}\right\rangle=\max_{\boldsymbol{v}\in\mathbb{S}^{d_{\boldsymbol{z}}-1}}\sum_{s=1}^{t}\left\langle\boldsymbol{v},\boldsymbol{z}_{s}\right\rangle^{2}\leq\sum_{s=1}^{t}\lVert\boldsymbol{z}_{s}\rVert_{2}^{2}\leq
tL_{\boldsymbol{z}}^{2}$

Finally, we note that the quantity
$\sigma_{\min}\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)\geq
t\mathfrak{r}$ by the definition of relevance, which implies

$\displaystyle\sigma_{\min}(\widehat{\boldsymbol{\Theta}}_{t})$
$\displaystyle=\frac{\sigma_{\min}\left(\mathbf{Z}_{t}^{\top}\mathbf{X}_{t}\right)}{\lambda^{2}_{\max}\left(\mathbf{Z}_{t}^{\top}\mathbf{Z}_{t}\right)}\geq\frac{t\mathfrak{r}^{2}}{tL_{\boldsymbol{z}}^{2}}\geq\frac{\mathfrak{r}^{2}}{L_{\boldsymbol{z}}^{2}}\>.$

∎

######  Lemma B.10 (Bounding the impact of first-stage noise).

For first stage noises that is component-wise sub-
Gaussian($\sigma_{\boldsymbol{\epsilon}}$), and bounded IVs, i.e.
$\lVert\boldsymbol{z}\rVert_{2}^{2}\leq L_{\boldsymbol{z}}^{2}$, we have that

$\displaystyle\sum_{t=1}^{T}\left\|\boldsymbol{\epsilon}_{t}\right\|_{\widehat{\mathbf{H}}_{t-1}^{-1}}^{2}$
$\displaystyle\leq\underbrace{\frac{\mathfrak{r}^{2}}{L_{\boldsymbol{z}}^{2}}\left(d_{\boldsymbol{x}}\sigma^{2}_{\boldsymbol{\epsilon}}f(T)+C_{5}\right)}_{\text{O}(d_{\boldsymbol{x}}\log
T)}$

with probability at least $1-\delta$. Here, $C_{5}$ is a constant of
$\text{O}(d_{\boldsymbol{x}})$ as defined in Equation 22.

###### Proof.

The proof follows using chain of inequalities

$\displaystyle\sum_{t=1}^{T}\left\|\boldsymbol{\epsilon}_{t}\right\|_{\widehat{\mathbf{H}}_{t-1}^{-1}}^{2}$
$\displaystyle\leq\sum_{t=1}^{T}\left\|\boldsymbol{\epsilon}_{t}\right\|_{2}^{2}\lambda_{\max}\left({\widehat{\mathbf{H}}_{t-1}^{-1}}\right)$
$\displaystyle\leq\sum_{t=1}^{T}\frac{\lVert\boldsymbol{\epsilon}_{t}\rVert^{2}_{2}}{\operatorname{\lambda_{min}}\left(\mathbf{G}_{\boldsymbol{z},t-1}\right)\>\sigma_{\min}\left({\widehat{\boldsymbol{\Theta}}_{t-1}}\right)}$
$\displaystyle\leq\frac{\mathfrak{r}^{2}}{L_{\boldsymbol{z}}^{2}}\sum_{t=1}^{T}\frac{\lVert\boldsymbol{\epsilon}_{t}\rVert^{2}_{2}}{\operatorname{\lambda_{min}}\left(\mathbf{G}_{\boldsymbol{z},t-1}\right)}$
$\displaystyle\leq\frac{\mathfrak{r}^{2}}{L_{\boldsymbol{z}}^{2}}\left(\underbrace{\sum_{t=1}^{T}\left\vvvert\mathbf{G}_{\boldsymbol{z},t-1}^{-1}\right\vvvert_{2}\left(\left\|\boldsymbol{\epsilon}_{t}\right\|_{2}^{2}-\mathbb{E}\left\|\boldsymbol{\epsilon}_{t}\right\|_{2}^{2}\right)}_{\textbf{Term
I}}+\underbrace{\sum_{t=1}^{T}\left\vvvert\mathbf{G}_{\boldsymbol{z},t-1}^{-1}\right\vvvert_{2}\mathbb{E}\left\|\boldsymbol{\epsilon}_{t}\right\|_{2}^{2}}_{\textbf{Term
II}}\right)$

##### Term I:

The squared $\ell_{2}$-norms of sub-Gaussian random variables are sub-
exponential (Wainwright,, 2019), therefore
$\left\|\boldsymbol{\epsilon}_{t}\right\|_{2}^{2}-\mathbb{E}\left\|\boldsymbol{\epsilon}_{t}\right\|_{2}^{2}\sim\operatorname{sub-
exp}(\nu,\alpha)$ where the correct values of $\nu,\alpha$ are derived in
Lemma A.12, in the result on the square of sub-Gaussians variables, and gives
$\nu\triangleq 4\sqrt{2}d_{\boldsymbol{x}}\sigma^{2}_{\boldsymbol{\epsilon}}$
and $\alpha\triangleq 4\sigma^{2}_{\boldsymbol{\epsilon}}$. Furthermore, given
an $X\sim\operatorname{sub-exp}(\nu,\alpha)$ and a constant $c$, then
$\nicefrac{{X}}{{c}}\sim\operatorname{sub-
exp}\left(\nicefrac{{v}}{{c}},\nicefrac{{c}}{{\alpha}}\right)$ which follows
by considering a new parameter $\lambda/c$ in the definitions of sub-
exponentiality $\mathbb{E}\left[e^{\lambda X/c}\right]\leq
e^{\lambda^{2}\nu^{2}/2c^{2}}$, where $|\lambda/c|\leq\frac{1}{\alpha}$ iff
$|\lambda|\leq\frac{c}{\alpha}$ Using this, we rescale by the factor $t$

$\displaystyle\mathbb{P}\left[\sum_{t=T_{0}}^{T}\frac{\left\|\boldsymbol{\epsilon}_{t}\right\|_{2}^{2}-\mathbb{E}\left\|\boldsymbol{\epsilon}_{t}\right\|_{2}^{2}}{t}\geq\mu\right]$
$\displaystyle\underset{(a)}{\leq}\mathbb{E}\left[e^{\lambda\sum_{t=T_{0}}^{T}\frac{\left\|\boldsymbol{\epsilon}_{t}\right\|^{2}-\mathbb{E}\left\|\epsilon_{t}\right\|^{2}}{t}}\right]e^{-\lambda\mu}$
$\displaystyle\underset{(b)}{\leq}e^{\sum_{t=T_{0}}^{T}\lambda^{2}\nu^{2}/2t^{2}-\lambda\mu}$
$\displaystyle\underset{(c)}{\leq}e^{\frac{\lambda^{2}\nu^{2}}{2}\left(\frac{1}{T_{0}-1}-\frac{1}{T}\right)-\lambda\mu}$

where (a) is Markov’s inequality, (b) uses the product rule for expectations
and
$\left\|\boldsymbol{\epsilon}_{t}\right\|_{2}^{2}-\mathbb{E}\left\|\boldsymbol{\epsilon}_{t}\right\|_{2}^{2}\sim\operatorname{sub-
exp}(\nu=4\sqrt{2}d_{\boldsymbol{x}}\sigma^{2}_{\boldsymbol{\epsilon}},\alpha=4\sigma^{2}_{\boldsymbol{\epsilon}})$,
and (c) holds $\forall|\lambda|\leq\frac{m}{\alpha}$ thanks to the following
series of inequalities
$\sum_{T_{0}}^{T}\frac{1}{t^{2}}\leq\int_{t_{0}-1}^{T}1/t^{2}dt=(-\frac{1}{t}|_{T_{0}-1}^{T}=-\frac{1}{T}+\frac{1}{T_{0}-1}.$
This proves that

$\sum_{t=T_{0}}^{T}\frac{\left\|\eta_{t}\right\|_{2}^{2}-\mathbb{E}\left\|\eta_{t}\right\|_{2}^{2}}{t}\sim\operatorname{sub-
exp}\Big{(}{\nu\sqrt{\frac{1}{T_{0}-1}-\frac{1}{T}}},{\frac{T_{0}}{\alpha}}\Big{)}$
(21)

We bound the following summation using Lemma B.6:

$\sum_{t=1}^{T}\left\vvvert\mathbf{G}_{\boldsymbol{z},t-1}^{-1}\right\vvvert_{2}\left(\left\|\boldsymbol{\epsilon}_{t}\right\|_{2}^{2}-\mathbb{E}\left\|\boldsymbol{\epsilon}_{t}\right\|_{2}^{2}\right)\\\
\begin{aligned}
&=\sum_{t=0}^{T_{0}}\operatorname{\lambda_{max}}\left(\mathbf{G}_{\boldsymbol{z},t}^{-1}\right)\left(\left\|\boldsymbol{\epsilon}_{t+1}\right\|_{2}^{2}-\mathbb{E}\left\|\boldsymbol{\epsilon}_{t+1}\right\|_{2}^{2}\right)+\sum_{t=T_{0}+1}^{T-1}\operatorname{\lambda_{max}}\left(\mathbf{G}_{\boldsymbol{z},t}^{-1}\right)\left(\left\|\boldsymbol{\epsilon}_{t+1}\right\|_{2}^{2}-\mathbb{E}\left\|\boldsymbol{\epsilon}_{t+1}\right\|_{2}^{2}\right)\\\
&\leq\frac{1}{\lambda}\sum_{t=0}^{T_{0}}\left(\left\|\boldsymbol{\epsilon}_{t+1}\right\|_{2}^{2}-\mathbb{E}\left\|\boldsymbol{\epsilon}_{t+1}\right\|_{2}^{2}\right)+\frac{2}{\operatorname{\lambda_{min}}\left(\boldsymbol{\Sigma}\right)}\sum_{t=T_{0}+1}^{T-1}\frac{\left\|\boldsymbol{\epsilon}_{t+1}\right\|_{2}^{2}-\mathbb{E}\left\|\boldsymbol{\epsilon}_{t+1}\right\|_{2}^{2}}{t}\\\
&\leq\frac{T_{0}+1}{\lambda}\left(4\sqrt{2}\sigma^{2}_{\boldsymbol{\epsilon}}d_{\boldsymbol{x}}\sqrt{2\log(1/\delta)}+\frac{1}{2\sigma^{2}_{\boldsymbol{\epsilon}}}\log(1/\delta)\right)\\\
&\qquad\qquad\qquad+\frac{2}{\operatorname{\lambda_{min}}\left(\boldsymbol{\Sigma}\right)}\left(\sqrt{2\nu^{2}\left(\frac{1}{T_{0}}-\frac{1}{T}\right)\log(1/\delta)}+\frac{2T_{0}}{\alpha}\log(1/\delta)\right)\end{aligned}$

Since Term I can be upper-bounded by a constant
$\text{O}(d_{\boldsymbol{x}})$, we just name this constant $C_{5}$ where we
also substitute back the definitions
$\nu=4\sqrt{2}d_{\boldsymbol{x}}\sigma^{2}_{\boldsymbol{\epsilon}}$ and
$\alpha=4\sigma^{2}_{\boldsymbol{\epsilon}}$. Specifically,

Term I
$\displaystyle\leq\frac{T_{0}+1}{\lambda}\left(4\sqrt{2}d_{\boldsymbol{x}}\sigma^{2}_{\boldsymbol{\epsilon}}\sqrt{2\log(1/\delta)}+\frac{1}{2\sigma^{2}_{\boldsymbol{\epsilon}}}\log(1/\delta)\right)$
$\displaystyle\quad\quad\quad\quad\quad+\frac{2}{\operatorname{\lambda_{min}}\left(\boldsymbol{\Sigma}\right)}\left(4\sqrt{2}d_{\boldsymbol{x}}\sigma^{2}_{\boldsymbol{\epsilon}}\sqrt{\frac{2}{T_{0}}\log(1/\delta)}+\frac{2T_{0}}{4\sigma^{2}_{\boldsymbol{\epsilon}}}\log(1/\delta)\right)\triangleq
C_{5},$ (22)

which is a $T$-independent constant of
$\text{O}(d_{\boldsymbol{x}}\sigma_{\boldsymbol{\epsilon}}^{2})$.

##### Term II:

The proof step-wise applies: (d) sub-Gaussianity of
$\boldsymbol{\epsilon}_{t}$, (e) the high-probability bound on the sum of the
minimum eigenvalue of the first-stage design matrix in Corollary B.7

Term II