acceptodds
Withdrawn from ICLR 2027

Heterogeneous Multi-Agent Contextual Bandits under Bounded Misspecification

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Misspecification is known to degrade the performance of contextual bandit algorithms, yet its impact has received little attention in the multi-agent setting. Motivated by this gap, we formulate the setting of arm-heterogeneous multi-agent linear contextual bandits under misspecification—a practically motivated model where each agent has access to only a subset of the global arm catalog. To minimize the joint regret of all agents without prior knowledge of the misspecification level, we propose HM-UCB, a collaborative algorithm that updates its parameter estimates via size-weighted pooling of agent observations. We first establish a high-probability regret upper bound of for HM-UCB. Next, by using geometric packing and information-theoretic techniques, we derive a generic regret lower bound in our model, which along with the upper bound of HM-UCB, establishing the near-optimality of HM-UCB in some practical regimes. To demonstrate the scalability of our framework, we instantiate HM-UCB under two practical protocols—Naive and N-Selection. For each, we design customized algorithms and establish corresponding theoretical guarantees. Empirical evaluations corroborate our theoretical findings, underscoring the strong practical performance of HM-UCB and substantiating the tightness of our regret bounds.

Primary area:
reinforcement learning
Keywords:
Multi-Agent Bandits, Model Misspecification, Linear Contextual Bandits, Catalog Heterogeneity, Regret Minimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_ZuFDOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies arm-heterogeneous multi-agent linear contextual bandits under bounded model misspecification. The authors propose HM-UCB, which extends SupLinUCB to the multi-agent setting using catalog-size-weighted pooling of observations. They establish a high-probability regret upper bound, derive complementary lower bounds to characterize the problem difficulty, and further study Naïve and N-Selection protocols. Synthetic experiments are provided to examine the effects of misspecification and heterogeneous catalog sizes.

Critical strengths
  1. Meaningful problem setting. The paper considers a practically relevant combination of two challenges in contextual bandits: heterogeneous arm availability across agents and model misspecification. This setting is well motivated by applications such as multi-platform recommendation, where agents may have different local catalogs while sharing common reward structure.

  2. Broad theoretical and empirical coverage. The paper provides an upper regret bound for HM-UCB, complementary lower-bound analyses, and extensions to the Naïve and N-Selection protocols. It also includes synthetic experiments examining misspecification and catalog heterogeneity, making the overall study relatively comprehensive.

Critical weaknesses
  1. Potential inconsistency in the size-weighted estimator. HM-UCB defines the covariance matrix as Vt,s=λI+∑(τ,n)∈Ψt,sxτ(iτ,n)xτ(iτ,n)⊤,V_{t,s} = \lambda I + \sum_{(\tau,n)\in\Psi_{t,s}} x_{\tau}(i_{\tau,n})x_{\tau}(i_{\tau,n})^\top, while the reward vector is updated as bt,s=∑(τ,n)∈Ψt,s∣Kn∣∣K∣rτ,nxτ(iτ,n),b_{t,s} = \sum_{(\tau,n)\in\Psi_{t,s}} \frac{|K_n|}{|K|} r_{\tau,n}x_{\tau}(i_{\tau,n}), and then uses θ^=V−1b\hat{\theta}=V^{-1}b. Thus, the catalog-size weight is applied to the response term but not to the corresponding covariance term. This differs from standard weighted least squares, where the same sample weights normally appear in both VV and bb. Even in the noiseless and perfectly specified case r=x⊤θr=x^\top\theta, the estimator becomes θ^=V−1∑nwnxx⊤θ,\hat{\theta} = V^{-1}\sum_n w_n xx^\top\theta, which is generally not equal to θ\theta when wn≠1w_n\neq 1. Therefore, the proposed weighting may introduce a systematic bias depending on catalog sizes and feature directions. Since size-weighted pooling is the key distinctive component of HM-UCB, this issue is consequential to my overall assessment.

  2. The relationship between the lower-bound setting and the original heterogeneous setting is unclear. The lower bound is derived using the N-Selection protocol, which requires agents to select distinct arms and is explicitly described as different from the setting introduced in Section 2. Although the paper later refers to N-Selection as a special case of the heterogeneous setting, I could not see a direct reduction showing how the distinct-arm constraint arises from the original model with fixed local catalogs. This makes the claimed generic lower bound and the resulting near-optimality conclusion less convincing.

Questions for authors
  1. Is the proposed size-weighted estimator intended to be a weighted least-squares estimator? If so, why is the catalog-size weight applied only to the reward vector bb, while the covariance matrix VV remains unweighted? Could the authors clarify why this asymmetric weighting does not introduce bias even in the noiseless, well-specified case?

  2. Could the authors clarify in what precise sense the N-Selection protocol is a special case of the heterogeneous setting in Section 2? In particular, how does the distinct-arm selection constraint in N-Selection arise from the original model with fixed local catalogs?

Reviewer_3tR3OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies multi-agent linear contextual bandits with heterogeneous arm catalogs and bounded misspecification. It proposes HM-UCB, a stage-wise algorithm using catalog-size-weighted reward pooling, and presents thereotical analysis including regret upper bounds, lower bounds, and implements numerical experiments.

Critical strengths

Studying misspecification together with heterogeneous arm availability is practically relevant. The paper attempts to address unknown misspecification through a stage-wise algorithm and to characterize both achievable regret and problem hardness. The experiments provide preliminary evidence about the proposed algorithms.

