acceptodds
Under review as a conference paper at ICLR 2027

Move: Learning Markov Persuasion for Online Federated Learning

Abstract

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.

Primary area:
learning theory
Keywords:
Online Federated Learning, Markov Persuasion, Participation Control, Bayes Plausibility, Sublinear Regret

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_aviROpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies client participation control in online federated learning and proposes MOVE, which models participation control as a constrained Markov persuasion problem, uses occupancy measures to characterize state dependence, learns the unknown condition distribution and state transitions online, and transforms the problem into finite linear programs. The paper provides theoretical proofs and validates the performance of the proposed approach through experiments.

Critical strengths

This paper provides a computationally tractable optimization method for complex signal mechanism design. It formulates participation control through occupancy measures under Bayes plausibility, Bayes benefit, and minimum participation requirements, and proves that posteriors supported on at most two communication conditions suffice for optimality. The paper thereby transforms the complex mechanism design problem into a computable finite optimization problem, providing a mathematical foundation for online optimization in unknown dynamic environments.

Critical weaknesses

The connection between the theoretical optimization objective and actual federated learning performance is insufficient, which limits the method's application value. Federated learning performance is also affected by data distribution, data quality, and differences in client training contributions. The same participation rate does not necessarily correspond to the same model convergence speed or accuracy. Although the paper conducts experiments on three datasets, the theoretical framework does not directly account for these factors, nor does it establish an explicit link between the participation rate constraint and model performance. Therefore, the existing results are insufficient to fully demonstrate that the method can still achieve the expected performance in more complex real-world federated learning scenarios.

Questions for authors

(1) Does MOVE's lower payment mainly stem from its mechanism or from a lower participation rate? Please supplement the cumulative payment and number of training rounds required to reach the target accuracy under comparable actual participation rates, so as to clarify whether the lower payment originates from information disclosure and Markov planning. (2) Is the adaptation of the baselines fair? Please explain the specific modifications made to each baseline, whether these modifications are justified, and whether they weaken the performance of the original methods, and re-compare under settings that preserve the core mechanisms of the baselines as much as possible.

2 comments
AuthorsOpenReview ↗

Linking Participation Control to FL Performance and Clarifying Baseline Fairness

We thank the reviewer for the thoughtful comments. In the revised version, we address W1&Q1 by adding a shared wireless service example in Section 3.3 and payment and update comparisons in Section 6.3 (Table 5). For Q2, we clarify the baseline implementations in Appendix A.9.1 and add the DaringFed signaling comparison in Section 6.3 (Table 4).

Q1&W1: FL performance and payment savings.

MOVE controls participation and payment to recruit clients for FL training, while model updates follow the underlying FL algorithm. Its constraint, E[∑at,n]≥qmin⁡E[∑Nt]\mathbb{E}[\sum a_{t,n}]\ge q_{\min}\mathbb{E}[\sum N_t], ensures a minimum expected rate of client updates, but does not itself guarantee convergence or target accuracy. We agree that data heterogeneity, client quality, and update contributions also affect convergence and are not explicitly modeled in our theory.

All methods share initialization, data partitions, client sampling rules, network environments, and episode budgets. Each participant performs one local epoch followed by a server update. FEMNIST uses natural LEAF partitions. CIFAR-10 uses a classwise Dirichlet partition (α=0.3\alpha=0.3) across 20 clients. We measure cumulative payment and training updates to the same accuracy targets (80% on FEMNIST and 70% on CIFAR-10).

DatasetMethodParticipation rate (%)Payment to targetTraining updates
FEMNISTMOVE59.721185.62 ± 55.632313.4
DaringFed (optimized signaling)57.651254.91 ± 23.632339.0
L2I58.771243.54 ± 51.002290.2
Dynamic Pricing59.611313.41 ± 33.832357.2
CIFAR-10MOVE59.72244.67 ± 43.42477.4
DaringFed (optimized signaling)58.58260.27 ± 41.29477.8
L2I61.45253.64 ± 19.34455.0
Dynamic Pricing60.74272.26 ± 17.92479.6

