Ordinal Bucketing for Game Trees using Dynamic Quantile Approximation
This work addresses efficiency issues in game tree search algorithms for AI applications, particularly in noisy settings, but it is incremental as it builds on existing Ordinal Monte Carlo Tree Search methods.
The paper tackled the problem of noisy rewards in Monte Carlo Tree Search by introducing an ordinal bucketing algorithm that dynamically approximates quantiles from incremental data streams, resulting in improved time and space complexity over vanilla MCTS in noisy environments, as demonstrated in the General Video Game Framework.
In this paper, we present a simple and cheap ordinal bucketing algorithm that approximately generates $q$-quantiles from an incremental data stream. The bucketing is done dynamically in the sense that the amount of buckets $q$ increases with the number of seen samples. We show how this can be used in Ordinal Monte Carlo Tree Search (OMCTS) to yield better bounds on time and space complexity, especially in the presence of noisy rewards. Besides complexity analysis and quality tests of quantiles, we evaluate our method using OMCTS in the General Video Game Framework (GVGAI). Our results demonstrate its dominance over vanilla Monte Carlo Tree Search in the presence of noise, where OMCTS without bucketing has a very bad time and space complexity.