Graph-Based Stochastic Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation

# Monte-Carlo Graph Search with Power Mean Estimation
Source: [https://arxiv.org/html/2609.19956](https://arxiv.org/html/2609.19956)
Tung TranAffiliation:School of ICTAffiliation:Hanoi University of Science and TechnologyAffiliation:Hanoi, VietnamEmail:[Tung\.td235240@sis\.hust\.edu\.vn](mailto:)Viet Bao MaiAffiliation:School of ICTAffiliation:Hanoi University of Science and TechnologyAffiliation:Hanoi, VietnamEmail:[bao\.MV225474@sis\.hust\.edu\.vn](mailto:)Hoang TaAffiliation:School of ICTAffiliation:Hanoi University of Science and TechnologyAffiliation:Hanoi, VietnamEmail:[hoang\.taduy@hust\.edu\.vn](mailto:)Tuan DamAffiliation:School of ICTAffiliation:Hanoi University of Science and TechnologyAffiliation:Hanoi, VietnamEmail:[tuan\.dam@hust\.edu\.vn](mailto:)

###### Abstract

Tree\-based Monte\-Carlo Tree Search \(MCTS\) duplicates the same state when it is reached through different trajectories, which can waste simulations in stochastic MDPs\. We introduce Graph\-Based Stochastic\-Power\-UCT \(GS\-Power\-UCT\), which shares states reached at the same planning depth while keeping separate values for states reached at different depths\. This design applies to general stochastic MDPs, including problems with cycles\. We prove that for a fixed planning horizon, the root estimate converges to the finite\-horizon value at rateO\(n−1/2\)O\(n^\{\-1/2\}\), matching tree\-based Stochastic\-Power\-UCT while reusing samples across shared states\. We also study two full\-state variants: GS\-Power\-UCT\-F, which stores one node per physical state to increase sample sharing but may mix values from different remaining horizons, and GS\-Power\-UCT\-F\+, which uses an adaptive horizon to control this bias\. The latter converges toV⋆​\(s0\)V^\{\\star\}\(s\_\{0\}\), the optimal infinite\-horizon discounted value at the root states0s\_\{0\}, when the remaining cross\-depth gap vanishes\. Experiments on stochastic planning benchmarks show improved sample efficiency over tree\-based and graph\-based baselines\.

## 1Introduction

Monte\-Carlo Tree Search \(MCTS\)\[[3](https://arxiv.org/html/2609.19956#bib.bib3),[2](https://arxiv.org/html/2609.19956#bib.bib2)\]is a widely used family of online planning algorithms that combine Monte\-Carlo sampling with forward tree search\. The success of MCTS lies in adaptive exploration strategies inspired by the multi\-armed bandit \(MAB\) literature, most notably the Upper Confidence Bound for Trees \(UCT\) algorithm\[[7](https://arxiv.org/html/2609.19956#bib.bib7)\]\. Recent advances in coupling MCTS with deep learning\[[12](https://arxiv.org/html/2609.19956#bib.bib12),[13](https://arxiv.org/html/2609.19956#bib.bib13),[9](https://arxiv.org/html/2609.19956#bib.bib9)\]have enabled breakthroughs in complex decision\-making problems\.

Despite these successes, tree\-based MCTS suffers from two fundamental limitations\. First, theoretical analysis of the logarithmic exploration bonus in UCT is incomplete due to issues identified by[Shah et al\. \[10\]](https://arxiv.org/html/2609.19956#bib.bib10), leading to the development of Fixed\-Depth\-MCTS with polynomial bonuses\[[11](https://arxiv.org/html/2609.19956#bib.bib11)\]\. Second, and more relevant to this work, tree\-based MCTS does not identify states that are reachable via multiple trajectories\. When a statesscan be reached via two different action sequences, it is represented as two separate nodes in the search tree, leading to redundant exploration and suboptimal use of computational budget\.

[Leurent and Maillard \[8\]](https://arxiv.org/html/2609.19956#bib.bib8)address the second limitation by proposing Monte\-Carlo Graph Search \(MCGS\), which merges identical states into a single node in a directed graph\. They show that this merging can reduce the effective branching factor fromκ\\kappa\(tree\) toκ∞≤κ\\kappa\_\{\\infty\}\\leq\\kappa\(graph\), yielding improved regret bounds\. However, their theoretical analysis is restricted to*deterministic*MDPs with an Optimism in the Face of Uncertainty \(OFU\) planning style, and the extension to stochastic MDPs is purely empirical\.

Separately, the Stochastic\-Power\-UCT algorithm\[[5](https://arxiv.org/html/2609.19956#bib.bib5)\]addresses the first limitation by introducing power mean value estimation with polynomial exploration bonuses for stochastic MCTS, establishingO\(n−1/2\)O\(n^\{\-1/2\}\)convergence rate for value estimation at the root node\.

##### Contributions\.

We make the following contributions:

1. 1\.We introduceGraph\-Based Stochastic Power\-UCT\(GS\-Power\-UCT\), which combines power mean backups, polynomial exploration bonuses, and depth\-augmented graph search\. By keying nodes as\(s,h\)\(s,h\), the search graph is a DAG by construction for any stochastic MDP, including MDPs with cycles\.
2. 2\.We prove that GS\-Power\-UCT preserves the\(α,β\)\(\\alpha,\\beta\)\-concentration \(Definition[1](https://arxiv.org/html/2609.19956#Thmdefinition1)\) guarantees of Stochastic\-Power\-UCT on depth\-augmented graphs\. The key step is a generalized graph Q\-concentration lemma, Lemma[1](https://arxiv.org/html/2609.19956#Thmlemma1), which handles child estimates whose visits are aggregated from multiple parents\. This yields root expected errorO\(n−1/2\)O\(n^\{\-1/2\}\)for the truncated valueV~​\(s0,0\)\\widetilde\{V\}\(s\_\{0\},0\); see Theorems[6](https://arxiv.org/html/2609.19956#Thmtheorem6)and[1](https://arxiv.org/html/2609.19956#Thmtheorem1)\.
3. 3\.We analyze the cost of merging states across depths\. Proposition[3](https://arxiv.org/html/2609.19956#Thmproposition3)shows that naive full\-state merging can introduce irreducible cross\-depth bias\. For the practical full\-merge variant, we give a controlled\-bias bound in Theorem[3](https://arxiv.org/html/2609.19956#Thmtheorem3), and an adaptive\-horizon guarantee for GS\-Power\-UCT\-F\+in Theorem[4](https://arxiv.org/html/2609.19956#Thmtheorem4), where convergence toV⋆​\(s0\)V^\{\\star\}\(s\_\{0\}\)holds when the empirical cross\-depth gap vanishes\.
4. 4\.We quantify the sample\-sharing effect of depth\-augmented graph search\. For a fixed collection of simulated trajectories, the graph representation is the quotient of the unrolled tree representation obtained by identifying equal\(s,h\)\(s,h\)pairs\. Theorem[2](https://arxiv.org/html/2609.19956#Thmtheorem2)gives a deterministic sample\-sharing identity and shows that, under the same recursive proof recipe, the corresponding same\-trajectory proof bounds are not enlarged by aggregation\. This is a representation\-level comparison, not an algorithm\-level dominance claim over an independently run tree MCTS algorithm\.

## 2Preliminaries

### 2\.1Markov Decision Process

We consider a discrete\-time discounted MDPℳ=⟨𝒮,𝒜,R,P,γ⟩\\mathcal\{M\}=\\langle\\mathcal\{S\},\\mathcal\{A\},R,P,\\gamma\\rangle, where𝒮\\mathcal\{S\}is the state space and𝒜s⊆𝒜\\mathcal\{A\}\_\{s\}\\subseteq\\mathcal\{A\}is the nonempty set of admissible actions atss, withK≜maxs⁡\|𝒜s\|<∞K\\triangleq\\max\_\{s\}\|\\mathcal\{A\}\_\{s\}\|<\\infty\. A simulator response at\(s,a\)\(s,a\)consists of a successor drawn fromP\(⋅∣s,a\)P\(\\cdot\\mid s,a\)and a reward in\[0,Rmax\]\[0,R\_\{\\max\}\];R⁡\(s,a,s′\)R\(s,a,s^\{\\prime\}\)denotes its conditional mean givens′s^\{\\prime\}\. The discount factor isγ∈\[0,1\)\\gamma\\in\[0,1\)\. The optimal value function satisfies the Bellman optimality equation:

V⋆​\(s\)=maxa∈𝒜s⁡Q⋆​\(s,a\),Q⋆​\(s,a\)=∑s′P⁡\(s′\|s,a\)​\[R⁡\(s,a,s′\)\+γ​V⋆​\(s′\)\]\.V^\{\\star\}\(s\)=\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}Q^\{\\star\}\(s,a\),\\quad Q^\{\\star\}\(s,a\)=\\sum\_\{s^\{\\prime\}\}P\(s^\{\\prime\}\|s,a\)\\left\[R\(s,a,s^\{\\prime\}\)\+\\gamma V^\{\\star\}\(s^\{\\prime\}\)\\right\]\.\(1\)

### 2\.2MCTS with Power Mean Value Backup

Given a planning horizonHHand a playout policyπ0\\pi\_\{0\}with valueV0V\_\{0\}, define inductivelyV~​\(sH\)=V0​\(sH\)\\widetilde\{V\}\(s\_\{H\}\)=V\_\{0\}\(s\_\{H\}\)and forh≤H−1h\\leq H\-1:

Q~​\(sh,a\)=r⁡\(sh,a\)\+γ​∑sh\+1P⁡\(sh\+1\|sh,a\)​V~​\(sh\+1\),V~​\(sh\)=maxa∈𝒜sh⁡Q~​\(sh,a\),\\widetilde\{Q\}\(s\_\{h\},a\)=r\(s\_\{h\},a\)\+\\gamma\\sum\_\{s\_\{h\+1\}\}P\(s\_\{h\+1\}\|s\_\{h\},a\)\\widetilde\{V\}\(s\_\{h\+1\}\),\\quad\\widetilde\{V\}\(s\_\{h\}\)=\\max\_\{a\\in\\mathcal\{A\}\_\{s\_\{h\}\}\}\\widetilde\{Q\}\(s\_\{h\},a\),\(2\)wherer⁡\(sh,a\)r\(s\_\{h\},a\)is the expected immediate reward; the truncation error satisfies\|Q⋆​\(s0,a\)−Q~​\(s0,a\)\|≤γH​‖V⋆−V0‖∞\|Q^\{\\star\}\(s\_\{0\},a\)\-\\widetilde\{Q\}\(s\_\{0\},a\)\|\\leq\\gamma^\{H\}\\\|V^\{\\star\}\-V\_\{0\}\\\|\_\{\\infty\}\. Equivalently, with the Bellman optimality operator\(ℬ​V\)​\(s\)≜max⁡∑s′a∈𝒜s⁡P⁡\(s′\|s,a\)​\[R⁡\(s,a,s′\)\+γ​V​\(s′\)\]\(\\mathcal\{B\}V\)\(s\)\\triangleq\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}\\sum\_\{s^\{\\prime\}\}P\(s^\{\\prime\}\|s,a\)\[R\(s,a,s^\{\\prime\}\)\+\\gamma V\(s^\{\\prime\}\)\],V⋆V^\{\\star\}is the unique fixed point ofℬ\\mathcal\{B\}and the depth\-hhtruncated value isV~​\(s,h\)=\(ℬH−h​V0\)​\(s\)\\widetilde\{V\}\(s,h\)=\(\\mathcal\{B\}^\{H\-h\}V\_\{0\}\)\(s\)\. Aftertttrajectories, the*power mean value estimate*at an internal nodeshs\_\{h\}is

V^t​\(sh\)=\(∑a∈𝒜shTsh,a​\(t\)t​\(Q^Tsh,a​\(t\)​\(sh,a\)\)p\)1/p,\\widehat\{V\}\_\{t\}\(s\_\{h\}\)=\\left\(\\sum\_\{a\\in\\mathcal\{A\}\_\{s\_\{h\}\}\}\\frac\{T\_\{s\_\{h\},a\}\(t\)\}\{t\}\\left\(\\widehat\{Q\}\_\{T\_\{s\_\{h\},a\}\(t\)\}\(s\_\{h\},a\)\\right\)^\{p\}\\right\)^\{1/p\},\(3\)wherep∈\[1,\+∞\)p\\in\[1,\+\\infty\)andTsh,a​\(t\)T\_\{s\_\{h\},a\}\(t\)is the number of visits to\(sh,a\)\(s\_\{h\},a\)\.

### 2\.3Concentration Framework

Following[Shah et al\. \[11\]](https://arxiv.org/html/2609.19956#bib.bib11)and[Dam et al\. \[5\]](https://arxiv.org/html/2609.19956#bib.bib5), we use the following notion of polynomial concentration\.

###### Definition 1\(\(α,β\)\(\\alpha,\\beta\)\-concentration\)\.

A sequence of estimators\(V^n\)n≥1\(\\widehat\{V\}\_\{n\}\)\_\{n\\geq 1\}concentrates at rate\(α,β\)\(\\alpha,\\beta\)towards some limitVVif there exists a constantc\>0c\>0such that:

∀n≥1,∀ε\>0:ℙ⁡\(\|V^n−V\|\>ε\)≤c​n−α​ε−β\.\\forall n\\geq 1,\\;\\forall\\varepsilon\>0:\\quad\\mathbb\{P\}\\left\(\|\\widehat\{V\}\_\{n\}\-V\|\>\\varepsilon\\right\)\\leq c\\,n^\{\-\\alpha\}\\varepsilon^\{\-\\beta\}\.\(4\)We writeV^n→n→∞α,βV\\widehat\{V\}\_\{n\}\\xrightarrow\[n\\to\\infty\]\{\\alpha,\\beta\}V\.

## 3Graph\-Based Stochastic Power\-UCT

The efficiency of graph\-based planning in MDPs hinges on the mechanism used to merge trajectories\. We present GS\-Power\-UCT, an algorithm designed to balanceestimation accuracy\(preserving value consistency\) withsample efficiency\(maximizing state reuse\)\. We formalize this balance through a state\-mapping functionϕ⁡\(s,h\)\\phi\(s,h\)that defines how physical statesssand trajectory depthshhare indexed in the search graph𝒢n\\mathcal\{G\}\_\{n\}, allowing us to transition between a theoretically consistent model and a computationally high\-throughput variant\.

### 3\.1Search Graph Construction

We maintain a graph𝒢n=\(𝒩n,ℰn\)\\mathcal\{G\}\_\{n\}=\(\\mathcal\{N\}\_\{n\},\\mathcal\{E\}\_\{n\}\)where each nodev∈𝒩nv\\in\\mathcal\{N\}\_\{n\}represents an aggregate statev=ϕ⁡\(s,h\)v=\\phi\(s,h\), and the choice ofϕ\\phidetermines the topology of the search space\. The*depth\-augmented mapping*ϕ⁡\(s,h\)=\(s,h\)\\phi\(s,h\)=\(s,h\)distinguishes the same physical state at different depths and is thecanonical formfor finite\-horizon MDPs, since the value of a state is inherently non\-stationary with respect to the remaining horizonH−hH\-h; it ensures𝒢n\\mathcal\{G\}\_\{n\}is a DAG by construction \(Prop\.[1](https://arxiv.org/html/2609.19956#Thmproposition1)\), eliminating the bias caused by depth\-cutoff truncation, and merges all same\-depth transpositions, which are the most frequent in structured MDPs\. The*full\-state mapping*ϕ⁡\(s,h\)=s\\phi\(s,h\)=sinstead merges all visits to a physical state regardless of depth, drastically reducing the graph size and maximizing information sharing across stages of the trajectory; this relaxation is particularly effective when the environment is cyclic or whenV0V\_\{0\}is a strong estimator, making the horizon\-induced bias negligible\.

### 3\.2Analyzing the Merging Trade\-off

The transition from depth\-augmented to full\-state merging involves a fundamental trade\-off: the former guarantees convergence to the optimal truncated value, whereas the latter introduces across\-depth biasΔcross\\Delta\_\{\\textsc\{cross\}\}that we now quantify\. For each physical statess, let𝒟⁡\(s\)=\{h:s​is visited at depth​h​during planning\}\\mathcal\{D\}\(s\)=\\\{h:s\\text\{ is visited at depth \}h\\text\{ during planning\}\\\}, withhmin​\(s\)=min⁡𝒟⁡\(s\)h\_\{\\min\}\(s\)=\\min\\mathcal\{D\}\(s\)andhmax​\(s\)=max⁡𝒟⁡\(s\)h\_\{\\max\}\(s\)=\\max\\mathcal\{D\}\(s\)\. The cross\-depth gap atssis

δ⁡\(s\)=maxh1,h2∈𝒟⁡\(s\)⁡\|V~​\(s,h1\)−V~​\(s,h2\)\|\.\\delta\(s\)=\\max\_\{h\_\{1\},h\_\{2\}\\in\\mathcal\{D\}\(s\)\}\\left\|\\widetilde\{V\}\(s,h\_\{1\}\)\-\\widetilde\{V\}\(s,h\_\{2\}\)\\right\|\.\(5\)SinceV~​\(s,h\)=\(ℬH−h​V0\)​\(s\)\\widetilde\{V\}\(s,h\)=\(\\mathcal\{B\}^\{H\-h\}V\_\{0\}\)\(s\)andℬ\\mathcal\{B\}is aγ\\gamma\-contraction in∥⋅∥∞\\\|\\cdot\\\|\_\{\\infty\},

δ⁡\(s\)≤γH−hmax​\(s\)−γH−hmin​\(s\)1−γ​‖ℬ​V0−V0‖∞≤\(1\+γ\)​\(γH−hmax​\(s\)−γH−hmin​\(s\)\)1−γ​‖V⋆−V0‖∞,\\delta\(s\)\\leq\\frac\{\\gamma^\{H\-h\_\{\\max\}\(s\)\}\-\\gamma^\{H\-h\_\{\\min\}\(s\)\}\}\{1\-\\gamma\}\\,\\\|\\mathcal\{B\}V\_\{0\}\-V\_\{0\}\\\|\_\{\\infty\}\\leq\\frac\{\(1\+\\gamma\)\\bigl\(\\gamma^\{H\-h\_\{\\max\}\(s\)\}\-\\gamma^\{H\-h\_\{\\min\}\(s\)\}\\bigr\)\}\{1\-\\gamma\}\\,\\\|V^\{\\star\}\-V\_\{0\}\\\|\_\{\\infty\},\(6\)using‖ℬ​V0−V0‖∞≤\(1\+γ\)​‖V⋆−V0‖∞\\\|\\mathcal\{B\}V\_\{0\}\-V\_\{0\}\\\|\_\{\\infty\}\\leq\(1\+\\gamma\)\\\|V^\{\\star\}\-V\_\{0\}\\\|\_\{\\infty\}for the second form\. The global cross\-depth gap isΔcross=maxs∈𝒢⁡δ⁡\(s\)\\Delta\_\{\\textsc\{cross\}\}=\\max\_\{s\\in\\mathcal\{G\}\}\\delta\(s\)\. Thus full\-state merging is reliable when the Bellman residual of the playout value is small, when relevant depths are close, or when the remaining horizonsH−hH\-hare all large; if every physical state is visited at a single depth, thenδ⁡\(s\)=0\\delta\(s\)=0\.

To resolve this, we usedepth\-augmented nodes: the graph𝒢n=\(𝒩n,ℰn\)\\mathcal\{G\}\_\{n\}=\(\\mathcal\{N\}\_\{n\},\\mathcal\{E\}\_\{n\}\)has nodes\(s,h\)∈𝒮×\{0,…,H\}\(s,h\)\\in\\mathcal\{S\}\\times\\\{0,\\ldots,H\\\}, wheressis the physical state andhhis the trajectory depth at which the node was created\. Formally,𝒩n⊆𝒮×\{0,…,H\}\\mathcal\{N\}\_\{n\}\\subseteq\\mathcal\{S\}\\times\\\{0,\\ldots,H\\\}collects the depth\-augmented nodes discovered so far, andℰn\\mathcal\{E\}\_\{n\}contains the observed transitions\(\(s,h\),a,\(s′,h\+1\)\)\(\(s,h\),a,\(s^\{\\prime\},h\+1\)\)with\(s,h\),\(s′,h\+1\)∈𝒩n\(s,h\),\(s^\{\\prime\},h\+1\)\\in\\mathcal\{N\}\_\{n\}anda∈𝒜sa\\in\\mathcal\{A\}\_\{s\}\. Since every edge strictly increases the depth coordinate,𝒢n\\mathcal\{G\}\_\{n\}is a DAG by construction\. Crucially, two trajectories reaching the same physical statessat the same depthhh*are merged*— they share the node\(s,h\)\(s,h\)and its value estimateV^​\(s,h\)\\widehat\{V\}\(s,h\)— capturing the key benefit of graph\-based planning while ensuring each node has a well\-defined target valueV~​\(sh\)\\widetilde\{V\}\(s\_\{h\}\)from \([2](https://arxiv.org/html/2609.19956#S2.E2)\)\.

###### Proposition 1\(DAG by construction\)\.

The search graph𝒢n\\mathcal\{G\}\_\{n\}maintained by GS\-Power\-UCT is a DAG for any MDP, including those with cyclic transitions; every edge connects\(s,h\)\(s,h\)to\(s′,h\+1\)\(s^\{\\prime\},h\+1\), strictly increasing the depth coordinate, so no directed cycle can exist\.

The internal nodes𝒢̊n\\mathring\{\\mathcal\{G\}\}\_\{n\}\(fully expanded\) and boundary nodes∂𝒢n\\partial\\mathcal\{G\}\_\{n\}\(not yet expanded\) partition𝒩n\\mathcal\{N\}\_\{n\}\. For each\(s,h\)∈𝒩n\(s,h\)\\in\\mathcal\{N\}\_\{n\}we maintainglobalvisit countsTs,h​\(n\)T\_\{s,h\}\(n\)\(total visits to\(s,h\)\(s,h\)\),Ts,h,a​\(n\)T\_\{s,h,a\}\(n\)\(actionaataken at\(s,h\)\(s,h\)\), andTs,h,as′​\(n\)T\_\{s,h,a\}^\{s^\{\\prime\}\}\(n\)\(transitions\(\(s,h\),a\)→\(s′,h\+1\)\(\(s,h\),a\)\\to\(s^\{\\prime\},h\+1\)\)\. These aggregate visits from*all*parents reaching\(s,h\)\(s,h\)— the defining feature of global\-count graph\-based planning\.

### 3\.3The Four Steps of GS\-Power\-UCT

Table 1:Conditions for algorithmic constants\.h∈\[0,H−1\]h\\in\[0,H\-1\]\.Table 2:Comparison of the algorithm variants\.H⁡\(n\)=⌈log⁡\(n\)/\(2​log⁡\(1/γ\)\)⌉H\(n\)=\\lceil\\log\(n\)/\(2\\log\(1/\\gamma\)\)\\rceilandc⁡\(n\)≜c⁡\(H⁡\(n\)\)c\(n\)\\triangleq c\(H\(n\)\)\. TheV⋆​\(s0\)V^\{\\star\}\(s\_\{0\}\)target and displayed rate for F\+are conditional on the cross\-depth conditions in Theorem[4](https://arxiv.org/html/2609.19956#Thmtheorem4)\.Each simulationttof GS\-Power\-UCT proceeds in four steps\.

##### Step 1: Selection with Lookup\.

Starting from the root\(s0,0\)\(s\_\{0\},0\), at each internal node\(s,h\)∈𝒢̊n\(s,h\)\\in\\mathring\{\\mathcal\{G\}\}\_\{n\}select an action via the UCB\-style rule

a=arg​maxa∈𝒜s⁡\{Q^Ts,h,a​\(t\)​\(s,h,a\)\+C⋅Ts,h​\(t\)bh\+1/βh\+1Ts,h,a​\(t\)αh\+1/βh\+1\},a=\\argmax\_\{a\\in\\mathcal\{A\}\_\{s\}\}\\left\\\{\\widehat\{Q\}\_\{T\_\{s,h,a\}\(t\)\}\(s,h,a\)\+C\\cdot\\frac\{T\_\{s,h\}\(t\)^\{b\_\{h\+1\}/\\beta\_\{h\+1\}\}\}\{T\_\{s,h,a\}\(t\)^\{\\alpha\_\{h\+1\}/\\beta\_\{h\+1\}\}\}\\right\\\},\(7\)where\{bh\}\\\{b\_\{h\}\\\},\{αh\}\\\{\\alpha\_\{h\}\\\},\{βh\}\\\{\\beta\_\{h\}\\\}satisfy Table[1](https://arxiv.org/html/2609.19956#S3.T1)andC\>0C\>0is an exploration constant\. Samples′∼P\(⋅\|s,a\)s^\{\\prime\}\\sim P\(\\cdot\|s,a\)and perform adepth\-augmented lookup: if\(s′,h\+1\)∈𝒢n\(s^\{\\prime\},h\+1\)\\in\\mathcal\{G\}\_\{n\}\(a*same\-depth transposition*\), continue selection from the existing node, adding the edge\(\(s,h\),a\)→\(s′,h\+1\)\(\(s,h\),a\)\\to\(s^\{\\prime\},h\+1\)toℰn\\mathcal\{E\}\_\{n\}if new; otherwise proceed to Step 2\. Selection terminates at depthHH\.

##### Step 2: Expansion\.

If\(s′,h\+1\)∉𝒢n\(s^\{\\prime\},h\+1\)\\notin\\mathcal\{G\}\_\{n\}, add it to∂𝒢n\\partial\\mathcal\{G\}\_\{n\}withTs′,h\+1=0T\_\{s^\{\\prime\},h\+1\}=0and append the edge\(\(s,h\),a\)→\(s′,h\+1\)\(\(s,h\),a\)\\to\(s^\{\\prime\},h\+1\)toℰn\\mathcal\{E\}\_\{n\}\.

##### Step 3: Evaluation\.

For a new boundary node\(s′,h\+1\)∈∂𝒢n\(s^\{\\prime\},h\+1\)\\in\\partial\\mathcal\{G\}\_\{n\}, draw one fresh rolloutZ1​\(s′\)∼π0​\(s′\)Z\_\{1\}\(s^\{\\prime\}\)\\sim\\pi\_\{0\}\(s^\{\\prime\}\)with𝔼⁡\[Z1​\(s′\)\]=V0​\(s′\)\\mathbb\{E\}\[Z\_\{1\}\(s^\{\\prime\}\)\]=V\_\{0\}\(s^\{\\prime\}\), and setV^1​\(s′,h\+1\)=Z1​\(s′\)\\widehat\{V\}\_\{1\}\(s^\{\\prime\},h\+1\)=Z\_\{1\}\(s^\{\\prime\}\)andTs′,h\+1=1T\_\{s^\{\\prime\},h\+1\}=1\. This is a single initialization sample; internal value estimates subsequently updated by the adaptive search are not treated as i\.i\.d\. samples\.

##### Step 4: Backpropagation \(Path\-Only\)\.

Update statistics only along the trajectory\{\(s0,0\),a0,…,\(sℓ,ℓ\)\}\\\{\(s\_\{0\},0\),a\_\{0\},\\ldots,\(s\_\{\\ell\},\\ell\)\\\}\. WritingT≡Tsh,h,ah​\(t\)T\\equiv T\_\{s\_\{h\},h,a\_\{h\}\}\(t\)andT′≡Tsh,h​\(t\)T^\{\\prime\}\\equiv T\_\{s\_\{h\},h\}\(t\), and lettingrtr\_\{t\}be the reward observed on the corresponding transition at simulationtt, in reverse order:

T\\displaystyle T←T\+1,T′←T′\+1,\\displaystyle\\leftarrow T\+1,\\quad T^\{\\prime\}\\leftarrow T^\{\\prime\}\+1,\(8\)Q^T​\(sh,h,ah\)\\displaystyle\\widehat\{Q\}\_\{T\}\(s\_\{h\},h,a\_\{h\}\)←\(T−1\)​Q^T−1​\(sh,h,ah\)\+rt\+γ​V^Tsh\+1,h\+1​\(sh\+1,h\+1\)T,\\displaystyle\\leftarrow\\tfrac\{\(T\-1\)\\widehat\{Q\}\_\{T\-1\}\(s\_\{h\},h,a\_\{h\}\)\+r\_\{t\}\+\\gamma\\widehat\{V\}\_\{T\_\{s\_\{h\+1\},h\+1\}\}\(s\_\{h\+1\},h\+1\)\}\{T\},\(9\)V^T′​\(sh,h\)\\displaystyle\\widehat\{V\}\_\{T^\{\\prime\}\}\(s\_\{h\},h\)←\(∑a∈𝒜shTsh,h,a​\(t\)T′​\(Q^Tsh,h,a​\(t\)​\(sh,h,a\)\)p\)1/p\.\\displaystyle\\leftarrow\\Big\(\\textstyle\\sum\_\{a\\in\\mathcal\{A\}\_\{s\_\{h\}\}\}\\tfrac\{T\_\{s\_\{h\},h,a\}\(t\)\}\{T^\{\\prime\}\}\\big\(\\widehat\{Q\}\_\{T\_\{s\_\{h\},h,a\}\(t\)\}\(s\_\{h\},h,a\)\\big\)^\{p\}\\Big\)^\{1/p\}\.\(10\)
Afternnsimulations, the recommended action isa^n=arg​maxa∈𝒜s0⁡Q^Ts0,0,a​\(n\)​\(s0,0,a\)\\hat\{a\}\_\{n\}=\\argmax\_\{a\\in\\mathcal\{A\}\_\{s\_\{0\}\}\}\\widehat\{Q\}\_\{T\_\{s\_\{0\},0,a\}\(n\)\}\(s\_\{0\},0,a\)and the root value estimate isV^n​\(s0,0\)\\widehat\{V\}\_\{n\}\(s\_\{0\},0\)\.

## 4Theoretical Analysis

The depth\-augmented graph𝒢n\\mathcal\{G\}\_\{n\}maintained by GS\-Power\-UCT is a DAG by Proposition[1](https://arxiv.org/html/2609.19956#Thmproposition1), without any assumption on the MDP topology\. This holds even for MDPs with arbitrary cycles or self\-loops\. The separate probabilistic and finiteness conditions used by the concentration results are collected in Appendix[A](https://arxiv.org/html/2609.19956#A1); the theoretical analysis proceeds by exploiting the DAG structure together with those conditions\.

### 4\.1Graph Structure and Topological Order

Since𝒢n\\mathcal\{G\}\_\{n\}is a DAG with depth as the natural topological coordinate, every node\(s,h\)\(s,h\)has a well\-defined depthh∈\{0,1,…,H\}h\\in\\\{0,1,\\ldots,H\\\}\. For each node, define:

- •Parents​\(s,h\)=\{\(\(s′,h−1\),a\):\(\(s′,h−1\),a,\(s,h\)\)∈ℰn\}\\textsc\{Parents\}\(s,h\)=\\\{\(\(s^\{\\prime\},h\-1\),a\):\(\(s^\{\\prime\},h\-1\),a,\(s,h\)\)\\in\\mathcal\{E\}\_\{n\}\\\}: the set of parent\-action pairs,
- •𝒩h=\{\(s,h\)∈𝒩n\}\\mathcal\{N\}\_\{h\}=\\\{\(s,h\)\\in\\mathcal\{N\}\_\{n\}\\\}: the set of nodes at depthhh\.

The key structural difference from tree\-MCTS is that a node\(s,h\)\(s,h\)with\|Parents​\(s,h\)\|\>1\|\\textsc\{Parents\}\(s,h\)\|\>1receives visits from multiple parent nodes\. In tree\-MCTS, the visit countTs,h​\(n\)T\_\{s,h\}\(n\)is entirely controlled by one parent’s bandit strategy\. In GS\-Power\-UCT,Ts,h​\(n\)=∑\(\(s′,h−1\),a\)∈Parents​\(s,h\)Ts′,h−1,as​\(n\)T\_\{s,h\}\(n\)=\\sum\_\{\(\(s^\{\\prime\},h\-1\),a\)\\in\\textsc\{Parents\}\(s,h\)\}T\_\{s^\{\\prime\},h\-1,a\}^\{s\}\(n\), aggregating contributions from all parents\.

Each node\(s,h\)\(s,h\)has a well\-defined concentration target: the truncated valueV~​\(sh\)\\widetilde\{V\}\(s\_\{h\}\)defined by the Bellman recursion \([2](https://arxiv.org/html/2609.19956#S2.E2)\) starting from depthhhwith remaining horizonH−hH\-h\. This is guaranteed because all visits to\(s,h\)\(s,h\)come from depthhh— the depth\-augmentation prevents mixing estimates from different effective horizons\.

###### Definition 2\(Transposition ratio\)\.

For depthhh, define the*transposition ratio*

τh≜\|𝒩h\|Nh𝒯,\\tau\_\{h\}\\triangleq\\frac\{\|\\mathcal\{N\}\_\{h\}\|\}\{N\_\{h\}^\{\\mathcal\{T\}\}\},\(11\)where\|𝒩h\|\|\\mathcal\{N\}\_\{h\}\|is the number of unique depth\-augmented nodes at depthhhandNh𝒯N\_\{h\}^\{\\mathcal\{T\}\}is the number of nodes at depthhhin the unrolled tree𝒯⁡\(𝒢\)\\mathcal\{T\}\(\\mathcal\{G\}\)\. We haveτh∈\(0,1\]\\tau\_\{h\}\\in\(0,1\], withτh=1\\tau\_\{h\}=1corresponding to no transpositions \(tree\) andτh≪1\\tau\_\{h\}\\ll 1indicating heavy same\-depth state merging\.

### 4\.2Generalized Topological Concentration Lemma

The following lemma is the key technical innovation for extending the concentration framework from trees to graphs\. It generalizes Lemma 1 of[Dam et al\. \[5\]](https://arxiv.org/html/2609.19956#bib.bib5)to handle the case where child value estimates are updated by visits from multiple parents\. For each fixed state–depth–action query, the reward–successor pairs form the fresh local stream in condition \(A\-Fresh\) of Assumption[1](https://arxiv.org/html/2609.19956#Thmassumption1); only this local stream is i\.i\.d\., whereas the child estimates are handled through their concentration premise\.

###### Lemma 1\(Q\-value concentration in graph\)\.

Consider an internal nodessin𝒢\\mathcal\{G\}with actiona∈𝒜sa\\in\\mathcal\{A\}\_\{s\}, and letM=\|\{s′:P⁡\(s′\|s,a\)\>0\}\|M=\|\\\{s^\{\\prime\}:P\(s^\{\\prime\}\|s,a\)\>0\\\}\|\. For eachm∈\[M\]m\\in\[M\], suppose the value estimates\(V^m,n\)n≥1\(\\widehat\{V\}\_\{m,n\}\)\_\{n\\geq 1\}for successorsms\_\{m\}satisfyV^m,n→n→∞α,βVm\\widehat\{V\}\_\{m,n\}\\xrightarrow\[n\\to\\infty\]\{\\alpha,\\beta\}V\_\{m\}with respect to theglobalvisit count ofsms\_\{m\}, withV^m,n≤L\\widehat\{V\}\_\{m,n\}\\leq L, in the time\-uniform form of local hypothesis \(H\-Q\) in Appendix[A](https://arxiv.org/html/2609.19956#A1)\. LetXiX\_\{i\}be i\.i\.d\. rewards with meanμ=r⁡\(s,a\)\\mu=r\(s,a\),Si∼P\(⋅\|s,a\)S\_\{i\}\\sim P\(\\cdot\|s,a\)the i\.i\.d\. transitions andNmn=\#⁡\{i≤n:Si=sm\}N\_\{m\}^\{n\}=\\\#\\\{i\\leq n:S\_\{i\}=s\_\{m\}\\\}the local transition counts\. LetTsmext​\(n\)T\_\{s\_\{m\}\}^\{\\textsc\{ext\}\}\(n\)be the \(non\-decreasing, possibly random\) visits tosms\_\{m\}from*other*parents, and define the*effective*countTsmeff​\(n\)=Nmn\+Tsmext​\(n\)T\_\{s\_\{m\}\}^\{\\textsc\{eff\}\}\(n\)=N\_\{m\}^\{n\}\+T\_\{s\_\{m\}\}^\{\\textsc\{ext\}\}\(n\)\. Then, provided2​α≤β2\\alpha\\leq\\betaandβ\>1\\beta\>1, the Q\-value estimate

Q^n​\(s,a\)=1n​∑i=1nXi\+γ​∑m=1MNmnn​V^m,Tsmeff​\(n\)\\widehat\{Q\}\_\{n\}\(s,a\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}X\_\{i\}\+\\gamma\\sum\_\{m=1\}^\{M\}\\frac\{N\_\{m\}^\{n\}\}\{n\}\\,\\widehat\{V\}\_\{m,T\_\{s\_\{m\}\}^\{\\textsc\{eff\}\}\(n\)\}\(12\)satisfiesQ^n​\(s,a\)→n→∞α,βμ\+γ​∑m=1Mpm​Vm=Q~​\(s,a\)\\widehat\{Q\}\_\{n\}\(s,a\)\\xrightarrow\[n\\to\\infty\]\{\\alpha,\\beta\}\\mu\+\\gamma\\sum\_\{m=1\}^\{M\}p\_\{m\}V\_\{m\}=\\widetilde\{Q\}\(s,a\), wherepm=P⁡\(sm\|s,a\)p\_\{m\}=P\(s\_\{m\}\|s,a\)\.

### 4\.3Main Result: Root Node Convergence

We can now state the main convergence result, obtained by induction over the topological order of the DAG\. For a depth\-augmented node\(s,h\)\(s,h\), we writeV~​\(s,h\)\\widetilde\{V\}\(s,h\)andQ~​\(s,h,a\)\\widetilde\{Q\}\(s,h,a\)as shorthand for the depth\-hhtruncated Bellman targetsV~​\(sh\)\\widetilde\{V\}\(s\_\{h\}\)andQ~​\(sh,a\)\\widetilde\{Q\}\(s\_\{h\},a\)from Equation \([2](https://arxiv.org/html/2609.19956#S2.E2)\)\.

###### Theorem 1\(Convergence rate of expected payoff\)\.

Under Assumption[1](https://arxiv.org/html/2609.19956#Thmassumption1), at the root depth\-augmented node\(s0,0\)\(s\_\{0\},0\), with optimal parameter tuning, GS\-Power\-UCT satisfies

\|𝔼\[V^n\(s0,0\)\]−V~\(s0,0\)\|≤O\(n−1/2\)\.\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}\(s\_\{0\},0\)\]\-\\widetilde\{V\}\(s\_\{0\},0\)\\right\|\\leq O\(n^\{\-1/2\}\)\.\(13\)

### 4\.4Quantifying the Graph Advantage

While Theorems[6](https://arxiv.org/html/2609.19956#Thmtheorem6)and[1](https://arxiv.org/html/2609.19956#Thmtheorem1)show that GS\-Power\-UCT achieves the same*asymptotic rate*O\(n−1/2\)O\(n^\{\-1/2\}\)as tree\-based Stochastic\-Power\-UCT, the graph structure provides a concrete advantage through the concentration constants\.

###### Theorem 2\(Sample sharing and non\-worsening proof constants\)\.

Fix a depth\-augmented search graph𝒢\\mathcal\{G\}and its unrolled tree𝒯⁡\(𝒢\)\\mathcal\{T\}\(\\mathcal\{G\}\)\. For each depthhh, letϕh:𝒯h→𝒩h\\phi\_\{h\}:\\mathcal\{T\}\_\{h\}\\to\\mathcal\{N\}\_\{h\}be the projection from a tree copy to its depth\-augmented graph node, and write𝒞⁡\(v\)=ϕh−1​\(v\)\\mathcal\{C\}\(v\)=\\phi\_\{h\}^\{\-1\}\(v\)\. Under the natural coupling using the same simulated trajectories,

Tv𝒢​\(n\)=∑u∈𝒞⁡\(v\)Tu𝒯​\(n\),Tv𝒢​\(n\)≥Tu𝒯​\(n\)∀u∈𝒞⁡\(v\)\.T\_\{v\}^\{\\mathcal\{G\}\}\(n\)=\\sum\_\{u\\in\\mathcal\{C\}\(v\)\}T\_\{u\}^\{\\mathcal\{T\}\}\(n\),\\qquad T\_\{v\}^\{\\mathcal\{G\}\}\(n\)\\geq T\_\{u\}^\{\\mathcal\{T\}\}\(n\)\\quad\\forall u\\in\\mathcal\{C\}\(v\)\.\(14\)The same identity holds for action countsTv,a𝒢​\(n\)T\_\{v,a\}^\{\\mathcal\{G\}\}\(n\)andTu,a𝒯​\(n\)T\_\{u,a\}^\{\\mathcal\{T\}\}\(n\)\. Consequently,

\|𝒩h\|−1​∑v∈𝒩hTv𝒢​\(n\)\|𝒯h\|−1​∑u∈𝒯hTu𝒯​\(n\)=\|𝒯h\|\|𝒩h\|=1τh\.\\frac\{\|\\mathcal\{N\}\_\{h\}\|^\{\-1\}\\sum\_\{v\\in\\mathcal\{N\}\_\{h\}\}T\_\{v\}^\{\\mathcal\{G\}\}\(n\)\}\{\|\\mathcal\{T\}\_\{h\}\|^\{\-1\}\\sum\_\{u\\in\\mathcal\{T\}\_\{h\}\}T\_\{u\}^\{\\mathcal\{T\}\}\(n\)\}=\\frac\{\|\\mathcal\{T\}\_\{h\}\|\}\{\|\\mathcal\{N\}\_\{h\}\|\}=\\frac\{1\}\{\\tau\_\{h\}\}\.\(15\)
Moreover, apply the same recursive concentration proof to𝒢\\mathcal\{G\}and𝒯⁡\(𝒢\)\\mathcal\{T\}\(\\mathcal\{G\}\), with identical leaf constants and Stochastic\-Power\-UCT parameters\. If the recursive constant maps are monotone, in the sense that larger child sample counts and smaller child concentration constants cannot worsen the parent constant, then the proof\-generated constants satisfy

ch𝒢​\(v\)≤ch𝒯​\(u\),∀v∈𝒩h,∀u∈𝒞⁡\(v\)\.c\_\{h\}^\{\\mathcal\{G\}\}\(v\)\\leq c\_\{h\}^\{\\mathcal\{T\}\}\(u\),\\qquad\\forall v\\in\\mathcal\{N\}\_\{h\},\\ \\forall u\\in\\mathcal\{C\}\(v\)\.\(16\)In particular,c0𝒢≤c0𝒯c\_\{0\}^\{\\mathcal\{G\}\}\\leq c\_\{0\}^\{\\mathcal\{T\}\}at the root\.

### 4\.5Computational Complexity

###### Proposition 2\(Complexity per simulation\)\.

Each simulation of GS\-Power\-UCT has the following complexity:

- •Selection \+ Lookup:O⁡\(H⋅\(K\+Thash\)\)O\(H\\cdot\(K\+T\_\{\\textsc\{hash\}\}\)\), whereThashT\_\{\\textsc\{hash\}\}is the cost of a hash table lookup\. For discrete states with a hash table,Thash=O⁡\(1\)T\_\{\\textsc\{hash\}\}=O\(1\)amortized\.
- •Expansion:O⁡\(K\+Thash\)O\(K\+T\_\{\\textsc\{hash\}\}\)for creating a new node and adding edges\.
- •Evaluation:O⁡\(H\)O\(H\)for a rollout of lengthHH\.
- •Backpropagation:O⁡\(H⋅K\)O\(H\\cdot K\)for updating Q\-values and power means along the path\.

Total per simulation:O⁡\(H⋅\(K\+Thash\)\)O\(H\\cdot\(K\+T\_\{\\textsc\{hash\}\}\)\), which is the same as tree\-MCTS up to theThashT\_\{\\textsc\{hash\}\}factor\.

### 4\.6Convergence of the Full\-Merge Variant

We now analyze the convergence of GS\-Power\-UCT\-F \(Algorithm[2](https://arxiv.org/html/2609.19956#alg2)\), the full state merging variant from Section[C\.2](https://arxiv.org/html/2609.19956#A3.SS2)\. The key difference is that a shared nodessvisited at multiple depths targets a mixture of truncated values rather than a single well\-defined limit\. We show that the convergence rate is preserved up to an additive bias term\.

###### Theorem 3\(Convergence rate of GS\-Power\-UCT\-F\)\.

Apply GS\-Power\-UCT\-F \(Algorithm[2](https://arxiv.org/html/2609.19956#alg2)\) with algorithmic constants\{bh\}h=0H−1\\\{b\_\{h\}\\\}\_\{h=0\}^\{H\-1\},\{αh\}h=0H−1\\\{\\alpha\_\{h\}\\\}\_\{h=0\}^\{H\-1\},\{βh\}h=0H−1\\\{\\beta\_\{h\}\\\}\_\{h=0\}^\{H\-1\}satisfying Table[1](https://arxiv.org/html/2609.19956#S3.T1)\. If the empirical full\-merge targetV¯n\\bar\{V\}\_\{n\}from Definition[4](https://arxiv.org/html/2609.19956#Thmdefinition4)satisfies𝔼⁡\[\|V¯n​\(s0\)−V~​\(s0,0\)\|\]≤CΔ​Δcross\\mathbb\{E\}\[\|\\bar\{V\}\_\{n\}\(s\_\{0\}\)\-\\widetilde\{V\}\(s\_\{0\},0\)\|\]\\leq C\_\{\\Delta\}\\Delta\_\{\\textsc\{cross\}\}, then under the optimal tuningα0/β0=1/2\\alpha\_\{0\}/\\beta\_\{0\}=1/2the root estimate satisfies

\|𝔼⁡\[V^n​\(s0\)\]−V~​\(s0,0\)\|≤O\(n−1/2\)⏟sampling error\+O⁡\(Δcross\)⏟cross\-depth bias\.\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}\(s\_\{0\}\)\]\-\\widetilde\{V\}\(s\_\{0\},0\)\\right\|\\leq\\underbrace\{O\(n^\{\-1/2\}\)\}\_\{\\text\{sampling error\}\}\+\\underbrace\{O\(\\Delta\_\{\\textsc\{cross\}\}\)\}\_\{\\text\{cross\-depth bias\}\}\.\(17\)The first term matches tree\-based Stochastic\-Power\-UCT \(Theorem[1](https://arxiv.org/html/2609.19956#Thmtheorem1)\); the second term vanishes whenΔcross=0\\Delta\_\{\\textsc\{cross\}\}=0, recovering that rate exactly\.

### 4\.7Controlling Cross\-Depth Bias with Depth\-Independent Exploration

The cross\-depth bias in Theorem[3](https://arxiv.org/html/2609.19956#Thmtheorem3)originates from the finite\-horizon cutoff: the same physical statessmay be entered at different trajectory depths, and hence may be backed up with different remaining horizons\. Depth\-dependent exploration parameters can introduce an additional artificial source of depth dependence\. We remove this artificial source by using a depth\-independent exploration bonus\. However, this does*not*make the finite\-horizon targetsV~H​\(s,h\)\\widetilde\{V\}\_\{H\}\(s,h\)independent ofhh\. Therefore, for the full\-merge variant we do not claim exact zero cross\-depth bias at every local node\. Instead, we obtain a root\-level convergence bound with an explicit cross\-depth bias term, and this term vanishes under a natural depth\-slack condition\.

##### Depth\-independent exploration bonus\.

Remark 2 of[Dam et al\. \[5\]](https://arxiv.org/html/2609.19956#bib.bib5)observes that the optimal parameter choiceαi/βi=1/2\\alpha\_\{i\}/\\beta\_\{i\}=1/2andbi/βi=1/4b\_\{i\}/\\beta\_\{i\}=1/4for alli∈\[0,H−1\]i\\in\[0,H\-1\]yields the exploration bonus:

B⁡\(n,s,a\)=C⋅Ts​\(n\)1/4Ts,a​\(n\)1/2,B\(n,s,a\)=C\\cdot\\frac\{T\_\{s\}\(n\)^\{1/4\}\}\{T\_\{s,a\}\(n\)^\{1/2\}\},\(18\)which is*independent of the depthhh*\. With this choice, the action selection rule at any nodessdepends only on the global visit counts\(Ts,Ts,a\)\(T\_\{s\},T\_\{s,a\}\)and Q\-value estimatesQ^​\(s,a\)\\widehat\{Q\}\(s,a\), none of which carry depth information\. Consequently, the exploration rule itself no longer depends on the trajectory depth at whichssis entered\. The remaining source of cross\-depth discrepancy is only the finite\-horizon cutoff\.

If we further choose the horizonHHlarge enough, the cutoff becomes irrelevant: both visits explore the subgraph belowssto sufficient depth that the truncation error is negligible\. This motivates the*adaptive horizon*strategy\.

##### Adaptive horizon\.

Given a budget ofnnsimulations, set the planning horizon to

H⁡\(n\)=⌈log⁡n2​log⁡\(1/γ\)⌉,H\(n\)=\\left\\lceil\\frac\{\\log n\}\{2\\log\(1/\\gamma\)\}\\right\\rceil,\(19\)so thatγH⁡\(n\)≤n−1/2\\gamma^\{H\(n\)\}\\leq n^\{\-1/2\}\. This choice makes the ordinary root\-level truncation error match then−1/2n^\{\-1/2\}sampling scale\. It does not, by itself, imply that every full\-merged node has zero cross\-depth bias\. To state the required condition precisely, define the adaptive cross\-depth gap below\.

###### Definition 3\(Adaptive empirical cross\-depth gap\)\.

Fix a horizonHH, letV~H​\(s,h\)\\widetilde\{V\}\_\{H\}\(s,h\)be the depth\-hhtruncated Bellman target with terminal valueV0V\_\{0\}at depthHHfrom \([2](https://arxiv.org/html/2609.19956#S2.E2)\), and let𝒟H,n​\(s\)⊆\{0,…,H\}\\mathcal\{D\}\_\{H,n\}\(s\)\\subseteq\\\{0,\\ldots,H\\\}be the set of trajectory depths at which physical statessis visited during the firstnnsimulations of the full\-merge algorithm with horizonHH\. The empirical cross\-depth gap at horizonHHis

ΔcrossH,n=maxs:𝒟H,n​\(s\)≠∅maxh1,h2∈𝒟H,n​\(s\)\|V~H\(s,h1\)−V~H\(s,h2\)\|,\\Delta\_\{\\textsc\{cross\}\}^\{H,n\}=\\max\_\{s:\\,\\mathcal\{D\}\_\{H,n\}\(s\)\\neq\\emptyset\}\\;\\max\_\{h\_\{1\},h\_\{2\}\\in\\mathcal\{D\}\_\{H,n\}\(s\)\}\\left\|\\widetilde\{V\}\_\{H\}\(s,h\_\{1\}\)\-\\widetilde\{V\}\_\{H\}\(s,h\_\{2\}\)\\right\|,\(20\)and we writeΔcrossn≜ΔcrossH⁡\(n\),n\\Delta\_\{\\textsc\{cross\}\}^\{n\}\\triangleq\\Delta\_\{\\textsc\{cross\}\}^\{H\(n\),n\}whenH=H⁡\(n\)=⌈log⁡n/\(2​log⁡\(1/γ\)\)⌉H=H\(n\)=\\lceil\\log n/\(2\\log\(1/\\gamma\)\)\\rceil\.

###### Theorem 4\(Convergence of GS\-Power\-UCT\-F\+with adaptive horizon\)\.

Consider GS\-Power\-UCT\-F\+with node keyss, depth\-independent bonusB⁡\(n,s,a\)=C​Ts​\(n\)1/4/Ts,a​\(n\)1/2B\(n,s,a\)=C\\,T\_\{s\}\(n\)^\{1/4\}/T\_\{s,a\}\(n\)^\{1/2\}, and adaptive horizonHn≜H⁡\(n\)=⌈log⁡n/\(2​log⁡\(1/γ\)\)⌉H\_\{n\}\\triangleq H\(n\)=\\lceil\\log n/\(2\\log\(1/\\gamma\)\)\\rceil\. LetV^nHn​\(s0\)\\widehat\{V\}\_\{n\}^\{H\_\{n\}\}\(s\_\{0\}\)be the root estimate afternnsimulations at horizonHnH\_\{n\}, and assume the hypotheses of Theorem[3](https://arxiv.org/html/2609.19956#Thmtheorem3)hold for each fixed horizonHHwith sampling constantc⁡\(H\)c\(H\)and bias constantCΔC\_\{\\Delta\}\. Then for everyn≥2n\\geq 2,

\|𝔼⁡\[V^nHn​\(s0\)\]−V⋆​\(s0\)\|≤c\(Hn\)n−1/2⏟sampling\+CΔ​𝔼​\[Δcrossn\]⏟cross\-depth bias\+γHn​‖V⋆−V0‖∞⏟truncation\.\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}^\{H\_\{n\}\}\(s\_\{0\}\)\]\-V^\{\\star\}\(s\_\{0\}\)\\right\|\\leq\\underbrace\{c\(H\_\{n\}\)\\,n^\{\-1/2\}\}\_\{\\text\{sampling\}\}\+\\underbrace\{C\_\{\\Delta\}\\,\\mathbb\{E\}\[\\Delta\_\{\\textsc\{cross\}\}^\{n\}\]\}\_\{\\text\{cross\-depth bias\}\}\+\\underbrace\{\\gamma^\{H\_\{n\}\}\\\|V^\{\\star\}\-V\_\{0\}\\\|\_\{\\infty\}\}\_\{\\text\{truncation\}\}\.\(21\)SinceγHn≤n−1/2\\gamma^\{H\_\{n\}\}\\leq n^\{\-1/2\}, this simplifies to\|𝔼⁡\[V^nHn​\(s0\)\]−V⋆​\(s0\)\|≤\(c⁡\(Hn\)\+‖V⋆−V0‖∞\)/n\+CΔ​𝔼​\[Δcrossn\]\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}^\{H\_\{n\}\}\(s\_\{0\}\)\]\-V^\{\\star\}\(s\_\{0\}\)\|\\leq\(c\(H\_\{n\}\)\+\\\|V^\{\\star\}\-V\_\{0\}\\\|\_\{\\infty\}\)/\\sqrt\{n\}\+C\_\{\\Delta\}\\,\\mathbb\{E\}\[\\Delta\_\{\\textsc\{cross\}\}^\{n\}\]\. Consequently, GS\-Power\-UCT\-F\+is consistent at the root \(𝔼⁡\[V^nHn​\(s0\)\]→V⋆​\(s0\)\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}^\{H\_\{n\}\}\(s\_\{0\}\)\]\\to V^\{\\star\}\(s\_\{0\}\)\) whenever bothc\(Hn\)n−1/2→0c\(H\_\{n\}\)\\,n^\{\-1/2\}\\to 0and𝔼⁡\[Δcrossn\]→0\\mathbb\{E\}\[\\Delta\_\{\\textsc\{cross\}\}^\{n\}\]\\to 0; if in addition𝔼\[Δcrossn\]=O\(n−1/2\)\\mathbb\{E\}\[\\Delta\_\{\\textsc\{cross\}\}^\{n\}\]=O\(n^\{\-1/2\}\)andc⁡\(Hn\)c\(H\_\{n\}\)grows at most polylogarithmically innn, the rate isO⁡\(c⁡\(Hn\)/n\)O\(c\(H\_\{n\}\)/\\sqrt\{n\}\)\.

## 5Experiments

##### Planning setting and scope\.

We study online model\-based replanning: at each decision, a planner receives a fixed simulation budget and calls a generative model of the current MDP\. No persistent value function is trained across episodes\. TD\(λ\\lambda\),nn\-step TD, RTDP, and Dyna instead learn a value function and/or model across interaction, so their learning resource is not directly comparable to a per\-decision simulation budget\. They are therefore outside this empirical comparison; a learned value function can nevertheless be used as the terminal evaluatorV0V\_\{0\}\.

We evaluate our two graph\-based variants on stochastic MDP environments and compare them against four baselines\.UCT\[[7](https://arxiv.org/html/2609.19956#bib.bib7)\]is the classical tree\-based MCTS algorithm with a logarithmic exploration bonus and arithmetic\-mean backup\.MENTS\[[15](https://arxiv.org/html/2609.19956#bib.bib15)\]incorporates a maximum entropy framework with a softmax backup to facilitate entropy\-regularized exploration\.Stochastic\-Power\-UCT\[[5](https://arxiv.org/html/2609.19956#bib.bib5)\]\(P\-UCT in the figure and tables\) extends the polynomial\-bonus design with power mean value backup, establishingO\(n−1/2\)O\(n^\{\-1/2\}\)concentration for stochastic MDPs while remaining tree\-based\.GBOP\[[8](https://arxiv.org/html/2609.19956#bib.bib8)\]is the graph\-based baseline with an OFU planning style\. OurGS\-Power\-UCT\(Algorithm[1](https://arxiv.org/html/2609.19956#alg1)\) combines the polynomial bonus and power mean backup with a depth\-augmented graph that merges same\-depth transpositions, whileGS\-Power\-UCT\-F\+relaxes the merging rule to share a single node per physical state across depths\. For F\+, at every reported budgetnnwe setH=H⁡\(n\)H=H\(n\)once before the search and keep it fixed for allnnsimulations\.

321285122k000\.20\.20\.40\.40\.60\.6RewardFrozenLake321285122k00224466RewardPassenger Grid321285122k224466RewardFactored River Swim

321285122k5510101515SimulationsRewardSysAdmin Ring321285122k0\.20\.20\.40\.40\.60\.6SimulationsRewardFourRooms

UCTP\-UCTMENTSGS\-Power\-UCTGS\-Power\-UCT\-F\+GBOP

Figure 1:Planning performance versus simulation budget across five stochastic MDPs\. Graph\-based methods are emphasized with solid curves; tree\-based baselines are shown with lighter dashed/dotted curves\.
##### Results\.

Figure[1](https://arxiv.org/html/2609.19956#S5.F1)shows that depth\-augmented GS\-Power\-UCT is particularly effective in these stochastic domains at small and moderate simulation budgets, where same\-depth transpositions can reuse observations before the budget is exhausted\. GS\-Power\-UCT\-F\+is competitive in four of five domains but underperforms inPassenger Grid, consistent with its additional cross\-depth\-bias term\. Thus full merging is most appropriate when the cross\-depth gap is small \(for example, with a strongV0V\_\{0\}or nearby relevant depths\); the depth\-augmented variant is the robust choice when this is uncertain\. The1/τh1/\\tau\_\{h\}factor in Theorem[2](https://arxiv.org/html/2609.19956#Thmtheorem2)is a representation\-level sample\-sharing identity under the same trajectories, not a predicted performance multiplier for independently run planners\.

## 6Limitations

WhileGS\-Power\-UCTdemonstrates robust theoretical properties, its current formulation involves several caveats that merit further discussion\.

- •Non\-negative Reward Constraint:The power\-mean backup assumes rewardsR∈\[0,Rmax\]R\\in\[0,R\_\{\\max\}\]\. Applying GS\-Power\-UCT to environments with signed rewards would require affine shifts or modified backup operators to ensure value targets remain well\-defined\.
- •State sharing helps or hurts:Sharing is useful when multiple simulated trajectories reach the same physical state at the same depth: depth\-augmented GS\-Power\-UCT then pools their samples without mixing finite\-horizon targets\. The identity in Theorem[2](https://arxiv.org/html/2609.19956#Thmtheorem2)is representation\-level—it does not guarantee that an independently run graph search dominates an independently run tree search\. With few or no same\-depth transpositions, sharing provides little reuse while retaining hash\-table and graph\-bookkeeping overhead\. Full merging can further reduce the graph size, but it can hurt by mixing targets with different remaining horizons; its error includes the cross\-depth term
- •Computational and Memory Overhead:Maintaining global statistics and hash\-based lookups introduces additional overhead\. Under depth augmentation, memory usage can scale up to\|𝒮\|⋅H\|\\mathcal\{S\}\|\\cdot Hnodes, which may increase the wall\-clock cost in large\-scale settings despite improved sample efficiency\. A detailed empirical breakdown of computational and memory overhead is presented in Appendix[E\.5](https://arxiv.org/html/2609.19956#A5.SS5)\.

## 7Related Work

##### MCTS with theoretical guarantees\.

The theoretical foundations of UCT\[[7](https://arxiv.org/html/2609.19956#bib.bib7)\]were revisited by[Shah et al\. \[10\]](https://arxiv.org/html/2609.19956#bib.bib10),[Shah et al\. \[11\]](https://arxiv.org/html/2609.19956#bib.bib11), who identified a gap in the analysis of logarithmic exploration bonuses and established polynomial convergence guarantees for Fixed\-Depth\-MCTS using polynomial bonuses\. Complementary work developed a unified analysis of value backup and exploration through power means and convex regularization\[[24](https://arxiv.org/html/2609.19956#bib.bib24)\]\. For stochastic MDPs,[Dam et al\. \[5\]](https://arxiv.org/html/2609.19956#bib.bib5)established convergence guarantees for power\-mean value estimation, with subsequent work extending theoretical guarantees to continuous stochastic planning\[[25](https://arxiv.org/html/2609.19956#bib.bib25)\]and robust planning under reward and transition uncertainty\[[26](https://arxiv.org/html/2609.19956#bib.bib26)\]\. We extend this line with the first convergence guarantees for graph\-based MCTS in stochastic settings\.

##### Online planning and reinforcement learning\.

TD\(λ\\lambda\),nn\-step TD, Dyna, and RTDP combine learning from interaction with value or model updates\[[23](https://arxiv.org/html/2609.19956#bib.bib23),[22](https://arxiv.org/html/2609.19956#bib.bib22),[16](https://arxiv.org/html/2609.19956#bib.bib16)\]\. They are complementary to the present work: GS\-Power\-UCT allocates a fresh online planning budget from a generative model, while a learned value function from such methods can instantiateV0V\_\{0\}\.

##### Generative\-model planning\.

SmoothCruiser\[[27](https://arxiv.org/html/2609.19956#bib.bib27)\]exploits entropy\-regularized Bellman smoothness to obtain sample\-complexity guarantees, while SecondOrderSmoothCruiser\[[28](https://arxiv.org/html/2609.19956#bib.bib28)\]develops this approach through optimal\-transport Bellman smoothing and second\-order value estimation\. Sparse sampling\[[20](https://arxiv.org/html/2609.19956#bib.bib20)\], OLOP\[[17](https://arxiv.org/html/2609.19956#bib.bib17)\], and TrailBlazer\[[19](https://arxiv.org/html/2609.19956#bib.bib19)\]study planning with a simulator, including methods that address large or even infinite successor spaces\. Our concentration proof requires finite successor support and focuses on sharing samples across identical state\-depth pairs in the search graph\.

##### Graph\-based planning\.

State merging in planning has appeared in various forms: state aggregation by partitioning\[[6](https://arxiv.org/html/2609.19956#bib.bib6)\], MCGS with theoretical analysis for deterministic MDPs\[[8](https://arxiv.org/html/2609.19956#bib.bib8)\], belief\-state merging in POMDPs without theoretical analysis\[[1](https://arxiv.org/html/2609.19956#bib.bib1)\], and transposition\-aware/UCD search in game DAGs\[[18](https://arxiv.org/html/2609.19956#bib.bib18),[21](https://arxiv.org/html/2609.19956#bib.bib21)\]\. Ours provides the first theoretical convergence analysis for graph\-based MCTS with UCB\-style exploration in stochastic MDPs\.

##### Power mean estimation\.

The power mean was introduced for MCTS by[Dam et al\. \[4\]](https://arxiv.org/html/2609.19956#bib.bib4)and later analyzed in[Dam et al\. \[5\]](https://arxiv.org/html/2609.19956#bib.bib5); closely related are MENTS\[[15](https://arxiv.org/html/2609.19956#bib.bib15)\]and its Rényi/Tsallis variants RENTS and TENTS\. Our work is the first to combine power mean estimation with graph\-based planning\.

## 8Conclusion

We introduced Graph\-Based Stochastic Power\-UCT, the first MCTS algorithm with convergence guarantees that combines graph\-based state merging with power mean value estimation for stochastic MDPs\. Our key technical contribution is the graphQQ\-concentration analysis, which allows child estimates to use visits aggregated from multiple same\-depth parents\. This yields the sameO\(n−1/2\)O\(n^\{\-1/2\}\)fixed\-horizon root rate as tree\-based Stochastic\-Power\-UCT\. At the representation level, unrolling the same graph trajectories into a tree shows an explicit sample\-sharing advantage: merged graph nodes receive the union of the samples assigned to their tree copies\. This can reduce the proof\-bound terms associated with transposed states, although it should not be interpreted as a dominance guarantee over an independently run tree\-search algorithm\.

Several directions for future work are promising\. First, connecting the graph\-dependent improvement to*spectral properties*of the state graph \(effective resistance, spectral gap\) would provide more interpretable complexity bounds\. Second, extending the analysis to*approximate*state merging for continuous state spaces would broaden the applicability\. Third, combining graph\-based planning with learned value functions \(as in AlphaZero\) could yield practical improvements for large\-scale problems\. Finally, extending the framework to*adversarial*settings \(e\.g\., two\-player games with graph transpositions\) is a natural next step\.

## References

- \[1\]J\. Ballesteros, L\. Merino, M\. A\. Trujillo, A\. Viguria, and A\. Ollero\.Improving the efficiency of online POMDPs by using belief similarity measures\.In*Proc\. of ICRA*, 2013\.
- \[2\]C\. Browne, E\. Powley, D\. Whitehouse, et al\.A survey of Monte Carlo tree search methods\.*IEEE Trans\. Comput\. Intell\. AI Games*, 4\(1\):1–43, 2012\.
- \[3\]R\. Coulom\.Efficient selectivity and backup operators in Monte\-Carlo tree search\.In*Int\. Conf\. Computers and Games*, pp\. 72–83, 2006\.
- \[4\]T\. Dam, P\. Klink, C\. D’Eramo, J\. Peters, and J\. Pajarinen\.Generalized mean estimation in Monte\-Carlo tree search\.*arXiv preprint arXiv:1911\.00384*, 2019\.
- \[5\]T\. Dam, O\.\-A\. Maillard, and E\. Kaufmann\.Power mean estimation in stochastic Monte\-Carlo tree search\.*arXiv preprint arXiv:2406\.02235*, 2024\.
- \[6\]J\. Hostetler, A\. Fern, and T\. Dietterich\.State aggregation in Monte Carlo tree search\.In*Proc\. of AAAI*, 2014\.
- \[7\]L\. Kocsis and C\. Szepesvári\.Bandit based Monte\-Carlo planning\.In*Proc\. of ECML*, pp\. 282–293, 2006\.
- \[8\]E\. Leurent and O\.\-A\. Maillard\.Monte\-Carlo graph search: the value of merging similar states\.In*Proc\. of ACML*, pp\. 577–592, 2020\.
- \[9\]J\. Schrittwieser, I\. Antonoglou, T\. Hubert, et al\.Mastering Atari, Go, chess and shogi by planning with a learned model\.*Nature*, 588\(7839\):604–609, 2020\.
- \[10\]D\. Shah, Q\. Xie, and Z\. Xu\.Non\-asymptotic analysis of Monte Carlo tree search\.In*SIGMETRICS*, pp\. 31–32, 2020\.
- \[11\]D\. Shah, Q\. Xie, and Z\. Xu\.Nonasymptotic analysis of Monte Carlo tree search\.*Operations Research*, 70\(6\):3234–3260, 2022\.
- \[12\]D\. Silver, A\. Huang, C\. J\. Maddison, et al\.Mastering the game of Go with deep neural networks and tree search\.*Nature*, 529\(7587\):484–489, 2016\.
- \[13\]D\. Silver, J\. Schrittwieser, K\. Simonyan, et al\.Mastering the game of Go without human knowledge\.*Nature*, 550\(7676\):354–359, 2017\.
- \[14\]T\. Weissman, E\. Ordentlich, G\. Seroussi, S\. Verdu, and M\. J\. Weinberger\.Inequalities for theL1L\_\{1\}deviation of the empirical distribution\.*Hewlett\-Packard Labs, Tech\. Rep\.*, 2003\.
- \[15\]C\. Xiao, R\. Huang, J\. Mei, D\. Schuurmans, and M\. Müller\.Maximum entropy Monte\-Carlo planning\.In*NeurIPS*, 2019\.
- \[16\]A\. G\. Barto, S\. J\. Bradtke, and S\. P\. Singh\.Learning to act using real\-time dynamic programming\.*Artificial Intelligence*, 72\(1–2\):81–138, 1995\.
- \[17\]S\. Bubeck and R\. Munos\.Open loop optimistic planning\.In*Proceedings of the 23rd Conference on Learning Theory*, 2010\.
- \[18\]B\. E\. Childs, J\. H\. Brodeur, and L\. Kocsis\.Transpositions and move groups in Monte Carlo tree search\.In*Proceedings of the IEEE Symposium on Computational Intelligence and Games*, pp\. 389–395, 2008\.
- \[19\]J\.\-B\. Grill, M\. Valko, and R\. Munos\.Blazing the trails before beating the path: Sample\-efficient Monte\-Carlo planning\.In*NeurIPS*, 2016\.
- \[20\]M\. J\. Kearns, Y\. Mansour, and A\. Y\. Ng\.A sparse sampling algorithm for near\-optimal planning in large Markov decision processes\.*Machine Learning*, 49\(2–3\):193–208, 2002\.
- \[21\]A\. Saffidine, T\. Cazenave, and J\. Méhat\.UCD: Upper confidence bound for rooted directed acyclic graphs\.*Knowledge\-Based Systems*, 34:26–33, 2011\.
- \[22\]R\. S\. Sutton\.Integrated architectures for learning, planning, and reacting based on approximating dynamic programming\.In*Proceedings of the Seventh International Conference on Machine Learning*, pp\. 216–224, 1990\.
- \[23\]R\. S\. Sutton and A\. G\. Barto\.*Reinforcement Learning: An Introduction*\.MIT Press, second edition, 2018\.
- \[24\]T\. Dam, C\. D’Eramo, J\. Peters, and J\. Pajarinen\.A unified perspective on value backup and exploration in Monte\-Carlo tree search\.*Journal of Artificial Intelligence Research*, 81:511–577, 2024\.
- \[25\]T\. Q\. Dam\.Power mean estimation in stochastic continuous Monte\-Carlo tree search\.In*Proceedings of the 42nd International Conference on Machine Learning*, pp\. 12344–12376, 2025\.
- \[26\]T\. Q\. Dam, K\. Panaganti, B\. Driss, and A\. Wierman\.Online robust reinforcement learning through Monte\-Carlo planning\.In*Proceedings of the 42nd International Conference on Machine Learning*, pp\. 12314–12343, 2025\.
- \[27\]J\.\-B\. Grill, O\. D\. Domingues, P\. Ménard, R\. Munos, and M\. Valko\.Planning in entropy\-regularized Markov decision processes and games\.In*Advances in Neural Information Processing Systems*, volume 32, 2019\.
- \[28\]T\. Dam\.Second\-order smooth planning with optimal\-transport Bellman smoothing\.In*Proceedings of the 43rd International Conference on Machine Learning*, 2026\.

Appendix of “Graph\-Based Stochastic Power\-UCT: Monte\-Carlo Graph Search with Power Mean Estimation”

Table of Contents

## Appendix AStanding Assumptions

This appendix collects the conditions used by the concentration results\. They do not restrict the topology of the MDP: cyclic transitions and self\-loops remain allowed\.

###### Assumption 1\(Standing MDP and evaluator conditions\)\.

1\.\(A\-Finite\)γ∈\[0,1\)\\gamma\\in\[0,1\), the planning horizon is finite, every𝒜s\\mathcal\{A\}\_\{s\}is finite with\|𝒜s\|≤K\|\\mathcal\{A\}\_\{s\}\|\\leq K, and everyP\(⋅∣s,a\)P\(\\cdot\\mid s,a\)has finite support\. Thus a \(possibly countable\) state space has a finiteHH\-reachable graph\. Rewards lie in\[0,Rmax\]\[0,R\_\{\\max\}\]; hence all rollout and backed\-up values are bounded byL≜Rmax/\(1−γ\)L\\triangleq R\_\{\\max\}/\(1\-\\gamma\)\.2\.\(A\-Fresh\)A generative\-model call at a fixed state–depth–action query returns a fresh reward–successor pair\. Successive pairs at that query are i\.i\.d\. from the stationary conditional law\. The reward and successor within one pair need not be independent\.3\.\(A\-Rollout\)Independent calls to the terminal evaluator returnZj​\(s\)∼π0​\(s\)Z\_\{j\}\(s\)\\sim\\pi\_\{0\}\(s\)with𝔼⁡\[Zj​\(s\)\]=V0​\(s\)\\mathbb\{E\}\[Z\_\{j\}\(s\)\]=V\_\{0\}\(s\)and0≤Zj​\(s\)≤L0\\leq Z\_\{j\}\(s\)\\leq L\. A call initializes a new boundary node; it is not an i\.i\.d\. assertion about adaptively updated internal estimates\.

##### Local proof hypotheses \(induction hypotheses\)\.

\(H\-Q\)In Lemma[1](https://arxiv.org/html/2609.19956#Thmlemma1), the child concentration premise is used in time\-uniform form: if an adapted traversal selects a child’s global countNN, thenℙ⁡\(\|V^N−V\|\>ε,N≥r\)≤c​r−α​ε−β\\mathbb\{P\}\(\|\\widehat\{V\}\_\{N\}\-V\|\>\\varepsilon,\\,N\\geq r\)\\leq c\\,r^\{\-\\alpha\}\\varepsilon^\{\-\\beta\}for everyr≥1r\\geq 1\. This induction hypothesis supplies concentration at a possibly random global child count; it does not declare adaptive child estimates i\.i\.d\.\(H\-V\)In Lemma[5](https://arxiv.org/html/2609.19956#Thmlemma5), the displayed bias\-radius condition compares its effective action targets with the depth\-specific targets\. Corollary[2](https://arxiv.org/html/2609.19956#Thmcorollary2)instantiates it using the explicit cross\-depth bound\. For a fixed successor support of sizeMM, graph\-QQconstants may depend on2M2^\{M\}and inverse successor probabilities \(for example,∑mpm−α\\sum\_\{m\}p\_\{m\}^\{\-\\alpha\}\); rare successors affect constants, not the stated rate\. The following table records where these standing conditions and local hypotheses are used\.

Table 3:Assumption\-discharge table for the analysis\.Result or proof termCondition and roleLeaf concentration\(A\-Rollout\) gives bounded i\.i\.d\. terminal\-evaluator calls, so Hoeffding applies to those calls\.Graph\-QQreward term\(A\-Finite\) bounds rewards; \(A\-Fresh\) makes the local reward–successor\-pair stream i\.i\.d\. at a fixed parent\-action query\.Graph\-QQtransition termA1A\_\{1\}\(A\-Finite\) gives finitely many successor categories, and \(A\-Fresh\) gives the i\.i\.d\. successor stream required by the multinomial deviation bound\.Graph\-QQchild\-value termA2A\_\{2\}\(H\-Q\) applies the child concentration premise at its global effective count\. Other\-parent visits can increase that count; no i\.i\.d\. claim is made for the adaptive child estimates\.Node and root concentrationThe graph\-QQlemma, the power\-mean induction\.Sample\-sharing theoremThis is a deterministic representation identity under the same realised trajectories; it introduces no additional stochastic assumption\.Full merge and F\+\(H\-V\) is instantiated by the explicit cross\-depth bound; the stated bounds also require their empirical\-target and cross\-depth\-gap hypotheses\. For F\+,H=H⁡\(n\)H=H\(n\)is fixed for all simulations in a search with budgetnn\.

## Appendix BNotation

Table 4:Notation used throughout the paper\.SymbolMeaningMDP, returns, and value functionsℳ=⟨𝒮,𝒜,R,P,γ⟩\\mathcal\{M\}=\\langle\\mathcal\{S\},\\mathcal\{A\},R,P,\\gamma\\rangleDiscounted MDP with state space𝒮\\mathcal\{S\}, action space𝒜\\mathcal\{A\}, conditional\-mean rewardRR, transition kernelPP, and discountγ∈\[0,1\)\\gamma\\in\[0,1\)\.𝒜s,K,Rmax,L\\mathcal\{A\}\_\{s\},K,R\_\{\\max\},LAdmissible actions atss,K=maxs⁡\|𝒜s\|K=\\max\_\{s\}\|\\mathcal\{A\}\_\{s\}\|, reward bound, and return boundL=Rmax/\(1−γ\)L=R\_\{\\max\}/\(1\-\\gamma\)\.s0,s,s′,a,h;i,j,m,t,ns\_\{0\},s,s^\{\\prime\},a,h;\\ i,j,m,t,nRoot state, generic/current/successor states, action, trajectory depth, and generic sample, successor, visit, or simulation indices\.H,H⁡\(n\),HnH,H\(n\),H\_\{n\}Fixed planning horizon; adaptive horizonH⁡\(n\)=⌈log⁡n/\(2​log⁡\(1/γ\)\)⌉H\(n\)=\\lceil\\log n/\(2\\log\(1/\\gamma\)\)\\rceil; and shorthandHn≜H⁡\(n\)H\_\{n\}\\triangleq H\(n\)\. Within an F\+search of budgetnn,H⁡\(n\)H\(n\)is fixed\.R⁡\(s,a,s′\),r⁡\(s,a\);r,rt,RiR\(s,a,s^\{\\prime\}\),r\(s,a\);\\ r,r\_\{t\},R\_\{i\}Conditional\-mean and expected immediate rewards; sampled reward, reward backed up at simulationtt, and theii\-th sampled reward in the full\-merge proof\.π0,V0,Zj,z\\pi\_\{0\},V\_\{0\},Z\_\{j\},zTerminal evaluator/policy, its value, itsjj\-th independent output, and a realized rollout/evaluation sample\.𝔼,ℙ,∥⋅∥∞,𝟏\\mathbb\{E\},\\mathbb\{P\},\\\|\\cdot\\\|\_\{\\infty\},\\mathbf\{1\}Expectation, probability, sup norm, and indicator function\.ℬ\\mathcal\{B\}Bellman optimality operator:\(ℬ​V\)​\(s\)=max⁡∑s′a∈𝒜s⁡P⁡\(s′\|s,a\)​\[R⁡\(s,a,s′\)\+γ​V​\(s′\)\]\(\\mathcal\{B\}V\)\(s\)=\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}\\sum\_\{s^\{\\prime\}\}P\(s^\{\\prime\}\|s,a\)\[R\(s,a,s^\{\\prime\}\)\+\\gamma V\(s^\{\\prime\}\)\]\.V⋆,Q⋆V^\{\\star\},Q^\{\\star\}Infinite\-horizon optimal value and action\-value functions\.V~​\(s,h\),Q~​\(s,h,a\),V~H​\(s,h\)\\widetilde\{V\}\(s,h\),\\widetilde\{Q\}\(s,h,a\),\\widetilde\{V\}\_\{H\}\(s,h\)Depth\-hhtruncated Bellman targets with terminal valueV0V\_\{0\};V~H\\widetilde\{V\}\_\{H\}displays the horizon explicitly\.V^t​\(s,h\),Q^t​\(s,h,a\)V^t​\(s\),Q^t​\(s,a\)\\begin\{subarray\}\{c\}\\widehat\{V\}\_\{t\}\(s,h\),\\,\\widehat\{Q\}\_\{t\}\(s,h,a\)\\\\\[\-1\.0pt\] \\widehat\{V\}\_\{t\}\(s\),\\,\\widehat\{Q\}\_\{t\}\(s,a\)\\end\{subarray\}Empirical estimates afterttvisits in the depth\-augmented and full\-merge variants, respectively\.ppPower\-mean exponent\. Rate theorems use finitep∈\[1,∞\)p\\in\[1,\\infty\);p=∞p=\\inftyis an algorithmic implementation limit\.Search graph, unrolling, and sample sharingϕ⁡\(s,h\)\\phi\(s,h\)Node\-key mapping:ϕ⁡\(s,h\)=\(s,h\)\\phi\(s,h\)=\(s,h\)for depth augmentation andϕ⁡\(s,h\)=s\\phi\(s,h\)=sfor full merging\.𝒢n=\(𝒩n,ℰn\),𝒩h\\mathcal\{G\}\_\{n\}=\(\\mathcal\{N\}\_\{n\},\\mathcal\{E\}\_\{n\}\),\\ \\mathcal\{N\}\_\{h\}Search graph afternnsimulations, its node and edge sets, and the set of discovered depth\-hhnodes\.\(s,h\),𝒢̊n,∂𝒢n,ℋ\(s,h\),\\mathring\{\\mathcal\{G\}\}\_\{n\},\\partial\\mathcal\{G\}\_\{n\},\\mathcal\{H\}Depth\-augmented node; internal and boundary node sets; and implementation hash map from a node key to its graph node\.Parents​\(s,h\)\\textsc\{Parents\}\(s,h\)Parent\-action pairs with an edge into depth\-augmented node\(s,h\)\(s,h\)\.𝒯⁡\(𝒢\),𝒯h;ϕh:𝒯h→𝒩h\\mathcal\{T\}\(\\mathcal\{G\}\),\\mathcal\{T\}\_\{h\};\\ \\phi\_\{h\}:\\mathcal\{T\}\_\{h\}\\to\\mathcal\{N\}\_\{h\}Unrolled tree of𝒢\\mathcal\{G\}, its depth\-hhnodes, and projection of a tree copy to its graph node\.v,u,𝒞⁡\(v\)v,u,\\mathcal\{C\}\(v\)Graph node, tree copy, and merged\-copy class𝒞⁡\(v\)=ϕh−1​\(v\)\\mathcal\{C\}\(v\)=\\phi\_\{h\}^\{\-1\}\(v\)\.τh,Nh𝒯\\tau\_\{h\},N\_\{h\}^\{\\mathcal\{T\}\}Transposition ratioτh=\|𝒩h\|/Nh𝒯\\tau\_\{h\}=\|\\mathcal\{N\}\_\{h\}\|/N\_\{h\}^\{\\mathcal\{T\}\}, whereNh𝒯=\|𝒯h\|N\_\{h\}^\{\\mathcal\{T\}\}=\|\\mathcal\{T\}\_\{h\}\|is the number of unrolled\-tree nodes at depthhh\.Tv𝒢,Tu𝒯,Tv,a𝒢,Tu,a𝒯,Nh​\(n\)T\_\{v\}^\{\\mathcal\{G\}\},T\_\{u\}^\{\\mathcal\{T\}\},T\_\{v,a\}^\{\\mathcal\{G\}\},T\_\{u,a\}^\{\\mathcal\{T\}\},N\_\{h\}\(n\)Graph/tree node and action visit counts in the same\-trajectory comparison, and the common total number of visits reaching depthhh\.chℛ,cQ,hℛ,Φhc\_\{h\}^\{\\mathcal\{R\}\},c\_\{Q,h\}^\{\\mathcal\{R\}\},\\Phi\_\{h\}Proof\-generated value and action\-value concentration constants and their monotone Power\-UCT aggregation map, forℛ∈\{𝒢,𝒯\}\\mathcal\{R\}\\in\\\{\\mathcal\{G\},\\mathcal\{T\}\\\}\.Visit counts, bonuses, and algorithmic parametersTs,h​\(n\),Ts,h,a​\(n\)Ts,h,as′​\(n\)\\begin\{subarray\}\{c\}T\_\{s,h\}\(n\),\\,T\_\{s,h,a\}\(n\)\\\\\[\-1\.0pt\] T\_\{s,h,a\}^\{s^\{\\prime\}\}\(n\)\\end\{subarray\}Depth\-augmented node visits, action selections, and observed transitions\(\(s,h\),a\)→\(s′,h\+1\)\(\(s,h\),a\)\\to\(s^\{\\prime\},h\+1\)\.Ts​\(n\),Ts,a​\(n\),Ts,as′​\(n\),Ts,a,h​\(n\)T\_\{s\}\(n\),T\_\{s,a\}\(n\),T\_\{s,a\}^\{s^\{\\prime\}\}\(n\),T\_\{s,a,h\}\(n\)Full\-merge state, state\-action, successor\-transition, and depth\-resolved state\-action visit counts\.B⁡\(n,s,a\),Bh​\(n,s,a\),CB\(n,s,a\),B\_\{h\}\(n,s,a\),CExploration bonus \(with depth\-indexed form when applicable\) and exploration constant\. For F\+,B⁡\(n,s,a\)=C​Ts​\(n\)1/4/Ts,a​\(n\)1/2B\(n,s,a\)=CT\_\{s\}\(n\)^\{1/4\}/T\_\{s,a\}\(n\)^\{1/2\}\.bh,αh,βh;b,α\+,β\+b\_\{h\},\\alpha\_\{h\},\\beta\_\{h\};\\ b,\\alpha\_\{\+\},\\beta\_\{\+\}Depth\-indexed Power\-UCT parameters and their local full\-merge counterparts\.ThashT\_\{\\textsc\{hash\}\}Cost of one hash\-table lookup in the runtime bound\.a^n\\hat\{a\}\_\{n\}Recommended root action afternnsimulations\.Graph\-QQconcentrationV^n→n→∞α,βV;α,β,c,ε\\widehat\{V\}\_\{n\}\\xrightarrow\[n\\to\\infty\]\{\\alpha,\\beta\}V;\\ \\alpha,\\beta,c,\\varepsilonPolynomial concentration:ℙ⁡\(\|V^n−V\|\>ε\)≤c​n−α​ε−β\\mathbb\{P\}\(\|\\widehat\{V\}\_\{n\}\-V\|\>\\varepsilon\)\\leq cn^\{\-\\alpha\}\\varepsilon^\{\-\\beta\}for everyn≥1n\\geq 1andε\>0\\varepsilon\>0\.M,\[M\],sm,pm,𝒑,𝒑^nM,\[M\],s\_\{m\},p\_\{m\},\\bm\{p\},\\widehat\{\\bm\{p\}\}\_\{n\}Successor\-support size,\[M\]=\{1,…,M\}\[M\]=\\\{1,\\ldots,M\\\}, successor states,pm=P⁡\(sm∣s,a\)p\_\{m\}=P\(s\_\{m\}\\mid s,a\), and true/empirical successor\-probability vectors\.Xi,Si,μ,X¯n,𝑽,𝑽^nX\_\{i\},S\_\{i\},\\mu,\\bar\{X\}\_\{n\},\\bm\{V\},\\widehat\{\\bm\{V\}\}\_\{n\}Local reward\-successor sample, its mean, empirical reward mean, vector of successor targets, and vector of their current estimates\.Nmn,p^m,nN\_\{m\}^\{n\},\\widehat\{p\}\_\{m,n\}Local successor countNmn=∑i=1n𝟏\{Si=sm\}N\_\{m\}^\{n\}=\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{S\_\{i\}=s\_\{m\}\\\}and empirical probabilityp^m,n=Nmn/n\\widehat\{p\}\_\{m,n\}=N\_\{m\}^\{n\}/n\.Tsmext​\(n\),Tsmeff​\(n\)T\_\{s\_\{m\}\}^\{\\textsc\{ext\}\}\(n\),T\_\{s\_\{m\}\}^\{\\textsc\{eff\}\}\(n\)External and effective child visits;Tsmeff​\(n\)=Nmn\+Tsmext​\(n\)T\_\{s\_\{m\}\}^\{\\textsc\{eff\}\}\(n\)=N\_\{m\}^\{n\}\+T\_\{s\_\{m\}\}^\{\\textsc\{ext\}\}\(n\)\. Subscripts may be abbreviated tommin proofs\.A1,A2,ℰm,rmA\_\{1\},A\_\{2\},\\mathcal\{E\}\_\{m\},r\_\{m\}Empirical\-transition and child\-value terms in the graph\-QQdecomposition; the high\-local\-count event and its threshold\.BQ,KmB\_\{Q\},K\_\{m\}Uniform graph\-QQerror bound and proof constant used to dominate exponential tail terms\.Cross\-depth and empirical full\-merge targets𝒟⁡\(s\),𝒟H,n​\(s\),hmin​\(s\),hmax​\(s\)\\mathcal\{D\}\(s\),\\mathcal\{D\}\_\{H,n\}\(s\),h\_\{\\min\}\(s\),h\_\{\\max\}\(s\)Visited depths ofss, their empirical counterpart for horizonHH, and their minimum and maximum\.δ⁡\(s\),Δcross\\delta\(s\),\\Delta\_\{\\textsc\{cross\}\}Local and global cross\-depth gaps:δ⁡\(s\)=maxh1,h2∈𝒟⁡\(s\)⁡\|V~​\(s,h1\)−V~​\(s,h2\)\|\\delta\(s\)=\\max\_\{h\_\{1\},h\_\{2\}\\in\\mathcal\{D\}\(s\)\}\|\\widetilde\{V\}\(s,h\_\{1\}\)\-\\widetilde\{V\}\(s,h\_\{2\}\)\|andΔcross=maxs⁡δ⁡\(s\)\\Delta\_\{\\textsc\{cross\}\}=\\max\_\{s\}\\delta\(s\)\.ΔcrossH,n,Δcrossn,CΔ\\Delta\_\{\\textsc\{cross\}\}^\{H,n\},\\Delta\_\{\\textsc\{cross\}\}^\{n\},C\_\{\\Delta\}Empirical cross\-depth gap, its adaptive\-horizon formΔcrossH⁡\(n\),n\\Delta\_\{\\textsc\{cross\}\}^\{H\(n\),n\}, and the full\-merge bias constant\.ωn,h​\(s,a\),Bh​V,𝒯F,nH\\omega\_\{n,h\}\(s,a\),B\_\{h\}V,\\mathcal\{T\}\_\{F,n\}^\{H\}Empirical depth\-mixture weight, terminal\-value operator, and empirical full\-merge Bellman operator\.V¯​\(s\),ρi\\bar\{V\}\(s\),\\rho\_\{i\}Limiting two\-depth mixture and its limiting depth weights in the irreducible\-bias proposition\.V¯n,Q¯n\\bar\{V\}\_\{n\},\\bar\{Q\}\_\{n\}Unique fixed point of𝒯F,nH\\mathcal\{T\}\_\{F,n\}^\{H\}and its associated empirical full\-mergeQQ\-target\.BF,nV​\(s,h\)B\_\{F,n\}^\{V\}\(s,h\)Local full\-merge target mismatch\|V¯n​\(s\)−V~​\(s,h\)\|\|\\bar\{V\}\_\{n\}\(s\)\-\\widetilde\{V\}\(s,h\)\|\.δQ,t​\(s,a,h\),δQ,n,BΔ,BΔ,n\\delta\_\{Q,t\}\(s,a;h\),\\delta\_\{Q,n\},B\_\{\\Delta\},B\_\{\\Delta,n\}QQ\-level cross\-depth drift, its uniformnn\-simulation bound, and the corresponding bias radii;BΔ=γ​Δcross/\(1−γ\)B\_\{\\Delta\}=\\gamma\\Delta\_\{\\textsc\{cross\}\}/\(1\-\\gamma\)andBΔ,n=δQ,n/\(1−γ\)B\_\{\\Delta,n\}=\\delta\_\{Q,n\}/\(1\-\\gamma\)\.Full\-merge proof auxiliariesℱi,0⊂ℱi,1⊂ℱi,2\\mathcal\{F\}\_\{i,0\}\\subset\\mathcal\{F\}\_\{i,1\}\\subset\\mathcal\{F\}\_\{i,2\}Filtration before theii\-th transition draw, after that draw, and after the recursive child call\.Ri,Si,Wi,YiR\_\{i\},S\_\{i\},W\_\{i\},Y\_\{i\}Reward, successor, recursive child return, and backed\-up returnYi=Ri\+γ​WiY\_\{i\}=R\_\{i\}\+\\gamma W\_\{i\}in the robust full\-merge proof\.Ai,ei,bi,ξiA\_\{i\},e\_\{i\},b\_\{i\},\\xi\_\{i\}Centered transition\-reward term, child\-estimation error, its predictable part, and its centered part\.Ji,ρ,ηi,G,ng​\(t\)J\_\{i\},\\rho,\\eta\_\{i\},G,n\_\{g\}\(t\)Local successor\-depth occurrence count,ρ=α/β\\rho=\\alpha/\\beta, integration threshold, number of successor\-depth groups, and group count up to timett\.LR,LV,LA,Lξ,Cch,Cρ,κ,σQL\_\{R\},L\_\{V\},L\_\{A\},L\_\{\\xi\},C\_\{\\mathrm\{ch\}\},C\_\{\\rho\},\\kappa,\\sigma\_\{Q\}Robust\-proof range, increment, predictable\-bias, averaging, and martingale\-deviation constants\.qa,q¯a,v⋆,v¯,Bq\_\{a\},\\bar\{q\}\_\{a\},v\_\{\\star\},\\bar\{v\},BDepth\-specific and effective action targets, their maximizing values, and the local bias radius in hypothesis \(H\-V\)\.α¯,β¯,αV,βV,CQ,CV\\bar\{\\alpha\},\\bar\{\\beta\},\\alpha\_\{V\},\\beta\_\{V\},C\_\{Q\},C\_\{V\}DerivedQQ\- and value\-concentration exponents and constants in the robust full\-merge lemmas\.Xn,ηn,CsampX\_\{n\},\\eta\_\{n\},C\_\{\\mathrm\{samp\}\}Root absolute error, tail\-integration threshold, and resulting sampling\-error constant in the full\-merge rate proof\.Table 4:Notation used throughout the paper \(continued\)\.
## Appendix CDetailed Algorithms

### C\.1Graph\-Based Stochastic Power\-UCT and Implementation Specification

Algorithm 1Graph\-Based Stochastic Power\-UCT \(GS\-Power\-UCT\)0:Root state

s0s\_\{0\}, budget

nn, horizon

HH, power

pp, playout policy

π0\\pi\_\{0\}, exploration constant

CC
1:

𝒢←\(\{\(s0,0\)\},∅\)\\mathcal\{G\}\\leftarrow\(\\\{\(s\_\{0\},0\)\\\},\\emptyset\);

ℋ⁡\[\(s0,0\)\]←node\\mathcal\{H\}\[\(s\_\{0\},0\)\]\\leftarrow\\text\{node\};

∂𝒢←\{\(s0,0\)\}\\partial\\mathcal\{G\}\\leftarrow\\\{\(s\_\{0\},0\)\\\};

𝒢̊←∅\\mathring\{\\mathcal\{G\}\}\\leftarrow\\emptyset
2:Initialize all statistics at

\(s0,0\)\(s\_\{0\},0\):

Ts0,0=0T\_\{s\_\{0\},0\}=0,

Ts0,0,a=0T\_\{s\_\{0\},0,a\}=0,

Q^​\(s0,0,a\)=0\\widehat\{Q\}\(s\_\{0\},0,a\)=0for all

a∈𝒜s0a\\in\\mathcal\{A\}\_\{s\_\{0\}\}
3:for

t=1,…,nt=1,\\ldots,ndo

4:

SimulateV​\(s0,0,t\)\\textsc\{SimulateV\}\(s\_\{0\},0,t\)
5:endfor

6:return

a^n=arg​maxa∈𝒜s0⁡Q^Ts0,0,a​\(s0,0,a\)\\hat\{a\}\_\{n\}=\\argmax\_\{a\\in\\mathcal\{A\}\_\{s\_\{0\}\}\}\\widehat\{Q\}\_\{T\_\{s\_\{0\},0,a\}\}\(s\_\{0\},0,a\)and

V^n​\(s0,0\)\\widehat\{V\}\_\{n\}\(s\_\{0\},0\)
7:Procedure

SimulateV​\(s,h,t\)\\textsc\{SimulateV\}\(s,h,t\)
8:if

h=Hh=Hor

ssis terminalthen

9:

z←π0​\(s\)z\\leftarrow\\pi\_\{0\}\(s\);

Ts,h←Ts,h\+1T\_\{s,h\}\\leftarrow T\_\{s,h\}\+1;

V^Ts,h​\(s,h\)←V^Ts,h​\(s,h\)\+z−V^Ts,h​\(s,h\)Ts,h\\widehat\{V\}\_\{T\_\{s,h\}\}\(s,h\)\\leftarrow\\widehat\{V\}\_\{T\_\{s,h\}\}\(s,h\)\+\\frac\{z\-\\widehat\{V\}\_\{T\_\{s,h\}\}\(s,h\)\}\{T\_\{s,h\}\}
10:return

V^Ts,h​\(s,h\)\\widehat\{V\}\_\{T\_\{s,h\}\}\(s,h\)
11:endif

12:if

\(s,h\)∈∂𝒢\(s,h\)\\in\\partial\\mathcal\{G\}then

13:Move

\(s,h\)\(s,h\)from

∂𝒢\\partial\\mathcal\{G\}to

𝒢̊\\mathring\{\\mathcal\{G\}\}
14:endif

15:if

∃a∈𝒜s\\exists a\\in\\mathcal\{A\}\_\{s\}with

Ts,h,a=0T\_\{s,h,a\}=0then

16:Choose such an action

aa
17:else

18:

a←arg​maxa′∈𝒜s⁡\{Q^Ts,h,a′​\(s,h,a′\)\+C​Ts,hbh\+1/βh\+1Ts,h,a′αh\+1/βh\+1\}a\\leftarrow\\argmax\_\{a^\{\\prime\}\\in\\mathcal\{A\}\_\{s\}\}\\left\\\{\\widehat\{Q\}\_\{T\_\{s,h,a^\{\\prime\}\}\}\(s,h,a^\{\\prime\}\)\+C\\frac\{T\_\{s,h\}^\{\\,b\_\{h\+1\}/\\beta\_\{h\+1\}\}\}\{T\_\{s,h,a^\{\\prime\}\}^\{\\,\\alpha\_\{h\+1\}/\\beta\_\{h\+1\}\}\}\\right\\\}
19:endif

20:Sample

s′∼P\(⋅\|s,a\)s^\{\\prime\}\\sim P\(\\cdot\|s,a\)and

r∼R⁡\(s,a,s′\)r\\sim R\(s,a,s^\{\\prime\}\); set

v′=\(s′,h\+1\)v^\{\\prime\}=\(s^\{\\prime\},h\+1\)
21:if

v′∈ℋv^\{\\prime\}\\in\\mathcal\{H\}then

22:Add edge

\(\(s,h\),a,v′\)\(\(s,h\),a,v^\{\\prime\}\)to

ℰ\\mathcal\{E\}if new \{same\-depth transposition\}

23:

Vchild←SimulateV​\(s′,h\+1,t\)V\_\{\\mathrm\{child\}\}\\leftarrow\\textsc\{SimulateV\}\(s^\{\\prime\},h\+1,t\)
24:else

25:Add

v′v^\{\\prime\}to

𝒢\\mathcal\{G\}and

∂𝒢\\partial\\mathcal\{G\};

ℋ⁡\[v′\]←node\\mathcal\{H\}\[v^\{\\prime\}\]\\leftarrow\\text\{node\}; add edge

\(\(s,h\),a,v′\)\(\(s,h\),a,v^\{\\prime\}\)
26:Initialize all statistics at

v′v^\{\\prime\};

z←Z1​\(s′\)∼π0​\(s′\)z\\leftarrow Z\_\{1\}\(s^\{\\prime\}\)\\sim\\pi\_\{0\}\(s^\{\\prime\}\);

Ts′,h\+1←1T\_\{s^\{\\prime\},h\+1\}\\leftarrow 1;

V^Ts′,h\+1​\(s′,h\+1\)←z\\widehat\{V\}\_\{T\_\{s^\{\\prime\},h\+1\}\}\(s^\{\\prime\},h\+1\)\\leftarrow z
27:

Vchild←V^Ts′,h\+1​\(s′,h\+1\)V\_\{\\mathrm\{child\}\}\\leftarrow\\widehat\{V\}\_\{T\_\{s^\{\\prime\},h\+1\}\}\(s^\{\\prime\},h\+1\)
28:endif

29:

Ts,h,as′←Ts,h,as′\+1T\_\{s,h,a\}^\{s^\{\\prime\}\}\\leftarrow T\_\{s,h,a\}^\{s^\{\\prime\}\}\+1;

Ts,h,a←Ts,h,a\+1T\_\{s,h,a\}\\leftarrow T\_\{s,h,a\}\+1
30:

Y←r\+γ​VchildY\\leftarrow r\+\\gamma V\_\{\\mathrm\{child\}\};

Q^Ts,h,a​\(s,h,a\)←Q^Ts,h,a​\(s,h,a\)\+Y−Q^Ts,h,a​\(s,h,a\)Ts,h,a\\widehat\{Q\}\_\{T\_\{s,h,a\}\}\(s,h,a\)\\leftarrow\\widehat\{Q\}\_\{T\_\{s,h,a\}\}\(s,h,a\)\+\\frac\{Y\-\\widehat\{Q\}\_\{T\_\{s,h,a\}\}\(s,h,a\)\}\{T\_\{s,h,a\}\}
31:

Ts,h←Ts,h\+1T\_\{s,h\}\\leftarrow T\_\{s,h\}\+1
32:

V^Ts,h​\(s,h\)←\(∑a′∈𝒜sTs,h,a′Ts,h​\(Q^Ts,h,a′​\(s,h,a′\)\)p\)1/p\\widehat\{V\}\_\{T\_\{s,h\}\}\(s,h\)\\leftarrow\\left\(\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\_\{s\}\}\\frac\{T\_\{s,h,a^\{\\prime\}\}\}\{T\_\{s,h\}\}\\bigl\(\\widehat\{Q\}\_\{T\_\{s,h,a^\{\\prime\}\}\}\(s,h,a^\{\\prime\}\)\\bigr\)^\{p\}\\right\)^\{1/p\}
33:return

V^Ts,h​\(s,h\)\\widehat\{V\}\_\{T\_\{s,h\}\}\(s,h\)

### C\.2Practical Variant: Full State Merging

While the depth\-augmented design of Section[3](https://arxiv.org/html/2609.19956#S3)provides clean theoretical guarantees, practical MCTS implementations often prefer*full state merging*: keying nodes by state identity alone, without the depth index\. This reduces the graph size from at most\|𝒮\|​\(H\+1\)\|\\mathcal\{S\}\|\(H\+1\)nodes to at most\|𝒮\|\|\\mathcal\{S\}\|nodes, which can be a significant saving in MDPs where the same state is revisited at many different depths \(e\.g\., grid navigation, board games with reversible moves\)\. In this section, we describe this practical variant and analyze the bias it introduces\.

##### Algorithm modification\.

The only change from Algorithm[1](https://arxiv.org/html/2609.19956#alg1)is in the hash key: the lookup usesHash​\(s′\)\\textsc\{Hash\}\(s^\{\\prime\}\)instead of\(s′,h\+1\)\(s^\{\\prime\},h\+1\)\. Each physical statesshas a single node in the graph, regardless of the depths at which it is visited\. The Q\-value and visit count statistics are shared across all depths\. We present the modified procedure in Algorithm[2](https://arxiv.org/html/2609.19956#alg2)\.

Algorithm 2Full\-Merge Graph\-Based Stochastic Power\-UCT \(GS\-Power\-UCT\-F\)0:Root state

s0s\_\{0\}, budget

nn, horizon

HH, power

pp, playout policy

π0\\pi\_\{0\}, exploration constant

CC
1:

𝒢←\(\{s0\},∅\)\\mathcal\{G\}\\leftarrow\(\\\{s\_\{0\}\\\},\\emptyset\);

ℋ⁡\[s0\]←node\\mathcal\{H\}\[s\_\{0\}\]\\leftarrow\\text\{node\};

∂𝒢←\{s0\}\\partial\\mathcal\{G\}\\leftarrow\\\{s\_\{0\}\\\};

𝒢̊←∅\\mathring\{\\mathcal\{G\}\}\\leftarrow\\emptyset
2:Initialize all statistics at

s0s\_\{0\}:

Ts0=0T\_\{s\_\{0\}\}=0,

Ts0,a=0T\_\{s\_\{0\},a\}=0,

Q^​\(s0,a\)=0\\widehat\{Q\}\(s\_\{0\},a\)=0for all

a∈𝒜s0a\\in\\mathcal\{A\}\_\{s\_\{0\}\}
3:for

t=1,…,nt=1,\\dots,ndo

4:

SimulateV​\(s0,0,t\)\\textsc\{SimulateV\}\(s\_\{0\},0,t\)
5:endfor

6:return

a^n=arg​maxa∈𝒜s0⁡Q^Ts0,a​\(s0,a\)\\hat\{a\}\_\{n\}=\\argmax\_\{a\\in\\mathcal\{A\}\_\{s\_\{0\}\}\}\\widehat\{Q\}\_\{T\_\{s\_\{0\},a\}\}\(s\_\{0\},a\)and

V^n​\(s0\)\\widehat\{V\}\_\{n\}\(s\_\{0\}\)
7:Procedure

SimulateV​\(s,h,t\)\\textsc\{SimulateV\}\(s,h,t\)
8:if

h=Hh=Hor

ssis terminalthen

9:

z←π0​\(s\)z\\leftarrow\\pi\_\{0\}\(s\);

Ts←Ts\+1T\_\{s\}\\leftarrow T\_\{s\}\+1;

V^Ts​\(s\)←V^Ts​\(s\)\+z−V^Ts​\(s\)Ts\\widehat\{V\}\_\{T\_\{s\}\}\(s\)\\leftarrow\\widehat\{V\}\_\{T\_\{s\}\}\(s\)\+\\frac\{z\-\\widehat\{V\}\_\{T\_\{s\}\}\(s\)\}\{T\_\{s\}\}
10:return

V^Ts​\(s\)\\widehat\{V\}\_\{T\_\{s\}\}\(s\)
11:endif

12:if

s∈∂𝒢s\\in\\partial\\mathcal\{G\}then

13:Move

ssfrom

∂𝒢\\partial\\mathcal\{G\}to

𝒢̊\\mathring\{\\mathcal\{G\}\}
14:endif

15:if

∃a∈𝒜s\\exists a\\in\\mathcal\{A\}\_\{s\}with

Ts,a=0T\_\{s,a\}=0then

16:Choose such an action

aa
17:else

18:

a←arg​maxa′∈𝒜s⁡\{Q^Ts,a′​\(s,a′\)\+C​Tsbh\+1/βh\+1Ts,a′αh\+1/βh\+1\}a\\leftarrow\\argmax\_\{a^\{\\prime\}\\in\\mathcal\{A\}\_\{s\}\}\\left\\\{\\widehat\{Q\}\_\{T\_\{s,a^\{\\prime\}\}\}\(s,a^\{\\prime\}\)\+C\\frac\{T\_\{s\}^\{\\,b\_\{h\+1\}/\\beta\_\{h\+1\}\}\}\{T\_\{s,a^\{\\prime\}\}^\{\\,\\alpha\_\{h\+1\}/\\beta\_\{h\+1\}\}\}\\right\\\}
19:endif

20:Sample

s′∼P\(⋅\|s,a\)s^\{\\prime\}\\sim P\(\\cdot\|s,a\)and

r∼R⁡\(s,a,s′\)r\\sim R\(s,a,s^\{\\prime\}\); set

v′=s′v^\{\\prime\}=s^\{\\prime\}
21:if

v′∈ℋv^\{\\prime\}\\in\\mathcal\{H\}then

22:Add edge

\(s,a,v′\)\(s,a,v^\{\\prime\}\)to

ℰ\\mathcal\{E\}if new

23:

Vchild←SimulateV​\(s′,h\+1,t\)V\_\{\\mathrm\{child\}\}\\leftarrow\\textsc\{SimulateV\}\(s^\{\\prime\},h\+1,t\)
24:else

25:Add

v′v^\{\\prime\}to

𝒢\\mathcal\{G\}and

∂𝒢\\partial\\mathcal\{G\};

ℋ⁡\[v′\]←node\\mathcal\{H\}\[v^\{\\prime\}\]\\leftarrow\\text\{node\}; add edge

\(s,a,v′\)\(s,a,v^\{\\prime\}\)
26:Initialize all statistics at

v′v^\{\\prime\};

z←rollout from​π0​\(s′\)z\\leftarrow\\text\{rollout from \}\\pi\_\{0\}\(s^\{\\prime\}\);

Ts′←1T\_\{s^\{\\prime\}\}\\leftarrow 1;

V^Ts′​\(s′\)←z\\widehat\{V\}\_\{T\_\{s^\{\\prime\}\}\}\(s^\{\\prime\}\)\\leftarrow z
27:

Vchild←V^Ts′​\(s′\)V\_\{\\mathrm\{child\}\}\\leftarrow\\widehat\{V\}\_\{T\_\{s^\{\\prime\}\}\}\(s^\{\\prime\}\)
28:endif

29:

Ts,as′←Ts,as′\+1T\_\{s,a\}^\{s^\{\\prime\}\}\\leftarrow T\_\{s,a\}^\{s^\{\\prime\}\}\+1;

Ts,a←Ts,a\+1T\_\{s,a\}\\leftarrow T\_\{s,a\}\+1
30:

Y←r\+γ​VchildY\\leftarrow r\+\\gamma V\_\{\\mathrm\{child\}\};

Q^Ts,a​\(s,a\)←Q^Ts,a​\(s,a\)\+Y−Q^Ts,a​\(s,a\)Ts,a\\widehat\{Q\}\_\{T\_\{s,a\}\}\(s,a\)\\leftarrow\\widehat\{Q\}\_\{T\_\{s,a\}\}\(s,a\)\+\\frac\{Y\-\\widehat\{Q\}\_\{T\_\{s,a\}\}\(s,a\)\}\{T\_\{s,a\}\}
31:

Ts←Ts\+1T\_\{s\}\\leftarrow T\_\{s\}\+1
32:

V^Ts​\(s\)←\(∑a′∈𝒜sTs,a′Ts​\(Q^Ts,a′​\(s,a′\)\)p\)1/p\\widehat\{V\}\_\{T\_\{s\}\}\(s\)\\leftarrow\\left\(\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\_\{s\}\}\\frac\{T\_\{s,a^\{\\prime\}\}\}\{T\_\{s\}\}\\bigl\(\\widehat\{Q\}\_\{T\_\{s,a^\{\\prime\}\}\}\(s,a^\{\\prime\}\)\\bigr\)^\{p\}\\right\)^\{1/p\}
33:return

V^Ts​\(s\)\\widehat\{V\}\_\{T\_\{s\}\}\(s\)

##### Source of bias\.

Consider a statessthat is visited at trajectory depthsh1<h2h\_\{1\}<h\_\{2\}during planning\. When the simulation reachesssat depthh1h\_\{1\}, it continues forH−h1H\-h\_\{1\}more steps before reaching the rollout horizon\. When it reachesssat depthh2h\_\{2\}, it continues for onlyH−h2H\-h\_\{2\}steps\. Both trajectories backpropagate returns into the*same*Q\-value estimatesQ^​\(s,a\)\\widehat\{Q\}\(s,a\)\. The returns from depthh1h\_\{1\}reflect a longer effective planning horizon than those from depthh2h\_\{2\}, so they target different values ofQ~\\widetilde\{Q\}\. The resulting Q\-value estimate converges to a visit\-weighted mixture of the two targets rather than either one individually\.

More precisely, the bias propagates recursively: a childs′s^\{\\prime\}ofssis also visited at multiple depths \(h1\+1h\_\{1\}\+1andh2\+1h\_\{2\}\+1\), so its value estimateV^​\(s′\)\\widehat\{V\}\(s^\{\\prime\}\)is itself biased, which in turn biasesQ^​\(s,a\)\\widehat\{Q\}\(s,a\)\. The total bias at any node depends on the full subgraph of cross\-depth transpositions reachable from that node\.

##### Quantifying the bias\.

For each statessin the graph, define the set of depths at whichssis visited:

𝒟⁡\(s\)=\{h:s​is visited at depth​h​during planning\}\.\\mathcal\{D\}\(s\)=\\\{h:s\\text\{ is visited at depth \}h\\text\{ during planning\}\\\}\.\(22\)The*cross\-depth gap*at statessis:

δ⁡\(s\)=maxh1,h2∈𝒟⁡\(s\)⁡\|V~​\(s,h1\)−V~​\(s,h2\)\|≤γH−hmax​\(s\)−γH−hmin​\(s\)1−γ​‖V⋆−V0‖∞,\\delta\(s\)=\\max\_\{h\_\{1\},h\_\{2\}\\in\\mathcal\{D\}\(s\)\}\|\\widetilde\{V\}\(s,h\_\{1\}\)\-\\widetilde\{V\}\(s,h\_\{2\}\)\|\\leq\\frac\{\\gamma^\{H\-h\_\{\\max\}\(s\)\}\-\\gamma^\{H\-h\_\{\\min\}\(s\)\}\}\{1\-\\gamma\}\\\|V^\{\\star\}\-V\_\{0\}\\\|\_\{\\infty\},\(23\)wherehmin​\(s\)=min⁡𝒟⁡\(s\)h\_\{\\min\}\(s\)=\\min\\mathcal\{D\}\(s\),hmax​\(s\)=max⁡𝒟⁡\(s\)h\_\{\\max\}\(s\)=\\max\\mathcal\{D\}\(s\)\. The global cross\-depth bias is:

Δcross=maxs∈𝒢⁡δ⁡\(s\)\.\\Delta\_\{\\textsc\{cross\}\}=\\max\_\{s\\in\\mathcal\{G\}\}\\delta\(s\)\.\(24\)

##### When isΔcross\\Delta\_\{\\textsc\{cross\}\}small?

The cross\-depth bias is negligible in several important regimes:

1. 1\.Good evaluation function: WhenV0≈V⋆V\_\{0\}\\approx V^\{\\star\}\(e\.g\., a well\-trained neural network as in AlphaZero\),‖V⋆−V0‖∞\\\|V^\{\\star\}\-V\_\{0\}\\\|\_\{\\infty\}is small, makingΔcross\\Delta\_\{\\textsc\{cross\}\}small regardless of the depth gap\.
2. 2\.Large horizon: WhenHHis large relative to the depth range, bothγH−hmax\\gamma^\{H\-h\_\{\\max\}\}andγH−hmin\\gamma^\{H\-h\_\{\\min\}\}are small, so their difference is negligible\.
3. 3\.Small depth range: When states are revisited only at similar depths \(hmax​\(s\)−hmin​\(s\)h\_\{\\max\}\(s\)\-h\_\{\\min\}\(s\)is small for allss\), the cross\-depth gap is small\.
4. 4\.No cross\-depth transpositions: When every transposition occurs at the same depth \(common in grid worlds with deterministic step costs\),Δcross=0\\Delta\_\{\\textsc\{cross\}\}=0and the full\-merge variant is exactly equivalent to the depth\-augmented variant\.

## Appendix DDetailed Proofs

### D\.1Proof of Lemma[1](https://arxiv.org/html/2609.19956#Thmlemma1)

We provide the complete proof of the Generalized Topological Concentration Lemma\.

###### Proof\.

The caseγ=0\\gamma=0reduces to the concentration of the empirical reward average, so assumeγ\>0\\gamma\>0\.

By \(A\-Fresh\) in Assumption[1](https://arxiv.org/html/2609.19956#Thmassumption1),\(Xi,Si\)i≥1\(X\_\{i\},S\_\{i\}\)\_\{i\\geq 1\}is the i\.i\.d\. local simulator stream for the fixed parent\-action pair\. No independence betweenXiX\_\{i\}andSiS\_\{i\}within a pair is used\. The estimatesV^m,Tmeff​\(n\)\\widehat\{V\}\_\{m,T\_\{m\}^\{\\textsc\{eff\}\}\(n\)\}are adaptive; their contribution is controlled by the time\-uniform local hypothesis \(H\-Q\), rather than by an i\.i\.d\. argument\.

Let

X¯n=1n​∑i=1nXi,𝑽^n=\(V^1,T1eff​\(n\),…,V^M,TMeff​\(n\)\),\\bar\{X\}\_\{n\}=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}X\_\{i\},\\qquad\\widehat\{\\bm\{V\}\}\_\{n\}=\\left\(\\widehat\{V\}\_\{1,T\_\{1\}^\{\\textsc\{eff\}\}\(n\)\},\\ldots,\\widehat\{V\}\_\{M,T\_\{M\}^\{\\textsc\{eff\}\}\(n\)\}\\right\),and let

𝑽=\(V1,…,VM\),𝒑^n=\(p^1,n,…,p^M,n\)\(p^i,n=Ninn\)𝒑=\(p1,…,pM\)\.\\bm\{V\}=\(V\_\{1\},\\ldots,V\_\{M\}\),\\qquad\\widehat\{\\bm\{p\}\}\_\{n\}=\(\\widehat\{p\}\_\{1,n\},\\ldots,\\widehat\{p\}\_\{M,n\}\)\\qquad\\left\(\\widehat\{p\}\_\{i,n\}=\\frac\{N\_\{i\}^\{n\}\}\{n\}\\right\)\\qquad\\bm\{p\}=\(p\_\{1\},\\ldots,p\_\{M\}\)\.We have

Q^n​\(s,a\)=X¯n\+γ⁡⟨𝒑^n,𝑽^n⟩\.\\widehat\{Q\}\_\{n\}\(s,a\)=\\bar\{X\}\_\{n\}\+\\gamma\\langle\\widehat\{\\bm\{p\}\}\_\{n\},\\widehat\{\\bm\{V\}\}\_\{n\}\\rangle\.Therefore,

ℙ⁡\(\|Q^n​\(s,a\)−\(μ\+γ⁡⟨𝒑,𝑽⟩\)\|≥ε\)\\displaystyle\\mathbb\{P\}\\\!\\left\(\\left\|\\widehat\{Q\}\_\{n\}\(s,a\)\-\\left\(\\mu\+\\gamma\\langle\\bm\{p\},\\bm\{V\}\\rangle\\right\)\\right\|\\geq\\varepsilon\\right\)≤ℙ⁡\(\|X¯n−μ\|≥ε2\)\+ℙ⁡\(γ​\|⟨𝒑^n,𝑽^n⟩−⟨𝒑,𝑽⟩\|≥ε2\)\\displaystyle\\quad\\leq\\mathbb\{P\}\\\!\\left\(\|\\bar\{X\}\_\{n\}\-\\mu\|\\geq\\frac\{\\varepsilon\}\{2\}\\right\)\+\\mathbb\{P\}\\\!\\left\(\\gamma\\left\|\\langle\\widehat\{\\bm\{p\}\}\_\{n\},\\widehat\{\\bm\{V\}\}\_\{n\}\\rangle\-\\langle\\bm\{p\},\\bm\{V\}\\rangle\\right\|\\geq\\frac\{\\varepsilon\}\{2\}\\right\)≤ℙ⁡\(\|X¯n−μ\|≥ε2\)\+A1\+A2,\\displaystyle\\quad\\leq\\mathbb\{P\}\\\!\\left\(\|\\bar\{X\}\_\{n\}\-\\mu\|\\geq\\frac\{\\varepsilon\}\{2\}\\right\)\+A\_\{1\}\+A\_\{2\},\(25\)where

A1=ℙ⁡\(\|⟨𝒑^n−𝒑,𝑽^n⟩\|≥ε4​γ\),A\_\{1\}=\\mathbb\{P\}\\\!\\left\(\\left\|\\langle\\widehat\{\\bm\{p\}\}\_\{n\}\-\\bm\{p\},\\widehat\{\\bm\{V\}\}\_\{n\}\\rangle\\right\|\\geq\\frac\{\\varepsilon\}\{4\\gamma\}\\right\),and

A2=ℙ⁡\(\|⟨𝒑,𝑽^n−𝑽⟩\|≥ε4​γ\)\.A\_\{2\}=\\mathbb\{P\}\\\!\\left\(\\left\|\\langle\\bm\{p\},\\widehat\{\\bm\{V\}\}\_\{n\}\-\\bm\{V\}\\rangle\\right\|\\geq\\frac\{\\varepsilon\}\{4\\gamma\}\\right\)\.

##### Reward term\.

Assume the reward samples have bounded range at mostRmaxR\_\{\\max\}\. By Hoeffding’s inequality,

ℙ⁡\(\|X¯n−μ\|≥ε2\)≤2​exp⁡\(−n​ε22​Rmax2\)\.\\mathbb\{P\}\\left\(\|\\bar\{X\}\_\{n\}\-\\mu\|\\geq\\frac\{\\varepsilon\}\{2\}\\right\)\\leq 2\\exp\\left\(\-\\frac\{n\\varepsilon^\{2\}\}\{2R\_\{\\max\}^\{2\}\}\\right\)\.\(26\)

##### Empirical\-transition term\.

Since\|V^m,Tmeff​\(n\)\|≤L\|\\widehat\{V\}\_\{m,T\_\{m\}^\{\\textsc\{eff\}\}\(n\)\}\|\\leq Lfor everymm,

\|⟨𝒑^n−𝒑,𝑽^n⟩\|≤‖𝒑^n−𝒑‖1​‖𝑽^n‖∞≤L​‖𝒑^n−𝒑‖1\.\\left\|\\langle\\widehat\{\\bm\{p\}\}\_\{n\}\-\\bm\{p\},\\widehat\{\\bm\{V\}\}\_\{n\}\\rangle\\right\|\\leq\\\|\\widehat\{\\bm\{p\}\}\_\{n\}\-\\bm\{p\}\\\|\_\{1\}\\\|\\widehat\{\\bm\{V\}\}\_\{n\}\\\|\_\{\\infty\}\\leq L\\\|\\widehat\{\\bm\{p\}\}\_\{n\}\-\\bm\{p\}\\\|\_\{1\}\.Using the Weissman–typeL1L\_\{1\}deviation inequality\[[14](https://arxiv.org/html/2609.19956#bib.bib14)\]for the empirical distribution onMMcategories,

A1≤ℙ⁡\(‖𝒑^n−𝒑‖1≥ε4​γ​L\)≤2M​exp⁡\(−n​ε232​γ2​L2\)\.A\_\{1\}\\leq\\mathbb\{P\}\\\!\\left\(\\\|\\widehat\{\\bm\{p\}\}\_\{n\}\-\\bm\{p\}\\\|\_\{1\}\\geq\\frac\{\\varepsilon\}\{4\\gamma L\}\\right\)\\leq 2^\{M\}\\exp\\\!\\left\(\-\\frac\{n\\varepsilon^\{2\}\}\{32\\gamma^\{2\}L^\{2\}\}\\right\)\.\(27\)

##### Child\-value term\.

Let

Zm​\(n\)=V^m,Tmeff​\(n\)−Vm,δ=ε4​γ\.Z\_\{m\}\(n\)=\\widehat\{V\}\_\{m,T\_\{m\}^\{\\textsc\{eff\}\}\(n\)\}\-V\_\{m\},\\qquad\\delta=\\frac\{\\varepsilon\}\{4\\gamma\}\.Then

A2=ℙ⁡\(\|∑m=1Mpm​Zm​\(n\)\|≥δ\)≤ℙ⁡\(∑m=1Mpm​\|Zm​\(n\)\|≥δ\)\.A\_\{2\}=\\mathbb\{P\}\\\!\\left\(\\left\|\\sum\_\{m=1\}^\{M\}p\_\{m\}Z\_\{m\}\(n\)\\right\|\\geq\\delta\\right\)\\leq\\mathbb\{P\}\\\!\\left\(\\sum\_\{m=1\}^\{M\}p\_\{m\}\|Z\_\{m\}\(n\)\|\\geq\\delta\\right\)\.Since∑mpm=1\\sum\_\{m\}p\_\{m\}=1, if\|Zm​\(n\)\|<δ\|Z\_\{m\}\(n\)\|<\\deltafor everymm, then∑mpm​\|Zm​\(n\)\|<δ\\sum\_\{m\}p\_\{m\}\|Z\_\{m\}\(n\)\|<\\delta\. Hence

A2≤∑m=1Mℙ⁡\(\|Zm​\(n\)\|≥δ\)\.A\_\{2\}\\leq\\sum\_\{m=1\}^\{M\}\\mathbb\{P\}\\\!\\left\(\|Z\_\{m\}\(n\)\|\\geq\\delta\\right\)\.\(28\)For eachmm, define the high\-local\-count event

ℰm=\{Nmn\>n​pm2\}\.\\mathcal\{E\}\_\{m\}=\\left\\\{N\_\{m\}^\{n\}\>\\frac\{np\_\{m\}\}\{2\}\\right\\\}\.Then

ℙ⁡\(\|Zm​\(n\)\|≥δ\)\\displaystyle\\mathbb\{P\}\\\!\\left\(\|Z\_\{m\}\(n\)\|\\geq\\delta\\right\)≤ℙ⁡\(\|Zm​\(n\)\|≥δ,ℰm\)\+ℙ⁡\(ℰmc\)\.\\displaystyle\\leq\\mathbb\{P\}\\\!\\left\(\|Z\_\{m\}\(n\)\|\\geq\\delta,\\mathcal\{E\}\_\{m\}\\right\)\+\\mathbb\{P\}\(\\mathcal\{E\}\_\{m\}^\{c\}\)\.\(29\)Onℰm\\mathcal\{E\}\_\{m\},

Tmeff​\(n\)=Nmn\+Tmext​\(n\)≥Nmn\>n​pm2\.T\_\{m\}^\{\\textsc\{eff\}\}\(n\)=N\_\{m\}^\{n\}\+T\_\{m\}^\{\\textsc\{ext\}\}\(n\)\\geq N\_\{m\}^\{n\}\>\\frac\{np\_\{m\}\}\{2\}\.Let

rm=max⁡\{1,n​pm2\}\.r\_\{m\}=\\max\\left\\\{1,\\frac\{np\_\{m\}\}\{2\}\\right\\\}\.By the time\-uniform child premise \(H\-Q\), we have

ℙ⁡\(\|Zm​\(n\)\|≥δ,ℰm\)\\displaystyle\\mathbb\{P\}\\left\(\|Z\_\{m\}\(n\)\|\\geq\\delta,\\mathcal\{E\}\_\{m\}\\right\)≤ℙ⁡\(\|V^m,Tmeff​\(n\)−Vm\|≥δ,Tmeff​\(n\)≥rm\)\\displaystyle\\leq\\mathbb\{P\}\\left\(\|\\widehat\{V\}\_\{m,T\_\{m\}^\{\\textsc\{eff\}\}\(n\)\}\-V\_\{m\}\|\\geq\\delta,T\_\{m\}^\{\\textsc\{eff\}\}\(n\)\\geq r\_\{m\}\\right\)≤cV​2α​pm−α​n−α​δ−β\.\\displaystyle\\leq c\_\{V\}2^\{\\alpha\}p\_\{m\}^\{\-\\alpha\}n^\{\-\\alpha\}\\delta^\{\-\\beta\}\.\(30\)Also, sinceNmn∼Binomial⁡\(n,pm\)N\_\{m\}^\{n\}\\sim\\mathrm\{Binomial\}\(n,p\_\{m\}\), Hoeffding’s inequality gives

ℙ⁡\(ℰmc\)=ℙ⁡\(Nmn≤n​pm2\)≤exp⁡\(−n​pm22\)\.\\mathbb\{P\}\(\\mathcal\{E\}\_\{m\}^\{c\}\)=\\mathbb\{P\}\\left\(N\_\{m\}^\{n\}\\leq\\frac\{np\_\{m\}\}\{2\}\\right\)\\leq\\exp\\left\(\-\\frac\{np\_\{m\}^\{2\}\}\{2\}\\right\)\.\(31\)Combining \([28](https://arxiv.org/html/2609.19956#A4.E28)\), \([30](https://arxiv.org/html/2609.19956#A4.E30)\), and \([31](https://arxiv.org/html/2609.19956#A4.E31)\), and substitutingδ=ε/\(4​γ\)\\delta=\\varepsilon/\(4\\gamma\), we obtain

A2≤cV​2α​\(4​γ\)β​\(∑m=1Mpm−α\)​n−α​ε−β\+∑m=1Mexp⁡\(−n​pm22\)\.A\_\{2\}\\leq c\_\{V\}2^\{\\alpha\}\(4\\gamma\)^\{\\beta\}\\left\(\\sum\_\{m=1\}^\{M\}p\_\{m\}^\{\-\\alpha\}\\right\)n^\{\-\\alpha\}\\varepsilon^\{\-\\beta\}\+\\sum\_\{m=1\}^\{M\}\\exp\\left\(\-\\frac\{np\_\{m\}^\{2\}\}\{2\}\\right\)\.\(32\)

##### Dominating the exponential terms\.

The estimators and rewards are bounded, so there exists a deterministic constantBQ<∞B\_\{Q\}<\\inftysuch that

\|Q^n​\(s,a\)−Q~​\(s,a\)\|≤BQalmost surely for all​n\.\\left\|\\widehat\{Q\}\_\{n\}\(s,a\)\-\\widetilde\{Q\}\(s,a\)\\right\|\\leq B\_\{Q\}\\qquad\\text\{almost surely for all \}n\.Forε\>BQ\\varepsilon\>B\_\{Q\}, the desired probability is zero, so it remains to consider0<ε≤BQ0<\\varepsilon\\leq B\_\{Q\}\.

Because2​α≤β2\\alpha\\leq\\beta, for everyc0\>0c\_\{0\}\>0there exists a finite constantK⁡\(c0,α,β\)K\(c\_\{0\},\\alpha,\\beta\)such that

exp⁡\(−c0​n​ε2\)≤K⁡\(c0,α,β\)​n−α​ε−β∀n≥1,ε\>0\.\\exp\(\-c\_\{0\}n\\varepsilon^\{2\}\)\\leq K\(c\_\{0\},\\alpha,\\beta\)n^\{\-\\alpha\}\\varepsilon^\{\-\\beta\}\\qquad\\forall n\\geq 1,\\ \\varepsilon\>0\.Indeed, withx=n​ε2x=n\\varepsilon^\{2\},

exp\(−c0x\)≤Kx−β/2=Kn−β/2ε−β≤Kn−αε−β,\\exp\(\-c\_\{0\}x\)\\leq Kx^\{\-\\beta/2\}=Kn^\{\-\\beta/2\}\\varepsilon^\{\-\\beta\}\\leq Kn^\{\-\\alpha\}\\varepsilon^\{\-\\beta\},where the last inequality usesβ/2≥α\\beta/2\\geq\\alpha\.

Similarly, for eachmm,

exp⁡\(−n​pm22\)≤Km​n−α≤Km​BQβ​n−α​ε−βfor​0<ε≤BQ\.\\exp\\left\(\-\\frac\{np\_\{m\}^\{2\}\}\{2\}\\right\)\\leq K\_\{m\}n^\{\-\\alpha\}\\leq K\_\{m\}B\_\{Q\}^\{\\beta\}n^\{\-\\alpha\}\\varepsilon^\{\-\\beta\}\\qquad\\text\{for \}0<\\varepsilon\\leq B\_\{Q\}\.Thus the reward term \([26](https://arxiv.org/html/2609.19956#A4.E26)\), the empirical\-transition term \([27](https://arxiv.org/html/2609.19956#A4.E27)\), and the binomial lower\-tail terms in \([32](https://arxiv.org/html/2609.19956#A4.E32)\) are all bounded by constants timesn−α​ε−βn^\{\-\\alpha\}\\varepsilon^\{\-\\beta\}\.

Combining these bounds in \([25](https://arxiv.org/html/2609.19956#A4.E25)\), there exists a constantCQ<∞C\_\{Q\}<\\inftysuch that

ℙ⁡\(\|Q^n​\(s,a\)−Q~​\(s,a\)\|\>ε\)≤CQ​n−α​ε−β\.\\mathbb\{P\}\\left\(\\left\|\\widehat\{Q\}\_\{n\}\(s,a\)\-\\widetilde\{Q\}\(s,a\)\\right\|\>\\varepsilon\\right\)\\leq C\_\{Q\}n^\{\-\\alpha\}\\varepsilon^\{\-\\beta\}\.This proves the claimed\(α,β\)\(\\alpha,\\beta\)\-concentration\. ∎

Before providing the Proof for Theorem[6](https://arxiv.org/html/2609.19956#Thmtheorem6), we provide the proof below\.

###### Lemma 2\(Leaf concentration\)\.

For any leaf nodessat depthHHin𝒢\\mathcal\{G\}, the value estimateV^n​\(s\)\\widehat\{V\}\_\{n\}\(s\)\(average ofnni\.i\.d\. calls toπ0\\pi\_\{0\}\) satisfies:

V^n​\(s\)→n→∞αH,βHV~​\(s\),\\widehat\{V\}\_\{n\}\(s\)\\xrightarrow\[n\\to\\infty\]\{\\alpha\_\{H\},\\beta\_\{H\}\}\\widetilde\{V\}\(s\),\(33\)whereαH,βH\\alpha\_\{H\},\\beta\_\{H\}can be chosen to satisfyαH≤βH/2\\alpha\_\{H\}\\leq\\beta\_\{H\}/2withβH\>2\\beta\_\{H\}\>2, andV~​\(s\)=V0​\(s\)\\widetilde\{V\}\(s\)=V\_\{0\}\(s\)is the playout value\.

###### Proof\.

SinceV^n​\(s\)=1n​∑i=1nXi\\widehat\{V\}\_\{n\}\(s\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}X\_\{i\}whereXi∼π0​\(s\)X\_\{i\}\\sim\\pi\_\{0\}\(s\)are i\.i\.d\. with meanV0​\(s\)V\_\{0\}\(s\)and bounded in\[0,Rmax/\(1−γ\)\]\[0,R\_\{\\max\}/\(1\-\\gamma\)\], Hoeffding’s inequality givesℙ\(\|V^n\(s\)−V0\(s\)\|\>ε\)≤2exp\(−2nε2/L2\)\\mathbb\{P\}\(\|\\widehat\{V\}\_\{n\}\(s\)\-V\_\{0\}\(s\)\|\>\\varepsilon\)\\leq 2\\exp\(\-2n\\varepsilon^\{2\}/L^\{2\}\), which implies\(α,β\)\(\\alpha,\\beta\)\-concentration for anyα≤β/2\\alpha\\leq\\beta/2with appropriate constants\. ∎

###### Theorem 5\(Power mean concentration at graph nodes\)\.

Consider an internal nodessin𝒢\\mathcal\{G\}at graph depthhh\. Suppose that for all actionsa∈𝒜sa\\in\\mathcal\{A\}\_\{s\}, the Q\-value estimates satisfyQ^n​\(s,h,a\)→n→∞αh\+1,βh\+1Q~​\(s,h,a\)\\widehat\{Q\}\_\{n\}\(s,h,a\)\\xrightarrow\[n\\to\\infty\]\{\\alpha\_\{h\+1\},\\beta\_\{h\+1\}\}\\widetilde\{Q\}\(s,h,a\)\. Assume the action selection follows \([7](https://arxiv.org/html/2609.19956#S3.E7)\) with parameters satisfying Table[1](https://arxiv.org/html/2609.19956#S3.T1)\.

Ifp,αh\+1,βh\+1,bh\+1p,\\alpha\_\{h\+1\},\\beta\_\{h\+1\},b\_\{h\+1\}satisfy either:

1. \(i\)1≤p≤21\\leq p\\leq 2andαh\+1≤βh\+1/2\\alpha\_\{h\+1\}\\leq\\beta\_\{h\+1\}/2, or
2. \(ii\)p\>2p\>2and0<αh\+1−βh\+1/p<10<\\alpha\_\{h\+1\}\-\\beta\_\{h\+1\}/p<1,

then the power mean value estimateV^n​\(s\)\\widehat\{V\}\_\{n\}\(s\)satisfies:

V^n​\(s,h\)→n→∞αh,βhV~​\(s,h\),\\widehat\{V\}\_\{n\}\(s,h\)\\xrightarrow\[n\\to\\infty\]\{\\alpha\_\{h\},\\beta\_\{h\}\}\\widetilde\{V\}\(s,h\),\(34\)whereαh=\(bh\+1−1\)​\(1−bh\+1/αh\+1\)\\alpha\_\{h\}=\(b\_\{h\+1\}\-1\)\(1\-b\_\{h\+1\}/\\alpha\_\{h\+1\}\)andβh=\(bh\+1−1\)\\beta\_\{h\}=\(b\_\{h\+1\}\-1\)\.

###### Proof\.

This follows directly from Theorem 1 of[Dam et al\. \[5\]](https://arxiv.org/html/2609.19956#bib.bib5)\. The key observation is that Theorem 1 only requires that the Q\-value estimates at the node concentrate at rate\(αh\+1,βh\+1\)\(\\alpha\_\{h\+1\},\\beta\_\{h\+1\}\)— it does not require any assumption about*how*those Q\-values were formed \(tree or graph\)\. Since Lemma[1](https://arxiv.org/html/2609.19956#Thmlemma1)establishes exactly this concentration for graph\-based Q\-values, the theorem applies\. ∎

### D\.2Proofs of Theorems[6](https://arxiv.org/html/2609.19956#Thmtheorem6)and[1](https://arxiv.org/html/2609.19956#Thmtheorem1)

Before going into the detailed proof, we state this result

###### Theorem 6\(Convergence of GS\-Power\-UCT\)\.

Apply GS\-Power\-UCT \(Algorithm[1](https://arxiv.org/html/2609.19956#alg1)\) to an MDP satisfying Assumption[1](https://arxiv.org/html/2609.19956#Thmassumption1), with algorithmic constants\{bh\}h=0H\\\{b\_\{h\}\\\}\_\{h=0\}^\{H\},\{αh\}h=0H\\\{\\alpha\_\{h\}\\\}\_\{h=0\}^\{H\}, and\{βh\}h=0H\\\{\\beta\_\{h\}\\\}\_\{h=0\}^\{H\}satisfying Table[1](https://arxiv.org/html/2609.19956#S3.T1)\. Then the depth\-augmented search graph𝒢n=\(𝒩n,ℰn\)\\mathcal\{G\}\_\{n\}=\(\\mathcal\{N\}\_\{n\},\\mathcal\{E\}\_\{n\}\)is a DAG by Proposition[1](https://arxiv.org/html/2609.19956#Thmproposition1)\. Moreover, the following concentration statements hold\.

1. \(i\)For any depth\-augmented node\(s,h\)∈𝒩n\(s,h\)\\in\\mathcal\{N\}\_\{n\}withh∈\{0,1,…,H\}h\\in\\\{0,1,\\ldots,H\\\}, the value estimate stored at this node concentrates around its depth\-hhtruncated Bellman target: V^n​\(s,h\)→n→∞αh,βhV~​\(s,h\)\.\\widehat\{V\}\_\{n\}\(s,h\)\\xrightarrow\[n\\to\\infty\]\{\\alpha\_\{h\},\\beta\_\{h\}\}\\widetilde\{V\}\(s,h\)\.\(35\)
2. \(ii\)For any internal depth\-augmented node\(s,h\)∈𝒢̊n\(s,h\)\\in\\mathring\{\\mathcal\{G\}\}\_\{n\}withh∈\{0,1,…,H−1\}h\\in\\\{0,1,\\ldots,H\-1\\\}and any actiona∈𝒜sa\\in\\mathcal\{A\}\_\{s\}, the Q\-value estimate stored at this node\-action pair concentrates around its depth\-hhtruncated Q\-target: Q^n​\(s,h,a\)→n→∞αh\+1,βh\+1Q~​\(s,h,a\),∀a∈𝒜s\.\\widehat\{Q\}\_\{n\}\(s,h,a\)\\xrightarrow\[n\\to\\infty\]\{\\alpha\_\{h\+1\},\\beta\_\{h\+1\}\}\\widetilde\{Q\}\(s,h,a\),\\qquad\\forall a\\in\\mathcal\{A\}\_\{s\}\.\(36\)

###### Proof\.

We prove by strong induction on depthhh, fromHHdown to00\. The induction is well\-defined because the depth\-augmented graph is a DAG by Proposition[1](https://arxiv.org/html/2609.19956#Thmproposition1): every edge connects depthhhto depthh\+1h\+1, so all children of a depth\-hhnode have depth exactlyh\+1h\+1\.

Base case \(h=Hh=H\):By Lemma[2](https://arxiv.org/html/2609.19956#Thmlemma2), for any node\(s,H\)\(s,H\)at depthHH:

V^n​\(s,H\)→n→∞αH,βHV~​\(s,H\)=V0​\(s\)\.\\widehat\{V\}\_\{n\}\(s,H\)\\xrightarrow\[n\\to\\infty\]\{\\alpha\_\{H\},\\beta\_\{H\}\}\\widetilde\{V\}\(s,H\)=V\_\{0\}\(s\)\.\(37\)
Inductive step:Suppose \(i\) and \(ii\) hold for all depthsh\+1,h\+2,…,Hh\+1,h\+2,\\ldots,H\. Consider a node\(s,h\)\(s,h\)at depthhh\.

*Step 1: Q\-value concentration\.*For any actiona∈𝒜sa\\in\\mathcal\{A\}\_\{s\}, the successor nodes are of the form\(s′,h\+1\)\(s^\{\\prime\},h\+1\)withs′∼P\(⋅\|s,a\)s^\{\\prime\}\\sim P\(\\cdot\|s,a\), which have depth exactlyh\+1h\+1by the depth\-augmented construction\. By the inductive hypothesis:

V^n​\(s′,h\+1\)→n→∞αh\+1,βh\+1V~​\(s′,h\+1\),for all successors​s′\.\\widehat\{V\}\_\{n\}\(s^\{\\prime\},h\+1\)\\xrightarrow\[n\\to\\infty\]\{\\alpha\_\{h\+1\},\\beta\_\{h\+1\}\}\\widetilde\{V\}\(s^\{\\prime\},h\+1\),\\quad\\text\{for all successors \}s^\{\\prime\}\.\(38\)Crucially, this concentration targets the correct valueV~​\(s′,h\+1\)\\widetilde\{V\}\(s^\{\\prime\},h\+1\)because every visit to node\(s′,h\+1\)\(s^\{\\prime\},h\+1\)occurs at depthh\+1h\+1— the depth\-augmentation guarantees no mixing of estimates from different effective horizons\.

By Lemma[1](https://arxiv.org/html/2609.19956#Thmlemma1):

Q^n​\(s,h,a\)→n→∞αh\+1,βh\+1Q~​\(s,h,a\),∀a∈𝒜s\.\\widehat\{Q\}\_\{n\}\(s,h,a\)\\xrightarrow\[n\\to\\infty\]\{\\alpha\_\{h\+1\},\\beta\_\{h\+1\}\}\\widetilde\{Q\}\(s,h,a\),\\quad\\forall a\\in\\mathcal\{A\}\_\{s\}\.\(39\)This establishes \(ii\) at depthhh\.

*Step 2: Value concentration via power mean\.*At nodess, the action selection rule \([7](https://arxiv.org/html/2609.19956#S3.E7)\) and the power mean backup \([10](https://arxiv.org/html/2609.19956#S3.E10)\) satisfy the conditions of Theorem[5](https://arxiv.org/html/2609.19956#Thmtheorem5)\(which is Theorem 1 of[Dam et al\. \[5\]](https://arxiv.org/html/2609.19956#bib.bib5)\)\. The Q\-value estimates concentrate at rate\(αh\+1,βh\+1\)\(\\alpha\_\{h\+1\},\\beta\_\{h\+1\}\)by Step 1, and the parameters satisfy Table[1](https://arxiv.org/html/2609.19956#S3.T1)\. Therefore:

V^n​\(s,h\)→n→∞αh,βhV~​\(s,h\),\\widehat\{V\}\_\{n\}\(s,h\)\\xrightarrow\[n\\to\\infty\]\{\\alpha\_\{h\},\\beta\_\{h\}\}\\widetilde\{V\}\(s,h\),\(40\)withαh=\(bh\+1−1\)​\(1−bh\+1/αh\+1\)\\alpha\_\{h\}=\(b\_\{h\+1\}\-1\)\(1\-b\_\{h\+1\}/\\alpha\_\{h\+1\}\)andβh=\(bh\+1−1\)\\beta\_\{h\}=\(b\_\{h\+1\}\-1\)\.

This establishes \(i\) at depthhh, completing the induction\. ∎

###### Proof\.

Identical to Theorem 3 of[Dam et al\. \[5\]](https://arxiv.org/html/2609.19956#bib.bib5)\. Using Jensen’s inequality and the\(α0,β0\)\(\\alpha\_\{0\},\\beta\_\{0\}\)\-concentration from Theorem[6](https://arxiv.org/html/2609.19956#Thmtheorem6):

\|𝔼⁡\[V^n​\(s0\)\]−V~​\(s0\)\|\\displaystyle\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}\(s\_\{0\}\)\]\-\\widetilde\{V\}\(s\_\{0\}\)\\right\|≤𝔼⁡\[\|V^n​\(s0\)−V~​\(s0\)\|\]=∫0∞ℙ⁡\(\|V^n​\(s0\)−V~​\(s0\)\|≥ε\)​𝑑ε\\displaystyle\\leq\\mathbb\{E\}\\left\[\|\\widehat\{V\}\_\{n\}\(s\_\{0\}\)\-\\widetilde\{V\}\(s\_\{0\}\)\|\\right\]=\\int\_\{0\}^\{\\infty\}\\mathbb\{P\}\(\|\\widehat\{V\}\_\{n\}\(s\_\{0\}\)\-\\widetilde\{V\}\(s\_\{0\}\)\|\\geq\\varepsilon\)\\,d\\varepsilon\(41\)≤n−α0/β0\+c0β0−1n−α0/β0\.\\displaystyle\\leq n^\{\-\\alpha\_\{0\}/\\beta\_\{0\}\}\+\\frac\{c\_\{0\}\}\{\\beta\_\{0\}\-1\}n^\{\-\\alpha\_\{0\}/\\beta\_\{0\}\}\.\(42\)Sinceα0/β0≤1/2\\alpha\_\{0\}/\\beta\_\{0\}\\leq 1/2\(from Table[1](https://arxiv.org/html/2609.19956#S3.T1)\), the best achievable rate isO\(n−1/2\)O\(n^\{\-1/2\}\), attained by choosingαh/βh=1/2\\alpha\_\{h\}/\\beta\_\{h\}=1/2for allhh\. ∎

### D\.3Proof of Theorem[2](https://arxiv.org/html/2609.19956#Thmtheorem2)

###### Proof\.

Fix a depth\-augmented search graph𝒢\\mathcal\{G\}and let𝒯⁡\(𝒢\)\\mathcal\{T\}\(\\mathcal\{G\}\)be its unrolled tree\. For each depthhh, the projection

ϕh:𝒯h→𝒩h\\phi\_\{h\}:\\mathcal\{T\}\_\{h\}\\to\\mathcal\{N\}\_\{h\}maps a tree copy to the unique depth\-augmented graph node with the same physical state and the same depth\. For a graph nodev∈𝒩hv\\in\\mathcal\{N\}\_\{h\}, write

𝒞⁡\(v\)≜ϕh−1​\(v\)\\mathcal\{C\}\(v\)\\triangleq\\phi\_\{h\}^\{\-1\}\(v\)for the set of tree copies that are merged intovv\.

The proof has two parts\. First, we prove the deterministic sample\-sharing identities\. Second, we prove the non\-worsening comparison for the proof\-generated concentration constants\.

##### Coupling the graph and the unrolled tree\.

We use the natural coupling in which the graph algorithm and the unrolled tree are exposed to the same realized simulated trajectories\. The unrolled tree keeps two prefixes distinct whenever their histories differ, even if they end at the same state\-depth pair\. The graph identifies all prefixes ending at the same depth\-augmented node\(s,h\)\(s,h\)\.

Fix a depthhhand a graph nodev∈𝒩hv\\in\\mathcal\{N\}\_\{h\}\. For theii\-th simulated trajectory, letUi,hU\_\{i,h\}denote the depth\-hhprefix in the unrolled tree, whenever the trajectory reaches depthhh\. Let

Vi,h=ϕh​\(Ui,h\)V\_\{i,h\}=\\phi\_\{h\}\(U\_\{i,h\}\)be its graph projection\. Then the event that the graph trajectory visitsvvis exactly the disjoint union of the events that the unrolled trajectory visits one of the tree copies in𝒞⁡\(v\)\\mathcal\{C\}\(v\)\. Hence, at the level of indicators,

𝟏\{Vi,h=v\}=∑u∈𝒞⁡\(v\)𝟏\{Ui,h=u\}\.\\mathbf\{1\}\\\{V\_\{i,h\}=v\\\}=\\sum\_\{u\\in\\mathcal\{C\}\(v\)\}\\mathbf\{1\}\\\{U\_\{i,h\}=u\\\}\.Summing over the firstnnsimulations gives

Tv𝒢​\(n\)=∑u∈𝒞⁡\(v\)Tu𝒯​\(n\)\.T\_\{v\}^\{\\mathcal\{G\}\}\(n\)=\\sum\_\{u\\in\\mathcal\{C\}\(v\)\}T\_\{u\}^\{\\mathcal\{T\}\}\(n\)\.\(43\)Because every term in the sum is nonnegative, we immediately obtain

Tv𝒢​\(n\)≥Tu𝒯​\(n\),∀u∈𝒞⁡\(v\)\.T\_\{v\}^\{\\mathcal\{G\}\}\(n\)\\geq T\_\{u\}^\{\\mathcal\{T\}\}\(n\),\\qquad\\forall u\\in\\mathcal\{C\}\(v\)\.\(44\)
The same argument applies after conditioning on the selected action\. Indeed, for any actionaa,

𝟏​\{Vi,h=v,ai,h=a\}=∑u∈𝒞⁡\(v\)𝟏​\{Ui,h=u,ai,h=a\}\.\\mathbf\{1\}\\\{V\_\{i,h\}=v,\\ a\_\{i,h\}=a\\\}=\\sum\_\{u\\in\\mathcal\{C\}\(v\)\}\\mathbf\{1\}\\\{U\_\{i,h\}=u,\\ a\_\{i,h\}=a\\\}\.Therefore,

Tv,a𝒢​\(n\)=∑u∈𝒞⁡\(v\)Tu,a𝒯​\(n\),T\_\{v,a\}^\{\\mathcal\{G\}\}\(n\)=\\sum\_\{u\\in\\mathcal\{C\}\(v\)\}T\_\{u,a\}^\{\\mathcal\{T\}\}\(n\),\(45\)and hence

Tv,a𝒢​\(n\)≥Tu,a𝒯​\(n\),∀u∈𝒞⁡\(v\),∀a∈𝒜\.T\_\{v,a\}^\{\\mathcal\{G\}\}\(n\)\\geq T\_\{u,a\}^\{\\mathcal\{T\}\}\(n\),\\qquad\\forall u\\in\\mathcal\{C\}\(v\),\\ \\forall a\\in\\mathcal\{A\}\.\(46\)

##### Average sample\-sharing factor\.

Every simulated trajectory that reaches depthhhcontributes exactly one depth\-hhvisit in the graph representation and exactly one depth\-hhvisit in the unrolled tree representation\. Therefore,

∑v∈𝒩hTv𝒢​\(n\)=∑u∈𝒯hTu𝒯​\(n\)\.\\sum\_\{v\\in\\mathcal\{N\}\_\{h\}\}T\_\{v\}^\{\\mathcal\{G\}\}\(n\)=\\sum\_\{u\\in\\mathcal\{T\}\_\{h\}\}T\_\{u\}^\{\\mathcal\{T\}\}\(n\)\.\(47\)Let this common total be denoted byNh​\(n\)N\_\{h\}\(n\)\. IfNh​\(n\)=0N\_\{h\}\(n\)=0, then no depth\-hhnode is visited and the identity is vacuous\. Otherwise,

1\|𝒩h\|​∑v∈𝒩hTv𝒢​\(n\)=Nh​\(n\)\|𝒩h\|,1\|𝒯h\|​∑u∈𝒯hTu𝒯​\(n\)=Nh​\(n\)\|𝒯h\|\.\\frac\{1\}\{\|\\mathcal\{N\}\_\{h\}\|\}\\sum\_\{v\\in\\mathcal\{N\}\_\{h\}\}T\_\{v\}^\{\\mathcal\{G\}\}\(n\)=\\frac\{N\_\{h\}\(n\)\}\{\|\\mathcal\{N\}\_\{h\}\|\},\\qquad\\frac\{1\}\{\|\\mathcal\{T\}\_\{h\}\|\}\\sum\_\{u\\in\\mathcal\{T\}\_\{h\}\}T\_\{u\}^\{\\mathcal\{T\}\}\(n\)=\\frac\{N\_\{h\}\(n\)\}\{\|\\mathcal\{T\}\_\{h\}\|\}\.Dividing the two displays gives

\|𝒩h\|−1​∑v∈𝒩hTv𝒢​\(n\)\|𝒯h\|−1​∑u∈𝒯hTu𝒯​\(n\)=\|𝒯h\|\|𝒩h\|=1τh\.\\frac\{\|\\mathcal\{N\}\_\{h\}\|^\{\-1\}\\sum\_\{v\\in\\mathcal\{N\}\_\{h\}\}T\_\{v\}^\{\\mathcal\{G\}\}\(n\)\}\{\|\\mathcal\{T\}\_\{h\}\|^\{\-1\}\\sum\_\{u\\in\\mathcal\{T\}\_\{h\}\}T\_\{u\}^\{\\mathcal\{T\}\}\(n\)\}=\\frac\{\|\\mathcal\{T\}\_\{h\}\|\}\{\|\\mathcal\{N\}\_\{h\}\|\}=\\frac\{1\}\{\\tau\_\{h\}\}\.\(48\)Thus1/τh1/\\tau\_\{h\}is an average sample\-sharing factor over visited depth\-hhnodes\.

##### Concentration constants at leaves\.

We now prove the proof\-bound comparison by backward induction on depth\. At depthHH, the target of both a graph leafv=\(s,H\)v=\(s,H\)and every tree copyu∈𝒞⁡\(v\)u\\in\\mathcal\{C\}\(v\)is the same terminal value,

V~​\(s,H\)=V0​\(s\)\.\\widetilde\{V\}\(s,H\)=V\_\{0\}\(s\)\.The leaf estimator is an empirical average of rollout or evaluation samples\. The leaf concentration constant produced by the same proof recipe is therefore the same for the graph node and for each tree copy\. Denote this common leaf constant bycHleafc\_\{H\}^\{\\mathrm\{leaf\}\}\. Thus

cH𝒢​\(v\)=cHleaf=cH𝒯​\(u\),∀u∈𝒞⁡\(v\)\.c\_\{H\}^\{\\mathcal\{G\}\}\(v\)=c\_\{H\}^\{\\mathrm\{leaf\}\}=c\_\{H\}^\{\\mathcal\{T\}\}\(u\),\\qquad\\forall u\\in\\mathcal\{C\}\(v\)\.Moreover, sinceTv𝒢​\(n\)≥Tu𝒯​\(n\)T\_\{v\}^\{\\mathcal\{G\}\}\(n\)\\geq T\_\{u\}^\{\\mathcal\{T\}\}\(n\)by \([44](https://arxiv.org/html/2609.19956#A4.E44)\), the full leaf concentration bound is no worse in the graph:

cH𝒢​\(v\)​\(Tv𝒢​\(n\)\)−αH​ε−βH≤cH𝒯​\(u\)​\(Tu𝒯​\(n\)\)−αH​ε−βH\.c\_\{H\}^\{\\mathcal\{G\}\}\(v\)\\bigl\(T\_\{v\}^\{\\mathcal\{G\}\}\(n\)\\bigr\)^\{\-\\alpha\_\{H\}\}\\varepsilon^\{\-\\beta\_\{H\}\}\\leq c\_\{H\}^\{\\mathcal\{T\}\}\(u\)\\bigl\(T\_\{u\}^\{\\mathcal\{T\}\}\(n\)\\bigr\)^\{\-\\alpha\_\{H\}\}\\varepsilon^\{\-\\beta\_\{H\}\}\.

##### Inductive hypothesis\.

Assume that the constant comparison holds at depthh\+1h\+1\. That is, for every graph childw∈𝒢h\+1w\\in\\mathcal\{G\}\_\{h\+1\}and every tree copyz∈ϕh\+1−1​\(w\)z\\in\\phi\_\{h\+1\}^\{\-1\}\(w\),

ch\+1𝒢​\(w\)≤ch\+1𝒯​\(z\)\.c\_\{h\+1\}^\{\\mathcal\{G\}\}\(w\)\\leq c\_\{h\+1\}^\{\\mathcal\{T\}\}\(z\)\.\(49\)We show that the same comparison holds at depthhh\.

Fix a graph node

v=\(s,h\)∈𝒩hv=\(s,h\)\\in\\mathcal\{N\}\_\{h\}and a tree copy

u∈𝒞⁡\(v\)=ϕh−1​\(v\)\.u\\in\\mathcal\{C\}\(v\)=\\phi\_\{h\}^\{\-1\}\(v\)\.The graph node and the tree copy have the same physical statessand the same depthhh, so they have the same finite\-horizon Bellman target

V~​\(s,h\)\.\\widetilde\{V\}\(s,h\)\.This is the key reason the depth\-augmented representation is analytically clean: same\-depth tree copies can be merged without mixing different remaining horizons\.

##### Action\-levelQQcomparison\.

Fix an actiona∈𝒜sa\\in\\mathcal\{A\}\_\{s\}\. Let

s1,…,sMs\_\{1\},\\ldots,s\_\{M\}be the possible successor states underP\(⋅\|s,a\)P\(\\cdot\|s,a\), and write

wm=\(sm,h\+1\)w\_\{m\}=\(s\_\{m\},h\+1\)for the corresponding graph child\. For the selected tree copyuu, letzmz\_\{m\}be the tree child reached after actionaaand successor statesms\_\{m\}\. Then

zm∈ϕh\+1−1​\(wm\)\.z\_\{m\}\\in\\phi\_\{h\+1\}^\{\-1\}\(w\_\{m\}\)\.
Consider the firstnnvisits to the parent\-action pair represented by the tree copy\(u,a\)\(u,a\)\. Under the natural coupling, these same local transition samples also appear among the visits to the graph parent\-action pair\(v,a\)\(v,a\), because the graph aggregates all copies ofvv\. Therefore, for each successorsms\_\{m\}, the graph child receives at least the local visits received by the corresponding tree child\. More explicitly, ifNmnN\_\{m\}^\{n\}denotes the local number of observed transitions tosms\_\{m\}through the selected tree copy, then the graph effective child count has the form

Tmeff,𝒢​\(n\)=Nmn\+Tmext,𝒢​\(n\),T\_\{m\}^\{\\textsc\{eff\},\\mathcal\{G\}\}\(n\)=N\_\{m\}^\{n\}\+T\_\{m\}^\{\\textsc\{ext\},\\mathcal\{G\}\}\(n\),whereTmext,𝒢​\(n\)T\_\{m\}^\{\\textsc\{ext\},\\mathcal\{G\}\}\(n\)counts visits to the same graph child from other parent copies\. Hence

Tmeff,𝒢​\(n\)≥Nmn=Tmeff,𝒯​\(n\)\.T\_\{m\}^\{\\textsc\{eff\},\\mathcal\{G\}\}\(n\)\\geq N\_\{m\}^\{n\}=T\_\{m\}^\{\\textsc\{eff\},\\mathcal\{T\}\}\(n\)\.\(50\)
TheQQ\-concentration proof decomposes the estimation error into three types of terms:

reward error\+empirical\-transition error\+child\-value error\.\\text\{reward error\}\\;\+\\;\\text\{empirical\-transition error\}\\;\+\\;\\text\{child\-value error\}\.For the reward term, the graph proof uses the same reward samples as the tree copy, plus possibly additional samples from other copies\. Since the reward concentration bound is nonincreasing in the number of samples, this term cannot be worse in the graph proof\.

For the empirical\-transition term, the graph again has at least the local transition samples of the selected tree copy\. The empirical distribution concentration term is therefore no worse in the graph proof\.

For the child\-value term, the induction hypothesis gives

ch\+1𝒢\(wm\)≤ch\+1𝒯\(zm\),m=1,…,M\.c\_\{h\+1\}^\{\\mathcal\{G\}\}\(w\_\{m\}\)\\leq c\_\{h\+1\}^\{\\mathcal\{T\}\}\(z\_\{m\}\),\\qquad m=1,\\ldots,M\.In addition, the effective child sample count in the graph is no smaller than the corresponding tree\-copy child count by \([50](https://arxiv.org/html/2609.19956#A4.E50)\)\. Since the recursiveQQ\-propagation constant is assumed to be coordinatewise nondecreasing in the child value\-concentration constants and coordinatewise nonincreasing in the effective child sample counts, the graph action\-levelQQconstant cannot exceed the tree\-copy action\-levelQQconstant:

cQ,h𝒢​\(v,a\)≤cQ,h𝒯​\(u,a\)\.c\_\{Q,h\}^\{\\mathcal\{G\}\}\(v,a\)\\leq c\_\{Q,h\}^\{\\mathcal\{T\}\}\(u,a\)\.\(51\)This holds for every actiona∈𝒜sa\\in\\mathcal\{A\}\_\{s\}\.

##### Value\-constant comparison\.

The Power\-UCT value\-concentration theorem maps the vector of action\-levelQQ\-concentration constants into a value\-concentration constant\. Write this map abstractly as

chℛ​\(x\)=Φh​\(\{cQ,hℛ​\(x,a\)\}a∈𝒜s\),ℛ∈\{𝒢,𝒯\}\.c\_\{h\}^\{\\mathcal\{R\}\}\(x\)=\\Phi\_\{h\}\\left\(\\\{c\_\{Q,h\}^\{\\mathcal\{R\}\}\(x,a\)\\\}\_\{a\\in\\mathcal\{A\}\_\{s\}\}\\right\),\\qquad\\mathcal\{R\}\\in\\\{\\mathcal\{G\},\\mathcal\{T\}\\\}\.The same Power\-UCT parameters are used in both representations, so the mapΦh\\Phi\_\{h\}is the same for the graph node and the tree copy\. By assumption,Φh\\Phi\_\{h\}is coordinatewise nondecreasing\. Combining this monotonicity with \([51](https://arxiv.org/html/2609.19956#A4.E51)\) gives

ch𝒢​\(v\)=Φh​\(\{cQ,h𝒢​\(v,a\)\}a∈𝒜s\)≤Φh​\(\{cQ,h𝒯​\(u,a\)\}a∈𝒜s\)=ch𝒯​\(u\)\.c\_\{h\}^\{\\mathcal\{G\}\}\(v\)=\\Phi\_\{h\}\\left\(\\\{c\_\{Q,h\}^\{\\mathcal\{G\}\}\(v,a\)\\\}\_\{a\\in\\mathcal\{A\}\_\{s\}\}\\right\)\\leq\\Phi\_\{h\}\\left\(\\\{c\_\{Q,h\}^\{\\mathcal\{T\}\}\(u,a\)\\\}\_\{a\\in\\mathcal\{A\}\_\{s\}\}\\right\)=c\_\{h\}^\{\\mathcal\{T\}\}\(u\)\.This proves the induction step\. Since the base case at depthHHholds, backward induction gives

ch𝒢​\(v\)≤ch𝒯​\(u\),∀h,∀v∈𝒩h,∀u∈ϕh−1​\(v\)\.c\_\{h\}^\{\\mathcal\{G\}\}\(v\)\\leq c\_\{h\}^\{\\mathcal\{T\}\}\(u\),\\qquad\\forall h,\\ \\forall v\\in\\mathcal\{N\}\_\{h\},\\ \\forall u\\in\\phi\_\{h\}^\{\-1\}\(v\)\.\(52\)Takingh=0h=0gives the root comparison

c0𝒢≤c0𝒯\.c\_\{0\}^\{\\mathcal\{G\}\}\\leq c\_\{0\}^\{\\mathcal\{T\}\}\.

##### Full proof\-bound comparison\.

Combining the constant comparison with the visit\-count comparison gives the corresponding comparison for the full polynomial concentration bound\. Namely, for everyu∈𝒞⁡\(v\)u\\in\\mathcal\{C\}\(v\),

ch𝒢​\(v\)​\(Tv𝒢​\(n\)\)−αh​ε−βh\\displaystyle c\_\{h\}^\{\\mathcal\{G\}\}\(v\)\\bigl\(T\_\{v\}^\{\\mathcal\{G\}\}\(n\)\\bigr\)^\{\-\\alpha\_\{h\}\}\\varepsilon^\{\-\\beta\_\{h\}\}≤ch𝒯​\(u\)​\(Tv𝒢​\(n\)\)−αh​ε−βh\\displaystyle\\leq c\_\{h\}^\{\\mathcal\{T\}\}\(u\)\\bigl\(T\_\{v\}^\{\\mathcal\{G\}\}\(n\)\\bigr\)^\{\-\\alpha\_\{h\}\}\\varepsilon^\{\-\\beta\_\{h\}\}\(53\)≤ch𝒯​\(u\)​\(Tu𝒯​\(n\)\)−αh​ε−βh,\\displaystyle\\leq c\_\{h\}^\{\\mathcal\{T\}\}\(u\)\\bigl\(T\_\{u\}^\{\\mathcal\{T\}\}\(n\)\\bigr\)^\{\-\\alpha\_\{h\}\}\\varepsilon^\{\-\\beta\_\{h\}\},\(54\)where the first inequality uses \([52](https://arxiv.org/html/2609.19956#A4.E52)\), and the second usesTv𝒢​\(n\)≥Tu𝒯​\(n\)T\_\{v\}^\{\\mathcal\{G\}\}\(n\)\\geq T\_\{u\}^\{\\mathcal\{T\}\}\(n\)\. Therefore the graph representation cannot produce a larger same\-trajectory proof bound than any corresponding tree copy\.

Finally, \([48](https://arxiv.org/html/2609.19956#A4.E48)\) gives the stated average sample\-sharing factor1/τh1/\\tau\_\{h\}\. This completes the proof\. ∎

### D\.4Why Depth Augmentation Is Necessary: The Cross\-Depth Merging Bias

A natural question is whether we can go further and merge nodes*across different depths*: treat\(s,3\)\(s,3\)and\(s,5\)\(s,5\)as the same node since they correspond to the same physical state\. We show that this introduces an irreducible bias that fundamentally prevents convergence to the correct value\.

###### Proposition 3\(Cross\-depth merging can introduce irreducible bias\)\.

Consider a physical statessthat is visited at two depthsh1<h2h\_\{1\}<h\_\{2\}under a fixed finite horizonH<∞H<\\infty\. Let

V~​\(s,h\)=\(ℬH−h​V0\)​\(s\)\\widetilde\{V\}\(s,h\)=\(\\mathcal\{B\}^\{H\-h\}V\_\{0\}\)\(s\)be the depth\-hhtruncated Bellman target\. A full\-merge estimator that stores a single statisticV^​\(s\)\\widehat\{V\}\(s\)for both depths generally does not target eitherV~​\(s,h1\)\\widetilde\{V\}\(s,h\_\{1\}\)orV~​\(s,h2\)\\widetilde\{V\}\(s,h\_\{2\}\)individually\.

More precisely, suppose the empirical fractions of updates arriving from depthsh1h\_\{1\}andh2h\_\{2\}converge to positive limits

nhinh1\+nh2⟶ρi,ρi\>0,ρ1\+ρ2=1\.\\frac\{n\_\{h\_\{i\}\}\}\{n\_\{h\_\{1\}\}\+n\_\{h\_\{2\}\}\}\\longrightarrow\\rho\_\{i\},\\qquad\\rho\_\{i\}\>0,\\qquad\\rho\_\{1\}\+\\rho\_\{2\}=1\.Then the limiting target of the shared statistic is the convex mixture

V¯​\(s\)=ρ1​V~​\(s,h1\)\+ρ2​V~​\(s,h2\)\.\\bar\{V\}\(s\)=\\rho\_\{1\}\\widetilde\{V\}\(s,h\_\{1\}\)\+\\rho\_\{2\}\\widetilde\{V\}\(s,h\_\{2\}\)\.\(55\)Consequently,

\|V¯​\(s\)−V~​\(s,h1\)\|=ρ2​\|V~​\(s,h2\)−V~​\(s,h1\)\|,\|\\bar\{V\}\(s\)\-\\widetilde\{V\}\(s,h\_\{1\}\)\|=\\rho\_\{2\}\|\\widetilde\{V\}\(s,h\_\{2\}\)\-\\widetilde\{V\}\(s,h\_\{1\}\)\|,\(56\)and similarly

\|V¯​\(s\)−V~​\(s,h2\)\|=ρ1​\|V~​\(s,h2\)−V~​\(s,h1\)\|\.\|\\bar\{V\}\(s\)\-\\widetilde\{V\}\(s,h\_\{2\}\)\|=\\rho\_\{1\}\|\\widetilde\{V\}\(s,h\_\{2\}\)\-\\widetilde\{V\}\(s,h\_\{1\}\)\|\.\(57\)Thus, wheneverV~​\(s,h1\)≠V~​\(s,h2\)\\widetilde\{V\}\(s,h\_\{1\}\)\\neq\\widetilde\{V\}\(s,h\_\{2\}\)and both depths have nonzero asymptotic mass, the bias does not vanish as the number of visits grows\.

Moreover, the possible size of this local bias is bounded by the cross\-depth gap:

\|V¯​\(s\)−V~​\(s,hi\)\|≤δ⁡\(s\),i∈\{1,2\},\|\\bar\{V\}\(s\)\-\\widetilde\{V\}\(s,h\_\{i\}\)\|\\leq\\delta\(s\),\\qquad i\\in\\\{1,2\\\},\(58\)whereδ⁡\(s\)\\delta\(s\)satisfies the bound in Lemma[3](https://arxiv.org/html/2609.19956#Thmlemma3)\.

###### Proof\.

The mixture expression \([55](https://arxiv.org/html/2609.19956#A4.E55)\) follows from the law of large numbers for a shared average whose depth\-hih\_\{i\}updates have meanV~​\(s,hi\)\\widetilde\{V\}\(s,h\_\{i\}\)and whose empirical depth proportions converge toρi\\rho\_\{i\}\. SubtractingV~​\(s,h1\)\\widetilde\{V\}\(s,h\_\{1\}\)gives

V¯​\(s\)−V~​\(s,h1\)\\displaystyle\\bar\{V\}\(s\)\-\\widetilde\{V\}\(s,h\_\{1\}\)=ρ1​V~​\(s,h1\)\+ρ2​V~​\(s,h2\)−V~​\(s,h1\)\\displaystyle=\\rho\_\{1\}\\widetilde\{V\}\(s,h\_\{1\}\)\+\\rho\_\{2\}\\widetilde\{V\}\(s,h\_\{2\}\)\-\\widetilde\{V\}\(s,h\_\{1\}\)\(59\)=ρ2​\(V~​\(s,h2\)−V~​\(s,h1\)\),\\displaystyle=\\rho\_\{2\}\\left\(\\widetilde\{V\}\(s,h\_\{2\}\)\-\\widetilde\{V\}\(s,h\_\{1\}\)\\right\),\(60\)which proves \([56](https://arxiv.org/html/2609.19956#A4.E56)\)\. The corresponding identity for depthh2h\_\{2\}is identical\.

The upper bound \([58](https://arxiv.org/html/2609.19956#A4.E58)\) follows immediately from the definition

δ⁡\(s\)=maxh,h′∈𝒟⁡\(s\)⁡\|V~​\(s,h\)−V~​\(s,h′\)\|\.\\delta\(s\)=\\max\_\{h,h^\{\\prime\}\\in\\mathcal\{D\}\(s\)\}\|\\widetilde\{V\}\(s,h\)\-\\widetilde\{V\}\(s,h^\{\\prime\}\)\|\.
It remains to show that unequal depth\-specific targets occur in general\. Consider the one\-state MDP with a single action, deterministic self\-loop, rewardR⁡\(s,a,s\)=1R\(s,a,s\)=1, discountγ∈\(0,1\)\\gamma\\in\(0,1\), and rollout valueV0​\(s\)=0V\_\{0\}\(s\)=0\. Then

V⋆​\(s\)=11−γ,V0​\(s\)≠V⋆​\(s\)\.V^\{\\star\}\(s\)=\\frac\{1\}\{1\-\\gamma\},\\qquad V\_\{0\}\(s\)\\neq V^\{\\star\}\(s\)\.For remaining horizonH−hH\-h, the truncated value is

V~​\(s,h\)=∑t=0H−h−1γt=1−γH−h1−γ\.\\widetilde\{V\}\(s,h\)=\\sum\_\{t=0\}^\{H\-h\-1\}\\gamma^\{t\}=\\frac\{1\-\\gamma^\{H\-h\}\}\{1\-\\gamma\}\.Therefore, forh1<h2h\_\{1\}<h\_\{2\},

V~​\(s,h1\)−V~​\(s,h2\)\\displaystyle\\widetilde\{V\}\(s,h\_\{1\}\)\-\\widetilde\{V\}\(s,h\_\{2\}\)=1−γH−h11−γ−1−γH−h21−γ\\displaystyle=\\frac\{1\-\\gamma^\{H\-h\_\{1\}\}\}\{1\-\\gamma\}\-\\frac\{1\-\\gamma^\{H\-h\_\{2\}\}\}\{1\-\\gamma\}\(61\)=γH−h2−γH−h11−γ\>0\.\\displaystyle=\\frac\{\\gamma^\{H\-h\_\{2\}\}\-\\gamma^\{H\-h\_\{1\}\}\}\{1\-\\gamma\}\>0\.\(62\)Hence, if both depths are assigned positive limiting weights, the full\-merge statistic has a non\-vanishing bias relative to each depth\-specific target\. ∎

###### Lemma 3\(Cross\-depth gap bound\)\.

Assumeγ∈\(0,1\)\\gamma\\in\(0,1\)and let

V~​\(s,h\)=\(ℬH−h​V0\)​\(s\)\\widetilde\{V\}\(s,h\)=\(\\mathcal\{B\}^\{H\-h\}V\_\{0\}\)\(s\)be the depth\-hhtruncated Bellman value\. For any statessand any two depthsh1<h2h\_\{1\}<h\_\{2\}, we have

\|V~​\(s,h1\)−V~​\(s,h2\)\|≤γH−h2−γH−h11−γ​‖ℬ​V0−V0‖∞\.\\left\|\\widetilde\{V\}\(s,h\_\{1\}\)\-\\widetilde\{V\}\(s,h\_\{2\}\)\\right\|\\leq\\frac\{\\gamma^\{H\-h\_\{2\}\}\-\\gamma^\{H\-h\_\{1\}\}\}\{1\-\\gamma\}\\,\\\|\\mathcal\{B\}V\_\{0\}\-V\_\{0\}\\\|\_\{\\infty\}\.\(63\)Consequently, for

δ⁡\(s\)=maxh1,h2∈𝒟⁡\(s\)⁡\|V~​\(s,h1\)−V~​\(s,h2\)\|,\\delta\(s\)=\\max\_\{h\_\{1\},h\_\{2\}\\in\\mathcal\{D\}\(s\)\}\|\\widetilde\{V\}\(s,h\_\{1\}\)\-\\widetilde\{V\}\(s,h\_\{2\}\)\|,we have

δ⁡\(s\)≤γH−hmax​\(s\)−γH−hmin​\(s\)1−γ​‖ℬ​V0−V0‖∞\.\\delta\(s\)\\leq\\frac\{\\gamma^\{H\-h\_\{\\max\}\(s\)\}\-\\gamma^\{H\-h\_\{\\min\}\(s\)\}\}\{1\-\\gamma\}\\,\\\|\\mathcal\{B\}V\_\{0\}\-V\_\{0\}\\\|\_\{\\infty\}\.\(64\)Moreover,

δ⁡\(s\)≤\(1\+γ\)​\(γH−hmax​\(s\)−γH−hmin​\(s\)\)1−γ​‖V⋆−V0‖∞\.\\delta\(s\)\\leq\\frac\{\(1\+\\gamma\)\\left\(\\gamma^\{H\-h\_\{\\max\}\(s\)\}\-\\gamma^\{H\-h\_\{\\min\}\(s\)\}\\right\)\}\{1\-\\gamma\}\\,\\\|V^\{\\star\}\-V\_\{0\}\\\|\_\{\\infty\}\.\(65\)

###### Proof\.

The caseh1=h2h\_\{1\}=h\_\{2\}is trivial, so assumeh1<h2h\_\{1\}<h\_\{2\}\. Let

k1=H−h1,k2=H−h2,d=k1−k2=h2−h1\.k\_\{1\}=H\-h\_\{1\},\\qquad k\_\{2\}=H\-h\_\{2\},\\qquad d=k\_\{1\}\-k\_\{2\}=h\_\{2\}\-h\_\{1\}\.Thenk1\>k2k\_\{1\}\>k\_\{2\}and

V~​\(⋅,h1\)=ℬk1​V0=ℬk2​\(ℬd​V0\),V~​\(⋅,h2\)=ℬk2​V0\.\\widetilde\{V\}\(\\cdot,h\_\{1\}\)=\\mathcal\{B\}^\{k\_\{1\}\}V\_\{0\}=\\mathcal\{B\}^\{k\_\{2\}\}\(\\mathcal\{B\}^\{d\}V\_\{0\}\),\\qquad\\widetilde\{V\}\(\\cdot,h\_\{2\}\)=\\mathcal\{B\}^\{k\_\{2\}\}V\_\{0\}\.Sinceℬ\\mathcal\{B\}is aγ\\gamma\-contraction in sup norm,

‖V~​\(⋅,h1\)−V~​\(⋅,h2\)‖∞\\displaystyle\\\|\\widetilde\{V\}\(\\cdot,h\_\{1\}\)\-\\widetilde\{V\}\(\\cdot,h\_\{2\}\)\\\|\_\{\\infty\}=‖ℬk2​\(ℬd​V0\)−ℬk2​V0‖∞\\displaystyle=\\left\\\|\\mathcal\{B\}^\{k\_\{2\}\}\(\\mathcal\{B\}^\{d\}V\_\{0\}\)\-\\mathcal\{B\}^\{k\_\{2\}\}V\_\{0\}\\right\\\|\_\{\\infty\}\(66\)≤γk2​‖ℬd​V0−V0‖∞\.\\displaystyle\\leq\\gamma^\{k\_\{2\}\}\\left\\\|\\mathcal\{B\}^\{d\}V\_\{0\}\-V\_\{0\}\\right\\\|\_\{\\infty\}\.\(67\)Now use the telescoping decomposition

ℬd​V0−V0=∑j=0d−1\(ℬj\+1​V0−ℬj​V0\)\.\\mathcal\{B\}^\{d\}V\_\{0\}\-V\_\{0\}=\\sum\_\{j=0\}^\{d\-1\}\\left\(\\mathcal\{B\}^\{j\+1\}V\_\{0\}\-\\mathcal\{B\}^\{j\}V\_\{0\}\\right\)\.Again by contraction,

‖ℬj\+1​V0−ℬj​V0‖∞≤γj​‖ℬ​V0−V0‖∞\.\\left\\\|\\mathcal\{B\}^\{j\+1\}V\_\{0\}\-\\mathcal\{B\}^\{j\}V\_\{0\}\\right\\\|\_\{\\infty\}\\leq\\gamma^\{j\}\\\|\\mathcal\{B\}V\_\{0\}\-V\_\{0\}\\\|\_\{\\infty\}\.Therefore,

‖ℬd​V0−V0‖∞\\displaystyle\\left\\\|\\mathcal\{B\}^\{d\}V\_\{0\}\-V\_\{0\}\\right\\\|\_\{\\infty\}≤∑j=0d−1γj​‖ℬ​V0−V0‖∞\\displaystyle\\leq\\sum\_\{j=0\}^\{d\-1\}\\gamma^\{j\}\\\|\\mathcal\{B\}V\_\{0\}\-V\_\{0\}\\\|\_\{\\infty\}\(68\)=1−γd1−γ​‖ℬ​V0−V0‖∞\.\\displaystyle=\\frac\{1\-\\gamma^\{d\}\}\{1\-\\gamma\}\\\|\\mathcal\{B\}V\_\{0\}\-V\_\{0\}\\\|\_\{\\infty\}\.\(69\)Combining the last two displays gives

‖V~​\(⋅,h1\)−V~​\(⋅,h2\)‖∞≤γk2−γk2\+d1−γ​‖ℬ​V0−V0‖∞\.\\\|\\widetilde\{V\}\(\\cdot,h\_\{1\}\)\-\\widetilde\{V\}\(\\cdot,h\_\{2\}\)\\\|\_\{\\infty\}\\leq\\frac\{\\gamma^\{k\_\{2\}\}\-\\gamma^\{k\_\{2\}\+d\}\}\{1\-\\gamma\}\\\|\\mathcal\{B\}V\_\{0\}\-V\_\{0\}\\\|\_\{\\infty\}\.Sincek2=H−h2k\_\{2\}=H\-h\_\{2\}andk2\+d=H−h1k\_\{2\}\+d=H\-h\_\{1\}, this is exactly

‖V~​\(⋅,h1\)−V~​\(⋅,h2\)‖∞≤γH−h2−γH−h11−γ​‖ℬ​V0−V0‖∞\.\\\|\\widetilde\{V\}\(\\cdot,h\_\{1\}\)\-\\widetilde\{V\}\(\\cdot,h\_\{2\}\)\\\|\_\{\\infty\}\\leq\\frac\{\\gamma^\{H\-h\_\{2\}\}\-\\gamma^\{H\-h\_\{1\}\}\}\{1\-\\gamma\}\\\|\\mathcal\{B\}V\_\{0\}\-V\_\{0\}\\\|\_\{\\infty\}\.Taking the maximum overh1,h2∈𝒟⁡\(s\)h\_\{1\},h\_\{2\}\\in\\mathcal\{D\}\(s\)gives \([64](https://arxiv.org/html/2609.19956#A4.E64)\), because the right\-hand side is maximized byh1=hmin​\(s\)h\_\{1\}=h\_\{\\min\}\(s\)andh2=hmax​\(s\)h\_\{2\}=h\_\{\\max\}\(s\)\.

Finally, sinceV⋆=ℬ​V⋆V^\{\\star\}=\\mathcal\{B\}V^\{\\star\},

‖ℬ​V0−V0‖∞\\displaystyle\\\|\\mathcal\{B\}V\_\{0\}\-V\_\{0\}\\\|\_\{\\infty\}=‖\(ℬ​V0−ℬ​V⋆\)\+\(V⋆−V0\)‖∞\\displaystyle=\\\|\(\\mathcal\{B\}V\_\{0\}\-\\mathcal\{B\}V^\{\\star\}\)\+\(V^\{\\star\}\-V\_\{0\}\)\\\|\_\{\\infty\}\(70\)≤‖ℬ​V0−ℬ​V⋆‖∞\+‖V⋆−V0‖∞\\displaystyle\\leq\\\|\\mathcal\{B\}V\_\{0\}\-\\mathcal\{B\}V^\{\\star\}\\\|\_\{\\infty\}\+\\\|V^\{\\star\}\-V\_\{0\}\\\|\_\{\\infty\}\(71\)≤\(1\+γ\)​‖V⋆−V0‖∞\.\\displaystyle\\leq\(1\+\\gamma\)\\\|V^\{\\star\}\-V\_\{0\}\\\|\_\{\\infty\}\.\(72\)Substituting this into \([64](https://arxiv.org/html/2609.19956#A4.E64)\) proves \([65](https://arxiv.org/html/2609.19956#A4.E65)\)\. ∎

###### Definition 4\(Empirical effective target for GS\-Power\-UCT\-F\)\.

LetTs,a,h​\(n\)T\_\{s,a,h\}\(n\)denote the number of times actionaawas selected at physical statesswhen entered at trajectory depthhhduring the firstnnsimulations, and writeTs,a​\(n\)=∑hTs,a,h​\(n\)T\_\{s,a\}\(n\)=\\sum\_\{h\}T\_\{s,a,h\}\(n\)\. Define the depth\-mixture weightsωn,h​\(s,a\)=Ts,a,h​\(n\)/Ts,a​\(n\)\\omega\_\{n,h\}\(s,a\)=T\_\{s,a,h\}\(n\)/T\_\{s,a\}\(n\)whenTs,a​\(n\)\>0T\_\{s,a\}\(n\)\>0, and arbitrarily on the simplex otherwise\. ForV:𝒮→ℝV:\\mathcal\{S\}\\to\\mathbb\{R\}, letBh​V​\(s′\)=V0​\(s′\)B\_\{h\}V\(s^\{\\prime\}\)=V\_\{0\}\(s^\{\\prime\}\)ifh\+1=Hh\+1=HandV⁡\(s′\)V\(s^\{\\prime\}\)otherwise\. The empirical full\-merge Bellman operator is

\(𝒯F,nH​V\)​\(s\)=max⁡∑h=0H−1a∈𝒜s⁡ωn,h​\(s,a\)​∑s′P⁡\(s′\|s,a\)​\[R⁡\(s,a,s′\)\+γ​Bh​V​\(s′\)\],\(\\mathcal\{T\}\_\{F,n\}^\{H\}V\)\(s\)=\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}\\sum\_\{h=0\}^\{H\-1\}\\omega\_\{n,h\}\(s,a\)\\sum\_\{s^\{\\prime\}\}P\(s^\{\\prime\}\|s,a\)\\left\[R\(s,a,s^\{\\prime\}\)\+\\gamma B\_\{h\}V\(s^\{\\prime\}\)\\right\],\(73\)which is aγ\\gamma\-contraction; we writeV¯n\\bar\{V\}\_\{n\}for its unique fixed point and define the correspondingQQ\-target

Q¯n​\(s,a\)=∑h=0H−1ωn,h​\(s,a\)​∑s′P⁡\(s′\|s,a\)​\[R⁡\(s,a,s′\)\+γ​Bh​V¯n​\(s′\)\]\.\\bar\{Q\}\_\{n\}\(s,a\)=\\sum\_\{h=0\}^\{H\-1\}\\omega\_\{n,h\}\(s,a\)\\sum\_\{s^\{\\prime\}\}P\(s^\{\\prime\}\|s,a\)\\left\[R\(s,a,s^\{\\prime\}\)\+\\gamma B\_\{h\}\\bar\{V\}\_\{n\}\(s^\{\\prime\}\)\\right\]\.\(74\)

### D\.5Proof of Theorem[3](https://arxiv.org/html/2609.19956#Thmtheorem3)

Before proving Theorem[3](https://arxiv.org/html/2609.19956#Thmtheorem3), we establish the following results\.

###### Lemma 4\(RobustQQ\-propagation under full merging\)\.

Fix a physical state\-action pair\(s,a\)\(s,a\)in the full\-merge algorithm and consider the firstt≥1t\\geq 1updates to the shared statisticQ^​\(s,a\)\\widehat\{Q\}\(s,a\), where theii\-th update arrives whenssis entered at depthhih\_\{i\}with sampled successorSi∼P\(⋅∣s,a\)S\_\{i\}\\sim P\(\\cdot\\mid s,a\), rewardRiR\_\{i\}, and recursive child returnWiW\_\{i\}from\(Si,hi\+1\)\(S\_\{i\},h\_\{i\}\+1\)\. For any reference depthhh, letQ~​\(s,h,a\)=∑s′P⁡\(s′∣s,a\)​\[R⁡\(s,a,s′\)\+γ​V~​\(s′,h\+1\)\]\\widetilde\{Q\}\(s,h,a\)=\\sum\_\{s^\{\\prime\}\}P\(s^\{\\prime\}\\mid s,a\)\[R\(s,a,s^\{\\prime\}\)\+\\gamma\\widetilde\{V\}\(s^\{\\prime\},h\+1\)\]and define the cross\-depth driftδQ,t​\(s,a,h\):=max1≤i≤t⁡\|Q~​\(s,hi,a\)−Q~​\(s,h,a\)\|\\delta\_\{Q,t\}\(s,a;h\):=\\max\_\{1\\leq i\\leq t\}\|\\widetilde\{Q\}\(s,h\_\{i\},a\)\-\\widetilde\{Q\}\(s,h,a\)\|\. Assume rewards and value estimates are bounded with reward range≤LR\\leq L\_\{R\}and\|Wi\|,\|V~​\(Si,hi\+1\)\|≤LV\|W\_\{i\}\|,\|\\widetilde\{V\}\(S\_\{i\},h\_\{i\}\+1\)\|\\leq L\_\{V\}a\.s\., and that there exist constantsB≥0B\\geq 0,cV\>0c\_\{V\}\>0,α\>0\\alpha\>0,β\>1\\beta\>1withρ:=α/β∈\(0,1\)\\rho:=\\alpha/\\beta\\in\(0,1\)such that for everyiiandu\>0u\>0,

ℙ⁡\(\|Wi−V~​\(Si,hi\+1\)\|\>B\+u\|ℱi,1\)≤cV​Ji−α​u−β,\\mathbb\{P\}\\left\(\\left\|W\_\{i\}\-\\widetilde\{V\}\(S\_\{i\},h\_\{i\}\+1\)\\right\|\>B\+u\\middle\|\\mathcal\{F\}\_\{i,1\}\\right\)\\leq c\_\{V\}J\_\{i\}^\{\-\\alpha\}u^\{\-\\beta\},\(75\)whereℱi,1\\mathcal\{F\}\_\{i,1\}is the history after observing\(Si,Ri\)\(S\_\{i\},R\_\{i\}\)but before the recursive child randomness, andJi:=1\+\#⁡\{r<i:\(Sr,hr\)=\(Si,hi\)\}J\_\{i\}:=1\+\\\#\\\{r<i:\(S\_\{r\},h\_\{r\}\)=\(S\_\{i\},h\_\{i\}\)\\\}is the local occurrence count of the same successor\-depth pair among the firstiiupdates\. Then there exist constantsκ,σQ<∞\\kappa,\\sigma\_\{Q\}<\\infty, independent oftt, such that for everyε\>0\\varepsilon\>0,

ℙ⁡\(\|Q^t​\(s,a\)−Q~​\(s,h,a\)\|\>δQ,t​\(s,a,h\)\+γ​B\+γ​κ​t−ρ\+ε\)≤2​exp⁡\(−t​ε22​σQ2\)\.\\mathbb\{P\}\\left\(\\left\|\\widehat\{Q\}\_\{t\}\(s,a\)\-\\widetilde\{Q\}\(s,h,a\)\\right\|\>\\delta\_\{Q,t\}\(s,a;h\)\+\\gamma B\+\\gamma\\kappa t^\{\-\\rho\}\+\\varepsilon\\right\)\\leq 2\\exp\\left\(\-\\tfrac\{t\\varepsilon^\{2\}\}\{2\\sigma\_\{Q\}^\{2\}\}\\right\)\.\(76\)Consequently, for anyα¯,β¯\\bar\{\\alpha\},\\bar\{\\beta\}withβ¯\>1\\bar\{\\beta\}\>1,2​α¯≤β¯2\\bar\{\\alpha\}\\leq\\bar\{\\beta\}, andα¯≤ρ​β¯\\bar\{\\alpha\}\\leq\\rho\\bar\{\\beta\}, there existsCQ<∞C\_\{Q\}<\\inftyindependent ofttsuch that

ℙ⁡\(\|Q^t​\(s,a\)−Q~​\(s,h,a\)\|\>δQ,t​\(s,a,h\)\+γ​B\+ε\)≤CQ​t−α¯​ε−β¯;\\mathbb\{P\}\\left\(\\left\|\\widehat\{Q\}\_\{t\}\(s,a\)\-\\widetilde\{Q\}\(s,h,a\)\\right\|\>\\delta\_\{Q,t\}\(s,a;h\)\+\\gamma B\+\\varepsilon\\right\)\\leq C\_\{Q\}t^\{\-\\bar\{\\alpha\}\}\\varepsilon^\{\-\\bar\{\\beta\}\};\(77\)in particular, ifB=BΔ≥δQ,t​\(s,a,h\)/\(1−γ\)B=B\_\{\\Delta\}\\geq\\delta\_\{Q,t\}\(s,a;h\)/\(1\-\\gamma\), then

ℙ⁡\(\|Q^t​\(s,a\)−Q~​\(s,h,a\)\|\>BΔ\+ε\)≤CQ​t−α¯​ε−β¯\.\\mathbb\{P\}\\left\(\\left\|\\widehat\{Q\}\_\{t\}\(s,a\)\-\\widetilde\{Q\}\(s,h,a\)\\right\|\>B\_\{\\Delta\}\+\\varepsilon\\right\)\\leq C\_\{Q\}t^\{\-\\bar\{\\alpha\}\}\\varepsilon^\{\-\\bar\{\\beta\}\}\.\(78\)

###### Proof\.

Let

qi:=Q~​\(s,hi,a\),qh:=Q~​\(s,h,a\),vi:=V~​\(Si,hi\+1\)\.q\_\{i\}:=\\widetilde\{Q\}\(s,h\_\{i\},a\),\\qquad q\_\{h\}:=\\widetilde\{Q\}\(s,h,a\),\\qquad v\_\{i\}:=\\widetilde\{V\}\(S\_\{i\},h\_\{i\}\+1\)\.Theii\-th backup satisfies

Yi−qh=\[Ri\+γ​vi−qi\]⏟Ai\+γ​\[Wi−vi\]⏟ei\+\[qi−qh\]⏟di\.Y\_\{i\}\-q\_\{h\}=\\underbrace\{\\left\[R\_\{i\}\+\\gamma v\_\{i\}\-q\_\{i\}\\right\]\}\_\{A\_\{i\}\}\+\\gamma\\underbrace\{\\left\[W\_\{i\}\-v\_\{i\}\\right\]\}\_\{e\_\{i\}\}\+\\underbrace\{\\left\[q\_\{i\}\-q\_\{h\}\\right\]\}\_\{d\_\{i\}\}\.\(79\)Averaging overi=1,…,ti=1,\\ldots,t, we obtain

Q^t​\(s,a\)−qh=1t​∑i=1tAi\+γt​∑i=1tei\+1t​∑i=1tdi\.\\widehat\{Q\}\_\{t\}\(s,a\)\-q\_\{h\}=\\frac\{1\}\{t\}\\sum\_\{i=1\}^\{t\}A\_\{i\}\+\\frac\{\\gamma\}\{t\}\\sum\_\{i=1\}^\{t\}e\_\{i\}\+\\frac\{1\}\{t\}\\sum\_\{i=1\}^\{t\}d\_\{i\}\.\(80\)
We bound the three terms separately\.

First, by definition ofδQ,t​\(s,a,h\)\\delta\_\{Q,t\}\(s,a;h\),

\|di\|=\|Q~​\(s,hi,a\)−Q~​\(s,h,a\)\|≤δQ,t​\(s,a,h\),\|d\_\{i\}\|=\\left\|\\widetilde\{Q\}\(s,h\_\{i\},a\)\-\\widetilde\{Q\}\(s,h,a\)\\right\|\\leq\\delta\_\{Q,t\}\(s,a;h\),and therefore

\|1t​∑i=1tdi\|≤δQ,t​\(s,a,h\)\.\\left\|\\frac\{1\}\{t\}\\sum\_\{i=1\}^\{t\}d\_\{i\}\\right\|\\leq\\delta\_\{Q,t\}\(s,a;h\)\.\(81\)
Second, consider the transition\-reward term

Ai=Ri\+γ​V~​\(Si,hi\+1\)−Q~​\(s,hi,a\)\.A\_\{i\}=R\_\{i\}\+\\gamma\\widetilde\{V\}\(S\_\{i\},h\_\{i\}\+1\)\-\\widetilde\{Q\}\(s,h\_\{i\},a\)\.Letℱi,0\\mathcal\{F\}\_\{i,0\}be the history immediately before drawing\(Si,Ri\)\(S\_\{i\},R\_\{i\}\)on theii\-th update to\(s,a\)\(s,a\)\. Conditional onℱi,0\\mathcal\{F\}\_\{i,0\}, the depthhih\_\{i\}is fixed, and

𝔼⁡\[Ri\+γ​V~​\(Si,hi\+1\)\|ℱi,0\]=Q~​\(s,hi,a\)\.\\mathbb\{E\}\\left\[R\_\{i\}\+\\gamma\\widetilde\{V\}\(S\_\{i\},h\_\{i\}\+1\)\\middle\|\\mathcal\{F\}\_\{i,0\}\\right\]=\\widetilde\{Q\}\(s,h\_\{i\},a\)\.Hence

𝔼⁡\[Ai∣ℱi,0\]=0\.\\mathbb\{E\}\[A\_\{i\}\\mid\\mathcal\{F\}\_\{i,0\}\]=0\.\(82\)ThusAiA\_\{i\}is a martingale\-difference term\. Since the reward range is at mostLRL\_\{R\}and\|V~\|≤LV\|\\widetilde\{V\}\|\\leq L\_\{V\}, there exists a finite constant

LA:=LR\+2​γ​LVL\_\{A\}:=L\_\{R\}\+2\\gamma L\_\{V\}such that

almost surely\.

Third, decompose the child\-estimation error

ei=Wi−vie\_\{i\}=W\_\{i\}\-v\_\{i\}into its predictable and centered parts\. Define

bi:=𝔼⁡\[ei∣ℱi,1\],ξi:=ei−bi\.b\_\{i\}:=\\mathbb\{E\}\[e\_\{i\}\\mid\\mathcal\{F\}\_\{i,1\}\],\\qquad\\xi\_\{i\}:=e\_\{i\}\-b\_\{i\}\.Then

𝔼⁡\[ξi∣ℱi,1\]=0\.\\mathbb\{E\}\[\\xi\_\{i\}\\mid\\mathcal\{F\}\_\{i,1\}\]=0\.\(83\)Moreover, because\|Wi\|≤LV\|W\_\{i\}\|\\leq L\_\{V\}and\|vi\|≤LV\|v\_\{i\}\|\\leq L\_\{V\},

\|ei\|≤2​LV\.\|e\_\{i\}\|\\leq 2L\_\{V\}\.Thus

\|ξi\|=\|ei−𝔼⁡\[ei∣ℱi,1\]\|≤4​LV\.\|\\xi\_\{i\}\|=\|e\_\{i\}\-\\mathbb\{E\}\[e\_\{i\}\\mid\\mathcal\{F\}\_\{i,1\}\]\|\\leq 4L\_\{V\}\.Set

Lξ:=4​LV\.L\_\{\\xi\}:=4L\_\{V\}\.
We now bound the predictable child biasbib\_\{i\}\. By Jensen’s inequality,

\|bi\|≤𝔼⁡\[\|ei\|∣ℱi,1\]\.\|b\_\{i\}\|\\leq\\mathbb\{E\}\[\|e\_\{i\}\|\\mid\\mathcal\{F\}\_\{i,1\}\]\.Also,

\|ei\|≤B\+\(\|ei\|−B\)\+\.\|e\_\{i\}\|\\leq B\+\\bigl\(\|e\_\{i\}\|\-B\\bigr\)\_\{\+\}\.Therefore,

\|bi\|≤B\+𝔼⁡\[\(\|ei\|−B\)\+\|ℱi,1\]\.\|b\_\{i\}\|\\leq B\+\\mathbb\{E\}\\left\[\\bigl\(\|e\_\{i\}\|\-B\\bigr\)\_\{\+\}\\middle\|\\mathcal\{F\}\_\{i,1\}\\right\]\.\(84\)Using the tail\-integral formula,

𝔼⁡\[\(\|ei\|−B\)\+\|ℱi,1\]=∫0∞ℙ⁡\(\|ei\|\>B\+u\|ℱi,1\)​𝑑u\.\\mathbb\{E\}\\left\[\\bigl\(\|e\_\{i\}\|\-B\\bigr\)\_\{\+\}\\middle\|\\mathcal\{F\}\_\{i,1\}\\right\]=\\int\_\{0\}^\{\\infty\}\\mathbb\{P\}\\left\(\|e\_\{i\}\|\>B\+u\\middle\|\\mathcal\{F\}\_\{i,1\}\\right\)\\,du\.\(85\)Let

ηi:=Ji−α/β=Ji−ρ\.\\eta\_\{i\}:=J\_\{i\}^\{\-\\alpha/\\beta\}=J\_\{i\}^\{\-\\rho\}\.Splitting the integral atηi\\eta\_\{i\}and using condition \([75](https://arxiv.org/html/2609.19956#A4.E75)\), we get

∫0∞ℙ⁡\(\|ei\|\>B\+u\|ℱi,1\)​𝑑u\\displaystyle\\int\_\{0\}^\{\\infty\}\\mathbb\{P\}\\left\(\|e\_\{i\}\|\>B\+u\\middle\|\\mathcal\{F\}\_\{i,1\}\\right\)\\,du≤ηi\+∫ηi∞cV​Ji−α​u−β​𝑑u\\displaystyle\\leq\\eta\_\{i\}\+\\int\_\{\\eta\_\{i\}\}^\{\\infty\}c\_\{V\}J\_\{i\}^\{\-\\alpha\}u^\{\-\\beta\}\\,du=ηi\+cVβ−1​Ji−α​ηi1−β\.\\displaystyle=\\eta\_\{i\}\+\\frac\{c\_\{V\}\}\{\\beta\-1\}J\_\{i\}^\{\-\\alpha\}\\eta\_\{i\}^\{1\-\\beta\}\.Sinceηi=Ji−α/β\\eta\_\{i\}=J\_\{i\}^\{\-\\alpha/\\beta\},

Ji−αηi1−β=Ji−αJi−\(α/β\)​\(1−β\)=Ji−α/β=Ji−ρ\.J\_\{i\}^\{\-\\alpha\}\\eta\_\{i\}^\{1\-\\beta\}=J\_\{i\}^\{\-\\alpha\}J\_\{i\}^\{\-\(\\alpha/\\beta\)\(1\-\\beta\)\}=J\_\{i\}^\{\-\\alpha/\\beta\}=J\_\{i\}^\{\-\\rho\}\.Hence

𝔼⁡\[\(\|ei\|−B\)\+\|ℱi,1\]≤\(1\+cVβ−1\)​Ji−ρ\.\\mathbb\{E\}\\left\[\\bigl\(\|e\_\{i\}\|\-B\\bigr\)\_\{\+\}\\middle\|\\mathcal\{F\}\_\{i,1\}\\right\]\\leq\\left\(1\+\\frac\{c\_\{V\}\}\{\\beta\-1\}\\right\)J\_\{i\}^\{\-\\rho\}\.Define

Cch:=1\+cVβ−1\.C\_\{\\mathrm\{ch\}\}:=1\+\\frac\{c\_\{V\}\}\{\\beta\-1\}\.Then

\|bi\|≤B\+Cch​Ji−ρ\.\|b\_\{i\}\|\\leq B\+C\_\{\\mathrm\{ch\}\}J\_\{i\}^\{\-\\rho\}\.\(86\)
It remains to average the local occurrence factorsJi−ρJ\_\{i\}^\{\-\\rho\}\. The possible groups are successor\-depth pairs

g=\(s′,ℓ\),g=\(s^\{\\prime\},\\ell\),wheres′s^\{\\prime\}is a possible successor of\(s,a\)\(s,a\), andℓ∈\{0,…,H−1\}\\ell\\in\\\{0,\\ldots,H\-1\\\}is a possible parent depth\. LetGGbe the number of such groups\. Since the successor support of\(s,a\)\(s,a\)is finite and the horizon is finite,

Letng​\(t\)n\_\{g\}\(t\)be the number of indicesi≤ti\\leq tbelonging to groupgg\. For a fixed groupgg, the corresponding values ofJiJ\_\{i\}are exactly

1,2,…,ng​\(t\)\.1,2,\\ldots,n\_\{g\}\(t\)\.Therefore,

∑i=1tJi−ρ=∑g∑j=1ng​\(t\)j−ρ\.\\sum\_\{i=1\}^\{t\}J\_\{i\}^\{\-\\rho\}=\\sum\_\{g\}\\sum\_\{j=1\}^\{n\_\{g\}\(t\)\}j^\{\-\\rho\}\.\(87\)Sinceρ∈\(0,1\)\\rho\\in\(0,1\),

∑j=1nj−ρ≤1\+∫1nx−ρ​𝑑x≤\(1\+11−ρ\)​n1−ρ\.\\sum\_\{j=1\}^\{n\}j^\{\-\\rho\}\\leq 1\+\\int\_\{1\}^\{n\}x^\{\-\\rho\}\\,dx\\leq\\left\(1\+\\frac\{1\}\{1\-\\rho\}\\right\)n^\{1\-\\rho\}\.Let

Cρ:=1\+11−ρ\.C\_\{\\rho\}:=1\+\\frac\{1\}\{1\-\\rho\}\.Then

∑i=1tJi−ρ≤Cρ​∑gng​\(t\)1−ρ\.\\sum\_\{i=1\}^\{t\}J\_\{i\}^\{\-\\rho\}\\leq C\_\{\\rho\}\\sum\_\{g\}n\_\{g\}\(t\)^\{1\-\\rho\}\.\(88\)By concavity ofx↦x1−ρx\\mapsto x^\{1\-\\rho\},

∑gng​\(t\)1−ρ≤Gρ​\(∑gng​\(t\)\)1−ρ\.\\sum\_\{g\}n\_\{g\}\(t\)^\{1\-\\rho\}\\leq G^\{\\rho\}\\left\(\\sum\_\{g\}n\_\{g\}\(t\)\\right\)^\{1\-\\rho\}\.Since∑gng​\(t\)=t\\sum\_\{g\}n\_\{g\}\(t\)=t,

∑i=1tJi−ρ≤Cρ​Gρ​t1−ρ\.\\sum\_\{i=1\}^\{t\}J\_\{i\}^\{\-\\rho\}\\leq C\_\{\\rho\}G^\{\\rho\}t^\{1\-\\rho\}\.\(89\)Dividing bytt,

1t​∑i=1tJi−ρ≤Cρ​Gρ​t−ρ\.\\frac\{1\}\{t\}\\sum\_\{i=1\}^\{t\}J\_\{i\}^\{\-\\rho\}\\leq C\_\{\\rho\}G^\{\\rho\}t^\{\-\\rho\}\.\(90\)Combining \(11\) and \(15\), we obtain

\|1t​∑i=1tbi\|≤1t​∑i=1t\|bi\|≤B\+Cch​Cρ​Gρ​t−ρ\.\\left\|\\frac\{1\}\{t\}\\sum\_\{i=1\}^\{t\}b\_\{i\}\\right\|\\leq\\frac\{1\}\{t\}\\sum\_\{i=1\}^\{t\}\|b\_\{i\}\|\\leq B\+C\_\{\\mathrm\{ch\}\}C\_\{\\rho\}G^\{\\rho\}t^\{\-\\rho\}\.Define

κ:=Cch​Cρ​Gρ\.\\kappa:=C\_\{\\mathrm\{ch\}\}C\_\{\\rho\}G^\{\\rho\}\.Then

\|γt​∑i=1tbi\|≤γ​B\+γ​κ​t−ρ\.\\left\|\\frac\{\\gamma\}\{t\}\\sum\_\{i=1\}^\{t\}b\_\{i\}\\right\|\\leq\\gamma B\+\\gamma\\kappa t^\{\-\\rho\}\.\(91\)
Usingei=bi\+ξie\_\{i\}=b\_\{i\}\+\\xi\_\{i\}, equation \(5\) becomes

Q^t​\(s,a\)−qh=1t​∑i=1t\[Ai\+γ​ξi\]\+γt​∑i=1tbi\+1t​∑i=1tdi\.\\widehat\{Q\}\_\{t\}\(s,a\)\-q\_\{h\}=\\frac\{1\}\{t\}\\sum\_\{i=1\}^\{t\}\\left\[A\_\{i\}\+\\gamma\\xi\_\{i\}\\right\]\+\\frac\{\\gamma\}\{t\}\\sum\_\{i=1\}^\{t\}b\_\{i\}\+\\frac\{1\}\{t\}\\sum\_\{i=1\}^\{t\}d\_\{i\}\.\(92\)The last two terms are controlled by \(6\) and \(16\)\. It remains to control the martingale term

Mt:=∑i=1t\[Ai\+γ​ξi\]\.M\_\{t\}:=\\sum\_\{i=1\}^\{t\}\\left\[A\_\{i\}\+\\gamma\\xi\_\{i\}\\right\]\.
Consider the refined filtration

ℱi,0⊂ℱi,1⊂ℱi,2,\\mathcal\{F\}\_\{i,0\}\\subset\\mathcal\{F\}\_\{i,1\}\\subset\\mathcal\{F\}\_\{i,2\},whereℱi,0\\mathcal\{F\}\_\{i,0\}is the history before drawing\(Si,Ri\)\(S\_\{i\},R\_\{i\}\),ℱi,1\\mathcal\{F\}\_\{i,1\}is the history after drawing\(Si,Ri\)\(S\_\{i\},R\_\{i\}\), andℱi,2\\mathcal\{F\}\_\{i,2\}is the history after completing the recursive child call\. The termAiA\_\{i\}is a martingale difference fromℱi,0\\mathcal\{F\}\_\{i,0\}toℱi,1\\mathcal\{F\}\_\{i,1\}, andγ​ξi\\gamma\\xi\_\{i\}is a martingale difference fromℱi,1\\mathcal\{F\}\_\{i,1\}toℱi,2\\mathcal\{F\}\_\{i,2\}\. Their absolute bounds areLAL\_\{A\}andγ​Lξ\\gamma L\_\{\\xi\}, respectively\.

Therefore, by Azuma\-Hoeffding applied to this refined martingale,

ℙ⁡\(\|Mt\|\>t​ε\)≤2​exp⁡\(−t2​ε22​t​\(LA2\+γ2​Lξ2\)\)\.\\mathbb\{P\}\\left\(\|M\_\{t\}\|\>t\\varepsilon\\right\)\\leq 2\\exp\\left\(\-\\frac\{t^\{2\}\\varepsilon^\{2\}\}\{2t\(L\_\{A\}^\{2\}\+\\gamma^\{2\}L\_\{\\xi\}^\{2\}\)\}\\right\)\.Define

σQ2:=LA2\+γ2​Lξ2\.\\sigma\_\{Q\}^\{2\}:=L\_\{A\}^\{2\}\+\\gamma^\{2\}L\_\{\\xi\}^\{2\}\.Then

ℙ⁡\(\|1t​Mt\|\>ε\)≤2​exp⁡\(−t​ε22​σQ2\)\.\\mathbb\{P\}\\left\(\\left\|\\frac\{1\}\{t\}M\_\{t\}\\right\|\>\\varepsilon\\right\)\\leq 2\\exp\\left\(\-\\frac\{t\\varepsilon^\{2\}\}\{2\\sigma\_\{Q\}^\{2\}\}\\right\)\.\(93\)
Combining \([81](https://arxiv.org/html/2609.19956#A4.E81)\), \([91](https://arxiv.org/html/2609.19956#A4.E91)\), \([92](https://arxiv.org/html/2609.19956#A4.E92)\), and \([93](https://arxiv.org/html/2609.19956#A4.E93)\), we obtain

ℙ⁡\(\|Q^t​\(s,a\)−qh\|\>δQ,t​\(s,a,h\)\+γ​B\+γ​κ​t−ρ\+ε\)≤2​exp⁡\(−t​ε22​σQ2\),\\mathbb\{P\}\\left\(\\left\|\\widehat\{Q\}\_\{t\}\(s,a\)\-q\_\{h\}\\right\|\>\\delta\_\{Q,t\}\(s,a;h\)\+\\gamma B\+\\gamma\\kappa t^\{\-\\rho\}\+\\varepsilon\\right\)\\leq 2\\exp\\left\(\-\\frac\{t\\varepsilon^\{2\}\}\{2\\sigma\_\{Q\}^\{2\}\}\\right\),which proves \([76](https://arxiv.org/html/2609.19956#A4.E76)\)\.

We now convert \([76](https://arxiv.org/html/2609.19956#A4.E76)\) into the polynomial bound \([77](https://arxiv.org/html/2609.19956#A4.E77)\)\. Fixα¯,β¯\\bar\{\\alpha\},\\bar\{\\beta\}satisfying

β¯\>1,2​α¯≤β¯,α¯≤ρ​β¯\.\\bar\{\\beta\}\>1,\\qquad 2\\bar\{\\alpha\}\\leq\\bar\{\\beta\},\\qquad\\bar\{\\alpha\}\\leq\\rho\\bar\{\\beta\}\.There are two cases\.

First suppose

0<ε≤2​γ​κ​t−ρ\.0<\\varepsilon\\leq 2\\gamma\\kappa t^\{\-\\rho\}\.Then the probability in \([77](https://arxiv.org/html/2609.19956#A4.E77)\) is at most11\. Moreover,

t−α¯​ε−β¯≥t−α¯​\(2​γ​κ​t−ρ\)−β¯=\(2​γ​κ\)−β¯​t−α¯\+ρ​β¯\.t^\{\-\\bar\{\\alpha\}\}\\varepsilon^\{\-\\bar\{\\beta\}\}\\geq t^\{\-\\bar\{\\alpha\}\}\\left\(2\\gamma\\kappa t^\{\-\\rho\}\\right\)^\{\-\\bar\{\\beta\}\}=\(2\\gamma\\kappa\)^\{\-\\bar\{\\beta\}\}t^\{\-\\bar\{\\alpha\}\+\\rho\\bar\{\\beta\}\}\.Sinceα¯≤ρ​β¯\\bar\{\\alpha\}\\leq\\rho\\bar\{\\beta\}, we havet−α¯\+ρ​β¯≥1t^\{\-\\bar\{\\alpha\}\+\\rho\\bar\{\\beta\}\}\\geq 1\. Hence, choosing

CQ≥\(2​γ​κ\)β¯C\_\{Q\}\\geq\(2\\gamma\\kappa\)^\{\\bar\{\\beta\}\}makes

1≤CQ​t−α¯​ε−β¯\.1\\leq C\_\{Q\}t^\{\-\\bar\{\\alpha\}\}\\varepsilon^\{\-\\bar\{\\beta\}\}\.
Now suppose

ε\>2​γ​κ​t−ρ\.\\varepsilon\>2\\gamma\\kappa t^\{\-\\rho\}\.Then

γ​κ​t−ρ<ε2\.\\gamma\\kappa t^\{\-\\rho\}<\\frac\{\\varepsilon\}\{2\}\.Therefore,

\{\|Q^t\(s,a\)−qh\|\>δQ,t\(s,a;h\)\+γB\+ε\}\\displaystyle\\left\\\{\\left\|\\widehat\{Q\}\_\{t\}\(s,a\)\-q\_\{h\}\\right\|\>\\delta\_\{Q,t\}\(s,a;h\)\+\\gamma B\+\\varepsilon\\right\\\}⊆\{\|Q^t\(s,a\)−qh\|\>δQ,t\(s,a;h\)\+γB\+γκt−ρ\+ε2\}\.\\displaystyle\\subseteq\\left\\\{\\left\|\\widehat\{Q\}\_\{t\}\(s,a\)\-q\_\{h\}\\right\|\>\\delta\_\{Q,t\}\(s,a;h\)\+\\gamma B\+\\gamma\\kappa t^\{\-\\rho\}\+\\frac\{\\varepsilon\}\{2\}\\right\\\}\.Applying \(1\) withε/2\\varepsilon/2gives

ℙ⁡\(\|Q^t​\(s,a\)−qh\|\>δQ,t​\(s,a,h\)\+γ​B\+ε\)≤2​exp⁡\(−t​ε28​σQ2\)\.\\mathbb\{P\}\\left\(\\left\|\\widehat\{Q\}\_\{t\}\(s,a\)\-q\_\{h\}\\right\|\>\\delta\_\{Q,t\}\(s,a;h\)\+\\gamma B\+\\varepsilon\\right\)\\leq 2\\exp\\left\(\-\\frac\{t\\varepsilon^\{2\}\}\{8\\sigma\_\{Q\}^\{2\}\}\\right\)\.\(94\)For everyc\>0c\>0and everyβ¯\>0\\bar\{\\beta\}\>0, there existsK⁡\(c,β¯\)<∞K\(c,\\bar\{\\beta\}\)<\\inftysuch that

e−c​x≤K\(c,β¯\)x−β¯/2∀x\>0\.e^\{\-cx\}\\leq K\(c,\\bar\{\\beta\}\)x^\{\-\\bar\{\\beta\}/2\}\\qquad\\forall x\>0\.Usingx=t​ε2x=t\\varepsilon^\{2\}andc=1/\(8​σQ2\)c=1/\(8\\sigma\_\{Q\}^\{2\}\), \(19\) implies

2exp\(−t​ε28​σQ2\)≤2Kt−β¯/2ε−β¯\.2\\exp\\left\(\-\\frac\{t\\varepsilon^\{2\}\}\{8\\sigma\_\{Q\}^\{2\}\}\\right\)\\leq 2Kt^\{\-\\bar\{\\beta\}/2\}\\varepsilon^\{\-\\bar\{\\beta\}\}\.Since2​α¯≤β¯2\\bar\{\\alpha\}\\leq\\bar\{\\beta\},

t−β¯/2≤t−α¯\.t^\{\-\\bar\{\\beta\}/2\}\\leq t^\{\-\\bar\{\\alpha\}\}\.Thus

2​exp⁡\(−t​ε28​σQ2\)≤2​K​t−α¯​ε−β¯\.2\\exp\\left\(\-\\frac\{t\\varepsilon^\{2\}\}\{8\\sigma\_\{Q\}^\{2\}\}\\right\)\\leq 2Kt^\{\-\\bar\{\\alpha\}\}\\varepsilon^\{\-\\bar\{\\beta\}\}\.IncreasingCQC\_\{Q\}if necessary proves \(2\)\.

Finally, supposeB=BΔB=B\_\{\\Delta\}and

BΔ≥δQ,t​\(s,a,h\)1−γ\.B\_\{\\Delta\}\\geq\\frac\{\\delta\_\{Q,t\}\(s,a;h\)\}\{1\-\\gamma\}\.Then

δQ,t​\(s,a,h\)≤\(1−γ\)​BΔ\.\\delta\_\{Q,t\}\(s,a;h\)\\leq\(1\-\\gamma\)B\_\{\\Delta\}\.Therefore,

δQ,t​\(s,a,h\)\+γ​BΔ≤\(1−γ\)​BΔ\+γ​BΔ=BΔ\.\\delta\_\{Q,t\}\(s,a;h\)\+\\gamma B\_\{\\Delta\}\\leq\(1\-\\gamma\)B\_\{\\Delta\}\+\\gamma B\_\{\\Delta\}=B\_\{\\Delta\}\.Hence

\{\|Q^t\(s,a\)−Q~\(s,h,a\)\|\>BΔ\+ε\}\\displaystyle\\left\\\{\\left\|\\widehat\{Q\}\_\{t\}\(s,a\)\-\\widetilde\{Q\}\(s,h,a\)\\right\|\>B\_\{\\Delta\}\+\\varepsilon\\right\\\}⊆\{\|Q^t\(s,a\)−Q~\(s,h,a\)\|\>δQ,t\(s,a;h\)\+γBΔ\+ε\}\.\\displaystyle\\subseteq\\left\\\{\\left\|\\widehat\{Q\}\_\{t\}\(s,a\)\-\\widetilde\{Q\}\(s,h,a\)\\right\|\>\\delta\_\{Q,t\}\(s,a;h\)\+\\gamma B\_\{\\Delta\}\+\\varepsilon\\right\\\}\.Applying \([77](https://arxiv.org/html/2609.19956#A4.E77)\) yields

ℙ⁡\(\|Q^t​\(s,a\)−Q~​\(s,h,a\)\|\>BΔ\+ε\)≤CQ​t−α¯​ε−β¯\.\\mathbb\{P\}\\left\(\\left\|\\widehat\{Q\}\_\{t\}\(s,a\)\-\\widetilde\{Q\}\(s,h,a\)\\right\|\>B\_\{\\Delta\}\+\\varepsilon\\right\)\\leq C\_\{Q\}t^\{\-\\bar\{\\alpha\}\}\\varepsilon^\{\-\\bar\{\\beta\}\}\.This proves \([78](https://arxiv.org/html/2609.19956#A4.E78)\), completing the proof\. ∎

###### Corollary 1\(Control by the cross\-depth gap\)\.

Suppose the state\-value cross\-depth gap satisfies

Δcross≥maxs′⁡maxh,k​\|V~​\(s′,h\+1\)−V~​\(s′,k\+1\)\|\\Delta\_\{\\textsc\{cross\}\}\\geq\\max\_\{s^\{\\prime\}\}\\max\_\{h,k\}\\left\|\\widetilde\{V\}\(s^\{\\prime\},h\+1\)\-\\widetilde\{V\}\(s^\{\\prime\},k\+1\)\\right\|over the successor states and depths relevant to the updates of\(s,a\)\(s,a\)\. Then

δQ,t​\(s,a,h\)≤γ​Δcross\.\\delta\_\{Q,t\}\(s,a;h\)\\leq\\gamma\\Delta\_\{\\textsc\{cross\}\}\.Consequently, one may choose

BΔ=γ1−γ​Δcross,B\_\{\\Delta\}=\\frac\{\\gamma\}\{1\-\\gamma\}\\Delta\_\{\\textsc\{cross\}\},and Lemma[4](https://arxiv.org/html/2609.19956#Thmlemma4)gives

ℙ⁡\(\|Q^t​\(s,a\)−Q~​\(s,h,a\)\|\>γ1−γ​Δcross\+ε\)≤CQ​t−α¯​ε−β¯\.\\mathbb\{P\}\\left\(\\left\|\\widehat\{Q\}\_\{t\}\(s,a\)\-\\widetilde\{Q\}\(s,h,a\)\\right\|\>\\frac\{\\gamma\}\{1\-\\gamma\}\\Delta\_\{\\textsc\{cross\}\}\+\\varepsilon\\right\)\\leq C\_\{Q\}t^\{\-\\bar\{\\alpha\}\}\\varepsilon^\{\-\\bar\{\\beta\}\}\.

###### Proof\.

For any two depthshhandkk,

\|Q~​\(s,h,a\)−Q~​\(s,k,a\)\|\\displaystyle\\left\|\\widetilde\{Q\}\(s,h,a\)\-\\widetilde\{Q\}\(s,k,a\)\\right\|=γ​\|∑s′P⁡\(s′∣s,a\)​\[V~​\(s′,h\+1\)−V~​\(s′,k\+1\)\]\|\\displaystyle=\\gamma\\left\|\\sum\_\{s^\{\\prime\}\}P\(s^\{\\prime\}\\mid s,a\)\\left\[\\widetilde\{V\}\(s^\{\\prime\},h\+1\)\-\\widetilde\{V\}\(s^\{\\prime\},k\+1\)\\right\]\\right\|≤γ​maxs′​\|V~​\(s′,h\+1\)−V~​\(s′,k\+1\)\|\\displaystyle\\leq\\gamma\\max\_\{s^\{\\prime\}\}\\left\|\\widetilde\{V\}\(s^\{\\prime\},h\+1\)\-\\widetilde\{V\}\(s^\{\\prime\},k\+1\)\\right\|≤γ​Δcross\.\\displaystyle\\leq\\gamma\\Delta\_\{\\textsc\{cross\}\}\.Taking the maximum over the depths appearing in the firstttupdates givesδQ,t​\(s,a,h\)≤γ​Δcross\\delta\_\{Q,t\}\(s,a;h\)\\leq\\gamma\\Delta\_\{\\textsc\{cross\}\}\. The claimed choice ofBΔB\_\{\\Delta\}then satisfies

BΔ=γ1−γ​Δcross≥δQ,t​\(s,a,h\)1−γ,B\_\{\\Delta\}=\\frac\{\\gamma\}\{1\-\\gamma\}\\Delta\_\{\\textsc\{cross\}\}\\geq\\frac\{\\delta\_\{Q,t\}\(s,a;h\)\}\{1\-\\gamma\},so the result follows from Lemma[4](https://arxiv.org/html/2609.19956#Thmlemma4)\. ∎

###### Lemma 5\(Robust Power\-UCT value step\)\.

Fix a physical statess, reference depthhh, and finite action set𝒜s\\mathcal\{A\}\_\{s\}, writingqa:=Q~​\(s,h,a\)q\_\{a\}:=\\widetilde\{Q\}\(s,h,a\)andv⋆:=V~​\(s,h\)=maxa∈𝒜s⁡qav\_\{\\star\}:=\\widetilde\{V\}\(s,h\)=\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}q\_\{a\}\. Afterttvisits to the full\-merge nodess, letTs,a​\(t\)T\_\{s,a\}\(t\)count selections ofaaandQ^m​\(s,a\)\\widehat\{Q\}\_\{m\}\(s,a\)be the sharedQQ\-estimate aftermmupdates to\(s,a\)\(s,a\), so the value estimate is the power mean

V^t​\(s\)=\(∑a∈𝒜sTs,a​\(t\)t​\(Q^Ts,a​\(t\)​\(s,a\)\)p\)1/p,p∈\[1,∞\)\.\\widehat\{V\}\_\{t\}\(s\)=\\left\(\\sum\_\{a\\in\\mathcal\{A\}\_\{s\}\}\\frac\{T\_\{s,a\}\(t\)\}\{t\}\\bigl\(\\widehat\{Q\}\_\{T\_\{s,a\}\(t\)\}\(s,a\)\\bigr\)^\{p\}\\right\)^\{1/p\},\\qquad p\\in\[1,\\infty\)\.Assume allQQ\-estimates and targets are nonnegative and bounded byLL, and \(after the usual forced initialization\) the local action\-selection rule uses a single Power\-UCT triple\(b,α\+,β\+\)\(b,\\alpha\_\{\+\},\\beta\_\{\+\}\):

aj∈arg​maxa∈𝒜s⁡\{Q^Ts,a​\(j−1\)​\(s,a\)\+C​Ts​\(j−1\)b/β\+Ts,a​\(j−1\)α\+/β\+\}\.a\_\{j\}\\in\\argmax\_\{a\\in\\mathcal\{A\}\_\{s\}\}\\left\\\{\\widehat\{Q\}\_\{T\_\{s,a\}\(j\-1\)\}\(s,a\)\+C\\,\\tfrac\{T\_\{s\}\(j\-1\)^\{b/\\beta\_\{\+\}\}\}\{T\_\{s,a\}\(j\-1\)^\{\\alpha\_\{\+\}/\\beta\_\{\+\}\}\}\\right\\\}\.Suppose there exist effective targets\{q¯a\}a∈𝒜s\\\{\\bar\{q\}\_\{a\}\\\}\_\{a\\in\\mathcal\{A\}\_\{s\}\}and a bias radiusB≥0B\\geq 0withmaxa∈𝒜s⁡\|q¯a−qa\|≤B\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}\|\\bar\{q\}\_\{a\}\-q\_\{a\}\|\\leq B\(H\-V\), and that for everyaaand everym≥1,ε\>0m\\geq 1,\\varepsilon\>0,

ℙ⁡\(\|Q^m​\(s,a\)−q¯a\|\>ε\)≤cQ​m−α\+​ε−β\+\.\\mathbb\{P\}\(\|\\widehat\{Q\}\_\{m\}\(s,a\)\-\\bar\{q\}\_\{a\}\|\>\\varepsilon\)\\leq c\_\{Q\}m^\{\-\\alpha\_\{\+\}\}\\varepsilon^\{\-\\beta\_\{\+\}\}\.\(95\)Assume further the Power\-UCT parameter conditions2<b<α\+2<b<\\alpha\_\{\+\}and either \(1≤p≤21\\leq p\\leq 2,α\+≤β\+/2\\alpha\_\{\+\}\\leq\\beta\_\{\+\}/2\) or \(p\>2p\>2,α\+≤β\+/2\\alpha\_\{\+\}\\leq\\beta\_\{\+\}/2,0<α\+−β\+/p<10<\\alpha\_\{\+\}\-\\beta\_\{\+\}/p<1\), and letαV:=\(b−1\)​\(1−b/α\+\)\\alpha\_\{V\}:=\(b\-1\)\(1\-b/\\alpha\_\{\+\}\)andβV:=b−1\\beta\_\{V\}:=b\-1\. Then there existsCV<∞C\_\{V\}<\\infty, depending only onK=\|𝒜s\|,p,C,L,cQ,b,α\+,β\+K=\|\\mathcal\{A\}\_\{s\}\|,p,C,L,c\_\{Q\},b,\\alpha\_\{\+\},\\beta\_\{\+\}but not ont,ε,Bt,\\varepsilon,B, such that

ℙ⁡\(\|V^t​\(s\)−V~​\(s,h\)\|\>B\+ε\)≤CV​t−αV​ε−βV,∀t≥1,ε\>0\.\\mathbb\{P\}\(\|\\widehat\{V\}\_\{t\}\(s\)\-\\widetilde\{V\}\(s,h\)\|\>B\+\\varepsilon\)\\leq C\_\{V\}t^\{\-\\alpha\_\{V\}\}\\varepsilon^\{\-\\beta\_\{V\}\},\\qquad\\forall t\\geq 1,\\ \\varepsilon\>0\.\(96\)

###### Proof\.

Define the effective value target induced by the effective action targets\(q¯a\)a∈𝒜s\(\\bar\{q\}\_\{a\}\)\_\{a\\in\\mathcal\{A\}\_\{s\}\}as

v¯:=maxa∈𝒜s⁡q¯a\.\\bar\{v\}:=\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}\\bar\{q\}\_\{a\}\.
The standard Power\-UCT concentration theorem says the following\. If, at a node, each action\-level estimatorQ^m​\(s,a\)\\widehat\{Q\}\_\{m\}\(s,a\)satisfies

ℙ⁡\(\|Q^m​\(s,a\)−q¯a\|\>ε\)≤cQ​m−α\+​ε−β\+,\\mathbb\{P\}\\left\(\|\\widehat\{Q\}\_\{m\}\(s,a\)\-\\bar\{q\}\_\{a\}\|\>\\varepsilon\\right\)\\leq c\_\{Q\}m^\{\-\\alpha\_\{\+\}\}\\varepsilon^\{\-\\beta\_\{\+\}\},and the node uses the Power\-UCT selection rule with parameters satisfying the conditions above, then the power\-mean value estimator satisfies

ℙ⁡\(\|V^t​\(s\)−v¯\|\>ε\)≤CV​t−αV​ε−βV,∀t≥1,∀ε\>0,\\mathbb\{P\}\\left\(\|\\widehat\{V\}\_\{t\}\(s\)\-\\bar\{v\}\|\>\\varepsilon\\right\)\\leq C\_\{V\}t^\{\-\\alpha\_\{V\}\}\\varepsilon^\{\-\\beta\_\{V\}\},\\qquad\\forall t\\geq 1,\\ \\forall\\varepsilon\>0,\(97\)where

αV=\(b−1\)​\(1−bα\+\),βV=b−1\.\\alpha\_\{V\}=\(b\-1\)\\left\(1\-\\frac\{b\}\{\\alpha\_\{\+\}\}\\right\),\\qquad\\beta\_\{V\}=b\-1\.This theorem is purely local: it only requires action\-levelQQ\-concentration and the Power\-UCT action\-selection rule at the node\. It does not depend on whether theQQ\-estimates were produced by a tree, a depth\-augmented graph, or a full\-merge graph\.

It remains to transfer concentration from the effective targetv¯\\bar\{v\}to the depth\-specific truncated targetv⋆=V~​\(s,h\)v\_\{\\star\}=\\widetilde\{V\}\(s,h\)\. By definition,

v⋆=maxa∈𝒜s⁡qa,v¯=maxa∈𝒜s⁡q¯a\.v\_\{\\star\}=\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}q\_\{a\},\\qquad\\bar\{v\}=\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}\\bar\{q\}\_\{a\}\.The max map is11\-Lipschitz in the sup norm\. Therefore,

\|v¯−v⋆\|\\displaystyle\|\\bar\{v\}\-v\_\{\\star\}\|=\|maxa∈𝒜s⁡q¯a−maxa∈𝒜s⁡qa\|\\displaystyle=\\left\|\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}\\bar\{q\}\_\{a\}\-\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}q\_\{a\}\\right\|\(98\)≤maxa∈𝒜s⁡\|q¯a−qa\|\\displaystyle\\leq\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}\|\\bar\{q\}\_\{a\}\-q\_\{a\}\|≤B,\\displaystyle\\leq B,where the last inequality is hypothesis \(H\-V\)\.

Now suppose

\|V^t​\(s\)−v⋆\|\>B\+ε\.\|\\widehat\{V\}\_\{t\}\(s\)\-v\_\{\\star\}\|\>B\+\\varepsilon\.Using the triangle inequality and \([98](https://arxiv.org/html/2609.19956#A4.E98)\),

\|V^t​\(s\)−v¯\|≥\|V^t​\(s\)−v⋆\|−\|v¯−v⋆\|\>B\+ε−B=ε\.\|\\widehat\{V\}\_\{t\}\(s\)\-\\bar\{v\}\|\\geq\|\\widehat\{V\}\_\{t\}\(s\)\-v\_\{\\star\}\|\-\|\\bar\{v\}\-v\_\{\\star\}\|\>B\+\\varepsilon\-B=\\varepsilon\.Hence the event inclusion

\{\|V^t\(s\)−v⋆\|\>B\+ε\}⊆\{\|V^t\(s\)−v¯\|\>ε\}\\left\\\{\|\\widehat\{V\}\_\{t\}\(s\)\-v\_\{\\star\}\|\>B\+\\varepsilon\\right\\\}\\subseteq\\left\\\{\|\\widehat\{V\}\_\{t\}\(s\)\-\\bar\{v\}\|\>\\varepsilon\\right\\\}holds\. Applying the Stochastic\-Power\-UCT bound \([97](https://arxiv.org/html/2609.19956#A4.E97)\) gives

ℙ⁡\(\|V^t​\(s\)−v⋆\|\>B\+ε\)≤ℙ⁡\(\|V^t​\(s\)−v¯\|\>ε\)≤CV​t−αV​ε−βV\.\\mathbb\{P\}\\left\(\|\\widehat\{V\}\_\{t\}\(s\)\-v\_\{\\star\}\|\>B\+\\varepsilon\\right\)\\leq\\mathbb\{P\}\\left\(\|\\widehat\{V\}\_\{t\}\(s\)\-\\bar\{v\}\|\>\\varepsilon\\right\)\\leq C\_\{V\}t^\{\-\\alpha\_\{V\}\}\\varepsilon^\{\-\\beta\_\{V\}\}\.Sincev⋆=V~​\(s,h\)v\_\{\\star\}=\\widetilde\{V\}\(s,h\), this is exactly \([96](https://arxiv.org/html/2609.19956#A4.E96)\)\. ∎

###### Corollary 2\(Value\-step bias controlled byQQ\-level cross\-depth drift\)\.

Under the assumptions of Lemma[5](https://arxiv.org/html/2609.19956#Thmlemma5), suppose

maxa∈𝒜s⁡\|q¯a−Q~​\(s,h,a\)\|≤BΔ\.\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}\|\\bar\{q\}\_\{a\}\-\\widetilde\{Q\}\(s,h,a\)\|\\leq B\_\{\\Delta\}\.Then

ℙ⁡\(\|V^t​\(s\)−V~​\(s,h\)\|\>BΔ\+ε\)≤CV​t−αV​ε−βV\.\\mathbb\{P\}\\left\(\|\\widehat\{V\}\_\{t\}\(s\)\-\\widetilde\{V\}\(s,h\)\|\>B\_\{\\Delta\}\+\\varepsilon\\right\)\\leq C\_\{V\}t^\{\-\\alpha\_\{V\}\}\\varepsilon^\{\-\\beta\_\{V\}\}\.In particular, if theQQ\-level effective targets satisfy

maxa∈𝒜s⁡\|q¯a−Q~​\(s,h,a\)\|≤γ1−γ​Δcross,\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}\|\\bar\{q\}\_\{a\}\-\\widetilde\{Q\}\(s,h,a\)\|\\leq\\frac\{\\gamma\}\{1\-\\gamma\}\\Delta\_\{\\textsc\{cross\}\},then

ℙ⁡\(\|V^t​\(s\)−V~​\(s,h\)\|\>γ1−γ​Δcross\+ε\)≤CV​t−αV​ε−βV\.\\mathbb\{P\}\\left\(\|\\widehat\{V\}\_\{t\}\(s\)\-\\widetilde\{V\}\(s,h\)\|\>\\frac\{\\gamma\}\{1\-\\gamma\}\\Delta\_\{\\textsc\{cross\}\}\+\\varepsilon\\right\)\\leq C\_\{V\}t^\{\-\\alpha\_\{V\}\}\\varepsilon^\{\-\\beta\_\{V\}\}\.

###### Proof\.

Apply Lemma[5](https://arxiv.org/html/2609.19956#Thmlemma5)with

The second claim follows from the specific choice

BΔ=γ1−γ​Δcross\.B\_\{\\Delta\}=\\frac\{\\gamma\}\{1\-\\gamma\}\\Delta\_\{\\textsc\{cross\}\}\.∎

##### Proof of Theorem[3](https://arxiv.org/html/2609.19956#Thmtheorem3)

###### Proof\.

We prove a stronger biased concentration statement and then integrate its tail\.

For a physical statessand depthhh, recall that

V~​\(s,h\)=\(ℬH−h​V0\)​\(s\),\\widetilde\{V\}\(s,h\)=\(\\mathcal\{B\}^\{H\-h\}V\_\{0\}\)\(s\),and

Q~​\(s,h,a\)=∑s′P⁡\(s′∣s,a\)​\[R⁡\(s,a,s′\)\+γ​V~​\(s′,h\+1\)\]\.\\widetilde\{Q\}\(s,h,a\)=\\sum\_\{s^\{\\prime\}\}P\(s^\{\\prime\}\\mid s,a\)\\left\[R\(s,a,s^\{\\prime\}\)\+\\gamma\\widetilde\{V\}\(s^\{\\prime\},h\+1\)\\right\]\.For the firstnnsimulations, define the uniformQQ\-level cross\-depth drift

δQ,n≜max\(s,a\):Ts,a​\(n\)≥1h∈𝒟H,n​\(s\),1≤t≤Ts,a​\(n\)δQ,t\(s,a;h\),\\delta\_\{Q,n\}\\triangleq\\max\_\{\\begin\{subarray\}\{c\}\(s,a\):\\,T\_\{s,a\}\(n\)\\geq 1\\\\ h\\in\\mathcal\{D\}\_\{H,n\}\(s\),\\ 1\\leq t\\leq T\_\{s,a\}\(n\)\\end\{subarray\}\}\\delta\_\{Q,t\}\(s,a;h\),with the maximum over an empty set taken as zero\. ThusδQ,n\\delta\_\{Q,n\}uniformly bounds the drift of every state\-action\-depth triple realized in the search\.

The key claim is that, for every depthh∈\{0,…,H\}h\\in\\\{0,\\ldots,H\\\}, every physical statess, and every visit countt≥1t\\geq 1, there exists a constantch<∞c\_\{h\}<\\infty, independent oftt,nn, andε\\varepsilon, such that

ℙ⁡\(\|V^t​\(s\)−V~​\(s,h\)\|\>BΔ,n\+ε\)≤ch​t−αh​ε−βh,∀ε\>0\.\\mathbb\{P\}\\left\(\\left\|\\widehat\{V\}\_\{t\}\(s\)\-\\widetilde\{V\}\(s,h\)\\right\|\>B\_\{\\Delta,n\}\+\\varepsilon\\right\)\\leq c\_\{h\}t^\{\-\\alpha\_\{h\}\}\\varepsilon^\{\-\\beta\_\{h\}\},\\qquad\\forall\\varepsilon\>0\.\(99\)HereV^t​\(s\)\\widehat\{V\}\_\{t\}\(s\)denotes the full\-merge value estimate at the physical nodessafterttvisits to that node\. Notice that the same estimatorV^t​\(s\)\\widehat\{V\}\_\{t\}\(s\)may be compared with several depth\-specific targetsV~​\(s,h\)\\widetilde\{V\}\(s,h\), because the full\-merge nodessmay be entered at several depths\. The price of this comparison is the additive bias radiusBΔ,nB\_\{\\Delta,n\}\.

We prove \([99](https://arxiv.org/html/2609.19956#A4.E99)\) by backward induction onhh\.

##### Base case:h=Hh=H\.

At depthHH, the recursive simulation stops and returns an independent rollout or evaluation sample with meanV0​\(s\)=V~​\(s,H\)V\_\{0\}\(s\)=\\widetilde\{V\}\(s,H\)\. Since rollout values are bounded, Hoeffding’s inequality implies that, for any admissibleαH,βH\\alpha\_\{H\},\\beta\_\{H\}withβH\>1\\beta\_\{H\}\>1andαH≤βH/2\\alpha\_\{H\}\\leq\\beta\_\{H\}/2, there existscH<∞c\_\{H\}<\\inftysuch that

ℙ⁡\(\|V^t​\(s\)−V~​\(s,H\)\|\>ε\)≤cH​t−αH​ε−βH\.\\mathbb\{P\}\\left\(\\left\|\\widehat\{V\}\_\{t\}\(s\)\-\\widetilde\{V\}\(s,H\)\\right\|\>\\varepsilon\\right\)\\leq c\_\{H\}t^\{\-\\alpha\_\{H\}\}\\varepsilon^\{\-\\beta\_\{H\}\}\.SinceBΔ,n≥0B\_\{\\Delta,n\}\\geq 0, this immediately gives

ℙ⁡\(\|V^t​\(s\)−V~​\(s,H\)\|\>BΔ,n\+ε\)≤cH​t−αH​ε−βH\.\\mathbb\{P\}\\left\(\\left\|\\widehat\{V\}\_\{t\}\(s\)\-\\widetilde\{V\}\(s,H\)\\right\|\>B\_\{\\Delta,n\}\+\\varepsilon\\right\)\\leq c\_\{H\}t^\{\-\\alpha\_\{H\}\}\\varepsilon^\{\-\\beta\_\{H\}\}\.Thus \([99](https://arxiv.org/html/2609.19956#A4.E99)\) holds at depthHH\.

##### Inductive step\.

Fixh<Hh<H, and assume that \([99](https://arxiv.org/html/2609.19956#A4.E99)\) holds for all depthsh\+1,h\+2,…,Hh\+1,h\+2,\\ldots,H\. We prove it at depthhh\.

Fix a physical statessand actionaa\. Consider the firstttupdates to the shared full\-merge statisticQ^​\(s,a\)\\widehat\{Q\}\(s,a\)\. Theii\-th such update may arrive whenssis entered at some depthhih\_\{i\}, not necessarily equal to the reference depthhh\. LetSiS\_\{i\}be the sampled successor,RiR\_\{i\}the sampled reward, andWiW\_\{i\}the value returned by the recursive child call from\(Si,hi\+1\)\(S\_\{i\},h\_\{i\}\+1\)\. With the corrected backup,

Yi=Ri\+γ​Wi,Q^t​\(s,a\)=1t​∑i=1tYi\.Y\_\{i\}=R\_\{i\}\+\\gamma W\_\{i\},\\qquad\\widehat\{Q\}\_\{t\}\(s,a\)=\\frac\{1\}\{t\}\\sum\_\{i=1\}^\{t\}Y\_\{i\}\.
By the induction hypothesis applied at the child depthhi\+1h\_\{i\}\+1, the child returned value satisfies the biased concentration condition required by Lemma[4](https://arxiv.org/html/2609.19956#Thmlemma4), with bias radiusBΔ,nB\_\{\\Delta,n\}\. Hence, for any reference depthhh, Lemma[4](https://arxiv.org/html/2609.19956#Thmlemma4)yields

ℙ⁡\(\|Q^t​\(s,a\)−Q~​\(s,h,a\)\|\>BΔ,n\+ε\)≤CQ​t−αh\+1​ε−βh\+1,∀ε\>0\.\\mathbb\{P\}\\left\(\\left\|\\widehat\{Q\}\_\{t\}\(s,a\)\-\\widetilde\{Q\}\(s,h,a\)\\right\|\>B\_\{\\Delta,n\}\+\\varepsilon\\right\)\\leq C\_\{Q\}t^\{\-\\alpha\_\{h\+1\}\}\\varepsilon^\{\-\\beta\_\{h\+1\}\},\\qquad\\forall\\varepsilon\>0\.\(100\)Indeed, the only deterministic drift term in Lemma[4](https://arxiv.org/html/2609.19956#Thmlemma4)is

δQ,t​\(s,a,h\):=max1≤i≤t⁡\|Q~​\(s,hi,a\)−Q~​\(s,h,a\)\|\.\\delta\_\{Q,t\}\(s,a;h\):=\\max\_\{1\\leq i\\leq t\}\\left\|\\widetilde\{Q\}\(s,h\_\{i\},a\)\-\\widetilde\{Q\}\(s,h,a\)\\right\|\.By definition ofδQ,n\\delta\_\{Q,n\},

δQ,t​\(s,a,h\)≤δQ,n\.\\delta\_\{Q,t\}\(s,a;h\)\\leq\\delta\_\{Q,n\}\.Since

BΔ,n=δQ,n1−γ,B\_\{\\Delta,n\}=\\frac\{\\delta\_\{Q,n\}\}\{1\-\\gamma\},we have

δQ,t​\(s,a,h\)\+γ​BΔ,n≤δQ,n\+γ​δQ,n1−γ=δQ,n1−γ=BΔ,n\.\\delta\_\{Q,t\}\(s,a;h\)\+\\gamma B\_\{\\Delta,n\}\\leq\\delta\_\{Q,n\}\+\\gamma\\frac\{\\delta\_\{Q,n\}\}\{1\-\\gamma\}=\\frac\{\\delta\_\{Q,n\}\}\{1\-\\gamma\}=B\_\{\\Delta,n\}\.Therefore the robustQQ\-propagation lemma gives exactly the biasedQQ\-concentration bound \([100](https://arxiv.org/html/2609.19956#A4.E100)\)\.

Now apply Lemma[5](https://arxiv.org/html/2609.19956#Thmlemma5)at the physical nodess\. The local action targets are

qa=Q~​\(s,h,a\),V~​\(s,h\)=maxa∈𝒜s⁡qa\.q\_\{a\}=\\widetilde\{Q\}\(s,h,a\),\\qquad\\widetilde\{V\}\(s,h\)=\\max\_\{a\\in\\mathcal\{A\}\_\{s\}\}q\_\{a\}\.By \([100](https://arxiv.org/html/2609.19956#A4.E100)\), every shared action estimateQ^​\(s,a\)\\widehat\{Q\}\(s,a\)concentrates around its depth\-hhtargetQ~​\(s,h,a\)\\widetilde\{Q\}\(s,h,a\)with the same additive bias radiusBΔ,nB\_\{\\Delta,n\}\. Since the full\-merge node uses a single depth\-independent Power\-UCT rule, the robust Power\-UCT value\-step lemma applies and gives

ℙ⁡\(\|V^t​\(s\)−V~​\(s,h\)\|\>BΔ,n\+ε\)≤ch​t−αh​ε−βh\.\\mathbb\{P\}\\left\(\\left\|\\widehat\{V\}\_\{t\}\(s\)\-\\widetilde\{V\}\(s,h\)\\right\|\>B\_\{\\Delta,n\}\+\\varepsilon\\right\)\\leq c\_\{h\}t^\{\-\\alpha\_\{h\}\}\\varepsilon^\{\-\\beta\_\{h\}\}\.\(101\)This is precisely \([99](https://arxiv.org/html/2609.19956#A4.E99)\) at depthhh\. The induction is complete\.

##### Root concentration\.

Every simulation starts froms0s\_\{0\}at trajectory depth00\. Therefore the full\-merge root visit count afternnsimulations satisfies

Ts0​\(n\)≥n\.T\_\{s\_\{0\}\}\(n\)\\geq n\.Applying \([99](https://arxiv.org/html/2609.19956#A4.E99)\) withs=s0s=s\_\{0\},h=0h=0, andt=Ts0​\(n\)t=T\_\{s\_\{0\}\}\(n\), we obtain

ℙ⁡\(\|V^n​\(s0\)−V~​\(s0,0\)\|\>BΔ,n\+ε\)≤c0​n−α0​ε−β0,∀ε\>0\.\\mathbb\{P\}\\left\(\\left\|\\widehat\{V\}\_\{n\}\(s\_\{0\}\)\-\\widetilde\{V\}\(s\_\{0\},0\)\\right\|\>B\_\{\\Delta,n\}\+\\varepsilon\\right\)\\leq c\_\{0\}n^\{\-\\alpha\_\{0\}\}\\varepsilon^\{\-\\beta\_\{0\}\},\\qquad\\forall\\varepsilon\>0\.\(102\)HereV^n​\(s0\)\\widehat\{V\}\_\{n\}\(s\_\{0\}\)denotes the root estimate afternnsimulations\.

##### Tail integration\.

Let

Xn:=\|V^n​\(s0\)−V~​\(s0,0\)\|\.X\_\{n\}:=\\left\|\\widehat\{V\}\_\{n\}\(s\_\{0\}\)\-\\widetilde\{V\}\(s\_\{0\},0\)\\right\|\.SinceBΔ,n≥0B\_\{\\Delta,n\}\\geq 0,

Xn≤BΔ,n\+\(Xn−BΔ,n\)\+\.X\_\{n\}\\leq B\_\{\\Delta,n\}\+\(X\_\{n\}\-B\_\{\\Delta,n\}\)\_\{\+\}\.Taking expectations and using the tail\-integral identity,

𝔼⁡\[Xn\]\\displaystyle\\mathbb\{E\}\[X\_\{n\}\]≤𝔼⁡\[BΔ,n\]\+∫0∞ℙ⁡\(Xn\>BΔ,n\+ε\)​dε\.\\displaystyle\\leq\\mathbb\{E\}\[B\_\{\\Delta,n\}\]\+\\int\_\{0\}^\{\\infty\}\\mathbb\{P\}\\left\(X\_\{n\}\>B\_\{\\Delta,n\}\+\\varepsilon\\right\)d\\varepsilon\.Using \([102](https://arxiv.org/html/2609.19956#A4.E102)\),

𝔼⁡\[Xn\]≤𝔼⁡\[BΔ,n\]\+∫0∞min⁡\{1,c0​n−α0​ε−β0\}​𝑑ε\.\\mathbb\{E\}\[X\_\{n\}\]\\leq\\mathbb\{E\}\[B\_\{\\Delta,n\}\]\+\\int\_\{0\}^\{\\infty\}\\min\\left\\\{1,\\,c\_\{0\}n^\{\-\\alpha\_\{0\}\}\\varepsilon^\{\-\\beta\_\{0\}\}\\right\\\}d\\varepsilon\.Set

ηn:=n−α0/β0\.\\eta\_\{n\}:=n^\{\-\\alpha\_\{0\}/\\beta\_\{0\}\}\.Then

𝔼⁡\[Xn\]\\displaystyle\\mathbb\{E\}\[X\_\{n\}\]≤𝔼⁡\[BΔ,n\]\+ηn\+∫ηn∞c0​n−α0​ε−β0​𝑑ε\\displaystyle\\leq\\mathbb\{E\}\[B\_\{\\Delta,n\}\]\+\\eta\_\{n\}\+\\int\_\{\\eta\_\{n\}\}^\{\\infty\}c\_\{0\}n^\{\-\\alpha\_\{0\}\}\\varepsilon^\{\-\\beta\_\{0\}\}\\,d\\varepsilon=𝔼⁡\[BΔ,n\]\+ηn\+c0β0−1​n−α0​ηn1−β0\.\\displaystyle=\\mathbb\{E\}\[B\_\{\\Delta,n\}\]\+\\eta\_\{n\}\+\\frac\{c\_\{0\}\}\{\\beta\_\{0\}\-1\}n^\{\-\\alpha\_\{0\}\}\\eta\_\{n\}^\{1\-\\beta\_\{0\}\}\.Becauseηn=n−α0/β0\\eta\_\{n\}=n^\{\-\\alpha\_\{0\}/\\beta\_\{0\}\},

n−α0ηn1−β0=n−α0n−\(α0/β0\)​\(1−β0\)=n−α0/β0\.n^\{\-\\alpha\_\{0\}\}\\eta\_\{n\}^\{1\-\\beta\_\{0\}\}=n^\{\-\\alpha\_\{0\}\}n^\{\-\(\\alpha\_\{0\}/\\beta\_\{0\}\)\(1\-\\beta\_\{0\}\)\}=n^\{\-\\alpha\_\{0\}/\\beta\_\{0\}\}\.Therefore,

𝔼\[Xn\]≤𝔼\[BΔ,n\]\+\(1\+c0β0−1\)n−α0/β0\.\\mathbb\{E\}\[X\_\{n\}\]\\leq\\mathbb\{E\}\[B\_\{\\Delta,n\}\]\+\\left\(1\+\\frac\{c\_\{0\}\}\{\\beta\_\{0\}\-1\}\\right\)n^\{\-\\alpha\_\{0\}/\\beta\_\{0\}\}\.\(103\)
Finally, Jensen’s inequality gives

\|𝔼⁡\[V^n​\(s0\)\]−V~​\(s0,0\)\|\\displaystyle\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}\(s\_\{0\}\)\]\-\\widetilde\{V\}\(s\_\{0\},0\)\\right\|≤𝔼⁡\[\|V^n​\(s0\)−V~​\(s0,0\)\|\]\\displaystyle\\leq\\mathbb\{E\}\\left\[\\left\|\\widehat\{V\}\_\{n\}\(s\_\{0\}\)\-\\widetilde\{V\}\(s\_\{0\},0\)\\right\|\\right\]=𝔼⁡\[Xn\]\.\\displaystyle=\\mathbb\{E\}\[X\_\{n\}\]\.Combining this with \([103](https://arxiv.org/html/2609.19956#A4.E103)\) yields

\|𝔼\[V^n\(s0\)\]−V~\(s0,0\)\|≤Csampn−α0/β0\+𝔼\[BΔ,n\],\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}\(s\_\{0\}\)\]\-\\widetilde\{V\}\(s\_\{0\},0\)\\right\|\\leq C\_\{\\mathrm\{samp\}\}n^\{\-\\alpha\_\{0\}/\\beta\_\{0\}\}\+\\mathbb\{E\}\[B\_\{\\Delta,n\}\],for

Csamp:=1\+c0β0−1\.C\_\{\\mathrm\{samp\}\}:=1\+\\frac\{c\_\{0\}\}\{\\beta\_\{0\}\-1\}\.Under the optimal tuning

α0/β0=1/2,\\alpha\_\{0\}/\\beta\_\{0\}=1/2,we obtain

\|𝔼\[V^n\(s0\)\]−V~\(s0,0\)\|≤Csampn−1/2\+𝔼\[BΔ,n\]\.\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}\(s\_\{0\}\)\]\-\\widetilde\{V\}\(s\_\{0\},0\)\\right\|\\leq C\_\{\\mathrm\{samp\}\}n^\{\-1/2\}\+\\mathbb\{E\}\[B\_\{\\Delta,n\}\]\.\(104\)Since

BΔ,n=δQ,n1−γ,B\_\{\\Delta,n\}=\\frac\{\\delta\_\{Q,n\}\}\{1\-\\gamma\},this proves the expected\-error bound in terms ofδQ,n\\delta\_\{Q,n\}\.

It remains to connectδQ,n\\delta\_\{Q,n\}to the stated cross\-depth gap\. Suppose

δQ,n≤γ​Δcrossalmost surely\.\\delta\_\{Q,n\}\\leq\\gamma\\Delta\_\{\\textsc\{cross\}\}\\qquad\\text\{almost surely\}\.Then

𝔼⁡\[BΔ,n\]=11−γ​𝔼​\[δQ,n\]≤γ1−γ​Δcross\.\\mathbb\{E\}\[B\_\{\\Delta,n\}\]=\\frac\{1\}\{1\-\\gamma\}\\mathbb\{E\}\[\\delta\_\{Q,n\}\]\\leq\\frac\{\\gamma\}\{1\-\\gamma\}\\Delta\_\{\\textsc\{cross\}\}\.Substituting into \([104](https://arxiv.org/html/2609.19956#A4.E104)\) gives

\|𝔼\[V^n\(s0\)\]−V~\(s0,0\)\|≤Csampn−1/2\+γ1−γΔcross\.\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}\(s\_\{0\}\)\]\-\\widetilde\{V\}\(s\_\{0\},0\)\\right\|\\leq C\_\{\\mathrm\{samp\}\}n^\{\-1/2\}\+\\frac\{\\gamma\}\{1\-\\gamma\}\\Delta\_\{\\textsc\{cross\}\}\.Thus

\|𝔼\[V^n\(s0\)\]−V~\(s0,0\)\|≤O\(n−1/2\)\+O\(Δcross\),\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}\(s\_\{0\}\)\]\-\\widetilde\{V\}\(s\_\{0\},0\)\\right\|\\leq O\(n^\{\-1/2\}\)\+O\(\\Delta\_\{\\textsc\{cross\}\}\),as claimed\. ∎

### D\.6Proof of Theorem[4](https://arxiv.org/html/2609.19956#Thmtheorem4)

###### Proof\.

Let

Hn≜H⁡\(n\)\.H\_\{n\}\\triangleq H\(n\)\.By the triangle inequality,

\|𝔼⁡\[V^nHn​\(s0\)\]−V⋆​\(s0\)\|\\displaystyle\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}^\{H\_\{n\}\}\(s\_\{0\}\)\]\-V^\{\\star\}\(s\_\{0\}\)\\right\|≤\|𝔼⁡\[V^nHn​\(s0\)\]−V~Hn​\(s0,0\)\|\\displaystyle\\leq\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}^\{H\_\{n\}\}\(s\_\{0\}\)\]\-\\widetilde\{V\}\_\{H\_\{n\}\}\(s\_\{0\},0\)\\right\|\+\|V~Hn​\(s0,0\)−V⋆​\(s0\)\|\.\\displaystyle\\quad\+\\left\|\\widetilde\{V\}\_\{H\_\{n\}\}\(s\_\{0\},0\)\-V^\{\\star\}\(s\_\{0\}\)\\right\|\.\(105\)
The first term is exactly the fixed\-horizon full\-merge error controlled by Theorem[3](https://arxiv.org/html/2609.19956#Thmtheorem3), applied with horizonH=HnH=H\_\{n\}\. Therefore,

\|𝔼\[V^nHn\(s0\)\]−V~Hn\(s0,0\)\|≤c\(Hn\)n−1/2\+CΔ𝔼\[ΔcrossHn,n\]\.\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}^\{H\_\{n\}\}\(s\_\{0\}\)\]\-\\widetilde\{V\}\_\{H\_\{n\}\}\(s\_\{0\},0\)\\right\|\\leq c\(H\_\{n\}\)n^\{\-1/2\}\+C\_\{\\Delta\}\\,\\mathbb\{E\}\\\!\\left\[\\Delta\_\{\\textsc\{cross\}\}^\{H\_\{n\},n\}\\right\]\.\(106\)By Definition[3](https://arxiv.org/html/2609.19956#Thmdefinition3),

Δcrossn=ΔcrossH⁡\(n\),n=ΔcrossHn,n\.\\Delta\_\{\\textsc\{cross\}\}^\{n\}=\\Delta\_\{\\textsc\{cross\}\}^\{H\(n\),n\}=\\Delta\_\{\\textsc\{cross\}\}^\{H\_\{n\},n\}\.Hence

\|𝔼\[V^nHn\(s0\)\]−V~Hn\(s0,0\)\|≤c\(Hn\)n−1/2\+CΔ𝔼\[Δcrossn\]\.\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}^\{H\_\{n\}\}\(s\_\{0\}\)\]\-\\widetilde\{V\}\_\{H\_\{n\}\}\(s\_\{0\},0\)\\right\|\\leq c\(H\_\{n\}\)n^\{\-1/2\}\+C\_\{\\Delta\}\\,\\mathbb\{E\}\\\!\\left\[\\Delta\_\{\\textsc\{cross\}\}^\{n\}\\right\]\.\(107\)
For the second term, the finite\-horizon truncation bound gives

\|V~Hn​\(s0,0\)−V⋆​\(s0\)\|≤γHn​‖V⋆−V0‖∞\.\\left\|\\widetilde\{V\}\_\{H\_\{n\}\}\(s\_\{0\},0\)\-V^\{\\star\}\(s\_\{0\}\)\\right\|\\leq\\gamma^\{H\_\{n\}\}\\\|V^\{\\star\}\-V\_\{0\}\\\|\_\{\\infty\}\.\(108\)Combining the previous displays yields

\|𝔼\[V^nHn\(s0\)\]−V⋆\(s0\)\|≤c\(Hn\)n−1/2\+CΔ𝔼\[Δcrossn\]\+γHn∥V⋆−V0∥∞\.\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}^\{H\_\{n\}\}\(s\_\{0\}\)\]\-V^\{\\star\}\(s\_\{0\}\)\\right\|\\leq c\(H\_\{n\}\)n^\{\-1/2\}\+C\_\{\\Delta\}\\,\\mathbb\{E\}\\\!\\left\[\\Delta\_\{\\textsc\{cross\}\}^\{n\}\\right\]\+\\gamma^\{H\_\{n\}\}\\\|V^\{\\star\}\-V\_\{0\}\\\|\_\{\\infty\}\.\(109\)
Finally, by the adaptive\-horizon choice

Hn=⌈log⁡n2​log⁡\(1/γ\)⌉,H\_\{n\}=\\left\\lceil\\frac\{\\log n\}\{2\\log\(1/\\gamma\)\}\\right\\rceil,we have

γHn≤n−1/2\.\\gamma^\{H\_\{n\}\}\\leq n^\{\-1/2\}\.Therefore,

\|𝔼\[V^nHn\(s0\)\]−V⋆\(s0\)\|≤c\(Hn\)n−1/2\+CΔ𝔼\[Δcrossn\]\+n−1/2∥V⋆−V0∥∞\.\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}^\{H\_\{n\}\}\(s\_\{0\}\)\]\-V^\{\\star\}\(s\_\{0\}\)\\right\|\\leq c\(H\_\{n\}\)n^\{\-1/2\}\+C\_\{\\Delta\}\\,\\mathbb\{E\}\\\!\\left\[\\Delta\_\{\\textsc\{cross\}\}^\{n\}\\right\]\+n^\{\-1/2\}\\\|V^\{\\star\}\-V\_\{0\}\\\|\_\{\\infty\}\.\(110\)Thus, if

𝔼\[Δcrossn\]→0andc\(Hn\)n−1/2→0,\\mathbb\{E\}\\\!\\left\[\\Delta\_\{\\textsc\{cross\}\}^\{n\}\\right\]\\to 0\\qquad\\text\{and\}\\qquad c\(H\_\{n\}\)n^\{\-1/2\}\\to 0,then

𝔼⁡\[V^nHn​\(s0\)\]→V⋆​\(s0\)\.\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}^\{H\_\{n\}\}\(s\_\{0\}\)\]\\to V^\{\\star\}\(s\_\{0\}\)\.Moreover, if

𝔼\[Δcrossn\]=O\(n−1/2\)\\mathbb\{E\}\\\!\\left\[\\Delta\_\{\\textsc\{cross\}\}^\{n\}\\right\]=O\(n^\{\-1/2\}\)andc⁡\(Hn\)c\(H\_\{n\}\)grows at most polylogarithmically innn, then

\|𝔼⁡\[V^nHn​\(s0\)\]−V⋆​\(s0\)\|=O⁡\(c⁡\(Hn\)n\)\.\\left\|\\mathbb\{E\}\[\\widehat\{V\}\_\{n\}^\{H\_\{n\}\}\(s\_\{0\}\)\]\-V^\{\\star\}\(s\_\{0\}\)\\right\|=O\\\!\\left\(\\frac\{c\(H\_\{n\}\)\}\{\\sqrt\{n\}\}\\right\)\.∎

## Appendix EExperimental Details

### E\.1Evaluation Protocol

To evaluate the performance and scalability of each algorithm, we define a set of simulation budgets \(number of iterations\) tailored to the complexity of each environment\. For every environment, each algorithm is evaluated across these simulation checkpoints to observe its performance profile\.

Our evaluation follows a replanning paradigm\. Specifically, at each time step of an episode, the agent executes a complete search process using its allotted simulation budget to determine the optimal action\. This process is repeated for every step until a terminal state is reached\. To ensure statistical significance and account for the stochastic nature of Monte Carlo\-based methods, we conduct 1,000 independent runs for each combination of algorithm, environment, and simulation budget, except for GBOP, which uses 500 runs\. The final performance is reported as the mean cumulative reward \(or other environment\-specific metric\) over the corresponding evaluation runs\.

### E\.2Hyperparameter Selection

To ensure a fair comparison, we perform an extensive hyperparameter sweep for both the proposed method and the baselines using a grid search strategy\. The search space for each algorithm is defined based on literature\-standard ranges and preliminary runs\.

The tuning process is conducted as follows:

- •For each environment and algorithm, we evaluate candidate hyperparameter sets using300300independent runs\.
- •These runs are performed across all predefined simulation budget checkpoints to ensure the robustness of the selected parameters\.
- •Selection Criterion:The optimal hyperparameter configuration is chosen based on the highest aggregate mean reward, calculated by averaging the performance across all simulation budgets within a specific environment\.

By selecting parameters that perform well across different simulation budgets, we aim to identify configurations that are not only high\-performing but also stable under varying computational constraints\.

### E\.3Benchmark Environments

#### E\.3\.1FrozenLake

Environment Description:The Frozen Grid environment consists of an8×88\\times 8grid where the agent starts at coordinate\(0,0\)\(0,0\)and aims to reach the goal state at\(7,7\)\(7,7\)\. The state space is defined by the agent’s\(x,y\)\(x,y\)coordinates\. The grid cells are categorized into Frozen \(F\), Holes \(H\), Start \(S\), and Goal \(G\)\. The action space consists of four discrete movements:left,down,right, andup\. To introduce stochasticity \(slippery mode\), transitions are non\-deterministic: the executed action results in the intended direction with a probability of1/31/3, or deviates to a perpendicular direction \(left turn or right turn\) with a probability of1/31/3each\. Boundary collisions result in the agent remaining in its current cell\. The episode terminates if the agent reaches the goal, falls into a hole, or exhausts the maximum horizon limit ofH=200H=200\. The reward function is strictly sparse, granting a reward of11only upon reaching the goal, and00for all other transitions\.

Selected Hyperparameters:UCT\(ϵ=1\.5\\epsilon=1\.5\), MENTS\(temperature=0\.25,ϵ=0\.5\\epsilon=0\.5\), Power\-UCT\(C=1\.5C=1\.5,p=2\.0p=2\.0\), GS\-Power\-UCT\(C=0\.5C=0\.5,p=∞p=\\infty\), GS\-Power\-UCT\-F\+\(C=1\.25C=1\.25,p=∞p=\\infty\)\.

#### E\.3\.2Passenger Grid

Environment Description:The Passenger Grid is formulated on a7×67\\times 6layout\. The state is represented as a tuple\(x,y,M\)\(x,y,M\), whereMMis a bitmask tracking the pickup status of passengers\. The agent starts at\(0,0\)\(0,0\)and must deliver passengers to the drop\-off goal at\(6,0\)\(6,0\)\. Three passengers are initially located at\(1,2\)\(1,2\),\(0,5\)\(0,5\), and\(6,4\)\(6,4\)\. Theii\-th bit ofMMflips to11when the agent occupies passengerii’s initial cell\. Actions includeleft,down,right, andup\. The environment operates in a slippery mode where the effective action is sampled from\{turn\-left,intended,turn\-right\}\\\{\\text\{turn\-left\},\\text\{intended\},\\text\{turn\-right\}\\\}with probabilities\{0\.25,0\.5,0\.25\}\\\{0\.25,0\.5,0\.25\\\}, respectively\. Boundary collisions keep the agent stationary\. Each transition increments the time step, and episodes terminate either upon reaching the drop\-off cell or at horizonH=70H=70\. The reward is delayed until the goal is reached and depends on the total number of collected passengers:00,11,33, or77for collecting00,11,22, or33passengers, respectively\. All other transitions yield a reward of00\.

Selected Hyperparameters:UCT\(ϵ=1\.5\\epsilon=1\.5\), MENTS\(temperature=0\.01,ϵ=0\.5\\epsilon=0\.5\), Power\-UCT\(C=1\.5C=1\.5,p=2\.5p=2\.5\), GBOP\(ϵ=0\.001\\epsilon=0\.001,γ=0\.99\\gamma=0\.99\), GS\-Power\-UCT\(C=0\.5C=0\.5,p=∞p=\\infty\), GS\-Power\-UCT\-F\+\(C=0\.5C=0\.5,p=4\.0p=4\.0\)\.

#### E\.3\.3Factored River Swim

Environment Description:The Factored River Swim environment comprises33independent river\-swim chains\. The joint state captures the position of an agent on each chain,P∈\{0,…,4\}3P\\in\\\{0,\\dots,4\\\}^\{3\}\. All rivers initialize at position00, with33being the target goal\. A joint action is represented as a33\-bit vector \(88possible actions\), where theii\-th bit indicates the behavior for riverii:00for resting/swimming downstream \(left\) and11for swimming upstream \(right\)\. Action00deterministically moves the agent one step left \(bounded at00\)\. Action11introduces stochastic transitions: at position00, the agent stays with probability0\.40\.4and moves right with0\.60\.6; at the goal \(44\), it falls back to33with probability0\.40\.4and stays with0\.60\.6; at any intermediate state, it moves left \(0\.050\.05\), stays \(0\.600\.60\), or moves right \(0\.350\.35\)\. Episodes terminate atH=35H=35\. Rewards are evaluated prior to position updates\. For each river, selecting action00at position00yields0\.10\.1, while selecting action11at position77yields1\.01\.0\. A synergistic bonus of4\.04\.0is granted if all rivers are simultaneously at position77and all action bits are set to11\. The total aggregated reward is normalized by a factor of66\.

Selected Hyperparameters:UCT\(ϵ=0\.5\\epsilon=0\.5\), MENTS\(temperature=0\.99,ϵ=0\.5\\epsilon=0\.5\), Power\-UCT\(C=1\.5C=1\.5,p=1\.0p=1\.0\), GBOP\(ϵ=0\.001\\epsilon=0\.001,γ=0\.99\\gamma=0\.99\), GS\-Power\-UCT\(C=0\.5C=0\.5,p=∞p=\\infty\), GS\-Power\-UCT\-F\+\(C=1\.5C=1\.5,p=∞p=\\infty\)\.

#### E\.3\.4SysAdmin Ring

Environment Description:The SysAdmin Ring models a network of2020interconnected computers forming a ring topology\. The state is represented by analive\_mask, where each bit denotes the running status of a specific machine\. Initially, all computers are down \(alive\_mask=0=0\)\. The agent can choose from2121actions: either reboot a specific computeri∈\{0,…,19\}i\\in\\\{0,\\dots,19\\\}or remain idle\. Rebooting a computer guarantees it will be running in the subsequent state\. For all other machines, the status updates stochastically based on their current state and that of their predecessor in the ring\. The running probabilities are determined as follows:0\.02380\.0238if both are down;0\.04750\.0475if the predecessor is running but the current is down;0\.5250\.525if the predecessor is down but the current is running; and0\.950\.95if both are running\. Episodes terminate deterministically att=50t=50\. The environment provides a dense step\-wise reward corresponding to the fraction of running machines\.

Selected Hyperparameters:UCT\(ϵ=1\.5\\epsilon=1\.5\), MENTS\(temperature=0\.25,ϵ=0\.5\\epsilon=0\.5\), Power\-UCT\(C=0\.5C=0\.5,p=3\.0p=3\.0\), GS\-Power\-UCT\(C=0\.5C=0\.5,p=2\.5p=2\.5\), GBOP\(ϵ=0\.001\\epsilon=0\.001,γ=0\.99\\gamma=0\.99\), GS\-Power\-UCT\-F\+\(C=0\.75C=0\.75,p=2\.5p=2\.5\)\.

#### E\.3\.5FourRooms

Environment Description:FourRooms is an11×1111\\times 11grid partitioned by a vertical wall atx=5x=5and a horizontal wall aty=5y=5\. Communication between rooms is facilitated by four door cells, one randomly placed on each of the four wall segments during reset\. The agent’s start and goal positions are uniformly sampled from non\-wall and non\-door cells\. The agent executes four directional actions, subject to slippery dynamics identical to the Passenger Grid: effective actions are sampled from\{turn\-left,intended,turn\-right\}\\\{\\text\{turn\-left\},\\text\{intended\},\\text\{turn\-right\}\\\}with probabilities\{0\.25,0\.5,0\.25\}\\\{0\.25,0\.5,0\.25\\\}\. Collisions with walls or boundaries leave the agent in place\. Episodes terminate upon reaching the target goal or hitting the time limitH=50H=50\. The reward is00at all steps except when the goal is reached, where a time\-discounted reward is issued:R=1−0\.9×\(t/50\)R=1\-0\.9\\times\(t/50\), incentivizing faster navigation\.

Selected Hyperparameters:UCT\(ϵ=1\.0\\epsilon=1\.0\), MENTS\(temperature=0\.01,ϵ=0\.5\\epsilon=0\.5\), Power\-UCT\(C=1\.0C=1\.0,p=2\.0p=2\.0\), GS\-Power\-UCT\(C=0\.5C=0\.5,p=∞p=\\infty\), GBOP\(ϵ=0\.001\\epsilon=0\.001,γ=0\.99\\gamma=0\.99\), GS\-Power\-UCT\-F\+\(C=0\.5C=0\.5,p=4\.0p=4\.0\)\.

### E\.4Experimental Results

The following tables report reward as the mean±\\pmtwice the standard deviation over 1,000 evaluation runs for each algorithm and simulation budget \(except GBOP: 500 runs\)\. Each table is split into two budget panels for readability; the column headings give the number of simulations per decision\. P\-UCT denotes Stochastic\-Power\-UCT\.

Table 5:FrozenLakeTable 6:Passenger GridTable 7:Factored River SwimTable 8:SysAdmin RingTable 9:FourRooms
### E\.5Runtime and memory analysis

For a fixed horizonHH, each search depth requires an expected\-O⁡\(1\)O\(1\)hash lookup andO⁡\(K\)O\(K\)action\-selection and backup work, givingO⁡\(H​K\)O\(HK\)time per simulation, the same asymptotic order as tree\-based Stochastic\-Power\-UCT\. For depth\-augmented GS\-Power\-UCT, Theorem[2](https://arxiv.org/html/2609.19956#Thmtheorem2)implies that the node and edge counts under the same realised trajectories do not exceed those of the unrolled tree\. This representation statement does not apply to independently run planners or to full merging\. The graph additionally stores a hash table and adjacency lists, requiringO⁡\(\|𝒩\|\+\|ℰ\|\)O\(\|\\mathcal\{N\}\|\+\|\\mathcal\{E\}\|\)auxiliary storage\. A finite discrete MDP stores at most\|𝒮\|​\(H\+1\)\|\\mathcal\{S\}\|\(H\+1\)depth\-augmented nodes or\|𝒮\|\|\\mathcal\{S\}\|full\-merge nodes; before saturation, both quantities are budget\-dependent\.

To illustrate implementation overhead, we compare the proposed algorithms with Stochastic\-Power\-UCT\. GS\-Power\-UCT adds state merging\. For GS\-Power\-UCT\-F\+, each reported budgetnnuses the fixed horizonH⁡\(n\)H\(n\)for allnnsimulations in that search\. We report three representative budgets for brevity\. Each budget is reported in two rows: average wall\-clock time per decision \(episode time divided by steps, averaged over 1,000 episodes\), and average expanded\-node count over all steps\.

Runtime and memory interpretation:The largest observed positive runtime difference is 15\.5% \(Table[10](https://arxiv.org/html/2609.19956#A5.T10)\); some measurements are lower than the tree baseline\. Expanded\-node counts indicate retained graph size and are not direct measurements of RAM use\. The proposed methods add hash\-table and graph\-bookkeeping storage, while node\-count reduction can be substantial when transpositions are common\. Without transpositions, node counts approach those of the tree representation, with additional bookkeeping constants\.

Table 10:Wall\-clock time per decision and average expanded\-node count across environments and simulation budgets\. Node counts are a retained\-graph\-size proxy, not memory measurements\.EnvironmentSimsMetricStochastic\-Power\-UCTGS\-Power\-UCTGS\-Power\-UCT\-F\+FourRooms16Time0\.0146 ms0\.0155 ms \(\+6\.2%\)0\.0146 ms \(\+0\.0%\)Nodes17\.08\.9 \(\-47\.6%\)8\.3 \(\-51\.2%\)FourRooms256Time0\.2513 ms0\.2771 ms \(\+10\.3%\)0\.2875 ms \(\+14\.4%\)Nodes257\.076\.9 \(\-70\.1%\)51\.9 \(\-79\.8%\)FourRooms2048Time4\.6116 ms5\.3265 ms \(\+15\.5%\)5\.2128 ms \(\+13\.0%\)Nodes1971\.780\.8 \(\-95\.9%\)54\.1 \(\-97\.3%\)Passenger Grid16Time0\.0199 ms0\.0199 ms \(\+0\.0%\)0\.0201 ms \(\+1\.0%\)Nodes17\.09\.1 \(\-46\.5%\)8\.5 \(\-50\.0%\)Passenger Grid256Time0\.3155 ms0\.3161 ms \(\+0\.2%\)0\.3273 ms \(\+3\.7%\)Nodes257\.075\.1 \(\-70\.8%\)51\.9 \(\-79\.8%\)Passenger Grid2048Time3\.9591 ms4\.1618 ms \(\+5\.1%\)4\.2138 ms \(\+6\.4%\)Nodes1732\.481\.5 \(\-95\.3%\)56\.8 \(\-96\.7%\)Factored River Swim16Time0\.0182 ms0\.0185 ms \(\+1\.6%\)0\.0185 ms \(\+1\.6%\)Nodes17\.017\.0 \(\-0\.0%\)17\.0 \(\-0\.0%\)Factored River Swim256Time0\.3205 ms0\.3311 ms \(\+3\.3%\)0\.3336 ms \(\+4\.1%\)Nodes257\.0174\.5 \(\-32\.1%\)161\.2 \(\-37\.3%\)Factored River Swim2048Time5\.5256 ms5\.6520 ms \(\+2\.3%\)5\.6782 ms \(\+2\.8%\)Nodes2049\.0702\.2 \(\-65\.7%\)463\.7 \(\-77\.4%\)SysAdmin Ring16Time0\.0215 ms0\.0213 ms \(\-0\.9%\)0\.0213 ms \(\-0\.9%\)Nodes17\.017\.0 \(\-0\.0%\)17\.0 \(\-0\.0%\)SysAdmin Ring256Time0\.3730 ms0\.3748 ms \(\+0\.5%\)0\.3758 ms \(\+0\.8%\)Nodes257\.0241\.7 \(\-6\.0%\)234\.3 \(\-8\.8%\)SysAdmin Ring2048Time6\.0448 ms6\.1197 ms \(\+1\.2%\)6\.1136 ms \(\+1\.1%\)Nodes2049\.01795\.9 \(\-12\.4%\)1663\.7 \(\-18\.8%\)FrozenLake16Time0\.1690 ms0\.1669 ms \(\-1\.2%\)0\.1665 ms \(\-1\.5%\)Nodes17\.08\.7 \(\-48\.8%\)8\.1 \(\-52\.4%\)FrozenLake256Time2\.9186 ms2\.9782 ms \(\+2\.0%\)2\.5900 ms \(\-11\.3%\)Nodes257\.074\.9 \(\-70\.9%\)49\.3 \(\-80\.8%\)FrozenLake2048Time30\.7731 ms31\.5220 ms \(\+2\.4%\)30\.0416 ms \(\-2\.4%\)Nodes2008\.778\.0 \(\-96\.1%\)51\.5 \(\-97\.4%\)Table 10:Wall\-clock time per decision and average expanded\-node count \(continued\)\.