Explore Once, Evaluate Many: Multiple Policy Evaluation for Stochastic Linear Bandits
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 ε with probability at least 1−δ. The algorithm uses 𝒪̃ ( ((L2S2+β2)(1∨ρ⋆))/ε2 · log(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.
Related
- Set Membership Estimation for Stochastic Linear Contextual Bandits
- Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
- Balanced Sampling in Stochastic Multi-objective Bandits
- Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates
- Stationary solution for a fractional stochastic delay differential equations with multiple delays
BibTeX
@misc{dragazis2026explore,
title = {{Explore Once, Evaluate Many: Multiple Policy Evaluation for Stochastic Linear Bandits}},
author = {Spyros Dragazis and Yilei Chen and Aldo Pacchiano},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22252},
eprint = {2610.22252},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22252},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Explore Once, Evaluate Many: Multiple Policy Evaluation for Stochastic Linear Bandits
AU - Spyros Dragazis
AU - Yilei Chen
AU - Aldo Pacchiano
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.22252
UR - https://arxiv.org/abs/2610.22252
AB - 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 ε with probability at least 1−δ. The algorithm uses 𝒪̃ ( ((L^2S^2+β^2)(1∨ρ^⋆))/ε^2 · log(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.
ER -