Percolation Markov Decision Processes
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "Percolation Markov Decision Processes".
Emmy: Here's the gist of the paper. Percolation Markov Decision Processes study single-player versions of percolation games with i.i.d.
Ada: payoffs on edges to establish existence and properties of limit values and optimal strategies.
Emmy: Model Definition and Classification The PMDP is described by a tuple (I, E, g) where I is the player’s action set, E is a probability space, and g is a collection of uniformly bounded i.i.d.
Ada: R-valued random payoffs defined on omega.
Paper summary: Ada: So we're talking about this paper titled Percolation Markov Decision Processes by Melissa Gonzalez Garcia and Guillaume Vigeral. The main idea here is studying games where you repeatedly move a token through some set of positions, and there are random payoffs on those edges that are revealed beforehand. They're looking to find the uniform value as the number of steps gets really big, and they also want to establish what kind of strategies can actually achieve that value.
Emmy: It's about these Markov Decision Processes, or PMDPs, which are these sequential decisions based on random outcomes. The paper sets up a model with an action set, a probability space for the random payoffs, and then it classifies the structure of this process into trivial, oriented, or controllable types based on what the decision maker can actually do.
Kolya: What's interesting is that they establish the existence of this uniform value—that there's a strategy that almost always gets you close to it for long enough—and they prove there's even a zero-optimal strategy that hits that limit exactly, which is pretty strong work for this type of problem <ref:2609.19905#pg3>.
Ada: Right, and they go into the specific case of Bernoulli payoffs, which are those random payoffs coming from a simple probability distribution. In that particular setup, they find some nice continuity results for the uniform value function <ref:2609.19905#pg4>. They also look at one-dimensional examples to show how complex optimal strategies can get before moving on to more general cases.
Emmy: The structure of the paper seems to focus a lot on classifying these processes, looking at whether the action set is trivial, oriented, or controllable because that dictates what kind of mathematical tools you need to use for the analysis <ref:2609.19905#pg3>. They show that for oriented processes, the sequence of values converges almost surely to a constant value independent of where you start in your state space Zd.
Kolya: That convergence result is important because it suggests that even when you're moving around in a complex network, if it's oriented correctly, the long-term average payoff settles down to one fixed number <ref:2609.19905#pg3>. But what about the other cases where you can cycle forever?
Paper summary: Ada: Well, they show that for those non-oriented cases—the trivial and controllable ones—they still establish the existence of a limit value, which means there's still some guarantee that a strategy will get you near that long-term average payoff <ref:2609.19905#pg3>. The main contribution is proving the existence of that uniform value itself for all three structures.
Emmy: And when they look at Bernoulli payoffs specifically, the paper gives us some concrete bounds on how much the value function changes as you change the underlying probability parameter, which they call p. They show it's Lipschitz on a certain range above zero <ref:2609.19905#pg4>.
Kolya: But there's a twist when the process is controllable with Bernoulli payoffs—they find that the uniform value function doesn't have to be continuous at zero, because it becomes equal to the essential supremum of those random payoffs <ref:2609.19905#pg4>. That sounds like a big structural difference in how these games behave near zero probability.
Ada: Exactly, and that connects into how they look at critical thresholds for percolation theory. They introduce this dimensional lifting property which lets them approximate these complex processes using simpler lower-dimensional ones <ref:2609.19905#pg1>. This is useful because they apply it to figure out the critical probability of oriented Bernoulli percolation on a square lattice by using one-dimensional PMDPs as an approximation <ref:2609.19905#pg3>.
Emmy: That dimensional lifting property seems to be the structural key that lets them bridge the gap between these Markov decision processes and standard percolation theory models <ref:2609.19905#pg1>. It allows them to characterize a critical threshold for oriented Bernoulli percolation using the uniform value function, stating that the uniform value equals one almost surely if and only if the probability p is greater than or equal to a specific threshold called pbc <ref:2609.19905#pg3>.
Kolya: When you tie this back to last-passage percolation models, they show a direct link for oriented PMDPs in dimensions two or higher, where they prove that the uniform value is equal to mu of one d over d <ref:2609.19905#pg3>. This relates the average payoff directly to the shape function of those last-passage percolation models.
Ada: That connection is quite neat because it takes something about decision making and maps it onto a geometric quantity from last-passage percolation, which we already study in physics <ref:2609.19905#pg3>. It suggests that the long-term performance of the decision maker is fundamentally linked to the geometry of how paths evolve on a lattice.
Paper summary: Emmy: The paper also touches on some really deep structural questions about optimal strategies, especially when we look at positive linearly dependent actions. They investigate whether you can even find an explicit variational formulation for these optimal strategies in those more complex cases <ref:2609.19905#pg3>. That suggests the mathematical structure of the problem itself might be quite rigid, or perhaps it's just very hard to pin down mathematically.
Kolya: I did see some analysis regarding myopic strategies, where we only consider the immediate next move, and they show that for a certain probability p greater than a critical point p star, no optimal myopic strategy actually exists <ref:2609.19905#pg5>. They find that the actual optimal strategy then depends on some property of k modulo three <ref:2609.19905#pg5>.
Ada: That dependence on k modulo three is interesting because it shows that even when we know the general structure of the problem, finding a simple rule for every single situation is not straightforward <ref:2609.19905#pg5>. It means the complexity of optimal play stays high even after you've established the existence of a uniform value.
Emmy: It also tells us that when we look at how the value function behaves as p approaches zero, it exhibits a phase transition at that same critical parameter where an associated oriented percolation process has its own threshold <ref:2609.19905#pg6>. That is a structural connection between these two seemingly different systems.
Kolya: So, to summarize what we've heard about this paper on Percolation Markov Decision Processes: they prove the existence of a uniform value and zero-optimal strategies for these games across different structures, especially for Bernoulli payoffs <ref:2609.19905#pg3>. They link these results to percolation theory through dimensional lifting and connect oriented processes to last-passage percolation models via the uniform value being mu of one d over d <ref:2609.19905#pg3>.
Ada: And they provide some concrete examples, like the continuity results for Bernoulli payoffs and how optimal strategies can be very complex in one dimension <ref:2609.19905#pg4>. It’s a deep look at the interplay between sequential decision making and spatial randomness.
Emmy: The authors also point out that they can approximate these processes using lower-dimensional models, which is a powerful tool for understanding things in higher dimensions by looking at simpler cases <ref:2609.19905#pg1>. This dimensional lifting is the mechanism that connects these different levels of complexity.
Paper summary: Kolya: They also flag a limitation, and it's this: they are working with i.i.d payoffs across space, but they question whether convergence results can be established when the payoffs are only i.i.d across space <ref:2609.19905#pg5>. That's a question about the underlying randomness that keeps them from claiming everything is settled and perfectly understood yet <ref:2609.19905#pg3>.
Ada: So, the big picture here seems to be establishing the fundamental existence of these optimal long-term behaviors and then showing how different mathematical structures—like dimensional lifting or last-passage percolation—can be used to characterize critical points in related fields like percolation theory <ref:2609.19905#pg3>.
Emmy: And the way they analyze the strategy existence, finding that myopic strategies fail past a certain point p star and require rules based on k modulo three <ref:2609.19905#pg5>, highlights just how much structure is hidden in these systems even when we can't find a simple formula for the best move <ref:2609.19905#pg3>.
Kolya: That seems to suggest that while the long-term average payoff might be predictable, the actual path taken to get there can be incredibly intricate depending on where you are in that probability space and what the structure is <ref:2609.19905#pg4>. We need more work on those convergence questions when randomness isn't perfectly independent across all space <ref:2609.19905#pg5>.
Ada: It’s a lot to take in, really how these simple setups of random walks and decisions can lead to such detailed structural results about the long-term behavior and the complexity of the optimal play <ref:2609.19905#pg3>. That's what this paper is all about.
Emmy: And when we think about its implications, it connects game theory, probability, and geometry in a way that suggests these types of decision processes are more deeply connected to spatial structures than we initially thought <ref:2609.19905#pg3>. It’s a lot to consider for how these models show up in other areas of science.
Kolya: I think the part about the phase transition at p star, linking it to oriented percolation processes, is a really important piece because it shows that the critical behavior isn't isolated; it's tied to how we define the underlying graph structure itself <ref:2609.19905#pg6>.
Ada: It’s definitely a paper that keeps you thinking about what happens when you add randomness to sequential choices and how the geometry of the movement space dictates everything about the long-term outcome <ref:2609.19905#pg3>. That's where we'll leave it for today.
Conclusion: Ada: So, we're wrapping up our look at Percolation Markov Decision Processes by Melissa Gonzalez Garcia and Guillaume Vigeral <ref:2609.19905#pg3>. This paper is really about taking these decision-making games, which are like a player moving through random edges with random payoffs, and figuring out what the long-term outcome actually settles down to.
Emmy: Exactly. They classify these games into three types: trivial, oriented, or controllable based on how much choice the player has. The main thrust of their work is proving that for all these structures, there is a uniform value—a number that a good strategy can almost always guarantee for a very long time.
Kolya: What I found most important was how they connected this to percolation theory. They use something called dimensional lifting to look at these complex decision processes and approximate them using simpler, lower-dimensional ones, which is a really useful trick for figuring out critical thresholds in other areas of math.
Ada: And they showed that this approach lets them pinpoint exactly when a certain probability p is enough for the uniform value to hit one almost surely. It links the average payoff directly to the shape function of last-passage percolation models, which is a cool way to see how these games connect to spatial geometry in physics.
Emmy: It suggests that the long-term behavior of a decision process isn't just about the immediate choices you make; it's tied to the underlying structure of the space itself, whether we view it through Markov processes or geometric paths.
Kolya: But they also pointed out some lingering questions, like whether these convergence results hold if the random payoffs aren't perfectly independent across every single location. That’s a caveat that suggests there’s still more to explore about how randomness affects these long-term averages.
Ada: Right. So, the authors set up a solid foundation for understanding how sequential choices interact with spatial randomness, and they've pointed us toward where the next big structural questions lie in this field.
Melissa González García, Guillaume Vigeral
Universit Paris Dauphine-PSL · Universit Paris 1 Panthon-Sorbonne, CNRS, Centre d’Economie de la Sorbonne, Paris, France
math.OC, math.PR
Submitted: 2026-09-17
Updated: 2026-11-16
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 79/100
The gist: Percolation Markov Decision Processes study single-player versions of percolation games with i.i.d.
Key concepts
- PMDP
- A framework describing single-player games where players choose actions based on a state, and transitions depend on random payoffs. It helps analyze strategic behavior in these probabilistic environments.
- Limit Value
- The uniform value is the long-term average payoff achievable by an optimal strategy as the game length becomes very large. The paper proves this limit value exists for these games.
- Oriented PMDPs
- These are PMDPs where the transition structure forms a directed graph. This structure is important because it links the game to directed last-passage percolation, allowing researchers to use known results from that field.
Terminology
Summary
Percolation Markov Decision Processes study single-player versions of percolation games with i. p. 1i.d. payoffs on edges to establish existence and properties of limit values and optimal strategies. p. 0
Model Definition and Classification
The PMDP is described by a tuple (I, E, g) where I is the player’s action set, E is a probability space, and g is a collection of uniformly bounded i.i.d. R-valued random payoffs defined on omega. p. 3 The transition structure induces a directed graph on the state space Zd, which is classified as trivial if I = O (the state never changes), oriented if 0 in/ conv(I) (the transition graph is acyclic), or controllable if 0 in conv(I) and I! p. 4= O (the transition graph contains cycles). p. 4
Main Results on Limit Values and Strategies
The paper establishes the existence of the uniform value as a limit value, meaning there is a strategy that nearly guarantees this value for all sufficiently large horizons. Theorem 2.11 proves the existence of a 0-optimal strategy that attains this limit value exactly, which implies the existence of the uniform value. p. 5 For oriented PMDPs, Theorem 2. p. 27 shows that for all z in Zd, the sequence vn(z) converges P-almost surely to a constant v∞ independent of z. p. 4
Properties of Bernoulli Payoffs
For PMDPs with Bernoulli payoffs, Proposition 4.1 proves that the limit value function p -> v∞(p) is Lipschitz on [p0, 1] for every p0 > 0. p. 3 Furthermore, if the PMDP is oriented, the value function is also continuous at p = 0. p. 2 Conversely, for controllable PMDPs with Bernoulli payoffs, the limit value p -> v∞(p) is discontinuous at p = 0 because v∞(p) = M(p) where M denotes the essential supremum of g. p. 7
Dimensional Lifting and Critical Thresholds
The paper introduces a dimensional lifting property that allows PMDPs to be approximated by lower-dimensional PMDPs. This property is applied to approximate the critical probability of oriented Bernoulli percolation on the square lattice via a sequence of values of one-dimensional PMDPs. p. 2 Theorem 5.3 characterizes the critical threshold of oriented Bernoulli percolation with the uniform value, stating that v∞(p) = 1, P-a. p. 6s if and only if p ≥ pbc. p. 6
Connection to Last-Passage Percolation
Oriented PMDPs naturally link with directed last-passage percolation (LPP) models. Proposition 6. p. 01 shows that for every oriented PMDP in dimension d ≥ 1 with a set I of d linearly independent actions, the uniform value is v∞ = µ(1d) / d. p. 5 This result relates the uniform value to the shape function µ(x) of LPP models. p. 5
Future Research Directions
The paper suggests several future research directions, including whether convergence results can be established when payoffs are i.i.d. only across space. p. 1 It also proposes a conjecture that for oriented PMDPs with Bernoulli(p) payoffs and p in (0, 1), the uniform value undergoes a phase transition at the same critical parameter as an associated oriented percolation process defined on the same transition graph. p. 1 The authors also question whether explicit variational formulations for the uniform value of oriented PMDPs with positive linearly dependent actions can be derived. p. 2
Proof of Proposition 4. p. 05
The proof of Proposition 4.5 involves considering λ-discounted games to solve the issue where a strategy optimal for every fixed horizon might not exist. p. 5 The analysis shows that for small enough λ, the proposed myopic strategy is optimal in Γ(z). p. 5 This leads to the determination of the critical probability p∗ where the uniform value function exhibits a change in behavior. p. 1 The final step involves solving a system of equations for wλ as λ -> 0 to yield v∞(p). p. 1
Sixth Step Analysis
The analysis for the case p > p∗ shows that no optimal myopic strategy exists when p > p∗, and an optimal strategy is given by a specific rule depending on k modulo 3. This demonstrates the complexity of optimal strategies in this regime. p. 0 p. 0 The proof involves comparing different sequences of actions to show that certain deviations are strictly better when p > pstar. p. 4 p. 4
The analysis for the case p > pstar shows that no optimal myopic strategy exists when p > pstar, and an optimal strategy is given by a specific rule depending on k modulo 3. This demonstrates the complexity of optimal strategies in this regime. The proof involves comparing different sequences of actions to show that certain deviations are strictly better when p > pstar.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Develop systems that can compute uniform values for percolation Markov decision processes (PMDPs) by employing block-based strategies that ensure convergence to the limit value in an infinite horizon average payoff with limit inferior criterion.
-
Create AI systems capable of finding 0-optimal strategies for oriented PMDPs by constructing stationary strategies based on the
priority order
derived from the state's Euclidean distance to the origin. -
Implement algorithms that approximate critical probability thresholds in percolation theory by using a sequence of one-dimensional PMDPs exhibiting a dimensional lifting property to converge to the critical parameter of oriented Bernoulli percolation on a square lattice.
-
Design systems that can analyze and compute explicit uniform values for specific one-dimensional oriented PMDPs with Bernoulli payoffs, such as those described in Example 1 and Example 6.
-
Build AI tools capable of determining whether the limit value of an oriented PMDP with Bernoulli payoffs is equal to 1 almost surely by checking if the Bernoulli parameter p is greater than or equal to the critical probability threshold pbc.
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise