Dr Jekyll and Mr Hyde: The Strange Case of Off-Policy Policy Updates

Abstract:
The policy gradient theorem states that the policy should only be updated in states that are visited by the current policy, which leads to insufficient planning in the off-policy states, and thus to convergence to suboptimal policies. We tackle this planning issue by extending the policy gradient theory to policy updates with respect to any state density. Under these generalized policy updates, we show convergence to optimality under a necessary and sufficient condition on the updates’ state densities, and thereby solve the aforementioned planning issue. We also prove asymptotic convergence rates that significantly improve those in the policy gradient literature. To implement the principles prescribed by our theory, we propose an agent, Dr Jekyll & Mr Hyde (J&H), with a double personality: Dr Jekyll purely exploits while Mr Hyde purely explores. J&H’s independent policies allow to record two separate replay buffers: one on-policy (Dr Jekyll’s) and one off-policy (Mr Hyde’s), and therefore to update J&H’s models with a mixture of on-policy and off-policy updates. More than an algorithm, J&H defines principles for actor-critic algorithms to satisfy the requirements we identify in our analysis. We extensively test on finite MDPs where J&H demonstrates a superior ability to recover from converging to a suboptimal policy without impairing its speed of convergence. We also implement a deep version of the algorithm and test it on a simple problem where it shows promising results.

heading: 1 Introduction
text: Policy Gradient algorithms in Reinforcement Learning (RL) have enjoyed great success both theoretically [50, 43, 16, 36] and empirically [23, 38, 37, 27]. Their principle consists in optimizing an objective function J (the expected discounted return) through gradient steps, both being formally specified below [43]:
J (π) .= E [ ∞∑ t=0 γtRt ∣∣∣∣S0 ∼ p0, At ∼ π(·|St), St+1 ∼ p(·|St, At), Rt ∼ r(·|St, At) ]
(1)
∇θJ (π) = ∑ s∈S dπ,γ(s) ∑ a∈A qπ(s, a)∇θπ(a|s) and θt+1 ←−−−−proj θt + ηt∇θtJ (πt), (2)
using standard Markov Decision Process notations (recalled in App. A), where ηt is the learning rate and dπ,γ(s) . = ∑∞ t=0 γ
tP(St = s|π) the discounted state density, the policies π .= πθ and πt . = πθt are implicitly parametrized by θ for conciseness, and←−−−−proj denotes the projection onto
the parameter space. We observe that the update established by the policy gradient theorem is proportional to the state density of the current policy. This is problematic, as it implies that no value improvement can be induced in off-policy states (i.e. states that are rarely visited). As a consequence, ∗Equal contribution. Correspondence to: rolaroch@microsoft.com. All code available at http://aka.ms/jnh.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
planning is inefficient in those states to the point of potentially compromising convergence to the optimal policy.
To address the planning issue in off-policy states, we generalize the policy gradient theory by considering the more general policy update:
U(θ, d) . = ∑ s∈S d(s) ∑ a∈A qπ(s, a)∇θπ(a|s) and θt+1 ←−−−−proj θt + ηtU(θt, dt), (3)
where dt designates the state distribution on which the policy is updated. It does not have to match the distribution induced by π and updates may therefore be off-policy. We note that U(θ, d) is not a gradient in the general case, hence the use of the term update. We prove in the direct: πθ . = θ and softmax: πθ ∼̇ exp(θ) parametrizations that following the exact policy updates induces a sequence of value functions qt . = qπt that is monotonously increasing, upper bounded, and thereby converges
to a q∞. We then show that the condition “∀s ∈ S, ∑ t ηtdt(s) =∞” on the sequence (dt) is necessary and sufficient for q∞ to be optimal. Our result generalizes previous theorems to broader updates and milder assumptions [2, 22]. Finally, we significantly improve the existing asymptotic convergence rates. We show that (qt) converges to the optimal value i) exactly in finite time for the direct parametrization (previously in O ( t−1/2|S||A|(1− γ)−6 ) [2]), and ii) in O ( t−1|S||A|(1− γ)−2
) for the softmax parametrization, to be compared with O ( t−1|S|2|A|2(1− γ)−6 ) [22].
Building on our theoretical results, we design a novel algorithm: Dr Jekyll and Mr Hyde (J&H). Its principle consists in training two independent policies: a pure exploitation one (Dr Jekyll) and a pure exploration one (Mr Hyde), and give control to either one for full trajectories. J&H’s independent policies allow to record two separate replay buffers: one on-policy (Dr Jekyll’s) and one off-policy (Mr Hyde’s), and therefore to update J&H’s models with any desired mixture of on-policy and off-policy updates. Beyond an algorithm, J&H introduces conditions based on our analysis that actor-critic algorithms should follow to properly plan off-policy. Furthermore, the separation of exploration and exploitation allows to stabilise the training of the exploitation policy while ensuring a full coverage of the state-action space through deep exploration [30].
We empirically validate our theoretical analysis and algorithmic innovation in both planning and RL settings. In the planning setting where we assume that qt is exactly known, we analyze the impact of the off-policiness of dt and conclude that, while it improves over classic policy gradient, the theoretical sufficient condition does not allow to converge in a reasonable amount of time in very hard planning tasks: we thereby recommend to enforce the stronger condition “∀s ∈ S, ∑t ηtdt(s) ∈ Ω(t)”. In the reinforcement learning domain, where qt must be estimated from the collected transitions, the off-policiness of J&H’s policy updates allows by design to satisfy the recommendation as long as Mr Hyde is able to cover the whole state space. This leads J&H to significantly outperform all competing actor-critic algorithms in the hard planning tasks and to be competitive with gradient updates in simple planning problems. As a proof of concept, we also test J&H in a deep reinforcement learning setting and show that it outperforms various baselines on a simple environment.
The paper is organized as follows. Section 2 develops the policy update theory. Section 3 describes J&H and positions it with respect to the literature. Section 4 presents the experiments and their results. Finally, Section 5 concludes the paper. The interested reader may refer to the appendix for the proofs (App. B), the domains (App. C), and the full experiment reports (App. D, E, and F). Finally, the supplementary material contains the code for the experiments: algorithms and environments.

