CAQL: Continuous Action Q-Learning
Authors: Moonkyung Ryu
Yinlam Chow
Ross Anderson
Christian Tjandraatmadja
Craig Boutilier
Venue:  (2020)
Keywords: Reinforcement learning (RL)
DQN
Continuous control
Mixed-Integer Programming (MIP)

Abstract: Reinforcement learning (RL) with value-based methods (e.g., Q-learning) has shown success in a variety of domains such as
games and recommender systems (RSs). When the action space is finite, these algorithms implicitly finds a policy by learning the optimal value function, which are often very efficient. 
However, one major challenge of extending Q-learning to tackle continuous-action RL problems is that obtaining optimal Bellman backup requires solving a continuous action-maximization (max-Q) problem. While it is common to restrict the parameterization of the Q-function to be concave in actions to simplify the max-Q problem, such a restriction might lead to performance degradation. Alternatively, when the Q-function is parameterized with a generic feed-forward neural network (NN), the max-Q problem can be NP-hard. In this work, we propose the CAQL method which minimizes the Bellman residual using Q-learning with one of several plug-and-play action optimizers. In particular, leveraging the strides of optimization theories in deep NN, we show that max-Q problem can be solved optimally with mixed-integer programming (MIP)---when the Q-function has sufficient representation power, this MIP-based optimization induces better policies and is more robust than counterparts, e.g., CEM or GA, that approximate the max-Q solution. To speed up training of CAQL, we develop three techniques, namely (i) dynamic tolerance, (ii) dual filtering, and (iii) clustering.
To speed up inference of CAQL, we introduce the action function that concurrently learns the optimal policy.
To demonstrate the efficiency of CAQL we compare it with state-of-the-art RL algorithms on benchmark continuous control problems that have different degrees of action constraints and show that CAQL significantly outperforms policy-based methods in heavily constrained environments.

