Evaluate many policies at once in stochastic contextual bandits
Explore Once, Evaluate Many: Multiple Policy Evaluation for Stochastic Linear Bandits
Machine Learning
Summary
When computers need to choose the best actions based on changing situations, they often test multiple decision strategies or policies to see which works best. This paper presents a method that can efficiently evaluate many such policies simultaneously under uncertain conditions, using fewer tries and observations. The authors introduced an approach that shares information across all policies to estimate their value accurately, reducing the needed data. Their method works without knowing some difficult-to-measure properties in advance and can handle very large or even infinite sets of possible situations and actions.
What this means in practice
- •For online advertising teams: Estimate the effectiveness of many ad display strategies simultaneously without costly live ad runs
- •For recommendation system engineers: Evaluate multiple recommendation policies from logged user data efficiently to choose the best one
Authors
Spyros Dragazis, Yilei Chen, Aldo Pacchiano
Abstract
We study how to evaluate $K$ target policies simultaneously in stochastic contextual bandits with linear reward structure. Given a known $d$-dimensional feature map and reward-free access to policy queries, we propose PRISMA (Policy evaluation through Regularized Information Sharing and Mixture Allocation), an algorithm that estimates every target policy's value to accuracy $\varepsilon$ with probability at least $1-δ$. The algorithm uses $\widetilde{\mathcal{O}}\!\left( \frac{(L^2S^2+β^2)(1\veeρ^\star)}{\varepsilon^2} \cdot \log(K) \right)$ context draws and reward observations, where $ρ^\star\le d$ is an instance-dependent measure of the difficulty of designing a shared sampling distribution. Here, $L$, $S$, and $β$ bound the feature norm, reward parameter norm, and reward noise, respectively, and the suppressed factors are logarithmic in $K$, $d$, and $1/δ$. Our method combines reward-free planning, a regularized sampling design, and a single ridge regression estimator shared across all target policies. An adaptive doubling procedure selects the regularization scale without knowledge of $ρ^\star$. The guarantees require no numerical lower bound on second-moment eigenvalues and have no explicit dependence on the cardinalities of the context and action spaces. Policy-query costs are accounted for separately, with $K$ queries per shared planning context.