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
Open official paper

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?