Provably Efficient Long-Horizon Exploration in Monte Carlo Tree Search through State Occupancy Regularization
<|reference_start|>Provably Efficient Long-Horizon Exploration in Monte Carlo Tree Search through State Occupancy Regularization: Monte Carlo tree search (MCTS) has been successful in a variety of domains, but faces challenges with long-horizon exploration when compared to sampling-based motion planning algorithms like Rapidly-Exploring Random Trees. To address these limitations of MCTS, we derive a tree search algorithm based on policy optimization with state occupancy measure regularization, which we call {\it Volume-MCTS}. We show that count-based exploration and sampling-based motion planning can be derived as approximate solutions to this state occupancy measure regularized objective. We test our method on several robot navigation problems, and find that Volume-MCTS outperforms AlphaZero and displays significantly better long-horizon exploration properties.<|reference_end|>
@article{schramm2024provably,
    title={Provably Efficient Long-Horizon Exploration in Monte Carlo Tree Search
  through State Occupancy Regularization},
    author={Liam Schramm, Abdeslam Boularias},
    journal={arXiv preprint arXiv:2407.05511},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.05511},
    primaryClass={cs.LG cs.RO}
}