EMaQ: Expected-Max Q-Learning Operator for Simple Yet Effective Offline and Online RL
Authors: Seyed Kamyar Seyed Ghasemipour
Dale Schuurmans
Shixiang Gu
Venue:  (2021)
Keywords: Offline Reinforcement Learning
Off-Policy Reinforcement Learning

Abstract: Off-policy reinforcement learning (RL) holds the promise of sample-efficient learning of decision-making policies by leveraging past experience. However, in the offline RL setting -- where a fixed collection of interactions are provided and no further interactions are allowed -- it has been shown that standard off-policy RL methods can significantly underperform. Recently proposed methods often aim to address this shortcoming by constraining learned policies to remain close to the given dataset of interactions. In this work, we closely investigate an important simplification of BCQ~\citep{fujimoto2018off} -- a prior approach for offline RL -- which removes a heuristic design choice and naturally restrict extracted policies to remain \emph{exactly} within the support of a given behavior policy. Importantly, in contrast to their original theoretical considerations, we derive this simplified algorithm through the introduction of a novel backup operator, Expected-Max Q-Learning (EMaQ), which is more closely related to the resulting practical algorithm. Specifically, in addition to the distribution support, EMaQ explicitly considers the number of samples and the proposal distribution, allowing us to derive new sub-optimality bounds which can serve as a novel measure of complexity for offline RL problems. In the offline RL setting -- the main focus of this work -- EMaQ matches and outperforms prior state-of-the-art in the D4RL benchmarks~\citep{fu2020d4rl}. In the online RL setting, we demonstrate that EMaQ is competitive with Soft Actor Critic (SAC). The key contributions of our empirical findings are demonstrating the importance of careful generative model design for estimating behavior policies, and an intuitive notion of complexity for offline RL problems. With its simple interpretation and fewer moving parts, such as no explicit function approximator representing the policy, EMaQ serves as a strong yet easy to implement baseline for future work.

Under review as a conference paper at ICLR 2021
EMAQ: EXPECTED-MAX Q-LEARNING OPERATOR FOR SIMPLE YET EFFECTIVE OFFLINE AND ONLINE RL
Anonymous authors Paper under double-blind review
ABSTRACT
Off-policy reinforcement learning (RL) holds the promise of sample-efficient learning of decision-making policies by leveraging past experience. However, the offline RL setting- where a fixed collection of interactions are provided and no further interactions are allowed - it has been shown that standard off-policy RL methods can significantly underperform. Recently proposed methods often aim address this shortcoming by constraining learned policies to remain close to the important simplification of BCQ (Fujimoto et al.) (0188) a prior approach for offline RL which removes heuristic design choice and naturally restrict extracted poli- cies to remain exactly within the support of a given behavior policy. Importantly, in contrast to their original theoretical considerations, we derive this simplified algorithm through the introduction of novel backup operator, Expected-Mi -ax Q-Learning (EMaQ), which more closely related to the resulting practical al- gorithm. Specifically, in addition to the distribution support, EMaQ explicitly considers the number of samples and the proposal distribution, allowing us derive new sub-optimality bounds which can serve novel measure of com- plexity for offline RL problems. In the offline RL setting - the main focus of this work EMaQ matches and outperforms prior state-of-the-arr in the D4RL bench- marks (Fu et al.) 2020a). In the online RL setting, we demonstrate that EMaQ is competitive with Soft Actor Critic (SAC). The key contributions of our empirical findings are demonstrating the importance of careful generative model design for estimating behavior policies, and an intuitive notion complexity for offline RL problems. With its simple interpretation and fewer moving parts, such as no ex- plicit function approximator representing the policy, EMaQ serves strong yet easy to implement baseline for future work.
given dataset of interactions. In this work, we closely investigate
INTRODUCTION
Leveraging past interactions in order improve decision-making process is the hallmark goal of off-policy reinforcement learning (RL) (Precup et al.) [000] Degris et al. 2012). Effectively learning from past experiences can significantly reduce the amount of online interaction required to learn good policy, and is a particularly crucial ingredient in settings where interactions are costly or safety is of great importance, such robotics Gu al. (011)): Kalashnikov al. (201 8a), health Murphy et al. (200I), dialog agents (Jaques et al. 22199) and education Mandel et al. (2014). In recent years, with neural networks taking more central role the RL literature, there have been significant advances in developing off- off-policy RI. algorithms for the function approximator setting, where policies and value functions are represented by neural networks (Mnih et al. 2015) Lillierap et al., 2015) Gu al. 2016bb al Haarnoja et al. 2018, Fujimoto et al. 1b)... Such algorithms, while off-policy in nature, are typically trained in an online setting where algorithm updates are interleaved with additional online interactions. However, in purely offline RL settings, where dataset of interactions are provided ahead of time and no additional interactions are allowed, the performance of these algorithms degrades drastically (Fujimoto et al., 2018a; Jaques et al.) 2019).
number of recent methods have been developed to address this shortcoming of off-policy RL algorithms. A particular class of algorithms for offline RL that have enjoyed recent success

---

