Research map / Bandits and online learning / Online convex optimization and games
Non-stationary Bandit Convex Optimization: A Comprehensive Study
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.
Studies non-stationary bandit convex optimization under switch, variation and path-length measures, proposing polynomial-time TEWA-SE (minimax-optimal for strongly convex losses) and exponential-weights cExO (optimal in S and Δ for general convex losses, not poly-time).
Problem
Minimizing dynamic, switching and path-length regret in bandit convex optimization (zeroth-order, one-point feedback) under non-stationarity measured by number of switches S, total variation Δ, and path length P.
Approach
Adapts the sleeping-experts / tilted exponentially weighted average framework of MetaGrad-style OCO to bandits via one-point spherical gradient estimates and a quadratic surrogate loss with a geometric covering of intervals and exponential learning-rate grid; a second method runs exponential weights (ExO) on a discretized, clipped action set to get √B adaptive regret for general convex losses.
Key results
- TEWA-SE achieves min{d√(ST), d^{2/3}Δ^{1/3}T^{2/3}} dynamic regret for strongly convex losses, matched by a lower bound Ω(d√(ST) ∧ d^{2/3}Δ^{1/3}T^{2/3}), hence minimax-optimal in T, d, S, Δ.
- cExO achieves d^{5/2}√(ST) switching regret and d^{5/3}Δ^{1/3}T^{2/3} dynamic regret, minimax-optimal in T, S, Δ but suboptimal in d.
- cExO path-length regret P^{1/3}T^{2/3} improves on prior P^{1/4}T^{3/4} rate for general convex losses.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use TEWA-SE for strongly convex losses with known S and Δ | Bandit convex optimization · Dynamic regret | regret upper bound: d\sqrt{ST}, d^{\frac{2}{3}}\Delta^{\frac{1}{3}} T^{\frac{2}{3}} | Helped |
| use cExO for general convex losses with known S and Δ | Bandit convex optimization · Dynamic regret | regret upper bound: d^{\frac{5}{2}}\sqrt{ST}, d^{\frac{5}{3}}\Delta^{\frac{1}{3}}T^{\frac{2}{3}} | Helped |
| use cExO instead of the previous best-known path-length rate for general convex losses | Bandit convex optimization · Path-length regret | regret upper bound: P^{\frac{1}{4}}T^{\frac{3}{4}}; P^{\frac{1}{3}}T^{\frac{2}{3}} | Helped |
| use TEWA-SE for general convex losses | Bandit convex optimization · Switching regret | regret upper bound: \sqrt{d}S^{\frac{1}{4}}T^{\frac{3}{4}} | Hurt |
| equip TEWA-SE with the Bandit-over-Bandit framework to select the interval size without knowing non-stationarity measures | TEWA-SE · General convex and strongly convex losses | regret upper bound: d^{\frac{1}{3}}T^{\frac{5}{6}}; d^{\frac{1}{2}}T^{\frac{3}{4}} | Hurt |
| equip cExO with the Bandit-over-Bandit framework to select the interval size without knowing non-stationarity measures | cExO · Non-stationary bandit convex optimization | regret upper bound: d^{\frac{5}{4}}T^{\frac{3}{4}} | Hurt |
| use cExO rather than TEWA-SE for general convex path-length regret | Bandit convex optimization · Path-length regret | regret upper bound: d^{\frac{2}{5}}P^{\frac{1}{5}} T^{\frac{4}{5}}; d^{\frac{5}{3}} P^{\frac{1}{3}}T^{\frac{2}{3}} | Helped |
Limitations
- cExO is not polynomial-time computable
- TEWA-SE suboptimal T^{3/4} rate for general convex losses
- Path-length lower bound does not match upper bounds
Experimental setup
Metrics: dynamic regret switching regret path-length regret adaptive regret
Baselines: Besbes et al. dynamic regret BCO bound Suggala and Netrapalli style BCO results prior P^{1/4}T^{3/4} path-length bounds
Builds on: MetaGrad Exploration by Optimization (ExO) Bandit-over-Bandit Geometric Covering intervals one-point gradient estimation
Closest papers by meaning
- Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · similarity 0.91)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.90)
- Tight Rates for Bandit Control Beyond Quadratics (NeurIPS 2024 · similarity 0.90)
- Non-Stationary Lipschitz Bandits (NeurIPS 2025 · similarity 0.90)
- Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits (NeurIPS 2025 · similarity 0.89)
- Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update (NeurIPS 2025 · similarity 0.89)
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.