acceptodds
Under review as a conference paper at ICLR 2027

No-Regret Learning for Capacity-Constrained -Fair Multi-Agent Bandits

Abstract

We study stochastic multi-agent bandits with finite arm capacities and a weighted -fair objective. The capacity-coupled matching action space and the non-Lipschitz objective near zero make standard upper confidence bound (UCB) analysis inapplicable. We propose a centralized two-phase cover-elimination-UCB algorithm that adaptively identifies a safe scale and uses a global elimination rule to remove certifiably poor base-arms while preserving optimal ones, thereby entering a Lipschitz regime. We derive a two-term regret upper bound, consisting of a capacity-coupled screening term for near-zero bad base-arms and a learning term in the safe Lipschitz regime, and establish a lower bound matching the - and -dependence up to logarithmic factors. We then develop a low auction-call complexity decentralized algorithm based on geometric shrinking, utilizing dual prices from a decentralized auction to compute forced-insertion gaps through augmented alternating cycles. Experiments demonstrate the effectiveness of our algorithms.

Primary area:
learning theory
Keywords:
Multi-armed bandit, UCB, $\alpha$-fair utility

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_f7ETOpenReview ↗
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 α\alpha-fair objective, mainly focusing on the case of α>1\alpha > 1. 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
  1. Strong theoretical guarantees for the non-Lipschitz setting. The paper addresses an important challenge in α\alpha-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.

  2. 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
  1. 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 α\alpha-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.

  2. The decentralized efficiency claims are not fully supported by the complexity analysis and experiments. The decentralized algorithm claims to require only O(log⁡log⁡T)O(\log\log T) 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 O(M2∣Aq∣)O(M^2|A_q|) 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
  1. Since each agent selects only one arm per round, the α\alpha-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?

  2. 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
