Title: KNOWLEDGE REPRESENTATION FOR REINFORCE-MENT LEARNING USING GENERAL VALUE FUNCTIONS Anonymous authors Paper under double-blind review

Abstract: Reinforcement learning (RL) is a very powerful approach for learning good control strategies from data. Value functions are a key concept for reinforcement learning, as they guide the search for good policies. A lot of effort has been devoted to designing and improving algorithms for learning value functions. In this paper, we argue that value functions are also a very natural way of providing a framework for knowledge representation for reinforcement learning agents. We show that generalized value functions provide a unifying lens for many algorithms, including policy gradient, successor features, option models and policies, and other forms of hierarchical reinforcement learning. We also demonstrate the potential of this representation to provide new, useful algorithms.

1. INTRODUCTION:

Value functions are at the heart of reinforcement learning algorithms (RL) as a very useful tool in guiding the progress towards good policies. Usually, a value function estimate, representing the expected discounted return of a policy, is maintained in order to guide policy improvement. However, the goal of having realistic AI agents requires us to consider how they may go beyond the goal of solving one task, to a setting in which such agents can acquire and maintain diverse knowledge about the world. This brings about the question of how such knowledge should be expressed and maintained in an RL agent.

In this paper, we highlight the fact that value functions can in fact be used as the main building block for knowledge representation in RL agents. We build on the framework of General Value Functions (GVFs) (White, 2015; Sutton & Tanner, 2005; Sutton et al., 2011; Schaul & Ring, 2013) , which have been proposed in prior work as a way to capture knowledge about the world in a flexible fashion. GVFs represent long-term predictions about different aspects of an agent's observations. For example, an RL agent interested in hockey can ask questions like "what is the expected time until I hit the puck, given my current strategy?" or "what are the chances of my team winning this game?" and represent the answers to these questions as GVFs. This form of knowledge representation provides two clear benefits. First, since it is grounded in actual observations, it can be learned incrementally from a single stream of experience, using off-policy learning methods. Second, as illustrated by the example questions above, it can be used to model the world at different time scales (Modayil et al., 2014) . The Horde architecture (Sutton et al., 2011) illustrates in fact the successful large-scale learning of GVFs about a diversity of signals and at many different time scales, in parallel, from a single stream of data. This aspect of GVFs is very appealing, as it allows using the experience (which may be difficult to acquire) in order to learn many different things. GVFs also have the advantage of being able to profit from a long history of RL algorithm development for value function learning (Sutton & Barto, 1998) .

Our main contribution in this paper is to unify and interpret several different RL algorithms, including policy gradients (Sutton et al., 1999a) and different ways of achieving temporal abstraction, such as successor features (Barreto et al., 2017) , option models and value functions (Sutton et al., 1999b) , feudal networks (Vezhnevets et al., 2017) and universal value functions (Schaul et al., 2015) through the lens of GVFs. We also explore how GVFs can be used to facilitate the development of new algorithmic ideas in RL, and we illustrate the benefits of this approach through two algorithms: a new approach to policy gradient, which produces much more stable and data-efficient convergence, and a combination of feudal networks and successor features.

2. BACKGROUND:

Consider a Markov Decision Process (MDP) with state space S, action space A, and transition function P (s |s, a). A task is specified using an extrinsic reward function R : S × A × S → [0, 1], and a discount value γ ∈ [0, 1], which define the expected discounted return:

E π [ ∞ t=0 γ t R t+1 ] = E π [ ∞ t=0 ( t i=1 γ)R t+1 ]

, also known as the value function of a given policy π.

General Value Functions (GVFs) Sutton et al. (2011) provide a unified way of expressing predictions about signals other than extrinsic rewards, under policies that are different from the behavior policy, and under flexible, state-dependent discount schemes. Given a policy π : S × A → [0, 1], a (possibly multi-dimensional) cumulant function C : S × A × S → R K and a continuation function γ : S → [0, 1], the associated generalized value function (GVF) v C,γ,π : S → R K predicts the expected cumulant-based return, discounted by the continuation function:

v C,γ,π (s) = E ∞ t=0 t i=1 γ(S i ) C t S 0 = s, A 0:∞ ∼ π .

Note that this definition extends easily to predictions associated with different initial conditions (e.g. for pairs (s, a), rather than just states).

Usual value functions are trivially GVFs v R,γ,π , where the cumulant is simply the MDP reward function, and the discount factor is constant across the state space. Similarly, when the cumulant C depends on state-action pairs, the corresponding GVF is equivalent to the state action Q-values.

In the following sections, we will explain how we can use GVFs to express different RL algorithms, gaining insight both into their behavior, as well as into paths for their possible improvement.

3. GVFS FOR SUCCESSOR FEATURES:

