PaperlayerView exact revision on arXiv

Source-linked AI summary

Two-Fidelity Best-Action Identification for Stochastic Minimax Tree

Peter Chen, Xi Chen

arXiv:2606.01708v1cs.LGcs.AI

TL;DR

The paper addresses fixed-confidence best-action identification in stochastic minimax trees, where search must balance cheap biased evaluations against expensive accurate ones. It introduces 2FFS, which adaptively expands with fast evaluations or locally certifies nodes with slow samples. The method is PAC-correct, stops finitely for exact identification under a local regularity assumption, and achieves a polynomial-depth cost bound while improving sampling and computational efficiency over BAI-MCTS-style baselines.

  • Problem

    Fixed-confidence best-action identification requires allocating limited computation between cheap biased information and expensive accurate information in stochastic minimax trees.

  • Method

    2FFS adaptively chooses between recursive fast-oracle expansion and local slow-oracle certification at decision-critical tree nodes.

  • Results

    2FFS provides (ε, δ)-PAC correctness, finite exact-identification stopping under local regularity, and a polynomial-depth general-depth cost bound.

  • Takeaways & Limitations

    Two-fidelity tree search offers a principled mechanism for trading cheap biased expansion against expensive accurate sampling while maintaining reliable root-action identification.

  • Takeaways & Limitations

    The finite-stopping and exact-identification cost guarantee relies on a local regularity assumption, and the theoretical analysis uses an unbiased slow oracle for clean analysis.

Abstract

from arXiv · show

We study fixed-confidence best-action identification (BAI) in stochastic minimax trees. This problem is increasingly relevant in modern AI planning, where deep minimax search and Monte Carlo Tree Search (MCTS) with language model long rollouts face a fundamental tradeoff: heuristic evaluations are cheap but biased, while accurate rollouts are reliable but prohibitively expensive. We propose 2FFS, a two-fidelity tree-search algorithm that brings multi-fidelity flat bandit ideas into trees. The algorithm combines minimax-style fast expansion with MCTS-style stochastic sampling, adaptively deciding when to exploit cheap biased evaluations and when to invoke expensive accurate evaluations for local certification. We prove fixed-confidence correctness, establish finite stopping for exact identification, and give a polynomial-depth cost upper bound for general-depth trees. Across numerical stochastic-tree experiments, 2FFS uses substantially fewer samples and computational operations comparing to existing BAI-MCTS baseline.

1 Introduction

The paper frames stochastic minimax-tree search as a budget-allocation problem between deeper cheap-but-biased expansion and narrower expensive-but-accurate sampling. It proposes 2FFS to adaptively resolve this tradeoff for fixed-confidence root-action identification.

  • Minimax-style search spends computation on deeper expansion with fast heuristic leaf evaluations, whereas MCTS uses repeated stochastic samples to grow a narrower tree.
  • Long-horizon language-model planning creates the same tradeoff because exhaustive expansion is infeasible and long rollouts are costly.
  • 2FFS allocates computation across a minimax tree by choosing between cheap biased fast evaluations and expensive statistically accurate slow evaluations.
  • 2FFS targets fixed-confidence identification of the optimal root action while minimizing total evaluation cost.
  • The paper proves PAC correctness, finite stopping under local regularity, and a polynomial-depth cost upper bound, while reporting improved sampling and computational efficiency over an existing baseline.

2 Problem Setup and Preliminaries

The setup defines a balanced alternating MAX/MIN tree with cheap biased and costly unbiased oracles, then builds confidence intervals and effective gaps for certifying only uncertainty that can affect the root decision. The resulting complexity framework measures fast queries, slow queries, and recursive certification costs under a fixed-confidence PAC objective.

  • Tree and oracles: The stochastic minimax tree is finite, balanced in depth, and alternates between MAX and MIN nodes, with leaf payoffs defining minimax values recursively.
  • Frontier and evaluation: A frontier is a complete root-to-leaf cut, and expanding an exposed internal node reveals its children, queries their fast evaluations, and retains prior slow samples.
  • Tree and oracles: The fast oracle is deterministic and cheap but has depth-dependent bias bounded by B(h(v)), while the slow oracle provides independent σ-sub-Gaussian samples unbiased for the true node value.
  • Oracle complexity: The fixed-confidence objective requires an (ε, δ)-PAC recommendation while minimizing expected cost, with total cost combining fast queries and slow queries weighted by c.
  • Intervals: 2FFS combines fast and slow evidence into local intervals, propagates child intervals through minimax backups, and preserves validity without increasing interval width.
  • Effective gaps: The effective gap captures the largest path bottleneck, allowing nodes to be estimated coarsely once remaining uncertainty cannot change the backed-up root decision.

