PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Spyros Dragazis, Yilei Chen, Aldo Pacchiano

arXiv:2610.22252v1cs.LGstat.ML

TL;DR

Evaluating many fixed policies can require costly reward observations, even when querying them on existing contexts is inexpensive. PRISMA uses reward-free shared-context planning and one shared linear reward model to estimate their values, with an instance-dependent guarantee that does not require a numerical eigenvalue lower bound or explicit dependence on context and action space sizes.

  • Problem

    It is often unclear which of many candidate policies will perform best in the population where it will be deployed, while evaluating recommendations requires costly reward observations.

    Source: §1 · p. 1

  • Method

    PRISMA uses reward-free queries on shared contexts to construct a sampling mixture, then fits one linear reward model to evaluate all target policies.

    Source: §1 · p. 2

  • Results

    With probability at least 1 −δ, PRISMA estimates every target policy’s value to accuracy ε, with an instance-dependent uncertainty measure ρ⋆≤d.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The guarantees avoid explicit dependence on context and action space cardinalities and require no numerical lower bound on second-moment eigenvalues.

    Source: §6 · p. 11

    The analysis upper-bounds evaluation cost using ρ⋆ but does not establish that this quantity is necessary.

    Source: §6 · p. 11

Abstract

from arXiv · show

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-\delta$. The algorithm uses $\widetilde{\mathcal{O}}\!\left( \frac{(L^2S^2+\beta^2)(1\vee\rho^\star)}{\varepsilon^2} \cdot \log(K) \right)$ context draws and reward observations, where $\rho^\star\le d$ is an instance-dependent measure of the difficulty of designing a shared sampling distribution. Here, $L$, $S$, and $\beta$ bound the feature norm, reward parameter norm, and reward noise, respectively, and the suppressed factors are logarithmic in $K$, $d$, and $1/\delta$. 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.

1 Introduction

Evaluating many candidate policies matters when their deployment-population performance is uncertain and reward observations are costly. The paper proposes PRISMA for simultaneous evaluation under linear reward structure, with logarithmic explicit dependence on policy count in the context and reward sample bounds.

1 Introduction

  • Candidate policies can arise from different training procedures, architectures, and hyperparameters, while their population performance may remain unclear.The motivating settings include pretrained treatment-recommendation models and policies deployed in a new market.Source: §1 · p. 1
  • The target problem is simultaneous high-confidence evaluation of fixed policies, motivated by choosing a near-optimal policy or identifying policies above a value threshold.Evaluating each candidate separately requires a separate reward budget, even when decisions overlap or feature representations permit sharing.Source: §1 · p. 1
  • The paper asks whether linear structure permits logarithmic explicit dependence on policy count and no context- or action-space cardinality dependence in context and reward sample bounds.A regularized design and adaptive doubling select the regularization scale and budgets without knowing ρ⋆.Source: §1 · p. 2
  • PRISMA uses reward-free queries on shared contexts to construct a sampling mixture, then fits one linear reward model to evaluate all target policies.The result is for stochastic contextual bandits with a known feature map and linear conditional mean reward.Source: §1 · p. 2
  • The method estimates every target policy’s value to accuracy ε with probability at least 1 − δ, with policy-query costs accounted for separately.Each shared planning context requires one query to every target policy; the supplied passages do not include the sample-complexity expression.Source: §1 · p. 2

2 Problem Formulation

The formulation is a stochastic contextual linear bandit with known policies and feature map, sampled contexts, and rewards generated by a linear conditional mean. The task is to estimate all target-policy values simultaneously under bounded-feature and coverage assumptions.

