Optimistic learning improves decision making in unknown path problems

OPSRL-SSP: Optimistic Posterior Sampling for Stochastic Shortest Path with Minimax-Optimal Regret

Machine Learning

Summary

This work looks at how computers can learn to find the best path in situations where the chances of moving from one place to another are not known. The authors propose a clever way for the computer to guess and explore these chances while being optimistic about the results, which helps the computer learn faster and make better decisions. Their method also comes with mathematical guarantees that it performs as well as the best possible approach in the worst cases. This solves a previously open question about how to do this type of learning efficiently.

What this means in practice

  • For robotics engineers: Design navigation algorithms that learn unknown environments quickly while minimizing travel costs.
  • For network operations teams: Optimize routing decisions in communication networks where the network behavior is uncertain and changes over time.

Authors

Yiming Xu, Xian Wei, Cheng Chen

Abstract

We study online reinforcement learning for the stochastic shortest path (SSP) problem with unknown transition dynamics. Although existing posterior-sampling methods perform well empirically on SSPs, their regret guarantees do not achieve the minimax-optimal order. We address this limitation by proposing OPSRL-SSP, an optimistic posterior-sampling algorithm for the SSP setting. The algorithm operates in epochs and uses a logarithmic, time-dependent schedule for the number of posterior samples. To induce optimism, we augment the transition model with a pseudo-state assigned an optimistic boundary value. We establish a high-probability regret bound of $\tilde{O}(B_\star \sqrt{SAK} + B_\star S^2 A)$, where $B_\star$ is an upper bound on the expected cost of the optimal policy, $S$ and $A$ are the numbers of states and actions, respectively, and $K$ is the number of episodes. In addition, we extend the analysis to general zero-cost SSPs using a universal cost-perturbation argument. The leading term matches the minimax lower bound $Ω(B_\star \sqrt{SAK})$, thereby addressing the open problem raised by Jafarnia-Jahromi et al. [19] for posterior sampling in the SSP setting.