# Planner-Admissible Graph-PDE Value Extensions for Sparse Goal-Conditioned Planning

arXiv: https://arxiv.org/abs/2605.19185 · HTML: https://mlsanity.com/paper/2605.19185/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 50 references that are in the map.
- First posted on arXiv 18 May 2026.

## Builds on (most cited first, 19 of 19)

- [D4RL: Datasets for Deep Data-Driven Reinforcement Learning](https://mlsanity.com/paper/2004.07219/) (2020)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Search on the Replay Buffer: Bridging Planning and Reinforcement Learning](https://mlsanity.com/paper/1906.05253/) (2019)
- [Value Iteration Networks](https://mlsanity.com/paper/1602.02867/) (2016)
- [Planning with Goal-Conditioned Policies](https://mlsanity.com/paper/1911.08453/) (2019)
- [Temporal Difference Models: Model-Free Deep RL for Model-Based Control](https://mlsanity.com/paper/1802.09081/) (2018)
- [Analysis of p-Laplacian Regularization in Semi-Supervised Learning](https://mlsanity.com/paper/1707.06213/) (2017)
- [The game theoretic p-Laplacian and semi-supervised learning with few labels](https://mlsanity.com/paper/1711.10144/) (2017)
- [Properly-weighted graph Laplacian for semi-supervised learning](https://mlsanity.com/paper/1810.04351/) (2018)
- [Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Rates](https://mlsanity.com/paper/2006.02765/) (2020)
- [Algorithms for Lipschitz Learning on Graphs](https://mlsanity.com/paper/1505.00290/) (2015)
- [Asymptotic behavior of ℓp-based Laplacian regularization in semi-supervised learning](https://mlsanity.com/paper/1603.00564/) (2016)
- [Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data](https://mlsanity.com/paper/1710.10364/) (2017)
- [Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression](https://mlsanity.com/paper/1907.07167/) (2019)
- [A maximum principle argument for the uniform convergence of graph Laplacian regressors](https://mlsanity.com/paper/1901.10089/) (2019)
- [Uniform Convergence Rates for Lipschitz Learning on Graphs](https://mlsanity.com/paper/2111.12370/) (2021)
- [Continuum Limit of Lipschitz Learning on Graphs](https://mlsanity.com/paper/2012.03772/) (2020)
- [Fast Algorithms for ℓp-Regression](https://mlsanity.com/paper/2211.03963/) (2022)
- [A comparison among various notions of viscosity solutions for Hamilton-Jacobi equations on networks](https://mlsanity.com/paper/1301.0194/) (2013)

## Abstract (arXiv)

Sparse goal-conditioned planning with few cost-to-go labels can be viewed as a graph-PDE Dirichlet extension problem: extend sparse labels on a goal-dependent boundary to unlabelled graph vertices so that greedy rollouts reach the goal. We study which graph value extensions are planner-admissible under the operational argmin-Q planner. Our main result is a local action-gap certificate: if the surrogate value error along the rollout stays below half the true action gap, then the greedy rollout reaches the goal. Absolutely Minimal Lipschitz Extension (AMLE), the p=infinity endpoint of the graph p-Laplacian family, instantiates this certificate through a comparison-principle fill-distance bound. Harmonic extension, by contrast, can mis-rank local actions because its values reflect boundary hitting probabilities rather than shortest-path greedy order. On 120 AntMaze layout-derived graph configurations, harmonic extension achieves 0.584 aggregate rollout success, while AMLE reaches 0.970. Finite high-p methods also enter a high-success regime, with success 0.903 for p=4, 0.973 for p=8, and 0.982 for a fixed-budget p=16 solver, though the p=16 row is not used as a converged endpoint ranking due to incomplete solver certification. Mechanism audits show that many rollout decisions occur in AMLE-compatible but harmonic-incompatible local geometry, and that AMLE corrects most harmonic inversions on the rollout-weighted decision scope.