heading: 2 Theoretical analysis
text: First, we recall some background: policy gradient methods depend on a parametrization θ ∈ R|S|×|A| of the policy. Like [2, 22], we will focus on the classic direct and softmax parametrizations:
• direct: π(a|s) .= θs,a, for which us,a = dt(s)qπ(s, a) and the projection is on the simplex.
• softmax: π(a|s) .= exp(θs,a)∑ a′ exp(θs,a′) , for which us,a = dt(s)π(a|s)(qπ(s, a)− vπ(s)).
For both parametrizations, [2] proves that following the policy gradient∇θJ (π) from Eq. (2) eventually leads to the optimal policy in finite MDPs under the following assumptions and condition2:
A1. The model (p0, p, r) is known. A2. The initial state-distribution covers the full state space: ∀s ∈ S, p0(s) > 0. C3. The learning rate is constant: ηt = (1−γ)3 2γ|A| (direct) and ηt = (1−γ)3 8 (softmax).
Those are stringent requirements. A1 implies that the values qπ and state density dπ,γ of the policy are known exactly. A2 is generally not satisfied in standard RL domains. Finally, verifying C3 makes learning slow to the point that it becomes impractical.

heading: 2.1 Convergence properties
text: In this section, we study, under A1, the convergence properties of the sequence of value functions (qt) induced by the update rule defined in Eq. (3). We note that U(θ, d) is not a gradient in general. Our first theoretical result is the monotonicity of the value function sequence (qt). Theorem 1 (Monotonicity under the direct and softmax parametrization). Under A1, the sequence of value functions qt . = qπt and vt . = vπt are monotonously increasing.
By the monotonous convergence theorem, Thm. 1 directly implies the convergence of (qt): Corollary 1 (Convergence under the direct and softmax parametrization). Under A1, the sequence of value functions qt uniformly converges: q∞ . = limt→∞ qt.
In order to go further and prove convergence to a global optimal value, we need to enforce an additional condition. Indeed, the update U relies multiplicatively on dt which could be equal (or tend very fast) to 0 in some states, compromising the policy’s ability to reach the optimal value. This argument is not only theoretical, it has been observed by many that policy gradient can get stuck in suboptimal policies, even with entropy regularization. We designed our chain domain to exhibit such behaviour (see Section 4.1).
Next, we show that (qt) converges to the optimal value function under some necessary and sufficient condition. Theorem 2 (Optimality under the direct and softmax parametrization). Under A1, the following condition:
C4. Each state s is updated with weights that sum to infinity over time: ∑∞ t=0 ηtdt(s) =∞,
is necessary and sufficient to guarantee that the sequence of value functions (qt) converges to optimality: q∞ = q? . = maxπ∈Π qπ .
Proof sketch. In both direct and softmax parametrizations, we assume there exists a state-action pair (s, a) advantageous with respect to the state value limits q∞ and v∞ . = limt→∞ vt, that is: adv∞(s, a) . = q∞(s, a) − v∞(s) > 0. We then prove that in this state s, the policy improvement yielded by the update is lower bounded by a linear function of the update weight ηtdt(s). Both parametrizations require different proof techniques and are dealt with in different theorems. Summing over t, we notice that this lower bounding sum diverges to infinity, which contradicts Corollary 1. We therefore infer that there cannot exist such a state-action pair, which allows us to conclude that no policy improvement is possible, and thus that the values are optimal: q∞ = maxπ∈Π qπ .
For the necessity of C4, we show that the parameter update is upper bounded in both parametrizations by a term linear in the action gap. By choosing the reward function adversarially, we may set it sufficiently small so that the sum of all the gradient steps is insufficient to reach optimality.
Thm. 2 is impactful along five dimensions.
Practice of on-policy undiscounted updates:ti li i t t :r f - s sac ce c c e a eti li i t t :r f - As Thm. 2 is applicable to any distribution sequence, it allows us in particular to consider the practice of using on-policy undiscounted updates: dt . = dπt,1.
2An assumption A# is a requirement on the environment or the application setting, while a condition C# is a requirement that may be enforced by a dedicated algorithm in any environment or setting.
Thus, it resolves a longstanding gap between the policy gradient theory and the actor-critic algorithm implementations [12, 7, 51, 17, 1, 19, 41]. This mismatch and its lack of theoretical grounding were identified in [45]. Later, [26] proved that the practitioners’ undiscounted updates are not the gradient of any function and may be strongly biased under state aliasing. Recently, [53] studied the practical advantage of the undiscounted updates from a representation learning perspective. C4 encompasses both standard policy gradient and the undiscounted update rule: convergence to optimality of both is guaranteed as long as C4 is verified. Our analysis thus shows that the convergence properties of policy gradient and undiscounted updates require the same set of assumptions and conditions. Conversely, it is possible to prove convergence to sub-optimal policies of either when C4 is violated. In other words, Thm. 2 allows to reduce the study of specific algorithms to whether they verify C4.
Experience replay and off-policy updates:i l li t :r r ff- se e ce e a a c a ei l li t :r r ff- It also justifies the use of an experience replay for the actor, a trick also widely used in the literature to distributed the training over several agents [24, 34, 49, 14, 35]. Furthermore, while widely overlooked in the literature, we prove that off-policy updates have an even higher impact, since they are necessary to guarantee the convergence to optimality3. We leverage this discovery to introduce new design principles and a novel algorithm in Section 3.
Policy gradient theory:li i t t :r rc a e eli i t t :r r Next, Thm. 2 generalizes previous optimality convergence results along two axes. The initial state distribution p0 is not required to cover the state space anymore (aka A2). A2 is unrealistic in most applications and cannot be enforced by an algorithm. Relaxing it is an important open problem [2], we disprove it in the full class of MDP. However, it might be possible to find a class of MDPs larger than the one verifying A2 where policy gradient also converges. Additionally, the condition on our learning rates is also much more flexible than C3.
Density vs. policy regularization:it . li l i ti :s s r re c e a zait . li l i ti :r r In contrast, C4 can be controlled by a dedicated algorithm. This theoretical result promotes the principle of density-based regularization [21, 32], at the expense of policy-based regularization that cannot guarantee that C4 is satisfied and sometimes fails to plan over the whole state space (our chain domain experiments in Section 4 illustrate it well).
Towards a generalized policy iteration theorem:li li it ti t :r s r r ra a e e a ze c e a e eli li it ti t :r r r r Finally, by combining Thm. 2, which analyzes policy improvement, with a thorough theoretical analysis of the policy evaluation step (discussed in Section 3.1), we see a path towards results describing conditions on both components of generalized policy iteration that guarantee convergence to optimality [4]. Furthermore, Thm. 2 gives sufficient conditions on the policy improvement step. The generalized policy iteration theorem was conjectured in [42] but never proved.

