Generalized Off-Policy Actor-Critic
Shangtong Zhang Wendelin Boehmer Shimon Whiteson



Diversity with Cooperation: Ensemble Methods for Few-Shot Classification
    Nikita Dvornik,  Cordelia Schmid,  Julien Mairal



Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000
Grenoble, France

firstname.lastname@inria.fr

    December 30, 2023
==================================================================================================================================================================




We propose a new objective, the counterfactual objective, unifying existing objectives for off-policy policy gradient algorithms in the continuing reinforcement learning (RL) setting. Compared to the commonly used excursion objective, which can be misleading about the performance of the target policy when deployed, our new objective better predicts such performance. We prove the Generalized Off-Policy Policy Gradient Theorem to compute the policy gradient of the counterfactual objective and use an emphatic approach to get an unbiased sample from this policy gradient, yielding the Generalized Off-Policy Actor-Critic (Geoff-PAC) algorithm. We demonstrate the merits of Geoff-PAC over existing algorithms in Mujoco robot simulation tasks, the first empirical success of emphatic algorithms in prevailing deep RL benchmarks. 




§ INTRODUCTION

Reinforcement learning (RL) algorithms based on the policy gradient theorem <cit.> have recently enjoyed great success in various domains, e.g., achieving human-level performance on Atari games <cit.>. The original policy gradient theorem is on-policy and used to optimize the on-policy objective. However, in many cases, we would prefer to learn off-policy to improve data efficiency <cit.> and exploration <cit.>. To this end, the Off-Policy Policy Gradient (OPPG) Theorem <cit.> was developed and has been widely used  <cit.>. 

Ideally, an off-policy algorithm should optimize the off-policy analogue of the on-policy objective. In the continuing RL setting, this analogue would be the performance of the target policy in expectation w.r.t. the stationary distribution of the target policy, which is referred to as the alternative life objective <cit.>. This objective corresponds to the performance of the target policy when deployed. Previously, OPPG optimizes a different objective, the performance of the target policy in expectation w.r.t. the stationary distribution of the behavior policy. This objective is referred to as the excursion objective <cit.>, as it corresponds to the excursion setting <cit.>. Unfortunately, the excursion objective can be misleading about the performance of the target policy when deployed, as we illustrate in Section <ref>. 

It is infeasible to optimize the alternative life objective directly in the off-policy continuing setting. Instead, we propose to optimize the counterfactual objective, which approximates the alternative life objective. In the excursion setting, an agent in the stationary distribution of the behavior policy considers a hypothetical excursion that follows the target policy. The return from this hypothetical excursion is an indicator of the performance of the target policy. The excursion objective measures this return w.r.t. the stationary distribution of the behavior policy, using samples generated by executing the behavior policy. By contrast, evaluating the alternative life objective requires samples from the stationary distribution of the target policy, to which the agent does not have access.  In the counterfactual objective, we use a new parameter γ̂ to control how counterfactual the objective is, akin to <cit.>. With γ̂ = 0, the counterfactual objective uses the stationary distribution of the behavior policy to measure the performance of the target policy, recovering the excursion objective. With γ̂ = 1, the counterfactual objective is fully decoupled from the behavior policy and uses the stationary distribution of the target policy to measure the performance of the target policy, recovering the alternative life objective. As in the excursion objective, the excursion is never actually executed and the agent always follows the behavior policy. 




We make two contributions in this paper.
First, we prove the Generalized Off-Policy Policy Gradient (GOPPG) Theorem, which gives the policy gradient of the counterfactual objective. 
Second, using an emphatic approach <cit.> to compute an unbiased sample for this policy gradient, we develop the Generalized Off-Policy Actor-Critic (Geoff-PAC) algorithm. We evaluate Geoff-PAC empirically in challenging robot simulation tasks with neural network function approximators. Geoff-PAC outperforms the actor-critic algorithms proposed by <cit.>, and to our best knowledge, Geoff-PAC is the first empirical success of emphatic algorithms in prevailing deep RL benchmarks.



§ BACKGROUND
 
We use a time-indexed capital letter (e.g., X_t) to denote a random variable. We use a bold capital letter (e.g., X) to denote a matrix and a bold lowercase letter (e.g., x) to denote a column vector. If x: 𝒮→ℝ is a scalar function defined on a finite set 𝒮, we use its corresponding bold lowercase letter to denote its vector form, i.e., x≐ [x(s_1), …, x(s_|𝒮|)]^T. We use I to denote the identity matrix and 1 to denote an all-one column vector.

We consider an infinite horizon MDP <cit.> consisting of a finite state space 𝒮, a finite action space 𝒜, a bounded reward function r: 𝒮×𝒜→ℝ and a transition kernel p: 𝒮×𝒮×𝒜→ [0, 1]. 
We consider a transition-based discount function <cit.> γ: 𝒮×𝒜×𝒮→ [0, 1] for unifying continuing tasks and episodic tasks. 
At time step t, an agent at state S_t takes an action A_t according to a policy π: 𝒜×𝒮→ [0, 1]. The agent then proceeds to a new state S_t+1 according to p and gets a reward R_t+1 satisfying 𝔼[R_t+1] = r(S_t, A_t). The return of π at time step t is G_t ≐∑_i=0^∞Γ_t^i-1R_t+1+i, where Γ_t^i-1≐Π_j=0^i-1γ(S_t+j, A_t+j, S_t+j+1) and Γ_t^-1≐ 1. 
We use v_π to denote the value function of π, which is defined as v_π(s) ≐𝔼_π[G_t|S_t=s]. Like <cit.>, we assume v_π exists for all s. We use q_π(s, a) ≐𝔼_π[G_t | S_t = s, A_t = a] to denote the state-action value function of π. We use P_π to denote the transition matrix induced by π, i.e., P_π[s, s^'] ≐∑_a π(a | s)p(s^'|s, a). 
We assume the chain induced by π is ergodic and use d_π to denote its unique stationary distribution.

