Robust Contextual Combinatorial Multi-Armed Bandits for Unreliable Network Systems

Junkai Wang; Xutong Liu; Jinhang Zuo; Yuedong Xu

doi:10.1109/INFOCOM55648.2025.11044618

Robust Contextual Combinatorial Multi-Armed Bandits for Unreliable Network Systems

Junkai Wang, Xutong Liu^*, Jinhang Zuo, Yuedong Xu^*

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

Combinatorial multi-armed bandit (CMAB) is a fundamental framework widely used in networked systems to maximize cumulative rewards under uncertainty. Real-world applications such as federated learning and content delivery network often involve feedback that may be corrupted due to adversarial attacks or network disruptions. In this paper, we study contextual CMAB (C² MAB) with adversarial corruptions, where feedback for base arms within any selected super arms can be corrupted by an adversary. We focus on L₁ -norm smooth reward function and both L₁ and L_∞ -norm corruption measures, establishing tight regret upper bounds for each scenario. Additionally, we provide the first lower bounds for C² MAB under corruptions, confirming the optimality of our proposed algorithm. To broaden the applicability, we further extend our algorithm to a more general C² - MAB setting with probabilistically triggered arms. Empirical validation demonstrates significant improvements across synthetic and real-world datasets, with applications in contextual latency-critic federated learning, user-specific online content delivery and 360° VR video streaming.
© 2025 IEEE.

Original language	English
Title of host publication	IEEE INFOCOM 2025 - IEEE Conference on Computer Communications
Publisher	IEEE
Number of pages	10
ISBN (Electronic)	9798331543051
ISBN (Print)	9798331543068
DOIs	https://doi.org/10.1109/INFOCOM55648.2025.11044618
Publication status	Published - 2025
Event	IEEE International Conference on Computer Communications 2025 (IEEE INFOCOM 2025) - Park Plaza Westminster Bridge, London, United Kingdom Duration: 19 May 2025 → 22 May 2025 https://infocom2025.ieee-infocom.org/

Publication series

Name	Proceedings - IEEE INFOCOM
ISSN (Print)	0743-166X
ISSN (Electronic)	2641-9874

Conference

Conference	IEEE International Conference on Computer Communications 2025 (IEEE INFOCOM 2025)
Abbreviated title	IEEE INFOCOM 2025
Place	United Kingdom
City	London
Period	19/05/25 → 22/05/25
Internet address	https://infocom2025.ieee-infocom.org/

Bibliographical note

Research Unit(s) information for this publication is provided by the author(s) concerned.

Funding

The work of Yuedong Xu was supported by National Key R&D Program of China under Grant 2020YFA0711400, the Natural Science Foundation of China under Grant 62072117 and the Key-Area Research and Development Program of Guangdong Province under Grant 2020B010166003. The work of Xutong Liu was partially supported by a fellowship award from the Research Grants Council of the Hong Kong Special Administrative Region, China (CUHK PDFS2324-4S04). The work of Jinhang Zuo was supported by CityU 9610706.

RGC Funding Information

RGC-funded

Access Output

10.1109/INFOCOM55648.2025.11044618

https://ieeexplore.ieee.org/document/11044618

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{ae13115cf84f4ef89fa552095f32d730,

title = "Robust Contextual Combinatorial Multi-Armed Bandits for Unreliable Network Systems",

abstract = "Combinatorial multi-armed bandit (CMAB) is a fundamental framework widely used in networked systems to maximize cumulative rewards under uncertainty. Real-world applications such as federated learning and content delivery network often involve feedback that may be corrupted due to adversarial attacks or network disruptions. In this paper, we study contextual CMAB (C2 MAB) with adversarial corruptions, where feedback for base arms within any selected super arms can be corrupted by an adversary. We focus on L1 -norm smooth reward function and both L1 and L∞ -norm corruption measures, establishing tight regret upper bounds for each scenario. Additionally, we provide the first lower bounds for C2 MAB under corruptions, confirming the optimality of our proposed algorithm. To broaden the applicability, we further extend our algorithm to a more general C2 - MAB setting with probabilistically triggered arms. Empirical validation demonstrates significant improvements across synthetic and real-world datasets, with applications in contextual latency-critic federated learning, user-specific online content delivery and 360° VR video streaming.{\textcopyright} 2025 IEEE.",

author = "Junkai Wang and Xutong Liu and Jinhang Zuo and Yuedong Xu",

note = "Research Unit(s) information for this publication is provided by the author(s) concerned.; IEEE International Conference on Computer Communications 2025 (IEEE INFOCOM 2025), IEEE INFOCOM 2025 ; Conference date: 19-05-2025 Through 22-05-2025",

year = "2025",

doi = "10.1109/INFOCOM55648.2025.11044618",

language = "English",

isbn = "9798331543068",

series = "Proceedings - IEEE INFOCOM",

publisher = "IEEE",

booktitle = "IEEE INFOCOM 2025 - IEEE Conference on Computer Communications",

address = "United States",

url = "https://infocom2025.ieee-infocom.org/",

}

Wang, J, Liu, X, Zuo, J & Xu, Y 2025, Robust Contextual Combinatorial Multi-Armed Bandits for Unreliable Network Systems. in IEEE INFOCOM 2025 - IEEE Conference on Computer Communications. Proceedings - IEEE INFOCOM, IEEE, IEEE International Conference on Computer Communications 2025 (IEEE INFOCOM 2025), London, United Kingdom, 19/05/25. https://doi.org/10.1109/INFOCOM55648.2025.11044618

Robust Contextual Combinatorial Multi-Armed Bandits for Unreliable Network Systems. / Wang, Junkai; Liu, Xutong; Zuo, Jinhang et al.
IEEE INFOCOM 2025 - IEEE Conference on Computer Communications. IEEE, 2025. (Proceedings - IEEE INFOCOM).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Robust Contextual Combinatorial Multi-Armed Bandits for Unreliable Network Systems

AU - Wang, Junkai

AU - Liu, Xutong

AU - Zuo, Jinhang

AU - Xu, Yuedong

N1 - Research Unit(s) information for this publication is provided by the author(s) concerned.

PY - 2025

Y1 - 2025

N2 - Combinatorial multi-armed bandit (CMAB) is a fundamental framework widely used in networked systems to maximize cumulative rewards under uncertainty. Real-world applications such as federated learning and content delivery network often involve feedback that may be corrupted due to adversarial attacks or network disruptions. In this paper, we study contextual CMAB (C2 MAB) with adversarial corruptions, where feedback for base arms within any selected super arms can be corrupted by an adversary. We focus on L1 -norm smooth reward function and both L1 and L∞ -norm corruption measures, establishing tight regret upper bounds for each scenario. Additionally, we provide the first lower bounds for C2 MAB under corruptions, confirming the optimality of our proposed algorithm. To broaden the applicability, we further extend our algorithm to a more general C2 - MAB setting with probabilistically triggered arms. Empirical validation demonstrates significant improvements across synthetic and real-world datasets, with applications in contextual latency-critic federated learning, user-specific online content delivery and 360° VR video streaming.© 2025 IEEE.

AB - Combinatorial multi-armed bandit (CMAB) is a fundamental framework widely used in networked systems to maximize cumulative rewards under uncertainty. Real-world applications such as federated learning and content delivery network often involve feedback that may be corrupted due to adversarial attacks or network disruptions. In this paper, we study contextual CMAB (C2 MAB) with adversarial corruptions, where feedback for base arms within any selected super arms can be corrupted by an adversary. We focus on L1 -norm smooth reward function and both L1 and L∞ -norm corruption measures, establishing tight regret upper bounds for each scenario. Additionally, we provide the first lower bounds for C2 MAB under corruptions, confirming the optimality of our proposed algorithm. To broaden the applicability, we further extend our algorithm to a more general C2 - MAB setting with probabilistically triggered arms. Empirical validation demonstrates significant improvements across synthetic and real-world datasets, with applications in contextual latency-critic federated learning, user-specific online content delivery and 360° VR video streaming.© 2025 IEEE.

UR - http://www.scopus.com/inward/record.url?scp=105011093119&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-105011093119&origin=recordpage

U2 - 10.1109/INFOCOM55648.2025.11044618

DO - 10.1109/INFOCOM55648.2025.11044618

M3 - RGC 32 - Refereed conference paper (with host publication)

AN - SCOPUS:105011093119

SN - 9798331543068

T3 - Proceedings - IEEE INFOCOM

BT - IEEE INFOCOM 2025 - IEEE Conference on Computer Communications

PB - IEEE

T2 - IEEE International Conference on Computer Communications 2025 (IEEE INFOCOM 2025)

Y2 - 19 May 2025 through 22 May 2025

ER -

Robust Contextual Combinatorial Multi-Armed Bandits for Unreliable Network Systems

Abstract

Publication series

Conference

Bibliographical note

Funding

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this