Explore Once, Evaluate Many: Multiple Policy Evaluation for Stochastic Linear Bandits

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 epsilon with probability at least 1-δ. The algorithm uses ! ((L 2S 2+β 2)(1 ρ) over epsilon squared times (K)) context draws and reward observations, where ρ 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 ρ. 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.