We define D_π≐ diag (d_π). 

In the off-policy setting, an agent aims to learn a target policy π but follows a behavior policy μ. We use the same assumption of coverage as <cit.>, i.e., ∀ (s, a),  π(a | s) > 0 μ(a | s) > 0. 
We assume the chain induced by μ is ergodic and use d_μ to denote its stationary distribution. Similarly, D_μ≐ diag(d_μ). We define ρ(s, a) ≐π(a | s)/μ(a | s), ρ_t ≐ρ(S_t, A_t) and γ_t ≐γ(S_t-1, A_t-1, S_t).

Typically, there are two kinds of tasks in RL, prediction and control.

Prediction: In prediction, we are interested in finding the value function v_π of a given policy π. Temporal Difference (TD) learning <cit.> is perhaps the most powerful algorithm for prediction. TD enjoys convergence guarantee in both on- and off-policy tabular settings. TD can also be combined with linear function approximation. The update rule for on-policy linear TD is w ← w + αΔ_t, where α is a step size and Δ_t ≐ [R_t+1 + γ V(S_t+1) - V(S_t)]∇_w V(S_t) is an incremental update. Here we use V to denote an estimate of v_π parameterized by w. <cit.> prove the convergence of on-policy linear TD. In off-policy linear TD, the update Δ_t is weighted by ρ_t. The divergence of off-policy linear TD is well documented <cit.>. To approach this issue, Gradient TD methods () were proposed. Instead of bootstrapping from the prediction of a successor state like TD, Gradient TD methods compute the gradient of the projected Bellman error directly. Gradient TD methods are true stochastic gradient methods and enjoy convergence guarantees. However, they are usually two-time-scale, involving two sets of parameters and two learning rates, which makes it hard to use in practice <cit.>. To approach this issue, Emphatic TD (ETD, ) was proposed. 

ETD introduces an interest function i: 𝒮→ [0, ∞) to specify user's preferences for different states. With function approximation, we typically cannot get accurate predictions for all states and must thus trade off between them. States are usually weighted by d_μ(s) in the off-policy setting (e.g., Gradient TD methods) but with the interest function, we can explicitly weight them by d_μ(s)i(s) in our objective.
Consequently, we weight the update at time t via M_t, which is the emphasis that accumulates previous interests in a certain way. In the simplest form of ETD, we have M_t ≐ i(S_t) + γ_t ρ_t-1M_t-1. The update Δ_t is weighted by ρ_t M_t. In practice, we usually set i(s) ≡ 1.

Inspired by ETD, <cit.> propose to weight Δ_t via ρ_t c̅(S_t) in the Consistent Off-Policy TD (COP-TD) algorithm, where c̅(s) ≐d_π(s)/d_μ(s) is the density ratio, which is also known as the covariate shift <cit.>. To learn c̅ via stochastic approximation, <cit.> propose the COP operator. However, the COP operator does not have a unique fixed point. 
Extra normalization and projection is used to ensure convergence <cit.> in the tabular setting. 
To address this limitation, <cit.> further propose the γ̂-discounted COP operator. 

<cit.> define a new transition matrix P_γ̂≐γ̂P_π + (1 - γ̂) 1d_μ^T where γ̂∈ [0, 1] is a constant. Following this matrix, an agent either proceeds to the next state according to P_π w.p. γ̂ or gets reset to d_μ w.p. 1 - γ̂. <cit.> show the chain under P_γ̂ is ergodic. With d_γ̂ denoting its stationary distribution, they prove 

    d_γ̂ = (1 - γ̂)(I - γ̂P_π^T)^-1d_μ   (γ̂ < 1)

and d_γ̂ = d_π  (γ̂=1).

With c(s) ≐d_γ̂(s)/d_μ(s), <cit.> prove that

    c = γ̂D_μ^-1P_π^TD_μc + (1 - γ̂) 1,

yielding the following learning rule for estimating c in the tabular setting:

    C(S_t+1) ← C(S_t+1) + α [γ̂ρ_t C(S_t) + (1 - γ̂) - C(S_t+1)],

where C is an estimate of c and α is a step size. A semi-gradient is used when C is a parameterized function <cit.>. For a small γ̂ (depending on the difference between π and μ), <cit.> prove a multi-step contraction under linear function approximation. For a large γ̂ or nonlinear function approximation, they provide an extra normalization loss for the sake of the constraint d_μ^Tc = 1^Td_γ̂ = 1. <cit.> use ρ_t c(S_t) to weight the update Δ_t in Discounted COP-TD. They demonstrate empirical success in Atari games <cit.> with pixel inputs.

Control: In this paper, we focus on policy-based control. 
In the on-policy continuing setting, we seek to optimize the average value objective <cit.>

    J_π≐∑_s d_π(s) i(s) v_π(s).

Optimizing the average value objective is equivalent to optimizing the average reward objective <cit.> if both γ and i are constant (see ).
In general, the average value objective can be interpreted as a generalization of the average reward objective to adopt transition-based discounting and nonconstant interest function.

In the off-policy continuing setting, <cit.> propose to optimize the excursion objective 

    J_μ≐∑_s d_μ(s)i(s)v_π(s)

instead of the alternative life objective J_π. 
The key difference between J_π and J_μ is how we trade off different states.
With function approximation, it is usually not possible to maximize v_π(s) for all states, which is the first trade-off we need to make.
Moreover, visiting one state more implies visiting another state less, which is the second trade-off we need to make.
J_μ and J_π achieve both kinds of trade-off according to d_μ and d_π respectively.
However, it is J_π, not J_μ, that correctly reflects the deploy-time performance of π,
as the behavior policy will no longer matter 
when we deploy the off-policy learned π in a continuing task.

