NeurIPS2026 (task-queue label; the cached paper does not establish acceptance) Learning Theory Reinforcement Learning best-action identification two-fidelity evaluation minimax trees fixed confidence budget allocation

Two-Fidelity Best-Action Identification for Stochastic Minimax Tree¶

Conference: NeurIPS2026 (task-queue label; the cached paper does not establish acceptance)
arXiv: 2606.01708
Code: https://github.com/PeterLauLukChen/2FFS
Area: Learning Theory / Reinforcement Learning
Keywords: best-action identification, two-fidelity evaluation, minimax trees, fixed confidence, budget allocation

TL;DR¶

Under a known fast-evaluation bias envelope and slow evaluations unbiased for true node minimax values, 2FFS uses endpoint certificates and recursive budgets to choose adaptively between expansion and sampling, achieving high synthetic-tree accuracy with substantially fewer node visits, while stopping and cost guarantees require additional regularity conditions.

Background & Motivation¶

In an alternating Max/Min adversarial search tree, the quality of a root action depends on optimal responses by both players, not merely the return of one random trajectory. Conventional minimax search expands deeply using cheap heuristic evaluations; MCTS and BAI-MCTS instead control uncertainty through repeated stochastic sampling. Expansion is fast, but propagating biased point estimates through extrema can mis-rank actions. Sampling offers statistical evidence, yet may spend substantial resources on expensive leaf evaluations.

Multi-fidelity bandits already study allocation between cheap biased and expensive accurate evaluations, but a flat collection of arms lacks alternating minimax propagation. Whether a child's uncertainty matters depends both on its role at the parent and on whether it can change the root comparison. The paper does not train a better critic: given two oracles, it asks whether a decision-critical node should be expanded further or evaluated more reliably in place.

Both routes remain available: an expanded node can still receive slow samples, and expansion does not discard previously collected local evidence. Core idea: use valid confidence intervals to certify recommendations, then concentrate computation on branches that can still change the root decision through scale-capped endpoint certificates and recursive budgets, falling back to local slow sampling when expansion is not worthwhile.

Method¶

Overall Architecture¶

Inputs are a finite minimax tree with a common terminal depth, two node-evaluation oracles, a known fast-oracle bias envelope, a node-wise confidence allocation, and a target error tolerance. The root is Max, with alternating Max/Min internal nodes. The output is a root action certified by interval separation, rather than an exact value function for the entire tree.

2FFS first evaluates all root children with the fast oracle, maintaining intervals constrained jointly by local evidence and child evidence. Its loop follows “Effective Interval Fusion → Root Endpoint Scheduling → Budgeted Two-Route Resolution” to select the node, endpoint, and precision scale at which evidence should be added. There is no teacher network or gradient training: oracle edges below represent observations during search, not training supervision.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    T["Finite minimax tree"] --> I["Effective Interval Fusion"]
    F["Fast oracle<br/>deterministic value and bias envelope"] -.->|Search observations, not training supervision| I
    S["Slow oracle<br/>stochastic node-value observations"] -.->|Search observations, not training supervision| I
    I --> R["Root Endpoint Scheduling"]
    R -->|Not separated| Q["Budgeted Two-Route Resolution"]
    Q -->|Fast expansion or local slow sampling| I
    R -->|Interval separation| O["Recommend root action"]

Key Designs¶

1. Effective Interval Fusion: constrain node values with both bias bounds and statistical evidence

At any exposed non-root node, the fast oracle returns a deterministic estimate whose error is bounded by a known envelope indexed by remaining depth. The envelope is nondecreasing in remaining depth and satisfies \(B(0)=0\), so exposing a leaf reveals its true mean through the fast evaluation. This is a modeling assumption, not a property that neural heuristics generally provide. The slow oracle can directly query any exposed non-root node; repeated observations are independent and sub-Gaussian, with mean equal to that node's true minimax value. Ordinary policy rollouts generally estimate policy value and cannot simply be treated as this oracle.

Fast and slow intervals are intersected, not averaged. The slow interval is itself the running intersection of time-uniform confidence intervals, so accumulated evidence narrows over time. Allocating \(\delta_v\) to each non-root node, with total allocation at most \(\delta\), allows a union bound over every node and sample count.

