Research map / Bandits and online learning / Online convex optimization and games
Queueing Matching Bandits with Preference Feedback
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 UCB- and Thompson-sampling-based MaxWeight algorithms for multi-class multi-server queues where servers choose among assigned jobs via a feature-based MNL preference model, proving queue stability and sublinear regret.
Problem
Stabilizing multi-queue multi-server systems when job-server service rates are unknown and depend on servers' stochastic (MNL) preferences over the set of jobs assigned to them, learned from preference feedback.
Approach
Model service rates as a feature-based MNL choice function over the assortment of agents assigned to each server, and combine MaxWeight scheduling with UCB or Thompson-sampling estimates of server preferences learned via online Newton steps, giving both queue stability and regret bounds.
Key results
- UCB-QMB and TS-QMB achieve stability with average queue length O(min{N,K}/epsilon), matching the known-parameter MaxWeight oracle asymptotically.
- Regret bounds of Otilde(min{sqrt(T) Q_max, T^{3/4}}) for the proposed algorithms, while baselines show superlinear regret in experiments due to growing queues.
- Experiments on synthetic instances (N=4, K=2, L=2, d=2) show the proposed algorithms outperform Q-UCB, DAM-UCB, MaxWeight-UCB and ETC-GS, except the oracle.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use UCB-QMB instead of previously suggested queueing-bandit and matching-bandit methods | Queueing matching bandits · Synthetic queueing system | average queue length | Helped |
| Use TS-QMB instead of previously suggested queueing-bandit and matching-bandit methods | Queueing matching bandits · Synthetic queueing system | regret | Helped |
| Use UCB-QMB or TS-QMB rather than the known-service-rate MaxWeight oracle | Queueing matching bandits · Synthetic queueing system | average queue length | No clear effect |
Limitations
- Constant depends on kappa with 1/kappa = O(L^2) worst case; dependence on kappa not optimal.
- No lower bounds for queue length or regret are established.
- Combinatorial MaxWeight optimization is NP-hard in general, requiring approximation oracles.
Experimental setup
Datasets: synthetic
Benchmarks: synthetic queueing simulation (N=4, K=2, L=2, d=2)
Metrics: average queue length cumulative regret
Baselines: Q-UCB DAM-UCB MaxWeight-UCB ETC-GS MaxWeight oracle with known parameters
Builds on: MaxWeight MNL bandits queueing bandits online newton step
Closest papers by meaning
- Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret (NeurIPS 2026 · similarity 0.89)
- Decentralized Scheduling with QoS Constraints: Achieving O(1) QoS Regret of Multi-Player Bandits (AAAI 2024 · similarity 0.86)
- Stochastic Matching Bandits with Rare Optimization Updates (NeurIPS 2026 · similarity 0.85)
- Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets (NeurIPS 2025 · similarity 0.85)
- Reinforcement Learning and Regret Bounds for Admission Control (ICML 2024 · similarity 0.84)
- Nearly Minimax Optimal Regret for Multinomial Logistic Bandit (NeurIPS 2024 · similarity 0.84)
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.