Under review as a conference paper at ICLR 2021
those based on dynamic programming and value estimation (Fujimoto et al. 2018a Jaques al. 2019 Kumar et al., 2019 Wu et al. 2019 Levine et al., 2020). Most proposed algorithms are designed with key intuition that it is desirable to prevent policies from deviating too much from the provided collection of interactions. By moving far from the actions taken in the offline data, any subsequently learned policies or value functions may not generalize well and lead to the belief that certain actions will lead to better outcomes than they actually would. Furthermore, due to the dynamics of the MDP, taking out-of-distribution actions may lead states not covered in the offline data, creating a snowball effect (Ross et al. 2011). In order to prevent learned policies from straying from the offline data, various methods have been introduced for regularizing the policy towards a
base behavior policy (e.g. through a divergence penalty (Jaques et al. 2019 Wu et al. 2019 Kumar et al. 2019) or clipping actions (Fujimoto et al. 2018a)).
Taking the above intuitions into consideration, in this work we investigate a simplifcation of the BCQ algorithm (Fujimoto et al. 2018a) (a notable prior work in offiin RL), which removes a heuristic design choice and has the property that extracted policies remain exactly within the sup- port of given behavior policy. In contrast to the theoretical considerations in the original work, we derive this simplified algorithm in theoretical setup that more closely reflects the resulting algo- rithm. We introduce the Expected-Mi Max Q-Learning (EMaQ) operator, which interpolates between the standard Q-function evaluation and Q-learning backup operators. The EMaQ operator makes explicit the relation between the proposal distribution and number of samples used, and leads to sub-optimality bounds which introduce novel notion of complexity for offline RL problems. In its practical implementation for the continuous control and function approximator setting, EMaQ has only two standard components (an estimate of the base behavior policy, and Q functions) and does not explicitly represent a policy, requiring fitting one less function approximator than prior approaches (Fujimoto et al. 2018a: Kumar et al., 2019; Wu et al., 2019).
In online RL, EMaQ is competitive with Soft Actor Critic (SAC) (Haamoja et al. 2018) and sur- passes SAC in the deployment-efficient setting (Matsushima et al. 2020). In the offline RL setting the main focus of this work - EMaQ matches and outperforms prior state-of-the-ar in the D4RL, (Fu (ct al. 2020a) benchmark tasks. Through our explorations with EMaQ we make two intriguing find- ings. First, due to the strong dependence of EMaQ the quality of behavior policy used, our results demonstrate the significant impact of careful considerations in modeling the behavior policy that generate the offline interaction datasets. Second, relating to the introduced notion of complex- ity, in a diverse array of benchmark settings considered in this work we observe that surprisingly little modification
base behavior policy is necessary obtain a performant policy. As an exam- ple, we observe that while a HalfCheetah random policy obtains a return of 0, a policy that at each state uniformly samples only 5 actions and chooses the one with the best value obtains return of 2000. The simplicity, intuitive interpretation, and strong empirical performance of EMaQ make it a great test-bed for further examination and theoretical analyses, and an easy to implement yet strong baseline for future work in offline RL.
2 BACKGROUND
Throughout this work, we represent Markov Decision Process (MDP) as M AS, 7) with state space S, action space A. reward function SxA-+ IR, transition dynamics P. and discount y. In offline RL, we assume access to a dataset of interactions with the MDP, which we will represent as collection of tuples D {(s, a, r, ?, where t is indicator variable that is set to True when is a terminal state. We will use j to represent the behavior policy used to collect D, and depending the context, we will overload this notation and use l to represent estimate of the true behavior policy. For a given policy म, we will use the notation d= (s), dd (s, a) to represent the state-visitation and state-action visitation distributions respectively.
As alluded to above, a significant challenge of offline RL methods is the problem of distribution shift. At training-time, there no distribution shift in states as fixed dataset D is used for training. and the policy and value functions are never evaluated on states outside of d' (s). However, a very significant challenge is the problem of distribution shift in actions. Consider the Bellman backup for obtaining the Q-function of a given policy ,,
T=Q(8, a) = r(s,a) a) + E. (
[(()
(1)
2

---

Under review as a conference paper at ICLR 2021
The target Q-values the right hand side depend on action samples a' ~ (a''ss). If the sampled actions are outside the distribution of actions observed in D. the estimated Q-values can be erroneous leading to incorrect target values. The effects of action distribution shift are further exacerbated in actor-critic algorithms; out of distribution (OOD) actions may incorrectly be assigned high values, in which case the policy will be updated to further sample OOD actions, leading to a hazardous loop-
An important approach - with particular recent interest to mitigate the effects of both kinds of distributional shift is devise methods for constraining learned policies to remain close to the behavior policy μ. d² (s, a) x d"(s,a) Below, we set the stage by reviewing a closely related prior work in offline RL.
Batch Constrained Q-Learning (BCQ) In BCQ (Fujimoto et al. 2018a| Sa) the aim is to constrain a Q-Learning based algorithm such that will be effective the offline RL continuous control setting with function approximators. To do so, the trained policy is parameterized as: for
To (als) = arg max Qu az Eo(s, a;)) a, (o(,,))))
a, ~ p(als), = I,,., N
(2)
y(s, a, s' r,t) r,t)
(++ ya (s(()a for de To(os'''s) N (3)
LQ = (v(s,a, s', Qx(,
(4)
where y(s,a) a) are target Q-values, Q is learned with the objective in equation 4 p(als) s) is an estimate of the base behavior policy generative model trained using the dataset D), and &e is an action perturbation model trained to modify actions towards more optimal ones. Crucially, each
component of the output of &o is bounded to the range b, +). The key intuition is that because o; are sampled from an estimate of the behavior policy, they should hopefully be within the distribution observed in D. Thus, since the perturbation model is constrained by the hyperparameter 4, the perturbed actions should not be too far from actions in the dataset. This should mitigate errors in value estimates, which should in turn lead to better updates for the perturbation model.
EXPECTED-MAX Q-LEARNING
We make the observation that, in the BCQ algorithm, if we could obtain good estimate (u(ass and sufficiently increased the number of samples N, there would be no need for the perturbation network fa. This simplification would remove one additional function approximator and the associated hy- perparameter Φb This is the driving intuition of our work, which we frame theoretically in a manner that encapsulates the key components: the behavior policy j and number of samples N. Below, we introduce the Expected-Maz Q operator, illustrate its key properties for tabular MDPs, and obtain sub-optimality bounds which can serve as a novel measure of complexity of an offline RL problem for future theoretical work. We then provide an extension to the offline RL setting with function approximators, and then discuss the generative model used to approximate the behavior policy.
3.1 EXPECTED-MAX Q OPERATOR
Let plaass s) be arbitrary behavior policy, and let {a,} ~ uuaas) denote sampling N iid actions from uu(a(s (). Let Q S x A + R an arbitrary function. For a given choice of N, we define the Expected-Max Q-Learning operator (EMaQ) T Q as follows:
Q(,,(s))) = r(s, r
a) + E. E. (agg~~alls)
max d'ElaiPN
Q(d,a')
(5)
Q- O-Evaluation for μ
TsQ(s, = = Ey E. and (o) QQ(ssaaa)
(6)
Q-Learning
T*Q(s,)) = rx, + E. max Q(s)
This operator provides natural interpolant between the on-policy backup for μ (Eq. 6) when
N = 1, and the Q-learning backup (Eq. 7 as N - oc (if p(als) has full support over A). We formalize these observations more precisely below when articulate the key properties in the tabular MDP setting. We discuss how this relates to existing modified backup operators in the related work.
3

---

Under review as a conference paper at ICLR 2021
3.2 DYNAMIC PROGRAMMING PROPERTIES IN THE TABULAR MDP SETTING
To understand any novel backup operator it is useful to first characterize its key dynamic program- ming properties in the tabular MDP setting. First, we establish that EMaQ retains essential contrac- tion and fixed-pe fixed-point existence properties, regardless of the choice of N N. In the interest of space, all missing proofs can be found in Appendix A
Theorem 3.1. In the tabular setting, for any N E IN, TEN contraction operator in the fooe. norm. Hence, with repeated applications of the T,N, any initial Q function converges to a unique fixed point.
Theorem 3.2. Let QN denote the unique fixed point achieved in Theorem 3.1 and let Ty T (als)
denote the policy that samples N actions from p(a]s). {a.}%. and chooses the action with the N
maximum Q2- Then Q2 is the Q-value function corresponding to xp (als).
Proof. (Theorem
3.2 Rearranging the terms in equation 5 we have,
TyN QN (s, a) = r(s, a) + Eg Eug (dl)s) (s', as',
Since by definition QN is the unique fixed point of T,N, we have our result.
From these results we can then rigorously establish the interpolation properties of the EMaQ family. Theorem 3.3. Let áh denote the optimal policy from the class of policies whose actions are re- stricted lie within the support of the policy plals). Let Qú denote the Q-value function cor- responding Tzz- Furthermore, let Q₁ denote the Q-value function of the policy p(a)s). Let (s) == Ssupportis (alo)) p(aas) denote the probability of optimal actions under p(a s). Under the assumption that inf, y μ² (s) > 0 and r(s, a) is bounded, we have that,
and
Tim ON =Q N
That is. Theorem 3.3 shows that, given base behavior policy p(als), the choice of N makes the EMaQ operator interpolate between evaluating the Q-value of μ on the one hand, and learning the optimal Q-value function on the other (optimal subject to the support constraint discussed in Theorem 3.3 In the special case where p{a)ss) s) has full support over the action space A, EMaQ interpolates between the standard Q-Evaluation and Q-Learning operators in reinforcement learning.
Intuitively, as we increase N, the fixed-points QN should correspond to increasingly better policies N TH (als). We show that this is indeed the case.
Theorem 3.4. For all N. M IN. where N M, have that Vs E S, Va E Support(u(-Is)) ON (s. 2 Q. (s,a). a). Hence, N (als) is at least as good of a policy as T. (als).
It is also valuable to obtain sense of how suboptimal T. (als) may be with respect to the optimal policy supported by the policy u(als). Theorem 3.5. For 3 E S let,
A Nss
max (, Fla.*~a max (7 be(a;
aESuppon(p(119))
The suboptimality of QN can be upperbounded follows. -
12 - Qill S 7 max F.y ( ND) 1-
7 max Asa N)
(8)
The same also holds when Qú is replaced with Q in the definition of A.
3.3 A MEASURE OF COMPLEXITY FOR OFFLINE RI.
The bounds in equation g capture the main intuitions about the interplay between p(als) and the choice of N. If for each state, μ(aas) places sufficient mass the optimal actions, n will be
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Test-Time Policy Tiss
Function Test Ensemble e (values):
return X -min(valus)) (1 - X). max(ualues)
Function Test (8):
{ag} ~ p(als)
return arg {a. Test TestEnsemmlee(Q((s.. for all :l)
close to ".. The two variants of (ss, N), based on Q or QN suggest an intriguing notion of difficulty for an offline RL problem. If we could estimate either of these Q-value functions, then for a desired set of states (such as initial states) we could plot N)) as decreasing function of N. The rate at which this function decreases could serve as an intuitive notion of difficulty for given offiine offline RI. problem which consists of an MDP and given behavior policy. While we leave theoretical investigations of this measure for future work, our empirical results in Section demonstrate that the effective value of N may be surprisingly small.
3.4 OFFLINE RL. SETTING WITH FUNCTION APPROXIMATORS
Typically, we not provided with the policies that generated the provided trajectories. Hence, as a first step we fit a generative model s(ass) to the (s, a) pairs in the offline dataset, representing the mixture of policies that generated this data (details below). Having obtained u(als), move to the EMaQ training procedure. Similar to prior works (Fujimoto et al., 201 Kumar et al.) 2019)] Wu et al. 2019). we train K functions (represented by MLPs) and make use of an ensembling procedure to combat overestimation bias (Hasseli, [2100] Van Hasselt et al., 2016 Fujimoto et al. 2018b). Letting D represent the offline dataset, the objective for the Q functions takes the following form:
[(0.) = Ess.add [Q0 v(s, (ls,a,s',n -,,
(9)
y(s, a, s,, = (++ max Veno
for ai "(dd)s'),; (10)
where t is the indicator variable 1[s' is terminal], and Q represents the ensemble of target Q functions. In short, we sample N actions from p(a' [s') and take the value of the best action to form the target. The algorithm box describing the full training loop can be viewed in Algorithm 2
Notably, we do not train an explicit neural network representing the policy. At test-time, given state we sample N actions from s{aas) and choose the action with the maximum value under the ensemble of Q functions (see Algorithm]] T). While Test Ensembl e can differ from the Ensembl l e function used compute target values in this work used the same ensembling procedure with = 1.0 (with the exception of experiments in Section
3.5 INTUITION FOR OFFLINE EMAQ AND MODELING p(als)
The intuition for how offline EMaQ aims to address the problem of erroneous value estimates can be understood from attending to equation 10 and the form of the test-time policy (Algorithm [ In equation 10 we observe that target values for the Q functions are computed by sampling actions from the behavior policy estimate μ., and not a separately learned policy that may sample out of distribution actions, as in BCQ. At test-time, our implicit policy is also formed by choosing amongst actions sampled from μ. Hence, if μ accurately estimates the behavior policy well, we will never sample actions outside the support and will not need evaluate the value of such actions. In the practical setting where y may have inaccuracies, the hyperparameter N acts as an implicit regularizer: Using very large values of N maximizes the chance of sampling actions that are out
some examples of alternative choices are mean, max, UCB-style estimates, simply using just one of the
trained Q functions
5

---

Under review as a conference paper at ICLR 2021
of distribution and have erroneous value estimates, while smaller N reduces the chance of this happening in every update iteration and therefore smoothens the incorrect values.
With the importance of good behavior estimates accentuated in our proposed method, we pay closer attention to the choice of generative model used for representing μ.. Past works (Fujimoto
et al. 2018a; Kumar et al. 2019 Wu et al. 2019) have typically used Variational Auto-Encoders (VAES) (Kingma & Welling, 2013) Rezende et al.] 2014) to represent the behavior distribution (a]ss) Unfortunately, after training the aggregate posterior Onge = Ez [g(=]==]] of VAE does not typically align well with its prior, making it challenging to sample from in a manner that ef- fectively covers the distribution it was trained or We opt for using an autoregressive architecture based on MADE (Germain et al. (2015) as it allows for representing more expressive distributions and enables more accurate sampling. Inspired by recent works (Metz et al. 2017| Van de Wiele et al.) 2020), our generative model architecture also makes use of discretization in each action dimension. Full details can be found in Appendix B
4 RELATED WORK
Offiine RL.
Many recent methods for offline RL (Fujimooo et al. 201 8a Kumar et al. 2019 Wu
et al., 2019 Jaques et al. 2019), where no interactive data collection is allowed during training, mostly rely on constraining the learned policy to stay close to the data collection distribution. Fuji- moto et al. (2018) 8a) clip the maximum deviation from actions sampled from base behavior policy, while Kumar et al. 2019): : Wu et al. 2019); : Jaques et al. (019 incorporate additional distribu- tional penalties (such as KL divergence or MMD) for regularizing learned policies to remain close to the base policy. Our work is an instance of this family of approaches for offline RL; however, arguably our method is simpler it does not involve learning an additional proposal-modifyin policy Fujimoto et al. (2018a), or modifying reward functions (Kumar et al. 2019 Jaques et al, 2019
Finding Maximizing Actions Naively, EMaQ can also be seen as just performing approxi- mate search for max ((s,a) a) in standard Q-learning operator, which has been studied in various prior works for Q-learning in large scale spaces (e.g. continuous). NAF (Gu et al.] 2016b) and ICNN (Amos et al., 2017) directly constrain the function family of Q-functions such that the opti- mization can be closed-form or tractable. QT-OPT (Kalashnikov et al.) 2018b) makes use of two iterations of the Cross-Enntroy Method (Rubinstein & Kroesel| 2013). while CAQL (Ryu al. 2019) uses Mixed-Integer Programming to find the exact maximizing action while also introducing faster approximate alternatives. In (Van de Wiele et al. 2020) the most similar approach to our pro- posed method EMaQ throughout training mixture of uniform and learned proposal distributions are used to sample actions. The sampled actions are then evaluated under the learned Q functions, and the top K maximizing actions are distilled back into the proposal distribution. In contrast to our work, these works assume these are approximate maximization procedures and do not provide extensive analysis for the resulting TD operators. Our theoretical analysis on the family of TD oper- ators described by EMaQ can therefore provide new perspectives on some of these highly successful Q-learning algorithms (Kalashnikov et al. 201 Sa Van de Wiele et al. 2020) particularly how the proposal distribution affects convergence.
Modified Backup Operators Many prior works study modifications to standard backup opera-
tors to achieve different convergence properties for action-value functions or their induced optimal policies. V-learning (Rawlik et al.) 2013) proposes a modified operator that corresponds to policy
iterations with KL-constrained updates (akaade 2002 Peters et al., 2010:; Schulman et al., 2015)
where the action-value function converges to negative infinity for all sub-optimal actions. Similarly ly
but distinctly, Fox et al. (2015); Daques et al. (207)) Haarnoja et al. (2018): Nachum et al. (2017)
study smoothed TD operators for modified entropy- KL-regularized RL objective. |elllemare
ee al. 2016) derives a family of consistent Bellman operators and shows that they lead to increasing
action gaps (Farahmand [01T) for more stable learning. However, most of these operators have
not been studied in offline learning. Our work adds a novel family operators to this rich literature of
ppast works typically clip the range of the latent variahle and adjust the weighting of the KI. term in the evidence lower-bound to ameliorate the situation

---

Under review as a conference paper at ICLR 2021
Random
Medium
Mixed
Medium-Expert
HalfCheetah
5000
D020
50C0
0000
1000
1002
2020
0l050
10
75
50
150
760
A00
15
25
50
150
700
920
10
05
100
750
450
5
10
75
93
160
760
450
4000
I
Walker
3000
3300
2300
1000
1000
50 EHGQ
150
A20
150
10
75
50
360
700
420
BN30
ENUO
1500
1000
900
2300
Hopper
375
800
I
2000
700
300
500
BM00
EN50
BN20
B400
Figure 1: Results for evaluating EMaQ on D4RL benchmark's (Fu et al. 2020b) standard Mujoco domains, with N E (5, 10, 20, 50, 100, 200, 400). Values above p(als) represent the result of evaluating the base behavior policies. Horizontal green lines represent the reported performance of BEAR in the D4RL benchmark (apples to apples comparisons in Figure 2 The types of offline datasets are: random: 1M transitions collected by random agent, medium: IM transitions are collected by half-trained SAC (Haarnoja et al. 2018) policy, mixed: the replay buffer of this half-traine trained policy, and medium-expert: combination of the medium dataset and 1M additional transitions from fully trained policy. Refer to main text (Section [5.] for description of color-coding. For better legibility, we have included larger variant of these plots in the Appendix Full experimental details in Appendix G
operators for RI., and provides strong empirical validation on how simple modifications of operators can translate to effective offline RI. with function approximations.
EXPERIMENTS
For experiments we make use of the codebase of (Wu et al. 2019). which presents the BRAC off- off-policy algorithm and examines the importance of various factors in BCQ (Fujimoto et al. (018a)) and BEAR (Kumar al. 2019) methods.
implement EMaQ into this codebase. We make use of the recently proposed D4RL Fu et al. 2020b) datasets for bechmarking offline RL.
Online EMaQ Despite obtaining strong online RL results competitive with and outperforming SAC (Haarnoja al. 2018)) (Figure 3 the main focus of our work is for the offline setting, have placed our online RL methodology and results in Appendix F However, we emphasize that significance of obtaining strong online RL performance with effectively the same algorithm the offline setting should not be overlooked. Most prior offline RL works have not considered how their methods might transfer to online batched online setting, and recent work (Nair et al. 2020) has demonstrated the challenges of finetuning from a policy trained offline, in the online setting.
5.1 PRACTICAL EFFECT OF N AND THE CHOICE OF GENERATIVE MODEL μ
We begin by empirically evaluating key aspects of offline EMaQ, namely the effect of N, and choice of generative model used for representing the behavior estimate μ. In prior approaches such those described in the background section of this work, care must be taken in choosing the hyperparam- eter that dictates the extent to which learned policies can deviate from the base behavior policies; too small and we cannot improve upon the base policy, too large and the value of actions cannot be correctly estimated. In EMaQ, at least in theory, choosing higher values of should result in strictly better policies. Additionally, there exists concern that N may need to be impractically large. Thus, we empirically investigate to what extent the monotonic trend holds in practice, and seek to understand what magnitudes of N result in good policies in practical benchmark domains. Figure [ presents our results with e (5, 10, 25, 50, 100. 200, 400). In the green plots, we ob- serve that empirical results follow our intuitions: with increasing N the resultant policies become

---

Under review as a conference paper at ICLR 2021
Random
Medium
Mixed
Medium-Expert
HalfCheetah
1000
I I
80
Walker
Hopper
200
Massoggl
Figure 2: Comparison of EMaQ. BCQ, and BEAR on D4RL (Fu al. 2020b) benchmark domains when using our proposed autoregressive j(als). For both BCQ and BEAR, from left right as the value of the hyperparameter increases, the allowed deviation from ((a.s) increases. Horizontal green lines represent the reported performance of BEAR in the D4RL benchmark. Color-coding follows Figure [ For better legibility, we have included a larger variant of these plots in the Appendix Full experimental details in Appendix G
better. In the medium-expert settings (i.e. orange plots), while for smaller values of N we observe strong performance, there appears to be a downward trend. As discussed in Section 3.5 smaller values of N result an implicit regularization. Hence, the orange plots may indicate that even with the stronger choice of generative models in EMaQ, inaccuracies in value estimates may still exist, suggesting the need for future work that introduces better regularizers for the value functions than ensembling (Kumar et al. 2020). Lastly, the red plots indicate settings where behavior is erratic. Closer examination training curves and our experiments with other off-policy methods (Figure suggests that this may be due to the intrinsic nature of these environment and data settings.
The dashed horizontal lines in Figure 2 represent the performance of BEAR which uses a VAE for representing μ reported in the D4RL (Fu et al. 2020b) benchmark paper (apples to apples com- parison in Section 5.2).. Our results demonstrate that the combination of a strong generative model match and in many
and EMaQ's ss simply constrained backup operator results from prior algorithms and design choices. Comparing Figure 2 to Figure in the Appendix, observe that our choice of generative model is crucial to the performance of EMaQ. With VAE architecture as used in prior work, EMaQ's performance is significantly reduced, most cases worse than prior reported results for BEAR, and never exhibits a monotonic trend function of N. This is despite the fact that when evaluating the performance of the behavior estimate μ under the two architecture choices results almost identical results (the first column of each sub-plot corresponding to μ(a|s)). We do not believe that autoregressive models are intrinsically better than VAEs, but rather our results demonstrate the need for more careful attention on the choice of μ(als). Since EMaQ is closely tied to the choice of behavior model, it may be more effective for evalu- ating how well ((as)) represents the given offline dataset. From practical perspective, our results suggest that for given domain, focusing efforts on building-in good inductive biases in the generative models and value functions might be sufficient to obtain strong offline RL performance in many domains.
noticeably exceed
5.2 COMPARISON ON D4RL OFFLINE RL BENCHMARK
To evaluate EMaQ with respect to prior methods, we compare to two popular and closely related prior methods for offline RL, BCQ (Fujimoto et al. 201 8a) and BEAR (Kumar al. 2019). As with the previous section, full experimental details can be found in Appendix G..l| Figure and Table present
empirical results. Note that with proposed autoregressive models, the sults for BEAR are matched and some cases noticeably above the values reported in the D4RL benchmark (Fu et al. 2020b) (green horizontal lines). For easier interpretation, the plots are colored
8

---

Under review as a conference paper at ICLR 2021
Sefting
BC
BCQ
BEAR
EMaQ
EMMQ
kitchen-complete
27.2 3.2
26.5
36.9
64
kitchen-partin
46.2 + 2.8
5.23
74.6 0.6
8
kitchen-mixed
52.5 + 3.8
6.85
70.8 + 2.3
8
antmaze-umate
59.0
25,5
56.3 = 28.8
91.0 = 4.6
100
antmarreuumaze-iivere
58.8
68.0 19.0
57.5 39.2
94.0 + 2.4
50
medmaze- play
0.7 = 1.0
3,5
0.2 = 0.4
0.0 = 0.0
antmaze-medium diverrs
0.4 = 0.8
0.9
0.2 0.4
0.0 = 0.0
antmaze-large-play
0.0 + 0.0
0.0
0.0 + 0.0
0.0
antmaze-large-dine diverse
0.0 0.0
0.0
0.0 0.0
0.0
door-cloned
0.0
0.2
0.0 0.0
0.2 = 0.3
64
hammer-cloned
1.2 0.6
1.3 0.5
0.3 0.0
1.0 = 0.7
64
pen-cloned
24.5 + 10.2
43.8
+ 6.4
-3.1 =.2
27.9 3.7
128
relocate-cloned
-0.2 + 0.0
-0.2 + 0.0
0.0 - 0.0
-0.2 + 0.2
16
Table 1: Results on a series of other environments and data settings from the D4RL benchmark (Fu et al. 2020aj. Results are normalized to the range [0. 100), per the D4RL normalization scheme. For each method, for each enviromment and data setting the results of the best hyperparameter setting reported. The last column indicates the best value of in EMaQ amongst the considered hyperparameters (for the larger antmaze domains, we do not report this value since no value of obtains nonzero returns). All the domains below the blue double-line are effectively unsolved by all methods. We have technical difficulties in evaluating BEAR on the kitchen domains. This manuscript will be updated upon obtaining these results. Additional details can be found in Appendix
the same as in Figure [ Our key take-away is that despite its simplistic form, EMaQ is strongly competitive with prior state-of-the-art methods, and in the case of Table [ outperforms prior ap- proaches. Despite this, there remain many domains in the D4RL benchmark on which none of the considered algorithms make any progress (Table TT. indicating that much algorithmic advances are still necessary for solving many of the considered domains.
very eye-catching result in above figures is that in almost all settings of the standard Mujoco environments (Figures andd matches or exceeds sigmificantly beyond previously reported results. Concretely, this means that in the HalfCheetah- Random setting, if at each state we sample actions uniformly random and choose best one under the learned Q-value function, we convert a random policy with return policy with return 2000. In this way, EMaQ provides quite intuitive and surprising measure of the complexity for offline RL problems. This empirical observation also corroborates our discussion in Section 3.3, encouraging future theoretical investigations into A A(s, N).
and 2), just N = significantly improves upon juals) and in most settings
CONCLUSION
In this work, we investigate significant simplification the BCQ (Fujimoto et al. 2018a) algorithm by removing the heuristic perturbation network. By introducing the Expect-Max Q-Learning opera- tor, we present a novel theoretical setup that takes into account the proposal distribution (a)s)) and the number of action samples N, and hence more closely matches the resulting practical algorithm. With fewer moving parts and one less function approximator, EMaQ matches and outperforms prior state-of-the- ootthe--tttttttte- in online and offline RL. Our investigations with EMaQ demonstrate the significance of careful considerations in the design of generative models used. Furthermore, our theoretical and empirical findings bring into light novel notions of complexity for offline RL problems. Given the simplicity, tractable theory, and state-of-the-ar performance of EMaQ, we hope our work can serve as foundation for future works on understanding and improving offline RI.
REFERENCES
Brandon Amos, Lei Xu, and Zico Kolter. Input convex neural networks. Proceedings of the 34th International Conference on Machine Learning- Cromming-Vollmee 70, pp. 146-155. JMLR. org, 2017.
Mare G Bellemare, Georg Ostrovski, Arthur Guez, Philip S Thomas, and Rémi Munos. Increasing the action gap: New operators for reinforcement learning. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.

---

Under review as a conference paper at ICLR 2021
Richard Y Chen, Szymon Sidor, Pieter Abbeel, and John Schulman. Ucb exploration via qr ensembles. arXiv preprint arXiv: 2017.
Thomas Degris, Martha White, and Richard S Sutton. Off-policy actor-critic. arXiv preprint (rXiv:1205.48333 2012.
Amir-massoud Farahmand. Action-gap phenomenon in reinforcement learning. In Advances in Neural Information Processing Systems, pp. 172-180, 2011.
Roy Fox, Ari Pakman, and Naftali Tishby. Taming the noise in reinforcement learning via soft updates. arXiv preprint arXiv: 1512.08512 2015.
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning, 2020a.
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. Datasets for data-driven reinforcement learning. arXiv preprint arXiv:2004.07219 2020b.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without 2018a.
exploration. arXiv preprint arXiv:
Scott Fujimoto, Herke Van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. arXiv preprint arXiv: 1802.088009900 8802009777, 2018b.
Mathieu Germain, Karol Gregor, lain Murray, and Hugo Larochelle. Made: Masked autoencoder for distribution estimation. In International Conference on Machine Learning, pp. 881-889, 2015.
Shixiang Gu. Timothy Lillicrap, Zoubin Ghahramani. Richard E Turner, and Sergey Levine. Q- prop: Sample-efficient policy gradient with an off-policy critic. arXiv preprint arXiv:1611.0224/ 2016a.
Shixiang Gu, Timothy Lillicrap, Ilya Sutskever, and Sergey Levine. Continuous deep q-learning with model-based acceleration. In International Conference on Machine Learning. 2016b.
Shixiang Gu, Ethan Holly, Timothy Lillicrap, and Sergey Levine. Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates. In International Conference on Roboties and Automation, 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. arXiv preprint 0000000290, 2018.
Hado V Hasselt. Double q-learning. In Advances in neural information processing systems, pp- 2613-2621, 2010.
Natasha Jaques, Shixiang Gu, Dzmitry Bahdanau, José Miguel Hermández-Lobato, Richard E Turner, and Douglas Eck. Sequence tutor: Conservative fine-tuning of sequence generation mod- els with kl-control. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1645-1654. JMLR. org, 2017.
Natasha Jaques, Asma Ghandeharioun, Judy Hanwen Shen, Craig Ferguson, Agata Lapedriza, Noah Jones, Shixiang Gu, and Rosalind Picard. Way off off-policy batch deep reinforcement learning of implicit human preferences in dialog. arXiv preprint
2019.
Sham M Kakade. A natural policy gradient. In Advances in neural information processing systems, pp. 1531-1538, 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, 20.
10

---

Under review as a conference paper at ICLR 2021
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Qt-opt: Scalable deep reinforcement learning for vision-based robotic manipulation. arXiv preprint arXiv:1806.1022. 2018b.
Diederik P Kingma and Max Welling. arXiv:1312.6114 14, 2013.
Auto-encoding variational bayes.
arXiv preprint
Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. Stabilizing off- policy q-learning via bootstrapping error reduction. In Advances in Neural Information Processing Sys- tems, 2019.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. arXiv preprint arXiv:2006. 2007:9000600777, 2020.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems. arXiv preprint arXiv:2005.0164) 2020.
Timothy P Lillicrap. Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver. and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint 1009v:5509.00000 2015.
Travis Mandel, Yun-En Liu, Sergey Levine. Emma Brunskill, and Zoran Popovic. Offline policy evaluation across representations with applications to educational games. International Con- ference Autonomous Agents and Multiagent Systems, 2014.
Tatsuya Matsushima, Hiroki Furuta, Yutaka Matsuo, Ofir Nachum, and Shixiang Gu. Deployment- efficient reinforcement learning via model-based offline optimization. arXiv preprint 00X44 2020.
Luke Metz, Julian Ibarz, Navdeep Jaitly, and James Davidson. Discrete sequential prediction of continuous actions for deep rl. arXiv preprint arXiv:1705.0503: 2017.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, Nature, 5 518(7540):529-51) 2015.
Susan A Murphy, Mark J van der Laan, James M Robins, and Conduct Problems Prevention Re- search Group. Marginal mean models for dynamic regimes. Journal of the American Statistical Association, 2001.
Ofir Nachum, Mohammad Norouzi, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2772-2782, 2017.
Ashvin Nair, Murtaza Dalal, Abhishek Gupta, and Sergey Levine. Accelerating online reinforcement learning with offline datasets. arXiv preprint arXiv:2006.099 09359, 2020.
Jan Peters, Katharina Mulling, and Yasemin Altun. Relative entropy policy search. In Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010.
Doina Precup, Richard S Sutton, and Sanjoy Dasgupta. Off-policy temporal-differee learning with function approximation. In International Conference on Machine Learning, 2001.
Konrad Rawlik, Marc Toussaint, and Sethu Vijayakumar. On stochastic optimal control and rein- forcement learning by approximate inference. In Twenty-Tiie Third International Joint Conference on Artificial Intelligence, 2013.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. arXiv preprint arXiv:1401.4082. 2014.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and struc- tured prediction to no-regret online learning. In Proceedings of the fourteenth international con- ference artificial intelligence and statisties, pp. 627-635, 2011.

---

Under review as a conference paper at ICLR 2021
Reuven Y Rubinstein and Dirk P Kroese. The cross-entropy method: &unified approach combina- torial optimization, Monte-Carlo simulation and machine learning. Springer Science & Business Media, 2013.
Moonkyung Ryu, Yinlam Chow, Ross Anderson, Christian Tjandraatmadja, and Craig Boutilier. Caql: Continuous action q-learning. arXiv preprini arXiv: 12397, 2019.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897, 2015.
Tom Van de Wiele, David Warde-Farley, Andriy Mnih, and Volodymyr Mnih. Q-learning in enor-
mous action spaces via amortized approximate maximization. arXiv preprint arXiv:2001.08///, 2020.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double qr learning. Thirtieth AAAI conference on artificial intelligence, 2016.
Lilian Weng.
Exploration strategies
deep reinforcement learning, Jun
2020.
URI.
explorat www.iioottstttsss-steeoeeee
Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning.
arXiv preprint arXiv:1911.11360 2019.
12

---

Under review as a conference paper at ICLR 2021
A
PROOFS
All the provided proofs operate under the setting where p(a[s) has full support over the action space. When this assumption is not satisfied, the provided proofs can be transferred by assuming operating new MDP Mp as defined below.
Given the MDP M (S,A.r, P.r) and p(als), let define the MDP Mμ Ap; r. 2,7), where Sy denotes the set of reachable states by μ, and Ap A restricted to the support of p(aas) in each state in Sy,-
A.1 CONTRACTION MAPPING
Theorem 3.1. In the tabular setting, for any N E IN, T is a contraction operator in the Loo norm. Hence, with repeated applications of the TNN any initial Q function converges to unique fixed point.
Proof. Let Q1 and Q2 be arbitrary Q functions.
T Q1 - Tp 221lo0
(11)
(r(s,a) + + Ey Bia
max (1(6', - (r(s, + -Er max Q2(s',a')) {a,)
max 5.a
{a,)
(12)
max
Fgg Egg.E.aa {a.}
max a'() - max O2 ad) (a
(13)
(o.]
max E, E (a:)
max Q1(s', [o.}8
max Q2(5',a) S [a.}
(14)
max E, E(,
11Q: Q21 =
(15)
- ||Q -Q2l1a-
(16)
where line 15 is due the following: Let arg max Qi(s', as)),
max {a,}*
Q1(8', - max {a,}*
Q2(s', = Qi(''á)) - max Q2(5',a)
(17)
{a:
$ $ - Q2(s',a)
(18)
< I1Qu - -221l
(19)
A.2 LIMITING BEIIAVIOR
Theorem 3.3. Let oi denote the optimal policy from the class of policies whose actions are re- stricted to lie within the support of the policy p(a s). Let Qº denote the Q-value function cor- responding to Th. Furthermore, let Qu denote the Q-value function of the policy p(a)s). Let 4² (*())) == JSupport<;; (al=)) p(a)s) denote the probability of optimal actions under p(a s). Under the assumption that inf, μ² (s) > and r(s, a), we have that, and
Q1 Q₂
lim O =
N
Let (s) = (Support(=;(als)) ({aas) denote the probability of optimal actions under μ(aas). To show 1om Q 2r we also require the additional assumption that inf, 4z" (s) > O.
Proof. Given that,
Ty Q(s, == r(, + +, (xp(lee) [Q(s', aa)]
(20)
the unique fixed-point of T is the Q-value function of the policy u(als). Hence Q). = Qu.
The second part of this theorem will be proven Corollary Theorem 3.5
13

---

Under review as a conference paper at ICLR 2021
A.3 INCREASINGLY BETTER POLICIES
Theorem 3.4. For all N, N.M E N. where N > M, we have that Vs E S. Va E Suppor(u((1s)), (s. 2 Qp (s,a). a). Hence, Tp (als) is at least as good of a policy as a (als).
Proof. is sufficient to show that Vs, a, + 2 Q (s, a). We will do so by induction. Let Q' denote the resulting function after applying T,+11, i times, starting from Q
Base Case
By definition Qo = Q2 Let S, S, E.
(=(s,a) = T T.N++ (NN+IQ((ssa)
(21)
a)( +7 F.g (to.)+t max ('')
(22)
(a.
r(s,a) +7 E. (o.) -
max (sss
(23)
{a.)x
ar(;,a) +7. E. MMa max Q (s', a')]
(24)
{a,)
= (s,a)
(25)
(s),a)
(26)
Induction Step
Assume Vs, a, Q' a) (s))
(sta - Q((ssa) = T, T.N+IQ' (8, T
TTN+tQii'(ss. (s,
(27)
=9 =7- (a. max Q'ss',a')-
max
(5-1(s',a"))
,a)]
(a.)
{a. N4.1
(28)
20
(29)
a). Since Q = Q and lim Q = Q,N+1, we have than Vs, a, (8, 2 (s, Thus = is better policy than T and by a simple induction argument, Tp is better policy than T when N > M.
Hence, by induction we have to Vi,ji> = Vs,a (s,,) 2 Q'
A.4 BOUNDS
Theorem 3.5. For E let.
A(s) = max (s,s,)) - BlarpN max (7 b)]
(ESuppot(u((1)))
bE(a,)
The suboptimality of Q can upperbounded as follows.
|1 Qiil
5
-T a.
7 max Eg ( S 7 max A(s)
(30)
The same also holds when Qú, is replaced with Q in the definition of A.
Proof. The two versions where ((s) is defined in terms of QN and Q7 have very similar proofs.
Version with Q
14

---

Under review as a conference paper at ICLR 2021
Let TQ% denote the backup operation in Q-Learning. Let (TQl)ym = -T o Thh o... T
We
m times
know the following statements to be true:
Q = Tp" QN = r((s,a) a) + Ea (M max QN aa)]
(31)
(or) TOI = (s,,a) +y Ey max 0 (s',
(32)
lim (TRI)m m 0/"² = =Q"
(33)
m-100
[ 2N - (TQ4)m Q mm S.. 1(T ON - NN
(34)
|[
0F - (TR4)m m Q 1l.0 - 1|T - 11
(35)
Putting these together we have that,
|00 - Q-1
(
QN - (T 10
(36)
m==
|| Q/
ym
(37)
m=0
||TRLON - 22%1
(38)
(1(s.0) + Eg max ON (5', aa)) a'
max 1 y 8a
(39)
- (r(s,a) +y- Eg
(0)
max Qn (s', ad)))
(40)
{a.)"
1 7 max E max 0 (s', d') - [aa)) m( (0))
max ON (s', (s,,'')]
(41)
(a.}
max max (5's'
(s', d')
Lugex Q (6', 07066' ad')
(42)
Version with Q%
Very similarly we have,
110 Q-
[I m -
(43)
m=0
| Q- - 11
(44)
m=0
1 l|Q' -TN@Q"
(45)
1 max
(1(s,0)+ +7 Es max ('((,aa))
(46)
7 sa
- (1(3,0) a) + (ag (5)
mmxx Q'(6' ad1)) {a.)x
(47)
max
Egg max Q¹ a'ss'aa'= - (aaa))aaloo ss)
[max Q* Q'(5aa1]
(48)
1 ? 8.0
(a.)
max
max Q'x a²) | /mx Q"(s', ,a')
(49)
(a.)"
15

---

Under review as a conference paper at ICLR 2021
Corollary A.1. Let Vn Qui Ay denote the value, Q and advantage functions of p respectively. When N = we have that,
11Qu - 10000 5
?
max
max Qu(s', d') Ea'n Eas (o
(50)
1 y
a'
7
max
max Qu(s', ,'') Vi(('))
(51)
1 -
1 max A d')
(52)
It is interesting how the sub-optimality can be upper-bounded in terms of a policy's 's own advantage function.
Corollary A.2. (Proof for second part of Theorem 3.3
Proof. We want to show lim OF Q" More exactly, what we seek to show is the following,
lim 11
10 =0
(53)
N
or,
Ve > ON,,, s.t. AM A NM 1
101 <e
(54)
Let c > O. Recall,
(ss)
max
(7 a) E( (Mpp)~p((()))))))))))))))))))))) max (7 b)]
(55)
aESuppon(n(
bE(a,)
Let inf, (s) = p > O. Let the lower and upper bounds of rewards be and L, and let a 1
and B LL L. We have that,
E [a. max (7, 2 (1 (1 (1-p) b
max aESuppon(a((aa)
(1(5, a) (56)
Hence Vs.
(s) S (1 - >)
max
(1 a) - (1-1)²
(57)
aESuppon(p((1s))
= =(1 - p)
max
(2(s, a) -a)
(58)
(ESuppes((p(11b)
$ (1 - p). (3
(59)
Thus, for large enough N we have that,
12 27 10.1300 S 1-7
max A(s) <
(60)
concluding the proof.
B AUTOREGRESSIVE GENERATIVE MODEL
The architecture for our autoregressive generative model is inspired by the works of (Metz al., 2017 Van de Wiele et al. 2020; Germain et al. 2015). Given a state-action pair from the dataset (s, a), first an ML.P produces didimensional embedding for s, which we will denote by h. Below, the notation a, to denote the 7th index of a, and d[s)] to represent slice from first up to and not including the ith index, where indexing begins O. We use discretization in each action dimension. Thus, we discretize the range of each action dimension into N uniformly sized bins, and represent a by the labels of the bins. Let E, denote the label of the 7th action index.
Training
We use separate MLPs per action dimension. Each MLP takes in the d-dimensional state embedding and ground-trute ttrth actions before that index, and outputs N logits for the choice over bins. The probability of given index's 's label is given by,
ple,|s, al: i)) SoftMax (MLP al: i1) [4,]
(61)
We standard maximun-likelihood training (i.e. cross-entropy loss).
16

---

Under review as a conference paper at ICLR 2021
Sampling
Given state s, sample action again embed the state, and sample the action indices one-by-one.
p((ols) = SoftMax (c))(())
(62)
6 p(cols), ao Uniform Bin corresponding to kn)
(63)
p((]s) SoftMax MMP.. al: i1) [4]
(64)
4 ~ p(,,ss, al: i)). Uniform Bin corresponding to E.)
(65)
C ALGORITHM BOx
Algorithm 2: Full EMaQ Training Algorithm
Offline dataset D, Pretrain ({aas) on D
Initialize K Q functions with parameters 0,, and K target Q functions with parameters 0.urges Ensemble parameter X, Exponential moving average parameter
Function Ensemble (values)
return À min min(values) + (1 A) max(values)
Function Ytarge (8, a, s', rr;)):
{at} ~ p(a'ls') Qvalues + for k to do
/x Estimate the value of action df Quolues.append (Bn.aappppeennmbeeeee.... [Ensemble (lQ [IQ (s', d() for all il)
return r + f) max(Qualues)
while converged do Sample batch {smm am, s'm T'a 1m) M D
for I,.., K do
((0,) = Em Qi(mm am) - Vtarget (8m; amm Sy Ti, 4m)
0, 0, AdamUpdate [((,,),
glargct a glarect (1 a) 02
D INCONCLUSIVE EXPERIMENTS
D.1 UPDATING THE PROPOSAL. DISTRIBUTION
Akin to the work of (Van de Wiele et al. 2020). we considered maintaining a second proposal distribution ju that is updated distill arg max x Q(s, a). and sampling from the mixture of μ and j. our experiments however, we did not observe noticeabel gains. This may potentially be due to the relative simplicity of the Mujoco benchmark domains, and may become more important more challenging domains with more uniformly distributed p(als).
E LAUNDRY LIST
Autoregressive models slow generate samples from and EMaQ needs to take many samples, so was slower to train than the alternative methods. However, this may be addressed by better generative models and engineering effort.
17

---

Under review as a conference paper at ICLR 2021
F ONLINE RL
EMaQ is also applicable to online RL setting. Combining strong offline RL methods with good exploration policies has the potential for producing highly sample-efficient online RL algorithms. Concretely, we refer to online RL. as the setting where iteratively, a batch of M environment steps with an exploration policy are interleaved with M RL updates (Levine et al. 2020: Matsushima
eet al. 2020).
EMaQ is designed to remain within the support of the provided training distribution. This however, is problematic for online RI. which requires good exploration interleaved with RI updates. To this end, first, we modify
autoregressive proposal distribution pu(a(s) by dividing the logits of all softmaxes by > 1. This has the effect of smoothing the μ{((s) distribution, and increasing the probability of sampling actions from the low-density regions and the boundaries of the support. Given this online proposal distribution, a criteria is required by which to choose amongst sampled actions. While there exists rich literature on how to design effective RL exploration policies (Weng) 2020), in this work we used simple UCB-style exploration criterion (Chen et al. 2017) as follows:
@explore (s, a) mean (Q, a)}x) + B std (Q:(s,)))x
(66)
Given N sampled actions from the modified proposal distribution, we take the action with highest Qexplore
We compare the online variant of EMaQ with entropy-constrained Soft Actor Critic (SAC) with automatic tuning of the temperature parameter (Haarnoja et al. 2018). For EMaQ we swept the temperatures and used a fixed bin size of 40, Q-function ensembles and N = 200. For fairness of comparisons, we also ran SAC with similar sweeps over different collection batch sizes and number
of Q-function ensembles. In the fully online setting (trajectory batch size 1, Figure 3a EMaQ is already competitive with SAC, and more excitingly, in the deployment-efficient setting (trajectory batch size 50K, Figure 3b). EMaQ can outperform SAC") Figures 4 and 5S) present the results for all hyperparameter settings, for SAC and EMaQ, in the batch size and batch size 50K settings respectively. In the fully online setting, EMaQ is already competitive with SAC, and more excitingly, in the deployment-efficcen setting, EMaQ can outperform SAC.
G OFFLINE RL EXPERIMENTAL DETAILS
For each environment and data setting, we train autoregressive model - as described above on the provided data with random seeds. These generative models are then frozen, and used by the downstream algorithms (EMaQ, BEAR, and BCQ) as the base behavior policy (u(a]s) in EMaQ
G.1 COMPARING OFFLINE RL METHODS
Following the bechmarking efforts of (Wu et al., 2019). the range of clipping factor considered for BCQ & {0.005, 0.015, 0.05, 0.15, 0.5}. and the range of target divergence value considered for BEAR was e E (0.015, 0.05, 0.15, 0.3, 1.5). For both methods, the larger the value of the hyperparameter is, the more the leamed policy is allowed deviate from the p(als).
The rest of the hyperparameters use can be found in Table 2 The autoregressive models have the following architecture sizes (refer Appendix B for description of the models used). The state embedding MLP consists of 2 hidden layers of dimension 750 with relu activations, followed by linear embedding into 750 dimensional state representation. The individual MLP for each action dimension consist of 3 hidden layers of dimension 256 with relu activations. Each action dimension discretized into 40 equally sized bins.
mean that less number of different policies need be executed in the environ- ment, which may have substantial benefits for safety and otherwise constrained domains (Matsushima et all 2020).
By eeployment-efffcceen
It must be noted that the online variant of EMaQ has more hyperparameters tune, and the relative performance is dependent on these hyperparameters, while SAC with ensembles has the one extra ensemble mixing parameter to tune.
While in the original presentation of BCQ and BEAR the behvior policy is learned online, there is techni- cally no reason for this to be the case, and in theory both methods should henefit from this pretraining
18

---

Under review as a conference paper at ICLR 2021
HelfCheetah-v2
Ant-v2
Hopper-v2
Walker2d-v2
15300
DPao 2-10 COR.AA1AA 1:20
SBC 2c200.00..0ll
Die jo-1. P-L2 m-20
SKC P-5 2 Gite)
104
6291
K00
DM6 14-26 p-13 n-38
2
603
500
1250
3002
250
1500
5X3
2004
300
350
2002
1230
883
2500
500
22
04
0.5
03
0.
00
02
14
92
03
(a) SAC vs. EMaQ. Trajectory Batch Size 1: For easier visual interpretration we plot a single hyperparameter setting of EMQQ that tended to perform well across the 4 domains considered. The hyperparameters considered
were N = 200, À= = 1.0, 8 = 1.0, T E {1,5, 10, 20). SAC performed worse when using 8 Q-functions as in EMaQ. x-axis unit is million environment steps.
HaltCheetah-v2
Ant-v2
Hopper-v2 satikaa
Walker2d-v2
14000
17590
10:0
10:03
E4.0 (le) Dht CHO 1027
ENUO (iw3 5.5 D H22
10:0
1003
20:0
430
1882
SAC 2H0T5, Cf
SAC PS BOnS
D460 (4000 100m.0-33 (-33)
-3000
DA6Q 1--1.66 OPTA 5-61, 1-20
(b) SAC vs. EMaQ, Trajectory Batch Size 50K: For easier visual interpretration we plot a single hyperparameter setting of EMaQ that tended to perform well across the 4 domains considered. The hyperparameters considered were N = 200, {0.75, 1.0). 3 E 1.01, steps.
10, x-axis unit is 1 million environment
Figure 3: Online RL results under different trajectory batch sizes.
HalfCheetah.v2
Ant-v2
Hopper-v2
Walker2d.v2
1739
1229
0003
2 0.7, 3 (4m)
4200
SAC di 20mm))
SSC p.-1.00
3000
SAC D4m)
5000
sac pird Ht, a
SeC 4.625 k0
1033
K62
2000
K63
420
AR2
883
665 (.0..5 4.mmu
2003
1090
2003
0.2
33
02
(a) SAC batch I results
HalfCheetah.v2
Ant-v2
Hopper-
Walker2d-v2
14000
EMUD cenbitt tr pw82 (m22)
EMaD 16-6.1t, p-83,
4000
EMUD (le3 soms, p-0. (-10)
(l-3 Bone, F-01
EMud (1e0.15. 5 (=22.
EMaa (--.75, 1 p-22.
BM.D Lenb (w2))
B46L0 (sed soms, PwLL (m2))
BSUG (swc.15 S (=20
11900
4002
3000
119)
KX2
R03
1762 -777 1 94m. J-- c-31
AX3
883
230
D400 (-075 8.0m..0000000 (000. cx28)
2003
1390
3003
(b) EMaQ batch 1 results
Figure 4: All results for batch size 1
G.2 EMAQ ABLATION EXPERIMENT
Hyperparameters are identical to those in Table except batch size is 100 and number of updates 500K.
G.3 DETAILS FOR TABLE ?? EXPERIMENTS
Generative Model The generative models used are almost identical to the description in Appendix
with slight modification that MLP, (d, af: i]) is replace with MLP; (d, Lan: ii)) where Lin, is a linear transformation. This change was not necessary for good performance: it was as architectural detail that experimented with and did not revert prior generating Table ??. The model dimensions for each domain are shown in 3 in the following format (state embedding MLP hidden size, state embedding ML. number of layers, action MI.P hidden size, action ML. number of layers, Ouput
19

---

Under review as a conference paper at ICLR 2021
HolfCheetah-v2
Ant-v2
Hopper-v2
Walker2d.v2
14330
SCC p-ia 20t4
pell a.oni
6000
2-1A C.
SIc p1-11.1222 2.01
SBC 21-30, 2.000
7- 04tl
0251
20mll
1003
Li-iit 201h0
1739
4230
1003
3030
4300
2000
8.00
325 232
0/2
100
332
173
830
323
DIE LO0
325
LTD
4.00
023 638
3.0
132
25
100
050
375
182
123
(a) SAC batch 50K results
13500
HelfCheetsh-v2
70:00
Ant-v2
EMUUl (im Offrr p-1.
Hopper-v2
2003
Walker2d.v2
P-1.
12500
5030
3003
3000
1500
DA
1A, 04br. 18,
5000
5007
5500
SM10 101.0 10
2500
12:01
1E02
4:50
335
HalfCheetah-v2
636 100 155 175
200
830
135
2.5
672 120 335
Ant-v2
LTt. 200
6.0 035 65E
Hopper-v2
13t
300
022 050 335
Walker2d-v2
13200
6030
Jon 5-01, T-1)
2.6 $-01. (i))
[N60 (1-1. p-o..
Dlul (i-16
F-011 r-b
EMud 10- pro
p-o
12000
43:11
Had jeet 1.0 9V Twitt
Plog (ed 1.8 2-0. 1-lf
EN60 (l. Dats 6-0 1-12
1464 (IC Pant twitt
Haar tler tc pwrt twit
EMUO 10-3 5. tm pwo 1011
108.
7000
2006
2400
0-1.0
100t..002. (l..0-02..00 c=23)
1.0 p-82. exCB)
2030
8.00 32n
1/0
132 173 200
8:0
325 535
D/1
100 15 133 Li 200
.81 12t 150 2/b 2.00
025 000
Walker2div2
12500
1720)
11:0
5890
4800
Re6 0 twll)
Hma 10 Aw
PMot agme twil)
EN60 11-333 3 p-10 yel
HANT sgmms twe
DMat C0 1-20)
DMai (or C 1-1.A
516. UP273 00002221000mm.. 2-1.0 c-1l
wMa arpte pullt hank
5300
Sha0 1- (-15, mi
00000-0.75 10005-01..1 19 p=1 (x))
3030
2000
2000
2500
90009.07 k0 (-16 m-20
1500 2e1 (ag))
1330
1083
8.00
HalfCheetah-v22
Ant-v2
Hopper-v2
Walker2d-v2
15500
7530
(ee 8Ctms 2-01.
5000
1960 (i2.73 80m.
2603
1460 19:5:1
12500
5030
5603
3000
1500
9500 101o 1-3)
5000
5000
550
1600 10tn (w))
1281
800 335
235
078
100
LB
332 133
830
125 DIT
180 335
153
L/2
800
825
658
230 125
500
033
030
375
182
125
130
L8 200
(b) EMaQ batch 50K results
Figure 5: All results for batch size 50K
20

---

Under review as a conference paper at ICLR 2021
Shared Hyperparameters
1.0
Batch Size
256
Num Updates
le6
Num Q Functions
8
Q Architecture
MLP. 3 layers, 750 hid dim, relu
f Ir
5e-4
0.995
EMaQ Hyperparameters
Qr BEAR Hyperparameters
le-4
Architecture
MLP. 3 layers, 750 hid dim, relu
Q Ir
le-3
n Ir
3e-5
BCQ Hyperparameters
т Architecture
MLP, 3 layers, 750 hid dim, relu
Qh lr π lr
le-4
5c-4
Table Hyperparameters for Mujoco Experiments
size of Lin,, number of bins for action discretization). Increasing the number of discretization bins from 40 (value for standard Mujoco experiments) 80 was the most important change. Output dimension of state-embedding MLP is the same as the hidden size.
Hyperparameters Table shows the hyperparameters used for the experiments in Table ??.
Shared Hyperparameters
1.0
Batch Size Num Updates
128
le6
Num Q Functions Q Architecture
16
MLP, 4 layers, 256 hid dim, relu
0.995
1 Ir
5e-4
Kitchen Arch Params
(256, 4, 128, 1, 128, 80) (256, 4, 128, 1, 128, 80)
Antmaze μ Arch Params
Adroit Arch Params
(256, 4, 128, 1, 128, 80)
EMaQ Hyperparameters
Q
le-4
Kitchen N's Searched
[4, 8, 16, 32, 64) (50, 100, 150, 200} {16, 32, 64, 128)
Antmaze N's Searched
Adroit N's Searched
BEAR Hyperparameters
и Architecture
MI., 4 layers, 256 hid dim, relu
Q lr π lr
1e44
5e-4
BCQ Hyperparameters
т Architecture
MLP, 4 layerss 256 hid dim, relu
Ql lr n Ir
le-4
5e-4
Table 3: Hyperparameters for Table
Experiments
21

---

Under review as a conference paper at ICLR 2021
Random
Medium
Mixed
Medium-Expert
HalfCheetah
12000
I
1
2000
4400
1000
4300
1000
01050
75
50
150
760
900
25
50
150
700
10
05
100
750
450
10
75
53
100
760
450
300
1200
Walker
250
000
1000
200
750
350
X00
500
25
50 EMGQ
150
P00
A2D
2:0
150
750
800
10
75
55
160
700
420
EN3O
204
I
Hopper
202
1400
700
3200
1200
000
1000
500
BM30
EN60
BN2O
B420
benchmark domains when using the described VAE implementation, with N E (5, 10, 25, 50, 100, 200, 400). Values above u(als) represent the result of evaluating the base behavior policies. Horizontal green lines represent the reported performance of BEAR in the D4RL benchmark (apples to apples comparisons in Figure
Figure 6: Results for evaluating EMaQ on D4RL (Fu ct al. 2020b
H
VAE RESULTS
H.1 IMPLEMENTATION
We also ran experiments with VAE parameterizations for p(a[s). To be approximately matched in parameter count with our autoregressive models, the encoder and decoder both have 3 hidden layers of size 1024 with relu activations. The dimension of the latent space was twice the number action dimensions. The decoder outputs vector which, and the decoder action distribution is defined to be (Tanh(u)) I). When sampling from the VAE, following prior work, samples from the VAE prior (spherical normal distribution) were clipped the range [-0.5, 0.5] and mean of the decoder distibution was used (i.e. the decoder distribution was not sampled from). The KL divergence loss term was weighted by 0.5. This VAE implementation codebase of (Wu et al. 2019). so we did not modify it.
the one used in the benchmarking
H.2 RESULTS
As can be seen in Figure EMaQ has a harder time improving upon u(a)s) when using the VAE architecture deseribed above. However, can be seen in Figure 7 BCQ and BEAR do show some variability as well when switching to the VAEs. Since as an algorithm EMaQ is much more reliant on p(als), hypothesis is that if it is true that the autoregressive models better captured the action distribution, letting EMaQ not make poor generalizations to out-of-distribution actions. Figures and 9 show autoregressive and VAE results side-by-side for casier comparison.
EMAQ MEDIUM- SETTING RESULTS
In HalfCheetah, increasing N significantly slows down the convergence rate of the training curves; while large Ns continue to improve, we were unable to train them long enough for convergence. In Walker, for EMaQ, BCQ, and most hyperparameter settings of BEAR, training curves have prototypical shape of a hump, where performance improves up certain high value, and then continues to fall very low. Hopper, for higher values of in EMaQ we observed that increasing batch size from 100 to 256 largely resolved the poor performance, but for consistency did not alter Figure with these values.
J COMPARISON WITH SOFTMAX BACKUP OPERATORS
22

---

Under review as a conference paper at ICLR 2021
Random
Medium
Mixed
Medium-Expert
HalfCheetah
111
1000
800
Walker
Hopper
I
Figure 7:
Comparison of EMaQ. BCQ, and BEAR D4RL (Fu al. 2020b) benchmark domains when using when using the described VAE implementation for u(als). For both BCQ and BEAR, from left to right the allowed deviation from μ(((s) increases. Horizontal green lines represent the reported performance of BEAR in the D4RL benchmark.
We thank one of our ICLR 2021 reviewers for the motivation for this section. For clarity of writing, will write the forms for deterministic dynamics and remove the expectations over the next state.
An interesting connection to our proposed backup operators would be the following Softmax backup operator with similarities to EMaQ.
Q(, = r(8, (Q0 a')]
(67)
soft(als) p(als) exp(a Q(s,a))
(68)
As suggested by our reviewer, the policy corresponding to soft(als) is a policy that aims max- imize Q-values, subject to a KL-ccostrriitt between itself and the policy μ(a[s). The looser the constraint, the larger the effective and the farther the policy will be from μ.. One approach to Monte Carlo estimation of the expectation on the right hand side could be to take samples using methods from the energy-based generative modelling literature.
An alternative approach which will more closely resembles EMaQ is to use self-normalized impor- tance sampling.
@HQ(s,a) r(s,a)) + Feottaa an
(0((s
(69)
=r(s,a)+ + Σ
w;
Q(s .a)
(70)
(a:)~~((a'(s))
0 m(afls')
expla Q(s',
(71)
m(a((ss)
w, = Σ wu
(72)
softmar(a- Q(s', [())
(73)
In this form, the soft backup is similar to EMaQ, where instead of taking ths max Q-value over the N samples, take average over the N Q-values, weighted by the softmax probabilities in equation
73
For a given N, the a = would be equivalent to Q-evaluation of the policy p(als), and as oc, the soft backups approach EMaQ backups.
In Figure 10 we present empirical results with the soft backup operators, under a large range a E 4,,4,8, 16, 32, 64, 128, 256, 512, 1024]. in the Halfcheetah settings. The EMaQ and EMat were run with the same architectures, but were smaller than the ones used for the results in the main text. We used the same checkpoints of the generative models for the results in the main
23

---

Under review as a conference paper at ICLR 2021
text. The test-time policy for both approaches is the same, sampling N actions and taking the argmax action under the ensemble Q-value. The only difference between the EMaQ and soft-EMaQ one-line change to replace max with softmax average of the Q-values.
implementations
Some interesting observations are the following: As anticipated, the soft EMaQ backups approach EMaQ as the value of is increased. However, the necessary value of match the performance of EMaQ can be quite large. In the medium-expen setting, where figure suggests challenges arising from the combination of large N' and function-approxmmatoss, soft backups, and only a E {8, 16, 32) seem to have provided some mitigation of the problem for N 25. Since the soft backup introduces an additional hyperparameter that cannot determined ahead of time, and does not seem to provide an advantage (at least in the limited Halfcheetah settings considered), from a practical perspective, we would prefer use the regular EMaQ backup.
did not gain much advantage from
K QUALITATIVE DIFFERENCES IN TRAINING CURVES
We have sometimes observed that the curves representing agent performance throughout training can be significantly more stable under EMaQ in comparison to BEAR and BCQ. A domain where the differences are particularly striking are the antmaze-uman ze and entmmazeuune ze-di verse domains. In figure 4 we have included plots of agent performance during training under the variety of considered hyperparameters and random seeds. can be seen that in these two domains, initially the BCQ agents improves in performance close the performance of EMaQ, and the drastically degrades with more training. In constrast, EMaQ agents remain stable even after twice as many training iterations BCQ, which may indicate the downside of the heuristic perturbation model for constraining actions.
EMaQ
BCQ
0.6
0.8
0.4
0.2
0-
antmazeeumazz
800%
1.6M
0.4
0.4
0.2
0.2
antmaze-umaze-diieee
Table 4: Comparison of agent returns throughout training, under the variety of hyperparameters and and random seeds, in the small ant domains. We observe that EMaQ is significantly more stable than BCQ these domains, though the values of N in EMaQ were fairly large for these plots N E (50, 100, 150, 200).
L LARGER PLOTS FOR VISIBILITY
Due to larger size of plots, each plot is shown separate page below, For ablation results, For MuloCo results, see Figure
Figure
24

---

Under teview as a confere
Medium-EEpp Expert
I
5000
0001
440
2000
200
Figure 8: Results with both autoregressive and VAE models in one plot for easier comparison.
I.A.E........111
I 1
Mixed
139
1100
19
Medium
U1
I
500
3030
P3
PRO
Random
2
W
Hopg
2

---

Under feview as a confere
1. ml A4
Medium- Expert
I
1
Figure 9: Results with both autoregressive and VAE models in one plot for easier comparison.
Likke Sille
17 Sille
Mixed
1
Ville Life
LR
Medium
1111
Aehe N.l J
1
Random
1I
|1111
11

---

Under Seview as a conference paper at ICLR 2021
--
100
medium- export
25
Figure 10: Comparison of Moft-EMaQ with EMaQ under large range of hyperparameters in the Halfcheetah domain.
8000
4000
2000
100
mixed
25
5000
4000
3000
2000
1000
4-41
100
medium
25
4000
3500
1-26
+-1
6-100
100
random
25
5
2500
2000
1500
1000
530
27

---

Under review as a conference paper at ICLR 2021
benchmark domains, with N E (5, 10. 25. 50, 100, 200, 400). Values above p s) represent
the result of evaluating the base behavior policies. Horizontal green lines represent the reported performance of BEAR in the D4RL benchmark (apples to apples comparisons in Figure 2 Refer main text (Section 5.1] for description color-coding.
400
400
200
200
Medium-Expert
100
100
BlaQ
LMaQ
30
50
25
75
25
10
10
5
5
MAbiSI 5
8000
6000
4000
4000
3000
2000
1000
3000
2000
1000
400
400
200
200
100
100
Mixed
50
BMSQ
50
25
25
10
10
5
5
5000
4000
3000
2000
1300
1000
800
700
600
1
400
1
400
200
200
200
150
100
Medium
30
ERPQ
50 LMPOQ)
Figure 11: Results for evaluating EMaQ on D4RL Fu et al. 2020b
25
23
10
10
10
5
5
Mells
x
5000
4000
3000
2000
1500
1000
500
400
400
400
200
700
700
100
100
Random
50 EMSQ
EMaQ
50
EMBQ
25
25
10
10
10
5
Allp)
3300
HaifCheekaa
2000
1000
300
Palke
10n
Hopper
375
H
325
300
28

---

Under review as a conference paper at ICLR 2021
benchmark domains when using our proposed autoregressive ((as (assss).s. For both BCQ and BEAR, from left to right the allowed deviation from ((as increases. Horizontal green lines represent the reported performance BEAR in the D4RL benchmark, Color-coding follows Figure T
Medium-Expper
15
sius 03
EUN 05
800
200
36
Mixed
HAN
300
203
2008
325
200
Figure 12: Comparison of EMaQ. BCQ. and BEAR on D4RL Fu et al. 2020b
CH6 1000
200
Medium
B2003 FIOTE 0% 11
05
TOUUS 012 05
500
600
600
2000
200
1300
7X6
500
0100 300g
.40
Random
15
16
BOO
II
50L
Salket
30
HairCheetal


Reviews:
[{"review_id": "yisTKoGdVXS", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes off-policy algorithms using a sampling-based maximization of the Q function over a behavior policy for both Bellman targets and for policy execution, introducing the “Expected Max Q-learning” operator EMaQ for analysis. The paper then proposes to use more expressive autoregressive models (MADE) for learning the behavior policy from replay buffer data (either online or offline), which turns out to be very important, especially on harder tasks in the D4RL benchmark. The method is relatively novel - it is close to other methods in the literature, but they make and evaluate important design decisions that are valuable for the community. The results are quite strong, matching or exceeding BEAR on D4RL while at the same time matching SAC for online learning.\n\nThe proposed method is simple yet effective: they learn a behavior policy on offline data. Then they learn a Q-function by Bellman bootstrapping, using max of N samples from the behavior policy for the target step. Then for executing the policy, the method again uses the argmax of N samples from the behavior policy. As mentioned in the related work, prior work such as BCQ and QT-Opt has studied sample-based policies, and it has also been common to mix the two decisions: eg. BEAR uses a parametric policy for bootstrapping but then reports a boost from sampling for policy execution. But the proposed method is perhaps the simplest of these from an RL point of view, which is a good thing - and the juice really comes from the proposal to use MADE for modeling the behavior policy. This also suggests clear future directions for research - to explore other, better generative models (AR models in particular are probably a poor long-term solution because of slow sampling).\n\nThe analysis centers around the EMaQ operator, which is a nice representation for thinking about the maximization problem in Bellman bootstrapping. The paper proves the convergence of the operator in the tabular setting, and some intuitive theorems that larger values of N result in policies with better Q values (for policy evaluation), and thus better policy improvement. One issue though with N -> inf, is that it would tend to exploit function approximation errors of the Q function, and this is borne out in some of the results. Theoretical results along these lines would significantly strengthen the paper.\n\nThe highlight of the paper is results on both offline and online RL. In offline RL, EMaQ roughly matches the performance of BCQ and BEAR while being significantly simpler to implement (except perhaps the MADE model) and exceeds BCQ and BEAR in some environments and depending on the underlying implementation. In online RL, EMaQ roughly matches SAC, being slightly worse when updating the policy frequently and slightly better when updating the policy less frequently. As far as I know, no prior method has been able to show good performance on both: SAC is poor on offline training and BCQ/BEAR is poor on online training. This is the strongest positive for the paper.\n\nMinor comments:\n\nThere are a couple of references to “number of samples” in the intro that do not make sense until reading the method. Perhaps you need to outline the method in the intro, instead of just hinting at it, if you want to discuss these details. “As an example, we observe that while a HalfCheetah random policy obtains a return of 0, a policy that at each state uniformly samples only 5 actions and chooses the one with the best value obtains a return of 2000.” - I’m not sure if I understood the setup here, or the significance. Is the value estimated with samples from the random behavior policy? Is the second policy you refer to your method (so fit a behavior policy on the random behavior data, then do Q learning + sample 5 actions for maximizing it), or something else? Moreover, I did not really understand why this is too surprising, since the bulk of the work is really being done by learning a good Q function and even on random-action data, learning a behavior policy would help you stay constrained to the data.\n\nDeferring the full related work to the appendix skirts the page limit rules and is somewhat unfair to other submitters, and also made it hard to read since the links do not cross-reference between PDFs.\n\n“Importantly, our theoretical analysis on the family of TD operators described by EMaQ apply beyond BCQ and can also provide new perspectives on some of the highly successful sample-max Q-learning algorithms (Kalashnikov et al., 2018a; Van de Wiele et al., 2020) – particularly on how the proposal distribution affects convergence.” Not sure if I missed this, but I didn’t exactly see such a result or know what this is referring to, which I would expect to be something like lower D(pi* || mu) implies faster convergence.", "extra_scores": {}, "extra_text": {}}, {"review_id": "pDfhUCJhXNp", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper proposes the expected-max operator to address the problem of distribution shift in offline RL (which could also be applied in online RL). The paper establishes theoretical analysis of the proposed operator in convergence, sub-optimality, etc. A practical algorithm is proposed based on previous techniques (an ensemble of Q-functions) and a different generative model using an autoregressive architecture. Experiments demonstrate the effectiveness of EMaQ. \n\nStrong points: The paper studies the important problem of how to mitigate distribution shift in offline RL, and proposes a simple but effective algorithm. The paper conducts extensive experiments comparing with state-of-the-art algorithms, with in-depth ablative studies of the effect of each component.\n\nConcerns:\n- I am surprised by the result in Figures 1 and 2 that EMaQ performs very well with a small value of N=5 (as the upper bound in Theorem 3.5 would be not very meaningful given a small N and gamma close 1). Could authors investigate the sampled 5 actions? Are they diverse enough to represent the entire action space well, considering the action space is continuous?\n\n- The performance of EMaQ strongly relates to how good \\mu is learned. What if \\mu is close to a deterministic policy (e.g., \\mu is not learned well and is close to a deterministic policy)? How to guarantee this diversity?\n\n- Could authors compare the performance of EMaQ when N is 1 and an extremely large value, which could better justifies the performance in extreme cases. \n\n- How are the computation time and learning curve (besides the final performance shown in the paper) of EMaQ compared with other methods? \n\n- In Section 3.5, it is not clear how a small value of N could serve as a regularizer and smoothen the incorrect values.", "extra_scores": {}, "extra_text": {}}, {"review_id": "MatXbKHtTOH", "reviewer": "AnonReviewer5", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a simple offline RL algorithm based on Q-learning that instead of computing the exact maximum over actions, takes the sample maximum when sampling from an learned estimate of the behavior policy. Experimental results are quite promising (competitive with previous algorithms in both offline and online settings). The authors demonstrate that utilizing autoregressive models significantly improves over simple VAEs when used to model the behavior policy in offline learning (both for the proposed method as well as prior work), highlighting the need to place more focus on how we model the behavior policy in offline RL.\n\nThe article is clearly written, and the analysis of the proposed backup is original to the best of my knowledge.\nHowever, with how important the choice of model used to model the behavior policy appears to be, I am unsure as to how significant the new proposed backup operator is. While I feel the paper clearly highlights the importance of how we model the behavior $\\mu(a\\vert s)$, I don't see particularly strong evidence, either theoretically or empirically, why one should prefer using the EMaQ backup. \n\nRegarding the simplicity of the proposed algorithm compared to previous ones, EMaQ does use one fewer network since it does not need to explicitly model a separate policy. However, in order to achieve competitive performance, EMaQ did require a more complicated model for the behavior policy, and the increased sensitivity to that perhaps counteracts the benefits of not having an explicit policy. Additionally, EMaQ also needs to sample multiple actions for each backup and when executing the learned policy, incurring more computational costs in sampling compared to using an explicit policy network. \n\nOne thing to potentially examine more closely is how EMaQ and the regularization from choosing small $N$ relates to previously used forms of regularization. We could consider an alternate procedure where instead of sampling N samples from $\\mu(a\\vert s)$ and taking the max, we instead sample from the distribution $\\mu(a\\vert s) \\exp(\\alpha Q(s,a))$ (using something like self-normalized importance sampling for example) for some temperature $\\alpha$. This corresponds to the policy that simultaneously maximizes the expected Q-value as well as  a KL divergence penalty against the original policy $\\mu(a\\vert s)$, and would resemble the sample maximum as the temperature increases. The key difference from other methods using KL-regularization against the behavior policy would be that it relies on samples solely from the behavior model, similarly to EMaQ. Comparing these two procedures with different parameters could perhaps give us a better understanding of how implicit regularization by choosing small $N$ in EMaQ relates to explicit regularization via KL.\n\n**Complexity Measure**: I strongly disagree that $\\Delta(s, N)$ is a useful notion of complexity for offline RL. While it captures a notion of how well the behavior policy covers good behaviors, it uses the exact $Q*$ or $Q_{\\mu}^N$ values. However, the difficult part in offline RL is to accurately estimate those Q values, and the proposed complexity term has no way to account for sources of complexity such as stochasticity or the horizon of the MDP. For example, an MDP with only 2 actions per state can be potentially very complex, but all 2-action MDPs would presumably look trivial just judging by how fast $\\Delta(s, N)$ decreases with N.\n\n**Misc. Comments:**\nWith regards to the inductive and the choice of model class for the behavior policy, what if we did actually have access to the behavior policy that generated the data? Would EMaQ perform better with oracle access to the behavior policy, or is there something about behavior model learned from the actual transitions in the dataset that would allow for better learning? Perhaps such a question would be useful for examining what sorts of inductive biases should go into the behavior model.\n\n**Updates after Author Response:**\n\n*Complexity Measure*: My concern with the complexity measure is that it seems to me that the biggest difficulty in reinforcement learning is in actually being able to estimate accurate value functions, while proposed complexity measure really only vaguely captures how far optimal policies are from the behavior distribution. \nIn particular, at each state, it only depends on the true values of Q for each action, and can't capture how hard it is to estimate them.\nEven among similarly structured MDPs, we can consider a 2-action MDP with a behavior policy that was simply uniform. \nWe could have one extremely simple MDP that was simply composed of independent deterministic bandit problems at each state with no transitions (always remain in your starting state), which would be trivial to solve even from offline data with full support.\nOn the other hand, we could have a much more complex MDP with meaningful stochastic transitions, random rewards and so on. \nIf we simply match the Q values in the two MDPs, they appear to be equally complex from this measure, despite the fact that the bandit MDP is far simpler to solve.\nAs such, I think the proposed complexity measure doesn't really reflect the real challenges of an offline RL problem, and am not sure how one would extend it to be useful.\n\n*Re misc comments and access to true behavior policies:* My thinking here was that if we had a very stochastic behavior and finite samples, there would be actions that have reasonably high probability under the true behavior policy, but we never get to see in the data and wont' be able to evaluate well. One benefit of fitting the behavior model the the empirical data is that it would focus on those actions that do appear in the dataset (in an extreme case, we could simply have Dirac deltas on the observed data points), and so could benefit by restricting the actions to those that can be evaluated better.\n\n*Overall Opinion:* In light of the empirical results mentioned in the author's response as well as the comparisons to KL regularization, I have raised my rating. I still do believe it is a very borderline paper, and would perhaps benefit from more careful analysis and focus on how the different behavior modelling choices influences offline. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "8j_Q6QVUyt", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed EMaQ, an approximation of Bellman operator, and thus yields a variant of deep Q learning algorithms in both online and offline settings. In tabular settings, several properties of the EMaQ operator such as the convergent guarantee, fixed point, and finite-sample error bounds were studied. Then the author shows the empirical performance of a deep learning approximation of the proposed algorithm on a standard batch RL benchmark. The authors also provide some analysis of the effect of different implementation choices on empirical performance, by ablation study.\n\n\nA key fact is that the proposed method can be directly got from BCQ by settings the perturbation parameter to zero. Thus, the originality here is quite little. The proposed algorithm is a simplification compared with BCQ. However, in terms of both theoretical and empirical contributions, this paper does not show a significant improvement compared with BCQ. In general, the findings of this paper seem not surprising at all given BCQ and BEAR paper.\n\nPros:\n1. Compared with BCQ, the proposed EMaQ operator has a simpler form with similar performance. In some sense, it is a Q learning analog of BCQ (which is actually an actor-critic algorithm).\n2. There is some ablation study on the choice of generative model for $\\mu(a|s)$, the number of action to sample, etc. which are missed in the original BCQ paper.\n\nCons:\n1. As I mentioned in the summary, the biggest issue is that as a very simple and incremental algorithmic change, this paper also failed to provide additional discussion in either theory or experimental that can provide significantly more insight and inspiration to people. There are many potential directions where the discussion can go: \n(1) In some sense it is a Q learning analog of BCQ (which is actually an actor-critic algorithm). It will be very interesting to discuss the effect of the difference between Q learning and actor-critic on BCQ v.s. EMaQ comparison. Unfortunately, I did not see enough in-depth discussion on that.\n(2) The new algorithm is more closed the tabular settings. So does that yield stronger theoretical guarantees in function approximation settings? Or is there a conceptual experiment to demonstrate where the perturbation model is a bad idea/approximation and cause the failure of the algorithm?\n(3) Does this very simple algorithmic choice lead to very different behavior of the algorithm (e.g. optimization path of the parameters, behavior of the resulting models other than just reward)? Why there is or is not a very different behavior of the algorithm?\n\n2. According to the paper a key contribution of the empirical part is the importance of careful generative model design for\nestimating behavior policies. This seems very straightforward as the BCQ/BEAR algorithm is using $\\mu(a|s)$. Given that $\\mu(a|s)$ is a plug-in module in those algorithms, new advances in the generative model can be immediately applied there so the significance and novelty of this finding are very limited.\n\n3. A general problem of this paper is over-claiming. For example: \n(1) \"EMaQ matches and outperforms the prior state-of-the-art in the D4RL benchmarks\" -- It matches (and did not outperform by any statistically significant margin) BCQ and BEAR. There are other baselines in D4RL that are better than BCQ/BEAR: BRAC, CQL, MOPO, MoRel. The former two are also model-free, and those numbers are all reported in the D4RL whitepaper.\n(2) \"EMaQ provides a quite intuitive and surprising measure of the complexity for offline RL problems.\" To claim that, I think it needs to show that  $\\Delta$ is related to some general structure of the problem (theoretically) or some general phenomenon for a large group of algorithms (empirically).\nThese two claims can also be a potential improvement of this paper if they are really achieved.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: **Overview** The paper provides a simplified offline RL algorithm based on BCQ. It analyzes the algorithms using a sampling-based maximization of the Q function over a behavior policy for both Bellman targets and for policy execution -- the EMaQ. Based on this, the paper then proposes to use more expressive autoregressive models (MADE) for learning the behavior policy from replay buffer data. The methods work well for harder tasks in the D4RL benchmark. 

**Pro** 
- The method is relatively novel 
- Algorithms are simple modifications of existing ones
- Empirical results are strong, matching or exceeding BEAR on D4RL while at the same time matching SAC for online learning
- Work for both and offline
- ablation study on the choice of generative model for μ(a|s)

**Con**
- The current form of the complexity measure is somewhat not practical.
- Theoretical results are not strong enough
- Algorithmic contributions appear incremental

**Recommendation** The paper is on the borderline. It contributes simple and nice algorithmic ideas and these ideas work well empirically. These results demonstrate that a good choice of the behavior policy generative model is important for some tasks. At the same time, the reviewers are concerned about the theoretical parts, e.g., issues relates new complexity measure. Overall, the meta-reviewer believes that the paper might not be in a status ready for publication.
Decision: Reject