3 2FFS Tree Search: Two-Fidelity Fast-Slow Tree Search

2FFS adaptively certifies root actions by choosing between local slow sampling and recursive fast expansion, while maintaining confidence intervals and scale-aware certificates. Under local regularity, it is PAC-correct and achieves finite stopping with a polynomial-depth cost overhead.

  • Algorithm: 2FFS repeatedly tests whether a root action is ε-optimal and otherwise resolves the coarser unresolved certificate of the leader or challenger.The root leader is selected by the largest lower endpoint, while the challenger is selected by the largest competing upper endpoint.
  • Algorithm: RESOLVE compares local slow sampling at a node with recursive expansion using fast child evaluations, retaining both routes throughout execution.If recursive progress cannot be made within its admissible budget, the resolver falls back to one slow local query.
  • Algorithm: The recursive route follows only children that can still affect the parent certificate, lazily removing children outside the current scale-comparison margin.This avoids fully certifying children that are already separated from the relevant minimax endpoint.
  • Theoretical results: Theorem 3.1 guarantees that every finite stopping recommendation is ε-optimal on the simultaneous-validity event, yielding (ε, δ)-PAC correctness.This correctness result uses the interval-validity event and root stopping rule, without the later cost-bound assumptions.
  • Theoretical results: With αh = (h + 1)^2, the depth overhead satisfies PD = OΛpre,Λgap(D^2), giving a polynomial-depth factor in the general-depth cost guarantee.The proof charges resolver work to ideal recursive oracle complexity and bounds the resulting overhead quadratically in depth.
  • Theoretical results: Under Assumption 3.3, Theorem 3.6 guarantees finite stopping, exact recovery, and cost Cτ ≤ PD H(δ) for ε = 0.The bound applies on Eδ and uses a feasible node-wise confidence allocation.

4 Numerical Experiments

The experiments evaluate 2FFS on balanced stochastic minimax trees against fixed-confidence baselines using sampling and operation counts. 2FFS substantially reduces search effort while remaining relatively stable across moderate fast-oracle bias and slow-oracle noise.

  • Setup and evaluation: 2FFS is compared with BAI-MCTS, Minimax-fast, and Slow-only on stochastic minimax trees.The experiments use fixed-confidence baselines representing stochastic sampling, fast-only expansion, and fixed-depth expansion followed by slow-oracle sampling.
  • Setup and evaluation: The evaluation uses balanced b-ary trees with (D, b) ∈ {(5, 8), (7, 6), (10, 3)} and 100 independently generated trees per setting.These configurations cover wide shallow and deeper narrower trees.
  • Metrics: Sampling count measures sampled or visited nodes, while operation count measures bookkeeping computation across methods.The two metrics distinguish repetitive node visits from overall computation.
  • Results: 160–1450× fewer sampled or visited nodes and 1.9–4.6× fewer bookkeeping operations are reported for 2FFS than for BAI-MCTS.Minimax-fast is cheap but affected by fast-oracle bias, whereas Slow-only uses more samples and often fails to stop within the finite budget.
  • Ablations: 2FFS remains relatively stable across the tested ranges of fast-oracle bias and slow-oracle noise.The ablation uses D = 5, 8-ary trees, fast-oracle bias with mean 0.45, and slow-oracle noise with mean 0.01.

5 Conclusion

The paper introduces 2FFS for fixed-confidence best-action identification in stochastic minimax trees and establishes theoretical guarantees for its two-fidelity strategy. Experiments report substantial sampling-efficiency gains over BAI-MCTS-style baselines while maintaining reliable root-action identification.

  • 2FFS adaptively trades cheap biased expansion against expensive accurate sampling for fixed-confidence best-action identification in stochastic minimax trees.
  • The paper proves PAC correctness, finite stopping, and a general-depth cost bound relative to an ideal recursive oracle complexity.
  • 2FFS achieves substantial sampling-efficiency gains over BAI-MCTS-style baselines while maintaining reliable root-action identification.

