arXiv 27 Dec 2023 · Machine Learning
arXiv:2312.16489 · PDF · DOI · OpenAlex · Extracted main text
This study investigates the problem of $K$-armed linear contextual bandits, an instance of the multi-armed bandit problem, under an adversarial corruption. At each round, a decision-maker observes an independent and identically distributed context and then selects an arm based on the context and past observations. After selecting an arm, the decision-maker incurs a loss corresponding to the selected arm. The decision-maker aims to minimize the cumulative loss over the trial. The goal of this study is to develop a strategy that is effective in both stochastic and adversarial environments, with theoretical guarantees. We first formulate the problem by introducing a novel setting of bandits with adversarial corruption, referred to as the contextual adversarial regime with a self-bounding constraint. We assume linear models for the relationship between the loss and the context. Then, we propose a strategy that extends the RealLinExp3 by Neu & Olkhovskaya (2020) and the Follow-The-Regularized-Leader (FTRL). The regret of our proposed algorithm is shown to be upper-bounded by $O\left(\min\left{\frac{(\log(T))^3}{\Delta_{*}} + \sqrt{\frac{C(\log(T))^3}{\Delta_{*}}},\ \ \sqrt{T}(\log(T))^2\right}\right)$, where $T \in\mathbb{N}$ is the number of rounds, $\Delta_{*} > 0$ is the constant minimum gap between the best and suboptimal arms for any context, and $C\in[0, T] $ is an adversarial corruption parameter. This regret upper bound implies $O\left(\frac{(\log(T))^3}{\Delta_{*}}\right)$ in a stochastic environment and by $O\left( \sqrt{T}(\log(T))^2\right)$ in an adversarial environment. We refer to our strategy as the Best-of-Both-Worlds (BoBW) RealFTRL, due to its theoretical guarantees in both stochastic and adversarial regimes.
appendix boundary found by appendix_command · 73% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Gergely Neu and Julia Olkhovskaya (2020) Efficient and robust algorithms for adversarial linear contextual bandits | 1.000 | 16 | 5 | 100% |
| 2 | Shinji Ito, Taira Tsuchiya, and Junya Honda (2022) Nearly optimal best-of-both-worlds algorithms for online learning with feedback graphs self | 1.000 | 5 | 3 | 100% |
| 3 | Ke Li, Yun Yang, and Naveen N. Narisetty (2021) Regret lower bound and optimal algorithm for high-dimensional contextual linear bandit | 0.928 | 4 | 3 | 100% |
| 4 | Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu (2022) Nearly optimal algorithms for linear contextual bandits with adversarial corruptions | 0.874 | 7 | 2 | 100% |
| 5 | Anupam Gupta, Tomer Koren, and Kunal Talwar (2019) Better algorithms for stochastic bandits with adversarial corruptions | 0.874 | 5 | 2 | 100% |
| 6 | Thodoris Lykouris and Sergei Vassilvtiskii (2018) Competitive caching with machine learned advice | 0.874 | 5 | 2 | 100% |
| 7 | Heyang Zhao, Dongruo Zhou, and Quanquan Gu (2021) Linear contextual bandits with adversarial corruptions, 2021 | 0.811 | 4 | 2 | 100% |
| 8 | Haolin Liu, Chen-Yu Wei, and Julian Zimmert (2023) Bypassing the simulator: Near-optimal adversarial linear contextual bandits | 0.737 | 3 | 2 | 100% |
| 9 | Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári (2011) Improved algorithms for linear stochastic bandits | 0.585 | 3 | 1 | 100% |
| 10 | Julian Zimmert and Yevgeny Seldin (2021) Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits | 0.585 | 3 | 1 | 100% |
Showing the top 10 of 38 scored citations.