Optimal cross-learning for contextual bandits with unknown context
  distributions
Jon Schneider Julian Zimmert
We consider the problem of designing contextual bandit algorithms in the
``cross-learning'' setting of Balseiro et al., where the learner observes the
loss for the action they play in all possible contexts, not just the context of
the current round. We specifically consider the setting where losses are chosen
adversarially and contexts are sampled i.i.d. from an unknown distribution. In
this setting, we resolve an open problem of Balseiro et al. by providing an
efficient algorithm with a nearly tight (up to logarithmic factors) regret
bound of $\widetilde{O}(\sqrt{TK})$, independent of the number of contexts. As
a consequence, we obtain the first nearly tight regret bounds for the problems
of learning to bid in first-price auctions (under unknown value distributions)
and sleeping bandits with a stochastic action set.
  At the core of our algorithm is a novel technique for coordinating the
execution of a learning algorithm over multiple epochs in such a way to remove
correlations between estimation of the unknown distribution and the actions
played by the algorithm. This technique may be of independent interest for
other learning problems involving estimation of an unknown context
distribution.