acceptodds
Under review as a conference paper at ICLR 2027

LAMF-MCTS: Learning-Augmented Multi-Fidelity Monte Carlo Tree Search for Expensive Combinatorial Black-Box Optimization

Abstract

Expensive stochastic simulations limit how broadly an optimizer can explore a combinatorial design space. We introduce LAMF-MCTS, a learning-augmented multi-fidelity Monte Carlo tree search framework that coordinates search and simulation effort. The key idea is to exploit information available before a simulation finishes: a partial trajectory can inform both a design's eventual performance and the direction of subsequent search. The framework combines observed partial returns with learned predictions of the remaining return, penalizing uncertain estimates. Repeatedly selected designs are progressively promoted to higher fidelities, while side information from the same trajectories provides action priors that guide tree expansion. Experiments on an application-derived combinatorial black-box optimization problem show that LAMF-MCTS attains the highest final full-fidelity objective among six application-specific planning baselines and, under the same simulator-call budget as full-fidelity MCTS, reduces cumulative simulation cost by 35.2% while attaining a higher running-best objective.

Primary area:
optimization
Keywords:
Combinatorial black-box optimization, Multi-fidelity optimization, Monte Carlo tree search, Simulation-based optimization, Learning-augmented optimization

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_ZM4QOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper is based around black-box, combinatorial optimization where evaluations of the combinatorial function being optimized are a realizations of a stochastic sequence. However, simulating these stochastic sequences to completion in order to obtain outcome observations can be costly. This paper proposes a method to balance the extent to which the sequences are generated to trade-off between costs and performance. The paper validates its approach in simulated automated electric taxi charging domain to provide evidence of its capabilities.

Critical strengths
  1. I found the problem statement well motivated. I also consider the problem of interest to the search/planning community.
  2. The approach seems intuitive and sound.
Critical weaknesses

The main issue I view in the paper is the limited evaluation. The approach introduced is only evaluated in a single domain. All results demonstrate the performance of their algorithm in only this domain. Furthermore, the paper lacks details on the baselines they compare against. I cannot validate the fairness of the comparisons --- LAMF-MCTS receives a simulation budget of 10,000 samples. However, there is no mention of the compute costs of the baseline algorithms. Do they get more or less resources compared to LAMF-MCTS?

Additionally, the description of "side-information" seems context specific. Is the side-information useful in other domains? How do you compute PP for PUCT without side information?

The paper does not describe how the hyperparameters were set? There is a table of these values but no description on how the values were chosen.

I also am curious about the choice to report the running-best values. That seems like it with high variance outcomes, we'd have a skewed result.

Questions for authors
  1. The paper states that λ\lambda controls a trade-off between performance and cost. But the way ff is computed in Equation 1, does it do so? Depending on the scales of RR and CC, λ\lambda may or may not have any noticeable effect on evaluations.
Reviewer_PDS1OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary
  • This paper proposes LAMF-MCTS to find solutions at low computational cost for combinatorial design problems with expensive simulations, focusing on electric taxi charging infrastructure placement.
  • The method uses MCTS to explore candidate designs. At the beginnig, it runs only a short simulation and scores each candidate as the return accumulated so far plus the return predicted by a pretrained critic. As the same candidate is selected again, it increases the fidelity by running longer simulations.
  • It achieved a higher final objective (expected operating revenue − infrastructure cost) than other charging infrastructure design baselines. Under same simulation-call budget, it achieved a search-time objective comparable to that of full-fidelity MCTS, which runs each simulation to completion, while using fewer total simulation steps.
Critical strengths
  1. Practical problem formulation. Using truncation of a sequential simulator to obtain multiple fidelity levels, without requiring a separate low-fidelity model, is a clean formulation that is directly applicable to simulation-based design problems.
  2. Clear and intuitive method. Using MCTS to explore sequential design modifications is natural and overall search procedure is intuitive.
Critical weaknesses
  1. Novelty and evaluation setting. The novelty beyond combining existing techniques is unclear. Based on the current presentation and experiments, I think the work appears closer to an integration of existing methods tailored to EV charging infrastructure design than a new general-purpose optimization method.

  2. Insufficient evidence for greater efficiency than full-fidelity MCTS.

    • Under fixed number of simulation calls, lower simulation cost is expected for LAMF-MCTS because it truncates some simulations. However, Figure4 shows that full-fidelity MCTS achieves a higher objective early in the search. In particular, it reaches a value close to its final objective after approximately 1000 calls, only 10% of the allotted 10000 calls. Thus, stopping full-fidelity MCTS early might achieve a comparable objective at lower cost, without requiring a continuation critic.
    • I think one possible explanation for the early performance gap is that, at low fidelity, the critic must predict returns over a longer remaining horizon, so the evaluations might be less accurate. If this is indeed the cause, it could indicate a weakness in the strategy of using shorter simulations early in the search.
    • The number of independent search runs underlying Figure 4 and the variability across runs are also unclear.

Also most of the baselines optimize their own formulations, making it difficult to distinguish whether performance differences in the simulator arise from the search algorithms or from mismatches between their formulations and the evaluation simulator. Although a BO baseline such as ACPM is included, comparisons with multi-fidelity BO under the same simulator objective and computational budget are lacking.

Questions for authors
  1. How many independent search runs and random seeds were used to produce Figure 4?
  2. Could you plot Figure 4 against cumulative simulation cost rather than the number of simulator calls, and compare the objectives achieved at equal cost? Specifically, could you compare the costs and objectives of full-fidelity MCTS stopped at approximately 1,000 calls with those of LAMF-MCTS at 1,000 and 10,000 calls?
  3. Could you investigate whether the weaker early-search performance is related to the critic having to predict returns over a longer remaining horizon at low fidelity?
  4. Could you compare against multi-fidelity BO or other combinatorial black-box optimizers under the same simulation cost budget?
Reviewer_oN4UOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies combinatorial black-box optimization where evaluating a candidate solution requires an expensive stochastic simulation. The authors propose LAMF-MCTS, which integrates four mechanisms: (1) multi-fidelity evaluation; (2) learning-augmented evaluation; (3) progressive fidelity allocation; (4) Guided MCTS. The method is evaluated on electric taxi charging-infrastructure planning. Compared with full-fidelity MCTS, it achieves a slightly higher running-best objective (51.3 versus 50.2) while reducing cumulative simulated evaluation cost by 35.2% under the same 10000-call budget.

Guided MCTS:

Critical strengths

Expensive stochastic simulation is a major computational bottleneck in combinatorial optimization. The idea of extracting useful information from partially completed simulations is well motivated and potentially valuable.

The paper incorporates multiple interesting techniques, which improve computation efficiency.

The paper includes experiments removing side-information guidance and action factorization. These help establish that the components play complementary roles.

Critical weaknesses

This paper has very limited methdological novelty. Most components of the framework are established techniques.

There is no theoretical guarantee for the proposed optimization.

The experiments are thin, and lack of statistical analysis.

Questions for authors

See weakness.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.