Sublinear Optimal Policy Value Estimation in Contextual Bandits


Weihao Kong, Emma Brunskill, Gregory Valiant ;
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:4377-4387, 2020.


We study the problem of estimating the expected reward of the optimal policy in the stochastic disjoint linear bandit setting. We prove that for certain settings it is possible to obtain an accurate estimate of the optimal policy value even with a sublinear number of samples, where a linear set would be needed to reliably estimate the reward that can be obtained by any policy. We establish near matching information theoretic lower bounds, showing that our algorithm achieves near optimal estimation error. Finally, we demonstrate the effectiveness of our algorithm on joke recommendation and cancer inhibition dosage selection problems using real datasets.

Related Material