mlsanityData to 13 Oct 2026

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

arXiv 2605.19185 ↗First posted 18 May 2026cs.LG cs.AIcited by 0

Not on the map. Why?

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.

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

Builds on

19 of 50 references.

References · 19

  1. 2020D4RL: Datasets for Deep Data-Driven Reinforcement Learningcited by 1,415
  2. 2017Hindsight Experience Replaycited by 1,104
  3. 2019Search on the Replay Buffer: Bridging Planning and Reinforcement Learningcited by 192
  4. 2016Value Iteration Networkscited by 158
  5. 2019Planning with Goal-Conditioned Policiescited by 145
  6. 2018Temporal Difference Models: Model-Free Deep RL for Model-Based Controlcited by 89
  7. 2017Analysis of p-Laplacian Regularization in Semi-Supervised Learningcited by 39
  8. 2017The game theoretic p-Laplacian and semi-supervised learning with few labelscited by 22
  9. 2018Properly-weighted graph Laplacian for semi-supervised learningcited by 19
  10. 2020Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Ratescited by 18
  11. 2015Algorithms for Lipschitz Learning on Graphscited by 16
  12. 2016Asymptotic behavior of ℓp-based Laplacian regularization in semi-supervised learningcited by 16
7 more
  1. 2017Consistency of Lipschitz learning with infinite unlabeled data and finite labeled datacited by 15
  2. 2019Fast, Provably convergent IRLS Algorithm for p-norm Linear Regressioncited by 10
  3. 2019A maximum principle argument for the uniform convergence of graph Laplacian regressorscited by 9
  4. 2021Uniform Convergence Rates for Lipschitz Learning on Graphscited by 9
  5. 2020Continuum Limit of Lipschitz Learning on Graphscited by 6
  6. 2022Fast Algorithms for ℓp-Regressioncited by 4
  7. 2013A comparison among various notions of viscosity solutions for Hamilton-Jacobi equations on networkscited by 2

Built on by

Not cited yet.