# The Traveling Bandit: A Framework for Bayesian Optimization with Movement Costs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 58 references that are in the map.
- First posted on arXiv 18 Oct 2024.

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

- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Greed is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation](https://mlsanity.com/paper/1911.12809/) (2019)
- [Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration](https://mlsanity.com/paper/1304.5350/) (2013)
- [Efficient Nonmyopic Bayesian Optimization via One-Shot Multi-Step Trees](https://mlsanity.com/paper/2006.15779/) (2020)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [GLASSES: Relieving The Myopia Of Bayesian Optimisation](https://mlsanity.com/paper/1510.06299/) (2015)
- [Why Non-myopic Bayesian Optimization is Promising and How Far Should We Look-ahead? A Study via Rollout](https://mlsanity.com/paper/1911.01004/) (2019)
- [Lipschitz Bandits with Batched Feedback](https://mlsanity.com/paper/2110.09722/) (2021)
- [An Algorithm for Stochastic and Adversarial Bandits with Switching Costs](https://mlsanity.com/paper/2102.09864/) (2021)
- [A Nonmyopic Approach to Cost-Constrained Bayesian Optimization](https://mlsanity.com/paper/2106.06079/) (2021)
- [Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index](https://mlsanity.com/paper/2406.20062/) (2024)
- [SnAKe: Bayesian Optimization with Pathwise Exploration](https://mlsanity.com/paper/2202.00060/) (2022)
- [Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times](https://mlsanity.com/paper/2201.12909/) (2022)
- [On Batch Bayesian Optimization](https://mlsanity.com/paper/1911.01032/) (2019)
- [Movement Penalized Bayesian Optimization with Application to Wind Energy Systems](https://mlsanity.com/paper/2210.08087/) (2022)
- [Bandits with Movement Costs and Adaptive Pricing](https://mlsanity.com/paper/1702.07444/) (2017)
- [Multi-Armed Bandits with Metric Movement Costs](https://mlsanity.com/paper/1710.08997/) (2017)
- [Bayesian Optimisation for Active Monitoring of Air Pollution](https://mlsanity.com/paper/2202.07595/) (2022)

## Abstract (arXiv)

This paper introduces a framework for Bayesian Optimization (BO) with metric movement costs, addressing a critical challenge in practical applications where input alterations incur varying costs. Our approach is a convenient plug-in that seamlessly integrates with the existing literature on batched algorithms, where designs within batches are observed following the solution of a Traveling Salesman Problem. The proposed method provides a theoretical guarantee of convergence in terms of movement costs for BO. Empirically, our method effectively reduces average movement costs over time while maintaining comparable regret performance to conventional BO methods. This framework also shows promise for broader applications in various bandit settings with movement costs.