Literature Database Entry

tao2024robust

Youming Tao, Xiuzhen Cheng, Falko Dressler, Zhipeng Cai and Dongxiao Yu, "Robust Matroid Bandit Optimization against Adversarial Contamination," Proceedings of 30th International Computing and Combinatorics Conference (COCOON 2024), Shanghai, China, August 2024.

Abstract

In this paper, we consider the matroid bandit optimization problem, a fundamental and widely applicable framework for combinatorial multi-armed bandits where the action space is constrained by a matroid. We tackle the chal- lenge of devising algorithms that can cope with adversarial contamination of the feedback rewards, which may severely degrade the performance or even mis- lead existing methods. Our main contribution is an efficient and robust algorithm, dubbed ROMM, which builds upon the idea of optimistic matroid maximization and leverages robust statistical techniques to estimate the quality of the base arms in polynomial time. We establish lower bounds for matroid bandit optimization under the ε-contamination model we adopt and show that ROMM achieves near- optimal regret bounds up to polylogarithmic factors. Furthermore, our analysis unveils a sharp phase transition between the small contamination regime and the large contamination regime for matroid bandit optimization. We establish that our algorithm can tolerate up to a universal constant fraction of corrupted feedbacks, which is optimal under mild conditions.

Quick access

Authors' Version (PDF on this web site)
BibTeX

Contact

Youming Tao
Xiuzhen Cheng
Falko Dressler
Zhipeng Cai
Dongxiao Yu

BibTeX reference

Copyright notice

Links to final or draft versions of papers are presented here to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted or distributed for commercial purposes without the explicit permission of the copyright holder.

The following applies to all papers listed above that have IEEE copyrights: Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

The following applies to all papers listed above that are in submission to IEEE conference/workshop proceedings or journals: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.

The following applies to all papers listed above that have ACM copyrights: ACM COPYRIGHT NOTICE. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM, Inc., fax +1 (212) 869-0481, or permissions@acm.org.

The following applies to all SpringerLink papers listed above that have Springer Science+Business Media copyrights: The original publication is available at www.springerlink.com.

This page was automatically generated using BibDB and bib2web.