Timezone: »
Oral
Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits
Zeyuan Allen-Zhu · Sebastien Bubeck · Yuanzhi Li
Regret bounds in online learning compare the player's performance to $L*$, the optimal performance in hindsight with a fixed strategy. Typically such bounds scale with the square root of the time horizon $T$. The more refined concept of first-order regret bound replaces this with a scaling $\sqrt{L*}$, which may be much smaller than $\sqrt{T}$.It is well known that minor variants of standard algorithms satisfy first-order regret bounds in the full information and multi-armed bandit settings. In a COLT 2017 open problem, Agarwal, Krishnamurthy, Langford, Luo, and Schapire raised the issue that existing techniques do not seem sufficient to obtain first-order regret bounds for the contextual bandit problem. In the present paper, we resolve this open problem by presenting a new strategy based on augmenting the policy space.
Author Information
Zeyuan Allen-Zhu (Microsoft Research AI)
Sebastien Bubeck (Microsoft Research)
Yuanzhi Li (Princeton University)
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Poster: Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits »
Thu. Jul 12th 04:15 -- 07:00 PM Room Hall B #124
More from the Same Authors
-
2021 : Ranking Architectures by Feature Extraction Capabilities »
Debadeepta Dey · Shital Shah · Sebastien Bubeck -
2021 : A Universal Law of Robustness via Isoperimetry »
Sebastien Bubeck · Mark Sellke -
2022 Poster: Data Augmentation as Feature Manipulation »
Ruoqi Shen · Sebastien Bubeck · Suriya Gunasekar -
2022 Spotlight: Data Augmentation as Feature Manipulation »
Ruoqi Shen · Sebastien Bubeck · Suriya Gunasekar -
2021 : A Universal Law of Robustness via Isoperimetry »
Sebastien Bubeck · Mark Sellke -
2020 Poster: Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization »
Hadrien Hendrikx · Lin Xiao · Sebastien Bubeck · Francis Bach · Laurent Massoulié -
2020 Poster: Online Learning for Active Cache Synchronization »
Andrey Kolobov · Sebastien Bubeck · Julian Zimmert -
2019 Poster: A Convergence Theory for Deep Learning via Over-Parameterization »
Zeyuan Allen-Zhu · Yuanzhi Li · Zhao Song -
2019 Oral: A Convergence Theory for Deep Learning via Over-Parameterization »
Zeyuan Allen-Zhu · Yuanzhi Li · Zhao Song -
2019 Poster: Adversarial examples from computational constraints »
Sebastien Bubeck · Yin Tat Lee · Eric Price · Ilya Razenshteyn -
2019 Oral: Adversarial examples from computational constraints »
Sebastien Bubeck · Yin Tat Lee · Eric Price · Ilya Razenshteyn -
2018 Poster: An Alternative View: When Does SGD Escape Local Minima? »
Bobby Kleinberg · Yuanzhi Li · Yang Yuan -
2018 Poster: Katyusha X: Simple Momentum Method for Stochastic Sum-of-Nonconvex Optimization »
Zeyuan Allen-Zhu -
2018 Poster: The Well-Tempered Lasso »
Yuanzhi Li · Yoram Singer -
2018 Oral: The Well-Tempered Lasso »
Yuanzhi Li · Yoram Singer -
2018 Oral: An Alternative View: When Does SGD Escape Local Minima? »
Bobby Kleinberg · Yuanzhi Li · Yang Yuan -
2018 Oral: Katyusha X: Simple Momentum Method for Stochastic Sum-of-Nonconvex Optimization »
Zeyuan Allen-Zhu -
2017 Poster: Near-Optimal Design of Experiments via Regret Minimization »
Zeyuan Allen-Zhu · Yuanzhi Li · Aarti Singh · Yining Wang -
2017 Poster: Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks »
Kevin Scaman · Francis Bach · Sebastien Bubeck · Yin Tat Lee · Laurent Massoulié -
2017 Talk: Near-Optimal Design of Experiments via Regret Minimization »
Zeyuan Allen-Zhu · Yuanzhi Li · Aarti Singh · Yining Wang -
2017 Talk: Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks »
Kevin Scaman · Francis Bach · Sebastien Bubeck · Yin Tat Lee · Laurent Massoulié -
2017 Poster: Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition »
Zeyuan Allen-Zhu · Yuanzhi Li -
2017 Poster: Faster Principal Component Regression and Stable Matrix Chebyshev Approximation »
Zeyuan Allen-Zhu · Yuanzhi Li -
2017 Poster: Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter »
Zeyuan Allen-Zhu -
2017 Talk: Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter »
Zeyuan Allen-Zhu -
2017 Talk: Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition »
Zeyuan Allen-Zhu · Yuanzhi Li -
2017 Talk: Faster Principal Component Regression and Stable Matrix Chebyshev Approximation »
Zeyuan Allen-Zhu · Yuanzhi Li -
2017 Poster: Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU »
Zeyuan Allen-Zhu · Yuanzhi Li -
2017 Poster: Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations »
Yuanzhi Li · Yingyu Liang -
2017 Talk: Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations »
Yuanzhi Li · Yingyu Liang -
2017 Talk: Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU »
Zeyuan Allen-Zhu · Yuanzhi Li -
2017 Tutorial: Recent Advances in Stochastic Convex and Non-Convex Optimization »
Zeyuan Allen-Zhu