PRODuctive bandits: Importance Weighting No More
Abstract
Prod is a seminal algorithm in full-information online learning, which has been conjectured to be fundamentally sub-optimal for multi-armed bandits. By leveraging the interpretation of Prod as a first-order OMD approximation, we present the following surprising results: 1. Variants of Prod can obtain optimal regret for adversarial multi-armed bandits. 2. There exists a simple and (arguably) importance-weighting free variant with optimal rate. 3. One can even achieve best-both-worlds guarantees with logarithmic regret in the stochastic regime. The bandit algorithms in this work use simple arithmetic update rules without the need of solving optimization problems typical in prior work. Finally, the results directly improve the state of the art of incentive-compatible bandits.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers1
Builds on5
- Adapting to Misspecification in Contextual BanditsDylan J. Foster, Claudio Gentile, Mehryar Mohri, Julian ZimmertNeurIPS 2020 · 111 citations
- Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPsChung-Wei Lee, Haipeng Luo, Chen-Yu Wei, Mengxiao ZhangNeurIPS 2020 · 65 citations
- Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated BonusesHaipeng Luo, Chen-Yu Wei, Chung-Wei LeeNeurIPS 2021 · 59 citations
- Online mirror descent and dual averaging: keeping pace in the dynamic caseHuang Fang, Nick Harvey, Victor S. Portella, Michael P. FriedlanderICML 2020 · 38 citations
- No-Regret and Incentive-Compatible Online LearningRupert Freeman, David M. Pennock, Chara Podimata, Jennifer Wortman VaughanICML 2020 · 19 citations
Related papers
- Versatile Dueling Bandits: Best-of-both World Analyses for Learning from Relative PreferencesAadirupa Saha, Pierre GaillardICML 2022 · 30 citations
- Tight First- and Second-Order Regret Bounds for Adversarial Linear BanditsShinji Ito, Shuichi Hirahara, Tasuku Soma, Yuichi YoshidaNeurIPS 2020 · 24 citations
- Rate-Optimal Policy Optimization for Linear Markov Decision ProcessesUri Sherman, Alon Cohen, Tomer Koren, Yishay MansourICML 2024 · 11 citations
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed FeedbackOfir Schlisselberg, Tal Lancewicki, Peter Auer, Yishay MansourNeurIPS 2025 · 2 citations
- An Exploration-by-Optimization Approach to Best of Both Worlds in Linear BanditsShinji Ito, Kei TakemuraNeurIPS 2023 · 7 citations