\[ I_v(t)=\underbrace{[V_F(v)-B(h(v)),\,V_F(v)+B(h(v))]\cap I_v^S(t)}_{I_v^{\mathrm{loc}}(t)}\cap I_v^{\mathrm{ch}}(t). \]

For child propagation, Max nodes take the maximum of child lower bounds and separately of upper bounds; Min nodes take the respective minima. An unexpanded node has an unbounded child-backup interval. After expansion, local evidence is still intersected with child backups, preserving previous slow samples and allowing direct parent evidence to be tighter than descendant information. Extremal backups preserve validity without accumulating interval-width inflation at each depth.

Appendix B.3 also specifies an immediate return of a predetermined default action if an intersection becomes empty, defining behavior on failure paths. This exit cannot occur on the simultaneous-validity event. It is not a normal optimality certificate; its possible errors are included in the confidence-failure event.

2. Root Endpoint Scheduling: refine only one-sided certificates that can still change the recommendation

The leader is the root action with the largest lower bound; the challenger has the largest upper bound among the other actions. Search stops when some action's lower bound exceeds every competitor's upper bound minus the allowed error:

\[ L_{\hat a_t}(t)\geq\max_{a\neq\hat a_t}U_a(t)-\varepsilon. \]

If separation fails, the algorithm compares the leader's lower-side scale with the challenger's coarsest unresolved side, prioritizing the coarser obligation. The challenger can either be excluded or become the leader, so it cannot always be refined only on its upper side. The precision grid starts from the largest initial root-child interval width and halves at each scale. A one-sided certificate at scale \(\rho_k\) bounds the corresponding endpoint error by \(\rho_k/2\); it need not make the entire interval that narrow.

Within a subtree, two rules apply. The lower side of a Min node and upper side of a Max node are selector cases: resolution follows a child currently determining the backed-up endpoint. The lower side of a Max node and upper side of a Min node are comparison cases: only children still blocking the scale certificate remain active, and the endpoint-most blocker is processed at each step. For a Max lower-side obligation, a child can be discharged if its upper bound is within “largest child lower bound plus \(\rho_k/2\),” or if it has a same-side certificate. The Min upper-side rule is the dual.

A comparison blocker is first refined on the opposite endpoint used for exclusion, then on the same side only after the opposite side is complete within the allowed scales. Child calls cannot use a finer scale than their parent obligation. Completed certificates are latched, and monotonically shrinking intervals preserve their endpoint guarantees. Switching blockers therefore does not cause repeated positive work on the same node-side-scale obligation.

The analysis captures decision relevance through an effective gap. The root starts with the best-versus-second-best action gap; each descendant inherits the maximum of the previous effective gap and the true parent-child value difference. A large gap means coarse estimation suffices for the root decision, rather than requiring precision matched to every node's smallest sibling gap.

\[ \Delta_r^{\mathrm{eff}}=\Delta_*,\qquad \Delta_v^{\mathrm{eff}}=\max\{\Delta_{p(v)}^{\mathrm{eff}},\,|V^*(v)-V^*(p(v))|\}. \]

True gaps are analysis-only quantities, not known to the algorithm. The appendix proves that active calls satisfy \(\Delta_v^{\mathrm{eff}}\leq2\rho_k\), with the constant 2 independent of depth. Capped descent prevents children from being pushed into irrelevant precision finer than the current parent task.

3. Budgeted Two-Route Resolution: retain local certification and limit wasted recursive exploration

At a node and scale, the resolver first attempts the recursive route. An unexpanded node exposes and fast-evaluates all children; an expanded node resolves one live child using the preceding rules. It neither estimates every child exactly nor permanently abandons local sampling after expansion. Direct slow sampling remains available when further recursion becomes too expensive.

Let \(\Gamma_v(\rho,\delta_v)\) be the local certification cost after the node is exposed. If \(B(h(v))\leq\rho/4\), the fast interval is already narrow enough and this cost is zero. Otherwise, it is \(c\) times the first slow sample count at which the confidence radius reaches \(\rho/4\). A fast query costs 1 and a slow query costs \(c\geq1\). Recursive spending at a node-scale obligation is capped by

