  Consider a nonparametric contextual multi-arm bandit problem where each arm
$a \in [K]$ is associated to a nonparametric reward function $f_a: [0,1] \to
\mathbb{R}$ mapping from contexts to the expected reward. Suppose that there is
a large set of arms, yet there is a simple but unknown structure amongst the
arm reward functions, e.g. finite types or smooth with respect to an unknown
metric space. We present a novel algorithm which learns data-driven
similarities amongst the arms, in order to implement adaptive partitioning of
the context-arm space for more efficient learning. We provide regret bounds
along with simulations that highlight the algorithm's dependence on the local
geometry of the reward functions.
