Accelerating Multi-Task Temporal Difference Learning under Low-Rank Representation
Yitao Bai, Sihan Zeng, Justin Romberg, Thinh T. Doan · 2025
Read Accelerating Multi-Task Temporal Difference Learning under Low-Rank Representation by Yitao Bai, Sihan Zeng, Justin Romberg, Thinh T. Doan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-02030.txt.
Introduction
Yitao Bai, Sihan Zeng, Justin Romberg, and Thinh Doan speed up how reinforcement learners grade many policies at once. When several tasks share a low-dimensional value structure, judging each alone wastes the overlap. Their variant of temporal difference learning inserts a truncated singular value step into every update.
The extra step steers updates along the dominant shared directions, exploiting the low-rank shape. Experiments show clear wins over classic temporal difference learning, growing as the rank shrinks. Theory calms the obvious worry: the truncation does not destabilize the iteration. The method converges at the standard rate, matching the classic guarantee with a leaner use of data.
Catalog record
| CREATOR | Yitao Bai, Sihan Zeng, Justin Romberg, Thinh T. Doan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-02030
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Accelerating Multi-Task Temporal Difference Learning under Low-Rank Representation Yitao Bai, Sihan Zeng, Justin Romberg, Thinh T. Doan Abstract We study policy evaluation problems in multi-task reinforcement learning (RL) under a low-rank representation setting. In this setting, we are given N N learning tasks where the corresponding value function of these tasks lie in an r r -dimensional subspace, with r < N r<N . One can apply the classic temporal-difference (TD) learning method for solving these problems where this method learns the value function of each task independently. In this paper, we are interested in understanding whether one can exploit the low-rank structure of the multi-task setting to accelerate the performance of TD learning. To answer this question, we propose a new variant of TD learning method, where we integrate the so-called truncated singular value decomposition step into the update of TD learning. This additional step will enable TD learning to exploit the dominant directions due to the low rank structure to update the iterates, therefore, improving its performance. Our empirical results show that the proposed method significantly outperforms the classic TD learning, where the performance gap increases as the rank r r decreases. From the theoretical point of view, introducing the truncated singular value decomposition step into TD learning might cause an instability on the updates. We provide a theoretical result showing that the instability does not happen. Specifically, we prove that the proposed method converges at a rate 𝒪 ( ln ( t ) t ) \mathcal{O}(\frac{\ln(t)}{t}) , where t t is the number of iterations. This rate matches that of the standard TD learning. Keywords: Representation learning, multi-task reinforcement learning, temporal-difference learning. 1 Introduction Reinforcement learning (RL) has witnessed significant advancements in recent years, particularly in solving complex decision-making problems across various domains such as robotics ( Kober et al., 2013 ) , game playing ( Silver et al., 2017 ) , autonomous driving ( Kiran et al., 2021 ) , and Olympiad-level mathematical reasoning ( Zhang et al., 2024 ) . However, a major challenge in RL is the substantial amount of data required to train agents effectively. Even when tasks are very similar, standard RL algorithms often need to learn each task independently from scratch, leading to redundant learning efforts. Identifying and exploiting common structures among tasks can significantly reduce the data needed for training, thereby enhancing the learning efficiency. This paper studies a multi-task RL problem under the low-rank representation. In particular, we consider multi-task policy evaluation, presented in detail in Section 2 , where the objective is to evaluate the value functions of a common policy in a range of environments. We are interested in the setting where the value functions lie in a subspace whose dimension is much smaller than the number of tasks. One can apply the standard temporal difference (TD) learning, originally proposed in Sutton (1988) , to evaluate the value function for each task independently. Our main focus is to investigate whether we can improve the sample complexity by solving all tasks simultaneously. We answer this question positively by developing a new variant of TD learning that accounts for the low-rank structure in the learning process. We summarize our main contributions below. • Algorithm Development : We propose a new variant of TD learning, where we integrate the singular value decomposition (SVD) step into the updates of TD learning. The additional SVD step exploits the low-rank structure and enables TD learning to choose only dominant directions in its updates. We term this approach a truncated SVD-TD learning method, which performs significantly better than the classic TD method in low-rank problems. Our method does not assume that the subspace shared among the tasks are known. Instead, it iteratively refines the estimate of the subspace as learning proceeds. • Finite-Time Complexity of SVD-TD Learning : From the theoretical point of view, introducing the truncated singular value decomposition step into TD learning might cause an instability on the updates. To rigorously understand the algorithm behavior, we provide a mathematical analysis on the finite-time complexity of the proposed method. Specifically, we show that the proposed method finds the true value functions and subspace at the rate \mathcal{O}\left(\frac{\ln t}{t}\right) , which matches the complexity of the standard TD learning applied independently to each task. Interestingly, our convergence guarantees hold regardless the subspace initialization. The key idea of our analysis is to carefully characterize the stochastic approximation nature of the algorithm and the impact of truncating the value function estimates. • Numerical Validations : We provide a number of numerical simulations to show the superior performance of the proposed truncated SVD-TD learning when compared to the classic one in solving the multi-task policy evaluation problems. In addition, our simulations indicate that the performance gap between these two methods increases as the rank r of the subspace decreases, highlighting the effectiveness of exploiting the low-rank structures of the truncated SVD-TD learning method. 1.1 Related Work Multi-Task Reinforcement Learning aims to improve learning efficiency by leveraging shared structures across multiple related tasks ( Caruana, 1997 ) . Our work aligns with this domain by addressing the challenge of efficiently learning value functions across multiple tasks that share underlying dynamics. Existing approaches in multitask learning can be broadly categorized into reinforcement learning methods and other machine learning techniques. For example, Rusu et al. (2015) propose policy distillation, which transfers knowledge across tasks through a pre-trained model, while Taylor and Stone (2009) focus on transfer learning techniques that rely on prior assumptions about task relationships. Our work is also related to the literature of representation learning in single-task RL; see Du et al. (2019) ; Agarwal et al. (2020) ; Modi et al. (2024) ; Misra et al. (2020) ; Mhammedi et al. (2024) ; Bennett et al. (2023) ; Uehara et al. (2021) ; Zhang et al. (2022b) ; Zhang et al. (2022a) and the references therein. Existing methods, while only applied to the mini-batch settings, are developed under a common assumption on the low-rank condition of the underlying transition kernel, referred to as low-rank MDPs. In contrast to these existing methods, our approach dynamically uncovers shared structures through the integration of TD learning and truncated SVD, and applies to a more general representation learning framework, which includes low-rank MDPs as a special case. Multi-Task Learning. On the other hand, some methods are not strictly within the RL domain but are relevant to multi-task learning in general. For instance, least-square-based algorithms such as those discussed in Lu et al. (2021) are more aligned with supervised learning and optimization frameworks rather than reinforcement learning. These methods typically focus on optimizing shared representations across tasks using least-squares formulations, which may not directly apply to the sequential decision-making problems in RL. Similarly, meta-learning approaches like model-agnostic meta-learning (MAML) ( Collins et al., 2022 ) are designed to improve learning efficiency across tasks by optimizing model initialization for rapid adaptation. While these methods are powerful for multi-task learning, they are not specifically tailored for RL. Low-Rank Approximation in Reinforcement Learning. Exploiting low-rank structures in value functions has been explored to reduce computational complexity and improve generalization. Bellemare et al. (2012) investigates low-rank approximations for value iteration in large-scale MDPs using