PaperlayerView exact revision on arXiv

Source-linked AI summary

Pathwise Information Certificates for Decentralized Adaptive Sensing

Theodoros Tsiligkaridis

arXiv:2610.10362v1cs.ITcs.LGmath.IT

TL;DR

Adaptive decentralized sensing leaves open whether measurements selected from evolving local beliefs have gathered enough evidence to distinguish the target from every alternative. The paper certifies realized evidence against the hardest competitor, yielding reliability bounds and an anytime stopping rule. In tested 1D and 2D query families, worst-competitor information is more strongly associated with localization speed than average-pair information.

  • Problem

    The paper asks whether measurements selected by adaptive decentralized policies have accumulated enough evidence to distinguish the target from every plausible alternative.

    Source: §1 · p. 1

  • Method

    The paper evaluates information induced by realized actions of arbitrary history-dependent policies, accumulating pairwise evidence against competitors along the trajectory.

    Source: §1 · p. 1, §4 · p. 4

  • Results

    Across tested 1D and 2D query families, worst-competitor information has a stronger pooled association with localization speed than average-pair information.

    Source: §1 · p. 2, §8 · p. 7

  • Takeaways & Limitations

    The realized-information process supports finite-horizon MAP bounds, an anytime network-wide stopping rule, and a finite-trajectory diagnostic.

    Source: §8 · p. 7

    The theory assumes a finite hypothesis class, fixed primitive graph, common full-support prior, and known conditionally independent sensors.

    Source: §7 · p. 7

Abstract

from arXiv · show

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\'enyi--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.

1 INTRODUCTION

The paper asks whether evidence gathered by adaptive decentralized policies suffices to distinguish the target from every alternative. It certifies realized evidence against the hardest competitor, deriving reliability guarantees and testing the bottleneck across 1D and 2D sensing.

1 INTRODUCTION

  • The certificate accumulates pairwise Chernoff information from selected queries; the least evidence against any competitor controls finite-time and anytime guarantees, with network disagreement a bounded transient.A query contributes only to hypothesis pairs it separates, with its contribution determined by the sensor model and stationary network.Source: §1 · p. 1, Figure 1 · p. 2
  • The approach evaluates realized actions from arbitrary history-dependent policies post hoc, without requiring a particular sensing policy or target geometry.The paper illustrates binary queries with ordered 1D thresholds and a structured 2D half-plane library.Source: §1 · p. 1
  • The realized-information process yields node-wise finite-horizon MAP bounds and a network-wide anytime certificate for arbitrary history-dependent policies.Each separating measurement contributes according to its sensor model and stationary graph influence; disagreement appears only as a bounded transient.Source: §1 · p. 2
  • Linear growth of the least-resolved competitor’s realized information yields exponential MAP and squared-localization-loss rates.The contribution connects classical hard-pair and two-point lower-bound machinery to the same adaptive decentralized transcript used by the certificate.Source: §1 · p. 2
  • A certified-exploration wrapper guarantees worst-pair coverage while leaving all other rounds to the base policy.Source: §1 · p. 2
  • Worst-competitor information is more strongly associated with localization speed than an average-pair proxy in both 1D and structured 2D sensing.The introduction reports tests across policies, graphs, sensors, and seeds.Source: §1 · p. 2

2 RELATED WORK

Prior work studies adaptive query design and decentralized learning, often through specific strategies, fixed observation models, or asymptotic characteristics. This paper instead certifies evidence accumulated along the realized trajectory of an arbitrary decentralized, history-dependent policy.

2 RELATED WORK

  • Adaptive-querying work studies uncertainty-reducing queries and policy design, while decentralized variants combine active queries with belief sharing.The paper distinguishes its focus as certifying evidence from a realized trajectory rather than optimizing a policy class.Source: §2 · p. 2
  • Decentralized learning and active network testing cover fixed observation models, selected actions, specific strategies, or asymptotic characteristics.Source: §2 · p. 2
  • The paper identifies its contribution as finite-time and anytime-valid guarantees for whether an arbitrary decentralized, history-dependent policy’s selected measurements suffice for reliable localization.Source: §2 · p. 2

3 DECENTRALIZED ADAPTIVE QUERYING

The model uses a finite hypothesis set and history-dependent local queries, with agents updating beliefs from noisy observations and pooling them over a primitive communication graph. The theory does not depend on the particular policies evaluated in the experiments.

3 DECENTRALIZED ADAPTIVE QUERYING

  • The setup has a finite target-hypothesis set, and each agent selects a binary query from its local history.The global filtration is defined after queries and policy randomization are selected but before the next observations.Source: §3 · p. 2
  • Agents begin with a common full-support prior and use a primitive row-stochastic communication matrix with a positive stationary left eigenvector.Each round consists of local Bayesian updating followed by log-linear pooling of beliefs through the network.Source: §3 · p. 3
  • Experiments evaluate posterior bisection, Thompson-style sampling, random querying, and exploration+bisection, but the theory assumes none of these policies.Source: §3 · p. 3

4 RELIABILITY CERTIFICATES FROM REALIZED INFORMATION

The section turns evidence accumulated along realized queries into reliability guarantees for adaptive decentralized sensing. Its central principle is that the least-resolved hypothesis pair controls certification and the attainable error exponent, while network mixing contributes a bounded transient.

4 RELIABILITY CERTIFICATES FROM REALIZED INFORMATION

  • The minimum accumulated pairwise Chernoff information from realized queries tracks the hardest competitor; an average can look favorable while leaving an alternative unresolved.A query contributes only to pairs it separates, with its contribution depending on sensor information and stationary network influence.Source: §4 · pp. 3–4, §4.3 · p. 5

4.1 Finite-time reliability

  • For any history-dependent policy, the finite-time MAP-error bound separates insufficient accumulated evidence from a residual due to observation noise and network disagreement.For geometrically mixing networks, poorer mixing changes the finite-time offset rather than which competitors are informative.Source: §4.1 · p. 4

4.2 Anytime network-wide reliability

  • The anytime network-wide rule stops only when every candidate pair has enough evidence, without knowing the true target or fixing a horizon.It requires the network-wide selected-query log, and its analysis parameter s is fixed in advance; post-hoc optimization is reserved for a diagnostic.Source: §4.2 · pp. 4–5

4.3 Exponential rates and why the hardest competitor matters

  • Linear information growth against every false target implies an exponential MAP-error rate, limited by the slower of information growth and its lower-tail reliability.With distinct targets in a finite metric space, MAP error and squared metric localization loss have the same exponent.Source: §4.3 · p. 5
  • Sublinear expected information for even one pair rules out a positive uniform localization-error exponent, making hardest-pair resolution necessary as well as sufficient for certification.The hard-pair principle is classical, but here the unresolved pair is identified from the realized decentralized action trajectory.Source: §4.3 · p. 5
  • The finite-time and anytime construction extends beyond BSC observations when action-conditioned output laws have uniformly bounded pairwise log-likelihood ratios.For general action-dependent observation kernels, the BSC information term is replaced by the corresponding Chernoff coefficient.Source: §4.3 · p. 6

5 CERTIFIED EXPLORATION FOR ARBITRARY ADAPTIVE POLICIES

Certified exploration supplements an arbitrary adaptive policy with cycles through a separating query family. These cycles give every hypothesis pair a guaranteed information floor, yielding an explicit MAP-error bound while preserving the option to use additional adaptive queries.

5 CERTIFIED EXPLORATION FOR ARBITRARY ADAPTIVE POLICIES

  • After each complete certified cycle, every pair has received at least the cycle’s guaranteed information, while adaptive rounds can only add nonnegative information.The family is synchronized and separates all target pairs.Source: §5 · p. 6
  • After C_t certified cycles, the MAP-error bound decays exponentially with the guaranteed per-cycle information, up to the stated finite-time network correction.The bound applies for every s in the admissible set.Source: §5 · p. 6
  • Ordered 1D thresholds use M − 1 queries per separating family, while an S × S grid uses S − 1 vertical and S − 1 horizontal cuts.For ordered thresholds, a balanced threshold cycle is max–min optimal within synchronized threshold exploration.Source: §5 · p. 6
  • The post-hoc worst-competitor score is a ranking diagnostic, not the fixed-s anytime certificate.It optimizes s after the rollout, unlike the fixed-s stopping guarantee.Source: §5 · p. 6

6 EXPERIMENTS

The experiments test exponential localization, graph effects, and the hardest-competitor hypothesis in ordered 1D and structured 2D sensing. In both settings, worst-competitor information is more strongly associated with localization speed than average-pair information.

6 EXPERIMENTS

  • The study tests exponential localization under linear information growth, graph-dependent finite-horizon behavior, and association with the least-resolved competitor in ordered 1D and non-ordered 2D queries.Rates use a deterministic pre-floor fitting rule; pooled correlations use paired seed-cluster bootstrap replicates.Source: §6 · p. 6

