Contextual Bandits with Latent Confounders: An NMF Approach
  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 \times K$ mean reward
matrix $\mathbf{U}$ (for each context in $[L]$ and each arm in $[K]$)
factorizes into non-negative factors $\mathbf{A}$ ($L \times m$) and
$\mathbf{W}$ ($m \times K$). This insight enables us to propose an
$\epsilon$-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 $\mathcal{O}\left(L\mathrm{poly}(m, \log K) \log
T \right)$ at time $T$, as compared to $\mathcal{O}(LK\log 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
$\mathcal{O}\left(Km\log T\right)$. 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.
