Stochastic Bandits with Context Distributions
This addresses a gap in bandit learning for applications with stochastic or predicted contexts, though it is incremental as it extends existing methods to a broader model.
The paper tackles the problem of stochastic contextual bandits where only context distributions are observed, not exact contexts, by adapting the UCB algorithm to achieve order-optimal high-probability regret bounds for linear and kernelized rewards, generalizing prior work.
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.