Remote Contextual Bandits
  We consider a remote contextual multi-armed bandit (CMAB) problem, in which
the decision-maker observes the context and the reward, but must communicate
the actions to be taken by the agents over a rate-limited communication
channel. This can model, for example, a personalized ad placement application,
where the content owner observes the individual visitors to its website, and
hence has the context information, but must convey the ads that must be shown
to each visitor to a separate entity that manages the marketing content. In
this remote CMAB (R-CMAB) problem, the constraint on the communication rate
between the decision-maker and the agents imposes a trade-off between the
number of bits sent per agent and the acquired average reward. We are
particularly interested in characterizing the rate required to achieve
sub-linear regret. Consequently, this can be considered as a policy compression
problem, where the distortion metric is induced by the learning objectives. We
first study the fundamental information theoretic limits of this problem by
letting the number of agents go to infinity, and study the regret achieved when
Thompson sampling strategy is adopted. In particular, we identify two distinct
rate regions resulting in linear and sub-linear regret behavior, respectively.
Then, we provide upper bounds on the achievable regret when the decision-maker
can reliably transmit the policy without distortion.
