Paper deep dive
Rank Without an Oracle: Deviation-Aware Interaction-Rank Selection from Offline Multi-Agent Logs
Xiangwu Wang, Chengwei Cao, Hongyuan Tang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 9/9/2026, 6:12:06 AM
Summary
The paper introduces Selective Interaction-Rank Validation (SIRV), a method for selecting interaction ranks in offline multi-agent payoff models. SIRV addresses the distribution shift between logging data and deployment/deviation distributions by constructing a common union of candidate-induced distributions. It uses calibration data to evaluate candidates on this union, providing finite-candidate target-risk bounds and coarse correlated equilibrium (CCE) gap certificates. The method abstains if targets are unsupported or imprecisely estimated. Empirical results show that SIRV with empirical-Bernstein bounds reduces CCE-gap certificates and regret compared to baselines like ID-Mean.
Entities (6)
Relation Signals (5)
SIRV → provides → CCE gap certificate
confidence 95% · A common coverage event yields a finite-candidate target-risk bound and a candidate-specific coarse correlated equilibrium (CCE) gap certificate.
SIRV → uses → common union of distributions
confidence 95% · A training split fits nested payoff models and constructs a common union of all candidate deployment and unilateral-replacement distributions
SIRV → abstains → unsupported targets
confidence 93% · SIRV returns the smallest rank ... and abstains when a declared target is unsupported or too imprecisely estimated.
Empirical-Bernstein → reduces → CCE-gap certificate
confidence 92% · empirical-Bernstein bounds reduce the median CCE-gap certificate by 42.5% relative to Hoeffding bounds
SIRV → outperforms → ID-Mean
confidence 90% · the SIRV-EB fallback rule lowers mean true candidate-selection CCE regret relative to ID-Mean
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Offline multi-agent payoff models are estimated under a logging distribution but used on distributions induced by learned solutions and unilateral deviations. Standard held-out loss can therefore favor an interaction class that predicts logged play well while distorting strategic incentives. We introduce Selective Interaction-Rank Validation (SIRV) for finite games with known logging distributions. A training split fits nested payoff models and constructs a common union of all candidate deployment and unilateral-replacement distributions; an independent calibration split evaluates every candidate on this same union. SIRV returns the smallest rank whose simultaneous upper worst-target risk is within tolerance of the best upper score, and abstains when a declared target is unsupported or too imprecisely estimated. A common coverage event yields a finite-candidate target-risk bound and a candidate-specific coarse correlated equilibrium (CCE) gap certificate. We also isolate an exact two-point off-support non-identifiability result. In a controlled factorial study with 2,048 independent games per family, empirical-Bernstein bounds reduce the median CCE-gap certificate by 42.5% relative to Hoeffding bounds on common returns, with a 1.36-point reduction in supported return. Under paired rank misspecification and in a separately generated congestion family, the SIRV-EB fallback rule lowers mean true candidate-selection CCE regret relative to ID-Mean, while retaining game-level losses. Across 384 games at $N=3,5,8$, ID-Mean-relative mean CCE-regret effects stay positive while certified return falls sharply under weak coverage. These results separate certifiable model selection from universal strategic improvement.
Tags
Links
- Source: https://arxiv.org/abs/2609.08358v1
- Canonical: https://arxiv.org/abs/2609.08358v1
Trouble viewing inline? Open PDF directly →
Full Text
89,888 characters extracted from source content.
Expand or collapse full text
\@ACM@balancefalse Rank Without an Oracle: Deviation-Aware Interaction-Rank Selection from Offline Multi-Agent Logs Conference: ; ; CCS: Computing methodologies Multi-agent systemsCCS: Theory of computation Algorithmic game theoryCCS: Computing methodologies Reinforcement learning Xiangwu Wang Affiliation: University of Hong Kong , Chengwei Cao Affiliation: University of California, San Diego and Hongyuan Tang Affiliation: Carnegie Mellon University © none Abstract. Offline multi-agent payoff models are estimated under a logging distribution but used on distributions induced by learned solutions and unilateral deviations. Standard held-out loss can therefore favor an interaction class that predicts logged play well while distorting strategic incentives. We introduce Selective Interaction-Rank Validation (Sirv) for finite games with known logging distributions. A training split fits nested payoff models and constructs a common union of all candidate deployment and unilateral- replacement distributions; an independent calibration split evaluates every candidate on this same union. Sirv returns the smallest rank whose simultaneous upper worst-target risk is within tolerance of the best upper score, and abstains when a declared target is unsupported or too imprecisely estimated. A common coverage event yields a finite-candidate target-risk bound and a candidate-specific coarse correlated equilibrium (CCE) gap certificate. We also isolate an exact two-point off-support non-identifiability result. In a controlled factorial study with 2,048 independent games per family, empirical-Bernstein bounds reduce the median CCE-gap certificate by 42.5% relative to Hoeffding bounds on common returns, with a 1.36-point reduction in supported return. Under paired rank misspecification and in a separately generated congestion family, the SIRV-EB fallback rule lowers mean true candidate-selection CCE regret relative to ID-Mean, while retaining game-level losses. Across 384 games at N=3,5,8N=3,5,8, ID-Mean-relative mean CCE-regret effects stay positive while certified return falls sharply under weak coverage. These results separate certifiable model selection from universal strategic improvement. Keywords: offline multi-agent learning, interaction-rank selection, coarse correlated equilibrium, abstaining model selection 1. Introduction An offline multi-agent learner observes actions and payoffs under a fixed logging distribution, yet its payoff model is used on distributions induced by a learned solution and by agents deviating from that solution (Cui and Du, 2022b; Zhang et al., 2023). This shift makes model complexity strategically consequential. Low-interaction-rank models replace unrestricted dependence on all agents with dependence on small interacting groups and can improve statistical rates when the chosen rank captures the relevant payoff structure (Zhan et al., 2025). Existing analyses, however, take the rank or function class as given. Ordinary held-out error measures prediction under the logging distribution, not whether a model preserves incentives under unilateral deviations. Offline RL faces an analogous problem of ranking candidates without deployment (Tang and Wiens, 2021), while interaction-rank analyses take the class as input and empirical-game analyses validate sampled-profile payoff error (Zhan et al., 2025; Jordan and Wellman, 2009). Neither addresses class selection on candidate-induced deviation distributions. For example, under independent binary logging with action-one probability p, a pair residual ca1a2ca_1a_2 contributes c2p2c^2p^2 to logging risk but c2pc^2p after fixing a1=1a_1=1, an amplification by 1/p1/p. At p=0p=0, that off-support payoff cannot be recovered by reweighting. Can interaction rank nevertheless be selected from logged play while every candidate is compared on the deployment and deviation distributions induced by the candidates themselves? We address this question in finite normal-form games. Selective Interaction-Rank Validation (Sirv) first uses a training split to fit nested models and a solution candidate for each rank, then defines the union of their deployment and unilateral-replacement distributions. Independent calibration data provide simultaneous squared-risk intervals on this common union. Thus every rank faces the same targets. Sirv abstains if the declared union is unsupported or imprecise; otherwise it returns the smallest rank whose upper score is within τ of the best upper score. The common target union is the central object of our analysis. It is fixed by training data, yet supports a selective comparison on independent calibration data. On the simultaneous coverage event, the returned candidate’s worst-target risk is at most τ+ωτ+ω above that of the best candidate, where ω is the observed maximum score width. The same event yields a candidate-specific coarse correlated equilibrium (CCE) gap certificate. Because return is decided on calibration data, the bound and certificate control the joint event of return and violation. Complementing these guarantees, a two-point construction identifies the information boundary: without additional assumptions, deciding one specified off-support deviation payoff has minimax error 1/21/2. We then evaluate whether target-risk calibration translates into strategic performance, treating the two as separate empirical questions. The study combines 2,048-game factorial and misspecification panels with an independently generated congestion family, target-scope ablations, and finite-grid scaling through eight players. True-payoff CCE regret, welfare regret, rank stability, and certificate thresholds reveal both the gains from variance-adaptive bounds and the remaining game-level losses. Our scope is finite actions, known logging probabilities, and targets fixed before calibration; the objective is target-specific adequacy rather than algebraic-rank recovery. 2. Related Work 2.1. Interaction Structure in Games Compact game representations exploit local or low-order interactions to avoid the full joint-action description (Kearns et al., 2001), including context-specific, anonymous, and additive structure (Jiang et al., 2011). Empirical games have also used payoff regression, clustering, and graphical structure recovery (Vorobeychik et al., 2007; Ficici et al., 2008; Honorio and Ortiz, 2015). Zhan et al. (Zhan et al., 2025) define interaction rank for offline multi-agent reinforcement learning and show how low rank improves parts of the distribution-shift and sample-complexity dependence. Their guarantees condition on a chosen K-IR class and assume that the relevant true and learned rewards have interaction rank at most K; they do not select K from the log. We instead select among nested ranks on candidate-induced targets, rather than recover generating algebraic structure from partial payoff observations (Duong et al., 2009). 2.2. Empirical-Game Model Selection Jordan and Wellman (Jordan and Wellman, 2009) compare representations of empirical games using validation stratified over profiles, construct reductions over equivalent strategies, and discuss factored representations; strategic regret is evaluated after selection, not used as validation loss. Related tools include importance-weighted cross-validation under covariate shift (Sugiyama et al., 2007) and overlap-aware confident off-policy selection (Kuzborskij et al., 2021). Single-agent offline RL provides oracle inequalities, selection without tuned hyperparameters, uncertainty-aware or pessimistic comparisons, and Bellman-error criteria (Lee et al., 2022; Zhang and Jiang, 2021; Yang et al., 2022; Yang et al., 2023; Zitovsky et al., 2023). Logged-bandit counterfactual risk minimization and overlap-aware evaluation likewise predate our estimators (Bottou et al., 2013; Swaminathan and Joachims, 2015; Wang et al., 2017). More broadly, data-dependent pessimism is a central response to insufficient offline coverage, although its form determines the resulting bias–coverage tradeoff (Jin et al., 2021; Xie et al., 2021). Abstention itself has a long history through reject-option and selective-prediction formulations, including modern risk–coverage formulations and distribution-free risk control (Chow, 1970; El-Yaniv and Wiener, 2010; Bates et al., 2021). Sirv combines held-out, distribution-corrected validation with a common multi-agent target set, an explicit support decision, and an equilibrium certificate. Here “selective” denotes an abstaining decision rule; the guarantee controls the joint event of return and violation, not error conditional on return. 2.3. Offline-Game Coverage Offline-game theory has already established that coverage must account for unilateral alternatives. In two-player zero-sum Markov games, single-policy coverage can be insufficient, whereas unilateral concentration supports learning guarantees (Cui and Du, 2022b). Results for general function approximation likewise control Nash, CE, or CCE learning through pessimism and selective coverage of deviation policies (Zhang et al., 2023). Strategy-wise confidence construction is another approach (Cui and Du, 2022a). COPSRO and uncertainty-aware empirical-game solvers choose equilibria under fixed representations (Shao et al., 2025; Nguyen and Wellman, 2026). Uniform payoff approximation has also been related to equilibrium preservation and stable properties (Tuyls et al., 2020; Areyan Viqueira et al., 2020; Cousins et al., 2023); a recent EGTA survey organizes the wider representation, sampling, and equilibrium-analysis literature (Wellman et al., 2025). Taken together, prior empirical-game work selects representations by predictive loss on sampled profiles, interaction-rank analyses take the class as input, and offline-game methods select policies or equilibria under a fixed representation. Sirv instead selects the representation class on one common, training-measurable union of rank-specific deployment and unilateral-replacement distributions. Relative to uniform-payoff EGTA guarantees, its certificate is target-local to the returned candidate. 3. Problem Setting and Information Boundary Let G=(N,(i)i∈[N],(ui)i∈[N])G=(N,(A_i)_i∈[N],(u_i)_i∈[N]) be a finite game, =∏iA= _iA_i, and ui:→[0,1]u_i:A→[0,1]. We observe i.i.d. tuples (As,Ys)(A_s,Y_s), where As∼νA_s ν for a known logging distribution ν, Ys,i∈[0,1]Y_s,i∈[0,1], and [Ys,i∣As=a]=ui(a)E[Y_s,i A_s=a]=u_i(a). The data are split once into training and calibration sets. For binary actions, our nested rank k class contains Boolean monomials up to order k, (1) fk,i(a)=∑S⊆[N],|S|≤kθi,S∏j∈Saj,ℱ1⊆⋯⊆ℱKmax.f_k,i(a)= _S [N],\,|S|≤ k _i,S _j∈ Sa_j, _1 ·s _K_ . The method itself only needs nested fitted candidates; the theorem does not require the true game to belong to one of these classes. Our order counts total joint-action variables in a monomial. For the strategically relevant generator terms, which all contain player i, order k therefore means player i plus at most k−1k-1 other agents. This makes the indexing consistent with the K-IR convention of Zhan et al. (Zhan et al., 2025), while Eq. (1) also permits nuisance terms that do not contain i. 3.1. Structural Rank and Target Adequacy Generating order need not equal the rank preferred for deployment: a high-order term may be negligible on the declared targets, and estimation may favor a smaller class. Our evaluation oracle is therefore the smallest rank whose exact worst risk on the training-defined target union is within τ of the minimum. Synthetic payoff tables provide this label only for evaluation and are unavailable to model fitting, target construction, or selection. To illustrate the distribution shift, consider an omission residual h(a)=caiajh(a)=ca_ia_j under product logging with action-one probabilities pi,pjp_i,p_j. Its squared-risk contribution is c2pipjc^2p_ip_j under ν but c2pjc^2p_j under replacement Di,1(ν)D_i,1(ν), an amplification by 1/pi1/p_i for pi>0p_i>0. This calculation isolates the mass-shift mechanism; it does not assume that a fitted model has exactly this residual. Small pip_i causes imprecision, while pi=0p_i=0 creates the information boundary below. For a distribution q and pure replacement b∈ib _i, define (2) Di,b(q)(a)=ai=b∑ai′∈iq(ai′,a−i).D_i,b(q)(a)=1\a_i=b\ _a_i _iq(a_i ,a_-i). The CCE gap, including the no-deviation option, is (3) Gapu(q)=max0,maxi,bA∼q[ui(b,A−i)−ui(A)].Gap_u(q)= \! \0, _i,bE_A q[u_i(b,A_-i)-u_i(A)] \. Pure replacements exhaust the ex-ante deviations in a finite CCE definition (Moulin and Vial, 1978; Monnot and Piliouras, 2017). CCE is also the canonical limiting notion associated with vanishing external regret (Roughgarden, 2015). 3.2. Off-Support Non-Identifiability The following pair isolates one deviation payoff that the log cannot distinguish. Proposition 0 (off-support deviation-payoff non-identifiability). Consider three binary-action players, logging probabilities (0,0.25,0.5)(0,0.25,0.5), and identical mean-zero additive noise supported on [−0.1,0.1][-0.1,0.1]. Let all payoffs except player 1’s be 0.50.5, and let u10(a)=0.4+0.1a1,u11(a)=0.4+0.1a1+0.2a1a2.u^0_1(a)=0.4+0.1a_1, u^1_1(a)=0.4+0.1a_1+0.2a_1a_2. Let H∈0,1H∈\0,1\ index the game and define the replacement payoff θH _H =ν−1[u1H(1,A−1)], =E_ _-1[u^H_1(1,A_-1)], (θ0,θ1) ( _0, _1) =(0.50,0.55), =(0.50,0.55), infH^maxh∈0,1Prh(H^≠h) _ H _h∈\0,1\ _h( H≠ h) =12. = 12. Here the infimum ranges over possibly randomized tests based only on the log. Equivalently, the binary decision target is H=θH>0.525H=1\ _H>0.525\. Logging fixes a1=0a_1=0, so the observation laws coincide, although the payoffs are respectively 1-IR and 2-IR and differ by 0.050.05 after replacement. The proposition concerns this payoff point, not every partial-support selection problem; Appendix D gives the proof. A candidate-local rule could retain candidates whose own targets are supported, but they would no longer be compared on the common union T; this changes RkR_k, the comparator, and the oracle. Sirv instead uses a conservative global support rule to retain the declared cross-candidate target union. 4. Selective Interaction-Rank Validation Condition on the training split. For every k∈[Kmax]k∈[K_ ], fit a payoff model u^k u_k and compute a solver-selected CCE σk _k of the estimated game. Every fitted payoff prediction is clipped to [0,1][0,1]. We deploy a logging-anchored mixture (4) qk=(1−α)ν+ασk,q_k=(1-α)ν+α _k, and define from the training split the common target set (5) =⋃j=1Kmax(qj∪Di,b(qj):i∈[N],b∈i).T= _j=1^K_ (\q_j\∪\D_i,b(q_j):i∈[N],b _i\ ). Every model is scored on every target in this union. This prevents a rank from being favored by generating an easy target only for itself. It also accounts for cross-candidate deployment: rank k must predict not only qkq_k but targets induced by every other rank. The union is finite and training-measurable, so this protection does not require uniform concentration over an adaptive policy class. The resulting objective is robust adequacy over the declared candidate set, rather than candidate-local deployment-risk minimization. Appendix H measures the return cost of this shared comparator against candidate-local scopes, which define different risks and oracles rather than competing estimates of the same objective. For model k, player i, and target t∈t , define noisy squared risk (6) rk,i,t=A∼t,Yi|A[(u^k,i(A)−Yi)2],Rk=maxi,trk,i,t.r_k,i,t=E_A t,Y_i A[( u_k,i(A)-Y_i)^2], R_k= _i,tr_k,i,t. Conditional unbiasedness decomposes expected squared loss into squared payoff bias plus reward variance. Thus, under target support, rk,i,tr_k,i,t is a validation-risk estimand that upper-bounds mean payoff error. Accordingly, RkR_k is a predictive-risk estimand, not a structural-rank or strategic-value estimand; we evaluate strategic outcomes separately. Heterogeneous variance can still affect which player–target pair attains the maximum; Appendix L discusses this scope. The selection and certification steps accept any simultaneous confidence procedure ℐI that, conditional on training, returns [ℓk,i,t,uk,i,t][ _k,i,t,u_k,i,t] satisfying the simultaneous coverage property (7) Pr(∀k,i,t:rk,i,t∈[ℓk,i,t,uk,i,t]∣Dtr)≥1−δ. \! (∀ k,i,t:\ r_k,i,t∈[ _k,i,t,u_k,i,t] D_ tr )≥ 1-δ. We satisfy this condition by estimating profile-conditional loss before averaging under each target. Let nan_a and m^k,i,a m_k,i,a be the calibration count and squared-loss mean at profile a, and let F=KmaxN||F=K_ N|A|. The profile-Hoeffding construction uses, for na>0n_a>0, (8) ρaH=min1,log(2F/δ)2na.ρ H_a= \! \1, (2F/δ)2n_a \. The profile-EB construction instead uses the variance-adaptive empirical-Bernstein radius derived in Appendix B. Each construction uses [0,1][0,1] when its required profile count is unavailable, otherwise clips the profile interval to [0,1][0,1], and averages its endpoints with weights t(a)t(a). Both perform exact finite-profile reweighting and satisfy Eq. (7) (Hoeffding, 1963; Maurer and Pontil, 2009). Their relation to importance-weighted validation and overlap is standard (Sugiyama et al., 2007; Cortes et al., 2010). The support decision uses the known population probabilities ν(a)ν(a), while the precision decision uses calibration counts and target mass. A positive-probability profile may therefore still trigger imprecision. The global support rule is not needed for interval validity—vacuous profile intervals preserve coverage—but is a conservative policy that preserves the declared target union. Restricting T to supported targets is possible, but would define a different risk, comparator, and oracle. Define rank scores (9) Lk=maxi,tℓk,i,t,Uk=maxi,tuk,i,t,ω=maxk(Uk−Lk).L_k= _i,t _k,i,t, U_k= _i,tu_k,i,t, ω= _k(U_k-L_k). Sirv abstains if some target has positive mass outside the support of ν, or if the largest target-interval half-width exceeds a declared ϵcert _ cert. Otherwise it returns (10) k^=mink:Uk≤minjUj+τ. k= \k:U_k≤ _jU_j+τ\. The tie-break returns the smallest rank meeting the declared upper-score criterion. The adequacy tolerance τ and precision threshold ϵcert _ cert are method parameters independent of the calibration observations. Algorithm 1 summarizes Sirv; full target-construction pseudocode appears in Appendix E. Table 1. Selectors compared with the same split and tolerance. Hats denote calibration point estimates; H and EB denote Hoeffding and empirical-Bernstein intervals. Method Rank score Refusal ID-Mean mean player loss under ν no ID-Max worst player loss under ν no Target-Point maxi,tr^k,i,t _i,t r_k,i,t no Target-IPS maxi,tr^k,i,tIPS _i,t r IPS_k,i,t support IPS-EB maxi,tuk,i,tIPS _i,tu IPS_k,i,t support/precision Sirv-H maxi,tuk,i,tH _i,tu H_k,i,t support/precision Sirv-EB maxi,tuk,i,tEB _i,tu EB_k,i,t support/precision ID-Mean and ID-Max use average and worst-player logging loss, respectively; Target-Point instead scores the common target set. Target-IPS estimates those risks by inverse propensity weighting, IPS-EB adds simultaneous confidence bounds, and Sirv-H/Sirv-EB aggregate profile-level intervals. Thus the comparisons separate target choice, reweighting, and uncertainty treatment; Table 1 records their distinct refusal rules. Algorithm 1 Selective Interaction-Rank Validation (Sirv) 1: split log, known ν, ranks 1:Kmax1:K_ , α,τ,ϵcert,δα,τ, _ cert,δ, confidence procedure ℐI 2: for k=1,…,Kmaxk=1,…,K_ do 3: fit u^k u_k on training data; compute σk _k 4: set qk←(1−α)ν+ασkq_k←(1-α)ν+α _k 5: construct T from the training split using Eq. (5) 6: build every [ℓk,i,t,uk,i,t][ _k,i,t,u_k,i,t] with ℐI 7: if a target is unsupported or maximum half-width >ϵcert> _ cert then 8: return abstain 9: compute Lk,UkL_k,U_k and return Eq. (10) 5. Guarantees Because all models and targets are measurable functions of the training split, concentration can be applied conditionally on training. The profile-based confidence constructions in Section 4 provide the following event. Lemma 0 (simultaneous target intervals). The Hoeffding and empirical-Bernstein profile constructions, together with the direct IPS-EB construction defined in Appendix B, satisfy Eq. (7). Thus, with conditional probability at least 1−δ1-δ, every rk,i,tr_k,i,t lies in [ℓk,i,t,uk,i,t][ _k,i,t,u_k,i,t] simultaneously. Denote this event by EtargetE_ target. For either profile construction, a union bound first covers the profile risks; every target then remains covered because it is a fixed nonnegative linear combination of them. IPS-EB instead covers target risks directly. The result does not assert usefulness: at zero or thin support an interval may be vacuous. All results below require only EtargetE_ target and therefore apply to any confidence procedure satisfying Eq. (7). Theorem 2 (finite-candidate target-risk selection bound). Let ℐI be any confidence procedure satisfying Eq. (7), and let k∗∈argminkRkk^*∈ _kR_k. On EtargetE_ target, whenever Sirv returns, (11) Rk^≤minkRk+τ+ω.R_ k≤ _kR_k+τ+ω. Consequently, (12) ℙ(Sirv returns and Rk^−minkRk>τ+ω)≤δ.P\! (Sirv returns and R_ k- _kR_k>τ+ω )≤δ. The proof is a short interval chain: Rk^≤Uk^≤Uk∗+τ≤Lk∗+ω+τ≤Rk∗+ω+τR_ k≤ U_ k≤ U_k^*+τ≤ L_k^*+ω+τ≤ R_k^*+ω+τ. Notably, the selector compares upper scores to the best upper score; it does not compare against the best lower bound. The final probability statement is joint. Conditioning it on return would divide by a data-dependent return probability and is not justified by this argument. Proposition 0 (observable precision and shared failure event). If Sirv returns, then ω≤2ϵcertω≤ 2 _ cert. Moreover, the probability that it returns and violates either Eq. (11) or the CCE certificate in Theorem 4 is at most δ (not 2δ2δ). For each rank, let (i,t)(i,t) attain UkU_k. Then Uk−Lk≤uk,i,t−ℓk,i,t≤2ϵcertU_k-L_k≤ u_k,i,t- _k,i,t≤ 2 _ cert on return, proving the first statement. Both theorem violations are impossible on the same event EtargetE_ target, so their union is contained in EtargetcE_ target^c. The precision term is therefore observable before deployment, although conservatism in the component intervals can make it larger than the realized excess risk. Target risk matters strategically because CCE gain is a difference of two payoff expectations. Define the computable certificate (13) Ck=Gapu^k(qk)+maxiuk,i,qk+maxi,buk,i,Di,b(qk).C_k=Gap_ u_k(q_k)+ _i u_k,i,q_k+ _i,b u_k,i,D_i,b(q_k). Theorem 4 (candidate-specific CCE certificate). On EtargetE_ target, Gapu(qk)≤CkGap_u(q_k)≤ C_k for every candidate k. Therefore (14) ℙ(Sirv returns and Gapu(qk^)>Ck^)≤δ.P(Sirv returns and Gap_u(q_ k)>C_ k)≤δ. For each deviation, insert and subtract the predicted payoff difference. Its two bias terms are bounded by Cauchy–Schwarz under qkq_k and Di,b(qk)D_i,b(q_k). Since YiY_i is conditionally unbiased, [(u^k,i−Yi)2∣A]E[( u_k,i-Y_i)^2 A] upper-bounds squared mean-payoff error. Maximizing gives Eq. (13); Appendix C gives the full proof. This theorem certifies a returned candidate. It neither orders candidates by true CCE gap nor promises that Sirv improves that gap over in-distribution validation. The predicted-gap term in Eq. (13) is necessary. Although σk _k is a CCE of the estimated game, the deployed qk=(1−α)ν+ασkq_k=(1-α)ν+α _k need not be one. The certificate therefore does not assume that logging anchoring preserves equilibrium. Also, because rk,i,tr_k,i,t includes conditional reward variance, it upper-bounds mean-payoff error rather than estimating it exactly; this is one source of the certificate slack observed below. 6. Experiments We evaluate SIRV through strategic outcomes and certificate utility computed from the true payoff table, neither of which defines its selection objective. We then study robustness to rank misspecification and heterogeneous noise. Target-risk alignment is reported separately in Appendix I. 6.1. Design We generate three-player binary-action games with zj=2aj−1z_j=2a_j-1 and (15) ui(a)=0.5+∑1≤|S|≤K,i∈Sθi,S∏j∈Szj.u_i(a)=0.5+ _1≤|S|≤ K,\,i∈ S _i,S _j∈ Sz_j. The controlled family makes target risks, CCE gaps, and welfare exactly computable, separating certificate validity from outcome-estimation error. Within each interaction order, independent signs and random magnitudes are normalized to fixed ℓ1 _1 budgets. Rank 1 uses B1=0.16B_1=0.16; rank 2 uses (B1,B2)=(0.16,h)(B_1,B_2)=(0.16,h); and rank 3 uses (0.08,0.08,h)(0.08,0.08,h), with h∈0.04,0.12h∈\0.04,0.12\. The total budget keeps noiseless payoffs in [0.22,0.78][0.22,0.78], and observations add independent Unif[−0.02,0.02]Unif[-0.02,0.02] noise. Each order contains 2,048 independent base games. Product-Bernoulli logging is balanced, moderate, thin, or unsupported; the three supported regimes have minority-action probabilities 0.50.5, [0.25,0.40][0.25,0.40], and [0.08,0.18][0.08,0.18], respectively. Unsupported logging fixes one action coordinate. We cross these regimes with n∈20,000,80,000,320,000n∈\20,000,80,000,320,000\ and two repetitions. The five game families therefore yield 245,760 configurations, of which 184,320 are supported. Conditions within a base game share the underlying payoff coefficients, and the base game is the inferential unit. All selectors use the same 50/50 training–calibration split, candidate ranks 1,2,3\1,2,3\, solver-selected welfare-maximizing predicted CCEs, and deployment weight α=0.5α=0.5. We set τ=0.002τ=0.002, ϵcert=0.12 _ cert=0.12, and δ=0.05δ=0.05. The two in-distribution comparators are mean logging loss (ID-Mean) and worst-player logging loss (ID-Max). Target-Point evaluates point estimates on the common target union. The same parameter setting is used throughout. Target-IPS instead estimates each target risk directly as r^k,i,tIPS=1m∑s=1mt(As)ν(As)(u^k,i(As)−Ys,i)2. r IPS_k,i,t= 1m _s=1^m t(A_s)ν(A_s)( u_k,i(A_s)-Y_s,i)^2. The seven selectors in Table 1 share data, candidate deployments, target union, and tolerance, but differ in support and precision behavior. For selected rank k k, we measure candidate CCE regret and welfare regret using the simulator’s mean payoff table, with Wu(q)=A∼q[N−1∑iui(A)]W_u(q)=E_A q[N^-1 _iu_i(A)]: (16) RegCCE(k^) _ CCE( k) =Gapu(qk^)−mink∈Gapu(qk), =Gap_u(q_ k)- _k Gap_u(q_k), (17) RegW(k^) _W( k) =maxk∈Wu(qk)−Wu(qk^). = _k W_u(q_k)-W_u(q_ k). These candidate-selection regrets compare only the fitted deployments qk\q_k\, not an unrestricted strategic oracle, and are unavailable to every selector. For selective methods, we report both conditional-on-return quantities and a complete-decision rule that uses ID-Mean after abstention. The main paired comparisons use this ID-fallback rule over all supported rows, with positive effects favoring the alternative to ID-Mean. We average paired effects within each base game and report equal-game means and 95% percentile intervals from 5,000 bootstrap resamples of the 2,048 games (Wiedenbeck et al., 2014). Intervals quantify random-game variation conditional on the fixed grid; within-game conditions are averaged, not treated as independent units. The primary comparison is SIRV-EB versus ID-Mean for candidate CCE regret under heterogeneous noise; other intervals are descriptive, with ties and losses retained. The robustness study applies a paired perturbation to the same 2,048 rank-3, h=0.12h=0.12 base games used in the factorial study; it is not an independent holdout set. Every selector is restricted to ranks 1,2\1,2\, so neither candidate is correctly specified. It crosses balanced, moderate, and thin logging with the same three sample sizes and two repetitions. Under homoscedastic noise, observations again use Unif[−0.02,0.02]Unif[-0.02,0.02]. Under heterogeneous noise, each game–player–profile has a half-width bi,a∈[0.01,0.10]b_i,a∈[0.01,0.10] and noise Unif[−bi,a,bi,a]Unif[-b_i,a,b_i,a]; exact target risk uses variance bi,a2/3b_i,a^2/3. The two noise conditions contribute 36,864 rows each, for 73,728 configurations. True CCE and welfare outcomes use only the mean payoff table. Regret in this study is relative to the better deployment within =1,2K=\1,2\, not to the excluded rank-3 model or an unrestricted oracle. 6.2. Selective return Figure 1. SIRV-EB selective return over the complete factorial grid. Five game families, four logging regimes, and three sample sizes give 60 cells. Each tile reports returns out of 4,096 runs (2,048 base games and two repetitions), accounting for all 245,760 configurations. Return increases with sample size under thin logging; all unsupported cells are refused.Five side-by-side four-by-three tile matrices show SIRV-EB returned-run counts. Rows are balanced, moderate, thin, and unsupported logging; columns are 20k, 80k, and 320k samples. Thin-row counts increase with sample size, while every unsupported count is zero. SIRV-EB returned on 169,004/184,320 supported rows (91.69%) and refused all 61,440 unsupported rows (Figure 1). The SIRV-H control returned on 171,504 supported rows (93.05%). Direct IPS-EB returned on 166,611 (90.39%). Target-IPS returned on every supported row and refused every unsupported row. Counts by condition and repetition stability appear in Appendix I. 6.3. Strategic outcomes in the well-specified family Figure 2. External strategic effects in the well-specified study. Rows separate generating ranks 2 and 3; columns show true-payoff candidate-selection CCE regret and welfare regret. Each panel contains the 2,048 paired base-game effects for six alternatives to ID-Mean under ID fallback, with interval summaries computed over games. Positive values favor the alternative. Every rank-2 effect is an exact tie; rank 3 has positive means but retains method-dependent ties and negative game-level effects.Four paired-effect panels compare ID-Max, Target-Point, Target-IPS, IPS-EB, SIRV-H, and SIRV-EB with ID-Mean. Both rank-two panels lie at zero. Rank-three CCE and welfare panels show positive mean effects with distributions extending to zero or negative values for some methods. The external outcomes sharply separate generating orders 2 and 3 (Figure 2). Generating-order-1 and -2 families each tied ID-Mean exactly in both regrets across all 2,048 games; order 1 is omitted from the figure. For generating order 3, the SIRV-EB fallback system reduced mean CCE regret by 0.00518 (95% interval [0.00486,0.00550][0.00486,0.00550]) and welfare regret by 0.00328 ([0.00303,0.00355][0.00303,0.00355]). SIRV-H produced similar effects, 0.00538 and 0.00346. The point selectors had larger mean effects: Target-Point and Target-IPS each reduced CCE regret by 0.00993 and welfare regret by 0.00635. They do not, however, supply the simultaneous selective certificates evaluated below. Thus the results distinguish strategic mean performance from certifiability rather than defining a single method ranking. 6.4. Rank misspecification and heterogeneous noise Figure 3. External effects across specification and noise conditions. Rows show true-payoff candidate-selection CCE and welfare regret; columns show well-specified rank-3 games, rank-misspecified games with homoscedastic noise, and the same misspecified games with heterogeneous noise. Each panel contains six methods’ 2,048 paired game effects relative to ID-Mean under ID fallback. Positive values favor the alternative.Six panels compare paired game-level regret effects. CCE effects have positive means for target-aware methods in all three columns, but include losses and ties. Target-aware welfare effects are positive on average in the three columns, while their game-level distributions also include losses and ties. Under misspecification and heterogeneous noise, the SIRV-EB fallback rule reduced mean candidate CCE regret by 0.01362 relative to ID-Mean (95% interval [0.01248,0.01479][0.01248,0.01479]; Figure 3). The effect was positive for 49.2% of game means, tied for 25.0%, and negative for 25.9%. The corresponding mean welfare-regret effect was 0.00397, with interval [0.00321,0.00474][0.00321,0.00474]; 32.1% of its game-level effects were negative. Homoscedastic noise gave a similar SIRV-EB CCE effect, 0.01383 [0.01265,0.01502][0.01265,0.01502], and a mean welfare effect of 0.00402 [0.00324,0.00479][0.00324,0.00479]. Target-Point attained a larger mean CCE effect under heterogeneous noise: 0.01741, with a 95% interval from 0.01569 to 0.01915. The Target-IPS mean was 0.01746, with interval 0.01576 to 0.01917. Neither point-estimator result removes the negative game-level tail, and neither establishes pointwise dominance. These results support positive average CCE- and welfare-regret effects in this controlled misspecification family, not a universal strategic advantage. On 512 independent weighted congestion games, SIRV-EB fallback improved mean CCE/welfare regret by 0.01317/0.01608, with both 95% game-bootstrap intervals above zero (Appendix G). On the N∈3,5,8N∈\3,5,8\ scale grid, its mean CCE effect remained positive, while return and certificate utility declined; three of nine agent-count–logging cells did not meet the predefined criterion through 1.28 million samples (Appendix H). 6.5. Certificate utility Figure 4. Certificate tightness and threshold utility on the 184,320 supported well-specified rows. Panels (a–b) show all 169,004 SIRV-EB returns: realized target-risk excess divided by budget τ+ωτ+ω, and true CCE gap divided by its candidate certificate, plotted against the corresponding certificate quantity. Panels (c–d) report the fraction of all supported rows that both return and satisfy each deployment threshold for SIRV-H, SIRV-EB, and IPS-EB; abstentions remain in the denominator.The upper panels compare realized quantities with their certificate boundaries for SIRV-EB returns. The lower panels show threshold-response profiles for three confidence procedures. Empirical- Bernstein bounds certify substantially more rows at strict risk and CCE thresholds than SIRV-H, while the strictest CCE thresholds remain rarely or never attainable. On 168,904 common returns, the median CCE certificate was 0.26668 for SIRV-EB versus 0.46365 for SIRV-H, a 42.5% reduction. Overall supported return was 1.36 percentage points lower. Across its own returns, IPS-EB reached a median of 0.23296 with a 90.39% return rate. Among all supported rows, the fraction that both returned and had risk budget at most 0.05 rose from 38.73% for SIRV-H to 71.94% for SIRV-EB and 72.83% for IPS-EB. At a CCE threshold of 0.2, the corresponding fractions were 0%, 28.57%, and 36.34%; at 0.5 they were 50.69%, 82.29%, and 82.80% (Figure 4). No method produced a certificate at most 0.05, so the certificates remain conservative at strict strategic tolerances. Among SIRV-EB returns, the median realized-excess/budget ratio was zero and its 90th percentile was 0.161; the median true-gap/certificate ratio was 0.282. The heterogeneous-noise condition was harder to certify: its median SIRV-EB CCE certificate was 0.40015, and only 0.65%, 7.69%, and 77.63% of returns met CCE thresholds 0.2, 0.3, and 0.5. Requiring both τ+ω≤0.05τ+ω≤ 0.05 and Ck^≤0.2C_ k≤ 0.2 retained 28.21% of all supported factorial rows but only 0.56% of heterogeneous-noise rows. Every covered return in both studies satisfied its target-risk budget and CCE certificate. A user with acceptable risk excess γR _R can require τ+ω≤γRτ+ω≤ _R, and a user with acceptable strategic gap γG _G can additionally require Ck^≤γGC_ k≤ _G. The threshold profiles show the resulting utilization rather than reporting coverage alone. Table 2. Selected-rank agreement across the two repetitions under ID fallback. The factorial and misspecified heterogeneous-noise columns contain 92,160 and 18,432 supported repetition pairs, respectively. Method Factorial Misspecified hetero. ID-Mean .9959 .9989 ID-Max .9933 .9995 Target-Point .9978 .9823 Target-IPS .9972 .9700 IPS-EB .9922 .9852 SIRV-H .9896 .9833 SIRV-EB .9892 .9826 Under ID fallback, repetition agreement was at least .9892 in the factorial study and .9700 in the misspecified study. Return-decision agreement ranged from .9915 to .9974 and from .9869 to .9909, respectively. 7. Conclusion Offline multi-agent model selection should evaluate candidates on deployment and unilateral deviations, not only logged play. Sirv compares nested ranks on a common target union, returning the smallest rank that meets a simultaneous upper-score criterion or abstaining. One coverage event yields target-risk and candidate-specific CCE-gap bounds; a two-point construction establishes non-identifiability of a specified off-support payoff. Empirical-Bernstein intervals reduced median CCE certificates by 42.5% relative to Hoeffding intervals. The SIRV-EB fallback system had positive average CCE- and welfare-regret effects in the rank-3, misspecified, and congestion families, while rank-2 effects were zero and individual losses remained. Scaling retained positive mean effects as certificate utility declined. Thus Sirv provides auditable, target-aware selection rather than universal strategic improvement; its return decision can be combined with application-specific risk and CCE thresholds. References Areyan Viqueira et al. (2020) E. Areyan Viqueira, C. Cousins, and A. Greenwald Improved algorithms for learning equilibria in simulation-based games. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, p. 79–87. Cited by: §2.3. Bates et al. (2021) S. Bates, A. Angelopoulos, L. Lei, J. Malik, and M. I. Jordan Distribution-free, risk-controlling prediction sets. Journal of the ACM 68 (6). External Links: Document Cited by: §2.2. Bottou et al. (2013) L. Bottou, J. Peters, J. Quiñonero-Candela, D. X. Charles, D. M. Chickering, E. Portugaly, D. Ray, P. Simard, and E. Snelson Counterfactual reasoning and learning systems: the example of computational advertising. Journal of Machine Learning Research 14 (101), p. 3207–3260. External Links: Link Cited by: §2.2. Chow (1970) C. K. Chow On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory 16 (1), p. 41–46. External Links: Document Cited by: §2.2. Cortes et al. (2010) C. Cortes, Y. Mansour, and M. Mohri Learning bounds for importance weighting. In Advances in Neural Information Processing Systems, Vol. 23, p. 442–450. Cited by: §4. Cousins et al. (2023) C. Cousins, B. Mishra, E. Areyan Viqueira, and A. Greenwald Learning properties in simulation-based games. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, p. 272–280. Cited by: §2.3. Cui and Du (2022a) Q. Cui and S. S. Du Provably efficient offline multi-agent reinforcement learning via strategy-wise bonus. In Advances in Neural Information Processing Systems, Vol. 35, p. 11739–11751. Cited by: §2.3. Cui and Du (2022b) Q. Cui and S. S. Du When are offline two-player zero-sum Markov games solvable?. In Advances in Neural Information Processing Systems, Vol. 35, p. 25779–25791. Cited by: §1, §2.3. Duong et al. (2009) Q. Duong, Y. Vorobeychik, S. Singh, and M. P. Wellman Learning graphical game models. In Proceedings of the 21st International Joint Conference on Artificial Intelligence, p. 116–121. Cited by: §2.1. El-Yaniv and Wiener (2010) R. El-Yaniv and Y. Wiener On the foundations of noise-free selective classification. Journal of Machine Learning Research 11 (53), p. 1605–1641. External Links: Link Cited by: §2.2. Ficici et al. (2008) S. G. Ficici, D. C. Parkes, and A. Pfeffer Learning and solving many-player games through a cluster-based representation. In Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, p. 187–195. Cited by: §2.1. Harks and Klimm (2012) T. Harks and M. Klimm On the existence of pure nash equilibria in weighted congestion games. Mathematics of Operations Research 37 (3), p. 419–436. External Links: Document Cited by: Appendix G. Hoeffding (1963) W. Hoeffding Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58 (301), p. 13–30. External Links: Document Cited by: §4. Honorio and Ortiz (2015) J. Honorio and L. Ortiz Learning the structure and parameters of large-population graphical games from behavioral data. Journal of Machine Learning Research 16, p. 1157–1210. Cited by: §2.1. Jiang et al. (2011) A. X. Jiang, K. Leyton-Brown, and N. A. R. Bhat Action-graph games. Games and Economic Behavior 71 (1), p. 141–173. External Links: Document Cited by: §2.1. Jin et al. (2021) Y. Jin, Z. Yang, and Z. Wang Is pessimism provably efficient for offline RL?. In Proceedings of the 38th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 139, p. 5084–5096. External Links: Link Cited by: §2.2. Jordan and Wellman (2009) P. R. Jordan and M. P. Wellman Generalization risk minimization in empirical game models. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems, p. 553–560. Cited by: §1, §2.2. Kearns et al. (2001) M. J. Kearns, M. L. Littman, and S. P. Singh Graphical models for game theory. In Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, p. 253–260. Cited by: §2.1. Kuzborskij et al. (2021) I. Kuzborskij, C. Vernade, A. György, and C. Szepesvári Confident off-policy evaluation and selection through self-normalized importance weighting. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 130, p. 640–648. External Links: Link Cited by: §2.2. Lee et al. (2022) J. N. Lee, G. Tucker, O. Nachum, B. Dai, and E. Brunskill Oracle inequalities for model selection in offline reinforcement learning. In Advances in Neural Information Processing Systems, Vol. 35, p. 28194–28207. Cited by: §2.2. Maurer and Pontil (2009) A. Maurer and M. Pontil Empirical bernstein bounds and sample-variance penalization. In Proceedings of the 22nd Annual Conference on Learning Theory, External Links: Link Cited by: §B.1, §4. Monnot and Piliouras (2017) B. Monnot and G. Piliouras Limits and limitations of no-regret learning in games. The Knowledge Engineering Review 32, p. e21. External Links: Document Cited by: §3.1. Moulin and Vial (1978) H. Moulin and J. Vial Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory 7 (3–4), p. 201–221. External Links: Document Cited by: §3.1. Nguyen and Wellman (2026) A. A. Nguyen and M. P. Wellman Conservative equilibrium discovery in offline game-theoretic multiagent reinforcement learning. In Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems, p. 3787–3794. Cited by: §2.3. Roughgarden (2015) T. Roughgarden Intrinsic robustness of the price of anarchy. Journal of the ACM 62 (5). External Links: Document Cited by: §3.1. Shao et al. (2025) Z. Shao, L. Zhuang, H. Li, and S. Wang COPSRO: an offline empirical game theoretic method with conservative critic. IEEE Transactions on Neural Networks and Learning Systems 36 (7), p. 12389–12399. External Links: Document Cited by: §2.3. Sugiyama et al. (2007) M. Sugiyama, M. Krauledat, and K. Müller Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research 8, p. 985–1005. External Links: Link Cited by: §2.2, §4. Swaminathan and Joachims (2015) A. Swaminathan and T. Joachims Counterfactual risk minimization: learning from logged bandit feedback. In Proceedings of the 32nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 37, p. 814–823. External Links: Link Cited by: §2.2. Tang and Wiens (2021) S. Tang and J. Wiens Model selection for offline reinforcement learning: practical considerations for healthcare settings. In Proceedings of the 6th Machine Learning for Healthcare Conference, Proceedings of Machine Learning Research, Vol. 149, p. 2–35. External Links: Link Cited by: §1. Tuyls et al. (2020) K. Tuyls, J. Pérolat, M. Lanctot, E. Hughes, R. Everett, J. Z. Leibo, C. Szepesvári, and T. Graepel Bounds and dynamics for empirical game theoretic analysis. Autonomous Agents and Multi-Agent Systems 34 (1), p. 7. External Links: Document Cited by: §2.3. Vorobeychik et al. (2007) Y. Vorobeychik, M. P. Wellman, and S. Singh Learning payoff functions in infinite games. Machine Learning 67 (1–2), p. 145–168. External Links: Document Cited by: §2.1. Wang et al. (2017) Y. Wang, A. Agarwal, and M. Dudík Optimal and adaptive off-policy evaluation in contextual bandits. In Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 70, p. 3589–3597. External Links: Link Cited by: §2.2. Wellman et al. (2025) M. P. Wellman, K. Tuyls, and A. Greenwald Empirical game theoretic analysis: a survey. Journal of Artificial Intelligence Research 82, p. 1017–1076. External Links: Document Cited by: §2.3. Wiedenbeck et al. (2014) B. Wiedenbeck, B. Cassell, and M. P. Wellman Bootstrap statistics for empirical games. In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems, p. 597–604. Cited by: §6.1. Xie et al. (2021) T. Xie, C. Cheng, N. Jiang, P. Mineiro, and A. Agarwal Bellman-consistent pessimism for offline reinforcement learning. In Advances in Neural Information Processing Systems, Vol. 34, p. 6683–6694. External Links: Link Cited by: §2.2. Yang et al. (2023) C. H. Yang, Z. Qi, Y. Cui, and P. Chen Pessimistic model selection for offline deep reinforcement learning. In Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, Proceedings of Machine Learning Research, Vol. 216, p. 2379–2389. External Links: Link Cited by: §2.2. Yang et al. (2022) M. Yang, B. Dai, O. Nachum, G. Tucker, and D. Schuurmans Offline policy selection under uncertainty. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 151, p. 4376–4396. External Links: Link Cited by: §2.2. Zhan et al. (2025) W. Zhan, S. Fujimoto, Z. Zhu, J. D. Lee, D. R. Jiang, and Y. Efroni Exploiting structure in offline multi-agent rl: the benefits of low interaction rank. In International Conference on Learning Representations, Cited by: §1, §1, §2.1, §3. Zhang and Jiang (2021) S. Zhang and N. Jiang Towards hyperparameter-free policy selection for offline reinforcement learning. In Advances in Neural Information Processing Systems, Vol. 34, p. 12864–12875. Cited by: §2.2. Zhang et al. (2023) Y. Zhang, Y. Bai, and N. Jiang Offline learning in Markov games with general function approximation. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 40804–40829. External Links: Link Cited by: §1, §2.3. Zitovsky et al. (2023) J. P. Zitovsky, D. De Marchi, R. Agarwal, and M. R. Kosorok Revisiting Bellman errors for offline model selection. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 43369–43406. Cited by: §2.2. Appendix A Notation and Assumptions Table 3 collects the quantities used in the proofs. The minimal statistical assumptions are: (i) calibration observations are independent conditional on the training split; (i) Yi∈[0,1]Y_i∈[0,1] and [Yi∣A=a]=ui(a)E[Y_i A=a]=u_i(a); (i) fitted predictions are in [0,1][0,1]; (iv) the finite models, candidates, deployments, and targets are measurable functions of training data only; and (v) the logging distribution ν is known for the support check. Realizability is not assumed for the risk or CCE theorem. Table 3. Core notation. Symbol Meaning N,N,A players and finite joint-action set ν known logging distribution u^k u_k rank-k fitted payoff vector σk _k solver-selected CCE of u^k u_k qkq_k (1−α)ν+ασk(1-α)ν+α _k Di,b(q)D_i,b(q) pure replacement of player i by action b T common training-defined target union mk,i,am_k,i,a conditional noisy squared loss at profile a rk,i,tr_k,i,t target-weighted noisy squared risk RkR_k worst player/target risk of rank k [Lk,Uk][L_k,U_k] max-aggregated rank score bounds ω maxk(Uk−Lk) _k(U_k-L_k) EtargetE_ target simultaneous target-interval event Appendix B Proofs for the Confidence Bounds and Selection Guarantee B.1. Proof of Lemma 1 Condition on all training data. This fixes u^k u_k, σk _k, qkq_k, and T. For a joint profile a, the calibration losses Zs=(u^k,i(a)−Ys,i)2∈[0,1]Z_s=( u_k,i(a)-Y_s,i)^2∈[0,1] among observations satisfying As=aA_s=a are independent with mean mk,i,am_k,i,a. Let F=KmaxN||F=K_ N|A|. For the Hoeffding construction and na>0n_a>0, the two-sided inequality gives Pr(|m^k,i,a−mk,i,a|>ρaH∣Dtr,na)≤2e−2na(ρaH)2≤δF. \! (| m_k,i,a-m_k,i,a|>ρ H_a D_ tr,n_a )≤ 2e^-2n_a(ρ H_a)^2≤ δF. If the radius clips at one, or if na=0n_a=0, the clipped interval [0,1][0,1] is valid deterministically. For the empirical-Bernstein construction and na≥2n_a≥ 2, let v^k,i,a v_k,i,a be the unbiased sample variance of these losses. It uses (18) ρk,i,aEB=min1,2v^k,i,alog(4F/δ)na+7log(4F/δ)3(na−1).ρ EB_k,i,a= \! \1, 2 v_k,i,a (4F/δ)n_a+ 7 (4F/δ)3(n_a-1) \. Applying the empirical-Bernstein inequality to both tails gives Pr(|m^k,i,a−mk,i,a|>ρk,i,aEB∣Dtr,na)≤δF, \! (| m_k,i,a-m_k,i,a|>ρ EB_k,i,a D_ tr,n_a )≤ δF, for the radius in Eq. (18). When na<2n_a<2, the construction instead uses [0,1][0,1]. Thus a union bound over all F triples (k,i,a)(k,i,a) shows that either construction covers every profile risk with conditional probability at least 1−δ1-δ. For a target t determined from the training split, rk,i,t=∑a∈t(a)mk,i,a.r_k,i,t= _a t(a)m_k,i,a. The weights are nonnegative and sum to one. Therefore simultaneous profile coverage implies ∑at(a)ℓk,i,a≤rk,i,t≤∑at(a)uk,i,a, _at(a) _k,i,a≤ r_k,i,t≤ _at(a)u_k,i,a, which is exactly the constructed target interval. Averaging the conditional failure probability over training proves the unconditional statement for both profile constructions. Direct IPS-EB. For a supported target t, let wt(a)=t(a)/ν(a)w_t(a)=t(a)/ν(a), Bt=maxa:ν(a)>0wt(a)B_t= _a:ν(a)>0w_t(a), and Xs=wt(As)(u^k,i(As)−Ys,i)2.X_s=w_t(A_s)( u_k,i(A_s)-Y_s,i)^2. Conditional on training, Xs=rk,i,tEX_s=r_k,i,t and Xs∈[0,Bt]X_s∈[0,B_t]. With candidate set K, define FIPS=||N||F_ IPS=|K|N|T|. For calibration size m≥2m≥ 2 and unbiased sample variance v^k,i,tIPS v IPS_k,i,t, IPS-EB uses (19) ρk,i,tIPS=2v^k,i,tIPSlog(4FIPS/δ)m+7Btlog(4FIPS/δ)3(m−1).ρ IPS_k,i,t= 2 v IPS_k,i,t (4F_ IPS/δ)m+ 7B_t (4F_ IPS/δ)3(m-1). Applying the empirical-Bernstein inequality to Xs/BtX_s/B_t and (Bt−Xs)/Bt(B_t-X_s)/B_t, followed by a union bound over (k,i,t)(k,i,t), gives simultaneous two-sided coverage (Maurer and Pontil, 2009). Unsupported targets or m<2m<2 receive [0,1][0,1]; otherwise the interval is [r^k,i,tIPS−ρk,i,tIPS,r^k,i,tIPS+ρk,i,tIPS]∩[0,1]. [ r IPS_k,i,t-ρ IPS_k,i,t,\ r IPS_k,i,t+ρ IPS_k,i,t ]∩[0,1]. Thus IPS-EB also satisfies Eq. (7). Averaging over training completes the proof of Lemma 1. □ B.2. Proof of Theorem 2 On EtargetE_ target, max aggregation preserves every score interval: Lk≤Rk≤UkL_k≤ R_k≤ U_k. Let k∗k^* minimize RkR_k. If Sirv returns, its rule and the definition of ω yield Rk R_ k ≤Uk ≤ U_ k ≤minjUj+τ ≤ _jU_j+τ ≤Uk∗+τ ≤ U_k^*+τ ≤Lk∗+ω+τ ≤ L_k^*+ω+τ ≤Rk∗+ω+τ. ≤ R_k^*+ω+τ. This proves Eq. (11). A return-and-violation can occur only on EtargetcE_ target^c, so its probability is at most δ. □ The exact evaluation oracle used in the experiments is k∗(τ)=mink:Rk≤minjRj+τ.k^*(τ)= \k:R_k≤ _jR_j+τ\. It is an evaluation label, not an input to the theorem or selector. The finite-candidate bound compares the selected risk with the minimum exact risk; accuracy measures whether the selected rank equals this smallest exact target-risk-oracle rank. These are related but distinct evaluations. B.3. Joint and conditional violation probabilities Let B be either violation event. The proof gives ℙ(return∩B)≤δP(return∩ B)≤δ. In contrast, ℙ(B∣return)=ℙ(return∩B)ℙ(return)≤δℙ(return),P(B )= P(return∩ B)P(return)≤ δP(return), when the denominator is positive. Because the precision criterion is calculated from calibration data, return is not independent of interval coverage. Accordingly, the theorem controls the joint event, and empirical system-level denominators retain abstentions. Appendix C Proof of the CCE-Gap Certificate Fix candidate k, player i, and replacement b. Write f=u^k,if= u_k,i, q=qkq=q_k, and d=Di,b(q)d=D_i,b(q). By construction of d, A∼qui(b,A−i)=A∼dui(A),E_A qu_i(b,A_-i)=E_A du_i(A), and the same identity holds for f. Insert and subtract the predicted payoffs: q[ui(b,A−i)−ui(A)] _q[u_i(b,A_-i)-u_i(A)] =q[f(b,A−i)−f(A)]+d[ui−f]−q[ui−f] =E_q[f(b,A_-i)-f(A)]+E_d[u_i-f]-E_q[u_i-f] ≤q[f(b,A−i)−f(A)]+|d[ui−f]|+|q[ui−f]|. _q[f(b,A_-i)-f(A)]+|E_d[u_i-f]|+|E_q[u_i-f]|. Cauchy–Schwarz gives |t[ui−f]|≤t[(ui−f)2]for t∈q,d.|E_t[u_i-f]|≤ E_t[(u_i-f)^2] t∈\q,d\. Conditional unbiasedness supplies the variance decomposition [(f(A)−Yi)2∣A=a]=(f(a)−ui(a))2+Var(Yi∣A=a),E[(f(A)-Y_i)^2 A=a]=(f(a)-u_i(a))^2+Var(Y_i A=a), so the noisy target risk upper-bounds the corresponding squared payoff bias. On EtargetE_ target, |t[ui−f]|≤rk,i,t≤uk,i,t.|E_t[u_i-f]|≤ r_k,i,t≤ u_k,i,t. Maximizing first over (i,b)(i,b) and including the no-deviation option yields Gapu(qk)≤ _u(q_k)≤ Gapu^k(qk)+maxiuk,i,qk _ u_k(q_k)+ _i u_k,i,q_k +maxi,buk,i,Di,b(qk)=Ck. + _i,b u_k,i,D_i,b(q_k)=C_k. All qkq_k and deviations appear in the common target union. The joint probability claim follows exactly as in Theorem 2. □ This result is deliberately candidate-specific. Comparing CkC_k values does not generally order the true gaps because each certificate contains a different predicted gap and may have different slack. Likewise, the target-risk oracle minimizes a maximum squared prediction risk, not Gapu(qk)Gap_u(q_k). Appendix D Proof of Off-Support Non-Identifiability Let H∈0,1H∈\0,1\ index the games in Proposition 1, and let PhP_h be the law of a full logged dataset under game h. Since ν(A1=0)=1ν(A_1=0)=1, both A1A_1 and A1A2A_1A_2 vanish almost surely. Player 1’s conditional mean payoff is therefore 0.40.4 under both games on the support of ν. All other payoffs, action probabilities, and noise laws coincide; hence P0=P1P_0=P_1 for every sample size. In contrast, after replacing player 1’s action by one, θ0=0.50,θ1=0.50+0.2[A2]=0.55. _0=0.50, _1=0.50+0.2E[A_2]=0.55. Let H H be any possibly randomized test based on the log. Because P0=P1P_0=P_1, there is a common value x=P0(H^=1)=P1(H^=1)x=P_0( H=1)=P_1( H=1). Its two error probabilities are x and 1−x1-x, so maxh∈0,1Prh(H^≠h)=maxx,1−x≥12. _h∈\0,1\ _h( H≠ h)= \x,1-x\≥ 12. An independent fair coin attains 1/21/2, proving the minimax equality. Since θ0≠θ1 _0≠ _1, the same argument establishes that this replacement payoff is not point identifiable from the log. Appendix E Algorithm and Computational Cost Algorithm 2 Sirv for finite games 1: training log DtrD_ tr, calibration log DcalD_ cal, known ν, ranks 1:Kmax1:K_ , α,τ,ϵcert,δα,τ, _ cert,δ, confidence procedure ℐI 2: for k=1,…,Kmaxk=1,…,K_ do 3: u^k←FitRank(Dtr,k) u_k← FitRank(D_ tr,k) 4: σk←SolveCCE(u^k) _k← SolveCCE( u_k) 5: qk←(1−α)ν+ασkq_k←(1-α)ν+α _k 6: ←∅T← 7: for j=1,…,Kmaxj=1,…,K_ do 8: ←∪qjT ∪\q_j\ 9: for i∈[N]i∈[N] and b∈ib _i do 10: add Di,b(qj)D_i,b(q_j) to T 11: if ∃t∈,a∈:t(a)>0∃ t ,a :t(a)>0 and ν(a)=0ν(a)=0 then 12: return abstain-unsupported 13: [ℓk,i,t,uk,i,t]k,i,t←ℐ(Dcal,u^k,,δ)\[ _k,i,t,u_k,i,t]\_k,i,t (D_ cal,\ u_k\,T,δ) 14: if maxk,i,t(uk,i,t−ℓk,i,t)/2>ϵcert _k,i,t(u_k,i,t- _k,i,t)/2> _ cert then 15: return abstain-imprecise 16: Lk←maxi,tℓk,i,tL_k← _i,t _k,i,t and Uk←maxi,tuk,i,tU_k← _i,tu_k,i,t for all k 17: return mink:Uk≤minjUj+τ \k:U_k≤ _jU_j+τ\ and its certificate For either profile-based construction, let P=||P=|A| and T=||T=|T|. After model fitting and CCE solving, forming all calibration losses costs O(|Dcal|KmaxN)O(|D_ cal|K_ N) table lookups and arithmetic operations; integrating the endpoints costs O(KmaxNPT)O(K_ NPT). The implementation stores all intervals; memory beyond the fitted models is O(KmaxN(P+T)+PT)O(K_ N(P+T)+PT). In our three-player binary setting P=8P=8, Kmax=3K_ =3, and the implementation has 21 named target slots (at most 21 distinct distributions), so the validation calculation is negligible relative to data generation and model fitting. The procedure requires neither density-ratio estimation nor iterative validation. Appendix F Random-Game Generator and Experimental Grid For every player i and order d, the generator enumerates subsets S⊆[N]S [N] satisfying |S|=d|S|=d and i∈Si∈ S. It draws independent signs si,S∈−1,1s_i,S∈\-1,1\ and magnitudes mi,S∼Unif[0.5,1.5]m_i,S [0.5,1.5], then sets θi,S=Bdsi,Smi,S∑T:|T|=d,i∈Tmi,T. _i,S=B_ds_i,S m_i,S _T:|T|=d,i∈ Tm_i,T. Thus the absolute coefficients at each player’s order sum to BdB_d. Every highest-order coefficient is nonzero, so the generating order is exactly K. We retain every generated game without conditioning on equilibrium properties or evaluation outcomes. Table 4. Experimental designs. “Log.” is the number of logging regimes, “Noise” is the number of observation-noise conditions, and the last column counts configurations except where marked as scoped decisions. Study Generating family Candidates Games Log. n values Noise Rows Factorial K=1;K=2,3,h∈.04,.12K=1;\ K=2,3,\ h∈\.04,.12\ 1,2,3\1,2,3\ 2,048/family 4 3 1 245,760 Misspecified K=3,h=.12K=3,\ h=.12 1,2\1,2\ 2,048 3 3 2 73,728 Congestion affine/quadratic latency 1,2,3\1,2,3\ 256/variant 3 2 1 6,144 Scaling normalized congestion, N∈3,5,8N∈\3,5,8\ 1,2,3\1,2,3\ 64/stratum 3 3 1 6,912 Target scope scaling games at N=5N=5 1,2,3\1,2,3\ 128 3 1 1 3,072 decisions Every cell contains two repetitions. The factorial study has balanced, moderate, thin, and unsupported logging. The misspecified study omits unsupported logging and crosses the three supported regimes with homoscedastic and heterogeneous noise. It therefore contains 2,048×3×3×2×2=73,7282,048× 3× 3× 2× 2=73,728 rows, with 2,048 independent games in each noise condition. These are the same 2,048 rank-3, h=.12h=.12 games as in the factorial grid, perturbed by candidate-rank restriction and noise condition; the study is paired rather than an independent holdout. Under heterogeneous noise, the half-width table is drawn once per game and shared across logging regimes, sample sizes, and repetitions. Deterministic arithmetic seeds preserve pairing across conditions. For game index g, let b=⌊g/64⌋b= g/64 , r=gmod64r=g 64, and o=10,000,000bo=10,000,000b. Then sgame s_ game =30,000+1,000K+r+o, =30,000+1,000K+r+o, slog s_ log =60,000+10,000K+100r+regime_id+o, =60,000+10,000K+100r+regime\_id+o, sdata s_ data =1,000,000+100,000K+1,000r+o =1,000,000+100,000K+1,000r+o +100regime_id+10nid+repetition, +100\,regime\_id+10\,n_ id+repetition, The heterogeneous half-width seed is 4,000,000+r+o4,000,000+r+o. The data seed excludes h, preserving paired actions, observation noise, and splits across signal levels. The bootstrap seed is 202,703. Fitting and CCE solver. Each rank uses all Boolean monomials up to that rank, ridge 10−810^-8, and post-fit clipping to [0,1][0,1]. The CCE linear program maximizes predicted mean welfare subject to six pure-replacement incentive constraints and the simplex constraints. We first use HiGHS with its default settings. If it reports failure or its solution does not pass the 10−810^-8 predicted-CCE-gap check, we retry the identical linear program with presolve disabled and primal/dual feasibility tolerances 10−910^-9. Every accepted solution passes the same 10−810^-8 check. Solver outputs with absolute mass below 10−1210^-12 are set to zero and renormalized. Rank-1 controls can admit multiple welfare optima, so we treat all outputs as solver-selected rather than unique CCEs. Appendix G Congestion-Game Validation We test dependence on the polynomial coefficient generator using weighted atomic singleton congestion games, a standard resource-allocation family (Harks and Klimm, 2012). Each of three players chooses one of two resources. Player weights are drawn independently from Unif[.8,1.2]Unif[.8,1.2] and resource load is xr(a)=∑jwjaj=rx_r(a)= _jw_j1\a_j=r\. For each resource, ℓr(x)=br+srx+crx2,ui(a)=.90−.80wiℓai(xai(a)), _r(x)=b_r+s_rx+c_rx^2, u_i(a)=.90-.80w_i _a_i(x_a_i(a)), where br∼Unif[.05,.12]b_r [.05,.12] and sr∼Unif[.04,.08]s_r [.04,.08]. The affine variant fixes cr=0c_r=0; the quadratic variant draws cr∼Unif[.006,.014]c_r [.006,.014]. These ranges keep normalized payoffs away from clipping while producing nondegenerate load effects over all feasible resource loads; they are not a canonical benchmark distribution. All 512 payoff tables lie in [.25,.90][.25,.90]. Direct multilinear expansion of each table verifies degree 2 for every affine game and degree 3 for every quadratic game; these labels are computed from the tables rather than assigned from the generator. No game is filtered by its equilibrium or evaluation outcome. Moreover, mean welfare is .90−(.80/3).90-(.80/3) times total weighted latency, so maximizing it is equivalent to the standard congestion-efficiency objective. For each variant we draw 256 independent games and apply the unchanged seven selectors, candidate ranks 1,2,3\1,2,3\, split, thresholds, and noise model. Balanced, moderate, and thin logging are crossed with n∈80,000,320,000n∈\80,000,320,000\ and two repetitions, yielding 6,144 evaluation runs. Every randomized component uses a deterministic namespace disjoint from the factorial experiments. The inferential unit remains the game; paired effects are first averaged across its 12 conditions and then bootstrapped over 512 games. Figure 5. Validation on 512 weighted singleton congestion games. Panels (a–b) show ID-Mean minus SIRV-EB regret under ID fallback, so positive values favor SIRV-EB; all 256 paired game effects per latency family are shown; diamonds are means, vertical ticks are medians, thick segments are IQRs, and thin segments span the 10th–90th percentiles. Panel (c) reports return rates over all 6,144 runs. Panel (d) gives the fraction of evaluation runs that both return and meet each CCE-certificate threshold.Two distribution panels show predominantly positive CCE- and welfare-regret effects for affine and quadratic congestion games. A return heatmap is nearly full except under thin logging at 80 thousand samples. Certificate-utility curves show empirical-Bernstein methods certifying more rows at strict thresholds than the Hoeffding control. Across both variants, SIRV-EB fallback reduced mean CCE regret by 0.01317 (95% paired-bootstrap interval [0.01211,0.01425][0.01211,0.01425]) relative to ID-Mean. The game-level effect was positive for 93.55% of games, tied for 6.25%, and negative for 0.20%. The mean welfare-regret effect was 0.01608 ([0.01514,0.01702][0.01514,0.01702]), with 94.53% positive, 4.69% tied, and 0.78% negative game means. Affine and quadratic CCE effects were 0.01417 and 0.01216, respectively, so the combined result is not driven by one latency family (Figure 5a–b). Table 5. All selectors on the congestion panel. Regrets are game-macro means under ID fallback; lower is better. Method Return (%) CCE regret Welfare regret ID-Mean 100.00 .01539 .01887 ID-Max 100.00 .01433 .01785 Target-Point 100.00 .00165 .00198 Target-IPS 100.00 .00165 .00197 IPS-EB 97.27 .00230 .00290 SIRV-H 99.85 .00181 .00225 SIRV-EB 97.97 .00223 .00279 The point selectors attain the lowest average regrets in this congestion study; the interval methods add simultaneous certificates and explicit abstention, not strategic dominance. SIRV-EB returned on 6,019/6,144 rows (97.97%), compared with 6,135 (99.85%) for SIRV-H and 5,976 (97.27%) for IPS-EB. All three confidence methods returned in all balanced, moderate, and 320k cells; at 80k under thin logging, the aggregate rates were 99.1%, 87.8%, and 83.6%, respectively (Figure 5c). On 6,019 common SIRV-H/SIRV-EB returns, the median CCE certificate fell from 0.34412 to 0.14063, a 59.1% reduction. Among all evaluation runs, SIRV-EB both returned and certified thresholds 0.1, 0.2, 0.3, and 0.5 in 25.13%, 73.16%, 86.31%, and 93.18% of cases (Figure 5d). No covered return violated its target-risk budget or CCE certificate. The congestion family remains synthetic, but its congestion construction is independent of Eq. (15) and therefore tests whether positive average strategic effects and certificate behavior transfer beyond that coefficient generator. It does not test broad model-class misspecification. Appendix H Scaling and Target-Set Analysis H.1. Variable-size congestion design We next vary the number of players while preserving the finite binary-action setting of the theory. For N∈3,5,8N∈\3,5,8\, define normalized load x~r(a)=∑jwjaj=r/∑jwj x_r(a)= _jw_j1\a_j=r\/ _jw_j and ℓr(x~)=br+srx~+crx~2,ui(a)=.90−.80wiℓai(x~ai(a)). _r( x)=b_r+s_r x+c_r x^2, u_i(a)=.90-.80w_i _a_i( x_a_i(a)). Weights and intercepts use the ranges in Appendix G; here sr∼Unif[.16,.30]s_r [.16,.30]. Affine games set cr=0c_r=0, and quadratic games draw cr∼Unif[.08,.16]c_r [.08,.16]. Normalizing the load keeps every enumerated payoff in [0,1][0,1] as N changes. Direct multilinear expansion verifies degree 2 and 3, respectively, for every table. Each of the six N–latency strata contains 64 independent games, giving 384 games. We use the unchanged candidates, selectors, split, noise, α,τ,ϵcertα,τ, _ cert, and δ. Balanced, moderate, and thin logging are crossed with n∈80,000,320,000,1,280,000n∈\80,000,320,000,1,280,000\ and two repetitions, for 6,912 experimental configurations. Conditions are averaged within game before inference. Figure 6. Variable-size congestion analysis. Panels (a–b) report selective return and the fraction of configurations that both return and have a CCE certificate at most .30. In panel (a), points average the six latency-family–logging cells and bands span their descriptive 10th–90th percentiles. Panel (b) first combines latency families, then summarizes the three logging regimes in the same way. Panel (c) reports equal-game mean ID-Mean-minus-method effects, so positive favors the named method. Panel (d) profiles one fixed balanced case per N–latency–sample combination in a separate single-threaded process; color encodes sample size, marker encodes latency family, and area encodes peak resident memory. Time covers the complete shared candidate-fitting, selection, and certification computation rather than one selector alone.Two line panels show return and certificate utilization as logged sample size increases for three, five, and eight agents. A heatmap reports CCE- and welfare-regret effects for three methods. A log-scale scatter plot relates end-to-end computation time to the number of joint profiles and sample size, with marker area representing peak memory. The resource measurements isolate one process per case and are not inferential replicates. Each timed call computes all seven selectors from one shared fit and candidate set; it is not a per-selector SIRV-EB runtime. Table 6 reports the larger of the affine and quadratic measurements at n=1.28n=1.28 million. All 18 resource measurements returned a SIRV-EB choice. Enumeration remained practical at N=8N=8 in this measured setting, but the joint-profile count is exponential in N and the measurements do not establish polynomial scalability. Table 6. Structure and measured resources at n=1.28n=1.28 million. Features count all Boolean monomials through rank 3; targets count the common union for three candidates. RSS and end-to-end computation time are maxima over the two latency families. N Profiles Payoff entries Features Targets RSS / shared time 3 8 24 8 21 582 MiB / .73 s 5 32 160 26 33 943 MiB / 1.14 s 8 256 2,048 93 51 1,567 MiB / 3.38 s Across the 2,304 configurations and 128 games at each N, SIRV-EB return fell from 98.35% at N=3N=3 to 73.70% at N=5N=5 and 45.66% at N=8N=8. The fractions that both returned and had a CCE certificate at most .30 were 90.45%, 56.90%, and 14.84%, respectively. Mean ID-Mean-minus-SIRV-EB CCE-regret effects remained positive: .01386 [.01171,.01608][.01171,.01608], .01672 [.01374,.01990][.01374,.01990], and .01802 [.01553,.02053][.01553,.02053]. Thus strategic mean effects did not disappear on this grid, but selective certificate utility deteriorated as the enumerated game and target sets grew (Figure 6). Table 7. Absolute scale-panel outcomes after averaging repeated conditions within each of 128 games per N. Regrets use ID fallback and lower is better. Certificate medians condition on return; utilization keeps all 2,304 configurations per N in the denominator. N Method Return (%) CCE regret Welfare regret Median cert. Cert. ≤.30≤.30 (%) 3 ID-Mean 100.00 .0151 .0184 – – 3 Target-Point 100.00 .0004 .0004 – – 3 SIRV-EB 98.35 .0012 .0013 .1206 90.45 3 IPS-EB 97.53 .0014 .0016 .1063 90.28 5 ID-Mean 100.00 .0305 .0250 – – 5 Target-Point 100.00 .0002 <.0001<.0001 – – 5 SIRV-EB 73.70 .0137 .0125 .1730 56.90 5 IPS-EB 73.65 .0138 .0126 .1404 62.85 8 ID-Mean 100.00 .0480 .0328 – – 8 Target-Point 100.00 .0002 <.0001<.0001 – – 8 SIRV-EB 45.66 .0300 .0216 .4523 14.84 8 IPS-EB 48.74 .0269 .0196 .3022 22.53 Table 8. Smallest tested n at which SIRV-EB return is at least .90 and its median returned CCE certificate is at most .30. “Not met” means the joint criterion failed at every tested n through 1.28 million. N Balanced Moderate Thin 3 80k 80k 320k 5 80k 320k Not met 8 1.28m Not met Not met Table 8 is a descriptive diagnostic over three tested sample sizes, not a sample-complexity estimate or an extrapolation beyond the grid. Target-Point always returned and had the lowest absolute regret in this family; the interval methods add simultaneous guarantees and abstention, not strategic dominance (Table 7). H.2. Target scope and heterogeneous-noise ordering The target-set ablation reuses the same fitted candidates, splits, and observations for four decisions on the 128 independent five-agent games at n=320,000n=320,000. The original common+deviation design compares every candidate on the union of all deployments and unilateral replacements. Local+deviation evaluates each candidate only on its own deployment and replacements, making support and precision eligibility candidate-local. The two deployment-only variants omit all replacement targets. Thus local designs change the comparator, while deployment-only designs cannot produce the CCE certificate in Theorem 4. A three-facet contrast forest reports local-minus-common changes in return rate and CCE-certificate magnitude for affine and quadratic games under balanced, moderate, and thin logging. A heatmap reports three external regrets for the four target designs. A second heatmap shows concordant, discordant, and tied ordering fractions under homoscedastic and heterogeneous noise. Figure 7. Target-set and noise-ordering analysis. Panel (a) gives paired local-minus-common effects in six prespecified 128-configuration cells. Horizontal segments begin at zero; circles denote affine games, diamonds denote quadratic games, and row color denotes logging regime. The first two facets show the full-target return-rate gain and reduction in the median returned CCE certificate; the third shows the deployment-only return-rate gain, for which no deviation certificate is available. Positive values favor the local design on the displayed quantity. Panel (b) evaluates all four designs using full-common exact risk and true-payoff regrets under ID fallback; lower is better. Panel (c) gives pairwise ordering composition among noisy target risk, noise-free payoff bias, and true CCE gap over 2,048 games per noise condition.A three-facet contrast forest reports local-minus-common changes in return rate and CCE-certificate magnitude for affine and quadratic games under balanced, moderate, and thin logging. A heatmap reports three external regrets for the four target designs. A second heatmap shows concordant, discordant, and tied ordering fractions under homoscedastic and heterogeneous noise. Common+deviation returned on 71.48% of the 768 configurations. Making the full target set candidate-local raised return to 88.54%; its median returned CCE certificate was .16662 versus .16018 for the common design. Common and local deployment-only return rates were 82.55% and 98.83%, respectively, but those decisions retain only the deployment-target risk bound and do not certify deviation incentives. All three logging regimes have positive support, so the return differences in this panel arise from precision scope, not recovered support. Descriptively, each local design also had lower mean full-common risk, CCE, and welfare regret than its corresponding common design (Figure 7b). This is a performance– comparability tradeoff, not dominance over the common construction: the local rule no longer asks every candidate to meet one shared target criterion. Among simulated rows on the scoped simultaneous interval event, no returned decision violated its scoped risk bound or candidate CCE certificate. Finally, we quantify how heterogeneous observation variance changes the two-candidate ordering in the rank-misspecified study. Deltas are computed for rank 2 minus rank 1 after averaging the 18 experimental configurations (three logging regimes, three sample sizes, and two repetitions) within each game and noise condition. Noisy target risk and noise-free squared payoff bias agreed on all 2,048 homoscedastic games and on 2,042/2,048 heterogeneous games (99.71%); the paired change was −0.29-0.29 percentage points (95% game-bootstrap interval [−0.54,−0.10][-0.54,-0.10]). In contrast, among games non-tied on both quantities, strict risk–CCE ordering agreement was 1,085/1,888 (57.47%) and 1,101/1,889 (58.28%), respectively; about 7.8% of all comparisons were tied in at least one CCE-related quantity. Heteroscedasticity therefore rarely changed the target-risk versus bias ordering in this perturbation, but neither ordering was a reliable surrogate for the strategic CCE ordering in this study. Appendix I Additional Experimental Results I.1. Selector definitions and denominators For a selective method, “conditional” quantities average only its returned rows. “ID fallback” replaces an abstention with the ID-Mean selected rank and therefore retains all supported rows. The main external comparisons use ID fallback; conditional means are not compared across methods because their returned subsets differ. Point comparators return on every row except Target-IPS, which returns on all supported rows and refuses all unsupported rows. The support rule is thus not shared by all seven methods. I.2. Target-risk alignment Figure 8. Target-risk-oracle accuracy on common supported returns. Rows share 2,048 games; marginals show the 10th–90th percentiles, IQR, median, and mean. This measures RkR_k-order recovery, not strategic value.Two seven-by-2,048 heat strips compare ID-Mean, ID-Max, Target-Point, Target-IPS, IPS-EB, SIRV-H, and SIRV-EB on exact target-risk-oracle accuracy for generating ranks two and three. Marginal interval plots summarize variation across games. Target-aware rows are generally more accurate than in-distribution rows. At τ=0.002τ=0.002, Target-Point had game-macro accuracy 0.9989 and 0.9998 for generating ranks 2 and 3, respectively, on the common returned set. Target-IPS had accuracy 0.9978 and 0.9992, while SIRV-EB had 0.9745 and 0.9958. These values show that the estimators track their declared target-risk criterion. They cannot establish a reduction in true CCE or welfare regret, which is why Figures 2–3 use the payoff-table outcomes instead. Two panels show target-risk-oracle accuracy versus adequacy tolerance for generating ranks two and three. Four validators have point estimates and 10th-to-90th-percentile bands; a vertical line marks tau equal to .002. Figure 9. Target-risk-oracle accuracy across τ∈0,.0005,.001,.002,.004τ∈\0,.0005,.001,.002,.004\ on common supported returns. Points are equal-game means and bands show the descriptive 10th–90th percentile range across 2,048 games. The vertical marker denotes the main value τ=.002τ=.002. Accuracy is not monotone in τ because the smallest adequate oracle rank changes with the tolerance.Two panels show target-risk-oracle accuracy versus adequacy tolerance for generating ranks two and three. Four validators have point estimates and 10th-to-90th-percentile bands; a vertical line marks tau equal to .002. I.3. Selective return and certificate thresholds For SIRV-EB, balanced and moderate logging returned in every factorial cell. Thin-logging return rose from 40.94% at n=20,000n=20,000 to 84.27% at n=80,000n=80,000 and 100% at n=320,000n=320,000. All 61,440 unsupported rows were refused. SIRV-H and IPS-EB also refused every unsupported row; their supported return rates were 93.05% and 90.39%. Here BR=τ+ωB_R=τ+ω for the profile-based confidence procedures and the corresponding simultaneous risk budget for IPS-EB. Among returned rows, the 10th–90th percentiles of Ck^C_ k were [.31872,.68205][.31872,.68205] for SIRV-H, [.14683,.50407][.14683,.50407] for SIRV-EB, and [.13666,.47127][.13666,.47127] for IPS-EB. The 90th percentiles of realized risk excess divided by its budget were .0388, .1612, and .1892, respectively; all three medians were zero. Tighter budgets therefore improve utilization but need not reduce the realized-to- allowed ratio. No covered return in either experimental grid exceeded its target-risk budget or CCE certificate. This is a numerical validation over the simulated rows, not an estimate of zero population failure probability. In particular, no confidence procedure certified Ck^≤.05C_ k≤.05 in the factorial study. The joint-probability theorems and the empirical threshold utilization answer different questions. I.4. External effects and selection stability Table 9. Mean ID-fallback effect relative to ID-Mean, with 95% paired base-game bootstrap intervals in brackets. Positive values indicate lower regret. All generating-rank-2 entries are exact zero; misspecified columns use heterogeneous noise and define regret relative to the better candidate in 1,2\1,2\, not to the excluded rank-3 deployment. Method Rank-2 CCE/W Rank-3 CCE Rank-3 welfare Misspecified CCE Misspecified welfare ID-Max .00000/.00000 .00042 [.00026,.00058] .00042 [.00029,.00055] .000038 [-.000004,.000117] .000027 [-.000005,.000085] Target-Point .00000/.00000 .00993 [.00931,.01054] .00635 [.00588,.00684] .01741 [.01569,.01915] .00449 [.00339,.00561] Target-IPS .00000/.00000 .00993 [.00931,.01054] .00635 [.00588,.00684] .01746 [.01576,.01917] .00458 [.00349,.00569] IPS-EB .00000/.00000 .00380 [.00357,.00403] .00244 [.00224,.00265] .01246 [.01145,.01351] .00370 [.00301,.00439] SIRV-H .00000/.00000 .00538 [.00505,.00571] .00346 [.00320,.00373] .01395 [.01277,.01516] .00408 [.00328,.00486] SIRV-EB .00000/.00000 .00518 [.00486,.00550] .00328 [.00303,.00355] .01362 [.01248,.01479] .00397 [.00321,.00474] The positive rank-3 and misspecified-study means are not pointwise dominance statements. Under heterogeneous noise, for example, SIRV-EB’s game effects on CCE regret were 49.2% positive, 25.0% tied, and 25.9% negative; its welfare effects were 47.1% positive, 20.8% tied, and 32.1% negative. The SIRV-EB mean welfare interval in Table 9 is positive despite this negative game-level tail. The point selectors have larger mean CCE effects than the selective methods in this family, while the interval methods add simultaneous bounds and explicit refusal. Appendix J Evaluation and Clustered Inference Exact payoff tables generate the synthetic rewards but are unavailable to all seven selectors. They enter only evaluation quantities: exact target risks, target-oracle labels, true CCE gaps, and true welfare. The external analyses include abstentions through ID fallback and retain exact ties and negative effects. Repetitions, sample sizes, signal levels, and logging regimes are repeated conditions within a base game rather than additional independent games. In the factorial and misspecified studies, paired ID-Mean-minus-method effects are averaged within game and the 2,048 equally weighted game effects are resampled within each reported family or noise condition. The congestion validation applies the same procedure to 512 games after averaging its 12 conditions per game. The scaling analysis first averages 18 conditions per game, then resamples 64 games for a latency-family result or 128 games for a result combined across both latency families at a fixed N. Every reported bootstrap interval uses 5,000 resamples with seed 202,703. Appendix K Reproducibility Details All simulations use deterministic pseudorandom seeds. The main studies comprise 10,240 payoff tables, 24,576 logging distributions, 245,760 factorial configurations, and 73,728 misspecified configurations. The congestion validation adds 512 payoff tables, 1,536 game–regime assignments, and 6,144 configurations. The scaling study adds 384 payoff tables, 1,152 game–regime assignments, and 6,912 configurations. Its target-set ablation re-evaluates 768 of those configurations under four target scopes, yielding 3,072 decisions, and its resource panel comprises 18 isolated process measurements. The noise-ordering analysis is derived from the existing misspecified configurations and introduces no additional simulated rows. Statistical analyses treat the base game as the inferential unit. Experiments were run with Python 3.13.1, NumPy 1.26.4, pandas 2.2.3, and SciPy 1.15.2. The isolated resource measurements used one process and one numerical-library thread. Appendix L Scope and Limitations The theory assumes a finite action table and known logging distribution; estimated propensities, continuous actions, and sequential games require new error control. Global-union support and precision abstention are conservative and may reject a useful supported-subset answer; that restriction changes the target risk and oracle. Conversely, positive support may be statistically negligible, motivating a separate precision check. Because the target risk in Eq. (6) uses noisy squared loss, it bounds squared mean-payoff error but also contains conditional reward variance. Heterogeneous noise can therefore alter the target-risk oracle. The robustness study examines one profile-specific variance pattern, not a general noise-shift benchmark. The finite-profile construction enumerates ||=2N|A|=2^N profiles in the binary-action panels. The measurements through N=8N=8 therefore do not establish scalability to large joint-action spaces. Our evaluation remains synthetic rather than a benchmark of real-world strategic systems. The factorial family contains three binary-action players, linear monomial payoff classes aligned with the fitted hierarchy, bounded uniform noise, and predicted CCE candidates chosen for welfare. Its 245,760 rows provide broad paired coverage, not evidence across 245,760 independent environments; there are 2,048 independent base games per generating order. The misspecified study reuses the rank-3, h=.12h=.12 games as a paired perturbation, and its candidate regrets compare ranks 1,2\1,2\ only. The separately generated congestion games reduce dependence on the monomial coefficient generator. The scaling panel varies the number of players through N=8N=8, but every game still has two actions per player and retains the same observation model and candidate solver. We use base games as inference units throughout. Variance-adaptive bounds tighten certificates, but the point selectors have larger mean CCE-regret reductions in the studied rank-3 conditions. The interval methods instead provide simultaneous bounds and abstention. Heterogeneous-noise outcomes retain a negative game-level tail, and few SIRV-EB returns meet joint risk-budget .05 and CCE .2 thresholds. Real logged strategic interactions are needed to assess external generality.