6.1 1D ordered thresholds: convergence, graph effects, and the bottleneck

  • With exploration+bisection fixed in 1D, fitted pre-floor exponents are 0.4288, 0.4035, and 0.3384 for complete, ring, and directed graphs.The corresponding hardest-competitor scores are 0.5380, 0.5295, and 0.5230; the finite-time mixing correction is an additive offset and does not change the asymptotic exponent.Source: §6.1 · p. 6
  • In 1D, the hardest-competitor score correlates with localization exponent at 0.891, versus 0.401 for the average-pair proxy.These pooled statistics are conditional on 210 of 240 configurations with resolvable pre-floor fits; they are not a within-policy rank-ordering guarantee.Source: §6.1 · p. 7

6.2 2D spatial queries: policy behavior and the bottleneck

  • The 2D study uses an 8 × 8 target grid and 42 vertical, horizontal, and diagonal half-plane queries; its certified family contains 14 pair-separating vertical and horizontal cuts.The experiments first compare policies on a complete graph, then test the bottleneck across policies, graphs, sensors, and seeds.Source: §6.2 · p. 7
  • In 2D, four policies show distinct pre-floor localization behavior, and random querying has an average-pair score of 0.44 but a hardest-competitor score and fitted exponent of about 0.09.The policy comparison uses an 8 × 8 grid and complete communication graph.Source: §6.2 · p. 7
  • In 2D, the hardest-competitor score correlates with localization exponent at 0.768, versus 0.484 for the average-pair proxy, across 240 configurations.The paired correlation difference is ∆r = 0.285 (95% CI [0.270, 0.299]); mean exponents are 0.44, 0.33, and 0.28 for complete, ring, and directed graphs.Source: §6.2 · p. 7

7 LIMITATIONS

The theory and its deployment guarantees rely on specific modeling and operational conditions, while several extensions remain open.

7 LIMITATIONS

  • The theory assumes a finite hypothesis class, fixed primitive graph, common full-support prior, and known conditionally independent sensors.Time-varying graphs require a product-mixing argument, and bounded pairwise log-likelihood ratios do not directly cover Gaussian tails; continuous hypotheses and misspecification remain open.Source: §7 · p. 7

8 CONCLUSION

The paper presents a pathwise certificate for evidence collected by arbitrary history-dependent decentralized sensing policies, with fixed-horizon bounds, anytime stopping, and exponential rates under linear information growth. Its tested 1D and 2D query families show a stronger pooled association between worst-competitor information and localization speed than between average-pair information and speed.

8 CONCLUSION

  • Across tested 1D and 2D query families, worst-competitor information has a stronger pooled association with localization speed than average-pair information.Figure 3 reports a 1D paired difference ∆r = 0.490 (95% CI [0.446, 0.527]); Figure 5 reports a 2D paired difference ∆r = 0.285 (95% CI [0.270, 0.299]).Source: §8 · p. 7, Figure 3 · p. 8, Figure 5 · p. 8
  • The same realized-information process yields fixed-horizon MAP bounds, an anytime network-wide stopping rule, and exponential localization rates under linear information growth.A pairwise KL converse connects insufficient information on any pair to the hardest-competitor bottleneck.Source: §8 · p. 7

AI USE STATEMENT

Generative AI tools were used to polish writing and debug experimental code; the authors state they were not used for research ideas, methodology, proofs, experiments, or results analysis.

AI USE STATEMENT

  • The authors report reviewing AI-assisted work and taking responsibility for the final content.They state that mathematical and algorithmic claims, experimental findings, and paper contents were conceived and verified by the authors.Source: AI USE STATEMENT · p. 9

CHECKLIST

The checklist records the paper’s assumptions, proofs, and reproducibility materials. Its appendices derive finite-time and anytime guarantees by tracking pairwise posterior odds, accumulated information, and bounded network disagreement.

CHECKLIST

  • The model assumes a primitive stationary graph, a common full-support prior, conditionally independent sensing noise, and bounded log-likelihood ratios for the controlled-observation extension.The checklist states that the model and update rules are specified in Sections 3–4, with full proofs in Appendix A.Source: CHECKLIST · pp. 10–11

