Timezone: »
We propose novel algorithms with first- and second-order regret bounds for adversarial linear bandits. These regret bounds imply that our algorithms perform well when there is an action achieving a small cumulative loss or the loss has a small variance. In addition, we need only assumptions weaker than those of existing algorithms; our algorithms work on discrete action sets as well as continuous ones without a priori knowledge about losses, and they run efficiently if a linear optimization oracle for the action set is available. These results are obtained by combining optimistic online optimization, continuous multiplicative weight update methods, and a novel technique that we refer to as distribution truncation. We also show that the regret bounds of our algorithms are tight up to polylogarithmic factors.
Author Information
Shinji Ito (NEC Corporation)
Shuichi Hirahara (National Institute of Informatics)
Tasuku Soma (University of Tokyo)
Yuichi Yoshida (National Institute of Informatics and Preferred Infrastructure, Inc.)
Related Events (a corresponding poster, oral, or spotlight)
-
2020 Poster: Tight First- and Second-Order Regret Bounds for Adversarial Linear Bandits »
Thu. Dec 10th 05:00 -- 07:00 AM Room Poster Session 4 #1280
More from the Same Authors
-
2023 Poster: An Exploration-by-Optimization Approach to Best of Both Worlds in Linear Bandits »
Shinji Ito · Kei Takemura -
2023 Poster: Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds »
Taira Tsuchiya · Shinji Ito · Junya Honda -
2023 Poster: Bandit Task Assignment with Unknown Processing Time »
Shinji Ito · Daisuke Hatano · Hanna Sumita · Kei Takemura · Takuro Fukunaga · Naonori Kakimura · Ken-Ichi Kawarabayashi -
2023 Poster: A Batch-to-Online Transformation under Random-Order Model »
Jing Dong · Yuichi Yoshida -
2022 Poster: Average Sensitivity of Euclidean k-Clustering »
Yuichi Yoshida · Shinji Ito -
2022 Poster: Single Loop Gaussian Homotopy Method for Non-convex Optimization »
Hidenori Iwakiri · Yuhang Wang · Shinji Ito · Akiko Takeda -
2022 Poster: Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs »
Shinji Ito · Taira Tsuchiya · Junya Honda -
2021 Poster: On Optimal Robustness to Adversarial Corruption in Online Decision Problems »
Shinji Ito -
2021 Poster: Hybrid Regret Bounds for Combinatorial Semi-Bandits and Adversarial Linear Bandits »
Shinji Ito -
2020 Poster: Improved Algorithms for Online Submodular Maximization via First-order Regret Bounds »
Nicholas Harvey · Christopher Liaw · Tasuku Soma -
2020 Poster: A Tight Lower Bound and Efficient Reduction for Swap Regret »
Shinji Ito -
2020 Poster: Delay and Cooperation in Nonstochastic Linear Bandits »
Shinji Ito · Daisuke Hatano · Hanna Sumita · Kei Takemura · Takuro Fukunaga · Naonori Kakimura · Ken-Ichi Kawarabayashi -
2020 Spotlight: A Tight Lower Bound and Efficient Reduction for Swap Regret »
Shinji Ito -
2020 Spotlight: Delay and Cooperation in Nonstochastic Linear Bandits »
Shinji Ito · Daisuke Hatano · Hanna Sumita · Kei Takemura · Takuro Fukunaga · Naonori Kakimura · Ken-Ichi Kawarabayashi -
2019 Poster: Improved Regret Bounds for Bandit Combinatorial Optimization »
Shinji Ito · Daisuke Hatano · Hanna Sumita · Kei Takemura · Takuro Fukunaga · Naonori Kakimura · Ken-Ichi Kawarabayashi -
2019 Poster: Submodular Function Minimization with Noisy Evaluation Oracle »
Shinji Ito -
2019 Poster: Oracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback »
Shinji Ito · Daisuke Hatano · Hanna Sumita · Kei Takemura · Takuro Fukunaga · Naonori Kakimura · Ken-Ichi Kawarabayashi -
2018 Poster: Fast greedy algorithms for dictionary selection with generalized sparsity constraints »
Kaito Fujii · Tasuku Soma -
2018 Spotlight: Fast greedy algorithms for dictionary selection with generalized sparsity constraints »
Kaito Fujii · Tasuku Soma -
2017 Poster: Fitting Low-Rank Tensors in Constant Time »
Kohei Hayashi · Yuichi Yoshida -
2017 Spotlight: Fitting Low-Rank Tensors in Constant Time »
Kohei Hayashi · Yuichi Yoshida -
2016 Poster: Minimizing Quadratic Functions in Constant Time »
Kohei Hayashi · Yuichi Yoshida -
2015 Poster: A Generalization of Submodular Cover via the Diminishing Return Property on the Integer Lattice »
Tasuku Soma · Yuichi Yoshida -
2015 Poster: Monotone k-Submodular Function Maximization with Size Constraints »
Naoto Ohsaka · Yuichi Yoshida