Successor representation. Under any distribution over the state space, as induced by a fixed policy, one can define a prediction for the discounted number of times a state s is visited. That is, we predict the one-hot cumulant I(s) such that C t = 1 if S t = s and 0 otherwise1 . For a fixed starting state s 0 , the associated prediction defines a measure over the state space S: µ(s|s 0 , γ, π). Dayan (1993) introduced the idea of using this representation of states through their possible futures, called successor representation, as a way to provide ideal features This becomes useful in describing predictions about other cumulants C: v C,γ,π (s 0 ) = Cdµ(•; s 0 , γ, π) (see appendix for proof).

Successor features Successor features (SF) (Barreto et al., 2017) generalize the idea of the successor representation to the case of function approximation in a natural way. Given a function φ : S × A × S → R K defining feature representations for s → a → s transitions, the SF vector is defined as

ψ(s, a; π) = E [ ∞ t=0 γ t φ(S t , A t+1 , S t+1 )|S 0 = s, A 1 = a, π] .

If the reward function is linear in the features (i.e. R(s, a, s ) = φ(s, a, s ) T w for some weight vector w), SFs become very useful in the context of transfer learning, where different tasks correspond to different w. Once SFs for a given policy are computed, they can be used for zero-shot policy evaluation, and in generalized policy improvement.

SF (Barreto et al., 2017) are naturally formulated as a GVF v φ,γ,π , where φ is a multi-dimensional cumulant and γ is constant A key result on SFs Barreto et al. (2017) can then be expressed and generalised immediately in the language of GVFs as follows: Proposition 1. For a fixed pair (π, γ), given a cumulant C : S × A × S → R k , and

w ∈ R k , v w T C,γ,π (s) = w T v C,γ,π (s).

This property is exploited in Barreto et al. (2017) for transfer learning. Given a new task corresponding to scalar cumulant C : S × A → R, the value of any given policy can be evaluated on this new task by approximating C with the L 2 projection on the space spanned by a multi-dimensional cumulant C. That is, given w C := arg min w (w T C-C ) 2 , one can estimate v C ,γ,π (s) ≈ w T C v C,γ,π (s). We will use the GVF version of SF in our experiments.

∇θv GVF π(θ) γ × s0 GVF π(θ) γ R s, a ∇θ log π(θ) (a)

The policy gradient algorithm describes the interdependence between the GVFs corresponding to the evaluation of a policy of a specific task (i.e. R) and the gradient of that evaluation with respect to the policy parameters (i.e. ∇ θ v)

    SF1 SF2 . . . SFk     GVF π(θ) γ     C1 C2 . . . Ck     s0 × [w1, w2, • • • , wk] ≈ ∇θv ×     C1 C2 . . . Ck     ≈ × ∇θ log π(θ) s, a GVF π(θ) γ R (b)

The GVFs involved in the computation of policy gradients can be naturally decoupled by using successor features to approximate the second GVF. The policy is evaluated on a set of cumulants (i.e. features) to compute successor features, which are then used to approximate the gradient ∇ θ v (see Proposition 1). 

4. GVFS FOR POLICY GRADIENT METHODS:

Performance gradient estimation techniques of score function and likelihood ratio, as introduced by Aleksandrov et al. (1968) and Rubinstein (1969) , are based on sampling trajectories to estimate both the value of a policy and the gradient used for improving the policy. Given a score function f that depends on a random variable sampled from a parameterised distribution q(θ), the gradient with respect to the parameters is given by

∇ θ E X∼q(θ) [f (X)] = E X∼q(θ) [f (X)∇ θ log q(X; θ)].

This principle is used in several popular RL algorithms, including REINFORCE (Williams, 1992) , actor-critic (Sutton, 1984) , policy gradient, eg. (Sutton et al., 1999a; Konda, 2000; Bhatnagar et al., 2009; Lillicrap et al.; Schulman et al., 2015) and other algorithms that use an estimate of the value function to compute the gradient of the policy parameters. The policy gradient theorem (Sutton et al., 1999a) provides a formal description of the procedure used in this broad class of algorithms.

We are now going to re-express this result in the language of GVFs, by re-casting the gradient computation in terms of an explicit cumulant. Theorem 1. Let π θ be a policy parameterised by a vector θ, γ be a constant continuation function, and C : S × A → R be a one-dimensional cumulant. The gradient of the general value function v C,γ,π θ (s) with respect to θ is itself a general value function that depends on the cumulant:

Ĉ(s, a) := v C,γ,π θ (s, a)∇ θ log π θ (a|s). That is, ∇ θ v C,γ,π θ (s) = v Ĉ,γ,π θ (s).

Figure 1a provides a visual depiction of this result and the appendix contains the proof.

The policy gradient theorem shows that these widely used methods are based on the estimation of two inter-dependent GVFs: the cumulant for one GVF is obtained as the output of another GVF. Note that this separation means we can easily consider other ways of estimating these cumulants.

4.1. BOOTSTRAPPED POLICY GRADIENT:

To illustrate the intuition that we gain from Theorem 1, we first run a procedure that is designed to follow the analytic description of the policy gradient: given policy parameters θ, (1) generate a number of rollouts from random initial states (uniformly sampled over the entire state space); (2) use TD(λ) on the sampled data to compute an estimate for the value function v R,γ,π θ ; (3) compute cumulants Ĉ in Theorem 1 based on the estimates in (1); and (4) generate a separate set of rollouts to estimate the GVF v R,γ,π θ , using the same TD(λ) procedure. We use TD(λ) to estimate GVFs since it has the flexibility of reusing previous estimates (i.e., bootstrapping). number of updates to policy parameters. We ran all versions of the algorithm over different eligibility trace parameters λ, constant learning rates for the value function α td , and constant learning rates α pg for policy parameters. For performance on various hyper-parameter settings, see Figure 6 (in Appendix). Mean and variance for the value of the policy as a function of policy updates are shown in blue when only the critic value is bootstrapped, in red when all GVF estimates are bootstrapped, and green when successor features are also used.

4.2. USING SUCCESSOR FEATURES FOR POLICY GRADIENT:

Theorem 1 provides a natural linear approximation to the gradient ∇ θ v. Given a finite number of auxiliary predictions (i.e. cumulants {C i } n i=1 ) and a linear approximation to an input cumulant Ĉ ≈ w i C i , we can compute ∇ θ v Ĉ,γ,π ≈ w i v Ci,γ,π , using the successor features idea (see Figure 1b for a corresponding illustration). The intuition is that successor features would help in tracking the continual change in cumulants that is a natural by-product of policy gradient. This should help when the gradient estimates are unstable; sampled data would be used to estimate the long-term accumulation of a fixed set of features instead of a set of parameter gradients.

4.3. EMPIRICAL ILLUSTRATION:

In Figure 2a , we illustrate the importance of bootstrapping not only the critic value v C,γ,π θ but also in any General Value Functions involved in the computation of the gradient with respect to the policy parameters. All algorithms were run on a simplified version of the four-room environment described in (Sutton et al., 1999a) , with discount factor set to 0.9, and the feature map used for linear value function approximation was computed using tile-coding (Sutton & Barto, 1998) (exact details of the experiments are in the appendix). Using small domains allows us to compute the exact value functions, and hence to compare the algorithms against ground truth. As can be seen, the proposed bootstrapped policy gradient approach provides significant improvement in data efficiency. While the advantage of bootstrapping compared to Monte Carlo estimation has been observed before, the effect is magnified through the use of multiple GVFs. 1999a ))(≈ 60 states and ≈ 15 total features). Bottom: large maze grid-world with sparse reward (≈ 3000 states and ≈ 90 total features). Each plot corresponds to a fixed number of steps L taken by the agent for every rollout, The plots displayed here correspond to the highest performing hyperparameter setting: α A is the learning rate for updates to the policy parameters, α C is the learning rate for updates to the critic component, and α G is the learning rate for updates to the gradient estimates. For performance on specific hyperparameter setting, see Figure 7 and 8 (in Appendix). Mean and variance for the value of the policy as a function of policy updates are shown in blue for baseline actor-critic, in green when actor-critic maintains bootstrapped estimates for parameter updates.

We tested the approach with the same tile-coding features as used for value function approximation. The results shown in Figure 2b demonstrate that estimating policy gradients using bootstrapped successor features exhibits much stronger robustness to changes in hyper-parameters.

Algorithm 1: Actor-Critic with GVFs for gradient estimation. Input: policy π(a|s, θ); critic state-value fn. v(s, w); general-value fn. ĝ(s, η). Algorithm parameters: step size α θ > 0, α w > 0, and α η > 0. repeat Initialize S (first state of episode);

I ← 1 repeat A ∼ π(a|s, θ) and take action A, observe S , R δ crit ← R + γv(S , w) -v(S, w) w ← w + α w Iδ crit ∇ w v(S, w) δ grad ← δ crit ∇ θ log π(A|S, θ) + γĝ(S , η) -ĝ(S, η) η ← η + α η Iδ grad ∇ η ĝ(S, η) θ ← θ + α θ ĝ(S, η) I ← γI and S ← γS until end of episode until convergence

