arXiv:2006.08785

On Effective Parallelization of Monte Carlo Tree Search

Anji Liu, Yitao Liang, Ji Liu, Guy Van Den Broeck, Jianshu Chen

제출 2020-06-15

원문 초록

Despite its groundbreaking success in Go and computer games, Monte Carlo Tree Search (MCTS) is computationally expensive as it requires a substantial number of rollouts to construct the search tree, which calls for effective parallelization. However, how to design effective parallel MCTS algorithms has not been systematically studied and remains poorly understood. In this paper, we seek to lay its first theoretical foundation, by examining the potential performance loss caused by parallelization when achieving a desired speedup. In particular, we discover the necessary conditions of achieving a desirable parallelization performance, and highlight two of their practical benefits. First, by examining whether existing parallel MCTS algorithms satisfy these conditions, we identify key design principles that should be inherited by future algorithms, for example tracking the unobserved samples (used in WU-UCT (Liu et al., 2020)). We theoretically establish this essential design facilitates $\mathcal{O} ( \ln n + M / \sqrt{\ln n} )$ cumulative regret when the maximum tree depth is 2, where $n$ is the number of rollouts and $M$ is the number of workers. A regret of this form is highly desirable, as compared to $\mathcal{O} ( \ln n )$ regret incurred by a sequential counterpart, its excess part approaches zero as $n$ increases. Second, and more importantly, we demonstrate how the proposed necessary conditions can be adopted to design more effective parallel MCTS algorithms. To illustrate this, we propose a new parallel MCTS algorithm, called BU-UCT, by following our theoretical guidelines. The newly proposed algorithm, albeit preliminary, out-performs four competitive baselines on 11 out of 15 Atari games. We hope our theoretical results could inspire future work of more effective parallel MCTS.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2410.14606v3cs.LG공통 태그 Atari Games공식 코드 · Papers with Code

스트리밍 심층 강화학습이 마침내 작동하다

Streaming Deep Reinforcement Learning Finally Works

경험이 도착하는 대로 스트림 형태로 학습하는 것, 즉 스트리밍 학습(streaming learning)은 자연스러운 학습의 핵심 요소이다. 그러나 신뢰할 수 있는 스트리밍 학습은 현대 심층 강화학습(RL)에서 지속적인 난제로 남아있다. 대신 대부분의 심층 RL 알고리즘은 과거의 상호작용을 버퍼에 저장하여 오래된 경험으로부터 학습한다. 우리는 Q-러닝(Q-learning) 및 액터-크리틱(actor-critic)과 같은 고전적 스트리밍 RL을 심층 신경망과 함께 사용할 때, 그리고 PPO, SAC, DQN과 같은 배치 심층 RL을 스트리밍 설정에 맞게 적용할 때 모두 종종 학습에 실패함을 보인다. 58개의 Atari 게임과 50개의 연속 제어(continuous-control) 과제 전반에서, 우리는 광범위한 과제별 하이퍼파라미터 탐색에도 불구하고 이러한 방법들이 종합적으로 무작위 정책(random policy)에 가까운 성능을 보임을 발견하였다. 우리는 이 패턴을 스트림 장벽(stream barrier)이라 부른다. 여기서 우리는 신호 정규화(signal normalization), 표현 안정화(representation stabilization), 통제된 매개변수 업데이트(controlled parameter updates)를 결합한, 스트리밍 심층 RL 알고리즘을 위한 공유 레시피인 Stream-X를 소개한다. Stream-X를 여러 기본 스트리밍 RL 알고리즘에 적용함으로써, 우리는 스트림 장벽을 극복한 최초의 심층 RL 알고리즘군을 제공한다. 과제 전반에 걸쳐 알고리즘별로 하나의 지정된 하이퍼파라미터 구성을 사용하여, Stream-X는 종합 성능을 크게 향상시키며 이는 종종 배치 RL 알고리즘과 대등한 수준이다. 이러한 벤치마크를 넘어, 우리는 비정상성(nonstationarity)과 자원 제약(resource constraints) 하에서 Stream-X 알고리즘을 이용한 학습을 시연한다. Stream-X 알고리즘 중 하나인 Stream-AC는 시뮬레이션에서 교대로 바뀌는 바닥 마찰(floor-friction) 환경 전반에 걸쳐 성능을 반복적으로 회복하며, 평가된 PPO 및 SAC 베이스라인을 능가한다. 또한 자연스럽게 변화하는 실험실 환경에서 온보드 카메라의 고유수용성(proprioceptive) 및 시각적 특징을 사용하여 로봇의 헤딩 추적(heading tracking) 과제를 학습한다. Stream-Q는 제한된 연산 및 메모리를 가진 장치인 ESP32-S3 마이크로컨트롤러 상에서 픽셀로부터 직접 퐁(Pong) 게임을 학습한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.