Research map / Bandits and online learning / Online convex optimization and games
Finite Time Logarithmic Regret Bounds for Self-Tuning Regulation
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.
Proposes PIECE, a clipped certainty-equivalence controller with increasingly infrequent probing inputs, and proves finite-time logarithmic regret for minimum-variance self-tuning regulation (C log T for bounded noise, C log^3 T for sub-Gaussian noise).
Problem
Finite-time regret of adaptive minimum variance (self-tuning) regulation of unknown ARX systems, where no control penalty exists; prior finite-time analyses only gave sqrt(T) regret for LQ problems.
Approach
Modify certainty equivalence by clipping control inputs to a bounded set and inserting white-noise probing episodes of geometrically/super-exponentially growing length, plus a diagnostic fallback to a sparser LSE-based gain estimate, yielding logarithmic finite-time regret.
Key results
- Theory: PIECE regret is C log T for bounded noise, with leading term sigma^2(p+q-1) log T matching the Lai-Wei asymptotic constant as epsilon goes to 0.
- Theory: under sub-Gaussian noise the regret bound is C log^3 T (log T log^2(T/delta) + sigma^2(p+q-1) log^2 T).
- Simulation at T=1000 (Example II): cumulative regret CE 16224624, LW 5816, PIECE 66; Example I PIECE 36 vs CE 313 and LW 364.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PIECE instead of LW | Self-tuning regulation · Examples I–III | cumulative regret: 364 -> 36; 5816 -> 66; 15644 -> 46 | Helped |
| Use PIECE instead of CE | Self-tuning regulation · Examples I–III | cumulative regret: 313 -> 36; 16224624 -> 66; 9888 -> 46 | Helped |
| Add input clipping and increasingly infrequent probing episodes | Certainty-equivalence self-tuning regulator · Simulation experiments | cumulative regret: null | Helped |
| Use PIECE for bounded-noise regulation | ARX system · Bounded noise | regret: C log T | Helped |
| Use PIECE for sub-Gaussian-noise regulation | ARX system · Sub-Gaussian noise | regret: C log3 T | Helped |
Surprising findings
- LW has lower estimation error than PIECE in simulations, yet PIECE achieves much lower regret, indicating exploration tuned for regret costs some estimation accuracy.
Limitations
- Sub-Gaussian noise bound is C log^3 T rather than the optimal C log T; whether it can be improved is open.
- Analysis relies on known compact parameter set Θ and minimum-phase assumption; constants depend on problem-dependent quantities hidden in ≲.
- Only ARX systems analyzed; ARMAX extension left open.
Experimental setup
Datasets: simulated ARX systems (paper machine example, Examples II and III)
Benchmarks: simulated ARX systems (Examples I-III)
Metrics: cumulative regret estimation error
Baselines: certainty equivalence (CE) LW (Lai & Wei 1987) OFU StabL
Builds on: Lai & Wei 1987 adaptive minimum variance control certainty equivalence Abbasi-Yadkori & Szepesvári 2011 OFU
Closest papers by meaning
- Reinforcement Learning with Logarithmic Regret and Policy Switches (NeurIPS 2022 · similarity 0.91)
- First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach (ICML 2022 · similarity 0.89)
- Cascaded Gaps: Towards Logarithmic Regret for Risk-Sensitive Reinforcement Learning (ICML 2022 · similarity 0.89)
- Minimax Regret Bounds for Reinforcement Learning (ICML 2017 · similarity 0.89)
- Naive Exploration is Optimal for Online LQR (ICML 2020 · similarity 0.89)
- Position: Constants are Critical in Regret Bounds for Reinforcement Learning (ICML 2025 · similarity 0.87)
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.