Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Stochastic Online Instrumental Variable Regression: Regrets for Endogeneity and Bandit Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies online two-stage least squares (O2SLS) for stochastic, unbounded, endogenous linear regression and uses it as an oracle in OFUL-IV, a linear bandit algorithm with endogeneity, giving sqrt(dxdz T) regret.
Problem
Online linear regression and linear bandits with endogeneity (noise correlated with covariates) and unbounded stochastic noise, where standard OLS/ridge and OFUL analyses assume exogeneity and fail.
Approach
Adapt two-stage least squares to the online setting with recursive updates (O2SLS), prove identification and oracle regret bounds under endogeneity with unbounded noise, and plug the O2SLS estimate and a new confidence ellipsoid built on the first-stage design matrix into OFUL to get OFUL-IV.
Key results
- O2SLS achieves O(dx dz log^2 T) identification regret and O(dx^2 log^2 T) oracle regret under exogeneity (gamma=0), matching online ridge order.
- OFUL-IV achieves O(sqrt(dx dz T) log T) regret, matching the exogenous OFUL order for just-identified IVs.
- In synthetic experiments, O2SLS outperforms online ridge regression and OFUL-IV incurs lower regret than OFUL as endogeneity level rho increases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use OTSLS instead of online ridge regression | Online regression · Synthetic data with endogeneity | identification regret | Helped |
| increase endogeneity level ρ | OTSLS compared with online ridge regression · Synthetic online regression | identification regret | Mixed |
| use OFUL-IV instead of OFUL | Stochastic linear bandits with endogeneity · Linear bandits with endogeneity | cumulative regret | Helped |
| use OFUL-IV instead of one-stage OFUL reduction (ablation) | Linear bandits with endogeneity · Linear bandits with endogeneity | regret | Helped |
| increase the hidden-parameter norm S (ablation) | OFUL and one-stage OFUL reduction · Linear bandits with endogeneity | regret | Hurt |
| set the first- and second-stage noise correlation γ to zero (ablation) | OTSLS · Online IV regression under exogeneity | oracle regret: \bigO(d_{\boldsymbol x}^2 \log^2 T) | Helped |
| use just-identified IVs, with d_{\boldsymbol x} = d_{\boldsymbol z} (ablation) | OTSLS · Online IV regression | identification regret | No clear effect |
Surprising findings
- Under endogeneity, oracle regret and population regret differ by Omega(T) in expectation, so population regret is avoided.
- OFUL-IV's regret is independent of the norm bound S of the hidden parameter, unlike OFUL and one-stage reduction.
Limitations
- Oracle regret has an additive gamma*sqrt(dz T log T) bias term under endogeneity that is not eliminated.
- Quadratic time and space complexity per step in the dimensions.
- Analysis assumes bounded instruments and bounded first-stage parameters, with linear first-stage and linear second-stage models.
Experimental setup
Datasets: synthetic Gaussian data with endogeneity
Benchmarks: synthetic linear regression and linear bandit simulations
Metrics: identification regret oracle regret cumulative regret
Baselines: Online Ridge Regression OFUL
Builds on: OFUL two-stage least squares online ridge regression Vovk-Azoury-Warmuth regressor
Closest papers by meaning
- Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data (NeurIPS 2024 · similarity 0.88)
- Contextual Bandits with Online Neural Regression (ICLR 2024 · similarity 0.87)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.87)
- Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approach (AAAI 2024 · similarity 0.87)
- Off-policy estimation with adaptively collected data: the power of online learning (NeurIPS 2024 · similarity 0.86)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.