Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1109/CIG.2019.8847965 | CoG |
Field | DocType | Volume |
Data mining,Monte Carlo tree search,Data stream,Ordinal number,Computer science,Spacetime,Algorithm,Quantile,Game tree | Journal | abs/1905.13449 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tobias Joppen | 1 | 1 | 0.70 |
| Tilman Strübig | 2 | 0 | 0.34 |
| Johannes Fürnkranz | 3 | 2476 | 222.90 |