Pathwise Information Certificates for Decentralized Adaptive Sensing

Theodoros Tsiligkaridis

cs.ITOct 7, 2026

Pathwise Information Certificates for Decentralized Adaptive Sensing

Authors: Theodoros Tsiligkaridis

Organizations: MIT Lincoln Laboratory

Abstract

We study decentralized adaptive sensing, where multiple agents choose measurements from evolving local beliefs while exchanging information over a communication graph. We ask whether the measurements actually selected by an adaptive policy have collected enough evidence to distinguish the true target from every plausible alternative. We develop a pathwise certificate based on the Rényi--Chernoff information accumulated along the realized sensing trajectory. It yields nonasymptotic MAP-error bounds and an anytime, network-wide stopping rule for arbitrary history-dependent sensing policies, while separating accumulated statistical information from a bounded network-mixing transient. Linear growth of the information against the least-resolved competitor implies exponential decay of MAP and squared-localization error. A classical pairwise KL converse, specialized to the adaptive decentralized transcript, shows that insufficient information on any pair prevents a positive uniform error exponent, confirming the hardest competitor as a fundamental bottleneck. Across policies, graph topologies, sensor profiles, and seeds, the worst-competitor score correlates more strongly with localization speed than an average-pair proxy in both 1D ( $r=0.89$ versus $0.40$ ) and structured 2D sensing ( $r=0.77$ versus $0.48$ ). Our results provide a practical way to certify and diagnose adaptive multi-agent sensing systems using the evidence they actually collect.

Figures & tables

Figure 1: Decentralized adaptive sensing and the pathwise certificate. Agents select history-dependent queries from evolving local beliefs, observe noisy responses, and pool beliefs over a communication graph. Each separating query contributes pairwise Chernoff information $\mathsf{J}_{j}(sv_{j})$ , which depends on the sensor model and the agent’s stationary network influence. Accumulating this evidence along the realized trajectory yields the information process $\mathcal{I}_{t}(m;s)$ , which drives finite-time and anytime reliability guarantees against the hardest competitor.

Work	Decentralized	Adaptive sensing	Arbitrary-policy cert.	Realized-path cert.	Finite-time	Anytime stop
Nedić et al. (2017)	$\checkmark$	–	–	–	$\checkmark$	–
Nitinawarat et al. (2013)	–	$\checkmark$	–	–	–	–
Tsiligkaridis et al. (2015)	$\checkmark$	$\checkmark$	–	–	–	–
Lalitha and Javidi (2017)	$\checkmark$	$\checkmark$	–	–	–	–
Rangi et al. (2021)	$\checkmark$	$\checkmark$	–	–	–	–
This work	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$

Table 1: Positioning of our work. The novelty of our guarantee is the conjunction of decentralization and adaptive sensing with a finite-time, anytime-valid certificate for the realized trajectory of an otherwise arbitrary policy.

Figure 2: 1D exponential localization across graph geometries. With the sensing policy fixed, network-average MAP error decays approximately exponentially before the Monte Carlo floor, with graph-dependent finite-horizon rates. Shading denotes pointwise 95% confidence intervals across independent trajectories.

Figure 3: 1D hardest-competitor bottleneck. Across policies, graph topologies, sensor profiles, and seed blocks, empirical localization speed correlates more strongly with the worst-competitor information score than with the average-pair proxy. The paired difference is

\Delta r=0.490

with 95% CI

[0.446,0.527]

Figure 4: Policy-dependent localization in 2D. Network-average MAP error for posterior bisection, Thompson-style sampling, random spatial querying, and exploration+bisection on the

8\times 8

spatial grid with a complete communication graph. Shading denotes pointwise 95% confidence intervals across independent Monte Carlo trajectories.

Figure 5: 2D hardest-competitor bottleneck. Across

240

policy–graph–sensor–seed configurations on an

8\times 8

spatial grid, worst-competitor information correlates more strongly with empirical localization speed than the average-pair proxy. The paired difference is

\Delta r=0.285

with 95% CI

