Sublinear Optimal Policy Value Estimation in Contextual Bandits
This work addresses efficient policy evaluation in contextual bandits, which is incremental but offers practical improvements for applications such as recommendation systems and medical treatment optimization.
The paper tackles the problem of estimating the optimal policy value in stochastic disjoint linear bandits, showing that accurate estimation can be achieved with a sublinear number of samples compared to finding such a policy, and demonstrates effectiveness on real datasets like joke recommendation and cancer inhibition dosage selection.
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 number of samples that is sublinear in the number that would be required to \emph{find} a policy that realizes a value close to this optima. We establish nearly 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.