Research map / Bandits and online learning / Online convex optimization and games
Regret Bounds for Episodic Risk-Sensitive Linear Quadratic Regulator
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 a least-squares greedy algorithm achieving polylog-regret (O~(log N)) under an identifiability assumption, and an exploration-noise least-squares algorithm achieving O~(sqrt N) regret, for episodic discrete-time risk-sensitive LEQR with unknown dynamics.
Problem
Online adaptive control of the finite-horizon episodic linear exponential-of-quadratic regulator (risk-sensitive LQR) with unknown system matrices; no prior regret bounds existed for this setting.
Approach
Adapts epoch-based least-squares greedy control from risk-neutral continuous-time LQR to discrete-time LEQR, using perturbation analysis of the two-step modified Riccati equation and a risk-sensitive suboptimality gap expressed through controller mismatch; a second algorithm adds Gaussian exploration noise with per-episode least-squares updates to obtain sqrt(N) regret without identifiability.
Key results
- Least-squares greedy algorithm (no exploration) achieves O~(log N) regret, i.e. O(log N * log log N), under an identifiability assumption (self-exploration via time-varying optimal K_t).
- Least-squares algorithm with Gaussian exploration noise achieves O~(sqrt N) regret without the identifiability assumption.
- Simulations show regret increases in horizon T and misspecifying gamma (including gamma=0) degrades regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use least-squares greedy control without exploration noise under the identifiability assumption | Episodic LEQR · Episodic LEQR, identifiability assumption satisfied | regret: O(log N · log log(N)) | Helped |
| Add Gaussian exploration noise to the least-squares-based algorithm | Episodic LEQR · Episodic LEQR, without identifiability assumption | regret: \widetilde{\mathcal{O}}(\sqrt{N}) | Helped |
| Update parameter estimates less frequently using increasing-length epochs | Least-squares greedy · System 1 | regret | Hurt |
| Use a misspecified risk-aversion parameter instead of the true value γ=0.1 | Least-squares greedy · System 1, T=3 | regret | Hurt |
| Set the risk-aversion parameter to γ=0 instead of the true value γ=0.1 | Least-squares greedy · System 1, T=3 | regret | Hurt |
| Increase the time horizon T | Least-squares greedy · System 1, γ=0.01 | regret | Hurt |
Surprising findings
- Greedy algorithm without exploration can incur large initial regret, performing worse than the exploration-based algorithm on the tested instance.
Limitations
- Identifiability assumption required for the logarithmic bound; the sqrt(N) algorithm is needed otherwise.
- Analysis restricted to finite-horizon episodic setting; infinite-horizon average-reward extension open.
- Bounds involve constants that grow with gamma and horizon T, and the greedy algorithm requires knowledge of N unless doubling trick is used.
Experimental setup
Benchmarks: simulated LEQR System 1 (from Section 6.1 of prior work) random 7-dim system (System 2) flying robot LEQR (System 3)
Metrics: cumulative regret 95% confidence interval over 150 runs
Baselines: Algorithm with gamma=0 (risk-neutral LQR policy)
Builds on: certainty-equivalence LQR regret (Mania et al.) greedy least-squares episodic continuous-time LQR (Basei et al.) self-normalized martingale bounds (Abbasi-Yadkori et al.)
Closest papers by meaning
- Naive Exploration is Optimal for Online LQR (ICML 2020 · similarity 0.92)
- Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator (NeurIPS 2018 · similarity 0.91)
- Learning Linear-Quadratic Regulators Efficiently with only $\sqrtT$ Regret (ICML 2019 · similarity 0.90)
- Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently (ICML 2020 · similarity 0.90)
- Infinite-Horizon Distributionally Robust Regret-Optimal Control (ICML 2024 · similarity 0.87)
- Online Learning in Risk Sensitive constrained MDP (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.