On Kernelized Multi-Armed Bandits with Constraints
| dc.contributor.author | Zhou, Xingyu | en |
| dc.contributor.author | Ji, Bo | en |
| dc.date.accessioned | 2024-02-19T14:06:43Z | en |
| dc.date.available | 2024-02-19T14:06:43Z | en |
| dc.date.issued | 2022-11-30 | en |
| dc.description.abstract | We study a stochastic bandit problem with a general unknown reward function and a general unknown constraint function. Both functions can be non-linear (even non-convex) and are assumed to lie in a reproducing kernel Hilbert space (RKHS) with a bounded norm. In contrast to safety-type hard constraints studied in prior works, we consider soft constraints that may be violated in any round as long as the cumulative violations are small. Our ultimate goal is to study how to utilize the nature of soft constraints to attain a finer complexity-regret-constraint trade-off in the kernelized bandit setting. To this end, leveraging primal-dual optimization, we propose a general framework for both algorithm design and performance analysis. This framework builds upon a novel sufficient condition, which not only is satisfied under general exploration strategies, including upper confidence bound (UCB), Thompson sampling (TS), and new ones based on random exploration, but also enables a unified analysis for showing both sublinear regret and sublinear or even zero constraint violation. We demonstrate the superior performance of our proposed algorithms via numerical experiments based on both synthetic and real-world datasets. Along the way, we also make the first detailed comparison between two popular methods for analyzing constrained bandits and Markov decision processes (MDPs) by discussing the key difference and some subtleties in the analysis, which could be of independent interest to the communities. | en |
| dc.description.notes | Yes, full paper (Peer reviewed?) | en |
| dc.description.version | Published version | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.isbn | 9781713871088 | en |
| dc.identifier.issn | 1049-5258 | en |
| dc.identifier.orcid | Ji, Bo [0000-0003-0149-7509] | en |
| dc.identifier.uri | https://hdl.handle.net/10919/118013 | en |
| dc.identifier.volume | 35 | en |
| dc.language.iso | en | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.title | On Kernelized Multi-Armed Bandits with Constraints | en |
| dc.title.serial | Advances in Neural Information Processing Systems | en |
| dc.type | Conference proceeding | en |
| dc.type.dcmitype | Text | en |
| dc.type.other | Conference Proceeding | en |
| pubs.organisational-group | /Virginia Tech | en |
| pubs.organisational-group | /Virginia Tech/Engineering | en |
| pubs.organisational-group | /Virginia Tech/Engineering/Computer Science | en |
| pubs.organisational-group | /Virginia Tech/All T&R Faculty | en |
| pubs.organisational-group | /Virginia Tech/Engineering/COE T&R Faculty | en |