Learning in Distributed Contextual Linear Bandits Without Sharing the Context
Contextual linear bandits is a rich and theoretically important model that
has many practical applications. Recently, this setup gained a lot of interest
in applications over wireless where communication constraints can be a
performance bottleneck, especially when the contexts come from a large
$d$-dimensional space. In this paper, we consider a distributed memoryless
contextual linear bandit learning problem, where the agents who observe the
contexts and take actions are geographically separated from the learner who
performs the learning while not seeing the contexts. We assume that contexts
are generated from a distribution and propose a method that uses $\approx 5d$
bits per context for the case of unknown context distribution and $0$ bits per
context if the context distribution is known, while achieving nearly the same
regret bound as if the contexts were directly observable. The former bound
improves upon existing bounds by a $\log(T)$ factor, where $T$ is the length of
the horizon, while the latter achieves information theoretical tightness.