Deceptive Stochastic Patrolling via Markov Chain Lifting

arXiv:2610.10903 · eess.SY, cs.SY, math.OC · Submitted 2026-10-07 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: Today's paper: "Deceptive Stochastic Patrolling via Markov Chain Lifting".

Dev: The gist In this paper we propose lifted Markov Chains as a new paradigm for deriving patrol strategies for mobile agents on an environment represented as a graph > How…

Rosa: First, who's behind it and why it matters.

Paper summary: Rosa: So this paper is about something called lifted Markov Chains, and they’re using it to figure out patrol strategies for mobile agents on a graph. It seems like they’re trying to make these strategies better by working with a bigger state space than just the actual locations of the nodes.

Dev: Right. The core idea here is that they lift the Markov Chain onto a larger state space and then project it back down to the actual graph nodes, which they say preserves the original stationary distribution of that chain. They’re essentially creating extra virtual copies of states to get better patrol plans <ref:2610.10903#pg2>.

Taro: What this means for us is that instead of just looking at where the patroller *is*, we can model the patrol process in a way that incorporates more information about the system, which should help when things get messy or unpredictable <ref:2610.10903#pg3>.

Rosa: Exactly. The paper claims they can prove bounds on how much better these lifted MCs are compared to standard, non-lifted Markov Chains when measuring performance by something called the Kemeny constant <ref:2610.10903#pg2>.

Dev: They show that even when you optimize the lifted chain, it still performs at least as well as optimizing the original non-lifted one <ref:2610.10903#pg2>. Specifically, they establish an upper bound related to one/two times the conductance of the original MC and a lower bound related to that same conductance <ref:2610.10903#pg2>.

Taro: That sounds like a solid theoretical underpinning for why this approach makes sense, linking it directly to how connected the graph is via its conductance <ref:2610.10903#pg2>.

Rosa: Beyond just the Kemeny constant, they also look at other metrics like Stackelberg Game Capture Probability and Return-Time Entropy <ref:2610.10903#pg2>. These metrics are supposed to show a corresponding monotonicity when you move from the original chain to the lifted one.

Dev: That’s interesting because it suggests that for strategies involving adversarial situations or unpredictability, the improvement isn't just a fluke; it’s consistent across these different measures of success <ref:2610.10903#pg2>.

Taro: If we think about the world misbehaving—say, if an adversary is trying to foil our patrol—this predictability in how the lifted strategy performs under those conditions is what matters most <ref:2610.10903#pg3>.

Rosa: And they show a tractable method for optimizing these lifted MCs on general graphs with edge weights that represent travel times, which is something we need when dealing with real-world environments <ref:2610.10903#pg2>.

Dev: So, the paper provides both the theoretical justification for why lifting works and a practical way to actually implement these strategies using optimization techniques like Projected Gradient Descent <ref:2610.10903#pg2>.

Taro: That’s helpful because it moves this from just a theoretical curiosity to something that could actually be used in planning patrol routes where travel times matter, which is a big step for autonomy <ref:2610.10903#pg2>.

Rosa: The deceptive aspect they mention is that an adversary can't see the MC state directly from the patroller’s location, which means a naive adversary using a plug-in estimator would arrive at what they think is optimal, even though it’s not <ref:2610.10903#pg2>.

Dev: That implies that our strategy can have some sort of inherent stealth or opacity that the opponent doesn't fully grasp, which is a subtle but important mechanism for patrol effectiveness <ref:2610.10903#pg2>.

Taro: It changes how we think about defense in these mobile agent scenarios; it suggests that making the system’s true underlying state harder to infer from external observations can be a way to build robustness <ref:2610.10903#pg3>.

Rosa: The real-world verification seems promising too, with simulation results showing substantial performance improvements on sparse graphs for metrics like Kemeny and SGCP <ref:2610.10903#pg2>.

Dev: It’s good to see that the improvement scales well with graph sparsity, meaning that if the environment is more spread out or less dense, this lifting technique gives us a bigger boost in performance <ref:2610.10903#pg2>.

Taro: So, when you look at real-world tests on things like a twelve-node weighted graph or an eighteen-node graph, the results consistently point to this scaling behavior for the metrics we care about <ref:2610.10903#pg2>.

Rosa: The authors are also flagging some limitations in their work, specifically mentioning that they haven't fully extended the theoretical results to accommodate travel times yet <ref:2610.10903#pg2>.

Dev: So, the paper shows what’s possible with static travel times in its current formulation but acknowledges that integrating dynamic travel times into the lifting process is a next step they haven't finished <ref:2610.10903#pg2>.

Taro: That gives us a clear direction for future research, focusing on how to make the lifted Markov Chains work when the environment itself is changing in real-time <ref:2610.10903#pg3>.

