Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback

Shuang Wu

cs.LGOct 13, 2026

Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback

Authors: Shuang Wu

Organizations: UCLA

Abstract

Gaussian process bandits exploit similarities among configurations to optimize prompts, retrieval systems, and agent workflows. In these applications, however, inexpensive model-based evaluations can disagree with trusted task outcomes. We study selective verification when an action is chosen before a diagnostic is observed and trusted feedback is informative on an unknown set of diagnostic states. A finite reliability class and a finite RKHS signal dictionary describe these two sources of uncertainty. We construct a fixed audit design that combines reliability coverage with reward separation and establish a finite-time regret bound that accounts for a hard audit budget and the rounds needed to obtain informative observations. A safe adaptive extension mixes this robust design with predictable Chernoff allocations while preserving a uniform identification floor and exact expected acquisition-cost accounting. For signed-coordinate kernels, structured and diffuse reliability classes require different audit scales despite sharing the same reward geometry. Synthetic experiments distinguish these certified designs from an adaptive posterior heuristic and GP controls. Safe adaptive allocation reduces aggregate regret relative to the fixed design under the exact dictionary, but its finite-budget error certificate is numerically loose. Conditional-feedback errors can remove the heuristic's advantage and target perturbations can reverse it. Separate AI-task replays assess feedback correction and fitted-dictionary policies without establishing end-to-end validation of a learned selective-verification method.

Figures & tables

Figure 1: Selective-verification protocol. (a) Given the observed history

\mathcal{F}_{t-1}

, actions precede diagnostics, which inform the audit decision. Dashed arrows show when a purchased outcome enters the update. (b) Reliability coverage and action separation bound the squared-mean margin per audit. The factors

\chi(\bm{p})

and

C_{\times}

charge acquisition time and regret. Proposition 4 adds predictable adaptive allocation.

n\leftarrow n+1,\qquad\ell_{h,z}\leftarrow\ell_{h,z}+\log p_{h,z}(Y_{t}\mid X_{t},s)\quad\text{for all }(h,z).

Algorithm 1 Reliability-Kernel-Design

Figure 2: Conditional feedback under a hard audit cap, with 256 paired replications in each of 36 settings. Left: geometric mean cumulative-regret ratios relative to pooled TS . Right: mean terminal simple regret. Lower values are better. Shading in (a) is a paired-bootstrap 95% interval conditional on the fixed settings. The full setting-level comparison and audit-completion panel appear in Figure 3 .

Policy	Cumulative regret $\downarrow$	Simple regret $\downarrow$
Conditional TS	$\mathbf{92.24}\pm 2.58$	$\mathbf{.0198}$
Candidate-gated pooled TS	$99.92\pm 2.58$	$.0219$
All-round joint TS	$106.09\pm 2.62$	$.0241$
All-round pooled TS	$124.30\pm 2.66$	$.0287$
GP-UCB	$119.27\pm 2.64$	$.0275$
GP-TS	$130.40\pm 2.65$	$.0292$

Table 1: Independent GP comparison on 24 settings and 128 paired replications per setting. Entries average settings equally. Cumulative regret is mean

\pm

Monte Carlo standard error, computed as

[\sum_{c=1}^{24}s_{c}^{2}/128]^{1/2}/24

, where

s_{c}^{2}

is the within-setting sample variance. Bold marks the lowest mean in each regret column, not statistical significance. GP and identity rows use default parameters. Development-selected variants and audit counts appear in Table 4 .

Comparator	Regret ratio $\downarrow$	Acquisition-time ratio $\downarrow$
Fixed robust joint design	.916	2.554
Pure adaptive design	1.006	.827
Product design	.916	4.764
Uniform action and verification	.907	4.764
Optimized action, uniform verification	.921	4.764
Audit-only dictionary TS	.943	4.764

Table 2: Supplementary safe-adaptive comparisons on 24 settings with 512 paired replications. Regret and time are geometric ratios to the comparator. Time is the round of the

M

th audit. Ratios below one favor safe adaptive. Every policy uses