heading: 2.2 Convergence rates
text: Next, we give convergence rates for both softmax and direct parametrizations:
Theorem 3 (Asymptotic convergence rates under the direct parametrization). With direct parametrization, under A1 and C4, the sequence of value functions qt converges to optimality in finite time:
∃t0, such that ∀t ≥ t0, qt = q?. (4)
C4 is required for optimality and convergence rate contrarily to the softmax parametrization. We significantly improve over previous bounds inO ( t−1/2|S||A|(1− γ)−6 ) [2]. We wish to emphasize that Theorem 3 does not say anything about how large t0 is, the rate is purely asymptotic.
Theorem 4 (Asymptotic convergence rates under the softmax parametrization). With softmax parametrization, under A1, C4, and A8:
A8. The optimal policy is unique: ∀s, q?(s, a1) = q?(s, a2) = v?(s) implies a1 = a2,
the sequence of value functions qt converges asymptotically as follows:
∃t0, such that ∀t ≥ t0, v?(s)− vt(s) ≤ 8|A|(v> − v⊥) (1− γ) mins∈supp(dπ?,γ) δ(s) ∑t−1 t′=t0 ηt′dt′(s) , (5)
3Other papers proving convergence to optimality of policy gradient rely on A2, which implies C4.
where δ(s) = v?(s) − maxa∈A/{π?(s)} q?(s, a) is the gap with the best suboptimal action in state s, v> (resp. v⊥) is the maximal (resp. minimal) value, and supp(dπ?,γ) denotes the support of the distribution of the optimal policy.
If (dt) satisfies the additional mild condition that the support of d? is covered on average: C5. ∀s ∈ supp(d?), limt→∞ 1t ∑t t′=0 ηt′dt′(s) . = e⊥(s) > 0,
then we obtain the following convergence rate in O(t−1):
∃t0, such that ∀t ≥ t0, v?(s)− vt(s) ≤ 8|A|(v> − v⊥)
(t− t0)(1− γ) mins∈supp(dπ?,γ) δ(s)e⊥(s) . (6)
C5 is implied by A2 and C3. Alternately, assuming ηt ≥ η⊥ > 0 ∀t, it is verified by a uniform distribution in which case e⊥(s) = η⊥|S| , or by an on-policy distribution dπt that converges to the distribution of some optimal policy dπ? in which case e⊥(s) = η⊥dπ?(s). Also, note that C4 is required for optimality, but not for convergence rates with respect to q∞. Thm. 4 establishes asymptotic rates in O ( t−1|S||A|(1− γ)−2 ) , to be compared with O ( t−1|S|2|A|2(1− γ)−6 ) [22]. The gap is partially explained by dropping C3 and allowing any learning rate (see App. A.6 for a thorough comparison). It is possible, see Thm. 7 of App. B, to show that under A2, a condition on the learning rate, and a bounding condition on dt (∃d> ≥ d⊥ > 0 such that ∀s, t, d> ≥ dt(s) ≥ d⊥), we have: t0 ≤ O ( |S|
(1−γ)7 d> d⊥ 1 mins δ(s)
) .

