Riccardo Della Vecchia

Debabrota Basu

Online Instrumental Variable Regression Online Instrumental Variable Regression: Regret Analysis and Bandit Feedback

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Online regression is a founding component of online learning [START_REF] Kivinen | Online learning with kernels[END_REF], sequential testing [START_REF] Kazerouni | Best arm identification in generalized linear bandits[END_REF], contextual bandits [START_REF] Foster | Beyond UCB: Optimal and efficient contextual bandits with regression oracles[END_REF], and reinforcement learning [START_REF] Ouhamma | Bilinear exponential family of mdps: Frequentist regret bound with tractable exploration and planning[END_REF]. Specially, online linear regression is widely used and analysed to design efficient algorithms with theoretical guarantees [START_REF] William H Greene | Econometric analysis[END_REF]Abbasi-Yadkori et al., 2011b;[START_REF] Hazan | Linear regression with limited observation[END_REF]. In linear regression, the outcome (or output variable) Y ∈ R, and the input features (or covariates, or treatments) X ∈ R d are related by a structural equation:

Y = β T X + η,
where β is the true parameter and η is the observational noise with variance σ 2 . The goal is to estimate β from an observational dataset. Two common assumptions in the analysis of linear regression are (i) bounded observations and covariates [START_REF] Vovk | Competitive on-line linear regression[END_REF][START_REF] Peter L Bartlett | Minimax fixed-design linear regression[END_REF][START_REF] Gaillard | Uniform regret bounds over R d for the sequential linear regression problem with the square loss[END_REF], and (ii) exogeneity, i.e. independence of the noise η and the input features X (E[η|X] = 0) (Abbasi-Yadkori et al., 2011b;[START_REF] Ouhamma | Stochastic online linear regression: the forward algorithm to replace ridge[END_REF]. Under exogeneity, researchers have studied scenarios, where the observational noise is unbounded and has only bounded variance σ 2 . [START_REF] Ouhamma | Stochastic online linear regression: the forward algorithm to replace ridge[END_REF] show that the unbounded stochastic setting asks for different technical analysis than the bounded adversarial setting popular in online regression literature. Additionally, in real-life, exogeneity is often violated, and we encounter endogeneity, i.e. dependence between noise and covariates (E[η|X] ̸ = 0) [START_REF] William H Greene | Econometric analysis[END_REF][START_REF] Angrist | Identification of causal effects using instrumental variables[END_REF]. Endogeneity arises due to omitted explanatory variables, measurement errors, dependence of the output and the covariates on unobserved confounding variables etc. [START_REF] Wald | The fitting of straight lines if both variables are subject to error[END_REF][START_REF] Mogstad | The causal interpretation of two-stage least squares with multiple instrumental variables[END_REF][START_REF] Zhu | Causal inference with treatment measurement error: a nonparametric instrumental variable approach[END_REF]. In this paper, we analyse online linear regression that aims to estimate β accurately from endogeneous observational data, where the noise is stochastic and unbounded.

Instrumental Variable Regression. Historically, Instrumental Variables (IVs) are introduced to identify and quantify the causal effects of endogenous covariates [START_REF] Whitney | Instrumental variable estimation of nonparametric models[END_REF]. IVs are widely used in economics [START_REF] Philip | Tariff on animal and vegetable oils[END_REF][START_REF] Mogstad | The causal interpretation of two-stage least squares with multiple instrumental variables[END_REF], causal inference [START_REF] Donald B Rubin | Estimating causal effects of treatments in randomized and nonrandomized studies[END_REF][START_REF] Ma Hernan | Causal Inference: What if[END_REF][START_REF] Harris | Strategic instrumental variable regression: Recovering causal relationships from strategic responses[END_REF], bio-statistics and epidemiology [START_REF] Burgess | A review of instrumental variable estimators for mendelian randomization[END_REF].

Example 1.1. [START_REF] Carneiro | Estimating marginal returns to education[END_REF]; [START_REF] Mogstad | The causal interpretation of two-stage least squares with multiple instrumental variables[END_REF] aim to estimate the number of returning students to college using the National Longitudinal Survey of Youth data. The return depends on multiple covariates X, such as whether the individual attended college, her AFQT scores, her family income, her family conditions (mother's years of education, number of siblings etc.). Often the family conditions have unobserved confounding effects on the college attendance and scores. This endogenous nature of data leads to bias in traditional linear regression estimates, such as Ordinary Least Squares (OLS). To mitigate this issue, [START_REF] Carneiro | Estimating marginal returns to education[END_REF]; [START_REF] Mogstad | The causal interpretation of two-stage least squares with multiple instrumental variables[END_REF] leverage two IVs (Z): average log income in the youth's county of residence at age 17, and the presence of a four-year college in the youth's county of residence at age 141 . The logic is that a youth might find going to college more attractive when labour market opportunities are weaker and a college is nearby. Using these two IVs, the youth's attendance to college is estimated. Then, in the next stage this estimate of college attendance is used with family conditions to predict the return of the youth to college. This two stage regression approach with IVs produces a more accurate estimate of youths' return to the college than OLS models assuming exogeneity.

This approach to conduct two stages of linear regression using instrumental variables is called Two Stage Least Squares Regression (2SLS) [START_REF] Joshua | Two-stage least squares estimation of average causal effects in models with variable treatment intensity[END_REF][START_REF] Angrist | Identification of causal effects using instrumental variables[END_REF]. 2SLS 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 2SLS techniques to nonlinear structures, non-compliant instruments, and corrupted observations using deep learning [START_REF] Liu | On deep instrumental variables estimate[END_REF][START_REF] Xu | Learning deep features in instrumental variable regression[END_REF][START_REF] Xu | Deep proxy causal learning and its application to confounded bandit policy evaluation[END_REF], graphical models [START_REF] Stirn | Thompson sampling for noncompliant bandits[END_REF], and kernel regression [START_REF] Zhu | Causal inference with treatment measurement error: a nonparametric instrumental variable approach[END_REF], respectively. The existing analysis of 2SLS are asymptotic, i.e. what can be learned if we have access to infinite number of samples in an offline setting [START_REF] Singh | Machine learning instrument variables for causal inference[END_REF][START_REF] Liu | On deep instrumental variables estimate[END_REF][START_REF] Nareklishvili | Deep partial least squares for iv regression[END_REF]. 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 [START_REF] Venkatraman | Online instrumental variable regression with applications to online linear system identification[END_REF]. This setting motivates us to analyse the online extension of 2SLS, referred as O2SLS.

Additionally, in an interactive setting, if a policy maker aims to build more schools at some of the lower income areas as a form of intervention, she observes only the changes corresponding to it. This is referred as bandit feedback in online learning literature and studied under the linear bandit formulation (Abbasi-Yadkori et al., 2011a). This motivates us to further extend O2SLS to linear bandits, where bandit feedback and endogeneity occur simultaneously.

In this paper, we investigate these two questions:

1. What is the upper bound on the loss in performance for deploying parameters estimated by O2SLS instead of the true parameters β? How estimating the true parameters β influence different performance metrics under endogeneity?

2. Can we design efficient algorithms for linear bandits with endogeneity by using O2SLS? Our Contributions. Our investigation has led to 1. A Non-asymptotic Analysis of O2SLS: First, we identify three notions of regret: identification regret, oracle regret, and population regret. Though all of them are of same order under endeogeneity, 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 {β t } T t=1 , and the true parameter β, and oracle regret, i.e. the sum of differences between the losses incurred by the estimated parameters {β t } T t=1 , and the true parameter β. In Section 4, we theoretically show that O2SLS achieve O(d 2 log 2 T ) identification regret and O(d 2 log 2 T + γ √ dT log T ) oracle regret after receiving T samples from the observational data. Identification regret of O2SLS is d log T multiplicative factor higher than regret of online linear regression under exogeneity, and oracle regret is O(γ √ dT log T ) additive factor higher. These are the costs that O2SLS pay for tackling endogeneity in two stages. In our knowledge, we are the first to propose a non-asymptotic regret analysis of O2SLS with stochastic and unbounded noise.

2. OFUL-IV for Linear Bandits with Endogeneity: In Section 5, we study the linear bandit problem with endogeneity. We design an extension of OFUL algorithm used for linear bandit with exogeneity, namely OFUL-IV, to tackle this problem. OFUL-IV uses O2SLS to estimate the parameters, and corresponding confidence bounds on β to balance exploration-exploitation. We show that OFUL-IV achieve O(d √ T log T ) regret after T interactions. We experimentally show that OFUL-IV incur lower regret than OFUL under endogeneity (end of Section 5).

Related Work

Online Regression without Endogeneity. Our analysis of O2SLS extends the tools and techniques of online linear regression without endogeneity. Analysis of online linear regression began with [START_REF] Dean | Prediction in the worst case[END_REF][START_REF] Littlestone | On-line learning of linear functions[END_REF]. [START_REF] Vovk | Competitive on-line linear regression[END_REF][START_REF] Vovk | Competitive on-line statistics[END_REF] show that forward and ridge regressions achieve O(dY2 max log T ) for outcomes with bound Y max . [START_REF] Peter L Bartlett | Minimax fixed-design linear regression[END_REF] generalise the analysis further by considering the features known in hindsight. [START_REF] Gaillard | Uniform regret bounds over R d for the sequential linear regression problem with the square loss[END_REF] 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. [START_REF] Ouhamma | Stochastic online linear regression: the forward algorithm to replace ridge[END_REF] 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 2SLS 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.

Linear Bandits without Endogeneity. Linear bandits generalise the setting of online linear regression under bandit feedback (Abbasi-Yadkori et al., 2011a, 2012;[START_REF] Foster | Beyond UCB: Optimal and efficient contextual bandits with regression oracles[END_REF]. 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 optimismin-the-face-of-uncertainty and Thompson sampling, are extended to propose OFUL [START_REF] Abbasi-Yadkori | Online-to-confidence-set conversions and application to sparse stochastic bandits[END_REF] and LinTS [START_REF] Abeille | Linear thompson sampling revisited[END_REF], respectively. OFUL and LinTS algorithms demonstrate O(d √ T log T ) and O(d 1.5 √ T log T ) regret guarantees under exogeneity assumption. Here, we use O2SLS as a regression oracle to develop OFUL-IV for linear bandits with endogeneity. We prove that OFUL-IV achieves O(d √ T log T ) regret. Instrument-armed Bandits. Kallus (2018) is the first to study endogeneity, and instrumental variables in stochastic bandit setting. [START_REF] Stirn | Thompson sampling for noncompliant bandits[END_REF] propose a Thompson sampling-type algorithm for stochastic bandits, where endogeneity arises due to non-compliant actions. But both Kallus (2018) and [START_REF] Stirn | Thompson sampling for noncompliant bandits[END_REF] 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.

Preliminaries: Instrumental Variables & Offline Two-stage Least Squares (2SLS)

We are given an observational dataset {x i , y i } n i=1 consisting of n pairs of input features and outcomes, such that y i ∈ R and x i ∈ R d . 2 These inputs and outcomes are stochastically generated using a linear model

y i = β ⊤ x i + η i , ( Second stage)
where β ∈ R d is the unknown true parameter vector of the linear model, and η i ∼ N (0, σ 2 η ) is the unobserved error term representing all causes of y i other than x i . It is assumed that the error terms η i are independently and identically distributed, and have bounded variance σ 2 . The parameter Figure 1: The DAG for 2SLS. The unobserved noises are ϵ and η (in grey), while z, x, y are observed quantities.

vector β quantifies the causal effect on y i due to a unit change in a component of x i , while retaining other causes of y i constant. The goal of linear regression is to estimate β by minimising the square loss over the dataset [START_REF] Brier | Verification of forecasts expressed in terms of probability[END_REF]

, i.e. β ≜ argmin β ′ i=1 (y i -β ′⊤ x i ) 2 .
The obtained solution is called the Ordinary Least Square (OLS) estimate of β [START_REF] Wasserman | All of statistics: a concise course in statistical inference[END_REF], and used as a corner stone of online regression [START_REF] Gaillard | Uniform regret bounds over R d for the sequential linear regression problem with the square loss[END_REF] and linear bandit algorithms [START_REF] Foster | Beyond UCB: Optimal and efficient contextual bandits with regression oracles[END_REF]. Specifically, if the input feature matrix X n ∈ R n×d is defined as [x 1 , x 2 , . . . , x n ] ⊤ , the outcome vector is y n ≜ [y 1 , . . . , y n ] ⊤ , and the noise vector is η n ≜ [η 1 , . . . , η n ] ⊤ , the OLS estimator is expressed as

β OLS ≜ (X ⊤ n X n ) -1 X ⊤ n y n = β + (X ⊤ n X n ) -1 X ⊤ n η n
If X n and η n are independent, the second term has zero expected value conditioned on X n . Hence, the OLS estimator is asymptotically unbiased, i.e. β OLS → ∞ as n → ∞.

In practice, the input features x and the noise η are often correlated (Greene, 2003, Chapter 8). As in Figure 1, this dependence, called endogeneity, is modelled with a confounding unobserved random variable ϵ. To compute an unbiased estimate of β under endogeneity, a popular technique is to introduce the Instrumental Variables (IVs) z [START_REF] Angrist | Identification of causal effects using instrumental variables[END_REF][START_REF] Whitney | Instrumental variable estimation of nonparametric models[END_REF]. IVs are chosen such that they are highly correlated with endogenous components of x (relevance condition) but are independent of the noise η (exogeneity condition for z).

This leads to the Two-stage Least Squares (2SLS) approach to IV regression [START_REF] Joshua | Two-stage least squares estimation of average causal effects in models with variable treatment intensity[END_REF][START_REF] Angrist | Identification of causal effects using instrumental variables[END_REF]. Here, we further assume that IVs, i.e. Z n ≜ [z 1 , . . . , z n ] ⊤ , cause linear effects on the endogenous covariates. Specifically, for the just-identified IVs,

X n = Z n Θ + E n , ( First stage)
where Θ ∈ R d×d is an unknown first-stage parameter matrix and E n ≜ [ϵ 1 , . . . , ϵ n ] ⊤ is the unobserved noise matrix leading to confounding in the second stage. This is a "classic" multiple regression, where the covariates z are independent of the noise terms ϵ ∼ N (0, σ 2 ϵ I d ) (Wasserman, 2004, Ch. 13). Thus, the first-stage is amenable to OLS regression. This formulation leads us to the 2SLS estimator:

β 2SLS = Z ⊤ n X n -1 Z ⊤ n y n . (2SLS)
As long as E[z i η i ] = 0 in the true model, we observe that

β 2SLS = Z ⊤ n X n -1 Z ⊤ n X n β + Z ⊤ n X n -1 Z ⊤ n η n p → β,
as n → ∞. This works because IV solves for the unique parameter that satisfies 1 n Z ⊤ n η p → 0. Since x and η are correlated, 2SLS estimator is not unbiased in finite-time.

Assumption 3.1. The assumptions for conducting 2SLS with just-identified IVs are [START_REF] William H Greene | Econometric analysis[END_REF]:

1. Well behaved data. For every n ∈ N, the matrices Z ⊤ n Z n and Z ⊤ n X n are full rank, and thus invertible. 2. Endogeneity of x. The second stage input features x and noise η are not independent:

x ̸ ⊥ ⊥ η. 3. Exogeneity of z. The IV random variables are independent of the noise in the second stage:

z ⊥ ⊥ η. 4. Relevance Condition. The variables z and x are correlated: z ̸ ⊥ ⊥ x. This implies that there exists r > 0:

n Z ⊤ n X n -1 2 ≤ 1 r .
(1)

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 O2SLS. Following that, we first define two notions of regret: identification and oracle, aimed at estimating the true parameter and producing accurate predictions. We provide a theoretical analysis of O2SLS and upper bound the two types of regret (Section 4.2). O2SLS. In the online setting of IV regression, the data (x 1 , z 1 , y 1 ), . . . , (x T , z T , y T ), . . . arrives in a stream. Following the 2SLS model (Figure 1), data is generated from

x t = Θ ⊤ z t + ϵ t y t = β ⊤ x t + η t , (2)
such that x t ̸ ⊥ ⊥ η t and z t ⊥ ⊥ η t for all t ∈ N. At each step t, the online IV regression algorithm is served with a new input feature x t and an IV z t , and it aims to predict an outcome ŷt ≜ β ⊤ t x t ∈ R. Here, β t is the estimate of the parameter at step t computed using current (x t , z t ) and the data {(x i , z i , y i )} i=1 observed so far. Following the prediction, Nature reveals the true outcome y t . Quality of the prediction is evaluated using a square loss ℓ t (β t ) ≜ ( y t -y t ) 2 [START_REF] Dean | Prediction in the worst case[END_REF]. The online protocol is the following.

At each round t = 1, 2, . . . , T 1. z t is sampled i.i.d. from an unknown distribution 2. x t is sampled according to Equation (2) given z t 3. we compute an estimate β • and make a prediction y t = β ⊤ • x t 4. we observe the true y t following Equation (2) 5. we incur in a loss (y t -y

t ) 2 = (y t -β ⊤ • x t ) 2
In order to address this problem, we propose an online form of the 2SLS estimator. Thus, modifying Equation (2SLS), we obtain the O2SLS estimator that is computed for the prediction at time t, using information up to time t -1:

β t-1 ≜ t-1 s=1 z s x ⊤ s -1 t-1 s=1 z s y s (O2SLS)
We use the O2SLS estimator at step t -1 for the prediction y t = β ⊤ t-1 x t . We elaborate O2SLS in Algorithm 1.

Remark 4.1. We could use x t and z t that we observe before committing to the estimate β t , and use it to predict y t [START_REF] Vovk | Competitive on-line statistics[END_REF]. Since we cannot use y t for this estimate, we have to modify

Predict y t = β ⊤ t-1 x t 5:
Observe y t and compute loss ℓ t β t-1 6: end for 2SLS to incorporate this additional knowledge. We skip this modification and use β t-1 to predict. Previously, [START_REF] Venkatraman | Online instrumental variable regression with applications to online linear system identification[END_REF] studied O2SLS for system identification but provided only an asymptotic analysis.

Defining Regrets: Identification and Oracle

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 O2SLS.

In econometrics and bio-statistics, where 2SLS is popularly used the focus is accurate identification of the underlying structural model β. Identifying β leads to understanding of the underlying economic or biological causal relations and their dynamics. In ML, [START_REF] Venkatraman | Online instrumental variable regression with applications to online linear system identification[END_REF] applied O2SLS for online linear system identification. Thus, given a sequence of estimators {β t } T t=1 and a sequence of covariates {x t } T t=1 , the cost of identifying the true parameter β can be quantified by

R T (β) ≜ T t=1 (x ⊤ t β t-1 -x ⊤ t β) 2 . (3)
We refer to R T (β) 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, [START_REF] Hartford | Counterfactual prediction with deep instrumental variables networks[END_REF]). Counterfactual predictions are important to study the causal questions: what would have changed in the outcome if Treatment a is used instead of treatment b. One of the modern applications of IVs are to facilitate such counterfactual predictions [START_REF] Hartford | Counterfactual prediction with deep instrumental variables networks[END_REF][START_REF] Bennett | Deep generalized method of moments for instrumental variable analysis[END_REF][START_REF] Zhu | Causal inference with treatment measurement error: a nonparametric instrumental variable approach[END_REF]. Alternatively, one might be interested in evaluating and improving the quality of prediction obtained using an estimator {β t } T t=1 with respect to an underlying oracle (or expert), which is typically the case in statistical learning theory and forecasting [START_REF] Dean | Prediction in the worst case[END_REF][START_REF] Cesa | Prediction, learning, and games[END_REF]. If the oracle has access to the true parameters β, the cost in terms of prediction that the estimators pay with respect to the oracle is rt ≜ ℓ t (β t ) -ℓ t (β). Thus, the regret in terms of the quality of prediction is defined as

R T (β) ≜ T t=1 (y t -x ⊤ t β t-1 ) 2 - T t=1 (y t -x ⊤ t β) 2 . ( 4
)
We refer to R T (β) as the oracle regret. This regret is studied for stochastic analysis of online regression [START_REF] Ouhamma | Stochastic online linear regression: the forward algorithm to replace ridge[END_REF] and is also useful for analysing bandit algorithms [START_REF] Foster | Beyond UCB: Optimal and efficient contextual bandits with regression oracles[END_REF]. As O2SLS is interesting for learning causal structures, 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 O2SLS. Though we know that they are of similar order (w.r.t. T ) in the exogenous setting, we show that they differ significantly for O2SLS under endogeneity.

Remark 4.2. 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 β T ≜ argmin β T t=1 (y t -x ⊤ t β) 2 given the observations over T steps [START_REF] Cesa | Prediction, learning, and games[END_REF]. Thus, the new formulation of regret becomes

R T = T t=1 (y t -x ⊤ t β t-1 ) 2 -min β T t=1 (y t -x ⊤ t β) 2 . ( 5
)
We refer to it as the population regret. Under exoegeneity, [START_REF] Ouhamma | Stochastic online linear regression: the forward algorithm to replace ridge[END_REF] shows that oracle regret and population regret differs by o(log 2 T ). We show that under endeogeneity their expected values differ by Ω(T ). Thus, we avoid studying this notion of regret in this paper. More details are in Appendix E.

Theoretical Analysis

Confidence Interval of β t . The central result in our analysis is concentration of the O2SLS estimates β t around β.

Lemma 4.1 (Confidence Ellipsoid for the Second-stage Parameters). Let us define the design matrix to be G z,t = Z ⊤ t Z t + λI d for some λ > 0. Then, for σ η -sub-Gaussian first stage noise η t , the true parameter β belongs to the set

E t = β ∈ R d : ∥β t -β∥ Ht ≤ b t (δ) , (6)
with probability at least 1 -δ ∈ (0, 1), for all t ≥ 0. Here, b t (δ) ≜

dσ 2 η 4 log 1+tL 2 z /λ δ , H t ≜ Θ ⊤ t G z,t Θ t ,
and Θ t is the estimate of the first-stage parameter at time t (Appendix J).

Lemma 4.1 extends the well-known elliptical lemma for OLS and Ridge estimators under exoegeneity to the O2SLS estimator under endogeneity. It shows that the size of the confidence intervals induced by O2SLS estimate at time T is O( √ d log T ), which is of the same order as that of the exogenous elliptical lemma (Abbasi-Yadkori et al., 2011a).

Identification Regret Bound. Now, we state the identification regret upper bound of O2SLS and a brief proof sketch.

Theorem 4.1 (Identification Regret of O2SLS). If Assumption 3.1 holds true, then for bounded IVs ∥z∥ 2 ≤ L 2 z , if η t is the σ η -sub-Gaussian second stage noise and ϵ t is the component-wise σ ϵsub-Gaussian first stage noise, the regret of O2SLS at step T > 1 satisfies

R T ≤ b T -1 (δ) Estimation O(d log T ) (C 2 1 + dC 2 2 )f (T ) + C 4 Second Stage Feature norm O(d log T )
with probability at least 1 -δ ∈ (0, 1). Here, b T -1 (δ) is the confidence bound of O2SLS estimate around β (Lemma 4.1) and f (T ) Proof Sketch. For brevity, we define ∆β t-1 ≜ β t-1 -β. By applying Cauchy-Schwarz inequality in Eq. (3), we decouple the effects of parameter estimates and feature norms

≜ C ′ 3 λ + log(T )+1 λ min (Σ)/2 . C 1 , C 2 , C ′ 3 ,
T t=1 ∆β ⊤ t-1 x t 2 ≤ T t=1 ∆β t-1 2 H t-1 ∥x t ∥ 2 H -1 t-1
Now, we bound this term by (a) using the confidence bound to control the concentration of β t around β, and (b) by bounding the sum of feature norms.

Step a: Confidence Intervals of β t . We directly use Lemma 4.1 to bound ∆β t-1

2 H t-1 by b t-1 .
Step b: Bounding the Second Stage Features. Now, we need to bound the sum of the feature norms. We use Lemma C.3 to obtain

T t=1 ∥x t ∥ 2 H -1 t-1 ≤ C 2 1 + dC 2 2 f (T ) + C 4 .
The idea is to substitute x t with (First stage) equation. This leads to two terms

T t=1 ∥Θ ⊤ z t ∥ 2 H -1 t-1 and T t=1 ∥ϵ t ∥ 2 H -1 t-1
. Then, we bound the first term by C 2 1 f (T ) using boundedness of the first-stage features and the concentration property of the minimum eigenvalue of the design matrix of the first stage, i.e.

G -1

z,t-1 2 ≜ t-1 s=1 z T s z s -1

2

. The concentration of the minimum eigenvalue leads to the term f (T )

≜ C ′ 3 λ + log(T )+1 λ min (Σ)/2 . Then, we bound T t=1 ∥ϵ t ∥ 2 H -1 t-1
using component-wise sub-Gaussianity of the first stage noise.

This leads to a bound

dC 2 2 f (T ) + C 4 with probability 1 -δ. Final step. Since b t-1 is non-decreasing in t, we conclude that T t=1 ∆β ⊤ t-1 x t 2 is upper bounded by b T -1 (δ)((C 2 1 + dC 2 2 )f (T ) + C 4
). Thus, we conclude that the identification regret of O2SLS is O(d 2 log 2 T ) for bounded IVs and unbounded noises.

Remark 4.3. Theorem 4.1 entails a regret R T = O d 2 log 2 (T )
, where d is dimension of IV. This regret bound is d log T more than the regret of online ridge regression, i.e. O(d log T ) [START_REF] Gaillard | Uniform regret bounds over R d for the sequential linear regression problem with the square loss[END_REF]. This is due to the fact that we perform d linear regressions in the first-stage and using the predictions of first stage for the second-stage regression. These two regression steps in cascade induce the proposed regret bound.

Oracle Regret Bound. Now, we provide a proof sketch of the oracle regret. Further details are in Appendix G.

Theorem 4.2 (Oracle Regret of O2SLS). Under the same hypothesis of Theorem 4.1, the Oracle Regret of O2SLS at step T > 1 satisfies

R T ≤ R T Identif. Regret O(d 2 log 2 T ) + b T -1 (δ) Estimation O( √ d log T )   σηC1 f (T ) log log T δ First Stage Feature Norm O( √ log T ) +C 5 2df (T ) + √ dC 6 Correlated noise Concentration Term O( √ d log T ) + γL Θ -1 C 3 √ λ + 2 √ 2T λ min (Σ)    Correlated noise Bias Term O(γ √ T )
with probability at least 1 -δ ∈ (0, 1). We define

γ ≜ ∥γ∥ 2 = ∥E[η s ϵ s ]∥ 2 . C 1 , C 2 , C ′ 3 ,
G). Constants C 5 ≜ 8e 2 σ 2 η + σ 2 ϵ L Θ -1 log(2/δ), C 6 ≜ C 5 max 1 λ , 2 λ min (Σ) log(2/δ), and f (T ) ≜ C ′ 3 λ + log(T )+1 λ min (Σ)/2 .
Proof Sketch. Using Equation (4) and Equation (2), we decompose the regret at step T as

R T = T t=1 ∆β ⊤ t-1 x t 2 (•1•) +2 T t=1 η t ∆β ⊤ t-1 Θ ⊤ z t (•2•) +2 T t=1 η t ∆β ⊤ t-1 ϵ t (•3•)
.

The proof proceeds by bounding each of these three terms.

Term 1: Second Stage Regression Error. We observe that Term (

•1•) is same as R T . By Theorem 4.1, we know R T = O(d 2 log 2 T ).
Term 2: Coupling of First-stage Data and Second-stage Parameter Estimation. Now, we bound the second term using concentration inequalities of martingales. First, we observe that w t ≜ β t-1 -β ⊤ Θ ⊤ z s is a martingale with respect to the filtration

F t-1 = σ (z 1 , ϵ 1 , η 1 , . . . , z t-1 , ϵ t-1 , η t-1 , z t ) .
We also note that w t is F t-1 -measurable since β t-1 and z t are too. By concentration property of scalar-valued martingale concentration (Theorem I.2), we get that with probability 1 -δ

(•2•) ≤ T t=1 η t w t ≤ 2 1 + σ 2 η T t=1 w 2 t log   1 + σ 2 η T t=1 w 2 t δ   .
Now, we focus on bounding the quantity appearing under square root. By applying Cauchy-Schwarz inequality and a reasoning similar to bounding Term (•1•), we get

T t=1 w 2 t ≤ b T -1 (δ)C 2 1 f (T ). Hence, we conclude that Term (•2•) is O( √ d log T
) ignoring the log log terms. Term 3: Coupling of First-and Second-stage Noises. Finally, we bound Term (•3•) containing the correlation between the first-and second-stage noise. This term is referred as the self-fulfilling bias [START_REF] Li | Self-fulfilling bandits: Dynamic selection in algorithmic decisionmaking[END_REF]. We bound this term by splitting it into two.

T t=1 η t ∆β ⊤ t-1 ϵ t = T t=1 ∆β T t-1 (ϵ t n t -γ) Martingale Concentration Term + T t=1 ∆β ⊤ t-1 γ Bias Term
Here, γ ≜ E[η s ϵ s ]. This leads to the first term, which is a summation of martingale difference sequence and can be bounded using concentration inequalities in Lemma F.2. The technical challenge is to derive the sub-exponential parameters induced by ϵ t η t in the martingale difference, since the individual terms are products of two dependent random variables ϵ t and η t . By applying Bernstein's inequality on the martingale difference and ∆β t-1

H t-1 ≤ b T -1 (δ) with probability 1 -δ, we obtain b T -1 (δ) Estimation O( √ d log T ) C 5 2d f (T ) + C 6 Correlated noise Concentration Term O( √ d log T )
The Bias Term is the one where the correlation γ appears explicitly. We bound this term (Lemma F.3) by bounding the sum of the square root of the smallest eigenvalues of the first stage covariates de-

sign matrix T t=1 G -1 z,t-1 2
. We reuse the upper bound on the individual terms (Lemma B.2),

where we show that the minimum eigenvalue of the first stage design matrix grows Ω(t). Thus, we

get that λ max G -1 z,t is O( 1 √ t )
. This leads to the following bound on the Bias Term

b T -1 (δ) Estimation O( √ d log T )   γL Θ -1 C 3 √ λ + 2 √ 2T λ min (Σ)    Correlated noise -Bias Term O(∥γ∥ 2 √ T )
Thus, we conclude the proof and get that the oracle regret of

O2SLS is O(γ √ dT log T + d 2 log 2 T ).
Remark 4.4. Under exogeneity and unbounded stochastic noise, the oracle regret of online linear regression is O(d 2 log 2 T ) [START_REF] Ouhamma | Stochastic online linear regression: the forward algorithm to replace ridge[END_REF]. Under endogeneity and unbounded stochastic noise, O2SLS incurs an extra O(γ √ dT log T ) factor 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 2SLS literature, this is referred as the self-fulfilling bias [START_REF] Li | Self-fulfilling bandits: Dynamic selection in algorithmic decisionmaking[END_REF]. When the noises are independent, i.e. γ = 0, we retrieve an oracle regret of the same order as that of the exogenous case.

Linear Bandits with Endogeneity: OFUL-IV

We formulate stochastic Linear Bandits with Endogeneity (LBE) with a two-stage linear model of data generation (Eqn. ( 2)). Then, we propose an index-based optimistic algorithm, OFUL-IV. Our analysis shows that OFUL-IV achieves O(d √ T log T ) regret. Our experimental results show that OFUL-IV achieve lower regret and more accurately estimates than OFUL (Abbasi-Yadkori et al., 2011a).

In bandit setting, we observe x t and y t depending on arm (or intervention) A t ∈ A t drawn at time t ∈ {1, . . . , T }.

x t = Θ ⊤ z t,At + ϵ t (LBE-first) y t = β ⊤ x t + η t (LBE-second)
Here, y t is the reward at round t. Each arm a corresponds to a vector of IVs z t,a ∈ Z t ⊂ R d , and a vector of endogenous variables x t,a ∈ X t ⊂ R d (generated as per (LBE-first)). Here, X t and Z t are sets of IVs and endogenous variables corresponding to A t . Similar to regression setting, we have two sources of unobserved noises: ϵ t (σ 2 ϵ I-sub-Gaussian) are i.i.d. vector error terms at round t which is independent of z, and η t (σ 2 η -sub-Gaussian), representing all causes of y t other than x t . True parameters β ∈ R d and Θ ∈ R d×d are unknown to the agents. This is an extension of the classical stochastic linear bandit (Lattimore and Szepesvári, 2020, Ch. 19). Now, we state the protocol of LBE.

At each round t = 1, 2, . . . , T , the agent 1. Observes a sample z t,a ∈ Z t and x t,a ∈ x t of contexts for all a ∈ A t 2. Chooses an arm A t ∈ A t 3. Obtains the reward y t computed from (LBE-first) 4. Updates the parameter estimates Θ t and β t OFUL-IV: Algorithm Design. If the agent had full information in hindsight, she could infer the best arm (or intervention) in A t as

a * t = argmax a∈At E[x ⊤ t,a β]
We denote the corresponding variables as z * t and x * t . Thus, choosing a * can be shown as choosing z * t and x * t . But the agent does not know them and aims to select {a t } T t=1 leading to minimum regret (Eqn. ( 4)). Now, we extend the 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 B t-1 ⊆ R d around the parameter β, which is computed only using the observed data. Then, the Algorithm 2 OFUL-IV

1: Input: Initialization parameters β 0 , Θ 0 , b ′ 0 2: for t = 1, 2, . . . , T do 3:
Observe z t,a ∈ Z t and x t,a ∈ x t for a ∈ A t

4:

Compute β t-1 according to Equation (O2SLS)

5:

Choose action A t that solves Equation ( 7)

6: Update β t ← β t-1 , Θ t ← Θ t , b ′ t ← b ′ t 7:
end for algorithm chooses an optimistic estimate of β t-1 from that confidence set:

β t-1 = argmax β ′ ∈B t-1 max x∈Xt x ⊤ β ′
Then, she chooses the action leading to x t = argmax x∈Xt x ⊤ β t , which maximizes the reward according to the estimate β t . In brief, the algorithm chooses the pair (x t , β t-1 ) = argmax

(x,β ′ )∈Xt×B t-1 x ⊤ β ′ .
In order to tackle endogeneity, we choose to use the O2SLS estimate β t-1 computed using data observed till t -1. Then, we build an ellipsoid B t-1 around it, such that

B t-1 ≜ β ∈ R d : ∥β t -β∥ Ht ≤ b ′ t (δ) and b ′ t (δ) ≜ 2σ 2 η log det (G z,t ) 1/2 λ -d/2 δ .
Given this confidence interval, we optimistically choose the arm

A t = argmax a∈At x t,a , β t-1 + b ′ t-1 (δ) ∥x t,a ∥ H -1 t-1 . ( 7
)
This arm selection index together with the O2SLS estimator yielding β t-1 construct the OFUL-IV (Algorithm 2).

Theorem 5.1. Under the same assumptions and notations of Theorem 4.1 and Theorem 4.2, Algorithm 2 incurs a regret

R T ≤ 2 √ T b T -1 (δ) Estimation O( √ d log T ) (C 2 1 + dC 2 2 )f (T ) + C 4 Second Stage Feature norm O( √ d log T )
with probability 1 -δ and for horizon T > 1.

Proof Sketch.

Step 1: Optimism. We observe that

R T = T t=1 β ⊤ x * -β ⊤ x t ≜ T t=1 r t . Since (x t , β t-1 ) is optimistic in X t × B t , and β ∈ B t , we obtain r t ≤ ( β t-1 -β) ⊤ x t .
Step 2: Decomposition. Now, we decompose regret as

( β t-1 -β) ⊤ x t = ( β t-1 -β t-1 ) ⊤ x t + (β t-1 -β) ⊤ x t .
The first term depends on tightness of confidence interval, while the second depends on accuracy of the estimate β t-1 . We show the MSE between the parameters estimated by the two algorithms and the true parameter β (right). OFUL-IV incurs lower instantaneous regret and MSE.

Step 3: Confidence Bound. Now, we can decouple the impact of parameter and observed data in both the terms using

β t-1 -β t-1 H t-1 ∥x t ∥ H -1 t-1 and β t-1 -β H t-1 ∥x t ∥ H -1 t-1
, respectively.

By construction of the optimistic confidence interval and concentrations bound of Lemma 4.1, both

β t-1 -β t-1 H t-1 and β t-1 -β H t-1 are bounded by b ′ t-1 (δ). By determinant-trace inequality (Lemma A.1), we get that b ′ T -1 (δ) ≤ dσ 2 η 4 log 1+T L 2 z /λ δ . Final Step. Since the regret R T ≤ T T t=1 r 2 t , we obtain R T ≤ σ η dT log 1 + T L 2 z /λ δ T t=1 ∥x t ∥ 2 H -1 t-1
. Now, we bound the sum of the first-stage feature norms T t=1 ∥x t ∥ 2

H -1 t-1 by (C 2 1 + dC 2 2 )f (T ) + C 4 (Lemma C.3), which is O(d log T ). A detailed proof is in Appendix H.
Thus, we conclude that regret of OFUL-IV is O(d √ T log T ). OFUL-IV achieves regret of similar order under endogeneity as OFUL achieves under exoegeneity. Experimental Analysis. Now, we compare performance of OFUL-IV and OFUL (Abbasi-Yadkori et al., 2011a) for LBE setting. OFUL builds a confidence ellipsoid centered at β Ridge,t to concentrate around β, while OFUL-IV uses O2SLS to build an accurate estimate. We deploy the experiments in Python3 on a single Intel(R) Core(TM) i7-8665U CPU@1.90GHz. For each algorithm, we report the mean and standard deviation of instantaneous regret and mean square error ∥β t -β∥ 2 over 100 runs. We run the algorithms with the same regularisation parameters equal to 10 -3 . We denote the normal distribution with mean µ and standard deviation σ as N (µ, σ), with N n we indicate its multivariate extension to n dimensions. For each experiment, we sample the true parameters in our model once according to β ∼ N 50 ( ⃗ 10, I 50 ) and Θ i,j ∼ N (0, 1) for each component. Then we sample at each time t the vectors z t,a ∼N 50 ( ⃗ 0, I 50 ), ϵ t,a ∼N 50 ( ⃗ 0, I 50 ), and the scalar noise η t,a = 1 13 η t,a + 12 i=1 ϵ t,a,i where η t,a ∼N (0, 1).

The estimates obtained by OFUL-IV achieves 3-order less error than those of OFUL (Fig. 2b). Thus, OFUL-IV leads to lower regret than OFUL for linear bandits with endogeneity (Fig. 2a). Further experimental details and results of regression are deferred to Appendix K.1.

Conclusions and Future Works

In this paper, we study online IV regression, specifically the online 2SLS algorithm, for unbounded noise and endogenous data. We analyse the finite-time identification and oracle regrets of O2SLS. We observe that O2SLS incurs O(d 2 log 2 T ) identification regret, which is d log T higher than that of online linear regression under exogeneity. In contrast, O2SLS achieves O(∥γ∥ 2 √ dT log T ) oracle regret as the correlation between the noises in the two-stages dominate the identification regret. But these two are of the same order in the exogenous setting. Following that, we study stochastic linear bandits with endogeneity. We propose OFUL-IV that uses O2SLS to estimate the model parameters. We show that OFUL-IV achieves O(d √ T log T ) regret. We experimentally show that OFUL-IV yields more accurate estimates of the true parameter and thus, lower regret.

For simplicity, we consider the just-identified IVs. In future, we will like to extend our algorithms and analysis to weakly or over-identified IVs (Greene, 2003). Additionally, O2SLS and OFUL-IV work if the IVs are already specified. There has been significant work to identify IVs in offline setting [START_REF] Whitney | Instrumental variable estimation of nonparametric models[END_REF][START_REF] Chen | Mostly harmless machine learning: learning optimal instruments in linear iv models[END_REF]. Still, it is an open question how optimally IVs can be identified online, while O2SLS is performed simultaneously.

Appendix A. Useful Results

Notations for scalars, vectors, matrices: We indicate in bold vectors and matrices, e.g. the vector and matrix (matrices are also usually capitalized) v ∈ R d , A ∈ R d×d ; while scalars do not use the bold notation, e.g. the scalar s ∈ R. We indicate the determinant of matrix A with det(A) and its trace with Tr(A). For a x ∈ R ≥0 , we indicate the function that takes as input x, and gives as output the least integer greater than or equal to x as ⌈x⌉ (ceiling function). We indicate the identity matrix of dimension d with I d .

A.1 Random Variables

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.1 (Sub-Gaussian r.v.). A random variable X with mean µ = E[X] is sub-Gaussian if there is a positive number σ such that E e λ(X-µ) ≤ e σ 2 λ 2 /2 for all λ ∈ R. Definition A.2 (Sub-exponential r.v.). A random variable X with mean µ = E[X] is sub-exponential if there are non-negative parameters (ν, α) such that E e λ(X-µ) ≤ e ν 2 λ 2 /2 for all |λ| < 1 α

A.2 Norms of Vectors and Matrices

Definition A.3 (ℓ p -norms). For a vector v ∈ R n , we express its ℓ p -norm as ∥v∥ p for p ≥ 0. A special case is the Euclidean ℓ 2 -norm denoted as ∥•∥ 2 , which is induced by classical scalar product on R n denoted by ⟨•, •⟩.

Given a rectangular matrix A ∈ R n×m with n ≥ m, we write its ordered singular values as

σ max (A) = σ 1 (A) ≥ σ 2 (A) ≥ • • • ≥ σ m (A) = σ min (A) ≥ 0
The minimum and maximum singular values have the variational characterization

σ max (A) = max v∈S m-1 ∥Av∥ 2 and σ min (A) = min v∈S m-1 ∥Av∥ 2 , where S d-1 ≜ v ∈ R d | ∥v∥ 2 = 1 is the Euclidean unit sphere in R d .
Definition A.4 (ℓ 2 -operator norm). The spectral or ℓ 2 -operator norm of A is defined as

~A~2 ≜ σ max (A) . (8)
Since covariance matrices are symmetric, we also focus on the set of symmetric matrices in R d , denoted

S d×d = Q ∈ R d×d | Q = Q T ,
as well as the subset of positive semidefinite matrices given by S d×d

+ ≜ Q ∈ S d×d | Q ⪰ 0 .
From standard linear algebra, we recall the facts that any matrix Q ∈ S d×d is diagonalizable via a unitary transformation, and we use λ(Q) ∈ R d to denote its vector of eigenvalues, ordered as

λ max (Q) = λ 1 (Q) ≥ λ 2 (Q) ≥ • • • ≥ λ d (Q) = λ min (Q).
Note that a matrix Q is positive semidefinite-written Q ⪰ 0 for short-if and only if λ min (Q) ≥ 0.

Remark A.1 (Rayleigh-Ritz variational characterization of eigenvalues). We remind also the Rayleigh-Ritz variational characterization of the minimum and maximum eigenvalues-namely

λ max (Q) = max v∈S d-1 v ⊤ Qv and λ min (Q) = min v∈S d-1 v ⊤ Qv.
Remark A.2. For any symmetric matrix Q, the ℓ 2 -operator norm can be written as

~Q~2 = max {λ max (Q), |λ min (Q)|} ,
by virtue of which it inherits the variational representation ~Q~2 = max v∈S d-1 v ⊤ Qv .

Corollary A.1. Given a rectangular matrix A ∈ R n×m with n ≥ m, suppose that we define the m dimensional symmetric matrix R = A T A. We then have the relationship

λ j (R) = (σ j (A)) 2 for j = 1, . . . , m
We now introduce norms that are induced by positive semi-definite matrices in the following way.

Definition A.5. For any vector y ∈ R n and matrix A ∈ S n×n + , let us define the norm ∥y∥ A ≜ y T Ay = ⟨y, Ay⟩.

Throughout the paper we will need often to bound matrix induced norms using ℓ 2 -norms for operators, the following results shows how this can be done easily for generic matrices. We specialize this result as we need in the text.

Proposition A.1. Take A, B ∈ R n×n , with B ⪰ 0 positive semi-definite and x ∈ R n ∥Ax∥ 2 B = ∥x∥ 2 A ⊤ BA ≤ ~B~2~A~2 2 ∥x∥ 2 2 (9)
Proof. The equality holds since we can rewrite

∥Ax∥ 2 B = ⟨Ax, BAx⟩ = ⟨x, A ⊤ BAx⟩ = ∥x∥ 2 A ⊤ BA .
The inequality follows by the definition of ℓ 2 -norms, where we further substitute y = Ax, to get

⟨Ax, BAx⟩ = ⟨Ax, BAx⟩ ∥Ax∥ 2 2 ∥Ax∥ 2 2 ∥x∥ 2 2 ∥x∥ 2 2 = ⟨y, By⟩ ∥y∥ 2 2 ∥Ax∥ 2 2 ∥x∥ 2 2 ∥x∥ 2 2 ≤ ~B~2~A~2 2 ∥x∥ 2 2 .
We note that the inequality holds trivially for x in the null space of A, therefore, in the previous case, we can safely divide by ∥Ax∥ 2 and ∥x∥ 2 .

A

d √ α 1 α 2 • • • α d ≤ α 1 + α 2 + • • • + α d d .
Therefore, det (G z,t ) ≤ (Tr (G z,t ) /d) d . Now, it remains to upper bound the trace:

Tr (G z,t ) = Tr(λI d ) + t s=1 Tr z s z ⊤ s = dλ + t s=1 ∥z s ∥ 2 2 ≤ dλ + tL 2 z
and the lemma follows.

B. Concentration of The Minimum Eigenvalue of The Design Matrix

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 ℓ 2 -norm of the inverse of the design matrix G -1 z,t 2 . We start by staging two know results that we use in order to derive Lemma B.2. Lemma B.1 is a direct corollary of Weyl's theorem for eigenvalues (see for example Exercise 6.1 in (Wainwright, 2019)). (11)

The following, is a classical concentration result for the covariance matrix using the ℓ 2 -norm for matrices, for a proof of this result we refer the reader to Corollary 6.20 in [START_REF] Martin | High-dimensional statistics: A non-asymptotic viewpoint[END_REF].

Theorem B.1 (Estimation of covariance matrices). Let z 1 , . . . , z t be i.i.d. zero-mean random vectors with covariance Σ such that ∥z s ∥ 2 ≤ L z almost surely. Then for all δ > 0, the sample covariance matrix

Σ t = 1 t t s=1 z s z ⊤ s satisfies P Σ t -Σ 2 ≥ δ ≤ 2d exp - tδ 2 (2L 2 z ~Σ~2 + δ)
, this means that with probability at least 1 -δ

Σ t -Σ 2 ≤ 4L 2 z t log 2d δ + 2 2L 2 z t log 2d δ ~Σ~2.
Now, we use this concentration bound together with the bound on the difference of the minimum eigenvalues of two symmetric matrices in order to bound the maximum eigenvalue of the inverse of the design matrix.

Lemma B.2 (Well-behavedness of First-stage Design Matrix). Let z 1 , . . . , z t be i.i.d. zero-mean random vectors with covariance Σ such that ∥z s ∥ 2 ≤ L z almost surely. We denote the regularized design matrix as G z,t = λI d + t s=1 z s z ⊤ s . For all δ > 0 and regularization parameter λ > 0, we observe that

G -1 z,t 2 = λ max G -1 z,t ≤ 1 λ if t ≤ C 3 2 t λ min (Σ) if t > C 3 .
Here, C 3 > 0 is a constant defined by Equation (13) and λ min (Σ) is the minimum eigenvalue of the true covariance matrix of z, i.e.

Σ ≜ E[zz ⊤ ].
Proof. First, we aim to find a lower bound for the smallest eigenvalue of the design, matrix where we set the regularization parameter λ to zero. We denote the 'non-regularized' design matrix as G λ=0 z,t . For t ≥ 1, we observe that G λ=0 z,t /t ≜ Σ t . Thus, by applying Equation (11), we obtain

λ min G λ=0 z,t /t -λ min (Σ) ≤ 4L 2 z t log 2d δ + 2 2L 2 z t log 2d δ ~Σ~2 .
Further substituting A ≜ 2L 2 z log 2d δ leads to the following lower bound for the minimum eigenvalue

λ min G λ=0 z,t ≥ max 0, t λ min (Σ) -2A /t -2 A λmax(Σ) /t .
Here, λ max (Σ) and λ min (Σ) is the maximum and minimum eigenvalues of the true covariance matrix of z, i.e. Σ ≜ E[zz ⊤ ]. By well-behavedness assumption of the IV, both of them are positive and bounded reals. Now, from the variational definition of the minimum eigenvalues, we have

λ min (G z,t ) ≥ λ min G λ=0 z,t + λ,
which implies that λ min (G z,t ) ≥ λ for all t ≥ 0, with equality for t = 0. Thus, we have

λ min (G z,t ) ≥ max λ, λ + t λ min (Σ) -2A /t -2 A λmax(Σ) /t . ( 12
)
Let us consider the second term inside maximum of Equation ( 12), and we split it in the following way

λ + t λ min (Σ) -2A -2 tA λ max (Σ) = t λ min (Σ) 2
Term (A) + t 2 λ min (Σ) -2 tA λ max (Σ) + λ -2A Term (B)
Now we study for which values Term (B) is non-negative. The corresponding second order polynomial equation is obtained substituting u = √ t, and reads

u 2 λ min (Σ) -4u A λ max (Σ) + 2(λ -2A) = 0 ,
which has two solutions given by

u ± = 2 A λ max (Σ) ± 4A λ max (Σ) + 2(2A -λ) λ min (Σ) λ min (Σ) .
In particular for t > ⌈u + ⌉, Term (A) ≥ 0, and Equation ( 12) reads λ min (G z,t ) ≥ max {λ, t λ min (Σ)/2} .

Therefore, for t > ⌈2λ/ λ min (Σ)⌉ and t > ⌈u + ⌉ we have that λ min (G z,t ) ≥ t λ min (Σ)/2. Putting the results together, we conclude that

λ min (G z,t ) ≥ t λ min (Σ)/2 for t > C 3 ≜ max {⌈2λ/ λ min (Σ)⌉, ⌈u + ⌉} , (13)
while for t ≤ C 3 , we retain the trivial lower bound of the minimum eigenvalue, i.e. λ.

In summary, we have

λ min (G z,t ) ≥ λ if t ≤ C 3 t λ min (Σ)/2 if t > C 3 ⇐⇒ λ max G -1 z,t ≤ 1 λ if t ≤ C 3 2 t λ min (Σ) if t > C 3 .

C. Technical Lemmas for the Endogeneous Setting

In this section, we present some useful Lemmas that we used in the proofs of the regret bounds of O2SLS and OFUL-IV.

Remark C.1. In Appendix J, we describe that the first stage regression in O2SLS can be expressed as running d independent ridge regressions for each column of Θ (Equation ( 27)). Since the standard analysis of each of the ridge regressions assume independent and sub-Gaussian noise added in the linear model (cf. Theorem J.1; [START_REF] Ouhamma | Stochastic online linear regression: the forward algorithm to replace ridge[END_REF])), we assume that each component of the first stage noise, i.e. ϵ t,i , corresponding to the i-th ridge regression is sub-Gauss(σ ϵ ). Thus, we obtain that E∥ϵ t ∥ 2 2 ≤ dσ 2 ϵ . We use this result throughout this section.

