Explore Once, Evaluate Many: A New Approach to Multi-Policy Evaluation in Stochastic Linear Bandits

In scenarios such as reinforcement learning and recommendation systems, simultaneously evaluating the value of multiple candidate policies is a common need. Traditional methods often collect data separately for each policy, with costs growing linearly with the number of policies. A recent arXiv study proposes the PRISMA algorithm, which uses a shared sampling design to reduce the evaluation cost of $K$ policies to a logarithmic level.

Background: The Cost Dilemma of Multi-Policy Evaluation

In stochastic contextual bandits, evaluating the value of each policy requires sampling from the environment and observing rewards. If the goal is to evaluate $K$ policies simultaneously, the most straightforward approach is to design a separate sampling scheme for each policy, but this leads to a $K$-fold increase in sample complexity.

The formal setting of this research is: given a known $d$-dimensional feature map and a reward-free policy query interface (i.e., one can query a policy's action under any context without consuming reward observations), the algorithm must simultaneously estimate the values of all $K$ target policies with precision $\varepsilon$ and confidence at least $1-\delta$. The key challenge is that different policies may prefer different context regions, so how can we design a shared sampling distribution that enables efficient convergence for all policy value estimates?

Stochastic Contextual Bandit is a classic sequential decision-making model at the intersection of reinforcement learning and statistical learning. At each time step, the learner observes a context generated by the environment (usually a feature vector), then selects an action from the feasible action set, and can only observe the reward corresponding to that action, without knowing the counterfactual rewards of unchosen actions. Rewards are typically assumed to be noisy observations of some unknown function of context and action. This model is widely used in news recommendation, ad placement, clinical trials, and other scenarios. Unlike full reinforcement learning, contextual bandits do not involve state transitions, making theoretical analysis easier; unlike supervised learning, they face the challenge of counterfactual inference—the goal of policy evaluation is precisely to use data collected by one behavior policy to estimate the value of another target policy, which requires explicit correction for distribution shift.

Reward-free nature of the policy query interface: In this setting, the algorithm can query a policy's action under any given context without consuming the reward observation budget. This assumption is natural in scenarios such as recommendation systems: the policy itself is a computational function (e.g., a deep learning model), and calling it only requires compute, whereas obtaining real user feedback (rewards) incurs actual costs. Separating query costs from reward observation costs allows the algorithm to first use queries to plan the sampling distribution, then perform a limited number of efficient reward observations.

PRISMA's Core Mechanism: Regularized Information Sharing

The core idea of PRISMA (Policy evaluation through Regularized Information Sharing and Mixture Allocation) is "explore once, evaluate many." The algorithm consists of three components: reward-free planning, regularized sampling design, and a ridge regression estimator shared across all target policies.

Specifically, PRISMA first uses a reward-free planning phase to explore the environment without observing rewards, constructing a context distribution that covers the regions all policies might visit. This distribution balances the needs of different policies through Mixture Allocation, so that each policy's value estimate can obtain sufficient information.

The regularization term controls the complexity of the shared sampling distribution. The algorithm introduces an instance-dependent difficulty measure $\rho^\star$ (no larger than the feature dimension $d$), which characterizes the inherent difficulty of designing a shared sampling distribution. When $\rho^\star$ is small, it indicates strong commonality among policies and high shared sampling efficiency; otherwise, the difficulty increases.

Ridge regression estimator and its role in bandit evaluation: Ridge regression is a linear regression method that adds an L2 regularization term $\lambda |\theta|_2^2$ to ordinary least squares, with the closed-form solution $\hat{\theta} = (\mathbf{X}^\top \mathbf{X} + \lambda \mathbf{I})^{-1} \mathbf{X}^\top \mathbf{y}$. In bandit policy evaluation, ridge regression is widely used to estimate the reward parameter $\theta$ from non-uniformly sampled data, because different contexts have different sampling probabilities, and bias must be corrected through importance weighting or direct weighting of the design matrix. The regularization term $\lambda$ not only prevents overfitting but also ensures the design matrix remains invertible when samples are insufficient, avoiding ill-conditioning. PRISMA's shared estimator uses the same set of sampling data for all target policies, so its design matrix is determined by the mixture distribution, and the bias-variance tradeoff of ridge regression is directly affected by the quality of the mixture distribution.

Meaning of Mixture Allocation: Mixture Allocation refers to combining several base sampling distributions into a global sampling distribution with certain weights. In PRISMA, each target policy corresponds to an ideal distribution that minimizes its value estimation variance (called the optimal design for that policy), but the algorithm cannot sample separately for each policy, so it needs to find a mixture distribution that covers all policies sufficiently well. The choice of mixture weights is automatically determined by a regularized optimization problem, with the goal of balancing estimation errors across policies.

Sample Complexity and Theoretical Guarantees

The sample complexity upper bound given in the paper is $\widetilde{\mathcal{O}}\left( \frac{(L^2S^2+\beta^2)(1\vee\rho^\star)}{\varepsilon^2} \cdot \log(K) \right)$, where $L$, $S$, and $\beta$ bound the feature norm, reward parameter norm, and reward noise, respectively. The $\log(K)$ term indicates that the cost of evaluating $K$ policies grows only logarithmically with the number of policies.

This result has several notable features. First, the algorithm does not require prior knowledge of a numerical lower bound on the second-moment eigenvalues, avoiding the ill-conditioning issues common in traditional methods. Second, the complexity does not explicitly depend on the cardinality of the context and action spaces, meaning the method can scale to large or even continuous spaces. Furthermore, policy query costs are accounted for separately: each shared planning context requires $K$ queries, which is separated from reward observation costs, better matching real-world scenarios where query and observation costs differ.

Explanation of parameters in the sample complexity: In the formula, $L$ typically denotes the norm upper bound of feature vectors, i.e., for all contexts $x$, $|x|_2 \leq L$; $S$ is the norm upper bound of the true reward parameter $\theta^\star$, i.e., $|\theta^\star|_2 \leq S$, which controls the scale of the value function; $\beta$ is the scale parameter of the reward noise (usually assumed sub-Gaussian), controlling the magnitude of random fluctuations in observations. $\rho^\star$ is an instance-dependent difficulty measure, typically defined in terms of the "effective rank" of the design matrix or the degree of conflict between policies, ranging from $1$ to $d$. $1 \vee \rho^\star$ denotes the maximum of $1$ and $\rho^\star$. The $\widetilde{\mathcal{O}}$ notation hides logarithmic factors. Overall, the upper bound depends only logarithmically on $K$, achieved through shared sampling, whereas traditional independent sampling methods incur a linear $K$-fold increase.

Why the second-moment eigenvalue lower bound assumption matters: In many linear bandit analyses, the algorithm needs to know that the smallest eigenvalue of the design matrix has a positive lower bound to guarantee fast convergence of ridge regression estimates. However, in practice, feature distributions may be extremely imbalanced, and the smallest eigenvalue may be very small or even zero (e.g., some directions are never sampled), in which case classical results fail or require explicit exploration. PRISMA avoids this requirement through adaptive regularization and shared design, making it applicable to a broader range of instances.

Adaptive Regularization: No Need to Know the Difficulty Parameter

A practical highlight of PRISMA is the Adaptive Doubling Procedure, which can select an appropriate regularization scale without knowing $\rho^\star$. $\rho^\star$ itself is instance-dependent and difficult to compute in advance. The adaptive strategy gradually adjusts the regularization strength, balancing exploration and exploitation.

This design allows PRISMA to strike a good compromise between theoretical guarantees and practical feasibility. The paper's proof techniques combine reward-free planning, regularized least squares, and uniform convergence analysis, providing a relatively complete theoretical framework for multi-policy evaluation.

Adaptive Doubling Procedure is a general technique for online tuning of algorithm hyperparameters when problem parameters are unknown. The basic idea is: start from an initial guess, run the algorithm and monitor certain statistics (e.g., estimation error or design matrix condition number); if the current parameter is found to be too small and fails to meet theoretical conditions, double the parameter and restart. Since the true parameter value usually lies within a finite range, the number of doublings is at most proportional to the logarithm of the parameter, so this "guess-verify-double" strategy incurs only logarithmic overhead. In PRISMA, adaptive doubling is used to determine the regularization strength $\lambda$, matching the unknown $\rho^\star$. Although this process increases implementation complexity, it avoids the unrealistic requirement of knowing the instance difficulty in advance, an important step toward making theoretical results practical.

Potential Impact and Limitations

PRISMA provides a new theoretical tool for multi-policy evaluation, and its logarithmic dependence on $K$ is especially suitable for scenarios requiring simultaneous comparison of many candidate policies, such as A/B testing in recommendation systems and comparison of medical treatment plans.

However, the method is currently based on the assumption of linear reward structure. Its applicability to nonlinear or more complex reward models remains to be studied. In addition, although $\rho^\star$ need not be known in advance, its magnitude still affects practical performance. How to characterize this parameter more tightly is also a future direction.

Overall, this work represents an important step in multi-policy evaluation for stochastic linear bandits, and its "explore once, evaluate many" idea is inspiring for reducing policy evaluation costs.

One-line Summary

PRISMA reduces the cost of simultaneously evaluating K policies to a logarithmic level through shared sampling and regularized information sharing.

Paragraph Summary

This article introduces the PRISMA algorithm from arXiv for simultaneous value evaluation of multiple policies in stochastic contextual bandits. Traditional methods sample independently for each policy, with costs growing linearly with the number of policies K; PRISMA uses a shared sampling design of "explore once, evaluate many" to reduce sample complexity to O(log K). The algorithm consists of reward-free planning, regularized sampling design, and a shared ridge regression estimator, and introduces an instance difficulty measure ρ* to control the complexity of the shared distribution. Theoretically, its sample complexity upper bound does not explicitly depend on the cardinality of context and action spaces, nor does it require a second-moment eigenvalue lower bound, and through an adaptive doubling procedure it does not need to know ρ* in advance. The method is based on the linear reward structure assumption and is suitable for scenarios requiring extensive policy comparison such as recommendation system A/B testing; nonlinear extensions are a future direction.