Generalization in Deep RL for TSP Problems via Equivariance and Local Search

• URL: http://arxiv.org/abs/2110.03595v1
• Date: Thu, 7 Oct 2021 16:20:37 GMT
• Title: Generalization in Deep RL for TSP Problems via Equivariance and Local Search
• Authors: Wenbin Ouyang, Yisen Wang, Paul Weng, Shaochen Han
• Abstract summary: We propose a simple deep learning architecture that learns with novel RL training techniques. We empirically evaluate our proposition on random and realistic TSP problems against relevant state-of-the-art deep RL methods.
• Score: 21.07325126324399
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Deep reinforcement learning (RL) has proved to be a competitive heuristic for solving small-sized instances of traveling salesman problems (TSP), but its performance on larger-sized instances is insufficient. Since training on large instances is impractical, we design a novel deep RL approach with a focus on generalizability. Our proposition consisting of a simple deep learning architecture that learns with novel RL training techniques, exploits two main ideas. First, we exploit equivariance to facilitate training. Second, we interleave efficient local search heuristics with the usual RL training to smooth the value landscape. In order to validate the whole approach, we empirically evaluate our proposition on random and realistic TSP problems against relevant state-of-the-art deep RL methods. Moreover, we present an ablation study to understand the contribution of each of its component

Related papers

• 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)
• Understanding the Complexity Gains of Single-Task RL with a Curriculum [83.46923851724408]
  Reinforcement learning (RL) problems can be challenging without well-shaped rewards. We provide a theoretical framework that reformulates a single-task RL problem as a multi-task RL problem defined by a curriculum. We show that sequentially solving each task in the multi-task RL problem is more computationally efficient than solving the original single-task problem.
  arXiv  Detail & Related papers  (2022-12-24T19:46:47Z)
• Meta Reinforcement Learning with Successor Feature Based Context [51.35452583759734]
  We propose a novel meta-RL approach that achieves competitive performance comparing to existing meta-RL algorithms. Our method does not only learn high-quality policies for multiple tasks simultaneously but also can quickly adapt to new tasks with a small amount of training.
  arXiv  Detail & Related papers  (2022-07-29T14:52:47Z)
• Jump-Start Reinforcement Learning [68.82380421479675]
  We present a meta algorithm that can use offline data, demonstrations, or a pre-existing policy to initialize an RL policy. In particular, we propose Jump-Start Reinforcement Learning (JSRL), an algorithm that employs two policies to solve tasks. We show via experiments that JSRL is able to significantly outperform existing imitation and reinforcement learning algorithms.
  arXiv  Detail & Related papers  (2022-04-05T17:25:22Z)
• Improving Generalization of Deep Reinforcement Learning-based TSP Solvers [19.29028564568974]
  We propose a novel approach named MAGIC that includes a deep learning architecture and a DRL training method. Our architecture, which integrates a multilayer perceptron, a graph neural network, and an attention model, defines a policy that sequentially generates a traveling salesman solution. Our training method includes several innovations: (1) we interleave DRL policy updates with local search (using a new local search technique), (2) we use a novel simple baseline, and (3) we apply gradient learning.
  arXiv  Detail & Related papers  (2021-10-06T15:16:19Z)
• POAR: Efficient Policy Optimization via Online Abstract State Representation Learning [6.171331561029968]
  State Representation Learning (SRL) is proposed to specifically learn to encode task-relevant features from complex sensory data into low-dimensional states. We introduce a new SRL prior called domain resemblance to leverage expert demonstration to improve SRL interpretations. We empirically verify POAR to efficiently handle tasks in high dimensions and facilitate training real-life robots directly from scratch.
  arXiv  Detail & Related papers  (2021-09-17T16:52:03Z)
• Heuristic-Guided Reinforcement Learning [31.056460162389783]
  Tabula rasa RL algorithms require environment interactions or computation that scales with the horizon of the decision-making task. Our framework can be viewed as a horizon-based regularization for controlling bias and variance in RL under a finite interaction budget. In particular, we introduce the novel concept of an "improvable" -- a that allows an RL agent to extrapolate beyond its prior knowledge.
  arXiv  Detail & Related papers  (2021-06-05T00:04:09Z)
• Combining Pessimism with Optimism for Robust and Efficient Model-Based Deep Reinforcement Learning [56.17667147101263]
  In real-world tasks, reinforcement learning agents encounter situations that are not present during training time. To ensure reliable performance, the RL agents need to exhibit robustness against worst-case situations. We propose the Robust Hallucinated Upper-Confidence RL (RH-UCRL) algorithm to provably solve this problem.
  arXiv  Detail & Related papers  (2021-03-18T16:50:17Z)
• FOCAL: Efficient Fully-Offline Meta-Reinforcement Learning via Distance Metric Learning and Behavior Regularization [10.243908145832394]
  We study the offline meta-reinforcement learning (OMRL) problem, a paradigm which enables reinforcement learning (RL) algorithms to quickly adapt to unseen tasks. This problem is still not fully understood, for which two major challenges need to be addressed. We provide analysis and insight showing that some simple design choices can yield substantial improvements over recent approaches.
  arXiv  Detail & Related papers  (2020-10-02T17:13:39Z)
• Dynamics Generalization via Information Bottleneck in Deep Reinforcement Learning [90.93035276307239]
  We propose an information theoretic regularization objective and an annealing-based optimization method to achieve better generalization ability in RL agents. We demonstrate the extreme generalization benefits of our approach in different domains ranging from maze navigation to robotic tasks. This work provides a principled way to improve generalization in RL by gradually removing information that is redundant for task-solving.
  arXiv  Detail & Related papers  (2020-08-03T02:24:20Z)

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.