# Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy, and Multi-Fidelity Feedback

arXiv: https://arxiv.org/abs/2110.07232 · HTML: https://mlsanity.com/paper/2110.07232/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 67 references that are in the map.
- First posted on arXiv 14 Oct 2021.

## Builds on (most cited first, 18 of 18)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Multi-fidelity Bayesian Optimisation with Continuous Approximations](https://mlsanity.com/paper/1703.06240/) (2017)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [BOCK : Bayesian Optimization with Cylindrical Kernels](https://mlsanity.com/paper/1806.01619/) (2018)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Monte-Carlo Tree Search as Regularized Policy Optimization](https://mlsanity.com/paper/2007.12509/) (2020)
- [Stochastic Bandit Models for Delayed Conversions](https://mlsanity.com/paper/1706.09186/) (2017)
- [Stochastic bandits with arm-dependent delays](https://mlsanity.com/paper/2006.10459/) (2020)
- [AlphaX: eXploring Neural Architectures with Deep Neural Networks and Monte Carlo Tree Search](https://mlsanity.com/paper/1903.11059/) (2019)
- [Regret Analysis for Continuous Dueling Bandit](https://mlsanity.com/paper/1711.07693/) (2017)
- [Bandit Online Learning with Unknown Delays](https://mlsanity.com/paper/1807.03205/) (2018)
- [Optimization of Smooth Functions with Noisy Observations: Local Minimax Rates](https://mlsanity.com/paper/1803.08586/) (2018)
- [Online Stochastic Optimization under Correlated Bandit Feedback](https://mlsanity.com/paper/1402.0562/) (2014)
- [Zeroth Order Non-convex optimization with Dueling-Choice Bandits](https://mlsanity.com/paper/1911.00980/) (2019)
- [UDO: Universal Database Optimization using Reinforcement Learning](https://mlsanity.com/paper/2104.01744/) (2021)
- [Noisy Blackbox Optimization with Multi-Fidelity Queries: A Tree Search Approach](https://mlsanity.com/paper/1810.10482/) (2018)
- [AdaDelay: Delay Adaptive Distributed Stochastic Convex Optimization](https://mlsanity.com/paper/1508.05003/) (2015)

## Built on by (most cited first, 2 of 2)

- [Preference-based Pure Exploration](https://mlsanity.com/paper/2412.02988/) (2024)
- [Certified Multi-Fidelity Zeroth-Order Optimization](https://mlsanity.com/paper/2308.00978/) (2023)

## Abstract (arXiv)

In black-box optimization problems, we aim to maximize an unknown objective function, where the function is only accessible through feedbacks of an evaluation or simulation oracle. In real-life, the feedbacks of such oracles are often noisy and available after some unknown delay that may depend on the computation time of the oracle. Additionally, if the exact evaluations are expensive but coarse approximations are available at a lower cost, the feedbacks can have multi-fidelity. In order to address this problem, we propose a generic extension of hierarchical optimistic tree search (HOO), called ProCrastinated Tree Search (PCTS), that flexibly accommodates a delay and noise-tolerant bandit algorithm. We provide a generic proof technique to quantify regret of PCTS under delayed, noisy, and multi-fidelity feedbacks. Specifically, we derive regret bounds of PCTS enabled with delayed-UCB1 (DUCB1) and delayed-UCB-V (DUCBV) algorithms. Given a horizon T, PCTS retains the regret bound of non-delayed HOO for expected delay of O(log T) and worsens by O(T^frac1-αd+2) for expected delays of O(T1-α) for α ∈ (0,1]. We experimentally validate on multiple synthetic functions and hyperparameter tuning problems that PCTS outperforms the state-of-the-art black-box optimization methods for feedbacks with different noise levels, delays, and fidelity.