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

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

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

$$ \begin{aligned} \mathbb{E}[e^{\lambda(Y-\mu_Y)}] &= 1 + \lambda \mathbb{E}[Y - \mu_Y] + \sum_{r=2}^{\infty} \frac{\lambda^r \mathbb{E}[(Y - \mu_Y)^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} \end{aligned} $$

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). $$

2. We notice that

$$ XY - \mathbb{E}[XY] = \left(\frac{X-Y}{2}\right)^2 - \mathbb{E}\left[\left(\frac{X-Y}{2}\right)^2\right] - \left(\left(\frac{X+Y}{2}\right)^2 - \mathbb{E}\left[\left(\frac{X+Y}{2}\right)^2\right]\right) \triangleq Z_1 - Z_2 $$

where we defined $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]$. We have to take into account the dependence, and we start with the sum/difference between $X, Y$

$$ \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 Cauchy-Schwarz inequality and the sub-Gaussianity of $X$ and $Y$. This proves for rescaled variables that both $X+Y$ and $X-Y$ are sub-Gauss($\sqrt{2}\sqrt{\sigma_X^2 + \sigma_Y^2}$), therefore their rescaled versions $\frac{X+Y}{2}$ and $\frac{X-Y}{2}$ are sub-Gauss($\frac{\sqrt{\sigma_X^2 + \sigma_Y^2}}{\sqrt{2}}$). At this point we use the result on square of sub-Gaussian random variables at point 1, to have that $Z_1$ and $Z_2$ are both sub-exp($4\sqrt{2}\frac{\sigma_X^2+\sigma_Y^2}{2}, 4\frac{\sigma_X^2+\sigma_Y^2}{2}$).

Again we use Cauchy-Schwarz due to the dependency between the random variables $Z_1$ and $Z_2$ in the first inequality in the next equation

$$ \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 \frac{1}{2(\sigma_X^2 + \sigma_Y^2)}$. This proves that the sub-exponential parameters are indeed $\nu \triangleq 4\sqrt{2}(\sigma_X^2 + \sigma_Y^2)$ and $\alpha \triangleq 2(\sigma_X^2 + \sigma_Y^2)$. $\square$

**Lemma F.2 (Concentration of Correlated First and Second-stage Noise).** For sub-Gaussian first- and second-stage noises with parameters $\sigma_\eta$ and $\sigma_\epsilon$, and first-stage parameter estimates satisfying $\|\hat{\Theta}_t^{-1}\|_2 \le L_{\hat{\Theta}^{-1}}$ (Lemma C.1), we show that
**Lemma B.12.** For any $t \ge 1$, we get

$$ \|\hat{\mathbf{H}}_{t-1}^{-1}\|_2 = \lambda_{\max}(\hat{\mathbf{H}}_{t-1}^{-1}) = \frac{1}{\lambda_{\min}(\hat{\mathbf{H}}_{t-1})} \le \frac{1}{\lambda_{\min}(\mathbf{G}_{z,t-1}) \sigma_{\min}^2(\hat{\mathbf{\Theta}}_{t-1})}. \quad (22) $$

*Proof.* The equalities follow directly from Corollary A.5, by the definition of the operator norm of a symmetric matrix, and using the fact that the maximum eigenvalue of an inverse matrix equals the inverse of the minimum eigenvalue of the matrix. For the inequality, we start by lower bounding the minimum eigenvalue of the second stage design matrix $\hat{\mathbf{H}}_{t-1}$ and applying the definitions:

$$ \begin{aligned} \lambda_{\min}(\hat{\mathbf{H}}_{t-1}) = \lambda_{\min}(\hat{\mathbf{\Theta}}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\mathbf{\Theta}}_{t-1}) &= \min_{v \in \mathbb{S}^{d_{\mathbf{x}}-1}} \langle v, \hat{\mathbf{\Theta}}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\mathbf{\Theta}}_{t-1} v \rangle \\ &= \min_{v \in \mathbb{S}^{d_{\mathbf{x}}-1}} \frac{\langle v, \hat{\mathbf{\Theta}}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\mathbf{\Theta}}_{t-1} v \rangle}{\langle \hat{\mathbf{\Theta}}_{t-1} v, \hat{\mathbf{\Theta}}_{t-1} v \rangle} \langle \hat{\mathbf{\Theta}}_{t-1} v, \hat{\mathbf{\Theta}}_{t-1} v \rangle \\ &\ge \lambda_{\min}(\mathbf{G}_{z,t-1}) \min_{v \in \mathbb{S}^{d_{\mathbf{x}}-1}} \|\hat{\mathbf{\Theta}}_{t-1} v\|^2 \\ &\ge \lambda_{\min}(\mathbf{G}_{z,t-1}) \sigma_{\min}^2(\hat{\mathbf{\Theta}}_{t-1}) \end{aligned} $$

and we conclude taking the inverses.

□

**Lemma B.13** (Bounding the impact of first-stage noise). For first stage noises that is component-wise sub-Gaussian($\sigma_{\epsilon}$), and bounded IVs, i.e. $\|z\|_2^2 \le L_z^2$, we have that

$$ \sum_{t=1}^{T} \|\epsilon_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2 \le \underbrace{\frac{\mathbf{r}^4}{L_z^4} (d_x \sigma_{\epsilon}^2 f(T) + C_5)}_{\mathcal{O}(d_x \log T)} $$

with probability at least $1 - \delta$. Here, $C_5$ is a constant of $\mathcal{O}(d_x)$ as defined in Equation (24).

*Proof.* The proof follows using chain of inequalities

$$ \begin{aligned} \sum_{t=1}^{T} \|\epsilon_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2 &\le \sum_{t=1}^{T} \|\epsilon_t\|_2^2 \lambda_{\max}(\hat{\mathbf{H}}_{t-1}^{-1}) = \sum_{t=1}^{T} \frac{\|\epsilon_t\|_2^2}{\lambda_{\min}(\hat{\mathbf{H}}_{t-1})} \\ &\le \sum_{t=1}^{T} \frac{\|\epsilon_t\|_2^2}{\lambda_{\min}(\mathbf{G}_{z,t-1}) \sigma_{\min}^2(\hat{\mathbf{\Theta}}_{t-1})} \le \frac{\mathbf{r}^4}{L_z^4} \sum_{t=1}^{T} \frac{\|\epsilon_t\|_2^2}{\lambda_{\min}(\mathbf{G}_{z,t-1})} \\ &= \frac{\mathbf{r}^4}{L_z^4} \left( \underbrace{\sum_{t=1}^{T} \|\mathbf{G}_{z,t-1}^{-1}\|_2^2 (\|\epsilon_t\|_2^2 - \mathbb{E}\|\epsilon_t\|_2^2)}_{\text{Term I}} + \underbrace{\sum_{t=1}^{T} \|\mathbf{G}_{z,t-1}^{-1}\|_2^2 \mathbb{E}\|\epsilon_t\|_2^2}_{\text{Term II}} \right) \end{aligned} $$

where in the second inequality we used Lemma B.12, Lemma B.11 in the third, and we simply split in two terms in the final passage the summation.

**Term I:** The squared $\ell_2$-norms of sub-Gaussian random variables are sub-exponential [Wainwright, 2019], therefore $\|\epsilon_t\|_2^2 - \mathbb{E}\|\epsilon_t\|_2^2 \sim \text{sub-exp}(\nu, \alpha)$ where the correct values of $\nu, \alpha$ are derived in Lemma A.12, in the result on the square of sub-Gaussians variables, and gives
$$
\left| \sum_{t=1}^{T} \Delta \beta_{t-1}^{\top} (\epsilon_t \eta_t - \gamma) \right| \le 8e^2 (\sigma_{\eta}^2 + \sigma_{\epsilon}^2) \sqrt{dL} \hat{\Theta}^{-1} \sqrt{b_{T-1}(\delta)} \left( \sqrt{2 \log(2/\delta)} \left( \frac{C_3+1}{\lambda} + 2 \frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right) \right. \\
\left. + \sqrt{\max \left\{ \frac{1}{\lambda}, \frac{2}{\lambda_{\min}(\Sigma)} \right\} \log(2/\delta)} \right)
$$

with probability at least 1 − δ ∈ [0 , 1) .

Proof. The proof proceeds in steps and the main technical difficulty arises from the dependence between the random variables, which we tackle using Lemma F.1 plus some techniques derived from the equivalent characterizations of sub-Gaussians and sub-exponential random variables.

1. We bound the p-th moment of the random variable z_i ≜ (ε_{s,i}η_s - γ_i) using the result from Lemma F.1 for the product of two non independent random variables. The random variable z_i is the centered product of η_s and ε_{s,i} which are sub-Gaussians, therefore it is sub-exp (ν_i, α_i) with ν_i ≜ 4√2 (σ_ε^2 + σ_η^2) , α_i ≜ 2 (σ_ε^2 + σ_η^2) . We can also take K_5 ≜ max { α_i, ν_i/√2 } = 4 (σ_ε^2 + σ_η^2) which implies E [e^{λz_i}] ≤ e^{λ^2 K_5^2} ∀|λ| ≤ 1/K_5, and together with the inequality |x|^p ≤ p^p (e^x + e^{-x}) we obtain

$$
\mathbb{E} \left[ \left| \frac{\mathbf{z}_i}{K_5} \right|^p \right] \le \mathbb{E} \left[ p^p \left( \exp \left( \frac{\mathbf{z}_i}{K_5} \right) + \exp \left( -\frac{\mathbf{z}_i}{K_5} \right) \right) \right] \le p^p 2e^{K_5^2/K_5^2} \le 2ep^p
$$

The previous inequality directly implies an inequality on the p-th norm of the random variable
$\epsilon_{s,i}\eta_s - \gamma_i$

$$
\sqrt[p]{\mathbb{E}[|\epsilon_{s,i}\eta_s - \gamma_i|^p]} \le \sqrt[p]{2eK_5p} \le 2eK_5p = 4e(\sigma_{\epsilon}^2 + \sigma_{\eta}^2)p \triangleq K_2p
$$

2. We finally find the sub-exponential parameters for the scalar product Δ β T s − 1 ( ϵ$_{s}$η$_{s}$ − γ ) . Using the sub-exponential characterization with L p norm we have ∀ p ≥ 1

$$
\| \Delta \beta_{s-1}^{T} (\epsilon_s \eta_s - \gamma) \|_p \le \sum_{i=1}^{d} |\Delta \beta_{s-1,i}| \| \epsilon_{s,i} \eta_s - \gamma \|_p \le \sum_{i=1}^{d} |\Delta \beta_{s-1,i}| K_2 p = K_s p \quad (19)
$$

where $K_s \triangleq \sum_{i=1}^d |\Delta\beta_{s-1,i}| K_2 \triangleq 4e(\sigma_\epsilon^2 + \sigma_\eta^2) \sum_{i=1}^d |\Delta\beta_{s-1,i}|$ We are ready to bound the moment-generating function and derive the

$$
\begin{align*}
\mathbb{E} \left[ e^{\lambda \sum_{i=1}^{d} \Delta \beta_{s-1,i} (\epsilon_{s,i} \eta_s - \gamma_i)} \mid \mathcal{F}_{s-1} \right] &= \mathbb{E} \left[ \sum_{p=0}^{\infty} \frac{\lambda^p (\Delta \boldsymbol{\beta}^{\top} (\epsilon_s \eta_s - \boldsymbol{\gamma}))^p}{p!} \right] && \text{(series expansion)} \\
&= \sum_{p=0}^{\infty} \frac{\lambda^p}{p!} \mathbb{E} \left[ \left( \Delta \boldsymbol{\beta}^{\top} (\epsilon_s \eta_s - \boldsymbol{\gamma}) \right)^p \right] && \text{(linearity of expectation)} \\
&= 1 + \sum_{p=2}^{\infty} \frac{\lambda^p \mathbb{E} \left[ \left( \Delta \boldsymbol{\beta}^{\top} (\epsilon_s \eta_s - \boldsymbol{\gamma}) \right)^p \right]}{p!} && \text{(1st moment = 0)} \\
&\le 1 + \sum_{p=2}^{\infty} \frac{\lambda^p K_s^p p^p}{p!} && \text{(Equation (19))} \\
&\le 1 + \sum_{p=2}^{\infty} \lambda^p K_s^p e^p && \text{(Stirling's approximation } p! \ge \frac{p^p}{ep^p})
\end{align*}
$$
$\nu \triangleq 4\sqrt{2}d_x\sigma_{\epsilon}^2$ and $\alpha \triangleq 4\sigma_{\epsilon}^2$. Furthermore, given an $X \sim \text{sub-exp}(\nu, \alpha)$ and a constant $c$, then $X/c \sim \text{sub-exp}(\nu/c, c/\alpha)$ which follows by considering a new parameter $\lambda/c$ in the definitions of sub-exponentiality $\mathbb{E}[e^{\lambda X/c}] \le e^{\lambda^2\nu^2/2c^2}$, where $|\lambda/c| \le \frac{1}{\alpha}$ iff $|\lambda| \le \frac{c}{\alpha}$. Using this, we rescale by the factor $t$

$$ \mathbb{P} \left[ \sum_{t=T_0}^{T} \frac{\|\epsilon_t\|_2^2 - \mathbb{E}\|\epsilon_t\|_2^2}{t} \ge \mu \right] \le \begin{aligned} & \mathbb{E} \left[ e^{\lambda \sum_{t=T_0}^{T} \frac{\|\epsilon_t\|_2^2 - \mathbb{E}\|\epsilon_t\|_2^2}{t}} \right] e^{-\lambda \mu} \\ & \le e^{\sum_{t=T_0}^{T} \lambda^2 \nu^2 / 2t^2 - \lambda \mu} \\ & \le e^{\frac{\lambda^2 \nu^2}{2} \left( \frac{1}{T_0-1} - \frac{1}{T} \right) - \lambda \mu} \end{aligned} $$

where (a) is Markov's inequality, (b) uses the product rule for expectations and $\|\epsilon_t\|_2^2 - \mathbb{E}\|\epsilon_t\|_2^2 \sim \text{sub-exp}(\nu = 4\sqrt{2}d_x\sigma_{\epsilon}^2, \alpha = 4\sigma_{\epsilon}^2)$, and (c) holds $\forall |\lambda| \le \frac{m}{\alpha}$ thanks to the following series of inequalities $\sum_{T_0}^{T} \frac{1}{t^2} \le \int_{t_0-1}^{T} 1/t^2 dt = (-\frac{1}{T})|_{T_0-1}^{T} = -\frac{1}{T} + \frac{1}{T_0-1}$. This proves that

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

We bound the following summation using Lemma B.8:

$$ \begin{aligned} & \sum_{t=1}^{T} \left\| \mathbf{G}_{z,t-1}^{-1} \right\|_{2} \left( \|\epsilon_t\|_{2}^{2} - \mathbb{E} \|\epsilon_t\|_{2}^{2} \right) \\ &= \sum_{t=0}^{T_0} \lambda_{\max}(\mathbf{G}_{z,t}^{-1}) \left( \|\epsilon_{t+1}\|_{2}^{2} - \mathbb{E} \|\epsilon_{t+1}\|_{2}^{2} \right) + \sum_{t=T_0+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}^{T_0} \left( \|\epsilon_{t+1}\|_{2}^{2} - \mathbb{E} \|\epsilon_{t+1}\|_{2}^{2} \right) + \frac{2}{\lambda_{\min}(\Sigma)} \sum_{t=T_0+1}^{T-1} \frac{\|\epsilon_{t+1}\|_{2}^{2} - \mathbb{E} \|\epsilon_{t+1}\|_{2}^{2}}{t} \\ &\le \frac{T_0+1}{\lambda} \left( 4\sqrt{2}\sigma_{\epsilon}^2 d_x \sqrt{2\log(1/\delta)} + \frac{1}{2\sigma_{\epsilon}^2} \log(1/\delta) \right) \\ &\quad + \frac{2}{\lambda_{\min}(\Sigma)} \left( \sqrt{2\nu^2 \left( \frac{1}{T_0} - \frac{1}{T} \right) \log(1/\delta)} + \frac{2T_0}{\alpha} \log(1/\delta) \right) \end{aligned} $$

Since Term I can be upper-bounded by a constant $O(d_x)$, we just name this constant $C_5$ where we also substitute back the definitions $\nu = 4\sqrt{2}d_x\sigma_{\epsilon}^2$ and $\alpha = 4\sigma_{\epsilon}^2$. Specifically,

$$ \text{Term I} \le \frac{T_0+1}{\lambda} \left( 4\sqrt{2}d_x\sigma_{\epsilon}^2 \sqrt{2\log(1/\delta)} + \frac{1}{2\sigma_{\epsilon}^2} \log(1/\delta) \right) \\ + \frac{2}{\lambda_{\min}(\Sigma)} \left( 4\sqrt{2}d_x\sigma_{\epsilon}^2 \sqrt{\frac{2}{T_0}\log(1/\delta)} + \frac{2T_0}{4\sigma_{\epsilon}^2} \log(1/\delta) \right) \triangleq C_5, \quad (24) $$

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

**Term II:** The proof step-wise applies: (d) sub-Gaussianity of $\epsilon_t$, (e) the high-probability bound on the sum of the minimum eigenvalue of the first-stage design matrix in Corollary B.9

$$ \text{Term II} \le \sum_{t=1}^{T} \left\| \mathbf{G}_{z,t-1}^{-1} \right\|_{2} \mathbb{E} \|\epsilon_t\|_{2}^{2} $$
$$
\begin{align*}
&= 1 + \frac{(\lambda K_s e)^2}{1 - \lambda K_s e} && (\text{expression valid } \forall |\lambda| \le \frac{1}{K_s e}) \\
&\le 1 + 2 (\lambda K_s e)^2 && (\text{valid for } |\lambda| \le \frac{1}{2K_s e}) \\
&\le e^{2\lambda^2 K_s e^2} && (\text{using } 1 + x \le e^{x^2} \text{ for all } x \in \mathbb{R})
\end{align*}
$$

Therefore we have that $\Delta\beta_{s-1}^T(\epsilon_s\eta_s - \gamma)$ is sub-exp$(2K_s e, 2K_s e)$. We finally substitute for $K_s$ and we obtain

$$
\Delta\beta_{s-1}^{T}(\epsilon_{s}\eta_{s} - \gamma) \sim \text{sub-exp} \left( 8e^{2}(\sigma_{\epsilon}^{2} + \sigma_{\eta}^{2}) \|\Delta\beta_{s-1}\|_{1}, 8e^{2}(\sigma_{\epsilon}^{2} + \sigma_{\eta}^{2}) \|\Delta\beta_{s-1}\|_{1} \right)
$$

3. We are now ready to derive the concentration for the sum of the martingale difference sequence using Theorem F.1. From Theorem F.1 we have that $\left|\sum_{t=1}^{T} D_t\right| \le \sqrt{2\log(2/\delta)} \sum_{t} \nu_s^2 + 2\alpha^* \log(2/\delta)$ with probability bigger than $1 - \delta$. With the following substitutions:

$$
D_t \rightarrow \Delta\beta_{t-1}^{\top}(\epsilon_t \eta_t - \gamma), \quad \alpha_* \rightarrow 8e^2 (\sigma_{\epsilon}^2 + \sigma_{\eta}^2) \max_s \|\Delta\beta_{s-1}\|_1, \quad \nu_s \rightarrow 8e^2 (\sigma_{\epsilon}^2 + \sigma_{\eta}^2) \|\Delta\beta_{s-1}\|_1
$$

we obtain that with probability bigger than $1 - \delta$

$$
\left| \sum_{t=1}^{T} \Delta \beta_{t-1}^{\top} (\epsilon_t \eta_t - \gamma) \right| \le \sqrt{ \begin{aligned}[t]
& 2 \log \left( \frac{2}{\delta} \right) (8e^2)^2 (\sigma_{\eta}^2 + \sigma_{\epsilon}^2)^2 \sum_{t=1}^{T} \| \Delta \beta_{t-1} \|_1^2 \\
& + 8e^2 (\sigma_{\eta}^2 + \sigma_{\epsilon}^2) \max_t \| \Delta \beta_{t-1} \|_1 \log(2/\delta)
\end{aligned} }
$$

4. We study the term $\|\Delta\beta_{t-1}\|_1$, its sum and maximum over $t$, which we need to substitute in the previous concentration bound. We can bound $\|\Delta\beta_{t-1}\|_1^2 \le d \|\Delta\beta_{t-1}\|_2^2$ and then use some matrix tricks in the following for the individual terms

$$
\begin{align*}
\|\Delta\beta_{t-1}\|_2^2 &= \|\hat{\mathbf{H}}^{-1/2}\hat{\mathbf{H}}^{1/2}\Delta\beta_{t-1}\|_2^2 \\
&\le \|\hat{\mathbf{H}}_{t-1}^{-1/2}\|_2^2 \|\Delta\beta_{t-1}\|_{\hat{\mathbf{H}}_{t-1}}^2 && (\text{Proposition A.1}) \\
&\le \|\hat{\mathbf{H}}_{t-1}^{-1}\|_2 \mathfrak{b}_{t-1}(\delta) && (\text{Lemma D.1}) \\
&\le L_{\hat{\mathbf{\Theta}}}^{-2} \|\mathbf{G}_{\mathbf{z},t-1}^{-1}\|_2 \mathfrak{b}_{T-1}(\delta) && (\text{again Proposition A.1})
\end{align*}
$$

When we take the sum over the rounds we have

$$
\begin{align*}
\sum_{t=1}^{T} \|\Delta\beta_{t-1}\|_{1}^{2} &\le d \sum_{t=1}^{T} \|\Delta\beta_{t-1}\|_{2}^{2} \le d L_{\hat{\Theta}^{-1}}^{2} \mathfrak{b}_{T-1}(\delta) \sum_{t=1}^{T} \|\mathbf{G}_{\mathbf{z},t-1}^{-1}\|_{2} \\
&\le d L_{\hat{\Theta}^{-1}}^{2} \mathfrak{b}_{T-1}(\delta) \left( \frac{C_3+1}{\lambda} + 2 \frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right) && \text{(from Lemma B.2)}
\end{align*}
$$

For the maximum, we have instead

$$
\max_t \|\Delta\beta_{t-1}\|_1 \le \sqrt{dL_{\hat{\Theta}^{-1}} \sqrt{\mathfrak{b}_{T-1}(\delta) \|\mathbf{G}_{\mathbf{z},t-1}^{-1}\|_2}} \le \sqrt{dL_{\hat{\Theta}^{-1}} \sqrt{\mathfrak{b}_{T-1}(\delta) \max\left\{\frac{1}{\lambda}, \frac{2}{\lambda_{\min}(\Sigma)}\right\}}}
$$

Finally, we can substitute back these expressions in the bound at the previous point. We have that with a probability bigger than $1 - \delta$

$$
\left| \sum_{t=1}^{T} \Delta \beta_{t-1}^{\top} (\epsilon_t \eta_t - \gamma) \right| \le \sqrt{2 \log(2/\delta) (8e^2)^2 (\sigma_{\eta}^2 + \sigma_{\epsilon}^2)^2 d L_{\hat{\Theta}^{-1}}^2 \mathfrak{b}_{T-1}(\delta) \left( \frac{C_3+1}{\lambda} + 2 \frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right)}
$$
$$
\begin{align*}
& \le \frac{d_x \sigma_{\epsilon}^2}{(d)} \sum_{t=1}^{T} \lambda_{\max} \left( \mathbf{G}_{z,t-1}^{-1} \right) \\
& \le \frac{d_x \sigma_{\epsilon}^2 f(T)}{(e)}.
\end{align*}
$$

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

$$
\sum_{t=1}^{T} \| \epsilon_t \|_{\hat{\mathbf{H}}_{t-1}^{-1}}^{2} \le \underbrace{\frac{\mathbf{r}^4}{L_z^4} (d_x \sigma_{\epsilon}^2 f(T) + C_5)}_{\mathcal{O}(d_x \log T)}
$$

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

**Lemma B.14 (Bounding the sum of second-stage feature norms).** Under the same conditions of Lemma B.13 plus first-stage parameters with bounded $\ell_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{\mathbf{H}}_{t-1}^{-1}}^2 \le \underbrace{\left( L_{\Theta}^2 \frac{\mathbf{r}^4}{L_z^2} + \frac{\mathbf{r}^4}{L_z^4} d_x \sigma_{\epsilon}^2 \right) f(T) + \frac{\mathbf{r}^4}{L_z^4} C_5}_{\mathcal{O}(d_x \log T)}
$$

Proof. We start by substituting the first-stage equations inside the norm and using triangle inequality

$$
\begin{align*}
\sum_{t=1}^{T} \|x_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2 &= \sum_{t=1}^{T} \|\boldsymbol{\Theta}^{\top} z_t + \boldsymbol{\epsilon}_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2 \\
&\le \underbrace{\sum_{t=1}^{T} \|\boldsymbol{\Theta}^{\top} z_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2}_{\text{Term 1}} + \underbrace{\sum_{t=1}^{T} \|\boldsymbol{\epsilon}_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2}_{\text{Term 2}}
\end{align*}
$$

**Step 1: Bounding Term 1.** First, we upper bound the Term 1

$$
\begin{align*}
\sum_{t=1}^{T} \|\boldsymbol{\Theta}^{\top} z_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2 &= \sum_{t=1}^{T} \langle \boldsymbol{\Theta}^{\top} z_t, \hat{\mathbf{H}}_{t-1}^{-1} \boldsymbol{\Theta}^{\top} z_t \rangle \\
&\le \sum_{t=1}^{T} \|\boldsymbol{\Theta}^{\top} z_t\|_2^2 \lambda_{\max}(\hat{\mathbf{H}}_{t-1}^{-1})
\end{align*}
$$

Therefore, by application of Lemma B.12 in the first inequality, we have

$$
\begin{align*}
\sum_{t=1}^{T} \|\boldsymbol{\Theta}^{\top} z_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2 &\le \sum_{t=1}^{T} \frac{\|\boldsymbol{\Theta}^{\top} z_t\|_2^2}{\lambda_{\min}(\mathbf{G}_{z,t-1}) \sigma_{\min}^2(\hat{\boldsymbol{\Theta}}_{t-1})} \\
&\le \frac{\mathbf{r}^4}{L_z^4} \sum_{t=1}^{T} \frac{\|\boldsymbol{\Theta}^{\top} z_t\|_2^2}{\lambda_{\min}(\mathbf{G}_{z,t-1})} \\
&\le L_{\Theta}^2 L_z^2 \frac{\mathbf{r}^4}{L_z^4} \sum_{t=1}^{T} \frac{1}{\lambda_{\min}(\mathbf{G}_{z,t-1})} \\
&= \frac{L_{\Theta}^2 \mathbf{r}^4}{L_z^2} \sum_{t=1}^{T} \frac{1}{\lambda_{\min}(\mathbf{G}_{z,t-1})} \tag{25}
\end{align*}
$$
$$ + (8e^2) (\sigma_{\eta}^2 + \sigma_{\epsilon}^2) \sqrt{d} L_{\hat{\Theta}^{-1}} \sqrt{\mathfrak{b}_{T-1}(\delta) \max \left\{ \frac{1}{\lambda}, \frac{2}{\lambda_{\min}(\Sigma)} \right\}} \log(2/\delta) \quad \square $$

**Lemma F.3 (Bias of Correlated First and Second-stage Noise).** Under the same hypothesis of previous lemmas we can bound the bias term in the following way

$$ \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top}\gamma \le \|\gamma\|_2 L_{\hat{\Theta}^{-1}} \sqrt{\mathfrak{b}_T(\delta)} \left( \frac{C_3}{\sqrt{\lambda}} + 2 \frac{\sqrt{2T}}{\sqrt{\lambda_{\min}(\Sigma)}} \right) $$

