Distributed Stochastic Bandit Learning with Delayed Context Observation
This addresses a practical challenge in applications like weather forecasting or stock prediction where contexts are predicted with delays, though it is incremental as it extends existing bandit methods to handle distributed and delayed settings.
The paper tackles the problem of distributed stochastic contextual bandit learning with delayed context observation, where agents must choose actions without knowing the exact context, only its distribution, and propose a UCB-based algorithm that achieves proven regret and communication bounds, validated on synthetic and real-world data.
We consider the problem where M agents collaboratively interact with an instance of a stochastic K-armed contextual bandit, where K>>M. The goal of the agents is to simultaneously minimize the cumulative regret over all the agents over a time horizon T. We consider a setting where the exact context is observed after a delay and at the time of choosing the action the agents are unaware of the context and only a distribution on the set of contexts is available. Such a situation arises in different applications where at the time of the decision the context needs to be predicted (e.g., weather forecasting or stock market prediction), and the context can be estimated once the reward is obtained. We propose an Upper Confidence Bound (UCB)-based distributed algorithm and prove the regret and communications bounds for linearly parametrized reward functions. We validated the performance of our algorithm via numerical simulations on synthetic data and real-world Movielens data.