Stochastic Bandits with Context Distributions
arXiv:1906.02685
Abstract
We introduce a stochastic contextual bandit model where at each time step the environment chooses a distribution over a context set and samples the context from this distribution. The learner observes only the context distribution while the exact context realization remains hidden. This allows for a broad range of applications where the context is stochastic or when the learner needs to predict the context. We leverage the UCB algorithm to this setting and show that it achieves an order-optimal high-probability bound on the cumulative regret for linear and kernelized reward functions. Our results strictly generalize previous work in the sense that both our model and the algorithm reduce to the standard setting when the environment chooses only Dirac delta distributions and therefore provides the exact context to the learner. We further analyze a variant where the learner observes the realized context after choosing the action. Finally, we demonstrate the proposed method on synthetic and real-world datasets.
arXiv commentAccepted at NeurIPS 2019
References in corpus (9)
- A Contextual-Bandit Approach to Personalized News Article Recommendation
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
- Finite-Time Analysis of Kernelised Contextual Bandits
- Learning from Distributions via Support Measure Machines
- Streaming kernel regression with provably adaptive mean, variance, and regularization
- Tight Regret Bounds for Infinite-armed Linear Contextual Bandits
- Perturbed-History Exploration in Stochastic Linear Bandits
- Stay With Me: Lifetime Maximization Through Heteroscedastic Linear Bandits With Reneging