*Proof.* The bias term has a much simpler analysis

$$ \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top}\gamma \le \sum_{t=1}^{T} \|\Delta\beta_{t-1}\|_{\hat{\mathbf{H}}_t} \|\gamma\|_{\hat{\mathbf{H}}_t^{-1}} \quad \text{(from Cauchy-Schwarz)} $$

$$ \le \sqrt{\mathfrak{b}_{T-1}(\delta)} \sum_{t=1}^{T} \|\gamma\|_{\hat{\Theta}_t^{-1} \mathbf{G}_{z,t}^{-1} \hat{\Theta}_t^{-1}} \quad \text{(from Lemma D.1 and $\mathfrak{b}_{T-1}$ increasing)} $$

$$ \le \sqrt{\mathfrak{b}_{T-1}(\delta)} \|\gamma\|_2 L_{\hat{\Theta}^{-1}} \sum_{t=1}^{T} \sqrt{\|\mathbf{G}_{z,t-1}^{-1}\|_2} \quad \text{(from Proposition A.1)} $$

$$ \le \sqrt{\mathfrak{b}_{T-1}(\delta)} \|\gamma\|_2 L_{\hat{\Theta}^{-1}} \left( \sum_{t=1}^{C_3} \frac{1}{\sqrt{\lambda}} + \sum_{t=C_3+1}^{T-1} \sqrt{\frac{2}{\lambda_{\min}(\Sigma)t}} \right) \quad \text{(from Lemma B.2)} $$

$$ \le \sqrt{\mathfrak{b}_{T-1}(\delta)} \|\gamma\|_2 L_{\hat{\Theta}^{-1}} \left( \frac{C_3}{\sqrt{\lambda}} + 2 \frac{\sqrt{2T}}{\sqrt{\lambda_{\min}(\Sigma)}} \right) $$

$$ \text{where the last inequality follows from } \sum_{k=1}^{n} \frac{1}{\sqrt{k}} = \sum_{k=1}^{n} \int_{k-1}^{k} \frac{dx}{\sqrt{k}} \le \sum_{k=1}^{n} \int_{k-1}^{k} \frac{dx}{\sqrt{x}} = \int_{0}^{n} \frac{dx}{\sqrt{x}} = 2\sqrt{n}. \quad \square $$
$$ \leq \frac{L_{\Theta}^{2} \mathbf{r}^{4}}{L_{z}^{2}} f(T) $$

Inequality (a) is due to Lemma B.11 that bounds the minimum singular value of the first-stage parameter estimates. Inequality (b) is direct consequence of boundedness of IVs and the true first-stage parameter, and (c) follows from Corollary B.9.

**Step 2: Bounding Term 2.** This term is bounded directly in in Lemma B.13 and we conclude that

$$ \sum_{t=1}^{T} \|\epsilon_t\|_{\hat{H}_{t-1}^{-1}}^{2} \leq \frac{\mathbf{r}^{4}}{L_{z}^{4}} (d_{x}\sigma_{\epsilon}^{2}f(T) + C_{5}) $$

**Step 3: Assembling the results.** Now combining the upper bounds for Term 1 and Term 2, we get

$$ \sum_{t=1}^{T} \|x_t\|_{\hat{H}_{t-1}^{-1}}^{2} \leq \left( L_{\Theta}^{2} \frac{\mathbf{r}^{4}}{L_{z}^{2}} + \frac{\mathbf{r}^{4}}{L_{z}^{4}} d_{x} \sigma_{\epsilon}^{2} \right) f(T) + \frac{\mathbf{r}^{4}}{L_{z}^{4}} C_{5} $$

□
## G. Regret Analysis for IV Regression: O2SLS

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

**Remark G.1.** In Appendix J, we describe that the first stage regression in O2SLS can be expressed as running d independent ridge regressions for each column of $\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$. For the rest of the paper, we use this bound for the expected value of the norm of the first stage noise.

**Theorem G.1** (Identification Regret of O2SLS). If Assumption 3.1 holds true, then for a first stage noises that is a componentwise sub-Gaussian($\sigma_{\epsilon}$) r.v., a second stage noise that is sub-Gaussian($\sigma_{\eta}$), first-stage parameters with bounded $l_2$-norm $\|\Theta\|_2 \le L_{\Theta}$, bounded IVs $\|z\|^2 \le L_z^2$ and a fixed expect value $E[\eta_s\epsilon_s] \triangleq \gamma \in \mathbb{R}^d$, the regret of O2SLS at step T is

$$ \tilde{R}_T \le \underbrace{\mathfrak{b}_{T-1}(\delta)}_{\text{Estimation}} \left( \underbrace{L_{\hat{\Theta}}^{2-1} (L_{\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}_{\text{Second Stage Feature norm}} \right) = \mathcal{O}(d^2 \log^2(T)) $$

with probability at least $1 - \delta \in [0, 1)$. Here, $\mathfrak{b}_{T-1}(\delta)$ is the confidence interval defined by Lemma 4.1, the estimates of the first-stage parameters are bounded according to Equation (14), i.e. $\|\hat{\Theta}_t^{-1}\|_2 \le L_{\hat{\Theta}}^{-1}$, $C_3$ is defined in Lemma B.2, $C_4$ in Lemma C.2, $\lambda > 0$ is the regularization parameter of the first stage and $\lambda_{\min}(\Sigma)$ is the minimum eigenvalue of the true covariance matrix of IVs, i.e. $\Sigma \triangleq E[zz^\top]$.

**Remark G.2.** In order to shorten the result and clarify the dimension d-dependence and T-dependence in Theorem 4.1, we further define $C_1 \triangleq L_{\hat{\Theta}}^{-1}L_{\Theta}L_z$, $C_2 \triangleq L_{\hat{\Theta}}^{-1}\sigma_{\epsilon}$. We also define the constants $C_3$ and $C_4$ respectively in Equation (13) and Equation (17). We define $C'_3 \triangleq C_3 + 1$ and $f(T) \triangleq (C'_3/\lambda + \log(T)/\lambda_{\min}(\Sigma)/2)$. Since these constants are d- and T-independent, and $\mathfrak{b}_{T-1}(\delta)$ is $\mathcal{O}(d \log(T))$, we obtain that the Identificaiton Regret of O2SLS is $\mathcal{O}(d^2 \log^2(T))$.

*Proof of Theorem.* We bound it (a) using the confidence bound to control the concentration of $\beta_t$ around $\beta$, and (b) by bounding the sum of feature norms according to the following decomposition.

*Step 1:* By applying Cauchy-Schwarz inequality, we first decouple the effect of parameter estimation and the feature norms

$$ (\beta_{t-1} - \beta)^{\top} x_t \le \|\beta_{t-1} - \beta\|_{\hat{\mathbf{H}}_t} \|x_t\|_{\hat{\mathbf{H}}_t^{-1}} \le \sqrt{\mathfrak{b}_{t-1}(\delta)} \|x_t\|_{(\hat{\mathbf{H}}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\mathbf{H}}_{t-1})^{-1}} \quad (20) $$

where we used the definition of $\hat{\mathbf{H}}_t \triangleq \hat{\Theta}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\mathbf{H}}_{t-1}$ and Lemma D.1. The last inequality holds with probability at least $1 - \delta$. Since $\mathfrak{b}_t$ is monotonically increasing in $t$, by Equation (20),

$$ \sum_{t=1}^{T} \left( (\beta_{t-1} - \beta)^{\top} x_t \right)^2 \le \mathfrak{b}_{T-1}(\delta) \sum_{t=1}^{T} \|x_t\|^2_{(\hat{\Theta}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\Theta}_{t-1})^{-1}}. $$

*Step 2:* Now, we need to bound the sum of the feature norms, for which we can directly use the result of Lemma C.3
## B.6 Upper bounding correlation between first and second stage noises

We start deriving a concentration result for the quantity $S_t \triangleq \sum_{s=1}^{t} \Delta\beta_{s-1}^{\top} (\epsilon_s \eta_s - \gamma)$. 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})$, by proving that $\mathbb{E}[|S_t|] \le \infty$ and $\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 + S_t. $$

**Lemma B.15 (Concentration of correlated first and second-stage noise).** Under Assumption 2.1, and for sub-Gaussian first- and second-stage noises with parameters $\sigma_{\eta}$ and $\sigma_{\epsilon}$, for given $T > 1$

$$ \left| \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} (\epsilon_t \eta_t - \gamma) \right| \le 8e^2 (\sigma_{\eta}^2 + \sigma_{\epsilon}^2) \sqrt{d_x} \frac{\tau^2}{L_z^2} \sqrt{\mathfrak{b}_{T-1}(\delta)} \left( \sqrt{2f(T) \log \frac{2}{\delta}} + \sqrt{\max \left\{ \frac{1}{\lambda}, \frac{2}{\lambda_{\min}(\Sigma)} \right\} \log \frac{2}{\delta}} \right) $$

with probability at least $1 - \delta \in [0, 1)$.

*Proof.* The proof proceeds in three steps and the main technical difficulty arises from the dependencies between the random variables, which we tackle using Lemma A.12 plus some techniques derived from the equivalent characterisations of sub-Gaussian and sub-exponential random variables [Vershynin, 2018].

**Step 1: Finding the sub-exponential parameters.** We start deriving the sub-exponential parameters for $\Delta\beta_{s-1}^{\top}(\epsilon_s \eta_s - \gamma)$.

First, we bound the p-th moment of the random variable $\phi_i \triangleq (\epsilon_{s,i} \eta_s - \gamma_i)$. This is the centred product of two sub-Gaussians non-independent random variables $\eta_s$ and $\epsilon_{s,i}$ and from Lemma A.12 is $\phi_i \sim \text{sub-exp}(\nu_i, \alpha_i)$ with $\nu_i \triangleq 4\sqrt{2}(\sigma_{\epsilon}^2 + \sigma_{\eta}^2)$, $\alpha_i \triangleq 2(\sigma_{\epsilon}^2 + \sigma_{\eta}^2)$. We can rewrite the previous sub-exponentiality condition using a unique parameter $K_1 \triangleq \max\{\alpha_i, \nu_i/\sqrt{2}\} = 4(\sigma_{\epsilon}^2 + \sigma_{\eta}^2)$ which implies $\mathbb{E}[e^{\lambda\phi_i}] \le e^{\lambda^2 K_1^2}$ for all $|\lambda| \le 1/K_1$. Using the general inequality $|x|^p \le p^p (e^x + e^{-x})$ valid for $x \in \mathbb{R}$ we obtain

$$ \mathbb{E}\left[\left|\frac{\phi_i}{K_1}\right|^p\right] \le \mathbb{E}\left[p^p \left(\exp\left(\frac{\phi_i}{K_1}\right) + \exp\left(-\frac{\phi_i}{K_1}\right)\right)\right] \le p^p 2e^{K_1^2/K_1^2} \le 2ep^p $$

The previous inequality directly implies an inequality on the p-th norm of the $\phi_i$

$$ \sqrt[p]{\mathbb{E}[|\epsilon_{s,i}\eta_s - \gamma_i|^p]} \le \sqrt[p]{2eK_1p} \le 2eK_1p = 4e(\sigma_{\epsilon}^2 + \sigma_{\eta}^2)p \triangleq K_2p \quad (26) $$

Now, we find the sub-exponential parameters for the scalar product $\Delta\beta_{s-1}^{\top}(\epsilon_s \eta_s - \gamma)$. Using the sub-exponential characterisation with $L^p$ norm that we just derived in Appendix B.6 we have $\forall p \ge 1$

$$ \|\Delta\beta_{s-1}^{\top}(\epsilon_s \eta_s - \gamma)\|_p \le \sum_{i=1}^{d} |\Delta\beta_{s-1,i}| \|\epsilon_{s,i}\eta_s - \gamma\|_p \le \sum_{i=1}^{d} |\Delta\beta_{s-1,i}| K_2 p \triangleq K_{3,s} p \quad (27) $$