\[ \mathsf B_{v,k}^{\mathrm{rec}}=\alpha_{h(v)}\Gamma_v(\rho_k,\delta_v),\qquad \alpha_h=(h+1)^2. \]

When the node's own recursive budget cannot afford expansion or further progress, resolution falls back to one local slow query. When only the invocation cap inherited from an ancestor is insufficient, it returns blocked instead of switching to a child-local action that would exceed the ancestor's budget. Each invocation performs at most one positive-cost oracle action, followed by interval, endpoint, and certificate updates before reselection. These distinctions are essential to the appendix's cost accounting.

The theoretical reference \(J_v^*\) chooses the cheaper of two costs at each internal node: local certification at its true effective gap, or the cost of exposing every child plus their reference costs. Root complexity \(H(\boldsymbol\delta)\) adds root-child initialization to all \(J_a^*\); \(H^*\) is its infimum over feasible confidence allocations. These are analysis references with perfect gap information, not information-theoretic lower bounds or budgets the algorithm can directly read.

The cost theorem additionally requires dyadic local-cost prefix sums to be bounded by the last scale's cost, and halving an effective gap not to cause an unbounded multiplicative cost jump. On the simultaneous-validity event, with a unique optimal root action and these regularity conditions, exact identification stops finitely and its weighted oracle cost satisfies

\[ C_\tau=N^F(\tau)+c\sum_vN_v^S(\tau) \leq P_DH(\boldsymbol\delta),\qquad P_D=O_{\Lambda_{\mathrm{pre}},\Lambda_{\mathrm{gap}}}(D^2). \]

The polynomial quantity is the depth overhead relative to reference complexity. \(H\) still depends on tree size and gaps; total search cost does not automatically become polynomial for an exponentially large tree. An \(H^*\)-order statement also requires uniform regularity constants along near-optimal confidence allocations, rather than claiming every practical allocation attains that bound.

A Worked Example¶

The following numbers are an illustrative example, not an experimental trajectory from the paper. Consider a depth-3 tree whose root has two Min actions A and B, with true values 0.65 and 0.50. Initial fast intervals are \([0.45,0.85]\) for A and \([0.40,0.80]\) for B. A is the leader, but its lower bound 0.45 does not beat B's upper bound 0.80.

Suppose A's lower side is selected and its recursive budget can expose two Max children. Their true values are 0.65 and 0.80, with fast intervals \([0.55,0.75]\) and \([0.70,0.90]\). The Min backup narrows A to \([0.55,0.75]\). Its lower-side selector focuses on the child with lower bound 0.55 rather than blindly continuing to certify the second child.

B's interval remains coarser. Suppose B has many children, whose combined exposure cost exceeds B's own remaining recursive budget at the current scale. The resolver purchases local slow samples at B instead. After several queries, suppose the running slow interval becomes \([0.48,0.52]\); intersecting it with the fast interval lowers B's upper bound to 0.52. No sample count is specified because it depends on noise, confidence allocation, and observed samples.

The root now has \(0.55\geq0.52\) and recommends A with \(\varepsilon=0\). Neither A's value nor all B descendants have been evaluated exactly. “Exact identification” concerns the selected action, not every node value. If B were blocked only by an inherited invocation cap, it should return blocked upward rather than use the own-budget fallback illustrated here.

Loss & Training¶

There is no trainable model, optimization loss, or policy-gradient experiment. The method concerns confidence and budget allocation during search. Confidence radii must be time-uniform, nonincreasing with sample count, and converge to zero; an ordinary interval valid only at one fixed sample count is insufficient for adaptive stopping.

Theorem 3.1 bounds the unconditional probability of “finite stopping and returning an action with error exceeding \(\varepsilon\)” by \(\delta\). It alone does not guarantee stopping, nor does it imply that error probability conditional on stopping is at most \(\delta\). Finite stopping and cost belong to the additional conditions of Theorem 3.6.

For biased slow oracles, the theoretical extension uses a known pointwise bias bound \(\xi\) to inflate the radius to \(\beta_v+\xi\). Minimax propagation does not require adding another \(\xi\) per depth, but the radius need not vanish, so the original stopping and cost proofs do not carry over. A proxy fast envelope must dominate the true envelope at every depth; a depth-dependent formula alone does not establish calibration. Under the same query history, a looser envelope only widens intervals, but actual adaptive runs may follow different paths, so their realized costs cannot be ordered from that observation.

