Unraveling the Rainbow: can value-based methods schedule?

• URL: http://arxiv.org/abs/2505.03323v1
• Date: Tue, 06 May 2025 08:51:17 GMT
• Title: Unraveling the Rainbow: can value-based methods schedule?
• Authors: Arthur Corrêa, Alexandre Jesus, Cristóvão Silva, Samuel Moniz,
• Abstract summary: Broadly, deep reinforcement learning methods fall into two categories: policy-based and value-based.<n>We show that several value-based approaches can match or even outperform the widely adopted policy optimization algorithm.
• Score: 41.94295877935867
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, deep reinforcement learning has emerged as a promising approach for solving complex combinatorial optimization problems. Broadly, deep reinforcement learning methods fall into two categories: policy-based and value-based. While value-based approaches have achieved notable success in domains such as the Arcade Learning Environment, the combinatorial optimization community has predominantly favored policy-based methods, often overlooking the potential of value-based algorithms. In this work, we conduct a comprehensive empirical evaluation of value-based algorithms, including the deep q-network and several of its advanced extensions, within the context of two complex combinatorial problems: the job-shop and the flexible job-shop scheduling problems, two fundamental challenges with multiple industrial applications. Our results challenge the assumption that policy-based methods are inherently superior for combinatorial optimization. We show that several value-based approaches can match or even outperform the widely adopted proximal policy optimization algorithm, suggesting that value-based strategies deserve greater attention from the combinatorial optimization community. Our code is openly available at: https://github.com/AJ-Correa/Unraveling-the-Rainbow.

Related papers

• Learning General Policies with Policy Gradient Methods [11.393603788068775]
  provable correct policies that generalize over all instances of a given domain have been learned using methods.<n>The aim of this work is to bring these two research threads together to illuminate the conditions under which (deep) reinforcement learning approaches can be used.<n>We draw on lessons learned from previous and deep learning approaches, and extend them in a convenient way.
  arXiv  Detail & Related papers  (2025-12-22T13:08:58Z)
• Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning [66.4260157478436]
  We study reinforcement learning in the policy learning setting.<n>The goal is to find a policy whose performance is competitive with the best policy in a given class of interest.
  arXiv  Detail & Related papers  (2025-07-06T14:40:05Z)
• Constructing an Optimal Behavior Basis for the Option Keyboard [15.595163824752769]
  Generalized Policy Improvement (GPI) addresses this by combining a set of base policies to produce a new one that is at least as good.<n>The Option Keyboard (OK) improves upon GPI by producing policies that are at least as good -- and often better.<n>This raises a key question: is there an optimal set of base policies that enables zero-shot identification of optimal solutions for any linear tasks?<n>We show that it significantly reduces the number of base policies needed to ensure optimality in new tasks.
  arXiv  Detail & Related papers  (2025-05-01T18:32:21Z)
• Offline Imitation Learning from Multiple Baselines with Applications to Compiler Optimization [17.729842629392742]
  We study a Reinforcement Learning problem in which we are given a set of trajectories collected with K baseline policies. The goal is to learn a policy which performs as well as the best combination of baselines on the entire state space.
  arXiv  Detail & Related papers  (2024-03-28T14:34:02Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Multi-Task Off-Policy Learning from Bandit Feedback [54.96011624223482]
  We propose a hierarchical off-policy optimization algorithm (HierOPO), which estimates the parameters of the hierarchical model and then acts pessimistically with respect to them. We prove per-task bounds on the suboptimality of the learned policies, which show a clear improvement over not using the hierarchical model. Our theoretical and empirical results show a clear advantage of using the hierarchy over solving each task independently.
  arXiv  Detail & Related papers  (2022-12-09T08:26:27Z)
• Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch [13.024115985194932]
  We propose a new approach for solving the data labeling and inference issues in optimization based on the use of the reinforcement learning (RL) paradigm. We use imitation learning to bootstrap an RL agent and then use Proximal Policy (PPO) to further explore global optimal actions.
  arXiv  Detail & Related papers  (2022-06-14T16:35:58Z)
• Towards an Understanding of Default Policies in Multitask Policy Optimization [29.806071693039655]
  Much of the recent success of deep reinforcement learning has been driven by regularized policy optimization (RPO) algorithms. We take a first step towards filling this gap by formally linking the quality of the default policy to its effect on optimization. We then derive a principled RPO algorithm for multitask learning with strong performance guarantees.
  arXiv  Detail & Related papers  (2021-11-04T16:45:15Z)
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy [95.98698822755227]
  We make the first attempt to study risk-sensitive deep reinforcement learning under the average reward setting with the variance risk criteria. We propose an actor-critic algorithm that iteratively and efficiently updates the policy, the Lagrange multiplier, and the Fenchel dual variable.
  arXiv  Detail & Related papers  (2020-12-28T05:02:26Z)
• SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learning [102.78958681141577]
  We present SUNRISE, a simple unified ensemble method, which is compatible with various off-policy deep reinforcement learning algorithms. SUNRISE integrates two key ingredients: (a) ensemble-based weighted Bellman backups, which re-weight target Q-values based on uncertainty estimates from a Q-ensemble, and (b) an inference method that selects actions using the highest upper-confidence bounds for efficient exploration.
  arXiv  Detail & Related papers  (2020-07-09T17:08:44Z)
• Population-Guided Parallel Policy Search for Reinforcement Learning [17.360163137926]
  A new population-guided parallel learning scheme is proposed to enhance the performance of off-policy reinforcement learning (RL) In the proposed scheme, multiple identical learners with their own value-functions and policies share a common experience replay buffer, and search a good policy in collaboration with the guidance of the best policy information.
  arXiv  Detail & Related papers  (2020-01-09T10:13:57Z)

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.