where $K_{3,s} \triangleq \sum_{i=1}^{d} |\Delta\beta_{s-1,i}| K_2 = 4e(\sigma_{\epsilon}^2 + \sigma_{\eta}^2) \sum_{i=1}^{d} |\Delta\beta_{s-1,i}|$.

We are ready to bound the moment-generating function and derive the

$$ \mathbb{E} \left[ e^{\lambda \sum_{i} \Delta \beta_{s-1,i} (\epsilon_{s,i} \eta_{s} - \gamma_{i})} \mid \mathcal{F}_{s-1} \right] = \mathbb{E} \left[ \sum_{p=0}^{\infty} \frac{\lambda^p (\Delta \beta^{\top} (\epsilon_s \eta_s - \gamma))^{p}}{p!} \right] = \sum_{p=0}^{\infty} \frac{\lambda^p}{p!} \mathbb{E} \left[ (\Delta \beta^{\top} (\epsilon_s \eta_s - \gamma))^{p} \right] $$
$$ \sum_{t=1}^{T} \|x_t\|_{\hat{\Theta}_{t-1}^{-1} \mathbf{G}_{z,t-1}^{-1} \hat{\Theta}_{t-1}^{\top}}^{2} \le L_{\hat{\Theta}^{-1}}^{2} (L_{\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 \quad (21) $$

Step 3: By combining the results of the previous steps and considering the definition of $\mathfrak{b}_{T-1}(\delta)$, we conclude that we can bound the Identification Regret as follows, and its orders is $O(d^2 \log^2(T))$

$$ \sum_{t=1}^{T} \left( (\beta_{t-1} - \beta)^{\top} x_t \right)^2 \le \underbrace{\mathfrak{b}_{T-1}(\delta)}_{O(d \log T)} \underbrace{\left( L_{\hat{\Theta}^{-1}}^{2} (L_{\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 \right)}_{O(d \log T)} $$

□

**Theorem G.2 (Oracle Regret of O2SLS).** If Assumption 3.1 hold true, then for first stage noises that is componentwise sub-Gaussian($\sigma_{\epsilon}$) and second stage noise that is sub-Gaussian($\sigma_{\eta}$), first-stage parameters with bounded $l_2$-norm $\|\Theta\|_2 \le L_{\Theta}$, bounded IVs $\|z\|^2 \le L_z^2$ and bounded expect value $\mathbb{E}[\eta_s \epsilon_s] \triangleq \gamma$, the regret of O2SLS at step T is

$$ \begin{aligned} \bar{R}_T &\le \underbrace{\mathfrak{b}_{T-1}(\delta)}_{\text{Estimation}} \left( \underbrace{L_{\hat{\Theta}^{-1}}^2 (L_{\Theta}^2 L_z^2 + d\sigma_{\epsilon}^2) \left( \frac{C_3+1}{\lambda} + 2 \frac{\log(T)+1}{\lambda_{\min}(\Sigma)} + C_4 \right)}_{\text{Second Stage Feature norm}} \right) \\ &\quad + \underbrace{\sqrt{\mathfrak{b}_{T-1}(\delta)}}_{\text{Estimation}} \left( \underbrace{\sigma_{\eta} L_{\hat{\Theta}^{-1}} L_{\Theta} L_z \sqrt{\left( \frac{C_3+1}{\lambda} + 2 \frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right)}}_{\text{First Stage Feature Norm}} \right) \\ &\quad + 8e^2 (\sigma_{\eta}^2 + \sigma_{\epsilon}^2) \sqrt{dL_{\hat{\Theta}^{-1}}} \left( \sqrt{2 \log\left(\frac{2}{\delta}\right)} \left( \frac{C_3+1}{\lambda} + 2 \frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right) + \sqrt{\max\left\{\frac{1}{\lambda}, \frac{2}{\lambda_{\min}(\Sigma)}\right\}} \log\frac{2}{\delta} \right) \\ &\quad + \underbrace{\|\gamma\|_2 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} \\ \mathcal{O}(\|\gamma\|_2 \sqrt{T})}} \\ &= \mathcal{O}\left( (d \log T)^2 + \|\gamma\|_2 \sqrt{dT \log T} \right) \end{aligned} $$

with probability at least $1 - \delta \in [0, 1)$. Here, $\mathfrak{b}_{T-1}(\delta)$ is the confidence interval defined by Lemma 4.1, the estimates of the first-stage parameters are bounded according to Equation (14),
$$
\begin{align*}
&= \sum_{(c)}^{\infty} \frac{\lambda^p \mathbb{E} \left[ \left( \Delta \boldsymbol{\beta}^{\top} (\epsilon_s \eta_s - \gamma) \right)^p \right]}{p!} \le \sum_{(d)}^{\infty} \frac{\lambda^p K_{3,s}^p p^p}{p!} \\
&\le \sum_{(e)}^{\infty} \frac{\lambda^p K_{3,s}^p e^p}{p!} = \sum_{(f)}^{\infty} \frac{(\lambda K_{3,s} e)^2}{1 - \lambda K_{3,s} e} \\
&\le 1 + 2 (\lambda K_{3,s} e)^2 \le \sum_{(g)}^{\infty} e^{2\lambda^2 K_{3,s}^2 e^2}
\end{align*}
$$

where (a) is a series expansion, (b) is from the linearity of expectation, (c) comes from the first moment equal to zero, (d) is obtained by substituting Equation (27), (e) is Stirling's approximation $p! \ge \frac{p^p}{e^p}$, (f) is valid $\forall |\lambda| \le \frac{1}{K_{3,s}e}$, (g) is valid for $|\lambda| \le \frac{1}{2K_{3,s}e}$, (h) uses $1+x \le e^x \forall x \in \mathbb{R}$.

Therefore we have that $\Delta\beta_{s-1}^T(\epsilon_s\eta_s - \gamma)$ is sub-exp$(2K_{3,s}e, 2K_{3,s}e)$. We finally substitute for $K_{3,s}$ and we obtain

$$ \Delta\beta_{s-1}^T(\epsilon_s\eta_s - \gamma) \sim \text{sub-exp} \left( 8e^2 (\sigma_{\epsilon}^2 + \sigma_{\eta}^2) \|\Delta\beta_{s-1}\|_1, 8e^2 (\sigma_{\epsilon}^2 + \sigma_{\eta}^2) \|\Delta\beta_{s-1}\|_1 \right) $$

**Step 2: Concentration.** We are now ready to derive the concentration for the sum of the martingale using Theorem A.13 and we obtain $\left|\sum_{t=1}^T S_t\right| \le \sqrt{2\log(2/\delta)\sum_t \nu_s^2} + 2\alpha^* \log(2/\delta)$ with probability bigger than $1 - \delta$ where

$$
\begin{align*}
S_t &\triangleq \Delta\beta_{t-1}^{\top} (\epsilon_t \eta_t - \gamma), \\
\alpha_* &\triangleq 8e^2 (\sigma_{\epsilon}^2 + \sigma_{\eta}^2) \max_s \|\Delta\beta_{s-1}\|_1, \\
\nu_s &\triangleq 8e^2 (\sigma_{\epsilon}^2 + \sigma_{\eta}^2) \|\Delta\beta_{s-1}\|_1
\end{align*}
$$

we obtain that with probability bigger than $1 - \delta$

$$ \left| \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} (\epsilon_t \eta_t - \gamma) \right| \le \sqrt{ 2 \log \left( \frac{2}{\delta} \right) (8e^2)^2 (\sigma_{\eta}^2 + \sigma_{\epsilon}^2)^2 \sum_{t=1}^{T} \|\Delta\beta_{t-1}\|_1^2 + 8e^2 (\sigma_{\eta}^2 + \sigma_{\epsilon}^2) \max_t \|\Delta\beta_{t-1}\|_1 \log(2/\delta) } $$

**Step 3: Bounding the norms of the estimator.** We study the term $\|\Delta\beta_{t-1}\|_1$, its sum and maximum over $t$, which we need to substitute in the previous concentration bound. We can bound $\|\Delta\beta_{t-1}\|_1^2 \le d_x \|\Delta\beta_{t-1}\|_2^2$ and then use some matrix tricks in the following for the individual terms

$$
\begin{align*}
\|\Delta\beta_{t-1}\|_2^2 &= \|\hat{\mathbf{H}}^{-1/2}\hat{\mathbf{H}}^{1/2}\Delta\beta_{t-1}\|_2^2 \le \|\hat{\mathbf{H}}_{t-1}^{-1/2}\|_2^2 \|\Delta\beta_{t-1}\|_{\hat{\mathbf{H}}_{t-1}}^2 \\
&\le \|\hat{\mathbf{H}}_{t-1}^{-1}\|_2 \mathbf{b}_{t-1}(\delta) \le \frac{\mathbf{r}^4}{L_z^4} \|\mathbf{G}_{z,t-1}^{-1}\|_2 \mathbf{b}_{T-1}(\delta)
\end{align*}
$$

where (a) follows from Proposition A.7, (b) follows from the definition of the confidence ellipsoid in Equation (5) and (c) from Lemma B.12. Then, we compute the maximum and sum of these norms over T rounds.

*Sum*: When we take the sum over the rounds, we use in (a) Proposition A.7, Lemma B.12 and Lemma B.11, and in (b) Lemma B.8:

$$ \sum_{t=1}^{T} \|\Delta\beta_{t-1}\|_1^2 \le d_x \sum_{t=1}^{T} \|\Delta\beta_{t-1}\|_2^2 \le \frac{d_x \mathbf{r}^4}{L_z^4} \mathbf{b}_{T-1}(\delta) \sum_{t=1}^{T} \|\mathbf{G}_{z,t-1}^{-1}\|_2 \le \frac{d_x \mathbf{r}^4}{L_z^4} \mathbf{b}_{T-1}(\delta) f(T) $$
i.e. $\|\hat{\Theta}_t^{-1}\|_2 \le L_{\hat{\Theta}^{-1}}$, $C_3$ is defined in Lemma B.2, $C_4$ in Lemma C.2, $\lambda > 0$ is the regularization parameter of the first stage and $\lambda_{\min}(\Sigma)$ is the minimum eigenvalue of the true covariance matrix of IVs, i.e. $\Sigma \triangleq \mathbb{E}[zz^\top]$.

**Remark G.3.** In order to shorten the result and clarify the dimension d-dependence and T-dependence in Theorem 4.2, we further define $C_1 \triangleq L_{\hat{\Theta}^{-1}} L_{\Theta} L_z$, $C_2 \triangleq L_{\hat{\Theta}^{-1}} \sigma_{\epsilon}$. We also define the constants $C_3$ and $C_4$ respectively in Equation (13) and Equation (17). Finally, the 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\{\frac{1}{\lambda}, \frac{2}{\lambda_{\min}(\Sigma)}\} \log(2/\delta)}$, and $f(T) \triangleq (\frac{C_3}{\lambda} + \frac{\log(T)+1}{\lambda_{\min}(\Sigma)/2})$. We also define $\gamma \triangleq \|\gamma\|_2 = \|\mathbb{E}[\eta_s \epsilon_s]\|_2$. Since these constants are d- and T-independent, and $b_{T-1}(\delta)$ is $\mathcal{O}(d \log(T))$, we obtain that the Identificaiton Regret of $\mathcal{O}(2SLS)$ is $\mathcal{O}(d^2 \log^2(T))$ and the Oracle Regret is $\mathcal{O}(d^2 \log^2 T + \gamma \sqrt{dT \log T})$.

**Proof of Theorem.** By Equation (4), defining $\Delta\beta_{t-1} \triangleq (\beta_{t-1} - \beta)$, the instantaneous regret at step t is

$$ \begin{aligned} \bar{R}_t &\triangleq \ell_t(\beta_{t-1}) - \ell_t(\beta) = (y_t - \beta_{t-1}^\top x_t)^2 - (y_t - \beta^\top x_t)^2 \\ &= ((\beta_{t-1} - \beta)^\top x_t - \eta_t)^2 - \eta_t^2 = ((\beta_{t-1} - \beta)^\top x_t)^2 + 2\eta_t (\beta_{t-1} - \beta)^\top x_t \\ &= (\Delta\beta_{t-1}^\top x_t)^2 + 2\eta_t \Delta\beta_{t-1}^\top x_t \end{aligned} $$

Since $x_t = \Theta^\top z_t + \epsilon_t$ by (First stage), the second term can be rewritten substituting as

$$ 2\eta_t \Delta\beta_{t-1}^\top x_t = 2\eta_t \Delta\beta_{t-1}^\top \Theta^\top z_t + 2\eta_t \Delta\beta_{t-1}^\top \epsilon_t $$

Therefore, the cumulative regret or regret $\bar{R}_T$ by horizon T is

$$ \sum_{t=1}^{T} \bar{R}_t = \underbrace{\sum_{t=1}^{T} (\Delta\beta_{t-1}^{\top} x_t)^2}_{(\bullet 1)} + 2 \underbrace{\sum_{t=1}^{T} \eta_t \Delta\beta_{t-1}^{\top} \Theta^{\top} z_t}_{(\bullet 2)} + 2 \underbrace{\sum_{t=1}^{T} \eta_t \Delta\beta_{t-1}^{\top} \epsilon_t}_{(\bullet 3)} \quad (22) $$

The proof proceeds by bounding each of the three terms individually.

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

$$ (\bullet 1) \le \underbrace{b_{T-1}(\delta)}_{\mathcal{O}(d \log T)} \frac{L_{\hat{\Theta}^{-1}}^2 (L_{\Theta}^2 L_z^2 + d\sigma_{\epsilon}^2) \left( \frac{C_3+1}{\lambda} + 2 \frac{\log(T)+1}{\lambda_{\min}(\Sigma)} + C_4 \right)}{\mathcal{O}(d \log T)} = \mathcal{O}(d^2 \log^2(T)) $$

**Term 2: Coupling of First-stage Data and Second-stage Parameter Estimation.** Now, we bound $(\bullet 2)$ using martingale inequalities similar to the ones used for the confidence intervals to derive a uniform high probability bound.

**Step 1:** Following Theorem I.2, we define

$$ w_s \triangleq (\beta_{s-1} - \beta)^\top \Theta^\top z_s \quad \text{and} \quad \mathcal{F}_{t-1} \triangleq \sigma(z_1, \epsilon_1, \eta_1, \dots, z_{t-1}, \epsilon_{t-1}, \eta_{t-1}, z_t). $$

It is immediate to verify that the hypothesis are satisfied, since $w_t$ is $\mathcal{F}_{t-1}$-measurable as $\beta_{t-1}$ and $z_t$ are too. Bearing in mind this substitution we have
Maximum: For the maximum, we have instead

$$ \max_t \|\Delta\beta_{t-1}\|_1 \le \sqrt{d_x} \frac{\mathbf{r}^2}{L_{z^2}} \sqrt{\mathfrak{b}_{T-1}(\delta) \|\mathbf{G}_{z,t-1}^{-1}\|_2} \le \sqrt{d_x} \frac{\mathbf{r}^2}{L_{z^2}} \sqrt{\mathfrak{b}_{T-1}(\delta) \max\left\{\frac{1}{\lambda}, \frac{2}{\lambda_{\min}(\Sigma)}\right\}} $$

**Step 4: Assembling the results.** Finally, we can substitute back these expressions in the bound at the previous point. We have that with a probability bigger than $1 - \delta$

$$ \begin{aligned} & \left| \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} (\epsilon_t \eta_t - \gamma) \right| \\ & \le \sqrt{2 \log(2/\delta) (8e^2)^2 (\sigma_{\eta}^2 + \sigma_{\epsilon}^2)^2 d_x \frac{\mathbf{r}^4}{L_{z^4}} \mathfrak{b}_{T-1}(\delta) f(T)} \\ & \qquad + (8e^2) (\sigma_{\eta}^2 + \sigma_{\epsilon}^2) \sqrt{d_x} \frac{\mathbf{r}^2}{L_{z^2}} \sqrt{\mathfrak{b}_{T-1}(\delta) \max\left\{\frac{1}{\lambda}, \frac{2}{\lambda_{\min}(\Sigma)}\right\} \log(2/\delta)} \\ & = (8e^2) (\sigma_{\eta}^2 + \sigma_{\epsilon}^2) \sqrt{d_x} \frac{\mathbf{r}^2}{L_{z^2}} \sqrt{\mathfrak{b}_{T-1}(\delta)} \left( \sqrt{2f(T) \log \frac{2}{\delta}} + \sqrt{\max\left\{\frac{1}{\lambda}, \frac{2}{\lambda_{\min}(\Sigma)}\right\} \log \frac{2}{\delta}} \right) \end{aligned} $$

□

**Lemma B.16 (Bias of Correlated First and Second-stage Noise).** Under the same hypothesis as that of Lemma 3.3, the bias term for any $T > 1$ is bounded as

$$ \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} \gamma \le \|\gamma\|_2 \frac{\mathbf{r}^2}{L_{z^2}} \sqrt{\mathfrak{b}_{T-1}(\delta)} \left( \frac{T_0}{\sqrt{\lambda}} + 2 \frac{\sqrt{2T}}{\sqrt{\lambda_{\min}(\Sigma)}} \right) $$

*Proof.* The bias term has a much simpler analysis

$$ \begin{aligned} \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} \gamma &\le \sum_{t=1}^{T} \|\Delta\beta_{t-1}\|_{\hat{\mathbf{H}}_t} \|\gamma\|_{\hat{\mathbf{H}}_t^{-1}} \le \sum_{t=1}^{T} \|\gamma\|_{\hat{\Theta}_t^{-1} \mathbf{G}_{z,t}^{-1} \hat{\Theta}_t^{-\top}} \\ &\le \sqrt{\mathfrak{b}_{T-1}(\delta)} \|\gamma\|_2 \sum_{t=1}^{T} \sqrt{\frac{\mathbf{r}^4}{L_{z^4}} \|\mathbf{G}_{z,t-1}^{-1}\|_2} \\ &\le \|\gamma\|_2 \frac{\mathbf{r}^2}{L_{z^2}} \sqrt{\mathfrak{b}_{T-1}(\delta)} \left( \sum_{t=1}^{T_0} \frac{1}{\sqrt{\lambda}} + \sum_{t=T_0+1}^{T-1} \sqrt{\frac{2}{\lambda_{\min}(\Sigma)t}} \right) \\ &\le \|\gamma\|_2 \frac{\mathbf{r}^2}{L_{z^2}} \sqrt{\mathfrak{b}_{T-1}(\delta)} \left( \frac{T_0}{\sqrt{\lambda}} + 2 \frac{\sqrt{2T}}{\sqrt{\lambda_{\min}(\Sigma)}} \right) \end{aligned} $$

where in (a) we used Cauchy-Schwarz, in (b) Lemma 3.3 and monontonicty of $\mathfrak{b}_t$, in (c) Proposition A.7, in (d) Lemma B.8 and finally in the last inequality follows from $\sum_{k=1}^n \frac{1}{\sqrt{k}} = \sum_{k=1}^n \int_{k-1}^k \frac{dx}{\sqrt{k}} \le \sum_{k=1}^n \int_{k-1}^k \frac{dx}{\sqrt{x}} = \int_0^n \frac{dx}{\sqrt{x}} = 2\sqrt{n}$. □
$$ \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)} \quad (23) $$

with probability at least $1 - \delta$.

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

$$ \sum_{t=1}^{T} \langle \beta_{t-1} - \beta, \Theta^{\top} z_t \rangle^2 \le b_{T-1}(\delta) \sum_{t=1}^{T} \|\Theta^{\top} z_t\|_{(\hat{\Theta}_{t-1}^{\top} G_{z,T-1} \hat{\Theta}_{t-1})^{-1}}^2 \quad \text{(Cauchy-Schwarz and Lemma D.1)} $$

