Research map / Bandits and online learning / Online convex optimization and games
Handling Heterogeneous Curvatures in Bandit LQR Control
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 bandit LQR control with heterogeneous (per-round) cost curvatures and semi-adversarial disturbances, using a lossless "with-history" reduction to BCO with memory and a Newton-decrement stability analysis to get interpolated regret bounds.
Problem
Online LQR with bandit feedback where cost curvatures vary across rounds (heterogeneous), rather than a uniform strong convexity lower bound, so that algorithms can adapt to true curvatures and remain robust to corrupted or decaying quadraticity.
Approach
Replaces truncation-based reduction with a lossless "with-history" reduction (avoids hard-to-control barrier truncation errors), then bounds the key local-norm stability term via the Newton decrement from interior-point methods, yielding curvature-adaptive regret bounds that interpolate between convex and quadratic rates.
Key results
- For Lipschitz quadratic costs, the algorithm achieves e O(alpha^{-1/3} T^{2/3}), a new bound in bandit LQR, interpolating between O(T^{3/4}) for convex and this for quadratic costs.
- For smooth quadratic costs, the regret is e O(alpha^{-1/2} sqrt(T)), matching the T-dependence of Sun et al. (2023) with a tighter curvature dependence.
- With corrupted quadraticity, smooth costs keep e O(sqrt(T)) when up to O(T^{3/4}) rounds are convex; Lipschitz costs keep e O(T^{2/3}) when up to O(T^{8/9}) rounds are convex.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Adapt Algorithm 2 to convex Lipschitz costs | Bandit LQR · Convex Lipschitz costs | expected policy regret: eO(T^{3/4}) | No clear effect |
| Use Algorithm 2 for α-quadratic Lipschitz costs | Bandit LQR · α-quadratic Lipschitz costs | expected policy regret: eO(α^{-1/3}T^{2/3}) | Helped |
| Adapt Algorithm 2 to convex smooth costs | Bandit LQR · Convex smooth costs | expected policy regret: eO(T^{2/3}) | No clear effect |
| Use Algorithm 2 for α-quadratic smooth costs | Bandit LQR · α-quadratic smooth costs | expected policy regret: eO(α^{-1/2}√T) vs eO(α^{-1}√T) | Helped |
| Allow M convex costs among α-quadratic Lipschitz costs | Algorithm 2 · Corrupted quadraticity, Lipschitz costs | expected policy regret: eO(M^{3/4} + α^{-1/3}(T−M)^{2/3}); eO(α^{-1/3}T(T−M)^{-1/3}) | Mixed |
| Allow M convex costs among α-quadratic smooth costs | Algorithm 2 · Corrupted quadraticity, smooth costs | expected policy regret: eO(√T + M^{2/3} + α^{-1/2}(T−M)^{1/2}); eO(√T + α^{-1/2}T(T−M)^{-1/2}) | Mixed |
| Allow curvature to decay as αt=t−γ | Algorithm 2 · Lipschitz costs, γ∈[0,1/4] versus γ∈(1/4,1] | expected policy regret: eO(T^{2/3+γ/3}); eO(T^{3/4}) | Mixed |
| Allow curvature to decay as αt=t−γ | Algorithm 2 · Smooth costs, γ∈[0,1/3] versus γ∈(1/3,1] | expected policy regret: eO(T^{1/2+γ/2}); eO(T^{2/3}) | Mixed |
| Use the with-history reduction instead of truncating older actions | Bandit LQR control · Bandit LQR with memory | truncation error | Helped |
| Analyze the stability term using Newton decrement | Algorithm 1 · BCO with switching cost | switching-cost control | Helped |
Surprising findings
- Lipschitzness is still required for smooth costs in bandit control, unlike the pure online setting.
Limitations
- Regret for smooth quadratic costs in the Lipschitz-and-smooth setting is not improved beyond Sun et al. (2023) in the T dependence; bounds for Lipschitz quadratic costs and general cases are sub-optimal compared to the lower bound.
- Requires Lipschitzness even for smooth costs due to the reduction.
- Analysis is limited to oblivious adversaries and known curvature lower bounds per round (known but heterogeneous curvatures).
Experimental setup
Metrics: expected policy regret (theoretical bound)
Baselines: Sun et al. (2023) Gradu et al. (2020) Cassel and Koren (2020) Luo et al. (2022)
Builds on: Sun et al. (2023) bandit LQR with optimal regret Luo et al. (2022) heterogeneous curvature BCO Cassel and Koren (2020) lazy update BCO with memory Simchowitz et al. (2020) disturbance-response policy Adaptive Online Gradient Descent (Bartlett et al., 2007)
Closest papers by meaning
- Tight Rates for Bandit Control Beyond Quadratics (NeurIPS 2024 · similarity 0.91)
- Non-stationary Bandit Convex Optimization: A Comprehensive Study (NeurIPS 2025 · similarity 0.87)
- Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · similarity 0.87)
- Exploiting Curvature in Online Convex Optimization with Delayed Feedback (ICML 2025 · similarity 0.87)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.86)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.86)
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.