Branching Reinforcement Learning

2022-02-16 · Yihan Du, Wei Chen

In this paper, we propose a novel Branching Reinforcement Learning (Branching RL) model, and investigate both Regret Minimization (RM) and Reward-Free Exploration (RFE) metrics for this model. Unlike standard RL where the trajectory of each episode is a single $H$-step path, branching RL allows an agent to take multiple base actions in a state such that transitions branch out to multiple successor states correspondingly, and thus it generates a tree-structured trajectory. This model finds important applications in hierarchical recommendation systems and online advertising. For branching RL, we establish new Bellman equations and key lemmas, i.e., branching value difference lemma and branching law of total variance, and also bound the total variance by only $O(H^2)$ under an exponentially-large trajectory. For RM and RFE metrics, we propose computationally efficient algorithms BranchVI and BranchRFE, respectively, and derive nearly matching upper and lower bounds. Our results are only polynomial in problem parameters despite exponentially-large trajectories.

📄 PDF Abstract BibTeX arXiv:2202.07995

Code (0)

등록된 구현이 없습니다.

Tasks

LEMMARecommendation Systems reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Methods 이 논문이 사용한 방법론

BASE 설명 없음

Improving Learning to Branch via Reinforcement Learning

2021-01-01 · NeurIPS Workshop LMCA 2020 12 · Haoran Sun, Wenbo Chen, Hui Li, Le Song

Branch-and-Bound~(B\&B) is a general and widely used algorithm paradigm for solving Mixed Integer Programming~(MIP). Recently there is a surge of interest in designing learning-based branching policies as a fast approxi…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Model-free Reinforcement Learning for Branching Markov Decision Processes

2021-06-12 · Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi 외

We study reinforcement learning for the optimal control of Branching Markov Decision Processes (BMDPs), a natural extension of (multitype) Branching Markov Chains (BMCs). The state of a (discrete-time) BMCs is a collecti…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization

2025-11-12 · Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan 외 arxiv

Mixed-Integer Linear Programming (MILP) lies at the core of many real-world combinatorial optimization (CO) problems, traditionally solved by branch-and-bound (B&B). A key driver influencing B&B solvers efficiency is the…

Reinforcement Learning

Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories

2022-05-28 · Christopher W. F. Parsonson, Alexandre Laterre, Thomas D. Barrett

Combinatorial optimisation problems framed as mixed integer linear programmes (MILPs) are ubiquitous across a range of real-world applications. The canonical branch-and-bound algorithm seeks to exactly solve MILPs by con…

Imitation Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Learning to branch with Tree MDPs

2022-05-23 · Lara Scavuzzo, Feng Yang Chen, Didier Chételat, Maxime Gasse 외

State-of-the-art Mixed Integer Linear Program (MILP) solvers combine systematic tree search with a plethora of hard-coded heuristics, such as the branching rule. The idea of learning branching rules from data has receive…

Reinforcement Learning (RL)