Sample Efficient Myopic Exploration Through Multitask Reinforcement Learning with Diverse Tasks

We thank the reviewer for their valuable suggestions from a deep RL perspective. Here are our detailed point-by-point responses.

Responses to the General Comment in Weakness:

We value the reviewer’s contextualization within the realm of deep RL. Indeed, multi-goal RL serves a motivating example of our proposed theoretical framework. HER, as proven to improve sample complexity, implicitly tackles a multitask RL problem, as articulated in Section 3. Specifically, Algorithm 1 encapsulates a form of HER within a multi-goal RL setting.

Connection to HER and multi-goal RL: In a multi-goal RL setting, all tasks share identical state space, action space, and transition function, with the only difference residing in the reward function. Algorithm 1 exemplifies this by sampling a trajectory on task $M$ through a mixture of all greedy policies from other tasks. Notably, this exploration strategy is akin to randomly selecting task $M'$ and collecting a trajectory on $M'$ using its own epsilon-greedy policy, followed by relabeling rewards to simulate a trajectory on $M$.

Connection to curriculum learning: Although Algorithm 1 does not explicitly implement curriculum learning by assigning preferences to tasks, an improvement could be made through adaptive task selection. If an algorithm with adaptive task selection achieves a sample complexity $\mathcal{C}$, Algorithm 1 should have a sample complexity of at most $\mathcal{C} |\mathcal{M}|^2$. Intuitively, if a curriculum selects tasks through an order of $M_1, \dots, M_T$, then at the each round, the algorithm uses the epsilon-greedy policy of MDP $M_{t-1}$ to explore $M_t$. This exploration is implicitly included in Algorithm 1 because Algorithm 1 explores all the MDPs in each round with the mixture of all epsilon-greedy policies.

This means that the sample-complexity of Algorithm 1 provides an upper bound on the sample complexity of underlying optimal task selection and in this way our theory provides some insights on the success of the curriculum learning. Designing a theoretically grounded algorithm for near-optimal adaptive task selection is a non-trivial improvement, and we defer this discussion to future work.

Responses to Questions:

Question 1: While I generally follow the argument, this paper has some rough grammar and odd word choices in places. I'd recommend a thorough editing pass to improve the language.

Response: We appreciate the observation regarding language issues and commit to a comprehensive editing pass to enhance the final version's clarity and coherence.

Question 2: The explanation of the multitask setup in Section 2.1 confused me as to how the tasks are getting selected. Is there a structure or order in which tasks are chosen among M?

Response: In the general multitask RL setup in Section 2.1, no assumptions are made regarding how tasks are selected. Algorithms have the flexibility to choose any task for trajectory collection in each round. To simplify the task selection in Algorithm 1, we explore all tasks simultaneously (line 3), avoiding the need for an adaptive task selection.

Question 3: Likewise, Definition 1 is a little confusing. C is a function of beta and delta? I'm confused as to why sample complexity doesn't depend on either the algorithm itself or the task(s) being learned.

Response: We appreciate the clarification question. The sample complexity $C$ is indeed a function of $\beta$, $\delta$, the algorithm, and the environment $\mathcal{M}$. While we did not explicitly state the dependence on the algorithm and environment to maintain simplicity, we acknowledge the importance of this clarification.

Question 4: How does algorithm 1 differ from the cited Zhumabekov 2023 policy ensemble method?

Response: While both Algorithm 1 and Zhumabekov 2023 share a similar high-level idea of ensembling policies, their implementation differs. In Algorithm 1, policies are mixed trajectory-wise, with one policy randomly selected for the entire episode. In contrast, Zhumabekov 2023 mixes policies on a step-wise basis for a continuous action space, selecting actions as a weighted average of actions chosen by different policies. We conjecture that this distinction impacts the worst-case sample complexity, with Algorithm 1 enjoying the guarantees outlined.

Question 5: How does this idea of multitask myopic exploration differ from normal goal-directed RL methods like hindsight experience replay?

Response: As elucidated in the Weakness section, Algorithm 1 implicitly incorporates HER in a multi-goal setting. It converges with methods like HER, sharing a common approach to myopic exploration.

Thanks for your comments and clarifications! Since most of my issues were with the presentation or drawing connections to related algorithms (which it sounds like you were aware of already, pleasantly), I think a revised manuscript with additions/changes along the lines you proposed would raise my score, if one can be assembled in time (and if not I encourage you to revise and resubmit the paper to another conference).

Re: question 7, I was thinking of how in standard (e.g. off-policy DQN style) epsilon-greedy a random action is chosen with probability epsilon at every timestep, which in this case results in a 1/epsilon fraction of actions PPO is trained on being off-policy actions (since they were chosen at random). In theory as well as my experience (inadvertently implementing epsilon-greedy exploration in the context of PPO-like algorithms), this causes unstable gradients and policy distribution/performance collapse, particularly late in training when the policy is relatively converged and randomly-selected actions often have an extremely small probability under the policy. Was this an issue for your PPO experiments, or am I misunderstanding what is meant by epsilon-greedy exploration in that experiment?

We thank the reviewer for their thoughtful examination of our paper. We acknowledge the need for more comprehensive discussions regarding the concept of diversity in deep RL.