A Further Related Works and Limitations

The related-work discussion positions 2FFS at the intersection of multi-fidelity methods, tree search, and best-action identification. It distinguishes the stochastic minimax-tree setting from black-box partition trees and identifies empirical, theoretical, and application boundaries.

  • Multi-fidelity methods: Multi-fidelity methods allocate queries across information sources with different costs and accuracies, using cheap biased fidelities when informative and expensive accurate fidelities for difficult comparisons.
  • Related tree search: MFHOO and MFPOO combine multi-fidelity queries with hierarchical partition trees for noisy black-box optimization under simple-regret objectives.
  • Distinction from black-box optimization: 2FFS instead operates on stochastic minimax trees with alternating MAX/MIN backups and fixed-confidence root-action identification.
  • Distinction from black-box optimization: 2FFS maintains minimax confidence intervals and chooses between local slow certification and recursive fast expansion.
  • Limitations and future work: The experiments focus on simulated finite minimax trees, while extensions to interactive environments, multi-agent reinforcement learning, neural-guided MCTS, dynamically generated trees, progressive widening, and very large action spaces remain future work.
  • Limitations and future work: The general-depth upper bound relies on mild local regularity assumptions, and the polynomial-depth factor remains looser than the ideal recursive oracle complexity.

B Missing Proofs and Further Technical Details

This section collects the paper’s detailed proofs, technical details, notation, and glossary material. It is intended to support readability and formal verification of the main text and appendix.

  • The appendix provides full detailed proofs and missing technical details for the main text.
  • A notation table is provided first in Appendix B.1 to define symbols used throughout the paper.
  • The notation glossary appears in Table 2 and its continuation.

B.2.1 Proof of Lemma 2.2

The proof establishes validity of propagated minimax intervals by induction on the maximum remaining distance to a frontier node. It then shows that interval half-widths remain controlled under upward backups.

  • Inductive setup: The induction parameter m(u) is the largest distance from u to any frontier node beneath it, with m(u)=0 exactly at frontier nodes.The base case is assumed, and higher values are handled using the validity of child intervals.
  • Inductive setup: Every child of a node on a frontier path is either itself frontier or an ancestor of a frontier node, enabling induction on each child.No strict ancestor of u can be frontier, because that would intersect the path to a frontier node twice.
  • Validity: MAX-node backups preserve the inclusion V∗(u) ∈ [L_u, U_u], while MIN nodes follow by the corresponding minimum argument.The proof treats the two minimax node types symmetrically.
  • Width control: If every child interval has width at most 2w, upward propagation gives the parent interval half-width at most w.For MAX nodes, the proof selects a child attaining the largest upper endpoint; MIN nodes are handled analogously.

B.2.2 Proof of Lemma 2.3

The proof shows that effective intervals remain valid after combining local oracle intervals with recursively propagated child intervals. This validity extends from exposed nodes to root and root-child intervals at every round.

  • Local validity: On the high-probability event Eδ, the slow interval is valid, while fast-oracle validity holds deterministically for exposed non-root nodes.These local guarantees provide the base cases for the recursive validity argument.
  • Recursive validity: For an unexpanded non-root node, the effective interval reduces directly to its local validity statement.No child backup is needed in this case.
  • Recursive validity: For an expanded node, valid child intervals imply validity of the MAX backup, with the MIN case following by duality.The proof proceeds upward from leaves through the explored tree.
  • Root validity: The root interval is valid because its children are valid and the same child-backup argument applies at the root.Thus all propagated intervals used by the algorithm, including root-child intervals, are valid.

B.3 Full 2FFS Operational Specification

