Communication-Efficient Federated Online Decision-Making with Stateful Costs

Abstract

We study dynamic regret in federated online decision-making with stateful incurred costs under block-based synchronization and partial client participation. In this setting, sparse communication affects not only the pointwise update quality but also the realized state trajectory along which costs are incurred. We propose \textbf{BLADE}, a projected blockwise federated online decision method. BLADE uses only \(O(T/K)\) communication and achieves a dynamic-regret bound for the incurred cost against path-length-bounded comparator sequences; under \(K=\lceil\sqrt T\rceil\), the bound is sublinear whenever \(V_T=o(T^{1/4})\). Experiments on a controlled synthetic stable linear system validate the predicted communication--regret, memory, participation, disturbance-variation, and horizon-scaling effects.