Rosa: Overall, this paper on Deceptive Stochastic Patrolling via Markov Chain Lifting shows a new way to derive patrol strategies by using larger state spaces and proving that this lifting method yields performance improvements over simpler models, especially as the graph structure gets sparser <ref:2610.10903#pg2>.

Dev: It’s a method that gives us solid theoretical bounds on the improvement, even if we still have some open questions about applying it perfectly to complex, time-varying environments <ref:2610.10903#pg2>.

Taro: It’s a practical tool for autonomy research because it shows how to use these mathematical structures to handle uncertainty and improve patrol success in real-world scenarios <ref:2610.10903#pg3>.

Rosa: That’s the gist of what they are proposing here, and it seems like a solid piece of work that connects theoretical Markov Chain analysis with practical mobile agent deployment <ref:2610.10903#pg1>.

Dev: We'll be keeping an eye on those future extensions regarding travel times and how the adversary reacts to this lifting approach <ref:2610.10903#pg3>.

Conclusion: Rosa: So we're wrapping up on "Deceptive Stochastic Patrolling via Markov Chain Lifting," which is about using bigger state spaces to design better patrol plans on graphs.

Dev: Right, so they've taken a standard Markov chain and lifted it onto a larger space, and then projected it back down to the actual map nodes.

Taro: What that means in practice is that the way we plan patrols can be more detailed than just where the agent is right now.

Rosa: It suggests that this lifting technique gives us a mathematical way to find better patrol routes, especially when you have things like travel times included in your model.

Dev: The authors show how this method actually improves things compared to simpler Markov Chain models, proving bounds on how much better it can get using metrics like the Kemeny constant.

Taro: And they point out that this improvement gets bigger the more sparse the graph becomes, which is pretty interesting for real-world deployment.

Rosa: It means we might be able to design patrols that are surprisingly robust even when the environment is quite open or spread out.

Dev: The paper also touches on how an adversary can't easily figure out what state the patrol agent is actually in, which adds another layer of complexity to the problem.

Taro: That deception aspect is key because it means our strategy isn't just reactive; it has some built-in uncertainty that a smart opponent can't just plug into.

Rosa: It really shows how these mathematical tools can help us think about mobile agents in ways we hadn't considered before, moving beyond simple shortest path problems.

Dev: But the authors also flag that they haven't fully worked out how to integrate dynamic travel times perfectly yet, which is a limitation for real-time applications.

Taro: So the big question now is how we tackle those time-varying environments if we want this lifting method to work reliably in practice.

Yohan John, Gilberto Díaz-García, Jason R. Marden, Francesco Bullo

eess.SY, cs.SY, math.OC

Submitted: 2026-10-07

Updated: 2026-10-07

Code: https://github.com/yohanjohn307/markov-chain-lifting

The gist: The gist In this paper we propose lifted Markov Chains as a new paradigm for deriving patrol strategies for mobile agents on an environment represented as a graph > How it works 1.

Key concepts

Lifted Markov Chains (LMCs)
LMCs operate on a larger state space than the graph nodes themselves. They create virtual copies of the original states while keeping the original chain's long-term behavior (stationary distribution) intact. This expansion allows for more nuanced patrol planning.
Kemeny Constant
This metric measures a patrol strategy's efficiency based on mean first passage times between nodes. A lower Kemeny constant generally indicates a better, more efficient patrolling strategy for the mobile agent in the environment.
Stackelberg Game Capture Probability (SGCP)
SGCP evaluates an optimal patrol strategy against an intelligent adversary trying to maximize capture probability. The goal is to find a strategy that minimizes the maximum probability of being captured by the adversary, leading to safer patrolling plans.

Terminology

Summary

The gist In this paper we propose lifted Markov Chains as a new paradigm for deriving patrol strategies for mobile agents on an environment represented as a graph >

How it works

  1. Lifted MCs operate on a state space that can be larger than the set of nodes of the graph, and a projection operation maps the MC state to the corresponding node of the graph >

  2. This lifting increases the size of the state space by creating virtual copies of original states while preserving the stationary distribution of the original MC >

  3. The transition probabilities are defined such that they satisfy specific conditions related to both graph constraints and stationary distribution preservation, as shown in Eq. (7) >

Key Metrics for Performance

The paper defines three important MC patrol strategy metrics:

  1. Kemeny Constant: This is defined as K(P) = π⊤Mπ, where M is the mean first passage time matrix whose entries are m j i >

  2. Stackelberg Game Capture Probability (SGCP): This metric identifies the optimal MC strategy for a patroller facing an omniscient adversary, aiming to maximize J(P) = min i,j∈S n P h T T j i(P) ≤ τ j i o >

  3. Return-Time Entropy (RTE): This metric identifies patrol strategies with unpredictable return times T j j to each node j in the graph, maximizing the truncated RTE defined as H(P) = − Xn j=1 π j X Kη k=1 Fk(j, j) log Fk(j, j) >