Lemma C.1 (Bounding the First-stage Parameters). Given the relevance condition in Assumption 3.1 and a regularization parameter λ > 0, we have the following upper bound for the inverse of the estimated parameter (Equation ( 27)) in the first-stage regression:

Θ -1 t 2 ≤ λ + L 2 z r ≜ L Θ -1 (14)
Proof. By the sub-multiplicativity of the matrix norms we have

Θ -1 t 2 = Z ⊤ t X t -1 Z ⊤ t Z t + λI 2 ≤ Z ⊤ t X t -1 2 Z ⊤ t Z t + λI 2
Then, by the sub-additivity of the norms and the variational definition of the biggest eigenvalue

Z ⊤ t Z t + λI 2 ≤ Z ⊤ t Z t 2 + ~λI~2 ≤ max v∈S d-1 v, t s=1 z s z ⊤ s v + λ = max v∈S d-1 t s=1 ⟨v, z s ⟩ 2 + λ ≤ t s=1 ∥z s ∥ 2 2 + λ ≤ tL 2 z + λ
Then, we note that the quantity

Z ⊤ t X t -1 2 ≤ 1
tr by the definition of relevance, which implies

Θ -1 t 2 ≤ tL 2 z + λ tr = L 2 z + λ /t r ≤ L 2 z + λ r ( 15
)
Lemma C.2 (Bounding the Impact of First-stage Noise). For first stage noises that is componentwise sub-Gaussian(σ ϵ ), and first-stage parameter estimates satisfying