$$ \le b_{T-1}(\delta) \sum_{t=1}^{T} \|G_{z,t-1}^{-1}\|_2 \|\hat{\Theta}_{t-1}^{-1}\|_2^2 \|\Theta^{\top} z_t\|_2^2 \quad \text{(Proposition A.1)} $$

$$ \le b_{T-1}(\delta) L_{\hat{\Theta}^{-1}}^2 \sum_{t=1}^{T} \|G_{z,t-1}^{-1}\|_2 \|\Theta\|_2^2 \|z_t\|_2^2 \quad \text{(Proposition A.1 and definition of } L_{\hat{\Theta}^{-1}}^2 \text{)} $$

$$ \le b_{T-1}(\delta) L_{\hat{\Theta}^{-1}}^2 L_{\Theta}^2 L_z^2 \sum_{t=1}^{T} \|G_{z,t-1}^{-1}\|_2 \quad \text{(boundedness of } z_t \text{ and definition of } L_{\Theta}) $$

$$ = \underbrace{b_{T-1}(\delta)}_{\mathcal{O}(d \log T)} \underbrace{L_{\hat{\Theta}^{-1}}^2 L_{\Theta}^2 L_z^2 \left( \frac{C_3+1}{\lambda} + 2 \frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right)}_{\mathcal{O}(\log T)} \quad \text{(from Lemma B.2)} $$

where in the first inequality we also used the fact that $b_{t-1}(\delta)$ is monotonically increasing in $t$, to take the radii outside the summation.

Step 3: Thus, substituting inside Equation (23), the order of (•2•) is negligible with respect to term (•1•)

$$ 2 \sum_{t=1}^{T} \eta_t (\beta_{t-1} - \beta)^{\top} \Theta^{\top} z_t \le \underbrace{\sqrt{2 \left( 1 + b_{T-1}(\delta) \sigma_{\eta}^2 L_{\hat{\Theta}^{-1}}^2 L_{\Theta}^2 L_z^2 \left( \frac{C_3+1}{\lambda} + 2 \frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right) \right)}}_{\mathcal{O}(\sqrt{d \log T})} \underbrace{\sqrt{\log \left( \sqrt{1 + b_{T-1}(\delta) \sigma_{\eta}^2 L_{\hat{\Theta}^{-1}}^2 L_{\Theta}^2 L_z^2 \left( \frac{C_3+1}{\lambda} + 2 \frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right)} / \delta \right)}}_{\mathcal{O}(\sqrt{\log(\sqrt{d \log T})})} = \mathcal{O}\left(\sqrt{d \log T} \sqrt{\log(\sqrt{d \log T})}\right) $$

with probability at least $1 - \delta$.
## B.7 Upper bounding the identification regret of O2SLS

In this section, we analyse the identification regret of O2SLS, and derive a high-probability upper bound on it.

**Theorem 3.4 (Identification regret of O2SLS).** If Assumption 2.1 holds true, first-stage noise is a component-wise sub-Gaussian($\sigma_{\epsilon}$) r.v., second-stage noise is also sub-Gaussian($\sigma_{\eta}$), the true first-stage parameter has bounded $l_2$-norm $\|\Theta\|_2 \le L_{\Theta}$, IVs are bounded $\|z\|^2 \le L_z^2$, and a two-stage correlation level $\mathbb{E}[\eta_s \epsilon_s] \triangleq \gamma \in \mathbb{R}^d$, the regret of O2SLS at step T is

$$ \tilde{R}_T \le \underbrace{\mathfrak{b}_{T-1}(\delta)}_{\text{Estimation}} \frac{\left( \left( L_{\Theta}^2 \frac{\mathfrak{r}^4}{L_z^2} + \frac{\mathfrak{r}^4}{L_z^4} d_x \sigma_{\epsilon}^2 \right) f(T) + \frac{\mathfrak{r}^4}{L_z^4} C_5 \right)}_{\text{Second-stage feature norm}} = \mathcal{O}(d_x d_z \log^2 T). $$

with probability at least $1 - \delta \in [0, 1)$. Here, $\mathfrak{b}_{T-1}(\delta)$ is the confidence interval defined by Lemma 3.3, $f(T)$ is defined in Corollary B.9, $C_5$ in Lemma B.13.

**Proof of Theorem 3.4.** We bound it (a) using the confidence bound to control the concentration of $\beta_t$ around $\beta$, and (b) by bounding the sum of feature norms according to the following decomposition.

**Step 1:** By applying Cauchy-Schwarz inequality, we first decouple the effect of parameter estimation and the feature norms

$$ (\beta_{t-1} - \beta)^{\top} x_t \le \|\beta_{t-1} - \beta\|_{\hat{\mathbf{H}}_t} \|x_t\|_{\hat{\mathbf{H}}_t^{-1}} \le \sqrt{\mathfrak{b}_{t-1}(\delta)} \|x_t\|_{\hat{\mathbf{H}}_t^{-1}} \quad (28) $$

The above inequality is due to Lemma 3.3, and holds with probability at least $1 - \delta$. Since $\mathfrak{b}_t$ is monotonically increasing in $t$, by Equation (28),

$$ \sum_{t=1}^{T} \left( (\beta_{t-1} - \beta)^{\top} x_t \right)^2 \le \mathfrak{b}_{T-1}(\delta) \sum_{t=1}^{T} \|x_t\|_{\hat{\mathbf{H}}_t^{-1}}^2. $$

**Step 2:** Now, we need to bound the sum of the feature norms, for which we can directly use the result of Lemma B.14

$$ \sum_{t=1}^{T} \|x_t\|_{\hat{\mathbf{H}}_t^{-1}}^2 \le \left( L_{\Theta}^2 \frac{\mathfrak{r}^4}{L_z^2} + \frac{\mathfrak{r}^4}{L_z^4} d_x \sigma_{\epsilon}^2 \right) f(T) + \frac{\mathfrak{r}^4}{L_z^4} C_5 = \mathcal{O}(d_x \log T) $$

**Step 3:** By combining the results of the previous steps and considering the definition of $\mathfrak{b}_{T-1}(\delta)$, we conclude that we can bound the Identification Regret as follows, and its orders is $\mathcal{O}(d_x d_z \log^2(T))$

$$ \sum_{t=1}^{T} \left( (\beta_{t-1} - \beta)^{\top} x_t \right)^2 \le \underbrace{\mathfrak{b}_{T-1}(\delta)}_{d_z \log T} \underbrace{\left( \left( L_{\Theta}^2 \frac{\mathfrak{r}^4}{L_z^2} + \frac{\mathfrak{r}^4}{L_z^4} d_x \sigma_{\epsilon}^2 \right) f(T) + \frac{\mathfrak{r}^4}{L_z^4} C_5 \right)}_{d_x \log T} = \mathcal{O}(d_z d_x \log^2 T). $$

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

$$
\begin{align}
\sum_{t=1}^{T} \eta_t (\underbrace{\beta_{t-1} - \beta}_{\Delta\beta_{t-1}})^{\top} \epsilon_t &= \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} (\epsilon_t \eta_t) + \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} \mathbb{E}_t [\epsilon_t \eta_t] - \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} \mathbb{E}_t [\epsilon_t \eta_t] \nonumber \\
&= \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} \epsilon_t \eta_t - \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} \gamma + \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} \gamma \nonumber \\
&= \underbrace{\sum_{t=1}^{T} \Delta\beta_{t-1}^{T} (\epsilon_t n_t - \gamma)}_{\text{Martingale Concentration Term} \mathcal{O}(\log(T))} + \underbrace{\sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} \gamma}_{\text{Bias Term} \mathcal{O}(\sqrt{T})} \tag{24}
\end{align}
$$

Now we can use Lemma F.2 and Lemma F.3 to conclude that term (•3•) is bounded by the following quantity

$$
\begin{align*}
& \underbrace{8e^2 (\sigma_{\eta}^2 + \sigma_{\epsilon}^2) L_{\hat{\Theta}^{-1}} \sqrt{d \mathfrak{b}_{T-1}(\delta)} \left( \sqrt{2 \log\left(\frac{2}{\delta}\right) \left( \frac{C_3+1}{\lambda} + 2 \frac{\log(T)+1}{\lambda_{\min}(\Sigma)} \right)} + \sqrt{\max\left\{\frac{1}{\lambda}, \frac{2}{\lambda_{\min}(\Sigma)}\right\}} \log \frac{2}{\delta} \right)}_{d \log(T)} \\
& \qquad + \underbrace{\sqrt{\mathfrak{b}_{T-1}(\delta)} \|\gamma\|_2 L_{\hat{\Theta}^{-1}} \left( \frac{C_3}{\sqrt{\lambda}} + 2 \frac{\sqrt{2T}}{\sqrt{\lambda_{\min}(\Sigma)}} \right)}_{\mathcal{O}(\|\gamma\|_2 \sqrt{dT \log T})}
\end{align*}
\hfill \square
$$

<figure><img src="image_5.png" /></figure>
## B.8 Upper bounding the oracle regret of O2SLS

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

**Theorem 3.5 (Oracle regret of O2SLS).** Under the same assumptions of Theorem 3.4, the oracle regret of O2SLS at step $T > 1$ is upper bounded by

$$ \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{\left(C_1 \sqrt{f(T)}\right)}_{\substack{\text{First-stage} \\ \text{feature norm}}} + \underbrace{\left(C_2 \sqrt{2d_x f(T)}\right)}_{\substack{\text{Correlated noise} \\ \text{Concentration term}}} + \underbrace{\sqrt{d_x C_3}}_{\substack{\text{Correlated noise} \\ \mathcal{O}(\sqrt{d_x \log T})}} + \underbrace{\gamma C_4 \sqrt{T}}_{\substack{\text{Bias term} \\ \mathcal{O}(\gamma \sqrt{T})}} \right) $$

with probability at least $1 - \delta \in (0, 1)$. Here, $\mathfrak{b}_{T-1}(\delta)$ is the confidence interval defined by Lemma 3.3, $f(T)$ is defined in Corollary B.9, $C_5$ in Lemma B.13, $\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.

*Proof.* Using Equation (4), and defining $\Delta\beta_{t-1} \triangleq (\beta_{t-1} - \beta)$, the instantaneous regret at step $t$ is

$$ \begin{aligned} \bar{r}_t &\triangleq \ell_t(\beta_{t-1}) - \ell_t(\beta) = (y_t - \beta_{t-1}^\top x_t)^2 - (y_t - \beta^\top x_t)^2 \\ &= ((\beta_{t-1} - \beta)^\top x_t - \eta_t)^2 - \eta_t^2 = ((\beta_{t-1} - \beta)^\top x_t)^2 + 2\eta_t (\beta_{t-1} - \beta)^\top x_t \\ &= (\Delta\beta_{t-1}^\top x_t)^2 + 2\eta_t \Delta\beta_{t-1}^\top x_t \end{aligned} $$

Since $x_t = \Theta^\top z_t + \epsilon_t$ by (First stage), the second term can be rewritten substituting as

$$ 2\eta_t \Delta\beta_{t-1}^\top x_t = 2\eta_t \Delta\beta_{t-1}^\top \Theta^\top z_t + 2\eta_t \Delta\beta_{t-1}^\top \epsilon_t $$

Therefore, the cumulative oracle regret $\bar{R}_T$ by horizon $T$ is

$$ \bar{R}_T = \sum_{t=1}^{T} \bar{r}_t = \underbrace{\sum_{t=1}^{T} (\Delta\beta_{t-1}^{\top} x_t)^2}_{(\bullet 1 \bullet)} + 2 \underbrace{\sum_{t=1}^{T} \eta_t \Delta\beta_{t-1}^{\top} \Theta^{\top} z_t}_{(\bullet 2 \bullet)} + 2 \underbrace{\sum_{t=1}^{T} \eta_t \Delta\beta_{t-1}^{\top} \epsilon_t}_{(\bullet 3 \bullet)} \quad (29) $$

The proof proceeds by bounding each of the three terms individually.

**Term 1: Second-stage regression error.** The first term $(\bullet 1 \bullet)$ quantifies the error introduced by the second stage regression. This is exactly equal to the identification regret. Thus, by Theorem 3.4,

$$ (\bullet 1 \bullet) \le \underbrace{\mathfrak{b}_{T-1}(\delta)}_{d_z \log T} \left( \underbrace{\left( \left( L_{\Theta}^2 \frac{\mathfrak{r}^4}{L_z^2} + \frac{\mathfrak{r}^4}{L_z^4} d_x \sigma_{\epsilon}^2 \right) f(T) + \frac{\mathfrak{r}^4}{L_z^4} C_5 \right)}_{d_x \log T} \right) = \mathcal{O}(d_x d_z \log^2 T). $$

**Term 2: Coupling of first-stage features and second-stage parameter estimation.**

Now, we bound $(\bullet 2 \bullet)$ using martingale inequalities similar to the ones used for the confidence intervals to derive a uniform high probability bound.

*Step 1:* Following Theorem A.16, we define

$$ w_s \triangleq (\beta_{s-1} - \beta)^\top \Theta^\top z_s \quad \text{and} \quad \mathcal{F}_{t-1} \triangleq \sigma(z_1, \epsilon_1, \eta_1, \dots, z_{t-1}, \epsilon_{t-1}, \eta_{t-1}, z_t). $$

It is immediate to verify that the hypothesis are satisfied, since $w_t$ is $\mathcal{F}_{t-1}$-measurable as $\beta_{t-1}$ and $z_t$ are too. Bearing in mind this substitution we have
## H. Regret Analysis for IV Linear Bandits: OFUL-IV

**Theorem H.1.** Under the same assumptions as that of Theorem 4.2, Algorithm 2 incurs a regret

$$R_T = \sum_{t=1}^{T} r_t \le 2\sqrt{T} \sqrt{\mathfrak{b}_{T-1}(\delta)} \sqrt{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}$$

with probability $1 - \delta$, horizon $T > 1$ and $C_4$ is defined in eq. (17).

*Proof.* The instantaneous regret $r_t$ reads

$$\langle \beta, x_* \rangle - \langle \beta, x_t \rangle \le \langle \tilde{\beta}_{t-1}, x_t \rangle - \langle \beta, x_t \rangle \quad (\text{since } (x_t, \tilde{\beta}_{t-1}) \text{ is optimistic inside } \mathcal{X}_t \times \mathcal{B}_t)$$

$$= \langle \beta_{t-1} - \beta, x_t \rangle + \langle \tilde{\beta}_{t-1} - \beta_{t-1}, x_t \rangle \quad (\text{summing and subtracting } \beta_{t-1})$$

$$\le \|\beta_{t-1} - \beta\|_{\hat{\Theta}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\Theta}_{t-1}} \|\mathbf{x}_t\|_{(\hat{\Theta}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\Theta}_{t-1})^{-1}} \\ + \|\tilde{\beta}_{t-1} - \beta_{t-1}\|_{\hat{\Theta}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\Theta}_{t-1}} \|\mathbf{x}_t\|_{(\hat{\Theta}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\Theta}_{t-1})^{-1}} \quad (\text{Cauchy-schwarz ineq.})$$

$$\le 2\sqrt{\mathfrak{b}_{t-1}(\delta)} \|\mathbf{x}_t\|_{(\hat{\Theta}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\Theta}_{t-1})^{-1}} \quad (\text{Lemma D.1})$$

The last inequality uses the concentration of $\beta_t$ around the true value $\beta$, and the fact that we choose $\tilde{\beta}_{t-1}$ inside $\mathcal{B}_{t-1}$. In both cases, the two norms are bounded by the radius of the ellipsoid, i.e. $\sqrt{\mathfrak{b}_{t-1}(\delta)}$. Since we already know in this case how to concentrate the sum of the features norms $\sum_{t=1}^T \|\mathbf{x}_t\|_{\hat{\Theta}_{t-1}^{-1} \mathbf{G}_{z,t-1}^{-1} \hat{\Theta}_{t-1}}^2$ from Lemma C.3, we bound the cumulative regret using Cauchy-Schwarz inequality in the first inequality below, and we substitute the bound on the instantaneous regret that we just obtained:

$$R_T \le \sqrt{T \sum_{t=1}^T r_t^2} \le 2 \sqrt{T \sum_{t=1}^T \mathfrak{b}_{t-1}(\delta) \|\mathbf{x}_t\|_{\hat{\Theta}_{t-1}^{-1} \mathbf{G}_{z,t-1}^{-1} \hat{\Theta}_{t-1}}^2} \\ \le 2\sqrt{T} \sqrt{\mathfrak{b}_{T-1}(\delta)} \sqrt{\sum_{t=1}^T \|\mathbf{x}_t\|_{\hat{\Theta}_{t-1}^{-1} \mathbf{G}_{z,t-1}^{-1} \hat{\Theta}_{t-1}}^2} \quad (25)$$

where in the second inequality, we used the fact that the radius $\mathfrak{b}_{t-1}(\delta)$ is monotonically increasing in $t$. Now, we can use Lemma C.3 to bound the sum of feature norms, and putting all together, we obtain the following bound:

$$R_T \le 2\sqrt{T} \underbrace{\sqrt{\mathfrak{b}_{T-1}(\delta)}}_{\mathcal{O}(\sqrt{d \log T})} \overbrace{\sqrt{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}}_{\mathcal{O}(\sqrt{d \log T})} = \mathcal{O}(d\sqrt{T} \log T). \quad \square$$
$$ \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)} \quad (30) $$

with probability at least $1 - \delta$.

**Step 2:** Now, the problem reduces to upper bounding $\sum_{t=1}^{T} w_t^2$. We proceed like for the first term in the Step 2 for **Term 1**:

$$ \begin{aligned} \sum_{t=1}^{T} w_t^2 = \sum_{t=1}^{T} \langle \beta_{t-1} - \beta, \mathbf{\Theta}^{\top} \mathbf{z}_t \rangle^2 &\le \sum_{t=1}^{T} \mathfrak{b}_{t-1}(\delta) \| \mathbf{\Theta}^{\top} \mathbf{z}_t \|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2 \\ &\le \mathfrak{b}_{T-1}(\delta) \sum_{t=1}^{T} \| \mathbf{\Theta}^{\top} \mathbf{z}_t \|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2 \\ &\le \mathfrak{b}_{T-1}(\delta) \frac{L_{\mathbf{\Theta}}^2 \mathbf{r}^4}{L_z^2} \sum_{t=1}^{T} \frac{1}{\lambda_{\min}(\mathbf{G}_{\mathbf{z},t-1})} \\ &\le \mathfrak{b}_{T-1}(\delta) \frac{L_{\mathbf{\Theta}}^2 \mathbf{r}^4}{L_z^2} f(T) = \mathcal{O} (d_z \log^2 T). \end{aligned} $$

where (a) comes from Cauchy-Schwarz and Lemma 3.3, (b) from monotonicity of $\mathfrak{b}_{t-1}(\delta)$ and (c) from Equation (25).

**Step 3:** Thus, substituting the bound of Step 2 into Equation (30), we obtain

$$ \begin{aligned} 2 \sum_{t=1}^{T} \eta_t (\beta_{t-1} - \beta)^{\top} \mathbf{\Theta}^{\top} \mathbf{z}_t &\le \underbrace{\sqrt{2 \left( 1 + \sigma_{\eta}^2 \mathfrak{b}_{T-1}(\delta) \frac{L_{\mathbf{\Theta}}^2 \mathbf{r}^4}{L_z^2} f(T) \right)}}_{\mathcal{O}(\sqrt{d_z \log T})} \underbrace{\sqrt{\log \left( \delta^{-1} \sqrt{1 + \sigma_{\eta}^2 \mathfrak{b}_{T-1}(\delta) \frac{L_{\mathbf{\Theta}}^2 \mathbf{r}^4}{L_z^2} f(T)} \right)}}_{\mathcal{O}(\sqrt{\log(\sqrt{d_z \log T})})} \\ &= \mathcal{O} \left( \sqrt{d_z \log T} \sqrt{\log(\sqrt{d_z \log T})} \right) \end{aligned} $$