The full specification makes 2FFS an adaptive, budgeted resolver that can combine local slow sampling with recursive fast expansion. It certifies only unresolved, decision-relevant sides and limits recursive depth-scale obligations to control cost.

  • Resolver routes: The local route shrinks a node’s local interval through slow samples, while the recursive route shrinks its effective interval by expanding and refining children.The resolver chooses between these routes through a budgeted live race.
  • Resolver routes: Local and recursive routes are no longer mutually exclusive, so work already invested at a node remains usable after expansion or later sampling.This removes residue terms from the earlier proof architecture and permits local sampling to act as a safety valve.
  • Root control: 2FFS resolves a root decision by selecting an uncertified leader or challenger side at an active dyadic scale and invoking RESOLVE.The root stops when one action beats every competitor up to ε; otherwise it refines the unresolved side with the coarser parent-relevant diameter.
  • Budgeting: A nondecreasing polynomial depth-budget sequence limits recursive spending at each internal node while preserving adaptive allocation to live witnesses.The counters record work already performed rather than comparing against a raw full-child same-scale surrogate.
  • Lazy comparison refinement: Recursive child calls are capped at the parent obligation’s scale rather than refined indefinitely below it.This capped rule prevents the localization constant from growing exponentially with tree depth.
  • Lazy comparison refinement: In comparison cases, only the current unresolved blocking child receives recursive comparison work, and it is recomputed after each unit of work.Other children are discharged by endpoint exclusion or same-side completion at the current scale.
  • Certificate bookkeeping: The algorithm tracks scale-local completion flags and defines certificates recursively from leaves upward, with recursion only through child nodes.This makes the joint certificate and comparison definitions well-founded.

B.4 Proof of Theorem 3.1

The theorem proof conditions on the simultaneous validity event and shows that any finite recommendation obeying the stopping rule is ε-optimal. Therefore, an incorrect finite recommendation can occur only outside that event.

  • Conditional correctness: The proof fixes an outcome in Eδ and assumes the algorithm stops at a finite time τ with returned action âτ.It then applies the stopping rule to the valid root-child intervals.
  • Conditional correctness: Lemma 2.3 supplies valid intervals for every root child at the stopping time.The lemma applies pathwise at every round, including the finite stopping round.
  • ε-optimality: If the returned action is not optimal, the stopping inequality bounds its value gap from the optimal root action by ε.Thus every finite recommendation on Eδ is ε-optimal.
  • ε-optimality: The theorem’s error event is contained in the complement of Eδ.Correctness follows by restricting failure to the probability of leaving the validity event.

B.5 Derived Lemmas for the General-Depth Bound

This section develops the interval-safety, recursive-resolution, and cost-charging ingredients behind 2FFS’s general-depth analysis. These ingredients establish sound certification, finite stopping, and polynomial depth dependence under the stated validity and regularity conditions.

  • Recursive algorithmic structure: The recursive resolver alternates between local slow sampling and fast expansion, using scale utilities, contender selection, capped scales, and budgeted recursive calls.The top-level driver repeatedly selects a decision-relevant root-child endpoint until an ε-optimal action is certified.
  • Derived safety and certification: The algorithm maintains nested local and child-backup intervals, so effective intervals shrink monotonically after expansion and interval updates.Nestedness follows from running intersections for slow intervals and monotone MAX/MIN child backups.
  • Recursive algorithmic structure: 2FFS’s atomic actions refresh intervals after sampling or expansion, propagate updates to the root, and return certification, progress, or blocked statuses.Expansion adds children and queries the fast oracle; local steps query the slow oracle when budget permits.
  • Derived safety and certification: 2FFS tracks side-specific scale safety and uses comparison certificates to ensure interval endpoints approximate node values at the active dyadic scale.The proof works on the simultaneous-validity event and establishes safety inductively over node depth.
  • Cost aggregation and stopping: Aggregate subtree charging avoids double-counting oracle costs and supports a polynomial-depth bound through recursively assigned costs.The resulting depth factor is O(D^2) under the specified depth-budget choice.
  • Cost aggregation and stopping: Finite stopping follows because every unresolved outer-loop round incurs at least qmin > 0 cost, contradicting a uniform finite upper bound if infinitely many rounds occurred.The same analysis establishes finite stopping and correctness for the returned action under the proof event.

B.6 Proof of Theorem 3.6

The proof of Theorem 3.6 combines finite stopping and correctness with aggregate subtree charging, then applies the resulting bound on a simultaneous-validity event. Choosing feasible confidence allocations yields the optimized high-probability statement.

  • Proof composition: Theorem 3.6 follows by applying Proposition B.15 at the finite stopping time supplied by Proposition B.18.This combines correctness, finite stopping, and aggregate cost control on the event Eδ.
  • Optimized allocation: The optimized bound is obtained by running 2FFS with a near-optimal feasible confidence allocation satisfying the uniform local regularity condition.If the infimum is attained, η can be set to zero; otherwise an η-approximate allocation gives the stated order.
Loading 2606.01708v1…