# Bounded (O(1)) Regret Recommendation Learning via Synthetic Controls Oracle

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 53 references that are in the map.
- First posted on arXiv 29 Jan 2023.

## Builds on (most cited first, 26 of 26)

- [Few-Shot Learning via Learning the Representation, Provably](https://mlsanity.com/paper/2002.09434/) (2020)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [A Contextual Bandit Bake-off](https://mlsanity.com/paper/1802.04064/) (2018)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [Adaptive Exploration in Linear Contextual Bandit](https://mlsanity.com/paper/1910.06996/) (2019)
- [The State of Applied Econometrics - Causality and Policy Evaluation](https://mlsanity.com/paper/1607.00699/) (2016)
- [Leveraging Good Representations in Linear Contextual Bandits](https://mlsanity.com/paper/2104.03781/) (2021)
- [Synthetic Interventions](https://mlsanity.com/paper/2006.07691/) (2020)
- [Carousel Personalization in Music Streaming Apps with Contextual Bandits](https://mlsanity.com/paper/2009.06546/) (2020)
- [Robust Synthetic Control](https://mlsanity.com/paper/1711.06940/) (2017)
- [The Augmented Synthetic Control Method](https://mlsanity.com/paper/1811.04170/) (2018)
- [Algorithms for Non-Stationary Generalized Linear Bandits](https://mlsanity.com/paper/2003.10113/) (2020)
- [Estimation Considerations in Contextual Bandits](https://mlsanity.com/paper/1711.07077/) (2017)
- [Latent Contextual Bandits and their Application to Personalized Recommendations for New Users](https://mlsanity.com/paper/1604.06743/) (2016)
- [Stochastic Linear Contextual Bandits with Diverse Contexts](https://mlsanity.com/paper/2003.02681/) (2020)
- [Bayesian Exploration with Heterogeneous Agents](https://mlsanity.com/paper/1902.07119/) (2019)
- [Synthetically Controlled Bandits](https://mlsanity.com/paper/2202.07079/) (2022)
- [Synthetic Control As Online Linear Regression](https://mlsanity.com/paper/2202.08426/) (2022)
- [Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees](https://mlsanity.com/paper/2210.13083/) (2022)
- [Adaptive Experimental Design and Counterfactual Inference](https://mlsanity.com/paper/2210.14369/) (2022)
- [Sublinear Optimal Policy Value Estimation in Contextual Bandits](https://mlsanity.com/paper/1912.06111/) (2019)
- [On the Complexity of Representation Learning in Contextual Linear Bandits](https://mlsanity.com/paper/2212.09429/) (2022)

## Abstract (arXiv)

In online exploration systems where users with fixed preferences repeatedly arrive, it has recently been shown that O(1), i.e., bounded regret, can be achieved when the system is modeled as a linear contextual bandit. This result may be of interest for recommender systems, where the popularity of their items is often short-lived, as the exploration itself may be completed quickly before potential long-run non-stationarities come into play. However, in practice, exact knowledge of the linear model is difficult to justify. Furthermore, potential existence of unobservable covariates, uneven user arrival rates, interpretation of the necessary rank condition, and users opting out of private data tracking all need to be addressed for practical recommender system applications. In this work, we conduct a theoretical study to address all these issues while still achieving bounded regret. Aside from proof techniques, the key differentiating assumption we make here is the presence of effective Synthetic Control Methods (SCM), which are shown to be a practical relaxation of the exact linear model knowledge assumption. We verify our theoretical bounded regret result using a minimal simulation experiment.