AuthorsOpenReview ↗

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)F_\alpha(p,\mu)=\sum_{m,n}p_{mn}w_mU_\alpha(\mu_{mn}). We can assign weight wmUα(μmn)w_mU_\alpha(\mu_{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\alpha>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\alpha>1, Uα′(x)=x−αU'_\alpha(x)=x^{-\alpha} 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⁡∗\underline\mu(t)\le\mu_{\min}^\ast from the lower-confidence matching value and require every edge sample count Nmn(t)≥30log⁡(MNT2)/μ‾(t)N_{mn}(t)\ge30\log(MNT^2)/\underline\mu(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⁡∗\mu_{\min}^\ast, 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][0,1]. In our problem, Uα(x)→−∞U_\alpha(x)\to-\infty as x→0x\rightarrow0, 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=min⁡m,nμmn\mu_{\mathrm{all,min}}=\min_{m,n}\mu_{mn} and let Gmax⁡G_{\max} be the worst one-round exploratory loss. For a candidate mean matrix x=(xmn)x=(x_{mn}), ∂mnFα(p,x)=pmnwmxmn−α\partial_{mn}F_\alpha(p,x)=p_{mn}w_mx_{mn}^{-\alpha}. Under uniform weights this gives the variance-weighted gradient bound Γg≤M−1/2μall,min1/2−α\Gamma_g\le M^{-1/2}\mu_{\mathrm{all,min}}^{1/2-\alpha} and coordinate-derivative bound Γ∞≤M−1μall,min−α\Gamma_\infty\le M^{-1}\mu_{\mathrm{all,min}}^{-\alpha}. For this analysis, we continue UαU_\alpha linearly below μall,min\mu_{\mathrm{all,min}}. Since UCBmn(t)≥μmn≥μall,min\mathrm{UCB}_{mn}(t)\ge\mu_{mn}\ge\mu_{\mathrm{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.
AuthorsOpenReview ↗

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 OinstO_{\rm inst} hides fixed parameters, not TT, and Nauc(T)N_{\rm auc}(T) counts main auctions in both phases:

ER(T)=Oinst(log⁡T),ENauc(T)=Oinst(1+log⁡log⁡T).\boxed{\mathbb E R(T)=O_{\rm inst}(\log T),\mathbb E N_{\rm auc}(T)=O_{\rm inst}(1+\log\log T).}

We use the existing truncation HT=(log⁡T)bH_T=(\log T)^b, with fixed b>0b>0: at εq≤1/HT\varepsilon_q\le1/H_T, 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).
AuthorsOpenReview ↗

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 MM-entry vector therefore costs MM units per link. We include feasibility checks, preprocessing and restoration, auctions, shared propagation, path reconstruction, matching outputs, shrinking/freezing and scheduling controls. The MM agents and NN arms retain all S=M+N−1S=M+N-1 links of the communication tree after statistical elimination: an eliminated allocation edge remains available for communication.

At epoch qq, AqA_q is the active-edge count and Uq=Aq−MU_q=A_q-M 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 Bq\mathcal B_q count main-auction bids and Bqper\mathcal B_q^{\rm per} 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 ηq=ϵauc,q=εq/M\eta_q=\epsilon_{\rm auc,q}=\varepsilon_q/M, keeping auction approximation error within the confidence scale εq\varepsilon_q.

Writing WIIW_{\rm II} for Phase-II communication and CII\mathcal C_{\rm II} for computation at its coordination updates, we obtain WIIshared=O(∑q[M2(Aq+S)+(Aq+S)Bq]),W_{\rm II}^{\rm shared}=O(\sum_q[M^2(A_q+S)+(A_q+S)\mathcal B_q]), WIIper=O(∑q[(Uq+1)M(Aq+S)+(Aq+S)Bqper]),W_{\rm II}^{\rm per}=O(\sum_q[(U_q+1)M(A_q+S)+(A_q+S)\mathcal B_q^{\rm per}]), CIIshared=O(∑q[M2(Aq+S)+M(Uq+1)2+(Aqlog⁡(2M)+S)Bq]),\mathcal C_{\rm II}^{\rm shared}=O(\sum_q[M^2(A_q+S)+M(U_q+1)^2+(A_q\log(2M)+S)\mathcal B_q]), CIIper=O(∑q[(Uq+1)M(Aq+S)+M(Uq+1)2+(Aqlog⁡(2M)+S)Bqper]).\mathcal C_{\rm II}^{\rm per}=O(\sum_q[(U_q+1)M(A_q+S)+M(U_q+1)^2+(A_q\log(2M)+S)\mathcal B_q^{\rm per}]).

The first term in each bound covers gap processing and associated coordination. Ours sends MM-entry vectors over at most MM propagation sweeps, giving M2(Aq+S)M^2(A_q+S). Per-edge repeats O(M(Aq+S))O(M(A_q+S)) feasibility and matching work for at most UqU_q 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 Uq+1U_q+1 candidate matchings, each represented by MM arm indices, adds O(M(Uq+1)2)O(M(U_q+1)^2) 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 O(M(T−tse))O(M(T-t_{\rm se})) computation, separately from these coordination bounds, where tset_{\rm se} is the Phase-I stopping time.

We also account explicitly for auction precision. Let VqV_q be the largest within-agent range of scores wmUα(UCBmn)w_mU_\alpha(\mathrm{UCB}_{mn}) 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$.
Reviewer_FYGnOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies a stochastic multi-agent multi-armed bandit in which arms have finite capacities and the system maximizes a weighted α-fair utility, focusing on the regime α>1\alpha > 1 where the utility is non-Lipschitz near zero and near-zero utilities are structurally unavoidable even in the optimal matching. The core contribution is a centralized two-phase cover-elimination-UCB algorithm that adaptively identifies a safe scale, globally eliminates certifiably poor base-arms while preserving optimal ones, and then runs UCB in a Lipschitz regime, with a regret upper bound and a lower bound matching in the horizon and in the minimal optimal utility up to logarithmic factors. The paper also gives a decentralized algorithm that computes all forced-insertion gaps from a single auction's dual prices through augmented alternating cycles, cutting auction calls to doubly logarithmic. Validation is numerical: cumulative-regret curves for the centralized method against several baselines, and auction-call comparisons for the decentralized method.

Critical strengths
  1. Combining capacity constraints with α>1\alpha > 1, where the utility is negative and unbounded near zero, moves beyond prior fair-bandit work that stays in the regime 0≤α<10 \le \alpha < 1, adds reward floors, or exploits the boundedness of Nash-welfare objectives. The paper argues convincingly that near-zero utilities are unavoidable even in the offline optimum, so the difficulty is structural rather than a corner case. Posing this problem sharply is itself a real contribution.

  2. The two-phase design confronts the non-Lipschitz difficulty directly: uniform cover exploration, estimate-dependent confidence radii, a data-driven safe scale, and a global elimination rule that provably spares optimal base-arms while certifying poor ones. The resulting bound O~(Δ(M×N) Gmax⁡/μmin⁡⋆+(μmin⁡⋆)1/2−αNT)\widetilde{O}\big(\Delta(M \times N)\, G_{\max}/\mu^\star_{\min} + (\mu^\star_{\min})^{1/2-\alpha} N\sqrt{T}\big) is matched, in TT and in the minimum optimal utility, by a lower bound, which is exactly the kind of guarantee this problem calls for. The decentralized insertion-gap mechanism is a creative extra, even though its guarantees are narrower.

Critical weaknesses
  1. The experiments amount to a few cumulative-regret plots for the centralized method and auction-call counts for the decentralized method, with no repeated runs, error bars, or cross-seed variance, and no sensitivity analysis for the algorithmic constants (the stopping scale, the growth factor, the checkpoint schedule). For a paper that advertises experimental validation, this is a modest base, and it is hard to judge how robust the reported gains are, especially the dramatic auction-call reduction in the decentralized studies.

  2. The decentralized phase is barely developed in the main text, and much of its correctness analysis is confined to the appendix, which makes the work hard to verify and forces the reader to trace several nested appended routines. The doubly logarithmic auction-call claim is only proved under a unique-optimal-matching regime, with a truncation variant needed otherwise, and there is no lower bound for the auction-call/regret tradeoff, so a headline claim rests partly on the thin experiments.

Questions for authors
  1. Clarification: the decentralized regret bound is instance-dependent, summing inverse insertion gaps, and carries no explicit horizon factor, whereas the centralized bound has a T\sqrt{T} term. On the hard instances from the centralized lower bound, how do these two compare, and is there a matching lower bound for the decentralized auction-call/regret tradeoff?

  2. Clarification (experimental): the figures show single cumulative-regret runs. How much do these curves vary across seeds, and how were the algorithmic constants chosen? Error bars or a variance table would strengthen the conclusions.

  3. Suggestion for future work: would the framework extend naturally to time-varying capacities or drifting means, which the conclusion mentions, and what would change in the analysis?

6 comments
AuthorsOpenReview ↗

Response to Reviewer FYGn (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 & W2: Comparison on the hard family and auction-call/regret lower bound.

Thanks for the comment. We provide the hard-family comparison and auction-budget lower bound in Section 4 and Appendix D.1.4 of the revised paper.

  1. Comparison on the centralized hard family.

We evaluate decentralized insertion gaps on the centralized hard family with α>1\alpha>1, N≥4N\ge4, M=⌊N/2⌋M=\lfloor N/2\rfloor, Kh=N−MK_h=N-M arms of capacity MM, MM unit-capacity arms and wm=1/Mw_m=1/M. Each agent has one best high-capacity arm of mean uu, other high-capacity means u−δu-\delta, and unit-capacity means ϵ\epsilon, where 0<u≤1/80<u\le1/8, 0<ϵ≤u/40<\epsilon\le u/4, and 0<δ≤u/40<\delta\le u/4. Thus μmin⁡∗=u\mu_{\min}^\ast=u. We write Uα(x)=x1−α1−α,dδ=Uα(u)−Uα(u−δ),G=Uα(u)−Uα(ϵ).U_\alpha(x)=\frac{x^{1-\alpha}}{1-\alpha},d_\delta=U_\alpha(u)-U_\alpha(u-\delta),G=U_\alpha(u)-U_\alpha(\epsilon). Since forcing a nonoptimal edge leaves other agents' best arms available, its insertion gap Δeins\Delta_e^{\rm ins} equals dδ/Md_\delta/M or G/MG/M. For the optimum's edge set X(p∗)X(p^\ast), we obtain ∑e∉X(p∗)1Δeins=M2(Kh−1dδ+MG).\sum_{e\notin X(p^\ast)}\frac1{\Delta_e^{\rm ins}}=M^2(\frac{K_h-1}{d_\delta}+\frac MG). Since safe elimination preserves the optimum and only increases retained gaps, we use this sum and dδ=Θα(δu−α)d_\delta=\Theta_\alpha(\delta u^{-\alpha}) in the Phase-II bound on the confidence event: RII(T)≤Clog⁡(MNT2)M2((Kh−1)u1−αδ+Mu1−2αG)R_{\rm II}(T)\le C\log(MNT^2)M^2(\frac{(K_h-1)u^{1-\alpha}}{\delta}+\frac{Mu^{1-2\alpha}}G) where CC is uniform in δ\delta. Substituting the centralized lower-bound choice δT=14Nu/T\delta_T=\frac14\sqrt{Nu/T}, valid for T≥N/uT\ge N/u, gives O~(M2(Kh−1)Nu1/2−αNT)\widetilde O(\frac{M^2(K_h-1)}Nu^{1/2-\alpha}\sqrt{NT}) for the learning term, while the Phase-I and bad-arm terms remain logarithmic in TT for fixed N,u,ϵN,u,\epsilon. Thus, the learning term recovers the centralized hard family's dependence on TT and μmin⁡∗=u\mu_{\min}^\ast=u.

  1. Auction-call/regret tradeoff.

We consider an adaptive Phase-I stopping time τ\tau, followed by Phase-II epochs whose main auctions fix their matching schedules and endpoints. These schedules may use several matchings, but within-epoch rewards cannot revise them. Let BTB_T count Phase-II main-auction calls.

For the lower bound, we consider two agents, two unit-capacity arms, equal weights, Bernoulli rewards and 0<u≤1/20<u\le1/2. We use the reference instance ν0\nu_0 with all means uu and construct alternatives ν+,δ\nu_{+,\delta} and ν−,δ\nu_{-,\delta}, for 0<δ≤u/80<\delta\le u/8, with means μ+,δ=(u+δu;u+2δu),μ−,δ=(u+2δu;u+δu).\mu^{+,\delta}=\begin{pmatrix}u+\delta&u ; u+2\delta&u\end{pmatrix},\mu^{-,\delta}=\begin{pmatrix}u+2\delta&u ; u+\delta&u\end{pmatrix}. Since both agents prefer unit-capacity arm 1, the alternatives have opposite unique optima, with μmin⁡∗=u\mu_{\min}^\ast=u, and a wrong matching loses [Uα(u+2δ)−Uα(u+δ)]/2=Θα(u−αδ)[U_\alpha(u+2\delta)-U_\alpha(u+\delta)]/2=\Theta_\alpha(u^{-\alpha}\delta) per round.

We assume P0(τ>S)≤1/4\mathbb P_0(\tau>S)\le1/4 and E0BT≤bauc\mathbb E_0B_T\le b_{\rm auc} on ν0\nu_0, where SS is the high-probability Phase-I duration budget and baucb_{\rm auc} is the expected Phase-II call budget, with integers S≥⌈1/u⌉S\ge\lceil1/u\rceil and T≥4ST\ge4S. We set L=⌈4(bauc+1)⌉L=\lceil4(b_{\rm auc}+1)\rceil and use the grid [1] zj=S(T/S)(1−2−j)/(1−2−L),sj=⌊zj⌋,j=0,…,L.z_j=S(T/S)^{(1-2^{-j})/(1-2^{-L})},s_j=\lfloor z_j\rfloor, j=0,\ldots,L. Markov's inequality gives P0(τ≤S,BT≤L)≥1/2\mathbb P_0(\tau\le S,B_T\le L)\ge1/2, so some grid interval lies inside one announced epoch with probability at least 1/(2L)1/(2L), during which planned actions cannot respond to new observations. With one arm-1 observation per round, the reference-to-alternative history KL through round ss is at most 12sδ2/u12s\delta^2/u. We choose δ=u/sj−1/(64L)\delta=\sqrt{u/s_{j-1}}/(64L) to bound total variation by 1/(16L)1/(16L). Since the histories are close at the interval's start but the optimal matchings are opposite, one alternative incurs Ω((sj−sj−1)/L)\Omega((s_j-s_{j-1})/L) expected suboptimal rounds. Combining this with the per-round loss and zjzj−1=T(T/S)1/[2(2L−1)]\frac{z_j}{\sqrt{z_{j-1}}}=\sqrt T(T/S)^{1/[2(2^L-1)]} gives, for cα>0c_\alpha>0 depending only on α\alpha, sup⁡σ∈+,−,0<δ≤u/8Eνσ,δR(T)≥cαL2u1/2−αT(T/S)1/[2(2L−1)].\boxed{\sup_{\substack{\sigma\in\\{+,-\\},0<\delta\le u/8}}\mathbb E_{\nu_{\sigma,\delta}}R(T)\ge\frac{c_\alpha}{L^2}u^{1/2-\alpha}\sqrt T(T/S)^{1/[2(2^L-1)]}}. Thus, a smaller expected auction budget gives a smaller LL and a larger regret lower bound.

For fixed uu and protocol parameters, our Phase-I analysis gives S=O(log⁡T)S=O(\log T). Comparing this lower bound with a uniform O~(u1/2−αT)\widetilde O(u^{1/2-\alpha}\sqrt T) guarantee requires log⁡(T/S)2(2L−1)=O(log⁡L+log⁡log⁡T),\frac{\log(T/S)}{2(2^L-1)}=O(\log L+\log\log T), which forces L=Ω(log⁡log⁡T)L=\Omega(\log\log T). Within this epoch structure, uniform near-minimax regret over this family requires Ω(log⁡log⁡T)\Omega(\log\log T) expected Phase-II main-auction calls on the reference instance, even with adaptive epoch lengths and a random Phase-I stopping time.

[1] Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched Multi-armed Bandits Problem. NeurIPS 2019.

AuthorsOpenReview ↗

Response to Reviewer FYGn (Part 2/4)

W2: Main-text clarity and multiple optima.

Thanks for the comment. We clarify the exposition and correctness argument in Section 4, establish the multiple-optimum guarantee in Appendix D.1.3, and report its experiments in Appendix E.2.

  1. Main-text clarity and organization.

We explain each phase's purpose and outputs before the derivations in Section 4, interpret priced-value losses and real-agent/slack-arm terms alongside the recurrences, and add a short correctness argument connecting observable-gap thresholds to safe elimination and certified optimal replay. We place the multiple-optimum refinement beside the original guarantee to explain where uniqueness is used.

We present definitions, decision rules, and guarantees together in the main text. We give the shortest-path and Phase-I procedures, accuracy bounds and proofs in Appendices D.1.1–D.1.3 and D.2.4.

  1. Multiple optimal matchings.

We establish the multiple-optimum guarantee in Section 4 and Corollary 4 of 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 OinstO_{\rm inst} hides fixed parameters, not TT, and Nauc(T)N_{\rm auc}(T) counts main auctions in both phases:

ER(T)=Oinst(log⁡T),ENauc(T)=Oinst(1+log⁡log⁡T).\boxed{\mathbb E R(T)=O_{\rm inst}(\log T),\mathbb E N_{\rm auc}(T)=O_{\rm inst}(1+\log\log T).} We use the existing truncation HT=(log⁡T)bH_T=(\log T)^b, with fixed b>0b>0: at εq≤1/HT\varepsilon_q\le1/H_T, refreshing stops and the current main matching is replayed. Thus we avoid relying on freezing.

We define δ+\delta_+ as the smallest suboptimal complete-matching loss:

\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).
AuthorsOpenReview ↗

Response to Reviewer FYGn (Part 3/4)

Q2 & W1: Experiments.

Thanks for the comment. We report ten-seed comparisons and explain parameter choices in Section 5 and Appendices E.1–E.2 of the revised paper.

  1. Repeated runs and variation across seeds.

We repeat each comparison with ten independent seeds on fixed mean matrices and report mean ± sample SD in tables and uncertainty bands.

For centralized evaluation, we retain three regret comparisons, the α\alpha sweep and Phase-I stopping versus μmin⁡∗\mu_{\min}^\ast. For each centralized instance, we use Bernoulli rewards, Cn=⌈M/N⌉C_n=\lceil M/N\rceil, wm=1/Mw_m=1/M and a mean matrix drawn from [0.25,0.85][0.25,0.85] with instance seed 32, fixed across reward seeds. We report terminal regret (mean ± sample SD over ten seeds) in the indicated units:

(M,N,α)(M,N,\alpha)Regret unitsOursUCBETUSEFE
(6,6,8)(6,6,8)10610^62.922 ± 0.0347.659 ± 0.0856.101 ± 0.06329.135 ± 0.25622.048 ± 1.507
(8,5,20)(8,5,20)101210^{12}2.479 ± 0.0224.292 ± 0.0703.411 ± 0.1076.790 ± 0.44411.480 ± 1.117
(10,3,10)(10,3,10)10610^68.911 ± 0.09820.188 ± 0.31116.621 ± 0.31242.330 ± 1.387118.090 ± 6.707

At T=300,000T=300{,}000, Ours achieves the lowest regret in all three settings.

For decentralized algorithms, we compare Ours with Per-edge, which retains shrinking and refreshing but replaces shared gap computations from the main auction's dual prices with a constrained auction for each non-selected edge. We also evaluate Truncated, which stops refreshing at εq≤1/HT\varepsilon_q\le1/H_T and replays its current main matching, with HT=(log⁡T)1/8H_T=(\log T)^{1/8}.

We use Bernoulli rewards, M=8,N=5M=8,N=5, capacities (2,2,2,1,1)(2,2,2,1,1), uniform weights, α=1.5\alpha=1.5 and T=6×106T=6\times10^6 in both unique-optimal and multiple-optima instances. For the unique-optimum instance, we set mean 0.985 on (1,2,3,1,2,5,4,3)(1,2,3,1,2,5,4,3) and at most 0.177 elsewhere, making this feasible assignment every agent's unique best choice. For multiple optima, we set all means to 0.985 except μmm=0.05\mu_{mm}=0.05 for m=1,…,5m=1,\ldots,5 and μ6,1=0.40\mu_{6,1}=0.40, giving 1,316 optimal assignments using only maximal means. Sampling the 0.40 edge produces positive Phase-II learning regret.

We report both regret measures in 10310^3 units.

InstanceMethodTotal regretPhase-II regretPhase-II auction callsPhase-II communication (units)
UniqueOurs3,721.79 ± 0.003,561.57 ± 0.008 ± 039,040.0 ± 0.0
UniquePer-edge4,724.36 ± 0.004,564.13 ± 0.0072 ± 063,579.0 ± 0.0
MultipleOurs219.24 ± 0.1241.91 ± 0.126 ± 043,428.0 ± 38.6
MultiplePer-edge211.33 ± 0.0033.99 ± 0.00140 ± 0129,562.0 ± 0.0
MultipleTruncated213.75 ± 0.0036.41 ± 0.006 ± 042,765.6 ± 23.2

We observe that Ours achieves Phase-II communication reductions of 38.60% and 66.48% relative to Per-edge on the unique and multiple instances, respectively. Both methods freeze in 10/10 unique-instance runs, at t=2,641,920t=2{,}641{,}920 for Ours and t=3,227,648t=3{,}227{,}648 for Per-edge, with flat regret and auction counts afterward. On the multiple instance, b=1/8b=1/8 Truncated reaches t=5,169,152t=5{,}169{,}152 in 10/10 runs and replays optimally with zero later regret. Here we count one communication unit per scalar or arm index sent over a physical link, including bids, shared propagation, path reconstruction, matching outputs and controls.

  1. Choice of constants and sensitivity.

Our decentralized defaults are g=2g=2, initial checkpoint level nckpt=2n_{\rm ckpt}=2, checkpoint bid increment ϵckpt=10−4\epsilon_{\rm ckpt}=10^{-4}, and Phase-II auction precision ϵauc,q=εq/M\epsilon_{\rm auc,q}=\varepsilon_q/M, with HT=(log⁡T)1/8H_T=(\log T)^{1/8} for truncation. We vary one factor at a time over g∈2,4,8g\in\\{2,4,8\\}, nckpt∈1,2,8,64n_{\rm ckpt}\in\\{1,2,8,64\\}, and ϵckpt∈10−4,10−3,10−2\epsilon_{\rm ckpt}\in\\{10^{-4},10^{-3},10^{-2}\\}, using ten seeds per method and setting.

On the fixed sensitivity instance (M=8,N=5M=8,N=5, α=1.5\alpha=1.5, T=106T=10^6), we report Phase-II communication (mean ± sample SD over ten seeds) below. Both methods have R(T)=237,771.37±0.00R(T)=237{,}771.37\pm0.00 in every tested setting.

ggnckptn_{\rm ckpt}ϵckpt\epsilon_{\rm ckpt}Ours communication (units)Per-edge communication (units)
2210−410^{-4}26,352 ± 030,900 ± 0
4210−410^{-4}13,176 ± 015,450 ± 0
8210−410^{-4}8,784 ± 010,300 ± 0
2110−410^{-4}26,352 ± 030,900 ± 0
2810−410^{-4}26,352 ± 030,900 ± 0
26410−410^{-4}26,352 ± 030,900 ± 0
2210−310^{-3}26,352 ± 030,900 ± 0
2210−210^{-2}26,352 ± 030,900 ± 0

From these results, we observe lower communication with larger gg and unchanged regret on this instance. We find unchanged terminal regret and Phase-II communication across the tested checkpoint counts and increments.

Reviewer_VzMZOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the stochastic multi-agent multi-armed bandit problem with known arm capacities and a weighted α\alpha-fair objective, focusing on the case where α>1\alpha > 1. The benchmark is defined as the optimal fixed feasible matching that maximizes the cumulative weighted α\alpha-fair utility. The proposed centralized algorithm incorporates cover exploration, an adaptive stopping rule, a global elimination rule, and a UCB strategy applied to the retained edge set. The algorithm’s regret upper bound distinguishes between the capacity-coupled screening term and the learning term in the safe Lipschitz regime. Furthermore, for a constructed family of Bernoulli instances, the algorithm achieves a matching lower bound regarding its dependence on both the time horizon and the minimum per-agent utility under the optimal matching. The decentralized algorithm utilizes auction dual prices and augmented alternating cycles to estimate forced-insertion gaps, thereby reducing the number of auction calls. For fixed instances with a unique optimal matching, the algorithm provides instance-dependent regret guarantees, requiring only O(log⁡log⁡T)O(\log\log T) auction calls; a target-resolution truncation variant is also provided for general instances. Numerical experiments compare the performance of this algorithm against several other baselines in terms of regret and the number of auction calls.

Critical strengths

The decentralized algorithm proposed in this paper addresses a challenge arising from capacity coupling, where certain arms cannot be safely eliminated based solely on their individual rankings by each agent.

Critical weaknesses

The comparison with existing work is incomplete. Prior research on nonlinear combinatorial semi-bandit problems has extensively studied the interplay between local reward sensitivity and statistical variance. The appearance of the factor (\mu^{1/2-\alpha}) in the paper’s analysis makes such a comparison particularly important. What theoretical guarantees can existing methods provide in the setting considered here, and which of their underlying assumptions no longer hold? Moreover, what specific improvements are achieved by the proposed “data-driven safe-regime detection” and “global elimination” strategies? Clarifying these points is essential for assessing the paper’s main theoretical contributions.

Questions for authors
  1. How exactly does the proposed algorithm address capacity coupling?
  2. Under the same objective function and capacity constraints, what regret guarantees can be obtained using a combinatorial UCB approach, either based on Bernstein’s inequality or incorporating variance information? At which specific steps of the proposed algorithm are the “data-driven safe-regime detection” and “global elimination” mechanisms employed?
  3. Please provide the complete parameter settings used in Figure 3 and clarify how tset_{\mathrm{se}} in the figure relates to the necessary condition tse≥75Nlog⁡(MNT2)/μmin⁡⋆t_{\mathrm{se}} \ge 75N\log(MNT^2)/\mu^\star_{\min}.
  4. In addition to the main auction procedure, Proposition 6 includes an O(M2∣Aq∣)O(M^2|A_q|) term for “shared propagation.” When accounting for this propagation process, path reconstruction, and auction precision, how does the proposed method compare with the “Per-edge Auction” baseline in terms of overall computational and communication costs?
6 comments
AuthorsOpenReview ↗

Response to Reviewer VzMZ (Part 1/4)

Thank you for your constructive comments. We have included the following discussions in the revised paper, with changes marked in blue.


W1 & Q2: Comparison with existing methods.

Thanks for the comment. We clarify the comparison with existing UCB and NSW methods and the roles of stopping and elimination in Section 1 and Sections 3.1–3.3 of the revised paper.

  1. Existing methods and regret guarantees.

Our adaptive two-phase cover-elimination-UCB algorithm addresses the non-Lipschitz utility Uα(x)=x1−α/(1−α)U_\alpha(x)=x^{1-\alpha}/(1-\alpha) for α>1\alpha>1 under capacity constraints. The data-driven stopping rule and global elimination rule remove very poor base-arms while preserving optimal base-arms, so Phase II runs UCB in a Lipschitz regime. The resulting learning term depends on the minimum optimal utility μmin⁡∗\mu_{\min}^\ast. For comparison with existing methods, we distinguish μall,min=min⁡m,nμmn\mu_{\mathrm{all,min}}=\min_{m,n}\mu_{mn} and μmin⁡∗=min⁡mum(p∗,μ).\mu_{\min}^\ast=\min_m u_m(p^\ast,\mu). Applying Corollary 4 of the variance-aware BC-UCB analysis [1] to the entire weighted objective over MNMN base-arms gives

+\Gamma_\infty MN+MN G_{\max}).$$ Here $\Gamma_g$ bounds the Euclidean norm of the gradient weighted coordinatewise by $\sqrt{x_{mn}(1-x_{mn})}$, and $\Gamma_\infty$ bounds each coordinate derivative uniformly. $x=(x_{mn})$ is a candidate mean matrix, $w=(w_m)$ is the weight vector, and $w_{\max}=\max_m w_m$. Let $G_{\max}$ be the worst one-round exploratory loss. Using $\partial_{mn}F_\alpha(p,x)=p_{mn}w_mx_{mn}^{-\alpha}$, $\Gamma_g\le\|w\|_2\mu_{\mathrm{all,min}}^{1/2-\alpha}$, and $\Gamma_\infty\le w_{\max}\mu_{\mathrm{all,min}}^{-\alpha}$, for uniform weights this gives $$\widetilde O( \mu_{\mathrm{all,min}}^{1/2-\alpha}\sqrt{NT} +N\mu_{\mathrm{all,min}}^{-\alpha}+MN G_{\max}).$$ This is our specialization of [1]. The ratio $\mu_{\min}^\ast/\mu_{\mathrm{all,min}}$ can be arbitrarily large. For unit capacities, equal weights, and $\mu=\begin{pmatrix}2u&u ; 2u&\epsilon\end{pmatrix}$ with $0<\epsilon<u\le1/2$, the off-diagonal matching is uniquely optimal. Thus $\mu_{\min}^\ast=u$ stays fixed while $\mu_{\mathrm{all,min}}=\epsilon\rightarrow0$. The feasible diagonal matching also makes the coefficient $\Gamma_g$ at least $\epsilon^{1/2-\alpha}\sqrt{1-\epsilon}/2$. In contrast, our global elimination rule preserves optimal base-arms and ensures that every surviving base-arm's mean is bounded below by a constant multiple of $\mu_{\min}^\ast$. This gives $$\mathbb E R(T)=\widetilde O( \frac{\Delta_{\rm cov}G_{\max}}{\mu_{\min}^\ast} +(\mu_{\min}^\ast)^{1/2-\alpha}\sqrt{NT}).$$ The first term is the regret of cover exploration before the stopping condition is satisfied. The second term is the regret of UCB on the surviving base-arms. The data-driven stopping rule and global elimination rule enable this decomposition. They address the fact that capacity constraints may force small utilities even in the optimal matching. Moreover, our lower bound matches the dependence on $T$ and $\mu_{\min}^\ast$ up to logarithmic factors. **In summary, the Phase-II learning term is controlled by $\mu_{\min}^\ast$ even when $\mu_{\mathrm{all,min}}$ approaches zero. The stopping and elimination rules obtain this scale while preserving optimal base-arms under capacity constraints.** The Nash Social Welfare (NSW) method in [2] also does not apply to our $\alpha>1$ objective. That work addresses non-Lipschitz NSW, but its treatment of small utilities uses the nonnegativity and boundedness of NSW in $[0,1]$. However, our utility is negative and unbounded near zero. Our data-driven stopping rule and global safe elimination address this difficulty before applying UCB in a Lipschitz regime. [1] Nadav Merlis and Shie Mannor. Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem. COLT 2019. [2] Mengxiao Zhang, Ramiro Deo-Campo Vuong, and Haipeng Luo. No-Regret Learning for Fair Multi-Agent Social Welfare Optimization. NeurIPS 2024. 2. **Where the stopping rule and global elimination are used.** We compute $$\mathrm{LB}(t)=\max_{p\in\mathcal P}F_\alpha(p,\mathrm{LCB}(t)), \underline\mu(t)=U_\alpha^{-1}( \frac{\mathrm{LB}(t)-(1-w_{\min})U_\alpha(1)}{w_{\min}}).$$ Set $\underline\mu(t)=0$ if $\mathrm{LB}(t)=-\infty$. Phase I stops when $$\underline\mu(t)>0, \min_{m,n}N_{mn}(t)\ge \frac{30L}{\underline\mu(t)},$$ where $L=\log(MNT^2)$ and $N_{mn}(t)$ counts observations of edge $(m,n)$ through round $t$. Upper-bounding every other agent's utility by $U_\alpha(1)$ gives $\underline\mu(t)\le \mu_{\min}^\ast$ on the confidence event. The test uses observed confidence bounds and requires no prior knowledge of $\mu_{\min}^\ast$. After this test succeeds, the algorithm applies the global elimination rule $\mathrm{UB}_{mn}<\mathrm{LB}$. It then runs UCB on the retained graph, where all surviving base-arms have means bounded below by a constant multiple of $\mu_{\min}^\ast$.
AuthorsOpenReview ↗

