Research map / Bandits and online learning / Online convex optimization and games
Non-Stationary Lipschitz Bandits
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.
Proposes Multi-Depth Bin Elimination (MDBE), a parameter-free algorithm for non-stationary Lipschitz bandits that tracks significant shifts via a dyadic-tree discretization with multi-depth replays, achieving minimax-optimal Õ(L̃^{1/3} T^{2/3}) dynamic regret.
Problem
Dynamic regret minimization in Lipschitz bandits over a continuous arm space [0,1] where mean reward functions can change arbitrarily over time, without knowing the degree of non-stationarity.
Approach
Extends significant-shift tracking from K-armed bandits to continuous arms by monitoring cumulative gaps between dyadic bins at multiple depths simultaneously, using importance-weighted estimates, bin eviction, and depth-dependent replays scheduled with probability sqrt(8^d/(s-tau)) so that a single sample updates all its containing bins.
Key results
- Proves a lower bound of order L̃^{1/3} T^{2/3} on expected dynamic regret for non-stationary Lipschitz bandits with L̃ significant shifts.
- MDBE achieves expected dynamic regret of order log^2(T) * sum_i (tau_i - tau_{i-1})^{2/3}, i.e. Õ(L̃^{1/3} T^{2/3}) without prior knowledge, matching the lower bound up to polylog factors.
- Corollary gives Õ(T^{2/3} + V_T^{1/4} T^{3/4}) in terms of total variation, also minimax optimal up to polylog factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use hierarchical multi-depth discretization and replays to adaptively detect significant shifts without prior knowledge of their number | Multi-Depth Bin Elimination (MDBE) · Non-stationary Lipschitz bandits | expected dynamic regret: \tilde{O}(\tilde{L}_T^{1/3}T^{2/3}) | Helped |
| Use Multi-Depth Bin Elimination to adapt to total variation without prior knowledge of V_T | Non-stationary Lipschitz bandits · Non-stationary Lipschitz bandits with total variation V_T | expected dynamic regret: \bar{c}_2\log^2(T)\left( T^{2/3} + V_T^{1/4}T^{3/4}\right) | Helped |
Limitations
- Mainly theoretical; computational efficiency is not optimized and empirical evaluation is limited to a synthetic example.
- Analysis is for 1-Lipschitz rewards on [0,1]; extensions to Hölder and multi-dimensional settings are only sketched.
- Relies on the oblivious adversary model and a union-bound concentration argument with polylog factors.
Experimental setup
Metrics: expected dynamic regret
Builds on: Lipschitz bandits MASTER significant shifts (K-armed non-stationary bandits) Successive Elimination
Closest papers by meaning
- Tracking Most Significant Shifts in Infinite-Armed Bandits (ICML 2025 · similarity 0.90)
- Non-stationary Bandit Convex Optimization: A Comprehensive Study (NeurIPS 2025 · similarity 0.90)
- Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits (NeurIPS 2025 · similarity 0.89)
- Lipschitz Dueling Bandits over Continuous Action Spaces (NeurIPS 2026 · similarity 0.89)
- Block Optimism for Nonstationary Bandits with Latent Linear Dynamics (NeurIPS 2026 · similarity 0.88)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · 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.