2 Problem Formulation

  • The learner receives independent contexts from an unknown distribution and may choose a target policy for each context before sampling its action and observing reward.The policies map contexts to action distributions, and rewards are conditionally generated from a fixed distribution.Source: §2 · pp. 2–3
  • Reward-free queries let the learner sample each policy’s action and compute its feature vector without executing the action or observing its reward.Context samples, policy queries, and reward observations are counted separately; context and action spaces may be infinite.Source: §2 · p. 3
  • The evaluation task is to output estimates for all K target policies that meet a prescribed accuracy and confidence requirement.The probability guarantee is over data-collection and algorithm randomness.Source: §2 · p. 3
  • Known constants L and S bound feature and parameter norms and control feature-estimation error and regularization bias.The paper states that avoiding prior knowledge of these bounds is beyond its scope.Source: §2 · p. 3
  • Coverage requires each target policy’s feature second-moment matrix to be positive definite, but imposes no numerical lower bound on its smallest eigenvalue.The feature distribution induced by each target policy must span R^d.Source: §2 · p. 3

3 Planning Phase

The planning phase uses shared, reward-free policy queries to estimate feature quantities and select a mixture for evaluating all target policies. Regularization enables the empirical design to avoid requiring a numerical eigenvalue lower bound.

3 Planning Phase

  • The linear design replaces explicit state–action visitation distributions and importance weights with a sampling problem expressed through the feature dimension d.This avoids a representation indexed by context–action pairs, which can be costly for large spaces or unsuitable for infinite spaces.Source: §3 · p. 4
  • The design selects a mixture to minimize the largest target-policy value-estimation uncertainty, measured by ρ(µ), with benchmark ρ⋆ = min over mixtures ρ(µ).The leading variance term scales as ˜O((LS+β)^2ρ(µ)/ε^2), and ρ⋆ is at most d.Source: §3 · p. 5
  • Shared contexts allow feature means and second moments for every policy to be estimated directly without observing rewards.The same context batch is queried under each policy, with fresh policy-action randomness.Source: §3 · pp. 5–6
  • The method estimates Σk + λI to constant multiplicative accuracy, making the concentration bound depend on λ rather than a lower bound on Σk’s eigenvalues.The regularization parameter is later chosen to balance planning cost against regularization bias in value estimation.Source: §3 · p. 6
  • The empirical regularized design is a convex optimization problem, and its selected mixture’s uncertainty is bounded in terms of the unregularized benchmark ρ⋆.The mixture is then deployed in the sampling phase, with regularization bias accounted for in value estimation.Source: §3 · pp. 6–7

4 Sampling phase

The sampling phase deploys the planned mixture, estimates all target values using shared feature-mean estimates and one ridge-regression reward model, and controls feature-mean error, regularization bias, and reward noise. The supplied guarantee states simultaneous ε-accuracy when the stated condition on r̂j holds.

4 Sampling phase

  • PRISMA’s estimator combines feature-mean estimates with a single linear reward model fitted by ridge regression.The reward model is fitted using rewards collected under the selected mixture.Source: §4 · pp. 7–8
  • The reward batch executes actions from the selected mixture, while feature-mean queries use fresh contexts shared across all policies and require no reward observations.The planning data, feature-mean batch, and reward batch are treated as independent in the procedure.Source: §4 · pp. 7–8
  • The value-estimation error is split into feature-mean error, regularization bias, and reward noise, with error allocated ε/2, ε/4, and ε/4 respectively.Separate batches for feature means and reward-model fitting simplify the dependence structure in the analysis.Source: §4 · pp. 7–8
  • The reward-noise term is bounded simultaneously over policies, and on the stated concentration events each Qk is at most 48ρ⋆ + 60.Under those events, the noise contribution is at most ε/4 when the corresponding reward-sample condition holds.Source: §4 · p. 9

5 Algorithm and guarantees

PRISMA uses an adaptive sequence of regularized empirical designs to select a shared sampling mixture, then evaluates all target policies from fresh feature-mean and reward batches. Its guarantee bounds every value error and the context and reward resources in terms of the accepted scale.

5 Algorithm and guarantees

  • PRISMA tests increasing regularization scales rj = 2j and accepts a scale when the empirical design objective is at most 9rj.The unknown ρ⋆ determines the sufficient scale, and ρ⋆≤d ensures the search through J = ⌈log2 d⌉ stages suffices.Source: §5 · p. 10
  • The stated budgets assume L, S > 0 and 0 < ε < LS; returning zero for every policy suffices when ε ≥LS.The sample-budget choices control regularization bias and reward noise using the accepted scale.Source: §5 · p. 10
  • With probability at least 1 −δ, PRISMA bounds every policy’s value error by ε and the accepted scale by 2(1 ∨ρ⋆).It terminates by stage J = ⌈log2 d⌉.Source: §5 · p. 10
  • After acceptance, PRISMA forms a mixture from planning data, collects fresh feature means and reward observations, and returns values using a shared ridge-regression model.The theorem assumes the empirical design problems are solved exactly.Source: §5 · pp. 10–11
  • The context-draw and reward-observation totals each obey the theorem’s stated resource bound on the same success event.For every realization, the corresponding resource bounds hold with 1 ∨ρ⋆ replaced by d.Source: §5 · p. 11

6 Discussion

The discussion identifies the scope of the guarantees and two open directions: extending the approach beyond contextual bandits and establishing whether ρ⋆ captures intrinsic evaluation difficulty.

6 Discussion

  • The guarantees concern stochastic contextual bandits with linear rewards, known feature maps, and shared sampling, without context- or action-cardinality dependence or an eigenvalue lower bound.The authors identify linear MDPs and more general function approximation as directions for extension.Source: §6 · p. 11
  • In linear MDPs and broader function-approximation settings, policy-dependent future states prevent direct feature-moment estimation from a shared policy-independent context distribution.The paper names this as an additional challenge to extending the techniques.Source: §6 · p. 11
  • Whether ρ⋆ captures intrinsic difficulty remains open because the analysis gives an upper bound but no necessity result or matching lower bounds.Such lower bounds could clarify when target-policy mixtures achieve optimal evaluation cost and whether broader sampling strategies can improve it.Source: §6 · p. 11

AI disclosure

The paper reports AI assistance during manuscript preparation and includes an appendix figure outlining its two-phase procedure.

AI disclosure

  • The authors used GPT-6 Astra and Sol in iterative discussions to polish the manuscript, work through concentration calculations, identify proof gaps, and refine proof presentation.The authors state they remain responsible for the final manuscript’s correctness and originality.Source: AI disclosure · p. 11

Appendix

  • Figure 1 depicts reward-free policy queries during planning, one executed action per sampling context, and a separate fresh batch for feature means.The reward dataset from sampling is reused to estimate all K policy values.Source: Figure 1 · p. 15

A Overview of our method

The method separates reward-free planning from reward collection and evaluation, using shared contexts and feature structure to reuse information across target policies. Its analysis develops high-probability bounds for the shared-mixture estimator and for estimating feature means.

A Overview of our method

  • Planning estimates target-policy feature means and second moments without rewards, then uses a regularized design to choose a mixture and sampling budgets.Fresh sampling data fit one ridge-regression model, which combines with separately estimated feature means to produce all policy values.Source: A Overview of our method · p. 15

B Related work

  • Unlike tabular shared-sampling approaches, the method uses linear feature representations to share information across policies taking different actions.The design controls maximum uncertainty across target policies and uses reward-free feature queries; policy queries still scale as K per shared context.Source: B Related work · p. 16

C Planning phase

  • The planning analysis invokes Bernstein’s inequality for independent, bounded, mean-zero variables to prove Lemma 1.The cited inequality is for controlling sums of such random variables.Source: C Planning phase · p. 16

C.1 Proof of Lemma 1

  • Lemma 1 gives a high-probability guarantee for the estimators when population feature means and second moments are known, and also applies conditionally with independent planning data.The guarantee is simultaneous over target policies.Source: §C.1 · pp. 16–18

C.2 Proof of Proposition 1

  • The optimal design complexity satisfies ρ⋆≤d.The proof establishes this bound using the design objective and minimax reasoning.Source: §C.2 · pp. 18–19

