Part of Advances in Neural Information Processing Systems 32 (NeurIPS 2019)
Nirandika Wanigasekara, Christina Yu
Consider a nonparametric contextual multi-arm bandit problem where each arm a∈[K] is associated to a nonparametric reward function fa:[0,1]→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.