In both objectives, i(s) is usually set to 1. We assume π is parameterized by θ. In the rest of this paper, all gradients are taken w.r.t. θ unless otherwise specified, and we consider the gradient for only one component of θ for the sake of clarity. 
It is not clear how to compute the policy gradient of J_π in the off-policy continuing setting directly. 
For J_μ, we can compute the policy gradient as 

    ∇ J_μ = ∑_s d_μ(s)i(s)∑_a (q_π(s, a) ∇π(a | s) + π(a | s)∇ q_π(s, a) ).

<cit.> prove in the Off-Policy Policy Gradient (OPPG) theorem that we can ignore the term π(s, a)∇ q_π(s, a) without introducing bias for a tabular policy[See Errata in <cit.>, also in <cit.>.] when i(s) ≡ 1, yielding the Off-Policy Actor Critic (Off-PAC), which updates θ as

    θ_t+1 = θ_t + αρ_t q_π(S_t, A_t) ∇logπ(A_t | S_t),

where α is a step size, S_t is sampled from d_μ, and A_t is sampled from μ(· | S_t). 
For a policy using a general function approximator, <cit.> propose a new OPPG theorem. They define

    F^(1)_t    ≐ i(S_t) + γ_t ρ_t-1F^(1)_t-1 ,    M^(1)_t ≐ (1 - λ_1) i(S_t) + λ_1 F^(1)_t,
    
    Z_t^(1)   ≐ρ_t M^(1)_t q_π(S_t, A_t) ∇logπ(A_t | S_t),

where λ_1 ∈ [0, 1] is a constant used to optimize the bias-variance trade-off and F^(1)_-1≐ 0.
<cit.> prove that Z_t^(1) is an unbiased sample of ∇ J_μ in the limiting sense if λ_1 = 1 and π is fixed, i.e., lim_t→∞𝔼_μ[Z_t^(1)] = ∇ J_μ. 
Based on this, <cit.> propose the Actor-Critic with Emphatic weightings (ACE) algorithm,
which updates θ as θ_t+1 = θ_t + α Z_t^(1).
ACE is an emphatic approach where M_t^(1) is the emphasis to reweigh the update.



§ THE COUNTERFACTUAL OBJECTIVE





We now introduce the counterfactual objective 

    J_γ̂≐∑_s d_γ̂(s) î(s) v_π(s),

where î is a user-defined interest function. Similarly, we can set î(s) to 1 for the continuing setting but we proceed with a general î. When γ̂=1, J_γ̂ recovers the alternative life objective J_π. When γ̂=0, J_γ̂ recovers the excursion objective J_μ. To motivate the counterfactual objective J_γ̂, we first present the two-circle MDP (Figure <ref>) to highlight the difference between J_π and J_μ.

In the two-circle MDP, an agent needs to make a decision only in state . The behavior policy μ proceeds to  or  randomly with equal probability. 
For this continuing task, the discount factor γ  is always 0.6 and the interest is always 1.
Under this task specification <cit.>, the optimal policy under the alternative life objective J_π, which is equivalent to the average reward objective as γ and i are constant, is to stay in the outer circle.
However, to maximize J_μ, the agent prefers the inner circle.
To see this, first note v_π() and v_π() hardly change w.r.t. π, and we have v_π() ≈ 3.6 and v_π() ≈ 5. To maximize J_μ, the target policy π would prefer transitioning to state  to maximize v_π().
The agent, therefore, remains in the inner circle.
The two-circle MDP is tabular, so the policy maximizing v_π(s) for all s can be represented accurately.
If we consider an episodic task, e.g., we aim to maximize only v_π() and set the discount of the transition back to  to 0, such policy will be optimal under the episodic return criterion.
However, when we consider a continuing task and aim to optimize J_π, we have to consider state visitation.
The excursion objective J_μ maximizes v_π() regardless of the state visitation under π, 
yielding a policy π that never visits the state , a state of the highest value.
Such policy is sub-optimal in this continuing task.
To maximize J_π, the agent has to sacrifice v_π() and visits state  more.
This two-circle MDP is not an artifact due to the small γ.
The same effect can also occur with a larger γ if the path is longer.
With function approximation, the discrepancy between J_μ and J_π can be magnified as we need to make trade-off in both maximizing v_π(s) and state visitation.


One solution to this problem is to set the interest function i in J_μ in a clever way. However, it is not clear how to achieve this without domain knowledge. <cit.> simply set i to 1. Another solution might be to optimize J_π directly in off-policy learning, if one could use importance sampling ratios to fully correct d_μ to d_π as <cit.> propose for value-based methods in the episodic setting. However, this solution is infeasible for the continuing setting <cit.>. 
One may also use differential value function <cit.> to replace the discounted value function in J_μ. 
Off-policy policy gradient with differential value function, however, is still an open problem and we are not aware of existing literature on this.

In this paper, we propose to optimize J_γ̂ instead.
It is a well-known fact that the policy gradient of the stationary distribution exists under mild conditions (e.g., see <cit.>).[
  For completeness, we include that proof in supplementary materials. 
] 
It follows immediately from the proof of this existence that lim_γ̂→ 1d_γ̂ = d_π. 
Moreover, it is trivial to see that lim_γ̂→ 0d_γ̂ = d_μ, indicating the counterfactual objective can recover both the excursion objective and the alternative life objective smoothly.
Furthermore, we show empirically that a small γ̂ (e.g., 0.6 in the two-circle MDP and 0.2 in Mujoco tasks) is enough to generate a different solution from maximizing J_μ. 



§ GENERALIZED OFF-POLICY POLICY GRADIENT
 

In this section, we derive an estimator for ∇ J_γ̂ and show in Proposition <ref> that it is unbiased in the limiting sense.
Our (standard) assumptions are given in supplementary materials. The OPPG theorem <cit.> leaves us the freedom to choose the interest function i in J_μ. In this paper, we set i(s) ≐î(s)c(s), which, to our best knowledge, is the first time that a non-trivial interest is used. Hence, i depends on π and we cannot invoke OPPG directly as ∇ J_μ≠∑_d d_μ(s)i(s)∇ v_π(s). However, we can still invoke the remaining parts of OPPG:

    ∑_s d_μ(s) i(s) ∇ v_π(s) = ∑_s m(s) ∑_a q_π(s, a)∇π(a | s),

