Successor Features for Transfer in Reinforcement Learning

Introduction

Reinforcement learning (RL) provides a framework for the development of situated agents that learn how to behave while interacting with the environment . The basic RL loop is defined in an abstract way so as to capture only the essential aspects of this interaction: an agent receives observations and selects actions to maximize a reward signal. This setup is generic enough to describe tasks of different levels of complexity that may unroll at distinct time scales. For example, in the task of driving a car, an action can be to turn the wheel, make a right turn, or drive to a given location.

Clearly, from the point of view of the designer, it is desirable to describe a task at the highest level of abstraction possible. However, by doing so one may overlook behavioral patterns and inadvertently make the task more difficult than it really is. The task of driving to a location clearly encompasses the subtask of making a right turn, which in turn encompasses the action of turning the wheel. In learning how to drive an agent should be able to identify and exploit such interdependencies. More generally, the agent should be able to break a task into smaller subtasks and use knowledge accumulated in any subset of those to speed up learning in related tasks. This process of leveraging knowledge acquired in one task to improve performance on other tasks is called transfer .

In this paper we look at one specific type of transfer, namely, when subtasks correspond to different reward functions defined in the same environment. This setup is flexible enough to allow transfer to happen at different levels. In particular, by appropriately defining the rewards one can induce different task decompositions. For instance, the type of hierarchical decomposition involved in the driving example above can be induced by changing the frequency at which rewards are delivered: a positive reinforcement can be given after each maneuver that is well executed or only at the final destination. Obviously, one can also decompose a task into subtasks that are independent of each other or whose dependency is strictly temporal (that is, when tasks must be executed in a certain order but no single task is clearly “contained” within another).

The types of task decomposition discussed above potentially allow the agent to tackle more complex problems than would be possible were the tasks modeled as a single monolithic challenge. However, in order to apply this divide-and-conquer strategy to its full extent the agent should have an explicit mechanism to promote transfer between tasks. Ideally, we want a transfer approach to have two important properties. First, the flow of information between tasks should not be dictated by a rigid diagram that reflects the relationship between the tasks themselves, such as hierarchical or temporal dependencies. On the contrary, information should be exchanged across tasks whenever useful. Second, rather than being posed as a separate problem, transfer should be integrated into the RL framework as much as possible, preferably in a way that is almost transparent to the agent.

In this paper we propose an approach for transfer that has the two properties above. Our method builds on two conceptual pillars that complement each other. The first is a generalization of Dayan’s successor representation. As the name suggests, in this representation scheme each state is described by a prediction about the future occurrence of all states under a fixed policy. We present a generalization of Dayan’s idea which extends the original scheme to continuous spaces and also facilitates the use of approximation. We call the resulting scheme successor features. As will be shown, successor features lead to a representation of the value function that naturally decouples the dynamics of the environment from the rewards, which makes them particularly suitable for transfer.

The second pillar of our framework is a generalization of Bellman’s classic policy improvement theorem that extends the original result from one to multiple decision policies. This novel result shows how knowledge about a set of tasks can be transferred to a new task in a way that is completely integrated within RL. It also provides performance guarantees on the new task before any learning has taken place, which opens up the possibility of constructing a library of “skills” that can be reused to solve previously unseen tasks. In addition, we present a theorem that formalizes the notion that an agent should be able to perform well on a task if it has seen a similar task before—something clearly desirable in the context of transfer. Combined, the two results above not only set our approach in firm ground but also outline the mechanics of how to actually implement transfer. We build on this knowledge to propose a concrete method and evaluate it in two environments, one encompassing a sequence of navigation tasks and the other involving the control of a simulated two-joint robotic arm.

Background and problem formulation

The objective of the agent in RL is to find a policy $\pi$—a mapping from states to actions—that maximizes the expected discounted sum of rewards, also called the return $G_{t}=\sum_{i=0}^{\infty}\gamma^{i}R_{t+i+1},$ where $R_{t}=R(S_{t},A_{t},S_{t+1})$. One way to address this problem is to use methods derived from dynamic programming (DP), which heavily rely on the concept of a value function . The action-value function of a policy $\pi$ is defined as