T

deployments and

M

labels. Table 3 gives per-setting uncertainty classifications and decision errors.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Complete primary synthetic comparison. Panels (a) and (b) show cumulative-regret ratios and terminal simple regret. Panel (c) compares all 36 settings with pooled TS . Circles and triangles indicate candidate-state probabilities

1

and

.25

, and points below the diagonal favor conditional TS . Panel (d) reports the fraction reaching the audit cap by the horizon when 75% of states are uninformative. There are 256 paired replications per setting. Shading in (a) is a paired-bootstrap 95% interval. The red curve denotes pooled maximum likelihood in (a) and pooled TS in (b).

Comparator	Regret ratio	Time ratio	Error (pp)	Lower	Unclear	Higher
Fixed robust joint design	.916	2.554	$-7.06$	13	11	0
Pure adaptive design	1.006	.827	$+0.66$	0	24	0
Product design	.916	4.764	$-6.89$	12	12	0
Uniform action and verification	.907	4.764	$-7.71$	11	13	0
Optimized action, uniform verification	.921	4.764	$-6.96$	11	12	1
Audit-only dictionary TS	.943	4.764	$-4.92$	6	18	0

Appendix

Table 3: Supplementary certified-adaptive comparisons on 512 paired replications per setting. Regret and time are safe/comparator geometric ratios across all 24 settings; time is the round of the

M

th audit. Error is the mean difference in final wrong-decision rate, in percentage points, so negative values favor safe adaptive. Lower, unclear, and higher count settings in which the paired 95% interval places safe-adaptive regret below, across, or above the comparator. The intervals are unadjusted descriptive comparisons, so unclear does not establish equivalence. Comparator choices followed the fresh suite and are not independent confirmation.

Policy	Cumulative regret $\downarrow$	Standard error	Simple regret $\downarrow$	Audits
Conditional TS	92.24	2.58	.0198	446.14
Candidate-gated pooled TS	99.92	2.58	.0219	446.14
All-round joint TS	106.09	2.62	.0241	448.00
GP-UCB , default	119.27	2.64	.0275	448.00
GP-UCB , selected	122.34	2.65	.0276	448.00
Identity-UCB , selected	123.17	2.72	.0284	448.00

Appendix

Table 4: Independent Gaussian-process control suite. Means average the 24 fixed settings equally. SE is

[\sum_{c=1}^{24}s_{c}^{2}/128]^{1/2}/24

, where

s_{c}^{2}

is the within-setting sample variance. Bold denotes the lowest mean regret. “Selected” denotes the setting chosen on the separate development grid.

Scenario	Conditional regret	Pooled regret	Geometric ratio
Nominal	54.8	88.1	.572
Feedback error $.10$	78.0	88.4	.875
Feedback error $.20$	90.8	89.2	1.027
Feedback flattened	92.4	87.4	1.068
Target perturbation $.05$	263.1	199.1	1.398
Target perturbation $.10$	350.7	204.5	1.799

Appendix

Table 5: Robustness suite. Means are final cumulative target regret; ratios are geometric means over six cells per scenario.

Figure 4: Misspecification defeats the nominal advantage. Feedback perturbations preserve target rewards; target perturbations shift both rewards and outcome means. Bars show geometric mean ratios with paired-bootstrap 95% intervals conditional on six cells.

Mean cumulative regret: shared calibration endowment
	$T=512$		$T=2048$
Method / comparison	$M=16$	$M=64$	$M=16$	$M=64$
Calibration greedy	0.000	0.000	0.000	0.000
Calibration only	9.327	9.242	37.190	37.015
Uniform audits	9.090	8.252	35.885	33.249
State-aware audits	9.040	8.566	36.315	34.649

Appendix

Table 6: JudgeBench conditional-correction development replay. Lower cumulative target regret is better. Calibration-informed methods share 144 offline labels and 1,584 archived judge outputs; audit-only receives neither. Negative paired differences favor state-aware audits; all 95% intervals include zero. Bold marks the lowest mean, not significance.