A.1 Posterior-odds recursion with a common full-support prior

  • Local posterior odds update by multiplying prior odds by the one-step likelihood ratio, while the common-prior term cancels under social pooling.Taking logarithms gives the recursion used in the proofs.Source: §A.1 · p. 12

A.2 Fractional-moment martingale

  • The fractional-moment process is a nonnegative martingale because nonseparating queries contribute no information and conditionally independent BSC observations yield the required conditional expectation.The proof distinguishes queries that separate a hypothesis pair from those that induce identical output laws.Source: §A.2 · p. 13

A.3 Network disagreement is a bounded transient

  • Network disagreement contributes a bounded transient, which combines with accumulated pairwise information to bound finite-time MAP error across false hypotheses.The proof bounds the disagreement term using a finite sum enlarged to the infinite mixing series, then applies a union bound.Source: §A.3 · pp. 13–14, §A.4 · p. 14

A.5 Proof of the anytime-valid network-wide certificate

  • The anytime certificate controls the probability of an incorrect MAP decision at any agent and time by requiring information to cross a threshold, then applying Ville’s inequality and a union bound.The threshold crossing defines the stopping rule; the information process is nondecreasing, and the resulting error probability is at most δ.Source: §A.5 · pp. 14–15

A.6 Derivation of the anytime sample-complexity consequence

  • If the least-competitor information grows at least as γt − B, the anytime stopping condition is met by a time obtained by solving that growth inequality.The appendix derives the corresponding sample-complexity consequence after Theorem 2.Source: §A.6 · p. 15

A.8 Proof of Corollary 1

  • A finite primitive stochastic matrix has geometrically decaying disagreement; with an information lower bound γt − B, MAP error has exponential rate at least min{γ, κ}.For symmetric doubly stochastic networks, the contraction is governed by the largest absolute nonunit eigenvalue; if the information bound is deterministic, the lower-tail term disappears.Source: §A.7 · p. 16, §A.8 · p. 16

A.9 Proof of Corollary 2

  • When the minimum target separation dmin is positive, MAP error and squared-metric localization loss have the same exponent; if dmin = 0, only the upper-bound implication is asserted.The proof relates squared localization loss to MAP error through fixed positive sandwich constants when dmin > 0.Source: §A.9 · pp. 16–17

A.10 Proof of Proposition 1

These proofs show why the least-resolved pair limits reliability guarantees, while balanced certified exploration provides a max–min information rate. They also extend the certificate beyond BSC queries and clarify its use as a post-hoc policy diagnostic.

A.10 Proof of Proposition 1

  • Repeating one threshold leaves some distinct hypotheses with identical transcript laws, forcing worst-case error at least 1/2, even though that cut separates many pairs.A balanced cyclic threshold schedule instead gives every adjacent pair a separation once per cycle, despite having a lower average pair-separation fraction than one balanced cut.Source: §A.10 · p. 17

A.11 Proof of Proposition 2

  • If the minimum adaptive-transcript KL divergence over hypothesis pairs is o(T), the uniform error probability cannot have a positive exponential decay rate.The transcript KL chain rule attributes divergence only to observation kernels: history-conditioned action selection and communication contribute zero, and nonseparating BSC queries contribute zero.Source: §A.11 · pp. 17–18

A.12 Proof of Proposition 3

  • A certified query family with minimum pairwise separation dQ yields at least CtdQW(s) information after Ct cycles, and the theorem gives the corresponding MAP and squared-localization bounds.Noncertified rounds add nonnegative information, so they do not reduce this lower bound.Source: §A.12 · p. 18

A.13 Max–min threshold exploration

  • Balanced cycling attains the max–min certified exploration rate within synchronized ordered-threshold schedules, without claiming a bound on additional information from adaptive noncertified rounds.Each adjacent pair is separated only by its corresponding boundary threshold, so distributing the H rounds evenly maximizes the minimum count.Source: §A.13 · p. 19

B QUERY CODING AND SEPARATING FAMILIES

  • Unrestricted binary queries can separate M hypotheses with as few as ⌈log2 M⌉ queries, while the 1D threshold and 2D axial libraries trade cardinality efficiency for interpretable actions.The ordered 1D code has length M − 1 and minimum distance one; the S × S axial code has length 2(S − 1) and minimum distance one.Source: B QUERY CODING AND SEPARATING FAMILIES · p. 19

C STATIONARY-IMBALANCE COMPARISON