Towards this direction, our simulation study provides a potential connection between diversity in the linear MDP case and the diversity in deep RL. In short, in linear MDP cases, we require that the optimal policies for different tasks induce a full-rank feature covariance matrix at the each step $h$. Our simulation study finds a benefit of having a more spread spectrum of feature covariance matrix in bipedal walker environment (medium range of stump heights) illuminating a potential way of investigating the diversity of tasks in deep RL.

To attain diversity in deep RL, one may apply the automatic curriculum learning (ACL) algorithm, which has been shown to coincidence with our notion of diversity in bipedal walker environment. It appears that ACL may implicitly optimize the diversity notion proposed in our paper. As part of our future work, we plan to formalize this observed similarity between ACL task selection and diversity from a theoretical perspective. Moreover, our work can be viewed as providing an explanation for the success of ACL in multitask RL tasks.

We thank the reviewer for the careful reading and insightful comments.

Response to weakness: The feature coverage assumption is an additional condition included for clarity in presentation. We acknowledge it is non-essential and discuss a relaxation of this assumption for the Tabular case. In this scenario, we construct a mirror MDP (refer to Appendix F.2), introducing an extra dependence of $\sqrt{SH}$.

Question 1: Is it possible to relax Definition 7?

Response: We concede that Definition 7 is indeed restrictive. We might conjecture that we only need the $\theta$'s for the reward parameter is rank $d$. This is in fact not sufficient. We provide an example in Appendix D Figure 3. To have a lower bounded Multitask MEG, we require, at each $h$, the optimal policies of different tasks induce a full-rank covariance matrix of the feature vectors (refer to Lemma 8).

More generally, a thorough discussion of diversity for general function classes is available in Appendix G. The overarching concept involves constructing a set of tasks whose optimal policies induce occupancy measures that are $\epsilon$-dependent. The size of the largest set is quantified by the BE dimension. However, the technical challenge lies in the fact that current algorithms only guarantee finding a $\beta$-optimal solution, which doesn't necessarily ensure convergence to the induced occupancy measure of the true optimal policy. There can be many interesting future works towards this direction.

Question 2: The offline learning oracle solves simultaneously. Can you do them sequentially and have similar guarantees?

Response: By "solving them sequentially," if you mean updating the value function for one task at each round, this approach is indeed feasible. We can achieve this by selecting a task in each round and collecting an episode for that task using the mixture policy (where the greedy policy from other tasks is based on the most recent update). If tasks are chosen in a fixed order ($1, \dots, |\mathcal{M}|$), we obtain guarantees similar to those outlined in Algorithm 1. There is potential for an adaptive task selection approach, akin to curriculum learning, which we leave for further exploration in future work

We thank the reviewer for the comments. Below, we provide detailed responses to each point raised.

Weakness 1: it is hard to validate such explanation.

Response: We acknowledge the challenge of validating the theoretical explanation in real-world empirical studies. However, we present two key points supporting the validity of our explanation. Firstly, the HER (Hindsight Experience Replay) algorithm, a successful practical implementation, shares similarities with Algorithm 1. HER enhances exploration by relabeling sampled trajectories from other tasks, suggesting that multitask RL indeed improves the sample efficiency of myopic exploration. Secondly, drawing on the concept of diverse tasks in Linear MDP cases, we establish a connection to the Bipedal Walker environment, demonstrating that a diversity notion favoring a full rank structure of the covariance matrix of the embeddings is pivotal (as discussed in Section 6). Based on these observations, we firmly believe that our paper offers a valid perspective on explaining the success of myopic exploration.

Weakness 2: The intuition of the proof is that, if we have a base policy class with good coverage, we are able to find the optimal policy by combining the base policies with naive exploration. However, it has been well known that exploration is simple when we have good coverage. Therefore, their contribution seems not novel enough.

Response: We appreciate the reviewer's comment and we would like to have some extra clarification on the coverage of a policy class. Typically, coverage assumptions are articulated for the behavior policy of an offline dataset, often with an all-policy or single-policy concentrability assumption (refer to [1]). While constructing a diverse task set for a discrete policy class with each policy representing the optimal policy of a task is straightforward, the challenge arises when the policy set is infinite. Constructing an epsilon-covering of the policy set may lead to an exponentially large task set. However, we demonstrate that for tabular and linear cases, a diverse task set can be constructed with only polynomial (SAH) or polynomial (dH) tasks, a departure from existing literature results.

Question 1: What does Def 3 mean in linear MDP?

Response: For a detailed understanding of Def 3 in linear MDP, we refer the reviewer to Lemma 8 in Appendix E.1, which states that the coverage condition in Def 3 could be expressed as a full rank condition of the feature covariance matrix. Low MEG in Def 3 in linear MDP intuitively implies that we should construct the task set “diverse” enough such that for all $h \in [H]$, the feature covariance matrix $\mathbb{E}_{\pi} \phi_h(s_h, a_h) \phi_h(s_h, a_h)^\top$ obtained by running the current exploration policy (mixture of epsilon greedy policies) is full rank.

Question 2: Can you provide an example where Def 3 holds and the coverage of the base policies is poor?

Response: Could the reviewer elaborate on "base policies"? Def 3 is not a condition. However, if the concern is whether low MEG holds even when the current greedy policies are non-optimal, we direct the reviewer to Figure 1, where low MEG consistently holds despite the non-optimality of the current greedy policies.

We hope that these responses effectively address the reviewer's comments and concerns.