{"id":"a2d17ad8-df96-4525-897f-91c71ada493f","arxiv_id":"2412.15534","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"SORREL combines offline reinforcement learning on suboptimal demonstrations with self-imitation finetuning to learn branching policies that match expert-trained solvers.","lead":"This paper presents SORREL, a two-stage learning method that trains a branching heuristic for mixed-integer linear programs using suboptimal demonstrations instead of expert ones. It matters because it could reduce the training cost of learned solvers while keeping performance close to solvers trained on near-optimal data.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central claim rests on an unproven equivalence between discounted local-dual-bound reward and B&B node count; no ablation isolates the reward design, so the mechanism behind SORREL's reported gains is not established.","rationale":"In good faith, the paper does what it claims at the level of the included experiments: SORREL improves over GCNN-VHB and the RL baselines on the tested benchmarks, and the theoretical propositions about contraction and the tree-MDP formulation are standard. However, the central claim that the tree-MDP objective is the reason for these improvements depends on an unproven alignment between expected discounted LDB improvement and B&B node count. The reader's weakest_assumption identified exactly this reward-proxy concern, and I agree. This is not a fatal flaw or an internal inconsistency; it is a load-bearing empirical claim that needs explicit validation, especially because the paper's own ablation study does not vary the reward. Other issues such as missing code, absent hyperparameters, and the omission of the parallel work Zhang et al. (2024) are real but secondary to the objective-alignment question. Since the reader already returned a moderate-confidence CONDITIONAL verdict, my analysis does not move the verdict; it sharpens the condition that should be met before the central mechanism is accepted.","tokens_in":14144,"tokens_out":8402,"duration_ms":81266,"concrete_test":"From the stored B&B trajectories used for Tables 1-3, compute for every recorded branching decision (s_i, a_i) the discounted LDB return R_i defined in the Method section and the number of nodes in the subtree actually explored below that decision under the same policy. Aggregate a Spearman correlation over all nodes and all five benchmarks. If the correlation is not negative and reasonably strong (say rho < -0.5) on each benchmark, the objective maximized by Eq. (4) is not aligned with the stated tree-size metric, and the central mechanism is unsupported; if it is negative and strong, the reward-proxy assumption is corroborated without retraining.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that SORREL improves branching quality and training efficiency by selectively learning from suboptimal demonstrations under a tree-MDP objective that reduces B&B tree size. The bridge between the objective and the metric is asserted, not shown, in the Method section: after defining the return as expected discounted local-dual-bound (LDB) improvement along a random-walk path (Eq. 4), the paper states that 'maximizing the return would encourage the brancher to improve the dual bound as soon as possible, and thus reduce the size of the search tree as well.' That is a heuristic proxy. Total node count depends not only on bound improvement but also on the shape of the whole tree, the node-selection policy, and the quality of the primal bound; maximizing early LDB gain can in principle increase the number of nodes if it produces lopsided subtrees or interacts badly with node selection. The experiments do not isolate this assumption: Table 3 ablates offline pretraining, online finetuning, and SIL, but never varies the reward; Figure 4 varies demonstration quality, not the objective. Consequently, the reported gains could in principle come from the BC/offline/SIL machinery rather than from the tree-MDP reward, and the claimed generalization to MILP families where LDB is uninformative (as the paper itself notes for MK) is not supported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes SORREL, a two-stage reinforcement learning method for variable selection (branching) in MILP branch-and-bound. Stage 1 performs offline RL on demonstrations collected by a suboptimal hybrid heuristic (VHB), using a TD3+BC-style objective. Stage 2 finetunes the agent online with PPO and augments it with self-imitation learning from per-instance priority queues. The RL formulation is a tree MDP with a random-walk discounted local-dual-bound reward. Experiments on five MILP benchmarks and a size-transfer setting report that SORREL reduces B&B tree size and solving time relative to GCNN, TreeREINFORCE, TreeDQN, and the underlying suboptimal heuristic, with ablations attributing gains to offline pretraining and SIL.","tokens_in":14430,"tokens_out":7249,"duration_ms":66658,"significance":"If the empirical results hold, the paper makes a useful practical contribution: it shows that suboptimal demonstrations can be used to train branching policies that match or beat expert-trained imitation on several benchmarks while improving sample efficiency. The evaluation is broad (five benchmark families, transfer to larger instances, and ablations) and the core algorithmic recipe is plausible. The main weakness is that the link between the random-walk local-dual-bound reward and the actual evaluation metric (B&B node count) is asserted heuristically and never tested by a reward ablation, so the mechanism behind the reported gains is not established. The paper would be significantly strengthened by isolating the reward design and by tightening the theoretical claims.","major_comments":[{"comment":"The sentence 'Since γ ∈ [0, 1), maximizing the return would encourage the brancher to improve the dual bound as soon as possible, and thus reduce the size of the search tree as well' is the load-bearing link between the RL objective and the evaluation metric, but it is asserted rather than proved. Total B&B node count depends on the entire tree shape, the node-selection policy, and the evolution of the primal bound; maximizing discounted local dual-bound improvement can in principle increase the number of nodes by producing lopsided subtrees or interacting badly with node selection. The experiments never vary the reward (Table 3 ablates offline pretraining, online finetuning, and SIL, while Figure 4 varies demonstration quality), so the reported gains could come from the BC/offline/SIL machinery instead of the tree-MDP reward. Please add either a formal argument or an ablation that isolates the reward design (for example, a sparse -1-per-node reward, an undiscounted LDB reward, or different settings of κ and γ).","section":"Method, 'Tree MDP for B&B' (after Proposition 3)"},{"comment":"The Bellman target in Eq. (5) writes E_{schi, achi}[rchi + γQθ′(schi, achi)] but does not specify the distribution of the next action achi. If achi is drawn from the current policy πφ, the equation is a policy-evaluation target; if it is drawn from the behavior policy that generated D1, the learned Q is not the value of the actor. The subsequent actor update (Eq. (6)) assumes the former, but the text should state it explicitly, because the choice affects both correctness and reproducibility of the offline stage.","section":"Eq. (5), 'Pretraining with Offline Reinforcement Learning'"},{"comment":"The paper's own limitation paragraph concedes that 'Design alternatives, including the reward function, returns, and priority queues, are still open for study.' This is consistent with the heuristic status of the reward objective described in my first comment, but it also means the abstract's and introduction's claims that SORREL is 'grounded' on the tree MDP should be narrowed: the theoretical results (Propositions 2 and 3) establish properties of the random-walk Bellman operator, not that the LDB reward is the right objective for minimizing B&B tree size. Please separate these claims and support the reward choice with evidence.","section":"Conclusion & Limitation"}],"minor_comments":[{"comment":"The text contains a typo: 'TreeREINFROCE' should be 'TreeREINFORCE'.","section":"Main Results paragraph"},{"comment":"The table header 'SORRE-offline' should be 'SORREL-offline' for consistency with the text.","section":"Table 3"},{"comment":"The sentence 'we always keep the results from the hard instances and the solving is not interrupted only if the 1-hour time limit is reached' is unclear; please state explicitly how timeouts are handled in the reported time metrics (e.g., whether a timeout is recorded as 3600 seconds).","section":"Experimental Setup, Metrics"},{"comment":"Hyperparameters α, κ, γ, ϵ, the network architecture, the number of training iterations, and the priority-queue size are not reported, which makes the training-efficiency comparison hard to reproduce.","section":"Experimental Setup"},{"comment":"The y-axis label is missing; the caption should state what quantity is plotted (tree size or solving time).","section":"Figure 4"},{"comment":"Proposition 1 ('Any B&B process following Definition 1 can be formulated as a tree MDP') is true by construction because Definition 1 already assigns the tree-MDP components; the 'universal model' claim would be stronger if the paper showed how arbitrary node-selection policies are handled or how the random-walk abstraction covers the actual B&B queue.","section":"Method, Proposition 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the scope of a machine-learning-for-combinatorial-optimization venue, and the empirical study is reasonably thorough. My main concern is not the method's validity but the gap between the claimed theoretical grounding and the evidence presented. I would like the authors to add a reward ablation and to clarify the offline Bellman target; these are addressable in revision. I also note that no code or data release is mentioned, which limits independent verification of the training-efficiency claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"SORREL is a sensible engineering contribution, not a deep theoretical one. The two-stage combination of TD3+BC-style offline RL on cheap heuristic demonstrations, followed by PPO with self-imitation learning, appears new for learning-to-branch, and the empirical results on five benchmarks are strong enough to take seriously. The paper is honest about its main limitation: it explicitly says reward design and returns are open alternatives.\n\nWhat is actually new: using offline RL to avoid the need for expert demonstrations, plus SIL to improve online sample efficiency. That is a useful practical recipe. The tree-MDP formulation is a minor generalization of Scavuzzo et al. 2022, and the propositions are standard contraction and stationary-distribution facts—correct but not deep. The experiments support the central claim that SORREL beats the included neural baselines on most benchmarks, transfers to larger instances, and that offline pretraining plus online finetuning both help. The MK result, where SORREL beats GCNN-FSB from suboptimal demonstrations, is the most convincing single datapoint.\n\nNow the soft spots. The reward design is asserted to reduce tree size via \"improve the dual bound as soon as possible,\" but there is no ablation that varies the reward, and the link between discounted local-dual-bound improvement along a random walk and total B&B node count is genuinely heuristic. That is a real gap, but it does not sink the paper: the method works empirically even if its mechanism is not isolated. Also missing: no comparison to the parallel Zhang et al. 2024 hybrid augmentation approach, no code, and no hyperparameter values. The training-efficiency claim is under-supported—Figure 3 only shows SIL versus no SIL, not wall-clock comparisons to TreeREINFORCE or GCNN. Error bars are per-instance rather than across seeds, so \"consistent improvement\" is a bit overstated.\n\nNet: this is a solid paper that deserves peer review. It is not revolutionary, but it addresses a real bottleneck and the experiments are careful enough to engage with. A serious referee should ask for code, a reward ablation, and a direct efficiency comparison. I would accept it for review and would cite it as related work if I were working in this subfield.","headline":"SORREL is a genuinely new and well-tested recipe for learning branching policies from cheap, suboptimal demonstrations, but the evidence for why it works is thinner than the claims.","tokens_in":14960,"tokens_out":1469,"would_cite":true,"duration_ms":14825,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"SORREL shows a branching policy for mixed-integer linear programs can be trained from suboptimal demonstrations and match an imitation learner trained on high-quality demonstrations.","keywords":["mixed integer linear programming","branch-and-bound","learning to branch","offline reinforcement learning","self-imitation learning","tree Markov decision process","imitation learning","neural branching"],"falsifier":"Run SORREL on a MILP family where the dual bound improves quickly but the search tree remains large, or replace the reward with the actual reduction in node count per branching step and compare policies; if the tree-size objective yields clearly better node counts, the dual-bound proxy is the load-bearing assumption.","tokens_in":13927,"feed_emoji":"🌳","tokens_out":5970,"duration_ms":43508,"temperature":0.7,"pith_summary":"Mixed-integer linear program (MILP) solvers rely on branching heuristics that are either hand-crafted or learned from high-quality demonstrations produced by near-optimal rules. High-quality demonstrations are expensive or impossible to obtain for every problem family. This paper claims that a branching policy can be trained effectively from suboptimal demonstrations by selectively imitating only the good decisions among them. It proposes SORREL, a two-stage reinforcement learning method that pretrains offline on suboptimal demonstrations and then finetunes with self-imitation learning. The reported experiments show SORREL beating imitation and reinforcement baselines that use the same weak demonstrations, and matching an imitation learner trained on full strong branching data.","feed_headline":"SORREL learns MILP branching from weak demos and matches expert IL","feed_subtitle":"Learning to branch no longer needs near-optimal heuristics; weak demonstrations plus self-imitation suffice.","key_machinery":"The central object is a tree Markov decision process for branch-and-bound variable selection: a state is a sub-MILP, an action picks a variable to branch on, and the action produces two child states whose rewards are the local dual-bound improvements. The return from a state is defined as the expected discounted reward over a random walk down the tree, and the paper proves the resulting Bellman operator is a contraction. On this MDP, SORREL trains a policy with offline reinforcement learning, regularizing the policy update toward the demonstration actions to control distributional shift, then finetunes online with Proximal Policy Optimization augmented by self-imitation learning that replays high-return trajectories kept in per-instance priority queues.","core_discovery":"SORREL establishes that the need for near-optimal branching demonstrations can be removed: a policy trained on suboptimal demonstrations, with a value filter that keeps only decisions leading to above-expected returns, performs as well as a policy trained on high-quality demonstrations. The method models branching as a tree Markov decision process in which rewards are local dual-bound improvements and returns are expectations over random walks down the tree; the associated Bellman operator is a contraction. Offline reinforcement learning with a behavior-cloning regularizer provides the pretrained starting policy, and self-imitation learning from a priority queue of the best trajectories provides the finetuning signal. On five MILP benchmarks, SORREL consistently reduces solving time and search-tree size relative to comparable neural baselines, and its offline-only variant already beats imitation learning on the same demonstrations.","pith_inferences":["The value-filtered use of suboptimal demonstrations could be transferred to other solver heuristics such as node selection and cutting-plane selection, where good demonstrations are similarly expensive.","The dual-bound reward proxy may be replaceable by direct node-count objectives or learned reward models; comparing those would isolate whether the reward choice or the selective imitation mechanism drives the gains.","The reported training-efficiency gain suggests that self-imitation acts as a conservative exploration strategy, trading asymptotic performance for stability; the paper's stated limitation of not benefiting from longer RL training time supports this reading."],"forward_implications":["MILP branching policies can be trained without near-optimal heuristics, removing the chicken-and-egg problem in data collection for new problem families.","The offline pretraining stage provides a strong starting point, so online finetuning requires far fewer solver interactions than prior RL branching methods.","On problem families with uninformative linear relaxations, SORREL can outperform imitation learning trained on full strong branching data.","Trained on small instances, SORREL generalizes to larger instances, cutting search-tree size and solving time on transfer benchmarks."],"supporting_citations":[{"why":"Introduces the tree MDP formulation for variable selection that SORREL generalizes.","marker":"Etheve et al. (2020)"},{"why":"Proposes the tree-MDP modeling of branching and the TreeREINFORCE baseline that SORREL compares against.","marker":"Scavuzzo et al. (2022)"},{"why":"Supplies the behavior-cloning regularization technique that stabilizes the offline RL policy update.","marker":"Fujimoto and Gu (2021)"},{"why":"Provides the self-imitation learning objective used in the finetuning stage.","marker":"Oh et al. (2018)"},{"why":"Establishes the bipartite-graph GNN architecture and the benchmark instance generators used throughout.","marker":"Gasse et al. (2019)"},{"why":"Provides the PPO algorithm used for the online finetuning updates.","marker":"Schulman et al. (2017)"},{"why":"Defines full strong branching, the high-quality demonstration source that SORREL aims to match.","marker":"Achterberg, Koch, and Martin (2005a)"}],"fun_headline_variants":["SORREL: Weak demos, expert-level branching","Suboptimal demos suffice: SORREL learns to branch","SORREL matches expert IL with only suboptimal demos","Branching without expert demos: SORREL makes it work"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that pushing the lower bound of relaxed subproblems upward quickly, as measured along a random walk of the search tree, will make the solver explore fewer nodes overall.","fun_headline_variants_meta":{"raw":{"variants":["SORREL: Weak demos, expert-level branching","Suboptimal demos suffice: SORREL learns to branch","SORREL matches expert IL with only suboptimal demos","Branching without expert demos: SORREL makes it work"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001079,"raw_usage":{"total_tokens":4481,"prompt_tokens":878,"completion_tokens":3603,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":494,"completion_tokens_details":{"reasoning_tokens":3532}},"tokens_in":494,"tokens_out":3603,"duration_ms":21669,"temperature":1.0,"reasoning_tokens":3532,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:20:05.248411+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SORREL on a MILP family where the dual bound improves quickly but the search tree remains large, or replace the reward with the actual reduction in node count per branching step and compare policies; if the tree-size objective yields clearly better node counts, the dual-bound proxy is the load-bearing assumption.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the tree MDP formulation for variable selection that SORREL generalizes."},{"cited_title":"Y.; Ch \\'e telat, D.; Gasse, M.; Lodi, A.; Yorke-Smith, N.; and Aardal, K","cited_arxiv_id":null,"evidence_quote":"Proposes the tree-MDP modeling of branching and the TreeREINFORCE baseline that SORREL compares against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the behavior-cloning regularization technique that stabilizes the offline RL policy update."}],"review_version":1}