Communication-Efficient Federated Online Decision-Making with Stateful Costs
For federated learning systems with state-dependent costs, BLADE provides a communication-efficient algorithm with theoretical guarantees.
BLADE achieves sublinear dynamic regret for federated online decision-making with stateful costs using only O(T/K) communication, validated on a synthetic linear system.
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.