Lune

NeurIPS2024Top-tier venue

PRODuctive bandits: Importance Weighting No More

Julian Zimmert, Teodor Vanislavov Marinov

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses cites Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and PracticalityChaiwon Kim, Jongyeong Lee, Min-hwan OhICML 2026

Builds on5

  1. Adapting to Misspecification in Contextual BanditsDylan J. Foster, Claudio Gentile, Mehryar Mohri, Julian ZimmertNeurIPS 2020 · 111 citations
  2. 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
  3. Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated BonusesHaipeng Luo, Chen-Yu Wei, Chung-Wei LeeNeurIPS 2021 · 59 citations
  4. Online mirror descent and dual averaging: keeping pace in the dynamic caseHuang Fang, Nick Harvey, Victor S. Portella, Michael P. FriedlanderICML 2020 · 38 citations
  5. No-Regret and Incentive-Compatible Online LearningRupert Freeman, David M. Pennock, Chara Podimata, Jennifer Wortman VaughanICML 2020 · 19 citations

Related papers

  1. Versatile Dueling Bandits: Best-of-both World Analyses for Learning from Relative PreferencesAadirupa Saha, Pierre GaillardICML 2022 · 30 citations
  2. Tight First- and Second-Order Regret Bounds for Adversarial Linear BanditsShinji Ito, Shuichi Hirahara, Tasuku Soma, Yuichi YoshidaNeurIPS 2020 · 24 citations
  3. Rate-Optimal Policy Optimization for Linear Markov Decision ProcessesUri Sherman, Alon Cohen, Tomer Koren, Yishay MansourICML 2024 · 11 citations
  4. Improved Best-of-Both-Worlds Regret for Bandits with Delayed FeedbackOfir Schlisselberg, Tal Lancewicki, Peter Auer, Yishay MansourNeurIPS 2025 · 2 citations
  5. An Exploration-by-Optimization Approach to Best of Both Worlds in Linear BanditsShinji Ito, Kei TakemuraNeurIPS 2023 · 7 citations
Dusk over the sea between two cliffs drawn in fine vertical lines