An Analysis on the Effects of Evolving the Monte Carlo Tree Search Upper Confidence for Trees Selection Policy on Unimodal, Multimodal and Deceptive Landscapes

• URL: http://arxiv.org/abs/2311.13609v1
• Date: Tue, 21 Nov 2023 20:40:34 GMT
• Title: An Analysis on the Effects of Evolving the Monte Carlo Tree Search Upper Confidence for Trees Selection Policy on Unimodal, Multimodal and Deceptive Landscapes
• Authors: Edgar Galvan and Fred Valdez Ameneyro
• Abstract summary: The Monte Carlo Tree Search (MCTS) is a best-first sampling method employed in the search for optimal decisions. A selection policy that works particularly well in MCTS is the Upper Confidence Bounds for Trees, referred to as UCT. This work explores the use of five functions of different natures, ranging from unimodal to multimodal and deceptive functions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Monte Carlo Tree Search (MCTS) is a best-first sampling method employed in the search for optimal decisions. The effectiveness of MCTS relies on the construction of its statistical tree, with the selection policy playing a crucial role. A selection policy that works particularly well in MCTS is the Upper Confidence Bounds for Trees, referred to as UCT. The research community has also put forth more sophisticated bounds aimed at enhancing MCTS performance on specific problem domains. Thus, while MCTS UCT generally performs well, there may be variants that outperform it. This has led to various efforts to evolve selection policies for use in MCTS. While all of these previous works are inspiring, none have undertaken an in-depth analysis to shed light on the circumstances in which an evolved alternative to MCTS UCT might prove advantageous. Most of these studies have focused on a single type of problem. In sharp contrast, this work explores the use of five functions of different natures, ranging from unimodal to multimodal and deceptive functions. We illustrate how the evolution of MCTS UCT can yield benefits in multimodal and deceptive scenarios, whereas MCTS UCT is robust in all of the functions used in this work.

Related papers

• Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond [58.39457881271146]
  We introduce a novel framework of multi-armed bandits (CMAB) with multivariant and probabilistically triggering arms (CMAB-MT) Compared with existing CMAB works, CMAB-MT not only enhances the modeling power but also allows improved results by leveraging distinct statistical properties for multivariant random variables. Our framework can include many important problems as applications, such as episodic reinforcement learning (RL) and probabilistic maximum coverage for goods distribution.
  arXiv  Detail & Related papers  (2024-06-03T14:48:53Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours. We focus on the case of linear utility functions parameterised by weight vectors w. We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• Towards Understanding the Effects of Evolving the MCTS UCT Selection Policy [0.0]
  Upper Confidence Bounds for Trees (UCT) is widely used in Monte Carlo Tree Search (MCTS) We show how the evolution of the UCT might be beneficial in multimodal and deceptive scenarios.
  arXiv  Detail & Related papers  (2023-02-07T09:50:55Z)
• Multimodal Chain-of-Thought Reasoning in Language Models [94.70184390935661]
  We propose Multimodal-CoT that incorporates language (text) and vision (images) modalities into a two-stage framework. Experimental results on ScienceQA and A-OKVQA benchmark datasets show the effectiveness of our proposed approach.
  arXiv  Detail & Related papers  (2023-02-02T07:51:19Z)
• Continuous Monte Carlo Graph Search [61.11769232283621]
  Continuous Monte Carlo Graph Search ( CMCGS) is an extension of Monte Carlo Tree Search (MCTS) to online planning. CMCGS takes advantage of the insight that, during planning, sharing the same action policy between several states can yield high performance. It can be scaled up through parallelization, and it outperforms the Cross-Entropy Method (CEM) in continuous control with learned dynamics models.
  arXiv  Detail & Related papers  (2022-10-04T07:34:06Z)
• Evolving the MCTS Upper Confidence Bounds for Trees Using a Semantic-inspired Evolutionary Algorithm in the Game of Carcassonne [0.0]
  We propose a Semantic-inspired Evolutionary Algorithm in Monte Carlo Tree Search (MCTS) We use Evolutionary Algorithms (EAs) to evolve mathematical expressions with the goal to substitute the Upper Confidence Bounds for Trees formula. We show how SIEA-MCTS is able to successfully evolve mathematical expressions that yield better or competitive results compared to UCT without the need of tuning these evolved expressions.
  arXiv  Detail & Related papers  (2022-08-29T13:31:06Z)
• On the Evolution of the MCTS Upper Confidence Bounds for Trees by Means of Evolutionary Algorithms in the Game of Carcassonne [0.0]
  Monte Carlo Tree Search (MCTS) is a sampling best-first method to search for optimal decisions. We use Evolutionary Algorithms (EAs) to evolve mathematical expressions with the goal to substitute the Upper Confidence Bounds for Trees (UCT) mathematical expression. We show how the ES-MCTS controller, is able to outperform all these 10 intelligent controllers, including robust UCT controllers.
  arXiv  Detail & Related papers  (2021-12-17T18:06:21Z)
• Decomposed Soft Actor-Critic Method for Cooperative Multi-Agent Reinforcement Learning [10.64928897082273]
  Experimental results demonstrate that mSAC significantly outperforms policy-based approach COMA. In addition, mSAC achieves pretty good results on large action space tasks, such as 2c_vs_64zg and MMM2.
  arXiv  Detail & Related papers  (2021-04-14T07:02:40Z)
• Monte Carlo Tree Search: A Review of Recent Modifications and Applications [0.17205106391379024]
  Monte Carlo Tree Search (MCTS) is a powerful approach to designing game-playing bots or solving sequential decision problems. The method relies on intelligent tree search that balances exploration and exploitation. The method has become a state-of-the-art technique for games, however, in more complex games.
  arXiv  Detail & Related papers  (2021-03-08T17:44:15Z)
• The Surprising Effectiveness of MAPPO in Cooperative, Multi-Agent Games [67.47961797770249]
  Multi-Agent PPO (MAPPO) is a multi-agent PPO variant which adopts a centralized value function. We show that MAPPO achieves performance comparable to the state-of-the-art in three popular multi-agent testbeds.
  arXiv  Detail & Related papers  (2021-03-02T18:59:56Z)
• Monte-Carlo Tree Search as Regularized Policy Optimization [47.541849128047865]
  We show that AlphaZero's search algorithms are an approximation to the solution of a specific regularized policy optimization problem. We propose a variant of AlphaZero which uses the exact solution to this policy optimization problem, and show experimentally that it reliably outperforms the original algorithm in multiple domains.
  arXiv  Detail & Related papers  (2020-07-24T13:01:34Z)

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.