Sublinear Optimal Policy Value Estimation in Contextual Bandits
Abstract
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.
Cite
Text
Kong et al. "Sublinear Optimal Policy Value Estimation in Contextual Bandits." Artificial Intelligence and Statistics, 2020.Markdown
[Kong et al. "Sublinear Optimal Policy Value Estimation in Contextual Bandits." Artificial Intelligence and Statistics, 2020.](https://mlanthology.org/aistats/2020/kong2020aistats-sublinear/)BibTeX
@inproceedings{kong2020aistats-sublinear,
title = {{Sublinear Optimal Policy Value Estimation in Contextual Bandits}},
author = {Kong, Weihao and Brunskill, Emma and Valiant, Gregory},
booktitle = {Artificial Intelligence and Statistics},
year = {2020},
pages = {4377-4387},
volume = {108},
url = {https://mlanthology.org/aistats/2020/kong2020aistats-sublinear/}
}