Θ -1 t 2 ≤ L Θ -1 (Lemma C.1), we have that T t=1 ∥ϵ t ∥ 2 Θ -1 t-1 G -1 z,t-1 Θ -⊤ t-1 ≤ dσ 2 ϵ L 2 Θ -1 C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + C 4 O(d log T )
with probability at least 1 -δ and with C 4 a constant defined in Equation (17).

Proof. The proof follows using chain of inequalities from Proposition A.1 and Lemma C.1,

T t=1 ∥ϵ t ∥ 2 Θ -1 t-1 G -1 z,t-1 Θ -⊤ t-1 ≤ T t=1 G -1 z,t-1 2 Θ -1 t-1 2 2 ∥ϵ t ∥ 2 2 ≤ L 2 Θ -1 T t=1 G -1 z,t-1 2 ∥ϵ t ∥ 2 2 -E ∥ϵ t ∥ 2 2 + E ∥ϵ t ∥ 2 2 ≤ L 2 Θ -1 T t=1 G -1 z,t-1 2 ∥ϵ t ∥ 2 2 -E ∥ϵ t ∥ 2 2 I + L 2 Θ -1 T t=1 G -1 z,t-1 2 E ∥ϵ t ∥ 2 2 II Term I: We now assume ∥ϵ t ∥ 2 2 -E ∥ϵ t ∥ 2 2 ∼ sub-exp(ν, α)
where the correct values of ν, α can simply be taken from the results on the square of sub-Gaussians and gives that ν ≜ d4 √ 2σ 2 ϵ and α ≜ 4σ 2 ϵ . Now, given an X ∼ sub-exp(ν, α), we have that its rescaling by a constant c is distributed according to X c ∼ sub-exp v c , c α which follows by sustituting λ → λ/c into the definitions

E e λX/c ≤ e λ 2 ν 2 /2c 2 , ∀|λ/c| ≤ 1 α ⇔ |λ| ≤ c α
Using this, we can rescale by the factor t in the following

P n t=m ∥ϵ t ∥ 2 2 -E ∥ϵ t ∥ 2 2 t ≥ µ ≤ E e λ n t=m ∥ϵ t ∥ 2 -E∥ϵ t ∥ 2 t e -λµ ≤ e n t=m λ 2 ν 2 /2t 2 -λµ ≤ e λ 2 ν 2 2 ( 1 m-1 -1 n )-λµ
which holds ∀|λ| ≤ m α thanks to the following series of inequalities

n m 1 t 2 ≤ n m-1 1/t 2 dt = (-1 t | n m-1 = -1 n + 1 m-1 . This proves that T t=C 3 ∥ε t ∥ 2 2 -E ∥ε t ∥ 2 2 t ∼ sub-exp ν 1 C 3 -1 - 1 T , C 3 α (16)
We bound the following summation using Lemma B.2:

T t=1 G -1 z,t-1 2 ∥ϵ t ∥ 2 2 -E ∥ϵ t ∥ 2 2 = C 3 t=0 λ max G -1 z,t ∥ϵ t+1 ∥ 2 2 -E ∥ϵ t+1 ∥ 2 2 + T -1 t=C 3 +1 λ max G -1 z,t ∥ϵ t+1 ∥ 2 2 -E ∥ϵ t+1 ∥ 2 2 ≤ 1 λ C 3 t=0 ∥ϵ t+1 ∥ 2 2 -E ∥ϵ t+1 ∥ 2 2 + 2 λ min (Σ) T -1 t=C 3 +1 ∥ϵ t+1 ∥ 2 2 -E ∥ϵ t+1 ∥ 2 2 t ≤ C 3 + 1 λ d4 √ 2σ 2 ϵ 2 log(1/δ) + 1 2σ 2 ϵ log(1/δ) + 2 λ min (Σ) 2ν 2 1 C 3 - 1 T log(1/δ) + 2C 3 α log(1/δ)
Since term I can be upperbounded by a constant O(1) we just name this constant C 4 where we also substitute back the definitions ν = d4 √ 2σ 2 ϵ and α = 4σ 2 ϵ :

C 4 ≜ L 2 Θ -1 C 3 + 1 λ d4 √ 2σ 2 ϵ 2 log(1/δ) + 1 2σ 2 ϵ log(1/δ) + 2L 2 Θ -1 λ min (Σ) d4 √ 2σ 2 ϵ 2 C 3 log(1/δ) + 2C 3 4σ 2 ϵ log(1/δ) (17)
Term II: The proof follows using the high probability bound that we introduce in Lemma B.2, plus the estimate n k=1 1 k < log(n) + 1:

dσ 2 ϵ L 2 Θ -1 T t=1 λ max G -1 z,t-1 ≤ dL 2 ϵ L 2 Θ -1   C 3 t=0 1 λ + T -1 t=C 3 +1 2 λ min (Σ)t   ≤ dL 2 ϵ L 2 Θ -1 C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) .
Therefore, putting Term I and Term II together, we obtain

T t=1 ∥ϵ t ∥ 2 Θ -1 t-1 G -1 z,t-1 Θ -⊤ t-1 ≤ dσ 2 ϵ L 2 Θ -1 C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + C 4 O(d log T )
Lemma C.3 (Bounding the Sum of Feature Norms). Under the same conditions of Lemma C.2 plus first-stage parameters with bounded ℓ 2 -norm ~Θ~2 ≤ L Θ and bounded IVs ∥z∥ 2 ≤ L 2 z we have that

T t=1 ∥x t ∥ 2 Θ -1 t-1 G -1 z,t-1 Θ -⊤ t-1 ≤ L 2 Θ -1 L 2 Θ L 2 z + dσ 2 ϵ C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + C 4 O(d log T )
Proof. We start by substituting the First Stage equations inside the norm and using a Triangle Inequality

T t=1 ∥x t ∥ 2 Θ -1 t-1 G -1 z,t-1 Θ -⊤ t-1 = T t=1 Θ ⊤ z t + ϵ t 2 Θ -1 t-1 G -1 z,t-1 Θ -⊤ t-1 ≤ T t=1 Θ ⊤ z t 2 Θ -1 t-1 G -1 z,t-1 Θ -⊤ t-1 + T t=1 ∥ϵ t ∥ 2 Θ -1 t-1 G -1 z,t-1 Θ -⊤ t-1 ≤ L 2 Θ -1 L 2 Θ L 2 z + dσ 2 ϵ C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + C 4
where in the last inequality we used the result of Lemma C.2 for the second term and the following chain of inequality for the following term

T t=1 Θ ⊤ z t 2 Θ -1 t-1 G -1 z,t-1 Θ -⊤ t-1 ≤ L 2 Θ L 2 z L 2 Θ -1 T t=1 λ max G -1 z,t-1 ≤ L 2 Θ L 2 z L 2 Θ -1   C 3 t=0 1 λ + T -1 t=C 3 +1 2 λ min (Σ)t   ≤ L 2 Θ L 2 z L 2 Θ -1 C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) .

D. Elliptical Lemma for the Endogeneous Setting

Lemma D.1 (Confidence Ellipsoid for the Second-stage Parameters). Let us define the design matrix to be G z,t = Z ⊤ t Z t + λI d for some λ > 0 and H t ≜ Θ ⊤ t G z,t Θ t . Then, for σ η -sub-Gaussian second stage noise η t , the true parameter β belongs to the set

E t = β ∈ R d : ∥β t -β∥ Ht ≤ b t (δ) ,
with probability at least 1 -δ ∈ (0, 1), for all t ≥ 0. Here, b t (δ) ≜

dσ 2 η 4 log 1+tL 2 z /λ δ .
Proof. We can rewrite

β t -β = Z ⊤ t X t -1 Z ⊤ t η t = Θ -1 t Z ⊤ t Z t + λI d -1 Z ⊤ t η t = Θ -1 t G -1 z,t Z ⊤ t η t .
Take x ∈ R d and by the Cauchy-Schwarz inequality we have

(I) x ⊤ β t -x ⊤ β = x ⊤ Θ -1 t G -1 z,t Z ⊤ t η t = Θ -⊤ t x, G -1 z,t Z ⊤ t η t ≤ Θ -⊤ t x G -1 z,t G -1 z,t Z ⊤ t η t Gz,t = Θ -⊤ t x G -1 z,t (II) Z ⊤ t η t G -1 z,t (III)
.

The choice we will make for x is the following

x ≜ Θ ⊤ t G z,t Θ t (β t -β) = H t (β t -β), (18)
which leads to the following rewriting for the three previous terms. Term (I): From a simple substitution and the definition of a norm induced by a matrix we have

x ⊤ β t -x ⊤ β = ⟨x, β t -β⟩ = Θ ⊤ t G z,t Θ t (β t -β), β t -β = ∥β t -β∥ 2 Θ ⊤ t Gz,t Θt .
Term (II): First, we rewrite the following term

Θ -⊤ t x G -1 z,t = Θ -⊤ t x, Θ -⊤ t x G -1 z,t = x ⊤ Θ -1 t G -1 z,t Θ -⊤ t x = ∥x∥ Θ -1 t G -1 z,t Θ -⊤ t = ∥x∥ Θ ⊤ t Gz,t Θt -1 ,
and, once again, we substitute the definition of x in Equation ( 18):

∥x∥ Θ ⊤ t Gz,t Θt -1 = ∥ Θ ⊤ t G z,t Θ t (β t -β)∥ Θ ⊤ t Gz,t Θt -1 = ∥β t -β∥ Θ ⊤ t Gz,t Θt
.

Terms (III):

We bound the last term using Theorem I.1 for the first inequality, and Lemma A.1 in the second inequality:

Z ⊤ t η t G -1 z,t = t s=1 η s z s G -1 z,t ≤ 2(σ η /2) 2 log det (G z,t ) 1/2 λ -d/2 δ ≤ dσ 2 η 4 log 1 + tL 2 z /λ δ .
Finally, from our initial decomposition, dividing on both sides by ∥β t -β∥

Θ ⊤ t Gz,t Θt
, we get

∥β t -β∥ Θ ⊤ t Gz,t Θt ≤ dσ 2 η 4 log 1 + tL 2 z /λ δ .
Remark D.1. We note that the ellipsoid bound has the following order in d and t while neglecting the constants:

b t (δ) = O (d log(t))
E. A Detailed Discussion on Different Definitions of Regret

In econometrics, the focus has historically been given to the correct identification of the estimator β. This is because the community has been mainly interested in discovering causal relations and assigning causal meaning to the parameters in the regression. Instead, the primary concern of the statistics and statistical learning community has been arguably on generalization. Interestingly, this tension between these two efforts has not been analyzed until recently since the two communities have worked in two different settings, the endogenous and the exogenous ones, where this conflict is not apparent. In fact, under exogeneity the problem of identifying correctly the true parameter β is solved at the same time as the one of having good generalization since the OLS estimator is a consistent estimator. With the exogeneity hypothesis is possible to perform the two tasks of identification and generalization at the same time. This is not true if we introduce the more realistic assumption of endogeneity. In this case, the Minimum Mean Squared Error Estimator (MMSEE) becomes the following, On the contrary, we are instead interested in finding notions of regret that preserve the causal interpretation of the estimates, and this naturally leads to extending the instrumental variables analysis to the online setting. This motivates the inspection of different notions of regret, which differ from the population regret for a time-dependent estimator

β MMSEE = E xx ⊤ -1 E[xy] = β + E xx ⊤ -1 E[xη].
β t-1 defined as R T (β T ) ≜ T t=1 (y t - x ⊤ t β t-1 ) 2 -min β T t=1 (y t -x ⊤ t β) 2
where we indicated with β T = arg min β T t=1 (y t -x ⊤ t β) 2 . This is studied in the online learning literature but under the exogeneity assumptions. Therefore, we introduce two alternative regrets that measure the performance of an estimator β t-1 compared to the oracle. They are the oracle regret R T (β) and the identification regret R T (β) below

R T (β) = T t=1 (y t -x ⊤ t β t-1 ) 2 - T t=1 (y t -x ⊤ t β) 2 and R T (β) = T t=1 (x ⊤ t β t-1 -x ⊤ t β) 2 .
Theorem E.1 shows that an estimator that performs well in terms of oracle regret is instead a bad choice for the population regret, and the other way around.

Theorem E.1. For any estimator, the quantity

∆ T ≜ R T (β T ) -R T (β) is lower bound in expec- tation by E[∆ T ] = Ω(T )
Proof Sketch. Solving for β T leads to the OLS estimator for data up to time T :

β T = β + T t=1 x ⊤ t x t -1 T t=1
x ⊤ t η t provided that we can invert the design matrix in the previous expression. Using this expression we ca rewrite ∆ T using ∆β T ≜ ββ T and G T ≜ T t=1 x ⊤ t x t as follows

∆ T = T t=1 x ⊤ t ∆β T 2 + 2 T t=1 η t x ⊤ t ∆β T = 3∥∆β T ∥ 2 G T .
Thanks to Lemma B.2, we know that the minimum eigenvalue of G T is Ω(T ) which implies

∥∆β T ∥ 2 G T ≥ ∥∆β T ∥ 2 2 λ min (G T ) ≳ ∥∆β T ∥ 2 2 T
. Furthermore, we can bound away from zero in expectation ∥∆β T ∥ by using Cramér-Rao bound on each component of the estimator β T , for which we have

E (β T,i -β i ) 2 ≥ [1+b ′ (β i )] 2 I(β i ) + b(β i ) 2 where b(β i ) = E[β T,i ] -β i
is the bias of the estimator and I(β i ) is the Fisher Information evaluated at β i . We know that β T is a biased estimator of β in the endogenous setting, therefore the bias is strictly positive for at least one component, and this concludes the proof.

F. Lemmas on Correlation between First and Second Stages

In the first part of this section, we derive a concentration result for the quantity

S t ≜ t s=1 ∆β ⊤ s-1 (ϵ s η s -γ) ,
which we call the Martingale Concentration Term in the proof of Theorem 4.2. We can prove that S t is a martingale adapted to the filtration F t ≜ σ (ϵ s:t , η 1:t , z 1:t ) (or equivalently a sum of martingale difference sequence), by proving that: (a)

E [|S t |] ≤ ∞ and (b) E [S t+1 | F t ] = S t .
The first condition is immediate and the second can be easily verified since:

E [S t+1 | F t ] = E ∆β ⊤ t (ϵ t 1 η t+1 -γ) + t s=1 ∆β ⊤ s-1 (ϵ s η s -γ) F t = 0 + t s=1 ∆β ⊤ s-1 (ϵ s η s -γ) = S t .
Then, the idea is to apply the following theorem on concentration bounds for martingale difference sequences for the first term in eq. ( 24). In our case the martingale difference sequence is

{(∆β ⊤ s-1 (ϵ s η s -γ) , F s )} ∞ s=1 .
Theorem F.1 (Concentration Bounds for Martingale Difference Sequences Wainwright ( 2019)).

Let {(D k , F k )} ∞ k=1 be a martingale difference sequence, and suppose that

E e λD k | F k-1 ≤ e λ 2 ν 2 k /2
almost surely for any |λ| < 1/α k . Then the following hold:

1. The sum n k=1 D k is sub-exponential with parameters n k=1 ν 2 k , α * , where α * := max k=1,...,n α k .

2. The sum satisfies the concentration inequality

P n k=1 D k ≥ t ≤    2e - r 2 2 n k=1 ν 2 k if 0 ≤ t ≤ n k=1 ν 2 k α * , 2e -1 2α * if t > n k=1 ν 2 k α *
.

To apply the previous theorem, we derive in the following the sub-exponentiality parameters ν * s , α * s for the martingale difference

D s ≜ ∆β ⊤ s-1 (ϵ s η s -γ) such that E e λ∆β ⊤ s-1 (ϵsηs-γ) F s-1 ≤ e λ 2 ν * 2
s /2 a.s. ∀|λ| < 1/α * s and then we apply the previous theorem. The bound is derived in the following lemma.

Lemma F.1 (Square and product of non-independent sub-Gaussian random variables). Given two non-independent random variables X ∼sub-Gauss(σ X ) and Y ∼sub-Gauss(σ Y ), we can prove the two following things:

1.

X 2 is sub-exp 4 √ 2σ 2 , 4σ 2 ; 2. the recentered random variable XY is sub-exp 4 √ 2 σ 2 X + σ 2 Y , 2 σ 2 X + σ 2 Y .
Proof. We prove the two statements in order and we use the first result to prove the second for the case of non independent random variables, which leads to different constants with respect to the result for independent random variables. 1. We start bounding the rescaled p-th power of X

E [| X /σ √ 2| p ] = ∞ 0 P {| X /σ √ 2| p ≥ u} du (integral identity for positive r.v.) = 1 √ 2σ ∞ 0 P |X| ≥ t √ 2σ pt p-1 dt (change of variable u = t p ) ≤ ∞ 0 2e -t 2 pt p-1 dt (by σ-sub-Gaussianity)
= pγ(p/2) (set t 2 = s and use definition of Gamma function))

By multiplying the previous inequality on both sides by the constant ( √ 2σ) p we obtain

E [|X| p ] ≤ p2 p 2 σ p Γ(p/2). Now, let Y = X 2 and µ Y = E[Y ]
. By power series expansion and since Γ(r) = (r -1)! for an integer r, we have:

E e λ(Y -µ Y ) = 1 + λE [Y -µ Y ] + ∞ r=2 λ r E [(Y -µ Y ) r ] r! ≤ 1 + ∞ r=2 λ r E |X| 2r r! ≤ 1 + ∞ r=2 λ r 2r2 r σ 2r Γ(r) r! = 1 + ∞ r=2 λ r 2 r+1 σ 2r = 1 + 8λ 2 σ 4 1 -2λσ 2
By making |λ| ≤ 1/ 4σ 2 , we have 1/ 1 -2λσ 2 ≤ 2. Finally, since (∀α)1 + α ≤ e α , we have that a sub-Gaussian variable X with parameter σ is sub-exponential with parameters (4 √ 2σ 2 , 4σ 2 ), in fact we have:

E e λ(X 2 -E[X 2 ]) ≤ e 16λ 2 σ 4 ∀|λ| ≤ 1/ 4σ 2 .
2. We notice that

XY -E[XY ] = X -Y 2 2 -E X -Y 2 2 - X + Y 2 2 -E X + Y 2 2 ≜ Z 1 -Z 2
where we defined

Z 1 ≜ X-Y 2 2 -E X-Y 2 2 and Z 2 ≜ X+Y 2 2 -E X+Y 2 2
. We have to take into account the dependence, and we start with the sum/difference between X, Y

E e λ(X+Y ) ≤ E [e 2λX ] E [e 2λY ] ≤ e 4λ 2 σ 2 X 2 e 4λ 2 σ 2 X 2 = e λ 2 2 [2(σ 2 X +σ 2 Y )]
where we used Cauchy-Schwarz inequality and the sub-Gaussianity of X and Y . This proves for rescaled variables that both X + Y and X -Y are sub-Gauss

√ 2 σ 2 X + σ 2 Y , therefore their rescaled versions X+Y 2 and X-Y 2 are sub-Gauss √ σ 2 X +σ 2 Y √ 2
. At this point we use the result on square of sub-Gaussian random variables at point 1, to have that Z 1 and Z 2 are both sub-exp 4 √ 2

σ 2 X +σ 2 Y 2 , 4 σ 2 X +σ 2 Y 2
. Again we use Cauchy-Schwarz due to the dependency between the random variables Z 1 and Z 2 in the first inequality in the next equation

E e λ(XY -E[XY )] = E e λ(Z 1 -Z 2 ) ≤ E [e 2λZ 1 ] E [e -2λZ 2 ] ≤ e + 4λ 2 2 8(σ 2 X +σ 2 Y ) 2 which holds for λ ≤ 1 2(σ 2 X +σ 2 Y )
. This proves that the sub-exponential parameters are indeed

ν ≜ 4 √ 2 σ 2 X + σ 2 Y and α ≜ 2 σ 2 X + σ 2 Y .
Lemma F.2 (Concentration of Correlated First and Second-stage Noise). For sub-Gaussian firstand second-stage noises with parameters σ η and σ ϵ , and first-stage parameter estimates satisfying

Θ -1 t 2 ≤ L Θ -1 (Lemma C.1), we show that T t=1 ∆β ⊤ t-1 (ϵ t η t -γ) ≤ 8e 2 σ 2 η + σ 2 ϵ √ dL Θ -1 b T -1 (δ) 2 log(2/δ) C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + max 1 λ , 2 λ min (Σ) log(2/δ)
with probability at least 1 -δ ∈ [0, 1).

Proof. The proof proceeds in steps and the main technical difficulty arises from the dependence between the random variables, which we tackle using Lemma F.1 plus some techniques derived from the equivalent characterizations of sub-Gaussians and sub-exponential random variables. 1. We bound the p-th moment of the random variable z i ≜ (ϵ s,i η s -γ i ) using the result from Lemma F.1 for the product of two non independent random variables. The random variable z i is the centered product of η s and ϵ s,i which are sub-Gaussians, therefore it is sub-exp (ν i , α i )

with ν i ≜ 4 √ 2 σ 2 ϵ + σ 2 η , α i ≜ 2 σ 2 ϵ + σ 2 η . We can also take K 5 ≜ max α i , ν i √ 2 = 4 σ 2 ϵ + σ 2 η which implies E e λz i ≤ e λ 2 K 2 5 ∀|λ| ≤ 1 K 5
, and together with the inequality |x| p ≤ p p (e x + e -x ) we obtain

E z i K 5 p ≤ E p p exp z i K 5 + exp - z i K 5 ≤p p 2e K 2 5 /K 2 5 ≤ 2ep p
The previous inequality directly implies an inequality on the p-th norm of the random variable

ϵ s,i η s -γ i p E [|ϵ s,i η s -γ i | p ] ≤ p √ 2eK 5 p ≤ 2eK 5 p = 4e σ 2 ϵ + σ 2 η p ≜ K 2 p 2.
We finally find the sub-exponential parameters for the scalar product ∆β T s-1 (ϵ s η s -γ). Using the sub-exponential characterization with L p norm we have ∀p ≥ 1

∆β T s-1 (ϵ s η s -γ) p ≤ d i=1 ∆β s-1,i ∥ϵ s,i η s -γ∥ p ≤ d i=1 ∆β s-1,i K 2 p = K s p (19)
where

K s ≜ d i=1 ∆β s-1,i K 2 ≜ 4e σ 2 ϵ + σ 2 η d i=1 ∆β s-1,i
We are ready to bound the moment-generating function and derive the

E e λ i ∆β s-1,i (ϵ s,i ηs-γ i ) | F s-1 = E   ∞ p=0 λ p ∆β ⊤ (ϵ s η s -γ) p p!   (series expansion) = ∞ p=0 λ p p! E ∆β ⊤ (ϵ s η s -γ) p (linearity of expectation) = 1 + ∞ p=2 λ p E ∆β ⊤ (ϵ s η s -γ) p p! (1st moment = 0) ≤ 1 + ∞ p=2 λ p K p s p p p! (Equation (19)) ≤ 1 + ∞ p=2 λ p K s p e p (Stirling's approximation p! ≥ p p e p ) = 1 + (λK s e) 2 1 -λK s e (expression valid ∀|λ| ≤ 1 Kse ) ≤ 1 + 2 (λK s e) 2 (valid for |λ| ≤ 1 2Kse ) ≤ e 2λ 2 K 2 s e 2 (using 1 + x ≤ e x 2 for all x ∈ R)
Therefore we have that ∆β T s-1 (ϵ s η s -γ) is sub-exp(2K s e, 2K s e). We finally substitute for K s and we obtain

∆β T s-1 (ϵ s η s -γ) ∼ sub-exp 8e 2 σ 2 ϵ + σ 2 η ∆β s-1 1 , 8e 2 σ 2 ϵ + σ 2 η ∆β s-1 1
3. We are now ready to derive the concentration for the sum of the martingale difference sequence using Theorem F.1. From Theorem F.1 we have that

T t=1 D t ≤ 2 log(2/δ) t ν 2 s + 2α * log(2/δ
) with probability bigger than 1 -δ. With the following substitutions:

D t → ∆β ⊤ t-1 (ϵ t η t -γ) , α * → 8e 2 σ 2 ϵ + σ 2 η max s ∆β s-1 1 , ν s → 8e 2 σ 2 ϵ + σ 2 η ∆β s-1 1
we obtain that with probability bigger than 1 -δ

T t=1 ∆β ⊤ t-1 (ϵ t η t -γ) ≤ 2 log 2 δ (8e 2 ) 2 σ 2 η + σ 2 ϵ 2 T t=1 ∆β t-1 2 1 + 8e 2 σ 2 η + σ 2 ϵ max t ∆β t-1 1 log(2/δ)
4. We study the term ∆β t-1 1 , its sum and maximum over t, which we need to substitute in the previous concentration bound. We can bound ∆β t-1

2 1 ≤ d ∆β t-1 2
2 and then use some matrix tricks in the following for the individual terms

∆β t-1 2 2 = H -1/2 H 1/2 ∆β t-1 2 2 ≤ H -1/2 t-1 2 2 ∆β t-1 2 H t-1 (Proposition A.1) ≤ H -1 t-1 2 b t-1 (δ) (Lemma D.1) ≤ L 2 Θ -1 G -1 z,t-1 2 b T -1 (δ) (again Proposition A.1)
When we take the sum over the rounds we have

T t=1 ∆β t-1 2 1 ≤ d T t=1 ∆β t-1 2 2 ≤ dL 2 Θ -1 b T -1 (δ) T t=1 G -1 z,t-1 2 (Proposition A.1) ≤ dL 2 Θ -1 b T -1 (δ) C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) (from Lemma B.2)
For the maximum, we have instead max

t ∆β t-1 1 ≤ √ dL Θ -1 b T -1 (δ)~G -1 z,t-1 ~2 ≤ √ dL Θ -1 b T -1 (δ) max 1 λ , 2 λ min (Σ)
Finally, we can substitute back these expressions in the bound at the previous point. We have that with a probability bigger than 1 -δ

T t=1 ∆β ⊤ t-1 (ϵ t η t -γ) ≤ 2 log(2/δ) (8e 2 ) 2 σ 2 η + σ 2 ϵ 2 dL 2 Θ -1 b T -1 (δ) C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + 8e 2 σ 2 η + σ 2 ϵ √ dL Θ -1 b T -1 (δ) max 1 λ , 2 λ min (Σ) log(2/δ)
Lemma F.3 (Bias of Correlated First and Second-stage Noise). Under the same hypothesis of previous lemmas we can bound the bias term in the following way

T t=1 ∆β ⊤ t-1 γ ≤ ∥γ∥ 2 L Θ -1 b T (δ) C 3 √ λ + 2 √ 2T λ min (Σ)
Proof. The bias term has a much simpler analyis

T t=1 ∆β ⊤ t-1 γ ≤ T t=1 ∥∆β t-1 ∥ Ht ∥γ∥ H -1 t (from Cauchy-Schwarz) ≤ b T -1 (δ) T t=1 ∥γ∥ Θ -1 t G -1 z,t Θ -⊤ t (from Lemma D.1 and b T -1 increasing) ≤ b T -1 (δ)∥γ∥ 2 L Θ -1 T t=1 G -1 z,t-1 2 (from Proposition A.1) ≤ b T -1 (δ)∥γ∥ 2 L Θ -1   C 3 t=1 1 √ λ + T -1 t=C 3 +1 2 λ min (Σ)t   (from Lemma B.2) ≤ b T -1 (δ)∥γ∥ 2 L Θ -1 C 3 √ λ + 2 √ 2T λ min (Σ)
where the last inequality follows from n k=1

1 √ k = n k=1 k k-1 dx √ k ≤ n k=1 k k-1 dx √ x = n 0 dx √ x = 2 √ n.
G. Regret Analysis for IV Regression: O2SLS

In this section, we elaborate on the proofs and techniques to bound the regret of O2SLS.

Remark G.1. In Appendix J, we describe that the first stage regression in O2SLS can be expressed as running d independent ridge regressions for each column of Θ (Equation ( 27)). Since the standard analysis of each of the ridge regressions assume independent and sub-Gaussian noise added in the linear model (cf. Theorem J.1; [START_REF] Ouhamma | Stochastic online linear regression: the forward algorithm to replace ridge[END_REF])), we assume that each component of the first stage noise, i.e. ϵ t,i , corresponding to the i-th ridge regression is sub-Gauss(σ ϵ ). Thus, we obtain that E∥ϵ t ∥ 2 2 ≤ dσ 2 ϵ . For the rest of the paper, we use this bound for the expected value of the norm of the first stage noise.

Theorem G.1 (Identification Regret of O2SLS). If Assumption 3.1 holds true, then for a first stage noises that is a componentwise sub-Gaussian(σ ϵ ) r.v., a second stage noise that is sub-Gaussian(σ η ), first-stage parameters with bounded ℓ 2 -norm ~Θ~2 ≤ L Θ , bounded IVs ∥z∥ 2 ≤ L 2 z and a fixed expect value

E[η s ϵ s ] ≜ γ ∈ R d , the regret of O2SLS at step T is R T ≤ b T -1 (δ) Estimation O(d log T )         L 2 Θ -1 L 2 Θ L 2 z + dσ 2 ϵ C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + C 4 Second Stage Feature norm O(d log T )         = O d 2 log 2 (T )
with probability at least 1-δ ∈ [0, 1). Here, b T -1 (δ) is the confidence interval defined by Lemma 4.1, the estimates of the first-stage parameters are bounded according to Equation (14 Proof of Theorem. We bound it (a) using the confidence bound to control the concentration of β t around β, and (b) by bounding the sum of feature norms according to the following decomposition.

), i.e. ~ Θ -1 t ~2 ≤ L Θ -1 , C 3 is defined in Lemma B.
Step 1: By applying Cauchy-Schwarz inequality, we first decouple the effect of parameter estimation and the feature norms

β t-1 -β ⊤ x t ≤ β t-1 -β Ht ∥x t ∥ H -1 t ≤ b t-1 (δ) ∥x t ∥ Θ ⊤ t-1 G z,t-1 Θ t-1 -1 (20)
where we used the definition of H t ≜ Θ ⊤ t-1 G z,t-1 Θ t-1 and Lemma D.1. The last inequality holds with probability at least 1 -δ. Since b t is monotonically increasing in t, by Equation (20),

