Fast rates for nonparametric bandits with covariates using adaptive partitioning.

We consider a bandit problem which involves sequential sampling from K populations (arms).
Each arm produces a noisy reward realization which depends on an observable random covariate.
The goal is to maximize cumulative expected reward. It is now known that a quantity analogous
to the margin condition in binary classification critically controls the complexity of this
problem. While a naive procedure based on binning is adaptive to small margin parameters, it
becomes suboptimal and not adaptive in the easy case, i.e., when fast rates are theoretically
attainable. We revisit the `successive elimination' policy and use it to construct an
adaptive partition that attains fast, adaptive and minimax optimal rates on the regret.
Joint work with Vianney Perchet and Assaf Zeevi.