with probability at least $1 - \delta$.

Thus, the order of (•2•) is negligible with respect to term (•1•).

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

$$ \begin{aligned} \sum_{t=1}^{T} \eta_t (\underbrace{\beta_{t-1} - \beta}_{\Delta\beta_{t-1}})^{\top} \epsilon_t &= \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} (\epsilon_t \eta_t) + \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} \mathbb{E}_t [\epsilon_t \eta_t] - \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} \mathbb{E}_t [\epsilon_t \eta_t] \\ &= \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} \epsilon_t \eta_t - \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} \gamma + \sum_{t=1}^{T} \Delta\beta_{t-1}^{\top} \gamma \\ &= \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}} \end{aligned} \quad (31) $$
# I. Concentration of Scalar and Vector-valued Martingales

We look for deviations of the vector martingales $\sum_{s=1}^{t} \eta_s z_s$ and the scalar valued martingale

$$ \sum_{t=1}^{T} \eta_t (\beta_{t-1} - \beta)^{\top} \Theta^{\top} z_t $$

from their expected values. These results are required in the proof of Theorem G.2. The first martingale is vector-valued while the second is scalar-valued. For the vector-valued martingale, we want to bound its deviations when its values are weighted by the inverse of its design matrix $G_{z,t}^{-1}$ like it appears in $\|s_t\|_{G_{z,t}^{-1}}^2$. The design matrix $G_{z,t}^{-1}$ is itself derived from the martingale. Hence, it is called the ‘self-normalized bound’. The following theorems were introduced in (Abbasi-Yadkori et al., 2011a, 2012) for the two cases. We state and prove them here for completeness. We leverage the fact that the first and second stage noises are sub-Gaussian random variables.

**Lemma I.1.** Let $\mu \in \mathbb{R}^d$ be arbitrary and consider for any $t \ge 0$

$$ m_t^{\mu} \triangleq \prod_{s=1}^{t} \exp \left( \frac{\eta_s \langle \mu, z_s \rangle}{\sigma_2} - \frac{1}{2} \langle \mu, z_s \rangle^2 \right). $$

Let $\tau$ be a stopping time with respect to the filtration $\{\mathcal{F}_t\}_{t=0}^{\infty}$. Then, $m_{\tau}^{\mu}$ is a.s. well-defined and $\mathbb{E}[m_{\tau}^{\mu}] \le 1$.

*Proof.* We claim that $\{m_t^{\mu}\}_{t=0}^{\infty}$ is a supermartingale. Let

$$ d_t^{\mu} \triangleq \exp \left( \frac{\eta_t \langle \mu, z_t \rangle}{\sigma_2} - \frac{1}{2} \langle \mu, z_t \rangle^2 \right). $$

Observe that by conditional R-sub-Gaussianity of $\eta_t$ we have $\mathbb{E}[d_t^{\mu} | \mathcal{F}_{t-1}] \le 1$. Clearly, $d_t^{\mu}$ is $\mathcal{F}_t$-measurable, as is $m_t^{\mu}$. Further,

$$ \mathbb{E}[m_t^{\mu} | \mathcal{F}_{t-1}] = \mathbb{E}[m_1^{\mu} \cdots d_{t-1}^{\mu} d_t^{\mu} | \mathcal{F}_{t-1}] = d_1^{\mu} \cdots d_{t-1}^{\mu} \mathbb{E}[d_t^{\mu} | \mathcal{F}_{t-1}] \le m_{t-1}^{\mu}, $$

showing that $\{m_t^{\mu}\}_{t=0}^{\infty}$ is indeed a supermartingale and in fact $\mathbb{E}[m_t^{\mu}] \le 1$.

Now, we argue that $m_{\tau}^{\mu}$ is well-defined. By the convergence theorem for nonnegative supermartingales, $M_{\infty}^{\mu} = \lim_{t \to \infty} m_t^{\mu}$ is almost surely well-defined. Hence, $m_{\tau}^{\mu}$ is indeed well-defined independently of whether $\tau < \infty$ holds or not. Next, we show that $\mathbb{E}[m_{\tau}^{\mu}] \le 1$. For this let $Q_t^{\mu} = M_{\min\{\tau,t\}}^{\mu}$ be a stopped version of $(m_t^{\mu})_{t}$. By Fatou's Lemma, $\mathbb{E}[m_{\tau}^{\mu}] = \mathbb{E}[\liminf_{t \to \infty} Q_t^{\mu}] \le \liminf_{t \to \infty} \mathbb{E}[Q_t^{\mu}] \le 1$, showing that $\mathbb{E}[m_{\tau}^{\mu}] \le 1$ indeed holds. $\square$

Next lemma uses the “method of mixtures” technique, (Lattimore and Szepesvári, 2020) Chapter 20.

**Lemma I.2.** Let $\{\mathcal{F}_t\}_{t=0}^{\infty}$ be a filtration. Let $\tau$ be a stopping time with respect to the filtration $\{\mathcal{F}_t\}_{t=0}^{\infty}$. Then, for any $\delta > 0$, with probability $1 - \delta$

$$ \|s_{\tau}\|_{G_{z,\tau}^{-1}}^2 \le 2\sigma_2^2 \log \left( \frac{\det(G_{z,\tau})^{1/2} \lambda^{-d/2}}{\delta} \right). $$
Now we can use Lemma B.15 and Lemma B.16 to conclude that term (•3•) is bounded by the following quantity

$$
\sum_{t=1}^{T} \eta_t (\underbrace{\beta_{t-1} - \beta}_{\Delta\beta_{t-1}})^{\top} \epsilon_t \\
\le 8e^2 (\sigma_{\eta}^2 + \sigma_{\epsilon}^2) \sqrt{d_x} \frac{\mathbf{r}^2}{L_z^2} \sqrt{\mathfrak{b}_{T-1}(\delta)} \left( \sqrt{2f(T) \log(2/\delta)} + \sqrt{\max\left\{\frac{1}{\lambda}, \frac{2}{\lambda_{\min}(\Sigma)}\right\} \log(2/\delta)} \right) \\
\underbrace{+ \|\gamma\|_2 \frac{\mathbf{r}^2}{L_z^2} \sqrt{\mathfrak{b}_T(\delta)} \left( \frac{T_0}{\sqrt{\lambda}} + 2 \frac{\sqrt{2T}}{\sqrt{\lambda_{\min}(\Sigma)}} \right)}_{\mathcal{O}(\|\gamma\|_2 \sqrt{d_x T \log T})} \\
$$

Final Step: Assembling the Results. Thus, by assembling the upper bounds on the three
terms, we get

