mlsanityData to 14 Oct 2026

Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming

arXiv 2503.16371 ↗First posted 20 Mar 2025cs.AI cs.LGcited by 1

On the map: Deep reinforcement learning methods → Deep RL algorithms and representations

Abstract (arXiv)

Domain-Independent Dynamic Programming (DIDP) is a state-space search paradigm based on dynamic programming for combinatorial optimization. In its current implementation, DIDP guides the search using user-defined dual bounds. Reinforcement learning (RL) is increasingly being applied to combinatorial optimization problems and shares several key structures with DP, being represented by the Bellman equation and state-based transition systems. We propose using reinforcement learning to obtain a heuristic function to guide the search in DIDP. We develop two RL-based guidance approaches: value-based guidance using Deep Q-Networks and policy-based guidance using Proximal Policy Optimization. Our experiments indicate that RL-based guidance significantly outperforms standard DIDP and problem-specific greedy heuristics with the same number of node expansions. Further, despite longer node evaluation times, RL guidance achieves better run-time performance than standard DIDP on three of four benchmark domains.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods. Builds on 25 of its 40 references that are in the map. First posted on arXiv 20 Mar 2025.

Builds on

25 of 40 references.

References · 25

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2017Graph Attention Networkscited by 8,923
  3. 2015Trust Region Policy Optimizationcited by 2,580
  4. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  5. 2017Deep Setscited by 1,421
  6. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 734
  7. 2018Attention, Learn to Solve Routing Problems!cited by 656
  8. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  9. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  10. 2017A Brief Survey of Deep Reinforcement Learningcited by 483
  11. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 333
  12. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
13 more
  1. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
  2. 2020A Closer Look at Invalid Action Masking in Policy Gradient Algorithmscited by 171
  3. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 162
  4. 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 140
  5. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  6. 2020Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimizationcited by 63
  7. 2019Hierarchical Reinforcement Learning with Advantage-Based Auxiliary Rewardscited by 40
  8. 2018Single-Agent Policy Tree Search With Guaranteescited by 22
  9. 2021Reinforcement Learning for Classical Planning: Viewing Heuristics as Dense Reward Generatorscited by 21
  10. 2021Policy-Guided Heuristic Search with Guaranteescited by 20
  11. 2022Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimizationcited by 7
  12. 2024Towards a Generic Representation of Combinatorial Problems for Learning-Based Approachescited by 5
  13. 2024Domain-Independent Dynamic Programmingcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Reinforcement Learning Methods for Neighborhood Selection in Local Searchcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Heuristics for Combinatorial Optimization via Value-based Reinforcement Learning: A Unified Framework and Analysis
  2. 2026Reinforcement Learning in Operational Research: A Technical Review and Practical Roadmap
  3. 2025Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
  4. 2026Modularized Reinforcement Learning on LLMs: From MDP Creation to Exploration and Learning
  5. 2026Offline Decision Transformers for Neural Combinatorial Optimization: Surpassing Heuristics on the Traveling Salesman Problem
  6. 2024Efficient Exploration in Deep Reinforcement Learning: A Novel Bayesian Actor-Critic Algorithm
  7. 2026When does learning pay off? A study on DRL-based dynamic algorithm configuration for carbon-aware scheduling
  8. 2025Exploiting Symbolic Heuristics for the Synthesis of Domain-Specific Temporal Planning Guidance using Reinforcement Learning