Move: Learning Markov Persuasion for Online Federated Learning

Online Federated Learning (OFL) trains a shared model from sequentially arriving clients without centralizing raw data. Sustaining participation at low payment is challenging because participation affects future states, only the server observes communication conditions, and their distribution and state dynamics are unknown to the server. Existing methods often neglect future effects, assume known environments, or design rewards and disclosure separately, leading to excessive payments or insufficient participation. We propose MOVE, an online Markov persuasion framework for participation control in unknown action dependent environments. MOVE coordinates rewards and disclosure while learning the condition distribution and state transitions. We formulate participation control through occupancy measures under Bayes plausibility, Bayes benefit, and participation requirements, and prove that posteriors supported on at most two communication conditions suffice for optimal signaling. This structure enables recovery of a signaling policy consistent with Bayes’ rule and finite optimistic planning that accounts for estimation uncertainty. With high probability, MOVE achieves sublinear payment pseudo regret against the best fixed feasible mechanism and sublinear cumulative constraint violations. Experiments show average reductions of 2.66% in payment per arrival versus w/o Signaling, 66.94% in participation violations versus w/o Markov, and 23.47% in target payment versus existing baselines.