Iterative Budgeted Exponential Search
Authors: Malte Helmert, Tor Lattimore, Levi H. S. Lelis, Laurent Orseau, Nathan R. Sturtevant
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experiments show that the new algorithms are robust in scenarios where existing algorithms fail. In the case of tree search, our new algorithms have no overhead over IDA* in scenarios to which IDA* is well suited and can therefore be recommended as a general replacement for IDA*. |
| Researcher Affiliation | Collaboration | 1Department of Mathematics and Computer Science, University of Basel, Switzerland 2Deep Mind, London, UK 3Departamento de Informática, Universidade Federal de Viçosa, Brazil 4Department of Computing Science, University of Alberta, Edmonton, AB, Canada |
| Pseudocode | Yes | Algorithm 1 Query with extended feedback for tree search, Algorithm 2 Exponential search with budgeted queries, Algorithm 3 Iterative Budgeted Exponential Search, Algorithm 4 Uniform Budgeted Scheduler, Algorithm 5 Dovetailing IBEX, Algorithm 6 Enhanced IBEX. |
| Open Source Code | Yes | All these algorithms are implemented in C++ in the publicly available HOG2 repository, https://github.com/nathansttt/hog2/. |
| Open Datasets | Yes | This paper uses well-known public datasets and refers to them with citations: '15-Puzzle [Doran and Michie, 1966]' and '(12, 4)-Top Spin [Lammertink, 1989]'. |
| Dataset Splits | No | The paper does not provide specific details on training, validation, or test dataset splits. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., GPU/CPU models, memory amounts) used for running its experiments. |
| Software Dependencies | No | The paper mentions that algorithms are 'implemented in C++' but does not specify versions of the compiler or any specific libraries/dependencies used. |
| Experiment Setup | Yes | Our implementation uses 50 buckets and sets b = 2. EDA*(γ) is a variant of IDA* designed for polynomial domains that repeatedly calls DFS with unlimited budget and a cost threshold of γk at iteration k. In our experiments we take γ {2, 1.01}. ... We report results also for α = 2 to show the gain in efficiency when using a budget factor window of [2, 8] instead of the narrower window [2, 2]. Taking is_additive=y helps on exponential domains, whereas is_additive=n helps on polynomial domains, as expected. |