Greedy Actor-Critic: A New Conditional Cross-Entropy Method for Policy Improvement
Authors: Samuel Neumann
Sungsu Lim
Ajin George Joseph
Yangchen Pan
Adam White
Martha White
Venue: ICLR 2023 poster (2023)
Keywords: actor-critic
policy gradient
entropy
cross-entropy method
greedy actor-critic
policy optimization

Abstract: Many policy gradient methods are variants of Actor-Critic (AC), where a value function (critic) is learned to facilitate updating the parameterized policy (actor). The update to the actor involves a log-likelihood update weighted by the action-values, with the addition of entropy regularization for soft variants. In this work, we explore an alternative update for the actor, based on an extension of the cross entropy method (CEM) to condition on inputs (states). The idea is to start with a broader policy and slowly concentrate around maximal actions, using a maximum likelihood update towards actions in the top percentile per state. The speed of this concentration is controlled by a proposal policy, that concentrates at a slower rate than the actor. We first provide a policy improvement result in an idealized setting, and then prove that our conditional CEM (CCEM) strategy tracks a CEM update per state, even with changing action-values. We empirically show that our Greedy AC algorithm, that uses CCEM for the actor update, performs better than Soft Actor-Critic and is much less sensitive to entropy-regularization.

Published as a conference paper at ICLR 2023
GREEDY ACTOR-CRITIC: A NEW CONDITIONAL CROSS-ENTROPY METHOD FOR POLICY IMPROVEMENT
Samuel Neumann, Sungsu Lim, Ajin Joseph, Yangchen Pan, Adam White, Martha White Department of Computing Science University of Alberta
Edmonton, Alberta, Canada is sfneuman uman, amw8, , whitem) @ualberta. ca
ABSTRACT
Many policy gradient methods are variants of Actor-Critic (AC), where a value function (critic) is learned to facilitate updating the parameterized policy (actor). The update to the actor involves log-likelihood update weighted by the action- values, with the addition of entropy regularization for soft variants, In this work, we explore an alternative update for the actor, based on an extension of the cross entropy method (CHM) to condition on inputs (states). The idea is to start with a broader policy and slowly concentrate around maximally valued actions, using a maximum likelihood update towards actions in the top percentile per state. The speed of this concentration is controlled by a proposal policy, that concentrates at a slower rate than the actor. We first provide policy improvement result in an idealized setting, and then prove that our conditional CEM (CCEM) strategy tracks CEM update per state, even with changing action-values. We empirically show that our Greedy AC algorithm, that uses CCEM for the actor update, performs better than Soft Actor-Critic and is much less sensitive entropy-regulaarizatoon.
INTRODUCTION
Many policy optimization strategies update the policy towards the Boltzmann policy. This strategy became popularized by Soft Q-Learning (Haarnoja et al., 2017) and Soft Actor-Critie (SAC) (Haarnoja et al., 2018a), but has a long history in reinforcement learning (Kober & Peters, 2008; Neumann, 20.1). In fact, recent work (Vieillard et al., 2020a; Chan et al., 2021) has highlighted that an broader variety of policy optimization methods can be seen as optimizing either forward or reverse KI. divergence to the Boltzmann policy, in SAC. In fact, even the original Actor-Critic (AC) update (Sutton, 1984) can be seen as optimizing reverse KL divergence, with zero-entropy.
The use of the Boltzmann policy underlies many methods for good reason: it guarantees policy improvement (Haarnoja et al., 201 8a). More specifically, this is the case when learning entropy- regularized action-valuee Q for a policy with regularization parameter T > The Boltzmann policy for state is proportional to exp(Q"(s. (s,(((()))))))) a). The level of emphasis on high-valued actions controlled by r: the higher the magnitude of the entropy level (larger 7), the less the probabilities in the Boltzmann policy are peaked around maximally valued actions.
This choice, however, has several limitations. The policy improvement guarantee is for the entropy- regularized MDP, rather than the original MDP. Entropy regularization is used to encourage explo- ration (Ziebart et al., 2008; Mei et al., 2019) and improve the optimization surface (Ahmed et al., 2019; Shani et al., 2020), resulting in a trade-off between improving the learning process and converging to the optimal policy. Additionally, SAC and other methods are well-known to be sensitive to the entropy regularization parameter (Pourchot & Sigaud, 2019). Prior work has explored optimizing entropy during learning (Haarnoja et al., 201 8b), however, this optimization introduces yet another hyperparameter tune, and this approach may be less performant than simple grid search (see Appendix D). It is reasonable to investigate alternative policy improvement approaches that could potentially improve our actor-critic algorithms.
Code available https: httpps//giii h/tg://itttt comb samuel Fneumann/Greeddyc.

---

Published as a conference paper at ICLR 2023
In this work we propose a new greedification strategy towards this goal. The basic idea is to iteratively take the top percentile of actions, ranked according to the learned action-values, The procedure slowly concentrates on the maximal action(s), across states, for the given action-values. The update itself is simple: N E N actions are sampled according to a proposal policy, the actions are sorted based on the magnitude of the veauus, and the policy is updated to increase the probability of the [pN]] maximally valued actions for E (0, 1). We call this algorithm for the actor Conditional CEM (CCEM), because is an extension of the well-known Cross-Entropy Method (CEM) (Rubinstein, 1999) to condition on inputs'. We leverage theory for CEM to validate that our algorithm concentrates on maximally valued actions across states over time, We introduce GreedyAC, a new AC algorithm that uses CCEM for the actor.
GreedyAC has several advantages over using Boltzmann greedification. First, we show that our new greedification operator ensures policy improvement for the original MDP, rather than different MDP. Second, we can still leverage entropy to prevent policy collapse, but only incorporate it into the proposal policy. This ensures the agent considers potentially optimal actions for longer. but does not skew the actor. In fact, it is possible to decouple the role of entropy for exploration and policy collapse within GreedyAC: the actor could have a small amount of entropy to encourage exploration, and the proposal policy a higher level of entropy to avoid policy collapse. Potentially because of this decoupling, we find that Greedy AC is much less sensitive to the choice of entropy regularizer, as compared to SAC. This design of the algorithm may help it avoid getting stuck in a locally optimal action, and empirical evidence for CEM suggests it can be quite effective for this purpose (Rubinstein & Kroese, 2004). In addition to our theoretical support for CCEM, we provide an empirical investigation comparing Greedy AC, SAC, and a vanilla AC, highlighting that GreedyAC performs consistently well, even in problems like the Mujoco environment Swimmer and pixel-based control where SAC performs poorly.
2 BACKGROUND AND PROBLEM FORMULATION
The interaction between the agent and environment is formalized by Markov decision process A, 7). where 8 is the state space, A is the action space, P : 8 x A S > (0) is the one-step state transition dynamics, R S x A x 8 + IR is the reward function, and E [0, 1] is the discount rate. We assume an episodic problem setting. where the start state Sp ~ dg for start state distribution dn : S > [0, 20) and the length of the episode T' is random, depending on when the agent reaches termination. At each discrete timestep 1 1, 2, T, the agent finds itself some state S, and selects an action A, drawn from its stochastic policy π 8 x A > [0, 2o). The agent then transitions to state S1+1 according to P and observes a scalar reward R R(S,, Ar, S141).
For parameterized policy Rw with parameters w. the agent attempts to maximize the objective J(w) = E.,. |E 7 Re+1), where the expectation is according to start state distribution dg tran- sition dynamics P, and policy Tw Policy gradient methods, like REINFORCE (Williams, 1992), attempt to obtain (unbiased) estimates of the gradient of this objective directly update the policy.
The difficulty is that the policy gradient is expensive to sample, because it requires sampling return trajectories from states sampled from the visitation distribution under Tw. as per the policy gradient theorem (Sutton et al., 1999). Theory papers analyze such an idcalized algorithm (Kakade & Langford, 2002; Agarwal et al., 2021), but in practice this strategy is rarely used. Instead, it is much more common to (a) ignore bias in the state distribution (Thomas, 2014; Imani et al., 2018; Nota & Thomas, 2020) and (b) use biased estimates of the return, in the form of a value function critic. The action-valus function Q" (s( a) E 1>>> 1 7d Re+x = 8, A. = a] is the expected return from a given state and action, when following policy Many PG methods specifically variants of Actor-Criti-eestimae these action-valuee with parameterized Qe a). to use the update Q0 a) V In n (als) or one with bascline (Qo(s,a) [s)) V In Tw (als) where the value function V(s)) is also typically learned. The state s is sampled from a replay buffer, and a ~ Tw (-|s), for the update.
'CEM has been used for policy optimization, but for two very different purposes. It has been used to directly optimize the policy gradient objective (Mannor et al., 2003; Szita & Lörinez, 2006). CEM has also been used to solve for the maximal action running CEM each time we want to find mar' Q(S", a'))-frr for an algorithm called Op- (Kalashnikov et al., 2018). A follow-up up algorithm adds an explicit deterministic policy to minimize a squared error to this maximal action (Simmons-Ean Edler et al., 2019) and another updates the actor with this action rather than the on-policy action (Shao al., 2022). We do not directly use CFM, but rather extend the idea underlying CEM to provide new policy update.
2

---

Published as a conference paper at ICLR 2023
There has been flurry of work, and success, pursuing this path, including methods such as OffPAC (Degris et al., 2012b). SAC (Haarnoja et al., 2018a), SQL (Haarnoja et al., 2017), TRPO (Schulman et al., 2015) and many other variants of related ideas (Peters et al., 2010; Silver et al., 2014; Schulman et al., 2016; Lillicrap et al., 2016; Wang et al., 2017; Gu et al., 2017: Schulman et al., 2017; Abdolmaleki et al., 2018; Mei et al., 2019; Vieillard et al., 2020b). Following close behind are unification results that make sense of this flurry of work (Tomar et al.. 2020; Vieillard et al., 2020a; Chan al., 2021; Lazié et al., 2021). They highlight that many methods include mirror descent component- to minimize KL to the most recent policy-ang and an entropy- regularaauuaiizzaioon component (Vieillard et al., 2020a). In particular, these methods are better thought of as (approximate) policy iteration approaches that update towards the Boltzmann policy, in some cases using mirror descent update. The Boltzmann policy (,Q(s, a) for a given Q is
((,a))
exp(Q(s,a)T a)T B,Q(s,a) = La (sp(Q(s,))TT)))
for entropy parameter т. A T + O, this policy puts all weight on greedy actions. As T + oo, all actions are weighted uniformly. This policy could be directly used as the new greedy policy. However, because it is expensive to sample from B, ((,, a). typically parameterized policy Tw is learned to approximate (sQ a), by minimizing KI. divergence. As the entropy goes to zero, we get an unregularized update that corresponds to the vanilla AC update (Chan et al., 2021).
3 CONDITIONAL CEM
Though using the Boltzmann policy has been successful, it does have some limitations. The primary limitation is that it is sensitive to the choice of entropy (Pourchot & Sigaud, 2019; Chan et al., 2021). A natural question is what other strategies we use for this greedification step in these approximate policy iteration algorithms, and how they compare to this common approach. We propose and motivate a new approach in this section, and then focus the paper on providing insight into its benefits and limitations, in contrast to using the Boltzmann policy.
Let us motivate our approach, by describing the well-known global optimization algorithm called the Cross Entropy Method (CEM) (Rubinstein, 1999). Global optimization strategies are designed to find the global optimum of a general function f(3 for some parameters B. For example, for parameters of neural network, f may be the loss function on sample of data. An advantage of these methods that they do not rely on gradient- hased strategies, which are prone to getting stuck in local optima. Instead, they use randomized search strategies, that have optimality guarantees in some settings (Hu et al., 2012) and have been shown to be effective in practice (Peters & Schaal, 2007; Hansen et al., 2003; Szita& & Lörinez, 2006; Salimans et al., 2017).
CEM maintains a distribution p(3) over parameters 3, iteratively narrowing the range of plausible solutions. The algorithm maintain a current threshold fe, that slowly increases over time it narrows on the maximal B. On iteration t, N parameter vectors 31...., 3y are sample from py; the algorithm only keeps 0i ...., 3% where f(3)) 2 f. and discards the rest. The KL divergence is reduced between Pt and this empirical distribution I = (3)..... )7 for S N. This step corresponds to increasing the likelihood of the 3 in the set f. Iteratively, the distribution over parameters pt narrows around B with higher values under f. To make more likely to find the global optimum, the initial distribution Po is a wide distribution, such as a Gaussian distribution with mean zero po = 0 and a diagonal covariance En of large magnitude.
CEM attempts to find the single-best set of optimal parame- ters for a single optimization problem. The straightforward use in reinforcement learning is to learn the single-best set of policy parameters w (Szita Lörinez, 2006; Mannor et al., 2003). Our goal, however, is to (repeatedly) find maximally valued actions a" conditioned on each state for Q(,,)) -). The global optimization strategy could be run on each step to find the exact best action for each current
Algorithm Distribution(NV, p)
Percentile Empirical
Evaluate and sort in descending order:
Qo a,, 2 2 Qo (iy) return i(S,) = [0;, ....,........................... aip
(where h [pN]]
state, in QT-Opt (Kalashnikov et al., 2018) 8) and follows-ups (Simmons- Ciimmnns-Edlerrae et al., 2019; Shao et al., 2022), but this is expensive and throws away prior information about the function surface obtained when previous optimizations were executed.
3