where m^T≐i^TD_μ(I - P_π, γ)^-1, P_π, γ[s, s^'] ≐∑_aπ(a | s)p(s^'|s, a)γ(s, a, s^'). We now compute the gradient ∇ J_γ̂. 



where 

Proof. We first use the product rule of calculus and plug in d_γ̂(s) = d_μ(s) c(s):

    ∇ J_γ̂   = ∑_s d_γ̂(s)î(s)∇ v_π(s) + ∑_s ∇ d_γ̂(s)î(s)v_π(s) 
        = ∑_s d_μ(s) c(s) î(s)∇ v_π(s)_3 + ∑_s d_μ(s) ∇ c(s)î(s)v_π(s)._4

1 = 3 follows directly from (<ref>). To show 2 = 4, we take gradients on both sides of (<ref>). We have ∇c = γ̂D_μ^-1P_π^TD_μ∇c + γ̂D_μ^-1∇P_π^TD_μc. Solving this linear system of ∇c leads to

    ∇c   = (I - γ̂D_μ^-1P_π^TD_μ)^-1γ̂D_μ^-1∇P_π^TD_μc = (D_μ^-1(I - γ̂P_π^T)D_μ)^-1γ̂D_μ^-1∇P_π^TD_μc
       = (D_μ^-1(I - γ̂P_π^T)^-1D_μ) γ̂D_μ^-1∇P_π^TD_μc =  g.

With ∇ c(s) = g(s), 2 = 4 follows easily. 

Now we use an emphatic approach to provide an unbiased sample of ∇ J_γ̂. We define

    I_t    ≐ c(S_t-1)ρ_t-1∇logπ(A_t-1 | S_t-1),   F_t^(2)≐ I_t + γ̂ρ_t-1 F_t-1^(2),    M_t^(2)≐ (1 - λ_2)I_t + λ_2 F_t^(2).

Here I_t functions as an intrinsic interest (in contrast to the user-defined extrinsic interest î) and is a sample for b. F_t^(2) accumulates previous interests and translates b into g. λ_2 is for bias-variance trade-off similar to <cit.>. We now define 

    Z_t^(2)≐γ̂î(S_t) v_π(S_t)M_t^(2),    Z_t ≐ Z_t^(1) + Z_t^(2)

and proceed to show that Z_t is an unbiased sample of ∇ J_γ̂ when t →∞.


Assuming the chain induced by μ is ergodic and π is fixed,
the limit f(s) ≐ d_μ(s) lim_t→∞𝔼_μ[F_t^(2) | S_t=s] exists, and  for γ̂ < 1.

Proof. Previous works <cit.> assume lim_t→∞𝔼_μ [F_t^(1)|S_t=s] exists. 
Here we prove the existence of lim_t→∞𝔼_μ [F_t^(2)|S_t=s], inspired by the process of computing the value of lim_t→∞𝔼_μ [F_t^(1)|S_t=s] (assuming its existence) in <cit.>.
The existence of lim_t→∞𝔼_μ [F_t^(1)|S_t=s] with transition-dependent γ can also be established with the same routine.[This existence does not follow directly from the convergence analysis of ETD in <cit.>.]
The proof also involves similar techniques as <cit.>.
Details in supplementary materials. 



Assuming the chain induced by μ is ergodic, π is fixed, λ_1 = λ_2 = 1, γ̂ < 1, i(s) ≐î(s) c(s), then lim_t→∞𝔼_μ [Z_t]= ∇ J_γ̂

Proof. The proof involves Proposition 1 in <cit.> and Lemma <ref>. Details are provided in supplementary materials. 













When γ̂ = 0, the Generalized Off-Policy Policy Gradient (GOPPG) Theorem recovers the OPPG theorem in <cit.>.
The main contribution of GOPPG lies in the computation of ∇c, 
i.e., the policy gradient of a distribution,
which has not been done by previous policy gradient methods.
The main contribution of Proposition <ref> is the trace F_t^(2), which is an effective way to approximate ∇c.
Inspired by Propostion <ref>, we propose to update θ as θ_t+1 = θ_t + α Z_t, where α is a step size.

So far, we discussed the policy gradient for a single dimension of the policy parameter θ, so F_t^(1), M_t^(1), F_t^(2), M_t^(2) are all scalars. When we compute policy gradients for the whole θ in parallel, F_t^(1), M_t^(1) remain scalars while F_t^(2), M_t^(2) become vectors of the same size as θ. This is because our intrinsic interest “function” I_t is a multi-dimensional random variable, instead of a deterministic scalar function like î. We, therefore, generalize the concept of interest.

So far, we also assumed access to the true density ratio c and the true value function v_π. We can plug in their estimates C and V, yielding the Generalized Off-Policy Actor-Critic (Geoff-PAC) algorithm.[At this moment, a convergence analysis of Geoff-PAC is an open problem.] The density ratio estimate C can be learned via the learning rule in (<ref>). The value estimate V can be learned by any off-policy prediction algorithm, e.g., one-step off-policy TD <cit.>, Gradient TD methods, (Discounted) COP-TD or V-trace <cit.>. Pseudocode of Geoff-PAC is provided in supplementary materials. 

We now discuss two potential practical issues with Geoff-PAC. First, Proposition <ref> requires t →∞. In practice, this means μ has been executed for a long time and can be satisfied by a warm-up before training. Second, Proposition <ref> provides an unbiased sample for a fixed policy π. Once π is updated, F_t^(1), F_t^(2) will be invalidated as well as C, V. As their update rule does not have a learning rate, we cannot simply use a larger learning rate for F_t^(1), F_t^(2) as we would do for C, V. This issue also appeared in <cit.>. In principle, we could store previous transitions in a replay buffer <cit.> and replay them for a certain number of steps after π is updated. In this way, we can satisfy the requirement t→∞ and get the up-to-date F_t^(1), F_t^(2). In practice, we found this unnecessary. When we use a small learning rate for π, we assume π changes slowly and ignore this invalidation effect.



§ EXPERIMENTAL RESULTS

Our experiments  aim to answer the following questions. 1) Can Geoff-PAC find the same solution as on-policy policy gradient algorithms in the two-circle MDP as promised? 2) How does the degree of counterfactualness (γ̂) influence the solution? 3) Can Geoff-PAC scale up to challenging tasks like robot simulation in Mujoco with neural network function approximators? 4) Can the counterfactual objective in Geoff-PAC translate into performance improvement over Off-PAC and ACE? 5) How does Geoff-PAC compare with other downstream applications of OPPG, e.g., DDPG <cit.> and TD3 <cit.>?



 §.§ Two-circle MDP