Response to Reviewer VzMZ (Part 2/4)

Q1: How does the algorithm address capacity coupling?

Thanks for the comment. We address capacity coupling in both exploration and elimination. The cover schedule explores every base-arm through feasible matchings. The global elimination rule compares an upper bound for matchings containing a base-arm with a lower bound on the optimal α\alpha-fair utility. It therefore removes very poor base-arms while preserving optimal base-arms. For example, with unit capacities, equal weights, and

\quad 0<\epsilon<u\le1/2,$$ the optimum assigns agent 1 its locally inferior arm of mean $u$, allowing agent 2 to receive mean $2u$. An agent's individual ranking can delete an edge required by the global optimum. The global elimination rule uses a feasible lower bound $\mathrm{LB}$ and the following upper bound for matchings containing $(m,n)$: $$\mathrm{UB}_{mn} =w_mU_\alpha(\mathrm{UCB}_{mn}) +\sum_{i\ne m}w_iU_\alpha(\max_k\mathrm{UCB}_{ik}).$$ On the confidence event, every complete feasible matching containing $(m,n)$ has value at most $\mathrm{UB}_{mn}$. Consequently, $\mathrm{UB}_{mn}<\mathrm{LB}$ excludes that edge from every optimum. The data-driven stopping rule ensures sufficiently concentrated estimates for global safe elimination. --- **Q3: Experimental parameters in Fig.3.** Thanks for the comment. We correct the experimental stopping constant to 30 and update its proofs and experiments in Sections 3.1 and 5 of the revised paper. We apologize that the stopping constant in the original experiment was implemented incorrectly. The revised implementation, proofs, and experiments consistently use the stopping constant 30. The revised experiment uses Bernoulli rewards, $M=N=3$, unit capacities, $w_m=1/3$, $\alpha=10$, $T=300{,}000$, $\delta=0.05$, and 10 reward seeds, with $$\mu(\epsilon)= \begin{pmatrix} 1&\epsilon&\epsilon/2; 1-\delta&\epsilon/2&\epsilon; \epsilon/2&1&1-\delta \end{pmatrix}, \quad \epsilon\in\\{0.20,0.15,0.10,0.08,0.06,0.05\\}.$$ For each $\epsilon$, the mean matrix is fixed across ten reward seeds. Exact optimization gives $\mu_{\min}^\ast=\epsilon$. The revised stopping condition requires $\underline\mu(t)>0$ and $\min_{m,n}N_{mn}(t)\ge30L/\underline\mu(t)$, where $L=\log(MNT^2)$. The cover samples each edge once per $N$ rounds, and $\underline\mu\le\mu_{\min}^\ast$ on the confidence event. Writing $t_{\rm se}$ for the Phase-I stopping time gives $$t_{\rm se}\ge\frac{30N\log(MNT^2)}{\mu_{\min}^\ast}.$$ The ten-seed results are: | $\mu_{\min}^\ast$ | $t_{\rm se}$, mean $\pm$ sample SD | Necessary threshold | |---:|---:|---:| | 0.20 | 20,874.0 $\pm$ 290.5 | 12,340 | | 0.15 | 27,845.4 $\pm$ 537.4 | 16,453 | | 0.10 | 41,523.9 $\pm$ 994.0 | 24,679 | | 0.08 | 52,416.6 $\pm$ 919.1 | 30,848 | | 0.06 | 69,884.4 $\pm$ 1,067.7 | 41,131 | | 0.05 | 84,084.6 $\pm$ 1,780.3 | 49,357 | All 60 runs reach the safe regime and individually satisfy the corresponding necessary threshold. The decentralized stopping analysis uses the same constant, with $u_{\rm se}=0.3\underline\mu(t_{\rm se})$ and $n_0\ge30L/\underline\mu(t_{\rm se})=9L/u_{\rm se}$, where $n_0$ is the minimum retained-edge sample count at safe entry.
AuthorsOpenReview ↗