---

Published as a conference paper at ICLR 2023
We extend CEM to be (a) conditioned state and (b) learned iteratively time. The key modification when extending CEM to Conditional CEM (CCEM), to handle these two key differences, introduce another proposal policy that concentrates more slowly. This proposal policy is entropy- regularized to ensure that we keep a broader set of potential actions when sampling, in case changing action-values very different since the previous update that state. The main policy (the actor) does not use entropy regularization, allowing it to more quickly start acting according to currently greedy actions, without collapsing. We visualize this in Figure I.
In(R(a)))
@e,
+V
Proposal Policy
f"
(++,
v((a)
V E ln(x(a/s))
Time
Policy
Actions
Actions
Actions
Figure 1: In the left figure we see multiple updates for both policies of the CCEM in a single state. We use uniform policies, for interpretability. the rightmost figure, we show an actual progression of CCEM with Gaussian policies, when executed on the action-values depicted in the leftmost figure. The Actor policy (in black) concentrates more quickly than the Proposal policy (in red).
The CCEM algorithm is presented in Algorithm 2. On each step, the proposal policy, ww: (.SS.). (, is sampled provide a of actions dt,..., a a from which we construct the empirical distribution of maximally valued actions. The actor parameters w, are updated using a gradient ascent step on the log-likelihood of the actions i(S.). The proposal parameters w/ are updated using a similar update, but with an entropy regularizer. To obtain ((S)), we select ag C. (a)..... aN) where (SS, of) are in the top (1 (1-p) p) quantile values. For example, for p = 0.2, approximately the top 20% of actions are chosen, with h = [pN]. Implicitly, fz is Qa (S,, af,) for az the action with the lowest value in this top percentile. This procedure is summarized in Algorithm
((S.) -....... 3
Greedy CctorcCritic, in Algorithm 3, puts this all together. We use experience replay, and the CCEM algorithm on mini-batch. The updates involve obtaining the sets i(S) for every S in the mini-batch B and updating with the gradient [B] ESEB Eme((s) V T (a (S. The Sarsa update the critic involves (1) sampling an on-policy action from the actor A' ~ (: (S") for each tuple in the mini- batch and (2) using the update b E(s.A,s RRAA)) (..SAA.S..R.A')BBB (R + (S A') Qo Qo A). Other critic updates are possible; we discuss alternatives and connections to related algorithms in Appendix A.
Algorithm 2 Conditional CEM for the Actor
Algorithm 3 Greedy Actor-Critic
Input: S, and Qe. N N, p E (0, 1) if actions discrete and | < 1/p then i(S.) arg max (S(S.aa)
Initialize parameters 8, w, w', replay buffer B Obtain initial state S while agent interacting with the environment do
else
Sample N actions a; न. (-1{)) Obtain ((S)) using Algorithm end if
Take action A ~ (:[S), observe R, S" Add (5, A, S" R)) the buffer B Grab random mini-batch B from buffer B Update using Sarsa for policy Tw on B Update w' using Algorithm 2 on B. end while
w c w + ap,t Enel(s)) V In (a
w' "''++0pp. Enci(s.) V in
-V Ft Hit
CCEM for Discrete Actions. Although we can use the same algorithm for discrete actions, we can make it simpler when have small number of discrete actions. Our algorithm is designed around
4

---

define the percentile-greedy policy as Published as a conference paper at ICLR 2023
the fact that it is difficult to solve for the maximal action for Qo(Si, a) for continuous actions; slowly identify this maximal action across states. For small set of discrete actions, it is easy to get this maximizing action. If [ 1/p. then the top percentile consists of the one top action (or the top actions if there are ties); we can directly set I(S))) arg max Qo(S,, a) and do not need to maintain proposal policy. For this reason, we focus our theory on the continuous-action setting, which is the main motivation for using CEM for the actor update.
4 THEORETICAL GUARANTEES
In this section, we motivate that the target policy underlying CCEM guarantees policy improvement, and characterize the ODE underlying CCEM. We show tracks a CEM update in expectation across states and slowly concentrates around maximally valued actions even while the action-values are changing.
4.1 POLICY IMPROVEMENT UNDER AN IDEALIZED SETTING
We first consider the setting where we have access to Q", as is typically done for characterizing the policy improvement properties of an operator (Haarnoja et al., 2018a; Ghosh al., 2020; Chan et al., 2021) as well as for the original policy improvement theorem (Sutton & Barto, 2018). Our update moves our policy towards percentile-gree
policy that redistributes probability solely the (1 p)-uunteele according to magniuudes under Q(s, a). More formally, let fQ s) be the threshold such that 2 18 (x:))) {{ass)da = p. namely that gives the set of actions in the top 1 p quantile, according to magnitudes under ((+,-) Then
x (als)/p
((s,a) 2 thresh (T;
Ta(a|s, Q,
else
where diving by P renormalizes the distribution. Computing this policy would be onerous; instead, we only sample the KL divergence to this policy, using sample percentile. Nonetheless, this percentile-greedy policy represents the target policy that the actor updates towards (in the limit of samples N for the percentile).
Intuitively, this target policy should give policy improvement, as it redistributes weight for low valued actions proportionally to high- actions. We formalize this in the following theorem. We write (als) instead Tp(als, s,, ()), when it is clear from context.
Theorem 4.1. For given policy action-value Q and p > O, the percentile-greedy policy xp in π and QT is guaranteed to be at least as good as all states:
f x Ta(als (" +)** a), 2 [ ((als)("((
(s, as,a
Proof. The proof is a straightforward modification of the policy improvement theorem. Notice that
/ TT(alss( a)da (s,a)da
ग [ 9) Q" a)da
/ T(al ((aal))(((ss as,a)da
(1
by the definition of percentiles, for any state s. Rewriting Ja (s, (2= A)],
(s) E, 5= (s, A)] s Ex, 10T (s, A)] Ex, [Re41 +Ex (S A41)|S E RR41 ME,,, [2 (S A++1))
< E., RR41 + RR+4 + 7 E, [Q (St+2, A1+2) ) =
S Ex,, (Re41 + Re42 + 7² RR43 + T....TTT11 Rr St = = = ( A)] V (s)
This result is sanity check ensure the target policy sensible in our update. Note that the Boltzmann policy only guarantees improvement under the catropy-rgullaizzed action-values.
5

---

Published as a conference paper at ICLR 2023
4.2 CCEM TRACKS THE GREEDY ACTION
Beyond the idealized setting, we would like to understand the properties of the stochastic algorithm. CCEM is not gradient descent approach, so we need to reason about its dynamics namely the underlying ODE. We expect CCEM to behave like CEM per state, but with some qualifiers. First, CCEM uses parameterized policy conditioned action distributions per state. CEM, on the other hand, does not account for such aliasing. We identify conditions on the parameterized policy and use ODE that takes expectations over states.
state, meaning that there is aliasing between the
Second, the function we are attempting to maximize is also changing with time, because the action- values are updating. We address this issue using two-timescale stochastic approximation approach, where the action-values Qo change more slowly than the policy, allowing the policy to track the maximally valued actions. The policy itself has two timescales, to account for its own parameters changing at different timescales. Actions for the maximum likelihood step are selected according to older (slower) parameters w', so that it is as if the primary (faster) parameters w are updated using samples from fixed distribution. These two policies correspond to our proposal policy (slow) and actor (fast).
We show that the ODE for the CCEM parameters w, is based on the gradient
V Vw(esEssww.Aw ( (-15) (200s In Twit)
(A[S)]
where 0 and w' are changing at slower timescales, and effectively fixed from the perspective of the faster changing w.. The term per-state is exactly the update underlying CEM, and so we can think of this ODE as one for an expected CEM Optimizer, across states for parameterized policies. We say that CCEM tracks this expected CEM Optimizer, because @ and w' are changing with time.
We provide an informal theorem statement here for Theorem B.1, with proof-sketch. The main result, including all conditions, is given in Appendix B. We discuss some of the (limitations of the) conditions after the proof sketch.
Informal Result:
Let Or be the action-value parameters with stepsize Cgg, and w, be the policy parameters with stepsize Ca,,t, with w/ a more slowly changing set of policy parameters set to ''',)'' + '',,,, for stepsize d',t E 10. Assume: (1) States S, are sampled from
= (1- w/= fixed marginal distribution. (2) V In ww (-[s) is locally Lipschitz w.r.t. w, Vs E S. (3) Parameters W, and 0, remain bounded almost surely. (4) Stepsizes are chosen for three different timescales: we evolves faster than w/ and w/ evolves faster than O,. Under these four conditions, the CCEM Actor tracks the expected CEM Optimizer.
Sketch: The stochastic update to the Actor is not a direct gradient-descent update. Each update to the Actor is a CEM update, which requires a different analysis to ensure that the stochastic noise remains bounded and is asymptotically negligible. Further, the classical results of CEM also do not immediately apply, because such updates assume distribution parameters can be directly computed. Here, distribution parameters are conditioned on state, as outputs from parametrized function. We identify conditions on the parametrized policy to ensure well-behaved CEM updates.
The multi-timescale analysis allows to foeus on the updates of the Actor w., assuming the action- value parameter 0 and action setion-sampling parameter w' are quasi-static. These parameters are allowed to change with time-as they will in practice-but are moving at a sufficiently slower timescale relative to w, and hence the analysis can be undertaken as if they are static.
The first step in the proof simply meaning a stochastic update where after each update the weights are projected to compact, convex set keep them bounded. The stochastic recursion reformulated into summation involving the mean vector field g (w:) (which depends on the action-value parameters 0), martingale noise, and a loss term E that is due to having approximate quantiles. The key steps are then to show almost surely that the mean vector field g" is locally Lipschitz, the martingale noise is quadratically bounded and that the loss term Ee decays to zero asymptotically. For the first and second, we identify conditions the policy parameterization that guarantee these. For the final case, we adapt the proof for sampled quantiles approaching true quantiles for CEM, with modifications to account for expectations over the conditioning variable, the state.
formulate the update to the weights a projected stochastic recursion-
This result has several limitations. First, it does not perfectly characterize the CCEM algorithm that actually use. We do not use the update w/ = (1 d'a)) + a' We, and instead entropy
6

---

Published as a conference paper at ICLR 2023
regularization to make w/ concentrate more slowly than wy- The principle is similar; empirically found entropy regularization to be an effective strategy to achieve this condition.
Second, the theory assumes the state distribution is fixed, and not influenced by Tw- It is standard to analyze the properties of (off-policy) algorithms for fixed datasets as a first step, as was done for Q-learning (Jaakkola et al., 1994). It allows to separate concerns, and just ask: does our method concentrate on maximal actions across states? An important next step is to characterize the full Greedy Actor-Critic algorithm, beyond just understanding the properties of the CCEM component.
5 EMPIRICAL RESULTS
We are primarily interested in investigating sensitivity to hyperparameters. This sensitivity reflects how difficult it can be get AC methods working on new relevanlevnnt for both applied settings and research. AC methods have been notoriously difficult to tune due to the interacting time scales of the actor and critic (Degris al., 2012a), further compounded by the sensitivity in the entropy scale. The use of modern optimizers may reduce some of the sensitivity in stepsize selection; these experiments help understand if that is the case. Further, a very well-tuned algorithm may not be representative of performance across problems. We particularly examine the impacts of selecting a single set of hyperparameters across environments, in contrast to tuning per environment.
We chose to conduct experiments in small, challenging domains appropriately sized for extensive experiment repetition. Ensuring significance in results and carefully exploring hyperparameter sensitivity required many experiments. Our final plots required ~30,000 runs across all environments, algorithms, and hyperparameters. Further, contrary to popular belief, classic control domains are challenge for Deep RL agents (Ghiassian et al., 2020), and performance differences in these environments have been shown to extend to larger environments (Obando-Cert & Castro, 2021).
5.1 ALGORITHMS
We focus on comparing GreedyAC to Soft Actor-Critic (SAC) both since this allows us to compare to method that uses the Boltzmann target policy on action-values and because SAC continues to have the most widely reported success?. We additionally include VanillaAC as a baseline, a basic AC variant which does not include any of the tricks SAC utilizes to improve performance, such as action reparameterization to estimate the policy gradient or double Q functions to mitigate maximization bias. For discrete actions, policies are parameterized using Softmax distributions. For continuous actions, policies are parameterized using Gaussian distributions, except SAC which uses squashed Gaussian policy as per the original work. We tested SAC with a Gaussian policy, and it performed worse. All algorithms use neural networks. Feedforward networks consist of two hidden layers of 64 units (classic control environments) or 256 units (Swimmer-v3 environment). Convolutional layers consists of convolutional layer with 3 kernels of size 16 followed by a fully connected layer of size 128. All algorithms use the Adam optimizer (Kingma & Ba, 2014), experience replay, and target networks for the value functions. See Appendix C. for full discussion of hyperparameters.
5.2 ENVIRONMENTS
We use the classic versions of Mountain Car (Sutton & Barto, 2018), Pendulum (Degris et al., 20),a), and Acrobot (Sutton & Barto, 2018). Each environment is run with both continuous and discrete action spaces; states are continuous. Discrete actions consist of the two extreme continuous actions and O. All environments use discount factor of 0.99, and episodes are cut off at 1,000 timesteps, teleporting the agent back to the start state (but not causing termination). To demonstrate the potential of GreedyAC AC scale, & Tian, 2019) as well as on Swimmer-v3 from OpenAl Gym (Brockman et al., 2016). On MinAtar, episodes cutoff at 2,500 timesteps.
also include experiments on Freeway and Breakout from MinAtar (Young
In Mountain Car, the goal is to drive an underpowered car up a hill. State consists of the position in 1.2, 0.6) and velocity in [-0.7, 0.7]. The agent starts in random position in [-0.6, -0.4| and velocity 0. The action is the force to apply to the car, in 1]. The reward is -1 per step.
In Pendulum, the goal is hold a pendulum with fixed base in vertical position. State consists of the angle (normalized in [-TT, x)) and angular momentum (in [-1, 1).. The agent starts with the pendulum facing downwards and 0 velocity. The action is the torque applied to the fixed base, in 2.. The reward is the cosine of the angle of the pendulum from the positive y-axis.
"See https: / http://spinnnnnnn.c.oo openai cww. en/ wtwp//aaett//tttt .ctm/////aatst//ppaiiii/ www.nnninnnnn/nn /bncch/benhhhhmm html
7

---

Published as a conference paper at ICLR 2023
In Acrobot, the agent controls doubly-linken pendulum with fixed base. The goal is swing the second link one link's 's length above the fixed base. State consists of the angle of each link (in [-,,, x)) and the angular velocity of each link (in [-4x, 4x] and [-9I, 9T] respectively). The agent starts with random angles and angular velocities in [-0.1, 1, 0.1]. The action is the torque applied to the joint between the two links, in [-1, 1]. The reward is 11 per step.
5.3 EXPERIMENTAL DETAILS
We sweep hyperparameters for 40 runs, tuning over the first 10 rums and reporting results using the final 30 runs for the best hyperparameters. We sweep critic step size a = 10 for I E {-5, -4, -.,...,.... We sweep For the classic control experiments, we used fixed batch sizes of 32 samples and replay buffer capacity of 100,000 samples. For the MinAtar experiments, we used fixed batch sizes of 32 samples and a buffer capacity of million. For the Swimmer experiments,
We set the actor step size to be x a and sweep K E {10-3 10-2 1,,
entropy scales 5 = 10" for y E {-3, -2 0, 1}.
used fixed batch sizes of 100 samples and buffer capacity of million. For CCEM, we fixed p = 0.1 and sample N 30 actions.
To select hyperparameters across environment, we must normalize performance provide an aggregate score. We use near-optimal performance as the normalizer for each environment, with score of I meaning equal to this performance. We only use this normalization to average scores across environments. We report learning curves using the original unnormalized returns. For more details, see Appendix C.2.
5.4 RESULTS
Per-environment Tuning: We first examine how well the algorithms can perform when they are tuned per- environment. In Figure 2, we see that SAC performs well in Pendulum-CA (continuous actions) and in Pendulum- DA (discrete actions) but poorly the other settings. SAC learns slower than GreedyAC and VanillaAC on Acrobot. GreedyAC performs worse than SAC in Pendulum-CAA but still performs acceptably, nearly reaching the same final performance. SAC performs poorly both versions of Mountain Car. That AC methods struggle with Acrobot common wisdom, but here we see that both Greedy and VanillaAC do well on this problem. GreedyAC is the clear winner in Mountain Car.
Acrobot
Mountain
Pendulum
Continuous
250
1100
1000
-300
1000
Averops soum
Discrete
-200
-55
Tirentess
Timasteos
Timentpee
Figure 2: Learning curves when tuning hyperparameters per- environment. averaged over 30 runs with standard errors.
Across-envinee eerrooennvronmmet Tuning: We next examine the performance of the algorithms when they are forced to se-
Acrobot
Mountain Car
Pendulum
-200
200
Merra Ruttin
Continuous
lect one hyperparameter setting across continuous- or discrete-action envi- ronments separately, shown in Fig- ure 3. We expect algorithms that are less sensitive their parameters to suffer less degradation. Under this regime, GreedyAC has clear advan- tage over SAC. GreedyAC maintains acceptable performance across all en- vironments, sometimes learning more slowly than under per-environment tuning, but having reasonable behavior.
becoaae Nours
Discelle
250
Cranbyic
-1000
3000
Strt BeAA
Timestops
Munndees of Thousands)
(Hundreda Thousandal
(fundress Thousands))
Figure 3: Learning curves when tuning hyperparameters across-nniiromeens, averaged over 30 runs with standard errors.
SAC performs poorly two-thirds of the environments. GreedyAC is less sensitive than VanillaAC under across-environment tuning and performs at least as good as VanillaAC.
8

---

Published as a conference paper at ICLR 2023
Hyperparameter Sensitivity: We examine the sensitivity of GreedyAC and SAC to their entropy scales, focusing on the continuous action environments. We plot sensitivity curves, with one plotted the x-axis and average return across all steps and all 40
for each entropy scale, with the stepsize runs on the y-axis. Because there are two stepsizes, we have two sets of plots. When examining the sensitivity to the critic stepsize, we select the best actor stepsize. We do the same for the actor stepsize plots. We provide the plots with individual lines in Appendix C.3 and here focus on a more summarized view.
Figure 4 depicts the range of perfor- mance obtained across entropy scales. The plot is generated by filling in the region between the curves for each en- tropy scale. If this sensitivity region is broad, then the algorithm performed very differently across different en- tropy scales and so is sensitive to the entropy. SAC has much wider sensi- tivity regions than GreedyAC. Those of ArreddyC are generally narrow, in- dicating that the stepsize rather than entropy was the dominant factor. Fur- ther, the bands of performance are generally the top of the plot. When SAC exhibits narrower regions than Greedy those regions are lower on the plot, indicating overall poor performance.
Acrobot
Mountain Car
Pendulum
100
GreedyAC
-1000
100
SAC
-50
-1000
Onticc Stee (209
Crttc Stea 1109
Crttcc
Figure 4: A sensitivity region plot for entropy, for GreedyAC (top row) and SAC (bottom row) in the continu- ous action problems.
SCALING GREEDY-AS AC
Freeway
Breakout
Online
Offline
150
averggr Mann
SAC
20
Greacyii
Timescpps gilllon))
Thmeetpp (Milllon))
Timestops (Millons)
Timestaps (Millions)
(a) Pixel-based control on MinAtar
(b) Learning curves on Swimmer over 10 runs, red line denotes SAC's final performance
Figure 5: Comparing Greedy and SAC in more challenging environments
We ran GreedyAC on two pixel-based control problems, Breakout and Freeway, from the MinAtar suite (Young& & Tian, 2019). Recent work has shown that MinAtar results are indicative of those in much larger scale problems (Obando-Cero) & Castro, 2021). We set the actor step-size scale to 1.0 and critic size of -3 for both GreedyAC and SAC-the defaults of SAC. We set the entropy scale of SAC to 10 based on a grid search. Figure 5a above clearly indicates GreedyAC can learn good policy from high- nigh-dimensional inputs; comparable performance to DQN Rainbow.
Finally, we ran GreedyAC on Swimmer-v3 from OpenAl Gym (Brockman et al., 2016). We tuned over one run and then ran the tuned hyperparameters for an additional runs to generate Figure 5b. We report online and offline performance. Offline evaluation is performed every 10,000 steps, for 10 episodes, where only the mean action selected and learning is disabled. We report SAC's final performance Swimmer from the SpinningUp benchmark Greedy AC is clearly not state-of-the-art here moot methods are not-however, Greedy AC steadily improves throughout the experiment.
7 CONCLUSION
In this work, we introduced new Actor-Critic (AC) algorithm called Greedy AC, that uses new update to the Actor based on an extension of the cross-entropy method (CEM). The idea is to (a) define a percentile- greedy target policy and (b) update the actor towards this target policy, by reducing a KL divergence to it. This percentile-greed, policy guarantees policy improvement, and we prove that our Conditional CEM algorithm tracks the actions of maximal value under changing action-values. We conclude with in-depth empirical study, showing that Greedy AC has significantly lower sensitivity to its hyperparameters than SAC does.
See https: http::///sinnnnguuie maniingu--ppnnee http://cccccco///aaattaaaaai//ia
html

---

Published as a conference paper at ICLR 2023
REFERENCES
Abbas Abdolmalcki, Jost Tobias Springenberg. Yuval Tassa, Remi Munos, Nicolas Heess, and Martin Riedmiller. Maximum a posteriori policy optimisation. In International Conference on Learning Representations, 2018.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-766 2021.
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact of entropy on policy optimization. In International Conference on Machine Learning. 2019.
Vivek S Borkar. Stochastic approximation with two time scales. Systems Control Letters, 29(5). 1997.
Vivek S. Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, 2008
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym, 2016.
Alan Chan, Hugo Silva, Sungsu Lim, Tadashi Kozuno, A. Rupam Mahmood, and Martha White. Greedification operators for policy optimization: Investigating forward and reverse kl divergences. In arXiv:2107.082855 2021.
Thomas Degris, Patrick M Pilarski, and Richard S Sutton. Model-free reinforcement learning with continuous action practice. In American Control Conference, 2012a
Thomas Degris, Martha White, and Richard S. Sutton. Off-policy actor-critic. International Conference Machine Learning, 2012b.
Richard Durrett. Probability: Theory and Examples (Wadsworth and Brooks/Cole Statis- tics/Probability Series). Wadsworth & Brooks/Cole Advanced Books & Software, 1991.
Amir-massoud Farahmand, Doina Precup, André MS Barreto, and Mohammad Ghavamzadeh. Classification based approximate policy iteration. IEEE Transactions on Automatic Control, 2015.
Sina Ghiassian, Banafsheh Rafice, Yat Long Lo, and Adam White. Improving performance in reinforcement learning by breaking generalization in neural networks. International Conference on Autonomous Agents and Multiagent Systems, 2020.
Dibya Ghosh, Marlos C. Machado, and Nicolas Le Roux. An operator view of policy gradient methods. In Advances Neural Information Processing Systems, 2020.
Shixiang Gu, Timothy P. Lillicrap, Zoubin Ghahramani, Richard E. Turner, and Sergey Levine Q-prop: Sample-effcient policy gradient with off-policy critic. In International Conference on Learning Representations, 2017.
Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. International Conference on Machine Learning, 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International Conference on Machine Learning, 2018 8a.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, and Sergey Levine. Soft actor-critic algorithms and applications. arXiv preprint arXiv: / 8.20505, 2018b.
Nikolaus Hansen, Sibylle D. Müller, and Petros Koumoutsakos. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (cma-es). Evolutionary Computation, 11(1), 2003.
10

---

Published as a conference paper at ICLR 2023
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301), 1963.
Tito Homem-de Mello. A study on the cross-entropy method for rare-event probability estimation. INFORMS Journal on Computing. 19(3), 2007.
Jiaqiao Hu, Michael Fu, and Steven Marcus, A model reference adaptive search method for global optimization. Operations Research, 55(3), 2007.
Jiaqiao Hu, Ping Hu, and Hyeong Soo Chang. A stochastic approximation framework for a class of randomized optimization algorithms. IEEE Transactions on Automatic Control, 57(1), 2012.
Ehsan Imani, Eric Graves, and Martha White. An off-policy policy gradient theorem using emphatic weightings. In Advances Neural Information Processing Systems, 2018.
Tommi Jaakkola, Michael Jordan, and Satinder P Singh. On the convergence of stochastic iterative
dynamic programming algorithms. Neural compulation, (66):1185-122) 1994.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference Machine Learning. 2002.
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, and Sergey Levine. Qt-opt: Scalable deep reinforcement learning for vision-based robotic manipulation. In Conference on Robot Learning, 2018.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2014.
Jens Kober and Jan R Peters. Policy search for motor primitives in robotics. In Advances in Neural Information Processing Systems, 2008.
Harold Kushner and Dean S. Clark. Stochastic Approximation Methods for Constrained and Unconstrained Systems. Springer Science & Business Media, 2012.
Michail G Lagoudakis and Ronald Parr. Reinforcement learning classification: Leveraging modern classifiers. In International Conference on Machine Learning, 2003.
Alessandro Lazaric, Mohammad Ghavamzadeh, and Rémi Munos. Analysis of a classification- policy iteration algorithm. In International Conference on Machine Leurning, 2010.
Nevena Lazić, Botao Hao, Yasin Abbasi- Yadkori, Dale Schuurmans, and Csaba Szepesvári. Opti- mization issues in kl-constrained approximate policy iteration. arXiv preprint arXiv:2102.0622 2021.
Timothy P Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In International Conference Learning Representutions, 2016.
Shie Mannor, Reuven Rubinstein, and Yohai Gat. The cross entropy method for fast policy search. In International Conference on Machine Learning, 2003.
Jincheng Mei, Chenjun Xiao, Ruitong Huang, Dale Schuurmans, and Martin Müller. On princi- pled entropy exploration in policy optimization. In International Joint Conference on Artificial Intelligence, 2019.
Carl N Morris. Natural exponential families with quadratic variance functions. The Annals of Statistics, 1982.
Gerhard Neumann. Variational inference for policy search in changing situations. In International Conference on Machine Learning. 2011.
Chris Nota and Philip S. Thomas. Is the policy gradient a gradient? In International Conference on Autonomous Agents and Multiagent Systems, 2020.

---

Published as a conference paper at ICLR 2023
Johan S Obando- Ceron and Pablo Samuel Castro. Revisiting rainbow: Promoting more insightful and inclusive deep reinforcement learning research. In International Conference on Machine Learning, 2021.
Emilio Parisotto, Jimmy Lei Ba, and Ruslan Salakhutdinov. Actor-mimic: Deep multitask and transfer reinforcement learning, In International Conference on Learning Representations, 2016.
Jan Peters and Stefan Schaal. Reinforcement learning by reward-weighted regression for operational space control. In International Conference on Machine Learning, 2007.
Jan Peters, Katharina Mülling, and Yasemin Altün. Relative entropy policy search. In AAAI
Conference on Artificial Intelligence, 2010.
Aloïs Pourchot and Olivier Sigaud. Cem-rl: Combining evolutionary and gradient-based methods for policy search. In International Conference on Learning Representations, 2019.
Herbert Robbins and Sutton Monro. stochastic approximation method. In Herbert Robbins Selected Papers. Springer, 1985.
Reuven Rubinstein.
The cross-entropy method for combinatorial and continuous optimization. Methodology And Computing In Applied Probability, 1(2), 1999.
Reuven Rubinstein and Dirk P Kroese. The cross-entropy method: a unified approach to com- binatorial optimization, Monte-Carke simulation, and machine learning, volume 133. Springer, 2004.
Reuven Rubinstein and Alexander Shapiro. Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method, volume 1. Wiley New York, 1993.
Tim Salimans, Jonathan Ho, Xi Chen, and Ilya Sutskever. Evolution strategies a scalable alternative 2017.
to reinforcement learning. arXiv preprint
John Schulman, Sergey Levine, Picter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, 2015.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. International Conference on Learning Representations, 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms.
2017.
Pranab K Sen and Julio M Singer. Large Sample Methods in Statistics (1994): An Introduction with Applications. CRC Press, 2017.
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In AAAI Conference on Artificial Intelligence, 2020.
Lin Shao, Yifan You, Mengyuan Yan, Shenli Yuan, Qingyun Sun, and Jeannette Bohg. Self-guided and self-regularized actor-critic. In Conference Robot Learning, 2022.
Grac:
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International Conference on Machine Learning, 2014.
Riley Simmons-Edler, Ben Eisner, Eric Mitchell, Sebastian Seung, and Daniel Lee. Q-learning for continuous actions with cross-entropy guided policies. In RLARealLife Workshop at the International Conference on Machine Learning, 2019.
Denis Steckelmacher, Hélène Plisnier, Diederik M Roijers, and Ann Nowé. Sample-efficient model- free reinforcement learning with off-policy critics. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, 2019.
Wen Sun, Geoffrey J Gordon, Byron Boots, and J Bagnell. Dual policy iteration. Advances in Neural Information Processing Systems, 31, 2018.
12

---

Published as a conference paper at ICLR 2023
Richard S. Sutton. Temporal Credit Assignment in Reinforcement Learning. PhD thesis, University of Massachusetts Amherst, 1984.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
Richard S. Sutton, David A. McAllester, Satinder P. Singh, and Yishay Mansour. Policy gradi- ent methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, 1999.
István Szita and András Lörinez. Learning tetris using the noisy cross-entropy method. Neural Computation, 18(12), 2006.
Philip Thomas. Bias in natural actor-critic algorithms. In International Conference Machine Learning, 2014.
Manan Tomar, Lior Shani, Yonathan Efroni, and Mohammad Ghavamzadeh. Mirror descent policy optimization. arXiv preprint 1/Xiv:20050098// 2020.
Nino Vieillard, Tadashi Kozuno, Bruno Scherrer, Olivier Pietquin, Remi Munos, and Matthieu Geist. Leverage the average: analysis of kl regularization in reinforcement learning. In Advances in Neural Information Processing Systems, 2020a.
Nino Vieillard, Olivier Pietquin, and Matthieu Geist. Deep conservative policy iteration. In AAAI Conference on Artificial Intelligence, 2020b.
Ziyu Wang, Victor Bapst, Nicolas Heess, Volodymyr Mnih, Remi Munos, Koray Kavukcuoglu, and Nando de Freitas. Sample efficient actor-critic with experience replay, International Conference on Learning Representutions, 2017.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3-4), 1992.
Kenny Young and Tian Tian. Minatar: An atari-inspired testbed for thorough and reproducible reinforcement learning experiments. arXiv preprint 1903v:1903033177 2019.
Brian D Ziebart, Andrew L Maas, Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement learning. In AAAI Conference on Artificial Intelligence, 2008
A RELATED POLICY OPTIMIZATION ALGOIIHTMM
As mentioned in the main text, there are many policy optimization algorithms that can be seen as approximate policy iteration (API) rather than performing gradient descent on policy objective. An overview and survey are given by Vieillard et al. (2020a) and Chan et al. (2021). There, many methods are shown to either minimize a forward or reverse KL-divergence to the Boltzmann policy. Our approach similarly updates the actor using a KL-divergence target policy is the percentile-gee greedy policy. By doing a maximum likelihood update with actions sampled under the percentile-greddy policy, we are reducing the forward KL-divergence to the percentile-greedy policy in Equation 2.
target policy, but here that
Our CCEM update for the actor is new, but there several approaches that resemble the idea, particularly those that try to match an expert. This includes dual policy iteration methods (DPI) (Parisotto al., 2016; Sun et al., 2018; Steckelmacher al., 2019) and RL as classification methods (Lagoudakis & Parr, 2003; Lazaric et al., 2010; Farahmand et al., 2015). DPI has two policies, one which is guiding the other. For example, one policy might be an expensive tree search and another learned neural network, trained to mimic the first (expert or guide) policy. CCEM, on the other hand, uses two policies differently. Our actor does not imitate our proposal policy. Rather, the proposal policy is used to improve the search over the nonconcave surface of Q. It samples actions more broadly, to make it more likely to find a maximizing action. Further, the actor increases the likelihood of only the top actions and does not imitate the proposal policy. In contrast, Bootstrap DPI (Steckelmacher et al., 2019, Equation 5) uses an update based on Actor-Mimic (Parisotto et al., 2016), where the policy increases likelihood of actions for the softmax policies it is trying to mimic The
13

---

Published as a conference paper at ICLR 2023
resemblance arises from the fact that (Steckelmacher et al., 2019. Equation 5) over forward KL divergences to softmax policies (for discrete actions), just like we have a forward KL divergence but to the percentile-greese policy (for discrete continuous actions).
can be
sum
The other class of algorithms, RL as classification, also look similar due to using a forward KL divergence. They reduce the problem to identifying "positive" actions in state (producing maximal returns) and "negative" actions in a state (producing non-maximal returns). a cross-entropy loss is used, then this corresponds maximizing the likelihood of the positive actions and minimizing the likelihood of the negative ones. More generally, other classification algorithms can be used that do not involve maximizing likelihood (like SVMs). The RL as classifications algorithms primarily focus on how to obtain these positive and negative actions, and otherwise look quite different from Greedy AC, addition to being restricted to a discrete set of actions.
Finally, we can also consider the connection to Conservative Policy Iteration (CPI) (Kakade & Langford, 2002) and a generalization called Deep CPI (Vieillard et al., 2020b). CPI updates the policy to be an interpolation between the greedy policy G(Q) and the current policy æ, get the new policy n' = (1 a)T i + aG((Q) for E [0, 1]. Deep CPI extends this idea to parameterized policies, instead minimizing a forward KL to this interpolation policy. Greedy AC could be seen as another way to obtain a conservative update, because it does not move the actor all the way to the greedy policy. Instead, it moves towards the prreentile-gredd policy (in Equation 2), which shifts probability to the upper percentile of actions. Similarly to the interpolation policy, this percentile-greedt policy depends the previous policy and increasing probability for maximally valued actions. As yet, Deep CPI has not been shown to enjoy the same theoretical guarantees as CPI: minimizing a forward KL to the interpolation policy does not provide the same guarantees. It remains open question how to implement this conservative update in deep RL, and it would be interesting to understand if the CCEM update could provide an alternative route to obtaining such guarantees.
B CONVERGENCE ANALYSIS OF THE ACTOR
We provided an informal proof statement and proof sketch in Section 4.2, provide intuition for the result. Here, we provide the formal proof in the following subsections. We first provide some definitions, particularly for the quantile function which is central to the analysis. We then lay out the assumptions, and discuss some policy parameterizations to satisfy those assumptions. We finally state the theorem, with proof, and provide one lemma needed to prove the theorem in the final subsection.
B. NOTATION AND DEFINITIONS
Notation: For set A, let À represent the interior of A, while 0A is the boundary of A. The abbreviation 0.8. stands for almost surely and i.o. stands for infinitely often. Let represent the set 1, 1, 2,....... }. For a set A, we let LA to be the indicator function//haraacterstti function of A and is defined as (xx = 1 if æ E A and O otherwise. Let Eg[.]. 1/[+] and PP (-) denote the expectation, variance and probability measure w.r.f g. For a-filld F. let [[- represent the conditional expectation w.r.f. F. A function f X + Y is called Lipschitz continuous if 3L E (0, oc) s.t. [[f(x)) (xx) S L||x] x2 ll. Vx1 X2 E X. A function f is called locally Lipschitz continuous if for every X, there exists neighbourhood U of X such that fiv is Lipschitz continuous. Let C(X,Y) Y) represent the space of continuous functions from X to Y. Also, let (x) represent an open ball of radius r with centered at x. For a positive integer M, let [M] = (1,2... M).
Definition 1. function P: C IR + V C IR Frechet differentiable at x if there exists a bounded linear operator Fx IR + RRd2 such that the limit
T(x tyy
lim <40 e
exists and is equal to i (x)). We say I' is Frechet differentiable if Frechet derivative of exists at every point in its domain.
Definition 2. Given a bounded real-valued contimuous function H. : IR - R. with H(a) E [H, H.] and scalar p [0, 1), we define the -qqquntille ((A) w.r.t. the PDF g (denoted as (P
14

---

Published as a conference paper at ICLR 2023
as follows:
())
sup (P 2 2 p),
(4)
BE(Ht.H.]
where Pg the probability measure induced by the PDF g. i.c. for Borel set A, P Po( Ja g(a)da.
=
This quantile operator will be used to succinctly write the quantile for Qo(S, :), with actions selected according to Tw. i.e.,
f/ (W(:s) =
sup {I (-1s)
(1)) A) p}.
(5)
RE(O Q.11
B.2 ASSUMPTIONS
Assumption 1. Given realization of the transition dynamics of the MDP in the form of a sequence of transition tuples @ = {(Sr, Ar, Rr, St))eeN, where the state St 8 drawn using a latent sampling distribution
while A, EA is the action chosen at slate St, the transitioned state S P(S, Ac;:) and the reward IR 3 Rg = R(S,, Ar, St). We further assume that the reward is uniformly bounded, i.c. (R(-,,))] Rmax 00.
We analyze the long run behaviour of the conditional cross-entropy recursion (actor) which is defined follows:
W141 = rw
We aa,t N₂
1
Σ (Q, Vw. In T (A (s)) y.
(6)
AEE;
where E, {Ai,1, At. AcN. Rd Tw/ (-1Se).
W4+1 w/ a'a, (We+1 - w())
(7)
Here, [' is the projection operator onto the compact (closed and bounded) and convex set W C IR" with smooth boundary OW. Therefore, rW maps vectors in IR" the nearest vectors in W w.r.t the Euclidean distance (or equivalent metric). Convexity and compactness ensure that the projection unique and belongs to W.
Assumption 2.
The pre-determined, deterministic, step-size sequences taa,then, ta and { JeeN heN are positive scalars which satisfy the following:
Σ Go.t > L'
Σ Ag.. =
LEN
IEN
YEN
Σ LEN
02 + a a,t
og
Cn.t
0, lim Qgg.t
lim 1-000 Ca.
0.
1-000 Ca.1
The first conditions in Assumption 2 the classical Robbins-Monre conditions (Robbins & Monro, 1985) required for stochastic approximation algorithms. The last two conditions enable the different stochastic recursions have separate timescales. Indeed, it ensures the Wt recursion is faster compared to the recursions of 0, and w/. This timescale divide is needed to obtain the desired asymptotic behaviour, as we describe the next section.
Assumption 3. The pre-determined, deterministic, sample length schedule (Nr NJEN positive and strictly monotonically increases to oo and inf.EN
Not1
1.
Nr
Assumption 3 states that the number of samples increases to infinity and is primarily required to ensure that the estimation error arising due the estimation of sample quantiles eventually decays to Practically, one can indeed consider a fixed, finite, positive integer for N, which is large enough to accommodate the acceptable error.
15

---

Published as a conference paper at ICLR 2023
Assumption 4. The sequence {9t) hey satisfies 0, 6, where O C IR" is convex, compact set. flso.for E θ let Qo(s, a) E [Q] Qul. vs E S, A.
Assumption 4 assumes stability of the Expert, and minimally only requires that the values remain in bounded range. We make additional assumptions the convergence properties of the Expert, as we simply need stability to prove the Actor tracks the update.
Assumption 5. For E and E S, let P (- (-1s) (Qo(s, A) 2 E) > O. Ae [Q Qul and Vw' E W.
Assumption 5 implies that there always exists a strictly positive probability mass beyond every threshold E [0 Q.) This assumption is easily satisfied when Qa(s, a) is continuous in a and Tw (-18) is a continuous probability density function.
Assumption 6.
sup w EW; BE Q.1
E E (15) (100(5.A)20) (w
EANT (115) ((Q0(S.A)22) V In Tw Tw (A[S)|s] [
< co a.s.,
E (11) [100S..A V In (A|S) [|s] <0 a.s.
sup w,w' EWW BE Q.11
Assumption 7. For s S, Vw In Tw (-Is) is locally Lipschitz continuous w.r.f.
Assumptions 6 and 7 are technical requirements that can be more easily characterized when we consider Tw belong to the natural exponential family (NEF) of distributions.
Definition 3. Natural exponential family of distributions (NEF)(Morris, 1982): These prohability distributions over IR." are represented by
(x) = +((x)e" T())-K()) !TACCR)
(8)
where yj is the natural parameter, h IR - IR, while T IR" - (called the sufficient statistic) and K K(n) = In h(x)e") T(x) (called the cumulant function of the family). The space A defined as A = (n I& [K(n) < oo). Also, the above representation assumed minimal." A few popular distributions which belong to the NEF family include Binomial, Poisson, Bernoulli, Gaussian, Geometric and Exponential distributions.
We parametrize the policy Tw (-1S) using neural network, which implies that when consider NEF for the stochastic policy, the natural parameter y) of the NEF is being parametrized by w. To be more specific, we have {&w network of the actor, i.e., for a given state s E 8, v/ (s) represents the natural parameter of the NEF policy Tw (-(s). Further,
A A/w IR") to be the function space induced by the neural
V In Tw
Tw (A[S) = In (h(A)) + (S.) TT(A) (S))(()) Vwttww (5) (T(A) v,,((,(())) Vw (S) (T(A) - E (115) [(())))
Therefore Assumption can be directly satisfied by assuming that the is twice continuously differen- tiable w.E.f.
Assumption 8. For every 0 O, S and W. (w: s) (from Eq. equation 5) exists and is unique.
The above assumption ensures that the true (1 p) quantile is unique and the assumption is usually satisfied for most distributions and well-bchaved Qo.
'For distribution in NEF, there exist multiple representations of the form (8). However, for the distribution, there definitely exists representation where the components of the sufficient statistic are lincarly independent and such representation referred as minimal.
16

---

Published as a conference paper at ICLR 2023
B.3 MAIN THEOREM
To analyze the algorithm, we employ here the ODE-based analysis as proposed in (Borkar, 2008; Kushner & Clark, 2012). The actor recursions (Eqs. (6-7)) represent classical timescale stochastic approximation recursion, where there exists a bilateral coupling between the individual stochastic recursions (6) and (7). Since the step-size schedules {Ro,thEE and HeN satisfy
da.t + 0, we have 02,t + relatively faster than Oa,t - 0. This disparity induces a pseudo- heterogeneous rate of convergence (or timescales) between the individual stochastic recursions which further amounts to the asymptotic emergence asynchronous. This pseudo-behavioue can be interpreted using multiple viewpoints. When viewed from the faster timescale recursion- controlled by Qa, the slower timescale recursion coniioolled by d2 appears quasi-static, i.e., almost constant. Likewise, when observed from the slower timescale, the faster timescale recursion seems equilibrated.
Qa.t
stable coherent behaviour which is quasi-
The existence of this stable long behaviour under certain standard assumptions of stochastic approximation algorithms is rigorously established in (Borkar, 1997) and also in Chapter of (Borkar, 2008). For our stochastic approximation setting (Eqs. (6-7)), appealing characterization of the long run behaviour of the two timescale stochastic approximation algorithms- after ensuring the compliance of our setting to the pre-requisites demanded by the characterization- considering the slow timescale stochastic recursion (7) to be quasi-stationary (i.e., w' w', a.s., Vt N), while analyzing the limiting behaviour of the faster timescale recursion (6). Similarly, we let 0 to be quasi-stationary too (i.e., 0, = 6, a.s., vt N). The asymptotic behaviour of the slower timescale recursion is further analyzed by considering the faster timescale temporal variable with the limit point so obtained during quasi-stationary analysis.
directly apply this
Define the filtration
(Fr HEN, family of increasing natural offildss where
Fj = a ((w;, w', (Si, A.. R4, S)), =i:sitt))
Theorem B.1. Let w/ w', w VI N a.s. Let Assumptions 1-8 hold. Then the stochastic sequence {Wi)es generated by the stochastic recursion (6) asymptotically tracks the ODE:
d dt w(() fw. w(t) (Vene)EssenA (18) (IQQu ( In Tw()) (T)( (AIs)) t t 0. (10)
In other words, lime-soo We E H a.s., where H is set of stable equilibria of the ODE (10) contained inside W.
Proof. Firstly, rewrite the stochastic recursion (6) under the hypothesis that O, and w/ quasi-stationary, ie., Og = and w/
= w' as follows:
a.s.
We+1 = W
We + aa,
Σ ACE;
(1 V In Tn
(11)
N₂
where (5(: = Tw (w. (+1S) and Vw. = Vw=w, ie.. the gradient w.r.t. at Define
(w(w)= (S (100)))(QOOOSAA [1Q0(S..A12//111... V In mw (A[Si)
(12)
1
M,+1
I (Q.(5..A1//..)) Vw, In In
No
AEE.
E
(1005S.A12PP..) Vw. In Tw (AIS))
(13)
N
ACE
C E N
Σ ((00SS.A))PE..)) Vw. (nT((A|S)) Fj
AEE,
Eg Amm [ (100 V n (A|S:)
(14)
17

---

Published as a conference paper at ICLR 2023
Then rewrite
equation 11 = w
W: + Oai ESINU,ANT ((00sS..)2//(():))) V In Tw (A|s:)
( (1000S) w. In Tw ( (A|S:) +
E Es
E
110 Vw. In (A|S:) Fg
N
ACE
(100(S,,)2PP...)
Vw, In (A(St) Fr +
N
AEE
Σ AI1 Vw In (A|S.) }
N.
ACE
[W (W()) + M1+11 + e
rw
(15)
A few observations are in order:
B1. {M44+ JeEN is martingale difference noise sequence the filtration (F.) ),E,,,N Le., M4+1 is -eeasuuure and integrable, Vt E N and E [M+1131 = 0 a.s., Vt E N.
B2. g is locally Lipschitz continuous. This follows from Assumption 7.
B3. e + 0 a.s. as + co. (By Lemma 2 below).
B4. The iterates [w:)ee is bounded almost surely, i.e.,
sup
|well
KEN
This is ensured by the explicit application of the projection operator IW [W[+} over the iterates {w, hee at every iteration onto the bounded set W.
B5. 3T. E (0, xo) s.l. E [|
[| < T. (1 + l|w. a.s.
This follows from Assumption 6 (ii).
Now, we rewrite the stochastic recursion (15) as follows:
1 {wo &e (9 (we) + MM + +(4)
W1+1 Wt + Cta,t
Caat
We + Cra,t (FW. (W)() + FW w. (M444) + fW we
(49) + o(aa.)).
(16)
where FW is the Frechet derivative (Definition 3).
The above stochastic recursion also stochastic approximation recursion with the vector field FW (9 (w:)), the noise term FW w. (M ) the bias term Fw w. (.+) with an additional error term o(a.,)) which asymptotically inconsequential.
Also, note that L is single-valued map since the set W is assumed convex and also the limit exists since the boundary dW is considered smooth. Further, for E W, we have
FW (u) w
lim
rW
[w + cu)
w
lim c-+
w + eu
w u (for sufficiently small c). (17)
18

---

Published as a conference paper at ICLR 2023
i.e,, fW (.) is identity map for E W.
Now by appealing to Theorem 2, Chapter (Borkar, 2008) along with the observations B1-B5, we conclude that the stochastic recursion (6) asymptotically tracks the following ODE almost surely:
di w(1) - Tw (w)()))(()))
(e (w())),
120
w(t) (ES-uLANR (15)
[100(s [10065.A/2//((/:s)
V (w(() In Tw (A|S)
w(() (Wwt)Ess 4Qu (100(S.A)2///(W (w In Tw Tw (A|S)
(18)
The interchange of expectation and the gradient in the last equality follows from dominated conver- gence theorem and Assumption 7 (Rubinstein Shapiro, 1993). The above ODE a gradient flow with dynamics restricted inside W. This further implies that the stochastic recursion (6) converges to a (possibly sample path dependent) asymptotically stable equilibrium point of the above ODE inside W.
B.4 PROOF OF LEMMA 2 TO SATISFY CONDITION 3
In this section, we show that e - 0 a.s. as f - oc, in Lemma 2. To do so, we first need to prove several supporting lemmas. Lemma 1 shows that, for given Actor and Expert, the sample quantile converges to the true quantile. Using this lemma, we can then prove Lemma 2. In the following subsection, we provide three supporting lemmas about convexity and Lipschitz properties of the sample quantiles, required for the proof Lemma 1.
For this section, require the following characterization of fP(Qe(s,)) w'). Please refer Lemma of (Homem-de Mello, 2007) for more details.
(P(oo(s.),, w') = arg min E E (Qoo(s A),
(19)
(E(QP.091
where (y, - - + (e (L- - 1)044e20)
Similarly, the sample estimate of the true (1 - 1)-pp-qunttlle, i.e., 8 ([(1-p))N] (where Q!! is
the i-th order statistic of the random sample (Qa(s, A)} with E = {A:) Tw (-1s)) can be characterized as the unique solution the stochastic counterpart of the above optimization problem, i.e.,
f arg min
1
Σ
(()s(s;A),))
(20)
N
EE
Q11
E|=N
Lemma 1. Assume 0, = 8, w w. WE N. Also, let Assumptions 3-5 hold. Then, for given state 8 E 8,
lim Je = (((Qo(s))) w') a.s.,
where Jr. = Q(((--))111 (where Q is the i-th order statistic of the random sample (Qo(s, A)}AEE, with E, = (A.)
ad Tw (1s)).
Proof. The proof is similar to arguments in Lemma 7 of (Hu et al., 2007). Since state and expert parameter 0 considered fixed, we assume the following notation the proof. Let
Pl = ft and ff.00 (s. w'),
(21)
where Ph and (o(Qo(s)), w') defined in Equations equation 19 and equation 20.
Consider the open cover { l 1Q,, Qil of 1 Qti. Since 1QP, Q is compact, there exists finite sub-cover, Le., ... [xr) s.I. UM, Br (C:)
[Q9. Q.)-
Let
19

---

Published as a conference paper at ICLR 2023
(() = E Am-Tw (V(Qo(s,A))))) and 0.( =
Σ V(Qo(s,A))
AEE, 1N
(,/rw/(11)))
Now, by triangle inequality, we have for / [Q], Qul.
(0(e) 0.)1 - (0(e) - o(e,) + (0(e)) - 0,(ee)) ()) 0.(4) P((1)
s Lpp e (d(e)) 0.((e)) + Eples - E
$ Tip + T.,)) r + (0(e) (e,)),
(22)
where I,p and T.p are the Lipschitz constants of 0()) and ),() respectively.
For 5 0, take ó(Lp + Lp) Also, by Kolmogorov's strong law of large numbers (Theorem 2.3.10 of (Sen Singer, 2017)), we have (e( + (() a.s. This implies that there exists T E N s.t. (0({,) ((())) < 6/2, vt 2 T, Vj E [M]. Then from Eq. (22), we have
(Ø(E) - (e) - 6/2 8, V 1 Q.-
This implies 0, converges uniformly to 8. By Lemmas 3 and 4, 02 and strictly convex and Lipschitz continuous, and so because 0g converges uniformly to 9, this means that the sequence of minimizers of 0, converge to the minimizer of i (see Lemma 5, Appendix B.6 for an explicit justification). These minimizers correspond to ff and (*(Qo(s,)) ) w") respectively, and so 1im Pe (0(Q(( w') a.s.
Now, for 8 > 0 and r = 5(L, //,) we obtain the following from Eq. (22):
(o(E)- 0,(1) - 6/2 + (0()) o.(e,)
+ {1o(e)) - 0,( - 6/2,vj E [M]} = (10(0)) - 0.(0) S 8, [Q/, Q.1
+ P (10(0) 0.00) 0,00) S 12/. 12). 2 Pk (19(6) - -.(()) 5/22 E MM])
Prw. (10(C)) 0.(G,)) 8/2,3j (M])
M
P Rw (10(e)) 0,(e,)) > 66/2
(1(()) - 0,(t,)) > 8/2)
M max
P JE[M]
TT/
-2
2 2M exp
(23)
4(Q%.
Q/12
where Fr., i = PANNT (-1s). And the last inequality follows from Hoeffding's 's inequality (Hoeffding.
1963) along with the fact that E [o.(E)] I(e)) and
[0(+) s Q Q..
sup telof.021
Now, the sub-differential of ((C) is given by (z)(e)= |p P P (1s) (Qo(s, A) (), 1 Amo (1)) (Qo(s, A) s =0)-
(24)
By the definition of sub- gradient we obtain
affia SPaol I - 0(S%,a)), E 0zl(1)
CIPR.O fPcoo S |0 - - ((Sr
(25)
20

---

Published as a conference paper at ICLR 2023
where C' max {o P. Pantwr(-(s)) (Q)(s,A)2 2 1Ph00) :p 1+ ( )
Further,
C1f - S2o0 1 |0(Fejs,0) 0186,0001
- 10 11P Te(Pie.o) + 1.. 0(8%
- 10 (PPooo))
O.(() 2(0)
sup
EEl99 Q41
2 sup #E(
(+.(E) 0(0))-
(26)
From Eqs. (23) and (26), obtain for é 0
Pw (NDIPBEe fPr.ol 2c) s Pw
N₁ sup
10.(1) - 0(0) 2
LElQP
-2
22N 22
$ 2M exp
2M exp
16N7 (Qth - 099
16(Q2) 99)
For E (0,1/2) and infrEn
Ny1 Ni
2 r > 1 (by Assumption 3), then
16((2 -2N,1 2
-27(1-20)( 20 2
Σ 2M exp
0/1²
2M exp
16( - Q9) < OC.
Therefore, by Corel-Cantelli's Lemma (Durrett, 1991), we have
Pw (No
fo st|s.0
fPaol 2 E i.0)
Thus we have No (Pin. - SPa + a.S. as N₂ - DC.
Lemma 2. Almost surely.
+0 as N; + xc.
Proof of Lemma 2: Consider
1
E
Σ
T1Q.(S..)2211 Vw, In Tw (A[St)
N
ACE.
E
((00SSAA12E.)) ww In (A(s:) S = s, w/ MEE
Notice that, because of the conditions on Tw an exponential rate in the number of samples, for arbitrary w' E W. Namely, for e >> 0 and N e N. we have
Tw'ss)), (-1s), we know that the sample average converges with
(I 1 Σ I
(100(t.)122//0000))))) (18)3 V Iw In (Als)) ACE
Rd (11))
( [Cieep(-o22Nee
(ANTwr())))
(reett. Vn In (Als)
W.'
where C1, C2, C3, C4 > 0. Therefore, for a' > O, we have
1(QuleAA)778.1 Vw, In Tw (Als) [ML0OCEAA128 Vw, In (((s) 20)
p
N
AEE,
N2 Ngsa"
NC22N (a) ea)
< C1 exp
= Ci exp
(-oyrloa- Nes-card es)
I C1 exp
21

---

Published as a conference paper at ICLR 2023
where f6.. = ( and infren
Ne41
2 1 (by Assumption 3). N,
For c3 cja's 0 = a' < ca/e1, we have
Σ Ciexp exp E-
6 < oo.
Therefore, by Borel-Cantelli's Lemma (Durrett, 1991), we have
Noo
Σ
(10((..)222..)) Vw, In Tw (Als) - E (100(sA)22E..) Vw, In Tw (w (A|s)) |
2e e i.o.)
N
AEEs
-0
This implies that Ne AEE
Σ
11o0s..12R.. Vw. (nTw(A)) - E ('Ia Vw, In (A|s)
+0 a.s.
N
(27)
The above result implies that the sample average converges at a rate O(N''), where 0 < a < ca/ca independent of w, w' W. By Lemma have the sample quantiles He also converging the true quantile at a rate ((N()) independent of w, w' E W. Now the claim follows directly from Assumption (ii) and bounded convergence theorem.
B.5 SUPPORTING LEMMAS FOR LEMMA 1
Lemma 3. Let Assumption 5 hold. For 0 E O w' W, 8 and E [Qi, O.}. we have
1. EAnaw/(1)) (Vo A), is Lipschitz continuous.
2. N Σ AEE ((Qa(s, A), (with E id T-(s)) is Lipschitz continuous with Lipschitz -I-N
constant independent of the sample length N.
Proof. Let l, la E [Q Q.1 2 4. By Assumption 5 we have P PA (Q))) ()) and P A~E (Qo(s,) f2) 0. Now,
E (An ((Qo(s, - E Em (VQo(s,,)))
EANT (1+) (Qo(s, (1 ()(((((._A)261) +(1 (66=
EAmT (115) [(Qu(s, A) (1) (0c1-pp)(ccoc -)((00(4 - (62-Qu(s, (1l=-Quss))pp/(220000
-ANt (-18) (Qo(s, () -) (400)))))00000000000000000000000
AQ)(s,A) (2) - -) (62, 000-0000002000000000000000-00000
EANa (1s) (1 (2 -
+ (-(1 pp11 - p62 + -Qo + (1)
(1- (1- = -p - 41/.
- -4- (2p 12 41
Similarly, we can prove the later claim also. This completes the proof of Lemma 3.
Lemma Let Assumption 5 hold. Then, for 0 θ, w' E W. E and E [Q], 221 we ad
have EA-Twr (VQo(s,))) 0)] and 1/ Σ AC= (sQo(s, A), (with Tw (-(s)) are strictly convex.
|
22

---

Published as a conference paper at ICLR 2023
Proof. For À E [0, and (,, [Qi, QuI with 6 I Eg, have
(11) ( (Q0, (1-1))6)
(28)
(1S) (1-
- -1-N-Na)aaosss222444----
+ + (1- A)62 - -2065-)))le....3334+----
Notice that
(Qo(5, - A61 - - (0l=)//)//o0
-A,Q(SS A) A&1 + +11 (1- (1 -10
We consider how one of these components simplifies.
E EAER (11)) (AQQ A) - 14000
()((00())))))))) - (Qo(S, A) (QodS,,)-Aa)mmssoooosssssss -tt.://a.atooossssss----aaaa XE AEA (-18) [[Qo(S,A) (19O((())) -
I AE AEAER ( (11) (Qo((s,)) - ()
& (Q) 0 Xe for Aor 5 (1-
S AE AE (11)) [(Qo(5, - ((00(5))))))
(Qo(S.A) -n) 0 [x
Similarly, we get
E (-18) ((Q6(S,) - 4101S..0... EAET ()) (Q0(5, ( 4))
E (-18) (ill-0(((S.)//pssSAAAH----- < E (8) (11- ( ((20(8.A)00)
E (-18) [(22 (
S EAER (8) [(2 Qo(S, ((ossssss))))ocsssssso)l
Therefore, for Equation equation 28, we get
equation 28 S A(1 P) (-18) (1 (
+ (1 A) (1s) (1) (IQu(S.A)2a))
+ ApE (-15) [(4 Qo (4)
+ (1 - A)pE AET (15) ((
= xE AE (115) ( (So, + (1 \)EAEE) (VQo
We can prove the second claim similarly. This completes the proof of Lemma 4.
B.6 LEMMA 5
Lemma 5. Let {Jn C(RR (R) IR)) be sequence of strictly convex, continuous functions converg- ing uniformly to a strict convex function f. Let x; arg min, fn(x) and x" = arg min f(x). Then lim x x².
Proof. L lim inf, z. We employ proof by contradiction here. For that, assume x² Now, note that f(x") < f(c) and f(x") < f((x" + +)) /2) (by the definition of x*). Also, by the strict convexity of f, we have f((x" + c)/2) (f(**) f(c)) /2 f(c). Therefore, we have
f(c) f((x* +c)/2) > f(z").
(29)
Let ri E IR be such that f(c) > mi > f((x* + c)/2). Now, since f' + 0 as n + oc. there exists positive integer N s.t. -f(c)-f(c) < f(c) T1, Vn 2 N and > 0. Therefore,
fa(c) - f(c > r1 - f(c) = fa(c) > T1. Similarily, we can show that fa((x* + c)/2 > T1- Therefore, have Sn(c) > Su(("" +2)/2). Similarily, can show that fa(("* + +c)/2) fn(x"). Finally, we obtain
fa(c) fn((x* + e)/2) > fn(x"), Vn N.
(30)
Now, by the extreme value theorem of the continuous functions, obtain that for n 2 N. fn achieves
minimum (say at Tp in the closed interval [c, (a* + c). Note that fn(x,) & fn + +c) (if so then fa (I.p) will be local minimum of fn since fo (x*) sa(("" + +))22)) Also, fn(xp) #
23

---

Published as a conference paper at ICLR 2023
fa((2" + +c)/2). Therefore, fn achieves it minimum in the closed interval [c, (x* + +c)/2] /2] the point (x" + c)/2. This further implies that 2, > (x" + c)/2. Therefore, lim inf, z 2 (x* + c) 2 =
2 (x' +c)/2 = c c2 x². This is contradiction and implies
lim inf x 2 x²
(31)
Now consider (x) fn(-z). Note that 9n is also continuous and strictly convex. Indeed, for E [0. 1], we have (n (1 = f
(- Arι - (1 x) < A (1- = (1( (1 ()2(22)- Applying the result from Eq. (31) to the sequence (0n mEN, obtain that lim inf (-2,) ) 2 -r" This implies lim sup, 2, S x². Therefore.
lim inf on 2 xx" 2 sup x z lim sup
a
Hence, lim inf, 1 lim sup,, 25
C EXPERIMENTAL DETAILS C.I HYPERPARAMETER DETAILS
In this section, we outline the tuned hyperparameters for each algorithm on each environment in our experiments. For each algorithm, hyperparameters were tuned over an initial 10 runs with different random seeds. Each algorithm saw the same 10 initial random seeds. For a list of all hyperparameters swept, see Section 5.3. Table we list the tuned hyperparameters for each algorithm when tuning across continuous- action environments. In Table 2, list the tuned hyperparameters for each algorithm when tuning across discrete action environments. hyperparameters when tuning per-environment for Greedy AC, VanillaAC, and SAC respectively. Finally, Table 6 outlines the hyperparamters used in the experiments on Swimmer.
Tables 3, 4, and 5, we list the tuned
Hyperparameter
T
Greedy Critic
1.0
le-3
le-3
Vanilla Actor-Crité
2.0
le-3
le-3
Soft Actor-Critic
1.0
le-3
le-3
Table 1: Hyperparameters tuned across continuous-action environments for GreedyAC, VanillaAC,
and SAC.
Hyperparameter
Greedy Actor-Criti
10.0
le-3
Vanilla Actor-Critic
1e-1
le-3
le-2
Soft Actor-Critis
10
le-5
10
Table 2: Hyperparameters tuned across discrete-action environments for GreedyAC, VanillaAC, and SAC.
Hyperparameter
Q
Acrobot-CA
le-1
le-3
le-2
Acrobot-Do DA
le-1
le-2
Mountain Car-CA
1.0
le-3
10.0
Mountain Car-DA
2.0
1e-3
Pendulum-CA
1e-1
1e-2
10.0
Pendulum-DA
1.0
le-3
Table 3: Hyperparameters tuned per-environment for GreedyAC.
24

---

Published as a conference paper at ICLR 2023
Hyperparameter
Acrobot-CA CA
2.0
le-3
le-3
Acrobot-Da.
le-1
le-2
le-2
Mountain Car-CA
2.0
le-3
le-3
Mountain Car-DA
1.0
le-3
le-2
Pendulum-CC CC
le-2
le-2
le-2
Pendulum-DD -D
2.0
le-3
1.0
Table 4: Hyperparameters tuned per-environment for VanillaAC.
Hyperparameter
Q
Acrobot- CAA
10.0
le-5
10.0
Acrobot-DA
2.0
le-5
10.0
Mountain Car-CA
1.0
le-3
le-3
Mountain Car-DA
1.0
le-3
le-2
Pendulum CA
le-1
le-2
le-1
Pendulum-DD -D
1.0
1e-3
1.0
Table 5: Hyperparameters tuned per-environment for SAC.
Hyperparameter
Greedy Actor-Critic
Te-2
le-4
Te-1
Table 6: Hyperparameters Chosen for GreedyAC on Swimmer.
C.2 NORMALIZATION APPROACH
For each environment, we find the best return achieved by any agent, across all runs, as simple approximation to ncar-optimal return. Table 7 lists these returns for each environment. Then, to obtain a normalized score, we use BestValue-AlyVaa Alg where the numerator is guaranteed to be [BestValue]
nonnegative. If Value BestValue we get the highest value of 1. If All is half of Vestu,l we get 0.5BestValue 0.5. If Alg is significantly worse than BestValue, the score is much lower. [alst
The Value that we normalize is the point depicted on the sensitivity plot. corresponds to the Average Return across timesteps and across runs for the algorithm, with that hyperparameter setting in that environment.
For the experiments in Figure 3, where we tune across the complete set of discrete- continuous- action environments, we first compute the normalized scores just described. Then, we compute the average normalized scores for each algorithm and hyperparameter setting across discrete-actoo and continuous-aco action environments separately. We then choose the hyperparameter setting for each algorithm for the discrete- and continuous-action environments based the hyperparameter setting which resulted in the highest normalized scores. The learning curves for these hyperparameters, for each algorithm, are shown in Figure 3.
Environment
Continuous
Discrete
Acrobot
-56
-56
Mountain Car
-65
-83
Pendulum
930
932
Table 7: Approximate return achieved by optimal policy. We approximate the return achievable by a ncar-optimal policy on environment & by finding the highest return achieved over all runs of all hyperparameters and all agents environment E
25

---

Published as a conference paper at ICLR 2023
C.3 SENSITIVITY PLOTS
We plot parameter sensitivity curves, which include a line for each entropy scale, with the stepsize on the X-axis. Because there two stepsizes, have sets of plots and one for the actor stepsize. When examining the sensitivity to the critic stepsize, we select the corresponding best actor stepsize. This means that for each point (critic stepsize, entropy scale) (a, r) on the sensitivity plot for the critic stepsize, we find the best actor stepsize and report the performance for that triplet averaged over all 40 runs. We do the same procedure when plotting the actor stepsize on the x-axis, but maximizing over critic stepsize.
for the critic stepsize
Acrobot
Mountain Car
Pendulum
Average Return
GreedyAC
-550
1000
1000
5
-3
-2
55
2
-4
33
-100
entropy 8.001
-100
entrosy 0.01
entropy 01
SAC
550
0
-100
1000
5
3
-2
55
.2
.4 33
-1
Critic Step-Size (10*)
Critic Step-Size
Critic Step-Size
(10*)
(10*)
Figure 6: Sensitivity curves for the critic step-size hyperparameter a for GreedyAC and SAC, with one line for each entropy scale tested. The critic step-size plotted on logarithmic scale on the x-axis.
Acrobot
Mountain Car
Pendulum
Average Return
-100
-100
1000
GreedyAC
-550
1000
1100
-1000
-3
-2
-1
0
-3
-2
-1
0
1
Average Return
-100
1000
0.0
entropy
ortragy 0.1
SAC
-550
-550
entrapy 1.0
ertrapy 10.0
1000
1000
1000
33
-2
-1
0
-3
-2
-
0
Actor Step-Size Scale (10*)
Actor Step-Size Scale
Actor Step-Size Scale (10*)
(10*)
Figure 7: Sensitivity curves for the actor stepsize scale hyperparameter for both Greedy AC and SAC, with one line for each entropy scale tested. The actor step-size scale is plotted on a logarithmic scale the x-axis.
26

---

Published as a conference paper at ICLR 2023
D ABLATION STUDY ON SAC
Acrobot
Mountain Car
Pendulum
-300
1000
Average Return
-650
-525
850
SAC (Auto Entropy)
-1000
1000
700
Timesteps
Timesteps
Timesteps (Hundreds of Thousands)
(Hundreds Thousands)
(Hundreds Thousands)
Figure 8: Learning curves over 40 runs for SAC and 10 runs for SAC (Auto Entropy) with shaded regions denoting standard error. The entropy scale for SAC as well as the entropy scale step-size for SAC (Auto Entropy) are tuned using grid search.
Modern variants of SAC utilize a trick to automatically adapt the entropy scale hyperparameter during training (Haarnoja et al., 2018b). In order to gauge which variant of SAC to use in this work, we performed an ablation study where we studied SAC with and without automatic entropy tuning. We ran SAC with automatic entropy tuning for 10 runs. Hyperparameters were swept in the same sets as listed in Section 5.3. Additionally, we swept entropy scale step-sizes 3 = 10a for in z E {-4,-3, -2 for automatic entropy tuning. Figure 8 shows the learning curves of SAC with automatic entropy tuning, over 10 runs, and SAC without automatic entropy tuning over the 40 runs conducted for the experiments in the main text. As can be seen in the figure, performing grid search over the entropy scale hyperparameter never degrades performance compared to using automatic entropy tuning, and some cases results better performance than when using automatic entropy tuning. Because of this, we decided to use manual entropy tuning through a grid search in our experiments, which also allows us to characterize the sensitivity SAC's performance with respect to the entropy scale hyperparameter.
27


Reviews:
[{"review_id": "u4PVEfHxA23", "reviewer": "Reviewer_zQ75", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper proposes a new policy improvement scheme called conditional cross-entropy method (CCEM), which leverages the cross-entropy method in global optimization to keep track of the set of maximal actions. The proposed algorithm is a variant of the actor-critic methods and called GreedyAC, which (i) uses CCEM for updating the actor and (ii) applies entropy regularization on the loss function of the actor. The proposed method enjoys the advantages of (i) being non-sensitive to the entropy regularization parameter, (ii) concentrating on the greedy policy more slowly, (iii) having better empirical results in some environments than SAC, and (iv) enjoying policy improvement guarantee and convergence.", "summary_of_the_review": "This paper presents a new perspective of applying CEM to policy improvement. While the theoretical result is interesting, there are some issues with whether the analysis actually captures the behavior of the proposed algorithm as well as with the empirical evaluation of the baselines and claim on sensitivity. Moreover, the novelty of this paper should be further clarified as there are some missing references that look relevant but not discussed in this paper.\n\n========== Post-rebuttal ==========\nI would like to thank the authors for providing a very detailed response. My main concerns, the difference between the algorithm and the analysis as well as the experimental results of the benchmark methods, have been addressed. As a result, I decided to raise my score from 5 to 6.", "strength_and_weaknesses": "**Strength**\n- This paper first introduces a new perspective of applying CEM to RL and thereby proposes the GreedyAC algorithm with theoretical convergence and improvement guarantee.\n- The proposed method is not sensitive to the entropy regularization parameter and appears to have some empirical advantage over the popular benchmark SAC.\n\n**Weaknesses**\n- While the theoretical results are interesting and could have their own merits, the algorithm analyzed in theory appear to deviate from the actual algorithm introduced in the paper (cf. Algorithms 2-3). \n- There are several concerns about the experimental results:\n    - SAC: The reported empirical performance of SAC looks quite different from the existing benchmarks. For example, from Figure 2, it is surprising that SAC fails to solve the simple Acrobot and MountainCar tasks. By contrast, in the existing benchmarks (e.g., Table 1 in https://arxiv.org/abs/1907.02057), SAC appears quite strong in these classic tasks of OpenAI gym. It is not clear what makes the difference, and further explanation is needed.\n    - Sensitivity: One of the claims is that GreedyAC empirically could be less sensitive to the entropy regularization parameter than SAC. However, it is not clear why this is true from the design or the convergence analysis. Further justification is needed for this claim, either from intuition, theoretical analysis or ablation studies.\n- Some components of GreedyAC look somewhat ad hoc and would require more explanation. For example, the proposal distribution plays an important role in the policy improvement of GreedyAC, and it relies on an entropy regularization term.\n- Several missing references on CEM for RL: There are several prior works on the combination of CEM and value-based methods, such as [Simmons-Edler et al. 2018] and [Shao et al. 2022]. These references are missing in this paper.\n\n[Simmons-Edler et al. 2019]  Riley Simmons-Edler, Ben Eisner, Eric Mitchell, Sebastian Seung, Daniel Lee (2019). “Q-Learning for Continuous Actions with Cross-Entropy Guided Policies”. In The Reinforcement Learning for Real Life (RL4RealLife) Workshop in the 36th International Conference on Machine Learning (ICML), 2019.\n\n[Shao et al., 2022] Lin Shao, Yifan You, Mengyuan Yan, Shenli Yuan, Qingyun Sun, Jeannette Bohg, \"GRAC: Self-Guided and Self-Regularized Actor-Critic.\" Conference on Robot Learning. PMLR, 2022.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "qHPdFpQrGnD", "reviewer": "Reviewer_BG9i", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The paper proposes an Actor-Critic algorithm in which the actor learns to pursue (imitate) the greedy policy of the critic, using, with continuous actions, a method inspired from the Cross-Entropy method (pursuing the top-K actions from a sample of relatively good actions). With continuous actions, the core contributions of the paper are the suggestion of using CEM to approximate $\\argmax_a Q(s, a)$, and the introduction of an entropy-regularized proposal policy $\\pi_{w'}$, to choose which actions to sample for computing the top-K of $Q(s, a)$.", "summary_of_the_review": "Very good idea, but learning the critic with SARSA? It seems that it helps with the proof, but maybe not the empirical performance. Other algorithms that train the actor towards target actions (as opposed to using Policy Gradient) should be discussed in the paper.", "strength_and_weaknesses": "Strengths:\n\n- The algorithms is simple, elegant and performs very well even on challenging tasks (Atari games, Mujoco tasks)\n- The paper is clear and well-written\n\nWeakness:\n\nMy use of \"pursue\" in \"Summary of the paper\" is on purpose. This paper actually presents an algorithm for continuous-action Conservative Policy Iteration [1], which can also be seen as continuous-action state-dependent Pursuit [2]. There is a large and exciting field of Reinforcement Learning that considers gradient-free optimization of the actors, using imitation learning to pursue the greedy policy of critics. Such work include:\n\n- The Actor-Mimic [3], in which a DQN policy is distilled into an actor\n- Dual Policy Iteration [4], the formalism behind AlphaZero, in which the actor pursues a proposal policy (in the case of MuZero, obtained by planning with MCTS)\n- Approximate Conservative Policy Iteration [1], in which the proposal policy is the greedy policy of an on-policy critic. This paper, with discrete actions (Algorithm 2, discrete), is Approximate Conservative Policy Iteration\n- Bootstrapped Dual Policy Iteration [5], close to Approximate Policy Iteration, but that shows that off-policy critics (learned with Q-Learning instead of SARSA) work, leading to extremely high sample-efficiency and hyper-parameter robustness (claims also made in this paper, and mostly due using Dual Policy Iteration instead of Policy Gradient)\n- Batch/Offline Reinforcement Learning also has extensive literature on proposal policies and how to sample actions. For instance, Batch-Constrained Q-Learning [6] learns the proposal policy using a conditional Variational Autoencoder. This work is however only distantly related to this paper.\n\nTo my knowledge, the proposal policy presented in this paper, and its use to compute approximate greedy policies with continuous actions, is novel. The fact that it works is however not surprising, as the literature mentioned above consistently, over the past years, showed that doing something else that Policy Gradient for actor-critic training is very good indeed.\n\nMy points above lead to two remarks:\n\n- Would it be possible for the authors to have a look at the world of Conservative Policy Iteration, Dual Policy Iteration and Policy Distillation, and briefly discuss that in the paper?\n- Why is the critic learned with SARSA in this paper? [6] shows that using SOTA critic-learning algorithms (the proposed algorithm combines twin-delayed critics (TD3) with Boostrapped DQN) leads to significant gains in sample-efficiency. The only challenge is that all these learning algorithms assume the existence of $\\argmax_a Q(s, a)$, so, discrete actions, but this paper happens to propose a way to compute that max and argmax using CEM and a proposition policy.\n\n[1]: Kakade, S., Langford, J.: Approximately optimal approximate reinforcement learning. In: International Conference on Machine Learning (ICML). pp. 267–274 (2002)\n\n[2]: Agache, M., & Oommen, B. J. (2002). Generalized pursuit learning schemes: New families of continuous and discretized learning automata. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 32(6), 738-749.\n\n[3]: Parisotto, E., Ba, J. L., & Salakhutdinov, R. (2015). Actor-mimic: Deep multitask and transfer reinforcement learning. arXiv preprint arXiv:1511.06342.\n\n[4]: Sun, W., Gordon, G. J., Boots, B., & Bagnell, J. (2018). Dual policy iteration. Advances in Neural Information Processing Systems, 31.\n\n[5]: Steckelmacher, D., Plisnier, H., Roijers, D. M., & Nowé, A. (2019, September). Sample-efficient model-free reinforcement learning with off-policy critics. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases (pp. 19-34). Springer, Cham.\n\n[6]: Scott Fujimoto, David Meger, and Doina Precup. 2019. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning. 2052–2062", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "74qMK14njlz", "reviewer": "Reviewer_y7Rc", "summary": "", "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": "", "summary_of_the_paper": "This paper proposes the Greedy Actor-Critic approach, which uses two policies, and a new CCEM approach: a conditional (on states) varianta of CEM. The critic is trained using Sarsa updates (with a replay buffer). A *proposal policy* (one of the two policies) is used to sample a distribution of actions, which are then evaluated and ranked by the critic. The top N of these actions are used for training the policies. The main policy (the second of the two policies) is used to select actions to be executed in the environment. Both policies are updated such that they increase the likelihood of the top N actions mentioned previously, but the proposal policy additionally has an entropy regularization term (which the main policy doesn't).", "summary_of_the_review": "Potentially a good paper, but currently having slightly too many issues with imprecise statements and confusing / unexplained notation.\n\n---\n\n**After discussion**: the revision of the paper has fixed and clarified many of my concerns, and I have updated my score.", "strength_and_weaknesses": "**Strengths**:\n- While the paper is rather technical and dense, in general it is possible to follow along with the main ideas.\n- Theoretical and algorithmic contributions appear to be sound, with good emprical results.\n\n**Weaknesses**:\n- In several parts of the more technical writing, it seems that there are slight mistakes and confusing notation (notation suddenly changes or is not explained at all), making some parts difficult to follow (see detailed comments below).\n- There are some statements where I'd appreciate a bit more intuition/explanations (see detailed comments below).\n\n---\n\n**After discussion**: the revision of the paper has fixed and clarified many of my concerns, and I have updated my score.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster