# Online Instrumental Variable Regression: Regret Analysis and Bandit Feedback

Riccardo Della Vecchia, Debabrota Basu

► To cite this version:

Riccardo Della Vecchia, Debabrota Basu. Online Instrumental Variable Regression: Regret Analysis and Bandit Feedback. 2023. [https://hal.science/hal-03831210v2](https://hal.science/hal-03831210v2)

HAL Id: hal-03831210

https://hal.science/hal-03831210v2

Preprint submitted on 20 Feb 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Stochastic Online Instrumental Variable Regression: Regrets for Endogeneity and Bandit Feedback

Riccardo Della Vecchia, Debabrota Basu

<figure><img src="image_1.png" /></figure>

## To cite this version:

Riccardo Della Vecchia, Debabrota Basu. Stochastic Online Instrumental Variable Regression: Regrets for Endogeneity and Bandit Feedback. AAAI Conference on Artificial Intelligence, Feb 2025, Philadelphia, United States. hal-03831210v3

HAL Id: hal-03831210

https://hal.science/hal-03831210v3

Submitted on 9 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Online Instrumental Variable Regression: Regret Analysis and Bandit Feedback

Riccardo Della Vecchia

Équipe Scool, Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189- CRISTAL, F-59000 Lille, France

Debabrota Basu

Équipe Scool, Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189- CRISTAL, F-59000 Lille, France

## Abstract

The independence of noise and covariates is a standard assumption in online linear regression with unbounded noise and linear bandit literature. This assumption and the following analysis are invalid in the case of endogeneity, i.e., when the noise and covariates are correlated. In this paper, we study the online setting of Instrumental Variable (IV) regression, which is widely used in economics to identify the underlying model from an endogenous dataset. Specifically, we upper bound the identification and oracle regrets of the popular Two-Stage Least Squares (2SLS) approach to IV regression but in the online setting. Our analysis shows that Online 2SLS (O2SLS) achieves $O(d^2 \log^2 T)$ identification and $O(\gamma \sqrt{dT} \log T)$ oracle regret after $T$ interactions, where $d$ is the dimension of covariates and $\gamma$ is the bias due to endogeneity. Then, we leverage O2SLS as an oracle to design OFUL-IV, a linear bandit algorithm. OFUL-IV can tackle endogeneity and achieves $O(d\sqrt{T} \log T)$ regret. For datasets with endogeneity, we experimentally show the efficiency of OFUL-IV in terms of estimation error and regret.

## Contents

<table><tr><td>1</td><td>Introduction</td><td>2</td></tr><tr><td>2</td><td>Related Work</td><td>4</td></tr><tr><td>3</td><td>Preliminaries: Instrumental Variables &amp; Offline Two-stage Least Squares (2SLS)</td><td>4</td></tr><tr><td>4</td><td>Online Two-Stage Least Squares Regression</td><td>6</td></tr><tr><td>4.1</td><td>Defining Regrets: Identification and Oracle</td><td>7</td></tr><tr><td>4.2</td><td>Theoretical Analysis</td><td>8</td></tr><tr><td>5</td><td>Linear Bandits with Endogeneity: OFUL-IV</td><td>11</td></tr><tr><td>6</td><td>Conclusions and Future Works</td><td>14</td></tr><tr><td>A</td><td>Useful Results</td><td>18</td></tr><tr><td>A.1</td><td>Random Variables</td><td>18</td></tr><tr><td>A.2</td><td>Norms of Vectors and Matrices</td><td>18</td></tr><tr><td>A.3</td><td>Technical Lemmas</td><td>20</td></tr><tr><td>B</td><td>Concentration of The Minimum Eigenvalue of The Design Matrix</td><td>21</td></tr><tr><td>C</td><td>Technical Lemmas for the Endogeneous Setting</td><td>23</td></tr></table>
# Stochastic Online Instrumental Variable Regression: Regrets for Endogeneity and Bandit Feedback

Riccardo Della Vecchia

Debabrota Basu

Université de Lille, Inria, CNRS,
F-59000 Lille, France

Université de Lille, Inria, CNRS,
F-59000 Lille, France

ric.della-vecchia@gmail.com

debabrota.basu@inria.fr

## Abstract

Endogeneity, i.e. the dependence of noise and covariates, is a common phenomenon in real data due to omitted variables, strategic behaviours, measurement errors etc. In contrast, the existing analyses of stochastic online linear regression with unbounded noise and linear bandits depend heavily on exogeneity, i.e. the independence of noise and covariates. Motivated by this gap, we study the over- and just-identified Instrumental Variable (IV) regression, specifically Two-Stage Least Squares, for stochastic online learning, and propose to use an online variant of Two-Stage Least Squares, namely O2SLS. We show that O2SLS achieves $O(d_x d_z \log^2 T)$ identification and $\tilde{O}(\gamma\sqrt{d_z T})$ oracle regret after $T$ interactions, where $d_x$ and $d_z$ are the dimensions of covariates and IVs, and $\gamma$ is the bias due to endogeneity. For $\gamma = 0$, i.e. under exogeneity, O2SLS exhibits $O(d_x^2 \log^2 T)$ oracle regret, which is of the same order as that of the stochastic online ridge. Then, we leverage O2SLS as an oracle to design OFUL-IV, a stochastic linear bandit algorithm to tackle endogeneity. OFUL-IV yields $\tilde{O}(\sqrt{d_x d_z T})$ regret that matches the regret lower bound under exogeneity. For different datasets with endogeneity, we experimentally show efficiencies of O2SLS and OFUL-IV.

## 1 Introduction

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

Like this example, online regression is a founding component of online learning [Kivinen et al., 2004], sequential testing [Kazerouni and Wein, 2021], contextual bandits [Foster and Rakhlin, 2020], and reinforcement learning [Ouhamma et al., 2022]. Especially, online linear regression is widely used and analysed to design efficient algorithms with theoretical guarantees [Greene, 2003, Abbasi-Yadkori et al., 2011b, Hazan and Koren, 2012]. In linear regression, the outcome (or output variable) $Y \in \mathbb{R}$, and the input features (or covariates, or treatments) $\mathbf{X} \in \mathbb{R}^d$ are related by a structural equation: $Y = \beta^T \mathbf{X} + \eta$, where $\beta$ is the true parameter and $\eta$ is the observational noise with variance $\sigma^2$. The goal is to estimate $\beta$ from an observational dataset. Two common assumptions in the analysis of linear regression are (i) bounded observations and covariates [Vovk, 1997, Bartlett et al., 2015, Gaillard et al., 2019], and (ii) exogeneity, i.e. independence of the noise $\eta$ and the input features $\mathbf{X}$ ($E[\eta|\mathbf{X}] = 0$) [Abbasi-Yadkori et al., 2011b, Ouhamma et al., 2021].
<table><tr><td>D</td><td>Elliptical Lemma for the Endogeneous Setting</td><td>26</td></tr><tr><td>E</td><td>A Detailed Discussion on Different Definitions of Regret</td><td>28</td></tr><tr><td>F</td><td>Lemmas on Correlation between First and Second Stages</td><td>30</td></tr><tr><td>G</td><td>Regret Analysis for IV Regression: O2SLS</td><td>35</td></tr><tr><td>H</td><td>Regret Analysis for IV Linear Bandits: OFUL-IV</td><td>40</td></tr><tr><td>I</td><td>Concentration of Scalar and Vector-valued Martingales</td><td>41</td></tr><tr><td>J</td><td>Parameter Estimation and Concentration in First Stage</td><td>46</td></tr><tr><td>K</td><td>Experiments</td><td>48</td></tr><tr><td>K.1</td><td>Experimental Analysis of O2SLS</td><td>48</td></tr></table>

# 1. Introduction

Online regression is a founding component of online learning (Kivinen et al., 2004), sequential testing (Kazerouni and Wein, 2021), contextual bandits (Foster and Rakhlin, 2020), and reinforcement learning (Ouhamma et al., 2022). Specially, online linear regression is widely used and analysed to design efficient algorithms with theoretical guarantees (Greene, 2003; Abbasi-Yadkori et al., 2011b; Hazan and Koren, 2012). In linear regression, the *outcome* (or output variable) $Y \in \mathbb{R}$, and the *input features* (or covariates, or treatments) $\mathbf{X} \in \mathbb{R}^d$ are related by a structural equation:

$$Y = \beta^T \mathbf{X} + \eta,$$

where $\beta$ is the *true parameter* and $\eta$ is the observational noise with variance $\sigma^2$. The goal is to estimate $\beta$ from an observational dataset. Two common assumptions in the analysis of linear regression are (i) bounded observations and covariates (Vovk, 1997; Bartlett et al., 2015; Gaillard et al., 2019), and (ii) exogeneity, i.e. independence of the noise $\eta$ and the input features $X$ ($E[\eta|X] = 0$) (Abbasi-Yadkori et al., 2011b; Ouhamma et al., 2021). Under exogeneity, researchers have studied scenarios, where the observational noise is unbounded and has only bounded variance $\sigma^2$. Ouhamma et al. (2021) 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[\eta|X] \neq 0$) (Greene, 2003; Angrist et al., 1996). Endogeneity arises due to omitted explanatory variables, measurement errors, dependence of the output and the covariates on unobserved confounding variables etc. (Wald, 1940; Mogstad et al., 2021; Zhu et al., 2022). In this paper, we analyse online linear regression that aims to estimate $\beta$ 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 (Newey and Powell, 2003). IVs are widely used in economics (Wright, 1928; Mogstad et al., 2021), causal inference (Rabin, 1974; Hernan and Robins, 2020; Harris et al., 2022), bio-statistics and epidemiology (Burgess et al., 2017).

**Example 1.1.** Carneiro et al. (2011); Mogstad et al. (2021) 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
<figure><img src="image_3.png" /><figcaption>(a) Graphical Model of Example 1.1</figcaption></figure>

$$ \text{Price}_t = \theta \times \underbrace{\text{MaterialCost}_t}_{\text{IV } z_t} + \rho_F \times \underbrace{\text{Event}_t + \epsilon_{F,t}}_{\epsilon_t} $$

-First Stage-

$$ \underbrace{\text{Sales}_t}_{\text{Outcome } y_t} = \beta \times \underbrace{\text{Price}_t}_{\text{Covariate } x_t} + \underbrace{\rho_S \times \text{Event}_t + \eta_{S,t}}_{\eta_t} $$

(b) Two-stages of IV Regression

<figure><img src="image_4.png" /><figcaption>(c) DAG of 2SLS at t</figcaption></figure>

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

Under exogeneity, researchers have studied scenarios where the observational noise is unbounded and has only bounded variance $\sigma^2$. But this setting asks for a different technical analysis than the bounded adversarial setting popular in online regression literature. For example, Ouhamma et al. [2021] analyse online forward and online ridge regressions in the unbounded stochastic setting.

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

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

**Instrumental Variable (IV) regression.** Historically, IVs are introduced to identify and quantify the causal effects of endogenous covariates [Newey and Powell, 2003]. IVs are widely used in economics [Wright, 1928, Mogstad et al., 2021], causal inference [Rubin, 1974, Hernan and Robins, 2020, Harris et al., 2022], bio-statistics and epidemiology [Burgess et al., 2017]. One popular framework is to choose IVs which heavily influence the covariates but are independent of the exogenous noise. Following that, one aims to learn the relations between IVs and covariates in one stage, then uses the predicted values of covariates to learn the relation between covariates and the outcome variables in the next stage. This approach to conducting two stages of linear regression using IVs is called Two Stage Least Squares Regression (2SLS) [Angrist and Imbens, 1995, Angrist et al., 1996]. 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 to nonlinear structures, non-compliant instruments, and corrupted observations using deep learning [Liu et al., 2020, Xu et al., 2020, 2021], graphical models [Stirn and Jebara, 2018], and kernel regression [Zhu et al., 2022].

**Example 1.1 (Continued).** To rectify the error due to endogeneity, the analyst further studies the main factors behind pricing and observes that $Price_t$ depends on material cost of the required components $MaterialCost_t$. She also observes that $MaterialCost_t$ is independent of the omitted variable $Event_t$. To rectify the error due to endogeneity, the analyst observes that $MaterialCost_t$ is
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, Carneiro et al. (2011); Mogstad et al. (2021) 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 14¹. 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)* (Angrist and Imbens, 1995; Angrist et al., 1996). 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 (Liu et al., 2020; Xu et al., 2020, 2021), graphical models (Stirn and Jebara, 2018), and kernel regression (Zhu et al., 2022), 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 (Singh et al., 2020; Liu et al., 2020; Nareklishvili et al., 2022). In applications, this analysis is vacuous as one has access to only finite samples. Additionally, in practice, it is natural to acquire the data sequentially as treatments are chosen on-the-go, and then to learn the structural equation from the sequential data (Venkatraman et al., 2016). This setting motivates us to analyse the online extension of 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 $\beta$? How estimating the true parameters $\beta$ 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 endogeneity, we show that the relations are more nuanced under endogeneity and unbounded noise. We focus specifically on the identification regret, i.e. the sum of differences between the estimated parameters $\{\beta_t\}_{t=1}^T$, and the true parameter $\beta$, and oracle regret, i.e. the sum of differences between the losses incurred by the estimated parameters $\{\beta_t\}_{t=1}^T$, and the true parameter $\beta$. In Section 4, we theoretically show that O2SLS achieve $O(d^2 \log^2 T)$ identification regret and $O(d^2 \log^2 T + \gamma \sqrt{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(\gamma \sqrt{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.

<footnote n="1">1. 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.</footnote>
independent of the omitted variable Event$_t$. Thus, she chooses MaterialCost$_t$ to be an *Instrumen-
tal Variable (IV)*. She runs an online linear regression to learn the relation between Price$_t$ and
MaterialCost$_t$. This is equivalent to learning θ in the first-stage Price$_t$ = θ × MaterialCost$_t$ + ϵ$_t$,
where exogeneity is obeyed. She learns that an increase in material cost increases the price, say
θ = 1. Now, she uses the prices predicted at time t, by the first-stage regressor, as the second-stage
covariates, and uses them further the relation between price and sales in the second-stage. This
leads her to an estimate of the second-stage parameter β, say -1.01, which is accurate even under
endogeneity.

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

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

1. What is the upper bound on the loss in performance for deploying parameters estimated by O2SLS instead of the true parameters $\beta$? How does estimating the true parameters $\beta$ 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 exogeneity, we show that the relations are more nuanced under endogeneity and unbounded noise (see Appendix B.9). We focus specifically on the identification regret, i.e. the sum of differences between the estimated parameters {$\beta_t$}$_{t=1}^T$, and the true parameter $\beta$, and oracle regret, i.e. the sum of differences between the losses incurred by the estimated parameters {$\beta_t$}$_{t=1}^T$, and the true parameter $\beta$. In Section 3, we theoretically show that O2SLS achieve $O(d_x d_z \log^2 T)$ identification regret and $O(d_x d_z \log^2 T + \gamma \sqrt{d_z T \log T})$ oracle regret after receiving $T$ samples from the observational data. Identification regret of O2SLS is $d_z$ multiplicative factor higher than regret of online linear regression under exogeneity, and oracle regret is $O(\gamma \sqrt{d_z T \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. Due to two-stages and endogeneity, we can't rely on standard techniques and need to prove concentration bounds for dependent r.v. (Appendix B.6) leading to a novel analysis for Thm. 3.5. We also experimentally demonstrate efficiency of O2SLS on synthetic and real-data with endogeneity (Section 5, Appendix D).

2. OFUL-IV for linear bandits with endogeneity: In Section 4, we study the linear bandit problem with endogeneity. We design an extension of OFUL algorithm used for linear bandit with exogeneity, namely OFUL-IV, to tackle this problem. OFUL-IV uses O2SLS to estimate the parameters, and corresponding confidence bounds on $\beta$ to balance exploration-exploitation.
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 $\beta$ to balance exploration-exploitation. We show that OFUL-IV achieve $O(d\sqrt{T} \log T)$ regret after $T$ interactions. We experimentally show that OFUL-IV incur lower regret than OFUL under endogeneity (end of Section 5).

## 2. 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 (Foster, 1991; Littlestone et al., 1991). Vovk (1997, 2001) show that forward and ridge regressions achieve $O(dY_{max}^2 \log T)$ for outcomes with bound $Y_{max}$. Bartlett et al. (2015) generalise the analysis further by considering the features known in hindsight. Gaillard et al. (2019) improve the analysis further to propose an optimal algorithm and a lower bound. These works perform an adversarial analysis with bounded outcomes, covariates, and observational noise, while we focus on the stochastic setting. Ouhamma et al. (2021) study the stochastic setting with bounded input features and unbounded noise. But they need to assume independence of noise and input features. In this paper, we analyse online 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; Foster and Rakhlin, 2020). To be specific, in bandit feedback, the algorithm observes only the outcomes for the input features that it has chosen to draw during an interaction. Popular algorithm design techniques, such as optimisin-the-face-of-uncertainty and Thompson sampling, are extended to propose OFUL (Abbasi-Yadkori et al., 2012) and LinTS (Abeille and Lazaric, 2017), respectively. OFUL and LinTS algorithms demonstrate $O(d\sqrt{T} \log T)$ and $O(d^{1.5}\sqrt{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\sqrt{T} \log T)$ regret.

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

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

We are given an observational dataset $\{x_i, y_i\}_{i=1}^n$ consisting of $n$ pairs of input features and outcomes, such that $y_i \in \mathbb{R}$ and $x_i \in \mathbb{R}^d$. These inputs and outcomes are stochastically generated using a linear model

$$y_i = \beta^\top x_i + \eta_i, \quad (\text{Second stage})$$

where $\beta \in \mathbb{R}^d$ is the unknown true parameter vector of the linear model, and $\eta_i \sim N(0, \sigma_i^2)$ is the unobserved error term representing all causes of $y_i$ other than $x_i$. It is assumed that the error terms $\eta_i$ are independently and identically distributed, and have bounded variance $\sigma^2$. The parameter

<footnote n="2">2. Matrices and vectors are represented with bold capital and bold small letters, e.g. $\mathbf{A}$ and $\mathbf{a}$, respectively.</footnote>
Lemma 3.3 derives a new confidence ellipsoid around O2SLS estimator $\beta_t$ with a new design matrix $\hat{H}_t$. Following existing derivations for ridge would ask algorithm to know tight upper bounds on the hidden paramenter unlike us. We show that OFUL-IV achieve $O(\sqrt{d_x d_z T \log T})$ regret after $T$ interactions. We further experimentally validate that OFUL-IV incurs lower regret under endogeneity than OFUL [Abbasi-Yadkori et al., 2011a] (Section 5, Appendix D).

**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 [Foster, 1991, Littlestone et al., 1991]. Vovk [1997, 2001] show that forward and ridge regressions achieve $O(d_x Y_{max}^2 \log T)$ for outcomes with bound $Y_{max}$. Bartlett et al. [2015] generalise the analysis further by considering the features known in hindsight. Gaillard et al. [2019] improve the analysis further to propose an optimal algorithm and a lower bound. These works perform an adversarial analysis with bounded outcomes, covariates, and observational noise, while we focus on the stochastic setting. Ouhamma et al. [2021] study the stochastic setting with bounded input features and unbounded noise. But they need to assume independence of noise and input features. In this paper, we analyse online O2SLS under endogeneity and unbounded (stochastic) noise. We do not assume to know the bound on the outcome and derive high probability bounds for any bounded sequence of features. Previously, Venkatraman et al. [2016] studied O2SLS for system identification but provided only asymptotic analysis.

**Related Work: Linear bandits without endogeneity.** Linear bandits generalise the setting of online linear regression under bandit feedback [Abbasi-Yadkori et al., 2011a, 2012, Foster and Rakhlin, 2020]. To be specific, in bandit feedback, the algorithm observes only the outcomes for the input features that it has chosen to draw during an interaction. Popular algorithm design techniques, such as optimism-in-the-face-of-uncertainty and Thompson sampling, are extended to propose OFUL [Abbasi-Yadkori et al., 2012] and LinTS [Abeille and Lazaric, 2017], respectively. OFUL and LinTS algorithms demonstrate $O(d\sqrt{T} \log T)$ and $O(d^{1.5}\sqrt{T} \log T)$ regret under exogeneity. 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\sqrt{T} \log T)$ regret.

**Related Work: Instrument-armed bandits.** Kallus [2018] is the first to study endogeneity and instrumental variables in a stochastic bandit setting. Stirn and Jebara [2018] propose a Thompson sampling-type algorithm for stochastic bandits, where endogeneity arises due to non-compliant actions. But both Kallus [2018] and Stirn and Jebara [2018] study only the finite-armed bandit setting where arms are independent of each other. In this paper, we study the stochastic linear bandits with endogeneity requiring different techniques of analysis and algorithm design. Krishnamurthy et al. [2018] studies a linear contextual bandit setup close to ours, but they assume arm-independent and bounded noise, and thus, yielding significantly different analysis.

**Notations:** Matrices and vectors are denoted by bold capital and bold small letters (e.g. $\mathbf{A}$ and $\mathbf{a}$). $\|\cdot\|_p$ is $l_p$ norm of a vector. $\sigma_{\min}(\cdot)$ is minimum singular value and $\|\cdot\|_2$ is operator norm of a matrix. For any vector $y \in \mathbb{R}^n$ and a positive definite matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$, let us define the norm $\|y\|_{\mathbf{A}} \triangleq \sqrt{y^T \mathbf{A} y} = \sqrt{\langle y, \mathbf{A} y \rangle}$.

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

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

$$y_i = \beta^\top x_i + \eta_i, \qquad (\text{Second stage})$$

where $\beta \in \mathbb{R}^{d_x}$ is the unknown true parameter vector of the linear model, and $\eta_i \sim N(0, \sigma_{\eta}^2)$ is the unobserved error representing all causes of $y_i$ other than $x_i$. It is assumed that the error terms $\eta_i$
<figure><img src="image_2.png" /><figcaption>Figure 1: The DAG for 2SLS. The unobserved noises are $\epsilon$ and $\eta$ (in grey), while $z$, $x$, $y$ are observed quantities.</figcaption></figure>

vector $\beta$ 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 $\beta$ by minimising the square loss over the dataset (Brier, 1950), i.e. $\hat{\beta} \triangleq \underset{\beta'}{\argmin} \sum_{i=1} (y_i - \beta' x_i)^2$.

The obtained solution is called the Ordinary Least Square (OLS) estimate of $\beta$ (Wasserman, 2004), and used as a corner stone of online regression (Gaillard et al., 2019) and linear bandit algorithms (Foster and Rakhlin, 2020). Specifically, if the input feature matrix $X_n \in \mathbb{R}^{n \times d}$ is defined as $[x_1, x_2, \dots, x_n]^\top$, the outcome vector is $y_n \triangleq [y_1, \dots, y_n]^\top$, and the noise vector is $\eta_n \triangleq [\eta_1, \dots, \eta_n]^\top$, the OLS estimator is expressed as

$$ \hat{\beta}_{\text{OLS}} \triangleq (X_n^\top X_n)^{-1} X_n^\top y_n = \beta + (X_n^\top X_n)^{-1} X_n^\top \eta_n $$

If $X_n$ and $\eta_n$ are independent, the second term has zero expected value conditioned on $X_n$. Hence, the OLS estimator is asymptotically unbiased, i.e. $\hat{\beta}_{\text{OLS}} \to \infty$ as $n \to \infty$.

In practice, the input features $x$ and the noise $\eta$ are often correlated (Greene, 2003, Chapter 8). As in Figure 1, this dependence, called endogeneity, is modelled with a confounding unobserved random variable $\epsilon$. To compute an unbiased estimate of $\beta$ under endogeneity, a popular technique is to introduce the Instrumental Variables (IVs) $z$ (Angrist et al., 1996; Newey and Powell, 2003). IVs are chosen such that they are highly correlated with endogenous components of $x$ (relevance condition) but are independent of the noise $\eta$ (exogeneity condition for $z$).

This leads to the Two-stage Least Squares (2SLS) approach to IV regression (Angrist and Imbens, 1995; Angrist et al., 1996). Here, we further assume that IVs, i.e. $Z_n \triangleq [z_1, \dots, z_n]^\top$, cause linear effects on the endogenous covariates. Specifically, for the just-identified IVs,

$$ X_n = Z_n \Theta + E_n, \qquad (\text{First stage}) $$

where $\Theta \in \mathbb{R}^{d \times d}$ is an unknown first-stage parameter matrix and $E_n \triangleq [\epsilon_1, \dots, \epsilon_n]^\top$ 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 $\epsilon \sim N(0, \sigma^2 I_d)$ (Wasserman, 2004, Ch. 13). Thus, the first-stage is amenable to OLS regression. This formulation leads us to the 2SLS estimator:

$$ \hat{\beta}_{2\text{SLS}} = (Z_n^\top X_n)^{-1} Z_n^\top y_n. \qquad (2\text{SLS}) $$

As long as $E[z_i \eta_i] = 0$ in the true model, we observe that

$$ \hat{\beta}_{2\text{SLS}} = (Z_n^\top X_n)^{-1} Z_n^\top X_n \beta + (Z_n^\top X_n)^{-1} Z_n^\top \eta_n \xrightarrow{p} \beta, $$

as $n \to \infty$. This works because IV solves for the unique parameter that satisfies $\frac{1}{n} Z_n^\top \eta \xrightarrow{p} 0$. Since $x$ and $\eta$ are correlated, 2SLS estimator is not unbiased in finite-time.
are independent and identically distributed with bounded variance $\sigma_{\eta}^2$. The parameter vector $\beta$ 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 $\beta$ by minimising the square loss over dataset [Brier, 1950], i.e. $\hat{\beta} \triangleq \operatorname{argmin}_{\beta'} \sum_{i=1}^{n} (y_i - \beta' x_i)^2$.

The obtained solution is called the Ordinary Least Square (OLS) estimate of $\beta$ [Wasserman, 2004], and is a corner stone of online regression [Gaillard et al., 2019] and linear bandit algorithms [Foster and Rakhlin, 2020]. Specifically, if we define the input feature matrix to be $\mathbf{X}_n \triangleq [x_1, x_2, \dots, x_n]^\top \in \mathbb{R}^{n \times d_x}$, the outcome vector to be $\mathbf{y}_n \triangleq [y_1, \dots, y_n]^\top$, and the noise vector is $\eta_n \triangleq [\eta_1, \dots, \eta_n]^\top$, OLS estimator is

$$ \hat{\beta}_{\text{OLS}} \triangleq (\mathbf{X}_n^\top \mathbf{X}_n)^{-1} \mathbf{X}_n^\top \mathbf{y}_n = \beta + (\mathbf{X}_n^\top \mathbf{X}_n)^{-1} \mathbf{X}_n^\top \eta_n $$

If $x_i$ and $\eta_i$ are independent, i.e. under exogeneity, the OLS estimator is unbiased: $E[\hat{\beta}_{\text{OLS}}] = \beta$. Furthermore, it is also asymptotically consistent since $\mathbf{X}_n^\top \eta_n \xrightarrow{p} 0$ implies $\hat{\beta}_{\text{OLS}} \xrightarrow{p} \beta$ [Greene, 2003].

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

$$ \mathbf{X}_n = \mathbf{Z}_n \mathbf{\Theta} + \mathbf{E}_n. \qquad (\text{First stage}) $$

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

$$ \begin{aligned} \hat{\beta}_{2\text{SLS}} &\triangleq (\hat{\mathbf{\Theta}}_n^\top \mathbf{Z}_n^\top \mathbf{Z}_n \hat{\mathbf{\Theta}}_n)^{-1} \hat{\mathbf{\Theta}}_n^\top \mathbf{Z}_n^\top \mathbf{y}_n \\ &= (\hat{\mathbf{X}}_n^\top \hat{\mathbf{X}}_n)^{-1} \hat{\mathbf{X}}_n^\top \mathbf{y}_n. \end{aligned} \qquad (2\text{SLS}) $$

Here, $\hat{\mathbf{X}}_n$ is the predicted covariate from first-stage. Given $E[z_i \eta_i] = 0$ in the true model, we observe that $\hat{\beta}_{2\text{SLS}} = (\hat{\mathbf{X}}_n^\top \hat{\mathbf{X}}_n)^{-1} \hat{\mathbf{X}}_n^\top \mathbf{X}_n \beta + (\hat{\mathbf{X}}_n^\top \hat{\mathbf{X}}_n)^{-1} \hat{\mathbf{X}}_n^\top \eta_n \xrightarrow{p} \beta$, as $n \to \infty$. Since $x$ and $\eta$ are correlated, 2SLS estimator is not unbiased in finite-time. When $d_x = d_z$, we call $z$ just-identified IVs. When $d_x < d_z$, we call $z$ over-identified IVs. In this paper, we analyse both of the conditions.

**Assumption 2.1.** The assumptions for conducting 2SLS are [Greene, 2003, Hernan and Robins, 2020]:

1. **Endogeneity of $x$.** The second stage input features $x$ and noise $\eta$ are not independent: $x \perp \eta$.

2. **Exogeneity of $z$.** IV random variables are independent of the noise in the second stage: $z \perp \eta$.

3. **Relevance Condition of IVs.** For every $t \in \mathbb{N}$, the variables $z$ and $x$ are correlated: $z \perp \tilde{x}$.

[Greene, 2003, Sec.8.2] and [Hernan and Robins, 2020, Ch. 16] state these three as the strictly necessary conditions for the existence of IVs in offline IV-regression. Thus, we assume only these necessary conditions to hold for our analysis of online 2SLS.
**Assumption 3.1.** The assumptions for conducting 2SLS with just-identified IVs are (Greene, 2003):

1. **Well behaved data.** For every $n \in \mathbb{N}$, the matrices $Z_n^\top Z_n$ and $Z_n^\top X_n$ are full rank, and thus invertible.

2. **Endogeneity of x.** The second stage input features $x$ and noise $\eta$ are not independent: $x \perp \eta$.

3. **Exogeneity of z.** The IV random variables are independent of the noise in the second stage: $z \perp \eta$.

4. **Relevance Condition.** The variables $z$ and $x$ are correlated: $z \perp x$. This implies that there exists $\mathbf{r} > 0$:

$$ \left\| n \left( Z_n^\top X_n \right)^{-1} \right\|_2 \le \frac{1}{\mathbf{r}}. \qquad (1) $$

## 4. 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), \dots, (x_T, z_T, y_T), \dots$ arrives in a stream. Following the 2SLS model (Figure 1), data is generated from

$$ \left\{ \begin{array}{l} x_t = \Theta^\top z_t + \epsilon_t \\ y_t = \beta^\top x_t + \eta_t, \end{array} \right. \qquad (2) $$

such that $x_t \perp \eta_t$ and $z_t \perp \eta_t$ for all $t \in \mathbb{N}$. At each step $t$, the online IV regression algorithm is served with a new input feature $x_t$ and an IV $z_t$, and it aims to predict an outcome $\hat{y}_t \triangleq \beta_t^\top x_t \in \mathbb{R}$. Here, $\beta_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}^T$ observed so far. Following the prediction, Nature reveals the true outcome $y_t$. Quality of the prediction is evaluated using a square loss $\ell_t(\beta_t) \triangleq (\hat{y}_t - y_t)^2$ (Foster, 1991). The online protocol is the following.

At each round $t = 1, 2, \dots, 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 $\beta_\bullet$ and make a prediction $\hat{y}_t = \beta_\bullet^\top x_t$

4. we observe the true $y_t$ following Equation (2)

5. we incur in a loss $(y_t - \hat{y}_t)^2 = (y_t - \beta_\bullet^\top 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$:

$$ \beta_{t-1} \triangleq \left( \sum_{s=1}^{t-1} z_s x_s^\top \right)^{-1} \sum_{s=1}^{t-1} z_s y_s \qquad (\text{O2SLS}) $$

We use the O2SLS estimator at step $t-1$ for the prediction $\hat{y}_t = \beta_{t-1}^\top 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 $\beta_t$, and use it to predict $\hat{y}_t$ (Vovk, 2001). Since we cannot use $y_t$ for this estimate, we have to modify
## 3 O2SLS: 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, measuring accuracy of estimating the true parameter and the predicted outcomes, respectively. We provide a theoretical analysis of O2SLS and upper bound the two types of regret (Section 3.2).

O2SLS. In the online setting of IV regression, the data $(x_1, z_1, y_1), \dots, (x_t, z_t, y_t), \dots$ arrives in a stream. Following 2SLS model (Fig. 1c), data is generated endogeneously

$$x_t = \Theta^\top z_t + \epsilon_t \qquad y_t = \beta_t^\top x_t + \eta_t, \qquad (1)$$

such that $x_t \perp \eta_t$ and $z_t \perp \eta_t$ for all $t \in \mathbb{N}$. At each step $t$, the online IV regression algorithm is served with a new input feature $x_t$ and an IV $z_t$. At time $t+1$, the algorithm aims to yield an estimate of the parameter $\beta_t$ and predict an outcome $\hat{y}_{t+1} \triangleq \beta_t^\top x_{t+1} \in \mathbb{R}$ using the data $\{(x_s, z_s, y_s)\}_{s=1}^t$ observed so far. Following the prediction, Nature reveals the true outcome $y_{t+1}$.

To address endogeneity in this problem, we propose an online form of the 2SLS estimator. Modifying Eq. (2SLS), we obtain the O2SLS estimator that is computed for the prediction at time $t+1$, using information up to time $t$:

$$\begin{aligned} \beta_t &\triangleq (\hat{\mathbf{X}}_t^\top \hat{\mathbf{X}}_t)^{-1} \hat{\mathbf{X}}_t^\top \mathbf{y} = \left(\sum_{s=1}^t \hat{x}_s \hat{x}_s^\top\right)^{-1} \sum_{s=1}^t \hat{x}_s y_s \\ &= (\mathbf{I} - \mathbf{G}_{\hat{x}_t, t}^{-1} \hat{x}_t \hat{x}_t^\top) \beta_{t-1} + \mathbf{G}_{\hat{x}_t, t}^{-1} \hat{x}_t y_t. \end{aligned} \qquad (\text{O2SLS})$$

Here, $\mathbf{G}_{\hat{x}_t, t} \triangleq \sum_{s=1}^t \hat{x}_s \hat{x}_s^\top = \mathbf{G}_{\hat{x}_t, t-1} + \hat{x}_t \hat{x}_t^\top$. We need the predicted value of covariate $\hat{x}_t \triangleq \hat{\Theta}_{t-1} z_t$ and output $y_t$ for the iterative update of $\beta_t$ given the estimates at previous time $\beta_t$ and $\mathbf{G}_{\hat{x}_t, t}$. To predict the covariate $\hat{x}_t$, we leverage an iterative update rule of $\hat{\Theta}_t$ from $\hat{\Theta}_{t-1}$ by using $z_t$, $x_t$ (Appendix B). In brief, for $\lambda > 0$,

$$\hat{\Theta}_t = \left(\sum_{s=1}^{t-1} z_s z_s^\top + \lambda \mathbf{I}_{dz}\right)^{-1} \sum_{s=1}^{t-1} z_s x_s^\top = (\mathbf{I} - \mathbf{G}_{z,t-1}^{-1} z_t z_t^\top) \hat{\Theta}_{t-1} + \mathbf{G}_{z,t-1}^{-1} z_t x_t^\top. \qquad (2)$$

Finally, we use the O2SLS estimator at step $t+1$ for the prediction $\hat{y}_{t+1} = \beta_t^\top x_{t+1}$, as in Algorithm 1.

### Algorithm 1 O2SLS

1: **Input:** Initialisation parameters $\beta_0, \hat{\Theta}_0, \lambda$

2: **for** $t = 1, \dots, T$ **do**

3: & Observe $z_t$ generated i.i.d. by Nature, and $x_t$ sampled from Eq. (1) given $z_t$

4: & Compute first-stage and second-stage estimates $\beta_{t-1}$ and $\hat{\Theta}_{t-1}$ as per Equation (2) and Equation (O2SLS)

5: & Predict $\hat{y}_t = \beta_{t-1}^\top x_t$

6: & Observe $y_t$ generated by Nature

7: **end for**

**Computational complexity.** For second-stage, we compute $\mathbf{G}_{\hat{x}_t, t}^{-1}$ from $\mathbf{G}_{\hat{x}_t, t-1}^{-1}$ in $O(d_x^2)$ time using the Sherman-Morrison formula. We store $\mathbf{G}_{\hat{x}_t, t}^{-1}$ after each step, which requires $O(d_x^2)$ memory. However, the first-stage update has $O(d_z^2 + d_z d_x)$ time complexity and requires $O(d_z^2)$ memory. Thus, O2SLS exhibits quadratic space and time complexity.
**Algorithm 1 O2SLS**

1: **for** t = 1, 2, ..., T **do**

2: Observe $z_t$, $x_t$

3: Compute $\beta_{t-1}$ according to Equation (O2SLS)

4: Predict $\hat{y}_t = \beta_{t-1}^\top x_t$

5: Observe $y_t$ and compute loss $\ell_t(\beta_{t-1})$

6: **end for**

O2SLS to incorporate this additional knowledge. We skip this modification and use $\beta_{t-1}$ to predict. Previously, Venkatraman et al. (2016) studied O2SLS for system identification but provided only an asymptotic analysis.

**4.1 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 $\beta$. Identifying $\beta$ leads to understanding of the underlying economic or biological causal relations and their dynamics. In ML, Venkatraman et al. (2016) applied O2SLS for online linear system identification. Thus, given a sequence of estimators $\{\beta_t\}_{t=1}^T$ and a sequence of covariates $\{x_t\}_{t=1}^T$, the cost of identifying the true parameter $\beta$ can be quantified by

$$ \tilde{R}_T(\beta) \triangleq \sum_{t=1}^{T} (x_t^\top \beta_{t-1} - x_t^\top \beta)^2. \qquad (3) $$

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

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

$$ \bar{R}_T(\beta) \triangleq \sum_{t=1}^{T} (y_t - x_t^\top \beta_{t-1})^2 - \sum_{t=1}^{T} (y_t - x_t^\top \beta)^2. \qquad (4) $$

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

As 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 3.1 (Proper online learning). As in improper online learning algorithms, we could use $\boldsymbol{x}_t$ and $\boldsymbol{z}_t$ that we observe before committing to the estimate $\boldsymbol{\beta}_t$, and use it to predict $\hat{y}_t$ [Vovk, 2001]. Since we cannot use $y_t$ for this estimate, we have to modify 2SLS to incorporate this additional knowledge. We avoid this modification, and follow a proper online learning approach to use $\boldsymbol{\beta}_{t-1}$ to predict.

## 3.1 Regrets for estimation & prediction: Identification & oracle regrets

To analyse the online regression algorithms, it is essential to define proper performance metrics, specifically *regrets*. 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 the accurate identification of the underlying structural model $\boldsymbol{\beta}$. Identifying $\boldsymbol{\beta}$ leads to understanding of the underlying economic or biological causal relations and their dynamics. In ML, Venkatraman et al. [2016] applied O2SLS for online linear system identification. Thus, given a sequence of estimators $\{\boldsymbol{\beta}_t\}_{t=1}^T$ and a sequence of covariates $\{\boldsymbol{x}_t\}_{t=1}^T$, the cost of identifying the true parameter $\boldsymbol{\beta}$ can be quantified by

$$ \tilde{R}_T(\boldsymbol{\beta}) \triangleq \sum_{t=1}^T (\boldsymbol{x}_t^\top \boldsymbol{\beta}_{t-1} - \boldsymbol{x}_t^\top \boldsymbol{\beta})^2. \quad (3) $$

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

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

$$ \bar{R}_T(\boldsymbol{\beta}) \triangleq \sum_{t=1}^T (y_t - \boldsymbol{x}_t^\top \boldsymbol{\beta}_{t-1})^2 - (y_t - \boldsymbol{x}_t^\top \boldsymbol{\beta})^2. \quad (4) $$

We refer to $\bar{R}_T(\boldsymbol{\beta})$ as the *oracle regret*. This regret is studied for stochastic analysis of online regression [Ouhamma et al., 2021] and for analysing bandits [Foster and Rakhlin, 2020].

As O2SLS is interesting for learning causal structures [Hartford et al., 2016, Bennett et al., 2019], we focus on the identification regret. On the other hand, to compare with the existing results in online linear regression, we also analyse the oracle regret of O2SLS. Though they are of similar order (w.r.t. $T$) in the exogenous setting, we show that they differ significantly for O2SLS under endogeneity (Section 3.2).

Remark 3.2 (Hardness of exogeneity vs. endogeneity for prediction). In online learning theory focused on Empirical Risk Minimisation (ERM), another type of regret is considered where the oracle has access to the best offline estimator $\boldsymbol{\beta}_T \triangleq \underset{\boldsymbol{\beta}}{\operatorname{argmin}} \boldsymbol{\beta} \sum_{t=1}^T (y_t - \boldsymbol{x}_t^\top \boldsymbol{\beta})^2$ given the observations over $T$ steps Cesa-Bianchi and Lugosi [2006]. Thus, the new formulation of regret becomes $R_T = \sum_{t=1}^T (y_t - \boldsymbol{x}_t^\top \boldsymbol{\beta}_{t-1})^2 - \min \boldsymbol{\beta} \sum_{t=1}^T (y_t - \boldsymbol{x}_t^\top \boldsymbol{\beta})^2$. We refer to it as the *population regret*. Under exogeneity, Ouhamma et al. [2021] show that oracle regret and population regret differs by $o(\log^2 T)$. We show that under endogeneity, their expected values differ by $\Omega(T)$. Thus, we avoid studying population regret in this paper, and detail it in Appendix B.9.
**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 $\beta_T \triangleq \underset{\beta}{\operatorname{argmin}} \sum_{t=1}^{T} (y_t - \mathbf{x}_t^\top \beta)^2$ given the observations over T steps Cesa-Bianchi and Lugosi (2006). Thus, the new formulation of regret becomes

$$R_T = \sum_{t=1}^{T} (y_t - \mathbf{x}_t^\top \beta_{t-1})^2 - \min_{\beta} \sum_{t=1}^{T} (y_t - \mathbf{x}_t^\top \beta)^2. \quad (5)$$

We refer to it as the population regret. Under exogeneity, Ouhamma et al. (2021) shows that oracle regret and population regret differs by $o(\log^2 T)$. We show that under endogeneity their expected values differ by $\Omega(T)$. Thus, we avoid studying this notion of regret in this paper. More details are in Appendix E.

## 4.2 Theoretical Analysis

**Confidence Interval of $\beta_t$.** The central result in our analysis is concentration of the O2SLS estimates $\beta_t$ around $\beta$.

**Lemma 4.1 (Confidence Ellipsoid for the Second-stage Parameters).** Let us define the design matrix to be $G_{z,t} = Z_t^\top Z_t + \lambda I_d$ for some $\lambda > 0$. Then, for $\sigma_\eta$-sub-Gaussian first stage noise $\eta_t$, the true parameter $\beta$ belongs to the set

$$\mathcal{E}_t = \{ \beta \in \mathbb{R}^d : \|\beta_t - \beta\|_{\hat{\mathbf{H}}_t} \le \sqrt{\mathfrak{b}_t(\delta)} \}, \quad (6)$$

with probability at least $1 - \delta \in (0, 1)$, for all $t \ge 0$. Here, $\mathfrak{b}_t(\delta) \triangleq \frac{d\sigma_\eta^2}{4}\log\left(\frac{1+tL^2/\lambda}{\delta}\right)$, $\hat{\mathbf{H}}_t \triangleq \hat{\mathbf{\Theta}}_t^\top G_{z,t} \hat{\mathbf{\Theta}}_t$, and $\hat{\mathbf{\Theta}}_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 exogeneity to the O2SLS estimator under endogeneity. It shows that the size of the confidence intervals induced by O2SLS estimate at time $T$ is $O(\sqrt{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 \le L_z^2$, if $\eta_t$ is the $\sigma_\eta$-sub-Gaussian second stage noise and $\epsilon_t$ is the component-wise $\sigma_\epsilon$-sub-Gaussian first stage noise, the regret of O2SLS at step $T > 1$ satisfies

$$\tilde{R}_T \le \underbrace{\mathfrak{b}_{T-1}(\delta)}_{\text{Estimation}} \underbrace{((C_1^2 + dC_2^2)f(T) + C_4)}_{\text{Second Stage Feature norm}}$$

with probability at least $1 - \delta \in (0, 1)$. Here, $\mathfrak{b}_{T-1}(\delta)$ is the confidence bound of O2SLS estimate around $\beta$ (Lemma 4.1) and $f(T) \triangleq \left(\frac{C_3}{\lambda} + \frac{\log(T)+1}{\lambda_{\min}(\Sigma)/2}\right)$. $C_1, C_2, C_3, C_4$ are d and T-independent positive constants (Appendix G), and $\lambda_{\min}(\Sigma)$ is the minimum eigenvalue of the true covariance matrix of IVs, i.e. $\Sigma \triangleq \mathbb{E}[zz^\top]$.

**Proof Sketch.** For brevity, we define $\Delta\beta_{t-1} \triangleq \beta_{t-1} - \beta$. By applying Cauchy-Schwarz inequality in Eq. (3), we decouple the effects of parameter estimates and feature norms

$$\sum_{t=1}^{T} (\Delta\beta_{t-1}^{\top} \mathbf{x}_t)^2 \le \sum_{t=1}^{T} \|\Delta\beta_{t-1}\|_{\hat{\mathbf{H}}_{t-1}}^2 \|\mathbf{x}_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2$$
## 3.2 Theoretical analysis

**Confidence set.** The central result in our analysis is concentration of O2SLS estimates $\beta_t$ around $\beta$.

**Lemma 3.3 (Confidence ellipsoid for the second-stage parameters).** Let us define the design matrix of IVs to be $G_{z,t} \triangleq Z_t^\top Z_t + G_{z,0} = \sum_{s=1}^t z_s z_s^\top + G_{z,0}$ with $G_{z,0} = \lambda I_{d_z}$ for some $\lambda > 0$. Then, for some $\sigma_\eta$-sub-Gaussian second stage noise $\eta_t$ and for all $t > 0$, the true parameter $\beta$ belongs to the confidence set

$$ \mathcal{E}_t \triangleq \{ \beta \in \mathbb{R}^{d_x} : \|\beta_t - \beta\|_{\hat{\mathbf{H}}_t} \le \sqrt{\mathfrak{b}_t(\delta)} \}, \quad (5) $$

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

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

**Identification regret bound.** Now, we state the identification regret upper bound of O2SLS.

**Theorem 3.4 (Identification regret of O2SLS).** If Assumption 2.1 holds true, for bounded IVs $\|z\|_2^2 \le L_z^2$ and bounded first-stage parameters $\|\mathbf{\Theta}\|_2 \le L_{\mathbf{\Theta}}^2$, the $\sigma_\eta$-sub-Gaussian second stage noise $\eta_t$ and the component-wise $\sigma_\epsilon$-sub-Gaussian first stage noise $\epsilon_t$, the regret of O2SLS satisfies with probability at least $1 - \delta$

$$ \tilde{R}_T \le \sum_{t=1}^T \underbrace{\|\beta_t - \beta\|_{\hat{\mathbf{H}}_t}^2}_{\text{Estimation}} \times \underbrace{\|x_t\|_{\hat{\mathbf{H}}_t^{-1}}^2}_{\text{Second-stage feature norm}} \le \underbrace{\mathfrak{b}_{T-1}(\delta)}_{\mathcal{O}(d_z \log T)} \times \underbrace{\sum_{t=1}^T \|x_t\|_{\hat{\mathbf{H}}_t^{-1}}^2}_{\mathcal{O}(d_x \log T)} = \mathcal{O}(d_x d_z \log^2(T)). $$

Theorem 3.4 entails a regret $\tilde{R}_T = \mathcal{O}(d_x d_z \log^2(T))$. This regret bound is $d_z \log T$ more than the regret of online ridge regression, i.e. $\mathcal{O}(d_x \log T)$ [Gaillard et al., 2019]. This is because we perform $d_x$ linear regressions in the first-stage and use the predictions of the first-stage for the second-stage regression. These two regression steps in cascade induce the proposed regret bound.

**Oracle regret bound.** Now, we bound the oracle regret, i.e. the goodness of predictions yielded by O2SLS. Detailed proof is deferred to Appendix B.

**Theorem 3.5 (Oracle regret of O2SLS).** Under the same hypothesis of Theorem 3.4, Oracle Regret of O2SLS at step $T > 1$, i.e. $\tilde{R}_T$ is upper bounded by (ignoring log log terms)

$$ \underbrace{\tilde{R}_T}_{\substack{\text{Identif.} \\ \text{Regret}}} + \underbrace{\sqrt{\mathfrak{b}_{T-1}(\delta)}}_{\substack{\text{Estimation} \\ \mathcal{O}(\sqrt{d_z \log T})}} \left( \underbrace{C_1 \sqrt{f(T)}}_{\substack{\text{First-stage} \\ \text{feature norm}}} + \underbrace{C_2 \sqrt{2d_x f(T)} + \sqrt{d_x} C_3}_{\substack{\text{Correlated noise} \\ \text{Concentration term}}} + \underbrace{\gamma C_4 \sqrt{T}}_{\substack{\text{Correlated noise} \\ \text{Bias term}}} \right) \underbrace{\mathcal{O}(d_x d_z \log^2 T)}_{\mathcal{O}(\gamma \sqrt{T})} $$

with probability at least $1 - \delta \in (0, 1)$. Here, $\gamma \triangleq \|\gamma\|_2 = \|\mathbb{E}[\eta_s \epsilon_s]\|_2$. $C_1, C_2, C_3$, and $C_4$ are $d_z$, $d_x$ and $T$-independent positive constants. $f(T) = \mathcal{O}(\log T)$ as defined in Corollary B.9.

**Discussion.** 1. Hardness of endogeneity vs. exogeneity. Under exogeneity and unbounded stochastic noise, the oracle regret of online linear regression is $\mathcal{O}(d^2 \log^2 T)$ [Ouhamma et al., 2021]. If we take the just-identified IVs, i.e. $d_x = d_z = d$, due to endogeneity, O2SLS incurs an
Now, we bound this term by (a) using the confidence bound to control the concentration of $\beta_t$ around $\beta$, and (b) by bounding the sum of feature norms.

Step a: Confidence Intervals of $\beta_t$. We directly use Lemma 4.1 to bound $\|\Delta\beta_{t-1}\|_{\hat{\mathbf{H}}_{t-1}}^2$ by $\mathfrak{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 $\sum_{t=1}^T \|\mathbf{x}_t\|_{\hat{\mathbf{H}}_{t-1}}^2 \le (C_1^2 + dC_2^2) f(T) + C_4$. The idea is to substitute $\mathbf{x}_t$ with (First stage) equation. This leads to two terms $\sum_{t=1}^T \|\mathbf{\Theta}^\top \mathbf{z}_t\|_{\hat{\mathbf{H}}_{t-1}}^2$ and $\sum_{t=1}^T \|\epsilon_t\|_{\hat{\mathbf{H}}_{t-1}}^2$. Then, we bound the first term by $C_1^2 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. $\|\mathbf{G}_{\mathbf{z},t-1}\|_2 \triangleq \|(\sum_{s=1}^{t-1} \mathbf{z}_s^T \mathbf{z}_s)^{-1}\|_2$. The concentration of the minimum eigenvalue leads to the term $f(T) \triangleq \left(\frac{C_3}{\lambda} + \frac{\log(T)+1}{\lambda_{\min}(\Sigma)/2}\right)$.

Then, we bound $\sum_{t=1}^T \|\epsilon_t\|_{\hat{\mathbf{H}}_{t-1}}^2$ 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 - \delta$.

Final step. Since $\mathfrak{b}_{t-1}$ is non-decreasing in $t$, we conclude that $\sum_{t=1}^T (\Delta\beta_{t-1}^\top \mathbf{x}_t)^2$ is upper bounded by $\mathfrak{b}_{T-1}(\delta)((C_1^2 + 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 $\tilde{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)$ (Gaillard et al., 2019). 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

$$ \bar{R}_T \le \underbrace{\tilde{R}_T}_{\substack{\text{Identif.} \\ \text{Regret} \\ \mathcal{O}(d^2 \log^2 T)}} + \underbrace{\sqrt{\mathfrak{b}_{T-1}(\delta)}}_{\substack{\text{Estimation} \\ \mathcal{O}(\sqrt{d} \log T)}} \left( \underbrace{\sigma_\eta C_1 \sqrt{f(T) \log\left(\frac{\log T}{\delta}\right)}}_{\substack{\text{First Stage Feature Norm} \\ \mathcal{O}(\sqrt{\log T})}} + \underbrace{C_5 \sqrt{2df(T)} + \sqrt{d}C_6}_{\substack{\text{Correlated noise} \\ \text{Concentration Term} \\ \mathcal{O}(\sqrt{d} \log T)}} + \underbrace{\gamma L \hat{\Theta}^{-1} \left( \frac{C_3}{\sqrt{\lambda}} + \frac{2\sqrt{2T}}{\sqrt{\lambda_{\min}(\Sigma)}} \right)}_{\substack{\text{Correlated noise} \\ \text{Bias Term} \\ \mathcal{O}(\gamma\sqrt{T})}} \right) $$

with probability at least $1 - \delta \in (0,1)$. We define $\gamma \triangleq \|\gamma\|_2 = \|\mathbb{E}[\eta_s \epsilon_s]\|_2$. $C_1, C_2, C_3'$, and $C_4$ are the $d$ and $T$-independent positive constants (as in Thm. 4.1 and App. G). Constants $C_5 \triangleq 8e^2 (\sigma_\eta^2 + \sigma_\epsilon^2) L_{\hat{\Theta}^{-1}} \sqrt{\log(2/\delta)}$, $C_6 \triangleq C_5 \sqrt{\max\left\{\frac{1}{\lambda}, \frac{2}{\lambda_{\min}(\Sigma)}\right\}} \log(2/\delta)$, and $f(T) \triangleq \left(\frac{C_3'}{\lambda} + \frac{\log(T)+1}{\lambda_{\min}(\Sigma)/2}\right)$.

**Proof Sketch.** Using Equation (4) and Equation (2), we decompose the regret at step $T$ as

$$ \bar{R}_T = \underbrace{\sum_{t=1}^T (\Delta\beta_{t-1}^\top \mathbf{x}_t)^2}_{(\bullet 1 \bullet)} + 2 \underbrace{\sum_{t=1}^T \eta_t \Delta\beta_{t-1}^\top \Theta^\top \mathbf{z}_t}_{(\bullet 2 \bullet)} + 2 \underbrace{\sum_{t=1}^T \eta_t \Delta\beta_{t-1}^\top \epsilon_t}_{(\bullet 3 \bullet)} $$
additive factor of $O(\gamma\sqrt{d_zT\log T})$ in the oracle regret. This term appears due to the correlation between the second and the first-stage noises, and it is proportional to the degree of correlation between the noises in these two stages. Thus, the bias due to the correlation of noises acts as the dominant term. In 2SLS literature, this phenomenon is called the self-fulfilling bias [Li et al., 2021]. But we did not find any explicit bound on it in a stochastic and non-asymptotic analysis.

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

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

# 4 Linear bandits with endogeneity: OFUL-IV

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

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

At each round $t = 1, 2, \dots, T$, the agent

1. Observes a sample $\mathbf{x}_{t,a} \in \mathcal{X}_t$ of contexts for all $a \in \mathcal{A}_t$

2. Chooses an arm $A_t \in \mathcal{A}_t$

3. Observes the sample $\mathbf{z}_{t,A_t} \in \mathcal{Z}_t$

4. Obtains a reward $y_t$

5. Updates the parameter estimates $\hat{\mathbf{\Theta}}_t$ and $\beta_t$

Here, $\mathcal{X}_t \subset \mathbb{R}^{d_x}$ and $\mathcal{Z}_t \subset \mathbb{R}^{d_z}$ are the sets of covariates and IVs corresponding to $\mathcal{A}_t$, i.e. the set of feasible actions at time $t$. Similar to regression under endogeneity, $\epsilon_t \perp z_t$ and $\epsilon_t \perp \eta_t$ (Eq. (1)). True parameters $\beta \in \mathbb{R}^{d_x}$ and $\mathbf{\Theta} \in \mathbb{R}^{d_z \times d_x}$ are unknown to the agents. This is an extension of stochastic linear bandit [Lattimore and Szepesvári, 2020, Ch. 19] to the endogenous setting.

**Remark 4.1** (Alternative protocol of LBE). We can alternatively represent the protocol, where at every step $t$, the agent observes covariates $\mathbf{x}_{t,a}$ and IVs $\mathbf{z}_{t,a}$ for all the arms $a \in \mathcal{A}_t$. Then, the agent can use all these information to choose an arm $A_t$ and observes the corresponding outcome $y_t$. But we do not require $\mathbf{z}_{t,a}$ except $\mathbf{z}_{t,A_t}$ to update the parameters and select arms. Thus, the alternative is reducible to the protocol above, while asking for less information.
The proof proceeds by bounding each of these three terms.

**Term 1: Second Stage Regression Error.** We observe that Term (•1•) is same as $\tilde{R}_T$. By Theorem 4.1, we know $\tilde{R}_T = \mathcal{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 \triangleq (\beta_{t-1} - \beta)^\top \Theta^\top z_s$ is a martingale with respect to the filtration

$$ \mathcal{F}_{t-1} = \sigma(z_1, \epsilon_1, \eta_1, \dots, z_{t-1}, \epsilon_{t-1}, \eta_{t-1}, z_t). $$

We also note that $w_t$ is $\mathcal{F}_{t-1}$-measurable since $\beta_{t-1}$ and $z_t$ are too. By concentration property of scalar-valued martingale concentration (Theorem I.2), we get that with probability $1 - \delta$

$$ \begin{aligned} (\bullet 2 \bullet) &\le \left| \sum_{t=1}^T \eta_t w_t \right| \\ &\le \sqrt{2 \left( 1 + \sigma_\eta^2 \sum_{t=1}^T w_t^2 \right) \log \left( \frac{\sqrt{1 + \sigma_\eta^2 \sum_{t=1}^T w_t^2}}{\delta} \right)}. \end{aligned} $$

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 $\sum_{t=1}^T w_t^2 \le b_{T-1}(\delta)C_1^2 f(T)$. Hence, we conclude that Term (•2•) is $\mathcal{O}(\sqrt{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 (Li et al., 2021). We bound this term by splitting it into two.

$$ \sum_{t=1}^{T} \eta_t \Delta \beta_{t-1}^{\top} \epsilon_t = \underbrace{\sum_{t=1}^{T} \Delta \beta_{t-1}^{T} (\epsilon_t n_t - \gamma)}_{\text{Martingale Concentration Term}} + \underbrace{\sum_{t=1}^{T} \Delta \beta_{t-1}^{\top} \gamma}_{\text{Bias Term}} $$

Here, $\gamma \triangleq \mathbb{E}[\eta_s \epsilon_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 $\epsilon_t \eta_t$ in the martingale difference, since the individual terms are products of two dependent random variables $\epsilon_t$ and $\eta_t$. By applying Bernstein's inequality on the martingale difference and $\|\Delta\beta_{t-1}\|_{\hat{\mathbf{H}}_{t-1}} \le \sqrt{b_{T-1}(\delta)}$ with probability $1 - \delta$, we obtain

$$ \underbrace{\sqrt{b_{T-1}(\delta)}}_{\text{Estimation}} \underbrace{C_5 \sqrt{2d f(T)} + C_6}_{\substack{\text{Correlated noise} \\ \text{Concentration Term}}} $$

The Bias Term is the one where the correlation $\gamma$ 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 design matrix $\sum_{t=1}^T \sqrt{\|G_{z,t-1}^{-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 $\Omega(t)$. Thus, we get that $\sqrt{\lambda_{\max}(G_{z,t}^{-1})}$ is $\mathcal{O}(\frac{1}{\sqrt{t}})$. This leads to the following bound on the Bias Term

$$ \underbrace{\sqrt{b_{T-1}(\delta)}}_{\text{Estimation}} \underbrace{\gamma L \hat{\Theta}^{-1} \left( \frac{C_3}{\sqrt{\lambda}} + 2 \frac{\sqrt{2T}}{\sqrt{\lambda_{\min}(\Sigma)}} \right)}_{\substack{\text{Correlated noise} \\ \text{Bias Term}}} $$
**OFUL-IV: Algorithm design.** If the agent had full information in hindsight, she could infer the best arm (a.k.a. action or intervention) in $\mathcal{A}_t$ as $a_t^* = \underset{a \in \mathcal{A}_t}{\operatorname{argmax}} \mathbb{E}[\mathbf{x}_{t,a}^\top \boldsymbol{\beta}]$. Choosing $a_t^*$ is equivalent to choosing $\mathbf{z}_{t,a_t^*}$ and $\mathbf{x}_{t,a_t^*}$. But the agent does not know them and aims to select $\{a_t\}_{t=1}^T$ to minimise regret: $R_T \triangleq \mathbb{E}[\sum_{t=1}^T \boldsymbol{\beta}^\top(\mathbf{x}_{t,a_t^*} - \mathbf{x}_{t,a_t})]$. 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 $\mathcal{B}_{t-1} \subset \mathbb{R}^{d_x}$ around the estimated parameter $\boldsymbol{\beta}_{t-1}$, which is computed only using the observed data. In order to tackle endogeneity, we choose to use the O2SLS estimate $\boldsymbol{\beta}_{t-1}$ computed using data observed till $t-1$ (Equation (O2SLS)). Then, we build an ellipsoid $\mathcal{B}_{t-1}$ around it, such that $\mathcal{B}_{t-1} \triangleq \{\boldsymbol{\beta} \in \mathbb{R}^{d_x} : \|\boldsymbol{\beta}_{t-1} - \boldsymbol{\beta}\|_{\hat{\mathbf{H}}_{t-1}} \le \sqrt{\mathbf{b}_{t-1}^\top(\boldsymbol{\delta})}\}$, where $\mathbf{b}_{t-1}(\boldsymbol{\delta}) \triangleq 2\sigma_\eta^2 \log(\det(\mathbf{G}_{\mathbf{z},t-1})^{1/2}\lambda^{-d_x/2}/\delta)$ and $\hat{\mathbf{H}}_{t-1} = \hat{\mathbf{\Theta}}_{t-1}^\top \mathbf{G}_{\mathbf{z},t-1} \hat{\mathbf{\Theta}}_{t-1}$. Then, the algorithm chooses an optimistic estimate $\tilde{\boldsymbol{\beta}}_{t-1}$ from that confidence set: $\tilde{\boldsymbol{\beta}}_{t-1} \triangleq \underset{\boldsymbol{\beta}' \in \mathcal{B}_{t-1}}{\operatorname{argmax}} \max_{\mathbf{x} \in \mathcal{X}_t} \mathbf{x}^\top \tilde{\boldsymbol{\beta}}_{t-1}$. Then, she chooses the action $A_t$ corresponding to $\mathbf{x}_{t,A_t} = \underset{\mathbf{x} \in \mathcal{X}_t}{\operatorname{argmax}} \mathbf{x}^\top \tilde{\boldsymbol{\beta}}_{t-1}$, which maximises the reward as per the estimate $\tilde{\boldsymbol{\beta}}_{t-1}$. In brief, the algorithm chooses the pair $(\mathbf{x}_{t,A_t}, \tilde{\boldsymbol{\beta}}_{t-1}) = \underset{(\mathbf{x},\boldsymbol{\beta}') \in \mathcal{X}_t \times \mathcal{B}_{t-1}}{\operatorname{argmax}} \mathbf{x}^\top \boldsymbol{\beta}'$. Given confidence interval, we optimistically choose $A_t$ by solving

$$ \underset{a \in \mathcal{A}_t}{\operatorname{argmax}} \left\{ \langle \mathbf{x}_{t,a}, \boldsymbol{\beta}_{t-1} \rangle + \sqrt{\mathbf{b}_{t-1}^\top(\boldsymbol{\delta})} \|\mathbf{x}_{t,a}\|_{\hat{\mathbf{H}}_{t-1}^{-1}} \right\} \quad (6) $$

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

**Algorithm 2 OFUL-IV**

1: **Input:** Initialisation parameters $\boldsymbol{\beta}_0, \hat{\mathbf{\Theta}}_0, \mathbf{b}'_0, \lambda$

2: **for** $t = 1, 2, \dots, T$ **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;Observe $\mathbf{x}_{t,a} \in \mathcal{X}_t$ for $a \in \mathcal{A}_t$

4: &nbsp;&nbsp;&nbsp;&nbsp;Compute $\boldsymbol{\beta}_{t-1}$ according to Equation (O2SLS)

5: &nbsp;&nbsp;&nbsp;&nbsp;Choose action $A_t$ that solves Equation (6)

6: &nbsp;&nbsp;&nbsp;&nbsp;Observe $\mathbf{z}_{t,A_t}$ and $y_t$

7: &nbsp;&nbsp;&nbsp;&nbsp;Update $\boldsymbol{\beta}_t \leftarrow \boldsymbol{\beta}_{t-1}, \hat{\mathbf{\Theta}}_t \leftarrow \hat{\mathbf{\Theta}}_{t-1}, \mathbf{b}'_t \leftarrow \mathbf{b}'_{t-1}$

8: **end for**

**Theorem 4.2 (Regret upper bound of OFUL-IV).** Under the assumptions and notations of Thm. 3.4 and 3.5, for horizon $T > 1$ and with probability $1 - \delta$, Algorithm 2 incurs regret

$$ R_T \le 2\sqrt{T} \underbrace{\sqrt{\mathbf{b}_{T-1}(\boldsymbol{\delta})}}_{\textit{Estimation}} \underbrace{\left(\sum_{t=1}^T \|\mathbf{x}_{t,A_t}\|_{\hat{\mathbf{H}}_t^{-1}}^2\right)^{1/2}}_{\textit{Second-stage feature norm}} = \mathcal{O}(\sqrt{d_x d_z T} \log T). $$

For just-identified IVs, i.e. $d_x = d_z = d$, OFUL-IV achieves regret of similar order under endogeneity as OFUL achieves under exogeneity, i.e. $\tilde{\mathcal{O}}(d\sqrt{T})$, and matches the lower bounds for linear bandits w.r.t. $d$ and $T$ [Lattimore and Szepesvári, 2020]. The proof details are in App. C.

1. **Handling unbounded outcomes.** We do not need bounded outcomes ($\boldsymbol{\beta}^\top \mathbf{x} \in [-1, 1]$) as OFUL [Abbasi-Yadkori et al., 2011a]. Similar to [Ouhamma et al., 2021], which removes this assumption for exogeneity, our analysis works for unbounded outcomes showing that the bounded outcome assumption is not needed even under endogeneity.

2. **Two-stage OFUL-IV vs. one-stage OFUL under endogeneity.** An alternative proposal than using a two-stage approach for LBE is to reduce it to a one-level linear bandit, i.e. $y_t =$
Thus, we conclude the proof and get that the oracle regret of O2SLS is $O(\gamma\sqrt{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)$ (Ouhamma et al., 2021). Under endogeneity and unbounded stochastic noise, O2SLS incurs an extra $O(\gamma\sqrt{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 O2SLS literature, this is referred as the self-fulfilling bias (Li et al., 2021). When the noises are independent, i.e. $\gamma = 0$, we retrieve an oracle regret of the same order as that of the exogenous case.

## 5. 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\sqrt{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 \in A_t$ drawn at time $t \in \{1, \dots, T\}$.

$$x_t = \Theta^\top z_{t,A_t} + \epsilon_t \qquad (\text{LBE-first})$$

$$y_t = \beta^\top x_t + \eta_t \qquad (\text{LBE-second})$$

Here, $y_t$ is the reward at round $t$. Each arm $a$ corresponds to a vector of IVs $z_{t,a} \in \mathcal{Z}_t \subset \mathbb{R}^d$, and a vector of endogenous variables $x_{t,a} \in \mathcal{X}_t \subset \mathbb{R}^d$ (generated as per (LBE-first)). Here, $\mathcal{X}_t$ and $\mathcal{Z}_t$ are sets of IVs and endogenous variables corresponding to $A_t$. Similar to regression setting, we have two sources of unobserved noises: $\epsilon_t$ ($\sigma^2\mathbb{I}$-sub-Gaussian) are i.i.d. vector error terms at round $t$ which is independent of $z$, and $\eta_t$ ($\sigma^2\mathbb{I}$-sub-Gaussian), representing all causes of $y_t$ other than $x_t$. True parameters $\beta \in \mathbb{R}^d$ and $\Theta \in \mathbb{R}^{d \times 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, \dots, T$, the agent

1. Observes a sample $z_{t,a} \in \mathcal{Z}_t$ and $x_{t,a} \in x_t$ of contexts for all $a \in A_t$

2. Chooses an arm $A_t \in A_t$

3. Obtains the reward $y_t$ computed from (LBE-first)

4. Updates the parameter estimates $\hat{\Theta}_t$ and $\beta_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^* = \underset{a \in A_t}{\operatorname{argmax}} \mathbb{E}[x_{t,a}^\top \beta]$$

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=1}^T$ 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} \subseteq \mathbb{R}^d$ around the parameter $\beta$, which is computed only using the observed data. Then, the
<figure><img src="image_5.png" /><figcaption>Figure 2: Regrets due to one-stage OFUL (green), OFUL (blue), and OFUL-IV (orange) for different norms of the hidden parameters ($S = 1, 3, 5$ from left to right). Only OFUL-IV (orange) is independent of $S$ and incurs the lowest regret across endogeneity levels $\rho$.</figcaption></figure>

($\Theta\beta)^{\top}z_t + \beta^{\top}\epsilon_t + \eta_t$. This leads to a composite unknown parameter $\Theta\beta$, and a new sub-Gaussian noise with component-wise variance $\sigma_{new}^2 = 2(\|\beta\|_2^2\sigma_{\epsilon}^2 + \sigma_{\eta}^2)$. Now, if we apply OFUL to this setup, we observe that the confidence bound around the new hidden parameter $\Theta\beta$ is proportional to $\sigma_{new}$. Thus, the confidence interval blows up by $\|\beta\|_2$. Also, using this interval in Equation (6) requires us to know either $\|\beta\|_2^2$ or a tight upper bound on it. In real-life, we cannot assume access to such knowledge. Additionally, $\|\beta\|_2^2$ grows linearly with $d_x$. Thus, this approach can incur significantly higher regret for high-dimensional covariates. In contrast, OFUL-IV does not require to know either $\|\beta\|_2$ or any bound on it. Additionally, the confidence interval of OFUL-IV depends on $\sigma_{\eta}^2$, which is significantly smaller than $\sigma_{new}^2$. These observations demonstrate the benefit of using OFUL-IV under endogeneity than OFUL with a single-stage reduction. Single-stage reduction might be helpful if the confounding noise is covariate dependent but is independent of the unknown parameter [Krishnamurthy et al., 2018]. Numerical results in Fig. 2 further validates this benefit of OFUL-IV over an one-stage reduction.

# 5 Experimental analysis

We present experimental results for both online regression and linear bandit in Figure 3a, 3b and 2. We compare the performance of O2SLS and Online Ridge Regression (Ridge). For LBEs, we compare the performance of OFUL-IV and OFUL [Abbasi-Yadkori et al., 2011a].

**Experimental Setup.** We induce endogeneity in the problem in the following arbitrary way: by settings $\eta_t = \rho\epsilon_{t,1} + \tilde{\eta}_t$ where $\epsilon_{t,1}$ indicates the first component of the vector $\epsilon_t$. Then, we can control the level of endogeneity of the first and second stages through $\rho$. We choose

<table><caption>Table 1: Experimental settings. $\rho$ controls endogeneity since $\eta_t = \rho\epsilon_{t,1} + \tilde{\eta}_t$ and $\tilde{\eta}_t$ is exogenous noise.</caption><thead><tr><th></th><th>Online regression</th><th>Linear bandit</th></tr></thead><tbody><tr><td>1st Stage</td><td>$\mathbf{x}_t = \mathbf{\Theta} \mathbf{z}_t + \mathbf{\epsilon}_t$</td><td>$\mathbf{x}_{t,a} = \mathbf{\Theta} \mathbf{z}_{t,a} + \mathbf{\epsilon}_t$</td></tr><tr><td>2nd Stage</td><td>$\mathbf{y}_t = \beta^{\top} \mathbf{x}_t + \eta_t$</td><td>$\mathbf{y}_t = \beta^{\top} \mathbf{x}_{t,A_t} + \eta_t$</td></tr></tbody></table>

$d_x = \{2, 5, 8\}$ and $d_z = \{4, 10, 16\}$ respectively. In our experiments, we choose arbitrarily $\beta$ as a normalised vector with equal negative entries; therefore, the values in the components are uniquely determined by the dimension $d_x$. We choose $\Theta = \mathbf{I}_{d_z, d_x}$ which has ones on the entries $i = j$ and zeros for $i \neq j$. Then, we sample at each time $t$ (and also for every arm $a$ for the LBE setting) the vectors $z_t \sim \mathcal{N}_{d_z}(\mathbf{0}, \mathbf{I}_{d_z})$ ($z_{t,a} \sim \mathcal{N}_{d_z}(\mathbf{0}, \mathbf{I}_{d_z})$), the vector noise $\epsilon_t \sim \mathcal{N}_{d_x}(\mathbf{0}, \mathbf{I}_{d_x})$, and the scalar noise $\eta_t = \tilde{\eta}_t + \rho \cdot \epsilon_{t,1}$ where $\tilde{\eta}_t \sim \mathcal{N}_1(0, 1)$. We run the algorithms with the same regularisation parameters, i.e. $\lambda = 0.1$. We repeat our experiments 20 times. We average the
**Algorithm 2 OFUL-IV**

1: **Input:** Initialization parameters $\beta_0, \hat{\Theta}_0, b'_0$

2: **for** $t = 1, 2, \dots, T$ **do**

3: Observe $z_{t,a} \in \mathcal{Z}_t$ and $x_{t,a} \in x_t$ for $a \in A_t$

4: Compute $\beta_{t-1}$ according to Equation (O2SLS)

5: Choose action $A_t$ that solves Equation (7)

6: Update $\beta_t \leftarrow \beta_{t-1}, \hat{\Theta}_t \leftarrow \hat{\Theta}_t, b'_t \leftarrow b'_t$

7: **end for**

algorithm chooses an optimistic estimate of $\tilde{\beta}_{t-1}$ from that confidence set:

$$ \tilde{\beta}_{t-1} = \underset{\beta' \in \mathcal{B}_{t-1}}{\operatorname{argmax}} \left( \max_{x \in \mathcal{X}_t} x^\top \beta' \right) $$

Then, she chooses the action leading to $x_t = \underset{x \in \mathcal{X}_t}{\operatorname{argmax}} x^\top \tilde{\beta}_t$, which maximizes the reward according to the estimate $\tilde{\beta}_t$. In brief, the algorithm chooses the pair $(x_t, \tilde{\beta}_{t-1}) = \underset{(x, \beta') \in \mathcal{X}_t \times \mathcal{B}_{t-1}}{\operatorname{argmax}} x^\top \beta'$.

In order to tackle endogeneity, we choose to use the O2SLS estimate $\beta_{t-1}$ computed using data observed till $t-1$. Then, we build an ellipsoid $\mathcal{B}_{t-1}$ around it, such that

$$ \mathcal{B}_{t-1} \triangleq \left\{ \beta \in \mathbb{R}^d : \|\beta_t - \beta\|_{\hat{\mathbf{H}}_t} \le \sqrt{\mathfrak{b}'_t(\delta)} \right\} $$

and

$$ \mathfrak{b}'_t(\delta) \triangleq 2\sigma_{\eta}^2 \log \left( \frac{\det(\mathbf{G}_{z,t})^{1/2} \lambda^{-d/2}}{\delta} \right). $$

Given this confidence interval, we optimistically choose the arm

$$ A_t = \underset{a \in A_t}{\operatorname{argmax}} \langle x_{t,a}, \beta_{t-1} \rangle + \sqrt{\mathfrak{b}'_{t-1}(\delta)} \|x_{t,a}\|_{\hat{\mathbf{H}}_{t-1}^{-1}}. \quad (7) $$

This arm selection index together with the O2SLS estimator yielding $\beta_{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 \le 2\sqrt{T} \underbrace{\sqrt{\mathfrak{b}_{T-1}(\delta)}}_{\substack{\text{Estimation} \\ \mathcal{O}(\sqrt{d \log T})}} \underbrace{\sqrt{(C_1^2 + dC_2^2)f(T) + C_4}}_{\substack{\text{Second Stage Feature norm} \\ \mathcal{O}(\sqrt{d \log T})}} $$

with probability $1 - \delta$ and for horizon $T > 1$.

*Proof Sketch. Step 1: Optimism.* We observe that $R_T = \sum_{t=1}^T \beta^\top x_* - \beta^\top x_t \triangleq \sum_{t=1}^T r_t$. Since $(x_t, \tilde{\beta}_{t-1})$ is optimistic in $\mathcal{X}_t \times \mathcal{B}_t$, and $\beta \in \mathcal{B}_t$, we obtain $r_t \le (\tilde{\beta}_{t-1} - \beta)^\top x_t$.

**Step 2: Decomposition.** Now, we decompose regret as

$$ (\tilde{\beta}_{t-1} - \beta)^\top x_t = (\tilde{\beta}_{t-1} - \beta_{t-1})^\top x_t + (\beta_{t-1} - \beta)^\top x_t. $$

The first term depends on tightness of confidence interval, while the second depends on accuracy of the estimate $\beta_{t-1}$.
<figure><img src="image_6.png" /><figcaption>Figure 3: (Left) **Regression:** Identification regrets of Online Ridge (blue) and O2SLS (orange) over $T = 5000$ steps, and for $\rho = 1, 1.5, 2$. With the increase in $\rho$, i.e. endogeneity, O2SLS performs better. (Right) **LBE:** Cumulative regrets of OFUL (blue) and OFUL-IV (orange) over $T = 5000$ steps with $\rho = 1, 1.5, 2$. OFUL-IV always incurs lower regrets, and improvements w.r.t. OFUL increases with $\rho$.</figcaption></figure>

results, and for each algorithm, we report the mean and standard deviation of the cumulative regret (shaded areas correspond to one standard deviation). For further experiments and results with both synthetic and real data, see Appendix D.

**Summary of Results.** 1. *Regression.* O2SLS outperforms Ridge in the whole parameter space under study, and the performance-gain increases with increasing values of the $\rho$ parameter, i.e. with increasing level of endogeneity. 2. *Bandits.* OFUL builds a confidence ellipsoid centered at $\beta_t^{\text{Ridge}}$, while OFUL-IV uses O2SLS to build an accurate estimate and an ellipsoid that with high probability contains $\beta$. Figure 3 indicates that OFUL-IV incurs lower regret than OFUL. 3. *Independence of OFUL-IV from the norm of hidden parameters.* Figure 2 shows that only OFUL-IV's regret is independent of the maximum norm of $\beta$, i.e. $S$. But OFUL (oblivious to endogeneity) and OFUL applied on one-stage reduction of IV regression incurs higher regret with increasing values of $S$ as indicated by theory.

# 6 Conclusion and future works

We study online IV regression, specifically online 2SLS, for unbounded noise and endogenous data. We analyse the finite-time identification and oracle regrets of O2SLS. We observe that O2SLS incurs $O(d_x d_z \log^2 T)$ identification regret, and $O(\gamma\sqrt{d_z T \log T})$ oracle regret as the correlation between the noises in the two-stages dominate the identification regret. For just-identified IVs, identification regrets are of the same order for exogeneity and endogeneity. We further propose OFUL-IV for stochastic linear bandits with endogeneity that uses O2SLS to estimate the parameters. We show that OFUL-IV achieves $O(\sqrt{d_x d_z T \log T})$ regret. We experimentally show that O2SLS and OFUL-IV are more accurate than Ridge and OFUL, respectively. In future, it would be interesting to extend the stochastic analysis of online IV regression and bandits with endogeneity to non-parametric [Newey and Powell, 2003], non-linear [Xu et al., 2020], and non-stationary [Russac et al., 2019] settings.
<figure><img src="image_3.png" /><figcaption>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 $\beta$ (right). OFUL-IV incurs lower instantaneous regret and MSE.</figcaption></figure>

**Step 3: Confidence Bound.** Now, we can decouple the impact of parameter and observed data in both the terms using $\|\tilde{\beta}_{t-1} - \beta_{t-1}\|_{\hat{\mathbf{H}}_{t-1}} \|\mathbf{x}_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}$ and $\|\beta_{t-1} - \beta\|_{\hat{\mathbf{H}}_{t-1}} \|\mathbf{x}_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}$, respectively. By construction of the optimistic confidence interval and concentrations bound of Lemma 4.1, both $\|\tilde{\beta}_{t-1} - \beta_{t-1}\|_{\hat{\mathbf{H}}_{t-1}}$ and $\|\beta_{t-1} - \beta\|_{\hat{\mathbf{H}}_{t-1}}$ are bounded by $\sqrt{\mathbf{b}'_{t-1}(\delta)}$. By determinant-trace inequality (Lemma A.1), we get that $\mathbf{b}'_{t-1}(\delta) \le \frac{d\sigma_{\eta}^2}{4} \log(\frac{1+TL_z^2/\lambda}{\delta})$.

**Final Step.** Since the regret $R_T \le \sqrt{T \sum_{t=1}^T r_t^2}$, we obtain

$$R_T \le \sigma_{\eta} \sqrt{dT \log \left(\frac{1+TL_z^2/\lambda}{\delta}\right) \left(\sum_{t=1}^T \|\mathbf{x}_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2\right)}.$$

Now, we bound the sum of the first-stage feature norms $\sum_{t=1}^T \|\mathbf{x}_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2$ by $(C_1^2 + 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\sqrt{T} \log T)$. OFUL-IV achieves regret of similar order under endogeneity as OFUL achieves under exogeneity.

**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 $\beta_{\text{Ridge},t}$ to concentrate around $\beta$, 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 $\|\beta_t - \beta\|^2$ over 100 runs. We run the algorithms with the same regularisation parameters equal to $10^{-3}$. We denote the normal distribution with mean $\mu$ and standard deviation $\sigma$ as $N(\mu, \sigma)$, 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 $\beta \sim N_{50}(\vec{0}, \mathbb{I}_{50})$ and $\Theta_{i,j} \sim N(0, 1)$ for each component. Then we sample at each time $t$ the vectors $z_{t,a} \sim N_{50}(\vec{0}, \mathbb{I}_{50})$, $\epsilon_{t,a} \sim N_{50}(\vec{0}, \mathbb{I}_{50})$, and the scalar noise $\eta_{t,a} = \frac{1}{13}(\tilde{\eta}_{t,a} + \sum_{i=1}^{12} \epsilon_{t,a,i})$ where $\tilde{\eta}_{t,a} \sim 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.
References

Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. *Advances in neural information processing systems*, 24, 2011a.

Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Online least squares estimation with self-normalized processes: An application to bandit problems. *arXiv preprint arXiv:1102.2670*, 2011b.

Yasin Abbasi-Yadkori, David Pal, and Csaba Szepesvari. Online-to-confidence-set conversions and application to sparse stochastic bandits. In *Artificial Intelligence and Statistics*, pages 1–9. PMLR, 2012.

Marc Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In *AISTATS*, 2017.

Joshua D Angrist and Guido W Imbens. Two-stage least squares estimation of average causal effects in models with variable treatment intensity. *Journal of the American statistical Association*, 90 (430):431–442, 1995.

Joshua D Angrist, Guido W Imbens, and Donald B Rubin. Identification of causal effects using instrumental variables. *Journal of the American statistical Association*, 91(434):444–455, 1996.

Peter L Bartlett, Wouter M Koolen, Alan Malek, Eiji Takimoto, and Manfred K Warmuth. Minimax fixed-design linear regression. In *Conference on Learning Theory*, pages 226–239. PMLR, 2015.

Andrew Bennett, Nathan Kallus, and Tobias Schnabel. Deep generalized method of moments for instrumental variable analysis. *Advances in neural information processing systems*, 32, 2019.

Glenn W. Brier. Verification of forecasts expressed in terms of probability. *Monthly Weather Review*, 78:1–3, 1950.

Stephen Burgess, Dylan S Small, and Simon G Thompson. A review of instrumental variable estimators for mendelian randomization. *Statistical methods in medical research*, 26(5):2333–2355, 2017.

Nicolo Cesa-Bianchi and Gábor Lugosi. *Prediction, learning, and games*. Cambridge university press, 2006.

Dean P Foster. Prediction in the worst case. *The Annals of Statistics*, pages 1084–1090, 1991.

Dylan Foster and Alexander Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. In *International Conference on Machine Learning*, pages 3199–3210. PMLR, 2020.

Pierre Gaillard, Sébastien Gerchinovitz, Malo Huard, and Gilles Stoltz. Uniform regret bounds over $\mathbb{R}^d$ for the sequential linear regression problem with the square loss. In *Algorithmic Learning Theory*, pages 404–432. PMLR, 2019.

William H Greene. *Econometric analysis*. Pearson Education India, 2003.

Keegan Harris, Dung Daniel T Ngo, Logan Stapleton, Hoda Heidari, and Steven Wu. Strategic instrumental variable regression: Recovering causal relationships from strategic responses. In *International Conference on Machine Learning*, pages 8502–8522. PMLR, 2022.

Jason Hartford, Greg Lewis, Kevin Leyton-Brown, and Matt Taddy. Counterfactual prediction with deep instrumental variables networks. *arXiv preprint arXiv:1612.09596*, 2016.
# 6. 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(\|\gamma\|_2 \sqrt{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\sqrt{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 (Newey and Powell, 2003; Chen et al., 2020). Still, it is an open question how optimally IVs can be identified online, while O2SLS is performed simultaneously.

# References

* Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. *Advances in neural information processing systems*, 24, 2011a.

* Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Online least squares estimation with self-normalized processes: An application to bandit problems. *arXiv preprint arXiv:1102.2670*, 2011b.

* Yasin Abbasi-Yadkori, David Pal, and Csaba Szepesvari. Online-to-confidence-set conversions and application to sparse stochastic bandits. In *Artificial Intelligence and Statistics*, pages 1-9. PMLR, 2012.

* Marc Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In *AISTATS*, 2017.

* Joshua D Angrist and Guido W Imbens. Two-stage least squares estimation of average causal effects in models with variable treatment intensity. *Journal of the American statistical Association*, 90 (430):431-442, 1995.

* Joshua D Angrist, Guido W Imbens, and Donald B Rubin. Identification of causal effects using instrumental variables. *Journal of the American statistical Association*, 91(434):444-455, 1996.

* Peter L Bartlett, Wouter M Koolen, Alan Malek, Eiji Takimoto, and Manfred K Warmuth. Minimax fixed-design linear regression. In *Conference on Learning Theory*, pages 226-239. PMLR, 2015.

* Andrew Bennett, Nathan Kallus, and Tobias Schnabel. Deep generalized method of moments for instrumental variable analysis. *Advances in neural information processing systems*, 32, 2019.

* Glenn W. Brier. Verification of forecasts expressed in terms of probability. *Monthly Weather Review*, 78:1-3, 1950.

* Stephen Burgess, Dylan S Small, and Simon G Thompson. A review of instrumental variable estimators for mendelian randomization. *Statistical methods in medical research*, 26(5):2333-2355, 2017.

* Pedro Carneiro, James J Heckman, and Edward J Vytlacil. Estimating marginal returns to education. *American Economic Review*, 101(6):2754-81, 2011.
Elad Hazan and Tomer Koren. Linear regression with limited observation. In *29th International Conference on Machine Learning*, ICML 2012, pages 807–814, 2012.

Christiaan Heij, Paul de Boer, Philip Hans Franses, Teun Kloek, and Herman K van Dijk. *Econometric methods with applications in business and economics*. Oxford University Press, 2004.

MA Hernan and J Robins. *Causal Inference: What if*. Boca Raton: Chapman & Hill/CRC, 2020.

Nathan Kallus. Instrument-armed bandits. In *Algorithmic Learning Theory*, pages 529–546. PMLR, 2018.

Abbas Kazerouni and Lawrence M Wein. Best arm identification in generalized linear bandits. *Operations Research Letters*, 49(3):365–371, 2021.

Jyrki Kivinen, Alexander J Smola, and Robert C Williamson. Online learning with kernels. *IEEE transactions on signal processing*, 52(8):2165–2176, 2004.

Akshay Krishnamurthy, Zhiwei Steven Wu, and Vasilis Syrgkanis. Semiparametric contextual bandits. In *International Conference on Machine Learning*, pages 2776–2785. PMLR, 2018.

Tor Lattimore and Csaba Szepesvári. *Bandit algorithms*. Cambridge University Press, 2020.

Jin Li, Ye Luo, and Xiaowei Zhang. Self-fulfilling bandits: Dynamic selection in algorithmic decision-making. *arXiv preprint arXiv:2108.12547*, 2021.

Nicholas Littlestone, Philip M Long, and Manfred K Warmuth. On-line learning of linear functions. In *Proceedings of the twenty-third annual ACM symposium on Theory of computing*, pages 465–475, 1991.

Ruiqi Liu, Zuofeng Shang, and Guang Cheng. On deep instrumental variables estimate. *arXiv preprint arXiv:2004.14954*, 2020.

Odalric-Ambrym Maillard. Self-normalization techniques for streaming confident regression, 2016.

Magne Mogstad, Alexander Torgovitsky, and Christopher R Walters. The causal interpretation of two-stage least squares with multiple instrumental variables. *American Economic Review*, 111(11):3663–98, 2021.

Maria Nareklishvili, Nicholas Polson, and Vadim Sokolov. Deep partial least squares for iv regression. *arXiv preprint arXiv:2207.02612*, 2022.

Whitney K Newey and James L Powell. Instrumental variable estimation of nonparametric models. *Econometrica*, 71(5):1565–1578, 2003.

Francesco Orabona. A modern introduction to online learning. *arXiv preprint arXiv:1912.13213*, 2019.

Reda Ouhamma, Odalric Maillard, and Vianney Perchet. Stochastic online linear regression: the forward algorithm to replace ridge. *arXiv preprint arXiv:2111.01602*, 2021.

Reda Ouhamma, Debabrota Basu, and Odalric-Ambrym Maillard. Bilinear exponential family of mdps: Frequentist regret bound with tractable exploration and planning. *arXiv preprint arXiv:2210.02087*, 2022.

Matteo Papini, Andrea Tirinzoni, Marcello Restelli, Alessandro Lazaric, and Matteo Pirotta. Leveraging good representations in linear contextual bandits. In *International Conference on Machine Learning*, pages 8371–8380. PMLR, 2021.
Nicolo Cesa-Bianchi and Gábor Lugosi. *Prediction, learning, and games*. Cambridge university press, 2006.

Jiafeng Chen, Daniel L Chen, and Greg Lewis. Mostly harmless machine learning: learning optimal instruments in linear iv models. *arXiv preprint arXiv:2011.06158*, 2020.

Dean P Foster. Prediction in the worst case. *The Annals of Statistics*, pages 1084–1090, 1991.

Dylan Foster and Alexander Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. In *International Conference on Machine Learning*, pages 3199–3210. PMLR, 2020.

David A Freedman. On tail probabilities for martingales. *the Annals of Probability*, pages 100–118, 1975.

Pierre Gaillard, Sébastien Gerchinovitz, Malo Huard, and Gilles Stoltz. Uniform regret bounds over $\mathbb{R}^d$ for the sequential linear regression problem with the square loss. In *Algorithmic Learning Theory*, pages 404–432. PMLR, 2019.

William H Greene. *Econometric analysis*. Pearson Education India, 2003.

Keegan Harris, Dung Daniel T Ngo, Logan Stapleton, Hoda Heidari, and Steven Wu. Strategic instrumental variable regression: Recovering causal relationships from strategic responses. In *International Conference on Machine Learning*, pages 8502–8522. PMLR, 2022.

Jason Hartford, Greg Lewis, Kevin Leyton-Brown, and Matt Taddy. Counterfactual prediction with deep instrumental variables networks. *arXiv preprint arXiv:1612.09596*, 2016.

Elad Hazan and Tomer Koren. Linear regression with limited observation. In *29th International Conference on Machine Learning, ICML 2012*, pages 807–814, 2012.

MA Hernan and J Robins. *Causal Inference: What if*. Boca Raton: Chapman & Hill/CRC, 2020.

Nathan Kallus. Instrument-armed bandits. In *Algorithmic Learning Theory*, pages 529–546. PMLR, 2018.

Abbas Kazerouni and Lawrence M Wein. Best arm identification in generalized linear bandits. *Operations Research Letters*, 49(3):365–371, 2021.

Jyrki Kivinen, Alexander J Smola, and Robert C Williamson. Online learning with kernels. *IEEE transactions on signal processing*, 52(8):2165–2176, 2004.

Tor Lattimore and Csaba Szepesvári. *Bandit algorithms*. Cambridge University Press, 2020.

Jin Li, Ye Luo, and Xiaowei Zhang. Self-fulfilling bandits: Dynamic selection in algorithmic decision-making. *arXiv preprint arXiv:2108.12547*, 2021.

Nicholas Littlestone, Philip M Long, and Manfred K Warmuth. On-line learning of linear functions. In *Proceedings of the twenty-third annual ACM symposium on Theory of computing*, pages 465–475, 1991.

Ruiqi Liu, Zuofeng Shang, and Guang Cheng. On deep instrumental variables estimate. *arXiv preprint arXiv:2004.14954*, 2020.
Donald B Rubin. Estimating causal effects of treatments in randomized and nonrandomized studies. *Journal of educational Psychology*, 66(5):688, 1974.

Yoan Russac, Claire Vernade, and Olivier Cappé. Weighted linear bandits for non-stationary environments. *Advances in Neural Information Processing Systems*, 32, 2019.

Shai Shalev-Shwartz and Shai Ben-David. *Understanding machine learning: From theory to algorithms*. Cambridge university press, 2014.

Amandeep Singh, Kartik Hosanagar, and Amit Gandhi. Machine learning instrument variables for causal inference. In *Proceedings of the 21st ACM Conference on Economics and Computation*, pages 835–836, 2020.

Andrew Stirn and Tony Jebara. Thompson sampling for noncompliant bandits. *arXiv preprint arXiv:1812.00856*, 2018.

Ambuj Tewari and Susan A Murphy. From ads to interventions: Contextual bandits in mobile health. *Mobile health: sensors, analytic methods, and applications*, pages 495–517, 2017.

Andrea Tirinzoni, Matteo Papini, Ahmed Touati, Alessandro Lazaric, and Matteo Pirotta. Scalable representation learning in linear contextual bandits with constant regret guarantees. *Advances in Neural Information Processing Systems*, 35:2307–2319, 2022.

Arun Venkatraman, Wen Sun, Martial Hebert, J Bagnell, and Byron Boots. Online instrumental variable regression with applications to online linear system identification. In *Proceedings of the AAAI Conference on Artificial Intelligence*, 2016.

Roman Vershynin. *High-dimensional probability: An introduction with applications in data science*, volume 47. Cambridge university press, 2018.

Volodya Vovk. Competitive on-line linear regression. *Advances in Neural Information Processing Systems*, 10, 1997.

Volodya Vovk. Competitive on-line statistics. *International Statistical Review*, 69(2):213–248, 2001.

Martin J Wainwright. *High-dimensional statistics: A non-asymptotic viewpoint*, volume 48. Cambridge University Press, 2019.

Abraham Wald. The fitting of straight lines if both variables are subject to error. *The annals of mathematical statistics*, 11(3):284–300, 1940.

Larry Wasserman. *All of statistics: a concise course in statistical inference*, volume 26. Springer, 2004.

Philip G Wright. *Tariff on animal and vegetable oils*. Macmillan Company, New York, 1928.

Liyuan Xu, Yutian Chen, Siddarth Srinivasan, Nando de Freitas, Arnaud Doucet, and Arthur Gretton. Learning deep features in instrumental variable regression. *arXiv preprint arXiv:2010.07154*, 2020.

Liyuan Xu, Heishiro Kanagawa, and Arthur Gretton. Deep proxy causal learning and its application to confounded bandit policy evaluation. *arXiv preprint arXiv:2106.03907*, 2021.

Yuchen Zhu, Limor Gultchin, Arthur Gretton, Matt J Kusner, and Ricardo Silva. Causal inference with treatment measurement error: a nonparametric instrumental variable approach. In *Uncertainty in Artificial Intelligence*, pages 2414–2424. PMLR, 2022.
Magne Mogstad, Alexander Torgovitsky, and Christopher R Walters. The causal interpretation of two-stage least squares with multiple instrumental variables. *American Economic Review*, 111 (11):3663-98, 2021.

Maria Nareklishvili, Nicholas Polson, and Vadim Sokolov. Deep partial least squares for iv regression. *arXiv preprint arXiv:2207.02612*, 2022.

Whitney K Newey and James L Powell. Instrumental variable estimation of nonparametric models. *Econometrica*, 71(5):1565-1578, 2003.

Francesco Orabona. A modern introduction to online learning. *arXiv preprint arXiv:1912.13213*, 2019.

Reda Ouhamma, Odalric Maillard, and Vianney Perchet. Stochastic online linear regression: the forward algorithm to replace ridge. *arXiv preprint arXiv:2111.01602*, 2021.

Reda Ouhamma, Debabrota Basu, and Odalric-Ambrym Maillard. Bilinear exponential family of mdps: Frequentist regret bound with tractable exploration and planning. *arXiv preprint arXiv:2210.02087*, 2022.

Donald B Rubin. Estimating causal effects of treatments in randomized and nonrandomized studies. *Journal of educational Psychology*, 66(5):688, 1974.

Amandeep Singh, Kartik Hosanagar, and Amit Gandhi. Machine learning instrument variables for causal inference. In *Proceedings of the 21st ACM Conference on Economics and Computation*, pages 835–836, 2020.

Andrew Stirn and Tony Jebara. Thompson sampling for noncompliant bandits. *arXiv preprint arXiv:1812.00856*, 2018.

Arun Venkatraman, Wen Sun, Martial Hebert, J Bagnell, and Byron Boots. Online instrumental variable regression with applications to online linear system identification. In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 30, 2016.

Volodya Vovk. Competitive on-line linear regression. *Advances in Neural Information Processing Systems*, 10, 1997.

Volodya Vovk. Competitive on-line statistics. *International Statistical Review*, 69(2):213-248, 2001.

Martin J Wainwright. *High-dimensional statistics: A non-asymptotic viewpoint*, volume 48. Cambridge University Press, 2019.

Abraham Wald. The fitting of straight lines if both variables are subject to error. *The annals of mathematical statistics*, 11(3):284-300, 1940.

Larry Wasserman. *All of statistics: a concise course in statistical inference*, volume 26. Springer, 2004.

Philip G Wright. *Tariff on animal and vegetable oils*. Macmillan Company, New York, 1928.

Liyuan Xu, Yutian Chen, Siddarth Srinivasan, Nando de Freitas, Arnaud Doucet, and Arthur Gretton. Learning deep features in instrumental variable regression. *arXiv preprint arXiv:2010.07154*, 2020.
# A Notations and useful results

We indicate in bold vectors and matrices, e.g. the vector and matrix (matrices are also usually capitalised) $\mathbf{v} \in \mathbb{R}^d$, $\mathbf{A} \in \mathbb{R}^{d \times d}$; while scalars do not use the bold notation, e.g. the scalar $s \in \mathbb{R}$. We indicate the determinant of matrix $\mathbf{A}$ with $\det(\mathbf{A})$ and its trace with $\mathrm{Tr}(\mathbf{A})$. For a $x \in \mathbb{R}_{\ge 0}$, we indicate the function that takes as input $x$, and gives as output the least integer greater than or equal to $x$ as $\lceil x \rceil$ (ceiling function). We indicate the identity matrix of dimension $d$ with $\mathbf{I}_d$ and when dimensions differ we indicate $\mathbf{I}_{d_1,d_2}$ a matrix which has ones on the entries $i = j$ and zeros for $i \neq j$. We dedicate the following table to index all the notations used in this paper. Note that every notation is defined, when it is introduced as well.

<table><caption>Table 2: Notations</caption><tr><td><b>x</b><sub>t</sub></td><td>Δ Covariates</td></tr><tr><td><b>z</b><sub>t</sub></td><td>Δ Instrumental Variables (IVs)</td></tr><tr><td><b>y</b><sub>t</sub></td><td>Δ Outcome variable</td></tr><tr><td><b>d</b><sub>z</sub></td><td>Δ Dimension of the IVs</td></tr><tr><td><b>d</b><sub>x</sub></td><td>Δ Dimension of the covariates</td></tr><tr><td><b>β</b></td><td>Δ True parameter for the second-stage</td></tr><tr><td><b>Θ</b></td><td>Δ True parameter for the first-stage</td></tr><tr><td><b>β</b><sub>t</sub></td><td>Δ O2SLS estimate of parameter for the second-stage at time t</td></tr><tr><td><b>Θ̂</b><sub>t</sub></td><td>Δ Estimate of parameter for the second-stage at time t</td></tr><tr><td><b>τ</b></td><td>Δ Relevance parameter</td></tr><tr><td><b>L</b><sub>Θ</sub></td><td>Δ Bound on the operator norm of the true first-stage parameter</td></tr><tr><td><b>L</b><sub>z</sub></td><td>Δ Bound on the <i>l</i><sub>2</sub> norms of IVs</td></tr><tr><td><b>σ</b><sub>η</sub><sup>2</sup></td><td>Δ Bound on the variance of the second-stage noise η</td></tr><tr><td><b>σ</b><sub>ε</sub><sup>2</sup></td><td>Δ Bound on the variance of the components of the first-stage noise ε</td></tr><tr><td><b>C</b><sub>1</sub></td><td>Δ √(2(1 + <b>L</b><sub>Θ</sub><b>τ</b><sup>2</sup>))</td></tr><tr><td><b>C</b><sub>2</sub></td><td>Δ 8e<sup>2</sup> (<b>σ</b><sub>η</sub><sup>2</sup> + <b>σ</b><sub>ε</sub><sup>2</sup>) <b>τ</b>/<b>L</b><sub>z</sub> √log <sup>2</sup>/<sub>δ</sub></td></tr><tr><td><b>C</b><sub>3</sub></td><td>Δ 8e<sup>2</sup> (<b>σ</b><sub>η</sub><sup>2</sup> + <b>σ</b><sub>ε</sub><sup>2</sup>) <b>τ</b>/<b>L</b><sub>z</sub> √max{<sup>1</sup>/<sub>λ</sub>, <sup>2</sup>/<sub>λ<sub>min</sub>(Σ)</sub>} log <sup>2</sup>/<sub>δ</sub></td></tr><tr><td><b>C</b><sub>4</sub></td><td>Δ <b>τ</b>/<b>L</b><sub>z</sub> (<b>T</b><sub>0</sub>√<sup>λ<sub>min</sub>(Σ)</sup>/<sub>λ</sub> + 2√2)</td></tr><tr><td><b>C</b><sub>5</sub></td><td>Δ A T-independent constant of O(<b>d</b><sub>x</sub><b>σ</b><sub>ε</sub><sup>2</sup>) (Equation (24))</td></tr><tr><td><b>G</b><sub>z,t</sub></td><td>Δ First-stage design matrix <b>G</b><sub>z,0</sub> + Σ<sub>s=1</sub><sup>t</sup> <b>z</b><sub>s</sub><b>z</b><sub>s</sub><sup>T</sup></td></tr><tr><td><b>Ĥ</b><sub>t</sub></td><td>Δ Second-stage design matrix <b>Θ̂</b><sub>t</sub><sup>T</sup> <b>Z</b><sub>t</sub><sup>T</sup> <b>Z</b><sub>t</sub><b>Θ</b><sub>t</sub></td></tr><tr><td><b>Σ</b></td><td>Δ The true covariance matrix of IVs E[<b>z</b><b>z</b><sup>T</sup>]</td></tr><tr><td><b>b</b><sub>t</sub>(δ)</td><td>Δ Radius of the second-stage confidence ellipsoid at time t (Equation (16))</td></tr><tr><td><b>λ</b></td><td>Δ Minimum eigenvalue of <b>G</b><sub>z,0</sub>, i.e. the (positive-valued) regularisation parameter</td></tr><tr><td><b>γ</b></td><td>Δ Covariance vector of the first-and second-stage noises E[<b>ε</b>δ]</td></tr><tr><td><b>γ</b></td><td>Δ <i>l</i><sub>2</sub> norm of the covariance vector γ</td></tr><tr><td><b>f</b>(T)</td><td>Δ Bound on the sum of maximum eigenvalues of the inverse of first-stage design matrices till time T, i.e. O(log(T)) (Corollary B.9)</td></tr></table>
Liyuan Xu, Heishiro Kanagawa, and Arthur Gretton. Deep proxy causal learning and its application to confounded bandit policy evaluation. *arXiv preprint arXiv:2106.03907*, 2021.

Yuchen Zhu, Limor Gultchin, Arthur Gretton, Matt J Kusner, and Ricardo Silva. Causal inference with treatment measurement error: a nonparametric instrumental variable approach. In *Uncertainty in Artificial Intelligence*, pages 2414–2424. PMLR, 2022.
## A.1 Vectors, matrices, and norms

**Definition A.1** ($l_p$-norms). For a vector $v \in \mathbb{R}^n$, we express its $l_p$-norm as $||v||_p$ for $p \ge 0$. A special case is the Euclidean $l_2$-norm denoted as $||\cdot||_2$, which is induced by classical scalar product on $\mathbb{R}^n$ denoted by $\langle \cdot, \cdot \rangle$.

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

$$ \sigma_{\max}(A) = \sigma_1(A) \ge \sigma_2(A) \ge \dots \ge \sigma_m(A) = \sigma_{\min}(A) \ge 0 $$

The minimum and maximum singular values have the variational characterisation

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

where $\mathbb{S}^{d-1} \triangleq \{v \in \mathbb{R}^d | ||v||_2 = 1\}$ is the Euclidean unit sphere in $\mathbb{R}^d$.

**Definition A.2** ($l_2$-operator norm). The spectral or $l_2$-operator norm of $A$ is defined as

$$ ||A||_2 \triangleq \sigma_{\max}(A). \qquad (7) $$

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

$$ S_{+}^{d \times d} \triangleq \{Q \in S^{d \times d} | Q \succeq 0\}. $$

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

$$ \lambda_{\max}(Q) = \lambda_1(Q) \ge \lambda_2(Q) \ge \dots \ge \lambda_d(Q) = \lambda_{\min}(Q). $$

Note that a matrix $Q$ is positive semidefinite-written $Q \succeq 0$ for short-if and only if $\lambda_{\min}(Q) \ge 0$. **Remark A.3** (Rayleigh-Ritz variational characterisation of eigenvalues). We remind also the Rayleigh-Ritz variational characterisation of the minimum and maximum eigenvalues-namely

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

**Remark A.4.** For any symmetric matrix $Q$, the $l_2$-operator norm can be written as

$$ ||Q||_2 = \max \{ \lambda_{\max}(Q), |\lambda_{\min}(Q)| \}, $$

by virtue of which it inherits the variational representation $||Q||_2 = \max_{v \in \mathbb{S}^{d-1}} |v^\top Q v|.$

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

$$ \lambda_j(R) = (\sigma_j(A))^2 \quad \text{for } j = 1, \dots, m $$

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

**Definition A.6.** For any vector $y \in \mathbb{R}^n$ and matrix $A \in S_{+}^{n \times n}$, let us define the norm $||y||_A \triangleq \sqrt{y^T A y} = \sqrt{\langle y, A y \rangle}$.

Throughout the paper we will need often to bound matrix induced norms using $l_2$-norms for operators, the following results show how this can be done easily for generic matrices. We specialise this result as we need in the text.
# 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) $\mathbf{v} \in \mathbb{R}^d$, $\mathbf{A} \in \mathbb{R}^{d \times d}$; while scalars do not use the bold notation, e.g. the scalar $s \in \mathbb{R}$. We indicate the determinant of matrix $\mathbf{A}$ with $\det(\mathbf{A})$ and its trace with $\mathrm{Tr}(\mathbf{A})$. For a $x \in \mathbb{R}_{\ge 0}$, we indicate the function that takes as input $x$, and gives as output the least integer greater than or equal to $x$ as $\lceil x \rceil$ (ceiling function). We indicate the identity matrix of dimension $d$ with $\mathbb{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 $\mu = \mathbb{E}[X]$ is sub-Gaussian if there is a positive number $\sigma$ such that

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

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

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

### A.2 Norms of Vectors and Matrices

**Definition A.3 (l_p-norms).** For a vector $\mathbf{v} \in \mathbb{R}^n$, we express its l_p-norm as $\|\mathbf{v}\|_p$ for $p \ge 0$. A special case is the Euclidean l_2-norm denoted as $\|\cdot\|_2$, which is induced by classical scalar product on $\mathbb{R}^n$ denoted by $\langle \cdot, \cdot \rangle$.

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

$$ \sigma_{\max}(\mathbf{A}) = \sigma_1(\mathbf{A}) \ge \sigma_2(\mathbf{A}) \ge \cdots \ge \sigma_m(\mathbf{A}) = \sigma_{\min}(\mathbf{A}) \ge 0 $$

The minimum and maximum singular values have the variational characterization

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

where $\mathbb{S}^{d-1} \triangleq \{\mathbf{v} \in \mathbb{R}^d | \|\mathbf{v}\|_2 = 1\}$ is the Euclidean unit sphere in $\mathbb{R}^d$.

**Definition A.4 (l_2-operator norm).** The spectral or l_2-operator norm of $\mathbf{A}$ is defined as

$$ \|\mathbf{A}\|_2 \triangleq \sigma_{\max}(\mathbf{A}). \qquad (8) $$

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

$$ S_{+}^{d \times d} \triangleq \{ \mathbf{Q} \in S^{d \times d} | \mathbf{Q} \succeq 0 \}. $$
**Proposition A.7.** Take $\mathbf{A}, \mathbf{B} \in \mathbb{R}^{n \times n}$, with $\mathbf{B} \succeq 0$ positive semi-definite and $\mathbf{x} \in \mathbb{R}^n$

$$ \|\mathbf{A}\mathbf{x}\|_{\mathbf{B}}^2 = \|\mathbf{x}\|_{\mathbf{A}^{\top}\mathbf{B}\mathbf{A}}^2 \le \|\mathbf{B}\|_2 \|\mathbf{A}\|_2^2 \|\mathbf{x}\|_2^2 \quad (8) $$

*Proof.* The equality holds since we can rewrite

$$ \|\mathbf{A}\mathbf{x}\|_{\mathbf{B}}^2 = \langle \mathbf{A}\mathbf{x}, \mathbf{B}\mathbf{A}\mathbf{x} \rangle = \langle \mathbf{x}, \mathbf{A}^{\top}\mathbf{B}\mathbf{A}\mathbf{x} \rangle = \|\mathbf{x}\|_{\mathbf{A}^{\top}\mathbf{B}\mathbf{A}}^2. $$

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

$$ \langle \mathbf{A}\mathbf{x}, \mathbf{B}\mathbf{A}\mathbf{x} \rangle = \frac{\langle \mathbf{A}\mathbf{x}, \mathbf{B}\mathbf{A}\mathbf{x} \rangle}{\|\mathbf{A}\mathbf{x}\|_2^2} \frac{\|\mathbf{A}\mathbf{x}\|_2^2}{\|\mathbf{x}\|_2^2} \|\mathbf{x}\|_2^2 = \frac{\langle \mathbf{y}, \mathbf{B}\mathbf{y} \rangle}{\|\mathbf{y}\|_2^2} \frac{\|\mathbf{A}\mathbf{x}\|_2^2}{\|\mathbf{x}\|_2^2} \|\mathbf{x}\|_2^2 \le \|\mathbf{B}\|_2 \|\mathbf{A}\|_2^2 \|\mathbf{x}\|_2^2. $$

We note that the inequality holds trivially for $\mathbf{x}$ in the null space of $\mathbf{A}$, therefore, in the previous case, we can safely divide by $\|\mathbf{A}\mathbf{x}\|_2$ and $\|\mathbf{x}\|_2$. $\square$

**Lemma A.8 (Determinant-Trace Inequality).** Suppose $z_1, z_2, \dots, z_t \in \mathbb{R}^d$ and for any $1 \le s \le t$, $\|z_s\|_2 \le L_z$. Let $\mathbf{G}_{z,t} = \lambda \mathbf{I}_{d_z} + \sum_{s=1}^t z_s z_s^\top$ for some $\lambda > 0$. Then,

$$ \det(\mathbf{G}_{z,t}) \le (\lambda + tL_z^2/d_z)^{d_z} \quad (9) $$

*Proof.* Let $\alpha_1, \alpha_2, \dots, \alpha_{d_z}$ be the eigenvalues of $\mathbf{G}_{z,t}$. Since $\mathbf{G}_{z,t}$ is positive definite, its eigenvalues are positive. Also, note that $\det(\mathbf{G}_{z,t}) = \prod_{s=1}^{d_z} \alpha_s$ and $\mathrm{Tr}(\mathbf{G}_{z,t}) = \sum_{s=1}^{d_z} \alpha_s$. By inequality of arithmetic and geometric means,

$$ d_z \sqrt{\alpha_1 \alpha_2 \cdots \alpha_{d_z}} \le \frac{\alpha_1 + \alpha_2 + \cdots + \alpha_{d_z}}{d_z}. $$

Therefore, $\det(\mathbf{G}_{z,t}) \le (\mathrm{Tr}(\mathbf{G}_{z,t})/d_z)^{d_z}$. Now, it remains to upper bound the trace:

$$ \mathrm{Tr}(\mathbf{G}_{z,t}) = \mathrm{Tr}(\lambda \mathbf{I}_{d_z}) + \sum_{s=1}^{t} \mathrm{Tr}(z_s z_s^\top) = d_z \lambda + \sum_{s=1}^{t} \|z_s\|_2^2 \le d_z \lambda + t L_z^2. $$

$\square$

As a direct corollary of Weyl's theorem for eigenvalues, we have the following [Wainwright, 2019].

**Lemma A.9.** For two symmetric matrices $\mathbf{A}$ and $\mathbf{B}$

$$ |\lambda_{\min}(\mathbf{A}) - \lambda_{\min}(\mathbf{B})| \le \|\mathbf{A} - \mathbf{B}\|_2. \quad (10) $$
From standard linear algebra, we recall the facts that any matrix $\mathbf{Q} \in S^{d \times d}$ is diagonalizable via a unitary transformation, and we use $\lambda(\mathbf{Q}) \in \mathbb{R}^d$ to denote its vector of eigenvalues, ordered as

$$ \lambda_{\max}(\mathbf{Q}) = \lambda_1(\mathbf{Q}) \ge \lambda_2(\mathbf{Q}) \ge \dots \ge \lambda_d(\mathbf{Q}) = \lambda_{\min}(\mathbf{Q}). $$

Note that a matrix $\mathbf{Q}$ is positive semidefinite-written $\mathbf{Q} \ge 0$ for short-if and only if $\lambda_{\min}(\mathbf{Q}) \ge 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

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

**Remark A.2.** For any symmetric matrix $\mathbf{Q}$, the $\ell_2$-operator norm can be written as

$$ \|\mathbf{Q}\|_2 = \max \{\lambda_{\max}(\mathbf{Q}), |\lambda_{\min}(\mathbf{Q})|\}, $$

by virtue of which it inherits the variational representation $\|\mathbf{Q}\|_2 = \max_{\mathbf{v} \in S^{d-1}} |\mathbf{v}^{\top} \mathbf{Q} \mathbf{v}|$.

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

$$ \lambda_j(\mathbf{R}) = (\sigma_j(\mathbf{A}))^2 \quad \text{for } j = 1, \dots, m $$

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

**Definition A.5.** For any vector $\mathbf{y} \in \mathbb{R}^n$ and matrix $\mathbf{A} \in S_{+}^{n \times n}$, let us define the norm $\|\mathbf{y}\|_{\mathbf{A}} \triangleq \sqrt{\mathbf{y}^{\top} \mathbf{A} \mathbf{y}} = \sqrt{\langle \mathbf{y}, \mathbf{A} \mathbf{y} \rangle}.$

Throughout the paper we will need often to bound matrix induced norms using $\ell_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 $\mathbf{A}, \mathbf{B} \in \mathbb{R}^{n \times n}$, with $\mathbf{B} \ge 0$ positive semi-definite and $\mathbf{x} \in \mathbb{R}^n$

$$ \|\mathbf{A}\mathbf{x}\|_{\mathbf{B}}^2 = \|\mathbf{x}\|_{\mathbf{A}^{\top}\mathbf{B}\mathbf{A}}^2 \le \|\mathbf{B}\|_2 \|\mathbf{A}\|_2^2 \|\mathbf{x}\|_2^2 \quad (9) $$

*Proof.* The equality holds since we can rewrite

$$ \|\mathbf{A}\mathbf{x}\|_{\mathbf{B}}^2 = \langle \mathbf{A}\mathbf{x}, \mathbf{B}\mathbf{A}\mathbf{x} \rangle = \langle \mathbf{x}, \mathbf{A}^{\top}\mathbf{B}\mathbf{A}\mathbf{x} \rangle = \|\mathbf{x}\|_{\mathbf{A}^{\top}\mathbf{B}\mathbf{A}}^2. $$

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

$$ \langle \mathbf{A}\mathbf{x}, \mathbf{B}\mathbf{A}\mathbf{x} \rangle = \frac{\langle \mathbf{A}\mathbf{x}, \mathbf{B}\mathbf{A}\mathbf{x} \rangle}{\|\mathbf{A}\mathbf{x}\|_2^2} \frac{\|\mathbf{A}\mathbf{x}\|_2^2}{\|\mathbf{x}\|_2^2} \|\mathbf{x}\|_2^2 = \frac{\langle \mathbf{y}, \mathbf{B}\mathbf{y} \rangle}{\|\mathbf{y}\|_2^2} \frac{\|\mathbf{A}\mathbf{x}\|_2^2}{\|\mathbf{x}\|_2^2} \|\mathbf{x}\|_2^2 \le \|\mathbf{B}\|_2 \|\mathbf{A}\|_2^2 \|\mathbf{x}\|_2^2. $$

We note that the inequality holds trivially for $\mathbf{x}$ in the null space of $\mathbf{A}$, therefore, in the previous case, we can safely divide by $\|\mathbf{A}\mathbf{x}\|_2$ and $\|\mathbf{x}\|_2$. $\square$
## A.2 Random variables and concentration bounds

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

**Definition A.10 (Sub-Gaussian r.v.)**. A random variable $X$ with mean $\mu = \mathbb{E}[X]$ is sub-Gaussian if there is a positive number $\sigma$ such that

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

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

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

**Lemma A.12 (Square and product of non-independent sub-Gaussian random variables).** Given two non-independent random variables $X \sim \text{sub-Gaussian}(\sigma_X)$ and $Y \sim \text{sub-Gaussian}(\sigma_Y)$, we have the following properties:

1. the squared random variable $X^2$ is sub-exp$(4\sqrt{2}\sigma^2, 4\sigma^2)$;

2. the recentered random variable $XY$ is sub-exp$(4\sqrt{2}(\sigma_X^2 + \sigma_Y^2), 2(\sigma_X^2 + \sigma_Y^2))$.

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

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

$$ \mathbb{E}[|X/\sigma_X\sqrt{2}|^p] = \int_0^\infty \mathbb{P}\{|X/\sigma_X\sqrt{2}|^p \ge u\} du \quad \text{(integral identity for positive r.v.)} $$

$$ = \frac{1}{\sqrt{2}\sigma_X} \int_0^\infty \mathbb{P}\{|X| \ge t\sqrt{2}\sigma_X\} pt^{p-1}dt \quad \text{(change of variable $u = t^p$)} $$

$$ \le \int_0^\infty 2e^{-t^2} pt^{p-1}dt \quad \text{(by $\sigma_X$-sub-Gaussianity)} $$

$$ = p\Gamma(p/2) \quad \text{(set $t^2 = s$ and use definition of Gamma function))} $$

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

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

$$ \mathbb{E}[e^{\lambda(W-\mu_W)}] = 1 + \lambda \mathbb{E}[W - \mu_W] + \sum_{r=2}^{\infty} \frac{\lambda^r \mathbb{E}[(W - \mu_W)^r]}{r!} \le 1 + \sum_{r=2}^{\infty} \frac{\lambda^r \mathbb{E}[|X|^{2r}]}{r!} $$

$$ \le 1 + \sum_{r=2}^{\infty} \frac{\lambda^r 2r 2^r \sigma^{2r} \Gamma(r)}{r!} = 1 + \sum_{r=2}^{\infty} \lambda^r 2^{r+1} \sigma^{2r} = 1 + \frac{8\lambda^2 \sigma^4}{1 - 2\lambda\sigma^2} $$

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

$$ \mathbb{E}[e^{\lambda(X^2 - \mathbb{E}[X^2])}] \le e^{16\lambda^2\sigma^4} \quad \forall |\lambda| \le 1/(4\sigma^2). $$
## A.3 Technical Lemmas

**Lemma A.1 (Determinant-Trace Inequality).** Suppose $z_1, z_2, \dots, z_t \in \mathbb{R}^d$ and for any $1 \le s \le t$, $\|z_s\|_2 \le L_z$. Let $G_{z,t} = \lambda \mathbb{I} + \sum_{s=1}^t z_s z_s^\top$ for some $\lambda > 0$. Then,

$$ \det(G_{z,t}) \le (\lambda + tL_z^2/d)^d \quad (10) $$

*Proof.* Let $\alpha_1, \alpha_2, \dots, \alpha_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}) = \prod_{s=1}^d \alpha_s$ and $\mathrm{Tr}(G_{z,t}) = \sum_{s=1}^d \alpha_s$. By inequality of arithmetic and geometric means,

$$ \sqrt[d]{\alpha_1 \alpha_2 \cdots \alpha_d} \le \frac{\alpha_1 + \alpha_2 + \cdots + \alpha_d}{d}. $$

Therefore, $\det(G_{z,t}) \le (\mathrm{Tr}(G_{z,t})/d)^d$.

Now, it remains to upper bound the trace:

$$ \mathrm{Tr}(G_{z,t}) = \mathrm{Tr}(\lambda \mathbb{I}_d) + \sum_{s=1}^{t} \mathrm{Tr}(z_s z_s^\top) = d\lambda + \sum_{s=1}^{t} \|z_s\|_2^2 \le d\lambda + tL_z^2 $$

and the lemma follows. $\square$

<figure><img src="image_4.png" /></figure>
To prove the second point we define $Z_1 \triangleq (\frac{X-Y}{2})^2 - \mathbb{E}[(\frac{X-Y}{2})^2]$ and $Z_2 \triangleq (\frac{X+Y}{2})^2 - \mathbb{E}[(\frac{X+Y}{2})^2]$, then $XY - \mathbb{E}[XY] = Z_1 - Z_2$. We take care of the dependence between X and Y using Cauchy-Schwarz inequality instead of the product rule for expectations of independent random variables:

$$ \mathbb{E}[e^{\lambda(X+Y)}] \le \sqrt{\mathbb{E}[e^{2\lambda X}]} \sqrt{\mathbb{E}[e^{2\lambda Y}]} \le \sqrt{e^{\frac{4\lambda^2\sigma_X^2}{2}}} \sqrt{e^{\frac{4\lambda^2\sigma_Y^2}{2}}} = e^{\frac{\lambda^2}{2}[2(\sigma_X^2+\sigma_Y^2)]} $$

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

$$ \mathbb{E}[e^{\lambda(XY - E[XY])}] = \mathbb{E}[e^{\lambda(Z_1 - Z_2)}] \le \sqrt{\mathbb{E}[e^{2\lambda Z_1}] \mathbb{E}[e^{-2\lambda Z_2}]} \le e^{\frac{4\lambda^2}{2} 8(\sigma_X^2 + \sigma_Y^2)^2} $$

which holds for $\lambda \le 1/2(\sigma_X^2+\sigma_Y^2)$. This proves that the sub-exponential parameters are indeed $\nu = 4\sqrt{2}(\sigma_X^2 + \sigma_Y^2)$ and $\alpha = 2(\sigma_X^2 + \sigma_Y^2)$. $\square$

The following are known concentration results, see [Wainwright, 2019].

**Theorem A.13 (Concentration of martingale difference sequences).** Let $\{(D_k, \mathcal{F}_k)\}_{k=1}^\infty$ be a martingale difference sequence, and suppose that $\mathbb{E}[e^{\lambda D_k} | \mathcal{F}_{k-1}] \le e^{\lambda^2 \nu_k^2/2}$ almost surely for any $|\lambda| < 1/\alpha_k$. Then the following hold:

1. the sum $\sum_{k=1}^n D_k$ is sub-exponential($\sqrt{\sum_{k=1}^n \nu_k^2}, \alpha_*$) where $\alpha_* \triangleq \max_{k=1,...,n} \alpha_k$;

2. the sum satisfies the concentration inequality

$$ \mathbb{P}\left[\left|\sum_{k=1}^{n} D_k\right| \ge t\right] \le \begin{cases} 2e^{-\frac{r^2}{2\sum_{k=1}^{n} \nu_k^2}} & \text{if } 0 \le t \le \frac{\sum_{k=1}^{n} \nu_k^2}{\alpha_*} \\ 2e^{-\frac{1}{2\alpha_*}} & \text{if } t > \frac{\sum_{k=1}^{n} \nu_k^2}{\alpha_*} \end{cases}. $$

**Theorem A.14 (Estimation of covariance matrices).** Let $z_1, \dots, z_t$ be i.i.d. zero-mean random vectors with covariance $\Sigma$ such that $\|z_s\|_2 \le L_z$ almost surely. Then for all $\delta > 0$, the sample covariance matrix $\hat{\Sigma}_t = \frac{1}{t} \sum_{s=1}^t z_s z_s^\top$ satisfies

$$ \mathbb{P}\left[\left\|\hat{\Sigma}_t - \Sigma\right\|_2 \ge \delta\right] \le 2d \exp\left(-\frac{t\delta^2}{(2L_z^2 \|\Sigma\|_2 + \delta)}\right), $$

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

$$ \left\|\hat{\Sigma}_t - \Sigma\right\|_2 \le \frac{4L_z^2}{t} \log\left(\frac{2d}{\delta}\right) + 2\sqrt{\frac{2L_z^2}{t} \log\left(\frac{2d_z}{\delta}\right) \|\Sigma\|_2}. $$

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

**Theorem A.15 (Self-Normalised Bound for Vector-Valued Martingales).** Let $\{\mathcal{F}_t\}_{t=0}^\infty$ be a filtration. Let $\{\eta_t\}_{t=1}^\infty$ be a real-valued stochastic process such that $\eta_t$ is $\mathcal{F}_t$-measurable and $\eta_t$ is conditionally $\sigma_\eta$-sub-Gaussian for some $\sigma_\eta \ge 0$ i.e. $\forall \lambda \in \mathbb{R}$ holds $\mathbb{E}[e^{\lambda \eta_t} | \mathcal{F}_{t-1}] \le \exp(\lambda^2 \sigma_\eta^2/2)$. Let $\{z_t\}_{t=1}^\infty$ be an $\mathbb{R}^d$-valued stochastic process such that $z_t$ is $\mathcal{F}_{t-1}$-measurable. For any $t \ge 0$, define $v_t = \sum_{s=1}^t \eta_s z_s$. Then, for any $\delta > 0$, with probability at least $1 - \delta$, for all $t \ge 0$,

$$ \|v_t\|_{\mathbf{G}_{z,t}^{-1}} \le \sqrt{2\sigma_{\eta}^2 \log\left(\frac{\det(\mathbf{G}_{z,t})^{1/2} \lambda^{-d/2}}{\delta}\right)} \le \sqrt{2d_z \sigma_{\eta}^2 \log\left(\frac{1 + tL_z^2/d_z\lambda}{\delta}\right)} $$
## 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 $l_2$-norm of the inverse of the design matrix $||G_{z,t}^{-1}||_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)).

**Lemma B.1.** For two symmetric matrices A and B

$$|\lambda_{\min}(A) - \lambda_{\min}(B)| \le ||A - B||_2. \quad (11)$$

The following, is a classical concentration result for the covariance matrix using the $l_2$-norm for matrices, for a proof of this result we refer the reader to Corollary 6.20 in (Wainwright, 2019).

**Theorem B.1 (Estimation of covariance matrices).** Let $z_1, \dots, z_t$ be i.i.d. zero-mean random vectors with covariance $\Sigma$ such that $||z_s||_2 \le L_z$ almost surely. Then for all $\delta > 0$, the sample covariance matrix $\hat{\Sigma}_t = \frac{1}{t} \sum_{s=1}^t z_s z_s^\top$ satisfies

$$\mathbb{P}\left[\left\|\hat{\Sigma}_t - \Sigma\right\|_2 \ge \delta\right] \le 2d \exp\left(-\frac{t\delta^2}{(2L_z^2 \|\Sigma\|_2 + \delta)}\right),$$

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

$$\left\|\hat{\Sigma}_t - \Sigma\right\|_2 \le \frac{4L_z^2}{t} \log\left(\frac{2d}{\delta}\right) + 2\sqrt{\frac{2L_z^2}{t} \log\left(\frac{2d}{\delta}\right) \|\Sigma\|_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, \dots, z_t$ be i.i.d. zero-mean random vectors with covariance $\Sigma$ such that $||z_s||_2 \le L_z$ almost surely. We denote the regularized design matrix as $G_{z,t} = \lambda I_d + \sum_{s=1}^t z_s z_s^\top$. For all $\delta > 0$ and regularization parameter $\lambda > 0$, we observe that

$$\|G_{z,t}^{-1}\|_2 = \lambda_{\max}(G_{z,t}^{-1}) \le \begin{cases} \frac{1}{\lambda} & \text{if } t \le C_3 \\ \frac{2}{t \lambda_{\min}(\Sigma)} & \text{if } t > C_3 \end{cases}.$$

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

*Proof.* First, we aim to find a lower bound for the smallest eigenvalue of the design, matrix where we set the regularization parameter $\lambda$ to zero. We denote the ‘non-regularized’ design matrix as $G_{z,t}^{\lambda=0}$. For $t \ge 1$, we observe that $G_{z,t}^{\lambda=0}/t \triangleq \hat{\Sigma}_t$. Thus, by applying Equation (11), we obtain

$$|\lambda_{\min}(G_{z,t}^{\lambda=0}/t) - \lambda_{\min}(\Sigma)| \le \frac{4L_z^2}{t} \log\left(\frac{2d}{\delta}\right) + 2\sqrt{\frac{2L_z^2}{t} \log\left(\frac{2d}{\delta}\right) \|\Sigma\|_2}.$$

Further substituting $A \triangleq 2L_z^2 \log(2d/\delta)$ leads to the following lower bound for the minimum eigenvalue

$$\lambda_{\min}(G_{z,t}^{\lambda=0}) \ge \max\left\{0, t\left(\lambda_{\min}(\Sigma) - 2A/t - 2\sqrt{A\lambda_{\max}(\Sigma)/t}\right)\right\}.$$
**Theorem A.16** (Self-normalised Bound for Scalar Valued Martingales). Under the same assumptions as the previous theorem, let {$\mathcal{F}_t$}$_{t=0}^\infty$ be a filtration. Let {$\eta_t$}$_{t=1}^\infty$ be a real-valued stochastic process such that $\eta_t$ is $\mathcal{F}_t$-measurable and $\eta_t$ is conditionally $\sigma_\eta$-sub-Gaussian for some $\sigma_\eta \ge 0$ i.e. $\forall \lambda \in \mathbb{R}$ holds $\mathbb{E}[e^{\lambda \eta_t} | \mathcal{F}_{t-1}] \le \exp(\lambda^2 \sigma_\eta^2/2)$. Let {$w_t$}$_{t=1}^\infty$ be a scalar-valued stochastic process such that $w_t$ is $\mathcal{F}_{t-1}$-measurable. Then, for any $\delta > 0$, with probability at least $1 - \delta$, for all $t \ge 0$,

$$ \left| \sum_{s=1}^{t} \eta_t w_t \right| \le \sigma_{\eta} \sqrt{2 \left( 1/\sigma_{\eta}^2 + \sum_{s=1}^{t} w_s \right) \log \left( \frac{\sqrt{1 + \sigma_{\eta}^2 \sum_{s=1}^{t} w_s^2}}{\delta} \right)} \quad (11) $$
Here, $\lambda_{\max}(\Sigma)$ and $\lambda_{\min}(\Sigma)$ is the maximum and minimum eigenvalues of the true covariance matrix of $z$, i.e. $\Sigma \triangleq \mathbb{E}[zz^\top]$. 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

$$\lambda_{\min}(\mathbf{G}_{z,t}) \geq \lambda_{\min}(\mathbf{G}_{z,t}^{\lambda=0}) + \lambda,$$

which implies that $\lambda_{\min}(\mathbf{G}_{z,t}) \geq \lambda$ for all $t \geq 0$, with equality for $t = 0$. Thus, we have

$$\lambda_{\min}(\mathbf{G}_{z,t}) \geq \max\{\lambda, \lambda + t(\lambda_{\min}(\Sigma) - 2A/t - 2\sqrt{A\lambda_{\max}(\Sigma)/t})\}. \quad (12)$$

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

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

Now we study for which values Term (B) is non-negative. The corresponding second order polynomial equation is obtained substituting $u = \sqrt{t}$, and reads

$$u^2 \lambda_{\min}(\Sigma) - 4u\sqrt{A \lambda_{\max}(\Sigma)} + 2(\lambda - 2A) = 0,$$

which has two solutions given by

$$u_{\pm} = \frac{2\sqrt{A \lambda_{\max}(\Sigma)} \pm \sqrt{4A \lambda_{\max}(\Sigma) + 2(2A - \lambda) \lambda_{\min}(\Sigma)}}{\lambda_{\min}(\Sigma)}.$$

In particular for $t > \lceil u_+ \rceil$, Term (A) $\geq 0$, and Equation (12) reads

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

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

Putting the results together, we conclude that

$$\lambda_{\min}(\mathbf{G}_{z,t}) \geq t \lambda_{\min}(\Sigma)/2 \quad \text{for } t > C_3 \triangleq \max\{\lceil 2\lambda/\lambda_{\min}(\Sigma) \rceil, \lceil u_+ \rceil\}, \quad (13)$$

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

In summary, we have

$$\lambda_{\min}(\mathbf{G}_{z,t}) \geq \begin{cases} \lambda & \text{if } t \leq C_3 \\ t \lambda_{\min}(\Sigma)/2 & \text{if } t > C_3 \end{cases} \iff \lambda_{\max}(\mathbf{G}_{z,t}^{-1}) \leq \begin{cases} \frac{1}{\lambda} & \text{if } t \leq C_3 \\ \frac{2}{t \lambda_{\min}(\Sigma)} & \text{if } t > C_3 \end{cases}.$$

□
# B Regret analysis of O2SLS

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

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

## B.1 A primer on just-identified and over-identified IVs and 2SLS

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

$$y_s = \beta^\top x_s + \eta_s,$$

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

$$X_t = Z_t \Theta + E_t,$$

where $\Theta \in \mathbb{R}^{d_z \times d_x}$ is an unknown first-stage parameter matrix and $E_t \triangleq [\epsilon_1, \dots, \epsilon_t]^\top$ is the unobserved noise matrix leading to confounding in the second stage. The most common IV specification uses the following estimator:

$$\hat{\beta}_{\text{IV},t} \triangleq (\mathbf{Z}_t^\top \mathbf{X}_t)^{-1} \mathbf{Z}_t^\top \mathbf{y}_t. \qquad (\text{IV})$$

As long as $\mathbb{E}[z_i \eta_i] = 0$ in the true model, $\hat{\beta}_{\text{IV},t} = (\mathbf{Z}_t^\top \mathbf{X}_t)^{-1} \mathbf{Z}_t^\top \mathbf{X}_t \beta + (\mathbf{Z}_t^\top \mathbf{X}_t)^{-1} \mathbf{Z}_t^\top \eta_t \xrightarrow{p} \beta$, as $t \to \infty$. This works because IV solves for the unique parameter that satisfies $\frac{1}{n} \mathbf{Z}_t^\top \eta_t \xrightarrow{p} 0$. Since $x$ and $\eta$ are correlated, IV estimator is not unbiased in finite-time.

Relevance condition for IVs ensures this. It basically means that **IVs and covariates must have some correlation**, and thus, IVs explain some of the variance observed in the endogenous covariates $x_t$ [Hernan and Robins, 2020, Chapter 16]. Since we are interested in finite time guarantees, we assume “positive-definite covariance" between IVs and covariates at any finite time.

Specifically, we use the following form of the relevance condition:

$$\sigma_{\min}(\operatorname{Cov}(\mathbf{Z}_t, \mathbf{X}_t)) = \sigma_{\min}\left(\frac{1}{t}\sum_{s=1}^{t} z_s x_s^\top\right) \geq \mathbf{r} > 0, \quad \forall t \in \mathbb{N}. \qquad (12)$$
## 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 $\Theta$ (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; (Ouhamma et al., 2021)), we assume that each component of the first stage noise, i.e. $\epsilon_{t,i}$, corresponding to the i-th ridge regression is sub-Gauss($\sigma_{\epsilon}$). Thus, we obtain that $E\|\epsilon_t\|_2^2 \le d\sigma_{\epsilon}^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 $\lambda > 0$, we have the following upper bound for the inverse of the estimated parameter (Equation (27)) in the first-stage regression:

$$ \|\hat{\Theta}_t^{-1}\|_2 \le \frac{\lambda + L_z^2}{\mathbf{r}} \triangleq L_{\hat{\Theta}}^{-1} \quad (14) $$

*Proof.* By the sub-multiplicativity of the matrix norms we have

$$ \|\hat{\Theta}_t^{-1}\|_2 = \|(Z_t^\top X_t)^{-1} (Z_t^\top Z_t + \lambda \mathbf{I})\|_2 \le \|(Z_t^\top X_t)^{-1}\|_2 \|Z_t^\top Z_t + \lambda \mathbf{I}\|_2 $$

Then, by the sub-additivity of the norms and the variational definition of the biggest eigenvalue

$$ \begin{aligned} \|Z_t^\top Z_t + \lambda \mathbf{I}\|_2 &\le \|Z_t^\top Z_t\|_2 + \|\lambda \mathbf{I}\|_2 \le \max_{v \in \mathbb{S}^{d-1}} \left\langle v, \sum_{s=1}^t z_s z_s^\top v \right\rangle + \lambda \\ &= \max_{v \in \mathbb{S}^{d-1}} \sum_{s=1}^t \langle v, z_s \rangle^2 + \lambda \le \sum_{s=1}^t \|z_s\|_2^2 + \lambda \\ &\le t L_z^2 + \lambda \end{aligned} $$

Then, we note that the quantity $\|(Z_t^\top X_t)^{-1}\|_2 \le \frac{1}{t\mathbf{r}}$ by the definition of relevance, which implies

$$ \|\hat{\Theta}_t^{-1}\|_2 \le \frac{tL_z^2 + \lambda}{\mathbf{r}} = \frac{L_z^2 + \lambda/t}{\mathbf{r}} \le \frac{L_z^2 + \lambda}{\mathbf{r}} \quad (15) $$

□

**Lemma C.2** (Bounding the Impact of First-stage Noise). For first stage noises that is component-wise sub-Gaussian($\sigma_{\epsilon}$), and first-stage parameter estimates satisfying $\|\hat{\Theta}_t^{-1}\|_2 \le L_{\hat{\Theta}}^{-1}$ (Lemma C.1), we have that

$$ \sum_{t=1}^{T} \|\epsilon_t\|_{\hat{\Theta}_{t-1}^{-1} G_{z,t-1}^{-1} \hat{\Theta}_{t-1}^{-1}}^2 \le \underbrace{d\sigma_{\epsilon}^2 L_{\hat{\Theta}}^{-1} \left( \frac{C_3+1}{\lambda} + 2 \frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right)}_{\mathcal{O}(d \log T)} + C_4 $$

with probability at least $1 - \delta$ and with $C_4$ a constant defined in Equation (17).
Remark B.1 (Requirement of the relevance condition). Here, we discuss different perspectives and results justifying the use of the relevance condition in the online IV regression setting like its offline counterpart.

1) Causality perspective: Relevance is one of the three strictly necessary conditions for the existence of IVs even in offline IV-regression [Greene, 2003, Hernan and Robins, 2020]. Without relevance, IV regressor is not defined. For linear case, [Martens et al.’06, Epidemiology] show that relevance exists for IVs causally associated with covariates.

2) Experimental grounding: We confirm that this assumption is good and realistic. Because our regression analysis and the bandit algorithm’s design are based on this assumption, and in both settings, our algorithms outperform the natural baselines (plus the one-stage reduction in fig) while not needing to know the exact amount of relevance.

3) Expressing relevance: [Greene, 2003] states that the relevance condition can also be written as a condition of rank maximality for covariance matrices, which we express as the minimum singular value being bounded away from zero a.s.

**Over-identified case** [$d_x < d_z$]: Suppose that there are more instruments than there are covariates in the equation of interest, so that $Z_t$ is a $t \times d_z$ matrix with $d_z > d_x$. This is often called the over-identified case. In this case, the generalised method of moments (GMM) can be used. The GMM IV estimator is

$$ \beta_{\text{GMM},t} \triangleq (\mathbf{X}_t^\top \mathbf{P}_{t,Z_t} \mathbf{X}_t)^{-1} \mathbf{X}_t^\top \mathbf{P}_{t,Z_t} \mathbf{y}_t, \quad (\text{GMM IV}) $$

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

**Assumption B.2** (Well-behaved IVs). For any $t > 0$, the matrix $\mathbf{Z}_t^\top \mathbf{Z}_t$ is full rank with $\lambda_{\min}(\mathbf{G}_{z,0}) \triangleq \lambda_0 > 0$.

**Proposition B.3.** If $d_x = d_z$, i.e. in the just-identified case, $\beta_{\text{GMM},t}$ reduces to $\beta_{\text{IV},t}$.

*Proof.* Expanding the $\beta_{\text{GMM}}$ expression:

$$ \beta_{\text{GMM},t} = (\mathbf{X}_t^\top \mathbf{Z}_t (\mathbf{Z}_t^\top \mathbf{Z}_t)^{-1} \mathbf{Z}_t^\top \mathbf{X}_t)^{-1} \mathbf{X}_t^\top \mathbf{Z}_t (\mathbf{Z}_t^\top \mathbf{Z}_t)^{-1} \mathbf{Z}_t^\top \mathbf{y}_t $$

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

$$ \begin{aligned} \beta_{\text{GMM},t} &= (\mathbf{Z}_t^\top \mathbf{X}_t)^{-1} (\mathbf{Z}_t^\top \mathbf{Z}_t) (\mathbf{X}_t^\top \mathbf{Z}_t)^{-1} \mathbf{X}_t^\top \mathbf{Z}_t (\mathbf{Z}_t^\top \mathbf{Z}_t)^{-1} \mathbf{Z}_t^\top \mathbf{y}_t \\ &= (\mathbf{Z}_t^\top \mathbf{X}_t)^{-1} (\mathbf{Z}_t^\top \mathbf{Z}_t) (\mathbf{Z}_t^\top \mathbf{Z}_t)^{-1} \mathbf{Z}_t^\top \mathbf{y}_t \\ &= (\mathbf{Z}_t^\top \mathbf{X}_t)^{-1} \mathbf{Z}_t^\top \mathbf{y}_t \\ &= \beta_{\text{IV},t} \end{aligned} $$

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

$$
\begin{align*}
\sum_{t=1}^{T} \|\epsilon_t\|^2_{\hat{\Theta}_{t-1}^{-1} \mathbf{G}_{z,t-1}^{-1} \hat{\Theta}_{t-1}^{-\mathrm{T}}} &\le \sum_{t=1}^{T} \|\mathbf{G}_{z,t-1}^{-1}\|_2 \|\hat{\Theta}_{t-1}^{-1}\|_2^2 \|\epsilon_t\|_2^2 \\
&\le L_{\hat{\Theta}^{-1}}^2 \sum_{t=1}^{T} \|\mathbf{G}_{z,t-1}^{-1}\|_2 \left( \left( \|\epsilon_t\|_2^2 - \mathbb{E}\|\epsilon_t\|_2^2 \right) + \mathbb{E}\|\epsilon_t\|_2^2 \right) \\
&\le L_{\hat{\Theta}^{-1}}^2 \underbrace{\sum_{t=1}^{T} \|\mathbf{G}_{z,t-1}^{-1}\|_2 \left( \|\epsilon_t\|_2^2 - \mathbb{E}\|\epsilon_t\|_2^2 \right)}_{\mathrm{II}} + L_{\hat{\Theta}^{-1}}^2 \sum_{t=1}^{T} \|\mathbf{G}_{z,t-1}^{-1}\|_2 \mathbb{E}\|\epsilon_t\|_2^2
\end{align*}
$$

**Term I:** We now assume $\|\epsilon_t\|_2^2 - \mathbb{E}\|\epsilon_t\|_2^2 \sim \text{sub-exp}(\nu, \alpha)$ where the correct values of $\nu, \alpha$ can simply be taken from the results on the square of sub-Gaussians and gives that $\nu \triangleq d_4\sqrt{2\sigma_{\epsilon}^2}$ and $\alpha \triangleq 4\sigma_{\epsilon}^2$.

Now, given an $X \sim \text{sub-exp}(\nu, \alpha)$, we have that its rescaling by a constant $c$ is distributed according to $\frac{X}{c} \sim \text{sub-exp}(\frac{\nu}{c}, \frac{c}{\alpha})$ which follows by substituting $\lambda \to \lambda/c$ into the definitions

$$ \mathbb{E}[e^{\lambda X/c}] \le e^{\lambda^2 \nu^2 / 2c^2}, \quad \forall |\lambda/c| \le \frac{1}{\alpha} \Leftrightarrow |\lambda| \le \frac{c}{\alpha} $$

Using this, we can rescale by the factor $t$ in the following

$$ \mathbb{P}\left[\sum_{t=m}^{n} \frac{\|\epsilon_t\|_2^2 - \mathbb{E}\|\epsilon_t\|_2^2}{t} \ge \mu\right] \le \mathbb{E}\left[e^{\lambda \sum_{t=m}^{n} \frac{\|\epsilon_t\|^2 - \mathbb{E}\|\epsilon_t\|^2}{t}}\right] e^{-\lambda \mu} \le e^{\lambda \sum_{t=m}^{n} \frac{\lambda^2 \nu^2}{2t^2} - \lambda \mu} \le e^{\frac{\lambda^2 \nu^2}{2} \left(\frac{1}{m-1} - \frac{1}{n}\right) - \lambda \mu} $$

which holds $\forall |\lambda| \le \frac{m}{\alpha}$ thanks to the following series of inequalities $\sum_{m}^{n} \frac{1}{t^2} \le \int_{m-1}^{n} 1/t^2 dt = (-\frac{1}{t}|_{m-1}^{n}| = -\frac{1}{n} + \frac{1}{m-1}$. This proves that

$$ \sum_{t=C_3}^{T} \frac{\|\epsilon_t\|_2^2 - \mathbb{E}\|\epsilon_t\|_2^2}{t} \sim \text{sub-exp} \left( \nu \sqrt{\frac{1}{C_3-1} - \frac{1}{T}}, \frac{C_3}{\alpha} \right) \quad (16) $$

We bound the following summation using Lemma B.2:

$$
\begin{align*}
\sum_{t=1}^{T} \|\mathbf{G}_{z,t-1}^{-1}\|_2 \left( \|\epsilon_t\|_2^2 - \mathbb{E}\|\epsilon_t\|_2^2 \right) & \\
&= \sum_{t=0}^{C_3} \lambda_{\max}(\mathbf{G}_{z,t}^{-1}) \left( \|\epsilon_{t+1}\|_2^2 - \mathbb{E}\|\epsilon_{t+1}\|_2^2 \right) + \sum_{t=C_3+1}^{T-1} \lambda_{\max}(\mathbf{G}_{z,t}^{-1}) \left( \|\epsilon_{t+1}\|_2^2 - \mathbb{E}\|\epsilon_{t+1}\|_2^2 \right) \\
&\le \frac{1}{\lambda} \sum_{t=0}^{C_3} \left( \|\epsilon_{t+1}\|_2^2 - \mathbb{E}\|\epsilon_{t+1}\|_2^2 \right) + \frac{2}{\lambda_{\min}(\mathbf{\Sigma})} \sum_{t=C_3+1}^{T-1} \frac{\|\epsilon_{t+1}\|_2^2 - \mathbb{E}\|\epsilon_{t+1}\|_2^2}{t} \\
&\le \frac{C_3+1}{\lambda} \left( d_4 \sqrt{2\sigma_{\epsilon}^2} \sqrt{2\log(1/\delta)} + \frac{1}{2\sigma_{\epsilon}^2} \log(1/\delta) \right) \\
&\quad + \frac{2}{\lambda_{\min}(\mathbf{\Sigma})} \left( \sqrt{2\nu^2} \left( \frac{1}{C_3} - \frac{1}{T} \right) \log(1/\delta) + \frac{2C_3}{\alpha} \log(1/\delta) \right)
\end{align*}
$$

Since term I can be upperbounded by a constant $\mathcal{O}(1)$ we just name this constant $C_4$ where we also substitute back the definitions $\nu = d_4\sqrt{2\sigma_{\epsilon}^2}$ and $\alpha = 4\sigma_{\epsilon}^2$:

$$ C_4 \triangleq L_{\hat{\Theta}^{-1}}^2 \frac{C_3+1}{\lambda} \left( d_4 \sqrt{2\sigma_{\epsilon}^2} \sqrt{2\log(1/\delta)} + \frac{1}{2\sigma_{\epsilon}^2} \log(1/\delta) \right) $$
**Interpretation as two-stage least-squares.** One computational method which can be used to calculate IV estimates is two-stage least squares 2SLS. In the first stage, each explanatory variable that is an endogenous covariate in the equation of interest is regressed on all of the exogenous variables in the model, including both exogenous covariates in the equation of interest and the excluded instruments. The predicted values from these regressions are obtained. Then, in the second stage, the regression of interest is estimated as usual, except that in this stage each endogenous covariate is replaced with the predicted values from the first stage.

**Proposition B.4.** For $d_x \le d_z$, i.e. in both just- and over-identified cases, $\beta_{GMM,t} = \beta_{2SLS,t}$.

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

*Stage 1:* Regressing each column of $X_t$ on $Z_t$ with a regularisation parameter $\lambda$, in the first stage

$$X_t = Z_t \Theta + E_t$$

yields

$$\hat{\Theta}_t \triangleq (Z_t^\top Z_t + G_{z,0})^{-1} Z_t^\top X_t \quad (13)$$

and save the predicted values:

$$\hat{X}_t \triangleq Z_t \hat{\Theta}_t = Z_t (Z_t^\top Z_t + G_{z,0})^{-1} Z_t^\top X_t \triangleq P_{t,z_t} X_t.$$

*Stage 2:* Regress $y_t$ on the predicted values from the first stage:

$$y_t = \hat{X}_t \beta + \eta_t$$

which gives:

$$\beta_{2SLS,t} = (\hat{X}_t^\top \hat{X}_t)^{-1} \hat{X}_t^\top y_t = (X_t^\top P_{t,z_t} X_t)^{-1} X_t^\top P_{t,z_t} y_t$$

where the second equality follows from the fact that the usual OLS estimator is: $(\hat{X}_t^\top \hat{X}_t)^{-1} \hat{X}_t^\top y_t$, and replacing $\hat{X}_t = P_{t,z_t} X_t$ and noting that $P_{t,z_t}$ is a symmetric and idempotent matrix, so that $P_{t,z_t} P_{t,z_t} = P_{t,z_t} P_{t,z_t} = P_{t,z_t}$ we have

$$\begin{align*}
\beta_{2SLS,t} &= (\hat{X}_t^\top \hat{X}_t)^{-1} \hat{X}_t^\top y_t = (X_t^\top P_{t,z_t}^\top P_{t,z_t} X_t)^{-1} X_t^\top P_{t,z_t}^\top y_t \\
&= (X_t^\top P_{t,z_t} X_t)^{-1} X_t^\top P_{t,z_t} y_t \\
&= \beta_{GMM,t}
\end{align*}$$

□

For brevity, in the proofs hereafter, we denote an O2SLS estimate at time $t$, i.e. $\beta_{2SLS,t}$ as $\beta_t$.
$$ + \frac{2L_{\hat{\Theta}^{-1}}^2}{\lambda_{\min}(\Sigma)} \left( d4\sqrt{2}\sigma_{\epsilon}^2 \sqrt{\frac{2}{C_3}\log(1/\delta)} + \frac{2C_3}{4\sigma_{\epsilon}^2}\log(1/\delta) \right) \quad (17) $$

**Term II:** The proof follows using the high probability bound that we introduce in Lemma B.2, plus the estimate $\sum_{k=1}^n \frac{1}{k} < \log(n) + 1$:

$$ \begin{aligned} d\sigma_{\epsilon}^2 L_{\hat{\Theta}^{-1}}^2 \sum_{t=1}^T \lambda_{\max}(G_{z,t-1}^{-1}) &\le dL_{\epsilon}^2 L_{\hat{\Theta}^{-1}}^2 \left( \sum_{t=0}^{C_3} \frac{1}{\lambda} + \sum_{t=C_3+1}^{T-1} \frac{2}{\lambda_{\min}(\Sigma)t} \right) \\ &\le dL_{\epsilon}^2 L_{\hat{\Theta}^{-1}}^2 \left( \frac{C_3+1}{\lambda} + 2\frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right). \end{aligned} $$

Therefore, putting **Term I** and **Term II** together, we obtain

$$ \sum_{t=1}^{T} \|\epsilon_t\|_{\hat{\Theta}_{t-1}^{-1} G_{z,t-1}^{-1} \hat{\Theta}_{t-1}^{-\top}}^2 \le \underbrace{d\sigma_{\epsilon}^2 L_{\hat{\Theta}^{-1}}^2 \left( \frac{C_3+1}{\lambda} + 2\frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right)}_{\mathcal{O}(d \log T)} + C_4 $$

□

**Lemma C.3 (Bounding the Sum of Feature Norms).** Under the same conditions of Lemma C.2 plus first-stage parameters with bounded $l_2$-norm $\|\Theta\|_2 \le L_{\Theta}$ and bounded IVs $\|z\|^2 \le L_z^2$ we have that

$$ \sum_{t=1}^{T} \|x_t\|_{\hat{\Theta}_{t-1}^{-1} G_{z,t-1}^{-1} \hat{\Theta}_{t-1}^{-\top}}^2 \le \underbrace{L_{\hat{\Theta}^{-1}}^2 (L_{\hat{\Theta}}^2 L_z^2 + d\sigma_{\epsilon}^2) \left( \frac{C_3+1}{\lambda} + 2\frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right)}_{\mathcal{O}(d \log T)} + C_4 $$

*Proof.* We start by substituting the First Stage equations inside the norm and using a Triangle Inequality

$$ \begin{aligned} \sum_{t=1}^{T} \|x_t\|_{\hat{\Theta}_{t-1}^{-1} G_{z,t-1}^{-1} \hat{\Theta}_{t-1}^{-\top}}^2 &= \sum_{t=1}^{T} \|\Theta^{\top} z_t + \epsilon_t\|_{\hat{\Theta}_{t-1}^{-1} G_{z,t-1}^{-1} \hat{\Theta}_{t-1}^{-\top}}^2 \\ &\le \sum_{t=1}^{T} \|\Theta^{\top} z_t\|_{\hat{\Theta}_{t-1}^{-1} G_{z,t-1}^{-1} \hat{\Theta}_{t-1}^{-\top}}^2 + \sum_{t=1}^{T} \|\epsilon_t\|_{\hat{\Theta}_{t-1}^{-1} G_{z,t-1}^{-1} \hat{\Theta}_{t-1}^{-\top}}^2 \\ &\le L_{\hat{\Theta}^{-1}}^2 (L_{\hat{\Theta}}^2 L_z^2 + d\sigma_{\epsilon}^2) \left( \frac{C_3+1}{\lambda} + 2\frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right) + C_4 \end{aligned} $$

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

$$ \begin{aligned} \sum_{t=1}^{T} \|\Theta^{\top} z_t\|_{\hat{\Theta}_{t-1}^{-1} G_{z,t-1}^{-1} \hat{\Theta}_{t-1}^{-\top}}^2 &\le L_{\hat{\Theta}}^2 L_z^2 L_{\hat{\Theta}^{-1}}^2 \sum_{t=1}^{T} \lambda_{\max}(G_{z,t-1}^{-1}) \\ &\le L_{\hat{\Theta}}^2 L_z^2 L_{\hat{\Theta}^{-1}}^2 \left( \sum_{t=0}^{C_3} \frac{1}{\lambda} + \sum_{t=C_3+1}^{T-1} \frac{2}{\lambda_{\min}(\Sigma)t} \right) \\ &\le L_{\hat{\Theta}}^2 L_z^2 L_{\hat{\Theta}^{-1}}^2 \left( \frac{C_3+1}{\lambda} + 2\frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right). \end{aligned} $$

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

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

$$L_t(\Theta') = \lambda \operatorname{Tr}(\Theta^{\top}\Theta') + \sum_{s=1}^{t} \operatorname{Tr}\left(\left(x_s - \Theta^{\top}z_s\right)\left(x_s - \Theta^{\top}\Theta z_s\right)^{\top}\right).$$

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

$$\hat{\Theta}_t = \underset{\Theta'}{\operatorname{argmin}} L_t(\Theta') = G_{z,t}^{-1} Z_t^\top X_t, \quad (14)$$

$$\text{where } G_{z,t} \triangleq G_{z,0} + \sum_{s=1}^{t} z_s z_s^\top = \lambda I_{d_z} + \sum_{s=1}^{t} z_s z_s^\top.$$

**Theorem B.5 (Confidence ellipsoid for columns in first-stage).** Consider the $\ell^2$-regularized least-squares parameter estimate $\hat{\Theta}_t$ with regularization coefficient $\lambda > 0$. Let $G_{z,t} = \lambda I_{d_z} + \sum_{s=1}^t z_s z_s^\top$ be the regularized design matrix of the IVs and $\operatorname{Tr}(\Theta^\top\Theta) \le S^2$. Define

$$\sqrt{\beta_t(\delta)} = d_x \sigma_{\epsilon} \sqrt{2 \log \left( \frac{\det(G_{z,t})^{1/2} \det(\lambda I_{d_z})^{-1/2}}{\delta} \right)} + \lambda^{1/2} S.$$

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

$$\operatorname{Tr}\left(\left(\hat{\Theta}_t - \Theta\right)^{\top} G_{z,t} \left(\hat{\Theta}_t - \Theta\right)\right) \le \beta_t(\delta).$$

In particular, $\mathbb{P}(\Theta \in C_t(\delta), t = 1, 2, \dots) \ge 1 - \delta$, where

$$C_t(\delta) = \left\{ \Theta \in \mathbb{R}^{d_z \times d_x} : \operatorname{Tr} \left( \left( \Theta - \hat{\Theta}_t \right)^{\top} G_{z,t} \left( \Theta - \hat{\Theta}_t \right) \right) \le \beta_t(\delta) \right\}.$$
## 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^\top Z_t + \lambda \mathbb{I}_d$ for some $\lambda > 0$ and $\hat{H}_t \triangleq \hat{\Theta}_t^\top G_{z,t} \hat{\Theta}_t$. Then, for $\sigma_\eta$-sub-Gaussian second stage noise $\eta_t$, the true parameter $\beta$ belongs to the set

$$ \mathcal{E}_t = \{ \beta \in \mathbb{R}^d : \|\beta_t - \beta\|_{\hat{H}_t} \le \sqrt{\mathfrak{b}_t(\delta)} \}, $$

with probability at least $1 - \delta \in (0, 1)$, for all $t \ge 0$. Here, $\mathfrak{b}_t(\delta) \triangleq \frac{d\sigma_\eta^2}{4}\log\left(\frac{1+tL_z^2/\lambda}{\delta}\right)$.

*Proof.* We can rewrite

$$ \beta_t - \beta = (Z_t^\top X_t)^{-1} Z_t^\top \eta_t = \hat{\Theta}_t^{-1} (Z_t^\top Z_t + \lambda \mathbb{I}_d)^{-1} Z_t^\top \eta_t = \hat{\Theta}_t^{-1} G_{z,t}^{-1} Z_t^\top \eta_t. $$

Take $x \in \mathbb{R}^d$ and by the Cauchy-Schwarz inequality we have

$$ \underbrace{x^\top \beta_t - x^\top \beta}_{(I)} = x^\top \hat{\Theta}_t^{-1} G_{z,t}^{-1} Z_t^\top \eta_t = \langle \hat{\Theta}_t^{-\top} x, G_{z,t}^{-1} Z_t^\top \eta_t \rangle \\ \le \| \hat{\Theta}_t^{-\top} x \|_{G_{z,t}^{-1}} \| G_{z,t}^{-1} Z_t^\top \eta_t \|_{G_{z,t}} = \underbrace{\| \hat{\Theta}_t^{-\top} x \|_{G_{z,t}^{-1}}}_{(II)} \underbrace{\| Z_t^\top \eta_t \|_{G_{z,t}^{-1}}}_{(III)}. $$

The choice we will make for $x$ is the following

$$ x \triangleq \hat{\Theta}_t^\top G_{z,t} \hat{\Theta}_t(\beta_t - \beta) = \hat{H}_t(\beta_t - \beta), \quad (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

$$ \begin{aligned} x^\top \beta_t - x^\top \beta &= \langle x, \beta_t - \beta \rangle = \langle \hat{\Theta}_t^\top G_{z,t} \hat{\Theta}_t(\beta_t - \beta), \beta_t - \beta \rangle \\ &= \|\beta_t - \beta\|_{\hat{\Theta}_t^\top G_{z,t} \hat{\Theta}_t}^2. \end{aligned} $$

**Term (II):** First, we rewrite the following term

$$ \begin{aligned} \| \hat{\Theta}_t^{-\top} x \|_{G_{z,t}^{-1}} &= \langle \hat{\Theta}_t^{-\top} x, \hat{\Theta}_t^{-\top} x \rangle_{G_{z,t}^{-1}} = x^\top \hat{\Theta}_t^{-1} G_{z,t}^{-1} \hat{\Theta}_t^{-\top} x = \|x\|_{\hat{\Theta}_t^{-1} G_{z,t}^{-1} \hat{\Theta}_t^{-\top}} \\ &= \|x\|_{(\hat{\Theta}_t^\top G_{z,t} \hat{\Theta}_t)^{-1}}, \end{aligned} $$

and, once again, we substitute the definition of $x$ in Equation (18):

$$ \begin{aligned} \|x\|_{(\hat{\Theta}_t^\top G_{z,t} \hat{\Theta}_t)^{-1}} &= \|\hat{\Theta}_t^\top G_{z,t} \hat{\Theta}_t(\beta_t - \beta)\|_{(\hat{\Theta}_t^\top G_{z,t} \hat{\Theta}_t)^{-1}} \\ &= \|\beta_t - \beta\|_{\hat{\Theta}_t^\top G_{z,t} \hat{\Theta}_t}. \end{aligned} $$

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

$$ \begin{aligned} \| Z_t^\top \eta_t \|_{G_{z,t}^{-1}} &= \left\| \sum_{s=1}^t \eta_s z_s \right\|_{G_{z,t}^{-1}} \le \sqrt{2(\sigma_\eta/2)^2 \log \left( \frac{\det(G_{z,t})^{1/2} \lambda^{-d/2}}{\delta} \right)} \\ &\le \sqrt{\frac{d\sigma_\eta^2}{4} \log \left( \frac{1+tL_z^2/\lambda}{\delta} \right)}. \end{aligned} $$
## B.3 Elliptical lemma for the second-stage in endogenous setting

**Lemma 3.3** (Second-stage confidence ellipsoid for endogenous setting). Given an O2SLS estimate $\beta_t$ at step $t > 0$, the true parameter $\beta$ with probability at least $1 - \delta$ belongs to

$$ \mathcal{E}_t = \{ \beta \in \mathbb{R}^{d_x} : \|\beta_t - \beta\|_{\hat{\mathbf{H}}_t} \le \sqrt{\mathfrak{b}_t(\delta)} \}, \quad (15) $$

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

$$ \mathfrak{b}_t(\delta) \triangleq 2d_z \sigma_{\eta}^2 \log \left( \frac{1 + tL_z^2/d_z\lambda}{\delta} \right). \quad (16) $$

*Proof.*

**Step 1:** First, we start by observing the O2SLS estimate of the second-stage parameter $\beta$:

$$ \begin{aligned} \beta_t &= \left( \mathbf{X}_t^\top \mathbf{Z}_t \left( \mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0} \right)^{-1} \mathbf{Z}_t^\top \mathbf{X}_t \right)^{-1} \mathbf{X}_t^\top \mathbf{Z}_t \left( \mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0} \right)^{-1} \mathbf{Z}_t^\top \mathbf{y}_t \\ &= \beta + \left( \mathbf{X}_t^\top \mathbf{Z}_t \left( \mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0} \right)^{-1} \mathbf{Z}_t^\top \mathbf{X}_t \right)^{-1} \mathbf{X}_t^\top \mathbf{Z}_t \left( \mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0} \right)^{-1} \mathbf{Z}_t^\top \mathbf{\eta}_t \end{aligned} $$

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

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

$$ \begin{aligned} \mathbf{x}^\top (\beta_t - \beta) &= \mathbf{x}^\top \left( \mathbf{X}_t^\top \mathbf{Z}_t \left( \mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0} \right)^{-1} \mathbf{Z}_t^\top \mathbf{X}_t \right)^{-1} \left( \mathbf{X}_t^\top \mathbf{Z}_t \right) \left( \mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0} \right)^{-1} \mathbf{Z}_t^\top \mathbf{\eta}_t \\ &= \mathbf{x}^\top \left( \hat{\mathbf{\Theta}}_t^\top \left( \mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0} \right)^\top \left( \mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0} \right)^{-1} \left( \mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0} \right) \hat{\mathbf{\Theta}}_t \right)^{-1} \\ &\quad \left( \mathbf{X}_t^\top \mathbf{Z}_t \right) \left( \mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0} \right)^{-1} \mathbf{Z}_t^\top \mathbf{\eta}_t \\ &= \mathbf{x}^\top \left( \hat{\mathbf{\Theta}}_t^\top (\mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0}) \hat{\mathbf{\Theta}}_t \right)^{-1} \left( \mathbf{X}_t^\top \mathbf{Z}_t \right) \left( \mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0} \right)^{-1} \mathbf{Z}_t^\top \mathbf{\eta}_t \\ &= \left( \left( \mathbf{Z}_t^\top \mathbf{X}_t \right) \underbrace{\left( \hat{\mathbf{\Theta}}_t^\top (\mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0}) \hat{\mathbf{\Theta}}_t \right)^{-1}}_{\hat{\mathbf{H}}_t} \right)^{-1} \mathbf{x}, \underbrace{(\mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0})^{-1} \mathbf{Z}_t^\top \mathbf{\eta}_t}_{\mathbf{G}_{z,t}} \\ &= \left\langle \left( \mathbf{Z}_t^\top \mathbf{X}_t \right) \hat{\mathbf{H}}_t^{-\top} \mathbf{x}, \mathbf{G}_{z,t}^{-1} \mathbf{Z}_t \mathbf{\eta}_t \right\rangle \\ &\le \| (\mathbf{Z}_t^\top \mathbf{X}_t) \hat{\mathbf{H}}_t^{-\top} \mathbf{x} \|_{\mathbf{G}_{z,t}^{-1}} \| \mathbf{G}_{z,t}^{-1} \mathbf{Z}_t \mathbf{\eta}_t \|_{\mathbf{G}_{z,t}} \\ &= \| (\mathbf{Z}_t^\top \mathbf{X}_t) \hat{\mathbf{H}}_t^{-\top} \mathbf{x} \|_{\mathbf{G}_{z,t}^{-1}} \| \mathbf{Z}_t \mathbf{\eta}_t \|_{\mathbf{G}_{z,t}^{-1}} \\ &= \left( \mathbf{x}^\top \hat{\mathbf{H}}_t^{-1} (\mathbf{X}_t^\top \mathbf{Z}_t) \left( \mathbf{Z}_t^\top \mathbf{Z}_t \right)^{-1} \left( \mathbf{Z}_t^\top \mathbf{X}_t \right) \hat{\mathbf{H}}_t^{-\top} \mathbf{x} \right) \| \mathbf{Z}_t \mathbf{\eta}_t \|_{\mathbf{G}_{z,t}^{-1}} \\ &= \left( \mathbf{x}^\top \hat{\mathbf{H}}_t^{-1} (\mathbf{X}_t^\top \mathbf{Z}_t) \hat{\mathbf{\Theta}}_t^\top \hat{\mathbf{H}}_t^{-\top} \mathbf{x} \right) \| \mathbf{Z}_t \mathbf{\eta}_t \|_{\mathbf{G}_{z,t}^{-1}} \\ &= \left( \mathbf{x}^\top \hat{\mathbf{H}}_t^{-1} \hat{\mathbf{\Theta}}_t^\top (\mathbf{Z}_t^\top \mathbf{Z}_t)^{-1} \hat{\mathbf{\Theta}}_t \hat{\mathbf{H}}_t^{-\top} \mathbf{x} \right) \| \mathbf{Z}_t \mathbf{\eta}_t \|_{\mathbf{G}_{z,t}^{-1}} \\ &= \left( \mathbf{x}^\top \hat{\mathbf{H}}_t^{-1} \hat{\mathbf{H}}_t \hat{\mathbf{H}}_t^{-\top} \mathbf{x} \right) \| \mathbf{Z}_t \mathbf{\eta}_t \|_{\mathbf{G}_{z,t}^{-1}} \\ &= \| \mathbf{x} \|_{\hat{\mathbf{H}}_t^{-1}} \| \mathbf{Z}_t \mathbf{\eta}_t \|_{\mathbf{G}_{z,t}^{-1}} \end{aligned} $$
Finally, from our initial decomposition, dividing on both sides by ‖ β$_{t}$ − β ‖$_{ˆ}$ Θ$_{t}$ ⊤ G$_{z,t}$ ˆ Θ$_{t}$ , we get

$$
\| \beta_t - \beta \|_{\hat{\Theta}_t^\top G_{z,t} \hat{\Theta}_t} \le \sqrt{\frac{d\sigma_\eta^2}{4} \log \left( \frac{1+tL_z^2/\lambda}{\delta} \right)}. \quad \square
$$

**Remark D.1.** We note that the ellipsoid bound has the following order in d and t while neglecting
the constants:

$$
\mathfrak{b}_t(\delta) = \mathcal{O}(d \log(t))
$$
Here, we define the first-stage design matrix to be $G_{z,t} \triangleq Z_t^\top Z_t$, and the second-stage design matrix to be $\hat{\mathbf{H}}_t \triangleq \hat{\Theta}_t^\top (\mathbf{Z}_t^\top \mathbf{Z}_t + \mathbf{G}_{z,0}) \hat{\Theta}_t = \hat{\Theta}_t^\top \mathbf{G}_{z,t} \hat{\Theta}_t$ for any $t > 0$.

Inequality (a) is obtained from the Cauchy-Schwartz inequality. Equality (b) is due to the fact that $\|\mathbf{A}^{-1}\mathbf{x}\|_{\mathbf{A}} = \|\mathbf{x}\|_{\mathbf{A}^{-1}}$. Equality (c) is due to the definition of $\hat{\Theta}_t$ (Eq. (13)).

**Step 3:** Now, let us choose $\mathbf{x} \triangleq \hat{\mathbf{H}}_t (\beta_t - \beta)$.

This leads to

$$ \text{LHS} = (\beta_t - \beta)^\top \hat{\mathbf{H}}_t (\beta_t - \beta) = \|\beta_t - \beta\|_{\hat{\mathbf{H}}_t}^2, $$

and

$$ \begin{aligned} \text{RHS} &= \|\hat{\mathbf{H}}_t(\beta_t - \beta)\|_{\hat{\mathbf{H}}_t^{-1}} \|\mathbf{Z}_t \eta_t\|_{\mathbf{G}_{z,t}^{-1}} \\ &= \|\beta_t - \beta\|_{\hat{\mathbf{H}}_t} \|\mathbf{Z}_t \eta_t\|_{\mathbf{G}_{z,t}^{-1}} \end{aligned} $$

**Step 4:** Combining the two results above lead to

$$ \|\beta_t - \beta\|_{\hat{\mathbf{H}}_t} \le \|\mathbf{Z}_t \eta_t\|_{\mathbf{G}_{z,t}^{-1}} $$

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

$$ \begin{aligned} \|\mathbf{Z}_t^\top \eta_t\|_{\mathbf{G}_{z,t}^{-1}} &= \left\| \sum_{s=1}^t \eta_s z_s \right\|_{\mathbf{G}_{z,t}^{-1}} \\ &\le \sqrt{2\sigma_\eta^2 \log \left( \frac{\det(\mathbf{G}_{z,t})^{1/2} \lambda^{-d_z/2}}{\delta} \right)} \\ &\le \sqrt{2d_z \sigma_\eta^2 \log \left( \frac{1 + tL_z^2/d_z\lambda}{\delta} \right)}. \end{aligned} $$

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

*Remark B.6 (t and d dependence.)*. We note that the ellipsoid bound has the following order in *d* and *t* while neglecting the constants:

$$ \mathfrak{b}_t(\delta) = \mathcal{O}(d_z \log(t)). $$

Thus, $\mathfrak{b}_t(\delta)$ is monotonically increasing with $t$. We widely leverage this property in the proofs.
E. A Detailed Discussion on Different Definitions of Regret

In econometrics, the focus has historically been given to the correct identification of the estimator $\beta$. 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 $\beta$ 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,

$$ \beta^{\text{MMSEE}} = \mathbb{E}[\mathbf{x}\mathbf{x}^{\top}]^{-1} \mathbb{E}[\mathbf{x}\mathbf{y}] = \beta + \mathbb{E}[\mathbf{x}\mathbf{x}^{\top}]^{-1} \mathbb{E}[\mathbf{x}\eta]. $$

This follows by solving for $\beta^*$ in $\partial_{\beta^*} \mathbb{E}_{xy}[(y - \mathbf{x}\beta^*)^2] = 0$, and by substituting for the definition of $y$ in $\mathbb{E}[\mathbf{x}\mathbf{y}] = \mathbb{E}[\mathbf{x}\mathbf{x}^{\top}]\beta^*$ (provided that we can invert the covariance matrix $\mathbb{E}[\mathbf{x}\mathbf{x}^{\top}$]). Under exogeneity $\mathbb{E}[\mathbf{x}\eta] = 0$ and the MMSEE concedes with $\beta$. Instead, in the more realistic case of endogenous noise $\mathbb{E}[\mathbf{x}\eta] \neq 0$ and the MMSEE estimator is biased with respect to the oracle $\beta$. This reveals that if we want to perform well at prediction time, we don't actually want an estimator for the oracle $\beta$, 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.

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 $\beta_{t-1}$ defined as $R_T(\beta_T) \triangleq \sum_{t=1}^T (y_t - \mathbf{x}_t^{\top} \beta_{t-1})^2 - \min_{\beta} \sum_{t=1}^T (y_t - \mathbf{x}_t^{\top} \beta)^2$ where we indicated with $\beta_T = \arg \min_{\beta} \sum_{t=1}^T (y_t - \mathbf{x}_t^{\top} \beta)^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 $\beta_{t-1}$ compared to the oracle. They are the oracle regret $\bar{R}_T(\beta)$ and the identification regret $\tilde{R}_T(\beta)$ below

$$ \bar{R}_T(\beta) = \sum_{t=1}^{T} (y_t - \mathbf{x}_t^{\top} \beta_{t-1})^2 - \sum_{t=1}^{T} (y_t - \mathbf{x}_t^{\top} \beta)^2 \quad \text{and} \quad \tilde{R}_T(\beta) = \sum_{t=1}^{T} (\mathbf{x}_t^{\top} \beta_{t-1} - \mathbf{x}_t^{\top} \beta)^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 $\Delta_T \triangleq R_T(\beta_T) - \bar{R}_T(\beta)$ is lower bound in expectation by $\mathbb{E}[\Delta_T] = \Omega(T)$

*Proof Sketch.* Solving for $\beta_T$ leads to the OLS estimator for data up to time $T$: $\beta_T = \beta + (\sum_{t=1}^T \mathbf{x}_t^{\top} \mathbf{x}_t)^{-1} \sum_{t=1}^T \mathbf{x}_t^{\top} \eta_t$ provided that we can invert the design matrix in the previous expression. Using this expression we can rewrite $\Delta_T$ using $\Delta\beta_T \triangleq \beta - \beta_T$ and $G_T \triangleq \sum_{t=1}^T \mathbf{x}_t^{\top} \mathbf{x}_t$ as follows

$$ \Delta_T = \sum_{t=1}^{T} (\mathbf{x}_t^{\top} \Delta\beta_T)^2 + 2 \sum_{t=1}^{T} \eta_t \mathbf{x}_t^{\top} \Delta\beta_T = 3 \|\Delta\beta_T\|_{G_T}^2. $$
## B.4 Concentration of the minimum eigenvalue of the design matrices

The aim of the section is to find a concentration result for the minimum eigenvalue of the design matrix, which, in turn, gives us a concentration of the $ℓ_2$-norm of the inverse of the design matrix $||G_{z,t}^{-1}||_2$. We use a classical concentration result for the covariance matrix Theorem A.14 together with the bound on the difference of the minimum eigenvalues of two symmetric matrices Lemma A.9 in order to bound the maximum eigenvalue of the inverse of the design matrix.

**Remark B.7 (Diversity condition of IVs).** In this section, we consider the covariance $\Sigma$, i.e. the true covariance matrix of the IVs vectors, to be only positive definite a.s. This is widely used in the stochastic online regression and linear bandit literature [Papini et al., 2021, Tirinzoni et al., 2022], and is known as the diversity condition.

**Lemma B.8 (Well-behavedness of First-stage Design Matrix).** Let $z_1, \dots, z_t$ be i.i.d. zero-mean random vectors with covariance $\Sigma$ such that $||z_s||_2 \le L_z$ almost surely. We denote the regularised design matrix as $G_{z,t} = \lambda I_{d_z} + \sum_{s=1}^t z_s z_s^\top$. For all $\delta > 0$ and regularisation parameter $\lambda > 0$, we observe that

$$ ||G_{z,t}^{-1}||_2 = \lambda_{\max}(G_{z,t}^{-1}) \le \begin{cases} \frac{1}{\lambda} & \text{if } t \le T_0 \\ \frac{2}{t \lambda_{\min}(\Sigma)} & \text{if } t > T_0 \end{cases} $$

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

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

$$ |\lambda_{\min}(G_{z,t}^{\lambda=0}/t) - \lambda_{\min}(\Sigma)| \le \frac{4L_z^2}{t} \log\left(\frac{2d_z}{\delta}\right) + 2\sqrt{\frac{2L_z^2}{t} \log\left(\frac{2d_z}{\delta}\right)} ||\Sigma||_2. $$

Further substituting $A \triangleq 2L_z^2 \log(\frac{2d_z}{\delta})$ leads to the following lower bound for the minimum eigenvalue

$$ \lambda_{\min}(G_{z,t}^{\lambda=0}) \ge \max \left\{ 0, t \left( \lambda_{\min}(\Sigma) - 2A/t - 2\sqrt{A \lambda_{\max}(\Sigma)/t} \right) \right\}. $$

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

Now, from the variational definition of the minimum eigenvalues, we have $\lambda_{\min}(G_{z,t}) \ge \lambda_{\min}(G_{z,t}^{\lambda=0}) + \lambda$, which implies that $\lambda_{\min}(G_{z,t}) \ge \lambda$ for all $t \ge 0$, with equality for $t = 0$. Thus, we have

$$ \lambda_{\min}(G_{z,t}) \ge \max \left\{ \lambda, \lambda + t \left( \lambda_{\min}(\Sigma) - 2A/t - 2\sqrt{A \lambda_{\max}(\Sigma)/t} \right) \right\}. \quad (17) $$

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

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

Now we study for which values Term (B) is non-negative. The corresponding second-order polynomial equation is obtained substituting $u = \sqrt{t}$, and is $u^2 \lambda_{\min}(\Sigma) - 4u\sqrt{A \lambda_{\max}(\Sigma)} + 2(\lambda -
Thanks to Lemma B.2, we know that the minimum eigenvalue of $G_T$ is $\Omega(T)$ which implies $\|\Delta\beta_T\|_{G_T}^2 \ge \|\Delta\beta_T\|_2^2 \lambda_{\min}(G_T) \gtrsim \|\Delta\beta_T\|_2^2 T$. Furthermore, we can bound away from zero in expectation $\|\Delta\beta_T\|$ by using Cramér-Rao bound on each component of the estimator $\beta_T$, for which we have $E[(\beta_{T,i} - \beta_i)^2] \ge \frac{[1+b'(\beta_i)]^2}{I(\beta_i)} + b(\beta_i)^2$ where $b(\beta_i) = E[\beta_{T,i}] - \beta_i$ is the bias of the estimator and $I(\beta_i)$ is the Fisher Information evaluated at $\beta_i$. We know that $\beta_T$ is a biased estimator of $\beta$ in the endogenous setting, therefore the bias is strictly positive for at least one component, and this concludes the proof.
2A) = 0, which has two solutions given by $u_{\pm} = 2\sqrt{A\lambda_{\max}(\Sigma)\pm\sqrt{4A\lambda_{\max}(\Sigma)+2(2A-\lambda)\lambda_{\min}(\Sigma)}}/\lambda_{\min}(\Sigma)$. In particular for $t > [u_{+}]$, Term (B) $\ge 0$, and Equation (17) simplifies in

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

Therefore, for $t > [2\lambda/\lambda_{\min}(\Sigma)]$ and $t > [u_{+}]$ we have that $\lambda_{\min}(\mathbf{G}_{z,t}) \ge t \lambda_{\min}(\Sigma)/2$. Putting the results together, we conclude that

$$ \lambda_{\min}(\mathbf{G}_{z,t}) \geq t \lambda_{\min}(\Sigma)/2 \quad \text{for} \quad t > T_0 \triangleq \max\{[2\lambda/\lambda_{\min}(\Sigma)], [u_{+}]\}, \quad (18) $$

while for $t \le T_0$, we retain the trivial lower bound of the minimum eigenvalue, i.e. $\lambda$. In summary, we have

$$ \lambda_{\min}(\mathbf{G}_{z,t}) \ge \begin{cases} \lambda & \text{if } t \le T_0 \\ t \lambda_{\min}(\Sigma)/2 & \text{if } t > T_0 \end{cases} \iff \lambda_{\max}(\mathbf{G}_{z,t}) \le \begin{cases} \frac{1}{\lambda} & \text{if } t \le T_0 \\ \frac{2}{t \lambda_{\min}(\Sigma)} & \text{if } t > T_0 \end{cases}. $$

□

**Corollary B.9** (Bound on the sum of maximum eigenvalues of the inverses of the first-stage design matrices). For every $T > 0$, we have

$$ \sum_{s=0}^{T} \|\mathbf{G}_{z,s}^{-1}\|_{2} \le f(T) = \mathcal{O}(\log(T)), $$

where $f(t) \triangleq \frac{T_0+1}{\lambda} + \frac{2(\log(T)+1)}{\lambda_{\min}(\Sigma)}$.

*Proof.* For $T \le T_0$,

$$ \sum_{s=0}^{T} \|\mathbf{G}_{z,s}^{-1}\|_{2} = \sum_{s=0}^{T} \frac{1}{\lambda} \le \frac{T_0 + 1}{\lambda} = \mathcal{O}(1). \quad (19) $$

If $T > T_0$

$$ \sum_{s=0}^{T} \|\mathbf{G}_{z,s}^{-1}\|_{2} = \sum_{s=0}^{T_0} \frac{1}{\lambda} + \sum_{s=T_0+1}^{T} \frac{2}{\lambda_{\min}(\Sigma)s} \le \frac{T_0+1}{\lambda} + \frac{2(\log(T)+1)}{\lambda_{\min}(\Sigma)} = \mathcal{O}(\log(T)) \quad (20) $$

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

□
## 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 \triangleq \sum_{s=1}^{t} \Delta\beta_{s-1}^{\top} (\epsilon_s \eta_s - \gamma),$$

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 $\mathcal{F}_t \triangleq \sigma(\epsilon_{s:t}, \eta_{1:t}, z_{1:t})$ (or equivalently a sum of martingale difference sequence), by proving that: (a) $\mathbb{E}[|S_t|] \le \infty$ and (b) $\mathbb{E}[S_{t+1} | \mathcal{F}_t] = S_t$. The first condition is immediate and the second can be easily verified since:

$$\mathbb{E}[S_{t+1} | \mathcal{F}_t] = \mathbb{E} \left[ \Delta\beta_t^{\top} (\epsilon_{t1} \eta_{t+1} - \gamma) + \sum_{s=1}^{t} \Delta\beta_{s-1}^{\top} (\epsilon_s \eta_s - \gamma) \mid \mathcal{F}_t \right] = 0 + \sum_{s=1}^{t} \Delta\beta_{s-1}^{\top} (\epsilon_s \eta_s - \gamma) = 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 $\{(\Delta\beta_{s-1}^{\top} (\epsilon_s \eta_s - \gamma), \mathcal{F}_s)\}_{s=1}^{\infty}$.

**Theorem F.1 (Concentration Bounds for Martingale Difference Sequences Wainwright (2019)).** Let $\{(D_k, \mathcal{F}_k)\}_{k=1}^{\infty}$ be a martingale difference sequence, and suppose that $\mathbb{E}[e^{\lambda D_k} | \mathcal{F}_{k-1}] \le e^{\lambda^2 \nu_k^2/2}$ almost surely for any $|\lambda| < 1/\alpha_k$. Then the following hold:

1. The sum $\sum_{k=1}^n D_k$ is sub-exponential with parameters $(\sqrt{\sum_{k=1}^n \nu_k^2}, \alpha_*)$, where $\alpha_* := \max_{k=1,...,n} \alpha_k$.

2. The sum satisfies the concentration inequality

$$\mathbb{P}\left[\left|\sum_{k=1}^{n} D_k\right| \ge t\right] \le \begin{cases} 2e^{-\frac{\nu^2}{2\sum_{k=1}^{n} \nu_k^2}} & \text{if } 0 \le t \le \frac{\sum_{k=1}^{n} \nu_k^2}{\alpha_*}, \\ 2e^{-\frac{1}{2\alpha_*}} & \text{if } t > \frac{\sum_{k=1}^{n} \nu_k^2}{\alpha_*}. \end{cases}$$

To apply the previous theorem, we derive in the following the sub-exponentiality parameters $\nu_s^*$, $\alpha_s^*$ for the martingale difference $D_s \triangleq \Delta\beta_{s-1}^{\top} (\epsilon_s \eta_s - \gamma)$ such that $\mathbb{E}[e^{\lambda\Delta\beta_{s-1}^{\top}(\epsilon_s \eta_s - \gamma)} | \mathcal{F}_{s-1}] \le e^{\lambda^2 \nu_s^*^2/2}$ a.s. $\forall |\lambda| < 1/\alpha_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 \sim \text{sub-Gauss}(\sigma_X)$ and $Y \sim \text{sub-Gauss}(\sigma_Y)$, we can prove the two following things:

1. $X^2$ is sub-exp$(4\sqrt{2}\sigma^2, 4\sigma^2)$;

2. the recentered random variable $XY$ is sub-exp$(4\sqrt{2}(\sigma_X^2 + \sigma_Y^2), 2(\sigma_X^2 + \sigma_Y^2))$.

*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

$$\mathbb{E}[|X/\sigma\sqrt{2}|^p] = \int_0^\infty \mathbb{P}\{|X/\sigma\sqrt{2}|^p \ge u\} du \quad (\text{integral identity for positive r.v.})$$

$$= \frac{1}{\sqrt{2\sigma}} \int_0^\infty \mathbb{P}\{|X| \ge t\sqrt{2\sigma}\} pt^{p-1}dt \quad (\text{change of variable } u = t^p)$$

$$\le \int_0^\infty 2e^{-t^2} pt^{p-1}dt \quad (\text{by } \sigma\text{-sub-Gaussianity})$$
## B.5 Upper bounding the feature norms

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

**Remark B.10.** In Appendix B.2, we describe that the first stage regression in O2SLS can be expressed as running *d* independent ridge regressions for each column of Θ (Equation (14)). Since the standard analysis of each of the ridge regressions assume independent and sub-Gaussian noise added in the linear model (cf. Theorem B.5; [Ouhamma et al., 2021]), we assume that each component of the first stage noise, i.e. $\epsilon_{t,i}$, corresponding to the *i*-th ridge regression is sub-Gauss($\sigma_{\epsilon}$). Thus, we obtain that $E\|\epsilon_t\|_2^2 \le d_x\sigma_{\epsilon}^2$. We use this result throughout this section.

**Lemma B.11 (Bounding the First-stage Estimates).** Under Assumptions 2.1 and IVs being bounded $\|z\|_2^2 \le L_z^2$, the minimum singular value of the estimated parameter in the first-stage regression (Equation (14)) is lower bounded by:

$$ \sigma_{\min}(\hat{\Theta}_t) \ge \frac{\mathbf{r}^2}{L_z^2}, \qquad (21) $$

where we have from the relevance condition of IVs, $\sigma_{\min}(\text{Cov}(\mathbf{Z}_t, \mathbf{X}_t)) = \sigma_{\min}(\frac{1}{t}\sum_{s=1}^t \mathbf{z}_s\mathbf{x}_s^\top) \ge \mathbf{r} > 0$ (Eq. (12)).

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

$$
\begin{align*}
\sigma_{\min}(\hat{\Theta}_t) &= \sigma_{\min} \left( (\mathbf{Z}_t^\top \mathbf{Z}_t)^{-1} (\mathbf{Z}_t^\top \mathbf{X}_t) \right) \\
&= \min_{v \in \mathbb{S}^{d_x-1}} \| (\mathbf{Z}_t^\top \mathbf{Z}_t)^{-1} (\mathbf{Z}_t^\top \mathbf{X}_t) v \|_2 \\
&= \min_{(a) v \in \mathbb{S}^{d_x-1}} \frac{\| (\mathbf{Z}_t^\top \mathbf{Z}_t)^{-1} (\mathbf{Z}_t^\top \mathbf{X}_t) v \|_2}{\| (\mathbf{Z}_t^\top \mathbf{X}_t) v \|_2} \| (\mathbf{Z}_t^\top \mathbf{X}_t) v \|_2 \\
&\ge \sigma_{\min} \left( (\mathbf{Z}_t^\top \mathbf{Z}_t)^{-1} \right) \sigma_{\min} \left( \mathbf{Z}_t^\top \mathbf{X}_t \right) \\
&= \lambda_{\min} \left( (\mathbf{Z}_t^\top \mathbf{Z}_t)^{-1} \right) \sigma_{\min} \left( \mathbf{Z}_t^\top \mathbf{X}_t \right) \\
&= \frac{\sigma_{\min} (\mathbf{Z}_t^\top \mathbf{X}_t)}{\lambda_{\max} (\mathbf{Z}_t^\top \mathbf{Z}_t)}.
\end{align*}
$$

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

$$ \lambda_{\max} (\mathbf{Z}_t^\top \mathbf{Z}_t) = \max_{v \in \mathbb{S}^{d_z-1}} \left\langle v, \sum_{s=1}^t z_s \mathbf{z}_s^\top v \right\rangle = \max_{v \in \mathbb{S}^{d_z-1}} \sum_{s=1}^t \langle v, z_s \rangle^2 \le \sum_{s=1}^t \|z_s\|_2^2 \le t L_z^2 $$

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

$$ \sigma_{\min}(\hat{\Theta}_t) = \frac{\sigma_{\min}(\mathbf{Z}_t^\top \mathbf{X}_t)}{\lambda_{\max}^2 (\mathbf{Z}_t^\top \mathbf{Z}_t)} \ge \frac{t\mathbf{r}^2}{tL_z^2} \ge \frac{\mathbf{r}^2}{L_z^2}. \quad \square $$

<figure><img src="image_7.png" /></figure>