At nearly matched participation, MOVE reduces payment over Dynamic Pricing by 9.73% (FEMNIST) and 10.13% (CIFAR-10). Update counts differ by only 1.9% and 0.5%, respectively, indicating that savings do not mainly come from fewer updates. Implied payment per update is about 8.0% and 9.7% lower. This links mechanism design to the cost of reaching the same FL accuracy without claiming a convergence guarantee. Note that fewer updates do not imply lower computational cost, as models and accuracy targets differ across datasets.

Q2: Baseline adaptations and fairness.

All baselines share data partitions, sampling, environments, target accuracies, and episode budgets. Adaptations address differences in information and decision spaces.

DaringFed. Its original formulation assumes a known communication prior, whereas MOVE learns an unknown prior. We therefore report two variants:

DatasetMethodPayment at target accuracyParticipation (%)
FEMNISTDaringFed (uninformative signaling)1817.75 ± 84.8793.00
DaringFed (optimized signaling)1132.45 ± 73.4350.00
MOVE1094.55 ± 54.8658.12
CIFAR-10DaringFed (uninformative signaling)386.52 ± 48.2093.14
DaringFed (optimized signaling)229.30 ± 19.7650.00
MOVE230.20 ± 30.6758.83

The uninformative version uses conservative rewards to meet participation requirements without the true prior, resulting in about 93% participation and higher payment. The optimized version jointly optimizes reward and disclosure using a uniform prior, preserving DaringFed's core mechanism without access to the unknown true prior. MOVE pays less on FEMNIST and comparably on CIFAR-10, while achieving higher participation. These are not comparisons at matched participation rates. The first table provides that comparison.

L2I. Its CUCB uses client quality estimates and confidence bonuses. Here, sequential arrivals allow only a binary participation decision, not client subset or data quantity selection. We preserve its exploration principle through larger reward bonuses for states with few visits and include a fixed reward schedule variant. This is an adapted reward policy baseline, not unmodified L2I.

Dynamic Pricing. We retain its increasing reward schedule and compensation for accumulated participation shortfalls, mapping rewards to the common feasible range and using a fixed prior because the true prior is unknown.

These adaptations preserve applicable core mechanisms while aligning information and action assumptions. We also disclose that all five FEMNIST DaringFed calibration seeds violate the cumulative Bayes benefit constraint. Their payments are therefore not presented as fully feasible outcomes.

We agree that data quality for individual clients, contributions, and their interaction with network conditions merit further study. Our guarantees concern payment and participation under stated assumptions. Experiments on heterogeneous datasets provide complementary empirical evidence of end to end FL performance.

Thank you for your response. After reviewing the feedback and the manuscript, I will maintain my score. Thank you.

Reviewer_cwNSOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies client participation in online federated learning setting. At each episode, the server commits to a scalar payment and a state-dependent signaling rule, the client computes expected cost and decides whether to participate, which causes the system state transition in a Markovian sense. The authors then used tools from Bayesian persuasion and online learning, MDP, to develop an algorithm to solve this online problem and achieve O(T+Th)O(\sqrt{T}+Th) regret.

Critical strengths

The paper studies an interesting setting of Bayesian persuasion in federated learning setting.

Dimension reduction in Lemma 2 is powerful (the result itself is not technically difficult to derive though).

Critical weaknesses

My main issue with the paper is not in the technical results, but rather in the modeling aspect.

  1. Markovian transition nature: in a federated learning setting, we usually assume a large number of agents and each with very limited influence on the system state. I find it hard to justify the setting in the paper where one client's participation may influence the entire system.

  2. The paper assumes the server having information about the local clients' environment, but not the agent themselves. This is again a bit hard to imagine. Since the edge devices are capable of doing the computation, they should have access to their local states. What kind of information would only be available to the server but not the clients?

  3. Limited improvement in the numerical studies. A few percentage improvement seems hard to justify the computation overhead.

  4. How does the algorithm scale with N? It seems the curse of dimensionality would be pretty bad.

  5. Negative regret in Fig 2 suggests participation constraint violation, how would this be justified in real setting?

  6. The paper appears to be heavily aided by AI and the presentation/motivation is very confusing.

