arXiv preprint ·
Explore Once, Evaluate Many: Multiple Policy Evaluation for Stochastic Linear Bandits
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy
Unit-level aggregation breaks coverage in causal foundation models
Score Mismatch and Set-Constrained Sampling in Zero-Shot Conditional Discrete Diffusion
Conformal Policy Selection: When to Deploy AI Decisions for Targeted Intervention
StochLOB: Heavy-Tailed Score Matching for Robust Limit Order Book Trend Prediction
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.