  We consider the contextual bandit problem on general action and context
spaces, where the learner's rewards depend on their selected actions and an
observable context. This generalizes the standard multi-armed bandit to the
case where side information is available, e.g., patients' records or customers'
history, which allows for personalized treatment. We focus on consistency --
vanishing regret compared to the optimal policy -- and show that for large
classes of non-i.i.d. contexts, consistency can be achieved regardless of the
time-invariant reward mechanism, a property known as universal consistency.
Precisely, we first give necessary and sufficient conditions on the
context-generating process for universal consistency to be possible. Second, we
show that there always exists an algorithm that guarantees universal
consistency whenever this is achievable, called an optimistically universal
learning rule. Interestingly, for finite action spaces, learnable processes for
universal learning are exactly the same as in the full-feedback setting of
supervised learning, previously studied in the literature. In other words,
learning can be performed with partial feedback without any generalization
cost. The algorithms balance a trade-off between generalization (similar to
structural risk minimization) and personalization (tailoring actions to
specific contexts). Lastly, we consider the case of added continuity
assumptions on rewards and show that these lead to universal consistency for
significantly larger classes of data-generating processes.