$T$	$M$	State-aware audits			Uniform audits
		Reveals	Unique	Reuse	Reveals	Unique	Reuse
512	16	14.6	13.5	1.1	14.4	13.4	1.0
512	64	61.0	44.4	16.6	61.3	45.6	15.8
2048	16	14.5	13.5	.9	14.3	13.4	.9
2048	64	60.8	44.2	16.6	60.5	45.1	15.4

Appendix

Table 7: JudgeBench online acquisition. “Reveals” counts trusted-label requests. “Unique” counts distinct development items, and “reuse” is their difference. Values are Monte Carlo means. Offline calibration costs are additional.

$T$	$M$	Uniform verified TS	RK design $k=1$	RK design $k=2$
512	16	5.469	58.801	80.364
512	64	4.921	62.836	113.122
2048	16	21.758	232.605	288.367
2048	64	19.090	238.288	312.919

Appendix

Table 8: Non-confirmatory JudgeBench execution of Algorithm 1 . RK denotes Reliability-Kernel-Design . Entries are mean cumulative regret across 512 repetitions. Lower is better. Both prespecified dictionary sizes and all four cells are retained.

One reliable state ( $k=1$ )
$T$	$M$	Full reliability class	Two fitted reliability sets
1,024	32	$32.20\pm.92$	$\mathbf{31.79}\pm.93$
1,024	128	$36.09\pm.82$	$\mathbf{35.65}\pm.83$
4,096	32	$127.10\pm 3.79$	$\mathbf{125.76}\pm 3.79$
4,096	128	$140.88\pm 3.63$	$\mathbf{139.90}\pm 3.64$
Two reliable states ( $k=2$ )

Appendix

Table 9: Thirty-two-judge development replay: cumulative regret, mean

\pm

Monte Carlo standard error from 512 paired replications. Each method keeps the same two fitted signals and uniform state gate. The full-class method includes all reliability sets of size

k

in its decoder, while the matched control includes only the two fitted sets. Bold denotes the lower mean in each row, not a significant difference.

Identity or guarantee	Evaluation systems	Observed discrepancy or check
Product separation	180 random dictionaries; 40 coordinate cases	Minimum normalized margin $.9999999999999989$ ; coordinate error $1.74\times 10^{-18}$
Deterministic coverage	1,440 LP cases from 240 set systems	Hitting error $8.88\times 10^{-16}$ ; coverage violation $2.22\times 10^{-16}$
Bernoulli testing bounds	2,000 separation cases; 100,000 KL and 251,001 Hellinger comparisons	No inequality violation; observed separation at least twice the conservative threshold
Causal acquisition	6,300 stationary programs; 5,000 occupancy programs; 45,157 adaptive histories	Acceptance-law error $3.34\times 10^{-16}$ ; causal cost error $1.14\times 10^{-13}$
Finite-horizon accounting	1,000 joint designs; independent forward recursion	Design-length error $4.27\times 10^{-14}$ ; regret error $2.85\times 10^{-14}$
Adaptive information floor	144 development systems and measured adaptive laws	Minimum information divided by $\varepsilon I_{0}$ equals one

Appendix

Table 10: Numerical verification by scientific purpose. Errors are maximum absolute discrepancies unless the entry specifies a ratio or a violation count. Identity checks and synthetic theorem diagnostics are distinct from the policy comparisons reported in Section 6 .

Comparator	Established capability	Distinction tested here
ASB [ 3 ]	post-surrogate acquisition, learned residual error, hard budgets	latent reliability dictionary and kernel decision geometry
Multi-rejection [ 28 ]	exact reuse under multiple collection policies	hard-budget regret and latent reliability learning
Cost-aware GP [ 8 ]	optional labels and cost-adjusted kernel information gain	post-state reliability and hard pathwise audits
Controlled sensing [ 18 , 22 ]	adaptive control and likelihood testing	latent reliability cost under action-before-state timing
Auxiliary IGP-UCB [ 1 ]	kernelized parameterized auxiliary feedback	audit scarcity and latent reliable-state dictionary
PP-LUCB [ 2 ]	selective audits for identification	cumulative regret and kernel action geometry

