Online Instrumental Variable Regression: Regret Analysis and Bandit Feedback - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2023

Online Instrumental Variable Regression: Regret Analysis and Bandit Feedback

Riccardo Della Vecchia
Debabrota Basu

Résumé

The independence of noise and covariates is a standard assumption in online linear regression with unbounded noise and linear bandit literature. This assumption and the following analysis are invalid in the case of endogeneity, i.e., when the noise and covariates are correlated. In this paper, we study the online setting of Instrumental Variable (IV) regression, which is widely used in economics to identify the underlying model from an endogenous dataset. Specifically, we upper bound the identification and oracle regrets of the popular Two-Stage Least Squares (2SLS) approach to IV regression but in the online setting. Our analysis shows that Online 2SLS (O2SLS) achieves $\mathcal O(d^2\log^2 T)$ identification and $\mathcal O(\gamma \sqrt{d T \log T})$ oracle regret after $T$ interactions, where $d$ is the dimension of covariates and $\gamma$ is the bias due to endogeneity. Then, we leverage O2SLS as an oracle to design OFUL-IV, a linear bandit algorithm. OFUL-IV can tackle endogeneity and achieves $\mathcal O(d\sqrt{T}\log T)$ regret. For datasets with endogeneity, we experimentally show the efficiency of OFUL-IV in terms of estimation error and regret.
Fichier principal
Vignette du fichier
o2sls.pdf (862.43 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Licence : CC BY NC - Paternité - Pas d'utilisation commerciale

Dates et versions

hal-03831210 , version 1 (26-10-2022)
hal-03831210 , version 2 (20-02-2023)

Licence

Paternité - Pas d'utilisation commerciale

Identifiants

  • HAL Id : hal-03831210 , version 2

Citer

Riccardo Della Vecchia, Debabrota Basu. Online Instrumental Variable Regression: Regret Analysis and Bandit Feedback. 2023. ⟨hal-03831210v2⟩
172 Consultations
188 Téléchargements

Partager

Gmail Facebook X LinkedIn More