Research map / Bandits and online learning / Multi-armed bandits
Decentralized Scheduling with QoS Constraints: Achieving O(1) QoS Regret of Multi-Player 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 AdeQoS, a decentralized multi-player bandit algorithm (exploration, forced-collision communication, and consensus via randomized BvN matching) that guarantees each player's QoS constraint with O(1) QoS regret, and links QoS to queue stability.
Problem
Decentralized multi-player multi-armed bandits where players cannot observe others' actions or rewards and must each meet a predetermined expected average reward (QoS) rather than maximize total reward.
Approach
Players compute a doubly stochastic matrix via a log-barrier strongly convex dominant mapping, decompose it with Birkhoff-von Neumann into permutation matrices driven by shared time-index randomness for collision-free round-robin play, and use forced-collision signaling plus a consensus phase to agree on the matrix and verify QoS feasibility.
Key results
- AdeQoS, given a known capacity lower bound, achieves bounded (O(1)) QoS regret for all players, with R(T) ≤ O(K^3 + N^3K^2 + N^4K e^{16/Δ²}/Δ^8).
- The unknown-capacity variant A2deQoS achieves O(log T) QoS regret, with R(T) ≤ O(K^3 + N^2K log T log log T + N^3K^2 + e^{8/Δ²}/Δ²).
- AdeQoS guarantees strong stability (bounded expected queue length) of the corresponding wireless queuing system.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use A2deQoS without prior knowledge of ∆ and omit the signaling procedure (ablation) | AdeQoS · MP-MAB | QoS regret: O(1) -> O(log T) | Mixed |
| Use A2deQoS without prior knowledge of ∆ (ablation) | AdeQoS · Wireless queuing system | queue stability | Mixed |
Surprising findings
- Algorithms achieving sublinear QoS regret can stabilize the analogous queuing system, but the converse does not hold: queue-stabilizing algorithms may fail to give sublinear QoS regret.
Limitations
- Exponential dependence on the capacity margin Δ (e^{16/Δ²}) in the regret bound; authors state tighter analysis is future work.
- Requires shared randomness via synchronized time index, all players starting at the same time, and a static arm-mean assumption.
- Requires knowing a lower bound on capacity Δ for O(1) regret; without it only O(log T) regret is achieved.
Experimental setup
Metrics: QoS regret queue length stability
Baselines: fairness-based MP-MAB algorithms sum-of-rewards MP-MAB algorithms
Builds on: Birkhoff von Neumann decomposition log-barrier method alpha-fairness
Closest papers by meaning
- Queue Up Your Regrets: Achieving the Dynamic Capacity Region of Multiplayer Bandits (NeurIPS 2022 · similarity 0.89)
- Optimal Algorithm for Max-Min Fair Bandit (ICML 2025 · similarity 0.88)
- Delay as Payoff in MAB (AAAI 2025 · similarity 0.87)
- Improved Regret Bounds for Online Fair Division with Bandit Learning (AAAI 2025 · similarity 0.86)
- Queueing Matching Bandits with Preference Feedback (NeurIPS 2024 · similarity 0.86)
- Honor Among Bandits: No-Regret Learning for Online Fair Division (NeurIPS 2024 · similarity 0.86)
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.