Response to Reviewer VzMZ (Part 3/4)

Q4: 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 MM-entry vector therefore costs MM units per link. We include feasibility checks, preprocessing and restoration, auctions, shared propagation, path reconstruction, matching outputs, shrinking/freezing and scheduling controls. The MM agents and NN arms retain all S=M+N−1S=M+N-1 links of the communication tree after statistical elimination: an eliminated allocation edge remains available for communication.

At epoch qq, AqA_q is the active-edge count and Uq=Aq−MU_q=A_q-M 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 Bq\mathcal B_q count main-auction bids and Bqper\mathcal B_q^{\rm per} 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 ηq=ϵauc,q=εq/M\eta_q=\epsilon_{\rm auc,q}=\varepsilon_q/M, keeping auction approximation error within the confidence scale εq\varepsilon_q.

Writing WIIW_{\rm II} for Phase-II communication and CII\mathcal C_{\rm II} for computation at its coordination updates, we obtain WIIshared=O(∑q[M2(Aq+S)+(Aq+S)Bq]),W_{\rm II}^{\rm shared}=O(\sum_q[M^2(A_q+S)+(A_q+S)\mathcal B_q]), WIIper=O(∑q[(Uq+1)M(Aq+S)+(Aq+S)Bqper]),W_{\rm II}^{\rm per}=O(\sum_q[(U_q+1)M(A_q+S)+(A_q+S)\mathcal B_q^{\rm per}]), CIIshared=O(∑q[M2(Aq+S)+M(Uq+1)2+(Aqlog⁡(2M)+S)Bq]),\mathcal C_{\rm II}^{\rm shared}=O(\sum_q[M^2(A_q+S)+M(U_q+1)^2+(A_q\log(2M)+S)\mathcal B_q]), CIIper=O(∑q[(Uq+1)M(Aq+S)+M(Uq+1)2+(Aqlog⁡(2M)+S)Bqper]).\mathcal C_{\rm II}^{\rm per}=O(\sum_q[(U_q+1)M(A_q+S)+M(U_q+1)^2+(A_q\log(2M)+S)\mathcal B_q^{\rm per}]).

The first term in each bound covers gap processing and associated coordination. Ours sends MM-entry vectors over at most MM propagation sweeps, giving M2(Aq+S)M^2(A_q+S). Per-edge repeats O(M(Aq+S))O(M(A_q+S)) feasibility and matching work for at most UqU_q 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 Uq+1U_q+1 candidate matchings, each represented by MM arm indices, adds O(M(Uq+1)2)O(M(U_q+1)^2) 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 O(M(T−tse))O(M(T-t_{\rm se})) computation, separately from these coordination bounds, where tset_{\rm se} is the Phase-I stopping time.

We also account explicitly for auction precision. Let VqV_q be the largest within-agent range of scores wmUα(UCBmn)w_mU_\alpha(\mathrm{UCB}_{mn}) 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$.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.