$$
\begin{align*}
\bar{R}_T &= \sum_{t=1}^{T} \bar{r}_t \\
&\le \underbrace{\frac{\mathfrak{b}_{T-1}(\delta)}{d_z \log T} \left( \underbrace{\left( \left( \frac{L_{\Theta}^2 \mathbf{r}^4}{L_z^2} + \frac{\mathbf{r}^4}{L_z^4} d_x \sigma_{\epsilon}^2 \right) f(T) + \frac{\mathbf{r}^4}{L_z^4} C_5 \right)}_{d_x \log T} \right)}_{\mathcal{O}(\sqrt{d_z \log T})} \\
&\quad + \underbrace{\sqrt{2 \left( 1 + \sigma_{\eta}^2 \mathfrak{b}_{T-1}(\delta) \frac{L_{\Theta}^2 \mathbf{r}^4}{L_z^2} f(T) \right)}_{\mathcal{O}(\sqrt{d_z \log T})} \underbrace{\sqrt{\log \left( \delta^{-1} \sqrt{1 + \sigma_{\eta}^2 \mathfrak{b}_{T-1}(\delta) \frac{L_{\Theta}^2 \mathbf{r}^4}{L_z^2} f(T)} \right)}}_{\mathcal{O}(\sqrt{\log(\sqrt{d_z \log T})})} \\
&\quad + 8e^2 (\sigma_{\eta}^2 + \sigma_{\epsilon}^2) \sqrt{d_x} \frac{\mathbf{r}^2}{L_z^2} \sqrt{\mathfrak{b}_{T-1}(\delta)} \underbrace{\left( \sqrt{2f(T) \log \frac{2}{\delta}} + \sqrt{\max\left\{\frac{1}{\lambda}, \frac{2}{\lambda_{\min}(\Sigma)}\right\} \log \frac{2}{\delta}} \right)}_{\mathcal{O}(\sqrt{d_x d_z \log(T)})} \\
&\quad + \underbrace{\|\gamma\|_2 \frac{\mathbf{r}^2}{L_z^2} \sqrt{\mathfrak{b}_{T-1}(\delta)} \left( \frac{T_0}{\sqrt{\lambda}} + 2 \frac{\sqrt{2T}}{\sqrt{\lambda_{\min}(\Sigma)}} \right)}_{\mathcal{O}(\|\gamma\|_2 \sqrt{d_z T \log T})} \\
&\le \underbrace{\mathfrak{b}_{T-1}(\delta) \left( \left( \frac{L_{\Theta}^2 \mathbf{r}^4}{L_z^2} + \frac{\mathbf{r}^4}{L_z^4} d_x \sigma_{\epsilon}^2 \right) f(T) + \frac{\mathbf{r}^4}{L_z^4} C_5 \right)}_{(a)} \\
&\quad + \sqrt{\mathfrak{b}_{T-1}(\delta)} \left( C_1 \sqrt{f(T)} + C_2 \sqrt{2d_x f(T)} + T_0 \sqrt{d_x} + \|\gamma\|_2 C_4 \sqrt{T} \right) \\
&= \underbrace{\mathcal{O}(\mathfrak{b}_{T-1}(\delta) d_x f(T))}_{\substack{\text{Identification} \\ \text{Regret} \\ \mathcal{O}(d_x d_z \log^2 T)}} + \underbrace{\sqrt{\mathfrak{b}_{T-1}(\delta)} \left( \underbrace{C_1 \sqrt{f(T)}}_{\substack{\text{First-stage} \\ \text{feature norm} \\ \mathcal{O}(\sqrt{\log T})}} + \underbrace{C_2 \sqrt{2d_x f(T)} + \sqrt{d_x} C_3}_{\substack{\text{Correlated noise} \\ \text{Concentration term} \\ \mathcal{O}(\sqrt{d_x \log T})}} + \underbrace{\gamma C_4 \sqrt{T}}_{\substack{\text{Correlated noise} \\ \text{Bias term} \\ \mathcal{O}(\gamma \sqrt{T})}} \right)
\end{align*}
$$

For simpler presentation of the result, we ignore the log log terms and define in inequality (a)
the constants

$$
C_1 \triangleq \sqrt{2 \left( 1 + \sigma_{\eta}^2 \frac{L_{\Theta}^2 \mathbf{r}^4}{L_z^2} \right)}
$$
*Proof.* We decompose $G_{z,t}$ according to the following notation in order to ease the notation

$$G_{z,t} \triangleq \lambda \mathbb{I}_d + \sum_{s=1}^{t} z_s z_s^\top = \mathbf{V} + \mathbf{V}_t$$

where $\mathbf{V}$ and $\mathbf{V}_t$ are defined by $\mathbf{V} \triangleq \lambda \mathbb{I}_d$ and $\mathbf{V}_t \triangleq \sum_{s=1}^t z_s z_s^\top$. We can rewrite for example $m_t^\mu$ as follows $m_t^\mu = \exp\left(\frac{\langle \mu, s_t \rangle}{\sigma_2} - \frac{1}{2} \|\mu\|_{\mathbf{V}_t}^2\right)$.

Let $\mu$ be a Gaussian random variable which is independent of all the other random variables and whose covariance is $\mathbf{V}^{-1}$. Define

$$m_t \triangleq \mathbb{E}[m_t^\mu | \mathcal{F}_\infty],$$

where $\mathcal{F}_\infty$ is the tail $\sigma$-algebra of the filtration i.e. the $\sigma$-algebra generated by the union of the all events in the filtration. Clearly, we still have $\mathbb{E}[m_\tau] = \mathbb{E}[\mathbb{E}[m_\tau^\mu | \mu]] \le 1$. Let us calculate $m_t$. Let $f$ denote the density of $\mu$ and for a positive definite matrix $\mathbf{P}$ let $c(\mathbf{P}) = \sqrt{(2\pi)^d/\det(\mathbf{P})} = \int \exp(-\frac{1}{2}\mathbf{x}^\top \mathbf{P} \mathbf{x}) d\mathbf{x}$. Then,

$$\begin{aligned}
m_t &= \int_{\mathbb{R}^d} \exp\left(\langle \mu, s_t \rangle - \frac{1}{2} \|\mu\|_{\mathbf{V}_t}^2\right) f(\mu) d\mu \\
&= \int_{\mathbb{R}^d} \exp\left(-\frac{1}{2} \|\mu - \mathbf{V}_t^{-1} s_t\|_{\mathbf{V}_t}^2 + \frac{1}{2} \|s_t\|_{\mathbf{V}_t^{-1}}^2\right) f(\mu) d\mu \\
&= \frac{1}{c(\mathbf{V})} \exp\left(\frac{1}{2} \|s_t\|_{\mathbf{V}_t^{-1}}^2\right) \int_{\mathbb{R}^d} \exp\left(-\frac{1}{2} \left\{\|\mu - \mathbf{V}_t^{-1} s_t\|_{\mathbf{V}_t}^2 + \|\mu\|_{\mathbf{V}}^2\right\}\right) d\mu
\end{aligned}$$

Elementary calculation shows that if $\mathbf{P}$ is positive semi-definite and $\mathbf{Q}$ is positive definite

$$\|\mathbf{x} - \mathbf{a}\|_{\mathbf{P}}^2 + \|\mathbf{x}\|_{\mathbf{Q}}^2 = \|\mathbf{x} - (\mathbf{P} + \mathbf{Q})^{-1}\mathbf{P}\mathbf{a}\|_{\mathbf{P}+\mathbf{Q}}^2 + \|\mathbf{a}\|_{\mathbf{P}}^2 - \|\mathbf{P}\mathbf{a}\|_{(\mathbf{P}+\mathbf{Q})^{-1}}^2.$$

Therefore,

$$\begin{aligned}
\|\mu - \mathbf{V}_t^{-1} s_t\|_{\mathbf{V}_t}^2 + \|\mu\|_{\mathbf{V}}^2 &= \|\mu - (\mathbf{V} + \mathbf{V}_t)^{-1} s_t\|_{\mathbf{V}+\mathbf{V}_t}^2 + \|\mathbf{V}_t^{-1} s_t\|_{\mathbf{V}_t}^2 - \|s_t\|_{(\mathbf{V}+\mathbf{V}_t)^{-1}}^2 \\
&= \|\mu - (\mathbf{V} + \mathbf{V}_t)^{-1} s_t\|_{\mathbf{V}+\mathbf{V}_t}^2 + \|s_t\|_{\mathbf{V}_t^{-1}}^2 - \|s_t\|_{(\mathbf{V}+\mathbf{V}_t)^{-1}}^2,
\end{aligned}$$

which gives

$$\begin{aligned}
m_t &= \frac{1}{c(\mathbf{V})} \exp\left(\frac{1}{2} \|s_t\|_{(\mathbf{V}+\mathbf{V}_t)^{-1}}^2\right) \int_{\mathbb{R}^d} \exp\left(-\frac{1}{2} \|\mu - (\mathbf{V} + \mathbf{V}_t)^{-1} s_t\|_{\mathbf{V}+\mathbf{V}_t}^2\right) d\mu \\
&= \frac{c(\mathbf{V} + \mathbf{V}_t)}{c(\mathbf{V})} \exp\left(\frac{1}{2} \|s_t\|_{(\mathbf{V}+\mathbf{V}_t)^{-1}}^2\right) = \left(\frac{\det(\mathbf{V})}{\det(\mathbf{V} + \mathbf{V}_t)}\right)^{1/2} \exp\left(\frac{1}{2} \|s_t\|_{(\mathbf{V}+\mathbf{V}_t)^{-1}}^2\right) \\
&= \left(\frac{\det(\mathbf{V})}{\det(\mathbf{V} + \mathbf{V}_t)}\right)^{1/2} \exp\left(\frac{1}{2} \|s_t\|_{(\mathbf{V}+\mathbf{V}_t)^{-1}}^2\right)
\end{aligned}$$

Now, from $\mathbb{E}[m_\tau] \le 1$, we obtain

$$\begin{aligned}
\mathbb{P}\left[\|s_{\tau}\|_{(\mathbf{V}+\mathbf{V}_{\tau})^{-1}}^2 > 2 \log\left(\frac{\det(\mathbf{V}+\mathbf{V}_{\tau})^{1/2}}{\delta \det(\mathbf{V})^{1/2}}\right)\right] &= \mathbb{P}\left[\frac{\exp\left(\frac{1}{2}\|s_{\tau}\|_{(\mathbf{V}+\mathbf{V}_{\tau})^{-1}}^2\right)}{\delta^{-1}\left(\det(\mathbf{V}+\mathbf{V}_{\tau})/\det(\mathbf{V})\right)^{1/2}} > 1\right] \\
&\le \mathbb{E}\left[\frac{\exp\left(\frac{1}{2}\|s_{\tau}\|_{(\mathbf{V}+\mathbf{V}_{\tau})^{-1}}^2\right)}{\delta^{-1}\left(\det(\mathbf{V}+\mathbf{V}_{\tau})/\det(\mathbf{V})\right)^{1/2}}\right] \\
&= \mathbb{E}[m_{\tau}] \delta \le \delta
\end{aligned}$$
$$
\begin{align*}
C_2 &\triangleq 8e^2 (\sigma_\eta^2 + \sigma_\epsilon^2) \frac{\mathbf{r}^2}{L_z^2} \sqrt{\log \frac{2}{\delta}} \\
C_3 &\triangleq 8e^2 (\sigma_\eta^2 + \sigma_\epsilon^2) \frac{\mathbf{r}^2}{L_z^2} \sqrt{\max\left\{\frac{1}{\lambda}, \frac{2}{\lambda_{\min}(\boldsymbol{\Sigma})}\right\}} \log \frac{2}{\delta} \\
C_4 &\triangleq \frac{\mathbf{r}^2}{L_z^2} \left(T_0 \lambda^{-1/2} + 2\sqrt{2} \lambda_{\min}(\boldsymbol{\Sigma})^{-1/2}\right).
\end{align*}
$$

$C_1, C_2, C_3$, and $C_4$ are dimension $d_x$, $d_{bz}$, and horizon $T$ independent constants leading to a regret upper bound of order

$$ \mathcal{O}(d_x d_z \log^2 T) + \mathcal{O}(\|\gamma\|_2 \sqrt{d_z T \log T}). $$

□

**Remark B.17 (Just-identified case.)**. For the just-identified IVs, $d_x = d_z = d$. Thus, the bound on oracel regret of O2SLS reduces to $\mathcal{O}(d^2 \log^2 T) + \mathcal{O}(\gamma \sqrt{dT} \log T)$.

**Remark B.18 (Exogeneous case.)**. For the exogeneous case, $\gamma = 0$. Thus, we O2SLS achieves an oracle regret bound $\mathcal{O}(d^2 \log^2 T)$. This is comparable in terms of dependence on $d$ and $T$ to the oracle regret of online ridge regression and online VAWR in the exogeneous setting.

**Remark B.19 (A discussion on $\lambda$)**. In the design matrix, we use the fact that $G_{z,t} \triangleq Z_t^\top Z_t = \sum_{s=1}^t z_s z_s^\top + G_{z,0}$, such that $\lambda_{\min}(G_{z,0}) \ge \lambda$. We discuss different ways to achieve it and standard rectifications, if we remove this condition.

1. **Adding a regulariser:** We can ensure $G_{z,0} = \lambda I_{d_z}$, and thus, $\lambda_{\min}(G_{z,0}) = \lambda$. This can be achieved by using a $\ell_2$ regulariser, i.e. $\lambda \|\beta\|_2^2$, in the second-stage, such that $\lambda > 0$.

2. **Data augmentation:** The other way to ensure is to consider a data augmentation approach. Rather than beginning with $z_0 = 0$, i.e. a vector with all zero entries, we can choose a $z_0$ during initialisation, such that $\lambda_{\min}(G_{z,0}) = \|z_0 z_0^\top\|_2 \ge \lambda$, and $\|z_0\|_2^2 = z_0^\top z_0 \le L_z^2$.

If we want to remove this condition that $\lambda_{\min}(G_{z,0}) \ge \lambda$, and redefine $G_{z,t}$ as $\sum_{s=1}^t z_s z_s^\top$, then we can modify the bounds in two ways:

1. **Well-behavedness of IVs:** It is common in econometrics and OLS regression literature to assume well-behavedness of the covariates for simplifying the analysis (Assumption A.2. in Chapter 8.2 [Greene, 2003]; Theorem 13.13. [Wasserman, 2004]. In our case, well-behavedness means that for any $t > 0$, $\lambda_{\min}(\sum_{s=1}^t z_s z_s^\top) > 0$, i.e. the first-stage design matrix dictated by the IVs is invertible at every step. In this case, we can proceed with our analysis by substituting $\lambda = \inf_{t \ge 0} \lambda_{\min}(\sum_{s=1}^t z_s z_s^\top)$.

2. **Added cost for initial design matrices:** Now, if we want to be more flexible and not to consider the well-behavedness of IVs assumption, we have to follow the rectifications as in the analysis of unregularised OLS by Maillard [2016] or the analysis of unregularised forward (VAWR) algorithm by Ouhamma et al. [2021]. Specifically, if we assume $t = T_0 > 1$ is the first time step when the design matrix becomes positive definite, the identification regret bound becomes $\tilde{R}_T = \mathcal{O}(\log(\delta^{-1} C_{\text{peeling}}(TL_z^2/\gamma d_z)^{d_z}) \log(\det(G_{z,T})/\det(G_{z,T_0})))$ with probability at least $1 - \delta$ as $T \gg T_0$. Here, $C_{\text{peeling}}$ is some dimension and $T$-independent constant invoked by the peeling technique in Theorem 5.4. of [Maillard, 2016]. Thus, we can asymptotically maintain the $\mathcal{O}(d_x d_z \log^2 T)$ identification regret bound for O2SLS. Similar relaxations can be derived for all other bounds as an interesting theoretical exercise.
and substituting back the definition of $G_{z,t}$ gives

$$ \mathbb{P} \left[ \| \boldsymbol{s}_{\tau} \|_{G_{z,\tau}}^{2} > 2 \log \left( \frac{\det (\boldsymbol{G}_{z,\tau})^{1/2}}{\delta \lambda^{d/2}} \right) \right] \leq \delta. $$

□

**Theorem I.1** (Self-Normalized 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_2$-sub-Gaussian for some $\sigma_2 \ge 0$ i.e. $\forall \lambda \in \mathbb{R}$ holds

$$ \mathbb{E} \left[ e^{\lambda \eta_t} \mid \mathcal{F}_{t-1} \right] \le \exp \left( \frac{\lambda^2 \sigma_2^2}{2} \right). $$

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 $\boldsymbol{s}_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$,

$$ \| \boldsymbol{s}_t \|_{\mathbf{G}_{z,t}}^2 \le 2\sigma_2^2 \log \left( \frac{\det (\mathbf{G}_{z,t})^{1/2} \lambda^{-d/2}}{\delta} \right) $$

*Proof.* We will use a stopping time construction, which goes back at least to (Freedman, 1975). Define the bad event

$$ B_t(\delta) = \left\{ \omega \in \Omega : \| \boldsymbol{s}_t \|_{\mathbf{G}_{z,t}}^2 > 2\sigma_2^2 \log \left( \frac{\det (\mathbf{G}_{z,t})^{1/2} \det (\mathbf{V})^{-1/2}}{\delta} \right) \right\} $$

We are interested in bounding the probability that $\bigcup_{t \ge 0} B_t(\delta)$ happens. Define $\tau(\omega) = \min\{t \ge 0 : \omega \in B_t(\delta)\}$, with the convention that $\min\emptyset = \infty$. Then, $\tau$ is a stopping time. Further, $\bigcup_{t \ge 0} B_t(\delta) = \{\omega : \tau(\omega) < \infty\}$ Thus,

$$ \begin{aligned} \mathbb{P} \left[ \bigcup_{t \ge 0} B_t(\delta) \right] &= \mathbb{P}[\tau < \infty] = \mathbb{P} \left[ \| \boldsymbol{s}_{\tau} \|_{\mathbf{G}_{z,\tau}}^2 > 2\sigma_2^2 \log \left( \frac{\det (\mathbf{G}_{z,\tau})^{1/2} \det (\mathbf{V})^{-1/2}}{\delta} \right), \tau < \infty \right] \\ &\le \mathbb{P} \left[ \| \boldsymbol{s}_{\tau} \|_{\mathbf{G}_{z,\tau}}^2 > 2\sigma_2^2 \log \left( \frac{\det (\mathbf{G}_{z,\tau})^{1/2} \det (\mathbf{V})^{-1/2}}{\delta} \right) \right] \le \delta. \end{aligned} $$

□

**Lemma I.3.** Let {$\mathcal{F}_t$}$_{t \ge 0}$ be a filtration such that $w_t$ is $\mathcal{F}_{t-1}$ measurable and $\eta_t$ is $\mathcal{F}_t$ measurable and is conditionally $\sigma_2$-sub-Gaussian. Let $\tau$ be a stopping time w.r.t. to this filtration i.e. the event {$\tau \le t$} belongs to $\mathcal{F}_t$. The following sequence of random variables is a martingale with respect to $\mathcal{F}_t$: $s_t = \sum_{s=1}^t \eta_s w_s$. Furthermore, for any $\delta > 0$, $\sigma_2 > 0$, with probability at least $1 - \delta$:

$$ |s_{\tau}| \le \sigma_2 \sqrt{2 \left( 1/\sigma_2^2 + \sum_{t=1}^{\tau} w_t^2 \right) \log \left( \frac{\sqrt{1 + \sigma_2^2 \sum_{t=1}^{\tau} w_t^2}}{\delta} \right)} $$

*Proof.* The fact that it is a martingale follows from the conditional sub-Gaussianity. Then for $\lambda \in \mathbb{R}^d, t > 0$ we define

$$ m_t^{\lambda} = \exp \left( \frac{\lambda s_t}{\sigma_2} - \frac{\lambda^2}{2} \sum_{s=1}^{t} w_s^2 \right) $$
## B.9 Discussion on different definitions of regret

Under exogeneity, [Ouhamma et al., 2021, Theorem 3.1] show that the oracle and population regrets differ by $o(\log^2 T)$. In this section, we show it to be not true under endogeneity. Thus, studying the three regrets shows that the hardness of identification of underlying model (the identification regret $\tilde{R}_T$), quality of predictions due to unavailability of oracle/true model (oracle regret $\bar{R}_T$), and quality of predictions w.r.t. a fixed dataset/population (population regret $R_T$) can differ significantly under endogeneity, whereas they are of similar order under exogeneity.

Historically, econometrics has focused on (asymptotic) correct identification of the estimator $\beta$ in presence of endogeneity in order to assign causal meaning to the parameters in a regression model [Angrist and Imbens, 1995].

Instead, the primary concern of the statistics and statistical learning community has arguably been generalisation (see for example [Shalev-Shwartz and Ben-David, 2014]), with the online learning literature initiated by the works by Foster [1991] and Littlestone et al. [1991].

Under exogeneity, the problem of identifying the true parameter $\beta$ is solved at the same time as minimizing the MSE by the OLS estimator, which is in fact a consistent estimator and is the Minimum Mean Squared Error Estimator (MMSE). This is not true if we introduce the more realistic assumption of endogeneity. In fact the estimator is biased and the MMSEE is different from the oracle $\beta$ in this case:

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

where we isolated the bias term $\mathbb{E}[\boldsymbol{x}\boldsymbol{x}^{\top}]^{-1} \mathbb{E}[\boldsymbol{x}\boldsymbol{\eta}]$. The expression simply follows by solving for $\beta'$ in $\partial_{\beta'} \mathbb{E}_{\boldsymbol{x}\boldsymbol{y}}[(y - \boldsymbol{x}\boldsymbol{\beta}')^2] = 0$. Under exogeneity, $\mathbb{E}[\boldsymbol{x}\boldsymbol{\eta}] = 0$ and the MMSEE concedes with $\beta$, while, in the more realistic case of endogenous noise $\mathbb{E}[\boldsymbol{x}\boldsymbol{\eta}] \neq 0$ and the estimator is biased for $\beta$.

Therefore, the oracle is not the best estimator in terms of prediction accuracy. Instead, we should aim for a consistent estimator of the MMSE, like the Empirical Risk Minimiser (ERM) which leads to the OLS estimator. In the endogenous setting, the OLS estimator is biased for the oracle $\beta$, and this poses the problem of assigning causal meaning to it.

We are interested in finding notions of regret that preserve the causal interpretation of the estimators while allowing a study of their generalisation properties. This has led us to extend the instrumental variables analysis to the online setting and to the inspection of different notions of regret. The regrets that we introduce below, differ from the population regret which is usually considered in online learning under the exogeneity assumption. The population regret is defined as

$$ R_T(\beta_T) \triangleq \sum_{t=1}^{T} (y_t - \boldsymbol{x}_t^{\top} \beta_{t-1})^2 - \min_{\beta} \sum_{t=1}^{T} (y_t - \boldsymbol{x}_t^{\top} \beta)^2 \quad (32) $$

for a time-dependent estimator $\beta_{t-1}$ and where we indicated with $\beta_T \triangleq \arg \min_{\beta} \sum_{t=1}^{T} (y_t - \boldsymbol{x}_t^{\top} \beta)^2$. Instead, we introduce two alternative regrets that measure the performance of an estimator $\beta_{t-1}$ with respect to the oracle $\beta$ (instead of $\beta_T$). Respectively, 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 - \boldsymbol{x}_t^{\top} \beta_{t-1})^2 - \sum_{t=1}^{T} (y_t - \boldsymbol{x}_t^{\top} \beta)^2, \quad \tilde{R}_T(\beta) = \sum_{t=1}^{T} (\boldsymbol{x}_t^{\top} \beta_{t-1} - \boldsymbol{x}_t^{\top} \beta)^2. $$

Theorem B.20 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 B.20.** For any estimator, the quantity $\Delta\Re_T \triangleq R_T(\beta_T) - \bar{R}_T(\beta)$ is lower bound in expectation by $\mathbb{E}[\Delta\Re_T] = \Omega(T)$
$$d_t^\lambda = \frac{\lambda \eta_t w_t}{\sigma_2} - \frac{\lambda^2}{2} w_t^2$$

Since $\tau$ be a stopping time with respect to the filtration $\{\mathcal{F}_t\}_{t=0}^\infty$ we can show that $m_\tau^\lambda$ is well-defined almost surely and $\mathbb{E}[m_\tau^\lambda] \le 1$. We start by proving that $\{m_t^\lambda\}_{t=0}^\infty$ is a supermartingale. Clearly, $d_t^\lambda$ is $\mathcal{F}_t$-measurable, as is $m_t^\lambda$. Further,

$$\mathbb{E}[m_t^\lambda | \mathcal{F}_{t-1}] = \mathbb{E}[m_1^\lambda \cdots d_{t-1}^\lambda d_t^\lambda | \mathcal{F}_{t-1}] = d_1^\lambda \cdots d_{t-1}^\lambda \mathbb{E}[d_t^\lambda | \mathcal{F}_{t-1}] \le m_{t-1}^\lambda,$$

showing that $\{m_t^\lambda\}_{t=0}^\infty$ is indeed a supermartingale. Next we show that $m_\tau^\lambda$ is always well-defined and $\mathbb{E}[m_\tau^\lambda] \le 1$. First define $\tilde{M} = m_\tau^\lambda$ and note that $\tilde{M}(\omega) = M_{\tau(\omega)}^\lambda(\omega)$. Thus, when $\tau(\omega) = \infty$, we need to argue about $M_\infty^\lambda(\omega)$. By the convergence theorem for nonnegative supermartingales, $\lim_{t\to\infty} m_t^\lambda(\omega)$ is well-defined, which means $m_\tau^\lambda$ is well-defined, independently of whether $\tau < \infty$ holds or not. Now let $Q_t^\lambda = M_{\min\{\tau,t\}}^\lambda$ be a stopped version of $m_t^\lambda$. We proceed by using Fatou's Lemma to show that $\mathbb{E}[m_\tau^\lambda] = \mathbb{E}[\liminf_{t\to\infty} Q_t^\lambda] \le \liminf_{t\to\infty} \mathbb{E}[Q_t^\lambda] \le 1$.

Let $\Lambda \sim N(0, \sigma_2^2)$ be a Gaussian random variable and define $m_t = \mathbb{E}[m_t^\Lambda | F^\infty]$. Clearly, we still have $\mathbb{E}[m_t] = \mathbb{E}[\mathbb{E}[m_t^\Lambda | \Lambda]] \le 1$. Let us calculate $m_t$. We will need the density $\lambda$ which is $f(\lambda) = \frac{1}{\sqrt{2\pi\sigma_2^2}}e^{-\lambda^2/2\sigma_2^2}$. Now, it is easy to write $m_t$ explicitly

$$m_t = \mathbb{E}[m_t^\Lambda | \mathcal{F}_\infty] = \int_{-\infty}^\infty m_t^\lambda f(\lambda) d\lambda = \sqrt{\frac{1}{2\pi\sigma_2^2}} \int_\infty^\infty \exp\left(\frac{\lambda s_t}{\sigma_2} - \frac{\lambda^2}{2} \sum_{s=1}^t w_s^2\right) e^{-\lambda^2/2\sigma_2^2} d\lambda \\ = \exp\left(\frac{s_t^2}{2\sigma_2^2 \left(1/\sigma_2^2 + \sum_{s=1}^t w_s^2\right)}\right) \sqrt{\frac{1}{1 + \sigma_2^2 \sum_{s=1}^t w_s^2}}$$

where we have used that $\int_{-\infty}^\infty \exp(a\lambda - b\lambda^2) = \exp(a^2/(4b)) \sqrt{\pi/b}$.

To finish the proof, we use Markov's inequality and the fact that $\mathbb{E}[m_\tau] \le 1$:

$$\begin{aligned} & \mathbb{P}\left[|s_\tau| \ge R \sqrt{2 \left(1/\sigma_2^2 + \sum_{t=1}^\tau w_t^2\right) \log \left(\frac{\sqrt{1+\sigma_2^2 \sum_{t=1}^\tau w_t^2}}{\delta}\right)}\right] \\ &= \mathbb{P}\left[\frac{(\sum_{t=1}^\tau \eta_t w_t)^2}{2\sigma_2^2 (1/\sigma_2^2 + \sum_{t=1}^\tau w_t^2)} \ge \log \left(\frac{\sqrt{1+\sigma_2^2 \sum_{t=1}^\tau w_t^2}}{\delta}\right)\right] \\ &= \mathbb{P}\left[\exp\left(\frac{s_\tau^2}{2\sigma_2^2 (1/\sigma_2^2 + \sum_{t=1}^\tau w_t^2)}\right) \ge \frac{\sqrt{1+\sigma_2^2 \sum_{t=1}^\tau w_t^2}}{\delta}\right] \\ &= \mathbb{P}\left[m_\tau \ge \frac{1}{\delta}\right] \le \frac{\mathbb{E}[m_\tau]}{1/\delta} \le \delta \end{aligned}$$

□

**Theorem I.2 (Self-normalized Bound for Scalar Valued Martingales).** Under the same assumptions as the previous theorem, 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_2 \sqrt{2 \left( 1/\sigma_2^2 + \sum_{s=1}^{t} w_s \right) \log \left( \frac{\sqrt{1+\sigma_2^2 \sum_{s=1}^{t} w_s^2}}{\delta} \right)} \quad (26)$$
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 \mathbf{x}_t^\top)^{-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\mathfrak{R}_T$ using $\Delta\beta_T \triangleq \beta - \beta_T$ and $\mathbf{G}_{\mathbf{x},T} \triangleq \sum_{t=1}^T \mathbf{x}_t \mathbf{x}_t^\top$ as follows

$$ \Delta\mathfrak{R}_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\|_{\mathbf{G}_{\mathbf{x},T}}^2. $$

Thanks to Lemma B.8, we know that the minimum eigenvalue of $\mathbf{G}_{\mathbf{x},T}$ is $\Omega(T)$ which implies $\|\Delta\beta_T\|_{\mathbf{G}_{\mathbf{x},T}}^2 \ge \|\Delta\beta_T\|_2^2 \lambda_{\min}(\mathbf{G}_{\mathbf{x},T}) \gtrsim \|\Delta\beta_T\|_2^2 T$. Furthermore, we can bound away from zero in expectation $\|\Delta\beta_T\|_2^2$ by using Cramér-Rao bound on each component of the estimator $\beta_T$, for which we have $\mathbb{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) = \mathbb{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.
Proof. Define the “bad” event

$$B_t(\delta) = \left\{ \omega \in \Omega : \frac{\left(\sum_{s=1}^{t} \eta_s w_s\right)^2}{1/\sigma_2^2 + \sum_{t=1}^{\tau} w_t^2} > 2\sigma_2^2 \ln \left( \frac{\sqrt{1 + \sigma_2^2 \sum_{s=1}^{t} w_s^2}}{\delta} \right) \right\}$$

We are interested in bounding the probability that $\bigcup_{t \ge 0} B_t(\delta)$ happens. Define $\tau(\omega) = \min\{t \ge 0 : \omega \in B_t(\delta)\}$, with the convention that $\min \emptyset = \infty$. Then, $\tau$ is a stopping time. Further, $\bigcup_{t \ge 0} B_t(\delta) = \{\omega : \tau(\omega) < \infty\}$. Thus, by the previous theorem it holds that

$$ \begin{aligned} \mathbb{P}\left[\bigcup_{t \ge 0} B_t(\delta)\right] &= \mathbb{P}[\tau < \infty] = \mathbb{P}\left[\frac{\left(\sum_{s=1}^{t} \eta_s w_s\right)^2}{1/\sigma_2^2 + \sum_{t=1}^{\tau} w_t^2} > 2\sigma_2^2 \ln\left(\frac{\sqrt{1 + \sigma_2^2 \sum_{s=1}^{t} w_s^2}}{\delta}\right) \text{ and } \tau < \infty\right] \\ &= \mathbb{P}\left[\frac{\left(\sum_{s=1}^{t} \eta_s w_s\right)^2}{1/\sigma_2^2 + \sum_{t=1}^{\tau} w_t^2} > 2\sigma_2^2 \ln\left(\frac{\sqrt{1 + \sigma_2^2 \sum_{s=1}^{t} w_s^2}}{\delta}\right)\right] \le \delta \end{aligned} $$

□
C Regret Analysis for IV Linear Bandits: OFUL-IV

**Theorem 4.2 (Regret of OFUL-IV).** Under the same assumptions as that of Theorem 3.5, for horizon $T > 1$, Algorithm 2 incurs a regret

$$R_T = \sum_{t=1}^{T} r_t \le 2\sqrt{T} \sqrt{\mathfrak{b}_{T-1}(\delta)} \sqrt{\left( \left( \frac{L_{\Theta}^2 \mathbf{r}^4}{L_z^2} + \frac{\mathbf{r}^4}{L_z^4} d_x \sigma_{\epsilon}^2 \right) f(T) + \frac{\mathbf{r}^4}{L_z^4} C_5 \right)},$$

with probability at least $1 - \delta$. Here, $C_5$ is $\mathcal{O}(d_x)$ constant as defined in Equation (24).

*Proof.* The instantaneous regret $r_t$ reads

$$ \begin{aligned} \langle \boldsymbol{\beta}, \mathbf{x}_* \rangle - \langle \boldsymbol{\beta}, \mathbf{x}_t \rangle &\le \langle \tilde{\boldsymbol{\beta}}_{t-1}, \mathbf{x}_t \rangle - \langle \boldsymbol{\beta}, \mathbf{x}_t \rangle \quad (\text{since } (\mathbf{x}_t, \tilde{\boldsymbol{\beta}}_{t-1}) \text{ is optimistic inside } \mathcal{X}_t \times \mathcal{B}_t) \\ &= \langle \boldsymbol{\beta}_{t-1} - \boldsymbol{\beta}, \mathbf{x}_t \rangle + \langle \tilde{\boldsymbol{\beta}}_{t-1} - \boldsymbol{\beta}_{t-1}, \mathbf{x}_t \rangle \quad (\text{summing and subtracting } \boldsymbol{\beta}_{t-1}) \\ &\le \|\boldsymbol{\beta}_{t-1} - \boldsymbol{\beta}\|_{\hat{\Theta}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\Theta}_{t-1}} \|\mathbf{x}_t\|_{(\hat{\Theta}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\Theta}_{t-1})^{-1}} \\ &\quad + \|\tilde{\boldsymbol{\beta}}_{t-1} - \boldsymbol{\beta}_{t-1}\|_{\hat{\Theta}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\Theta}_{t-1}} \|\mathbf{x}_t\|_{(\hat{\Theta}_{t-1}^{\top} \mathbf{G}_{z,t-1} \hat{\Theta}_{t-1})^{-1}} \quad (\text{Cauchy-Schwarz}) \\ &\le 2\sqrt{\mathfrak{b}_{t-1}(\delta)} \|\mathbf{x}_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}} \quad (\text{Lemma 3.3}) \end{aligned} $$

