The Limits of Transfer Reinforcement Learning with Latent Low-rank Structure

We thank reviewer LmTe for the suggestions on how to improve the presentation of our paper and have made the modifications for the final version. We have corrected the typos addressed by points 1a, 1c, 1g, 1j, 3, 4, 5, 6, 7, 8, 9, 13, 15, 16, 17, and 20. Regarding Theorem 1, the key idea is that we can construct two transfer RL problems with similar source $Q^*$s but use orthogonal feature representations in the target phase. As the learner is given one of the transfer RL problems with equal probability, they must identify which one it is to avoid using an orthogonal feature mapping with high probability. To identify the transfer RL problem, one must distinguish between the $Q^*$ from the different source MDPs, which depends on $\alpha$, the parameter to the result. From standard hypothesis testing sample complexity lower bounds (we need the noise variable to be Bernoulli to use this result), one must incur a sample complexity of $o(\alpha^2)$ to identify the correct transfer RL problem and feature mapping.

1b: Thank you for pointing this out. We will clarify that $\alpha$ is lower bounded by 1/(dM) (see Lemma 2). With a loose upper bound, it follows that $c \in (1, 2dM)$. As $d, M > 1$, we have that $2\alpha dM > \alpha$ and still require that one must observe $o(\alpha^2)$ samples to benefit from transfer learning.

1e: The Bernoulli variable specifies the noise model in our setting; one observes a realization of a Bernoulli random variable when specifying a $Q^*$ and state-action pair to observe from. We chose Bernoulli random variable as our noise model to use the result from [5].

1f: Thank you for pointing this out. The relevant result is Lemma 5.1 from [5] by setting $\delta = 0.24$, and we have added this to our paper.

1i: Yes, these matrices are block matrices. Thank you for your suggestions. We will emphasize this. Also, as the matrices are rank 1, the columns are orthogonal to each other. Furthermore, the norm of each block vector is 1 when accounting for the size of the blocks.

10: First, note that from Assumption 3, $\|Q^\*\|\_{\infty} \geq C$, so $\frac{1}{\sigma\_d} \leq \frac{\|Q^\*\|\_\infty }{ C\sigma\_d}$. From the last equation on page 48 from [28], we have that $\frac{\|Q^\*\|\_\infty}{C\sigma\_d} \leq \frac{\kappa d \mu}{\sqrt{S A} C}$. Thus, we have $\bar{\gamma} \leq \frac{ \kappa d \mu }{ (\sqrt{S A} C)} \sqrt{S A} \|D\|\_\infty$. From the source sample complexity, it follows that $\|D\|\_\infty \leq \frac{C}{2d\mu}$, which proves that $\bar{\gamma} \leq \frac{1}{2}$. Thank you for pointing this out, we will add more intermediate steps and clarification in the text. We have updated Corollary 3 as it was missing a factor of $\mu$.

11: Thank you for catching these errors. We have redefined our definition of misspecified low Tucker rank MDPs to $| \sum\_{s’ \in \mathcal{S}} P(s’|s, a) - G(a)U(s’, s) | \leq \xi$ instead of using the total variation distance as our analysis holds with the above definition.

14: We first show that $\bar{\gamma} = \frac{\|D\|\_{op}}{\sigma\_r} = \frac{\kappa d \mu \|D\|\_\infty}{C}$. Combining this with the definition of incoherence and Proposition 2, we get the result of Corollary 3.

18: recall that since the feature mapping was scaled up ($G_h = \sqrt{\frac{A }{d\mu}} G'$) to ensure the max entries of $G$ and $W, U$ are on the same scale, it follows that $|W\_{h}(s)|\_2 \leq 1$ and $\|\sum\_{s' \in \mathcal{S}} V\_{h+1}^\pi(s') U\_{h}(s', s) \|\_2 \leq H$. Therefore, it follows that $\|w\_h^s\|\_2 \leq 2H\sqrt{d}$.

19: The rightmost term is upper bounded by $\sqrt{d}$ from Lemma D.1 in [15]. As $|T_{k-1, h}^s| \leq k$, it follows that $\sqrt{ \sum_{t \in T_{k-1, h}^s} g^\top (\Lambda\_h^s)^{-1} g} \leq \sqrt{k g^\top (\Lambda\_h^s)^{-1} g}$. Since $\Lambda\_h^s$is real and symmetric with smallest eigenvalue lower bounded by $\lambda$, it follows that the largest eigenvalue of $(\Lambda\_h^s)^{-1}$ is upper bounded by $\lambda$. It follows that $g^\top (\Lambda\_h^s)^{-1} g \leq \|g\|_2^2/\lambda$ from the fact that the maximum value a Rayleigh quotient $(g^\top (\Lambda\_h^s)^{-1} g/ g^\top g)$is the largest eigenvalue of $(\Lambda\_h^s)^{-1}$(see Theorem 4.2.2 from Matrix Analysis by Horn et al).

