Dr Jekyll & Mr Hyde: the strange case of off-policy policy updates
Authors: Romain Laroche
Remi Tachet des Combes
Venue: NeurIPS 2021 Poster (2021)
Keywords: policy gradient
reinforcement learning
actor-critic
theory
algorithm
deep reinforcement learning
exploration
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.

Dr Jekyll and Mr Hyde: The Strange Case of Off-Policy Policy Updates
Romain Laroche" Microsoft Research Montréal, Canada
Rémi Tachet des Combes" Microsoft Research Montréal, Canada
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 the off- off-pollcy states, and thus to convergence to suboptimal policies. We tackle this planning issue by extending the policy gradient theory to policy updates with re- spect to any state density. Under these generalized policy updates, we show con- vergence 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 theory, pro- pose an agent, Dr Jekyll & Mr Hyde (J&H), with double personality: Dr Jekyll purely exploits while Mr Hyde purely explores. J&H's independent policies al- low to record two separate replay buffers: one on-policy (Dr Jekyll's) and one off-policy (Mr Hyde's), s), and therefore to update J&H's models with mixture of on-policy and off- aff-policy updates. More than an algorithm, J&H defines principles for actor-critic algorithms
satisfy the requirements We extensively test on finite MDPs where J&H demonstrates a superior ability suboptimal policy without impairing its speed of
identify in our analysis.
recover from converging convergence. We also implement deep version of the algorithm and test it on a simple problem where shows promising results.
1 Introduction
Policy Gradient algorithms in Reinforcement Learning (RL) have enjoyed great success both theo- retically [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]:
[(T) =
Σ
7
Rs
So Po. x(118),, S441 ~ ((, r(-(S,, Ac)
(1)
VaJ(T) Σ (s) Σ SES
gx (e)s,))VoT(al and 0,41 ppooj O2 ni Ve. (TT),
aEAA
using standard Markov Decision Process notations (recalled in App. A), where T/e is the learning rate and (s) D T PPSS = 8/ the discounted state density, the policies π ma and T, - Te, implicitly parametrized by for conciseness, and "roo 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 aff-po states (i.e. states that rarely visited). As consequence,
Equal contribution. Correspondence to: rolaroch@ microsoft.com. All code available at http://aka.m/jnh.
35th Conference on Neural Information Processing Systems (NcurIPS 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 con- sidering the more general policy update:
U(0, d) = ((0.d)=Ed(s) d(s) E a) and aut1 proo 01 + (O de), (3)
SES
aeA
where de 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 (0, d) is not gradient in the general case, hence the use of the term update. We prove in the direct: xe = 0 and softmax: Tа ~ exp(0) parametrizations that following the exact policy updates induces sequence of value functions qe = qx, that is monotonously increasing, upper bounded, and thereby converges foc- We then show that the condition "V's E S, Σ, ()) = oo" on the sequence (de) is neces- sary and sufficient for Jeo. to be optimal. Our result generalizes previous theorems to broader updates and milder assumptions [2, 22]. Finally, we significantly improve the existing asymptotic conver- gence rates. We show that (4:) converges to the optimal value i) exactly finite time for the direct parametrization (previously in O (1]AA1 -
(2), and ii) in O (1-1SS||A[() - ->)-*)
for the softmax parametrization, to be compared with O (S- (A 7)= [22].
Building on theoretical results, we design novel algorithm: Dr Jekyll and Mr Hyde (J&H). Its principle consists in training two independent policies: a pure exploitation one (Dr Jekyll) and 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), s), and therefore to update J&H's models with any desired mixture of on-policy and off- 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 4: is exactly known, analyze the impact of the off-policiness of de and conclude that, while it improves over classic policy gradient, the theoret- ical sufficient condition does not allow converge in a reasonable amount of time in very hard plan- ning tasks: we thereby recommend to enforce the stronger condition "Vs E S, Σ, (s) E 22())" In the reinforcement learning domain, where qe must be estimated from the collected transitions, the off off-policiness of J&H's policy updates allows by design to satisfy the recommendation as long as Mr Hyde is able cover the whole state space. This leads J&H significantly outperform all competing actor-critic algorithms in the hard planning tasks and to be competitive with gradient up- dates 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 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 re- sults. 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.
2 Theoretical analysis
First, we recall some background: policy gradient methods depend on parametrization 0 R |||||||| of policy. Like [2, 22], we will focus the classic direct and softmax parametrizations:
direct: T (a]s)) + ts.a, for which us.a = de(s)) (s, (s) and the projection is on the simplex.
exp(Px.a) for which Us.a =d))))((as)((( vz()))
softmax:
(aas)) E.. cxp(Ox.ar)
2

---

For both parametrizations, [2] proves that following the policy gradient V=](T) from Eq. (2) even- tually leads to the optimal policy in finite MDPs under the following assumptions and condition":
A1. The model (P is known.
A2. The initial state-distribution covers the full state space: Vs E S,po(s) > 0.
(1-7)² (direct) and TJ: (1-7)² (softmax).
C3. The learning rate constant: 7/+ 27|
Those are stringent requirements. Al implies that the values 4ur and state density dx.,y the policy are known exactly. A2 is generally not satisfied in standard RL domains. Finally, verifying C3 makes learning slow to the point that becomes impractical.
2.1 Convergence properties
In this section, we study, under AI, the convergence properties of the sequence of value functions (q:) induced by the update rule defined in Eq. (3). We note that (0, d) is not a gradient in general. Our first theoretical result is the monotonicity of the value function sequence (gt).
Theorem (Monotonicity under the direct and softmax parametrization) Under Al, the se- quence of value functions qe = Qa, and 1/ = Ust are monotonously increasing.
By the monotonous convergence theorem, Thm. directly implies the convergence of (q:): Corollary 1 (Convergence under the direct and softmax parametrization) Under Al, the se- quence of value functions qe uniformly converges: Us0
1im 9t-
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 de which could be equal (or tend very fast) to 0 in some states, compromising the policy's s ability to reach the optimal value. This argument not only theoretical, 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 (q:) converges to the optimal value function under some necessary and sufficient condition.
Theorem 2 (Optimality under the direct and softmax parametrization) Under AI, the following condition:
C4. Each state is updated with weights that sum to infinity over time: E (s) = co.
necessary and sufficient guarantee that the sequence of value functions (gt) converges to opti- mality: 9x- = q, max 9n.
Proof sketch. In both direct and softmax parametrizations, we assume there exists state-action pair (s, advantageous with respect to the state value limits 9:0 and Use - lim4 that is: adv (s, a) = 9:0 (s, a) Voc (s) > O. 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 (s), Both parametrizations require different proof techniques and are dealt with in different theorems. Sum- ming over f, 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 conclude that no policy improvement is possible, and thus that the values are optimal: fxo max In-
For the necessity of C4, show that the parameter update is upper bounded in both parametriza- tions by term linear in the action gap. By choosing the reward function adversarially, we may set it sufficiently small that the sum of all the gradient steps is insufficient reach optimality.
Thm. 2 is impactful along five dimensions.
Practice of on-policy undiscounted updates: As Thm. 2 is applicable any distribution sequence, it allows us in particular to consider the practice using on policy undiscounted updates: d, = dz,,1-
2 An assumption A# is requirement on the environment or the application setting, while condition C# is requirement that may be enforced by dedicated algorithm in any environment or setting.
3

---

Thus, it resolves a longstanding gap between the policy gradient theory and the actor-critic algorithm implementations [12. 7, 51, 17, 19, 41J. 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. allows to reduce the study of specific algorithms to whether they verify C4.
Experience replay and off- off-policy updates: 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 optimality?. We leverage this discovery to introduce new design principles and a novel algorithm in Section 3.
Policy gradient theory: Next, Thm. 2 generalizes previous optimality convergence results along two axes. The initial state distribution Po 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 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: In contrast, C4 can be controlled by a dedicated algorithm. This theoretical result promotes the principle of density-basee regularization [21, 32], at the expense of policy-based regularization that cannot guarantee that C4 is satisfied and sometimes fails plan over the whole state space (our chain domain experiments in Section 4 illustrate it well).
Towards generalized policy iteration theorem: Finally, by combining Thm. 2, which analyzes pol- icy improvement, with a thorough theoretical analysis of the policy evaluation step (discussed in Section 3.1). see path towards results describing conditions on both components of generalized policy iteration that guarantee convergence to optimality [4]. Furthermore, Thm. 2 gives sufficient conditions the policy improvement step. The generalized policy iteration theorem conjec- tured in [42] but never proved.
2.2 Convergence rates
Next, we give convergence rates for both softmax and direct parametrizations:
Theorem 3 (Asymptotic convergence rates under the direct parametrization), With direct parametrization, under Al and C4, the sequence of value functions qe converges to optimality in finite time:
Soo such that Vt 2 to. 9: = qx
(4)
C4 is required for optimality and convergence rate contrarily to the softmax parametrization. We significantly improve over previous bounds in O (t- [/-//||S||A| - 7) [2]. We wish to emphasize that Theorem 3 does not say anything about how large to is, the rate is purely asymptotic.
Theorem 4 (Asymptotic convergence rates under the softmax parametrization). With softmax parametrization, under Al, C4, and A8:
A8. The optimal policy is unique: Vs, (,( q. (s, u. (s) implies an a2
the sequence of value functions q converges asymptotically as follows:
81A - -.))
Slo such that Vt 2 to. (s) (s) S (1 - 7) min ,)) 6(s) El-l dy)
(5)
*Other papers proving convergence optimality of policy gradient rely A2, which implies C4.

---

where 8(s) = v, (s) / (s)),a) is the gap with the best suboptimal action in state u- (resp. v_) is the maximal (resp. minimal) value, and supp(da..n) denotes the support of the distribution of the optimal policy.
If (de) satisfies the additional mild condition that the support of d, is covered on average:
C5. Vs E supp(d_), lime-roo E' (. e. es) > 0.
then we obtain the following convergence rate in (t-
8]A[(u, v.)
3to such that Vt 2 to. v.(s) - vr(s) 5 (1- ln)(1 - min sespoesspp(dd... 0()) (8)
(6)
C5 is implied by A2 and C3. Alternately, assuming 2 > 0 Vt. it is verified by a uniform distribution in which case e. (s) i or by an on-poliey distribution dx, that converges to the dis-
tribution of some optimal policy d=, in which case e, (8) = 11 dz, (s). Also, note that C4 is required for optimality, but not for convergence rates with respect fsc- Thm. 4 establishes asymptotic rates in O [S|AA|[ partially explained by dropping C3 and allowing any learning rate (see App. A.6 for a thorough
to be compared with O (| - ?) -)- [22]. The gap
comparison). It is possible, see Thm. 7 of App. B, to show that under A2, a condition on the learning
rate, and bounding condition on de (Ed, d2 > such that Vs,t, dr 2 (s) 2 d.), we have:
to O
|s| dr --->)>
di min, 6(8)
2.3 Related work
[11, 15, 52] study the off-policy, continuing setting paired with the average value objective. That objective is either expressed with 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 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 study). It is 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 byproduct, can rely on standard optimization results: strong convexity and convergence of gradients to O. We cannot do so as our updates are not gradients anymore. More precisely, Lemma C2 in [2] uses the strong con- vexity 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 con- dition the learning rate) and, in admittedly biased opinion, more elegant proof of that lemma in our Theorem 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 non- 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 setting, had to leverage C4 instead.
3
Dr Jekyll and Mr Hyde: an actor-critic with convergence guarantees
3.1 Conditions for an actor-critic algorithm to converge to optimality
C4 states the necessary and sufficient condition for optimal planning with the exact model. In reinforcement learning setting however, the model is not known; the policy must be learnt from samples collected in the environment. As consequence, Al cannot be made anymore, we need to rely on an exploration condition instead:
C6. Each state-action pair is explored infinitely many times: Vs, a, lim me (s. a) x0,
where ne (, a) is the count of samples collected for the state-action pair (s, a) at time l. 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 qr. C6 is necessary because
5

---

the required statistical precision can only be achieved when the number of samples tends to infinity; it sufficient as guaranteed by many off off-po policy evaluation algorithms from the literature [31, 46]. Classic concentration bounds, such as Hoeffding's s inequality, tell us that with ((1/5²) samples in every state, a f-accurate critic can be achieved. Under C4 and C6, there thus exists a timestep after which updates based on & are sufficiently close to the true ones for continuity argument to show that the policy improves eventually* (as guaranteed by theory under Al).
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 in- stance. [26] proves that using the on-policy undiscounted update dx,,1 instead of the policy gradient can lead to highly suboptimal policies under state aliasing. Their counter-exame exammee applies to our policy updates as well. Nevertheless, we believe that state aliasing is a worst-case scenario and con- jecture that 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- 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.
3.2 Our solution to enforce C4 and C6
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, condition stronger than C4, as well as two techniques for C4-s to verified:
C4-s. Vs E S, 1om + Ei= (s) 2 (s) > O.
The first technique to enforce C4-s is to apply the approximate expected policy update [39,20, 10]:
( 8) Σ Vor(ll)) BEA
The expected policy update is deterministic in the sense that does not require sampling actions. As there exists deterministic optimal policy, this in turn implies that the learning rate 7)t does not need to satisfy the second
condition: E, n² < co, and thus may be constant 17: = 17.
The second technique to enforce C4-s is to ensure that the density of updates de does not decay to 0 for any state s. This can be obtained by maintaining constant proportion or 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 concept that exists in the literature, but it refers 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 our suggestion. Finally, off- 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 ex- ploration. 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, 32D. 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].
AA formal proof would require dealing with several technical challenges due to stochasticity of the value updates that break the monotonicity of the estimator accuracy. We leave it for future work.
5 CC4s is identical to C5, but applied to the full state space S (it thus implies C5).