Appendix

Table 11: Comparison of feedback protocols, guarantees, and modeling assumptions.

Explore similar work

Sep 28, 2026

Verifier Errors in RLVR: Reward Hacking, Limits of Feedback, and Selective Control

In reinforcement learning with verifiable rewards (RLVR), imperfect verifiers can reward incorrect responses, creating opportunities for reward hacking. Using gradient flow with a fixed verifier, we characterize the conditions under which reward rises while correctness falls. We then show that the observations available during RLVR are, in general, insufficient to detect or identify accepted errors, or to guarantee their reduction without sacrificing correct responses. To address this limit, we construct a correction using additional feedback about correctness from audits. This correction achieves selective control: at the current policy, it lowers the probability of accepted errors and raises that of correct responses, provided it outweighs the pressure toward errors from verifier reward. Experiments with log linear and neural contextual bandits and with a language model support the analysis and show that selective control under partial auditing reduces accepted errors while increasing correctness.

Christian Moya, Elliott Thornley, Guang Lin

Purdue University · National University of Singapore

Reward Hacking Reinforcement Learning Reinforcement Learning with Verifiable Rewards Reward Design for RL

Ask PDF

Aug 21, 2026

The geometry of AI validation: From structural blindness to reusable audits

AI systems increasingly search among candidate answers and deploy the highest-scoring one. Increasing search changes which errors matter, so a precise evaluation at one computation budget can leave another budget unresolved. We connect this information gap to the cost of closing it. For independent best-of-n search, aggregate reliability measurements identify deployment only through the directions they observe; we derive an exact ambiguity frontier when only small search widths are audited. Retaining candidate ranks and truth labels enables a constructive alternative: one audit can estimate reliability across all widths up to N. With known score percentiles, the minimax worst-coordinate mean squared error scales as (1 + log N)/T + N/M, capped at a constant, for expected budgets of T truth labels and M candidate observations. Matching lower bounds allow adaptive label acquisition, establishing that the distinct label and candidate costs are intrinsic to this experiment. An explicit design attains this order; a complementary record-based procedure supplies simultaneous guarantees without a known score distribution. Retrospective mathematical-reasoning and code-generation analyses show why search-dependent validation matters. In held-out CodeRM pools, a shared audit reduces the 95th-percentile maximum error across 100 widths by 58% and 40% relative to uniform labeling. These results turn structural ambiguity into a quantitative prescription for reusable validation.

Ricardo Fitas

Technical University of Darmstadt, 64289 Darmstadt, Germany

Automated Evaluation Algorithmic Auditing Minimax Estimation

Ask PDF

Sep 28, 2026

Test-Time Scaling via Budgeted Multi-Attribute Verification

Verifying LLM-generated answers under a shared computational budget requires jointly deciding which candidates to inspect and which verification attributes to evaluate. We formulate this problem as multi-attribute good-arm identification under a global budget: each candidate is an arm evaluated along several costly attributes, and the goal is to certify as many candidates as possible whose mean scores exceed the prescribed thresholds on all attributes. We propose BMA-GAI, an algorithm that combines cost-aware arm selection with adaptive sampling of attributes. Every observation serves both to guide adaptive allocation and to support anytime-valid certification, which removes the need for a separate confirmation stage. We establish an asymptotic coverage guarantee for BMA-GAI and derive a matching information-theoretic converse that characterizes the intrinsic complexity of the problem, thereby proving that BMA-GAI is first-order optimal away from critical budget levels. Experiments on synthetic benchmarks and an LLM answer-verification task show that BMA-GAI allocates the verification budget more efficiently and certifies more high-quality candidates than competing methods.

Bo Xue, Ji Cheng, Shen-Huan Lyu +2

City University of Hong Kong · Hohai University · Zhejiang University

Multi-Armed Bandits LLM Answer Verification Cost-Aware Inference

Ask PDF