Next, we tested the approach in the context of Actor-Critic (Konda, 2000) , an approach commonly used to scale the policy gradient algorithm to large or continuous environments. We modified the actor-critic algorithm in (Konda, 2000) to both the value function corresponding to the MDP reward function (i.e. the critic) and the gradients w.r.t. to the policy parameters. That is, just as the original actor-critic algorithm uses parameters w to approximate bootstrap values for the critic function (i.e. v R,γ,π (s) ≈ vw (s), we use a similar approximation for the GVF corresponding to policy gradient

Q(s 0 , ω) GVF π(ω) γ(1 -β(ω)) C(ω) s 0 Q(•, ω 0 ) R Q(•, ω 1 ) . . . Q(•, ω k ) (a) GVFs for Option-value function v W GVF π(g(M), η) γ W R + R I (g(M)) s v M GVF π(W, θ) γ M R s (b) GVFs for Feudal Networks.

Figure 4 : Left: Every option-value corresponds to a separate GVF, concerned both with external reward R, as well as all other GVFs. Right: In FuN, manager (M) and worker (W) are trained using separate GVFs: v M , concerned with external return as corresponding to W's policy; v W , conditioned on goals specified by M. estimates (i.e. v Ĉ,γ,π (s) ≈ ĝ(s, η)). By doing so, we replace updates to the policy parameters that consider only ∇ θ log π • Q with long term estimates of the GVFs derived from the analytic form of the policy gradient. These estimates contain gradient information from past gradient computations (i.e. they are bootstrapped). See Algorithm 2 in the appendix for details on the proposed procedure and other implementation details. See Figure 3 for a comparative analysis of the baseline actorcritic algorithm and the aforementioned modification; the results clearly demonstrate the benefit of a principled approach in estimating GVFs corresponding to policy gradients in an end-to-end algorithmic framework.

5. GVFS FOR HIERARCHICAL REINFORCEMENT LEARNING:

Hierarchical reinforcement learning refers to a collection of methods which aim to structure the policy of an agent into "chunks" which have a temporal extent and can be re-used for different tasks. A large variety of methods have been proposed, including options (Sutton et al., 1999b; Precup, 2000) , MAXQ (Dietterich, 2000) , feudal architectures (Dayan & Hinton, 1993; Vezhnevets et al., 2017) and others. We will now illustrate how GVFs can be used in a natural way to analyze and extend such approaches. We will focus on the options framework and on feudal architectures, since these two approaches have recently been shown to yield algorithms that can learn the hierarchical structure from scratch (Bacon et al., 2017; Vezhnevets et al., 2017) .

GVFs for options An option ω is defined as a tuple containing a set of states in which the option can be initiated, an internal policy π ω : S × A → [0, 1], which is used to pick actions when the option is executing, and a termination function β ω : S → [0, 1]. As in other recent work (Bacon et al., 2017) , we ignore the initiation set in this paper. The typical execution model for options uses a policy over options, π Ω , which chooses options from a set Ω. Whenever an option is picked, its policy chooses actions until the termination condition is met. Note that at a state s, an option ω will continue with probability 1 -β ω (s).

Options also have associated reward and transitions models (Sutton et al., 1999b) . For example, the reward model of an option is given by:

r(s, ω) = E[ ∞ t=0 γ t R t+1 |S t = s, ω t = ω] = E[R(s, A t+1 ) + γ(1 -β(S t+1 ))r(S t+1 , ω)|S t = s, A t+1 ∼ π ω (s, •), S t+1 ∼ p(•|s, A t+1 )]

It is easy to see then that r(s, ω) can be written as a GVF which has as cumulant the environment reward R, the continuation function is γ(1 -β ω(s) ) and the policy is π ω . A similar development can be done for option transition models.

Another important quantity in the context of options is the option-value function, Q πΩ (s, ω), which generalizes the action-value function, and is used to drive option construction algorithms such as option-critic. Indeed, the option-critic architecture (Bacon et al., 2017) uses a policy gradient algorithm to learn the internal policies and termination functions for a fixed number of options Ω = {ω 1 , • • • , ω k }. We now show that the option-value function can be expressed as a GVF.

Proposition 2. Given a set of options Ω and a fixed policy over options π Ω , define the cumulant C ω for option ω as C ω (s, a, s ) = R(s, a)

+ γβ ω (s )E [Q(s , ω ) | ω ∼ π Ω ( • |s )]. Then: Q πΩ (s, ω) = v Cω,γ(1-βω),πω (s, ω).

The proof is in the appendix. Figure 4a illustrates the statement. The GVF view highlights the fact that the option-value function depends both on a short term signal coming from the reward and a long-term signal summarizing the performance of other options. This leads to a very hard task, since each option has to be aware of the performance of the rest of the options. In the option-critic framework, this can lead to degenerate solutions, e.g. when each option considers itself less qualified than the others and wishes to cede control immediately (which leads to all options collapsing to singlestep actions), or when one option decides it is better than the others, and hence never terminates and tries to learn the optimal policy internally. Note that the option models, on the other hand, achieve a separation of concerns naturally. Hence, in the context of transfer learning, option models may be more useful than option-value functions.

GVFs for feudal networks Feudal Networks (FuN) (Vezhnevets et al., 2017) is an HRL approach designed to provide an explicit separation of concerns between levels of hierarchy. It uses a network which consists of two parts. The top level, or the Manager M, chooses goals g(M) at a slower time scale in a latent state-space that is itself learned. The lower level, or the Worker W, operates at a faster time scale and produces primitive actions, conditioned on the goals received from the Manager. The Worker is motivated to follow the goals by a combination of intrinsic and extrinsic reward. No gradients are propagated between W and M; M receives its learning signal from the environment alone, adjusting g(M) to maximize the extrinsic reward using transition policy gradient (Vezhnevets et al., 2017) .

We now show how GVFs can be used to provide a general version of the transition policy gradient introduced in Vezhnevets et al. ( 2017). Proposition 3. Let z ∈ Z ⊆ R k represent some latent variables used to model a hierarchical policy parameterised as: π(a|s) = π(a|s, z; θ 2 )dπ(z|s; θ 1 ). Let v be a set of random variables corresponding to predictions about π. Given continuation function γ and cumulant C :

S×A×Z → R, ∇ θ1 v C,γ,π (s) = v Ĉ1,γ,π (s) and ∇ θ2 v C,γ,π (s) = v Ĉ2,γ,π (s) with Ĉ1,t = v C,γ,π (s t , z t , v t )∇ θ1 log π(z t , v t |s t ; θ 1 ), and Ĉ2,t = v C,γ,π (s t , a t , z t )∇ θ2 log π(a t |s t , z t ; θ 2 ).

The proof is in the appendix. This result allows the manager in FuN to move from fixed temporal difference in state representations (e.g. v t := s t+c ), to any general prediction conditioned on π. It also shows that the transition policy gradient can be used for broader choices of latent attributes than those used in Vezhnevets et al. (2017) , where log π(z t , v t ) was proportional to the cosine distance between (s t+c -s t ) and z t .

When v C,γ,π (s, a) in Prop. 3 is independent of z, low-level action choices that ignore z (i.e. π(a|s, z; θ 2 ) = π(a|s; θ 2 )) end up as valid local minima for the corresponding optimisation problem. One way to avoid this kind of degeneracy is to use intrinsic rewards corresponding to some notion of alignment between the observed trajectory and z (Dayan & Hinton, 1993; Barto et al., 2004; Kulkarni et al., 2016; Baranes & Oudeyer, 2013) . Alternatively, one could use Universal Value Functions as GVFs, consider latents z that determine specific goals (i.e. (C, γ) pairs) and train low-level controllers to achieve those goals (Schaul et al., 2015) .

To illustrate the ideas above, we have used the following GVFs: v := v C,γ,π , with C t = s t+c -s t and some discount factor γ possibly different from the discount of the GVF v R,γ,π used for evaluating the agent on the given task. We assumed a von Mises-Fisher distribution for the higherlevel policy: π(z t , v t |s t ) ∝ exp(d cos (z t , v t )). The intrinsic reward for the low-level component was chosen as :

r I t = t-c j=0 γ γ j (st-st-c) T zt-c-j

vt-c-j zt-c-j . See Appendix for details on an efficient recursive computation of this reward and a proof that this corresponds to an intrinsic return

R I = ∞ i=0 γ i log π(v i , z i |s i ).

We also use successor features (SF) for GVFs. We conducted a number of experiments in the ATARI games (Bellemare et al., 2013) for which the original FuN Figure 5 : Training curves for FuN with high-level choices over GVFs in ATARI games (Bellemare et al., 2013) . In Seaquest and Enduro, agents for which the manager uses successor features consistently outperform the baseline algorithm. In Gravitar and Ms. Pacman, the proposed modifications have no impact on performance. See appendix for more results.

architecture was shown to exhibit substantial empirical improvements over corresponding network structures (Vezhnevets et al., 2017) . The experimental setup and all the hyper-parameters were set to those used in the original paper on FuN (Vezhnevets et al., 2017) . The results in Figure 5 show that using GVFs either reproduces the results in baseline FuN or improves the learning speed.

6 OTHER RELATED WORK Schaul et al. (2015) address the issue of learning a large number of GVFs individually, which is not scalable and misses out on learning shared feature structure among different GVFs. They propose that an agent may want to focus on learning a special type of GVF, which is optimal with respect to a specific minimum-time-to-goal based task. Such a task can be specified using a (C, γ) pair, in which C is positive at the goal state(s) and 0 otherwise, and γ < 1 is constant at all states except the goal, where it is 0. In general, however, we could have GVFs that are optimal with respect to any cumulant and continuation, which we can be denoted as v * C,γ . Note that, if C is multidimensional, additional requirements such as having a bounded output and an ordering on the co-domain of C are necessary in this case. In Universal Value Functions (UVFs), the task (C, γ) can be summarized through a goal state g, which can then be presented as an input, to allow an agent to generalize between tasks. Hence, in this approach, a shared approximator v(s, g) is estimated from data.

Synthetic gradients (Jaderberg et al., 2016) allow a learner to estimate directly a gradient for certain input data points, without backpropagation. The idea is to use a secondary function approximator for this estimation. The policy gradient approach that we presented is similar in spirit, as we use a separate GVF as a gradient estimator. Further connections are left for future investigation. Auxiliary tasks Jaderberg et al. (2017) are an approach which uses secondary reward functions in order to learn a better internal representation for an RL agent. The idea of using many GVFs, corresponding to many different cumulants, is very much in the same spirit.

7. CONCLUSION AND FUTURE WORK:

We proposed to use GVFs as a unifying language for describing several popular reinforcement learning algorithms. This approach provides interesting connections between algorithms and helps us understand certain pathological behaviors (such as the collapse encountered in certain temporal abstraction algorithms). Moreover, we can use the GVF framework in order to generate new algorithms, by making different choices for how these functions are encoded. We illustrated this ability by generating new versions of policy gradient and of feudal networks. In the case of policy gradient, the proposed approach, which uses bootstrapping as well as successor features, greatly improves learning speed and stability. However, more experience is needed with this algorithm, especially in conjunction with function approximation.

GVFs can enable a natural injection of domain knowledge, as the designer of the system can specify cumulants and continuation functions, then let the system learn about all of them. We will investigate this approach in future work. GVFs promise to enable life-long, incremental learning, as an agent could add new GVFs to its repertoire over time, perhaps following a meta-learning or curriculum learning approach.

Proof. WLOG, assume C is defined over state-action pairs, i.e C : S × A → R and fix a starting state s 0 . Let S 0 , A 0 , S 1 , A 1 , •, S n , A n , • • • be the random trajectory generated when following policy π from initial state S 0 = s 0 and using γ(S i ) as a Bernoulli process that determines the termination of a trajectory. Following the definition of general value functions (see Section 2),

Cdµ(•; s 0 , γ, π) = s,a C(s, a)v I(s,a),γ,π (s 0 ) = s,a C(s, a)E ∞ t=0 t i=1 γ(S i ) I((S t , A t ) = (s, a)) S 0 = s 0 , A 0:∞ ∼ π = E ∞ t=0 t i=1 γ(S i ) s,a C(s, a)I((S t , A t ) = (s, a)) S 0 = s 0 , A 0:∞ ∼ π = E ∞ t=0 t i=1 γ(S i ) C t S 0 = s 0 , A 0:∞ ∼ π = v(s 0 ; C, γ, π)

Theorem. Sutton et al. (1999a) . (Policy gradient theorem) Let π θ be a policy parameterised by a vector θ, γ be a constant continuation function, and C : S × A → R be a one-dimensional cumulant. The gradient of the general value function v C,γ,π θ (s) with respect to θ is itself a general value function that depends on the cumulant: Proposition. Fix a set of options Ω and a meta-policy π Ω and define the cumulant C(ω) for every option ω as Note that the statement above is equivalent to the Bellman equation for General Value Functions, where the cumulant is C(ω) and continuation function is γ(1 -β(ω)). Since the Bellman equation is known to have a unique solution, the statement of the proposition follows as a direct consequence.

Ĉ(s, a) := v C,γ,π θ (s, a)∇ θ log π θ (a|s).

C t (ω) = R(S t , A t ) + γβ(S t+1 ; ω)E Q(S t+1 , ω ) | ω ∼ π Ω S t+1 )]. Then, Q(s 0 , ω) = v(s 0 ; C(ω), γ(1 -β(ω)), π(ω)).