Questions for authors

See weakness 4 and 5

3 comments
AuthorsOpenReview ↗

Clarifying Modeling Assumptions, Practical Benefits, and Scalability

We thank the reviewer for the thoughtful feedback. In the revised version, we address W1&W2 by clarifying how uploads affect current costs and later arrivals in Section 3.3. For W3, we add payment and runtime comparisons in Appendix A.9.5 (Table 11). For W4, we report results for larger NN in Appendix A.9.6 (Table 12) and summarize them in Section 6.4. For W5, we add D0 continuation results in Section 6.2 (Table 3).

W1&W2: Markov transitions and information asymmetry.

MOVE targets OFL over shared wireless infrastructure, where sequential uploads compete for uplink capacity. The state τ\tau represents shared network conditions (e.g., load and available capacity), not a client's private computing state. The aggregator monitors aggregate traffic and reservations. Clients observe their devices and links but may not know overall congestion or competing traffic. We do not assume clients lack all network information, only the aggregator's global view. If both observe the same state, signaling may have no value. This setting is outside our scope.

An upload does not determine the global state. It consumes shared capacity and may change residual capacity or queueing delay, altering the next state distribution. The kernel captures this probabilistic effect. Relative to w/o Markov, MOVE reduces mean participation violation by 61.7%, 69.8%, and 69.3% under weak, default, and strong action coupling, respectively. The result under weak coupling shows that a large individual effect is unnecessary. With no effect, transitions are independent of the action.

W3: Payment savings versus computational overhead.

We compared methods at similar participation rates (target accuracy: 80% on FEMNIST and 70% on CIFAR-10).

DatasetMethodParticipation rate (%)Payment to targetTotal time to target (s)
FEMNISTMOVE59.721185.62 ± 55.63353.89
DaringFed (optimized signaling)57.651254.91 ± 23.63376.18
L2I (reward policy)58.771243.54 ± 51.00369.64
Dynamic Pricing59.611313.41 ± 33.83363.80
CIFAR-10MOVE59.72244.67 ± 43.42396.92
DaringFed (optimized signaling)58.58260.27 ± 41.29378.02
L2I (reward policy)61.45253.64 ± 19.34352.06
Dynamic Pricing60.74272.26 ± 17.92424.94

At comparable participation, MOVE reduces payment over Dynamic Pricing by 9.73% and 10.13%. It is not always fastest, showing runtime tradeoffs that depend on the dataset.

W4: Scaling with NN.

NN is the maximum arrivals per episode. Each LP has O(∣X∣∣Qh∣+m∣X∣2)O(|X||Q_h|+m|X|^2) variables and constraints, with one LP solved per candidate reward. With fixed states per stage, ∣X∣=O(N)|X|=O(N). For fixed m,hm,h, LP size grows polynomially in NN. We tested m=3m=3, h=0.05h=0.05, and two states per stage:

NNTotal states ∣X∣\lvert X\rvertPlanning time per episode (s)Peak memory (MB)
360.132 ± 0.02081.8
5100.271 ± 0.06389.1
10200.932 ± 0.179120.7
20403.127 ± 0.093240.4
5010012.168 ± 2.6341059.2

Planning time includes all candidate rewards. MOVE is feasible up to 50 arrivals, but larger instances are costly.

W5: Negative payment regret and participation violations.

Negative payment regret over a finite horizon means cumulative expected payment is below the best fixed feasible benchmark. It does not imply that the participation target is met. Underestimated costs may reduce payment while creating a participation deficit. We report both:

Episodes TTPayment regret per episode RT/TR_T/TParticipation rate (%)Gap below required participation rate VTP/∑tAˉtV_T^P/\sum_t\bar A_tPayment per arrival ∑tCˉt/∑tAˉt\sum_t\bar C_t/\sum_t\bar A_t
1,000-0.026 ± 0.02039.08 ± 1.020.159 ± 0.0100.244 ± 0.007
2,0000.146 ± 0.01953.76 ± 0.900.012 ± 0.0090.304 ± 0.007
5,0000.100 ± 0.01156.14 ± 0.520.000 ± 0.0000.288 ± 0.004

For qmin⁡=55%q_{\min}=55\%, participation reaches 56.14% at 5,000 episodes, with zero deficit. After episode 1,000, a variant using feedback replans every ten episodes. This is empirical, not a new guarantee for the original algorithm. The theorem bounds average payment regret and participation violation under its assumptions.

W6: Motivation, contribution, and AI assistance.

MOVE's novelty is the joint treatment of reward, information disclosure, and network dynamics that depend on participation. This goes beyond simply combining Bayesian persuasion with an MDP. It learns the communication prior and transition kernel, proves that optimal induced posteriors need at most two communication conditions, and uses this structure for finite optimistic LP planning with regret and constraint violation bounds that hold with high probability. The AI statement discloses help with wording, grammar, and repetition removal. The authors reviewed the suggestions and made final content decisions.

Thank the authors for their work on revision. I still do not see a clear application space where the author's model of information asymmetry would make sense. Most of my concerns remain valid after the revision. Also perhaps partially due to the usage of AI, the writing of the paper is not clear. I'm keeping my score.

Thank you for reviewing our revision. In the revised manuscript, we added Section 3.3 to illustrate our information model through an example in which an edge service recruits mobile devices to train a shared model over a wireless network. The example works as follows.

  1. From past observations, the service learns how often each communication condition occurs and how network load changes after a device accepts or declines. (Online learning)

  2. Before devices arrive, the service sets the reward and decides what to disclose under each communication condition. (Reward and signal design)

  3. When a device arrives, both sides know the public network state x. Through the ETSI Radio Network Information API, the operator can let the edge service see how much of the cell’s uplink capacity is in use. In this deployment, the training app has no direct access to that measurement. The device may have strong radio reception even when the cell is busy. (Information asymmetry about the current condition τ\tau)

  4. The service sends a message based on the resource availability it observes. The device uses the message to estimate its upload cost and decides whether the offered reward is enough to participate. (Bayesian persuasion and participation)

  5. An upload can leave other traffic waiting. The next device may therefore be more likely to encounter congestion than if the current device had declined. (Markov state transition)

Reviewer_zQcTOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how a central server can encourage clients to help train a shared model while paying them as little as possible. The server offers each client a reward for participating. It also chooses what to tell the client about network conditions, which affect the cost of sending its model update. The MOVE method learns how the network behaves and chooses both rewards and messages. The main technical result simplifies the messages the server needs to consider: the authors also prove that, over time, excess spending and participation shortfalls become small on average under their assumptions. They test the method in simulations and on three federated-learning datasets.

Critical strengths

The paper studies a useful problem. Both the reward and the information a client receives can affect its decision to participate. Accounting for how that decision affects future network conditions makes the problem more realistic.

The paper also provides a clear mathematical basis for simplifying the server’s choices. This makes the proposed method possible to compute and supports its theoretical guarantees.

Critical weaknesses

There are three main issues that I find concerning:

The comparisons leave out key parts of competing methods. The authors test DaringFed without its ability to choose what information to reveal. They also remove important parts of L2I. These changes may make the competing methods weaker, so the results do not convincingly show that MOVE improves on the original methods. Its gains over the strongest tested competitor, Dynamic Pricing, are much smaller than the headline result. This probably needs to be revised to avoid overclaiming.

Lower spending is not enough if too few clients participate. In one main simulation, MOVE’s participation rate remains roughly 15 percentage points below the required level. Spending less while recruiting fewer clients does not clearly show a better method. The theory says this shortfall should shrink over time, but the experiments do not establish how long that takes. Comparing costs when all methods meet the same participation requirement would make the results more convincing.