We implemented a tabular version of ACE and Geoff-PAC for the two-circle MDP. The behavior policy μ was random, and we monitored the probability from  to  under the target policy π. In Figure <ref>, we plot π(→) during training. The curves are averaged over 10 runs and the shaded regions indicate standard errors. We set λ_1 = λ_2 = 1 so that both ACE and Geoff-PAC are unbiased. For Geoff-PAC, γ̂ was set to 0.9. ACE converges to the correct policy that maximizes J_μ as expected, while Geoff-PAC converges to the policy that maximizes J_π, the policy  we want in on-policy training. Figure <ref> shows how manipulating γ̂ and λ_2  influences the final solution. In this two-circle MDP, λ_2 has little influence on the final solution, while manipulating γ̂ significantly changes the final solution. 



 §.§ Robot Simulation




Evaluation: We benchmarked Off-PAC, ACE, DDPG, TD3, and Geoff-PAC on five Mujoco robot simulation tasks from OpenAI gym <cit.>. As all the original tasks are episodic, we adopted similar techniques as <cit.> to compose continuing tasks. We set the discount function γ to 0.99 for all non-termination transitions and to 0 for all termination transitions. The agent was teleported back to the initial states upon termination. The interest function was always 1. This setting complies with the common training scheme for Mujoco tasks <cit.>. However, we interpret the tasks as continuing tasks. As a consequence, J_π, instead of episodic return, is the proper metric to measure the performance of a policy π. The behavior policy μ is a fixed uniformly random policy, same as <cit.>. The data generated by μ is significantly different from any meaningful policy in those tasks. Thus, this setting exhibits a high degree of off-policyness. We monitored J_π periodically during training. To evaluate J_π, states were sampled according to π, and v_π was approximated via Monte Carlo return. Evaluation based on the commonly used total undiscounted episodic return criterion is provided in supplementary materials. The relative performance under the two criterion is almost identical.

