Independent Reading · 2025
Non-Stationary Lipschitz Bandits
Nicolas Nguyen, Solenne Gaucher, and Claire Vernade · NeurIPS
Non-Stationary BanditsLipschitz BanditsAdaptive Learning
Full text
Read the Paper
Use View PDF or Download PDF to read the full paper on this device.
Paper Information
- Authors
- Nicolas Nguyen, Solenne Gaucher, and Claire Vernade
- Venue
- NeurIPS · 2025
Summary
This paper studies continuous-action Lipschitz bandits whose reward functions may change arbitrarily over time.
Core Idea
A hierarchical discretization can jointly adapt its resolution and detect significant shifts without knowing the degree of non-stationarity in advance.
Method
The authors introduce MDBE, combining multiscale discretization, restarts, and replay-based exploration to achieve minimax-optimal dynamic regret.
Key Takeaways
- Continuous action spaces make change detection and discretization inseparable.
- Significant shifts give a more refined complexity measure than counting every change.
- Optimal adaptation is possible without prior non-stationarity parameters.
Questions
- How does MDBE behave when smoothness varies across the action space?
- Can the framework extend to contextual or high-dimensional continuous actions?