D GENERAL CONTROLLED OBSERVATION MODELS: DERIVATION

  • The certificate extends to controlled observation laws when truth-indexed log-likelihood ratios are uniformly bounded; the same martingale and network-disagreement arguments give finite-time and anytime guarantees.For BSC queries, the general information increment is zero for nonseparating pairs and recovers the usual Chernoff contribution for separating pairs.Source: D GENERAL CONTROLLED OBSERVATION… · pp. 20–21

F USING THE CERTIFICATE WITH LEARNED QUERY POLICIES

  • For learned policies, a fixed, prespecified s yields a diagnostic score, but optimizing s after rollout does not itself give an anytime-valid certificate; an exponentially decaying information lower tail is additionally needed for an unconditional exponent guarantee.This distinguishes post-hoc evidence measurement from a guarantee valid across time.Source: F USING THE CERTIFICATE WITH LEARNED… · p. 21

G ADDITIONAL EXPERIMENTAL DETAILS

The additional experiments probe policy, graph, sensor, and observation-model variations, with fitting restricted to positive-error pre-floor regions. In structured 2D sensing, the worst-competitor score correlates more strongly with localization speed than the average-pair score.

G ADDITIONAL EXPERIMENTAL DETAILS

  • Exponent fits use only positive-error points before the Monte Carlo floor, and configurations without a stable pre-floor segment are reported as n/a rather than assigned an exponent.The pooled 1D bottleneck correlations and regressions are conditional on the 210 of 240 configurations that satisfy the rate-fit rule.Source: G ADDITIONAL EXPERIMENTAL DETAILS · pp. 21–23

H ADDITIONAL QUERY-POLICY EXPERIMENTS

  • Additional graph-geometry policy runs report no stable exponent for posterior bisection on the ring, while Thompson and random policies have fitted exponents across all three graphs.The predefined positive-error pre-floor fitting rule determines whether an exponent is reported.Source: G ADDITIONAL EXPERIMENTAL DETAILS · p. 22
  • For exploration+bisection on the directed heterogeneous-sensor graph, fitted exponents are 0.4637 under standard updating and 0.4633 under inverse-stationary updating.The corresponding raw post-hoc information scores are 0.5407 and 0.1590, but their magnitudes are not compared directly because the parameterization changes.Source: G ADDITIONAL EXPERIMENTAL DETAILS · pp. 22–23, Figure 8 · p. 25, Figure 10 · p. 26
  • Across additional policies on the directed heterogeneous-sensor setting, inverse-stationary updating does not uniformly improve fitted empirical convergence speed.Reported exponents vary by policy: Thompson is 0.3770 versus 0.5061, random is 0.0478 versus 0.0502, and exploration+bisection is 0.4637 versus 0.4633 for standard versus inverse-stationary updating.Source: G ADDITIONAL EXPERIMENTAL DETAILS · p. 23

G ADDITIONAL EXPERIMENTAL DETAILS

  • In the bounded continuous-observation study, the complete-graph fitted exponent / worst-score pair is 0.4248/0.5372; ring and directed runs have no fitted exponent because they reach zero Monte Carlo error before the fitting rule finds a stable region.The study uses the exact likelihood in the Bayes update and the exact information increment.Source: G ADDITIONAL EXPERIMENTAL DETAILS · p. 23
  • On the 8 × 8 grid, posterior bisection has the highest reported fitted exponent at 0.7571, while random spatial queries have the lowest at 0.0914.The experiment uses a 42-query library and 14 certified axial cuts; final empirical MAP errors are zero at round 100.Source: G ADDITIONAL EXPERIMENTAL DETAILS · p. 23, Figure 7 · p. 24
  • For pooled 2D configurations, the worst-competitor correlation is 0.768 (95% CI [0.761, 0.777]), versus 0.484 (95% CI [0.474, 0.494]) for the average-pair proxy.The paired difference is ∆r = 0.285 (95% CI [0.270, 0.299]); all 240 configurations yield valid pre-floor fits.Source: G ADDITIONAL EXPERIMENTAL DETAILS · p. 23

H ADDITIONAL QUERY-POLICY EXPERIMENTS

  • The companion figures include localization-loss curves, additional policy curves, and directed-network update comparisons; their results are presented as mechanism checks rather than claims of policy optimality.The 2D curves show pointwise 95% normal-approximation confidence intervals across independent trajectories.Source: H ADDITIONAL QUERY-POLICY EXPERIMENTS · p. 24, Figure 6 · p. 24, Figure 7 · p. 24

Related papers

Loading 2610.10362v1…