CAQL: CONTINUOUS ACTION Q-LEARNING
Moonkyung Ryu*, Yinlam Chow*, Ross Anderson, Christian Tjandraatmadja, Craig Boutilier Google Research fmkryu, yinlamchow, rander, ct cboaat/t..coriiilee/ggoo........
ABSTRACT
Value-based reinforcement learning (RL. methods like Q-learning have shown success in a variety of domains. One challenge in applying Q-laaring to continuous-acteo RL problems, however, is the continuous action maximization (max-Q) required for optimal Bellman backup. In this work, we develop CAQI., a (class of) algorithm(s) for citinuous-acttionn Q-lcarning that can use several plug- and-play optimizers for the max-Q problem. Leveraging recent optimization re- sults for deep neural networks, we show that max-Q can be solved optimally us- ing mixed- mixed-integer programming (MIP). When the Q-function representation has sufficient power, MIP-based optimization gives rise to better policies and is more robust than approximate methods (e.g.. gradient ascent, cross-entropy search). We further develop several techniques to accelerate inference in CAQL, which despite their approximate nature, perform well. We compare CAQL with state-of-the -hrt RL algorithms on benchmark continuous-control problems that have different de- grees of action constraints and show that CAQL outperforms policy-based meth- ods in heavily constrained environments, often dramatically.
INTRODUCTION
Reinforcement learning (RL) has shown success in variety of domains such games (Mnih al. 2013) and recommender systems (RSs) (Gauci et al. (2018) When the action space is finite, value- based algorithms such as Q-learning (Watkins & Dayan 1992), which implicitly finds policy by learning the optimal value function, are often very efficient because action optimization can be done by exhaustive enumeration. By contrast, in problems with a continuous action spaces (e.g.. robotics (Peters& & Schaal 20066), policy-based algorithms, such as policy gradient (PG) (Sutton et al. 2000 Siiver et al. 2014) cross-entropy policy search (CEPS) (Mannor al., 2003 Kalashnikov al., 2018). which directly learn a return- moximmmmxiiiziing policy, have proven more practical. Recently, meth- ods such as ensemble critic (Fujimoto al. 2018) and entropy regularization (Haarnoja et al. 2018)
have been developed improve the performance of policy-based RL algorithms.
Policy-based approaches require a reasonable choice of policy paramcterization. In some continu- ous control problems, Gaussian distributions over actions conditioned on some state representation is used. However, in applications such as RSs, where actions often take the form of high-dimensional item-feature vectors, policies cannot typically be modeled by common action distributions. Further- more, the admissible action set in RL is constrained in practice. for example, when actions must lie within specific range for safety (Chow al. 2018). In RSs, the admissible actions are often random functions of the state (Boutilier et al. 2018). In such cases, it is non-trivial to define policy parameterizations that handle such factors. On the other hand, value-based algorithms are well- suited to these settings, providing potential advantage over policy methods. Moreover, at least with linear function approximation (Melo & Ribeiro, 2007), under reasonable assumptions, Q-learning converges to optimality, while such optimality guarantees for non-convex policy-based methods are generally limited (Fazel al.) 2018). Empirical results also suggest that basee methods more data-efficient and less sensitive to hyper-parameters (Quillen et al. 2018). Of course, with large action spaces, exhaustive action enumeration in value-based algorithms can be expensive- one solution is represent actions with continuous features (Dulac-Arnold et al., 2015).
The main challenge in applying value-based algorithms to continuous-action domains is selecting optimal actions (both at training and inference time). Previous work in this direction falls into three broad categories. The first solves the inner maximization of the (optimal) Bellman residual loss using global nonlinear optimizers, such as the cross-entropy method (CEM) for QT-Opt (Kalash- nikov et al. 2018)), gradient ascent (GA) for actor-expert (Lim et al. 2018), and action discretization (Uther & Veloso 1998, Smart& & Kaelbling 2000 Lazaric al. 2008). However, these approaches do not guarantec optimality. The second approach restricts the Oufunctoon parametcrization so that the optimization problem is tractable. For instance, one can discretize the state and action spaces and tabular Q-function representation. However, due to the curse of dimensionality, discretizations

---

must generally be coarse, often resulting in unstable control. Millán al. (2002) cireumvents this issue by averaging discrete actions weighted by their Q-values. Wire-fiting (Gaskett et al. [999]
III Klopf 1993) approximates Q-values piecewise-linearty over a discrete set of points, chosen to
ensure the maximum action is one of the extreme points. The normalized advantage function (NAF)
(Gu et al. 2016) constructs the state- aattencctoon advantage function to be quadratic, hence analytically solvable. Parameterizing the Q-function with an input-convex neural network (Amos et al.) 2017) ensures it is concave. These restricted functional forms, however, may degrade pertormance if the domain does not conform to the imposed structure. The third category replaces optimal Q-values with a "soft" counterpart (Haarnoja et al. 2018): an entropy regularizer ensures that both the opti- mal Q-function and policy have closed- form solutions. However, the sub-optimality gap of this soft policy scales with the interval and dimensionality of the action space (Neu et al.) 2017).
Motivated by the shortcomings of prior approaches, we propose Continuous Action Q-learning (CAQL), Q-learning framework for continuous actions in which the Q-function is modeled by a generic feed-forward neural network [ Our contribution is three-fold. First, we develop the CAQL. framework, which minimizes the Bellman residual in Q-learning using one of several "plug-and- play" action optimizers. We show that "max-Q" optimization, when the Q-function is approximated by a deep ReI.U network, can be formulated as a mixed-integer program (MIP) that solves max-Q optimally. When the Q-function has sufficient representation power, MIP-based optimization in- duces better policies and is more robust than methods (e.g., CEM, GA) that approximate the max-Q solution. Second, to improve CAQL's practicality for larger-scale applications, we develop three speed-up techniques for computing max-Q values: (i) dynamic tolerance; (ii) dual filtering; and (iii) clustering. Third, we compare CAQL with several state-of-the-art RI. algorithms on several benchmark problems with varying degrees of action constraints. Value-based CAQL is generally competitive, and outperforms policy-based methods in heavily constrained environments, some- times significantly. We also study the effects of our speed-ups through ablation analysis.
PRELIMINARIES
We consider an infinite-horizon, discounted Markov decision process (Puterman 2014) with states X, (continuous) action space A, reward function R, transition kernel P. initial state distribu- tion 3 and discount factor ry E [0, 1). all having the usual meaning. A (stationary, Marko- vian) policy specifies a distribution T (-122)) over actions to be taken at state x. Let A be the set of such policies. The expected cumulative return of E A is J(r) == E 7 I P, R. To ~ T. An optimal policy x* satisfies x² E arg max EAA J(T). The Bellman op- erator F[Q](xr, a) R(z,0) a) + 7 Exexx P(x' [r, a) max.'e Q(2', ,a)) over state-action value function Q has unique fixed point (²(2aa) a) (Puterman 2014), which is the optimal Q-function @*(I,a) = E 1Σ:= y' R(z,, a.) Ho = ag = a, π.' T... An optimal (deterministic) policy x can be extracted from Q": xt' (alz) = laa = a (x)), where (x) E arg max, ("
For large or continuous state/action spaces, the optimal f-uuccio can be approximated, e.g., using deep neural network (DNN) as in DQN (Mnih et al., (013). In DQN, the value function Qo is updated using the value label r + 7 max.'' Quuase (x' ,, a'). where Qaaeer is a target Q-function. Instead of training these weights jointly, gharget is updated in a separate iterative fashion using the previous f for fixed number of training steps. by averaging gtarget < 78 + (1 7)6 for some small momentum weight T E [0, 1] (Mnih et al. 2016). DQN is off-policy-the target is valid no matter how the experience was generated (as long as it is sufficiently exploratory). Typically, the loss is minimized over batches B of past data (I., a, r,, x²) sampled from a large experience replay buffer R (Lin & Mitchell 1992). One common loss function for training Qg. is mean squared
Bellman error: minę E (Qe [z,, a.) - - max, Q8 (I/, a²))² Under this loss, RL can be viewed as lg fg-regression of Q+(--)) w.r.t. target labels r + max.'' Q gragen (z', a'). We augment DQN, using double Q-learning for more stable training (Hasselt et al., 2016). whose loss is:
[B]
min Σ
(r. (ri+ TQguaQuusfe (2%, arg max Qo(2),a')) - Qo(o),a)))
(I)
a'
A hinge loss can also be used in Q-learning, and has connections the linear programming (LP) formulation of the MDP (Puterman (2014). The optimal Q-network weights can be specified as:
ming 1 [
[B] E Q0(2;, az) + Arr + max.'eA Q0(2), a²) - Q0 ax)) where X > 0 is tun-
Results can be extended handle convolutional NNs, but are omitted for brevity.
2

---

able penalty w.r.t constraint: r+ r+yyaa,''s m Qo (0) - Qo(a, a), V(z, a, r,) B. To stabilize training. we replace the Q-network of the inner maximization with the target Q-network and the optimal Q-value with the double-Q label, giving (see Appendix for details):
[BI
min
Co(o,, + (r= QQ (2%, arg max Qu a')) -o)(,,))))) B
1
Σ
(2)
In this work, we assume the Q-function approximation Qo to be a feed-forward network. Specif- ically, let Qo be a K- Kllayer feed-forward NN with state-action input (x, a) (where lies in d- dimensional real vector space) and hidden layers arranged according to the equations:
21 ax, 2j 1- + bJ-1, 2j h(2z), j 2, ,.,,.,, K, Qo(x, a) == c 22 2
(3)
where (Wj.b;) are the multiplicative and bias weights, is the output weight of the Q-network, 0 = (c, [C, b,)) are the weights of the Q-network, 2 denotes pre-activation values at layer j. and h(.) is the (component-wise) activation function. For simplicity, in the following analysis, we restrict our attention to the case when the activation functions are ReLU's. We also assume that the action space A is a d-dimensional log -bll (a, A) with some radius A > 0 and center Therefore, at any arbitrary state E X the max-Q problem can be re-written as L. := max.eA Q0(2,, a) = max X (= {er {c_2x] 21 (z,a), a E (a, A), eqs. (
While the above formulation intuitive, the nonlinear equality constraints in the neural network formulation (3) makes this problem non-convex and NP-hard (Katz et al. 2017
3 CONTINUOUS ACTION Q-LEARNING ALGORITHM
Policy-based methods (Silver et al. 2014 Fujimoto et al., 2018; Haarnoja et al. 2018) have been widely-used to handle continuous actions in RI. However, they suffer from several well-known difficulties, e.g., (i) modeling high- nigh-dimensional action distributions, (ii) handling action constraints, and (iii) fata-inefficiency. Motivated by earlier work on value-based RI. methods, such as QT- Opt (Kalashnikov et al. 2018) and actor-expert (Lim et al., 2018). we propose Continuous Action Q-learning (CAQL), general framework for cuntinoous-actin value-based RL, in which the Q- function is parameterized by NN (Eq. (). One novelty of CAQL is the formulation of the "max-Q -"" problem, i.e., the inner maximization in and (2) as a mixed-integer programming (MIP).
The benefit of the MIP formulation is that it guarantees that we find the optimal action (and its true bootstrapped Q-value) when computing target labels (and at inference time). We show empirically that this can induce better performance, especially when the Q-network has sufficient representa- tion power. Moreover, since MIP can readily model linear and combinatorial constraints. it offers considerable flexibility when incorporating complex action constraints in RL. That said, finding the optimal Q-label (e.g., with MIP) is computationally intensive. To alleviate this, we develop several approximation methods to systematically reduce the computational demands of the inner maximiza- tion. In Sec. 3.2 we introduce the action function to approximate the arg max-policy at inference time, and in Sec. 4 we propose three techniques, dynamic tolerance, dual filtering, and clustering, to speed up max- computation during training.
3.1 PLUG-N-PLAY MAX-Q OPTIMIZERS
In this section, we illustrate how the max-Q problem, with the Q-function represented by a ReLU network, can be formulated (e.g.. SCIP (Gleixner et al., 2018). CPLEX (CPLEX 2019). Gurobi (Gurobi, 2019)). In addition, we detail how approximate optimizers, specifically, gradient ascent (GA) and the cross-entropy method (CEM), can trade optimality for speed in max-Q computation within CAQL. For case of exposition, we focus on Q-functions parameterized by a feedforward ReLU network. Extending our methodology (including the MIP formulation) to convolutional networks (with ReLU activation and max pooling) is straightforward (see Anderson et al. (2019)) While GA and CEM can handle generic activation functions beyond ReLU, our MIP requires additional approximations for those that are not piecewise linear.
MIP, which can be solved using off-the-shelf optimization packages
Mixed-Integee Programming (MIP) A trained feed-forward ReLU network can be modeled as a MIP by formulating the nonlinear activation function at each neuron with binary constraints. Specif- ically, for a ReLU with pre-activation function of form 2 = max w + 6). where x E [e. u] is
Without loss of generality, we simplify the NN by omitting the output bias and output activation function.
3

---

d-dimensional bounded input, w RA, b E R. and é, R are the weights, bias and lower-upper bounds respectively, consider the following set with a binary variable Ç indicating whether the ReLU is active or not:
({ (1,
2 =2 wT x ++ b, 2 =20, 2 =5 SwTT + M- () 2 = M+C. }.
R(w,b, k,2 -
(z, () E [e, w x R x {
In this formulation, both M+ max w x + b and M = min w/ x: + b can be computed in linear time in d. We assume M* 0 and M O, otherwise the function can be replaced by O or 2 = w x + b. These constraints ensure that 2 is the output of the ReLU: If <= = 0, then they are reduced to 2 = 0 2 w x+ and i = 1, then they become & = w x++bb 2 O.
This can be extended to the ReLU network in (3) by chaining copies of intermediate ReLU formu- lations. More precisely, if the ReLU Q-network has m. neurons in layer j E [2,..., K}. for any given state x E X, the max- Q problem can be reformulated as the following MIP:
L- = max cZZK ZK
(4)
S.L. 21 == E Boo (T,
23,4 Cea) 3,, by.a; 13-1, jE (2..... K), i (1.....,
a ++A A are the (action) input-bound vectors. Since the output layer of the ReLU NN is linear, the MIP objective is linear as well. Here, W,, E Rm, and 6j. RR are the weights and bias of neuron i in layer j. Furthermore, b, Uy are interval bounds for the outputs of the neurons in layer for j 2 2. and computing them can be done via interval arithmetic or other propagation methods (Weng et al., 2018) from the initial action space bounds (see Appendix for details). As detailed by Anderson et al. 2019), this can be further tightened with additional constraints, and its implementation can be found in the ffoor package described therein. As long as these bounds are redundant, having these additional box constraints will not affect optimality. We emphasize that the MIP returns provably global optima, unlike GA and CEM. Even when interrupted with stopping conditions such as time limit, MIP often produces high-quality solutions in practice.
where l = - A,
In theory, this MIP formulation
be solved in time exponential on the number of ReLUs and polynomial on the input size (e.g., by naively solving an LP for each binary variable assignment). In practice however, a modern MIP solver combines many different techniques to significantly speed up this process, such as sranch-and-bound cutting planes, preprocessing techniques, and primal heuristics (Linderoth & Savelsbergh, 1999). Versions of this MIP model have been used in neural network verilication (Cheng et al. [2017] Lomuscio & Maganti,
Bunel et al. 2018 Dutta et al. 2018 Fischetti & Jo 2018] Anderson et al. 2019 Jeng et al. (2019) and analysis (Serra al. 2018 Kumar et al.) 2019), but its application to RL is novel. While Say et al. (2017) also proposed a MIP formulation to solve the planning problem with non-linear state transition dynamics model learned with NN, it is different than ours, which solves the max-Q problem.
Gradient Ascent GA (Nocedal & Wright 2006 is simple first-order optimization method for finding the (local) optimum of a differentiable objective function, such as a neural network Q- function. At any state x E X, given a "seed" action ag, the optimal action arg max, Qo (z, a) computed iteratively by at+1 f- a₂ + VoQ,, a). where r > is a step size (either tun- able parameter or computed using back-tracking line search (Nocedal & Yuan 1998)). This process repeats until convergence, [Qo ax+1) Qo(x, ax)l < 6, a maximum iteration count is reached.
Cross-Entrope Method CEM (Rubinstein) 1999) is derivative-free optimization algorithm. At any given state x. E X, it samples a batch of N actions {a:)/r, from A using fixed distribution (e.g., a Gaussian) and ranks the corresponding Q-values {Qe(æ, a:) Using the top K < N actions, it then updates the sampling distribution, e.g., using the sample mean and covariance to update the Gaussian. This is repeated until convergence or a maximum iteration count is reached.
3.2 ACTION FUNCTION
In traditional Q-learning, the policy x²" is "implemented" by acting greedily w.r.t the learned Q- function: x- (z) = arg max, Qo (x. F However, computing the optimal action can be expensive in the continuous case, which may be especially problematic inference time (e.g., when compu- tational power is limited in, say embedded systems, or real-time response is critical). To mitigate the problem, we can use an action function Tw. X - A effectivel trainable actor network- to
Some exploration strategy may be incorporated well.
4

---

approximate the greedy-action mapping n². We train Twe using training data B ((r q }
B i= where 0f is the max-Q label at state Tz. Action function learning is then simply a supervised re-
gression problem: w- E arg min Σ.n BB (q)
(x.))) This is similar to the notion of "distilling" an optimal policy from max- Q labels, as in actor-expert (Lim al. 2018). Unlike actor- expert-a separate stochastic policy network is jointly learned with the Q-function to maximize the likelihood with the underlying optimal policy- imate arg max, Qo (I, a does not require distribution matching and is generally more stable. The use of action function in CAQL is simply optional to accelerate data collection and inference.
method learns state-action mapping to approx-
4 ACCELERATING MAX-Q COMPUTATION
In this section, we propose three methods to speed up the computationally-expeniis max- solution during training: (i) dynamic tolerance, (ii) dual filtering, and (iii) clustering.
Dynamic Tolerance Tolerance plays a critical role in the stopping condition of nonlinear optimiz- ers. Intuitively. in the early phase of CAQL, when the Q-function estimate has high Bellman error, it may be wasteful compute: a highly accurate max-Q label when a crude estimate can already guide the gradient of CAQL to minimize the Bellman residual. We can speed up the max-Q -ax-Q solver by dynamically adjusting its tolerance T > 0 based on (a) the TD-error, which measures the estimation error of the optimal Q-function, and (b) the training step 1 O, which ensures the bias of the gradient (induced by the sub-optimality of max Q solver) vanishes asymptotically so that CAQL converges to stationary point. While relating tolerance with the Bellman residual is intuitive, it is impossible to calculate that without knowing the max-Q label. To resolve this circular dependency, notice that the action function Tu approximates the optimal policy, i.e., (-2x) = arg max, (z. We therefore replace the optimal policy with the action function in Bellman residual and propose the dynamic tolerance: T; := [
J Σ! [ 7 (I';, Tw. (z²)) - Qo, (zi, a:)l k1 kg. where 1
and 2 E [0, 1) are tunable parameters. Under standard assumptions, CAQL with dynamic tolerance } converges a.s. to stationary point (Thm. 1, (Carden )014
Dual Filtering The main motivation of dual filtering is to reduce the number of max-Q problems at each CAQL training step. For illustration, consider the formulation of hinge Q-learning in ( Denote by Le guna the max-Q label w.r.t. the target Q-network and next state x'. The structure of the hinge penalty means the TD-error corresponding to sample (I,, a, x', r) is inactive whenever th gung I (Qu(1, a) -rrr//thiis data can be discarded. In dual filtering, we efficiently estimate an upper bound on q. gurn before max-Q optimization. Specifically, recall that the main source of non-convexity in (3) comes from the equality constraint of the ReL.U activation function at each NN layer. Similar to MIP for- mulation, assume we have component-wise bounds (lj, ug). = 2, ... K
,urn using some convex relaxation to determine which data can be discarded
the neurons, such
that 1j S 2 S Uj. The ReLU equality constraint H(l, := k) E R h E [4, u], k = [ can be relaxed using a convex outer-approximaation
(Wong & Kolter 2017): Hl(1, u) := {(h, k) e IR, A 2/2 h, k 0, -wh + (u - 1)k < -ul}. We use this approximation to define the re- laxed NN equations, which replace the nonlinear equality constraints in (3) with the convex set H((l,,) u). We denote the optimal Q-value w.r.t. the relaxed NN as Th, which is by definition an up- per bound on z.- Hence, the condition: Te. Teggoma I (Qa (2, a) - r)// is a conservative certificate for checking whether the data (xr, a,)r,,)) is inactive. For further speed up, we estimate Thd with its dual upper bound (see Appendix [for derivations) ब - m || ( + EK= E.EI, (s)] - >xp1 b5 where V is defined by the following recursion "dual" network: PK= -c, by = WJ Mo+1, j 1, 1,.... K- 1, Mj = Dy0y, j j= 2, ..... K 1, and D, is a diagonal matrix with [D,1(s, = 11s E +,,
(s)) 1(s E Z2 and replace the above certificate with an even more conservative one: To' grage < (Qo a) - -r)/7.
Although dual filtering is derived for hinge Q-learning, it also applies to the f--loss counterpart by replacing the optimal value Lh ouge with its dual upper-hound estimate To' O0me whenever the verification condition holds (i.e., the TD error is negative). Since the dual estimate is greater than the primal, the modified loss function will be lower bound of the original in (I). i.e., (r+77xx Ougee
Qo (2, a² < (r+77m,, graa Qo(x, a))² whenever + /am. game Qo a) S 0. which can stabilize training by reducing over-estimation error.
5

---

One can utilize the inactive samples in the action function (Tw) learning problem by replacing the max-Q Q label Ge with its dual approximation ar p.. Since qe 2 92 this replacement will not affect optimality. i
Clustering To reduce the number of max-Q solves further still, we apply online state aggre- gation (Meyerson 2001), which picks number of centroids from the batch of next states B' as the centers of p-metric balls with radius b > O. such that the union of these balls form a minimum covering of B.. Specifically, at training step t E (0. denote by Cr(b) S B' the set of next-state centroids. For each next state c' E Cbb)). Ler,omn = maxa' Quuan (c', a'), where 0r is the corresponding optimal action. For all remaining next states x' E BB ((()), we approximate their max-Q Q values via first-order Taylor series ex- pansion Jor grarg == Te B8rgg + V.rQuuna( (2', (z', "'' 2 (I' - c')} in which e' is the closest centroid to v.i.e., c' E arg min,rec,()) ||''-c'Ilp. By the envelope theorem for arbitrary choice sets MMilgrom & Segal 2002), the gradient V. max. Qgann (x', a') is equal to V=.Quams (x', a') d')'''=a" In this approach the cluster radius 0 controls the number of max-Q computations, which trades complexity for accuracy Bellman residual estimation. This parameter can either be a tuned or adjusted dynamically (similar to dynamic tolerance), e.g.. r4 = lig ki with hyperparameters kg >> 0 cluster radius schedule we can
compute the max-Q value
and Yą [o. 1). Analogously, with this ssponentially-eccaiin gue that the bias of CAQL. gradient (induced by max-Q estimation error due to clustering) vanishes asymptotically, and the corresponding Q-function converges to a stationary point. To combine clus- tering with dual filtering. we define Barr the batch of next states that are inconclusive after dual filtering, i.e., Byr = (x' E B', Os' 00argn > (Qn(2; a) - r)/7). Then instead of applying clustering to B' we apply this method onto the refined batch B'rr
Dynamic tolerance not only speeds up training. but also improves CAQL's performance (see Ta- bles 4 and 5): thus, we recommend using it by default. Dual filtering and clustering both trade off training speed with performance. These are practical options-wile tunable parameters-thee allow practitioners to explore their utility in specific domains.
5 EXPERIMENTS ON MUJoCO BENCHMARKS
To illustrate the effectiveness of CAQL,, we (i) compare several CAQL variants with several state-of- the-art RL methods on multiple domains, and (ii) assess the trade-off between max-Q computation speed and policy quality via ablation analysis.
Comparison with Baseline RL Algorithms We compare CAQL with four baseline methods, DDPG (Silver et al. 2014), TD3 (Fujimoto et al. 2018), and SAC (Haarnoja et al. (018)) thrree popular pasicy-based deep RL algorithms and NAT (Gu et al. 2016), a value-based method using an action-quadratic f-uuction. We train CAQL using three different max-Q Q optimizers, MIP, GA, and CEM. Note that CAQL-CEM counterpart is similar
QT-Opt (Kalashnikov et al. 2018) and
CAQL-GA reflects some aspects actor-expert (Lim et al. 2018). These CAQL variants allow assess- ment of the degree to which policy quality is impacted by Q-learning with optimal Bellman residual (using MIP) rather than an approximation (using GA or CEM), at the cost of steeper computation. To match the implementations of the baselines, we use &2 loss when training CAQL. Further ablation analysis on CAQL with & loss vs. hinge loss is provided in Appendix E
We evaluate CAQL on one classical control benchmark (Pendulum) and five MuJoCo benchmarks (Hopper, Walker2D, HalfCheetah, Ant, Humanoid) Different than most previous work, we eval- uate the RL algorithms on domains not just with default action ranges, but also using smaller, con- strained action ranges (see Table 6 in Appendix D for action ranges used in our experiments) The motivation for this is two-fold: (1) To simulate real-world problems (Dulac-Arold et al.) 2019)) where the restricted ranges represent the safe/constrained action sets; (ii) To validate the hypothe- sis that intion-diitributiinn learning in policy-based methods cannot casily handle such constraints, while CAQL does so, illustrating its flexibility. For problems with longer horizons, a larger neural network is often required to learn good policy, which in turn significantly increases the complexity
*One can also the upper bound qet.o as the label for training the action function in Section 3.2. Empiri- cally, this approach often leads to better policy performance.
$ 'Sinee the objective of these experiments is largely to evaluate different RL algorithms, we do not exploit problem structures, e.g., symmetry, when training policies.
'Smaller action ranges often induce easier MIP problems in max-Q computation. However, given the com- plexity of MIP in more complex environments such Walker2D, HalfCheetah, Ant, and Humanoid, we run experiments only with action ranges smaller than the defaults.

---

Env. |Action range]
CAQL-MIP
CAQL-GA
CAQL-CEM
NAF
DDPG
TD3
SAC
Fendulum [0,66, 0.66)
339. + 1583
+42.4 151.6
-94.6 246.5
449.4
280.5
400.3 + 180.3
48888
232.3
-789.6 + 299
Pendulum [1
235.9
122.7
257.0
135.5
236.1
116.3
312.7
242.5
2528
163.0
279.5
186.8
-366.6 1 28K
Pendulum [22 2]
143.2 + 161.0
-145.5
136.
-144. = 208.8
115.22
168.9
-146.2
+ 257.6
-142.3
195.9
-163.3 + 190.
Hopper [0,25, 0,25]
62.6
329.7
97.4
100.0
98.1
217.1
73.7
309.3 73.0
Hoppee [0.5, 0.51
411.7 1 115.2
341.7
1 139.9
342.9
1 142
248.2 1 113.2
294,5 1 108.7
280.1
1 80.0
309.1
1 95.8
Hopper
459.8
144.9
427.5
131.2
41722
145.4
243.9 140.7
139.5
372.5 138.5
Walker2D [-0.25 0,25]
276.3
118.5
285.6
= 97.6
283.7 + 104.6
219.9 120.8
270.4
- 104.2
250.0
+ 78.3
254.0
= 114.5
Walkerr21> 10.55 0.5]
288.9 + 118.1
295.6 + 113.9
M64.7 + 116.1
233.7
99.4
259.0 + 110.7
243.8 + 116.4
287.0 + 128.3
IaalCCheetah [0025, 0.25]
39488 43.8
337.4
60.0
339. 1 137.9
247
96.0
330.7
98.9
264.3
142.2
325.9
38.6
HalfChhettah [-0.5.
718.6 + 199.9
736.4
+ 122.8
686.7 + 224
405
+ 243.2
456.3
+ 238.5
213.8 214.6
614.8 + 69.4
Ani 0.11
27.4
406.2
378.2 39.7
295.0
374.0
35.9
268.9
65.3
Ani -0.25, 0.251
413.1 2 60.0
443.1
1 65.6
451.4
1 54.8
325.0 60.
444.2 1 63.3
472.3 1 61.9
399.3 1 59.2
Humanod U.I1
405.7 112.5
494,43 1820
456.3 112.4
Humanoid [-0.25, 0.25]
460.2
= 143.2
622.8
138.1
529.8
+ 179.9
374.6
126.5
582
176.7
348.1 + 106.3
446.9 + 103.9
Table 1: The mean + standard deviation of (95 (95-percentile) final returns with the best hyper- parameter configuration. CAQL significantly outperforms NAF most benchmarks, well as DDPG, TD3, and SAC on 11/14 benchmarks.
Hopparr
Happert
330
-100
-V0
-000
-750
230
-1200
231
-1200
-1250
180
332
30
330
30
383
330
332
23
209
300
400
Day
330
200
200
230
430
200
100
300
330
359
0.2
300
400
300
220
200
Thanning
Figure I:
Mean cumulative reward of the best hyper parameter configuration over 10 random seeds. Data points are average over a sliding window of size 6. The length of an episode is limited to 200 steps. The training curves with standard deviation are given in Figure in Appendix
of the MIP To reduce this computational cost, we reduce episode length in each experiment from 1000 to 200 steps, and parameterize the Q-function with relatively simple 32 x 16 feedforward ReLU network. With shorter episodes and smaller networks. the returns of our experiments are lower than those reported in state-of-the of-te-------rtt art RL benchmarks (Duan et al. 2016). Details on network architectures and hyperparameters are described in Appendix D
For the more difficult MuJoCo environments (i.e., Ant, HalfCheetah, Humanoid), the number of training steps is set to 300, 000, while for simpler ones (i.e., Pendulum, Hopper, Walker2D), it is set to 200, 000. Policy performance is evaluated every 1000 training iterations, using policy with no exploration. Each measurement is an average return over 10 episodes, each generated using separate random seed. To smooth learning curves, data points are averaged over a sliding window of size 6. Similar to the setting of [im et al. (2018). CAQL measurements are based on trajectories that are generated by the learned action function instead of the optimal action w.r.t. the Q-function.
Table Tand Figure show the average return of CAQL and the baselines under the best hyperparam- eter configurations. CAQL significantly outperforms NAF on most benchmarks, as well as DDPG, TD3, and SAC on 11 of 14 benchmarks. Of all the CAQL policies, those trained using MIP among the best performers in low-dimensional benchmarks (c.g., Pendulum and Hopper). This ver- ifies our conjecture about CAQL: Q-learning with optimal Bellman residual (using MIP) performs better than using approximation (using GA, CEM) when the Q-function has sufficient representa- tion power (which is more likely in ciw-dimensional tasks). Moreover, CAQL-MIP policies have slightly lower variance than those trained with GA and CEM on most benchmarks. Table aadd Fig- ure 2 show summary statistics of the returns of CAQL and the baselines all 320 confgurations
7

---

Env. |Action rangel
CAQL-MIP
CAQLGGA
CAQL-CEM
NAV
DDPG
TD3
SAC
Pendulum [-066, 0.66)
-700.5 3450
76666
344.2
-784.7
349
-75.3 + 3534
855.2 331
942.1 + 308.3
-144, 195.3
Pendulum [1.
508.1 + 3832
509.7
383.5
300.7 8825
529.5
3774
623.3 1952
730.3 1 389.4
972.0 1 345.5
Pendulum F2. 2]
-23.33 = 487.2
-250.6
508.1
249.7
= 488.5
-2574
+ 370.3
262.0
+ 452.6
-361 + 473.2
-639.5 + 472.7
Hopper -0.25, 0.25]
292.7
210.8
125.3
1969
130.
176.6
109.1
178.8
140.5
106.5
225.0
84.9
Hupper [U.55
332.21 1 119.7
222.2
138.5
228 1 135.7
192.8 1 101.6
218.3 1 129.6
200.
- 100.7
243.6
1 81.6
Hopper [-1
352.21 141.3
153.6
201.9 126.2
148.3
248.2 124.4
263.6 118.9
Walker2D [-0:25, 0.25]
247.6 109.0
213.5
111.
206.7
001211000 112.
190,5 117.5
200.9
= 105.6
204.8
= 113.3
224.5 105.1
Walker213 0.5)
213.1 + 120.0
119
112.5
209
+ 112.5
179.7
100.9
210.8
108.3
175.1
101.1
220.9 4 114.8
HallChhetthh [4:25, 0.25)
340.9 110:2
234.3
136.5
240.4
143.1
169.7
123.7
228.9
113.1
192.9
136.8
260.7 1 108.5
HalfCheeteh 0.5)
395.1 + 275.2
435.5
+ 273.7
377.5
+ 280.5
271.8 + 226.9
273.8
199.5
119.8
139.6
378.3 + 219.6
[..1
3194
327.5
67.5
295.5
53.1
298
67.6
213.7
40.8
205.9
34,9
Ant F0, 25, 0.25]
362.3 - 60.3
388.9
1 63.9
392.9
67.1
270.4 1 72.5
381.9 1 63.3
377.
1 93.
314.3 1 88.2
Humanoid 6..
93.5
235 165.4
227.7
261.6 154.1
259.0
188.1
251.7
127.5
377.5
Humanoid [-0.25, 0.25]
267.0 163.8
364.3
+ 215.9
309.4
18633
270.2 # 124.6
347.3
= 220.8
262.8
= 109.2
381.0 + 84,4
Table 2: The mean + standard deviation of (95-percentile) final returns over all 320 configurations
(32 hyper parameter combinations x 10 random seeds). CAQL policies are less sensitive to hyper parameters on 1/14 benchmarks.
TED
Pancad om 18.66 0.66
Penduium [-1.5
Penofolu
Ieppert 15:25, 3.251
Hoppert (4.55
-250
-004
-200
1200
-1300
-400
2.00
290
-1200
-3250
130
150
.150
-1000
30-
50
353
156
230
50
383
156
330
50
36a
150
389
53
130
150
309
53
330
350
300
Hogper 13.5, 1.0)
Wa (5.25, 3,25)
Walcer2D 5.5)
MerChsetah [0.21 225)
HaPCherrar (0..
4000
150
210
330
301
230
151
116
251
158
251
128
231
100
120
202
120
221
120
20.12..1..11
Art 0.25)
Munureic (.1)
Mumrrrll 10.25 0:25)
302
310
330
306
250
250
250
250
150
150
125
20
330
38 200
532
322
230
532
152
233
Figure 2: Mean cumulative reward over all 320 configurations (32 hyper parameter combinations x 10 random seeds). Data points are average over sliding window of size 6. The length of an episode limited to 200 steps. The training curves with standard deviation are in Figure 5 in Appendix E
(32 hyperparameter combinations x 10 random seeds) and illustrates the sensitivity to hyperparam- eters of each method. CAQL least sensitive in 11 of 14 tasks, and policies trained using MIP optimization, specifically, are best in 6 of 14 tasks. This corroborates the hypothesis that value- based methods are generally more robust to hyperparameters than their policy-based counterparts. Table 9 in Appendix [E. compares the speed (in terms of average elapsed time) of various max-Q Q solvers (MIP, GA, and CEM), with MIP clearly the most computationally intensive.
We note that CAQL-MIP suffers from performance degradation in several high-dimensional envi- ronments with large action ranges (c.g.. Ant [-0.25, 0.25] and Humanoid [-0.25, 0.25]). In these experiments, its performance is even worse than that of CAQL-GA or CAQL-CEM. We speculate that this is due to the fact that the small ReI.U NN (32 x 16) doesn't have enough representation power accurately model the Q-functions in more complex tasks, and therefore optimizing for the true max-Q Q value using an inaccurate function approximation impedes learning.
We also test CAQL using the standard MuloCo 1 1000-step episode length, using gradient ascent as the optimizer, and Q-function is parameterized with a 200 x 100 feedforward ReLU network for Hopper and with 400 x 300 for the rest benchmarks. CAQL-GA is trained using dynamic tolerance and an action function but without dual filtering or clustering. Figure 6 in Appendix E shows that CAQL-GA performs better than, or similar to, the best of the bascline methods, except on Hopper [-0.25, 0.25] performed best in that setting, however, it suffers from very high performance variance.
We now study the effects of using dynamic tolerance, dual filtering, and clus- tering CAQL via two ablation analyses. For simplicity, we experiment standard benchmarks
Ablation Analysis
8

---

Enn. [Action range]
GA
+F
GA DF C(0.25)
GA DF Cro.5)
Dual
Pendulum (-2
144.6 + 154.2
-146.1 +: 229.8
-146.7 = 216.8
-149.9 = 215.0
-175.1 246.8
(R: 0.00%)
(R: 26.5%)
(R: 79.75)
(R: 81.2%)
(R: 100%)
Hopper [-1,
414.9 181.9
424.8 176.7
396.3 138.8
371.2 + 171.7
270.2 147.6
(R: 0.00%)
(R: 9.11%)
(R: 38.25)
(R: 61.5%)
(R: 100%)
Walker2D [-1,
267.6 107.3
236.1 99.6
249.2 + 125.1
235.6 + 108.1
201.5 136.0
(R: 0.00%)
(R: 12.4%)
33.66)
(R: 50.8%)
(R: 100%)
HallCheetah I-1,
849.0 108.9
737.3 170.2
649.5 + 146.7
445.4 + 207.8
406.6 206.4
(R: 0.00%)
5.515)
(R: 15.45)
(R: 49.1%9.18
(R: 100%)
Ant 0.51
370.0 106.5
275.1 92.1
271.5 94.3
214.0 75.4
161.1 + 54.7
(R: 0.00%
(R: 3.195,1
(R: 14.3%)
(R: 31.1%)
(R: 100%)
Humanoid 0.41
702.7 = 162.9
513.9 : 146.0
458.2 = 120.4
387.7 + 117.4
333.3 = 117.9
(R: 0.00%)
(R: 13.8%)
(R: 52.1%)
(R: 80.8%)
(R: 1009))
Table 3: Ablation analysis CAQL-GA with dual filtering and clustering, where both the mean + standard deviation of (95-percentile) final returns and the average %--mx-Q-reee Q-reducctitonn (in parenthe- sis) are based on the best configuration. See Figure
7 in Appendix E
for training curves.
Env. (Ation range]
To((Tc-))
Toi(T0))
DA+DIOKIM,
Pendulum []
144.3 I. 195.6
158.1 I 165.0
114.11 159.2
.143.7 229.5
144.2 137.6
(AGA ltr: 200)
(# lt::
(# lir: 45.4)
(& lt:: 58.1)
(P lir: 69.5)
Hopper []
371.4 1993
19939
360.4 15899
4414 I 141.3
46LD 127.8
452.5 I 137.0
(A 200)
(A lt::
(# lir: 46.0)
(A ltr: 59.5)
(9 (A ltr: 78.4)
Walker2D [-1,
273.6 1. 112.4
281.6 121.2
2820 1. 104.5
309.0 1. 118.8
292.7 1: 113.8
(A 200)
(# D)
(* 47.4)
(A 59.8)
(# 71.2)
HaliChoetah [-I.
837.5 = 130.6
129.3 313.8
8966 = 145.7
864,4 + 123,1
894.0 = 159.9
GA 200)
(* 91.2)
(A 113.5)
Itr: 140.7)
Ant [M0.330003]
373.1 = 118.5
420.7 148.8
364,4 111.324
388.2 + 110.7
429.3 = 139.3
GA 200)
(+ D)
(+ 86.3)
GA 109.5)
ltr: 139.7)
Humanoid [-0.4,0.]
689.8 = 193.9
500.2 = 214.9
7162 = 191.4
689.5 + 191.6
710.9 = 188.4
GA 200)
(# GA D)
GA 88.6)
GA Ir: 115.9)
ltr: 133.4)
Table 4: Ablation analysis on CAQL-GA with dynamic tolerance, where both the mean + standard deviation of (95 (95-percentile) final returns and the average number of GA iterations (in parenthesis) based on the best configuration. See Figure in Appendix for training curves. NOTE: In (+)
the performance significantly drops after hitting the peak, and learning curve does not converge.
(with full action ranges), and primarily test CAQL-GA using an fg loss. Default values on tolerance and maximum iteration are le-6 and 200, respectively.
Table 3 shows how reducing the number of max-Q problems using dual filtering and clustering af- fects performance of CAQL. Dual filtering (DF) manages to reduce the number of max-Q problems (from 3.2% 26.5% across different benchmarks), while maintaining similar performance with the unfiltered CAQL-GA. On top of dual filtering we apply clustering (C) to the set of inconclusive next states By in which the degree of approximation is controlled by the cluster radius. With small cluster radius (e.g.. impacting training performance (and in some cases it actually improves performance), though fur- ther increasing the radius would significant degrade performance. To illustrate the full trade-off of max-Q reduction versus policy quality, we also include the Dual method, which eliminates all max- Q computation with the dual approximation. Table 4 shows how dynamic tolerance influences the quality of CAQL policies. Compared with the standard algorithm, with a large tolerance (7 100) GA achieves notable speed up (with only 1 step per max-Q optimization) in training but incurs loss in performance. GA with dynamic tolerance atttains the best of both worlds- significantly reduces inner-maximization steps (from 29.5% to 77.3% across different problems and initial settings), while achieving good performance.
0.1), clustering further reduces max-Q solves without significantly
Additionally, Table shows the results of CAQL-MIP with dynamic tolerance (i.e., optimality gap). This method significantly reduces both median and variance of the MIP elapsed time, while having better performance. Dynamic tolerance eliminates the high latency in MIP observed in the early phase of training (see Figure
Env. [Action range]
MIP + Tok(e=4)
MIP D'TokLJee4)
HalfChoctah 0-3.5.0.3]
718.6 + 199.9 (Mdinn:: 263.3, SD(R). (6.269)
764.5 = 132.9 (ModiNE 118.5, SD(K): 75.610)
Ant (-0.1,
27.4 (Medres): 80.7, SDG))
404.9 27.7 (Medic): 40.3, SD(K):
Ani (0225, 0.25]
413.1 1: 60.0 (Med(rg 87.6, SDIRE 160.211)
424.9 1. 60.9 (MediRE 6200 SDORE 27.646)
Humanoad 6.1
405.7 -: (MedixE
SDAY 27.381)
475.0 1 173.4 (MGloo) 29.1, SDIRE: 10.508)
Humanoid [-025. 0.25]
460.2 # 143.2 (Med(n). 71.2. SDXO): 45.763)
410.1 + 174,4 (MSd(o) 39.7. SDOO) 11.088)
Table 5: Ablation analysis on CAQL-MIP with dynamic tolerance, where both the mean + standard
deviation of (9e-peccet final returns and the (median, standard deviation) of the elapsed time (in msec) are based on the best configuration. See Figure
II in Appendix for training curves.

---

6 CONCLUSIONS AND FUTURE WORK
We proposed Continuous Action Q-learning (CAQL), a general framework for handling continuous actions in value-based RI, in which the Q-function is parameterized by neural network. While generic nonlinear optimizers ner maximization of Q-learning can be formulated as mixed-integer programming when the Q- function is parameterized with a ReL. network. CAQL (with action function learning) is a general Q-learning framework that includes many existing value-based methods such QT-Opt and actor- expert. Using several benchmarks with varying degrees of action constraint, we showed that the policy learned by CAQL-MIP generally outperforms those learned by CAQL-GA and CAQL-CEM; and CAQL is competitive with several state-of-the-ar policy-based RL algorithms, and often out- performs them (and is more robust) in heavily-constrained environments. Future work includes: extending CAQL to the full batch learning setting, in which the optimal Q-function is trained using only offline data; speeding up the MIP computation of the max-Q problem to make CAQL more scalable; and applying CAQL. to real-world RI. problems.
be naturally integrated with CAQL, illustrated how the in-
REFERENCES
B. Amos, L. Xu, and Z. Kolter. Input convex neural networks. In Proceedings of the 34th Interna- tional Conference on Machine Learning, volume 70, pp. 146-155, PMLR, 2017.
R. Anderson, J. Huchette, W. Ma, C. Tjandraatmadja, and J. P. Vielma. Strong mixed-integer pro- gramming formulations for trained neural networks. arXiv preprint arXiv: I. 1.01988, 2019.
C. Boutilier, A. Cohen, A. Hassidim, Y. Mansour, O. Meshi, M. Mladenov, and D. Schuurmans. Planning and learning with stochastic action sets, In Proceedings of the 27th International Joint Conference on Artificial Intelligence, JJCAI' 18, pp.
AAAI Press, 2018.
R. Bunel, Turkaslan, Torr, Kohli, and M. P. Kumar, A unified view of piecewise linear neural network verification. In Advances in Neural Information Processing Systems 31, pp. 4790-4799. 2018.
S. Carden. Convergence of a Q-learning variant for continuous states and actions. Journal of Artificial Intelligence Research, 49:705-731, 2014.
C.-H. Cheng, G. Nührenberg, and H. Ruess. Maximum resilience of artificial neural networks. In International Symposium on Automated Technology for Verification and Analysis, pp. 251-268. Springer, 2017.
Y. Chow, O. Nachum, F. Duenez-Guzman and M. Ghavamzadeh. A Lyapunov- baased approach to safe reinforcement learning. In Advances in Neural Information Processing Systems 31, pp- 8092-8101. Curran Associates, Inc., 2018.
IBM ILOG CPLEX. V12.1: Userâs manual for CPLEX, 2019. URL httph:ttp////m //wp::://wwww.... www. ibm. com/
iwwiiationnssttt studio
Y. Duan, X. Chen, R. Houthooft, J. Schulman, and P. Abbeel. Benchmarking deep reinforcement learning for continuous control. In International Conference Machine Learning, pp. 1329- 1338, 2016.
G. Dulac-Arnold, R. Evans, H. van Hasselt, P. Sunchag, T. Lillicrap, J. Hunt, T. Mann, T. Weber, T. Degris, and B. Coppin. Deep reinforcement learning in large discrete action spaces. arXiv preprint arXiv:1512.07677 2015.
G. Dulac-Amold, D. Mankowitz, and Hester. Challenges of real-world reinforcement learning. arXiv preprini arXiv: 12901, 2019.
Dutta, S. Jha, S. Sankaranarayanan, and Tiwari. Output range analysis for deep feedforward neural networks. In NASA Formal Methods Symposium, pp. 121-138. Springer, 2018.
M. Fazel, R. Ge, S. Kakade, and M. Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In Proceedings of the 35th International Conference on Machine Learning, volume 80. pp. 1467-1476, Stockholm, Sweden, 2018. PMLR.
M. Fischetti and J. Jo. Deep neural networks and mixed integer linear optimization. Constraints, 2018.
10

---

S. Fujimoto, H. van Hoof, and D. Meger. Addressing function approximation enror in actor-critic methods. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 1587-1596, Stockholm, Sweden, 2018. PMLR.
C. Gaskett, D. Wettergreen, and A. Zelinsky. Qllearning in continuous state and action spaces. In Proceedings of the 12th Australian Joint Conference on Artificial Intelligence, pp. 417-428. Springer, 1999.
J. Gauci, E. Conti, Y. Liang, K. Virochsiri, Y. He, Z. Kaden, V. Narayanan, and X. Ye. Horizon: Facebook's open source applied reinforcement learning platform. arXiv preprint arXiv: 2018.
A. Gleixner, M. Bastubbe, L. Eifler, T. Gally, G. Gamrath, R. L. Gottwald, G. Hendel, C. Hojny, T. Koch, M. E. Lübbecke, S. J. Maher, M. Miltenberger, B. Müller, M. E. Pfetsch, C. Puchert, D. Rehfeldt, Schlösser, C. Schubert, F. Wegscheider, J. T. Witt, and J. Witzig. The SCIP Optimization Suite 6.0. Technical report, Optimization Online, July 2018. URL http:///wwwt opt imi www.zatiiiooooo inn. org/ /DB HTML/2018/C7/6692.oo html
Serrano, Y. Shinano. J. M. Viernickel, M. Walter,
Gu, T. Lillicrap, I. Sutskever, and Levine. Continuous deep Q-learnigg with model- based accel- eration. In Proceedings of The 33rd International Conference on Machine Learning, volume 48, pp. 2829-2838, New York, NY, USA, 2016. PMLR.
Gurobi. Gurobi optimizer reference manual, 2019. URL http:://ww.gur..t// .co.rriii.ommm. coom
T. Haarnoja, A. Zhou, P. Abbeel, and Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In Proceedings of the 35th International Conference Machine Learning, volume 80, pp. 1861-1870, Stockholm, Sweden, 2018. 2018.PMLR. PMLR.
H. Van Hasselt, A. Guez, and D. Silver. Deep reinforcement learning with double Q-learning, In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI' 16, pp. 2094- 2100. AAAI Press, 2016.
L. Baird III and A. Klopf. Reinforcement learning with high-dimensional, continuous actions. Tech- nical report, Wright Lab Wright-Patterson AFB OH, 1993.
D. Kalashnikov, A. Irpan, P. Pastor, J. Ibarz, A. Herzog, E. Jang, D. Quillen, F. Holly, M. Kalakrish- nan, V. Vanhoucke, and S. Levine. QT-Opt Scalable deep reinforcement learning for vision-based robotic manipulation. In Proceedings of The 2nd Conference on Robot Learning, volume 87, pp- 651-673. PMLR, 2018.
G. Katz, C. Barrett, D. L. Dill, K. Julian, and M. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pp. 97-117. Springer, 2017.
A. Kumar, T. Serra, and S. Ramalingam. Equivalent and approximate transformations of deep neural networks. arXiv preprint arXiv: 1905. / 1428, 2019.
A. Lazaric, M. Restelli, and A. Bonarini. Reinforcement learning in continuous action spaces through sequential Monte Carlo methods. In Advances in Neural Information Processing Sys- tems, pp. 833 840, 2008.
S. Lim, A. Joseph. L. Lc, Y. Pan, and M. White. Actor-Expert: A framework for using action-value methods in continuous action spaces. arXiv preprint arXiv:1810.09100 2018.
L. Lin and T. Mitchell. Memory approaches to reinforcement learning in non-Markovian domains. Technical report, Pittsburgh, PA, USA, 1992.
J. Linderoth and M. Savelshergh. A computational study of search strategies for mixed integer programming. INFORMS Journal on Computing, 11(2):133-177, 1999.
A. Lomuscio and L. Maganti. An approach reachability analysis for networks. arXiv preprint arXiv: 106.0730... 2017.
ReLU neural
S. Mannor, R. Rubinstein, and Y. Gat. The cross entropy method for fast policy search. In Proceed- ings of the 20th International Conference on Machine Learning, ICML'03, pp. 512-519, AAAI Press, 2003.
11

---

F. Melo and M. Ribeiro. Q-learning with linear function approximation. In International Conference on Computational Learning Theory, pp. 308 008-322. Springer, 2007.
A. Meyerson. Online facility location. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 426-431. IEEE, 2001.
Milgrom and Segal. Envelope theorems for arbitrary choice sets, Econometrica, 70(2):583-601, 2002.
J. Millán, D. Posenato, and E. Dedieu. Continuous-action Q-learning. Machine Learning, 49(2-3): 247-265, 2002.
V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, Antonoglou, D. Wierstra, and M. Riedmiller. Playing Atari with deep reinforcement learning. arXiv preprint conferernc on machine
2013.
V. Mnih, A. Badia, M. Mirza, A. Graves, T. Lillicrap, T. Harley, D. Silver, and K. Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference learning, pp. 1928-1937, 2016.
G. Neu, A. Jonsson, and V. Gómez. A unified view of antroyy-regularin Markov decision pro- cesses, arXiv preprint
2017.
J. Nocedal and S. Wright. Numerical optimization. Springer Science & Business Media, 2006.
J. Nocedal and Y. Yuan. Combining trust region and line search techniques. In Advances in nonlinear programming, pp. 153-175. Springer, 1998.
J. Peters and S. Schaal. Policy gradient methods for robotics. In 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2225. IEFE, 2006.
M. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
D. Quillen, E. Jang, O. Nachum, C. Finn, J. Ibarz, and S. Levine. Deep reinforcement learning for vision-based robotic grasping: A simulated comparative evaluation of poficc methods. CoRR, has/1802.10264, 2018 http:/
org/ abs 1002 102
R. Rubinstein. The cross-entropy method for combinatorial and continuous optimization. Method- ology And Computing In Applied Probability, 1(2): 1999.
B. Say, Wu, Y. Q. Zhou, and S. Sanner. Nonlinear hybrid planning with deep net learned transition models and mixed-integer linear programming. In Proceedings of the Twenty-Sine International Joint Conference on Artificial Intelligence, IJCAI' pp. 750-756, 2017.
T. Serra, C. Tjandraatmadja, and S. Ramalingam. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learning, pp. 4573, 2018.
D. Silver, G. Lever, N. Heess, T. Degris, D. Wierstra, and M. Riedmiller. Deterministic policy gradi- ent algorithms. In Proceedings of the 31 International Conference International Conference on Machine Learning Volume 32, ICML' 14, pp. 1-387-1-395, JMLR.org, 2014.
W. Smart and L. Kaelbling. Practical reinforcement learning in continuous spaces. In Proceedings of the Seventeenth International Conference on Machine Learning, ICML '00, pp. 903-910, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc
R. Sutton, D. McAllester, S. Singh P. and Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, pp. 1057-1063, 2000.
V. Tjeng, K. Xiao, and R. Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference Learning Representations, 2019,
W. Uther and M. Veloso. Tree based discretization for continuous state space reinforcement learning. In Proceedings of AAAI '98, pp. 769-774, 1998.
C. Watkins and P. Dayan. Q-learning. Machine learning, 8(3-4)277-292, 1992.
T. Weng, H. Zhang, H. Chen, Z. Song, C. Hsieh, D. Boning, I. Dhillon, and L. Daniel. Towards fast computation of certified robustness for ReLU networks. arXiv preprint arXiv: 1804.096999 2018.
E. Wong and Z. Kolter. Provable defenses against adversarial examples via the convex outer adver- sarial polytope. arXiv preprint arXiv: /11.1/7111008..1 2017.
12

---

A HINGE Q-LEARNING
Consider an MDP with states X, actions A, transition probability function P. discount factor Y e [0. 1). reward function R. and initial state distribution B. We want to find an optimal Q-function by solving the following optimization problem:
min Σ p(z,a)Q(xx,)
=EX,aEA
Q(x.a) R(z,a) +Y
E P(x' xr a) max Q( Q(a',a)), ve X, x'X
(5)
a'EA
The formulation is based the LP formulation of MDP (see Puterman 2014) for more details). Here the distribution p(z, a) is given by the date-geneg distribution of the replay buffer B. (We assume that the replay buffer is large enough such that it consists of experience from almost all state-action pairs.) It is well-known that problem into an unconstrained one by applying a penalty-based approach (to the constraints). For simplicity, here we stick with single constant penalty parameter À 2 0 (instead of going for state-action Lagrange multiplier and maximizing that), and hinge penalty function (+)_. With given penalty optimal Q- Q-function by solving the following optimization prohlem:
transform the above constrained optimization
2 (that can be separately optimized), we propose finding the
p(z,a)Q(I, + [[(z,a)+ P(a'Iz a) ((ex aEE
min
(6)
d'Ed
ZEX
Furthermore, recall that in many off-policy and offline RL algorithms (such as DQN), samples in form of {(x; a, x,, are independently drawn from the replay buffer, and instead of the op- timizing the original objective function, one goes for its unbiased sample average approximation (SAA). However, viewing from the objective function of problem (6). finding an unbiased SAA for this problem might be challenging, due to the non-linearity of hinge penalty function (-)+- There- fore, alternatively we turn to study the following unconstrained optimization problem:
min Σ pla, (zz,))(z.a)++ Σ P(x' (tclla,, ar (((,, +y max Q(z', - (7) x'
a'EA
ZEX,aEA
Using the Jensen's inequality for convex functions, one can see that the objective function in 7 an upper-bound of that in (6). Equality of the Jensen's 's inequality will hold in the case when transition function is deterministic. (This is similar to the argument of PCL algorithm.) Using Jensen's inequality one justifies that optimization problem 7 is indeed eligible upper-bound optimization to problem (6).
Recall that p(z, a) is the data cata-generation distribution of the replay buffer B. The unbiased SAA of problem 7 is therefore given by
Σ
Q1), + rra max ((x -( a'EA
min Q
where [xx ag Pr. x,)) 1 following, will find the optimal Q function by solving this SAA problem. In general when the state and action spaces are large/uncountable, instead of solving the Q-function exactly (as in the tabular case), we turn to approximate the Q-function with its parametrized form Qs. and optimize the set of real weights 0 (instead of Q) in problem 8
a are the samples drawn independently from the replay buffer. In the
13

---

B CONTINUOUS ACTION Q-LEARNING ALGORITHM
Algorithm 1 Continuous Action Q-learning (CAQL)
1: Define the maximum training epochs T', episode length L, and training steps (per epoch) S
2: Initialize the Q-function parameters 6, target Q-function parameters (lurgi, and action function parameters w
3: Choose a max-Q solver OPT E {MIP, CEM, GA} (Section
4: Select options for max-Q speed up (Section 4 using the following Boolean variables: (i) DTol: Dynamic Tolerance, (ii) DF: Dual Filtering, (iii) C: Clustering; Denote by OPT(Dtol) the final max-Q solver, constructed by the base solver and dynamic tolerance update rule (if used)
5: Initialize replay buffer R. of states, actions, next states and rewards
6: for f- 1,..., T
7:
Sample an initial state from the initial distribution for E f- ........ L do
8:
Online Data Collection
9:
Select action ag clip(z + (0, a.. u)
10:
Execute action d, and observe reward ry and new state I++1 Store transition (zz, ag, 1(+1) in Replay Buffer R
11:
for
1, , do
CAQL Training; S 20 by default
13:
Sample a random minibatch B of [B] transitions ((1;, az Fi, x1,11)1111 from
14:
Initialize the refined batches B'r x- B and B' < B;
(i) IF DF is True:
Ba (1x a, r.)) E B To' gona (Qo(z,a)-r)/1
(ii) IF C is True:
B: t (10,0, E B:r E C,(b)}
15:
For each (Is 0z, r,, E BBrr By, compute optimal action ae using OPT(DTol):
df E arg max Qo(24,a') o'
16:
and the corresponding TD targets:
Oi = ri + vo
yagge (1',, a!)
17:
For each (Ii, di ri, 2 E B BBB Byy),, compute the approximate TD target:
(i) Cs True: V(a,, a4 ry, r(, x()) E Bar \ By, @i x ri + 70c
where lug.ounn = gepe + Qu (x', aa') l'))aa= ala'= a'=ay (0) -0))
and of E C.(b) is the closest centroid to x/}
(ii) IF DF is True: V(z,, os, re, x.)) B B'r 96 r, aun.
18:
Update the Q-function parameters:
<- arg min
-
B
19:
Update the action function parameters:
arg min 1
Σ ((00(16)0) -olc,
nn (z!))))
B
20:
Update the target function parameters:
Ouarett + T0 + (1 Puurgot
21:
Decay the Gaussian noise:
0 0 E [0
14

---

C DETAILS OF DUAL FILTERING
Recall that the Q-function NN has a nonlinear activation function, which can be viewed as a non- linear equality constraint, according to the formulation in (3). To tackle this constraint, [Wong & Kolter (2077) proposed convex relaxation of the ReLU non-linearity. Specifically, first, they sume that for given x' E X and a' E Bx (T) such that 21 = (z' (z',a'), there exists collection of component-wise bounds Uy), ] = 2,..., K redundant, adding these constraints into primal problem q. does not affect the optimal value. Second, the ReLU non-linear equality constraint is relaxed using a convex outer-approximation. In particular, for a scalar input a within the real interval [t. u/, the exact ReLU non-linearity acting on is captured by the set
1 such that 1 S 2j S Uj. As long as the bounds
= H(l, u) {(b, k) IR? h [1, = [b]+}.
Its convex outer- outer- approximaiooxoinnnnnmmm is given by:
Hl(1, u) ((h, k) E R22 h k 2 0, -u + (u 1)k S -ul).
(9)
Analogously to 3 define the relaxed NN equations
(z', a'), a' E Box (0,, A)
(10a)
2g Wj
.,...,
(10b)
(2), E H1 uj); j j= ,,..., K- 1,
(10c)
where the third equation above is understood be component-wiss across layer for each j
{2...., K 1], i.e.
(s) (5)) (())()) = 1, Rgj
where n, is the dimension of hidden layer j. Using the relaxed NN equations, we now propose the following relaxed (convex) verification problem:
K-1
max 2,=
c cT2 +
+
Σ
(
(1
f=2
s.t. 8 W
j 2, K,
(1lb)
where (.) is the indicator function for set A (i.e., 6x(x) = 0f x E A and co otherwise). Note that the indicator for the vector-ReLU in cost function above is understood to be component-wise, i.e.,
m2
u (1)1
Σ
= 2, ....... 1.
The optimal value of the relaxed problem, i.e., The an upper bound on the optimal value for original problem z.y- Thus, the certification one can obtain is the following: if Th S (Qo(2, a) r) r)/7, then the sample (ar, a, a²)x) is discarded for inner maximization. However, if Th (Qr a) r)/7, the sample (z, a, x²) may or may not have any contribution to the TD-error in the hinge loss function.
To further speed up the computation of the verification problem, by looking into the dual variables of problem (11), in the next section we propose numerically efficient technique to estimate sub- optimal, upper-bound estimate to Th namely Ye' Therefore, one verification criterion on whether a sample drawn from replay buffer should be discarded for maximizaaii is check whether the following inequality holds:
To' S Q0(2, a) -r
(12)
C. SUB-OPTIMAL SOLUTION TO THE RELAXED PROBLEM
In this section, we detail the sub-optimal lower bound solution to the relaxed problem in 11 as
proposed in Wong & Kolter (017). Let uy. 2, ..., K denote the dual variables for the linear
cquality constrannt ın problem ITT.. The Lagrangian for the relaxed problem in (IT) is given by:
1(2,z (c êK + =k²K) +
VI W121) +
K-1
K-1
Σ
(oRa), (2)) + vJJ W)
Σ bs41bg.
3=1
15

---

Define 2 := : W 11+1 for = 1..... K 1, and define 'f' (WF) V2g 29 (Wf')² TT2 Then, given the decoupled structure of L in (2), 2z), minimizing L w.r.t. (2, 2) yields the following dual function:
((/x)) 8/ ((z)))-=
K-1 8 R()), 5 (0))) (0f')
-
Eje K-1 Velibe
if
g(v)
else.
(13)
Recall that for a real vector space X C R", let X denote the dual space of X with the standard pairing (.-)) X X + R. For real-valued function X k U foo,-00) let
X R fo0, -oo be its convex conjugate, defined as: (v) = imfzex (f(x) (y) x))
suPzEx ((y.2) f())), vy E X". Therefore, the conjugate for the vector-Rela ReLU indicator above takes the following component-wiss structure:
((t)) Σ (onnt
j 1-
(14)
Now, the convex conjugate of the set indicator function is given by the support function. Thus,
o (z) (8 = oT + +
|l l1g:
where || ||g is the 1p-dual conjugate for the ReLU relaxation, we analyze the scalar definition as provided in ( Specifically, we characterize 8 (H (p. 9) defined by the scalar bounds (4, u). for the dual vector (p.9) E RR. There exist possible cases:
defined by the identity 1/p 1/4 1. To compute the convex
Case 1:1 < u S 0:
p-
ifp 0
8 (p.
p-l
if pp pf
(15)
Case HI: < u.
(p g)
i
8 ku. (p.9) 9)
(p 1)+
i
(16)
0
ifp=
Case III: u: For this case, the sup will occur either on the line uu + (u fly at the origin. Thus,
ul or
_ R(l.a) (p.g) = sup p. h u
u-1 (h 1)
hell,u]
sup bE(l.u]
p q. --) h q
1
(17)
[Iv + 4) .u]
p
11
[p-1] [-11-
if
p
q I.
=pp-10 1p- +]
if
p +
0.
Applying these in context of equation following cases.
[4 we calculate the Lagrange multipliers by considering the
Case I: 15()) < (s)()) 0: In this case, since (s(s) = 0 regardless of the value of 2,(s), one can
simply remove these variables from problems [10 and 11 by eliminating the jth row of W, and
by-1 and the 5th column of W,. Equivalently, from 15 one can remove their contribution in 13
by setting (s()) = O.
16

---

Case 11: 0 - (1)) <s)(s): In this case, the ReLU non-linearity for (2,(s), (s)) in problems (10)
and (11) may be replaced with the convex linear equality constraint 2,(5) (5)s) with associated
dual variable j.. Within the Lagrangian, this would result in modification of the term
oHa,))) (2) 2y (5) +2 (s) - (5)))2((5)
-
(3)) +
+
Minimizing this over (s), (+))), a non-trivial lower bound (i.e., is obtained only if vy(s)
Py(s) = -r. Equivalently, from 16., we set (s) = 0y(s).
Case III: For the non-trivial third case, where 1,(s) < 0 < (s), notice that due to i, the dual function g(v) not decoupled across the layers. In order get a sub-optimal, but analytical solution to the dual optimization, we will optimize each term within the first sum in (33) independently. To do this, notice that the quantity in sub-case in (17) is strictly greater than the other two sub-cases. Thus, the best bound is obtained by using the third sub-case, which corresponds setting:
Mi (s(())
By (s(s) (s)
us(s) (s)
Combining all the previous analysis, we now calculate the dual of the solution to problem 111 Let Zj := {s E Nn, (s)s) S 0}, IJ == {s E N,, (s(s) 2 0}, and Z, == NR, \ (Z) U I
Using the above case studies, a sub-optimal (upper-bound) dual solution the primal solution Ju' in problem (11) is given by
K-1
R-1 Djtbb
T := == A1109 (1F) +
Σ ((s))(()))
- Σ 1=1
(18)
SEZ
where v is defined by the following recursion, termed the "dual" network:
VK := -, 2j = W Ps+1.
j = 1, I.....K K 1, :D::Dyyy j= K -1, (19)
and D, is a diagonal matrix with
if E I, if
s))
(20)
(s)
if EZj
(8( - (8)
C.2 COMPUTING PRE-ACTIVATION BOUNDS
For (3..... ......,KK... K - 1}, define the k --partial NN as the set of equations:
21 a1'd,',", = = by-1,
== 2, 2, h j= k
(21)
Finding the lower bound 4. for Es involves solving the following problem:
min E.=
e, 2
(22)
s.t. =1 = (x',a'),,, d' E Boc A), eq.
(23)
where is one-hot vector with the non-zero element in the s-th entry, for E {1,.... n2). Simi- larly, obtain Uy by maximizing the objective above. Assuming are given bounds {4,, u ) we can employ the same convex relaxation technique and approximate dual solution for the verifi- cation problem (since we simply optimizing a linear function of the output of the first layers of the NN). Doing this recursively allows us to compute the bounds {4g. u. for j = 3,..., K 1. The recursion is given in Algorithm I in Wong & Kolter (2017) and is based on the matrix form of the recursion 19), i.c., with replaced with / and -I, so that the quantity in (18) vector-valued.
k-1
17

---

D EXPERIMENTAL DETAILS
Environment
State dimension
Action dimension
Action ranges
Pendulum
3
[-2, 21. [-1, 11, [-0.66, 0.66]
Hopper
3
-1, 1J. [-0.5, 0.5], [-0.25, 0.25]
Walker2D
17
6
- 1]. [-0.5, 0.51, [-0.25, 0.25
HalfCheetah
17
6
[I, [-0.3 0.51, [-0.25, 0.25
Ant
111
8 [11.0, 1.0], [-0.5, 0.5], [-0.25, 0.25], [-0.1, 0.1] [-0.4, 0.4), [-0.25, 0.25]. [-0.1, 0.1]
Humanoid
376
17
Table 6: Benchmark Environments. Various action bounds are tested from the default to smaller ones. The action range in bold is the default one. For nigh-dimensional environments such as Walker2D, HalfCheetah, Ant, and Humanoid, we only test on action ranges that are smaller than the default (in bold) due to the long computation time for MIP. A smaller action bound results in MIP that solves faster.
Hyper Parameters for CAQL and NAF
Value(s)
Discount factor
0.99
Exploration policy
(O o 1) 0.9995, 0.9999
Exploration noise (σ) decay
Exploration noise (a) minimum
0.01 0.001
Soft target update rate (7)
Replay memory size
105
Mini-batch size
64
Q-function learning rates
0.001, 0.0005, 0.0002, 0.0001
Action function learning rates (for CAQL only)
0.001, 0.0005, 0.0002, 0.0001
Tolerance decay (for dynamic tolerance)
0.995, 0.999, 0.9995
Lambda penalty (for CAQL with Hinge loss)
0.1. 1.0, 10.0
Neural network optimizer
Adam
Table 7: Hyper parameters settings for CAQL(+ MIP, GA, CEM) and NAF We sweep over the Q-function learning rates, action function learning rates, and exploration noise decays.
Hyper Parameters for DDPG, TD3, SAC
Value(s)
Discount factor
0.99
Exploration policy (for DDPG and TD3)
N(0, a 1) 0.9995
Exploration noise (σ) decay (for DDPG and TD3)
Exploration noise (a) minimum (for DDPG and TD3)
0.01
Temperature (for SAC)
0.99995, 0,99999
Soft target update rate (T)
0,001
Replay memory size
10
Mini-batch size
64
Critic learning rates
0.001, 0.0005, 0,0002, 0.0001
Actor learning rates
0.001, 0.0005, 0.0002, 0.0001 Adam
Neural network optimizer
Table 8: Hyper parameters settings for DDPG, TD3, and SAC. We sweep the critic learning rates, actor learning rates, temperature,and exploration noise decays.
We use two hidden layer neural network with ReLU activation (32 units in the first layer and 16 units in the second layer) for both the Q-function and the action function. The input layer for the Q-function is concatenated vector of state representation and action variables. The Q-function has a single output unit (without ReLU). The input layer for the action function is only the state representation. The output layer for the action function has d units (without ReLU), where d is the action dimension of a benchmark environment. We use SCIP 6.0.0 (Gleixner et al., 2018) for the MIP solver. A time limit of 60 seconds and a optimality gap limit of 10 are used for all experiments. For GA and CEM, a maximum iterations of 20 and convergence threshold of 10 used for all experiments if not stated otherwise.
18

---

E ADDITIONAL EXPERIMENTAL RESULTS
E.1 OPTIMIZER SCALABILITY
Table shows the average elapsed time of various optimizers computing max-Q in the experiment setup described in Appendix [D] MIP is robust action dimensions than GA and CEM. MIP latency depends on the state of neural network weights. It takes longer time with highly dense NN weights, but on the other hand, it can be substantially quicker with sparse NN weights. Figure shows the average elapsed time of MIP served that MIP very slow the beginning of the training phase but it quickly becomes faster. This trend is observed for most benchmarks except Humanoid. We speculate that the NN weights for the Q-function are dense the beginning of the training phase, but it is gradually structurized (e.g, sparser weights) so that it becomes an casier problem for MIP.
training steps for various benchmarks. We have ob-
Ean: [Action range]
CEM
MIP
Hopper [-1.0, 1.0]
Mediay: 1L00,, STXCY: 0.155
Mediay: 0.375, SDIY 0.059
Med(ny: 85.515, SDRE 209
Walker2D [-0.5, 0.5]
Mediey: 0.093, SDXx). 0.015
MedrwJ: 0,406, SDIR). 0.075
Medoc): 104,968, SDINE 178.797
HallCheetah (-0.5, 0.5]
Med(ay: 0.093, SDO6): 0.015
Med(ae): 0.296, SDGs): 0.072
Med(s): 263.453, SDüx): 88.269
Ani 0.225, 0,25
Med(re): 0.109, SDXRE: 0.018
Medizi:: 0,341, SDIRE 0.054
Medoyy: 87,640, SDXKE: 160.91
Humannid [.025, 0.25
Medlay 0.140, STXee; 0002
Mediae:: 0.640, SDXR:: 0.T33
Med(ay T..11. 45.763
Table The (median, standard deviation) for the average elapsed time x (in msec) of various solvers computing max-Q problem.
Dynamic
Elapsed for Mext) com pomijuaaionn (mnse)
HalfCheetah [-0.5, D.5]
Ant [-0.25, 0.25]
Humanaid 1-0.25, 0.25)
1200
2500
300
1.000
250
2000
800
200
1500
150
1000
400
500
Training Steps
Training Steps
Training Steps
Figure 3: Average elapsed time (in msec) MIP computing max-Q with constant and dynamic optimality gap.
19

---

E.2 ADDITIONAL RESULTS
Happart
-500
-11
-1000
-1300
231
331
246
300
400
830
230
369
700
204
000
254
200
200
Trandig 100e
Thandin Febdd
(a) Mean cumulative reward with full standard deviation.
Hopger
Hopper
-250
.20
-20
300
430
-150
-188
230
1150
1400
303
Happer
300
200
200
430
359
510
300
300
304
300
300
220
200
Thaniing Sama (023))
Thaniig (-1d))
The Ta (-20))
Thamen Stmm c4lud)
(b) Mean cumulative reward with half standard deviation.
Figure 4: Mean cumulative reward of the best hyper parameter configuration over 10 random seeds. Shaded area is + full or half standard deviation. Data points are average over a sliding window of size 6. The length of episode is limited to 200 steps.
20

---

Persudum 0.66, 0,66]
Pardwuu
-546
-25
-15
-18
1180
-3000
291
-109
-150
-300
Wilbor0 5.25]
WalcerD (4.5
325)
H4PCheeraa
306
200
200
0-
(..25.
300
300
240
200
200
100
Traniig
1g
Trunh
(a) Mean cumulative reward with full standard deviation.
Percidum
Haspel
430
330
-3300
130
-276
400
530
200
200
100
089
330
200
250
150
234
1aaring
(b) Mean cumulative reward with half standard deviation.
Figure 5: Mean cumulative reward over all 320 configurations (32 hyper parameter combinations 10 random seeds). Shaded area is + full or half standard deviation. Data points are average over a sliding window of size 6. The length of episode is limited to 200 steps.
21

---

10.0
5000
2009
0.2.0
3000
1700
1000
250
200
1000
350
483
630
306
1000
256
1200
1549
2009
500
1006
1304
3000
226
483
530
100
Mostoo F..... 1.01
An: (0225, 0.25
Anc F.100.
Mumareid 00.1 0.11
1Mmrrooe 12.4.
4000
5000
33000
3000
2009
0203
4008
3000
5000
2000
100
280
1004
Yainig 2mpp. HA66
Stagi (x
Traning (xdal)
(a) Mean cumulative reward with full standard deviation.
Happer
Mupper (-l..
15:00
2008
2009
15:0
1000
1009
500
250
400
306
491
6m
17tm
19th
1928
2003
60
1180
1128
209
224
491
303
1764
1nd HnMtCeettt hestat 1..5
4000
Amt (325,,02) 021
6000
Ant 1.5.
4000
Hummarel (-3.1,00
0000
Bamaneic 13.4.0..1
13500
3008
2000
4003
200
100
2003
Tuitre 14500
Thamms Seps
Tra Ontt
Thaniin 203e5t
Themrna Stens (c260)
(b) Mcan cumulative reward with half standard deviation.
Figure 6: Mean cumulative reward of the best hyper parameter configuration over 10 random seeds. Shaded area is + full or half standard deviation. Data points are average over a sliding window of size 6. The length of an episode is 1000 steps.
22

---

E.3 ABLATION ANALYSIS
Posper
Harerrld
340
4.00
200
159
175
30
180
175
28
100
W
301
160
180
206
303
504
300
25
150
206
Figure 7: Mean cumulative reward of the best hyper parameter configuration over 10 random seeds. Shaded area is + standard deviation. Data points are average over sliding window of size 6. The length of an episode is limited 200 steps.
We 11.5,
Hepper 11 5,1
Haraneld 13.4
350
350
380
100
150
115
189
175
248
300
50
13C
206
3/0
1
Tram
25
Than 14.340
300
150
375
276
Figure 8: Mean cumulative reward over all 320 configurations (32 hyper parameter combinations x 10 random seeds). Shaded area is + standard deviation. Data points are average over a sliding window of size 6. The length of an episode is limited to 200 steps.
23

---

480
240
Haftheeshh 1.5,
me/0 6.5
bondukers C.0 2.6)
1290
-75
27
-150
Figure 9: Mean cumulative reward of the best hyper parameter configuration over 10 random seeds. Shaded area is + standard deviation. Data points are average over sliding window of size 6. The length of an episode is limited to 200 steps.
WalkerD (3.0, 1.
HAserr 1.0
Humassalf
23e
20
380
280
120
360
150
136
118
20
-2400
-20
Terking 2111
Figure 10: Mean cumulative reward over all 320 configurations (32 hyper parameter combinations x 10 random seeds). Shaded area is + standard deviation. Data points are average over a sliding window of size 6. The length of an episode is limited to 200 steps.
CONSTANT
holtchuttat-133 1.35.25 25)
Ant 0011011.00 0.11
530
Ast (0.25, 3.25)
714
Mumano di 10.. 0.11
Samania (0.25,
830
400
606
591
350
435
330
206
Tuparoo www.. Octan)
Trae 23 Nine 103-0
Figure 11: Comparison of CAQL-MIP with or without dynamic optimality gap on the mean return over 10 random seeds. Shaded area is + standard deviation. Data points are average over a sliding window of size 6. The length of an episode is limited to 200 steps.
24

---

GUING
0.5
200
200
100
160
3.9
HarCherah 1d
Tenduken 2.00
300
Dun
1450
15.0
Thaing
Mean cumulative reward of the best hyper parameter configuration over 10 random seeds. Shaded area is + standard deviation. Data points are average over a sliding window size 6. The length of an episode is limited to 200 steps.
Figure 12:
Env. [Action range]
81 CAQL-GA
Hinge CAQL-GA
Pendulum (-2,2)
2244488 = 497.467
233.307 476,410
Hopper [1
253.459
158.578
130,846 + 92.298
Walker2D [].
207.916
100.069
173.160
= 106.138
HalfCheetah [-1,
628.440 +: 234.809
532.160
+ 192.558
Ant [O.5,,051
256.804
90.335
199.667
84.116
Humanosi [4.4,
443.733
223.356
297.197 1. 151.333
Table 10: The mean + standard deviation of (95-percentile) final returns over all 320 configura- tions (32 hyper parameter combinations x 10 random seeds). The full training curves are given in
Figure 2
25


Reviews:
[{"review_id": "S1lSZ2z0FH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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: \nThis paper targets the maximization issue in continuous value based methods, especially Q Learning. The idea is to use Mixed Integer Programming (MIP) to solve the Q maximization step by formulating the neural network structure of the Q function as a constrained mixed integer program. Further improvements are made by approximating the MIP solution in order to make training/inference faster. The method is tested on tasks from the Mujoco domain and compared with other value based methods for continuous control. I found the paper simple to follow and well structured. The problem is well motivated too and the empirical analysis is quite rigorous.    \n\nThe obvious concerns are regarding scalability of the method; both in terms of 1) using other forms of neural network components (ex. Other activation functions, Convolutional networks in the case of vision based problems such as robotic manipulation) and 2) problems that are inherently less sample efficient, i.e. cases where shortening the sampling horizon is not a feasible option for learning meaningful policies. \n\nOverall, I feel the positive aspects more or less outweigh the drawbacks and therefore my vote is for a weak accept.\n\n\nComments/Questions: \n- Table 8 description says hyper-parameter sweeps were done for temperature and exploration noise decay values but the table is missing their values.\n- What happens when action range is increased from default? One of the reasons mentioned for constraining the action space is to validate how well policy-based methods work. To really take this point home, I feel it might be good to check with an increased action range.\n- Controlling w.r.t symmetry of the env (esp. in Mujoco domains), thus reducing the number of actions by half, might help faster MIP computation times. \n- Figure 3 x-axis runs till different values, but the description says training steps are 1000. How long are the experiments run for?\n- Can the authors elaborate on why the episode length is decreased from 1000 to 200?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "H1lX6OD6Kr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 novel value-based continuous control algorithm by formulating the problem as mixed-integer programming. With this formulation, the optimal action (corresponding to the maximum action value) can be found by solving the optimization problem at each time step. To reduce the time complexity of the optimization, the author proposes several variants to approximately solve the problem. Results on robotics control are presented. The proposed looks interesting and could be useful in practice. \n\n1. Section 4 of the paper can be improved. Although the author proposes several methods for approximating the optimal solution, it is unclear what message the author wants to convey. How to decide which approximation to use? Is there any situation where one of the approximations should be preferred? \n\n2. In the experiments, the standard deviation is very large, so it is hard to claim the proposed method is better.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers gave scores of Weak Accept. AC has read the reviews and rebuttal and agrees that the paper makes a solid contribution and should be accepted.
Decision: Accept (Poster)