In this paper we are interested in the problem of transfer, which we define as follows. Let $\mathcal{T},\mathcal{T}^{\prime}$ be two sets of tasks such that $\mathcal{T}^{\prime}\subset\mathcal{T}$, and let $t$ be any task. Then there is transfer if, after training on $\mathcal{T}$, the agent always performs as well or better on task $t$ than if only trained on $\mathcal{T}^{\prime}$. Note that $\mathcal{T}^{\prime}$ can be the empty set. In this paper a task will be defined as a specific instantiation of the reward function $R(s,a,s^{\prime})$ for a given MDP. In Section 4 we will revisit this definition and make it more formal.

Successor features

In this section we present the concept that will serve as a cornerstone for the rest of the paper. We start by presenting a simple reward model and then show how it naturally leads to a generalization of Dayan’s successor representation (SR).

Suppose that the expected one-step reward associated with transition $(s,a,s^{\prime})$ can be computed as

SFs extend SR in two other ways. First, the concept readily applies to continuous state and action spaces without any modification. Second, by explicitly casting (2) and (3) as inner products involving feature vectors, SFs make it evident how to incorporate function approximation: as will be shown, these vectors can be learned from data.

Transfer via successor features

Now that our setup is clear we can start to describe our solution for the transfer problem discussed above. We do so in two stages. First, we present a generalization of DP’s notion of policy improvement whose interest may go beyond the current work. We then show how SFs can be used to implement this generalized form of policy improvement in an efficient and elegant way.

One of the fundamental results in RL is Bellman’s policy improvement theorem. In essence, the theorem states that acting greedily with respect to a policy’s value function gives rise to another policy whose performance is no worse than the former’s. This is the driving force behind DP, and most RL algorithms that compute a value function are exploiting Bellman’s result in one way or another.

In this section we extend the policy improvement theorem to the scenario where the new policy is to be computed based on the value functions of a set of policies. We show that this extension can be done in a natural way, by acting greedily with respect to the maximum over the value functions available. Our result is summarized in the theorem below.

for any $s\in\mathcal{S}$ and $a\in\mathcal{A}$, where $Q^{\pi}$ is the action-value function of ${\pi}$.

The proofs of our theoretical results are in the supplementary material. As one can see, our theorem covers the case where the policies’ value functions are not computed exactly, either because function approximation is used or because some exact algorithm has not be run to completion. This error is captured by $\epsilon$ in (6), which re-appears as a penalty term in the lower bound (8). Such a penalty is inherent to the presence of approximation in RL, and in fact it is identical to the penalty incurred in the single-policy case (see e.g. Bertsekas and Tsitsiklis’s Proposition 6.1 ).

If we consider the usual DP loop, in which policies of increasing performance are computed in sequence, our result is not of much use because the most recent policy will always dominate all others. Another way of putting it is to say that after Theorem 1 is applied once adding the resulting $\pi$ to the set $\{\pi_{1}$, $\pi_{2},...,\pi_{n}\}$ will reduce the next improvement step to standard policy improvement, and thus the policies $\pi_{1}$, $\pi_{2},...,\pi_{n}$ can be simply discarded. There are however two situations in which our result may be of interest. One is when we have many policies $\pi_{i}$ being evaluated in parallel. In this case GPI provides a principled strategy for combining these policies. The other situation in which our result may be useful is when the underlying MDP changes, as we discuss next.

2 Generalized policy improvement with successor features

Once the functions ${Q}^{{}_{\pi_{i}^{*}}}_{n+1}$ have been computed, we can apply GPI to derive a policy $\pi$ whose performance on $M_{n+1}$ is no worse than the performance of $\pi_{1}^{*},\pi^{*}_{2},...,\pi^{*}_{n}$ on the same task. A question that arises in this case is whether we can provide stronger guarantees on the performance of $\pi$ by exploiting the structure shared by the tasks in $\mathcal{M}^{\phi}$. The following theorem answers this question in the affirmative.

