Bounded (O(1)) Regret Recommendation Learning via Synthetic Controls Oracle
This work provides a theoretical solution for practical recommender systems where items have short-lived popularity, though it is incremental as it builds on prior bounded regret results.
The paper tackles the challenge of achieving bounded regret in online recommendation systems without exact knowledge of the linear model, addressing issues like unobservable covariates and uneven user arrival rates, and demonstrates bounded regret through a minimal simulation experiment.
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.