Proposition. Assume latent attributes z are elements of Z ⊆ R k . Let θ 1 and θ 2 be two sets of parameters used to model distributions π(z|s; θ 1 ) and π(a|s, z; θ 2 ), correspondingly. These models describe the low-level action choice π(a|s) = π(a|s, z)dπ(z|s). Let γ be a constant continuation function, and C be any cumulant defined on S × A × Z → R. Additionally, let v be a set of random variables corresponding to predictions about the policy π.

EQUATION

Ĉ2,t = v(s t , a t , z t ; C, γ, π)∇ θ2 log π(a t |s t , z t ; θ 2 ).

Proof. The statement is a corollary to Theorem 1, where the gradient with respect to the flat policy is:

∇ θ1 π(a, z, v|s; θ 1 , θ 2 ) = ∇ θ1 π(a|z, s; θ 2 )π(z, v|s; θ 1 ) = π(a|z, s; θ 2 )∇ θ1 π(z, v|s; θ 1 ) = π(a, z, v|s; θ 1 , θ 2 )∇ θ1 log π(z, v|s; θ 1 ) ∇ θ2 π(a|s; θ 1 , θ 2 ) = ∇ θ2 π(a|z, s; θ 2 )π(z, v|s; θ 1 ) = π(z, v|s; θ 1 )∇ θ2 π(a|z, s; θ 2 ) = π(a, z, v|s; θ 1 , θ 2 )∇ θ2 log π(a|z, s; θ 2 ) icy gradients estimation, we used parameters η ∈ R K×|A| and ĝ(s, η) = η T φ(s).

