# Shortest Paths without a Map, but with an Entropic Regularizer

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2022.

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

- [Mixing predictions for online metric algorithms](https://mlsanity.com/paper/2304.01781/) (2023)
- [Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors](https://mlsanity.com/paper/2506.05479/) (2025)
- [Learning-Augmented Online Minimization with Dual Predictions](https://mlsanity.com/paper/2606.05380/) (2026)
- [Ariadne and Theseus: Exploration and Rendezvous with Two Mobile Agents in an Unknown Graph](https://mlsanity.com/paper/2403.07748/) (2024)

## Abstract (arXiv)

In a 1989 paper titled "shortest paths without a map", Papadimitriou and Yannakakis introduced an online model of searching in a weighted layered graph for a target node, while attempting to minimize the total length of the path traversed by the searcher. This problem, later called layered graph traversal, is parametrized by the maximum cardinality k of a layer of the input graph. It is an online setting for dynamic programming, and it is known to be a rather general and fundamental model of online computing, which includes as special cases other acclaimed models. The deterministic competitive ratio for this problem was soon discovered to be exponential in k, and it is now nearly resolved: it lies between Omega(2k) and O(k2k). Regarding the randomized competitive ratio, in 1993 Ramesh proved, surprisingly, that this ratio has to be at least Omega(k2 / log1+ε k) (for any constant ε > 0). In the same paper, Ramesh also gave an O(k13)-competitive randomized online algorithm. Between 1993 and the results obtained in this paper, no progress has been reported on the randomized competitive ratio of layered graph traversal. In this work we show how to apply the mirror descent framework on a carefully selected evolving metric space, and obtain an O(k2)-competitive randomized online algorithm. This matches asymptotically an improvement of the aforementioned lower bound (Bubeck, Coester, Rabani; STOC 2023), which we announced (among other results) after the initial publication of the results here.