Upper Counterfactual Confidence Bounds: a New Optimism Principle for
  Contextual Bandits
  The principle of optimism in the face of uncertainty is one of the most
widely used and successful ideas in multi-armed bandits and reinforcement
learning. However, existing optimistic algorithms (primarily UCB and its
variants) are often unable to deal with large context spaces. Essentially all
existing well performing algorithms for general contextual bandit problems rely
on weighted action allocation schemes; and theoretical guarantees for
optimism-based algorithms are only known for restricted formulations. In this
paper we study general contextual bandits under the realizability condition,
and propose a simple generic principle to design optimistic algorithms, dubbed
"Upper Counterfactual Confidence Bounds" (UCCB). We show that these algorithms
are provably optimal and efficient in the presence of large context spaces. Key
components of UCCB include: 1) a systematic analysis of confidence bounds in
policy space rather than in action space; and 2) the potential function
perspective that is used to express the power of optimism in the contextual
setting. We further show how the UCCB principle can be extended to infinite
action spaces, by constructing confidence bounds via the newly introduced
notion of "counterfactual action divergence."
