Contextual Combinatorial Bandits with Probabilistically Triggered Arms

Xutong Liu; Jinhang Zuo; Siwei Wang; John C.S. Lui; Mohammad Hajiesmaili; Adam Wierman; Wei Chen

Contextual Combinatorial Bandits with Probabilistically Triggered Arms

Xutong Liu^*, Jinhang Zuo, Siwei Wang, John C.S. Lui^*, Mohammad Hajiesmaili, Adam Wierman, Wei Chen^*

^*Corresponding author for this work

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

1 Citation (Scopus)

Abstract

We study contextual combinatorial bandits with probabilistically triggered arms (C²MAB-T) under a variety of smoothness conditions that capture a wide range of applications, such as contextual cascading bandits and contextual influence maximization bandits. Under the triggering probability modulated (TPM) condition, we devise the C²-UCB-T algorithm and propose a novel analysis that achieves an Õ(d√KT) regret bound, removing a potentially exponentially large factor O(1/p_min), where d is the dimension of contexts, p_min is the minimum positive probability that any arm can be triggered, and batch-size K is the maximum number of arms that can be triggered per round. Under the variance modulated (VM) or triggering probability and variance modulated (TPVM) conditions, we propose a new variance-adaptive algorithm VAC²-UCB and derive a regret bound Õ(d√T), which is independent of the batch-size K. As a valuable by-product, our analysis technique and variance-adaptive algorithm can be applied to the CMAB-T and C²MAB setting, improving existing results there as well. We also include experiments that demonstrate the improved performance of our algorithms compared with benchmark algorithms on synthetic and real-world datasets.

© 2023 by the author(s)

Original language	English
Title of host publication	Proceedings of the 40^thInternational Conference on Machine Learning
Publisher	ML Research Press
Publication status	Published - Jul 2023
Externally published	Yes
Event	40th International Conference on Machine Learning (ICML 2023) - Hawaii Convention Center, Honolulu, United States Duration: 23 Jul 2023 → 29 Jul 2023 https://icml.cc/

Publication series

Name	Proceedings of Machine Learning Research
Volume	202
ISSN (Print)	2640-3498

Conference

Conference	40th International Conference on Machine Learning (ICML 2023)
Abbreviated title	ICML'23
Place	United States
City	Honolulu
Period	23/07/23 → 29/07/23
Internet address	https://icml.cc/

Funding

The work of John C.S. Lui was supported in part by RGC’s GRF 14215722. The work of Mohammad Hajiesmaili is supported by NSF CAREER-2045641, CPS-2136199, CNS2106299, and CNS-2102963. Wierman is supported by NSF grants CNS-2146814, CPS-2136197, CNS-2106403, and NGSDI-2105648.

Access Output

https://proceedings.mlr.press/v202/liu23bf.html

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{8e3ef43d97224cb1a3895ff55c4802c8,

title = "Contextual Combinatorial Bandits with Probabilistically Triggered Arms",

abstract = "We study contextual combinatorial bandits with probabilistically triggered arms (C2MAB-T) under a variety of smoothness conditions that capture a wide range of applications, such as contextual cascading bandits and contextual influence maximization bandits. Under the triggering probability modulated (TPM) condition, we devise the C2-UCB-T algorithm and propose a novel analysis that achieves an {\~O}(d√KT) regret bound, removing a potentially exponentially large factor O(1/pmin), where d is the dimension of contexts, pmin is the minimum positive probability that any arm can be triggered, and batch-size K is the maximum number of arms that can be triggered per round. Under the variance modulated (VM) or triggering probability and variance modulated (TPVM) conditions, we propose a new variance-adaptive algorithm VAC2-UCB and derive a regret bound {\~O}(d√T), which is independent of the batch-size K. As a valuable by-product, our analysis technique and variance-adaptive algorithm can be applied to the CMAB-T and C2MAB setting, improving existing results there as well. We also include experiments that demonstrate the improved performance of our algorithms compared with benchmark algorithms on synthetic and real-world datasets. {\textcopyright} 2023 by the author(s)",

author = "Xutong Liu and Jinhang Zuo and Siwei Wang and Lui, {John C.S.} and Mohammad Hajiesmaili and Adam Wierman and Wei Chen",

year = "2023",

month = jul,

language = "English",

series = "Proceedings of Machine Learning Research",

publisher = "ML Research Press",

booktitle = "Proceedings of the 40th International Conference on Machine Learning",

note = "40th International Conference on Machine Learning (ICML 2023), ICML'23 ; Conference date: 23-07-2023 Through 29-07-2023",

url = "https://icml.cc/",

}

