Research map / Federated learning and privacy / Communication-efficient FL

Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users

AAAI 2024 · Federated learning and privacy › Communication-efficient FL · approach: Communication-efficient heterogeneous FL · 6 citations (OpenAlex)

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 FedC3UCB-H, a UCB-based federated contextual combinatorial cascading bandit algorithm with asynchronous agent-server communication and server-side graph-based user clustering for heterogeneous users, achieving O(d√(JKT) log T) regret with logarithmic communication.

Problem

Federated contextual combinatorial cascading bandits where each user has its own agent, users belong to J unknown preference clusters, and agents communicate asynchronously with a central server, so the goal is low regret with low communication cost.

Approach

Combines a determinant-based communication trigger with a randomized p_t-auxiliary communication rule (p_t = 3 log t / t) and server-side edge-deletion heterogeneity testing on a user graph, so agents asynchronously share data only with the users in their estimated cluster while keeping communication logarithmic in T.

Key results

• On synthetic J=10, FedC3UCB-H reduces regret by 82% vs FedLinUCB and 64% vs FedInd.
• On Yelp (J=10), FedC3UCB-H reduces regret by 67% vs FedLinUCB and 5% vs NoAuxiliary.
• Theory: regret O(d√(JKT) log T) with communication O(d|U| log T + log^2 T).

Measured effects reported in the paper

Surprising findings

• FedLinUCB has lower communication cost than FedC3UCB-H in the experiments (e.g., 479.7 vs 818.3 on synthetic J=5), since the auxiliary communication adds cost.

Limitations

• Regret has an O(sqrt(dK)) gap to the lower bound and communication has an O(d|U|) gap to the known lower bound.
• Assumes linear reward structure; non-linear structures or model misspecification are not handled.
• Some communication overhead: FedC3UCB-H communicates more than FedLinUCB and NoAuxiliary in experiments.

Experimental setup

Datasets: Yelp synthetic linear bandit data

Benchmarks: synthetic cascading bandit environment Yelp

Metrics: cumulative regret communication cost user clustering error rate

Baselines: FedLinUCB FedInd NoAuxiliary ForceComm CLUB-cascade DisLinUCB

Builds on: CLUB-cascade FedLinUCB CascadeLinUCB DisLinUCB

Closest papers by meaning

• Federated Combinatorial Multi-Agent Multi-Armed Bandits (ICML 2024 · similarity 0.89)
• On Differentially Private Federated Linear Contextual Bandits (ICLR 2024 · similarity 0.88)
• Federated X-armed Bandit (AAAI 2024 · similarity 0.88)
• Communication-Efficient Federated Non-Linear Bandit Optimization (ICLR 2024 · similarity 0.87)
• Incentivized Truthful Communication for Federated Bandits (ICLR 2024 · similarity 0.87)
• Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks (NeurIPS 2025 · similarity 0.87)