Research map / Bandits and online learning / Online convex optimization and games
Regret Analysis of Multi-task Representation Learning for Linear-Quadratic Adaptive 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.
Analyzes regret of a shared-representation certainty-equivalent LQR algorithm for H linear systems whose dynamics lie in a common dtheta-dimensional basis, giving sqrt(T/H) regret under benign exploration and sqrt(du·dtheta)·sqrt(T) + T^{3/4}/H^{1/5} under difficult exploration.
Problem
Online adaptive linear-quadratic control of many related linear systems that share an unknown low-dimensional dynamics basis; prior regret guarantees for adaptive control are single-agent and static for representation learning.
Approach
Combines certainty-equivalent adaptive LQR with a de-biased, feature-whitened (DFW) federated representation update across agents, replacing least squares for the shared basis, and characterizes regret in benign vs. difficult exploration regimes.
Key results
- In the easily identifiable setting, regret is O(sqrt(T)/sqrt(H)), decreasing as the number of tasks H grows (compared H=25 and H=100 against fully-unknown single-task baseline).
- In the difficult-exploration setting, regret scales as sqrt(du*dtheta)*sqrt(T) + T^{3/4}/H^{1/5}, improving on single-task sqrt(dx*du^2*T) when dtheta < dx*du and T is moderate or H large.
- Numerical cartpole experiments with H systems show the multi-task algorithm beats the fully-unknown single-system baseline in regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| share a learned representation across agents rather than learning each system independently | Adaptive LQR · Easily identifiable multi-task setting | regret: \tilde \calO\paren{ \sqrt{\frac{T}{H}}} vs. \calO(\sqrt{\dx\du^2 T}) | Helped |
| share a learned representation across agents rather than learning each system independently | Adaptive LQR · Not easily identifiable multi-task setting | regret: \tilde \calO \paren{\sqrt{\du \dtheta }\sqrt{T} + \frac{T^{3/4}}{H^{1/5 }}} vs. \calO(\sqrt{\dx\du^2 T}) | Mixed |
| increase the number of communicating tasks from $H = 25$ to $H = 100$ | Shared-Representation Certainty-Equivalent Control with Continual Exploration · Cartpole, easily identifiable, nominal task h = 1 | regret | Helped |
Limitations
- Difficult-exploration regret has a T^{3/4} term that dominates for large T; not known whether sqrt(T) achievable there.
- Algorithm is not anytime: parameters depend on the horizon T.
- Numerical validation is limited to simulated cartpole systems with a single nominal task evaluated.
Experimental setup
Datasets: simulated cartpole linearized dynamics
Benchmarks: simulated multi-cartpole LQR regret
Metrics: expected regret vs timesteps T regret scaling with number of tasks H
Baselines: fully-unknown single-agent certainty-equivalent control
Builds on: DFW (de-bias and feature whiten) certainty-equivalent adaptive LQR least squares system identification minimax single-task LQR regret
Closest papers by meaning
- Improved Regret Bounds for Thompson Sampling in Linear Quadratic Control Problems (ICML 2018 · similarity 0.87)
- Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs (NeurIPS 2024 · similarity 0.87)
- Regret Bounds for Episodic Risk-Sensitive Linear Quadratic Regulator (ICLR 2025 · similarity 0.86)
- No Regrets: Investigating and Improving Regret Approximations for Curriculum Discovery (NeurIPS 2024 · similarity 0.86)
- Risk-Conditioned Reinforcement Learning: A Generalized Approach for Adapting to Varying Risk Measures (AAAI 2024 · similarity 0.85)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.85)
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.