Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.00614 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914819321364480 |
|---|---|
| author | Kwak, Yunhyeok Hwang, Inwoo Kim, Dooyoung Lee, Sanghack Zhang, Byoung-Tak |
| author_facet | Kwak, Yunhyeok Hwang, Inwoo Kim, Dooyoung Lee, Sanghack Zhang, Byoung-Tak |
| contents | Monte Carlo Tree Search (MCTS) has showcased its efficacy across a broad spectrum of decision-making problems. However, its performance often degrades under vast combinatorial action space, especially where an action is composed of multiple sub-actions. In this work, we propose an action abstraction based on the compositional structure between a state and sub-actions for improving the efficiency of MCTS under a factored action space. Our method learns a latent dynamics model with an auxiliary network that captures sub-actions relevant to the transition on the current state, which we call state-conditioned action abstraction. Notably, it infers such compositional relationships from high-dimensional observations without the known environment model. During the tree traversal, our method constructs the state-conditioned action abstraction for each node on-the-fly, reducing the search space by discarding the exploration of redundant sub-actions. Experimental results demonstrate the superior sample efficiency of our method compared to vanilla MuZero, which suffers from expansive action space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_00614 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Monte Carlo Tree Search via On-the-Fly State-Conditioned Action Abstraction Kwak, Yunhyeok Hwang, Inwoo Kim, Dooyoung Lee, Sanghack Zhang, Byoung-Tak Machine Learning Artificial Intelligence Monte Carlo Tree Search (MCTS) has showcased its efficacy across a broad spectrum of decision-making problems. However, its performance often degrades under vast combinatorial action space, especially where an action is composed of multiple sub-actions. In this work, we propose an action abstraction based on the compositional structure between a state and sub-actions for improving the efficiency of MCTS under a factored action space. Our method learns a latent dynamics model with an auxiliary network that captures sub-actions relevant to the transition on the current state, which we call state-conditioned action abstraction. Notably, it infers such compositional relationships from high-dimensional observations without the known environment model. During the tree traversal, our method constructs the state-conditioned action abstraction for each node on-the-fly, reducing the search space by discarding the exploration of redundant sub-actions. Experimental results demonstrate the superior sample efficiency of our method compared to vanilla MuZero, which suffers from expansive action space. |
| title | Efficient Monte Carlo Tree Search via On-the-Fly State-Conditioned Action Abstraction |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2406.00614 |