Transform then Explore: a Simple and Effective Technique for Exploratory Combinatorial Optimization with Reinforcement Learning

• URL: http://arxiv.org/abs/2404.04661v1
• Date: Sat, 6 Apr 2024 15:31:17 GMT
• Title: Transform then Explore: a Simple and Effective Technique for Exploratory Combinatorial Optimization with Reinforcement Learning
• Authors: Tianle Pu, Changjun Fan, Mutian Shen, Yizhou Lu, Li Zeng, Zohar Nussinov, Chao Chen, Zhong Liu,
• Abstract summary: We propose a gauge transformation (GT) technique to solve optimization problems (COPs) over graphs. GT is very simple, which can be implemented with less than 10 lines of Python codes, and can be applied to a vast majority of reinforcement learning models. We show that traditional RL models with GT technique produce the state-of-the-art performances on the MaxCut problem.
• Score: 11.531786269804707
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many complex problems encountered in both production and daily life can be conceptualized as combinatorial optimization problems (COPs) over graphs. Recent years, reinforcement learning (RL) based models have emerged as a promising direction, which treat the COPs solving as a heuristic learning problem. However, current finite-horizon-MDP based RL models have inherent limitations. They are not allowed to explore adquately for improving solutions at test time, which may be necessary given the complexity of NP-hard optimization tasks. Some recent attempts solve this issue by focusing on reward design and state feature engineering, which are tedious and ad-hoc. In this work, we instead propose a much simpler but more effective technique, named gauge transformation (GT). The technique is originated from physics, but is very effective in enabling RL agents to explore to continuously improve the solutions during test. Morever, GT is very simple, which can be implemented with less than 10 lines of Python codes, and can be applied to a vast majority of RL models. Experimentally, we show that traditional RL models with GT technique produce the state-of-the-art performances on the MaxCut problem. Furthermore, since GT is independent of any RL models, it can be seamlessly integrated into various RL frameworks, paving the way of these models for more effective explorations in the solving of general COPs.

Related papers

• Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II [52.083337333478674]
  This paper proposes a weight-aware deep reinforcement learning (WADRL) approach designed to address the multiobjective vehicle routing problem with time windows (MOVRPTW) The Non-dominated sorting genetic algorithm-II (NSGA-II) method is then employed to optimize the outcomes produced by the WADRL.
  arXiv  Detail & Related papers  (2024-07-18T02:46:06Z)
• Continuous-Time Reinforcement Learning: New Design Algorithms with Theoretical Insights and Performance Guarantees [4.248962756649803]
  This paper introduces a suite of (decentralized) excitable integral reinforcement learning (EIRL) algorithms. We provide convergence and closed-loop stability guarantees on a significant application problem of controlling an unstable, nonminimum phase hypersonic vehicle.
  arXiv  Detail & Related papers  (2023-07-18T01:36:43Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms. Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return. We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
  arXiv  Detail & Related papers  (2023-02-02T18:27:20Z)
• A Survey of Meta-Reinforcement Learning [69.76165430793571]
  We cast the development of better RL algorithms as a machine learning problem itself in a process called meta-RL. We discuss how, at a high level, meta-RL research can be clustered based on the presence of a task distribution and the learning budget available for each individual task. We conclude by presenting the open problems on the path to making meta-RL part of the standard toolbox for a deep RL practitioner.
  arXiv  Detail & Related papers  (2023-01-19T12:01:41Z)
• Reinforcement Learning to Solve NP-hard Problems: an Application to the CVRP [0.0]
  We evaluate the use of Reinforcement Learning (RL) to solve a classic optimization problem. We compare two of the most promising RL approaches with traditional solving techniques on a set of benchmark instances. We find that despite not returning the best solution, the RL approach has many advantages over traditional solvers.
  arXiv  Detail & Related papers  (2022-01-14T11:16:17Z)
• Automated Reinforcement Learning (AutoRL): A Survey and Open Problems [92.73407630874841]
  Automated Reinforcement Learning (AutoRL) involves not only standard applications of AutoML but also includes additional challenges unique to RL. We provide a common taxonomy, discuss each area in detail and pose open problems which would be of interest to researchers going forward.
  arXiv  Detail & Related papers  (2022-01-11T12:41:43Z)
• PC-MLP: Model-based Reinforcement Learning with Policy Cover Guided Exploration [15.173628100049129]
  This work studies a model-based algorithm for both Kernelized Regulators (KNR) and linear Markov Decision Processes (MDPs) For both models, our algorithm guarantees sample complexity and only uses access to a planning oracle. Our method can also perform reward-free exploration efficiently.
  arXiv  Detail & Related papers  (2021-07-15T15:49:30Z)
• RL-DARTS: Differentiable Architecture Search for Reinforcement Learning [62.95469460505922]
  We introduce RL-DARTS, one of the first applications of Differentiable Architecture Search (DARTS) in reinforcement learning (RL) By replacing the image encoder with a DARTS supernet, our search method is sample-efficient, requires minimal extra compute resources, and is also compatible with off-policy and on-policy RL algorithms, needing only minor changes in preexisting code. We show that the supernet gradually learns better cells, leading to alternative architectures which can be highly competitive against manually designed policies, but also verify previous design choices for RL policies.
  arXiv  Detail & Related papers  (2021-06-04T03:08:43Z)
• Reinforcement Learning as One Big Sequence Modeling Problem [84.84564880157149]
  Reinforcement learning (RL) is typically concerned with estimating single-step policies or single-step models. We view RL as a sequence modeling problem, with the goal being to predict a sequence of actions that leads to a sequence of high rewards.
  arXiv  Detail & Related papers  (2021-06-03T17:58:51Z)
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning [35.50454156611722]
  Reinforcement learning (RL) has recently emerged as a new framework to tackle these problems. We propose a general RL framework that not only exhibits state-of-the-art empirical performance but also generalizes to a variety class of COPs.
  arXiv  Detail & Related papers  (2021-02-14T18:05:42Z)
• Reinforcement Learning for Combinatorial Optimization: A Survey [12.323976053967066]
  Many traditional algorithms for solving optimization problems involve using hand-crafteds that sequentially construct a solution. Reinforcement learning (RL) proposes a good alternative to automate the search of theses by training an agent in a supervised or self-supervised manner.
  arXiv  Detail & Related papers  (2020-03-07T16:19:45Z)

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.