Monte Carlo Tree Search (MCTS) algorithms perform simulation-based search to improve policies online. During search, the simulation policy is adapted to explore the most promising lines of play. MCTS has been used by state-of-the-art programs for many problems, however a disadvantage to MCTS is that it estimates the va…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “policy tree search”
Paper shows MCTS approximates policy optimization, proposing an improved variant.
problem Improving AI performance through better MCTS algorithms.
method Shows MCTS approximates policy optimization problem, proposes a new algorithm.
result Proposed algorithm reliably outperforms original AlphaZero in multiple domains.
This paper improves self-play learning in games by manipulating experience distributions.
problem Improving self-play learning in games through better experience sampling.
method Three approaches: weighted sampling, Prioritized Experience Replay, and diversifying trajectories.
result Major improvements in early training performance in some games, minor improvements overall.
Branch and Bound (B&B) is the exact tree search method typically used to solve Mixed-Integer Linear Programming problems (MILPs). Learning branching policies for MILP has become an active research area, with most works proposing to imitate the strong branching rule and specialize it to distinct classes of problems. We …
Transformer learns to search through reinforcement learning, mimicking DFS.
problem Understanding how transformers learn search capabilities in RL.
method Two-head transformer, depth-wise curriculum, discounted returns.
result Transformer policy generalizes depth and prioritizes high-probability branches.
Paper uses CMAB to improve NAS efficiency and accuracy.
problem Improving efficiency and accuracy of NAS for DNNs.
method Formulated NAS as CMAB, used Nested Monte-Carlo Search.
result Discovered cell structure achieves comparable accuracy to state-of-the-art, 20x faster.
Gradient-based methods are often used for policy optimization in deep reinforcement learning, despite being vulnerable to local optima and saddle points. Although gradient-free methods (e.g., genetic algorithms or evolution strategies) help mitigate these issues, poor initialization and local optima are still concerns …
Finite-horizon lookahead policies are abundantly used in Reinforcement Learning and demonstrate impressive empirical success. Usually, the lookahead policies are implemented with specific planning methods such as Monte Carlo Tree Search (e.g. in AlphaZero). Referring to the planning problem as tree search, a reasonable…
Monte Carlo Tree Search improves financial derivative hedging efficiency.
problem Optimizing pricing and hedging of derivative contracts in incomplete markets.
method Integrates tree search techniques with Reinforcement Learning for optimal control problems.
result Monte Carlo Tree Search outperforms -learning in sample efficiency and learning speed.
Deep imagination optimizes decision-making in large trees with limited resources.
problem Optimal planning in large decision trees with limited resources and time.
method Analytical solutions and numerical analysis of sampling capacity allocation.
result Optimal policy is to allocate few samples per level for deep exploration, favoring depth over breadth.
AlphaCFG discovers alpha factors using grammar-guided search.
problem Discovering formulaic alpha factors in finance.
method AlphaCFG uses a grammar-based framework to define and discover alpha factors with syntactic and semantic constraints.
result AlphaCFG outperforms state-of-the-art methods in trading profitability and efficiency.
Monte-Carlo Tree Search (MCTS) methods are drawing great interest after yielding breakthrough results in computer Go. This paper proposes a Bayesian approach to MCTS that is inspired by distributionfree approaches such as UCT [13], yet significantly differs in important respects. The Bayesian framework allows potential…
Improves RL planning by proposing sub-goals hierarchically.
problem Sequential planning assumption in RL.
method Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS).
result Improves navigation and control tasks.
We study the problem of learning a good search policy for combinatorial search spaces. We propose retrospective imitation learning, which, after initial training by an expert, improves itself by learning from \textit{retrospective inspections} of its own roll-outs. That is, when the policy eventually reaches a feasible…
InfoTree improves reinforcement learning by optimizing tool use with a greedy submodular approach.
problem Maximizing information from tool use in reinforcement learning with limited resources.
method Formalizes Rollout Informativeness, recasts state selection as submodular maximization, and uses UUCB and ABA.
result InfoTree outperforms existing methods across various benchmarks, improving performance by 18.2% on average.
CAPITAL algorithm identifies optimal patient subgroups for better treatment.
problem Identify maximum number of patients benefiting from better treatment.
method Constrained Policy Tree Search (CAPITAL) algorithm to find optimal subgroup selection rule (SSR).
result Maximizes the number of patients with enhanced treatment effects.
DR-MCTS improves decision quality and sample efficiency in complex environments.
problem Improving decision quality and sample efficiency in complex environments.
method Integrates Doubly Robust off-policy estimation into Monte Carlo Tree Search (MCTS).
result DR-MCTS achieves superior performance in Tic-Tac-Toe and VirtualHome tasks.
Bayesian model-based reinforcement learning is a formally elegant approach to learning optimal behaviour under model uncertainty, trading off exploration and exploitation in an ideal way. Unfortunately, finding the resulting Bayes-optimal policies is notoriously taxing, since the search space becomes enormous. In this …
In recent years, state-of-the-art game-playing agents often involve policies that are trained in self-playing processes where Monte Carlo tree search (MCTS) algorithms and trained policies iteratively improve each other. The strongest results have been obtained when policies are trained to mimic the search behaviour of…
While many recent advances in deep reinforcement learning (RL) rely on model-free methods, model-based approaches remain an alluring prospect for their potential to exploit unsupervised data to learn environment model. In this work, we provide an extensive study on the design of deep generative models for RL environmen…
A new algorithm, Regular Tree Search, tackles non-convex simulation optimization problems.
problem Non-convex objective functions in simulation optimization.
method Integrates adaptive sampling with recursive partitioning of the search space.
result Proves global convergence and reliably identifies the global optimum.
Multiple-step lookahead policies have demonstrated high empirical competence in Reinforcement Learning, via the use of Monte Carlo Tree Search or Model Predictive Control. In a recent work \cite{efroni2018beyond}, multiple-step greedy policies and their use in vanilla Policy Iteration algorithms were proposed and analy…
In many settings, a decision-maker wishes to learn a rule, or policy, that maps from observable characteristics of an individual to an action. Examples include selecting offers, prices, advertisements, or emails to send to consumers, as well as the problem of determining which medication to prescribe to a patient. Whil…
Unified framework for policy improvement in RL with benefits in data efficiency and computation.
problem Improving data efficiency and computation in reinforcement learning for continuous control.
method Local, regularized policy improvement with tree search for continuous action spaces.
result Improves data efficiency and reduces wall-clock time in high-dimensional domains.
Protein Thoughts interprets protein interactions with clear reasoning, improving prediction accuracy.
problem Lack of mechanistic justification in protein-protein interaction predictions.
method Interpretable search problem reformulation, hypothesis-guided entropy-regularized Tree-of-Thoughts search, embedding-space flow matching.
result Improves mean best-binder rank from 47.7 to 11.2 on SHS148k benchmark.
RiskMiner discovers formulaic alphas using MCTS for better performance.
problem Mining formulaic alphas without considering structural information and alpha correlations.
method Formulates alpha mining as an MDP and solves it with a risk-seeking MCTS.
result Our method outperforms state-of-the-art benchmarks and achieves the most profitable results.
Optimizes tree models for better beam search performance.
problem Beam search causes retrieval performance deterioration in tree models.
method Develops Bayes optimality and calibration under beam search, proposes a novel algorithm for optimal tree model learning.
result Eliminates the training-testing discrepancy in tree models.
In this work, we consider the popular tree-based search strategy within the framework of reinforcement learning, the Monte Carlo Tree Search (MCTS), in the context of infinite-horizon discounted cost Markov Decision Process (MDP). While MCTS is believed to provide an approximate value function for a given state with en…
Recently, a novel class of Approximate Policy Iteration (API) algorithms have demonstrated impressive practical performance (e.g., ExIt from [2], AlphaGo-Zero from [27]). This new family of algorithms maintains, and alternately optimizes, two policies: a fast, reactive policy (e.g., a deep neural network) deployed at t…
We present an extension of Monte Carlo Tree Search (MCTS) that strongly increases its efficiency for trees with asymmetry and/or loops. Asymmetric termination of search trees introduces a type of uncertainty for which the standard upper confidence bound (UCB) formula does not account. Our first algorithm (MCTS-T), whic…
Statistical model checking for PCTL on MDPs using reinforcement learning.
problem Model checking PCTL specifications on MDPs with statistical methods.
method Reinforcement learning for policy search, statistical model checking with UCB-based Q-learning.
result Provably guaranteed statistical model checking method for PCTL specifications on MDPs.
While deep reinforcement learning has successfully solved many challenging control tasks, its real-world applicability has been limited by the inability to ensure the safety of learned policies. We propose an approach to verifiable reinforcement learning by training decision tree policies, which can represent complex p…
Retro* uses neural networks to efficiently find high-quality synthetic routes in organic chemistry.
problem Finding efficient synthetic routes in organic chemistry is challenging due to the vast search space.
method Retro* is a neural-based A*-like algorithm that learns a neural search bias to guide efficient best-first search.
result Retro* outperforms existing methods in both success rate and solution quality while being more efficient.
We consider the classical sparse regression problem of recovering a sparse signal given a measurement vector . We propose a tree search algorithm driven by the deep neural network for sparse regression (TSN). TSN improves the signal reconstruction performance of the deep neural network designed for sp…
Monte Carlo Tree Search (MCTS) algorithms have achieved great success on many challenging benchmarks (e.g., Computer Go). However, they generally require a large number of rollouts, making their applications costly. Furthermore, it is also extremely challenging to parallelize MCTS due to its inherent sequential nature:…
Automates optimizer design for diverse tasks efficiently.
problem Scalability, generability, and sample efficiency in optimizer search.
method Re-arranged optimizer space into a super-tree, applying tree traversal methods.
result Discover optimizers with only 128 evaluations, surpassing human-designed and prior methods.
We consider the problem of finding Nash equilibrium for two-player turn-based zero-sum games. Inspired by the AlphaGo Zero (AGZ) algorithm, we develop a Reinforcement Learning based approach. Specifically, we propose Explore-Improve-Supervise (EIS) method that combines "exploration", "policy improvement"' and "supervis…
Optimal decision trees learned via dynamic programming and search.
problem Finding the best classification trees that are both accurate and compact.
method Dynamic programming and search techniques.
result Our algorithm learns optimal classification trees significantly faster and scales better than existing methods.
Bayesian approach for policy search in stochastic domains.
problem Policy search in stochastic domains.
method Nested probabilistic programs, Lightweight Metropolis-Hastings (LMH) adaptation.
result Similar quality policies learned with simpler algorithm.
SMAC method optimizes tree-boosting hyperparameters best.
problem Optimizing hyperparameters for tree-boosting to improve model accuracy.
method Compared and evaluated various hyperparameter optimization methods.
result SMAC method outperforms other methods for hyperparameter tuning.
A hybrid model for Bayesian optimization handles mixed variables using MCTS for categorical and GP for continuous.
problem Optimizing functions with mixed variable types (continuous, integer, categorical).
method Merges MCTS for categorical and GP for continuous variables, integrates UCTS search strategy, and dynamically selects kernels.
result Hybrid models outperform traditional methods in Bayesian optimization.
GFN-SR uses deep learning to generate diverse mathematical expressions.
problem Symbolic regression to find best mathematical expressions.
method Traversing a DAG to generate expression trees sequentially with GFlowNet.
result GFN-SR outperforms other SR algorithms in noisy data.
Planning problems are among the most important and well-studied problems in artificial intelligence. They are most typically solved by tree search algorithms that simulate ahead into the future, evaluate future states, and back-up those evaluations to the root of a search tree. Among these algorithms, Monte-Carlo tree …
A new algorithm improves sample complexity for thresholding in Monte Carlo Tree Search.
problem Determining if the root node value of a tree is at least a given threshold.
method Developed a δ-correct sequential sampling algorithm based on the Track-and-Stop strategy.
result Ratio-based modification of D-Tracking strategy reduces sample complexity and computational cost.
Trust-region methods have yielded state-of-the-art results in policy search. A common approach is to use KL-divergence to bound the region of trust resulting in a natural gradient policy update. We show that the natural gradient and trust region optimization are equivalent if we use the natural parameterization of a st…
DTS improves inference-time alignment of diffusion models with less compute.
problem Inference-time alignment of diffusion models suffers from inaccurate value estimation and inefficient reuse of past computations.
method Diffusion Tree Sampling (DTS) uses a tree-based approach to propagate terminal rewards and iteratively refine value estimates.
result DTS produces asymptotically exact samples and matches the FID of best-performing baselines with up to 10x less compute.
Combines MCTS and neural networks for efficient multi-period financial planning.
problem Solving multi-period financial planning models with high transaction costs and regime switching.
method Integrates Monte Carlo Tree Search with deep neural networks, using UTC and lookup search.
result Combined approach outperforms individual methods, solving complex models.
Predict accuracy of neural architectures using non-neural models.
problem Improving efficiency and effectiveness of neural architecture search.
method Used gradient boosting decision tree (GBDT) for accuracy prediction and pruned the search space based on features learned from GBDT.
result GBDT-based predictor achieves comparable or better accuracy than neural network-based predictors and is 22x more sample efficient on NASBench-101.