Liu, X, Zuo, J, Wang, S, Lui, JCS, Hajiesmaili, M, Wierman, A & Chen, W 2023, Contextual Combinatorial Bandits with Probabilistically Triggered Arms. in Proceedings of the 40^thInternational Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 202, ML Research Press, 40th International Conference on Machine Learning (ICML 2023), Honolulu, Hawaii, United States, 23/07/23. <https://proceedings.mlr.press/v202/liu23bf.html>

Contextual Combinatorial Bandits with Probabilistically Triggered Arms. / Liu, Xutong; Zuo, Jinhang; Wang, Siwei et al.
Proceedings of the 40^thInternational Conference on Machine Learning. ML Research Press, 2023. (Proceedings of Machine Learning Research; Vol. 202).

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

TY - GEN

T1 - Contextual Combinatorial Bandits with Probabilistically Triggered Arms

AU - Liu, Xutong

AU - Zuo, Jinhang

AU - Wang, Siwei

AU - Lui, John C.S.

AU - Hajiesmaili, Mohammad

AU - Wierman, Adam

AU - Chen, Wei

PY - 2023/7

Y1 - 2023/7

N2 - We study contextual combinatorial bandits with probabilistically triggered arms (C2MAB-T) under a variety of smoothness conditions that capture a wide range of applications, such as contextual cascading bandits and contextual influence maximization bandits. Under the triggering probability modulated (TPM) condition, we devise the C2-UCB-T algorithm and propose a novel analysis that achieves an Õ(d√KT) regret bound, removing a potentially exponentially large factor O(1/pmin), where d is the dimension of contexts, pmin is the minimum positive probability that any arm can be triggered, and batch-size K is the maximum number of arms that can be triggered per round. Under the variance modulated (VM) or triggering probability and variance modulated (TPVM) conditions, we propose a new variance-adaptive algorithm VAC2-UCB and derive a regret bound Õ(d√T), which is independent of the batch-size K. As a valuable by-product, our analysis technique and variance-adaptive algorithm can be applied to the CMAB-T and C2MAB setting, improving existing results there as well. We also include experiments that demonstrate the improved performance of our algorithms compared with benchmark algorithms on synthetic and real-world datasets. © 2023 by the author(s)

AB - We study contextual combinatorial bandits with probabilistically triggered arms (C2MAB-T) under a variety of smoothness conditions that capture a wide range of applications, such as contextual cascading bandits and contextual influence maximization bandits. Under the triggering probability modulated (TPM) condition, we devise the C2-UCB-T algorithm and propose a novel analysis that achieves an Õ(d√KT) regret bound, removing a potentially exponentially large factor O(1/pmin), where d is the dimension of contexts, pmin is the minimum positive probability that any arm can be triggered, and batch-size K is the maximum number of arms that can be triggered per round. Under the variance modulated (VM) or triggering probability and variance modulated (TPVM) conditions, we propose a new variance-adaptive algorithm VAC2-UCB and derive a regret bound Õ(d√T), which is independent of the batch-size K. As a valuable by-product, our analysis technique and variance-adaptive algorithm can be applied to the CMAB-T and C2MAB setting, improving existing results there as well. We also include experiments that demonstrate the improved performance of our algorithms compared with benchmark algorithms on synthetic and real-world datasets. © 2023 by the author(s)

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

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

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

T3 - Proceedings of Machine Learning Research

BT - Proceedings of the 40th International Conference on Machine Learning

PB - ML Research Press

T2 - 40th International Conference on Machine Learning (ICML 2023)

Y2 - 23 July 2023 through 29 July 2023

ER -

Contextual Combinatorial Bandits with Probabilistically Triggered Arms

Abstract

Publication series

Conference

Funding

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this