Implementation: Although emphatic algorithms have enjoyed great theoretical success <cit.>, their empirical success is still limited to simple domains (e.g., simple hand-crafted Markov chains, cart-pole balancing) with linear function approximation. To our best knowledge, this is the first time that emphatic algorithms are evaluated in challenging robot simulation tasks with neural network function approximators. To stabilize training, we adopted the A2C <cit.> paradigm with multiple workers and utilized a target network <cit.> and a replay buffer <cit.>. All three algorithms share the same architecture and the same parameterization. We first tuned hyperparameters for Off-PAC. ACE and Geoff-PAC inherited common hyperparameters from Off-PAC. For DDPG and TD3, we used the same architecture and hyperparameters as <cit.> and <cit.> respectively. 
More details are provided in supplementary materials and all the implementations are publicly available [<https://github.com/ShangtongZhang/DeepRL>].

Results: We first studied the influence of λ_1 on ACE and the influence of λ_1, λ_2, γ̂ on Geoff-PAC in HalfCheetah. The results are reported in supplementary materials. We found ACE was not sensitive to λ_1 and set λ_1 = 0 for all experiments. For Geoff-PAC, we found λ_1 = 0.7, λ_2 = 0.6, γ̂=0.2 produced good empirical results and used this combination for all remaining tasks. All curves are averaged over 10 independent runs and shaded regions indicate standard errors. 
Figure <ref> compares Geoff-PAC, ACE, and Off-PAC. Geoff-PAC significantly outperforms ACE and Off-PAC in 3 out of 5 tasks. The performance on Walker and Reacher is similar. This performance improvement supports our claim that optimizing J_γ̂ can better approximate J_π than optimizing J_μ. We also report the performance of a random agent for reference. Moreover, this is the first time that ACE is evaluated on such challenging domains instead of simple Markov chains. 
Figure <ref> compares Geoff-PAC, DDPG, and TD3. Geoff-PAC outperforms DDPG in Hopper and Swimmer. DDPG with a uniformly random policy exhibits high instability in HalfCheetah, Walker, and Hopper. This is expected because DDPG ignores the discrepancy between d_μ and d_π. As training progresses, this discrepancy gets larger and finally yields a performance drop. 
TD3 uses several techniques to stabilize DDPG, which translate into the performance and stability improvement over DDPG in Figure <ref>.
However, Geoff-PAC still outperforms TD3 in Hopper and Swimmer.
This is not a fair comparison in that many design choices for DDPG, TD3 and Geoff-PAC are different (e.g., one worker vs. multiple workers, deterministic vs. stochastic policy, network architectures), and we do not expect Geoff-PAC to outperform all applications of OPPG. However, this comparison does suggest GOPPG sheds light on how to improve applications of OPPG. 



§ RELATED WORK

The density ratio c is a key component in Geoff-PAC, 
which is proposed by <cit.>. 
However, how we use this density ratio is different.
Q-Learning <cit.> is a semi-gradient method.
<cit.> use the density ratio to reweigh the Q-Learning semi-gradient update directly.
The resulting algorithm still belongs to semi-gradient methods. 
If we would use the density ratio to reweigh the Off-PAC update (<ref>) directly, 
it would just be an actor-critic analogue of the Q-Learning approach in <cit.>.
This reweighed Off-PAC, however, will no longer follow the policy gradient of the objective J_μ, yielding instead “policy semi-gradient”.
In this paper, we use the density ratio to define a new objective, the counterfactual objective, and compute the policy gradient of this new objective directly (Theorem <ref>).
The resulting algorithm, Geoff-PAC, still belongs to policy gradient methods (in the limiting sense).
Computing the policy gradient of the counterfactual objective requires computing the policy gradient of the density ratio, which has not been explored in <cit.>.  

There have been many applications of OPPG, e.g., DPG <cit.>, DDPG, ACER <cit.>, EPG <cit.>, and IMPALA <cit.>. Particularly, <cit.> propose IPG to unify on- and off-policy policy gradients. IPG is a mix of gradients (i.e., a mix of ∇ J_μ and ∇ J_π). To compute ∇ J_π, IPG does need on-policy samples. In this paper, the counterfactual objective is a mix of objectives, and we do not need on-policy samples to compute the policy gradient of the counterfactual objective. Mixing ∇ J_γ̂ and ∇ J_π directly in IPG-style is a possibility for future work. 

There have been other policy-based off-policy algorithms. <cit.> provide an unbiased estimator (in the limiting sense) for ∇ J_μ, assuming the value function is linear. Theoretical results are provided without empirical study. <cit.> eliminate this linear assumption and provide a thorough empirical study. We, therefore, conduct our comparison with <cit.> instead of <cit.>. In another line of work, the policy entropy is used for reward shaping. The target policy can then be derived from the value function directly <cit.>. This line of work includes the deep energy-based RL <cit.>, where a value function is learned off-policy and the policy is derived from the value function directly, and path consistency learning <cit.>, where gradients are computed to satisfy certain path consistencies. This line of work is orthogonal to this paper, where we compute the policy gradients of the counterfactual objective directly in an off-policy manner and do not involve reward shaping. 

<cit.> prove that c̅ is the unique solution for a minimax problem, 
which involves maximization over a function set ℱ.
They show that theoretically ℱ should be sufficiently rich (e.g., neural networks).
To make it tractable, they restrict ℱ to a ball of a reproducing kernel Hilbert space,
yielding a closed form solution for the maximization step. 
SGD is then used to learn an estimate for c̅ in the minimization step, 
which is then used for policy evaluation.
In a concurrent work <cit.>, this approximate for c̅ is used in off-policy policy gradient for J_π, and 
empirical success is observed in simple domains.
By contrast, our J_γ̂ unifies J_π and J_μ, where γ̂ naturally allows bias-variance trade-off, 
yielding an empirical success in challenging robot simulation tasks.



§ CONCLUSIONS


In this paper, we introduced the counterfactual objective unifying the excursion objective and the alternative life objective in the continuing RL setting. We further provided the Generalized Off-Policy Policy Gradient Theorem and corresponding Geoff-PAC algorithm. GOPPG is the first example that a non-trivial interest function is used, and Geoff-PAC is the first empirical success of emphatic algorithms in prevailing deep RL benchmarks. 
There have been numerous applications of OPPG including DDPG, ACER, IPG, EPG and IMPALA. We expect GOPPG to shed light on improving those applications. Theoretically, a convergent analysis of Geoff-PAC involving compatible function assumption <cit.> or multi-timescale stochastic approximation <cit.> is also worth further investigation.



  §.§.§ Acknowledgments

SZ is generously funded by the Engineering and Physical Sciences Research Council (EPSRC). This project has received funding from the European Research Council under the European Union's Horizon 2020 research and innovation programme (grant agreement number 637713). The experiments were made possible by a generous equipment grant from NVIDIA. The authors thank Richard S. Sutton, Matthew Fellows, Huizhen Yu for the valuable discussion.




apa





§ ASSUMPTIONS AND PROOFS



 §.§ Assumptions

We use the same standard assumptions as <cit.> and <cit.>. 




 §.§ Proof of the Existence of ∇d_γ̂

Proof. (From <cit.>)
From the proof of Theorem 1.1 (f) in <cit.>,
each row of Adj(I - P_γ̂) is a left eigenvector of P_γ̂ corresponding to the eigenvalue 1,
where Adj(·) is the adjugate matrix.
Normalizing the row of Adj(I - P_γ̂) then yields the stationary distribution d_γ̂.
As each element of Adj(I - P_γ̂) is a polynomial of elements in P_γ̂,
∇d_γ̂ exists whenever ∇π exists.
It follows easily that lim_γ̂→ 1d_γ̂ = d_π.
 




















 §.§ Proof of Lemma <ref>

Proof. 
To get F_t^(2), we start from F_-1^(2) and follow μ for t steps. 
The expectation is taken w.r.t. to this process of following μ for t steps.
We use p(s|s̅, k) to denote the probability of transitioning to a state s from a state s̅ in k steps under the target policy π. 
We define shorthands:

    p_t(s̅, a̅, s)    ≐_μ(S_t-1 = s̅, A_t-1 = a̅ | S_t = s), 
    
    f_t(s)    ≐𝔼_μ [F_t^(2) | S_t = s], 
    
    i_t(s)    ≐𝔼_μ [I_t | S_t = s].
 
When t →∞, the agent goes to the stationary distribution d_μ, so 

    lim_t →∞ p_t(s̅, a̅, s) 
    
    =   lim_t →∞_μ(S_t-1=s̅, A_t-1=a̅, S_t=s)/d_μ(s)   (Bayes' rule) 
    
    =    d_μ(s)^-1 d_μ(s̅) μ(a̅ | s̅) p(s | s̅, a̅).

Consequently,

    d_μ(s) ρ(s̅, a̅) lim_t →∞ p_t(s̅, a̅, s) = d_μ(s̅)π(a̅ | s̅) p(s|s̅, a̅).

We first compute the limit of the intrinsic interest I_t: 

    lim_t →∞ i_t(s) 
    
    =   lim_t →∞∑_s̅, a̅_μ(S_t-1=s̅, A_t-1=a̅|S_t = s) 𝔼_μ[I_t | S_t-1=s̅, A_t-1 = a̅] 
     (Law of total expectation and Markov property)
    =    d_μ(s)^-1∑_s̅, a̅ d_μ(s̅) μ(a̅ | s̅) p(s|s̅, a̅)c(s̅)ρ(s̅, a̅)∇logπ (a̅ | s̅)   (Eq. <ref> and definition of I_t)
    
    =    d_μ(s)^-1∑_s̅, a̅ d_μ(s̅) π(a̅ | s̅) p(s|s̅, a̅) c(s̅) ∇logπ(a̅ | s̅) 
    
    =    d_μ(s)^-1∑_s̅ d_μ(s̅) c(s̅) ∑_a̅∇π(a̅ | s̅) p(s|s̅, a̅) 
    
    =    d_μ(s)^-1 b(s)   (Definition of b)

We then expend f_t recursively:

    f_t(s_k) 
    
    =   𝔼_μ[I_t + γ̂ρ_t-1 F_t-1^(2) | S_t = s_k] 
    
    =    i_t(s_k) + γ̂𝔼_μ[ρ_t-1 F_t-1^(2) | S_t = s_k] 
    
    =    i_t(s_k)  + γ̂∑_s_k-1, a_k-1 p_t(s_k-1, a_k-1, s_k) 𝔼_μ [ρ_t-1 F_t-1^(2) | S_t-1 = s_k-1, A_t-1 = a_k-1] 
    
    =    i_t(s_k) + γ̂∑_s_k-1, a_k-1 p_t(s_k-1, a_k-1, s_k) ρ(s_k-1, a_k-1) f_t-1(s_k-1)] 
    
    =    i_t(s_k)  + γ̂∑_s_k-1, a_k-1 p_t(s_k-1, a_k-1, s_k) ρ(s_k-1, a_k-1) i_t-1(s_k-1)]  
       +γ̂^2 ∑_s_k-1, a_k-1 p_t(s_k-1, a_k-1, s_k) ρ(s_k-1, a_k-1) ∑_s_k-2, a_k-2 p_t-1(s_k-2, a_k-2, s_k-1) ρ(s_k-2, a_k-2) f_t-2(s_k-2)
    
    =    i_t(s_k) + γ̂∑_s_k-1, a_k-1 p_t(s_k-1, a_k-1, s_k) ρ(s_k-1, a_k-1) i_t-1(s_k-1)  
       +γ̂^2 ∑_s_k-1, a_k-1 p_t(s_k-1, a_k-1, s_k) ρ(s_k-1, a_k-1) ∑_s_k-2, a_k-2 p_t-1(s_k-2, a_k-2, s_k-1) ρ(s_k-2, a_k-2) i_t-2(s_k-2)] 
       + …
       +γ̂^t ∑_s_k-1, a_k-1 p_t(s_k-1, a_k-1, s_k) ρ(s_k-1, a_k-1) …∑_s_k-t, a_k-t p_1(s_k-t, a_k-t, s_k-t+1) ρ(s_k-t, a_k-t) f_0(s_k-t)

