Research map / Bandits and online learning / Online convex optimization and games
Improved Regret Bounds for Online Fair Division with Bandit Learning
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.
Gives a UCB algorithm for online fair division with unknown item-value means that achieves about O~(sqrt(T)) regret while keeping proportionality in expectation with high probability, improving on the prior O~(T^{2/3}) explore-then-commit rate.
Problem
Online fair division of indivisible items of random types to players with unknown stochastic values, requiring proportionality in expectation at every step while maximizing expected utilitarian welfare (minimizing regret against the fair optimum that knows the means).
Approach
A UCB algorithm that uses two rounds of linear programming: the first finds an allocation that is proportional for all plausible mean matrices in the confidence set, and the second solves per-(player,item) LPs to ensure sufficient exploration of each pair while keeping welfare close to the optimum; averaging these yields an allocation that supports a UCB regret argument.
Key results
- Algorithm achieves O~(n^5 m^3 sqrt(T)) regret with probability 1-1/T while satisfying proportionality in expectation constraints (normalized values, bounded means).
- Improves the previous best regret rate from O~(T^{2/3}) to O~(sqrt(T)) for proportionality in expectation.
- Shows envy-freeness in expectation under normalized values requires Omega~(T^{2/3}) regret, so the sqrt(T) rate does not extend to envy-freeness.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use two-round UCB optimization with initial UAR exploration instead of explore-then-commit | Online fair division with proportionality in expectation · Online fair division, proportionality in expectation | regret: \tilde{O}(T^{2/3}) to \tilde{O}(n^5m^3\sqrt{T}) | Helped |
| Require envy-freeness in expectation rather than proportionality in expectation | Online fair division with normalized values · Online fair division, envy-freeness in expectation | regret: \frac{T^{2/3}}{\log(T)} | Hurt |
Surprising findings
- Envy-freeness in expectation cannot achieve sqrt(T) regret under normalized values, unlike proportionality.
Limitations
- Runtime is exponential in n and m because of the second optimization round.
- Result is stated only for proportionality; extension to other fairness notions such as equitability is open.
- Regret bound has large polynomial dependence on n and m (n^5 m^3).
Experimental setup
Metrics: regret proportionality in expectation satisfaction
Baselines: explore-then-commit algorithm for online fair division
Builds on: explore-then-commit fair division (prior work) upper confidence bound bandits bandits with linear safety constraints
Closest papers by meaning
- Honor Among Bandits: No-Regret Learning for Online Fair Division (NeurIPS 2024 · similarity 0.95)
- Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies (ICML 2026 · similarity 0.92)
- Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility (AAAI 2024 · similarity 0.90)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.89)
- Greedy-Based Online Fair Allocation with Adversarial Input: Enabling Best-of-Many-Worlds Guarantees (AAAI 2024 · similarity 0.89)
- Improved Analysis for Bandit Learning in Matching Markets (NeurIPS 2024 · similarity 0.88)
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.