# Sublinear Optimal Policy Value Estimation in Contextual Bandits

arXiv: https://arxiv.org/abs/1912.06111 · HTML: https://mlsanity.com/paper/1912.06111/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2019.

## Built on by (most cited first, 4 of 4)

- [A Query-Optimal Algorithm for Finding Counterfactuals](https://mlsanity.com/paper/2207.07072/) (2022)
- [Active Learning for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2605.24803/) (2026)
- [Bounded (O(1)) Regret Recommendation Learning via Synthetic Controls Oracle](https://mlsanity.com/paper/2301.12571/) (2023)
- [Estimating Optimal Policy Value in General Linear Contextual Bandits](https://mlsanity.com/paper/2302.09451/) (2023)

## Abstract (arXiv)

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 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.