Research map / Reinforcement learning / Imitation learning

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

AAAI 2025 · Reinforcement learning › Imitation learning · approach: Imitation combined with RL · 3 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

SORREL learns MILP branching by combining offline RL on demonstrations from a suboptimal heuristic (VHB) with online PPO on a tree MDP plus self-imitation learning from a per-instance priority queue of good trajectories.

Problem

Learned branching heuristics for branch-and-bound in MILP solvers depend on high-quality demonstrations from near-optimal heuristics (e.g., full strong branching), which are costly or unavailable, while existing RL methods have poor sample efficiency.

Approach

A two-stage RL approach: offline RL with a behavior-cloning-regularized actor-critic on suboptimal demonstrations, then online PPO over a tree MDP with random-walk returns, augmented by self-imitation learning on the best past trajectories per instance stored in priority queues.

Key results

• On standard test instances SORREL achieves the lowest solving time on 3 of 5 datasets and the smallest node count among neural methods on all five datasets (e.g., MK: 142 nodes vs 159 for TreeDQN).
• On transfer (larger) instances SORREL has the best solving time on SC, MIS, CFL and best node counts across all datasets, e.g., MIS solving time 62.41s vs 91.35s for RPB.
• Offline-only SORREL-offline already improves over GCNN-VHB on all datasets, e.g., MK 234 vs 458 nodes.

Measured effects reported in the paper

Surprising findings

• SORREL-offline outperforms GCNN-FSB (trained on near-optimal FSB demonstrations) on the MK dataset without online training.
• Previous RL methods (TreeREINFORCE, TreeDQN) show high variance in performance across seeds, which SORREL reduces.

Limitations

• SIL conservativeness prevents benefit from longer RL training time.
• Reward function, returns, and priority queue design remain open for study.
• Suboptimal demonstrations are simulated via VHB rather than from real-world heuristics.

Experimental setup

Datasets: Set Covering Maximal Independent Set Combinatorial Auction Capacitated Facility Location Multiple Knapsack

Benchmarks: Set Covering Maximal Independent Set Combinatorial Auction Capacitated Facility Location Multiple Knapsack

Metrics: solving time (1-shifted geometric mean) number of B&B nodes (10-shifted geometric mean)

Baselines: FSB RPB VHB TreeREINFORCE TreeDQN GCNN-VHB GCNN-FSB

Builds on: tree MDP TreeREINFORCE PPO self-imitation learning GCNN (Gasse et al. 2019)

Closest papers by meaning

• CAMBranch: Contrastive Learning with Augmented MILPs for Branching (ICLR 2024 · similarity 0.86)
• Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning? A Theoretical Perspective (ICML 2024 · similarity 0.85)
• Beyond-Expert Performance with Limited Demonstrations: Efficient Imitation Learning with Double Exploration (ICLR 2025 · similarity 0.85)
• Demonstration-Regularized RL (ICLR 2024 · similarity 0.85)
• $\mathcal{B}$-Coder: Value-Based Deep Reinforcement Learning for Program Synthesis (ICLR 2024 · similarity 0.85)
• An Optimal Discriminator Weighted Imitation Perspective for Reinforcement Learning (ICLR 2025 · similarity 0.85)