heading: 2.3 Related work
text: [11, 15, 52] study the off-policy, continuing setting paired with the average value objective. That objective is either expressed with a state visitation coming from the behavioral policy (the excursion objective) or from the trained policy (the alternative life objective). Its gradient can be computed exactly or approximated and used to optimize the objective. The weights assigned to each state during an update stem from the gradient computation (exactly as in the discounted return gradient we study). It is an interesting question, left for future work, to understand whether those weights have desirable properties from a convergence standpoint. In particular, it is possible that a condition akin to C4 exists in the continuing objective case.
From a proof technique perspective, [2] studies gradient ascent and, as a byproduct, can rely on standard optimization results: strong convexity and convergence of gradients to 0. We cannot do so as our updates are not gradients anymore. More precisely, Lemma C2 in [2] uses the strong convexity of the objective function to prove that following the gradient results in a value improvement (assuming a learning rate sufficiently small). We provide a more general (we do not need the condition on the learning rate) and, in our admittedly biased opinion, more elegant proof of that lemma in our Theorem 1. Second, their Lemma C5 uses (i) the convergence of the gradient to 0 (a standard result with gradient as-/des-cent), and (ii) the assumption that all states have a non-vanishing density to infer that, in the limit, the learnt policy does not assign any mass to states that have a non-zero advantage. Neither (i) nor (ii) hold in our setting, we had to leverage C4 instead.

heading: 3 Dr Jekyll and Mr Hyde: an actor-critic with convergence guarantees

heading: 3.1 Conditions for an actor-critic algorithm to converge to optimality
text: C4 states the necessary and sufficient condition for optimal planning with the exact model. In a reinforcement learning setting however, the model is not known; the policy must be learnt from samples collected in the environment. As a consequence, A1 cannot be made anymore, we need to rely on an exploration condition instead:
C6. Each state-action pair is explored infinitely many times: ∀s, a, limt→∞ nt(s, a) =∞,
where nt(s, a) is the count of samples collected for the state-action pair (s, a) at time t.
In finite MDPs, C6 provides a necessary and sufficient condition for having an unbiased estimator of the value. As is customary, we call this estimator the critic and denote it q̊t. C6 is necessary because
the required statistical precision can only be achieved when the number of samples tends to infinity; it is sufficient as guaranteed by many off-policy policy evaluation algorithms from the literature [31, 46]. Classic concentration bounds, such as Hoeffding’s inequality, tell us that with O(1/ξ2) samples in every state, a ξ-accurate critic can be achieved. Under C4 and C6, there thus exists a timestep after which updates based on q̊t are sufficiently close to the true ones for a continuity argument to show that the policy improves eventually4 (as guaranteed by theory under A1).
Our results till now have assumed a finite MDP and models with sufficient capacity. In larger domains, those assumptions do not hold anymore, and therefore our theory does not apply. For instance, [26] proves that using the on-policy undiscounted update dπt,1 instead of the policy gradient can lead to highly suboptimal policies under state aliasing. Their counter-example applies to our policy updates as well. Nevertheless, we believe that state aliasing is a worst-case scenario and conjecture that it does not happen to neural networks thanks to their high expressive capacity. Also note that this concern with respect to distribution shift is general and could be formulated for any neural model, including supervised models, or in RL the purely value-based ones such as DQN that are frequently trained off-policy. The consensus in the literature is that neural models do not suffer too much from distribution shift as long as the testing set distribution is well covered by the training set. Since appropriate coverage of the state-action space is actually the final objective of our off-policy policy updates, we expect minimal impact on this dimension, though it does remain to be formally demonstrated. Our empirical results from Section 4.4 support this conjecture. The theoretical study of the function approximation setting is left for future work.

