Regret Analysis of Multi-task Representation Learning for Linear-Quadratic Adaptive Control

• URL: http://arxiv.org/abs/2407.05781v2
• Date: Sat, 27 Jul 2024 13:20:35 GMT
• Title: Regret Analysis of Multi-task Representation Learning for Linear-Quadratic Adaptive Control
• Authors: Bruce D. Lee, Leonardo F. Toso, Thomas T. Zhang, James Anderson, Nikolai Matni,
• Abstract summary: We analyze the regret of multi-task representation learning for linear-quadratic control. We demonstrate that for settings where exploration is "benign", the regret of any agent after $T$ timesteps scales as $tilde O(sqrtT/H)$. In settings with "difficult" exploration, the regret scales as $tilde O(sqrtd_u d_theta sqrtT + T3/4/H1/5)$, where $d_the
• Score: 3.7603027627883363
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Representation learning is a powerful tool that enables learning over large multitudes of agents or domains by enforcing that all agents operate on a shared set of learned features. However, many robotics or controls applications that would benefit from collaboration operate in settings with changing environments and goals, whereas most guarantees for representation learning are stated for static settings. Toward rigorously establishing the benefit of representation learning in dynamic settings, we analyze the regret of multi-task representation learning for linear-quadratic control. This setting introduces unique challenges. Firstly, we must account for and balance the $\textit{misspecification}$ introduced by an approximate representation. Secondly, we cannot rely on the parameter update schemes of single-task online LQR, for which least-squares often suffices, and must devise a novel scheme to ensure sufficient improvement. We demonstrate that for settings where exploration is "benign", the regret of any agent after $T$ timesteps scales as $\tilde O(\sqrt{T/H})$, where $H$ is the number of agents. In settings with "difficult" exploration, the regret scales as $\tilde O(\sqrt{d_u d_\theta} \sqrt{T} + T^{3/4}/H^{1/5})$, where $d_x$ is the state-space dimension, $d_u$ is the input dimension, and $d_\theta$ is the task-specific parameter count. In both cases, by comparing to the minimax single-task regret $O(\sqrt{d_x d_u^2}\sqrt{T})$, we see a benefit of a large number of agents. Notably, in the difficult exploration case, by sharing a representation across tasks, the effective task-specific parameter count can often be small $d_\theta < d_x d_u$. Lastly, we provide numerical validation of the trends we predict.

Related papers

• Scaling Distributed Multi-task Reinforcement Learning with Experience Sharing [38.883540444516605]
  DARPA launched the ShELL program, which aims to explore how experience sharing can benefit distributed lifelong learning agents. We conduct both theoretical and empirical research on distributed multi-task reinforcement learning (RL), where a group of $N$ agents collaboratively solves $M$ tasks. We propose an algorithm called DistMT-LSVI, where each agent independently learns $epsilon$-optimal policies for all $M$ tasks.
  arXiv  Detail & Related papers  (2023-07-11T22:58:53Z)
• Simplifying and Understanding State Space Models with Diagonal Linear RNNs [56.33053691749856]
  This work disposes of the discretization step, and proposes a model based on vanilla Diagonal Linear RNNs. We empirically show that, despite being conceptually much simpler, $mathrmDLR$ is as performant as previously-proposed SSMs. We also characterize the expressivity of SSMs and attention-based models via a suite of $13$ synthetic sequence-to-sequence tasks.
  arXiv  Detail & Related papers  (2022-12-01T18:53:06Z)
• Multi-Task Imitation Learning for Linear Dynamical Systems [50.124394757116605]
  We study representation learning for efficient imitation learning over linear systems. We find that the imitation gap over trajectories generated by the learned target policy is bounded by $tildeOleft( frack n_xHN_mathrmshared + frack n_uN_mathrmtargetright)$.
  arXiv  Detail & Related papers  (2022-12-01T00:14:35Z)
• On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
  We investigate the sample complexity of learning the optimal arm for multi-task bandit problems. Arms consist of two components: one that is shared across tasks (that we call representation) and one that is task-specific (that we call predictor) We devise an algorithm OSRL-SC whose sample complexity approaches the lower bound, and scales at most as $H(Glog(delta_G)+ Xlog(delta_H))$, with $X,G,H$ being, respectively, the number of tasks, representations and predictors.
  arXiv  Detail & Related papers  (2022-11-28T08:40:12Z)
• Joint Representation Training in Sequential Tasks with Shared Structure [40.1056491921582]
  We introduce the Shared-MatrixRL algorithm for the setting of Multitask MatrixRL. We show the regret on the the $P$ tasks can be improved from $O(PHdsqrtNH)$ to $O((HdsqrtrP + HPsqrtrd)sqrtNH)$ over $N$ episodes of horizon $H$.
  arXiv  Detail & Related papers  (2022-06-24T18:10:00Z)
• Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
  We consider the setting where we play $M$ linear bandits with dimension $d$, each for $T$ rounds, and these $M$ bandit tasks share a common $k(ll d)$ dimensional linear representation. We come up with novel algorithms that achieve $widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret bounds, which matches the known minimax regret lower bound up to logarithmic factors.
  arXiv  Detail & Related papers  (2022-03-29T15:27:13Z)
• On the Power of Multitask Representation Learning in Linear MDP [61.58929164172968]
  This paper presents analyses for the statistical benefit of multitask representation learning in linear Markov Decision Process (MDP) We first discover a emphLeast-Activated-Feature-Abundance (LAFA) criterion, denoted as $kappa$, with which we prove that a straightforward least-square algorithm learns a policy which is $tildeO(H2sqrtfrackappa mathcalC(Phi)2 kappa dNT+frackappa dn)
  arXiv  Detail & Related papers  (2021-06-15T11:21:06Z)
• Multitask Online Mirror Descent [35.93027027759005]
  We analyze MT-OMD, a multitask generalization of Online Mirror Descent (OMD) which operates by sharing updates between tasks. Our extensions of Online Gradient Descent and Exponentiated Gradient, two important instances of OMD, are shown to enjoy closed-form updates.
  arXiv  Detail & Related papers  (2021-06-04T10:14:57Z)
• Near-optimal Representation Learning for Linear Bandits and Linear RL [41.33483293243257]
  We first consider the setting where we play $M$ linear bandits with dimension $d$ concurrently. These bandits share a common $k$-dimensional linear representation so that $kll d$ and $k ll M$. We propose a sample-efficient algorithm, MTLR-OFUL, which leverages the shared representation to achieve $tildeO(MsqrtdkT + dsqrtkMT )$ regret.
  arXiv  Detail & Related papers  (2021-02-08T11:11:53Z)
• On the Theory of Transfer Learning: The Importance of Task Diversity [114.656572506859]
  We consider $t+1$ tasks parameterized by functions of the form $f_j circ h$ in a general function class $mathcalF circ mathcalH$. We show that for diverse training tasks the sample complexity needed to learn the shared representation across the first $t$ training tasks scales as $C(mathcalH) + t C(mathcalF)$.
  arXiv  Detail & Related papers  (2020-06-20T20:33:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.