Planner-Admissible Graph-PDE Value Extensions for Sparse Goal-Conditioned Planning
Shiheng Zhang [email protected] · 2026
Read Planner-Admissible Graph-PDE Value Extensions for Sparse Goal-Conditioned Planning by Shiheng Zhang [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-19185.txt.
Introduction
Shiheng Zhang studies which value extensions a greedy planner can trust with few cost labels. The task is a Dirichlet extension problem: spread goal labels to vertices so greedy rollouts reach the goal. His main result is a local certificate: if rollout error stays below half the true action gap, the greedy rollout still reaches the goal. Absolutely Minimal Lipschitz Extension meets the certificate as the infinite-p endpoint of the p-Laplacian family. Harmonic extension can mis-rank actions, and on 120 AntMaze graphs it reaches 0.584 success against 0.970 for AMLE.
Catalog record
| CREATOR | Shiheng Zhang [email protected] |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80318 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.19185
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Planner-Admissible Graph-PDE Value Extensions for Sparse Goal-Conditioned Planning Shiheng Zhang [email protected] Abstract Sparse goal-conditioned planning with few cost-to-go labels can be cast as graph-PDE Dirichlet extension: extend labels on a small boundary Γ g \Gamma_{g} to unlabelled vertices so that greedy rollouts reach the goal. We argue the key criterion is planner admissibility , not pointwise error. Within the graph p p -Laplacian family, harmonic averaging ( p = 2 p=2 ) often fails to preserve local greedy orderings, whereas high- p p and Absolutely Minimal Lipschitz Extension ( AMLE ) / Lipschitz-extremal extensions enter a high-success regime. AMLE is the simple, analyzable p = ∞ p=\infty endpoint of this family, with a local midrange update and a clean comparison / Lipschitz theory. Our main theoretical statement is a planner-admissibility certificate : under the operational argmin- Q Q planner, if at every state visited by the surrogate-greedy rollout the local value error stays below half the true action gap, then the rollout reaches the goal (Theorem 3.3 ). AMLE instantiates the certificate through a comparison-principle fill-distance bound (Corollary 3.5 ); harmonic can violate it because its neighbour rankings are boundary-label-weighted hitting-probability rankings, not shortest-path rankings (Lemma 3.8 , Lemma 3.9 ). All p p -Laplacian endpoints share a structural maximum principle (Lemma 3.6 ): no strict interior sinks across p ∈ [ 2 , ∞ ] p\in[2,\infty] . An operator-level identity (Proposition 3.10 ) shows that shortest-path distance is locally AMLE -compatible on the geodesically extendable interior, while harmonic-compatibility requires a non-generic degree-balance condition n + = n − n_{+}=n_{-} (Corollary 3.11 ). A refinement-stable seven-node construction is a positive-margin witness for a local harmonic-ordering failure mode that persists under graph subdivision. On 120 120 AntMaze layout-derived graph configurations ( 22 ) , aggregate rollout success is 0.584 0.584 for p = 2 p=2 , 0.903 0.903 for p = 4 p=4 , 0.973 0.973 for p = 8 p=8 , 0.982 0.982 for a fixed-budget p = 16 p=16 solver, and 0.970 0.970 for AMLE . Large finite- p p rows are not used for exact endpoint ranking because solver certification is incomplete. On the rollout-weighted decision scope, AMLE reduces the low neighbour-Kendall- τ nbr \tau_{\mathrm{nbr}} tail from 0.064 0.064 to 0.015 0.015 and the true cost-to-go gap of the surrogate-chosen action from 0.049 0.049 to 0.006 0.006 . 1 Introduction Goal-conditioned reinforcement learning (GCRL) supports agents that reach designated states by consuming a goal-conditioned value function V^{\star}(s,g) on a state-transition graph ( 38 ; 4 ; 20 ) . In practice this value function is observed at only a small subset of state-goal pairs — a sparse boundary \Gamma_{g}\subset V of cost-to-go labels — and must be extended to unlabelled interior vertices before the agent can plan. Many extension principles are available: harmonic averaging ( 51 ) , smoothness-regularised graph p -Laplacians ( 26 ; 13 ) , and Lipschitz-extremal completions ( 6 ; 35 ) . Existing analyses of value approximation justify greedy policies through action-value ordering or weighted L^{p} loss bounds ( 42 ; 30 ) , but graph semi-supervised learning objectives optimise extension smoothness or pointwise fit. Our criterion is the induced graph planner: which extension principle preserves the local action ordering on which one-step decisions depend? We frame this as a graph partial differential equation (graph-PDE) Dirichlet extension problem. The state-transition graph G=(V,E,w) has positive edge weights w(s,y) encoding transition costs; the boundary \Gamma_{g}\subset V carries the observed labels with g\in\Gamma_{g} as the goal; the surrogate \hat{V} extends these labels to the interior V\setminus\Gamma_{g} . The planner used throughout this paper, matching the graph-search rule of Search-on-Replay-Buffer-style methods ( 20 ) , is the operational argmin- Q rule T_{\hat{V},g}(s)\;=\;\arg\min_{y\,\sim\,s}\,\bigl[w(s,y)+\hat{V}(y,g)\bigr], with consistent tie-breaking and absorbing g . Within the graph p -Laplacian family, the natural endpoints are harmonic averaging at p=2 and the Absolutely Minimal Lipschitz Extension ( AMLE ) at p=\infty , with intermediate p interpolating between them; the question is which members of the family preserve the action ordering well enough for the argmin- Q rollout to reach the goal from interior starts. Our main theoretical result is a planner-admissibility certificate (Theorem 3.3 ): if local surrogate error stays below half the true action gap along the realised rollout, the greedy rollout reaches the goal. AMLE instantiates the certificate via a fill-distance comparison bound (Corollary 3.5 ); harmonic can violate it because its rankings are harmonic-measure rankings rather than shortest-path rankings (Lemma 3.9 ). All p -Laplacian endpoints share a structural maximum principle (Lemma 3.6 ): no strict interior local extrema across p\in[2,\infty] . The AMLE -vs-harmonic separator therefore lives in the local action-ordering layer. Empirically, on 120 paired AntMaze layout-derived configurations ( 22 ) ( 61{,}440 rollouts per method), aggregate rollout success is 0.584\pm 0.230 for p=2 and \mathbf{0.970\pm 0.061} for p=\infty , a \mathbf{+38.6} pp paired lift (95% run-bootstrap CI [+34.9,+42.3] ). Intermediate p\in\{4,8,16\} cluster with AMLE in the 0.90 – 0.98 regime, with the few-pp p=16 vs p=\infty lift solver-tolerance-bound rather than a converged endpoint ranking. The mechanism audit in Section 5 localises the gap to operator geometry: 54.8\% of rollout decisions sit in geometry where the true distance d_{g} is locally AMLE -compatible but harmonic-incompatible (Proposition 3.10 and Corollary 3.11 ); 99.3\% of harmonic inversions concentrate there, AMLE corrects 93.1\% of inversions, and the per-state half-gap test of Lemma 3.2 (the local hypothesis underlying Theorem 3.3 ) certifies 67.0\% of inversion events. The ordering and mechanism audits are decision-scope diagnostics, not direct upper bounds on \phi(\hat{V}) . The local mechanism is illustrated by a seven-node graph G_{7} (Example 3.12 ) with sparse-label boundary \Gamma_{g}=\{0,7\} and labels Y_{g}(0)=0 , Y_{g}(7)=3 . At decision state s=4 the true greedy neighbour is 3 , but harmonic assigns \hat{u}_{2}(1)=36/29<\hat{u}_{2}(3)=39/29 ( wrong ), whereas AMLE assigns \hat{V}_{\infty}(3)=1<\hat{V}_{\infty}(1)=4/3 ( correct ); the inversion persists under uniform graph subdivision (Corollary B.5 ). An adversarial 4\times 4 subgraph search complements this construction with mirror cases where harmonic is greedy-perfect and AMLE degenerates on a plateau, so the seven-node example illustrates a mechanism rather than a global comparison. Contributions. We formulate sparse GCRL value completion as a planner-admissible graph-PDE extension problem and read the surrogate choice as a p -family geometry question. Specifically: • We prove a local action-gap certificate (Theorem 3.3 ) and its AMLE fill-distance instantiation (Corollary 3.5 ) translating sparse-label density into greedy-rollout success. • We establish harmonic anti-admissibility through harmonic-measure rankings (Lemma 3.9 ) and an operator-level mismatch with shortest-path distance (Proposition 3.10 , Corollary 3.11 ). • We validate the resulting p -family transition on 120 AntMaze graph layouts via the main rollout experiment, the ordering audit, the mechanism audit, and the failure-mode decomposition. • Adaptive label selection, closed-loop continuous control, and certified intermediate- p solvers are open directions deferred to § 6 . 2 Related work and positioning Harmonic / Laplacian SSL and low-label degeneracy. The classical harmonic SSL approach fits a function agreeing with labels on a boundary set and minimising quadratic Dirichlet energy on the interior ( 51 ; 50 ) , generalised by manifold and graph-Laplacian regularisation ( 8 ; 7 ; 9 ; 44 ) . At very sparse labellings the harmonic minimiser is known to degenerate to