An Asymptotically Optimal Contextual Bandit Algorithm Using Hierarchical
  Structures
  We propose online algorithms for sequential learning in the contextual
multi-armed bandit setting. Our approach is to partition the context space and
then optimally combine all of the possible mappings between the partition
regions and the set of bandit arms in a data driven manner. We show that in our
approach, the best mapping is able to approximate the best arm selection policy
to any desired degree under mild Lipschitz conditions. Therefore, we design our
algorithms based on the optimal adaptive combination and asymptotically achieve
the performance of the best mapping as well as the best arm selection policy.
This optimality is also guaranteed to hold even in adversarial environments
since we do not rely on any statistical assumptions regarding the contexts or
the loss of the bandit arms. Moreover, we design efficient implementations for
our algorithms in various hierarchical partitioning structures such as
lexicographical or arbitrary position splitting and binary trees (and several
other partitioning examples). For instance, in the case of binary tree
partitioning, the computational complexity is only log-linear in the number of
regions in the finest partition. In conclusion, we provide significant
performance improvements by introducing upper bounds (w.r.t. the best arm
selection policy) that are mathematically proven to vanish in the average loss
per round sense at a faster rate compared to the state-of-the-art. Our
experimental work extensively covers various scenarios ranging from bandit
settings to multi-class classification with real and synthetic data. In these
experiments, we show that our algorithms are highly superior over the
state-of-the-art techniques while maintaining the introduced mathematical
guarantees and a computationally decent scalability.