The last inequality uses the concentration of $\boldsymbol{\beta}_t$ around the true value $\boldsymbol{\beta}$, and the fact that we choose $\tilde{\boldsymbol{\beta}}_{t-1}$ inside $\mathcal{B}_{t-1}$. In both cases, the two norms are bounded by the radius of the ellipsoid, i.e. $\sqrt{\mathfrak{b}_{t-1}(\delta)}$. Since we already know in this case how to concentrate the sum of the features norms $\sum_{t=1}^T \|\mathbf{x}_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2$ from Lemma B.14, we bound the cumulative regret using Cauchy-Schwarz inequality in the first inequality below, and we substitute the bound on the instantaneous regret that we just obtained:

$$R_T \le \sqrt{T \sum_{t=1}^T r_t^2} \le 2 \sqrt{T \sum_{t=1}^T \mathfrak{b}_{t-1}(\delta) \|\mathbf{x}_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2} \le 2\sqrt{T} \sqrt{\mathfrak{b}_{T-1}(\delta)} \sqrt{\sum_{t=1}^T \|\mathbf{x}_t\|_{\hat{\mathbf{H}}_{t-1}^{-1}}^2}$$

where in the second inequality, we used the fact that the radius $\mathfrak{b}_{t-1}(\delta)$ is monotonically increasing in $t$. Now, we can use Lemma B.14 to bound the sum of feature norms, and putting all together, we obtain the following bound:

$$R_T \le 2\sqrt{T} \underbrace{\sqrt{\mathfrak{b}_{T-1}(\delta)}}_{\mathcal{O}(\sqrt{d_z \log T})} \underbrace{\left( \left( \frac{L_{\Theta}^2 \mathbf{r}^4}{L_z^2} + \frac{\mathbf{r}^4}{L_z^4} d_x \sigma_{\epsilon}^2 \right) f(T) + \frac{\mathbf{r}^4}{L_z^4} C_5 \right)^{1/2}}_{\mathcal{O}(\sqrt{d_x \log T})} = \mathcal{O}\left(\sqrt{d_x d_z T \log T}\right). \quad \square$$
## J. Parameter Estimation and Concentration in First Stage

There are many ways of addressing the regression problem in the first stage and they fundamentally reduce to a choice for the regularizer in the regression. If we do not introduce such regularizer, we are left with a system of multiple regressions that can be solved with standard OLS (estimator). Another choice is to introduce a Frobenius norm regularizer. We introduce the parameter $\lambda > 0$ and a regularization term $\lambda \|\Theta\|_F^2$, which is used to penalize the model complexity. By choosing the Frobenius norm, the system of equations decouples again but each with a regularizer term. Thus, we end up with $d$ independent linear equations that we try to fit separately. More interesting settings could try to solve the optimization problem jointly by a regularizer that couples the equations (e.g. (Wainwright, 2019) provides concentration results for such settings). This will be interesting to investigate in future works.

We indicate with $\underline{\theta}_j$ the j-th column of the matrix $\Theta$, then

$$ 
\begin{aligned}
\hat{\Theta}_t &\in \operatorname*{argmin}_{\Theta} \sum_{s=1}^t \|\mathbf{x}_s^\top - \mathbf{z}_s^\top \underline{\Theta}\|_2^2 + \lambda \|\underline{\Theta}\|_F^2 \\
&= \operatorname*{argmin}_{\Theta} \sum_{s=1}^t \left( \sum_{j=1}^d \left( \mathbf{x}_{s,j} - \mathbf{z}_s^\top \underline{\theta}_j \right)^2 + \lambda \sum_{j=1}^d \|\underline{\theta}_j\|_2^2 \right) \\
&= \operatorname*{argmin}_{\{\underline{\theta}_j\}_{j=1}^d} \sum_{j=1}^d \left( \sum_{s=1}^t \left( \mathbf{x}_{s,j} - \mathbf{z}_s^\top \underline{\theta}_j \right)^2 + \lambda \|\underline{\theta}_j\|_2^2 \right)
\end{aligned}
$$

Clearly, we can compute separately the columns $\hat{\theta}_{t,j}$ of $\hat{\Theta}_t$ as

$$ \hat{\theta}_{t,j} \in \operatorname*{argmin}_{\underline{\theta}_j} \sum_{s=1}^{t} \left( \mathbf{x}_{s,j} - \mathbf{z}_s^\top \underline{\theta}_j \right)^2 + \lambda \|\underline{\theta}_j\|_2^2 \quad (27) $$

with solution

$$ \hat{\theta}_{t,j} = (\mathbf{Z}_t^\top \mathbf{Z}_t + \lambda \mathbb{I}_d)^{-1} \mathbf{Z}_t^\top \mathbf{x}_{t,j} $$

where $\mathbf{x}_{t,j}$ is a vector with components $x_{1,j}, \dots, x_{t,j}$. The solution to the independent quadratic optimization problems is in matrix notation equal to

$$ \hat{\Theta}_t = (\mathbf{Z}_t^\top \mathbf{Z}_t + \lambda \mathbb{I}_d)^{-1} \mathbf{Z}_t^\top \mathbf{X}_t $$

From the decomposition of the problem into multiple independent regressions, we understand that it is enough to concentrate the individual columns of $\hat{\Theta}_t$ around the ones of $\Theta$ and then to use a union bound to put things together.

**Theorem J.1 (Confidence Ellipsoid for Columns in First Stage).** Define $\mathbf{x}_t = \mathbf{z}_t^\top \underline{\theta}_j + \epsilon_{t,j}$ with $\epsilon_{t,j}$ is $\sigma_\epsilon$-sub-Gaussian and assume that $\|\underline{\theta}_j\|_2 \le S$. Then, for any $\delta > 0$, with probability at least $1 - \delta$, for all $t \ge 0$, $\underline{\theta}_j$ lies in the set

$$ \mathcal{E}_t = \left\{ \underline{\theta}_j \in \mathbb{R}^d : \left\| \hat{\underline{\theta}}_{t,j} - \underline{\theta}_j \right\|_{\mathbf{G}_{z,t}} \le \sigma_\epsilon \sqrt{2 \log \left( \frac{\det(\mathbf{G}_{z,t})^{1/2} \det(\lambda \mathbb{I}_d)^{-1/2}}{\delta} \right)} + \lambda^{1/2} S \right\} $$

Furthermore, if for all $t \ge 1$, $\|\mathbf{z}_t\|_2 \le L_z$ then with probability at least $1 - \delta$, for all $t \ge 0$,

$$ \|\hat{\underline{\theta}}_{t,j} - \underline{\theta}_j\|_{\mathbf{G}_{z,t}} \le \sigma_\epsilon \sqrt{d \log \left( \frac{1 + tL_z^2/\lambda d}{\delta} \right)} + \lambda^{1/2} S $$
# D Experimental analysis

**Experimental setup.** We deploy the online regression and bandit experiments in Python3 on a Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz. The code and the real data for the experiments can be found in the **Experiments** folder within the supplementary material. These files contain the necessary code for:

i. online regression and linear bandit experiments with varying covariate dimensions and endogeneity levels;

ii. the simulations for price-sales dynamics, both in a regression setting and in the pricing case described in Example 1.1;

iii. online estimation for real data of gasoline consumption.

We refer to the code for a detailed understanding of the implementation and to reproduce our results.

**Notation:** 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. Therefore, the normal distribution of $n$ dimensions with mean $\mu$ and standard deviation $\Sigma$ is $N_n(\mu, \Sigma)$. In a similar way, $U_n$ is the uniform distribution over $[0, 1]^n$. The vector with components all equal to one is denoted by $\vec{1}$.

## D.1 Regression with endogeneity on synthetic data

We conduct an empirical comparison of the performance of O2SLS, and that of two other algorithms: Online Ridge Regression (Ridge) and the Vovk-Azoury-Warmuth Forecaster (VAWR) [Orabona, 2019]. The difference between the two algorithms lies in the design matrices' inverse. The Vovk-Azoury-Warmuth Forecaster, in the inverse of the design matrix, uses the information at time $t$ by adding the covariate available at that time. This addition guarantees better regret bounds on adversarial losses, while on the stochastic setup, the two algorithms are expected to perform similarly, as we confirm experimentally in the following. Specifically, we compare the following online algorithms and their respective estimators:

$$ \beta_t^{\text{Ridge}} = (\mathbf{X}_t^\top \mathbf{X}_t + \lambda_{\text{Ridge}} \mathbf{I}_d)^{-1} \mathbf{X}_t^\top \mathbf{y}_t, \quad \text{(Online Ridge)} $$

$$ \beta_t^{\text{VAWR}} = (\mathbf{X}_{t+1}^\top \mathbf{X}_{t+1} + \lambda_{\text{VAWR}} \mathbf{I}_d)^{-1} \mathbf{X}_t^\top \mathbf{y}_t, \quad \text{(VAWR)} $$

$$ \beta_t^{\text{O2SLS}} = (\hat{\mathbf{X}}_t^\top \hat{\mathbf{X}}_t)^{-1} \hat{\mathbf{X}}_t^\top \mathbf{y}_t = (\hat{\Theta}_t^\top \mathbf{Z}_t^\top \mathbf{Z}_t \hat{\Theta}_t)^{-1} \hat{\Theta}_t^\top \mathbf{Z}_t^\top \mathbf{y}_t. \quad \text{(O2SLS)} $$

**Experimental setup.** Here, we adopt the following experimental setup and generative model.

$$ \mathbf{x}_t = \mathbf{\Theta} \mathbf{z}_t + \mathbf{\epsilon}_t \quad \text{(First Stage)} $$

$$ y_t = \beta^\top \mathbf{x}_t + \eta_t = \beta^\top \mathbf{x}_t + (\rho \cdot \epsilon_{t,1} + \tilde{\eta}_t), \quad \text{(Second Stage)} $$

where $\epsilon_{t,1}$ indicates the first component of the vector $\epsilon_t$, and $\eta_t = \rho \cdot \epsilon_{t,1} + \tilde{\eta}_t$. We choose $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 $\mathbf{\Theta} = \mathbf{I}_{d_x, d_x}$ which has ones on the entries $i = j$ and zeros for $i \neq j$. Then, we sample at each time $t$, the vectors $\mathbf{z}_t \sim N_{d_x}(\mathbf{0}, \mathbf{I}_{d_x})$, the vector noise $\epsilon_t \sim N_{d_x}(\mathbf{0}, \mathbf{I}_{d_x})$, and the scalar noise $\tilde{\eta}_t \sim N_1(0, 1)$. We run the algorithms with the same regularisation parameters, i.e. $\lambda = 10^{-1}$.¹ We repeat our experiments 20 times. For each algorithm, we report the mean and standard deviation of the cumulative regret over the 20 runs (shaded areas correspond to one standard deviation). In Figure 4, we present the learning curves for the identification regret $\tilde{R}_T$. In Figure 5, we plot the MSE = $\|\beta_t - \beta\|_2$, which shows the estimation error of the two. In each of the figures, we further compare for different values of increasing endogeneity $\rho$.
**Corollary J.1 (Confidence Ellipsoid for First Stage).** Under the conditions of the previous theorem, for any $\delta > 0$, with probability at least $1 - \delta$, for all $t \ge 0$

$$ \|\hat{\Theta}_t - \Theta\|_F^2 = \sum_{j=1}^d \|\hat{\theta}_{t,j} - \theta_j\|_2^2 \le d \left( \sigma \epsilon \sqrt{d \log \left( \frac{1 + tL_z^2/\lambda d}{\delta} \right)} + \lambda^{1/2} S \right) $$
<figure><img src="image_9.png" /><figcaption>(a) Cum. reg., $d_x = 2, d_z = 4$</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(b) Cum. reg., $d_x = 5, d_z = 10$</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(c) Cum. reg., $d_x = 8, d_z = 16$</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(a) MSE, $d_x = 2, d_z = 4$</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(b) MSE, $d_x = 5, d_z = 10$</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>(c) MSE, $d_x = 8, d_z = 16$</figcaption></figure>

<caption>Figure 5: $MSE = ||\beta_t - \beta||_2$ of OFUL and OFUL-IV for different endogeneity levels and covariates' dimension.</caption>

**Results.** By analysing Figure 4 and Figure 5, we observe that when endogeneity is present, both Ridge and VAWR exhibit similar performances, which are noticeably inferior to that of O2SLS. Figure 5 also shows that the performance gap between Ridge and O2SLS is approximately one order of magnitude in terms of the mean square error obtained by the respective estimators with respect to the true value of the parameter $\beta$. O2SLS's gain in performance is reflected in the identification regret. O2SLS's performance gets increasingly better while compared to Ridge and VAWR for increasing values of endogeneity ($\rho$) as shown in Figure 4.

## D.2 Linear bandits with endogeneity on synthetic data

Finally, we compare the performance of OFUL-IV and OFUL [Abbasi-Yadkori et al., 2011a] for the LBE setting. OFUL builds a confidence ellipsoid centered at $\beta_t^{\text{Ridge}}$ to concentrate around $\beta$, while OFUL-IV uses $\beta_t^{\text{O2SLS}}$ to build an accurate estimate of the true $\beta$. Our experiments demonstrate the superiority of our instrumental variables approach, which can be used to boost the performances in a linear bandit problem plagued by endogeneity when valid instruments are available. Our approach is superior to the standard OFUL or even a clever one-stage OFUL reduction. We beat the previous baselines in terms of regret performances across a wide range of covariate dimensions and endogeneity levels. Furthermore, we also experimentally confirm that using the O2SLS estimators leads to a linear bandit where performances do not depend on an upper bound to the hidden parameters $\beta$ and $\Theta$ that we would like to estimate like for OFUL

<footnote n="1">¹One can choose to tune $\lambda$ by line search or other hyperparameter tuning algorithms. We chose to set $\lambda = 10^{-1}$ and use it in all the experiments.</footnote>
# K. Experiments

## K.1 Experimental Analysis of O2SLS

Now, we aim to compare the empirical performance of O2SLS estimator with the online ridge regression (Ridge) and the Vovk-Azoury-Warmuth Forecaster (VAWf) (Orabona, 2019). The Ridge estimator is given by

$$ \beta_t^{\text{Ridge}} = (\mathbf{X}_t^\top \mathbf{X}_t + \lambda_{\text{Ridge}} \mathbb{I}_d)^{-1} \mathbf{X}_t^T \mathbf{y}_t, $$

while VAWf reads

$$ \beta_t^{\text{VAWf}} = (\mathbf{X}_{t+1}^\top \mathbf{X}_{t+1} + \lambda_{\text{VAWf}} \mathbb{I}_d)^{-1} \mathbf{X}_t^T \mathbf{y}_t. $$

We choose the regularisation parameters to be all equal to $10^{-3}$. We deploy the experiments in Python3 on a single Intel(R) Core(TM) i7-8665U CPU@1.90GHz. An experiment consisting of 100 runs of an algorithm takes approximately ten minutes. We denote the normal distribution with mean $\mu$ and standard deviation $\sigma$ as $N(\mu, \sigma)$, with $N_n$ we indicate its multivariate extension to n dimensions. We consider the true parameter of the model to be generated as $\beta \sim N_{50}(\vec{0}, \mathbb{I}_{50})$ and $\Theta_{i,j} \sim N(0, 1)$ for each of its entry. At each time step we sample the vectors $z_t \sim N_{50}(\vec{0}, \mathbb{I}_{50})$, and $\epsilon_t \sim N_{50}(\vec{0}, \mathbb{I}_{50})$. The endogenous noise in the second stage is $\eta_t = (\tilde{\eta}_t + \sum_{i=1}^{12} \epsilon_{t,i})/13$, where $\tilde{\eta}_t \sim N(0, 1)$ is a r.v. independent from all the others. From Figure 3, we observe that in the presence of endogeneity, Ridge and VAWf have very similar performances and are sensibly worse than O2SLS according to the instantaneous identification regret.

<figure><img src="image_6.png" /><figcaption>Figure 3: Performance of O2SLS for online linear regression compared with online Ridge and VAWf in terms of identification regret. O2SLS incurs lower regret compared to the other two. We average our curves over 100 samples and the shaded area indicates one standard deviation. The y-axis is in logarithmic scale.</figcaption></figure>
and one-stage OFUL, where, knowledge of such upper bounds is something unavoidable. This last fact is an additional interesting and unexpected property of our algorithm.

**Experimental setup.** We adopt the following experimental setup and data generation model.

$$x_{t,a} = \Theta z_{t,a} + \epsilon_t \quad (\text{First Stage})$$

$$y_t = \beta^\top x_{t,A_t} + \eta_t = \beta^\top x_{t,A_t} + (\rho \cdot \epsilon_{t,1} + \tilde{\eta}_t) \quad (\text{Second Stage})$$

Here, $\epsilon_{t,1}$ indicates the first component of the vector $\epsilon_t$, and $\eta_t = \rho \cdot \epsilon_{t,1} + \tilde{\eta}_t$. We choose $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 = 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 for every arm $a$ the vectors $z_{t,a} \sim N_{d_z}(\vec{0}, I_{d_z})$, for each time $t$ the vector noise $\epsilon_t \sim N_{d_x}(\vec{0}, I_{d_x})$, and the scalar noise $\eta_t = \tilde{\eta}_t + \rho \cdot \epsilon_{t,1}$ where $\tilde{\eta}_t \sim N_1(0, 1)$. We run the algorithms with the same regularisation parameters equal to $\lambda = 10^{-1}$. We repeat our experiments 20 times. We average the results, and for each algorithm, we report the mean and standard deviation of the cumulative regret (shaded areas correspond to one standard deviation). In Figure 6 we present the learning curves for the regret $R_T$, while in Figure 7 we plot the MSE = $\|\beta_t - \beta\|_2$ which shows the estimation error of the two. In addition, we compare them for increasing values of endogeneity, i.e. $\rho$.

<figure><img src="image_15.png" /><figcaption>Figure 6: Cumulative regret of OFUL and OFUL-IV for different endogeneity levels and covariates' dimension.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>Figure 7: MSE = $\|\beta_t - \beta\|_2$ of OFUL and OFUL-IV for different endogeneity levels and covariates' dimension.</figcaption></figure>
**Results.** The experiments show that for a wide range of dimensions of the covariates and for different values of endogeneity, the MSE of the estimator used by OFUL-IV is almost 1-order smaller than those of OFUL over a $T = 5000$ rounds Figure 7. *Thanks to a better estimate and better confidence intervals, OFUL-IV has much lower cumulative regret than OFUL for linear bandits with endogeneity* as illustrated in Figure 6.

### D.2.1 Unavoidable dependence on the norms of hidden parameters for OFUL and one-stage OFUL

In this section, we compare OFUL, one-stage OFUL, and OFUL-IV for different endogeneity levels $\rho$ and values of the parameter $S$ defined as $S \triangleq \|\beta\|_2 = \|\Theta\beta\|_2$, where the equalities follow from the choice $\beta = -S \cdot \vec{1}_{d_x}/\|\vec{1}_{d_x}\|_2$ and $\Theta = I_{d_z \times d_x}$ in the setting of Appendix D.2. We fix the dimension of the covariates to $d_x = 2$ and $d_z = 4$, but similar results hold in general for the over-identified case $d_z \ge d_x$.

One-stage OFUL reduction is defined in Section 4, by $y_t = (\Theta\beta)^\top z_t + \beta^\top \epsilon_t + \eta_t$. The average performance of one-stage OFUL is dependent on $\beta$, which directly goes into the noise variance $\sigma_{new}^2 = 2(\|\beta\|_2^2\sigma_{\epsilon}^2 + \sigma_{\eta}^2)$, and $\|\Theta\beta\|_2$ goes into the index computation of OFUL through the ellipsoid radius [Abbasi-Yadkori et al., 2011a, Thoerem 2]. *Favourable to OFUL and one-stage OFUL, we use knowledge of S for them, which might be unavailable in reality.* In that case, we might use a larger but misspecified upper-bound as a proxy. *We also do not use and need knowledge of S for OFUL-IV.*

We show how this dependency can cause results of OFUL and one-stage OFUL to deteriorate arbitrarily even when we know the tightest possible upper bound on $\|\beta\|_2$ and $\|\Theta\beta\|_2$. In principle, the two norms could be different, but the choices of Appendix D of $\beta$ and $\Theta$ help us to simplify the ablation study. Thus, we keep the two norms the same and control them by just one parameter $S$.

**Results.** From our numerical investigation, we observe that the average regret for OFUL-IV is insensitive to $S$. On the contrary, $S$ immediately affects one-stage OFUL, as expected. Also, in *all the settings with different endogeneity levels $\rho$ and norms $S$, OFUL-IV incurs lower regrets than the others*.
<figure><img src="image_17.png" /><figcaption>(a) Cum. reg.: $S = 1.0$</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>(b) Cum. reg.: $S = 1.5$</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>(c) Cum. reg.: $S = 2.0$</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>(d) Cum. reg.: $S = 2.5$</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>(e) Cum. reg.: $S = 3.0$</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>(f) Cum. reg.: $S = 3.5$</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(g) Cum. reg.: $S = 4.0$</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>(h) Cum. reg.: $S = 4.5$</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>(i) Cum. reg.: $S = 5.0$</figcaption></figure>

Figure 8: Comparing the evolution of cumulative regrets incurred by OFUL (blue), OFUL applied on one-stage reduction of LBE (green), and OFUL-IV (orange) across different values of the upper bounds of $\beta$, i.e. $S$. For each $S$, we plot the mean and standard deviation of regrets of each of the algorithms across three levels of endogeneity $\rho = 1.0, 1.5$, and $2.0$. While performance of OFUL applied on one-stage reduction of LBE (green) deteriorates with increasing value of $S$, performance of OFUL-IV is independent of $S$ and incurs the least cumulative regret for all the settings.

## D.3 Price-Sales Dynamics (PSD)

In Section 1, we introduced in Example 1.1 a compelling scenario where a market analyst aims to understand the impact of item prices ($Price_t$) on item sales ($Sales_t$), using a continuous stream of daily data. However, in this context, assuming exogeneity of price in the model is not viable due to the presence of unobserved confounding variables ($Event_t$), which remains unaccounted for in the regression model, resulting in an omitted variable. These confounders can influence both the noise term ($\eta_t$) and the price ($Price_t$) itself. In Section 4 we revisit Example 1.1, and we formulate it as a decision process by introducing a bandit setting where the agent has to decide on a price ($Price_{t,a}$) among a feasible set of prices in order to increase the sales ($Sales_t$). The agent also has access to a set of suppliers (contexts) such that each price corresponds to a compatible material cost ($MaterialCost_{t,a}$).
**Data generation with PSD.** To investigate these two scenarios, we generate semi-synthetic data according to the generating processes in Table 3. We take $d_x = d_z = 1$, and then we sample for each time $t$ the endogenous Event$_t \sim$ Bernoulli(0.1), and the exogenous noises $\epsilon_{F,t} \sim N_1(0, 0.01)$, $\eta_{S,t} \sim N_1(0, 0.1)$. The Random variable MaterialCost$_t \sim U_1$ is sampled for each time $t$ for the online regression setting and also for each arm $a$ in the pricing setting. We fix the hidden constants of the problem to $\theta = 1$ and $\beta = -1$.

<table><caption>Table 3: Experimental settings for PSD. We consider two settings. **Online regression with PSD** aims at learning the dynamic online, and performances are measured by the identification regret. **Pricing with PSD** is formulated as a linear bandit problem; we devise sampling strategies using a new oracle and confidence ellipsoid, and we study its regret. The term “cvt” stands for “covariate”, and “cvts” stands for “covariates”.</caption><thead><tr><th></th><th>Online regression with PSD</th><th>Pricing with PSD</th></tr></thead><tbody><tr><td>1st Stage</td><td>Price<sub>t</sub> = &theta; MaterialCost<sub>t</sub> + &rho;<sub>F</sub>Event<sub>t</sub> + &epsilon;<sub>F,t</sub></td><td>Price<sub>t,a</sub> = &theta; MaterialCost<sub>t,a</sub> + &rho;<sub>F</sub>Event<sub>t</sub> + &epsilon;<sub>F,t</sub></td></tr><tr><td>2nd Stage</td><td>Sales<sub>t</sub> = &beta; Price<sub>t</sub> + &rho;<sub>S</sub>Event<sub>t</sub> + &eta;<sub>S,t</sub></td><td>Sales<sub>t</sub> = &beta; Price<sub>t,A<sub>t</sub></sub> + &rho;<sub>S</sub>Event<sub>t</sub> + &eta;<sub>S,t</sub></td></tr><tr><td></td><td>outcome y<sub>t</sub></td><td>outcome y<sub>t</sub></td></tr></tbody></table>

**Results for online regression with PSD.** To control the degree of endogeneity, we manipulate the impact of the unobserved variable Event$_t$ on both Price$_t$ and Sales$_t$ by adjusting the values of two parameters: $\rho_F$ and $\rho_S$. From the perspective of endogeneity, it is crucial to assess the accuracy of parameter estimation. We investigate this by presenting regret learning curves for varying levels of increasing endogeneity in Figure 9a. In Figure 9b, we show the final regret across a wide range of parameter values at the time horizon.

<figure><img src="image_26.png" /><figcaption>(a) Learning curves for identification regret.</figcaption></figure>

<figure><img src="image_27.png" /><figcaption>(b) Final step $\tilde{R}_T$, different endogeneity ranges.</figcaption></figure>

Figure 9: In Figure 9a are shown the learning curves for the identification regret $\tilde{R}_T$ of Online Ridge and O2SLS over $T = 5000$ steps, and for $\rho_S = \rho_F = 3, 4, 5$. Figure 9b is the identification regret after $T = 5000$ steps of Online Ridge (left) and O2SLS (right), for different combination of $\rho_F$ and $\rho_S$. With the increasing endogeneity, O2SLS attains lower regret than Ridge in all experiments.

In Figure 9a, we examine the learning curves for the identification regret while varying the level of endogeneity. We visually represent the learning curves, capturing the mean values and their corresponding standard deviations. These curves are generated by averaging the results over 20 independent runs for different parameter combinations. Specifically, we consider increasing parameters $\rho_S = \rho_F = 3, 4, 5$ (higher ($\rho_S, \rho_F$) indicates higher endogeneity) to show how performances deteriorate for increasing endogeneity levels. O2SLS consistently outperforms Online Ridge (Ridge) across the entire parameter space considered. The performance-gain increases with increasing values of the two parameters, i.e. with increasing levels of endogeneity.
In Figure 9b we show the final regret across a wide range of parameter values at the time horizon $T = 5000$. On the left, we present the identification regret after $T = 5000$ steps of Online Ridge, while the right side is the regret for O2SLS. We consider all combinations of $\rho_F$ and $\rho_S$ within the range of values $\rho_S, \rho_F \in \{0, 0.5, 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5\}$. This range encompasses a significant portion of the parameter space we wish to explore and, thus, a wide range of endogeneity. Figure 9b validates the claim that O2SLS outperforms Online Ridge in achieving lower regret across a wide range of parameter values.

Upon examining the results, a clear pattern emerges. O2SLS consistently identifies the true parameter correctly across all levels of endogeneity, maintaining accurate estimates. This demonstrates the method's ability to handle endogeneity and provide reliable parameter estimation. Conversely, Online Ridge displays a notable decline in performance as the level of endogeneity increases. The estimated values deviate increasingly from the true parameter, leading to incorrect estimation. This emphasizes the vulnerability of Online Ridge to the detrimental effects of endogeneity, resulting in biased parameter estimates. These findings highlight the superior performance of O2SLS in handling endogeneity and preserving accurate estimation, in contrast to the deteriorating performance of Online Ridge with increasing endogeneity levels. The robustness of O2SLS positions it as a tool for tackling endogeneity-related challenges in parameter estimation.

**Results for pricing with PSD.** Similarly to the regression setting, we want to investigate the performances of our approach in the case of pricing with PSD. This can be phrased as a linear bandit problem with endogeneity. As before, to control the degree of endogeneity, we manipulate the impact of the unobserved variable $Event_t$ on both the set of prices $Price_{t,a}$ and $Sales_t$ by adjusting the values of two parameters: $\rho_F$ and $\rho_S$. In this online decision-making scenario, it is crucial to assess parameter estimation accuracy like for online regression with PSD. This is done in Figure 10a and Figure 10b. In Figure 10c, we show cumulative regret performances of the two possible approaches: OFUL, which does not consider the endogeneity of the setting and OFUL-IV, which does.

In Figure 10a and Figure 10b, we show that for increasing levels of endogeneity, both OFUL and OFUL-IV perform worse in estimating correctly the true parameter $\beta = -1$. In particular, when the endogeneity is more severe OFUL estimates it to have a positive sign mistakenly. This is reflected in very poor performances of OFUL against OFUL-IV in terms of cumulative regret in Figure 10c.

<figure><img src="image_28.png" /><figcaption>Figure 10: Comparison of OFUL and OFUL-IV in a pricing with price-sales dynamics setting for a fixed value of $\rho_F = 1$ and for increasing endogeneity levels controlled by $\rho_S = 2, 4, 6$. Estimated value over a span of $T = 5000$ steps, where shaded regions indicate one standard deviation. Figure 10a is the estimated value of $\beta_t$ by Online Ridge and O2SLS, while Figure 10b is the mean squared error with respect to the true parameter $\beta$. Figure 9a are learning curves for the regret.</figcaption></figure>
## D.4 An experiment on real data: Online estimation of gasoline consumption

**Motivation in real-life applications.** A real-life example, where applying linear bandits with endogeneity would be important and relevant is the Just-In-Time Adaptive Interventions (JITAI).

**Example D.1** (Just-In-Time Adaptive Interventions (JITAI) Tewari and Murphy [2017]). *JITAI* framework is evoked to build mobile health platforms where a number of decisions have to be taken (e.g. “whether or not to send an activity encouraging message”) depending “on a variety of behavior change domains including alcohol abuse, depression, obesity, and substance abuse”, and the data regarding a patient’s health condition (“such as GPS location, calendar busyness, and heartrate”) is collected through mobile or IoT devices. [Tewari and Murphy, 2017] states that “Contextual bandit algorithms can be used for personalizing JITAIs” (page 2 of Tewari and Murphy [2017]).

In our contextual bandit formulation, a decision corresponds to an arm, the data regarding a patient form the covariates $X$, and a proximal outcome of a decision (e.g. whether the person gets into an activity or not) leads to the outcome $y$. In this setting, at step $t$, choosing an intervention/decision corresponds to choosing an instrument $Z$. Our goal is to choose a set of instruments at each step $t$ so that the health condition of the patient improves the most. This is an online problem by nature.

Performing a stochastic analysis of an online learning algorithm before deployment is important as it tells us expected gains and limitations, which correspond to the health of actual people. Tewari and Murphy [2017] echo our motivation as “Algorithms designed for the worst-case adversarial framework can perform sub-optimally when data is actually generated stochastically”. They also state that one of the “assumptions that make repeated appearance in the theoretical analyses of contextual bandit algorithms” is “independence” (or exogeneity as we call it), and “any candidate online learning algorithm needs to be tested for reasonable departures from these ideal assumptions in simulations before being deployed in a real study with users”.

We exactly aim to do that by studying how online regression behaves under endogeneity and what are the departures from well-known behaviours under exogeneity. Tewari and Murphy [2017] further state that “New algorithms that are more robust to failure of assumptions need to be designed and associated guarantees provided.” This discussion makes it evident why studying endogeneity is important and is not a theoretical exercise.

**Experiments on LBE with real-world data.** Since we do not have access to datasets like Just-In-Time interventions, which are hardly available in public due to their sensitive nature, we demonstrate the practical experiments on simulated datasets. This is not our construct but a known phenomenon in the existing literature on instrumental variable based bandits [Kallus, 2018, Stirn and Jebara, 2018], or tackling action-independent endogeneity [Krishnamurthy et al., 2018]. But for regression, we use the publicly available dataset from the “Economic Report of the President 2000 and Census Bureau and Department of Energy” on motor gasoline consumption in the United States between 1970 and 1999.

**Data description.** The dataset used in our analysis spans the period from 1970 to 1999, and pertains to the consumption of motor gasoline in the United States. It encompasses various factors, including the price index, disposable income, and price indices of used cars, new cars, and public transport. The original source of the data is the "Economic Report of the President 2000 and Census Bureau and Department of Energy". However, for a more comprehensive understanding and analysis of this dataset, we also refer to the work of Heij et al. [2004]. In their study, they provide an in-depth examination and econometric analysis of the data, offering valuable insights into the relationships and dynamics among the different variables. We summarise the variables appearing in our model in Table 4.
<table><caption>Table 4: Observations appearing in the two-stage equations with the symbols used for them and the type of variable they represent in our regression setting.</caption><thead><tr><th>Observation</th><th>Symbol</th><th>Type</th></tr></thead><tbody><tr><td>year of observation</td><td>•<sub>t</sub></td><td>round</td></tr><tr><td>log real gasoline consumption</td><td>GC</td><td>outcome y<sub>t</sub></td></tr><tr><td>log real gasoline price index</td><td>PG</td><td>endogenous covariate x<sub>t,1</sub></td></tr><tr><td>log real disposable income</td><td>RI</td><td>exogenous covariate x<sub>t,2</sub> / IV z<sub>t,1</sub></td></tr><tr><td>log real price index of new cars</td><td>RPN</td><td>IV z<sub>t,2</sub></td></tr><tr><td>log real price index of public transport</td><td>RPT</td><td>IV z<sub>t,3</sub></td></tr><tr><td>log real price index of used cars</td><td>RPU</td><td>IV z<sub>t,4</sub></td></tr></tbody></table>

In our study, we adopt an online estimation approach to address the issue of endogeneity in the gasoline price model. Our methodology is motivated by [Heij et al., 2004], where instrumental variables are carefully selected based on their relevance and tests for endogeneity. The focus of our analysis is to estimate the price elasticity ($\beta_2$) in an online fashion, taking into account the dynamic nature of the data. It is important to note that the estimation of the price elasticity is carried out using the online Two-Stage Least Squares (O2SLS) algorithm. This online approach allows us to continually update and refine our estimates as new data becomes available. We leverage instrumental variables, namely RI, RPT, RPN, and RPU, which have been chosen based on their ability to address endogeneity concerns and improve the identification of the price elasticity parameter. Our approach enables us to capture the dynamic relationship between gasoline consumption and price, taking into account any potential endogeneity issues that may arise.

$$ \text{PG}_t = c_1 + (\theta_1, \theta_2, \theta_3, \theta_4) \cdot \underbrace{(\text{RI}_t, \text{RPT}_t, \text{RPN}_t, \text{RPU}_t)}_{\text{IVs } z_t} + \epsilon_t \quad \text{(First Stage)} $$

$$ \underbrace{\text{GC}_t}_{\text{Outcome } y_t} = c_2 + \beta_2 \underbrace{\text{PG}_t}_{\text{Endogenous } x_{t,1}} + \beta_3 \underbrace{\text{RI}_t}_{\text{Exogenous } x_{t,2}} + \eta_t \quad \text{(Second Stage)} $$

**Evaluation metrics.** We use two evaluation metrics to evaluate the goodness of O2SLS and Online Ridge regressors. First, we plot the learning curve of O2SLS and Ridge for parameters $\beta_1$ and $\beta_2$, while comparing them with their offline counterparts. Second, we plot the evolution of $R^2$ of both the estimators, i.e. the proportion of the variation in the dependent variable that is predictable from the independent variables and is mathematically computed in the following way. The sum of squares of residuals, also called the residual sum of squares is $SS_{\text{res}} = \sum_i (y_i - \langle \beta, x_i \rangle)^2$ and the total sum of squares (proportional to the variance of the data) is $SS_{\text{tot}} = \sum_i (y_i - \bar{y})^2$. The formal definition of the coefficient of determination is $R^2 = 1 - \frac{SS_{\text{res}}}{SS_{\text{tot}}}$.

**Results.** Although we do not have a ground truth for the real dataset and cannot average our runs over multiple simulations, several important observations can still be made from the results shown in Figure 11. Firstly, we observe that the coefficient $\beta_1$ corresponding to the endogenous variable exhibits significant differences between the estimates obtained from Online Ridge and O2SLS. This disparity is expected since O2SLS is specifically designed to address endogeneity, whereas Online Ridge does not possess this capability. Conversely, we notice that the difference between the estimates for the exogenous variable coefficient $\beta_2$ is less pronounced. In both cases, O2SLS converges to its final value in fewer rounds (years in this dataset) and then remains relatively constant. This behaviour confirms that the dataset is affected by endogeneity, and O2SLS effectively mitigates this issue. Secondly, the coefficient of determination approaches values
<figure><img src="image_29.png" /><figcaption>Figure 11: Comparison between the estimation of the price elasticity $\beta_1$ (left) and the coefficient $\beta_2$ of the exogenous variables $RI_t$ (centre) obtained using O2SLS for online linear estimation and the offline estimate. The dashed line corresponds to the offline estimate obtained by the two Ridge and 2SLS. On the right, we plot the coefficient of determination $R^2$, for the two methods. Closer to one at earlier stages, indicating that the estimation of the $\beta$ coefficients is more reliable and robust for O2SLS compared to Ridge. This suggests that O2SLS provides more trustworthy estimates and demonstrates superior performance in handling endogeneity-related challenges.</figcaption></figure>