Key Experimental Results¶

Main Results¶

Each setting uses 100 independently generated balanced synthetic stochastic minimax trees. The slow oracle adds noise to true minimax values, directly instantiating the theoretical oracle rather than testing its availability through real-game rollouts. The following results are from Table 1 and report mean ± standard deviation for counts.

Depth D / Branching b / Total Nodes	Method	Stopping Rate	Accuracy	Sampling / Visit Count	Operation Count
5 / 8 / 37,449	2FFS	1.00	1.00	\(5.39\times10^3\pm1.27\times10^3\)	\(8.38\times10^7\pm4.05\times10^7\)
5 / 8 / 37,449	BAI-MCTS	1.00	0.99	\(8.80\times10^5\pm3.39\times10^5\)	\(2.38\times10^8\pm9.49\times10^7\)
7 / 6 / 335,923	2FFS	1.00	1.00	\(1.77\times10^4\pm2.64\times10^3\)	\(1.06\times10^9\pm3.02\times10^8\)
7 / 6 / 335,923	BAI-MCTS	0.98	0.98	\(1.75\times10^7\pm6.71\times10^6\)	\(4.85\times10^9\pm1.87\times10^9\)
10 / 3 / 88,573	2FFS	1.00	1.00	\(1.31\times10^4\pm2.34\times10^3\)	\(2.49\times10^9\pm8.64\times10^8\)
10 / 3 / 88,573	BAI-MCTS	0.98	0.98	\(1.91\times10^7\pm4.19\times10^6\)	\(4.62\times10^9\pm9.34\times10^8\)

Sampling count measures total sampling and node visits, not distinct nodes or the theoretically \(c\)-weighted cost \(C_\tau\). Operation count treats one constant-time scalar state access, update, or comparison as one unit, covering interval and certificate bookkeeping rather than measured wall-clock time.

Ablation Study¶

The controlled baselines in the same Table 1 either remove slow certification or commit to a fixed expansion depth before sampling only at the frontier. These assess the need for adaptive two-route selection, not removal of modules from a trained network.

Depth D / Branching b	Config	Stopping Rate	Accuracy	Sampling / Visit Count	Operation Count
5 / 8	Minimax-fast	1.00	0.91	\(1.49\times10^4\pm3.35\times10^3\)	\(8.20\times10^5\pm1.91\times10^5\)
5 / 8	Slow-only	0.47	0.47	\(5.87\times10^5\pm4.86\times10^5\)	\(8.62\times10^7\pm7.15\times10^7\)
7 / 6	Minimax-fast	1.00	0.88	\(5.52\times10^4\pm7.08\times10^3\)	\(3.48\times10^6\pm4.59\times10^5\)
7 / 6	Slow-only	0.73	0.70	\(4.22\times10^6\pm9.16\times10^6\)	\(1.49\times10^9\pm4.13\times10^8\)
10 / 3	Minimax-fast	1.00	0.90	\(4.69\times10^4\pm5.67\times10^3\)	\(4.56\times10^6\pm5.81\times10^5\)
10 / 3	Slow-only	0.77	0.77	\(5.60\times10^6\pm8.98\times10^6\)	\(1.63\times10^9\pm4.22\times10^8\)

Figure 2 additionally examines fast-bias and slow-noise sensitivity on depth-5, 8-ary trees. The text gives parameter means of 0.45 and 0.01, respectively, and qualitatively describes stability over moderate ranges. The cache provides no readable pointwise curve values, so sweep endpoints or error bars are not reconstructed.

Key Findings¶

Ratios of the reported means give approximately 163, 989, and 1,458 times fewer samples/visits than BAI-MCTS, and 2.84, 4.58, and 1.86 times fewer operations. The paper summarizes these as approximately 160–1450 and 1.9–4.6 times; these are rounded summaries, not additional experiments.
Fewer samples do not imply proportionate computational savings. Every 2FFS observation also maintains fast–slow intersections, scale certificates, and comparison sets, so visit reductions greatly exceed operation reductions.
Minimax-fast actually has far fewer operations than 2FFS, but accuracy is only 0.88–0.91. The result is not “2FFS computes less than every baseline”; its advantage combines reliability with adaptive efficiency.
Slow-only frequently fails to stop within the finite budget. Stopping and accuracy are reported separately; accuracy 0.70 must not be interpreted as “70% correct among stopped runs.” The text does not fully specify budget thresholds or accuracy-denominator handling.

