Research map / Federated learning and privacy / Communication-efficient FL
Incentivized Truthful Communication for Federated Bandits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Truth-FedBan, a truthful incentivized communication protocol for federated linear bandits that uses a monotone greedy client selection with critical-value payments, keeping sub-linear regret and near-optimal social cost.
Problem
Incentivized communication in federated bandits assumes clients report costs truthfully, so strategic clients can profit by misreporting; the paper seeks mechanisms that are truthful and individually rational while keeping near-optimal regret, communication, and social cost.
Approach
Decouple each client's incentive from its own reported cost by using a monotone submodular set-cover selection rule with critical-value payments (Myerson-style characterization), so reporting true cost is a dominant strategy while regret and communication bounds are preserved.
Key results
- Truth-FedBan achieves sub-linear regret O(d sqrt(T) log T) and communication cost O(N^2 d^3 log T), matching the non-truthful Inc-FedUCB/DisLinUCB bounds.
- Theory gives a bi-criteria approximation: social cost within (1+epsilon) of optimal while the constraint is met up to factor (1-e^{-1}).
- Micro-level experiments show misreporting does not increase a single client's utility under Truth-FedBan; macro-level experiments show collusion can raise incentive costs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a monotone participant-selection rule with critical-value payments independent of the target client's report | Truth-FedBan · Federated contextual linear bandits | truthfulness | Helped |
| Use Truth-FedBan instead of Inc-FedUCB | Federated contextual linear bandits · Federated contextual linear bandits | regret: $O(d\sqrt{T} \log T)$ -> $O(d\sqrt{T} \log T)$ | No clear effect |
| Use Truth-FedBan instead of Inc-FedUCB | Federated contextual linear bandits · Federated contextual linear bandits | communication cost: $O(N^{2} d^3\log T)$ -> $O(N^{2} d^3\log T)$ | No clear effect |
| Use Truth-FedBan instead of Inc-FedUCB | Federated contextual linear bandits · Federated contextual linear bandits | incentive compatibility | Helped |
| Use Truth-FedBan instead of Inc-FedUCB | Federated contextual linear bandits · Federated contextual linear bandits | social cost guarantee | Helped |
| Over-report participation cost | Truth-FedBan · Simulated federated bandits, individual client | utility | No clear effect |
| Under-report participation cost | Truth-FedBan · Simulated federated bandits, individual client | utility | Hurt |
| Over-report participation cost | Vanilla greedy incentive mechanism · Simulated federated bandits, individual client | utility | Helped |
| Increase the fraction of clients misreporting | Truth-FedBan · Simulated federated bandits, whole system | regret | No clear effect |
| Increase the fraction of clients under-reporting | Truth-FedBan · Simulated federated bandits, whole system | communication cost | Hurt |
| Increase the fraction of clients over-reporting | Truth-FedBan · Simulated federated bandits, whole system | communication cost | Helped |
| Increase the fraction of clients misreporting | Truth-FedBan · Simulated federated bandits, whole system | social cost | Mixed |
Surprising findings
- Over-reporting cost by a single client slightly increased its utility under the vanilla greedy mechanism, attributed to reduced participation cost.
- When a large fraction of clients misreport, incentive costs rise because collusion forces higher critical values, exposing a vulnerability to collusion.
Limitations
- Truthfulness is proven per round; long-term strategic behavior (e.g., over-reporting to become a monopoly) is not addressed.
- Assumes clients are non-malicious and the server is committed to honest payments; collusion vulnerability is observed empirically.
- Bi-criteria approximation relaxes the participation constraint by a factor (1-e^{-1}), and the no-monopoly elimination requires a conservative beta.
Experimental setup
Datasets: simulated federated linear bandit environment
Benchmarks: simulated federated linear bandit environment
Metrics: cumulative regret communication cost incentive cost social cost client utility under misreporting
Baselines: DisLinUCB Inc-FedUCB vanilla greedy incentive mechanism
Builds on: DisLinUCB Inc-FedUCB Myerson monotone characterization of truthful mechanisms submodular set cover greedy
Closest papers by meaning
- Incentivized Communication for Federated Bandits (NeurIPS 2023 · similarity 0.95)
- Communication-Efficient Federated Non-Linear Bandit Optimization (ICLR 2024 · similarity 0.89)
- Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users (AAAI 2024 · similarity 0.87)
- Federated X-armed Bandit (AAAI 2024 · similarity 0.87)
- FACT or Fiction: Can Truthful Mechanisms Eliminate Federated Free Riding? (NeurIPS 2024 · similarity 0.86)
- On Differentially Private Federated Linear Contextual Bandits (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.