T t=1 β t-1 -β ⊤ x t 2 ≤ b T -1 (δ) T t=1 ∥x t ∥ 2 Θ ⊤ t-1 G z,t-1 Θ t-1 -1 .
Step 2: Now, we need to bound the sum of the feature norms, for which we can directly use the result of Lemma C.3

T t=1 ∥x t ∥ 2 Θ -1 t-1 G -1 z,t-1 Θ -⊤ t-1 ≤ L 2 Θ -1 L 2 Θ L 2 z + dσ 2 ϵ C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + C 4 (21)
Step 3: By combining the results of the previous steps and considering the definition of b T -1 (δ), we conclude that we can bound the Identification Regret as follows, and its orders is O d 2 log 2 (T )

T t=1 β t-1 -β ⊤ x t 2 ≤ b T -1 (δ) O(d log T )   L 2 Θ -1 L 2 Θ L 2 z + dσ 2 ϵ C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + C 4   O(d log T )
Theorem G.2 (Oracle Regret of O2SLS). If Assumption 3.1 hold true, then for first stage noises that is componentwise sub-Gaussian(σ ϵ ) and second stage noise that is sub-Gaussian(σ η ), first-stage parameters with bounded ℓ 2 -norm ~Θ~2 ≤ L Θ , bounded IVs ∥z∥ 2 ≤ L 2 z and bounded expect value Proof of Theorem. By Equation ( 4), defining ∆β t-1 ≜ β t-1 -β , the instantaneous regret at step t is

E[η s ϵ s ] ≜ γ, the regret of O2SLS at step T is R T ≤ b T -1 (δ) Estimation O(d log T )         L 2 Θ -1 L 2 Θ L 2 z + dσ 2 ϵ C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + C 4 Second Stage Feature norm O(d log T )         + b T -1 (δ) Estimation O( √ d log T )          σ η L Θ -1 L Θ L z C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) First Stage Feature Norm O( √ log T ) +8e 2 σ 2 η + σ 2 ϵ √ dL Θ -1 2 log 2 δ C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + max 1 λ , 2 λ min (Σ) log 2 δ Correlated noise Concentration Term O( √ d log T ) + ∥γ∥ 2 L Θ -1 C 3 √ λ + 2 √ 2T λ min (Σ) Correlated noise Bias Term O(∥γ∥ 2 √ T )            = O (d log T ) 2 + ∥γ∥ 2 dT
R t ≜ ℓ t β t-1 -ℓ t (β) = y t -β ⊤ t-1 x t 2 -y t -β ⊤ x t 2 = β t-1 -β ⊤ x t -η t 2 -η 2 t = β t-1 -β ⊤ x t 2 + 2η t β t-1 -β ⊤ x t = ∆β ⊤ t-1 x t 2 + 2η t ∆β ⊤ t-1 x t
Since x t = Θ ⊤ z t + ϵ t by (First stage), the second term can be rewritten substituting as

2η t ∆β ⊤ t-1 x t = 2η t ∆β ⊤ t-1 Θ ⊤ z t + 2η t ∆β ⊤ t-1 ϵ t
Therefore, the cumulative regret or regret R T by horizon T is

T t=1 R t = T t=1 ∆β ⊤ t-1 x t 2 (•1•) +2 T t=1 η t ∆β ⊤ t-1 Θ ⊤ z t (•2•) +2 T t=1 η t ∆β ⊤ t-1 ϵ t (•3•) (22)
The proof proceeds by bounding each of the three terms individually.

Term 1: Second-stage Regression Error. The first term (•1•) quantifies the error introduced by the second stage regression. This is exactly equal to the Identification Regret that we bounded in Theorem G.1. Therefore we know that it is bounded as

(•1•) ≤ b T -1 (δ) O(d log T ) L 2 Θ -1 L 2 Θ L 2 z + dσ 2 ϵ C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + C 4 O(d log T ) = O d 2 log 2 (T )
Term 2: Coupling of First-stage Data and Second-stage Parameter Estimation. Now, we bound (•2•) using martingale inequalities similar to the ones used for the confidence intervals to derive a uniform high probability bound.

Step 1: Following Theorem I.2, we define

w s ≜ β s-1 -β ⊤ Θ ⊤ z s and F t-1 ≜ σ (z 1 , ϵ 1 , η 1 , . . . , z t-1 , ϵ t-1 , η t-1 , z t ) .
It is immediate to verify that the hypothesis are satisfied, since w t is F t-1 -measurable as β t-1 and z t are too. Bearing in mind this substitution we have

T t=1 η t w t ≤ 2 1 + σ 2 η T t=1 w 2 t log   1 + σ 2 η T t=1 w 2 t δ   (23)
with probability at least 1 -δ.

Step 2: Thus, we proceed like for the first term in the Step 2 for Term 1:

T t=1 β t-1 -β, Θ ⊤ z t 2 ≤ b T -1 (δ) T t=1 Θ ⊤ z t 2 Θ ⊤ t-1 G z,T -1 Θ t-1 -1
(Cauchy-Schwarz and Lemma D.1)

≤ b T -1 (δ) T t=1 G -1 z,t-1 2 Θ -1 t-1 2 2 Θ ⊤ z t 2 2 (Proposition A.1) ≤ b T -1 (δ)L 2 Θ -1 T t=1 G -1 z,t-1 2 ~Θ~2 2 ∥z t ∥ 2 2 (Proposition A.1 and definition of L 2 Θ -1 ) ≤ b T -1 (δ)L 2 Θ -1 L 2 Θ L 2 z T t=1 G -1 z,t-1 2 (boundedness of z t and definition of L Θ ) = b T -1 (δ) O(d log T ) L 2 Θ -1 L 2 Θ L 2 z C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) O(log T ) (from Lemma B.2) = O d(log T ) 2
where in the first inequality we also used the fact that b t-1 (δ) is monotonically increasing in t, to take the radii outside the summation.

Step 3: Thus, substituting inside Equation ( 23), the order of (

•2•) is negligible with respect to term (•1•) 2 T t=1 η t (β t-1 -β) ⊤ Θ ⊤ z t ≤ 2 1 + b T -1 (δ)σ 2 η L 2 Θ -1 L 2 Θ L 2 z C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) O( √ d log T ) log 1 + b T -1 (δ)σ 2 η L 2 Θ -1 L 2 Θ L 2 z C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) δ O √ log( √ d log T ) = O √ d log T log( √ d log T )
with probability at least 1 -δ.

Term 3: Coupling of First-and Second-stage Noises. We bound the term (•3•) containing the self-fulfilling bias, i.e. the correlation between the first-and second-stage noise, by splitting it into two contributions.

T t=1 η t (β t-1 -β ∆β t-1 ) ⊤ ϵ t = T t=1 ∆β ⊤ t-1 (ϵ t η t ) + T t=1 ∆β ⊤ t-1 E t [ϵ t η t ] - T t=1 ∆β ⊤ t-1 E t [ϵ t η t ] = T t=1 ∆β ⊤ t-1 ϵ t η t - T t=1 ∆β ⊤ t-1 γ + T t=1 ∆β ⊤ t-1 γ = T t=1 ∆β T t-1 (ϵ t n t -γ) Martingale Concentration Term O(log(T )) + T t=1 ∆β ⊤ t-1 γ Bias Term O( √ T ) (24)
Now we can use Lemma F.2 and Lemma F.3 to conclude that term (•3•) is bounded by the following quantity

8e 2 σ 2 η + σ 2 ϵ L Θ -1 db T -1 (δ) 2 log( 2 δ ) C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + max 1 λ , 2 λ min (Σ) log 2 δ d log(T ) + b T -1 (δ)∥γ∥ 2 L Θ -1 C 3 √ λ + 2 √ 2T λ min (Σ) O(∥γ∥ 2 √ dT log T )
H. Regret Analysis for IV Linear Bandits: OFUL-IV Theorem H.1. Under the same assumptions as that of Theorem 4.2, Algorithm 2 incurs a regret

R T = T t=1 r t ≤ 2 √ T b T -1 (δ) L 2 Θ -1 L 2 Θ L 2 z + dσ 2 ϵ C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + C 4
with probability 1 -δ, horizon T > 1 and C 4 is defined in eq. (17).

Proof. The instantaneous regret r t reads

⟨β, x * ⟩ -⟨β, x t ⟩ ≤ β t-1 , x t -⟨β, x t ⟩ (since (x t , β t-1 ) is optimistic inside X t × B t ) = β t-1 -β, x t + β t-1 -β t-1 , x t (summing and subtracting β t-1 ) ≤ β t-1 -β Θ ⊤ t-1 G z,t-1 Θ t-1 ∥x t ∥ Θ ⊤ t-1 G z,t-1 Θ t-1 -1 + β t-1 -β t-1 Θ ⊤ t-1 G z,t-1 Θ t-1 ∥x t ∥ Θ ⊤ t-1 G z,t-1 Θ t-1 -1 (Cauchy-schwarz ineq.) ≤ 2 b t-1 (δ) ∥x t ∥ Θ ⊤ t-1 G z,t-1 Θ t-1 -1 (Lemma D.1)
The last inequality uses the concentration of β t around the true value β, and the fact that we choose β t-1 inside B t-1 . In both cases, the two norms are bounded by the radius of the ellipsoid, i.e. b t-1 (δ). Since we already know in this case how to concentrate the sum of the features norms

T t=1 ∥x t ∥ 2 Θ -1 t-1 G -1 z,t-1 Θ -⊤ t-1
from Lemma C.3, we bound the cumulative regret using Cauchy-Schwarz inequality in the first inequality below, and we substitute the bound on the instantaneous regret that we just obtained:

R T ≤ T T t=1 r 2 t ≤ 2 T T t=1 b t-1 (δ) ∥x t ∥ 2 Θ -1 t-1 G -1 z,t-1 Θ -⊤ t-1 ≤ 2 √ T b T -1 (δ) T t=1 ∥x t ∥ 2 Θ -1 t-1 G -1 z,t-1 Θ -⊤ t-1 (25)
where in the second inequality, we used the fact that the radius b t-1 (δ) is monotonically increasing in t. Now, we can use Lemma C.3 to bound the sum of feature norms, and putting all together, we obtain the following bound:

R T ≤ 2 √ T b T -1 (δ) O( √ d log T ) L 2 Θ -1 L 2 Θ L 2 z + dσ 2 ϵ C 3 + 1 λ + 2 log(T ) + 1 λ min (Σ) + C 4 O( √ d log T ) = O d √ T log T .

I. Concentration of Scalar and Vector-valued Martingales

We look for deviations of the vector martingales t s=1 η s z s and the scalar valued martingale

T t=1 η t β t-1 -β ⊤ Θ ⊤ z t
from their expected values. These results are required in the proof of Theorem G.2. The first martingale is vector-valued while the second is scalar-valued. For the vector-valued martingale, we want to bound its deviations when its values are weighted by the inverse of its design matrix G -1

