Research map / Bandits and online learning / Multi-armed bandits
PRODuctive bandits: Importance Weighting No More
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that variants of the Prod (product-update) algorithm, derived as linear approximations of OMD, achieve optimal regret for adversarial and stochastic bandits, including an importance-weighting-free variant and a best-of-both-worlds variant.
Problem
Prod was conjectured to be fundamentally sub-optimal for multi-armed bandits; prior bandit Prod variant (WSU-UX) only achieves T^{2/3} regret, which also limits incentive-compatible bandit learning.
Approach
Interpret Prod updates as first-order approximations of OMD; correct the approximation error via loss biasing (WSU-UX variant), use a Logbarrier potential so that masked losses need no importance weighting (LB-Prod), and use a 1/2-Tsallis potential with biasing to get best-of-both-worlds (TS-Prod).
Key results
- WSU-UX with loss biasing achieves O(sqrt(KT log K)) regret for adversarial bandits, improving on the T^{2/3} of prior Prod bandit variants.
- LB-Prod, an importance-weighting-free Prod variant, achieves O(sqrt(KT log T)) regret.
- TS-Prod achieves O(sqrt(KT) + K log T) adversarial regret and O(log T) stochastic regret (best-of-both-worlds).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add the Equation 1 loss bias to WSU-UX | WSU-UX · Adversarial MAB | regret: T2/3 -> O(√(KT log(K))) | Helped |
| Use masked, non-importance-weighted losses with Logbarrier normalization | Prod bandit updates · Adversarial MAB | regret: O(√(KT log(T))) | Helped |
| Use 1/2-Tsallis updates with the specified decreasing learning rate and bias | Prod bandit updates · Adversarial MAB | regret: O(√(KT) + K log(T)) | Helped |
| Use 1/2-Tsallis updates with the specified decreasing learning rate and bias | Prod bandit updates · Stochastic MAB | regret: O(∑i≠i⋆ log(T)/∆i) | Helped |
| Use the perturbed OMD update in Equation 4 | TS-Prod · Adversarial MAB | regret: O(√(KT)) | Helped |
| Use the perturbed OMD update in Equation 4 | TS-Prod · Stochastic MAB | regret: O(∑i≠i⋆ log(T)/∆i + K log²(1/∆min)/∆min + K3/2) | Helped |
Surprising findings
- The conjectured separation between full-information Prod and bandit Prod does not hold; Prod variants can achieve optimal bandit regret.
- Logbarrier-based Prod works on masked, non-importance-weighted losses without any loss correction.
Limitations
- Purely theoretical; no empirical experiments reported.
- Regret bounds carry log factors (log T for LB-Prod) and require tuned learning rates.
Experimental setup
Metrics: pseudo-regret (theoretical bound)
Baselines: WSU-UX Exp3 Tsallis-INF Logbarrier bandit algorithms
Builds on: WSU-UX Tsallis-INF Exp3 Fang et al. 2022 stabilized OMD Logbarrier OMD
Closest papers by meaning
- Near-Optimal Regret in Adversarial Kernel Bandits (NeurIPS 2026 · similarity 0.88)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.88)
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.87)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.87)
- Leveraging (Biased) Information: Multi-armed Bandits with Offline Data (ICML 2024 · similarity 0.87)
- Bandits with Ranking Feedback (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.