Note that we used $M_{i}$ rather than $M_{n+1}$ in the theorem’s statement to remove any suggestion of order among the tasks. Theorem 2 is a specialization of Theorem 1 for the case where the set of value functions used to compute $\pi$ are associated with tasks in the form of (5). As such, it provides stronger guarantees: instead of comparing the performance of $\pi$ with that of the previously-computed policies $\pi_{j}$, Theorem 2 quantifies the loss incurred by following $\pi$ as opposed to one of $M_{i}$’s optimal policies.

Experiments

In this section we present our main experimental results. Additional details, along with further results and analysis, can be found in Appendix B of the supplementary material.

The first environment we consider involves navigation tasks defined over a two-dimensional continuous space composed of four rooms (Figure 1). The agent starts in one of the rooms and must reach a goal region located in the farthest room. The environment has objects that can be picked up by the agent by passing over them. Each object belongs to one of three classes determining the associated reward. The objective of the agent is to pick up the “good” objects and navigate to the goal while avoiding “bad” objects. The rewards associated with object classes change at every $20\,000$ transitions, giving rise to very different tasks (Figure 1). The goal is to maximize the sum of rewards accumulated over a sequence of $250$ tasks, with each task’s rewards sampled uniformly from $^{3}$.

The second environment we consider is a set of control tasks defined in the MuJoCo physics engine . Each task consists in moving a two-joint torque-controlled simulated robotic arm to a specific target location; thus, we refer to this environment as “the reacher domain.” We defined $12$ tasks, but only allowed the agents to train in $4$ of them (Figure 3c). This means that the agent must be able to perform well on tasks that it has never experienced during training.

Results are shown in Figures 3a and 3b. Looking at the training curves, we see that whenever a task is selected for training SFDQN’s return on that task quickly improves and saturates at near-optimal performance. The interesting point to be noted is that, when learning a given task, SFDQN’s performance also improves in all other tasks, including the test ones, for which it does not have specialized policies. This illustrates how the combination of SFs and GPI can give rise to flexible agents able to perform well in any task of a set of tasks with shared dynamics—which in turn can be seen as both a form of temporal abstraction and a step towards more general hierarchical RL .

Related work

When we look at SFs strictly as a representation scheme, there are clear similarities with Littman et al.’s predictive state representation (PSR). Unlike SFs, though, PSR tries to summarize the dynamics of the entire environment rather than of a single policy $\pi$. A scheme that is perhaps closer to SFs is the value function representation sometimes adopted in inverse RL .

Conclusion

This paper builds on two concepts, both of which are generalizations of previous ideas. The first one is SFs, a generalization of Dayan’s SR that extends the original definition from discrete to continuous spaces and also facilitates the use of function approximation. The second concept is GPI, formalized in Theorem 1. As the name suggests, this result extends Bellman’s classic policy improvement theorem from a single to multiple policies.

Although SFs and GPI are of interest on their own, in this paper we focus on their combination to induce transfer. The resulting framework is an elegant extension of DP’s basic setting that provides a solid foundation for transfer in RL. As a complement to the proposed transfer approach, we derived a theoretical result, Theorem 2, that formalizes the intuition that an agent should perform well on a novel task if it has seen a similar task before. We also illustrated with a comprehensive set of experiments how the combination of SFs and GPI promotes transfer in practice.

We believe the proposed ideas lay out a general framework for transfer in RL. By specializing the basic components presented one can build on our results to derive agents able to perform well across a wide variety of tasks, and thus extend the range of environments that can be successfully tackled.

Acknowledgments

The authors would like to thank Joseph Modayil for the invaluable discussions during the development of the ideas described in this paper. We also thank Peter Dayan, Matt Botvinick, Marc Bellemare, and Guy Lever for the excellent comments, and Dan Horgan and Alexander Pritzel for their help with the experiments. Finally, we thank the anonymous reviewers for their comments and suggestions to improve the paper.

