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

arXiv:2610.22252v1 Announce Type: new 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 arepsilon with probability at least 1-elta. The algorithm uses widetilde{O}!left( frac{(L^2S^2+eta^2)(1eerho^star)}{arepsilon^2} dot log(K) right) context draws and reward observations, where rho^starle d is an instance-dependent measure of the difficulty of designing a shared sampling distribution. Here, L, S, and eta bound the feature norm, reward parameter norm, and reward noise, respectively, and the suppressed factors are logarithmic in K, d, and 1/elta. 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 rho^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.

Source: arXiv cs.LG | 2026-10-16