Highlights & Insights¶

Two-fidelity reasoning is not simply score mixing: it retains two certifiable evidence sources and intersects them. Cheap biased information can still support deterministic exclusion when its bias bound is valid.
One-sided certificates align more closely with the final decision than whole-interval certification. Root selection needs a sufficiently high leader lower bound and resolved competitor information, not uniform precision across the tree.
Local reversibility avoids committing prematurely to expansion. Recursive spending does not prohibit later local certification, while budget competition limits over-exploration of a poor route.
The depth factor follows from scale synchronization and aggregate cost accounting, not from eliminating the expense of tree structure. This reasoning may inform other hierarchical certificate searches, but their own interval propagation must be proved separately.

Limitations & Future Work¶

An unbiased oracle for true minimax values at arbitrary exposed nodes is a strong assumption. Real policy rollouts, neural critics, and LLM scores generally do not satisfy it directly; both bias and evaluation costs need calibration rather than merely relabeling resources as fast and slow.
A known fast envelope with terminal \(B(0)=0\) provides a special informational advantage. Baseline interfaces also differ: BAI-MCTS samples leaves stochastically, whereas 2FFS can query internal nodes directly, so the experiments do not isolate every source of improvement.
Local regularity can fail at the fast-bias cutoff. Appendix B.8 explicitly notes that when \(\Delta_v^{\mathrm{eff}}/8<B(h(v))\leq\Delta_v^{\mathrm{eff}}/4\), local cost is zero at the effective gap but positive at half the gap. Polynomial scaling of slow sample cost alone cannot establish the condition.
The MARL discussion in §3.2 is a theoretical robustness extension for biased oracles and proxy envelopes. Appendix A explicitly places real MARL, policy-gradient, and neural-guided MCTS experiments outside the paper's scope. No real-game, LLM, or MARL experiment supports deployment conclusions.
The paper collectively calls its three comparison schemes fixed-confidence baselines, but fast-only accuracy is below 2FFS and no equivalent PAC certification is demonstrated. The baseline label should not be treated as an equivalent guarantee.
Dynamic trees, progressive widening, online calibration of unknown envelopes, and weaker regularity conditions are possible directions. How calibration failures enter the total failure probability requires separate analysis rather than direct reuse of these theorems.

vs BAI-MCTS (Kaufmann & Koolen, 2017): Both study fixed-confidence identification of minimax root actions. This paper adds deterministic biased fast evaluations and local slow certification at any exposed node, enabling competition between expansion and sampling at the cost of stronger oracle assumptions and more bookkeeping.
vs multi-fidelity best-arm identification: Flat bandits choose evaluation fidelity for the same arm. 2FFS can additionally expand a subtree, requiring alternating extrema and ancestor-level decision relevance rather than direct reuse of flat-arm allocation.
vs MFHOO / MFPOO: Their trees hierarchically partition a continuous black-box domain and target simple regret under a budget. Here the tree is the adversarial decision structure itself, and the objective is fixed-confidence root-action certification; both tree semantics and stopping objectives differ.
Research insight: A useful next step is replacing node-wise unbiased oracles with provable policy-evaluation bias bounds and testing how much efficiency remains under identical evaluation interfaces. This is a follow-up question, not an empirical result established here.

Rating¶

Novelty: 4/5 — Introduces two-fidelity allocation into minimax endpoint certification with recursive-budget analysis.
Experimental Thoroughness: 2/5 — Each setting has 100 synthetic trees and controlled ablations, but lacks real-environment and runtime validation.
Writing Quality: 4/5 — The appendix separates correctness, stopping, and complexity carefully; experimental budgets and statistical conventions remain incomplete.
Value: 4/5 — Provides a reusable certificate framework for cost-sensitive tree search, with practical value contingent on available oracles and envelopes.