References

Appendix A Proofs of theoretical results

for any $s\in S$ and any $a\in A$, where $Q^{\pi}$ is the action-value function of ${\pi}$.

We start by noting that for any $s\in S$ and any $a\in A$ the following holds:

For all $s\in S$, $a\in A$, and $i\in\{1,2,...,n\}$ we have

Let $\delta_{ij}=\max_{s,a}\left|r_{i}(s,a)-r_{j}(s,a)\right|$. Then,

To simplify the notation, let $Q^{j}_{i}(s,a)\equiv Q_{i}^{\pi^{*}_{j}}(s,a)$. Then,

Our strategy will be to bound $|Q_{i}^{i}(s,a)-Q^{j}_{j}(s,a)|$ and $|Q_{j}^{j}(s,a)-Q^{j}_{i}(s,a)|$. Note that $|Q_{i}^{i}(s,a)-Q^{j}_{j}(s,a)|$ is the difference between the value functions of two MDPs with the same transition function but potentially different rewards. Let $\Delta_{ij}=\max_{s,a}|Q_{i}^{i}(s,a)-Q^{j}_{j}(s,a)|$. Then, We follow the steps of Strehl and Littman .

Since (A) is valid for any $s,a\in S\times A$, we have shown that $\Delta_{ij}\leq\delta_{ij}+\gamma\Delta_{ij}$. Solving for $\Delta_{ij}$ we get

We now turn our attention to $|Q_{j}^{j}(s,a)-Q^{j}_{i}(s,a)|$. Following the previous steps, define $\Delta^{\prime}_{ij}=\max_{s,a}|Q_{i}^{i}(s,a)-Q^{j}_{i}(s,a)|$. Then,

Solving for $\Delta^{\prime}_{ij}$, as above, we get

Plugging (13) and (14) back in (A) we get the desired result. ∎

The result is a direct application of Theorem 1 and Lemma 1. For any $j\in\{1,2,...,n\}$, we have

Appendix B Details of the experiments

In this section we provide additional information about our experiments. We start with the four-room environment and then we discuss the reacher domain. In both cases the structure of the discussion is the same: we start by giving a more in depth description of the environment itself, both at a conceptual level and at a practical level, then we provide a thorough description of the algorithms used, and, finally, we explain the protocol used to carry out the experiments.

In Section 5 of the paper we gave an intuitive description of the four-room domain used in our experiments. In this section we provide a more formal definition of the environment $\mathcal{M}$ as a family of Markov decision processes (MDPs) $M$, each one associated with a task.

The environment has objects that can be picked up by the agent by passing over them. There is a total of $n_{o}$ objects, each belonging to one of $n_{c}\leq n_{o}$ classes. The class of an object determines the reward $r_{c}$ associated with it. An episode ends when the agent reaches the goal, upon which all the objects re-appear. We assume that $r_{g}$ is always $1$ but $r_{c}$ may vary: a specific instantiation of the rewards $r_{c}$ defines a task. Every time a new task starts the rewards $r_{c}$ are sampled from a uniform distribution over $$. Figure 1 shows the specific environment layout used, in which$n_{o}=12$and$n_{c}=3$.

Having already described $\mathcal{S}$, $\mathcal{A}$, and $p(\cdot|s,a)$, we only need to define the reward function $R(s,a,s^{\prime})$ and the discount factor $\gamma$ in order to conclude the formulation of the MDP $M$. As discussed in Section 5, the reward $R(s,a,s^{\prime})$ is a deterministic function of $s^{\prime}$: if the agent is over an object of class $c$ in $s^{\prime}$ it gets a reward of $r_{c}$, and if it is in the goal region it gets a reward of $r_{g}=1$; in all other cases the reward is zero. In our experiments we fixed $\gamma=0.95$.

Since $r(s,a,s^{\prime})$ can be written in the form of (2), the definition of $M$ can be naturally extended to $\mathcal{M}$, as in (5). In our experiments we assume that the agents receive a signal from $\mathcal{M}$ whenever the task changes (see Algorithms 1, 2, and 3 and discussion below).

