# Reaching Your Goal Optimally by Playing at Random

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 May 2020.

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

- [Mixing Any Cocktail with Limited Ingredients: On the Structure of Payoff Sets in Multi-Objective POMDPs and its Impact on Randomised Strategies](https://mlsanity.com/paper/2502.18296/) (2025)

## Abstract (arXiv)

Shortest-path games are two-player zero-sum games played on a graph equipped with integer weights. One player, that we call Min, wants to reach a target set of states while minimising the total weight, and the other one has an antagonistic objective. This combination of a qualitative reachability objective and a quantitative total-payoff objective is one of the simplest setting where Min needs memory (pseudo-polynomial in the weights) to play optimally. In this article, we aim at studying a tradeoff allowing Min to play at random, but using no memory. We show that Min can achieve the same optimal value in both cases. In particular, we compute a randomised memoryless varepsilon-optimal strategy when it exists, where probabilities are parametrised by varepsilon. We then characterise, and decide in polynomial time, the class of games admitting an optimal randomised memoryless strategy.