On Using Admissible Bounds for Learning Forward Search Heuristics

• URL: http://arxiv.org/abs/2308.11905v3
• Date: Tue, 7 May 2024 11:11:47 GMT
• Title: On Using Admissible Bounds for Learning Forward Search Heuristics
• Authors: Carlos Núñez-Molina, Masataro Asai, Pablo Mesejo, Juan Fernández-Olivares,
• Abstract summary: We focus on how to effectively utilize the information provided by admissibles in learning. We model the learned as a truncated ssian, where admissibles are used not as training targets but as lower bounds of this distribution. Results show that our proposed method converges faster during training and yields bettergauss.
• Score: 9.749638953163391
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In recent years, there has been growing interest in utilizing modern machine learning techniques to learn heuristic functions for forward search algorithms. Despite this, there has been little theoretical understanding of what they should learn, how to train them, and why we do so. This lack of understanding has resulted in the adoption of diverse training targets (suboptimal vs optimal costs vs admissible heuristics) and loss functions (e.g., square vs absolute errors) in the literature. In this work, we focus on how to effectively utilize the information provided by admissible heuristics in heuristic learning. We argue that learning from poly-time admissible heuristics by minimizing mean square errors (MSE) is not the correct approach, since its result is merely a noisy, inadmissible copy of an efficiently computable heuristic. Instead, we propose to model the learned heuristic as a truncated gaussian, where admissible heuristics are used not as training targets but as lower bounds of this distribution. This results in a different loss function from the MSE commonly employed in the literature, which implicitly models the learned heuristic as a gaussian distribution. We conduct experiments where both MSE and our novel loss function are applied to learning a heuristic from optimal plan costs. Results show that our proposed method converges faster during training and yields better heuristics.

Related papers

• Attribute-to-Delete: Machine Unlearning via Datamodel Matching [65.13151619119782]
  Machine unlearning -- efficiently removing a small "forget set" training data on a pre-divertrained machine learning model -- has recently attracted interest. Recent research shows that machine unlearning techniques do not hold up in such a challenging setting.
  arXiv  Detail & Related papers  (2024-10-30T17:20:10Z)
• Automatic debiasing of neural networks via moment-constrained learning [0.0]
  Naively learning the regression function and taking a sample mean of the target functional results in biased estimators. We propose moment-constrained learning as a new RR learning approach that addresses some shortcomings in automatic debiasing.
  arXiv  Detail & Related papers  (2024-09-29T20:56:54Z)
• Learning Latent Graph Structures and their Uncertainty [63.95971478893842]
  Graph Neural Networks (GNNs) use relational information as an inductive bias to enhance the model's accuracy. As task-relevant relations might be unknown, graph structure learning approaches have been proposed to learn them while solving the downstream prediction task.
  arXiv  Detail & Related papers  (2024-05-30T10:49:22Z)
• Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
  We propose a novel equation discovery method based on Kernel learning and BAyesian Spike-and-Slab priors (KBASS) We use kernel regression to estimate the target function, which is flexible, expressive, and more robust to data sparsity and noises. We develop an expectation-propagation expectation-maximization algorithm for efficient posterior inference and function estimation.
  arXiv  Detail & Related papers  (2023-10-09T03:55:09Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  We suggest learning the instance-dependent proxies that are supposed to notably increase the efficiency of the search. The first proxy we suggest to learn is the correction factor, i.e. the ratio between the instance independent cost-to-go estimate and the perfect one. The second proxy is the path probability, which indicates how likely the grid cell is lying on the shortest path.
  arXiv  Detail & Related papers  (2022-12-22T14:26:11Z)
• Relational Surrogate Loss Learning [41.61184221367546]
  This paper revisits the surrogate loss learning, where a deep neural network is employed to approximate the evaluation metrics. In this paper, we show that directly maintaining the relation of models between surrogate losses and metrics suffices. Our method is much easier to optimize and enjoys significant efficiency and performance gains.
  arXiv  Detail & Related papers  (2022-02-26T17:32:57Z)
• MURAL: Meta-Learning Uncertainty-Aware Rewards for Outcome-Driven Reinforcement Learning [65.52675802289775]
  We show that an uncertainty aware classifier can solve challenging reinforcement learning problems. We propose a novel method for computing the normalized maximum likelihood (NML) distribution. We show that the resulting algorithm has a number of intriguing connections to both count-based exploration methods and prior algorithms for learning reward functions.
  arXiv  Detail & Related papers  (2021-07-15T08:19:57Z)
• DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction [96.90215318875859]
  We show that bootstrapping-based Q-learning algorithms do not necessarily benefit from corrective feedback. We propose a new algorithm, DisCor, which computes an approximation to this optimal distribution and uses it to re-weight the transitions used for training.
  arXiv  Detail & Related papers  (2020-03-16T16:18:52Z)
• Adaptive Approximate Policy Iteration [22.915651391812187]
  We present a learning scheme which enjoys a $tildeO(T2/3)$ regret bound for undiscounted, continuing learning in uniformly ergodic MDPs. This is an improvement over the best existing bound of $tildeO(T3/4)$ for the average-reward case with function approximation.
  arXiv  Detail & Related papers  (2020-02-08T02:27:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.