This means we can expand f_t(s_k) into t+1 terms.
For each term, we multiply it by d_μ(s_k) and compute the limit of the product as:

    lim_t →∞  d_μ(s_k) ∑_s_k-1, a_k-1 p_t(s_k-1, a_k-1, s_k) ρ(s_k-1, a_k-1) i_t-1(s_k-1) 
    
    =   ∑_s_k-1, a_k-1 d_μ(s_k) ρ(s_k-1, a_k-1) lim_t →∞ p_t(s_k-1, a_k-1, s_k)  lim_t →∞ i_t-1(s_k-1) 
    
    =   ∑_s_k-1, a_k-1 d_μ(s_k-1) π(a_k-1 | s_k-1) p(s_k | s_k-1, a_k-1) d_μ(s_k-1)^-1 b(s_k-1)   (Eq. <ref> and Eq. <ref>)
    
    =   ∑_s_k-1 b(s_k-1) p(s_k | s_k-1, 1)


    lim_t →∞ d_μ(s_k) ∑_s_k-1, a_k-1 p_t(s_k-1, a_k-1, s_k) ρ(s_k-1, a_k-1) ∑_s_k-2, a_k-2 p_t-1(s_k-2, a_k-2, s_k-1) ρ(s_k-2, a_k-2) i_t-2(s_k-2)
    
    =   ∑_s_k-1, a_k-1 d_μ(s_k) ρ(s_k-1, a_k-1) lim_t →∞ p_t(s_k-1, a_k-1, s_k)  lim_t →∞∑_s_k-2, a_k-2 p_t-1(s_k-2, a_k-2, s_k-1) ρ(s_k-2, a_k-2) i_t-2(s_k-2) 
    
    =   ∑_s_k-1, a_k-1 d_μ(s_k-1) π(a_k-1 | s_k-1) p(s_k | s_k-1, a_k-1) lim_t →∞∑_s_k-2, a_k-2 p_t-1(s_k-2, a_k-2, s_k-1) ρ(s_k-2, a_k-2) i_t-2(s_k-2)
    
    =   ∑_s_k-1, a_k-1π(a_k-1 | s_k-1) p(s_k | s_k-1, a_k-1) ∑_s_k-2 b(s_k-2)  p(s_k-1 | s_k-2, 1)   (Eq. <ref>)
    
    =   ∑_s_k-2 b(s_k-2) p(s_k | s_k-2, 2)

