PROSE: A Theory of Optimal Stopping with Perishable Evidence for Peer Selection in Intermittently Connected Decentralised Learning

Christos Anagnostopoulos

Decentralised federated learning removes the aggregation server but makes collaboration dependent on transient peer availability. In mobile and intermittently connected systems, evaluating a promising peer consumes contact time and may cause the exchange opportunity itself to vanish, so that the evidence a learner gathers about a peer is perishable: it decays because links expire and because peer models drift while old measurements age. This paper develops a self-contained theory of optimal stopping for the resulting peer-selection problem. We formalise a receiver's within-contact decision as a finite-horizon Markov optimal-stopping problem with costly information acquisition and a future-arrival outside option, and prove that it admits an optimal policy characterised by a reservation value (Snell-envelope structure). Around this formulation we prove: (i) stage-uniform, drift-aware concentration and a maximin certification rule that is correct with high probability together with a finite-sample identification bound; (ii) a mobility-aware value of-information stopping rule and comparative statics showing that higher link hazard lowers the value of continued probing and enlarges…