---

Input: Scheduling of exploration (4t), of off-policiness (ot) and of actor learning rate (fi))
1: Initialize Dr Jekyll's replay buffer á 0. actor 4 and critic q.
exploitation agent
2: Initialize Mr Hyde's replay buffer D 0. and policy #.
a exploration agent
3: Set the behavioural policy and working replay buffer to Dr Jekyll'': m + & and Do + D.
4: for t = 0 to oo do
5: Sample a transition 7. = (st, ar ~ (-(-)))); 8141 ~ p(-1 ot), re ~ r(1ss,,
6: Add it to the working replay buffer D3 <- D3 U (Te)-
7:
if
terminal, then (Tb. Db) ( D) w.p. e,, (To, Do) (t, D) otherwise.
8:
if Update step, then
9:
T = (s, 0, s'.r) D w.p. ot, T (s, a, r) ~ D otherwise.
10:
Update Mr Hyde's 's policy # o.
Deg. with Q-learning trained UCB rewards > e.g. with SARSA update
11: Update Dr Jekyll's critic q on T.
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 produce a transition 7x (line 5). 7: 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 '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 (ca) = 0, J&H amounts to on on-policy expected updates from 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 ob- servations: i) exploration involves moving objective, hence 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 's value overtakes another's). As consequence, a dual ration 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.
actor-critic algorithm takes lot of time to switch from deep explo-
3.3
Dr Jekyll and Mr Hyde algorithm (J&H)
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 mixture of two policies:
* Dr Jekyll सt is a pure exploitation policy,
Mr Hyde #e is a pure exploration policy.
At the beginning of a new trajectory, Mr Hyde 7. (resp. Dr Jekyll ft)) is chosen with probability er (resp. (x) and used to generate the full trajectory. Dr Jekyll ât trained with the update rule of Eq. (3), where de is defined by prioritized sampling over the experience replays, ge is replaced with an unbiased estimator q of the value of it, and 6, are the parameters of tt. He is pure exploratory policy, designed to verify almost surely: V(s, a) E S x A, lime- n (s,a) 2 d. > O,, where (s, (s, a) is the count of samples (s, a) in its experience replay. We note that uniform policy satisfies this condition, but with very small constant d, which compromises convergence in reasonable time. Any deep exploration algorithm should be guaranteeing it In our finite MDP experiments, we implement q-learning with UCB rewards [3]: #e = argmax,e.4 q where q is trained to predict the expectation of the discounted sum of rewards: F(s, a) = 1 (see full Alg.
Vn((s.o)
'Efficient exploratory algorithms are a challenge in large environments. The design of such algorithms is beyond the scope of this paper.
7

---

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 specify the exploration/explottttonn trade-off and get full control on the exploration requirements for condition C6: Vs, E: dx, (s, a) o0. Second, Jekyll's actor A is not optimized under moving objective which would otherwise induce a high level of instability on the poliey. Third, one can define the on on- an-policiness/off policinessooff-oliiinsss or 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 E, (s).
These various observations lead to the design of the Dr Jekyll and Mr Hyde algorithm (J&H), for- mally detailed in Alg. 1.
4 Experiments
4.1 Domains
87*
94
85
A8
Figure I: Deterministic chain MDP. Initial state is Reward is 0 everywhere except when access- ing final states s-1 and sy. Reward in s-1 set such that q(50, a1) = Bg.. (so. a2), with B E [0, 1).
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 8k, the agent has the opportunity to play action a₃ and receive an immediate reward of 33y151-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 -1 Fig. represents a chain of size 10. We report the normalized performance: Jn ---J J.-J.' where J. is the optimal performance and J, - q(30, a1) = B-1
Random MDPs The random MDPs domain 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 domain where 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. 1.1.3 of [18]. We report the normalized performance: Jn = -ーー where J. the optimal performance and Ju is the performance of the uniform policy. The full description of both domains is available in App. C.
4.2 Finite MDP policy planning (A1)
We test performance against time, learning rate y7 of the actor, MDP parameters |S| and B, off- policiness ot, and policy entropy regularization weight X, with both direct and softmax parametriza- tions, on the chain and random MDPs. The full report is available in App. D.
deux including On the chain domain, we confirm that enforcing updates with d, = o,dy +(1-x+)))))) (( T
off-policy component o, 0 on uniform state distribution (s) = [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 E 22(t) enforces C4, and therefore guarantees convergence to optimality, it may not happen in a reasonable amount of time, and a constant off- policiness is preferable. By sweeping over the chain parameters 3 and [S], we observe that on on-policy updates are sensitive to both: even with a small = 0.1, reasonably sized chain |S] be solved. In contrast, o 0.5 converges fast to optimality even with B 0.95 and |S| 25.
cannot

---

Autte 2001 3014
Aulfe 30V8 3000
spdets Ao
indropentdd
onjesonn
(a) Chain experiment
(h) Random MDPs experiment
(c) Random MDPs zoomed in
Figure 2: RL experiments: normalized expected return vs. number of trajectories (200+ runs).
On the random MDPs domain, we observe empirically that discounted and undiscounted updates perform well but oftentimes stagnate at 99% of the optimal performance; d, with an poolccy component performs better and gets even closer to optimality. Finally, we note that purely uniform updates: o = 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 dz. These experiments also allow us to observe the biased convergence implied by policy entropy regularization.
4.3 Finite MDP reinforcement learning experiments
With the softmax parametrizattonn, we tested J&H with various scheduling for c and o against on-policy (PG/undiscountee) updates. with/without policy entropy regularization (hyperparameter A), and with/without UCB critic (UCB hyperparameter 1/). The full description of the algorithms implementations is available in App. E. Our policy planning experiments suggested that o was best constant 0.5, the same holds in our RI. experiments. Fig. 2a reveals that on-policy updates with/without policy entropy regularization cannot solve the chain experiment of size 10 with B 0.8. contrast, the task is solved by on-policy updates with a strong UCB bonus v/ 1 for the critic, and by all J&H implementations. Concerning J&H scheduling hyperparameters, that o = 0.5 allows to identify the optimal policy significantly faster, and e, = 100 is sufficient and allows to converge faster asymptotically than 6 = 10 Fig. 2b shows that all algorithms are able 77
observe
solve the random MDP task. However, UCB crities with high E (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 the tight convergence of every algorithm on Fig. 2c, we observe that the policy entropy regularization incurs a bias and that off- off-policiness of updates of J&H does not slow down convergence compared to vanilla on- policy updates. Note that J&H with E, = 10
Vt 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 r and critic Ye. MDP parameters [S] and B8, off- poficioiisness ot, exploration 6, and critic initialization qo with the softmax parametrization on the chain and random MDPs domains. See App. E for the full report.
4.4 Deep reinforcement learning experiments
To conclude our empirical evaluation, we implemented deep version of J&H, as described in Algorithm 1, by parametrizing the agents using deep neural networks (see App. for full details).
Dr Jekyll is 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 second one, the predictor, are used 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 evaluated, the predictor is trained to predict the output of the target. The more a state is seen, the smaller the prediction enror will be. The error is used as reward signal for Mr Hyde, 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.

---

300
Roling Eptzedo Scores
Balling Eptsorie Scores
20-
200
100
Episode Number
DOON
SAC-RND
J6f1
D2ON-RND
SAC+RAD
J6l1
(a) Level
(b) Level
Figure 3: Deep RL experiments: score vs. number of training episodes, averaged over 10 seeds.
We train J&H version of the Four Rooms environment [44], 15x15 grid split into four rooms (see App. F for the exact layout). The agent, placed at random initially, needs to navigate to fixed goal location, where it is granted 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 (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 contain any state from the
where the goal is located, and call that task level 2. We compare J&H to DDQN and Soft-Actor Critic [13, SACJ. 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, 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, with A2 verified, adding 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 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 mixed exploration/exploitttoon behavior and fail to reach the maximum score.
5
Contributions and limitations
Contributions: 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 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- off-policy (Mr Hyde's), and therefore to update J&H's models with a mixture of on-policy and off- 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 demonstrates superior planning abilities, and at least comparable asymptotic rates, to its competitors.
Limitations and future work: On the theory side, our non-asymptotic convergence rates 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 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.
10

---

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.
References
[1] Joshua Achiam. Spinning up in deep reinforcement learning, 2018.
[2] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approx- imation with policy gradient methods in markov decision processes. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings 3rd Conference on Learning Theory (COLT), volume
125 of Proceedings of Machine Learning Research, pages 64-66. PMLR, 09-12 Jul 2020.
[3] Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. In Proceedings of the 29th Advances in Neural Information Processing Systems (NIPS), pages 1471-1479, 2016.
[4] Jalaj Bhandari and Daniel Russo. On the linear convergence of policy gradient methods for finite mdps. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS)) pages 2394, PMLR, 2021.
[5] Mathieu Blondel, Akinori Fujino, and Naonori Ueda. Large-scale multiclass support vec- tor machine training via euclidean projection onto the simplex. In Proceedings of the 22nd International Conference on Pattern Recognition (ICPR), pages 1289-1294. IEEE, 2014.
[6] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by ran- dom network distillation. In Proceedings of the 7th International Conference on Learning Representations (ICLR), 2019.
[7] Itai Caspi, Gal Leibovich, Gal Novik, and Shadi Endrawis. Reinforcement learning coach,
December 2017.
[8] Petros Christodoulou. rithms
Deep
learning https://githi:: com/ comps/chrst//// 2019.
reinforcement
algo-
with pytorch.
[9] Kamil Ciosek, Quan Vuong, Robert Loftin, and Katja Hofmann. Better exploration with op- timistic actor critic. In Proceedings of the 32nd Advances in Neural Information Processing Systems (NeurIPS), volume 32. Curran Associates, Inc., 2019.
[10] Kamil Ciosek and Shimon Whiteson. Expected policy gradients. Proceedings of the 32nd AAAI Conference on Artificial Intelligence, volume 32, 2018.
[11] Thomas Degris, Martha White, and Richard S. Sutton. Off-policy actor-critic. Proceedings of the 29th nternational Conference Machine Learning (ICML), page 179-186, 2012.
[12] Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford, John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov. Openai baselines. https: /ttpt//tttbb/// com/
2017.
[13] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critie: Off- policy maximum entropy deep reinforcement learning with stochastic actor. Proceedings of the 35th International Conference on Machine Learning (ICML), pages 1861-1870. PMLR,
2018.
[14] Dan Horgan, John Quan, David Budden, Gabriel Martn, Matteo Hessel, Hado van Has- selt, and David Silver. Distributed prioritized experience replay. In Proceedings of the 6th International Conference on Learning Representations (ICLR), 2018.
[15] Ehsan Imani, Eric Graves, and Martha White. An off-policy policy gradient theorem using emphatic weightings. In Proceedings of the 31st Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2018.
[16] Vijay R Konda. Actor-critic algorithms. PhD thesis, Massachusetts Institute of Technology, 2002.
[17] Ilya Kostrikov. Pytorch implementations of reinforcement learning algorithms. https:/ github. com/ womm//kkostikkoo/pptoeeee a2c- pwwpppppppooeeeepeeeee gail, 2018.

---

[18] Romain Laroche, Paul Trichelair, and Rémi Tachet des Combes. Safe policy improvement with baseline bootstrapping. Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
[19] Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gonzalez, Michael Jordan, and Ion Stoica. Rllib: Abstractions for distributed reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
[20] Timothy Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learn- ing. In Proceedings of the 4th International Conference on Learning Representations (ICLR, poster), 2016.
[21] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gra- dient with stationary distribution correction. In Ryan P. Adams and Vibhav Gogate, editors, Proceedings of The 35th Uncertainty in Artificial Intelligence Conference (UAI), pages 1180-
1190. PMLR, 2020.
[22] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global con- vergence rates of softmax policy gradient methods. Proceedings of the 37th International Conference on Machine Learning (ICML), pages 6820-6829, PMLR, 2020.
[23] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep rein- forcement learning. In Proceedings of the 33rd International Conference Machine Learning (ICML), 2016.
[24] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 2015.
[25] Kimia Nadjahi, Romain Laroche, and Rémi Tachet des Combes. Safe policy improvement with soft baseline bootstrapping. Proceedings of the 17th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD), 2019.
[26] Chris Nota and Philip S. Thomas. Is the policy gradient a gradient? In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2020.
[27] OpenAL. Openai five. https: / com/ five/ 2018.
[28)
Ronald Ortner and Peter Auer. Logarithmic online regret bounds for undiscounted reinforce- ment learning. In Proceedings of the 20th Advances in Neural Information Processing Systems (NIPS), volume 19, page 49, 2007.
[29] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dgn. In Proceedings of the 29th Advances in Neural Information Processing Systems (NIPS), pages 4026-4034 2016.
[30] Ian Oshand, Benjamin Van Roy, Daniel Russo, and Zheng Wen. Deep exploration via ran- domized value functions. Journal of Machine Learning Research, 20(124):1-62, 2019.
[31] Doina Precup. Eligibility traces for off- off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
[32] Zengyi Qin, Yuxiao Chen, and Chuchu Fan. Density constrained reinforcement learning, 2021.
[33] Srinjoy Roy, Saptam Bakshi, and Tamal Maharaj. Opac: Opportunistic actor-critic. arXiv preprint arXiv:2012.06555 2020.
[34] Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience re- play. In Proceedings of the 4th International Conference on Learning Representations (ICLR, poster), 2016.
[35] Simon Schmitt, Matteo Hessel, and Karen Simonyan. Off-policy actor-critic with shared expe- rience replay. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine I Learning Research, pages 8545-8554. PMLR, 13-18 Jul 2020.
12

---

[36]
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015.
[37] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arxivv:1011 .6347,6377 2017.
[38] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanc- tot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 2016.
[39] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Ried- miller. Deterministic policy gradient algorithms. In Proceedings of the 31st International Conference on Machine Learning (ICML), pages 387-395. PMLR, 2014.
[40] Thiago D. Simão, Romain Laroche, and Rémi Tachet des Combes. Safe policy improvement with estimated baseline bootstrapping. In Proceedings of the 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2020.
[41] Adam Stooke and Pieter Abbeel. rlpyt: A research code base for deep reinforcement learning in pytorch. arXiv preprint arXiv: 1909.01900000000 2019.
[42] Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction (2nd
Edition). MIT press, 2018.
[43] Richard S Sutton, David A McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Proceedings of the 13th Advances in Neural Information Processing Systems (NIPS), 2000.
[44] Richard S. Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A frame- work for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(():181
211, 1999.
[45] Philip Thomas. Bias in natural actor-critic algorithms. In Proceedings of the 31st International Conference on Machine Learning (ICML), 2014.
[46] Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforce- ment learning. In International Conference on Machine Learning, pages 2139-2148 PMLR, 2016.
[47] Michel Tokic Adaptive s-greedy exploration in reinforcement learning based on value differ- ences. In Proceeding of the 33rd Annual German Conference on AI, volume 6359, page 203. Springer, 2010.
[48] Hado Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-learning, 2015. cite 1oxiv:1599.06661como
AAAI 2016.
[49] Ziyu Wang, Victor Bapst, Nicolas Heess, Volodymyr Mnih, Remi Munos, Koray Kavukcuoglu, and Nando de Freitas. Sample efficient actor-critic with experience replay. arXiv preprint
1rXiv:1611.01221 2016.
[50] Ronald Williams. Simple statistical gradient-following algorithms for connectionist rein- forcement learning. Machine learning, 1992.
[51] Shangtong Zhang. Modularized implementation of deep rl algorithms in pytorch. https: DeepRL, 2018.
//github. Stoon/Shanttooo Deaagg/ehhan/DDeLLL...
[52] Shangtong Zhang, Wendelin Boehmer, and Shimon Whiteson. Generalized off-policy actor- critic. Proceedings of the 32nd Advances Neural Information Processing Systems (NeurIPS), volume 32, 2019.
[53] Shangtong Zhang, Romain Laroche, Harm van Seijen, Shimon Whiteson, and Remi Tachet des Combes. A deeper look at discounting mismatch in actor-critic algorithms. arXiv preprint arXiv:2010.01069, 2021.
13


Reviews:
[{"review_id": "mivovYp8rN", "reviewer": "Reviewer_622C", "summary": "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Edit: I have updated my score following the author rebuttal. Please see my remaining concerns in my comment to the author rebuttal.\n\n\nIt is difficult to ascertain the significance of the results / ideas in the paper.\n\nThe claimed primary contribution seems to be the convergence of Eq 3 under some step-size schedule; however, this is not particularly novel and seems to follow quickly from the policy improvement theorem and standard results in stochastic approximation (unless I am misunderstanding the result).\n\nAll of the results are exclusively in the fully-parameterized regime with exact access to Q functions; while in this regime, off-policy updates do converge to the optimal policy, this breaks as soon as either condition is broken, for example when dealing with arbitrary function classes F or imperfect estimates of Q (e.g. approximate policy iteration). Given that both of these things hold when applying RL on any non-toy problem, I am not convinced about the relevance of the ideas / results derived in the paper.\n\nIt would be very interesting to see analysis as to how quickly (or slowly) these results break under these more realistic assumptions. I think something of this form would strengthen the paper significantly.\n\nIt would be useful to explicitly highlight why using the on-policy distribution is bad based on the formal results in your paper. While it is clear intuitively that the on-policy distribution will visit some states sparingly, it is not clear from the text to what degree this slows down convergence.\n\nThis paper proposes J&H as a mechanism to ensure that the policy is updated on a wide state distribution instead of the narrow on-policy distribution -- why should this mechanism be preferred over the standard mechanism of using a replay buffer to achieve the same effect? The replay buffer is a very common mechanism, and used with almost all recent practical actor-critic methods (e.g SAC, DQN)\n\nThe current experiments in the chain / random MDP / 4 room domains are in very toy settings (all either completely tabular, or in general, no need for generalization). Echoing my previous comment earlier, while these results do affirm the theoretical results, they provide very little intuition for how this kind of method will do on more standard domains that policy gradient and actor critic methods are applied to (as an example, Gym or Atari). For example, I imagine in many domains of interest with large state spaces, a dithering based strategy will perform better than this decoupled exploration / exploitation behavior, because the number of interesting states is simply dwarfed by the number of less useful states.\n\nMinor notes:\n- Is a formal definition of $\\delta(s)$ provided in the main text?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "mLU1yeP5ITb", "reviewer": "Reviewer_hpwC", "summary": "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.\n", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Novelty\n\nThe work is novel. It brings together a collection of previous work and resolves some open questions in the theory of policy gradient methods. It provides theoretical grounding for the long-established engineering technique of using off-policy updates to improve RL performance, an algorithm design with convergence guarantees, and more.\n\nThe authors clearly identify related work and place it in context in their paper.\n\n## Quality\n\nThis is a comprehensive look at the theoretical underpinnings of off-policy policy gradient methods. Claims are systematically introduced, proved, and eventually experimentally verified. (In the appendix) the proofs are clearly laid out, with proof sketches explaining complicated proofs as necessary.\n\nThe paper also includes the chain-MDP experiment that elegantly demonstrates how their method learns the globally optimal policy when traditional policy gradient approaches fail. This experiment shows the theoretical advantages manifest in practice. They also demonstrate their method in a simple Deep-RL setting.\n\nThe authors clearly identify and discuss limitations of their work. The greatest limitation of the work is that convergence proofs don’t necessarily cover the deep RL case, but that is unsurprising.\n\n## Clarity\n\nThe paper is written very clearly, and is a pleasure to read. At each stage of the derivation, the importance, implications, and potential pitfalls are identified. The derivation of their final result proceeds logically and methodically from related work.\n\n(As a small suggestion, consider adding a brief explanation/proof sketch of Theorem 2 in the main text, because it is a key theorem and its truth is not obvious. It is explained well in the appendix.)\n\n## Significance\n\nThe results are important, both because they provide theoretical grounding for common RL engineering strategies, and because it is likely to lead to a long line of further work in applying their results to more complex domains.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper deals with basic research and doesn't directly have societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "KVjmaGjxI_", "reviewer": "Reviewer_rE42", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of the paper is a new theoretical framework for designing  new actor critic methods which are more robust to the common problem of converging to suboptimal policies. By defining an update rule which can be applied under any state density, it is possible to combine data from exploratory policies which cover the state space and thus avoid early convergence to suboptimal policies. The authors show an example of such an approach with their J&K algorithm. \n\nIn their analysis the authors consider only the direct and softmax parameterization of the policy to prove their theoretical claims. This is a limitation which the authors acknowledge and is left as a future work, while they also provide empirical results to support the claim over the\ngenerality of their method. \n\nMinor Comments\nline 35: designates ? \nline 40: Define n_t before using it\nline 75: Degine adv before using it\nline 676: Lemmas are denoted as Theorems a, b. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "4LHjnEf1xU", "reviewer": "Reviewer_T2tW", "summary": "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.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nI find that the idea of explicitly separating exploration and exploitation makes sense for policy-based RL methods. I think the theoretical contributions are particularly interesting and I would have liked to see them developed further, especially with regards to doing updates with arbitrary $d(s)$ using samples. \nGenerally, the experiments were well-done and thorough although I have certain concerns about the deep RL section. \nThe writing was satisfactory overall (didn't spot any typos!) although there were a few parts I would have like to have clarified. The proofs were well-written and clear as far as I could tell. \n\nDetailed comments:\n- There is a line of work on off-policy actor-critic algorithms that I haven't seen mentioned [1,2,3], which feature different state-distribution weightings and analyze these algorithms theoretically and empirically. \nWhile all state-distribution weightings are subsumed in a general $d(s)$ in this paper, I would have liked some discussion on what weighting should be used then. \nCurrently, C4 and C4-s are fairly loose constraints on $d_t$ and $\\eta_t$. I think it would be interesting to look into this further and see what forms of d_t are theoretically advantageous, beyond simply covering all the states. In the experiments, a mix of the the on-policy state distribution and an exploratory policy's state distribution is used. Perhaps there could be some theory to support this choice? \n\nOne issue to consider would be the compatibility of a specific $d(s)$ with sampling. In particular, these previous algorithms [1,2,3] can usually be run in an online fashion (updating at every step or at every episode). In this paper, it hasn't been discussed much although there is the mention of experience-replay to help. Even with experience replay, there are many sampling strategies that could be used and it would be interesting if the theory could guide it.\n\n[1] Off-Policy Actor-Critic, Degris et al. (2012),\n[2] An Off-policy Policy Gradient Theorem Using Emphatic Weightings, Imani et al. (2018),\n[3] Generalized Off-Policy Actoc-Critic, Zhang et al. (2019)\n\n- I find theorem 2 to be a nice result since it gives necessary and sufficient conditions for arbitrary state distributions $d_t(s)$. I have various questions about the lines that follow and the interpretations of this result though.\n- Line 107-110: Could you clarify how this is related to generalized policy iteration? I'm not sure how this theorem is helping towards a generalized policy iteration theorem or what this GPI theorem would say.\n- Line 118-119: \"the convergence propoerties of policy gradient and undiscounted updates require the same set of assumptions and conditions\". Could you clarify this statement?\n- Line 123: \"prove that off-policy updates... are necessary to guarantee convergence to optimality\". Why is this true? I don't see how this follows from the theorem. There are also convergence results for on-policy PG algorithms e.g. \"On the Global Convergence Rate of Softmax Policy Gradient\" Mei et al.\n- Line 125-128: Although the initial state distribution doesn't have to cover the space, it isn't clear that this approach solves the exploration issue theoretically. If my interpretation is correct, the open problem outlined in the citation (\"Optimality and Approximation...\"Agarwal et al.) is not to relax A2 with any algorithm but with the standard policy gradient. That is, can we get the convergence rates for vanilla PG in the survey by Agarwal et al. without having A2? So, I don't think the claim of solving this open problem would be justified.\n\n- Concerning condition C4 and theorem 3 (the convergence rate), why is that we can't just choose eta_t to be extremely large (even increasing over time)? Then we would satisfy C4 or C4-s easily for any d_t that is nonzero everywhere. Also, we would seemingly get the best convergence rate.\n\n- In the deep RL experiments, J&H uses value-based methods for each part. This confuses me since the original motivation seemed to be to improve the behaviour of policy gradient algorithms. Hence, I would have expected, at least, Dr Jekyll (the exploitation agent) to be a policy-based algorithm. As presented currently, I don't really see any connection between the theory and the practical method proposed. For example, the point about the policy gradient being weighted by the stationary distribution doesn't apply to value-based methods anymore. Similarly, the point about policy-based methods having a slow-moving policy (lines 211-218) aren't relevant. \nTo me, this disconnect between the theory and implementation casts doubt on whether these experiments actually support the rest of the paper.\n\nI appreciate that the other experiments were done with an actor-critic method though and those seem to be properly done. The thorough study of various parameters was a good addition.\n\n- About the finite MDP experiments, I didn't see the performance of just Q-learning with exploration bonuses. How does that perform compared to J&H? In a similar vein, what would the performance of just Mr Hyde look like for these experiments? While Mr Hyde only seeks to explore perhaps that would be enough to do well in these domains?\n\n- In the finite MDP experiments, how important is it to decay epsilon for the performance? All the runs for J&H decay epsilon over time, indicating that Jekyll gets chosen more often over time. \n\n- Have you tried a version where Hyde (the exploratory agent) gets to choose all the actions and Jekyll only learns off-policy from the data? In principle, it seems like with the right replay mechanism, this could do well too. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers discussed this paper and came to a consensus that it is a useful contribution and should be accepted. 

There were concerns about the fact that this work is primarily in the tabular setting and novelty relative to existing work. The restriction to the tabular setting is quite limited, in that convergence behavior is known to be quite different for (biased) policy gradient methods in the tabular setting (namely that convergence is still guaranteed, as opposed to under function approximation where there are known counterexamples). An issue raised by a reviewer is in the omission of previous work for off-policy policy gradients, that highlight some of these issues, and that consider a different behavior distribution in the objective (somewhat similarly to what is done here, though it is less general since it is restricted to the distribution under a fixed behavior). This connection should be discussed, and the issue of potential divergence more clearly highlighted. The authors do acknowledge this in the paper, refering to the work on biased actor-critic, but it is somewhat buried. This paper would be improved with a much more explicit discussion about this, and if or how the authors think these results might extend to function approximation.

As mentioned, despite some of these issues, the insights provided, particularly about convergence rates and relationships to the state weightings, are useful. 
Decision: Accept (Poster)