C.3 Proof of Lemma 2

  • With high probability, the estimated feature means are accurate simultaneously across all K target policies when contexts are shared and each policy is queried on them.The feature vectors are bounded in norm by L.Source: §C.3 · pp. 19–20

C.4 Proof of Lemma 3

The proof uses matrix concentration to control empirical policy second moments after regularization. This yields simultaneous bounds for all target policies without requiring independence between policies that share contexts.

C.4 Proof of Lemma 3

  • With probability at least 1 −δ, every target policy’s regularized empirical second-moment matrix lies between one-half and three-halves of its population counterpart.The proof applies matrix Bernstein to normalized second-moment errors and uses a union bound across policies.Source: §C.4 · pp. 21–23
  • The proof normalizes each sampled feature outer product by the regularized population matrix, then applies matrix Bernstein to the centered matrices.The population matrix is used only in the analysis.Source: §C.4 · pp. 21–22
  • The simultaneous guarantee does not require independence between policies that use the same context.A union bound over policies controls the probability that any policy’s inequality fails.Source: §C.4 · p. 23

C.5 Proof of Lemma 4

The proof establishes uniform comparisons between empirical and population regularized design objectives, then applies concentration arguments to shared ridge estimation under the reward model.

C.5 Proof of Lemma 4

  • With probability at least 1 −δ, every minimizer of the empirical design objective satisfies the stated guarantee.The supplied passage states the probability and minimizer condition but does not include the guarantee’s expression.Source: §C.5 · p. 23
  • The empirical and population design objectives are compared in both directions, simultaneously for every mixture.The proof defines the regularized population benchmark as the minimum of Fλ over the simplex.Source: §C.5 · p. 24

D.1 Proof of Lemma 5

  • Lemma 5’s proof substitutes the linear reward model into the shared ridge estimator.The estimator is defined as ˆθ := B−1˜g.Source: §D.1 · p. 25

D.2 Proof of Lemma 6

The proof conditions on the planning and sampling data so that the estimator’s matrices and feature vectors are fixed, then controls reward-noise contributions across policies.

D.2 Proof of Lemma 6

  • With probability at least 1 −ζ, the stated bound holds simultaneously for all K policies, both conditionally and unconditionally.A union bound over target policies gives the conditional guarantee before taking expectations over the data.Source: §D.2 · pp. 25–26
  • Conditionally on the planning data, feature-mean batch, and reward-batch contexts and actions, the noise terms are independent and bounded.The proof applies Hoeffding’s inequality to the centered noise contributions.Source: §D.2 · p. 26
  • If β = 0 or the relevant sum is zero, the proof treats the noise contribution as zero almost surely.In those cases the desired conclusion follows immediately.Source: §D.2 · p. 26

E.1 Proof of Theorem 1

The theorem establishes simultaneous ε-accuracy and instance-dependent resource bounds for PRISMA under its stated assumptions. Its proof also shows deterministic termination with resource bounds that can use d in place of the instance-dependent quantity.

E.1 Proof of Theorem 1

  • PRISMA terminates by stage J = ⌈log2 d⌉, and deterministic resource bounds replace 1 ∨ρ⋆ with d.The proof establishes termination for every realization.Source: §E.1 · pp. 27–28
  • Under Assumptions 1 and 2, the stochastic reward model in Equation (1), and exact PRISMA empirical-design solutions, max k∈[K] |V̂k−Vk| ≤ ε and r̂j ≤ 2(1∨ρ⋆).Source: §E.1 · pp. 26–27
  • The context-draw and reward-observation counts satisfy the theorem’s instance-dependent resource bounds with probability at least 1 −δ.The supplied passages do not include the expressions for these bounds.Source: §E.1 · p. 27
  • The proof bounds the empirical design objective by d, ensuring that the final stage satisfies the acceptance criterion.At the final stage, r_J ≥ d.Source: §E.1 · p. 27
Loading 2610.22252v1…