- Rating
- 2
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3(+1)
Read review
Paper summary
This paper studies capacity-constrained multi-agent bandits with a weighted -fair objective, mainly focusing on the case of . The authors first propose a centralized two-phase algorithm, providing a regret upper bound and a lower bound that matches the dependence on the time horizon and the minimum optimal utility up to a logarithmic factors. The paper then proposes a decentralized algorithm based on auctions and insertion gaps, reducing the number of auction calls.
Critical strengths
-
Strong theoretical guarantees for the non-Lipschitz setting. The paper addresses an important challenge in -fair multi-agent bandits. The proposed centralized algorithm combines adaptive exploration with a global elimination rule, which removes sub-optimal agent-arm pairs. Moreover, the paper provides both regret upper and lower bounds that match in their dependence on the time horizon and the minimum optimal utility up to logarithmic factors.
-
An interesting decentralized algorithm with efficient insertion-gap computation. The decentralized algorithm provides a useful technical contribution beyond the centralized analysis. The authors use auction dual prices and alternating-cycle computations to estimate insertion gaps through a shared procedure. This reduces the number of auction calls.
Critical weaknesses
-
The problem formulation limits the generality of the proposed approach, and the novelty could be better justified. Although the paper emphasizes the difficulty of combining capacity constraints with a nonlinear -fair objective, the objective becomes additive across agent-arm pairs under the assumed integral matching model. As a result, the offline problem reduces to a standard maximum-weight capacitated matching problem with transformed edge utilities. This makes the setting more structured than the paper's motivation may suggest. It would be better if the authors could explain the significance of this choice and clarify which technical contributions extend beyond this specific formulation.
-
The decentralized efficiency claims are not fully supported by the complexity analysis and experiments. The decentralized algorithm claims to require only auction calls, but the paper does not provide a complete analysis of communication costs or total computational complexity. In particular, the insertion-gap procedure still requires repeated message exchanges and computation per epoch. Therefore, fewer auction calls do not necessarily imply lower overall computational or communication costs. Moreover, the strongest regret guarantee assumes a unique optimal matching, while the general-instance result introduces a much larger regret term.
Questions for authors
-
Since each agent selects only one arm per round, the -fair objective can be written as a sum of transformed edge utilities. Could the authors clarify the main technical differences between the proposed method and standard combinatorial bandit algorithms applied to these transformed utilities?
-
The strongest guarantee for the decentralized algorithm requires a unique optimal matching. Can the proposed method be extended to cases with multiple optimal matchings? What are the main challenges?
6 comments
Response to Reviewer f7ET (Part 2/4)
Q2 & W2: Multiple optimal matchings.
Thanks for the comment. We establish the multiple-optimum guarantee in Section 4 and Appendix D.1.3, with experiments in Appendix E.2 of the revised paper.
We prove that the existing truncation jointly guarantees logarithmic regret and doubly logarithmic total main-auction calls on every fixed instance, including multiple optima. Here hides fixed parameters, not , and counts main auctions in both phases:
We use the existing truncation , with fixed : at , refreshing stops and the current main matching is replayed. Thus we avoid relying on freezing.
We define the smallest suboptimal complete-matching loss by
\delta_+=\min_{\substack{p\in\mathcal P,F_\alpha(p,\mu)<F^\ast}}[F^\ast-F_\alpha(p,\mu)].$$ Here $\mathcal P$ is the set of feasible complete matchings. Finiteness gives $\delta_+>0$ if a suboptimal matching exists. If every feasible matching is optimal, regret is zero. On the confidence event $\mathcal E$, with $\Pr(\mathcal E^c)\le5/T$, all optima survive and main or refresh losses are at most $3\varepsilon_q$ or $9\varepsilon_q$. Let $\mathcal A_0$ be the retained graph at the Phase-I stopping time $t_{\rm se}$ and $n_0=\min_{e\in\mathcal A_0}N_e(t_{\rm se})$, where $N_e(t)$ counts edge observations. For fixed $g\ge2$, we set $L_T=\log(MNT^2)$, $c_0=\sqrt3+\sqrt{9+3\sqrt3}$, $B=c_0^2u_{\rm se}^{1-2\alpha}L_T$, $n_q=n_0g^q$, $\varepsilon_q=\sqrt{B/n_q}$, $K=1+|\mathcal A_0|$, and $A_g=9(g-1)/(1-g^{-1/2})$, where $u_{\rm se}$ is the safe scale and $K$ bounds refresh matchings. A positive refresh loss requires $\delta_+\le9\varepsilon_q$, giving $n_q\le81B/\delta_+^2$. We sum $9K(g-1)\sqrt{Bn_q}$ geometrically to bound exploration by $9A_gKB/\delta_+$. Including final replay gives $$R_{\rm II}^{\rm trunc}(T)\le\frac{9A_gKB}{\delta_+}+C_{\delta_+,b},$$ where $C_{\delta_+,b}$ is a finite constant independent of $T$. Indeed, the replay loss is at most $3/H_T$, so the replay matching is optimal whenever $3/H_T<\delta_+$. Since $H_T=(\log T)^b$, positive replay loss is possible only over a bounded range of horizons, and its total contribution is uniformly bounded by $C_{\delta_+,b}$. Safe entry gives $B=O_{\rm inst}(\log T)$ and $K\le1+MN$. Adding logarithmic Phase-I regret and at most $5G_{\max}$ from confidence failures yields $$\mathbb E R(T)\le C_{1,\rm inst}\log T+C_{2,\rm inst}=O_{\rm inst}(\log T),$$ where both constants are independent of $T$ and $G_{\max}$ is the worst one-round loss. For auction calls, $n_0\ge9L_T/u_{\rm se}$ gives $B/n_0\le(c_0^2/9)u_{\rm se}^{2-2\alpha}=O_{\rm inst}(1)$, cancelling the logarithmic factors. Including the truncation auction, we obtain the Phase-II bound $$N_{\rm II}\le1+\max\\{0,\lceil\log_g(BH_T^2/n_0)\rceil\\}=O_{\rm inst}(1+\log\log T)$$ for main-auction calls. Phase I has the same order and confidence failures add $O(\log T/T)$ expected calls. **Thus, the existing truncation removes uniqueness from the joint guarantee without changing the geometric schedule.** In experiments, we evaluate truncation with $b=1/8$ on $M=8,N=5$ with **1,316 optima**. In **10/10 runs**, it truncates at $t=5{,}169{,}152$ with **zero later regret**. We record Phase-II regret 36,413.76±0.00, 6±0 calls and communication 42,765.6±23.2 units (mean ± sample SD).Response to Reviewer f7ET (Part 3/4)
W2: Communication and computational cost (Part 1).
Thanks for the comment. We provide the cost analysis in Section 4 and Appendices D.1.1 and D.2.3, with experiments in Appendix E.2 of the revised paper. Our method shares the main auction's dual prices to compute all insertion gaps jointly, avoiding a fresh constrained auction for each feasible non-selected edge. The comparison includes the main auction and the complete additional coordination work.
We count one scalar or index sent over one physical agent–arm link as one communication unit. An -entry vector therefore costs units per link. We include feasibility checks, preprocessing and restoration, auctions, shared propagation, path reconstruction, matching outputs, shrinking/freezing and scheduling controls. The agents and arms retain all links of the communication tree after statistical elimination: an eliminated allocation edge remains available for communication.
At epoch , is the active-edge count and counts edges outside the main matching. Ours runs one main auction. Per-edge additionally checks each non-selected edge and, when feasible, runs a constrained auction forcing that edge. Let count main-auction bids and count all Per-edge bids, including its main auction. An auction call can contain many bids, so we account for both. Both methods use increment , keeping auction approximation error within the confidence scale .
Writing for Phase-II communication and for computation at its coordination updates, we obtain
The first term in each bound covers gap processing and associated coordination. Ours sends -entry vectors over at most propagation sweeps, giving . Per-edge repeats feasibility and matching work for at most forced-edge problems, in addition to the main procedure. The bid terms charge price messages, synchronization, best/second-best selection and sorting. Comparing at most candidate matchings, each represented by arm indices, adds operations to retain one copy of each matching. Each sum uses that method's own executed epochs and graphs. Per-round reward-statistic updates add the common computation, separately from these coordination bounds, where is the Phase-I stopping time.
We also account explicitly for auction precision. Let be the largest within-agent range of scores over active edges. Then
\le A_q(\lfloor MV_q/\eta_q\rfloor+M).$$ A bidder's pre-bid price is at most $MV_q+(M-1)\eta_q$, and a repeat bid on the same arm follows a price increase of at least $\eta_q$. This bounds bids per agent–arm pair and hence per auction. Per-edge executes at most $U_q+1$ auctions, explaining the normalization above. Safe entry bounds $V_q$ on the confidence event. Summing the costs over the geometric precision schedule gives Phase-II communication $O_{\rm inst}(1+\log\log T)$ under uniqueness and $O_{\rm inst}(1+\log\log T+H_T)$ under truncation, where $H_T=(\log T)^b$, $b>0$. The hidden constants depend on fixed instance parameters, not $T$.
Response to Reviewer f7ET (Part 1/4)
Thank you for your constructive comments. We have included the following discussions in the revised paper, with changes marked in blue.
Q1 & W1: Problem formulation and contributions.
Thanks for the comment. We clarify the modeling rationale and learning contributions in Sections 1–3.
We consider resource allocation in which each agent receives one resource per round and each resource can serve only a limited number of agents, as with shared channels or servers. An integral matching represents these assignments and capacity limits directly. We evaluate fairness on agents' expected rewards, as in welfare-based bandit formulations [1], and model shared resources with finite capacity, motivated by [2].
We agree that, when the means are known, our problem reduces to a maximum-weight capacitated matching problem. For an integral matching, Fα(p,μ)=∑m,npmnwmUα(μmn). We can assign weight wmUα(μmn) to each edge and solve the known-mean problem by matching. This gives a tractable benchmark for learning.
Our contribution lies in achieving no-regret learning for the non-Lipschitz α>1 objective with unknown reward means under capacity constraints, rather than in solving the known-mean offline matching problem. Although the known-mean objective is additive, learning its edge values requires controlling estimation error under a non-Lipschitz utility function. For α>1, Uα′(x)=x−α diverges near zero, so small errors in the estimated means can produce large utility errors. Capacity constraints can also force small utilities at the optimum. The core learning challenge is to identify a safe scale from data and control this sensitivity while preserving optimal matchings under capacity constraints.
We address this challenge through data-driven stopping and global elimination. We certify a positive lower bound μ(t)≤μmin∗ from the lower-confidence matching value and require every edge sample count Nmn(t)≥30log(MNT2)/μ(t) before entering Phase II. We then compare each edge's upper objective bound with a feasible lower objective bound to remove sufficiently poor edges while preserving optimal edges under capacity constraints. On the confidence event, surviving means are bounded below by a constant multiple of μmin∗, allowing UCB learning in a Lipschitz regime.
The method in [1] also addresses a non-Lipschitz objective, but its small-utility analysis uses NSW's nonnegativity and boundedness in [0,1]. In our problem, Uα(x)→−∞ as x→0, and capacities can force small utilities even at the optimum. Thus the method in [1] is inapplicable.
To quantify the distinction from a direct full-graph UCB analysis, we specialize Corollary 4 of [3]. Let μall,min=minm,nμmn and let Gmax be the worst one-round exploratory loss. For a candidate mean matrix x=(xmn), ∂mnFα(p,x)=pmnwmxmn−α. Under uniform weights this gives the variance-weighted gradient bound Γg≤M−1/2μall,min1/2−α and coordinate-derivative bound Γ∞≤M−1μall,min−α. For this analysis, we continue Uα linearly below μall,min. Since UCBmn(t)≥μmn≥μall,min on the confidence event, this gives finite constants without changing true or optimistic matching values. We obtain
+N\mu_{\mathrm{all,min}}^{-\alpha}+MN G_{\max}),$$ whereas our algorithm yields $$\widetilde O(\Delta_{\rm cov}G_{\max}/\mu_{\min}^\ast +(\mu_{\min}^\ast)^{1/2-\alpha}\sqrt{NT}).$$ We illustrate these scales using $\mu=\begin{pmatrix}2u&u ; 2u&\epsilon\end{pmatrix}$, unit capacities, equal weights and $0<\epsilon<u\le1/2$. The unique optimum assigns $(u,2u)$, so $\mu_{\min}^\ast=u$ stays fixed while $\mu_{\mathrm{all,min}}=\epsilon\rightarrow0$. Agent 1 must retain its locally inferior $u$ edge to leave arm 1 to agent 2. Our global elimination preserves this optimum while removing sufficiently poor edges. **The resulting learning term uses the optimal-utility scale $\mu_{\min}^\ast$ rather than $\mu_{\mathrm{all,min}}$, and our lower bound matches its $T$ and $\mu_{\min}^\ast$ dependence up to logarithmic factors.** [1] Mengxiao Zhang, Ramiro Deo-Campo Vuong, and Haipeng Luo. No-Regret Learning for Fair Multi-Agent Social Welfare Optimization. NeurIPS 2024. [2] Xuchuang Wang, Hong Xie, and John C. S. Lui. Multiple-Play Stochastic Bandits with Shareable Finite-Capacity Arms. ICML 2022. [3] Nadav Merlis and Shie Mannor. Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem. COLT 2019.