Research map / Bandits and online learning / Online convex optimization and games
Tight Rates for Bandit Control Beyond Quadratics
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.
Gives an O~(sqrt(T)) optimal-regret algorithm for bandit non-stochastic control with adversarial perturbations and strongly convex smooth (non-quadratic) costs, by reducing to a no-memory BCO with Newton-based updates and an improved BCO-M algorithm.
Problem
Bandit non-stochastic control of partially observable LTI systems with adversarial perturbations/noise and adversarially chosen non-quadratic strongly convex costs; prior bandit methods only reached O~(T^{2/3}) for this general setting, and optimal O~(sqrt(T)) was known only for quadratic costs or s
Approach
Exploit the kappa_0-convexity induced by the affine memory structure of control (Hessian estimator H_t = G_t^T G_t computed from the known system, not from bandit loss feedback) to run a Newton-based BCO-M algorithm with occasional updates and delayed updates; reduce to no-memory BCO on the unit sphere to avoid the Cartesian-product sphere issue, giving O~(sqrt(T)) regret for general strongly conv
Key results
- Achieves O~(sqrt(T)) regret for bandit non-stochastic control with adversarial perturbations and strongly convex smooth costs, improving the prior O~(T^{2/3}) bound.
- Improved BCO-M algorithm attains O~((beta/alpha) G D sqrt(T)) regret for affine-memory losses with general smooth convex costs, removing the need for quadratic losses.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed control algorithm for adversarial perturbations, bandit feedback, and strongly-convex smooth costs | Bandit non-stochastic control · Bandit non-stochastic control with strongly-convex smooth costs | regret: $ \tilde{O}(T^{2/3})$ -> $ \tilde{O}(\sqrt{T})$ | Helped |
| Use the proposed affine-memory BCO-M algorithm | BCO-M · BCO-M with general smooth convex loss | regret: $\tilde{O}(T^{2/3})$ -> $\tilde{O}(\sqrt{T})$ | Helped |
Limitations
- Requires strong convexity of the cost functions; unclear whether it is necessary for O~(sqrt(T)) regret.
- Polynomial dependence on system parameters (e.g., kappa_sys, gamma, d_x) and assumption that system parameters are O~(1).
- Result is theoretical; the bounds hide logarithmic factors and large constants.
Experimental setup
Metrics: regret
Baselines: Gradient perturbation controller O~(T^{2/3}) bandit non-stochastic control algorithm semi-adversarial bandit control algorithm quadratic-cost bandit control algorithm
Builds on: bandit convex optimization with memory online non-stochastic control kappa-convexity Newton-based BCO occasional update reduction for BCO-M
Closest papers by meaning
- Optimal Rates for Bandit Nonstochastic Control (NeurIPS 2023 · similarity 0.94)
- Handling Heterogeneous Curvatures in Bandit LQR Control (ICML 2024 · similarity 0.91)
- Non-stationary Bandit Convex Optimization: A Comprehensive Study (NeurIPS 2025 · similarity 0.90)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.89)
- Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · similarity 0.89)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · 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.