- 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
-
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.
-
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
-
Potential inconsistency in the size-weighted estimator. HM-UCB defines the covariance matrix as while the reward vector is updated as and then uses . 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 and . Even in the noiseless and perfectly specified case , the estimator becomes which is generally not equal to when . 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.
-
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
-
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 , while the covariance matrix remains unweighted? Could the authors clarify why this asymmetric weighting does not introduce bias even in the noiseless, well-specified case?
-
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?