heading: 3.2 Our solution to enforce C4 and C6
text: Enforcing C4 C4 defines the necessary and sufficient condition for asymptotic convergence to optimality. However, we will see in Section 4.2 that in difficult planning tasks, C4 can be insufficient for convergence to happen in a reasonable amount of time. Below, we therefore introduce C4-s, a condition stronger5 than C4, as well as two techniques for C4-s to be verified:
C4-s. ∀s ∈ S, limT→∞ 1T ∑T t=0 ηtdt(s) ≥ d⊥(s) > 0.
The first technique to enforce C4-s is to apply the approximate expected policy update [39, 20, 10]: Û(θ, s) . = ∑ a∈A q̊(s, a)∇θπ(a|s). (7)
The expected policy update is deterministic in the sense that it does not require sampling actions. As there exists a deterministic optimal policy, this in turn implies that the learning rate ηt does not need to satisfy the second Robbins-Monro condition: ∑ t η 2 t <∞, and thus may be constant ηt . = η.
The second technique to enforce C4-s is to ensure that the density of updates dt does not decay to 0 for any state s. This can be obtained by maintaining a constant proportion ot of off-policy actor updates in order to cover the whole state space. We propose to do so by recording two replay buffers: one with on-policy samples, i.e. samples collected with an exploitation policy, and another with off-policy samples, i.e. samples collected with an exploration policy.
To the best of our knowledge, this type of prioritized experience replay has never been used in this fashion, nor to this effect. We note that off-policy policy gradient is a concept that exists in the literature, but it refers to the application of policy gradients from batch samples [21]. Following the success of DQN [24], experience replays have also been used in actor-critic methods [49] which bears some resemblance to our suggestion. Finally, off-policy actor-critic with shared prioritized experience replay [34] has been applied to large-scale experiments with distributed agents [14, 35].
Enforcing C6 Many RL algorithms (actor-critic or purely value-based) ensure some form of exploration. They broadly form two groups: dithering exploration (e.g., epsilon greedy, softmax, entropy regularization [47, 42, 13]), and deep exploration (e.g., UCB, thompson sampling, density constraints [28, 3, 29, 32]). Strong cases have been made against dithering exploration, arguing in particular its inability to ensure visits to all states and therefore convergence to optimality [30].
4A formal proof would require dealing with several technical challenges due to the stochasticity of the value updates that break the monotonicity of the estimator accuracy. We leave it for future work.
5C4-s is identical to C5, but applied to the full state space S (it thus implies C5).
Input: Scheduling of exploration ( t), of off-policiness (ot) and of actor learning rate (η̊t). 1: Initialize Dr Jekyll’s replay buffer D̊ = ∅, actor π̊, and critic q̊. . exploitation agent 2: Initialize Mr Hyde’s replay buffer D̃ = ∅, and policy π̃. . exploration agent 3: Set the behavioural policy and working replay buffer to Dr Jekyll’s: πb ← π̊ and Db ← D̊. 4: for t = 0 to∞ do 5: Sample a transition τt = 〈st, at ∼ πb(·|st), st+1 ∼ p(·|st, at), rt ∼ r(·|st, at)〉. 6: Add it to the working replay buffer Db ← Db ∪ {τt}. 7: if τ was terminal, then (πb, Db)← (π̃, D̃) w.p. t, (πb, Db)← (̊π, D̊) otherwise. 8: if Update step, then 9: τ . = 〈s, a, s′, r〉 ∼ D̃ w.p. ot, τ .= 〈s, a, s′, r〉 ∼ D̊ otherwise. 10: Update Mr Hyde’s policy π̃ on τ . . e.g. with Q-learning trained on UCB rewards 11: Update Dr Jekyll’s critic q̊ on τ . . e.g. with SARSA update 12: Expected update of Dr Jekyll’s actor π̊ in state s. . Eq. (7) 13: end if 14: end for Algorithm 1: Dr Jekyll & Mr Hyde algorithm. After initialization of parameters and buffers, we enter the main loop. At every time step, an action, chosen by the behavioral policy, is executed in the environment to produce a transition τt (line 5). τt is stored in the replay buffer of the personality in control (either Dr Jekyll or Mr Hyde, line 6). If the trajectory is done, the algorithm samples a new personality to be in control during the next one (line 7). Then, the updates of the models start (line 8). The updates for Mr Hyde’s policy π̃ and Dr Jekyll’s critic q̊ are underspecified, and may be any algorithm in the literature satisfying the exploration (for Mr Hyde) or unbiased (for Dr Jekyll) conditions. When ( t) = 0, J&H amounts to on-policy expected updates from a single replay buffer.
In spite of these arguments (that we recall in App. A.5), there are still only very few actor-critic algorithms that realize deep exploration [9, 33]. We conjecture that this relates to the following observations: i) exploration involves a moving objective, hence a non-stationarity of the desired policy, ii) actor-critic algorithms have a structural inertia in their policy (in contrast to value-based methods that can completely switch policy when an action’s value overtakes another’s). As a consequence, a dual exploration-exploitation actor-critic algorithm takes a lot of time to switch from deep exploration to exploitation, and back, making it inefficient. To avoid this issue, we propose to train two policies, a pure exploration one and a pure exploitation one. As an added benefit, they will be used to constitute the on-policy and off-policy replay buffers introduced in the second technique above.