We appreciate reviewer nw9e’s feedback and suggestions on how to improve our paper. We completely agree that our paper would benefit from numerical experiments and will look into running simulations to illustrate the benefits of our algorithm.

Q2&4: Regarding estimating $\alpha$, $\alpha$ is a fundamental quantity in each transfer RL problem. The significance of $\alpha$ is that for large $\alpha$, transfer learning approaches will perform worse than tabular MDP algorithms which ignore the source MDPs. While our source sample complexity and target regret bound depend on $\alpha$, we emphasize that one does not need to know $\alpha$ to run our algorithm. When running our algorithm in practice, one should observe as many samples in the source phase as allowed by their computational budget/constraint to obtain the best performance on the target problem.

Q5: Our approach will work for a multi-task learning setting with multiple target MDPs, as long as each of the target MDPs satisfy our transfer learning assumption (Assumption 2), i.e., each target task’s feature representation lies in the space spanned by the source MDP feature representations. Our algorithm would proceed in the same way to estimate the subspaces in the source phase, and then would run LSVI-UCB-(S, S, d) on each target MDP subsequently, assuming that all MDPs have transition kernels with Tucker rank $(S, S, d)$. The same approach works in the other Tucker rank settings. Our approach differs from policy distillation algorithms as we only require the feature representation from the target MDP to be contained in the space spanned by the source MDP feature representation. While one typically transfers a policy or $Q$ function from a teacher (source MDP) to a student (target MDP) in policy distillation, in our setting, the optimal $Q$ function and policy in the source MDPs can be very different from the optimal $Q$ function and policy from the target MDP. Therefore, with our assumptions, transferring only a policy or $Q$ function can lead to no improvement on the student or target MDP. Our setting is similar to the meta RL setting as the agent attempts to learn information from the source MDPs or meta tasks to improve the efficiency of learning in the target MDP. By learning a sufficient feature representation from the source MDPs (meta tasks), one can learn a good policy with significantly fewer samples, which is the goal in meta RL.

I really appreciate your detailed response to my questions. After reading the authors' responses and comments from other reviewers, I will keep my score.

We appreciate reviewer Stu9’s feedback and suggestions on how to improve our paper. We completely agree that our paper would benefit from adding a column listing the target regret bounds in Table 1 and will add it to the final version.

Weakness 2: We realize that our terminology is misleading in Assumption 3. Our “full-rank” $Q^*$ assumption asserts that $rank(Q^*) = d$, not that $rank(Q^*) = \min(S, A)$. We have fixed this for the final version and have removed the mention of “full-rank”.

Q1: The algorithm from [4] does not work in the $(S, S, d)$ and $(S, d, A)$ Tucker rank settings due to the difference in structural assumptions on the transition kernel. Specifically, [4] assumes low rank structure across the transition forward in time (between $s’$ and $(s, a)$) whereas in our work, we assume that there is low rank structure between $(s, s’)$ and $a$ or $(a, s’)$ and $s$. As a result, our algorithm learns feature mappings and weight vectors with different dimensions than in [4]. In the $(d, d, d)$ Tucker rank setting, one could use the algorithm in [4], which admits a target regret bound that matches ours with respect to $d, T, S, A$. However, our source sample complexities differ as the one using algorithm [4] depends on the size of the function class that the feature representations belong to instead of $\mathcal{S}$ or $\mathcal{A}$, and our algorithm does not require a computationally inefficient oracle in the source phase.

Q3: We apologize for the typo/mistake as they mean the same thing. The main difference in our models is that in [4] each MDP, source and target, share the same d-dimensional feature mapping while ours only assumes that the space spanned by the target feature mapping lies in the space spanned by the source feature mappings. This means that our results actually allow the target MDP to have up to $dM$-feature mapping if each of the $M$ source MDP subspaces are disjoint.

Q4: In our lower bound, the learner is given one of two transfer RL problems, 1 and 2, with equal probability where the one latent feature is optimal in problem 1 and the other is optimal in problem 2. The two latent factors are orthogonal to each other, so choosing the wrong latent feature is no better than randomly guessing a latent feature. Thus, to benefit from transfer learning with high probability, one must identify which transfer RL problem they are dealing with. To do so, one must determine if the $Q$ function from the second source MDP is $Q_{2, 1}^{ \*, 1}$ or $Q^{\*, 2}_{2, 1}$.

1: Yes, the thresholding procedure also works for the intermediate case. This procedure computes the union of the dimensions from all the source MDP subspaces. It then discards the repeated dimensions from each source MDP (as well as superfluous dimensions due to estimation error in the source MDPs). Thus, if the feature mapping lies in a $n$-dimensional subspace where $d < n < dM$, then the union of the subspaces of all the source MDPs is also $n$-dimensional, in which case the thresholding procedure will output $\tilde{G}_h$ with dimension $n$ (with high probability with respects to the estimation errors).

2: We thank reviewer Stu9 for the suggestion and will include a notation table in the appendix in the final version.