The experiments leave scalability and realism unclear. The simulated network has only six states, three possible communication conditions, and each episode contains at most three client arrival, so it's a fairly small scalability tests. Since the method is designed to handle changing network conditions, testing larger networks and using measured network behavior would provide stronger evidence that it is useful in practice.

Questions for authors
  1. Can the authors justify the removal of signaling from DaringFed and the core components omitted from L2I, and provide comparisons preserving those mechanisms or explain why a faithful adaptation is infeasible?
  2. How do payment costs compare when MOVE and the baselines achieve the same participation level? In particular, how much additional training is needed for MOVE’s substantial participation deficit in Table 6 to disappear?
3 comments
AuthorsOpenReview ↗

Clarifying Baseline Fairness, Participation Shortfalls, and Scalability

We thank the reviewer for the feedback. In the revised version, we address Q1&W1 by clarifying the baselines in Appendix A.9.1 and adding the DaringFed signaling comparison in Section 6.3 (Table 4). The abstract and contribution statement replace 23.47% with mean target payment reductions of 3.54% to 10.13% after participation calibration. For Q2&W2, we add D0 continuation and participation calibration results in Sections 6.2 and 6.3 (Tables 3 and 5). For W3, we report scalability tests with larger configurations in Appendix A.9.6 (Table 13).

Q1&W1: Baseline Implementation and Fair Comparisons.

DaringFed. Our known participation response p(γ,κˉ)p(\gamma,\bar{\kappa}) requires no estimation, as in DaringFed's formulation with known responses. DaringFed assumes a known communication prior, whereas MOVE learns an unknown prior. We therefore report two variants:

DatasetMethodPayment at target accuracyParticipation rate (%)
FEMNISTDaringFed (uninformative signaling)1817.75 ± 84.8793.00
DaringFed (optimized signaling)1132.45 ± 73.4350.00
MOVE1094.55 ± 54.8658.12
CIFAR-10DaringFed (uninformative signaling)386.52 ± 48.2093.14
DaringFed (optimized signaling)229.30 ± 19.7650.00
MOVE230.20 ± 30.6758.83

Uninformative signaling uses conservative rewards to meet participation requirements without the true prior. Optimized signaling jointly sets reward and disclosure under a uniform prior. MOVE pays less on FEMNIST and 0.39% more on CIFAR-10, with higher participation on both datasets.

L2I. Its CUCB uses client quality estimates and confidence bonuses. Sequential arrivals permit only binary participation, not client subset or data quantity selection. In the calibration experiments, our reward policy comparator uses larger bonuses for states with fewer visits. Table 2 uses the fixed reward schedule.

Dynamic Pricing. We retain its increasing reward schedule and compensate for accumulated participation shortfalls within the common reward range under a fixed prior. In Table 2, MOVE reduces mean target payment versus Dynamic Pricing by 1.45% on FEMNIST and 6.37% on CIFAR-10.

Q2&W2: Payment comparisons and participation shortfalls

Methods share initialization, data partitions, client sampling, environments, and episode budgets. Each participant performs one local epoch and one server update. FEMNIST uses natural LEAF partitions. CIFAR-10 uses a classwise Dirichlet partition (α=0.3\alpha=0.3) across 20 clients. We calibrated participation to similar rates above 0.5 and compared cumulative payment and updates to target accuracy (80% for FEMNIST and 70% for CIFAR-10).

DatasetMethodParticipation rate (%)Payment to targetTraining updates to target
FEMNISTMOVE59.721185.62 ± 55.632313.4
DaringFed (optimized signaling)57.651254.91 ± 23.632339.0
L2I58.771243.54 ± 51.002290.2
Dynamic Pricing59.611313.41 ± 33.832357.2
CIFAR-10MOVE59.72244.67 ± 43.42477.4
DaringFed (optimized signaling)58.58260.27 ± 41.29477.8
L2I61.45253.64 ± 19.34455.0
Dynamic Pricing60.74272.26 ± 17.92479.6