heading: 3.3 Dr Jekyll and Mr Hyde algorithm (J&H)
text: The objective of this section is to introduce a novel algorithm that satisfies conditions C4 (or C4-s) and C6 by design. To do so, we maintain a mixture of two policies:
• Dr Jekyll π̊t is a pure exploitation policy,
• Mr Hyde π̃t is a pure exploration policy.
At the beginning of a new trajectory, Mr Hyde π̃t (resp. Dr Jekyll π̊t) is chosen with probability t (resp. 1− t) and used to generate the full trajectory. Dr Jekyll π̊t is trained with the update rule of Eq. (3), where dt is defined by prioritized sampling over the experience replays, qt is replaced with an unbiased estimator q̊ of the value of π̊t, and θ̊t are the parameters of π̊t. π̃t is a pure exploratory policy, designed to verify almost surely: ∀(s, a) ∈ S × A, limt→∞ n|D̃|(s, a) ≥ d̃⊥ > 0,, where n|D̃t|(s, a) is the count of samples (s, a) in its experience replay. We note that a uniform policy satisfies this condition, but with a very small constant d̃⊥ which compromises convergence in a reasonable time. Any deep exploration algorithm should be guaranteeing it6. In our finite MDP experiments, we implement q-learning with UCB rewards [3]: π̃t . = argmaxa∈A q̃t where q̃t is trained to predict the expectation of the discounted sum of rewards: r̃(s, a) .= 1√ nt(s,a) (see full Alg.
6Efficient exploratory algorithms are a challenge in large environments. The design of such algorithms is beyond the scope of this paper.
3 in App. E). In our deep learning experiments, Hyde is a Double-DQN [48] trained to maximize an exploration bonus based on Random Network Distillation [6] (Section 4.4).
The advantages of separating the exploration from the exploitation policy are the following. First, it is easier to specify the exploration/exploitation trade-off and get full control on the exploration requirements for condition C6: ∀s, a, ∑t dπt(s, a) =∞. Second, Jekyll’s actor π̊ is not optimized under a moving objective which would otherwise induce a high level of instability on the policy. Third, one can define the on-policiness/off-policiness ot by recording two separate replay buffers D̊ and D̃, for trajectories respectively controlled by Dr Jekyll and Mr Hyde. This offers full control on condition C4/C4-s and on the asymptotic behaviour of ∑ t ηtdt(s).
These various observations lead to the design of the Dr Jekyll and Mr Hyde algorithm (J&H), formally detailed in Alg. 1.

heading: 4 Experiments

heading: 4.1 Domains
text: Chain Domain The chain domain is designed to measure the ability of algorithms to overcome immediate rewards pushing the policy gradient towards suboptimal policies. In every state sk, the agent has the opportunity to play action a1 and receive an immediate reward of βγ|S|−2, or to play a2 and progress to next state sk+1 without any immediate reward. A reward of 1 is eventually obtained when reaching state s|S|−1. Fig. 1 represents a chain of size 10. We report the normalized performance: J π = Jπ−J⊥J?−J⊥ , where J? is the optimal performance and J⊥ . = q(s0, a1) = βγ |S|−2.
Random MDPs The random MDPs domain is designed to test the algorithms in situations where exploration is not an issue. Indeed, by its design of stochastic transition functions, random MDPs will have a non-null chance to visit every state whatever the behavioural policy. It is therefore a domain where we expect policy gradient updates to perform well, perhaps optimally, and hope that our modified updates still perform comparably. We reproduce the random MDPs environment published in App. B.1.3 of [18]. We report the normalized performance: J π = Jπ−JuJ?−Ju , where J? is the optimal performance and Ju is the performance of the uniform policy. The full description of both domains is available in App. C.

