# Pure entropic regularization for metrical task systems

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2019.

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

- [Movement Penalized Bayesian Optimization with Application to Wind Energy Systems](https://mlsanity.com/paper/2210.08087/) (2022)
- [Dynamic Data Layout Optimization with Worst-case Guarantees](https://mlsanity.com/paper/2405.04984/) (2024)
- [Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints](https://mlsanity.com/paper/2408.07831/) (2024)
- [Learning-Augmented Online Minimization with Dual Predictions](https://mlsanity.com/paper/2606.05380/) (2026)
- [Compressing Value Predictions for Learning-Augmented Metrical Task Systems](https://mlsanity.com/paper/2609.33580/) (2026)

## Abstract (arXiv)

We show that on every n-point HST metric, there is a randomized online algorithm for metrical task systems (MTS) that is 1-competitive for service costs and O(log n)-competitive for movement costs. In general, these refined guarantees are optimal up to the implicit constant. While an O(log n)-competitive algorithm for MTS on HST metrics was developed by Bubeck et al. (SODA 2019), that approach could only establish an O((log n)2)-competitive ratio when the service costs are required to be O(1)-competitive. Our algorithm can be viewed as an instantiation of online mirror descent with the regularizer derived from a multiscale conditional entropy. In fact, our algorithm satisfies a set of even more refined guarantees; we are able to exploit this property to combine it with known random embedding theorems and obtain, for any n-point metric space, a randomized algorithm that is 1-competitive for service costs and O((log n)2)-competitive for movement costs.