[0.270,0.299]

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 6 — Figure 6: Additional theory-facing checks. Left: four query policies on the common 1D problem. Right: the bounded continuous-observation model, which exercises the general controlled-observation construction.

Panel of Figure 7 — Figure 7: Structured 2D localization curves. Four query policies on the $8\times 8$ spatial grid; shading denotes pointwise 95% normal-approximation confidence intervals over independent trajectories.

Figure 8: Directed stationary-influence stress test. Sensor information is deliberately anti-aligned with stationary network influence, exposing the coupling represented by

\mathsf{J}_{j}(sv_{j})

Panel of Figure 9 — Figure 9: Graph-geometry robustness and MSE companion. The MSE panel for the main exploration+bisection study and MAP-error results for the remaining query policies. Full MAP/MSE outputs are included with the released figure scripts.

Panel of Figure 10 — Figure 10: Directed-network update comparisons. Standard versus inverse-stationary updating under four query policies, all using the same anti-aligned sensor-quality/stationary-influence profile shown in Fig. 8 .

Explore similar work

Bayesian Networks for Path-Based Sensors: Gathering Information and Path Planning in Communication Denied Environments
May 15, 2026Alkesh K. Srivastava, George P. Kontoudis, Donald Sofge +1Path Planning Bayesian Networks
University of Maryland, College Park, MD, US. · Temple University, Philadelphia, PA, US. · Colorado School of Mines, Golden, CO, US. +1
A Fundamental Limit in Decentralized Decision-Making
Sep 7, 2026Marco Carpentiero, Felice Scala, Vincenzo Matta +1Decentralized Autonomous Organization Network Science
Department of Information and Electrical Engineering and Applied Mathematics (DIEM), University of Salerno, I-84084 Fisciano (SA), Italy · Institute of Electrical and Micro Engineering, EPFL, CH-1015 Lausanne, Switzerland
Entropy-Gated Belief Coordination for Decentralized Multi-Agent Search Under Intermittent Communication
Oct 5, 2026Mohamed Abdelnaby, Kevin Leahy
Department of Robotics Engineering, Worcester Polytechnic Institute

May 15, 2026, cs.ROJ/K move · Enter open · S save

Bayesian Networks for Path-Based Sensors: Gathering Information and Path Planning in Communication Denied Environments

Alkesh K. Srivastava, George P. Kontoudis, Donald Sofge, Michael Otte

University of Maryland, College Park, MD, US. · Temple University, Philadelphia, PA, US. · Colorado School of Mines, Golden, CO, US.+1

Path Planning Bayesian Networks Event-Guided Sensor-Level Fusion Particle Filters Bayesian Robot Systems

Open paper AskPDF arXiv

A "path-based sensor" produces a single observation along a continuous path. For example, a boolean path-based sensor returns a single "1" if an event of interest is detected at any point along the path and a "0" otherwise. Notably, a "1" provides no direct information about where along the path the event(s) may have occurred. Previous work has demonstrated that observations from multiple path-based sensors can be fused to create a Bayesian belief map over the spatial locations of the underlying event or phenomenon. Moreover, path planning can employ Shannon information theory to accelerate the rate of convergence of the belief map. In this paper, we present a new method to update the belief map based on a path-based sensor observation, and then plan paths to increase information gain. In contrast to prior work that approximates the posterior by averaging over the alternative event histories, we introduce a Bayesian Network (BN) formulation that models the probabilistic relationships between the latent variables and path-based sensor measurements, enabling a more principled Bayesian belief update. We consider static hazard detection in a communication-denied environment as a representative problem setting. The event of a robot returning from its path corresponds to a path-based hazard sensor reading of "0" (hazard not detected), while a robot failing to return corresponds to a reading of "1" (hazard detected). We consider false positives and false negatives. We find that the new method leads to quicker convergence of the belief map than prior work in both single- and multi-robot cases.

Abstract

Explore similar work

Bayesian Networks for Path-Based Sensors: Gathering Information and Path Planning in Communication Denied Environments

A Fundamental Limit in Decentralized Decision-Making

Entropy-Gated Belief Coordination for Decentralized Multi-Agent Search Under Intermittent Communication