# Contextual Bandits with Latent Confounders: An NMF Approach

arXiv: https://arxiv.org/abs/1606.00119 · HTML: https://mlsanity.com/paper/1606.00119/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2016.

## Built on by (most cited first, 26 of 26)

- [Hierarchical Bayesian Bandits](https://mlsanity.com/paper/2111.06929/) (2021)
- [An Instrumental Variable Approach to Confounded Off-Policy Evaluation](https://mlsanity.com/paper/2212.14468/) (2022)
- [Causal Deep Learning](https://mlsanity.com/paper/2303.02186/) (2023)
- [Deep Hierarchy in Bandits](https://mlsanity.com/paper/2202.01454/) (2022)
- [Adaptively Exploiting d-Separators with Causal Bandits](https://mlsanity.com/paper/2202.05100/) (2022)
- [Invariant Policy Learning: A Causal Perspective](https://mlsanity.com/paper/2106.00808/) (2021)
- [A Causal Bandit Approach to Learning Good Atomic Interventions in Presence of Unobserved Confounders](https://mlsanity.com/paper/2107.02772/) (2021)
- [Optimal Algorithms for Latent Bandits with Cluster Structure](https://mlsanity.com/paper/2301.07040/) (2023)
- [Learning User Preferences in Non-Stationary Environments](https://mlsanity.com/paper/2101.12506/) (2021)
- [Online Low Rank Matrix Completion](https://mlsanity.com/paper/2209.03997/) (2022)
- [Delphic Offline Reinforcement Learning under Nonidentifiable Hidden Confounding](https://mlsanity.com/paper/2306.01157/) (2023)
- [Learning Good Interventions in Causal Graphs via Covering](https://mlsanity.com/paper/2305.04638/) (2023)
- [Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms](https://mlsanity.com/paper/2201.12700/) (2022)
- [Context-lumpable stochastic bandits](https://mlsanity.com/paper/2306.13053/) (2023)
- [Online learning in bandits with predicted context](https://mlsanity.com/paper/2307.13916/) (2023)
- [Debiasing Multimodal Models via Causal Information Minimization](https://mlsanity.com/paper/2311.16941/) (2023)
- [Transfer Learning in Latent Contextual Bandits with Covariate Shift Through Causal Transportability](https://mlsanity.com/paper/2502.20153/) (2025)
- [Invariant Lipschitz Bandits: A Side Observation Approach](https://mlsanity.com/paper/2212.07524/) (2022)
- [Causal Contextual Bandits with Adaptive Context](https://mlsanity.com/paper/2405.18626/) (2024)
- [Contextual Bandit with Herding Effects: Algorithms and Recommendation Applications](https://mlsanity.com/paper/2408.14432/) (2024)
- [Generator-Mediated Bandits: Thompson Sampling for GenAI-Powered Adaptive Interventions](https://mlsanity.com/paper/2505.16311/) (2025)
- [Identifiable Latent Bandits: Leveraging observational data for personalized decision-making](https://mlsanity.com/paper/2407.16239/) (2024)
- [Online Matrix Completion: A Collaborative Approach with Hott Items](https://mlsanity.com/paper/2408.05843/) (2024)
- [Active Hypothesis Testing for Correlated Combinatorial Anomaly Detection](https://mlsanity.com/paper/2601.17430/) (2026)
- [Learning to Price: Interpretable Attribute-Level Models for Dynamic Markets](https://mlsanity.com/paper/2602.00188/) (2026)
- [OTSS: Output-Targeted Soft Segmentation for Contextual Decision-Weight Learning](https://mlsanity.com/paper/2605.00193/) (2026)

## Abstract (arXiv)

Motivated by online recommendation and advertising systems, we consider a causal model for stochastic contextual bandits with a latent low-dimensional confounder. In our model, there are L observed contexts and K arms of the bandit. The observed context influences the reward obtained through a latent confounder variable with cardinality m (m ll L,K). The arm choice and the latent confounder causally determines the reward while the observed context is correlated with the confounder. Under this model, the L × K mean reward matrix U (for each context in [L] and each arm in [K]) factorizes into non-negative factors A (L × m) and W (m × K). This insight enables us to propose an ε-greedy NMF-Bandit algorithm that designs a sequence of interventions (selecting specific arms), that achieves a balance between learning this low-dimensional structure and selecting the best arm to minimize regret. Our algorithm achieves a regret of Oleft(Lpoly(m, log K) log T right) at time T, as compared to O(LKlog T) for conventional contextual bandits, assuming a constant gap between the best arm and the rest for each context. These guarantees are obtained under mild sufficiency conditions on the factors that are weaker versions of the well-known Statistical RIP condition. We further propose a class of generative models that satisfy our sufficient conditions, and derive a lower bound of Oleft(Kmlog Tright). These are the first regret guarantees for online matrix completion with bandit feedback, when the rank is greater than one. We further compare the performance of our algorithm with the state of the art, on synthetic and real world data-sets.