Paper deep dive
Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback
Shuang Wu
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.17760v1
- Canonical: https://arxiv.org/abs/2610.17760v1
Trouble viewing inline? Open PDF directly →
Full Text
137,834 characters extracted from source content.
Expand or collapse full text
Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback Shuang Wu Affiliation: UCLA Email: shuangwu222@ucla.edu 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. 1 Introduction Language-model judges make repeated evaluation inexpensive, but they can reverse the ranking of prompts, retrieval pipelines, or agent configurations. A Gaussian process (GP) fitted to such scores can estimate the wrong objective precisely. Trusted evaluation—human adjudication, execution in a protected environment, or a high-quality test suite—repairs the target but can dominate total cost. This motivates a bandit that sees cheap post-action information and selectively purchases the trusted outcome. Existing methods cover selective audits, prediction-powered inference, auxiliary-feedback kernel bandits, and post-surrogate acquisition [1, 2, 3, 4]. We ask how many trusted outcomes are required when the learner must discover where feedback is informative. For unrestricted outcome laws, target-kernel rank and a fixed finite collection of conditional statistics do not determine that information. We introduce a finite conditional-reliability class. A known dictionary Ch\C_h\ contains possible informative diagnostic sets, but h is unknown. Its fractional hitting number τ⋆τ measures the audit mass needed to touch every candidate reliable set. We couple this uncertainty to a finite RKHS signal dictionary through a max–min experimental design. The resulting rate depends on reliability coverage and on the action energy needed to distinguish reward models with different optima. For example, RAG configurations differ in their prompts and retrieval pipelines. A cheap diagnostic can reveal request or output categories where trusted correctness distinguishes configurations. A selective policy must discover these categories and acquire informative observations while paying for every intervening deployment. This separates reward geometry, conditional reliability, and acquisition time. Our contributions are: • We prove a finite-time bound with audit scale τ⋆+τ D_+ and characterize the exact expected acquisition cost of a joint action–state design. A safe adaptive mixture preserves a uniform Hellinger-information floor under a pathwise audit cap. A prior-mixture converse permits fully adaptive auditing and infinite signal classes. • For signed rank-d signals, we establish matching polynomial audit scales of dτ⋆/Δ2dτ / ^2 for structured reliability and d(τ⋆)2/Δ2d(τ )^2/ ^2 for a diffuse reliability class. The deterministic structured model admits an exact asymptotic regret coefficient expressed by a coverage problem. • We distinguish feedback-law error from target approximation. Two rank-one dictionaries match any prescribed finite collection of bounded feedback summaries and have identical targets, yet their regret differs by a factor growing as K/logK/ K at a common log2K _2K audit budget. Sequential audit-only controls provide reliability-free comparisons. • We evaluate the proved designs, an adaptive-action posterior heuristic, and GP controls across kernel geometries, overlapping reliability sets, rare states, and model perturbations. AI-task replays examine calibration and acquisition costs without establishing end-to-end validation of a learned reliability model. Figure 1: Selective-verification protocol. (a) Given the observed history ℱt−1F_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 χ()χ( p) and C×C_× charge acquisition time and regret. Proposition 4 adds predictable adaptive allocation. 2 Related work Selective verification and surrogate feedback. Prediction-powered best-arm identification and adaptive inference combine inexpensive predictions with selectively acquired trusted labels [2, 4]. Limited-verification bandits and surrogate-reward bandits study trusted feedback under attacks or machine-learning-generated rewards [5, 6]. ASB permits acquisition after observing a surrogate and accounts for learned refinements and hard budgets [3]. Confidence–budget matching and costly-observation bandits provide reward-only controls [7, 8]. Our question concerns the additional cost of identifying an unknown reliable-state set while optimizing cumulative true reward. Kernel bandits and AI evaluation. Auxiliary-feedback IGP-UCB, prediction-augmented GP-UCB, and robust multi-fidelity optimization exploit additional feedback under structural assumptions [9, 1, 10]. Kernel experimental design and misspecified GP bandits characterize reward geometry and target approximation [11, 12]. Related exploration methods include residual-bootstrap LinReBoot, graph-neural GNN-TS, and Laplacian kernelized bandits [13, 14, 15]. ARES and HbBoPs connect trusted evaluation and kernel optimization to RAG and prompt selection [16, 17]. We study how conditional reliability interacts with kernel decision geometry, rather than a new kernel posterior or a generic correction estimator. Controlled sensing and decision-focused learning. Controlled sensing, decision-region active learning, and transductive design allocate measurements to distinguish consequential alternatives [18, 19, 20, 21, 22]. Best-arm identification with post-action context provides context-tracking and Track-and-Stop rules [23]. These ideas motivate our likelihood decoder and adaptive allocation. Our analysis separates reliability coverage, action separation, and the deployment cost imposed by choosing an action before observing the diagnostic. Partial monitoring and identifiability. Kernelized partial monitoring, conditional mean embeddings, and cost-aware streaming labels provide broader sequential abstractions [24, 25, 26, 27]. Exact rejection sampling implements the desired accepted-query law [28]. Classical best-arm and mixture testing explain the polynomial rates in our structured–diffuse comparison [29, 30, 31], while contaminated and misspecified identification establish related identifiability failures [32, 33]. Our results specialize these tools to a finite reliability–signal dictionary, with an adaptive converse and matched-summary counterexamples. Appendix D compares the assumptions and guarantees in detail. 3 Problem formulation 3.1 AI evaluation protocol and objective Each action is a fixed prompt, retrieval pipeline, or agent configuration used on a fresh request. A cheap diagnostic is observed after deployment, and a trusted assessment is available only if purchased. We optimize expected trusted quality under a stationary action set and kernel. Request-dependent routing and within-agent-step optimization are outside this model. Let A and S be finite, with integer horizon T≥1T≥ 1 and audit cap M≥1M≥ 1. At round t, the learner chooses Xt∈X_t , observes St∈S_t , and then chooses Bt∈0,1B_t∈\0,1\. If Bt=1B_t=1, it spends one audit and observes Yt∈0,1Y_t∈\0,1\. The policy satisfies ∑t=1TBt≤M _t=1^TB_t≤ M almost surely. The audit decision may use StS_t, so the lower bounds permit post-state acquisition. 3.2 Conditional reliability and kernel signals Write Δ() (X) for the probability simplex on a finite set X and [x]+=maxx,0[x]_+= \x,0\. States are i.i.d. from a known action-independent law μ, with μmin=minsμ(s)>0 _ = _sμ(s)>0. A known finite family Ch:h∈ℋ\C_h:h \ has μ(Ch)=ρ>0μ(C_h)=ρ>0. Its fractional hitting number is τ⋆=min≥0∑s∈xs:∑s∈Chxs≥1∀h.τ = _ x≥ 0 \ _s x_s: _s∈ C_hx_s≥ 1\ ∀ h \. (1) For an optimizer, ps=xs/τ⋆p_s=x_s/τ obeys p(Ch)≥1/τ⋆p(C_h)≥ 1/τ . Let k be a known positive-semidefinite kernel on A, with RKHS ℋkH_k. A finite signal dictionary =uz:z∈⊂ℋkU=\u_z:z \ _k satisfies ∥uz∥ℋk≤B,∥uz∥∞≤U≤14,az⋆∈argmaxa∈uz(a). u_z _H_k≤ B, u_z _∞≤ U≤ 14, a_z ∈ _a u_z(a). Under environment (h,z)(h,z), audited outcomes are conditionally independent with Yt∣(St=s,Xt=a)∼Bern(12+s∈Chuz(a)).Y_t (S_t=s,X_t=a) \! ( 12+1\s∈ C_h\u_z(a) ). (2) The target is fz(a)=12+ρuz(a)f_z(a)= 12+ρ u_z(a) and RT=∑t=1T[fz(az⋆)−fz(Xt)],RT⋆=infcausal policiessuph,zh,z[RT].R_T= _t=1^T[f_z(a_z )-f_z(X_t)], R_T = _causal policies _h,zE_h,z[R_T]. The known centering constant is 1/21/2, and the kernel models the action-dependent target component. Trusted outcomes are informative about the best action within ChC_h and uninformative outside it. The diagnostic StS_t need not be a reward prediction, and the model does not assume an arbitrary judge is unbiased. Fix one maximizing action az⋆a_z for each signal, including a deterministic tie rule. The learner knows the dictionaries but neither h nor z. Equal reliable-set mass and action-independent μ make the target depend only on z, while h controls information acquisition. This factorization need not hold for action-dependent diagnostics. Appendix B.3 extends only the acquisition rule to a known action-dependent law. Neither result learns or validates the outcome dictionary. 3.3 Decision geometry and scope For ∈Δ() λ∈ (A), define the action-separation margin v+()=min v_+( λ)= \ minza∼[uz(a)2], _zE_a λ[u_z(a)^2], minaz⋆≠az′⋆a∼[(uz(a)−uz′(a))2],V+=maxv+(),+=V+−1. _a_z ≠ a_z E_a λ[(u_z(a)-u_z (a))^2] \, V_+= _ λv_+( λ), D_+=V_+^-1. (3) Writing uz(a)=⟨ϕ(a),ϑz⟩u_z(a)= φ(a), _z , every constraint is linear in λ through ()=∑aλaϕ(a)ϕ(a)⊤ V( λ)= _a _a φ(a) φ(a) . Hence V+V_+ is a pre-outcome linear program, not an oracle posterior quantity. We assume V+>0V_+>0 and at least two different designated optima. The features ϕ(a) φ(a) and coefficients ϑz _z are vectors in a feature representation of k. 4 Selective Verification with Kernel Decision Geometry 4.1 Reliability coverage and kernel action selection Two pre-outcome linear programs determine the policy. State allocation covers every candidate reliable set. Action allocation separates weak individual signals and reward pairs with different optima. Both use the known dictionaries, without knowledge of the true environment. Let ⋆ λ optimize (3). For an optimizer p of (1), define its action-before-state realization factor χ()=maxs∈psμ(s).χ( p)= _s p_sμ(s). Let mh,z(a,s)=12+s∈Chuz(a)m_h,z(a,s)= 12+1\s∈ C_h\u_z(a) and write ph,z(y∣a,s)=mh,z(a,s)y[1−mh,z(a,s)]1−yp_h,z(y a,s)=m_h,z(a,s)^y[1-m_h,z(a,s)]^1-y. Algorithm 1 compiles the product law ⋆⊗ λ p by rejection sampling after the state arrives. The audit coin is drawn only after observing the state, independently of the unobserved outcome conditional on the action, state, and past. For Λ≥1 ≥ 1, define the exact expected number of design rounds before M accepts or horizon end, T,M(Λ)=∑t=0T−1PrBin(t,Λ−1)<M. N_T,M( )= _t=0^T-1 \Bin(t, ^-1)<M\. Algorithm 1 Reliability-Kernel-Design 1. Input: T,M,μ,Ch,uzT,M,μ,\C_h\,\u_z\. Solve (1) and (3) for ,⋆ p, λ . 2. Initialize: n←0n← 0, ℓh,z←0 _h,z← 0 for every (h,z)(h,z). 3. For t=1,…,Tt=1,…,T do 4. If n<Mn<M then draw Xt∼⋆X_t λ and observe St=sS_t=s. 5. Draw Bt∼Bern(ps/[χ()μ(s)])B_t \! (p_s/[χ( p)μ(s)] ). 6. If Bt=1B_t=1 then purchase YtY_t and set n←n+1,ℓh,z←ℓh,z+logph,z(Yt∣Xt,s)for all (h,z).n← n+1, _h,z← _h,z+ p_h,z(Y_t X_t,s) all (h,z). 7. If n=Mn=M then set (h^,z^)∈argmaxh,zℓh,z( h, z)∈ _h,z _h,z. 8. Else play Xt=az^⋆X_t=a_ z , observe StS_t, and set Bt=0B_t=0. 9. End if. 10. End for. 11. Return: az^⋆a_ z if n=Mn=M and “insufficient audits” otherwise. Proposition 1 (Product separation). For any (h,z)(h,z) and (h′,z′)(h ,z ) with az⋆≠az′⋆a_z ≠ a_z , s∼,a∼⋆[(mh,z(a,s)−mh′,z′(a,s))2]≥V+τ⋆,E_s p,a λ [(m_h,z(a,s)-m_h ,z (a,s))^2]≥ V_+τ , where mh,zm_h,z is the Bernoulli mean in (2). The proof partitions the two reliable sets into their overlap and two differences. See Appendix A.1. The product value is also controlled from above for every fixed accepted-query design. Define VΔ V_ =max∈Δ()minaz⋆≠az′⋆a∼[(uz(a)−uz′(a))2], = _ λ∈ (A) _a_z ≠ a_z E_a λ[(u_z(a)-u_z (a))^2], J⋆ J =max∈Δ(×)minaz⋆≠az′⋆(a,s)∼[(mh,z(a,s)−mh′,z′(a,s))2], = _ ν∈ (A×S) _a_z ≠ a_z E_(a,s) ν[(m_h,z(a,s)-m_h ,z (a,s))^2], where the second minimum ranges over all h,h′,z,z′h,h ,z,z with different designated optima. Proposition 2 (Fixed-design sandwich). The exact squared-mean fixed-design value obeys V+τ⋆≤J⋆≤VΔτ⋆. V_+τ ≤ J ≤ V_ τ . Consequently the product design is exact whenever its individual-energy constraints are nonbinding, V+=VΔV_+=V_ . A product dual certificate gives the upper bound (Appendix A.2). The individual energy constraints in (3) are essential. Pairwise action separation alone can be hidden outside the overlap of two reliability sets. The method remains finite-dictionary and exact-kernel: ℋH, U, and both designs must be frozen before outcomes are opened. Maximum-likelihood decoding uses the margin V+/τ⋆V_+/τ within controlled testing [18, 21, 22]. Adaptive sensing can outperform fixed designs in general multihypothesis problems [18], so this comparison does not establish adaptive optimality. 4.2 Finite-time regret with a hard audit budget The pathwise audit cap and expected-regret bound account for all deployed actions. Independence of accepted samples and stationary interarrival counts gives exact finite-horizon accounting. Full proofs appear in Appendix A. Theorem 1 (Finite-dictionary RKHS achievable rate). Under (2) with V+>0V_+>0, Algorithm 1 uses at most M audits and satisfies [RT]≤C×χ()T,M(χ())+2ρU[T−T,M(χ())]|ℋ|||exp(−M2τ⋆+).E[R_T]≤ C_×χ( p) N_T,M (χ( p) )+2ρ U [T- N_T,M (χ( p) ) ]|H||Z| \! (- M2τ D_+ ). Here C×=ρχ()maxza∼⋆[uz(az⋆)−uz(a)]≤2ρUχ().C_×=ρχ( p) _zE_a λ [u_z(a_z )-u_z(a)]≤ 2ρ Uχ( p). Since T,M(Λ)≤minT,MΛ N_T,M( )≤ \T,M \, this refines the simpler untruncated charge whenever the horizon binds. Thus M≥2τ⋆+log(2|ℋ|||T)M≥ 2τ D_+ (2|H||Z|T) makes the exploitation-error term at most ρUρ U. Appendix A.3 proves the result by factoring accepted triples from their geometric waiting times and applying a Hellinger likelihood bound. 4.3 Joint action–verification policies and acquisition costs The audit scale τ⋆+τ D_+ measures information per accepted query. In contrast, χ()χ( p) controls how quickly those queries arrive, and C×/χ()C_×/χ( p) is the worst expected regret per design round. Rare informative states can therefore make an audit-efficient design costly in calendar time. If =μ p=μ, every round is accepted and χ()=1χ( p)=1. The stopped bound charges exploitation only after all M observations arrive. For fixed M and a long horizon, the design charge approaches MC×MC_×. The product construction is interpretable but can be conservative. To state the exact fixed-design cost, let ℰE be a finite environment dictionary with at least two designated optima. Under e∈ℰe , fresh outcomes at (a,s)(a,s) have law Pea,sP_e^a,s, independently across rounds conditional on actions and states. Define fe(a)=S∼μ[e[Y∣a,S]]f_e(a)=E_S μ[E_e[Y a,S]], choose ae⋆∈argmaxafe(a)a_e ∈ _af_e(a), and put Δe(a)=fe(ae⋆)−fe(a) _e(a)=f_e(a_e )-f_e(a). Put G=maxe,aΔe(a)G= _e,a _e(a). For ∈Δ(×) ν∈ (A×S) define Λ() ( ν) =∑a∈maxs∈ν(a,s)μ(s), = _a _s ν(a,s)μ(s), C() C( ν) =max∑a∈eΔe(a)maxsν(a,s)μ(s), = _e _a _e(a) _s ν(a,s)μ(s), I() I( ν) =mine,e′:ae⋆≠ae′⋆∑a,sν(a,s)H2(Pea,s,Pe′a,s), = _e,e :a_e ≠ a_e _a,sν(a,s)H^2(P_e^a,s,P_e ^a,s), where H2(P,Q)=1−∫dP,dQH^2(P,Q)=1- dP,dQ. Proposition 3 (Action-before-state rejection-sampling identity). There is a stationary action and post-state audit rule whose accepted pairs are i.i.d. ν and whose acceptance probability per round is 1/Λ()1/ ( ν). Every causal rule producing one accepted pair with law ν has expected waiting time at least Λ() ( ν) and sampling regret at least Ce():=∑aΔe(a)maxsν(a,s)/μ(s)C_e( ν):= _a _e(a) _sν(a,s)/μ(s) under e; the stationary rule attains both. After the MMth audit, choose a maximum-likelihood environment and play its designated optimum without further audits. If the horizon arrives first, remain in the design phase. Then supe∈ℰe[RT]≤C()Λ()T,M(Λ())+G[T−T,M(Λ())](|ℰ|−1)e−MI(). _e E_e[R_T]≤ C( ν) ( ν) N_T,M ( ( ν) )+G [T- N_T,M ( ( ν) ) ](|E|-1)e^-MI( ν). The bound therefore holds after infimizing its right-hand side over ν. Appendix A.4 proves both the causal cost identity and the finite-horizon decoding bound. 4.4 Adaptive verification with an information guarantee The fixed design can be adapted without losing worst-case identifiability. Given a fixed 0 ν_0 with I0:=I(0)>0I_0:=I( ν_0)>0, fix 0<ε≤10< ≤ 1 and mix any predictable design as m=ε0+(1−ε)~m ν_m= ν_0+(1- ) ν_m. Our implementation uses the Chernoff max–min law against different-optimum alternatives to the current maximum-likelihood environment. Proposition 4 (Safe adaptive joint design). Assume an exact finite observation dictionary, a known action-independent state law, and the same predictable rule under every environment. At stage m, hold m ν_m fixed until the next accepted audit and apply the row-max compiler of Proposition 3. After M audits, exploit the designated optimum of a maximum-likelihood environment. Define the stage sequence by continuing the same rule beyond T if necessary. Then at most M audits are used pathwise and, for every e∈ℰe , e[RT]≤e[∑m=1MCe(m)]+GTmin1,(|ℰ|−1)e−εMI0.E_e[R_T] _e\! [ _m=1^MC_e( ν_m) ]+GT \! \1,(|E|-1)e^- MI_0 \. The conditional Hellinger information is at least εI0 I_0 for every different-optimum pair, and the process extended until M audits arrive has e[τM]=e[∑m=1MΛ(m)]E_e[ _M]=E_e[ _m=1^M ( ν_m)]. Appendix A.5 combines accepted-history contraction with the horizon coupling. The result composes controlled sensing [18, 22] and density-ratio rejection sampling [28] for this protocol. It requires an exact dictionary and differs from ASB’s inverse-propensity variance objective [3]. Corollary 1 (Independent calibration transfer). Let independent calibration data C return a finite dictionary ℰ^() E(C) containing the exact true environment with probability at least 1−δ1-δ. Let GallG_ all bound every true one-round gap, including when calibration fails (Gall=1G_ all=1 is valid for rewards in [0,1][0,1]). If the instantiated policy has a nonnegative conditional bound BT()B_T(C) on the coverage event, then [RT]≤[BT()]+δGallTE[R_T] [B_T(C)]+δ G_ allT. Calibration with ncaln_ cal trusted labels gives total trusted-label use at most ncal+Mn_ cal+M. Appendix A.6 proves this elementary conditioning transfer. Exact coverage is essential; continuously refit signals, misspecification, and population shift remain outside its scope. 5 Adaptive limits and reliability sensitivity 5.1 An adaptive converse and a matched coordinate family The converse permits actions based on the entire history and audits chosen after the current state. It therefore covers adaptive policies, rather than only the fixed designs analyzed above. For a converse beyond finite signal dictionaries, let Π0 _0 contain every probability law π on a measurable collection 0⊂ℋkU_0 _k with ∥u∥ℋk≤B u _H_k≤ B and ∥u∥∞≤U≤1/4 u _∞≤ U≤ 1/4 and u∼π[u(a)]=0∀a∈.E_u π[u(a)]=0 ∀ a . (4) For π∈Π0π∈ _0, put Gπ=u∼π[maxau(a)],Wπ=maxau∼π[u(a)2].G_π=E_u π[ _au(a)], W_π= _aE_u π[u(a)^2]. Theorem 2 (Prior-mixture adaptive lower bound). For every π∈Π0π∈ _0, the minimax regret over ℋ×0H×U_0 satisfies RT⋆≥ρT[Gπ−4UMWπ3τ⋆]+.R_T ≥ρ T [G_π-4U MW_π3τ ]_+. When Wπ>0W_π>0, M≤3τ⋆Gπ2/(64U2Wπ)M≤ 3τ G_π^2/(64U^2W_π) implies RT⋆≥ρGπT/2R_T ≥ρ G_πT/2. The proof compares every environment with a fair-outcome null law and averages the resulting KL divergence under a zero-barycenter prior. See Appendix A.7. The prior may have infinite support in the RKHS. The bound respects the hard audit cap and counts every action used while waiting for an informative state. Its applicability depends on the existence of a zero-barycenter prior. For the finite balanced signed specialization, let gj:j∈⊂ℋk\g_j:j \ _k satisfy ∥gj∥ℋk≤B g_j _H_k≤ B and include both signs uj,θ=θgju_j,θ=θ g_j. Assume maxaθgj(a)≥gmin>0 _aθ g_j(a)≥ g_ >0 for every (j,θ)(j,θ) and maxj∥gj∥∞=U≤1/4 _j g_j _∞=U≤ 1/4. Define V−=max∈Δ()minja∼[gj(a)2].V_-= _ λ∈ (A) _jE_a λ[g_j(a)^2]. (5) LP duality supplies a law on j with maxa[gj(a)2]=V− _aE[g_j(a)^2]=V_-. Combining it with an independent uniform sign gives a member of Π0 _0 with Gπ≥gminG_π≥ g_ and Wπ=V−W_π=V_-. Therefore Theorem 2 yields RT⋆≥ρT[gmin−4UMV−3τ⋆]+.R_T ≥ρ T [g_ -4U MV_-3τ ]_+. In particular, M≤3τ⋆gmin2/(64U2V−)M≤ 3τ g_ ^2/(64U^2V_-) implies RT⋆≥ρgminT/2R_T ≥ρ g_ T/2. The coordinate family makes the two design quantities coincide. For d≥1d≥ 1 and 0<Δ≤minB,1/40< ≤ \B,1/4\, let =[d]×±1A=[d]×\± 1\, k((i,a),(j,b))=i=jab,uJ,θ(i,a)=Δθai=J.k((i,a),(j,b))=1\i=j\ab, u_J,θ(i,a)= θ a1\i=J\. (6) Then V+=V−=Δ2/dV_+=V_-= ^2/d, +=d/Δ2 D_+=d/ ^2, and gmin=U=Δg_ =U= . For d≥2d≥ 2, VΔ=2Δ2/dV_ =2 ^2/d, so Proposition 2 also makes the product design two-approximate for the exact squared-mean fixed-design game (the rank-one ratio is four). Appendix A.8 derives these identities. Theorems 1–2 match at the polynomial audit scale dτ⋆/Δ2dτ / ^2, up to logarithmic factors. 5.2 Structured and diffuse reliability The coordinate example separates reward-direction uncertainty from reliability uncertainty. Knowing the active coordinate reduces + D_+ from d/Δ2d/ ^2 to 1/Δ21/ ^2 without changing the kernel. Kernel rank alone therefore does not specify the decision complexity. The finite-dictionary assumption is consequential. Let =[L]S=[L] be uniform, let 1≤k≤L/21≤ k≤ L/2 be an integer and ρ=k/Lρ=k/L, and take as reliability class every k-subset C⊆[L]C [L]. This class has τ⋆=L/k=1/ρτ =L/k=1/ρ. The structured and diffuse families share the target kernel, rank, signal family, and hitting number, but their polynomial audit scales differ by τ⋆τ . Both satisfy (2) exactly. In the diffuse family, state labels rarely repeat when L≥8T2L≥ 8T^2, so their identities provide little reusable information about reliability. This regime is essential to the lower bound. The next theorem shows that selective audits cannot improve its polynomial rate. Theorem 3 (Diffuse-reliability frontier). Use the signed coordinate kernel and signals in (6). If M≤TM≤ T, a balanced pooled policy satisfies [RT]≤2ρΔM+4ρΔTdexp−⌊M/d⌋ρ2Δ22.E[R_T]≤ 2ρ M+4ρ Td \! \- M/d ρ^2 ^22 \. Conversely, if d≥32d≥ 32, L≥8T2L≥ 8T^2, and M≤3d4096ρ2Δ2,M≤ 3d4096ρ^2 ^2, every adaptive action-before-state policy with post-state audits obeys supC,J,θ[RT]≥ρΔT/4 _C,J,θE[R_T]≥ρ T/4. Hence this family has audit scale d(τ⋆)2/Δ2d(τ )^2/ ^2 up to constants and logarithms. Appendix A.9 proves the upper bound by balanced audit-only sampling and the lower bound by an exchangeable unseen-state mixture. 5.3 Robustness and limits of summary statistics Keep the independent Bernoulli protocol, with nominal and true means me(a,s)m_e(a,s) and m~e(a,s) m_e(a,s). The true target is f~e(a)=S∼μ[m~e(a,S)] f_e(a)=E_S μ[ m_e(a,S)], and R~T R_T denotes regret against its maximizing action. Define D()=minae⋆≠ae′⋆∑a,sν(a,s)[me(a,s)−me′(a,s)]21/2.D( ν)= _a_e ≠ a_e \ _a,sν(a,s)[m_e(a,s)-m_e (a,s)]^2 \^1/2. Proposition 5 (Feedback-law misspecification boundary). Assume supe,a,s|m~e(a,s)−me(a,s)|≤δfb,supe,a|f~e(a)−fe(a)|≤εtar. _e,a,s| m_e(a,s)-m_e(a,s)|≤ _ fb, _e,a| f_e(a)-f_e(a)|≤ _ tar. Replace maximum likelihood in Proposition 3 by the nominal squared-loss decoder. Then supee[R~T]≤C()Λ()T,M(Λ())+G[T−T,M(Λ())](|ℰ|−1)exp−3M40[D()−2δfb]+2+2εtarT. _eE_e[ R_T]≤ C( ν) ( ν) N_T,M ( ( ν) )+G [T- N_T,M ( ( ν) ) ](|E|-1) \! \- 3M40[D( ν)-2 _ fb]_+^2 \+2 _ tarT. Conversely, for every 0<ρ≤1/20<ρ≤ 1/2 and 0<Δ≤1/40< ≤ 1/4, there is a two-action rank-one instance with εtar=0 _ tar=0 and δfb=(1−ρ)Δ _ fb=(1-ρ) such that every causal policy obeys supee[RT]≥ρΔT2e−MκρΔ,κx=2xlog1+2x1−2x≤16x2(0≤x≤1/4). _eE_e[R_T]≥ ρ T2e^-M _ρ , _x=2x 1+2x1-2x≤ 16x^2 (0≤ x≤ 1/4). Appendix A.10 gives the squared-loss concentration argument and the target-preserving two-point construction. Thus target error contributes an additive comparison term, while feedback-law error erodes the testing margin and can destroy identifiability. Related identifiability failures arise in contaminated best-arm identification and misspecified linear identification [32, 33]. For the product design, Proposition 1 gives D(⋆⊗)≥V+/τ⋆D( λ p)≥ V_+/τ . Beyond Bernoulli outcomes, identical targets and any prescribed finite feedback summaries can coexist with a regret ratio at least K/(4log2K)K/(4 _2K) under equal log2K _2K audit budgets (Proposition 6, Appendix B.2). Appendix B.1 gives an exact deterministic coverage coefficient. 6 Experiments 6.1 Evaluation protocol and comparison methods We evaluate whether conditional reliability improves decisions under a fixed trusted-label budget, whether adaptive verification improves the proved fixed design, and how these benefits depend on model specification. Cumulative target regret RTR_T charges every deployed action, including rounds without an audit. Terminal simple regret is the gap of the recommended action. Lower values are better. We separately report trusted-label counts and the round of the final audit, since equal label budgets need not imply equal acquisition time. Synthetic tasks. The primary study uses signed-coordinate kernels of ranks two and eight and a periodic RBF kernel on 16 actions. It crosses one or four reliability groups, candidate-state probabilities 11 and .25.25, and audit caps 128128, 512512, and 2,0482,048, with horizon 8,1928,192 and 256 paired replications per setting. The independent GP comparison uses 24 settings, T=4,096T=4,096, M∈64,256,1,024M∈\64,256,1,024\, and 128 paired replications. A separate adaptive-design study uses eight actions, four squared-exponential kernel signals, three reliability families, (T,M)∈(512,32),(2048,64)(T,M)∈\(512,32),(2048,64)\, and 512 paired replications. Each primary evaluation uses prespecified dictionaries, policies, and seeds. Policies and controls. Reliability-Kernel-Design is Algorithm 1. The safe adaptive policy in Proposition 4 mixes a fixed robust joint law with Chernoff allocation using ε=.25 =.25. Conditional TS instead samples a reliability–signal pair from its posterior to select actions and audits all candidate-state outcomes until the cap. Its gate is fixed, so it is an adaptive-action heuristic, not the proved adaptive-verification policy. Controls include marginal-dictionary pooled TS, direct-arm UCB, likelihood decoders, GP policies, and a known-reliability oracle. Actions precede states, and only purchased outcomes update the models. GP controls use a Gaussian working likelihood with variance 1/41/4. Appendix C gives the grids, default parameters, and separately development-selected parameters. Uncertainty and aggregation. Policies share environment and noise streams. Per-setting paired 95% intervals are descriptive and unadjusted. Aggregate ratios are geometric means of per-setting mean-regret ratios. Standard errors and bootstrap intervals condition on the fixed task grid, not a population of new tasks. 6.2 Regret reduction and component comparisons Conditional feedback and adaptive action selection. In the 36-setting primary study, conditional TS has the lowest mean cumulative regret in 27 settings. Its paired comparison with pooled TS favors the conditional policy in 22 settings, is unresolved in 14, and never favors the pooled policy. The geometric regret ratios are .556.556, .339.339, and .369.369 as the audit cap increases (Figure 2). Direct-arm UCB has higher regret in 34 settings and no resolved improvement. The overlapping-reliability study gives a ratio of .569.569, supporting the mechanism beyond disjoint reliable states. 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. The fixed design improves terminal identification: mean simple regret falls from .0243.0243 to .00053.00053 across budgets. Its mean cumulative regret is nevertheless 196.1196.1, versus 84.084.0 for conditional TS (at cap 2,0482,048: 261.5261.5 versus 24.724.7). The information guarantee therefore does not imply adaptive-regret optimality. With 75% uninformative states, only 51.3% of either policy’s trajectories reach that cap by the horizon. Table 1: Independent GP comparison on 24 settings and 128 paired replications per setting. Entries average settings equally. Cumulative regret is mean ± Monte Carlo standard error, computed as [∑c=124sc2/128]1/2/24[ _c=1^24s_c^2/128]^1/2/24, where sc2s_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. Policy Cumulative regret ↓ Simple regret ↓ Conditional TS 92.24±2.5892.24± 2.58 .0198.0198 Candidate-gated pooled TS 99.92±2.5899.92± 2.58 .0219.0219 All-round joint TS 106.09±2.62106.09± 2.62 .0241.0241 All-round pooled TS 124.30±2.66124.30± 2.66 .0287.0287 GP-UCB 119.27±2.64119.27± 2.64 .0275.0275 GP-TS 130.40±2.65130.40± 2.65 .0292.0292 Identity-UCB 124.83±2.78124.83± 2.78 .0286.0286 Identity-TS 144.58±2.76144.58± 2.76 .0325.0325 Reliability-Kernel-Design 138.46±2.74138.46± 2.74 .0226.0226 GP controls and component effects. Table 1 reports absolute regret and uncertainty for the independent comparison. Conditional TS has lower mean cumulative and simple regret than all listed controls. Its geometric regret ratios are .663.663 against default GP-UCB and .612.612 against default GP-TS, although UCB wins two settings. Development-selected GP parameters do not improve the aggregate result. Matched kernel-versus-identity ratios are .925.925 for UCB and .886.886 for TS, with most paired comparisons unresolved. Joint versus pooled likelihood under the same candidate-state gate has ratio .901.901. The full conditional policy therefore benefits from the combination of its model and acquisition rule, while the isolated kernel effect is smaller. Adaptive verification and acquisition time. On the separately seeded exact-dictionary study, safe adaptive allocation has regret ratio .933.933 relative to the fixed robust joint design. Nine settings favor safe adaptive, 15 are unresolved, and none favor the fixed design. A subsequent comparison on new paired streams evaluates stronger controls (Table 2). Most comparisons with audit-only TS and posterior greedy are unresolved, and pure adaptive allocation is comparable without the robust floor. The supplementary study is post-measurement evidence, not independent confirmation. Equal T deployments and M labels conceal longer acquisition times under selective verification. The exact-model information floor holds, but its error bound clips to one in all 24 settings. 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 MMth 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. Comparator Regret ratio ↓ Acquisition-time ratio ↓ 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 Audit-only posterior greedy .966 4.764 6.3 Model sensitivity and AI-task evaluation Reliability errors and target perturbations. The robustness study separates changes to the conditional feedback law from changes to the reward target. Target-preserving feedback error gradually erodes the conditional policy’s advantage. The conditional-to-pooled regret ratio is 1.0271.027 at feedback error .20.20 and 1.0681.068 after exact feedback flattening. Target perturbations of .05.05 and .10.10 reverse the comparison, with ratios 1.3981.398 and 1.7991.799. Correct target geometry alone therefore does not ensure informative conditional feedback, as Proposition 5 predicts. Appendix C.4 gives the laws and uncertainty. AI evaluation with fitted dictionaries. JudgeBench and the 32-judge ChaosNLI study test whether calibration can supply the model required by the online policy. The former uses 144 calibration labels and 1,584 archived judge outputs, while the latter uses 591 labels and 18,912 outputs. Online reveal budgets are additional to these calibration costs. On JudgeBench, fitted dictionaries predict worse than a pooled model and give regret ratios 11.6311.63 and 16.4616.46 against uniform verified TS. In the 32-judge study, clipping nearly every fitted signal entry makes the action design collapse to a tie, and selective verification changes acquisition time without improving regret over its matched uniform-state control. A postdiagnostic 32-judge study separates reliability-set coverage from action-model expansion. Retaining two fitted signals while completing the reliability class improves all four settings relative to expanding both classes. The two-state reliability model has ratio .581.581 against uniform verified TS, whereas the one-state model has ratio 1.1431.143. This contrast identifies action-model constraints as a concrete source of the earlier loss, but it is fitted-table development evidence and does not validate a learned selective gate. Appendix C gives the complete comparisons, offline replays, calibration uncertainty, and data-access provenance. The evidence supports the exact-model mechanism, while practical gains remain sensitive to model estimation and acquisition time. References [1] A. Verma et al. (2023) Exploiting correlated auxiliary feedback in parameterized bandits. In NeurIPS, Cited by: Table 11, Appendix D, Appendix D, §1, §2. [2] R. Ao, H. Chen, S. Gao, H. Li, and D. Simchi-Levi (2026) Best arm identification with LLM judges and limited human. Note: arXiv:2601.21471 Cited by: Table 11, Appendix D, Appendix D, §1, §2. [3] K. Lee and M. R. Kosorok (2026) The surrogate is not the reward: post-surrogate primary-outcome acquisition in contextual bandits. Note: arXiv:2610.06610v1October 5 Cited by: Table 11, Appendix D, Appendix D, §1, §2, §4.4. [4] M. Sargent et al. (2026) Prediction-powered adaptive inference. In ICML, Cited by: Appendix D, Appendix D, §1, §2. [5] A. Rangi et al. (2022) Stochastic bandits with limited verification. In AAAI, Cited by: Appendix D, Appendix D, §2. [6] W. Ji, Y. Pan, R. Zhu, and L. Lei (2026) Multi-armed bandits with machine learning-generated surrogate rewards. Note: arXiv:2506.16658 Cited by: Appendix D, Appendix D, §2. [7] Y. Efroni, N. Merlis, A. Saha, and S. Mannor (2021) Confidence–budget matching for sequential budgeted learning. In ICML, Cited by: §B.1, Table 11, Appendix D, Appendix D, §2. [8] F. Schur, J. Lago, and T. Fiez (2026) The price of knowledge: optimal algorithms for costly bandits. In UAI, Cited by: Table 11, Appendix D, Appendix D, §2. [9] P. Mikkola et al. (2023) Robust multi-fidelity Bayesian optimization. In AISTATS, Cited by: Appendix D, Appendix D, §2. [10] X. J. Chen and Y. Tong (2026) Gaussian process bandit optimization with machine learning predictions and application to hypothesis generation. Note: arXiv:2601.22315 Cited by: Appendix D, Appendix D, §2. [11] I. Bogunovic and A. Krause (2021) Misspecified Gaussian process bandit optimization. In NeurIPS, Cited by: Appendix D, Appendix D, §2. [12] R. Camilleri, K. Jamieson, and J. Katz-Samuels (2021) High-dimensional experimental design and kernel bandits. In ICML, Cited by: Appendix D, Appendix D, §2. [13] S. Wu, C.-H. Wang, Y. Li, and G. Cheng (2022) Residual bootstrap exploration for stochastic linear bandit. In UAI, Proceedings of Machine Learning Research, Vol. 180, p. 2117–2127. Cited by: Appendix D, §2. [14] S. Wu and A. A. Amini (2024) Graph neural Thompson sampling. Note: arXiv:2406.10686 Cited by: Appendix D, §2. [15] S. Wu and A. A. Amini (2026) Laplacian kernelized bandit. In ICLR, Cited by: Appendix D, §2. [16] S. Saad-Falcon et al. (2024) ARES: an automated evaluation framework for retrieval-augmented generation systems. In NAACL, Cited by: Appendix D, Appendix D, §2. [17] R. Liu et al. (2025) HbBoPs: prompt selection with Bayesian optimization and Hyperband. In ICML, Cited by: Appendix D, Appendix D, §2. [18] S. Nitinawarat, G. K. Atia, and V. V. Veeravalli (2013) Controlled sensing for multihypothesis testing. IEEE Transactions on Automatic Control 58 (10), p. 2451–2464. Cited by: Table 11, Appendix D, Appendix D, §2, §4.1, §4.4. [19] S. Javdani, Y. Chen, A. Karbasi, A. Krause, J. A. Bagnell, and S. Srinivasa (2014) Near optimal Bayesian active learning for decision making. In AISTATS, Cited by: Appendix D, Appendix D, §2. [20] Y. Chen, S. H. Hassani, and A. Krause (2017) Near-optimal Bayesian active learning with correlated and noisy tests. In AISTATS, Cited by: Appendix D, Appendix D, §2. [21] T. Fiez, L. Jain, K. Jamieson, and L. Ratliff (2019) Sequential experimental design for transductive linear bandits. In NeurIPS, Cited by: Appendix D, Appendix D, §2, §4.1. [22] S. Mukherjee, A. S. Tripathy, and R. Nowak (2022) Chernoff sampling for active testing and extension to active regression. In AISTATS, Cited by: Table 11, Appendix D, Appendix D, §2, §4.1, §4.4. [23] M. Shahverdikondori, A. M. Abouei, A. Rezaeimoghadam, and N. Kiyavash (2026) Pure exploration beyond reward feedback: the role of post-action context. Note: arXiv:2502.03061v2May 12 Cited by: Appendix D, §2. [24] J. Kirschner, T. Lattimore, and A. Krause (2020) Information directed sampling for linear partial monitoring. In COLT, Cited by: Appendix D, Appendix D, §2. [25] S. R. Chowdhury, R. Oliveira, and F. Ramos (2020) Active learning of conditional mean embeddings via Bayesian optimisation. In UAI, Cited by: Appendix D, Appendix D, §2. [26] S. Takemori (2022) Distributionally-aware kernelized bandit problems for risk aversion. In ICML, Cited by: Appendix D, Appendix D, §2. [27] T. Cai and K. Kandasamy (2023) Active cost-aware labeling of streaming data. In AISTATS, Cited by: Appendix D, Appendix D, §2. [28] Y. Chandak, S. Shankar, V. Syrgkanis, and E. Brunskill (2024) Adaptive instrument design for indirect experiments. In ICLR, Cited by: Table 11, Appendix D, Appendix D, §2, §4.4. [29] A. Garivier and E. Kaufmann (2016) Optimal best arm identification with fixed confidence. In COLT, Cited by: Appendix D, Appendix D, §2. [30] J. C. H. Lee and P. Valiant (2019) Uncertainty about uncertainty: optimal adaptive algorithms for estimating mixtures of unknown coins. Note: arXiv:1904.09228 Cited by: Appendix D, Appendix D, §2. [31] K. Balagopalan, Y. Li, Y. Zhao, T. N. Nguyen, A. Daitche, H. Nassif, and K.-S. Jun (2026) Fixed budget is no harder than fixed confidence in best-arm identification up to logarithmic factors. In ICML, Cited by: Appendix D, Appendix D, §2. [32] J. Altschuler, V.-E. Brunel, and A. Malek (2019) Best-arm identification for contaminated bandits. JMLR 20 (91), p. 1–39. Cited by: Table 11, Appendix D, §2, §5.3. [33] C. Réda, A. Tirinzoni, and R. Degenne (2021) Dealing with misspecification in fixed-confidence linear Top-m identification. In NeurIPS, Cited by: Table 11, Appendix D, §2, §5.3. [34] I. Bárány and P. Soberón (2018) Tverberg’s theorem is 50 years old: a survey. Bulletin of the American Mathematical Society 55 (4), p. 459–492. Cited by: §A.11, §B.2, Appendix D. [35] S. Raghavendran and V. Narayanan (2019) The Prouhet Tarry Escott problem: a review. Mathematics 7 (3), p. 227. Cited by: §A.11, Appendix D. [36] C. Li, Y. Yu, and Y. Li (2026) How many humans are 32 LLM judges worth?. Note: arXiv:2609.21277 Cited by: §C.7, Appendix D. [37] Y. Nie, X. Zhou, and M. Bansal (2020) What can we learn from collective human opinions on natural language inference data?. In EMNLP, Cited by: §C.7, Appendix D. [38] Q. Zeng, X. Wang, J. Shen, X. Liu, F. Kong, and J. Zuo (2026) Best arm identification in generalized linear bandits via hybrid feedback. Note: arXiv:2605.05745 Cited by: Appendix D, Appendix D. [39] C. Wang, Z. Ye, Z. Feng, A. Badanidiyuru, and H. Xu (2023) Follow-ups also matter: improving contextual bandits via post-serving contexts. In NeurIPS, Cited by: Appendix D, Appendix D. [40] X. Gong and J. Zhang (2026) The cost of information: phase transitions in contextual bandits with paid observations. In ICML, Cited by: Appendix D, Appendix D. [41] M. O. Harding, V. Singh, and K. Kandasamy (2026) Learning from biased and costly data sources: minimax-optimal data collection under a budget. In COLT, Cited by: Appendix D, Appendix D. [42] L. Reyzin, A. Saha, and S. Wu (2026) Expert advice with costly observations. In UAI, Cited by: Appendix D, Appendix D. [43] K. W. Zhang, T. Baldwin-McDonald, K. Ciosek, L. Maystre, and D. Russo (2026) Impatient bandits: optimizing for the long-term without delay. JMLR 27, p. 1–58. Cited by: Appendix D, Appendix D. [44] W. Wei, S. Pal, K. Mukherjee, F. Dernoncourt, R. A. Rossi, B. Kveton, and H. Eldardiry (2026) Online learning with LLM experts from limited feedback. Note: arXiv:2609.05820 Cited by: Appendix D, Appendix D. [45] A. N. Sridhar, R. Singh, M. Mahdavi, and V. Narayanan (2026) Correlation-aware contextual bandits with surrogate rewards for LLM routing. Note: arXiv:2607.09015 Cited by: Appendix D, Appendix D. [46] Z. Du, H. Zhang, H. Zhu, and B. Zhang (2026) Optimal design for active preference learning with biased LLM judges. Note: arXiv:2609.38860 Cited by: Appendix D, Appendix D. Appendix A Proofs The proofs follow the order of the main statements. The final three proofs establish the supplementary results in Appendix B. A.1 Proof of Proposition 1 Fix e=(h,z)e=(h,z) and e′=(h′,z′)e =(h ,z ) with az⋆≠az′⋆a_z ≠ a_z . Let H=Ch∩Ch′,A=Ch∖Ch′,B=Ch′∖Ch.H=C_h∩ C_h , A=C_h C_h , B=C_h C_h. The constant 1/21/2 in the conditional means cancels. Independence of the action and state under the product design therefore gives s∼,a∼⋆[(me(a,s)−me′(a,s))2] _s p,\,a λ [(m_e(a,s)-m_e (a,s))^2 ] =p(H)a∼⋆[(uz(a)−uz′(a))2]+p(A)a∼⋆[uz(a)2]+p(B)a∼⋆[uz′(a)2] =p(H)E_a λ [(u_z(a)-u_z (a))^2 ]+p(A)E_a λ [u_z(a)^2 ]+p(B)E_a λ [u_z (a)^2 ] ≥V+p(H)+p(A)+p(B)=V+p(Ch∪Ch′)≥V+p(Ch)≥V+τ⋆. ≥ V_+\p(H)+p(A)+p(B)\=V_+p(C_h∪ C_h )≥ V_+p(C_h)≥ V_+τ . The first inequality uses all three classes of constraints in (3). The last inequality follows from the feasibility of p in (1). This proves the proposition. □ A.2 Proof of Proposition 2 Taking =⋆⊗ ν= λ p in the definition of J⋆J and applying Proposition 1 gives J⋆≥V+/τ⋆J ≥ V_+/τ . For the reverse inequality, let =(z,z′):az⋆≠az′⋆P=\(z,z ):a_z ≠ a_z \. Finite-game duality yields distributions q on ℋH and ξ on P such that ∑hqhs∈Ch≤1τ⋆for every s,∑(z,z′)∈ξz,z′[uz(a)−uz′(a)]2≤VΔfor every a. _hq_h1\s∈ C_h\≤ 1τ every s, _(z,z ) _z,z [u_z(a)-u_z (a)]^2≤ V_ every a. Fix an arbitrary joint design ν. Restricting the alternatives to h=h′h=h and then averaging them with ⊗ q ξ gives minh,h′,(z,z′)∈[(mh,z(X,S)−mh′,z′(X,S))2] _h,h ,\,(z,z ) E_ ν [(m_h,z(X,S)-m_h ,z (X,S))^2 ] ≤∑s,aν(a,s)(∑hqhs∈Ch)(∑(z,z′)∈ξz,z′[uz(a)−uz′(a)]2) ≤ _s,aν(a,s) ( _hq_h1\s∈ C_h\ ) ( _(z,z ) _z,z [u_z(a)-u_z (a)]^2 ) ≤VΔτ⋆∑s,aν(a,s)=VΔτ⋆. ≤ V_ τ _s,aν(a,s)= V_ τ . Maximizing over ν proves the upper bound. When V+=VΔV_+=V_ , the lower and upper bounds agree. □ A.3 Proof of Theorem 1 Accepted observations and waiting times. Fix the true environment e=(h,z)e=(h,z) and write χ=χ()χ=χ( p). Extend the design phase to an infinite sequence for the purpose of defining its stopping time. In each round, let ItI_t denote the acceptance indicator generated by the rejection rule. The actual policy uses this sequence only until M acceptances or the horizon. In one design round, PreXt=a,St=s,It=1=λa⋆μ(s)psχμ(s)=λa⋆psχ. _e\X_t=a,S_t=s,I_t=1\= _a μ(s) p_sχμ(s)= _a p_sχ. Thus ItI_t are independent Bernoulli(1/χ)(1/χ) variables and PreXt=a,St=s∣It=1=λa⋆ps. _e\X_t=a,S_t=s I_t=1\= _a p_s. Write τM=inft:∑j=1tIj=M _M= \t: _j=1^tI_j=M\. The actual number of audits is at most M on every sample path. Moreover, e[minT,τM] _e[ \T, _M\] =∑t=1TPreτM≥t = _t=1^T _e\ _M≥ t\ =∑t=0T−1PrBin(t,1/χ)<M=T,M(χ). = _t=0^T-1 \Bin(t,1/χ)<M\= N_T,M(χ). Regret during acquisition. Let ℱt−1F_t-1 contain all variables generated before design round t, and define the target gap Δz(a)=ρ[uz(az⋆)−uz(a)] _z(a)=ρ[u_z(a_z )-u_z(a)]. The event τM≥t\ _M≥ t\ is ℱt−1F_t-1-measurable, while XtX_t has law ⋆ λ independently of that history. Hence the regret incurred before completion satisfies e[∑t=1TτM≥tΔz(Xt)] _e\! [ _t=1^T1\ _M≥ t\ _z(X_t) ] =∑t=1TPreτM≥ta∼⋆[Δz(a)] = _t=1^T _e\ _M≥ t\E_a λ [ _z(a)] ≤C×χT,M(χ). ≤ C_×χ N_T,M(χ). Likelihood comparison. It remains to control the recommendation error. Let QeQ_e be the law of one accepted triple (X,S,Y)(X,S,Y), so that Qe(a,s,y)=psλa⋆me(a,s)y[1−me(a,s)]1−y,y∈0,1.Q_e(a,s,y)=p_s _a m_e(a,s)^y[1-m_e(a,s)]^1-y, y∈\0,1\. The accepted triples are independent with law QeQ_e. For any e′=(h′,z′)e =(h ,z ) with a different designated optimum, let LM(e′)/LM(e)L_M(e )/L_M(e) be the likelihood ratio of their first M accepted triples. Markov’s inequality and independence imply PreLM(e′)≥LM(e) _e\L_M(e )≥ L_M(e)\ ≤e[LM(e′)/LM(e)] _e\! [ L_M(e )/L_M(e) ] =(∑s,a,yQe(a,s,y)Qe′(a,s,y))M = ( _s,a,y Q_e(a,s,y)Q_e (a,s,y) )^M =(1−s∼,a∼⋆[H2(Pea,s,Pe′a,s)])M = (1-E_s p,\,a λ [H^2(P_e^a,s,P_e ^a,s)] )^M ≤exp−M2s∼,a∼⋆[(me(a,s)−me′(a,s))2] ≤ \! \- M2E_s p,\,a λ [(m_e(a,s)-m_e (a,s))^2] \ ≤exp(−MV+2τ⋆). ≤ \! (- MV_+2τ ). Here H2(P,Q)=1−∑yP(y)Q(y)H^2(P,Q)=1- _y P(y)Q(y). The penultimate line uses 1−x≤e−x1-x≤ e^-x and the Bernoulli inequality H2(Bern(x),Bern(y))≥(x−y)2/2H^2(Bern(x),Bern(y))≥(x-y)^2/2. The final line is Proposition 1. Let E be the event that the maximum-likelihood recommendation has a different designated optimum. On E, some such e′e has likelihood at least that of e, including ties. A union bound gives Pre(E)≤|ℋ|||exp(−MV+2τ⋆). _e(E)≤|H||Z| \! (- MV_+2τ ). Stopping and exploitation. To combine this error probability with the remaining horizon, let GjG_j be the waiting time for the jjth accepted triple (X¯j,S¯j,Y¯j)( X_j, S_j, Y_j). The repeated independent rejection rule gives, for every integer g≥1g≥ 1 and measurable set D of triples, PreGj=g,(X¯j,S¯j,Y¯j)∈D=(1−1/χ)g−1χ−1Qe(D). _e\G_j=g,\ ( X_j, S_j, Y_j)∈ D\=(1-1/χ)^g-1χ^-1Q_e(D). The pairs indexed by j are independent. Thus τM=∑j=1MGj _M= _j=1^MG_j is independent of the accepted sample and of E. Since each target gap is at most 2ρU2ρ U, exploitation regret is at most 2ρUe[(T−τM)+E] 2ρ UE_e[(T- _M)_+1\E\] =2ρUT−T,M(χ)Pre(E) =2ρ U\T- N_T,M(χ)\ _e(E) ≤2ρUT−T,M(χ)|ℋ|||e−M/(2τ⋆+). ≤ 2ρ U\T- N_T,M(χ)\|H||Z|e^-M/(2τ D_+). Adding the design and exploitation terms proves the regret bound. Finally, e[τM]=MχE_e[ _M]=Mχ gives T,M(χ)≤minT,Mχ N_T,M(χ)≤ \T,Mχ\. Substituting the stated audit threshold makes the last exponential at most 1/(2|ℋ|||T)1/(2|H||Z|T), so the exploitation term is at most ρUρ U. □ A.4 Proof of Proposition 3 Write ma=maxs∈ν(a,s)μ(s),Λ=∑a∈ma.m_a= _s ν(a,s)μ(s), = _a m_a. Actions with ma=0m_a=0 are never selected. For ma>0m_a>0, define qa=maΛ,αa,s=ν(a,s)maμ(s).q_a= m_a , _a,s= ν(a,s)m_aμ(s). Because ma≥ν(a,s)/μ(s)m_a≥ν(a,s)/μ(s), we have 0≤αa,s≤10≤ _a,s≤ 1. A design round draws Xt∼X_t q, observes StS_t, and audits with probability αXt,St _X_t,S_t. Hence PrXt=a,St=s,Bt=1 \X_t=a,S_t=s,B_t=1\ =qaμ(s)αa,s=ν(a,s)Λ, =q_aμ(s) _a,s= ν(a,s) , PrBt=1 \B_t=1\ =1Λ,PrXt=a,St=s∣Bt=1=ν(a,s). = 1 , \X_t=a,S_t=s B_t=1\=ν(a,s). Independent repetition therefore produces i.i.d. accepted pairs with law ν. Causal lower bound. We next prove the causal lower bound. Consider any policy that produces one audited pair with law ν. Let ℱt−1F_t-1 contain the history before action XtX_t is chosen, let τ be the first audited round, and define Na=∑t≥1τ≥t,Xt=a.N_a= _t≥ 11\τ≥ t,X_t=a\. The event τ≥t,Xt=a\τ≥ t,X_t=a\ is measurable with respect to σ(ℱt−1,Xt)σ(F_t-1,X_t). Since St∼μS_t μ independently of ℱt−1F_t-1 and XtX_t, Tonelli’s theorem gives, for every (a,s)(a,s), [∑t≥1τ≥t,Xt=a,St=s] \! [ _t≥ 11\τ≥ t,X_t=a,S_t=s\ ] =∑t≥1[τ≥t,Xt=aPrSt=s∣ℱt−1,Xt] = _t≥ 1E\! [1\τ≥ t,X_t=a\ \S_t=s _t-1,X_t\ ] =μ(s)[Na]. =μ(s)E[N_a]. The audited occurrence (Xτ,Sτ)(X_τ,S_τ) is one term in this sum and has law ν. Therefore ν(a,s)≤μ(s)[Na],[Na]≥maxsν(a,s)μ(s)=ma.ν(a,s)≤μ(s)E[N_a], [N_a]≥ _s ν(a,s)μ(s)=m_a. Summing over a yields [τ]=∑a[Na]≥∑ama=Λ.E[τ]= _aE[N_a]≥ _am_a= . Under environment e, weighting the same inequality by Δe(a) _e(a) yields the sampling-regret bound e[∑t=1τΔe(Xt)]=∑aΔe(a)e[Na]≥∑aΔe(a)ma=Ce().E_e\! [ _t=1^τ _e(X_t) ]= _a _e(a)E_e[N_a]≥ _a _e(a)m_a=C_e( ν). For the stationary construction, [τ]=ΛE[τ]= and [Na]=qaΛ=maE[N_a]=q_a =m_a, so both inequalities are equalities. The argument applies conditionally at each stage when the next design law is measurable with respect to the accepted history. Finite-horizon regret. It remains to prove the finite-horizon regret bound. Before the MMth audit, one design round has expected regret ∑aqaΔe(a)=Ce()Λ≤C()Λ. _aq_a _e(a)= C_e( ν) ≤ C( ν) . The accept indicators are i.i.d. Bernoulli(1/Λ)(1/ ). Repeating the stopping-time calculation in Appendix A.3, the expected design length is T,M(Λ) N_T,M( ) and the expected exploitation length is T−T,M(Λ)T- N_T,M( ). Let QeQ_e denote the law of one accepted triple. For a wrong-decision environment e′e , its Bhattacharyya affinity with QeQ_e is ∑a,sν(a,s)∫dPea,sdPe′a,s _a,sν(a,s) dP_e^a,sdP_e ^a,s =1−∑a,sν(a,s)H2(Pea,s,Pe′a,s) =1- _a,sν(a,s)H^2(P_e^a,s,P_e ^a,s) ≤1−I()≤e−I(). ≤ 1-I( ν)≤ e^-I( ν). For the first M accepted triples, Markov’s inequality applied to the square root of the likelihood ratio and independence give PreLM(e′)≥LM(e)≤e−MI(). _e\L_M(e )≥ L_M(e)\≤ e^-MI( ν). A maximum-likelihood decision with the wrong optimum implies this event for at least one of the at most |ℰ|−1|E|-1 alternatives. A union bound therefore gives error probability at most (|ℰ|−1)e−MI()(|E|-1)e^-MI( ν). The accepted triples are independent of their geometric waiting times, so this event is independent of the exploitation length. Multiplying its probability by the expected exploitation length and the largest one-round gap G, then adding the design regret, proves the displayed bound. If fewer than M audits arrive by time T, the policy remains in the design phase and has no exploitation segment. □ A.5 Proof of Proposition 4 Fix the true environment e and a different-optimum alternative e′e . Let ℱm−1audF aud_m-1 be the observed history before stage m, including internal randomization, and let Lm(e′)/Lm(e)L_m(e )/L_m(e) be the likelihood ratio after m accepted observations. The law m ν_m is measurable with respect to ℱm−1audF aud_m-1 and is selected by the same rule under both environments. Therefore the design factors cancel from the likelihood ratio. Conditional on ℱm−1audF aud_m-1, we have e[Lm(e′)Lm(e)|ℱm−1aud] _e\! [ . L_m(e )L_m(e)\, |F aud_m-1 ] =Lm−1(e′)Lm−1(e)∑a,sνm(a,s)∫dPea,sdPe′a,s = L_m-1(e )L_m-1(e) _a,s _m(a,s) dP_e^a,sdP_e ^a,s =Lm−1(e′)Lm−1(e)[1−∑a,sνm(a,s)H2(Pea,s,Pe′a,s)]. = L_m-1(e )L_m-1(e) [1- _a,s _m(a,s)H^2(P_e^a,s,P_e ^a,s) ]. By nonnegativity and the mixture definition, ∑a,sνm(a,s)H2(Pea,s,Pe′a,s)≥ε∑a,sν0(a,s)H2(Pea,s,Pe′a,s)≥εI0. _a,s _m(a,s)H^2(P_e^a,s,P_e ^a,s)≥ _a,s _0(a,s)H^2(P_e^a,s,P_e ^a,s)≥ I_0. Iterating conditional expectations, using 1−x≤e−x1-x≤ e^-x, and applying Markov’s inequality gives PreLM(e′)≥LM(e)≤e[LM(e′)LM(e)]≤(1−εI0)M≤e−εMI0. _e\L_M(e )≥ L_M(e)\ _e\! [ L_M(e )L_M(e) ]≤(1- I_0)^M≤ e^- MI_0. A maximum-likelihood recommendation with the wrong optimum requires this event for at least one of at most |ℰ|−1|E|-1 alternatives. Hence its probability is at most min1,(|ℰ|−1)e−εMI0. \! \1,(|E|-1)e^- MI_0 \. Acquisition cost and the finite horizon. Extend the design process beyond T until it collects all M audits. Conditional on ℱm−1audF aud_m-1, Proposition 3 gives expected waiting time Λ(m) ( ν_m) and expected design-stage regret Ce(m)C_e( ν_m). The tower property and Tonelli’s theorem give e[τM]=e[∑m=1MΛ(m)],e[Rdesignext]=e[∑m=1MCe(m)].E_e[ _M]=E_e\! [ _m=1^M ( ν_m) ], _e[R_ design ext]=E_e\! [ _m=1^MC_e( ν_m) ]. The horizon-T design regret is at most RdesignextR_ design ext pathwise. If all audits arrive by T, erroneous exploitation implies an error of the extended M-audit decoder and costs at most GTGT. If they do not arrive, there is no exploitation segment. Adding the two terms proves the regret bound. This coupling does not assume independence between completion time and decoding error. The algorithm checks the remaining budget before every purchase, so the cap holds pathwise. □ A.6 Proof of Corollary 1 Let E=e⋆∈ℰ^()E=\e_ ∈ E(C)\ be the exact-coverage event. Because E is measurable with respect to the independent calibration sample, the conditional online guarantee and the pathwise bound 0≤RT≤GallT0≤ R_T≤ G_ allT give [RT] [R_T] =[RTE]+[RTEc] =E[R_T1\E\]+E[R_T1\E^c\] ≤[BT()E]+GallTPr(Ec) [B_T(C)1\E\]+G_ allT (E^c) ≤[BT()]+δGallT. [B_T(C)]+δ G_ allT. The calibration phase consumes ncaln_ cal trusted labels before the online audit cap M, so the total trusted-label endowment is ncal+Mn_ cal+M. □ A.7 Proof of Theorem 2 Fix an arbitrary adaptive policy with at most M audits on every sample path. The dual of (1) supplies a distribution q over h such that Prh∼s∈Ch≤1/τ⋆∀s. _h q\s∈ C_h\≤ 1/τ ∀ s. (7) Fix π∈Π0π∈ _0 and put the product prior ⊗π q π on E=(h,u)E=(h,u). For each e=(h,u)e=(h,u), let PeP_e be the policy transcript law under the conditional mean in (2). Let P0P_0 be the transcript law obtained by replacing every audited outcome with an independent Bern(1/2)Bern(1/2) variable while leaving the state process and the policy’s internal randomization unchanged. Let ℱt−1F_t-1 contain the transcript before XtX_t is chosen, and let BtB_t be the audit indicator selected after observing StS_t. Under P0P_0, the latent variable E is independent of ℱt−1F_t-1, XtX_t, StS_t, and BtB_t. By (7), the zero-barycenter condition, and the definition of WπW_π, every audited query satisfies E[St∈Chu(Xt)2∣ℱt−1,Xt,St,Bt=1]≤Wπτ⋆.E_E\! [1\S_t∈ C_h\u(X_t)^2 _t-1,X_t,S_t,B_t=1 ]≤ W_πτ . For |x|≤1/4|x|≤ 1/4, kl(Bern(1/2),Bern(1/2+x)) \! (Bern(1/2),Bern(1/2+x) ) =−12log(1−4x2) =- 12 (1-4x^2) ≤83x2, ≤ 83x^2, where the inequality holds because 4x2≤1/44x^2≤ 1/4 and −log(1−y)≤4y/3- (1-y)≤ 4y/3 for 0≤y≤1/40≤ y≤ 1/4. The adaptive KL chain rule, followed by the preceding conditional bound and the pathwise constraint ∑t=1TBt≤M _t=1^TB_t≤ M, yields E[KL(P0∥PE)] _E[KL(P_0\|P_E)] =0,E[∑t=1TBtkl(Bern(1/2),Bern1/2+(St∈Ch)u(Xt))] =E_0,E\! [ _t=1^TB_tkl\! (Bern(1/2),Bern\1/2+1(S_t∈ C_h)u(X_t)\ ) ] ≤830[∑t=1TBtWπτ⋆]≤8MWπ3τ⋆. ≤ 83E_0\! [ _t=1^TB_t W_πτ ]≤ 8MW_π3τ . For a fixed environment e=(h,u)e=(h,u) and transcript, define the target regret functional Le=ρ∑t=1Tmaxau(a)−u(Xt).L_e=ρ _t=1^T\ _au(a)-u(X_t)\. It satisfies 0≤Le≤2ρUT0≤ L_e≤ 2ρ UT. Under P0P_0, the policy actions are independent of u, so (4) gives E[0[LE]] _E[E_0[L_E]] =ρ∑t=1Tu∼π[maxau(a)]−0[u∼π[u(Xt)]] =ρ _t=1^T \E_u π[ _au(a)]-E_0[E_u π[u(X_t)]] \ =ρGπT. =ρ G_πT. For each e, the variational characterization of total variation gives e[Le]≥0[Le]−2ρUTTV(P0,Pe).E_e[L_e] _0[L_e]-2ρ UTTV(P_0,P_e). Averaging over E, using Pinsker’s inequality, Jensen’s inequality, and the KL bound above, we obtain e∼⊗π[Pe[Le]] _e q π[E_P_e[L_e]] ≥ρGπT−2ρUTE[TV(P0,PE)] ≥ρ G_πT-2ρ UTE_E[TV(P_0,P_E)] ≥ρGπT−2ρUT12E[KL(P0∥PE)] ≥ρ G_πT-2ρ UT 12E_E[KL(P_0\|P_E)] ≥ρT(Gπ−4UMWπ3τ⋆). ≥ρ T (G_π-4U MW_π3τ ). The left-hand side is the Bayes regret of the fixed policy, and Bayes regret lower-bounds its worst-environment regret. Since regret is nonnegative, taking the positive part and then infimizing over policies proves the first claim. If Wπ=0W_π=0, every action has u(a)=0u(a)=0 almost surely under π, so Gπ=0G_π=0 and the bound is trivial. Otherwise, if M≤3τ⋆Gπ2/(64U2Wπ)M≤ 3τ G_π^2/(64U^2W_π), the square-root term is at most Gπ/2G_π/2, which proves the second claim. □ A.8 Coordinate specialization of the design bounds For a design λ on [d]×±1[d]×\± 1\, write ri=(i,+1)+(i,−1),∑i=1dri=1.r_i= λ(i,+1)+ λ(i,-1), _i=1^dr_i=1. The sign assigned within a coordinate does not affect any squared signal. For uJ,θu_J,θ, (i,a)∼[uJ,θ(i,a)2]=Δ2rJ.E_(i,a) λ[u_J,θ(i,a)^2]= ^2r_J. Hence the energy part of v+()v_+( λ) is Δ2minJrJ≤Δ2/d ^2 _Jr_J≤ ^2/d. Under the uniform coordinate design ri=1/dr_i=1/d. If two signals use distinct coordinates, their squared contrast is Δ2(rJ+rJ′)=2Δ2/d ^2(r_J+r_J )=2 ^2/d. If they use the same coordinate with opposite signs, it is 4Δ2rJ=4Δ2/d4 ^2r_J=4 ^2/d. All pairs with different designated optima fall into one of these cases. The energy constraint is therefore the active one and V+=Δ2/dV_+= ^2/d. The functions gJ(i,a)=Δai=Jg_J(i,a)= a1\i=J\ satisfy [gJ2]=Δ2rJE_ λ[g_J^2]= ^2r_J, so the identical max–min calculation in (5) gives V−=Δ2/dV_-= ^2/d. Finally, if d≥2d≥ 2, the pure pairwise value VΔV_ is at most 2Δ2/d2 ^2/d because the two smallest coordinate masses sum to at most 2/d2/d. Uniform coordinate mass attains this bound, as the two contrast cases above show. Thus VΔ=2Δ2/dV_ =2 ^2/d. When d=1d=1, only the opposite-sign case remains and VΔ=4Δ2V_ =4 ^2. □ A.9 Proof of Theorem 3 For the all-k-subset class, uniform weights xs=1/kx_s=1/k are feasible in (1). Conversely, averaging any feasible constraint over a uniformly random k-subset gives (k/L)∑sxs≥1(k/L) _sx_s≥ 1. Hence τ⋆=L/k=1/ρτ =L/k=1/ρ. For M<dM<d, the stated upper bound exceeds the maximal regret 2ρΔT2ρ T, so any recommendation suffices. For M≥dM≥ d, audit the first M rounds and assign at least n=⌊M/d⌋n= M/d sign-+1+1 queries to every coordinate. Marginalizing the i.i.d. state gives, independently across queries, Y∣I=i,A=+1∼Bern(12+ρθΔi=J).Y I=i,A=+1 \! ( 12+ρθ 1\i=J\ ). Choose the coordinate with largest absolute centered empirical mean and choose its sign from that mean. The active coordinate has centered expectation θρΔθρ , while all other coordinates have expectation zero. If every empirical mean differs from its expectation by strictly less than ρΔ/2ρ /2, the active coordinate and sign are recovered. For n Bernoulli samples, Hoeffding’s inequality and a union bound give PrJ^≠J or θ^≠θ≤2dexp(−nρ2Δ22). \ J≠ J or θ≠θ\≤ 2d \! (- nρ^2 ^22 ). Each exploration round and each round after an incorrect recommendation incurs at most 2ρΔ2ρ . The first M rounds therefore contribute at most 2ρΔM2ρ M, and the remaining rounds contribute at most the second term in the theorem. Diffuse-reliability lower bound. For the converse, let P0P_0 be the transcript law with every audited outcome fair. For each coordinate j, let QjQ_j mix the sign-+1+1 environments uniformly over all k-subsets. Define Qj†Q_j by using the same state sequence and policy randomization as QjQ_j, but returning a fair outcome whenever a state label repeats. Before a repeat, after t−1t-1 distinct labels have appeared, a newly observed label has posterior active probability at most kL−t+1≤2ρ. kL-t+1≤ 2ρ. This remains true after conditioning on adaptive actions and post-state audit decisions because the unobserved labels are exchangeable and at most k active labels remain. Conditional on a first-seen state, an audit of coordinate j under Qj†Q_j has mean 1/2+σptΔ1/2+σ p_t , where σ∈±1σ∈\± 1\ is the played sign and 0≤pt≤2ρ0≤ p_t≤ 2ρ. Thus its absolute displacement from 1/21/2 is at most 2ρΔ≤1/42ρ ≤ 1/4. Audits of other coordinates are fair. For |x|≤1/4|x|≤ 1/4, klBern(1/2),Bern(1/2+x)≤83x2.kl\Bern(1/2),Bern(1/2+x)\≤ 83x^2. Let NjN_j be the number of audits on coordinate j. The adaptive KL chain rule, with all conditionals taken under P0P_0, and the pathwise budget yield ∑j=1dKL(P0∥Qj†)≤323ρ2Δ20[∑jNj]≤323ρ2Δ2M. _j=1^dKL(P_0\|Q_j )≤ 323ρ^2 ^2E_0[ _jN_j]≤ 323ρ^2 ^2M. The coordinate play counts TjT_j satisfy ∑jTj=T _jT_j=T. If j is uniform, Markov’s inequality shows that each of the events 0[Tj]>4T/d\E_0[T_j]>4T/d\ and KL(P0∥Qj†)>128ρ2Δ2M/(3d)\KL(P_0\|Q_j )>128ρ^2 ^2M/(3d)\ contains fewer than one quarter of the coordinates. Hence at least one j satisfies both 0[Tj]≤4Td,KL(P0∥Qj†)≤128ρ2Δ2M3d≤132.E_0[T_j]≤ 4Td, (P_0\|Q_j )≤ 128ρ^2 ^2M3d≤ 132. For Ej=Tj≤T/2E_j=\T_j≤ T/2\, Markov’s inequality gives P0(Ejc)≤8/d≤1/4P_0(E_j^c)≤ 8/d≤ 1/4. The budget condition makes the displayed KL at most 1/321/32, so Pinsker’s inequality gives Qj†(Ej)≥P0(Ej)−KL(P0∥Qj†)/2≥34−18=58.Q_j (E_j)≥ P_0(E_j)- KL(P_0\|Q_j )/2≥ 34- 18= 58. The state sequence is common under QjQ_j and Qj†Q_j . Their transcripts can differ only after a repeated state, whose probability is at most T(T−1)/(2L)≤1/16T(T-1)/(2L)≤ 1/16. Hence Qj(Ej)≥9/16≥1/2Q_j(E_j)≥ 9/16≥ 1/2. On EjE_j, at least T/2T/2 actions use another coordinate, and every such action incurs target regret ρΔρ . The Bayes regret under QjQ_j is therefore at least ρΔ(T/2)(1/2)=ρΔT/4ρ (T/2)(1/2)=ρ T/4. Since QjQ_j is a uniform mixture over fixed k-subsets, at least one fixed C attains this lower bound. The sign-+1+1 subfamily lies inside the stated signed class. □ A.10 Proof of Proposition 5 Fix the true environment e and a wrong-decision e′e . For one accepted query x=(a,s)∼x=(a,s) ν, put d(x)=me(x)−me′(x)d(x)=m_e(x)-m_e (x) and W=Y−me′(x)2−Y−me(x)2=2d(x)Y−me(x)+me′(x)2.W=\Y-m_e (x)\^2-\Y-m_e(x)\^2=2d(x) \Y- m_e(x)+m_e (x)2 \. Writing De,e′2=[d(x)2]D_e,e ^2=E_ ν[d(x)^2] and re(x)=m~e(x)−me(x)r_e(x)= m_e(x)-m_e(x), Cauchy–Schwarz gives W¯:=e[W]=De,e′2+2[d(x)re(x)]≥De,e′(De,e′−2δfb). W:=E_e[W]=D_e,e ^2+2E_ ν[d(x)r_e(x)]≥ D_e,e (D_e,e -2 _ fb). When De,e′≤2δfbD_e,e ≤ 2 _ fb the displayed upper bound is trivial. Otherwise, |W|≤2|d(x)||W|≤ 2|d(x)|, [W2]≤4De,e′2E[W^2]≤ 4D_e,e ^2, W¯≤De,e′2+2δfbDe,e′<2De,e′2 W≤ D_e,e ^2+2 _ fbD_e,e <2D_e,e ^2, and |W−W¯|≤4|W- W|≤ 4. Bernstein’s inequality yields Pre∑m=1MWm≤0≤exp−MW¯22(4De,e′2+4W¯/3)≤exp−3M40(De,e′−2δfb)2. _e\! \ _m=1^MW_m≤ 0 \≤ \! \- M W^22(4D_e,e ^2+4 W/3) \≤ \! \- 3M40(D_e,e -2 _ fb)^2 \. A union bound over wrong-decision environments, followed by the same schedule calculation as in Proposition 3, proves the nominal-regret term. For every action, replacing fef_e by f~e f_e changes its gap by at most 2εtar2 _ tar, which adds at most 2εtarT2 _ tarT. Target-preserving converse. For the converse, take actions a∈−1,+1a∈\-1,+1\, signs θ∈−1,+1θ∈\-1,+1\, and a known set C with μ(C)=ρμ(C)=ρ. The nominal and true conditional means are mθ(a,s)=12+s∈CθaΔ,m~θ(a,s)=12+ρθaΔ.m_θ(a,s)= 12+1\s∈ C\θ a , m_θ(a,s)= 12+ρθ a . Both have target fθ(a)=12+ρθaΔf_θ(a)= 12+ρθ a , so εtar=0 _ tar=0, while their uniform conditional discrepancy is (1−ρ)Δ(1-ρ) . The true feedback is state independent. Let P+P_+ and P−P_- be the complete transcript laws under the two signs. Conditional on any audited action, the outcome laws are Bern(1/2+ρΔ)Bern(1/2+ρ ) and Bern(1/2−ρΔ)Bern(1/2-ρ ), possibly in the opposite order. Unaudited rounds have identical conditional laws. The adaptive KL chain rule and the pathwise constraint therefore give KL(P+∥P−)≤+[∑t=1TBt]κρΔ≤MκρΔ.KL(P_+\|P_-) _+\! [ _t=1^TB_t ] _ρ ≤ M _ρ . Apply Bretagnolle–Huber to the event Xt=+1\X_t=+1\ using the transcript available before XtX_t is chosen. Data processing bounds its KL by the full-transcript KL, so P+Xt=−1+P−Xt=+1≥12e−MκρΔ.P_+\X_t=-1\+P_-\X_t=+1\≥ 12e^-M _ρ . The two one-round regret gaps are 2ρΔ2ρ . Summing over t and averaging the two signs yields +[RT]+−[RT]2=ρΔ∑t=1T[P+Xt=−1+P−Xt=+1]≥ρΔT2e−MκρΔ. E_+[R_T]+E_-[R_T]2=ρ _t=1^T [P_+\X_t=-1\+P_-\X_t=+1\ ]≥ ρ T2e^-M _ρ . Finally, κx=4xartanh(2x)≤16x2 _x=4xartanh(2x)≤ 16x^2 for x≤1/4x≤ 1/4. The maximum regret is at least the two-point average, which proves the converse. □ A.11 Proof of Proposition 6 Index environments by leaves h∈0,1dh∈\0,1\^d and put θh=(−1)∑ihi _h=(-1) _ih_i. Besides decision actions +1,−1\+1,-1\, include one diagnostic qvq_v for every internal binary-tree node. Decision outcomes have law Bern(1/2+aθhΔ)Bern(1/2+a _h ). Matching the feedback summaries. Fix distinct x1,…,x4p+5∈(0,1/2)x_1,…,x_4p+5∈(0,1/2) and map each point into ℝ2p+1R^2p+1 by (x)=(x,ψ1(x),…,ψp(x),ψ1(1−x),…,ψp(1−x)). F(x)= (x, _1(x),…, _p(x), _1(1-x),…, _p(1-x) ). Tverberg’s theorem partitions these 4p+5=2(2p+1)+1+14p+5=2\(2p+1)+1\+1 points into three nonempty sets I0,I1,I2I_0,I_1,I_2 whose convex hulls intersect [34]. Hence there are probability weights wj,iw_j,i supported on IjI_j with ∑i∈Ijwj,i(xi) _i∈ I_jw_j,i F(x_i) independent of j. Define Qj=12∑i∈Ijwj,i(δxi+δ1−xi).Q_j= 12 _i∈ I_jw_j,i ( _x_i+ _1-x_i ). The three laws have pairwise disjoint supports, common mean 1/21/2, and identical expectations of every ψr _r: the latter is half the matched ψr(x) _r(x) coordinate plus half the matched ψr(1−x) _r(1-x) coordinate. Their combined support has at most 8p+108p+10 points. Choosing ψr(y)=yr _r(y)=y^r recovers finite raw-moment matching; the equal-weight Prouhet construction gives a separate explicit instance [35]. Equal targets and different information. In the coded dictionary, qvq_v returns Qh|v|+1Q_h_|v|+1 when v is a prefix of h, and Q2Q_2 otherwise. In the uninformative dictionary every diagnostic returns Q0Q_0. Their common target is fh(a)=1/2+aθhΔf_h(a)=1/2+a _h on decisions and fh(qv)=1/2f_h(q_v)=1/2 on diagnostics. With ϕ(+1)=1φ(+1)=1, ϕ(−1)=−1φ(-1)=-1, and ϕ(qv)=0φ(q_v)=0, the centered target is θhΔϕ _h φ under the rank-one kernel k(x,x′)=ϕ(x)ϕ(x′)k(x,x )=φ(x)φ(x ). For the uninformative dictionary, fix opposite-parity leaves and let P+,P−P_+,P_- be their transcript laws. Only audited decision actions distinguish them. The adaptive KL chain rule and the pathwise budget give KL(P+∥P−)≤MκΔ,κΔ=klBern(1/2+Δ),Bern(1/2−Δ).KL(P_+\|P_-)≤ M _ , _ =kl\! \Bern(1/2+ ),Bern(1/2- ) \. Achievable regret in the informative dictionary. The coded policy starts at the root. At depth r, it audits qvq_v for the prefix v already recovered. The resulting sample belongs to the disjoint support of Q0Q_0, Q1Q_1, or Q2Q_2. Because the queried node is on the true path, only Q0Q_0 or Q1Q_1 can occur, and its support identifies bit hr+1h_r+1 from one sample. After d audits the leaf and its parity are known. Each diagnostic action has target value 1/21/2 while the optimal decision has value 1/2+Δ1/2+ , so these d rounds incur exactly dΔd regret. The policy then plays the optimal sign. Lower bound in the uninformative dictionary. For the uninformative dictionary, map decision actions to their signs and map every diagnostic action to an independent fair sign. Under either environment, the expected instantaneous regret is exactly 2Δ2 times the probability that this mapped sign is wrong. For each t, apply Bretagnolle–Huber to the mapped sign based on the pre-action transcript. Data processing and the preceding KL bound give P+θ^t=−1+P−θ^t=+1≥12e−MκΔ.P_+\ θ_t=-1\+P_-\ θ_t=+1\≥ 12e^-M _ . Consequently, +[RT]+−[RT]2=Δ∑t=1T[P+θ^t=−1+P−θ^t=+1]≥ΔT2e−MκΔ. E_+[R_T]+E_-[R_T]2= _t=1^T [P_+\ θ_t=-1\+P_-\ θ_t=+1\ ]≥ T2e^-M _ . Thus one of the two leaves attains the stated lower bound. Finally, κΔ=4Δartanh(2Δ)≤16Δ2 _ =4 (2 )≤ 16 ^2 for Δ≤1/4 ≤ 1/4. Under M=dM=d, T=KT=K, and Δ=1/(4K) =1/(4 K), we have MκΔ≤d/K≤1/2M _ ≤ d/K≤ 1/2. Since e−1/2/2≥1/4e^-1/2/2≥ 1/4, the uninformative regret is at least ΔK/4 K/4, whereas the coded regret is dΔd . Their ratio is at least K/(4d)=K/(4log2K)K/(4d)=K/(4 _2K). □ A.12 Proof of Theorem 4 For the deterministic class, let zs,j≥0z_s,j≥ 0 be a feasible fractional hitting weight on ×[d]S×[d]. Fixing j gives ∑s∈Chzs,j≥1 _s∈ C_hz_s,j≥ 1 for every h, so ∑szs,j≥τ⋆ _sz_s,j≥τ . Summing over j gives mass at least dτ⋆dτ . Conversely, copying an optimizer of (1) into every coordinate slice gives feasible mass dτ⋆dτ . Thus the product set system has fractional hitting number exactly dτ⋆dτ . Normalize these weights to a distribution on (s,j)(s,j) and draw M pairs independently, retaining their set of distinct values. Every Ch×JC_h×\J\ receives probability mass at least 1/(dτ⋆)1/(dτ ), so its hit probability is at least 1−(1−1dτ⋆)M.1- (1- 1dτ )^M. For the reverse bound, linear-program duality supplies a distribution on (h,J)(h,J) such that every single pair (s,j)(s,j) belongs to Ch×JC_h×\J\ with probability at most 1/(dτ⋆)1/(dτ ). For any fixed set Q of at most M pairs, the union bound gives hit probability at most M/(dτ⋆)M/(dτ ). Averaging over randomized Q and truncating at one proves (9). Deterministic lower bound. For the regret lower bound, fix a policy and run it on the null transcript Yt=1/2Y_t=1/2. Its audited state-coordinate support Q is a random set of size at most M. The finite zero-sum game in (8) has a dual prior on (h,J)(h,J) under which every distribution of Q misses Ch×JC_h×\J\ with probability at least 1−cM(d)1-c_M^(d). Draw θ independently and uniformly. On the miss event, every audited outcome equals 1/21/2, so the true transcript agrees pathwise with the null transcript. Conditional on that transcript, the policy cannot depend on θ. Averaging over θ, every played action has target value 1/21/2, while the optimal action has value 1/2+γρ1/2+γρ. Therefore [RT]≥γρTPrQ∩(Ch×J)=∅≥γρT(1−cM(d)).E[R_T]≥γρ T \Q∩(C_h×\J\)= \≥γρ T(1-c_M^(d)). Matching deterministic policy. For the upper bound, draw a support Q from an optimizer of (8). Test its pairs in any fixed order. To test (s,i)(s,i), repeatedly play coordinate i with an independent uniform sign until state s appears, then audit. The deterministic residual is nonzero exactly when s∈Chs∈ C_h and i=Ji=J, in which case its sign together with the played sign reveals θ. The policy then plays the optimal action forever. If every test is uninformative, it continues with independent uniform signs on an arbitrary coordinate. Before identification, uniform signs have expected target value 1/21/2 and incur γργρ regret per round. Let LQL_Q be the total number of rounds required to complete all tests. Each waiting time has expectation at most 1/μmin1/ _ , so [LQ]≤M/μminE[L_Q]≤ M/ _ . If Q hits Ch×JC_h×\J\, all regret is charged within these test rounds. If it misses, at most γρTγρ T additional regret is charged. Hence, uniformly over (h,J,θ)(h,J,θ), [RT]≤γρ[LQ]+γρTPrQ∩(Ch×J)=∅≤γρMμmin+γρT(1−cM(d)).E[R_T]≤γ [L_Q]+γρ T \Q∩(C_h×\J\)= \≤ γρ M _ +γρ T(1-c_M^(d)). Dividing both bounds by T and letting T→∞T→∞ proves the limit. □ A.13 Proof of Proposition 7 Proof. The definitions give 0≤αa,s≤10≤ _a,s≤ 1. For one stationary design round, PrXt=a,St=s,Bt=1=qaμa(s)αa,s=ν(a,s)Λad(). \X_t=a,S_t=s,B_t=1\=q_a _a(s) _a,s= ν(a,s) _ ad( ν). Summing over (a,s)(a,s) proves both the acceptance probability and the conditional accepted law. Independent fresh rounds therefore give i.i.d. accepted pairs. For the causal lower bound, let ℱt−1F_t-1 contain the history before XtX_t is selected and set Na=∑t≥1τ≥t,Xt=aN_a= _t≥ 11\τ≥ t,X_t=a\. Conditional on ℱt−1F_t-1 and Xt=aX_t=a, the state law is μa _a. Tonelli’s theorem therefore gives [∑t≥1τ≥t,Xt=a,St=s]=μa(s)[Na].E\! [ _t≥ 11\τ≥ t,X_t=a,S_t=s\ ]= _a(s)E[N_a]. The audited occurrence (Xτ,Sτ)(X_τ,S_τ) is one term in this sum and has probability ν(a,s)ν(a,s). Hence ν(a,s)≤μa(s)[Na]ν(a,s)≤ _a(s)E[N_a], so [Na]≥maE[N_a]≥ m_a. Summing over a proves the waiting-time bound, and weighting by Δe(a) _e(a) proves the sampling-regret bound. Under the stationary compiler, [τ]=Λad()E[τ]= _ ad( ν) and [Na]=qa[τ]=maE[N_a]=q_aE[τ]=m_a, proving equality. Conditioning on the accepted history gives the stagewise predictable statement. ∎ Appendix B Supplementary theoretical results This appendix gives the deterministic coverage specialization, the finite-summary counterexample, and the acquisition rule for known action-dependent diagnostic laws. These results refine the main guarantees without changing the action-independent assumptions used in the primary experiments. Their proofs are collected in Appendix A. B.1 Deterministic coverage and audit-only comparison The deterministic coordinate model has a sharper coefficient. Let M=Q⊆×[d]:|Q|≤MQ_M=\Q ×[d]:|Q|≤ M\. Define cM(d)=max∈Δ(M)minh,JPrQ∼Q∩(Ch×J)≠∅.c_M^(d)= _ ω∈ (Q_M) _h,J _Q ω\Q∩(C_h×\J\)≠ \. (8) The product dictionary has fractional hitting number dτ⋆dτ and 1−(1−1dτ⋆)M≤cM(d)≤min1,Mdτ⋆.1- (1- 1dτ )^M≤ c_M^(d)≤ \1, Mdτ \. (9) Theorem 4 (Exact deterministic specialization). Write the coordinate action as Xt=(It,At)∈[d]×±1X_t=(I_t,A_t)∈[d]×\± 1\. For 0<γ≤1/20<γ≤ 1/2, replacing (2) by Yt=12+γθAtIt=J,St∈ChY_t= 12+γθ A_t1\I_t=J,S_t∈ C_h\ gives γρT(1−cM(d))≤RT⋆≤γρT(1−cM(d))+γρMμmin.γρ T(1-c_M^(d))≤ R_T ≤γρ T(1-c_M^(d))+ γρ M _ . For fixed M, μ, and reliability class, limT→∞RT⋆/T=γρ(1−cM(d)) _T→∞R_T /T=γρ(1-c_M^(d)). See Appendix A.12 for the mixed-coverage duality argument and the matching audit policy. For deterministic outcome contamination bounded by ε<γ/2 <γ/2, threshold decoding remains valid and target comparison adds at most 2εT2 T. This does not cover overlapping informative and uninformative ranges. Sequential audit-only policies remain a necessary comparison because they use trusted outcomes without a reliability model [7]. The pooled policy in Theorem 3 gives one such guarantee, and Section 6 compares the conditional policies with marginal-dictionary and GP controls. Standard GP information gain cannot determine the sharper class-dependent frontier. With the same rank-d coordinate kernel, a known active coordinate gives +=1/Δ2 D_+=1/ ^2, while an unknown coordinate gives d/Δ2d/ ^2; the kernel information-gain curve is unchanged. Extending the result to a full RKHS ball requires a separate packing or localization argument. B.2 Information absent from finite feedback summaries The next result allows bounded outcomes Y∈[0,1]Y∈[0,1] and a singleton diagnostic state. It therefore concerns general conditional feedback laws rather than only the Bernoulli family in (2). Proposition 6 (Finite-statistic distributional barrier). Fix any integer p≥1p≥ 1 and bounded measurable statistics ψ1,…,ψp:[0,1]→ℝ _1,…, _p:[0,1] . For every integer d≥1d≥ 1, K=2dK=2^d, T≥dT≥ d, and 0<Δ≤1/40< ≤ 1/4, there are two finite verified-feedback dictionaries with identical target functions, the same rank-one centered target kernel, zero target misspecification, and identical conditional expectations of all ψi(Y) _i(Y) for every environment and action. One admits a causal M=dM=d policy with RT=dΔR_T=d . In the other, every causal policy using at most M audits satisfies supee[RT]≥ΔT2e−MκΔ,κΔ=2Δlog1+2Δ1−2Δ≤16Δ2. _eE_e[R_T]≥ T2e^-M _ , _ =2 1+2 1-2 ≤ 16 ^2. At M=dM=d, T=KT=K, and Δ=1/(4K) =1/(4 K) with K≥2dK≥ 2d, the regret ratio is at least K/(4log2K)K/(4 _2K). The construction and testing reduction are proved in Appendix A.11. The construction combines Tverberg’s convex-partition theorem [34] with active testing. It shows why misspecifying the conditional feedback law cannot be covered by the 2εT2 T target-comparison term or by any fixed finite summary vector on an unrestricted law class: full-law distinguishability changes while every displayed statistic and target quantity remains fixed. It does not apply when the statistics identify a restricted conditional-law family; full laws or a characteristic representation can still distinguish the construction. B.3 Action-dependent diagnostic laws The structured model in Section 3 uses a common state law so that the reliable-set mass and the target reward separate. The rejection-sampling compiler has a broader scope. Suppose instead that, conditional on choosing action a and on the past, the next state has a known law μa _a that is common across candidate environments. Let ∈Δ(×) ν∈ (A×S) be supported only on cells with μa(s)>0 _a(s)>0, and define ma=maxs:μa(s)>0ν(a,s)μa(s),Λad()=∑ama,qa=maΛad(),αa,s=ν(a,s)maμa(s),m_a= _s: _a(s)>0 ν(a,s) _a(s), _ ad( ν)= _am_a, q_a= m_a _ ad( ν), _a,s= ν(a,s)m_a _a(s), where αa,s _a,s is defined by the formula when maμa(s)>0m_a _a(s)>0 and set to zero otherwise. Zero rows are never selected. Proposition 7 (Action-dependent compiler). Selecting Xt∼X_t q and auditing after state s with probability αXt,s _X_t,s produces accepted action–state pairs that are i.i.d. ν, with acceptance probability 1/Λad()1/ _ ad( ν) per round. Moreover, every causal rule whose first audited pair has law ν satisfies [Na]≥ma,[τ]≥Λad(),e[∑t=1τΔe(Xt)]≥Cead():=∑aΔe(a)ma,E[N_a]≥ m_a, [τ]≥ _ ad( ν), _e\! [ _t=1^τ _e(X_t) ]≥ C_e ad( ν):= _a _e(a)m_a, where NaN_a counts plays of action a through the first audit time τ. The stationary compiler attains all three bounds. The identities also hold conditionally for a predictable sequence of accepted-query laws, each held fixed until the next audit. See Appendix A.13 for the construction and causal lower bound. This proposition changes only the acquisition compiler. If a separate exact finite dictionary supplies outcome laws Pea,sP_e^a,s and action-dependent targets fe(a)=∑sμa(s)e[Y∣a,s]f_e(a)= _s _a(s)E_e[Y a,s], the accepted-history Hellinger argument in Proposition 4 carries over after replacing Λ and CeC_e by Λad _ ad and CeadC_e ad. Proposition 7 does not extend the reliable-set product factorization or adaptive converse, and it does not cover estimated state laws or a learned outcome dictionary. Appendix C Experimental details and additional evidence We first specify the synthetic comparisons and uncertainty calculations, then examine conditional-model errors and AI evaluation. Each study retains its full comparison family. The AI results distinguish offline identification, fitted-table policy evaluation, and independently tested synthetic policies. Numerical checks of the mathematical identities appear at the end of this appendix. C.1 Synthetic environments, policies, and statistical analysis Policy choices were fixed using separate development seeds. Implementation checks enforce action-before-state timing, posterior normalization, and the pathwise audit cap (Appendix C.8). Each cell uses 256 paired seeds and horizon 8,192. The primary grid crosses three action geometries (rank-two and rank-eight signed coordinates and a periodic RBF kernel on 16 actions), reliability dictionary sizes one and four, known cold-state mass zero and .75.75, and budgets 128, 512, and 2,048. This gives 36 cells, seven methods, and 64,512 trajectories. All cells are retained. Reported cumulative regret is target regret over calendar time; offline simple regret is evaluated from the terminal recommendation. We also record audits, cheap state observations, completion time, and runtime. Pooled TS uses the exact state-marginal signal dictionary and purchases every early outcome until the cap. Conditional TS maintains the joint posterior over (h,z)(h,z) and purchases every outcome in the union of candidate reliable sets until the cap; the audit rule does not learn. Both sample a target model for each action while budget remains, then exploit the maximum-likelihood model. Direct UCB purchases early outcomes and uses empirical-best exploitation after exhaustion. Joint and pooled likelihood controls use the same frozen action LP as Algorithm 1, but audit every early round. The known-h design is an oracle. States are generated by the environment, never chosen by these controls. The paired intervals are descriptive, unadjusted per-setting comparisons across 256 shared environment/noise streams. They do not give simultaneous 95% coverage over the grid. Aggregate figure intervals use 2,000 paired bootstrap resamples within each cell, conditional on the fixed grid; cells are not resampled as random tasks. Conditional TS versus pooled TS changes both likelihood and audit gate; this is not an isolated kernel-sharing ablation. They do not establish the performance of learned audit allocation. The offline application replays evaluate correction estimators, while the JudgeBench and 32-judge policy studies below execute fitted finite-dictionary policies. The overlapping suite replaces singleton reliable states by cyclic blocks of sizes two and four on eight states. It crosses two reward geometries, two state-arrival regimes, and three budgets (24 cells; 30,720 trajectories). Thirty-eight construction checks verify every target mean, overlap mass, posterior likelihood, and absence of unaudited outcomes. Paired 95% intervals favor the conditional policy in 19 settings, are unresolved in five, and favor the pooled policy in none; its budget-wise geometric regret ratios are .904,.522,.392.904,.522,.392. 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 11 and .25.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). C.2 Adaptive verification: regret and acquisition tradeoffs The theory-aligned adaptive suite uses eight actions, four squared-exponential kernel sections, and three prespecified reliability families: four singleton sets, six cyclic adjacent pairs, and four disjoint adjacent pairs. It crosses two horizon–cap pairs (512,32)(512,32) and (2048,64)(2048,64), giving 24 settings. The floor ε=.25 =.25, Chernoff alternative rule, analysis, and 512 paired replications were selected on a separate 24-system development study before the fresh suite was measured. Every environment, setting, and outcome is retained. The fresh suite contains 36,864 trajectories. Safe adaptive versus the fixed robust joint design has geometric regret ratio .933.933 and nine lower-regret, 15 unresolved, and no higher-regret paired comparisons; the three reliability-family ratios are .937,.934,.929.937,.934,.929. Pure adaptive allocation has ratio .915.915 and 13 lower-regret and 11 unresolved comparisons, but does not preserve the robust information floor. One safe-adaptive point estimate is adverse, with ratio 1.0211.021, and remains unresolved. Independent reconstruction from every-round action counts and accepted success/failure counts reproduces total regret and every final likelihood for all trajectories; the maximum errors are 6.14×10−126.14× 10^-12 and 8.53×10−148.53× 10^-14. A supplementary study was specified after the preceding outcomes and then run on new paired streams. It retains all 24 settings and matches the exact dictionary, zero-label calibration endowment, horizon, cap, and maximum-likelihood commit rule. Every trajectory has exactly T action deployments and M trusted labels. Regret charges all T actions, including unaudited waiting rounds. Table 3 reports all comparators and separately measures the round on which the cap is reached. The audit-only controls either sample an environment from the exact posterior or choose the posterior-mean-best action, and purchase every early trusted outcome until the cap. Comparator Regret ratio Time ratio Error (p) Lower Unclear Higher Fixed robust joint design .916 2.554 −7.06-7.06 13 11 0 Pure adaptive design 1.006 .827 +0.66+0.66 0 24 0 Product design .916 4.764 −6.89-6.89 12 12 0 Uniform action and verification .907 4.764 −7.71-7.71 11 13 0 Optimized action, uniform verification .921 4.764 −6.96-6.96 11 12 1 Audit-only dictionary TS .943 4.764 −4.92-4.92 6 18 0 Audit-only posterior greedy .966 4.764 −4.21-4.21 3 21 0 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 MMth 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. The one resolved adverse comparison is against optimized-action uniform verification for the disjoint-pair family at (T,M)=(512,32)(T,M)=(512,32) and the smoothest signal: ratio 1.0781.078 and paired regret difference .738.738 with interval [.026,1.451][.026,1.451]. At the level of sample means, safe adaptive has higher regret in 2 settings against fixed robust design, 12 against pure adaptive, 1 against each product or uniform design, 3 against audit-only dictionary TS, and 5 against audit-only posterior greedy. Safe adaptive takes 4.764×4.764× as many rounds geometrically as every-round controls (setting range 3.2383.238–6.8036.803), so this is a trusted-label comparison rather than a general cost advantage. The supplementary study comprises 98,304 trajectories. Its acquisition accounting uses every action and every purchased label. Proposition 4’s raw union-bound terms range from 14.4714.47 to 22.8222.82, so clipping makes the guaranteed error upper bound one in all 24 settings. The result proves a positive information floor but does not quantitatively explain the observed finite-budget gain. These exact-model experiments do not establish learned-dictionary validity, calibration coverage, a kernel effect, monetary savings, or real-task benefit. C.3 Gaussian-process and factorial controls A development screen for the Gaussian-process controls was specified before execution. It crossed coordinate and periodic-RBF actions, one and four reliability groups, cold-state masses zero and .75.75, budgets 64 and 256, horizon 1,024, and 24 repetitions. GP and identity controls received the same prior-scale grid, and UCB controls received the same exploration-width grid. Each method minimized mean cumulative regret over the complete development grid. The selected settings and the defaults were then frozen before an independently seeded measured comparison. The measured grid adds budget 1,024, uses horizon 4,096 and 128 paired repetitions, and contains 24 cells, 13 methods, and 39,936 trajectories. GP-UCB and GP-TS use the target kernel and a Gaussian working likelihood with variance 1/41/4 for bounded Bernoulli outcomes. Identity-UCB and identity-TS use the same updates and hyperparameters without cross-action covariance. The prior mean is 1/21/2 and covariance is (s0ρU)2(s_0ρ U)^2 K, with s0∈.5,1,2s_0∈\.5,1,2\ in the screen. The UCB multiplier is chosen from 1,2,3\1,2,3\. Defaults use s0=1s_0=1 and multiplier two. Selection gives (s0,β)=(2,3)(s_0,β)=(2,3) for GP-UCB, s0=2s_0=2 for GP-TS, (.5,3)(.5,3) for identity-UCB, and s0=2s_0=2 for identity-TS. Both types audit every round until the cap and then exploit a posterior-mean maximizer. Candidate-gated pooled TS uses audited mean 1/2+uz(a)/g1/2+u_z(a)/g, where g is the number of candidate reliability groups. All-round pooled TS instead uses 1/2+ρuz(a)1/2+ρ u_z(a). These controls are computational GP baselines, not exact Bayesian inference for the finite signal dictionary. Every method observes 4,096 cheap states and respects the hard audit cap. Policy Cumulative regret ↓ Standard error Simple regret ↓ 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 All-round pooled TS 124.30 2.66 .0287 448.00 Identity-UCB, default 124.83 2.78 .0286 448.00 GP-TS, default 130.40 2.65 .0292 448.00 GP-TS, selected 136.68 2.70 .0310 448.00 Reliability-Kernel-Design 138.46 2.74 .0226 446.14 Identity-TS, default 144.58 2.76 .0325 448.00 Identity-TS, selected 149.37 2.76 .0337 448.00 Table 4: Independent Gaussian-process control suite. Means average the 24 fixed settings equally. SE is [∑c=124sc2/128]1/2/24[ _c=1^24s_c^2/128]^1/2/24, where sc2s_c^2 is the within-setting sample variance. Bold denotes the lowest mean regret. “Selected” denotes the setting chosen on the separate development grid. Against default GP-UCB, conditional TS has 15 lower-regret, seven unresolved, and two higher-regret paired comparisons and geometric-mean regret ratio .663.663. Against default GP-TS 15 comparisons favor the conditional policy and nine are unresolved, with ratio .612.612. Both GP-UCB losses occur in coordinate cells. The selected GP settings have higher aggregate regret than their defaults and are retained in Table 4. Matched comparisons separate the ingredients. Kernel versus identity covariance favors GP-UCB in three settings and GP-TS in six, with respective regret ratios .925.925 and .886.886. Joint versus pooled likelihood favors the joint model in six settings under the candidate gate and nine under all-round auditing, with ratios .901.901 and .800.800. Candidate-state auditing is favored in ten settings under either likelihood, with ratios .820.820 for the joint model and .728.728 for the pooled model. All remaining comparisons are unresolved, and none favor the comparator. Thus the complete conditional policy has a nominal advantage in these families, while the isolated kernel effect is smaller and often unresolved. The intervals are unadjusted descriptive 95% normal intervals for paired seed differences within each cell. C.4 Feedback-law and target misspecification The supported robustness grid has 36 cells, five methods, and 46,080 trajectories. Write the nominal mean as 1/2+s∈Chuz(a)1/2+1\s∈ C_h\u_z(a). The feedback perturbation uses 1/2+[s∈Ch(1−α)+s∉Chαρ/(1−ρ)]uz(a)1/2+[1\s∈ C_h\(1-α)+1\s∉ C_h\αρ/(1-ρ)]u_z(a), preserving the target exactly. Here ρ=1/16ρ=1/16, |uz(a)|≤1/4|u_z(a)|≤ 1/4, and the conditional-error radius is α/4α/4. Exact flattening requires α=1−ρα=1-ρ. The target perturbation instead adds a state-independent cosine residual r(a)r(a), of radius .05.05 or .10.10, to both the conditional outcome mean and the scoring target. This tests target/dictionary error and also shifts the conditional means; it does not leave the full feedback model correct. On the finite full-rank RBF grid, it is not evidence that a specified RKHS norm bound is violated. All reported perturbation experiments use the outcome laws above, with target rewards obtained by marginalizing those same laws. Policies, audit budgets, horizons, kernels, and perturbation magnitudes were specified before evaluation. Exact checks verified the marginal targets, bounded Bernoulli probabilities, and state independence in the flattened model. Table 5 reports every specified perturbation, including settings in which conditional inference increases regret. Scenario Conditional regret Pooled regret Geometric ratio Nominal 54.8 88.1 .572 Feedback error .10.10 78.0 88.4 .875 Feedback error .20.20 90.8 89.2 1.027 Feedback flattened 92.4 87.4 1.068 Target perturbation .05.05 263.1 199.1 1.398 Target perturbation .10.10 350.7 204.5 1.799 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. C.5 Offline AI-system identification SAID RAG Evaluation contains 24 configurations and 15 requests per dataset, with three human ratings per output and four archived judge dimensions. The RAG method uses two-fold multivariate cross-fitting and a frozen additive generator–pipeline kernel. HotpotQA is development; PubMedQA remains unopened. AgentRewardBench development froze five binary judges and coefficient .9.9, the request split, audit design, 40,000-trial count, .02.02 simple-regret tolerance, and 90% success endpoint. The confirmation program verified the frozen protocol hash before reading targets. Selection endpoint and evaluation costs. All selection experiments report the first audit budget attaining 90% probability of simple regret at most .02.02. SAID uses 10,000 fixed-seed trials and AgentRewardBench uses 40,000. Audit-only methods receive the same trusted samples as corrected methods. Kernel smoothers are frozen before confirmation. Judge calls are counted even when archived; no missing ground truth is replaced by a prediction. RAGTruth transfer provides no gain over its strongest kernel audit-only baselines: QA ties at 48 ratings, data-to-text ties at 6, and summarization uses 18 versus 12. SummEval’s kernel baseline saturates the endpoint. No claim is made for the unevaluated PubMedQA split. A separate 32-judge Civil Comments development screen is a negative control. Its best oracle proxy predicts only 1.07× mean audit savings, and no tested method reaches the endpoint by 160 trusted outcomes per judge. Its reserved 248-item split is excluded from the reported comparison. For AgentRewardBench, the frozen judge set averages two priced GPT-4o-mini variants and three self-hosted Llama/Qwen variants. Logged API costs cover only the priced judges. The table therefore makes no monetary-saving claim. Raw or row-level derivatives are not redistributed. C.6 JudgeBench: conditional correction and dictionary fit Conditional-correction policies. JudgeBench is analyzed only on the frozen calibration and development groups. The simulator draws states with calibration frequencies and scores each action by its development conditional means under that same state law. The retained data loaders skip the 106 reserved rows before decoding (see the provenance statement below). Policies, horizons, caps, repetitions, and seeds are unchanged from the frozen protocol; only the inconsistent regret estimand and acquisition ledger were repaired. 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=512T=512 T=2048T=2048 Method / comparison M=16M=16 M=64M=64 M=16M=16 M=64M=64 Mean cumulative regret: shared calibration endowment 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 Audit only (no calibration) 97.036 82.003 382.906 322.982 Paired comparison: state-aware minus uniform audits Mean difference −0.050-0.050 0.3140.314 0.4300.430 1.4001.400 95% interval [−0.305,0.189][-0.305,0.189] [−0.039,0.691][-0.039,0.691] [−0.518,1.360][-0.518,1.360] [−0.147,3.020][-0.147,3.020] 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 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 The policy Monte Carlo intervals condition on the fixed tables. Separately, 20,000 paired item bootstraps resample development items within each state while retaining calibration state weights. Calibration greedy is best or tied in 90.625% of those resamples; its regret against the resampled best action has mean .00211.00211 and percentile interval [0,.03041][0,.03041]. This is a finite-item sensitivity check, not population-level uncertainty or policy re-learning. Historical price, token, labeling-time, and latency fields are absent from the release. The finite-dictionary online policy. We separately execute the online policy in Algorithm 1. The reliability dictionary is constructed only from the 144 calibration items: deterministic two-fold validation selects two candidate sets for each prespecified cardinality k∈1,2k∈\1,2\, signals are refit on all calibration items, and the dictionary and both designs are then frozen. This construction uses 144 trusted labels and 1,584 archived judge outputs before online interaction. Dictionary learning is outside the fixed-dictionary theorem. The online policies share this endowment, observe one archived judge output per round, and obey the same pathwise trusted-label cap. All four (T,M)(T,M) cells, both dictionary sizes, matched uniform-state and uniform-action ablations, calibration controls, and audit-only TS were retained. The development Bernoulli NLL is .64475.64475 for the pooled calibration model and .65311.65311 for a saturated action–state calibration model, versus .68828.68828 and .67361.67361 for the k=1k=1 and k=2k=2 dictionaries. Thus neither selected dictionary predicts the development table as well as the pooled model. Table 8 shows the corresponding policy result. 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. T M Calibration greedy Uniform verified TS RK design k=1k=1 RK design k=2k=2 512 16 0.000 5.469 58.801 80.364 512 64 0.000 4.921 62.836 113.122 2048 16 0.000 21.758 232.605 288.367 2048 64 0.000 19.090 238.288 312.919 The geometric-mean regret ratios of the RK designs to uniform verified TS are 11.6311.63 and 16.4616.46. Against the same action design with uniform-state auditing, the k=1k=1 design is worse in all four cells; the k=2k=2 design is better in one cell and worse in three. The selective gate approximately doubles the rounds needed to collect M audits for k=1k=1 and quadruples them for k=2k=2. At (T,M)=(2048,64)(T,M)=(2048,64), the two RK designs use 30.0 and 24.6 unique development items for 64 reveal calls, versus 43.6 under uniform verification. This is adverse, non-confirmatory development evidence: the 100 development labels had been opened by earlier analyses, while retained loaders skip the 106 reserved rows before decoding. C.7 Thirty-two LLM judges: signal clipping and reliability coverage Task, feedback, and calibration. A fresh replay couples all 32 archived LLM judges from Li et al. [36] to ChaosNLI human-majority labels [37]. An action chooses a judge before the task family is realized; the three action-independent states are MNLI-matched, SNLI, and α ; the cheap output is the selected judge’s archived class; and an audit reveals the majority of 100 human annotations. The hash split contains 591 calibration and 1,248 development items. The 1,140-row reserved partition is excluded from the reported study. All ten policies, both prespecified dictionary sizes, four horizon–budget settings, and 512 repetitions were fixed before outcome decoding for this study. Calibration-informed policies share an offline endowment of 591 trusted labels and 18,912 judge outputs, observe one archived output per online round, and obey the same pathwise reveal cap. The study comprises 20,480 trajectories. The saturated action–state model has development Bernoulli NLL .48280.48280, compared with .52020.52020 for the pooled model and .59460.59460 and .53301.53301 for the k=1k=1 and k=2k=2 dictionaries. All 64 refit signal entries for k=1k=1 and 63 of 64 for k=2k=2 equal the clipping ceiling .24.24. Consequently, both action designs collapse to a one-point design chosen from a clipped tie. The RK policies have lower fixed-table regret than their uniform-action and uniformly verified controls, but their regret is exactly equal to the matched uniform-state ablation in every cell and repetition. The state gate therefore changes only acquisition time: at (T,M)=(4096,128)(T,M)=(4096,128), the mean time to collect the cap is 192.5 rounds for k=1k=1 and 386.5 for k=2k=2, versus 128 under uniform-state verification. This adverse result shows that high-accuracy judge rewards can lie outside the useful range of the centered clipped dictionary. It supplies no positive evidence for state-aware auditing; historical price, token, latency, and human-labeling costs are unavailable and are not imputed. Separating reliability coverage from action-model expansion. Expanding both the reliability class and the signal dictionary changes two parts of the policy simultaneously. A postdiagnostic study separates their effects. For each k∈1,2k∈\1,2\, the reliability class contains all three k-subsets of the three task states, while the signal dictionary retains only the two baseline-offset signals selected by calibration-only cross-validation; the environment class is their Cartesian product. The reliability LP therefore gives a uniform state gate, while the action LP is unchanged from the two-signal design. Because the common fitted baseline cancels from every likelihood contrast, the product-separation guarantee applies conditional on these fitted signals. It does not cover calibration or population uncertainty. Table 9: Thirty-two-judge development replay: cumulative regret, mean ± 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. T M Full reliability class Two fitted reliability sets One reliable state (k=1k=1) 1,024 32 32.20±.9232.20±.92 31.79±.9331.79±.93 1,024 128 36.09±.8236.09±.82 35.65±.8335.65±.83 4,096 32 127.10±3.79127.10± 3.79 125.76±3.79125.76± 3.79 4,096 128 140.88±3.63140.88± 3.63 139.90±3.64139.90± 3.64 Two reliable states (k=2k=2) 1,024 32 16.00±.2416.00±.24 16.32±.2416.32±.24 1,024 128 20.38±.2120.38±.21 20.57±.2020.57±.20 4,096 32 61.38±.9861.38±.98 62.60±.9762.60±.97 4,096 128 69.61±.9169.61±.91 70.03±.9070.03±.90 Closing the reliability class changes mean regret little relative to the matched two-set model: the geometric ratios are 1.0111.011 for k=1k=1 (all four comparisons unresolved) and .986.986 for k=2k=2 (one lower-regret and three unresolved comparisons). These intervals do not establish equivalence. Relative to full closure, which also inserts every fitted signal into the action LP, the decoupled design improves all four cells for each k, with ratios .802.802 and .862.862. Thus the earlier closure penalty came from expanded action-signal constraints, not uniform state coverage. The k=2k=2 design also improves all four cells against a pure hitting gate (ratio .829.829), uniform verified TS (.581.581), and calibration greedy (.464.464). The adverse k=1k=1 result is retained: it is worse than uniform verified TS in all four cells (ratio 1.1431.143) and unresolved against pure hitting (.990.990). The study comprises 24,576 trajectories over 48 policy–cell groups. Independent checks verify the full reliability class, unchanged two-signal action design, hard caps, acquisition ledgers, and regret rescoring; the largest rescore error is 1.38×10−111.38× 10^-11. Calibration-informed policies share 591 trusted labels and 18,912 archived judge outputs, whereas audit-only TS does not. Monetary, token, latency, and labeling-time prices are unavailable and are not imputed. Protected confirmation rows were skipped before decoding. This is development evidence selected after diagnosing the initial Panel32 failure, not fresh confirmation. It neither learns the audit gate nor establishes population-level coverage. Calibration uncertainty. An aggregate-only calibration analysis sharpens this boundary. Simultaneous two-sided Clopper–Pearson intervals use 95% familywise coverage over all 224 pooled and state-subset action means considered by the selection family. None of the four fitted targets certifies a unique best action: their point-estimate margins are .00779,.000216,.00919,0.00779,.000216,.00919,0, whereas the corresponding lower-bound versus strongest-competitor-upper-bound margins are −.108,−.156,−.0959,−.134-.108,-.156,-.0959,-.134. A conservative nearest-candidate Hoeffding calculation, holding these point gaps fixed, requires respectively 300,053, 391,088,570, and 215,323 observations per controlled quantity; the zero-gap target cannot certify at any finite size under this rule. These are sufficient sizes, not power estimates or collection recommendations. Failure to certify does not show that a selected action is wrong, but it prevents this aggregate evidence from supplying a useful δ in Corollary 1; exact dictionary coverage is stronger still. The calculation assumes independent calibration requests within each action and subset and does not cover dictionary misspecification or population shift. Reserved-data provenance. Reserved groups are excluded from the reported development fitting, policy selection, and performance evaluation, but their access histories differ. Retained JudgeBench loaders skip the 106 reserved rows before decoding. RAGTruth reserved labels were processed by upstream preparation and included in aggregate summaries, without use in the reported development comparisons. The LPHB confirmation rows were exposed and subsequently quarantined. SummEval reserved rows were decoded during processing but not used for development. These groups therefore do not constitute a uniformly untouched confirmation pool. No study above is reclassified as independent confirmation on the basis of those reserved groups. C.8 Numerical checks of the theoretical identities These checks assess the implementation of algebraic identities, optimization programs, and trajectory accounting. They supplement the proofs in Appendix A and are not an independent proof review or evidence of practical performance. Table 10 groups the checks by the mathematical claim they assess. Full generators, tolerances, and outputs are supplied with the reproducibility code. 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. Identity or guarantee Evaluation systems Observed discrepancy or check Product separation 180 random dictionaries; 40 coordinate cases Minimum normalized margin .9999999999999989.9999999999999989; coordinate error 1.74×10−181.74× 10^-18 Deterministic coverage 1,440 LP cases from 240 set systems Hitting error 8.88×10−168.88× 10^-16; coverage violation 2.22×10−162.22× 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×10−163.34× 10^-16; causal cost error 1.14×10−131.14× 10^-13 Finite-horizon accounting 1,000 joint designs; independent forward recursion Design-length error 4.27×10−144.27× 10^-14; regret error 2.85×10−142.85× 10^-14 Adaptive information floor 144 development systems and measured adaptive laws Minimum information divided by εI0 I_0 equals one Diffuse reliability 44 hitting LPs; 210,000 KL comparisons; 19,200 decoder trajectories Hitting error 8.88×10−168.88× 10^-16; no five-standard-deviation upper-bound violation Misspecification bounds 100,000 random systems; 10,000 flattening cases; 72,000 decoder trajectories No constant violation; target-preservation error 1.11×10−161.11× 10^-16 Finite-summary construction Tree depths through 12; moment orders through eight 8,188 adaptive paths checked; zero requested-moment discrepancies on 29,520 points Trajectory reconstruction. The adaptive study records every action and every accepted outcome. Independent reconstruction of all 36,864 primary trajectories reproduces cumulative regret and terminal likelihoods to 6.14×10−126.14× 10^-12 and 8.53×10−148.53× 10^-14, respectively. The 98,304 supplementary trajectories use the same reconstruction. Timing checks ensure that actions precede the current state, audit decisions follow it, and every path respects the hard cap. These checks validate accounting rather than the accuracy of a learned outcome model. Optimization and acquisition checks. Additional product-design comparisons verify the exact χ()χ( p) cost on 1,000 cases and the prior-mixture and fixed-design dual identities on 500 cases each. The largest prior-mixture error is 9.02×10−119.02× 10^-11, and the largest fixed-design inequality violation is 1.19×10−151.19× 10^-15. The finite-horizon design/exploitation partition has error 1.57×10−131.57× 10^-13. These independent formulations detect coding or normalization errors without replacing the analytical arguments. Appendix D Detailed comparisons with prior work Verified and prediction-powered bandits. P-LUCB studies best-arm identification with LLM judges, selective audits, and residual-aware allocation [2]. PPAI estimates prediction weights under adaptive sampling [4]. Limited-verification bandits quantify the value of trusted observations under attacks [5]. These works establish that auditing and correction are not new primitives. Our objective is cumulative true-reward regret under a hard audit budget, and our new parameter is an unknown conditional-reliability class. MLA-UCB uses machine-learning-generated surrogate rewards for cumulative-regret reduction [6], while confidence–budget matching treats optional costly observations in sequential learning [7]. They provide controls for judge-assisted and audit-scarce regimes, respectively. Neither models a latent post-action reliability set coupled to kernel action geometry. Kernel and multi-fidelity optimization. Auxiliary-feedback IGP-UCB uses parameterized correlated feedback [1]. PA-GP-UCB models prediction and reward jointly and observes both during online selection [10]. Robust multi-fidelity BO guards against unreliable low-fidelity sources [9]. Kernel experimental design and misspecified GP bandits already control target approximation error [11, 12]. ASB permits post-surrogate acquisition: its fixed-comparison theorem gives PRE/POST variance-optimal allocations, its main guarantees cover finite policy classes and a hard-budget linear construction, and its learned-refinement proposition charges residual-model error [3]. Chandak et al. optimize context-conditioned collection policies and use exact multi-proposal rejection sampling to reuse adaptively collected data [28]. These results establish post-surrogate timing, residual-based allocation, kernel modeling, and rejection sampling as existing components. Controlled sensing and experimental design. Controlled multihypothesis testing optimizes Chernoff information over sensing controls, and adaptive causal controls can improve on open-loop designs with three or more hypotheses [18, 22]. Bayesian decision-region determination already selects tests only to resolve the action-relevant equivalence class, including correlated noisy tests [19, 20]. Transductive linear best-arm identification separates measurement and decision sets through experimental design [21]; recent hybrid-feedback GLB identification optimizes a joint query space and includes heterogeneous acquisition costs [38]. These methods supply decision-focused likelihood tests and query designs with exponentially decreasing error. Proposition 4 composes their predictable adaptive allocation principle with a fixed robust information floor and the exact action-before-state cost identity. The composition is scoped to this protocol and is not a new generic adaptive-testing principle. Our reliability–action factorization, adaptive converse, and deterministic coverage formula specialize this approach to unknown reliable-state sets; they do not characterize general adaptive optimality. Mixture testing and the diffuse regime. Adaptive mixture testing already shows that repeated allocation can overcome rare-component dilution when the same latent item can be queried repeatedly [30]. Our diffuse construction instead makes state repetitions negligible over the decision horizon. After the negligible-collision coupling, marginalizing the reliability set gives a standard d-armed Bernoulli identification problem with gap ρΔρ ; classical best-arm lower bounds and fixed-budget conversions already yield the d/(ρ2Δ2)d/(ρ^2 ^2) scale up to logarithms [29, 31]. The resulting comparison shows that rank and hitting number alone are insufficient to determine audit complexity. Partial monitoring. Kernelized linear partial monitoring already supplies information-directed sequential policies, observability-based regret classifications, and RKHS observation operators [24]. Its contextual extension also plans against a known context distribution, so a sequential information ratio, context-weighted observability coefficient, or kernelization is not new here. A finite verified-feedback dictionary can be unfolded into a constrained partial-monitoring game over contingent audit maps; our protocol-specific remainder is the hard pathwise audit cap together with the exact action-before-state compilation cost. This is why the paper states a structured finite-family factorization rather than a new generic sequential complexity. Nonparametric conditional feedback. Nonparametric models provide another way to represent conditional feedback laws. CME-UCB already estimates conditional mean embeddings while sequentially optimizing an unknown conditional expectation [25]; distributionally-aware kernel bandits model probability kernels through kernel mean embeddings and prove UCB guarantees and lower bounds [26]; and active cost-aware streaming labeling chooses expensive labels after inputs arrive and gives matching discrete and continuous-RKHS rates [27]. These models do not impose the action-before-state protocol with a hard audit cap. Extending their estimators to that protocol would require accounting for the acquisition costs in Proposition 3. Post-action contexts. Post-serving-context bandits also observe informative features only after action selection; poLinUCB learns a pre-to-post context map and attains tight linear-contextual regret [39]. The trusted outcome here is optional and subject to a hard pathwise budget. The row-max formula is the exact domination constant obtained when classical rejection sampling is restricted to proposals of the form q(a)μ(s)q(a)μ(s); it quantifies acquisition cost under this proposal restriction. Cost-sensitive acquisition. Costly-observation bandits provide complementary cost-sensitive guarantees. Schur et al. give two-phase GP algorithms, cost-adjusted information-gain complexities, and matching finite-arm rates for observation-priced objectives [8]. Gong and Zhang establish hard free-observation-budget phase transitions for contextual bandits with paid observations [40]. Harding et al. choose a costly source before an unobserved group is revealed and obtain matching budgeted minimax rates by effective-sample-size design and post-stratification [41]; Reyzin et al. give tight cost-adaptive rates for heterogeneous expert queries [42]. Progressive-feedback bandits quantify early-surrogate value by conditional mutual information, but eventually observe the primary outcome for every play [43]. Cost-aware acquisition, hard feedback budgets, and rejection-sampled reuse are therefore prior methods. Harding et al. do not select labels after seeing the group or study sequential decision regret, while Chandak et al. do not study hard audit budgets, sampling regret, or latent reliability. The remaining scoped distinction is the finite-dictionary reliability–kernel theorem and its adaptive converse; Schur et al. explicitly leave general-kernel optimality open, so Proposition 3 is not presented as a matching kernel converse. LLM routing with restricted feedback. Recent LLM-routing studies consider related feedback restrictions. Wei et al. give linear-contextual upper and lower bounds under a limited reward-feedback budget [44]. Sridhar et al. combine context-dependent graph feedback with ML surrogate rewards and use expert aggregation to recover a reward-only guarantee when those surrogates are misspecified [45]. Unlike both settings, trusted outcomes here are optional after observing a post-action state, and the unknown object is the state-conditional reliability law. AI evaluation. ARES uses prediction-powered inference for RAG evaluation [16]. HbBoPs applies deep-kernel Bayesian optimization to prompt selection [17]. NAOD designs preference queries while accounting for judge nuisance [46]. Our model is narrower: fixed configurations, i.i.d. requests, bounded outcomes, and a fixed kernel. It excludes contextual routing, nonstationarity, and within-agent-step credit assignment. 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 P-LUCB [2] selective audits for identification cumulative regret and kernel action geometry Robust / misspecified BAI [32, 33] contaminated or structurally misspecified identification separate target and audit-law error costs Audit-only / CBM [7] valid without an informative judge benchmark that proposed feedback must improve Table 11: Comparison of feedback protocols, guarantees, and modeling assumptions. 18, 19, 29, 20, 34, 32, 21, 30, 35, 37, 24, 25, 11, 12, 7, 33, 13, 22, 5, 26, 27, 9, 1, 39, 16, 28, 14, 17, 2, 3, 45, 31, 40, 41, 43, 15, 6, 46, 10, 36, 23, 4, 42, 8, 44, 38