Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search
The combination of Monte-Carlo Tree Search (MCTS) and deep reinforcement learning is state-of-the-art in two-player perfect-information games. In this paper, we describe a search algorithm that uses a variant of MCTS which we enhanced by 1) a novel action value normalization mechanism for games with potentially unbounded rewards (which is the case in many optimization problems), 2) defining a virtual loss function that enables effective search parallelization, and 3) a policy network, trained by generations of self-play, to guide the search. We gauge the effectiveness of our method in "SameGame"---a popular single-player test domain. Our experimental results indicate that our method outperforms baseline algorithms on several board sizes. Additionally, it is competitive with state-of-the-art search algorithms on a public set of positions.
Code (0)
등록된 구현이 없습니다.
Tasks
Deep Reinforcement LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games
Multi-Agent Reinforcement Learning (MARL) -- where multiple agents learn to interact in a shared dynamic environment -- permeates across a wide range of critical applications. While there has been substantial progress on…
Multi-agent Reinforcement LearningA Single Online Agent Can Efficiently Learn Mean Field Games
Mean field games (MFGs) are a promising framework for modeling the behavior of large-population systems. However, solving MFGs can be challenging due to the coupling of forward population evolution and backward agent dyn…
Speeding up Policy Simulation in Supply Chain RL
Simulating a single trajectory of a dynamical system under some state-dependent policy is a core bottleneck in policy optimization (PO) algorithms. The many inherently serial policy evaluations that must be performed in …
GPUSAPO: Single-Rollout Autoregressive Policy Optimization for Agentic Reinforcement Learning
Agentic reinforcement learning (RL) has become a critical stage in the post-training of large language models. Existing critic-free, group-relative methods estimate policy advantages from multiple rollouts, avoiding the …
Reinforcement LearningBatch Reinforcement Learning Through Continuation Method
Many real-world applications of reinforcement learning (RL) require the agent to learn from a fixed set of trajectories, without collecting new interactions. Policy optimization under this setting is extremely challengi…
global-optimizationreinforcement-learningReinforcement LearningReinforcement Learning (RL)