Putting all the limits together, we have

    f(s_k) 
    
    =   d_μ(s_k) lim_t →∞ f_t(s_k) 
    
    =    b(s_k)  
       + γ̂∑_s_k-1 b(s_k-1)p(s_k | s_k-1, 1) 
       + γ̂^2 ∑_s_k-2 b(s_k-2)p(s_k | s_k-2, 2) 
       + …

In a matrix form, we have

    f   = b + γ̂P^_πb + (γ̂P^_π)^2 b + …

It follows easily that f = (I - γ̂P_π^T)^-1b  



































 §.§ Proof of Proposition <ref>

Proof. From Proposition 1 in <cit.> [It can be easily verified that the dependence of i on π does not influence this proposition.], we have

    lim_t→∞𝔼_μ[ρ_t M_t^(1) q_π(S_t, A_t) ∇logπ(A_t | S_t)] = 1.
 
With D_î≐ diag(î), we have,

    lim_t →∞𝔼_μ[γ̂ v_π(S_t) î(S_t) M_t^(2)]    =γ̂lim_t →∞𝔼_μ[ 𝔼_μ[v_π(S_t) î(S_t) F_t^(2) | S_t=s] ]   (law of total expectation) 
       = γ̂lim_t→∞∑_s d_μ(s) 𝔼_μ[v_π(S_t) î(S_t) F_t^(2) | S_t=s] 
        =γ̂∑_s d_μ(s) î(s) v_π(s) lim_t →∞𝔼_μ[F_t^(2) | S_t=s]   (conditional independence)
        =γ̂∑_s v_π(s) î(s) f(s) 
        = γ̂v_π^TD_îf
        = γ̂v_π^TD_îD_μD_μ^-1(I - γ̂P_π^T)^-1b  (Lemma <ref>)
         = v_π^TD_îD_μg
        = ∑_s d_μ(s) î(s) v_π(s) g(s) = 2.

As ∇ J_γ̂ = 1 + 2, we have proved lim_t→∞𝔼_μ [Z_t]= ∇ J_γ̂. 
















§ DETAILS OF EXPERIMENTS




 §.§ Pseudocode of Geoff-PAC



Algorithm <ref> provides the pseudocode of Geoff-PAC.  refers to the soft normalization loss for θ_c in <cit.>. β is the weight for the .



 §.§ Implementation Details


Task Selection: We use 5 Mujoco tasks from Open AI gym [<https://gym.openai.com/>]<cit.>.
Those 5 tasks are of a medium difficulty level.
The easy tasks (e.g., the pendulum tasks) and the hard tasks (e.g., the ant task and the humanoid tasks) are excluded.

Function Parameterization: For Off-PAC, ACE, and Geoff-PAC, 
we use separate two-hidden-layer networks to parameterize C, V and π. Each hidden layer has 64 hidden units and a ReLU <cit.> activation function.
Particularly, we parameterized π as a diagonal Gaussian distribution with the mean being the output of the network. 
The standard derivation is a global state-independent variable. 
This is a common policy parameterization for continuous-action problems <cit.>.
For DDPG and TD3, we use the same parameterization as <cit.> and <cit.> respectively.

Hyperparameter Tuning: Our implementation is based on the A2C <cit.> architecture.
We first tune hyperparameters for Off-PAC based on the A2C implementation from <cit.> and previous experiences.
Our ACE and Geoff-PAC implementations inherited common hyperparameters from the Off-PAC implementation without further fine-tuning.
Previously, Off-PAC and ACE were evaluated on only simple domains with linear function approximation. 
To our best knowledge, we are the first to demonstrate an empirical success for them in challenging robot simulation tasks. 

Hyperparameters of Off-PAC: 

Number of workers: 10 

Optimizer: RMSProp with an initial learning rate 10^-3 

Gradient clip by norm: 0.5 

Replay buffer size: 10^6 

Batch size of the replay buffer: 10 

Warm-up steps before learning: 100 environment steps

Target network update frequency: 200 optimization steps

Importance sampling ratio clip: [0, 2]

Additional Hyperparameters of ACE: 

λ_1: 0, tuned over {0, 0.1, 0.2, …, 0.9, 1} on HalfCheetah with a grid search

Additional Hyperparameters of Geoff-PAC: 

Density ratio (C) clip: [0, 2] 

 weight (β): 10^-3, suggested by <cit.> 

λ_1: 0.7, tuned over {0, 0.1, 0.2, …, 0.9, 1} on HalfCheetah 

λ_2: 0.6, tuned over {0, 0.1, 0.2, …, 0.9, 1} on HalfCheetah 

γ̂: 0.2, tuned over {0, 0.1, 0.2, …, 0.9} on HalfCheetah 

We first select a reasonable γ̂ based on some preliminary experiments. 
Then λ_1 and λ_2 are tuned with a grid search. 

Hyperparameters of DDPG: 

We implemented DDPG ourself. 
With the normal behavior policy, our implementation matched the reported performance in the literature, e.g., in <cit.>.
We use the same hyperparameters as <cit.>.
We do not use batch normalization.

Hyperparameters of TD3: 

We implemented TD3 ourself. 
With the normal behavior policy, our implementation matched the reported performance in <cit.>.
With a uniformly random behavior policy, our implementation outperformed the implementation from <cit.> by a large margin, 
we therefore use our implementation for comparison.
We use the same hyperparameters as <cit.>.

Computing Infrastructure: 

We conducted our experiments on an Nvidia DGX-1 with PyTorch.



 §.§ Other Experimental Results




We include a comparison under the total undiscounted episodic return criterion for reference. The results are reported in Figure <ref> and Figure <ref>. All curves are averaged over 10 independent runs, and standard errors are reported as the shadow.





We studied the influence of (λ_1, λ_2, γ̂) on ACE and Geoff-PAC in HalfCheetah. Results are reported in Figure <ref>. Five random seeds were used. 