Algorithm 2: Actor-Critic with GVFs for gradient estimation.

Input: policy π(a|s, θ); critic state-value fn. v(s, w); general-value fn. ĝ(s, η). Algorithm parameters: step size α θ > 0, α w > 0, and α η > 0. repeat Initialize S (first state of episode); I ← 1 repeat A ∼ π(a|s, θ) and take action A, observe S , R δ 

crit ← R + γv(S , w) -v(S, w) w ← w + α w Iδ crit ∇ w v(S, w) δ grad ← δ crit ∇ θ log π(A|S, θ) + γĝ(S , η) -ĝ(S, η) η ← η + α η Iδ grad ∇ η ĝ(S, η) θ ← θ + α θ ĝ(S,

C DETAILS OF GVF-FUN EXPERIMENTS:

We follow the same experimental procedure described in (Vezhnevets et al., 2017) , where hyperparameters are tuned using randomized search on the following domain: the learning rate for the policy gradient updates is sampled from Log-Uniform(10 -4.5 , 10 -3.5 ); the entropy penalty was sampled from Log-Uniform(10 -4 , 10 -3 ); the weight of the intrinsic reward was sampled from Uniform(0, 1). Moreover, to increase stability, the reward is clipped in [-1, 1].

For the purpose of illustrating the concept of separation of concerns, the worker and the manager were trained with respect to GVFs of different discount values: manager's discount γ M = 0.99 and worker's discount γ W = 0.95.

We compare baseline FuN with a modified network where the goal g picked by the manager corresponds to the latent z in Proposition 3 and the manager is trained with transition policy gradient ∇g t = A M t d cos (v t , g t (θ)). Since the prediction horizon of the baseline FuN agent is set to c = 10, we compute successor features v t using a discount value γ = 0.8 to make sure that the corresponding temporal resolution is essentially the same2 . The intrinsic reward corresponding to specific goals set by the manager was computed using Equation 1. Since our intent was to test the hypothesis that a Feudal Network would be capable of reasoning over successor features, all other components were kept invariant.

See Figure 9 for results for all the games for which we have ran the experiments. Specifically, the plots in the figure provide the average and standard deviations over 5 different runs of the algorithm, where each run was based on a randomized search picking the top performing hyper-parameter setting among 20 samples, and the policy gradient algorithm is performed over 80 epochs 3 . Figure 6 : Policy gradient updates with TD(λ) estimates. L 1 norm of the exact value function vs. number of updates to policy parameters. Each plot corresponds to a fixed number N of rollouts for estimating GVFs, a fixed λ as eligibility for TD(λ), fixed learning rate for α td , and fixed learning rate α pg for policy parameters. Mean and variance for the value of the policy as a function of policy updates are shown in (blue) when only the critic value is bootstrapped, in (red) when all GVF estimates are bootstrapped, and (green) when successor features are used to stabalized the learning algorithm.

Figure 7 : Actor-Critic with bootstrapped gradient estimates -results on four-room maze (introduced in (Sutton et al., 1999a) ) L 1 norm of the exact value function vs. number of rollouts used for policy updates. Each plot corresponds to a fixed number of steps L taken by the agent for every rollout, the learning rate α A for updates to the policy parameters, a learning rate α C for updates to the critic component, and a learning rate α G for updates to the gradient estimates. Mean and variance for the value of the policy as a function of policy updates are shown in (blue) for baseline actor-critic, in (green) when actor-critic maintains bootstrapped estimates for parameter updates. (Bellemare et al., 2013) demonstrate gains in data-efficiency for some ATARI games. In games such as Seaquest, Alien, and Enduro, agents for which the manager uses successor features consistently outperform the baseline algorithm. In Gravitar, Amidar and Ms. Pacman, the proposed modifications have no impact on performance. In Frostbite, both versions of the algorithm are usually stuck in a local minimum (average reward ≈ 250), and the noticeable improvement is due to one of the agents luckily getting out of the local minimum for a limited number of steps.

:

Similar one-hot cumulants can be defined for (s, a) pairs or s → a → s transitions and derive the corresponding measure over spaces S × A and S × A × S, respectively.

When a GVF is using a constant discount value γ and no explicit horizon length is used, rewards obtained after log γ become numerically insignificant (i.e. ≤ Rmax).

A training epoch is equivalent to 10 6 steps.

Figures and Tables:

Figure 1: GVFs for Policy Gradient Methods

(a) This plot compares the best combination of hyper-parameters for each algorithm -each plot corresponds to a fixed number N of rollouts for estimating GVFs.(b) Plots corresponding to individual hyper-parameter configurations illustrate the increased stability of the bootstrapped policy gradient approach when gradients are approximated with successor features.

Figure 2: Policy gradient updates with TD(λ) estimates. L 1 norm of the exact value function vs.number of updates to policy parameters. We ran all versions of the algorithm over different eligibility trace parameters λ, constant learning rates for the value function α td , and constant learning rates α pg for policy parameters. For performance on various hyper-parameter settings, see Figure6(in Appendix). Mean and variance for the value of the policy as a function of policy updates are shown in blue when only the critic value is bootstrapped, in red when all GVF estimates are bootstrapped, and green when successor features are also used.

Figure3: Actor-Critic with bootstrapped gradient estimates. L 1 norm of the exact value function vs. number of rollouts used for policy updates. Top: four-room maze introduced in(Sutton et al.,  1999a))(≈ 60 states and ≈ 15 total features). Bottom: large maze grid-world with sparse reward (≈ 3000 states and ≈ 90 total features). Each plot corresponds to a fixed number of steps L taken by the agent for every rollout, The plots displayed here correspond to the highest performing hyperparameter setting: α A is the learning rate for updates to the policy parameters, α C is the learning rate for updates to the critic component, and α G is the learning rate for updates to the gradient estimates. For performance on specific hyperparameter setting, see Figure7and 8 (in Appendix). Mean and variance for the value of the policy as a function of policy updates are shown in blue for baseline actor-critic, in green when actor-critic maintains bootstrapped estimates for parameter updates.

