A patrol robot that follows a fixed schedule is easy to beat. An intruder who watches it learns exactly how long each location stays unwatched. One principled fix is to make the robot's movements a Markov chain, a random walk whose next step depends only on the current location, and to tune the chain's transition probabilities so that the time until the robot returns to each location is as unpredictable as possible. Duan, George and Bullo call this quantity return time entropy. The trouble is computing such a chain. It requires a slow, non-convex optimization that must be rerun from scratch for every patrol graph, every set of travel times and every desired visit frequency. When a corridor closes, a road floods, or the priorities over targets shift, the robot either keeps an outdated chain or waits for the solver to finish.
Novel-view synthesis faced the same problem. Fitting a 3D scene by per-scene gradient descent took minutes to hours, and the field largely removed that cost by training one network that outputs the answer in a single forward pass. The best such networks then add a few learned correction steps driven by feedback on the network's own error. This note proposes carrying that recipe over to surveillance planning: train a graph network, with a short error-feedback refinement loop, that maps any patrol graph to a near-optimal maximum-return-time-entropy chain in milliseconds. The network would be trained without any solver-generated labels, by directly maximizing the differentiable return time entropy of its own outputs.
Core Claim
The per-instance solver MaxReturnEntropy can largely be replaced by a learned solver, with little loss of entropy and a large gain in replanning speed. That solver is from Markov Chains with Maximum Return Time Entropy for Robotic Surveillance, which runs gradient projection on a truncated return time entropy. The learned solver does its job in three stages. It first produces a single-pass guess, then projects that guess onto the feasible set of chains, and finally applies $T$ recurrent refinement steps. In each step the network sees the current chain's per-node return-time distributions and entropy gradient and predicts a correction. That speed makes possible a regime the per-instance solver cannot serve: patrols that re-randomize online whenever the environment changes.
Let $P$ be a transition matrix supported on the graph's edges with prescribed stationary distribution $\pi$ (the long-run fraction of time spent at each node). Let $\tau_i$ be the first return time to node $i$ under the edge travel times. The objective is
$$H_R(P) = \sum_i \pi_i \, H(\tau_i),$$
where $H$ is Shannon entropy. We use the truncated version $H_R^K$, which keeps return times up to horizon $K$. Its analytic gradient, derived by Duan et al., supplies the training signal. For a distribution $\mathcal{D}$ over graph instances $G$, a network $f_\theta$ and the projection $\Pi_G$ onto feasible chains, training solves
$$\max_\theta \; \mathbb{E}_{G \sim \mathcal{D}} \big[ H_R^K(\Pi_G(f_\theta(G))) \big].$$
Because every output passes through $\Pi_G$, the stationary-distribution and graph-structure constraints hold exactly by construction rather than approximately.
Why this pairing, and what prior work supplies
The surveillance side supplies the objective and its known difficulties. Duan et al. show three things about MaxReturnEntropy. It beats both MaxEntropyRate and MinKemeny against intruders who observe patrol history. The objective has no closed form and must be truncated. The problem is non-convex, with multiple local optima. The companion survey, Markov Chain-Based Stochastic Strategies for Robotic Surveillance, treats these chains as solved once per fixed graph. Neither work considers the cost of re-solving, which is the gap this note targets.
Two further papers motivate the online setting, and neither addresses how to compute randomized strategies quickly on changing instances. Mitigating the Curse of Correlation in Security Games by Entropy Maximization argues that structured, low-entropy randomization leaks information across targets. Unpredictable Planning Under Partial Observability equates trajectory entropy with information leaked to an observer.
The reconstruction side supplies the method, not the application. GS-LRM shows that a transformer trained across many scenes can replace per-scene fitting, reconstructing in about 0.23 s. DepthSplat shows that such a network can be trained self-supervised through the very objective it serves, in its case photometric rendering loss. We mirror this by training through $H_R^K$ with no solver labels. ReSplat shows that single-pass predictors are systematically imprecise. It also shows that feeding the model's own rendering error back through four recurrent steps surpasses 4,000-iteration per-scene optimization while running 100x faster. Our refinement loop is the direct analogue, with the per-node return-time distributions and entropy gradient playing the role of ReSplat's error maps. We do not claim these gains transfer. Whether they do is the empirical question.
The two papers that already connect the directions are AREA3D and GO-PRE. Both are close in vocabulary but distinct in substance. AREA3D uses feed-forward perception to speed up deterministic next-best-view selection. GO-PRE measures the entropy of rendered pixels at candidate poses. Neither randomizes the agent's path, and neither models revisit timing. We amortize the planner itself, and the entropy we optimize concerns the agent's revisit times, not scene uncertainty.
Research Program
Instances. We will build a distribution of patrol graphs from two sources. The first is building-scale navigation graphs from the scans in Habitat-Matterport 3D and Replica. For these, we sample 20 to 200 waypoint nodes from navigable space and set integer travel times from geodesic distance. The second is random geometric and grid graphs, used to probe out-of-distribution transfer. Stationary distributions $\pi$ will be sampled to reflect target priorities, and HM3D scenes will be held out by scene for testing. The road-network San Francisco crime-map scenario of Duan et al. will be reconstructed as a final test instance of a different kind, with the caveat that our version may differ in detail from theirs.
Model. The model is a message-passing graph network. Its inputs are the adjacency structure, the travel times, $\pi$ and a random seed. The seed lets the network output different near-optimal chains for the same graph, and the implications of that are tested below. The network outputs logits for the edges, and a batched differentiable projection $\Pi_G$ maps them onto the convex polytope of feasible chains. The refinement stage shares weights across its $T$ steps. At each step it takes as input the current chain, the truncated per-node return-time distributions (obtained from the delayed linear system), the per-node entropies and the analytic gradient. It then outputs a residual correction, which is projected again.
Training. Training maximizes the objective above, with an intermediate loss applied at every refinement step, as in ReSplat's training scheme.
Analyses. We will study how accuracy trades off against $T$ and against the truncation horizon $K$. We will also check whether the network, trained across many instances, finds better basins than a single solver run. The problem's non-convexity makes this plausible, but it is not guaranteed.
Baselines
The naive reference points are the uniform random walk projected onto the constraints, which serves as the do-nothing baseline, and the MinKemeny chain, which minimizes expected travel time. Duan et al. show that MinKemeny is fast but predictable. Both are cheap and bound the problem from below.
The strongest competitor on entropy quality is the MaxReturnEntropy gradient-projection solver of Duan et al., run to convergence with multiple random restarts, keeping the best. It defines the quality ceiling we must approach. For fairness, it gets the same truncation horizon $K$, the same projection routine and the same GPU, batched across instances. Its step size and restart count will be tuned on the validation graphs with the same tuning budget we spend on the network. On the SF scenario, Duan et al. report only that MaxReturnEntropy has higher return time entropy and entropy rate than MinKemeny, at the cost of a larger Kemeny constant. We found no reported numerical result on Lacuna for exact MaxReturnEntropy values on the SF scenario, so we will re-measure every baseline ourselves.
The strongest competitor on speed is the same solver warm-started from the previous chain after the graph changes, run under fixed wall-clock budgets. We treat this as the real threat. The network beats it if, at matched wall-clock budgets of 10 ms and 100 ms, the network reaches higher $H_R^K$ on held-out scenes. The target is at least 95% of the multi-restart solver's value within 10 ms, measured both on cold starts and after large perturbations.
We also compare against MaxEntropyRate. It is fast to compute but weaker against intruders, per Duan et al., and it is included in the intruder evaluation.
Two ablations isolate the key ingredient. The first removes the return-time feedback, making the model single-pass only. The second feeds the refinement steps the raw gradient alone, without the return-time distributions. The second ablation separates "learned optimizer" from "learned solver that reads its own error."
Why not just…?
Why not just warm-start the gradient-projection solver after each change? For small edits, such as a slight change in travel time, warm-starting may be almost free, and it may match the network. We do not dismiss this. The proposal's claim is scoped to cold starts, fleets of many distinct graphs, and structural edits such as removed edges or added nodes. Those edits make the old chain infeasible, so the solver must start from a projection far from the new optimum. The perturbation-sequence experiment below settles which regime each method wins. If warm-starting matches the network at a 10 ms budget across all perturbation sizes, we will drop the replacement claim. The network's role would then shrink to initializing the solver on cold starts, and we will report that instead.
Why not just maximize entropy rate, which is convex and fast? Duan et al. show MaxEntropyRate is beaten by MaxReturnEntropy against observing intruders. They also show that return time entropy can exceed entropy rate by up to a factor of $n$, so the two objectives rank chains differently. We will re-test this with the intruder simulation below. If the intruder success rate under MaxEntropyRate equals that under MaxReturnEntropy on our building graphs, the case for learning the harder objective collapses, and we will say so.
Why not just run the solver for fewer iterations on a GPU? A truncated solver is exactly the matched-budget comparison in the baselines. ReSplat's finding suggests that four feedback-driven learned steps can beat thousands of generic gradient steps. That finding is about rendering, though, not Markov chains, so the budget curves must show the same effect here.
Why not learn a patrol policy with reinforcement learning against a modeled intruder? Duan et al. note that return time entropy defends against unspecified intruders rather than a particular parameterized one. Training against one modeled intruder risks overfitting to that intruder. We keep the intruder-agnostic objective and use modeled intruders only for evaluation.
Proposed Experiments and Decisive Checks
The first experiment measures the quality–latency frontier on held-out HM3D and Replica graphs. It plots $H_R^K$ normalized by the multi-restart solver against wall-clock time for every method, across graph sizes from 20 to 200 nodes.
The second is the perturbation-sequence test. Each episode applies 50 random edits to a graph, ranging from travel-time noise to edge deletions and node insertions. After each edit, we record the entropy each method reaches within 10 ms and 100 ms, and the time each takes to reach 99% of the converged value.
The third checks security directly. We simulate the rational intruder of Duan et al., which observes arrival history and times an attack of duration $d$ to fall in a revisit gap. We then report the detection probability for each chain as a function of $d$, including under online replanning after edits.
The fourth tests transfer, from building graphs to random graphs and to the SF road network.
The fifth measures seed diversity. Suppose different seeds give distinct near-optimal chains for the same graph. Then an observer who has estimated the current chain gains little, because the next replan draws a new one. We will measure the total-variation distance between chains from different seeds at matched entropy, and the success of an intruder that fits the chain from the last replan.
The proposal is falsified if either of two things happens. One is that warm-started solving matches the network at every perturbation size under a 10 ms budget. The other is that the feedback ablation matches the full model. In the second case, the ReSplat-style refinement contributes nothing, and the result reduces to a plain learned heuristic.
References
- Markov Chains with Maximum Return Time Entropy for Robotic Surveillance
- Markov Chain-Based Stochastic Strategies for Robotic Surveillance
- Mitigating the Curse of Correlation in Security Games by Entropy Maximization
- Unpredictable Planning Under Partial Observability
- GS-LRM: Large Reconstruction Model for 3D Gaussian Splatting
- DepthSplat: Connecting Gaussian Splatting and Depth
- ReSplat: Learning Recurrent Gaussian Splats
- AREA3D: Active Reconstruction Agent with Unified Feed-Forward 3D Perception and Vision-Language Guidance
- GO-PRE: Goal-Oriented Next-Best-View Selection via Predictive Rendering Entropy for Active 3D Reconstruction
- Habitat-Matterport 3D Dataset (HM3D): 1000 Large-scale 3D Environments for Embodied AI
- The Replica Dataset: A Digital Replica of Indoor Spaces