heading: 4.2 Finite MDP policy planning (A1)
text: We test performance against time, learning rate η of the actor, MDP parameters |S| and β, offpoliciness ot, and policy entropy regularization weight λ, with both direct and softmax parametrizations, on the chain and random MDPs. The full report is available in App. D.
On the chain domain, we confirm that enforcing updates with dt . = otdu+(1−ot) dπt,γ‖dπt,γ‖1 including an off-policy component ot > 0 on a uniform state distribution du(s) . = 1|S| helps path discovery and policy planning, while on-policy updates fail at converging to the optimal policy, even with policy entropy regularization. We also observe that while ot ∈ Ω(t) enforces C4, and therefore guarantees convergence to optimality, it may not happen in a reasonable amount of time, and a constant offpoliciness is preferable. By sweeping over the chain parameters β and |S|, we observe that on-policy updates are sensitive to both: even with a small β = 0.1, a reasonably sized chain |S| = 15 cannot be solved. In contrast, ot = 0.5 converges fast to optimality even with β = 0.95 and |S| = 25.
On the random MDPs domain, we observe empirically that discounted and undiscounted updates perform well but oftentimes stagnate at 99% of the optimal performance; dt with an off-policy component performs better and gets even closer to optimality. Finally, we note that purely uniform updates: ot = 1 slow down training in the random MDPs experiment. We conclude that it is best to include both on-policy and off-policy components in dt. These experiments also allow us to observe the biased convergence implied by policy entropy regularization.

heading: 4.3 Finite MDP reinforcement learning experiments
text: With the softmax parametrization, we tested J&H with various scheduling for t and ot against on-policy (PG/undiscounted) updates, with/without policy entropy regularization (hyperparameter λ), and with/without UCB critic (UCB hyperparameter ν). The full description of the algorithms implementations is available in App. E.1. Our policy planning experiments suggested that ot was best constant at 0.5, the same holds in our RL experiments. Fig. 2a reveals that on-policy updates with/without policy entropy regularization cannot solve the chain experiment of size 10 with β = 0.8. In contrast, the task is solved by on-policy updates with a strong UCB bonus ν = 1 for the critic, and by all J&H implementations. Concerning J&H scheduling hyperparameters, we observe that ot = 0.5 allows to identify the optimal policy significantly faster, and t = 100t is sufficient and allows to converge faster asymptotically than t = 10√t . Fig. 2b shows that all algorithms are able to solve the random MDP task. However, UCB critics with high ν ∈ {0.1, 1} (including the only on-policy setting that succeeded on the chain task) fail to do so properly: they eventually will, but explore too much within the experimental time. If we look more closely at the tight convergence of every algorithm on Fig. 2c, we observe that the policy entropy regularization incurs a bias and that off-policiness of updates of J&H does not slow down convergence compared to vanilla onpolicy updates. Note that J&H with t = 10√t performs worse only because we report the expected performance of the mixture of Dr Jekyll and Mr Hyde. The performance of Dr Jekyll alone is comparable, and even slightly better than vanilla on-policy updates (see Fig. 9b in App. E).
For completeness, we also test performance against time, learning rates of the actor η and critic ηc, MDP parameters |S| and β, off-policiness ot, exploration t, and critic initialization q0 with the softmax parametrization on the chain and random MDPs domains. See App. E for the full report.

