SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch

• URL: http://arxiv.org/abs/2412.15534v1
• Date: Fri, 20 Dec 2024 03:48:53 GMT
• Title: SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch
• Authors: Shengyu Feng, Yiming Yang,
• Abstract summary: Mixed Linear Program (MILP) solvers are mostly built upon a Branch sampling-and-Bound (B&B) algorithm, where the efficiency of traditional solvers heavily depends on hand-crafteds for branching. This paper proposes Sub-optimal-Demonstration-Reinforcement Learning (SORREL) for learning to branch.
• Score: 33.90726769113883
• License:
• Abstract: Mixed Integer Linear Program (MILP) solvers are mostly built upon a Branch-and-Bound (B\&B) algorithm, where the efficiency of traditional solvers heavily depends on hand-crafted heuristics for branching. The past few years have witnessed the increasing popularity of data-driven approaches to automatically learn these heuristics. However, the success of these methods is highly dependent on the availability of high-quality demonstrations, which requires either the development of near-optimal heuristics or a time-consuming sampling process. This paper averts this challenge by proposing Suboptimal-Demonstration-Guided Reinforcement Learning (SORREL) for learning to branch. SORREL selectively learns from suboptimal demonstrations based on value estimation. It utilizes suboptimal demonstrations through both offline reinforcement learning on the demonstrations generated by suboptimal heuristics and self-imitation learning on past good experiences sampled by itself. Our experiments demonstrate its advanced performance in both branching quality and training efficiency over previous methods for various MILPs.

Related papers

• Comparative Analysis of Demonstration Selection Algorithms for LLM In-Context Learning [18.58278188791548]
  In-context learning can help Large Language Models (LLMs) to adapt new tasks without additional training. Despite all the proposed demonstration selection algorithms, efficiency and effectiveness remain unclear. This lack of clarity makes it difficult to apply these algorithms in real-world scenarios.
  arXiv  Detail & Related papers  (2024-10-30T15:11:58Z)
• Unlearning with Control: Assessing Real-world Utility for Large Language Model Unlearning [97.2995389188179]
  Recent research has begun to approach large language models (LLMs) unlearning via gradient ascent (GA) Despite their simplicity and efficiency, we suggest that GA-based methods face the propensity towards excessive unlearning. We propose several controlling methods that can regulate the extent of excessive unlearning.
  arXiv  Detail & Related papers  (2024-06-13T14:41:00Z)
• "Give Me an Example Like This": Episodic Active Reinforcement Learning from Demonstrations [3.637365301757111]
  Methods like Reinforcement Learning from Expert Demonstrations (RLED) introduce external expert demonstrations to facilitate agent exploration during the learning process. How to select the best set of human demonstrations that is most beneficial for learning becomes a major concern. This paper presents EARLY, an algorithm that enables a learning agent to generate optimized queries of expert demonstrations in a trajectory-based feature space.
  arXiv  Detail & Related papers  (2024-06-05T08:52:21Z)
• Getting More Juice Out of the SFT Data: Reward Learning from Human Demonstration Improves SFT for LLM Alignment [65.15914284008973]
  We propose to leverage an Inverse Reinforcement Learning (IRL) technique to simultaneously build an reward model and a policy model. We show that the proposed algorithms converge to the stationary solutions of the IRL problem. Our results indicate that it is beneficial to leverage reward learning throughout the entire alignment process.
  arXiv  Detail & Related papers  (2024-05-28T07:11:05Z)
• CAMBranch: Contrastive Learning with Augmented MILPs for Branching [5.216027167816416]
  We propose a framework that generates Augmented MILPs (AMILPs) by applying variable shifting to limited expert data from their original MILPs. Results demonstrate that CAMBranch, trained with only 10% of the complete dataset, exhibits superior performance.
  arXiv  Detail & Related papers  (2024-02-06T02:47:16Z)
• Inverse Reinforcement Learning by Estimating Expertise of Demonstrators [15.662820454886205]
  IRLEED, Inverse Reinforcement Learning by Estimating Expertise of Demonstrators, is a novel framework that overcomes hurdles without prior knowledge of demonstrator expertise. IRLEED enhances existing Inverse Reinforcement Learning (IRL) algorithms by combining a general model for demonstrator suboptimality to address reward bias and action variance. Experiments in both online and offline IL settings, with simulated and human-generated data, demonstrate IRLEED's adaptability and effectiveness.
  arXiv  Detail & Related papers  (2024-02-02T20:21:09Z)
• Leveraging Demonstrations to Improve Online Learning: Quality Matters [54.98983862640944]
  We show that the degree of improvement must depend on the quality of the demonstration data. We propose an informed TS algorithm that utilizes the demonstration data in a coherent way through Bayes' rule.
  arXiv  Detail & Related papers  (2023-02-07T08:49:12Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  Machine learning has emerged as a promising paradigm for branching. We propose retro branching; a simple yet effective approach to RL for branching. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
  arXiv  Detail & Related papers  (2022-05-28T06:08:07Z)
• DEALIO: Data-Efficient Adversarial Learning for Imitation from Observation [57.358212277226315]
  In imitation learning from observation IfO, a learning agent seeks to imitate a demonstrating agent using only observations of the demonstrated behavior without access to the control signals generated by the demonstrator. Recent methods based on adversarial imitation learning have led to state-of-the-art performance on IfO problems, but they typically suffer from high sample complexity due to a reliance on data-inefficient, model-free reinforcement learning algorithms. This issue makes them impractical to deploy in real-world settings, where gathering samples can incur high costs in terms of time, energy, and risk. We propose a more data-efficient IfO algorithm
  arXiv  Detail & Related papers  (2021-03-31T23:46:32Z)
• Learning Sparse Rewarded Tasks from Sub-Optimal Demonstrations [78.94386823185724]
  Imitation learning learns effectively in sparse-rewarded tasks by leveraging the existing expert demonstrations. In practice, collecting a sufficient amount of expert demonstrations can be prohibitively expensive. We propose Self-Adaptive Learning (SAIL) that can achieve (near) optimal performance given only a limited number of sub-optimal demonstrations.
  arXiv  Detail & Related papers  (2020-04-01T15:57:15Z)

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.