B.1.2 Algorithms

As one can see in this section, we tried to keep the methods as simple as possible in order to not obfuscate the main message of the paper, which is not to propose any particular algorithm but rather to present a general framework for transfer based on the combination of SFs and GPI.

B.1.3 Experimental setup

QL, PRQL, and SFQL depend on different sets of parameters, as shown in Algorithms 1, 2, and 3. In order to properly configure the algorithms we tried three different values for each parameter and checked the performance of the corresponding agents under each resulting configuration. Specifically, we tried the following sets of values for each parameter:

The cross-product of the values above resulted in $3$ configurations of QL, $27$ configurations of PRQL, and $9$ configurations of SFQL. The results reported correspond to the best performance of each algorithm, that is, for each algorithm we picked the configuration that lead to the highest average return over all tasks.

B.2 Reacher environment

The reacher environment is a two-joint torque-controlled robotic arm simulated using the MuJoCo physics engine . It is based on one of the domains used by Lillicrap et al. . This is a particularly appropriate domain to illustrate our ideas because it is straightforward to define multiple tasks (goal locations) sharing the same dynamics.

The reward received at each time step was $-\delta$, where $\delta$ is the Euclidean distance between the target position and the tip of the arm. The start state at each episode was defined as follows during training: the inner joint angle was sampled from an uniform distribution over $[0,2\pi]$, the outer joint was sampled from an uniform distribution over $\{-\pi/2,\pi/2\}$, and both angular velocities were set to (during the evaluation phase two fixed start states were used—see below). We used a time step of $0.02$s and episodes lasted for $10$s ($500$ time steps). We defined $12$ target locations, $4$ of which we used for training and $8$ were reserved for testing (see Figure 3).

B.2.2 Algorithms

B.2.3 Experimental setup

The agents were trained for $200\,000$ transitions on each of the $4$ training tasks. Data was collected using an $\epsilon$-greedy policy with $\epsilon=0.1$ (for SFDQN, this corresponds to lines 15 and 16 of Algorithm 3). As is common in fixed episode-length control tasks, we excluded the terminal transitions during training to make the value of states independent of time, which corresponds to learning continuing policies .

During the entire learning process we monitored the performance of the agents on all $12$ tasks when using an $\epsilon$-greedy policy with $\epsilon=0.03$. The results shown in Figure 3 reflect the performance of this policy. Specifically, the return shown in the figure is the sum of rewards received by the $0.03$-greedy policy over two episodes starting from fixed states. Since the maximum possible return varies across tasks, we normalized the returns per task based on the performance of standard DQN on separate experiments (this is true for both training and test tasks). Specifically, we carried out the normalization as follows. First, we ran DQN $30$ times on each task and recorded the algorithm’s performance before and after training. Let $\bar{G}_{b}$ and $\bar{G}_{a}$ be the average performance of DQN over the $30$ runs before and after training, respectively. Then, if during our actual experiments DQN or SFDQN got a return of $G$, the normalized version of this metric was obtained as $G_{n}=(G-\bar{G}_{b})/(\bar{G}_{a}-\bar{G}_{b})$. These are the values shown in Figure 3. Visual inspection of videos extracted from the experiments with DQN alone suggests that the returns used for normalization were obtained by near-optimal policies that reach the targets almost directly.

Appendix C Additional empirical analysis

In this section we report empirical results that had to be left out of the main paper due to the space limit. Specifically, the objective of the experiments described here is to provide a deeper understanding of SFQL, in particular, and of SFs, more generally. We use the four-room environment to carry out our empirical investigation.

In order to have a better understanding of the two types of transfer promoted by SFs, we carried out experiments in which we tried to isolate as much as possible each one of them. Specifically, we repeated the experiments shown in Figure 2 but now running SFQL with and without GPI (we can turn off GPI by replacing $c$ with $t$ in line 12 of Algorithm 3).

C.2 Analyzing the robustness of SFs

References