Proof. (sketch) Recall from Section 3 that v(s; C, γ, π) = Cdµ(•; s, γ, π) and v C,γ,π (s, a) = Cdµ(•; s, a, γ, π). The derivation below follows,∇ θ v C,γ,π(θ) (s 0 ) = a∈A v C,γ,π (s, a)∇ θ π(a|s; θ)dµ(s; s 0 , γ, π) = a∈A π(a|s; θ) v C,γ,π (s, a) ∇ θ π(a|s;θ) π(a|s;θ)dµ(s; s 0 , γ, π)= v C,γ,π (s, a)∇ θ log π(a|s; θ)dµ(s, a; s 0 , π(θ), γ).

Proof. Let V (s) := E[Q(s, ω)|ω ∼ π Ω ].Based on the definition provided inBacon et al. (2017),Q(s 0 , ω) = a∈A π(a|s 0 ) R(s 0 , a) + γ s ∈S P (s |s 0 , a) [(1 -β(s ; ω)Q(s , ω) + β(s ; ω)V (s )] = a∈A π(a|s 0 ) R(s 0 , a) + γ s ∈S P (s |s 0 , a)β(s ; ω)V (s |s 0 , a)(1 -β(s ; ω)Q(s , ω) = E [C(s 0 , A, S ; ω) | A ∼ π(s 0 ); S ∼ P (•|s 0 , A)] + E [γ(1 -β(S ; ω))Q(S ,ω) | A ∼ π(s 0 ); S ∼ P (•|s 0 , A)] .

Figure8: Actor-Critic with bootstrapped gradient estimates -results on large maze grid-world with sparse reward. L 1 norm of the exact value function vs. number of rollouts used for policy updates. Each plot corresponds to a fixed number of steps L taken by the agent for every rollout, the learning rate α A for updates to the policy parameters, a learning rate α C for updates to the critic component, and a learning rate α G for updates to the gradient estimates. Mean and variance for the value of the policy as a function of policy updates are shown in (blue) for baseline actor-critic, in (green) when actor-critic maintains bootstrapped estimates for parameter updates.

Figure 9: Training curves for FuN with high-level choices over GVFs. Results on ATARI games(Bellemare et al., 2013) demonstrate gains in data-efficiency for some ATARI games. In games such as Seaquest, Alien, and Enduro, agents for which the manager uses successor features consistently outperform the baseline algorithm. In Gravitar, Amidar and Ms. Pacman, the proposed modifications have no impact on performance. In Frostbite, both versions of the algorithm are usually stuck in a local minimum (average reward ≈ 250), and the noticeable improvement is due to one of the agents luckily getting out of the local minimum for a limited number of steps.

η) I ← γI and S ← γS until end of episode until convergence

Table content: <table/>

Peer review (iclr2019):
 The authors analyze various RL algorithms under the purview of Generalized Value Functions (Sutton et al. 2011). Specifically, the successor feature vector, the policy-gradient theorem, the option-value function, and the gradients for manager/worker in FeUdal Networks are all represented crisply in terms of GVFs. The detailed proofs in the Appendix and the mathematical rigor are appreciated. A major motivation for unifying ideas under GVFs is to facilitate development of new algorithms, but I find the paper slightly less convincing on this front. With respect to different sections: • [GVF for PG]: Rewriting the policy-gradient theorem with 2 GVFs, the authors propose to improve on the baseline algorithm with bootstrapping on both the critic and the actor-gradients. Although the results on a small domain look interesting, I would have enjoyed some discussion on the scalability aspects and integration/comparison with more recent actor-critic algorithms. • [GVF for Options]: The authors claim that “The GVF view highlights the fact that the option-value function depends .... and a long-term signal summarizing the performance of other options”. I believe that the definition of the option-value defined in Bacon et al. (2017) makes this dependence quite clear – it has an expectation over the option-value of all options. Therefore, I’m unable to appreciate the importance of writing option-value in GVFs and/or deriving an algorithmic improvement out of that. • [GVF for FuN]: Using the GVF view, the authors propose to use a different prediction variable (v) for the policy – i.e. instead of difference in state representation at (t+c) and (t) as used in FuN, they use a discounted (by gamma_hat) sum of these differences. Is this interpretation correct? If yes, could you provide some intuition for how this amounts to an algorithmic improvement over FuN? The Atari results definitely don’t show the improvement empirically.