Critical weaknesses
  1. Algorithm 1 uses an unweighted covariance matrix V=λI+∑xx⊤V=\lambda I+\sum xx^\top, but a weighted reward vector b=∑wnrxb=\sum w_nrx. Consequently, the decomposition of θ^−θ\hat\theta-\theta contains the additional term V−1∑(wn−1)xx⊤θV^{-1}\sum(w_n-1)xx^\top\theta, which is absent in analysis. This term can remain nonzero even without misspecification or noise. For example, repeated one-dimensional observations with constant weight (w<1) yield an estimate converging to wθw\theta, rather than θ\theta. This raises a direct concern about Theorem 1 as currently proved.
  2. The application motivates multiple learners, but the algorithm assumes globally shared stage statistics and a common parameter. The paper should distinguish its contribution from a centralized batched extension of M-SupLinUCB with local action constraints. The comparison with H-LINUCB also involves different notions of heterogeneity and should be qualified accordingly.
  3. Following point 2, it seems that the analysis relies on exact shared statistics. It does not specify the messages, synchronization schedule, or decentralized aggregation procedure.
  4. The main comparisons are between the authors’ own variants. Missing baselines include independent M-SupLinUCB, centralized pooled learning, and an unweighted pooling ablation.
  5. The terminology “heterogeneous multi-agent” is potentially a little misleading. The main source of heterogeneity is the agents’ access to different, potentially overlapping subsets of a shared global arm catalog, while the linear parameter and arm features are shared. “Heterogeneous arm availability” or “heterogeneous local catalogs” would describe the setting more precisely.
Questions for authors
  1. When Condition 2 or the small-misspecification assumption of Corollary 1 fails, which guarantees remain informative?
  2. What communication protocol realizes the exact shared statistics? Does the algorithm assume synchronous centralized aggregation, and what information must decentralized agents exchange?
Reviewer_JkM8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies cooperative contextual bandits in which agents share a linear reward parameter but have different available-arm catalogs and bounded, agent-specific model errors. HM-UCB combines stage-wise elimination with a shared estimator that weights reward observations by catalog size. Without knowing the misspecification level, it claims regret

O~ ⁣(RdNTlog⁡(KN)+εd NT+Bd).\widetilde O\!\left(R\sqrt{dNT\log(KN)}+\varepsilon\sqrt d\,NT+Bd\right).

The paper also develops lower bounds, a near-optimality corollary, and variants for common catalogs and distinct-arm selection. Synthetic experiments over 30 seeds vary misspecification and catalog sizes (Section 6; Appendix F).

Critical strengths

The formulation separates access to arms from access to observations. Two agents can share a reward parameter and pool data while still choosing from different catalogs. Including local model errors makes this distinction useful: a large shared sample can remain misleading for an agent whose available items are poorly represented. The paper puts these issues in one model and defines regret against each agent's own feasible choices. This is the part of the submission I would retain, even though the proposed analysis needs revision.

Critical weaknesses
  1. The weighted estimator introduces a bias omitted from the analysis. Algorithm 1, lines 31–32 (p. 4), uses

    \quad w_n=|K_n|/K.$$ With exact linear rewards, $\widehat\theta-\theta$ therefore contains $V^{-1}\sum(w_n-1)xx^\top\theta$, in addition to ridge bias. Lemma 8 omits this term. For example, take two agents with disjoint singleton catalogs, both scalar features equal to 1, $\theta=1$, and noiseless rewards 1. Both weights are $1/2$, so after $m$ stage observations,\$ \widehat\theta=\frac{m}{2(\lambda+m)}\longrightarrow\frac12, \$ while the claimed error bound at $\varepsilon=0$ contracts as $\beta/\sqrt{\lambda+m}$. This contradicts the confidence argument; the example itself has zero regret and is not a direct regret counterexample. There is a separate budget problem: Lemmas 9–10 use $\varepsilon_n\leq\varepsilon$, whereas Definition 1 guarantees only $\sum_n w_n\varepsilon_n\leq\varepsilon$. These are central steps in Theorem 1.
  2. The supplied packing witness and its transfer to the original model are invalid as written.** In Appendix D.2 (p. 21, lines 1086–1099), write Δ\Delta for the paper's reward-gap parameter. The proof sets Δ=ε/ρ\Delta=\varepsilon/\rho, θ=Δa⋆\theta=\Delta a_\star, and assigns each other good arm ii the residual Δ(1−⟨a⋆,ai⟩)\Delta(1-\langle a_\star,a_i\rangle). Since ∣⟨a⋆,ai⟩∣≤ρ|\langle a_\star,a_i\rangle|\leq\rho, that residual is at least ε1−ρρ>ε\varepsilon\frac{1-\rho}{\rho}>\varepsilon when ρ<12\rho<\tfrac12, an allowed regime. The exhibited parameter and residuals therefore fail their stated residual bound. This does not prove that no alternative parameter could represent the same rewards; it means the submitted witness does not establish the claimed hard family.

    The coverage argument has a second problem. Section 2 permits agents to repeat the same arm, whereas Section 5.2 requires distinct choices. The proof takes full catalogs and equal rewards on a good set OO, then asserts that some agent must pull a suboptimal arm until all of OO has been discovered (p. 21, lines 1101–1107). Under Section 2, two agents can repeatedly choose one discovered good arm, incur zero regret, and leave another good arm undiscovered. Counting NN optimal arms does not supply the missing distinct-choice constraint. A valid construction and reduction are needed before this argument can support the claimed heterogeneous lower bound or near-optimality result.

Questions for authors
  1. Is the combination of an unweighted Gram matrix and weighted rewards intentional? How should the missing linear-signal bias enter the estimator or proof?
  2. How do Lemmas 9–10 follow from the weighted global misspecification budget? Would the required correction change Theorem 1?
  3. Can you give a feasible packing construction under Definition 1, justify the reduction to Section 2's objective, and supply the probability argument needed for Corollary 1?

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

Related papers

Discussion (0)

Sign in to comment.