Learning a Prior for Monte Carlo Search by Replaying Solutions to Combinatorial Problems

• URL: http://arxiv.org/abs/2401.10431v1
• Date: Fri, 19 Jan 2024 00:22:31 GMT
• Title: Learning a Prior for Monte Carlo Search by Replaying Solutions to Combinatorial Problems
• Authors: Tristan Cazenave
• Abstract summary: We propose a method to automatically compute a prior. It is a simple and general method that incurs no computational cost at playout time. The method is applied to three difficult problems: Latin Square Completion, Kakuro, and Inverse RNA Folding.
• Score: 4.561007128508218
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Monte Carlo Search gives excellent results in multiple difficult combinatorial problems. Using a prior to perform non uniform playouts during the search improves a lot the results compared to uniform playouts. Handmade heuristics tailored to the combinatorial problem are often used as priors. We propose a method to automatically compute a prior. It uses statistics on solved problems. It is a simple and general method that incurs no computational cost at playout time and that brings large performance gains. The method is applied to three difficult combinatorial problems: Latin Square Completion, Kakuro, and Inverse RNA Folding.

Related papers

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• AlphaMapleSAT: An MCTS-based Cube-and-Conquer SAT Solver for Hard Combinatorial Problems [13.450216199781671]
  This paper introduces AlphaMapleSAT, a novel Monte Carlo Tree Search (MCTS) based Cube-and-Conquer (CnC) SAT solving method. By contrast, our key innovation is a deductively-driven MCTS-based lookahead cubing technique, that performs a deeper search to find effective cubes.
  arXiv  Detail & Related papers  (2024-01-24T19:37:10Z)
• Solving a Class of Non-Convex Minimax Optimization in Federated Learning [84.98927714326908]
  The minimax problems arise throughout machine learning applications, ranging from machine learning training to large-scale learning. We propose a class of algorithms for non minimax problems (emphi) that reduce complexity to $varepsilon-6)$. We prove that FedSGDA-M has the best sample complexity of $O(kappa2-3)$ and the best-known communication of $O(kappa2-3)$.
  arXiv  Detail & Related papers  (2023-10-05T15:48:41Z)
• An AlphaZero-Inspired Approach to Solving Search Problems [63.24965775030674]
  We adapt the methods and techniques used in AlphaZero for solving search problems. We describe possible representations in terms of easy-instance solvers and self-reductions. We also describe a version of Monte Carlo tree search adapted for search problems.
  arXiv  Detail & Related papers  (2022-07-02T23:39:45Z)
• Learning Best Combination for Efficient N:M Sparsity [75.34103761423803]
  N:M learning can be naturally characterized as a problem which searches for the best combination within a finite collection. We show that our learning best combination (LBC) performs consistently better than off-the-shelf N:M sparsity methods across various networks.
  arXiv  Detail & Related papers  (2022-06-14T07:51:31Z)
• The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights [59.93939636422896]
  The ML4CO aims at improving state-of-the-art optimization solvers by replacing key components. The competition featured three challenging tasks: finding the best feasible solution, producing the tightest optimality certificate, and giving an appropriate routing configuration.
  arXiv  Detail & Related papers  (2022-03-04T17:06:00Z)
• SOLO: Search Online, Learn Offline for Combinatorial Optimization Problems [4.777801093677586]
  We study problems with real world applications such as machine scheduling, routing, and assignment. We propose a method that combines Reinforcement Learning (RL) and planning. This method can equally be applied to both the offline, as well as online, variants of the problem, in which the problem components are not known in advance, but rather arrive during the decision-making process.
  arXiv  Detail & Related papers  (2021-04-04T17:12:24Z)
• Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems [21.411742165753456]
  ZTop is a simple yet effective model selection and ensemble mechanism for learning to solve problems. We show how ZTopping, using a ZTop ensemble strategy with a given deep learning approach, can significantly improve the performance of the current state-of-the-art deep learning approaches.
  arXiv  Detail & Related papers  (2021-02-05T05:23:26Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  Combinatorial bandits generalize multi-armed bandits, where the agent chooses sets of arms and observes a noisy reward for each arm contained in the chosen set. We focus on the pure-exploration problem of identifying the best arm with fixed confidence, as well as a more general setting, where the structure of the answer set differs from the one of the action set. Based on a projection-free online learning algorithm for finite polytopes, it is the first computationally efficient algorithm which is convexally optimal and has competitive empirical performance.
  arXiv  Detail & Related papers  (2021-01-21T10:35:09Z)
• Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems [0.6882042556551609]
  This approach makes use of a algorithm to explore the search space tree of a problem instance. The algorithm is based on Monte Carlo tree search, a popular algorithm in game playing that is used to explore game trees.
  arXiv  Detail & Related papers  (2020-10-22T08:33:58Z)
• Curriculum learning for multilevel budgeted combinatorial problems [7.804994311050265]
  Multilevel optimization problems are their generalization, encompassing situations with multiple players taking decisions sequentially. We devise a value-based method to learn to solve multilevel budgeted problems involving two players in a zero-sum game over a graph. Our framework is based on a simple curriculum: if an agent knows how to estimate the value of instances with budgets up to $B$, then solving instances with budget $B+1$ can be done in time regardless of the direction of every possible afterstate.
  arXiv  Detail & Related papers  (2020-07-07T01:09:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.