Research map / Bandits and online learning / Multi-armed bandits
Optimal Algorithm for Max-Min Fair Bandit
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 a decentralized fair elimination (DFE) algorithm for max-min fair multi-player bandits with heterogeneous rewards and collisions, achieving O((N^2+K) log T/Δ) regret and a matching Ω(max{N^2,K} log T/Δ) lower bound.
Problem
Max-min fair matching in decentralized heterogeneous multi-player multi-armed bandits with collisions, where the goal is to maximize the reward of the worst-off player and prior regret bounds were O(log T log log T) with large constants.
Approach
Phased elimination in which players share UCB/LCB estimates, compute the max-min LCB matching, eliminate player-arm pairs that cannot belong to a max-min matching, and then explore only remaining pairs using a new assignment scheme that covers them in about N^2+K rounds without selecting eliminated pairs.
Key results
- DFE attains regret upper bound O((N^2+K) log T/Δ), improving prior O(exp(1/Δ)+K^3 log T log log T).
- Matching lower bound Ω(max{N^2,K} log T/Δ) shows the algorithm is optimal in N, K, Δ, and T.
- In experiments, DFE's regret is reduced by more than 90% relative to My Fair Bandit and more than 80% relative to Leshem (2025) across three settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DFE instead of My Fair Bandit | Max-min MP-MAB · (4, 4), (10, 10), and (10, 15) settings | cumulative regret: more than 90% | Helped |
| Use DFE instead of the Leshem algorithm | Max-min MP-MAB · (4, 4), (10, 10), and (10, 15) settings | cumulative regret: more than 80% | Helped |
| Eliminate sub-optimal player-arm pairs instead of continuing phased explore-then-commit exploration | DFE · Max-min MP-MAB | regret upper bound: O(log T log log T) -> O((N 2 + K) log T/∆) | Helped |
Limitations
- Assumes each pair of players can exchange one arm's estimate in one round with regret up to γ*; the bit-wise alternative adds a log(1/Δ) factor.
- Regret is only analyzed for the decentralized setting with an index-search preliminary; the robustness and incentive compatibility are left open.
- Lower bound holds for a specific constructed instance with Bernoulli rewards and minimum gap Δ < 1/N.
Experimental setup
Benchmarks: simulated MP-MAB instances with (N,K) = (4,4), (10,10), (10,15), T=500,000
Metrics: cumulative regret
Baselines: My Fair Bandit (Bistritz et al., 2020) Leshem (2025)
Builds on: Bistritz et al. (2020) max-min MP-MAB Leshem (2025) max-min fair bandit Panagiotas et al. (2023) threshold-based max-min matching Boursier & Perchet (2019) communication via collisions
Closest papers by meaning
- Decentralized Scheduling with QoS Constraints: Achieving O(1) QoS Regret of Multi-Player Bandits (AAAI 2024 · similarity 0.88)
- Improved Regret Bounds for Online Fair Division with Bandit Learning (AAAI 2025 · similarity 0.88)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.88)
- Honor Among Bandits: No-Regret Learning for Online Fair Division (NeurIPS 2024 · similarity 0.87)
- Pairwise Elimination with Instance-Dependent Guarantees for Bandits with Cost Subsidy (ICLR 2025 · similarity 0.87)
- Stochastic Matching Bandits with Rare Optimization Updates (NeurIPS 2026 · similarity 0.87)
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.