heading: 4.4 Deep reinforcement learning experiments
text: To conclude our empirical evaluation, we implemented a deep version of J&H, as described in Algorithm 1, by parametrizing the agents using deep neural networks (see App. F for full details).
Dr Jekyll is a policy network, with a standard architecture, trained using the updates described in Eq. (7). As previously mentioned, any exploration algorithm can be used for Mr Hyde. In our experiments, we chose Random Network Distillation [6, RND] to generate exploration bonuses. Two networks, one random, the target, and a second one, the predictor, are used to assess the novelty of an observed state via the distance between the output of the target and the output of the predictor on that state. Each time a given state is evaluated, the predictor is trained to predict the output of the target. The more a state is seen, the smaller the prediction error will be. The error is used as a reward signal for Mr Hyde, a standard Double-DQN [48, DDQN] trained to maximize it. By doing so, Mr Hyde is incentivized to explore parts of the state space that have not been visited much yet.
We train J&H on a version of the Four Rooms environment [44], a 15x15 grid split into four rooms (see App. F for the exact layout). The agent, placed at random initially, needs to navigate to a fixed goal location, where it is granted a positive reward. For each step taken in the environment, the agent incurs a small negative reward. We consider two levels for the task. In level 1 (the original version of the game), the initial state distribution covers the entire state space, which corresponds to A2 being verified. To make exploration harder, we also consider an initial state distribution that does not contain any state from the room where the goal is located, and call that task level 2. We compare J&H to DDQN and Soft-Actor Critic [13, SAC]. For fair comparison, we also train these agents on the environment rewards augmented with the RND rewards used to train Mr Hyde, represented by the curves labelled DDQN+RND and SAC+RND.
Results can be found in Fig. 3. On level 1, we see that J&H reaches quite fast the maximal score of 90, The baselines do not perform as well and fail to converge to the optimal policy. Interestingly, even with A2 verified, adding an RND bonus led to increased performance. We also notice that overall SAC outperforms DDQN. The same observations can be made on level 2. We note that on some seeds, J&H takes more time to learn the optimal policy, leading to visible plateaus and temporary high variance. However, a powerful property underlined by our experiments and offered by the decoupling of exploration from exploitation is the ability of J&H, unhindered by dithering and/or conflicting reward signals, to converge to optimality. Comparatively, the baselines get stuck in a mixed exploration/exploitation behavior and fail to reach the maximum score.

heading: 5 Contributions and limitations
text: Contributions:t i ti :r st i ti :r We study a planning issue in actor-critic algorithms and tackle it by extending the policy gradient theory to policy updates with respect to any state density. Under these generalized policy updates, we show convergence to optimality under a necessary and sufficient condition on the updates’ state densities. We also significantly improve previous asymptotic convergence rates. We implement the principles prescribed by our theory in a novel algorithm, Dr Jekyll & Mr Hyde (J&H), with a double personality: Dr Jekyll purely exploits while Mr Hyde purely explores. J&H’s independent policies allow to record two separate replay buffers: one on-policy (Dr Jekyll’s) and one off-policy (Mr Hyde’s), and therefore to update J&H’s models with a mixture of on-policy and off-policy updates. Beyond J&H, we define conditions for actor-critic algorithms to satisfy the requirements from our analysis. We extensively test J&H on finite MDPs and deep RL where it demonstrates superior planning abilities, and at least comparable asymptotic rates, to its competitors.
Limitations and future work:i it ti t :s f r ra a ei it ti t :f r r On the theory side, our non-asymptotic convergence rates are limited to the softmax and require A2 and C3. Although we are convinced our arguments hold, we did not develop the formal convergence proof in the RL setting (see second paragraph of Section 3.1). Finally, our theory does not tackle function approximation. In that context, we believe techniques from [2] could be useful. On the empirical side, we wish to emphasize that our deep RL experiments are to be considered as a proof of concept of the relevance of J&H’s principles in that setting. A thorough study, encompassing more environments and baselines, potentially both in discrete and continuous actions spaces, is left for future work.
Acknowledgments and Disclosure of Funding
We would like to thank Shangtong Zhang for our fruitful discussions and Alessandro Sordoni for helping us presenting and organizing the paper.

Review summaries:
The paper addresses exploration with policy optimization methods by explicitly separating the exploration and exploitation parts of the policy. First, some theory is developed to support this idea by generalizing the policy gradient to allow arbitrary state distributions. Then, experiments in small MDPs and in deep RL demonstrates its advantages empirically.  

In this paper the authors propose an extension to policy gradient theory which considers policy updates under any state distribution density. Moreover, they present the necessary conditions for convergence to optimality under their new formulation. Subsequently, they implement the ideas supported by their theory and construct a new agent which they call J&H (Dr Jekyll and Dr Hyde). The main idea of this agent is to consider two policies one which is fully exploitative (Jekyll) and one which is completely exploratory (Hyde). This way during training they can combine on-policy and off-policy updates. Finally, they test their agent in a series of simple MDPs and show that their proposed agent is superior at  recovering from converging to a suboptimal policy. 

This paper studies the effects of off-policy updates for policy gradient methods in RL. The authors show that under certain conditions on the state update distribution and learning rate, exact PG methods will converge to the optimal solution. Based on this result, the authors propose an RL algorithm where the policy is trained on states from two distributions: 1) the on-policy data distribution and 2) the distribution of an "exploratory" policy. This method is demonstrated on two exceedingly simple tasks. 

The paper extends the policy gradient theorem from purely on-policy gradients to arbitrary state distributions. The authors provide proofs of convergence and (improved) rate of convergence under milder assumptions than the original policy gradient theorem. They propose a simple agent that separately performs on-policy and off-policy updates, and include a carefully-designed toy experiment that elegantly shows their algorithm achieve globally-optimal results when traditional policy gradient approaches fail. They also demonstrate their approach on a simple deep-RL benchmark.