z,t like it appears in ∥s t ∥ 2 G -1 z,t
. The design matrix G -1 z,t is itself derived from the martingale. Hence, it is called the 'self-normalized bound'. The following theorems were introduced in (Abbasi- Yadkori et al., 2011a[START_REF] Abbasi-Yadkori | Online-to-confidence-set conversions and application to sparse stochastic bandits[END_REF] for the two cases. We state and prove them here for completeness. We leverage the fact that the first and second stage noises are sub-Gaussian random variables.

Lemma I.1. Let µ ∈ R d be arbitrary and consider for any t ≥ 0

m µ t ≜ t s=1 exp η s ⟨µ, z s ⟩ σ 2 - 1 2 ⟨µ, z s ⟩ 2 .
Let τ be a stopping time with respect to the filtration {F t } ∞ t=0 . Then, m µ τ is a.s. well-defined and E m µ τ ≤ 1.

Proof. We claim that m µ t ∞ t=0 is a supermartingale. Let

d µ t ≜ exp η t ⟨µ, z t ⟩ σ 2 - 1 2 ⟨µ, z t ⟩ 2 .
Observe that by conditional R-sub-Gaussianity of η t we have

E d µ t | F t-1 ≤ 1. Clearly, d µ t is F t -measurable, as is m µ t . Further, E m µ t | F t-1 = E m µ 1 • • • d µ t-1 d µ t | F t-1 = d µ 1 • • • d µ t-1 E d µ t | F t-1 ≤ m µ t-1 ,
showing that m µ t ∞ t=0 is indeed a supermartingale and in fact E m µ t ≤ 1. Now, we argue that m µ τ is well-defined. By the convergence theorem for nonnegative supermartingales, M µ ∞ = lim t→∞ m µ t is almost surely well-defined. Hence, m µ τ is indeed well-defined independently of whether τ < ∞ holds or not. Next, we show that E m µ τ ≤ 1. For this let

Q µ t = M µ min{τ,t} be a stopped version of m µ t t . By Fatou's Lemma, E m µ τ = E lim inf t→∞ Q µ t ≤ lim inf t→∞ E Q µ t ≤ 1, showing that E m µ τ ≤ 1 indeed holds.
Next lemma uses the "method of mixtures" technique, (Lattimore and Szepesvári, 2020) Chapter 20.

Lemma I.2. Let {F t } ∞ t=0 be a filtration. Let τ be a stopping time with respect to the filtration {F t } ∞ t=0 . Then, for any δ > 0, with probability 1 -δ

∥s τ ∥ 2 G -1 z,τ ≤ 2σ 2 2 log det (G z,τ ) 1/2 λ -d/2 δ .
and substituting back the definition of G z,t gives

P ∥s τ ∥ 2 G -1 z,τ
> 2 log det (G z,τ ) 1/2 δλ d/2 ≤ δ.

Theorem I.1 (Self-Normalized Bound for Vector-Valued Martingales). Let {F t } ∞ t=0 be a filtration. Let {η t } ∞ t=1 be a real-valued stochastic process such that η t is F t -measurable and η t is conditionally σ 2 -sub-Gaussian for some σ 2 ≥ 0 i.e. ∀λ ∈ R holds

E e ληt | F t-1 ≤ exp λ 2 σ 2 2 2 .
Let {z t } ∞ t=1 be an R d -valued stochastic process such that z t is F t-1 -measurable. For any t ≥ 0, define s t = t s=1 η s z s . Then, for any δ > 0, with probability at least 1 -δ, for all t ≥ 0,

∥s t ∥ 2 G -1 z,t ≤ 2σ 2 2 log det (G z,t ) 1/2 λ -d/2 δ
Proof. We will use a stopping time construction, which goes back at least to [START_REF] David A Freedman | On tail probabilities for martingales[END_REF]. Define the bad event

B t (δ) = ω ∈ Ω : ∥s t ∥ 2 G -1 z,t > 2σ 2 2 log det (G z,t ) 1/2 det(V) -1/2 δ
We are interested in bounding the probability that t≥0 B t (δ) happens. Define τ (ω) = min{t ≥ 0 : ω ∈ B t (δ)}, with the convention that min ∅ = ∞. Then, τ is a stopping time. Further, det (G z,τ ) 1/2 det(V) -1/2 δ ≤ δ.

Lemma I.3. Let (F t ) t≥0 be a filtration such that w t is F t-1 measurable and η t is F t measurable and is conditionally σ 2 -sub-Gaussian. Let τ be a stopping time w.r.t. to this filtration i.e. the event {τ ≤ t} belongs to F t . The following sequence of random variables is a martingale with respect to F t : s t = t s=1 η s w s . Furthermore, for any δ > 0, σ 2 > 0, with probability at least 1 -δ:

|s τ | ≤ σ 2 2
E m λ t | F t-1 = E m λ 1 • • • d λ t-1 d λ t | F t-1 = d λ 1 • • • d λ t-1 E d λ t | F t-1 ≤ m λ t-1 ,
showing that m λ t ∞ t=0 is indeed a supermartingale. Next we show that m λ τ is always well-defined and E m λ τ ≤ 1. First define M = m λ τ and note that M (ω) = M λ τ (ω) (ω). Thus, when τ (ω) = ∞, we need to argue about M λ ∞ (ω). By the convergence theorem for nonnegative supermartingales, lim t→∞ m λ t (ω) is well-defined, which means m λ τ is well-defined, independently of whether τ < ∞ holds or not. Now let Q λ t = M λ min{τ,t} be a stopped version of m λ t . We proceed by using Fatou's Lemma to show that E m λ τ = E lim inf t→∞ Q λ t ≤ lim inf t→∞ E Q λ t ≤ 1. Let Λ ∼ N 0, σ 2 2 be a Gaussian random variable and define

m t = E m Λ t | F ∞ . Clearly, we still have E [m t ] = E E m Λ t | Λ ≤ 1.
Let us calculate m t . We will need the density λ which is

f (λ) = 1 √ 2πσ 2 2
e -λ 2 /2σ 2 2 . Now, it is easy to write m t explicitly

m t = E m Λ t | F ∞ = ∞ -∞ m λ t f (λ)dλ = 1 2πσ 2 2 ∞ ∞ exp λs t σ 2 - λ 2 2 t s=1 w 2 s e -λ 2 /2σ 2 2 dλ = exp s 2 t 2σ 2 2 1 /σ 2 2 + t s=1 w 2 s 1 1 + σ 2

J. Parameter Estimation and Concentration in First Stage

There are many ways of addressing the regression problem in the first stage and they fundamentally reduce to a choice for the regularizer in the regression. If we do not introduce such regularizer, we are left with a system of multiple regressions that can be solved with standard OLS (estimator).

Another choice is to introduce a Frobenius norm regularizer. We introduce the parameter λ > 0 and a regularization term λ~Θ~2 F , which is used to penalize the model complexity. By choosing the Frobenius norm, the system of equations decouples again but each with a regularizer term. Thus, we end up with d independent linear equations that we try to fit separately. More interesting settings could try to solve the optimization problem jointly by a regularizer that couples the equations (e.g. [START_REF] Martin | High-dimensional statistics: A non-asymptotic viewpoint[END_REF] provides concentration results for such settings). This will be interesting to investigate in future works.

We indicate with θ j the j-th column of the matrix Θ, then Clearly, we can compute separately the columns θ t,j of Θ t as θ t,j ∈ argmin Z ⊤ t x t,j where x t,j is a vector with components x 1,j , . . . , x t,j . The solution to the independent quadratic optimization problems is in matrix notation equal to

Θ t = Z ⊤ t Z t + λI d -1 Z ⊤ t X t
From the decomposition of the problem into multiple independent regressions, we understand that it is enough to concentrate the individual columns of Θ t around the ones of Θ and then to use a union bound to put things together.

Theorem J.1 (Confidence Ellipsoid for Columns in First Stage). Define x t = z ⊤ t θ j + ϵ t,j with ϵ t,j is σ ϵ -sub-Gaussian and assume that θ j 2 ≤ S. Then, for any δ > 0, with probability at least 1 -δ, for all t ≥ 0, θ j lies in the set

E t =    θ j ∈ R d : θ t,

  C 4 are d and T -independent positive constants (Appendix G), and λ min (Σ) is the minimum eigenvalue of the true covariance matrix of IVs, i.e. Σ ≜ E[zz ⊤ ].

  and C 4 are the d and T -independent positive constants (as in Thm. 4.1 and App.

Figure 2 :

 2 Figure 2: We compare instantaneous regrets (left) of OFUL and OFUL-IV in a linear bandit setting. We show the MSE between the parameters estimated by the two algorithms and the true parameter β (right). OFUL-IV incurs lower instantaneous regret and MSE.

Lemma B. 1 .

 1 For two symmetric matrices A and B |λ min (A) -λ min (B)| ≤ ~A -B~2.

  2, C 4 in Lemma C.2, λ > 0 is the regularization parameter of the first stage and λ min (Σ) is the minimum eigenvalue of the true covariance matrix of IVs, i.e. Σ ≜ E[zz ⊤ ]. Remark G.2. In order to shorten the result and clarify the dimension d-dependence and Tdependence in Theorem 4.1, we further defineC 1 ≜ L Θ -1 L Θ L z , C 2 ≜ L Θ -1 σ ϵ .We also define the constants C 3 and C 4 respectively in Equation (13) and Equation (17). We defineC ′ 3 ≜ C 3 + 1 and f (T ) ≜ C ′ 3 λ + log(T )+1λ min (Σ)/2 . Since these constants are d-and T -independent, and b T -1 (δ) is O (d log(T )), we obtain that the Identificaiton Regret of O2SLS is O d 2 log 2 (T ) .

  log T with probability at least 1 -δ ∈ [0, 1). Here, b T -1 (δ) is the confidence interval defined by Lemma 4.1, the estimates of the first-stage parameters are bounded according to Equation (14), i.e. ~ Θ -1 t ~2 ≤ L Θ -1 , C 3 is defined in Lemma B.2, C 4 in Lemma C.2, λ > 0 is the regularization parameter of the first stage and λ min (Σ) is the minimum eigenvalue of the true covariance matrix of IVs, i.e. Σ ≜ E[zz ⊤ ]. Remark G.3. In order to shorten the result and clarify the dimension d-dependence and Tdependence in Theorem 4.2, we further define C 1≜ L Θ -1 L Θ L z , C 2 ≜ L Θ -1 σ ϵ .We also define the constants C 3 and C 4 respectively in Equation (13) and Equation (17). Finally, the constantsC 5 ≜ 8e 2 σ 2 η + σ 2 ϵ L Θ -1 log(2/δ), C 6 ≜ C 5 max 1 λ , 2 λ min (Σ) log(2/δ),and f (T ) ≜ C ′ 3 λ + log(T )+1 λ min (Σ)/2 . We also define γ ≜ ∥γ∥ 2 = ∥E[η s ϵ s ]∥ 2 . Since these constants are d-and T -independent, and b T -1 (δ) is O (d log(T )), we obtain that the Identificaiton Regret of O2SLS is O d 2 log 2 (T ) and the Oracle Regret is O(d 2 log 2 T + γ √ dT log T ).

  t≥0 B t (δ) = {ω : τ (ω) < ∞} Thus,

  aλ -bλ 2 = exp a 2 /(4b) π/b. To finish the proof, we use Markov's inequality and the fact that E [m τ ] ≤ 1 : 2 (Self-normalized Bound for Scalar Valued Martingales). Under the same assumptions as the previous theorem, for any δ > 0, with probability at least 1 -δ, for all t ≥ 0, t s=1 η t w t ≤ σ 2 2 1/σ 2 in bounding the probability that t≥0 B t (δ) happens. Define τ (ω) = min {t ≥ 0 : ω ∈ B t (δ)}, with the convention that min ∅ = ∞. Then, τ is a stopping time. Further, t≥0 B t (δ) = {ω : τ (ω) < ∞} Thus, by the previous theorem it holds that

  j = Z ⊤ t Z t + λI d -1

  .3 Technical Lemmas Lemma A.1 (Determinant-Trace Inequality). Suppose z 1 , z 2 , . . . , z t ∈ R d and for any 1≤ s ≤ t, ∥z s ∥ 2 ≤ L z . Let G z,t = λI + t s=1 z s z ⊤ s for some λ > 0. Then, det (G z,t ) ≤ λ + tL 2 z /dProof. Let α 1 , α 2 , . . . , α d be the eigenvalues of G z,t . Since G z,t is positive definite, its eigenvalues are positive. Also, note that det(G z,t ) = d s=1 α s and Tr (G z,t ) =

	d s=1 α s . By inequality of
	arithmetic and geometric means,

d

(10)

  This follows by solving for β * in ∂ β

* E xy (y -xβ * ) 2 = 0, and by substituting for the definition of y in E[xy] = E xx ⊤ β * (provided that we can invert the covariance matrix E xx ⊤ ). Under exogeneity E[xη] = 0 and the MMSEE conicedes with β. Instead, in the more realistic case of endogenous noise E[xη] ̸ = 0 and the MMSEE estimator is biased with respect to the oracle β.

This reveals that if we want to perform well at prediction time, we don't actually want an estimator for the oracle β, but we want to use an estimator of the MMSE, which can be done in by taking the Empirical Risk Minimizer (ERM). This would lead us to the OLS estimator for regression but without the nice properties of unbiasedness that it has in the exogenous setting. If we don't account for this endogeneity, we end up with a biased estimate that generalizes well but has no causal meaning.

  The fact that it is a martingale follows from the conditional sub-Gaussianity. Then for λ ∈ R d , t > 0 we define Since τ be a stopping time with respect to the filtration {F t } ∞ t=0 we can show that m λ τ is well-defined almost surely and E m λ τ ≤ 1. We start by proving that m λ t ∞ t=0 is a supermartingale. Clearly, d λ t is F t -measurable, as is m λ t . Further,

	d λ t =	λη t w t σ 2		-	λ 2 2	w 2 t
	1/σ 2 2 +	τ t=1	w 2 t		log	 	1 + σ 2 2 δ	τ t=1 w 2 t	 
	Proof. m λ t = exp	λ s t σ 2	-	λ 2 2	t s=1	w 2 s

  j -θ j Gz,t ≤ σ ϵ 2 log det (G z,t ) 1/2 det(λI d )

	δ	-1/2	+ λ 1/2 S	 



Furthermore, if for all t ≥ 1, ∥z t ∥ 2 ≤ L z then with probability at least 1 -δ, for all t ≥ 0,

θ t,j -θ j Gz,t ≤ σ ϵ d log 1 + tL 2 z/λd δ + λ 1/2 S

One can argue whether these are either sufficient or weak IVs. For simplicity, we assume sufficiency here, i.e. the IVs can decouple the unobserved confounding.

Matrices and vectors are represented with bold capital and bold small letters, e.g. A and a, respectively.

Proof. We decompose G z,t according to the following notation in order to ease the notation

where V and V t are defined by V ≜ λI d and V t ≜ t s=1 z s z ⊤ s . We can rewrite for example m µ t as follows m µ t = exp ⟨µ,st⟩ σ 2 -1 2 ∥µ∥ 2 Vt . Let µ be a Gaussian random variable which is independent of all the other random variables and whose covariance is

, where F ∞ is the tail σ-algebra of the filtration i.e. the σ-algebra generated by the union of the all events in the filtration. Clearly, we still have

Let us calculate m t . Let f denote the density of µ and for a positive definite matrix P let c(P) = (2π) d / det(P) = exp -1 2 x ⊤ Px dx. Then,

Elementary calculation shows that if P is positive semi-definite and Q is positive definite

which gives

Corollary J.1 (Confidence Ellipsoid for First Stage). Under the conditions of the previous theorem, for any δ > 0, with probability at least 1 -δ, for all t ≥ 0

Now, we aim to compare the empirical performance of O2SLS estimator with the online ridge regression (Ridge) and the Vovk-Azoury-Warmuth Forecaster (VAWf) [START_REF] Orabona | A modern introduction to online learning[END_REF]. The Ridge estimator is given by

We choose the regularisation parameters to be all equal to 10 -3 . We deploy the experiments in Python3 on a single Intel(R) Core(TM) i7-8665U CPU@1.90GHz. An experiment consisting of 100 runs of an algorithm takes approximately ten minutes. We denote the normal distribution with mean µ and standard deviation σ as N (µ, σ), with N n we indicate its multivariate extension to n dimensions. We consider the true parameter of the model to be generated as β∼N 50 ( ⃗ 10, I 50 ) and Θ i,j ∼N (0, 1) for each of its entry. At each time step we sample the vectors z t ∼N 50 ( ⃗ 0, I 50 ), and ϵ t ∼N 50 ( ⃗ 0, I 50 ). The endogenous noise in the second stage is η t = ( η t + 12 i=1 ϵ t,i )/13, where η t ∼N (0, 1) is a r.v. independent from all the others. From Figure 3, we observe that in the presence of endogeneity, Ridge and VAWf have very similar performances and are sensibly worse than O2SLS according to the instantaneous identification regret.