Performance Improvement and Bounds

The authors prove bounds on the performance improvement of lifted MCs over non-lifted MCs using the Kemeny constant, showing that optimized lifted MCs cannot perform worse than optimized non-lifted MCs >

  1. The upper bound is established by Theorem 1, which states that for any irreducible MC P and partition V, the optimal lifting achieves 1/2Φ(P) ≤ min P lift∈L(P,V) K lift(P lift) ≤ K(P) >

  2. The lower bound in Theorem 1 is given by Corollary 6, which relates the Kemeny constant of the optimal lifted MC for a given collapsed MC P and partition V to the conductance Φ as [2Φ(P)]−1 ≤ min P lift∈L(P,V) K lift(P lift) >

  3. The improvement grows as the number of nodes n in the path graph increases, where the lifted MC achieves linear scaling while the non-lifted MC scales quadratically >

Deception and Optimization

The paper shows that MC lifting provides an interesting deceptive aspect since an adversary cannot perceive the state of the MC directly from the location of the patroller, leading to a model misspecification error on the part of the adversary >

  1. A naive adversary using a plug-in estimator will arrive at P, which is also considered optimal because it is the KL-optimal aggregation of P lift with respect to V >

  2. The optimization problem for lifted MCs can be formulated as minimizing Y(P lift) subject to constraints that ensure a valid lifting, and this minimization can be solved using a Projected Gradient Descent (PGD) approach which results in a convex quadratic program >

  3. The study demonstrates substantial performance improvement on sparse graphs, particularly for the Kemeny and SGCP metrics, with the results showing an increase in performance scaling with graph sparsity >

Real-World Applications

Numerical experiments on randomly generated and real-world graphs verify that lifted MCs achieve substantial improvements, particularly on sparse graphs >

  1. In a San Francisco Case Study involving a 12-node weighted graph, the SGCP metric results show a consistent trend of greater improvements with graph sparsity >

  2. The results for all three metrics in the San Francisco Case Study show that the SGCP metric results show a consistent trend of greater improvements with graph sparsity >

  3. The University of Coimbra Case Study on an 18-node weighted graph shows that a significant performance improvement can be seen, particularly for the Kemeny and SGCP metrics >

The work suggests several topics for future study, including extensions of the theoretical results to accommodate travel times, the optimal assignment of virtual states to nodes, and approaches for the adversary against lifted MCs >

--- Page 1 ---

The gist In this paper we propose lifted Markov Chains as a new paradigm for deriving patrol strategies for mobile agents on an environment represented as a graph >

--- Page 5 ---

The gist In this paper we propose lifted Markov Chains as a new paradigm for deriving patrol strategies for mobile agents on an environment represented as a graph >

How it works

  1. Lifted MCs operate on a state space that can be larger than the set of nodes of the graph, and a projection operation maps the MC state to the corresponding node of the graph >

  2. This lifting increases the size of the state space by creating virtual copies of original states while preserving the stationary distribution of the original MC >

Improvements for AI systems

  1. textbf Lifting for Higher Performance Patrol Strategies in Sparse Graphs (Kemeny Constant) with Bounds 1/2Φ(P) ≤ min P lift∈L(P,V) K lift(P lift) ≤ K(P). This allows patrol systems to achieve a dramatic improvement over K(P) on sparse graphs like the University of Coimbra case study.

  2. textbf Deceptive Performance via Model Misspecification Error. The paper shows that a naive adversary using a plug-in estimator converges to P, leading them to underestimate the performance of the patroller because "Klift(P lift) < K(P)" in the corridor environment. This enables agents to exploit an adversary's reliance on standard estimators.

  3. textbf Optimized Strategy Assignment via Centrality Metrics in Graphs. The optimization process can use metrics like node degree, betweenness centrality, eigenvector centrality to assign virtual states proportionally, leading to substantial performance improvement in Kemeny and SGCP metrics on 10-node ER random graphs.

  4. textbf Travel-Time Weighted Path Optimization for Real-World Constraints. The method allows for the definition of a weighted set first passage time where edge weights represent the number of time steps it takes the patroller to traverse the edge, enabling patrol strategies on weighted graphs like San Francisco's police locations, which can be pruned based on wmax.

  5. textbf Tractable Optimization via Projected Gradient Descent (PGD). The paper provides a method for optimizing lifted MC metrics subject to constraints, specifically presenting a convex quadratic program solved by PGD to find the optimal lifting of an MC.

Related papers