Paperlane

no. 16 · Tuesday 17 November 2026

Percolation Markov Decision Processes

Melissa González García and Guillaume Vigeral

math.OC · v2

Abstract

We study Percolation Markov Decision Processes (PMDPs), where the decision maker repeatedly moves a token through the d-dimensional integer lattice with deterministic transitions and random payoffs assigned to the edges. Payoffs are revealed before the beginning of the decision process and the decision maker aims to maximize the average accumulated payoff over a fixed horizon. First, we address general asymptotic control-theoretic questions by proving the existence of the uniform value and 0-optimal strategies. Furthermore, we examine the structural properties of optimal strategies: we establish the existence of stationary 0-optimal strategies for a class where the token moves in a fixed direction independent of the player's actions, and we provide low-dimensional examples to illustrate their complexity. Moreover, we introduce a dimensional lifting property that allows PMDPs to be approximated by lower-dimensional PMDPs, offering a representation of the approximation of critical probability thresholds in percolation theory via PMDPs.

fields
Optimization and Control, Probability
pdf ↗ page arXiv:2609.19905 ↗