# Learning Graph-Indexed Trajectory Patterns for Stochastic On-Time Arrival Routing

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 25 references that are in the map.
- First posted on arXiv 24 Aug 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [On Deep Recurrent Reinforcement Learning for Active Visual Tracking of Space Noncooperative Objects](https://mlsanity.com/paper/2212.14304/) (2022)
- [Tractable Pathfinding for the Stochastic On-Time Arrival Problem](https://mlsanity.com/paper/1408.4490/) (2014)

## Abstract (arXiv)

Correlated link travel times create decision-relevant patterns in partial route histories. In stochastic on-time arrival (SOTA) routing, each route prefix forms a variable-length, graph-indexed sequence in which traversed-edge identities, realized travel times, and route order jointly indicate the reliability of downstream actions. We present GPG-HT, a history-conditioned Transformer policy that learns a trajectory representation from this structured sequence together with the current node, destination, and remaining budget. Edge-time cross-attention and sequence encoding capture dependencies within the observed history, while decoder cross-attention maps the resulting trajectory memory and decision context to an online distribution over feasible outgoing edges. A history-conditioned generalized policy-gradient objective trains the representation from terminal on-time outcomes. Experiments on the Sioux Falls and Anaheim road-network topologies with simulated correlated link times show that GPG-HT achieves higher mean on-time arrival probabilities than representative optimization and reinforcement-learning baselines. Paired common-pool evaluation confirms statistically significant gains in all six network-budget settings, reaching 2.82-3.27 percentage points on Sioux Falls and 0.36-1.04 percentage points on Anaheim. Correlated, independent, shuffled-history, no-history, and architecture controls further demonstrate that GPG-HT learns decision-relevant structure from graph-indexed route prefixes.