# An Improved Reinforcement Learning Algorithm for Learning to Branch

arXiv: https://arxiv.org/abs/2201.06213 · HTML: https://mlsanity.com/paper/2201.06213/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Placed in Imitation learning methods, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 7 of its 15 references that are in the map.
- First posted on arXiv 17 Jan 2022.

## Placed in

- Offline RL and imitation learning from data / [Imitation learning methods](https://mlsanity.com/offlinerl/imitation-learning-methods/)

## Builds on (most cited first, 7 of 7)

- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers](https://mlsanity.com/paper/2011.06069/) (2020)
- [Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm](https://mlsanity.com/paper/2005.10026/) (2020)
- [Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends](https://mlsanity.com/paper/2111.06257/) (2021)

## Built on by (most cited first, 14 of 14)

- [On Representing Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2209.12288/) (2022)
- [On Representing Mixed-Integer Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2210.10759/) (2022)
- [A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availability](https://mlsanity.com/paper/2310.02807/) (2023)
- [Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation](https://mlsanity.com/paper/2310.14161/) (2023)
- [Rethinking the Capacity of Graph Neural Networks for Branching Strategy](https://mlsanity.com/paper/2402.07099/) (2024)
- [Artificial Intelligence for Operations Research: Revolutionizing the Operations Research Process](https://mlsanity.com/paper/2401.03244/) (2024)
- [SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch](https://mlsanity.com/paper/2412.15534/) (2024)
- [Machine Learning Insides OptVerse AI Solver: Design Principles and Applications](https://mlsanity.com/paper/2401.05960/) (2024)
- [CoCo-MILP: Inter-Variable Contrastive and Intra-Constraint Competitive MILP Solution Prediction](https://mlsanity.com/paper/2511.09209/) (2025)
- [RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domains](https://mlsanity.com/paper/2511.02331/) (2025)
- [Data-driven Mixed Integer Optimization through Probabilistic Multi-variable Branching](https://mlsanity.com/paper/2305.12352/) (2023)
- [Discounted Pseudocosts in MILP](https://mlsanity.com/paper/2407.06237/) (2024)
- [Learning Branching Policies for MILPs with Proximal Policy Optimization](https://mlsanity.com/paper/2511.12986/) (2025)
- [Designing faster mixed integer linear programming algorithm via learning the optimal path](https://mlsanity.com/paper/2601.16056/) (2026)

## Abstract (arXiv)

Most combinatorial optimization problems can be formulated as mixed integer linear programming (MILP), in which branch-and-bound (B&B) is a general and widely used method. Recently, learning to branch has become a hot research topic in the intersection of machine learning and combinatorial optimization. In this paper, we propose a novel reinforcement learning-based B&B algorithm. Similar to offline reinforcement learning, we initially train on the demonstration data to accelerate learning massively. With the improvement of the training effect, the agent starts to interact with the environment with its learned policy gradually. It is critical to improve the performance of the algorithm by determining the mixing ratio between demonstration and self-generated data. Thus, we propose a prioritized storage mechanism to control this ratio automatically. In order to improve the robustness of the training process, a superior network is additionally introduced based on Double DQN, which always serves as a Q-network with competitive performance. We evaluate the performance of the proposed algorithm over three public research benchmarks and compare it against strong baselines, including three classical heuristics and one state-of-the-art imitation learning-based branching algorithm. The results show that the proposed algorithm achieves the best performance among compared algorithms and possesses the potential to improve B&B algorithm performance continuously.