At nearly matched participation, MOVE reduces payment over Dynamic Pricing by 9.73% (FEMNIST) and 10.13% (CIFAR-10). Updates differ by only 1.9% and 0.5%, so savings mainly reflect lower payment per update. Implied payment per update is about 8.0% and 9.7% lower. Fewer updates do not imply lower computational cost, as models and accuracy targets differ across datasets. All five FEMNIST DaringFed calibration seeds violate the cumulative Bayes benefit constraint.

We extended the D0 simulation from 1,000 to 5,000 episodes. After episode 1,000, a variant replans every ten episodes using observed feedback. The theoretical guarantees concern the original algorithm.

Episodes TTParticipation rate (%)Gap below required participation rate VTP/∑tAˉtV_T^P/\sum_t\bar A_tPayment per arrival ∑tCˉt/∑tAˉt\sum_t\bar C_t/\sum_t\bar A_t
1,00039.08 ± 1.020.159 ± 0.0100.244 ± 0.007
2,00053.76 ± 0.900.012 ± 0.0090.304 ± 0.007
5,00056.14 ± 0.520.000 ± 0.0000.288 ± 0.004

At 5,000 episodes, mean cumulative participation reaches 56.14%, above the required 55%. The normalized deficit falls from 0.159 to 0 while payment per arrival rises from 0.244 to 0.288.

W3: Scalability and the scope of practical validation

We extend the individual sweeps in Section 6.4 (Table 6) to larger configurations and joint expansion at h=0.05h=0.05.

Configuration(N,∣X∣,m)(N,\lvert X\rvert,m)Planning time per episode (s)Peak memory (MB)
Default(3,6,3)0.132 ± 0.02081.8
More arrivals(10,20,3)0.932 ± 0.179120.7
More states(3,24,3)2.831 ± 0.106339.7
More communication conditions(3,6,10)0.939 ± 0.244142.3
All three increased(8,24,10)16.258 ± 2.7381345.7

These experiments use simulated network dynamics. Evaluation with measured network traces remains future work.

Thank you for the revision. The new results address several of my concerns. I have a follow-up questions on comparison with baselines.

Restoring DarlingFed signaling closes much of the original gap, although it still uses a fixed uniform prior while MOVE learns the communication distribution. Would it make sense to let DaringFed estimate the prior using the same procedure as MOVE? If feasible, this would be a useful ablation to understand how much of the remaining gain comes from planning rather than learning the prior.

Please also clearly rectify the simplified implementations in Table 2, Figure 3, and the related discussion, and use Tables 4–5 as the main reference for comparison claims. The modified L2I baseline should likewise be labeled as an adaptation.

Thank you for taking the time to review our revision.

Why use a fixed prior for DaringFed?

DaringFed takes a public communication prior as input when optimizing rewards and signals. Since the true prior is unknown in our setting, we supplied a uniform prior and retained both mechanisms. This comparison evaluates DaringFed with a given prior and MOVE with a learned prior.

How do the methods compare after restoring signaling?

In Table 4, MOVE achieved higher participation than DaringFed on both datasets, with lower payment on FEMNIST and nearly the same payment on CIFAR-10. After participation calibration in Table 5, MOVE had the lowest mean payment to reach the target accuracy on both datasets.

What does the planning ablation show?

Full MOVE and w/o Markov use the same method to learn the communication prior. Full MOVE accounts for how a client’s participation affects the next network state, while w/o Markov uses the same transition model whether the client participates or not. Across the simulations in Section 6.2, full MOVE reduced the average participation shortfall per episode by 66.94% relative to w/o Markov.

How have we clarified the baseline comparisons?

We updated the labels in Tables 2, 5, and 11 and the caption of Figure 3 to distinguish the DaringFed signaling variants and identify L2I as an adapted baseline.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.