Accelerating Quadratic Optimization with Reinforcement Learning
Authors: Jeffrey Ichnowski
Paras Jain
Bartolomeo Stellato
Goran Banjac
Michael Luo
Francesco Borrelli
Joseph E. Gonzalez
Ion Stoica
Ken Goldberg
Venue: NeurIPS 2021 Poster (2021)
Keywords: quadratic optimization
convex optimization
first-order methods
reinforcement learning for optimization

Abstract: First-order methods for quadratic optimization such as OSQP are widely used for large-scale machine learning and embedded optimal control, where many related problems must be rapidly solved. These methods face two persistent challenges: manual hyperparameter tuning and convergence time to high-accuracy solutions. To address these, we explore how Reinforcement Learning (RL) can learn a policy to tune parameters to accelerate convergence. In experiments with well-known QP benchmarks we find that our RL policy, RLQP, significantly outperforms state-of-the-art QP solvers by up to 3x. RLQP generalizes surprisingly well to previously unseen problems with varying dimension and structure from different applications, including the QPLIB, Netlib LP and Maros-M{\'e}sz{\'a}ros problems. Code, models, and videos are available at https://berkeleyautomation.github.io/rlqp/.

Accelerating Quadratic Optimization with Reinforcement Learning
Jeffrey Ichnowski*) Paras Jain 1 Bartolomeo Stellato', Goran Banjac', Michael Luo', Francesco Borrelli' Joseph E. Gonzalez', Ion Stoica', and Ken Goldberg' University of Califormia, Berkeley, Princetoon University, 'ETH Zürich Correspondence to: {jeffi, *qqal contribution
Abstract
First-order methods for quadratic optimization such as OSQP are widely used for large-scale machine learning and embedded optimal control, where many related problems must be rapidly solved. These methods face two persistent challenges: manual hyperparameter tuning and convergence time high-accuracy solutions. To address these, we explore how Reinforcement Learning (RL) can learn policy to tune parameters accelerate convergence. In experiments with well-known QP benchmarks we find that our RL policy. RLQP, significantly outperforms of the-art QP solvers by up to 3x. RI.QP generalizes surprisingly well to previously unseen problems with varying dimension and structure from different applications, including the QPLIB, Netlib I.P and Maros-Mészáros problems. Code, models, and videos are available at https: hutpp:://brrkeeeeytttoottttt
gi thub. io/rlqp/
Introduction
Solving quadratic programs (QPs) efficiently is critical to applications finance, robotic control and operations research. While state-of-ther -het-artt interior-point methods scale poorly with problem dimensions, first-order methods for solving QPs typically require thousands of iterations. Moreover, real-time control applications have tight latency constraints for solvers 333. Therefore, it is important to develop efficient heuristics to solve QPs in fewer iterations.
The Alternating Direction Method of Multipliers (ADMM) 6
15
18 is an efficient first-order
optimization algorithm, and the basis for the widely used and state-of-lt the art Operator-Splitting QP (OSQP) solver [44). ADMM performs linear solve matrix based on the optimality conditions of the QP to generate a step direction, and then projects the step onto the constraint bounds.
While state-of-the-arr, the ADMM algorithm has numerous hyperparameters that must be tuned with heuristics regularize and control optimization. Most importantly, the step size parameter p has considerable impact on the convergence rate. However, is still unclear how to select before attempting the QP solution. While some theoretical works compute the optimal p [7], they rely on solving semidefinite optimization problems which are much harder than solving the QP itself. Alternatively, some heuristics introduce "feedhack" by adapting p throughout optimization order to balance primal and dual residuals 44 (22
We propose RLQP (see Fig. D. an accelerated QP solver based on OSQP that uses reinforcement learning (RL) to adapt the internal parameters of the ADMM algorithm between iterations to minimize solve times. An RL algorithm learns policy πe - A. parameterized by (e.g., the weights of neural network), that maps states in set S to actions in set A such that the selected action maximizes the accumulated reward To train the policy for RLQP, we define S be the internal state of the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Agent
policy (-)
QP A,g.A,
Environment (QP solver)
Scalar adapt-p policy:
h
p t Tacalar (8)
state
action adapt p
KKT matrix
ADMM iterations
hm
Vector adapt-p policy:
parameters 0
state x,, V/
TT((.))
p - (vee(s)
reward
7 pp(5m))
state f(x, y, 2; u,
Figure 1: RLQP uses deep reinforcement learning (RL) to compute a policy that adapts the internal parameters of first-order quadratic program (QP) solver speed up the solver's s convergence rate. In standard RL formulation, policy computes an action based on its observation of the state of the environment, and taking the action results change in state and reward. In RLQP, the policy is parameterized by neural network, the state is function of the solver's ' internal state parameterized by the QP, the action changes parameter (p) the solver, and the reward minimizes QP solve time. RLQP proposes 2 formulations of RL and associated policy: scalar and vector.
QP solver (e.g., the constraint bounds, the primal and dual estimates), A to be the adaptation to the internal parameter (p) vector, and r to minimize the number of ADMM iterations taken.
RLQP's policy can be trained either jointly across general classes QPs or with respect to a specific class. The general version of RLQP is trained once a broad class of QPs and can be used out-of- the-box on new problems. The specialized version of RLQP is trained on a specific class problems that the solver will repeatedly encounter. While this requires additional setup and training time, it is useful when QPs will be repeatedly solved in application (e.g.. in a 100 Hz. control loop).
In experiments, we train RLQP on of randomized QPs, and compare convergence rates of RLQP to non-adaptive and heuristic adaptive policies. To compare generalization and specialization, we investigate RLQP's performance in the settings where 1) the train and test sets of QPs come from the same class of problems, 2) the train set contains problems from a superset classes contained the test set, 3) the train set contains subset, and 4) when the train and test sets are from distinct classes. In the results section we show that RLQP outperforms OSQP by up to 3x.
The contributions of this paper are:
Two RL formulations train policies that provide coarse (scalar) and fine (vector) grain updates to the internal parameters of a QP solver for faster convergence times
Policies trained jointly across QP problem classes to specialize to specific classes
Experimental results showing that RLQP reduces convergence times by up to 3x and generalizes to different problem classes and outperform existing methods
2 Related Work
This work touches a number of related research areas, including convex optimization, ML-accelerated optimization, learning in -rrrr methods and RL. We summarize related work in Table
Convex optimization Many researchers have proposed algorithms for quadratic programs, which generally fall into three classes: active set [47] interior point (37], and first-order methods. Of the
active set and interior point solvers, perhaps the most well- are Gurobi (2) and MOSEK (36..
Active-set solvers operate by iteratively adapting an active set of constraints based on the cost function gradient and dual variables [39]. Interior-point solvers iteratively introduce and vary barrier functions to represent constraints and solve unconstrained convex problems. We instead base this work on a first-order method solver, OSQP [44] One of the advantages of OSQP over interior points solvers, is that it can readily be warm started from a near-by solution, as is common in many applications such solving a sequential quadratic program [1] and solving QPs for model- control.
aL-accllerated combinatorial optimization Accelerating combinatorial optimization problems with deep learning has been explored with wide application 5] including branch-and- aanch-and-bound for

---

Accelerare specialized 1 problems
Scalable arbitrary # of dims.
Generalize novel problems
Continuous space
Guaranteed convergence
Domain agnostic
Khalil
Dai et al. 9
X
Li and Malik 28
Metz al. [3
X
V
/
Wei et al. 46
X
RLQP
Table Summary of related work. RLQP meets all objectives while demonstrating state-of-the-art performance on challenging optimization problem sets.
mixed-integer linear programming 27 graph algorithms 9 and boolean satisfiability problems (SAT) 77.. Many combinatorial optimization problems have exponential search spaces and NP-hard in general setting. However, learning-augnn augmented combinatorial algorithms utilize very different methods RLQP combinatorial problems have discrete search spaces.
Learning in first-order methods Accelerating first-order methods with machine learning has gained considerable recent interest. Li and Malik [28] demonstrate a learned optimization algorithm outperforms common first-order methods for several convex problems and a small non-convex problem. Metz et al. [34] show learned policy outperforms first-order methods when optimizing neural networks, but finds that directly learning parameter update values can be sensitive to exploding gradient problems. We avoid this instability during optimization by learning a policy to adapt parameters of the ADMM algorithm. Wei al. [66 recently proposed an RL agent tune parameters for an ADMM-based inverse imaging solver.
Reinforcement Learning Overview Reinforcement learning (RL) algorithms include both on- policy algorithms, such as Proximal Policy Optimization 442. REINFORCE [45) and IMPALA [I],
and off-policy algorithms, such as DON (35 and Soft Actor Critic [21] RLQP extends the off-
policy Twin-Delayed DDPG (TD3) [3] actor-critic framework with exploration policy for continuous action spaces that extends Deep Deterministic Policy Gradient (DDPG) algorithm [29 while addressing approximation errors. Furthermore, in formulation of RLQP, train shared policy for multiple agents following an RL approach proposed by Huang et al. (23]. With this single policy, RLQP updates multiple parameters using state associated with each constraint of QP.
Background
In this section, we summarize QPs, the OSQP solver, and an MDP formalization.
3.1 Quadratic Programs
quadratic program with variables and constraints takes the form:
minimize (1/2)x² Px q" subject 15 Ar < u
where x: E IR" is the optimization variable, P that defines the quadratic cost, E R² defines the linear cost, A is an m x n matrix that defines the linear constraints, and u R. the constraint's 's lower and upper bounds. Here, S is an element-wise less-than-or-equal-e operator. In this form, to specify an equality constraint, the lower and upper bounds are set the same value, and specify a constraint unbounded from one side, sufficiently large value (or #oo) is specified for the other side.
symmetric positive semi-definite matrix
3.2 First-Order QP Solver Algorithm
The solver we speed up is OSQP, which uses first-order ADMM method to solve QPs. We summarize OSQP here. Given QP, OSQP first forms a KKT matrix (below), then iteratively refines
solution from initialization point for vectors (0)) R", (0) nM, and 20)) m where the

---

superscript in parenthesis refers to the iteration. Each iteration computes the values for the k + 1 iterates by solving following linear system (e.g., with an LDL" solver):
P + ol AT
x((+11
oz((k)
(1)
diag(p)
22()) - diag(p) -1 -1))))
KKT
and then performing the following updates:
g(k+1) + 2kk) + (ang(p))~(((ttt) (()
(b+1)) + [(. (z(k+1) + diag(p) -
(k+1) + (M)) + diag(p) (=(k++1) =
where R+ and p R regularization and step-size parameters, and H[ R R projects its argument on the constraint bounds. We use the notation diag: IR" - S" to denote the operator that maps vector diagonal matrix. We define the primal and the dual residual vectors as
(k) Sprimal
Ax (k)) and <(t)
(x) +
A"
When the primal and dual residual vectors are small enough in norm after iterations, x (k++) and 1(+++) are primal and dual (approximate) solutions to the QP.
Internally, OSQP has a single scalar that uses to form according to the following formula:
h1
where h, {1 if j ue (inequality constraints)
p p
1003
if de (equality constraints),
hmm
where the subscript denotes the i-th coefficient of h, and the bounds I and u.
Periodically, between ADMM iterations, OSQP will adapt the value of p. The existing hand- crafted formula for adapting p attempts to balance between primal and dual residuals, by setting g(k=1) 1) ((k) /llSprimal be/ /llalull Empirically, adapting p between iterations speed up the convergence rate.
3.3 Multi-Agent Single-Policy MDP
In a Markov Decision Process (MDP), an agent can be in any state s E S, take an action a E A. and with the transition dynamics function, T( s, s,a), transitions from state s to state s' after taking action a. The agent receives a reward R: S x A + R for transitioning from to s' by taking action a. Given a tuple (S, A, R, 7), the MDP optimization objective to find a policy To :S + A, parameterized by 0, that maximizes the expected cumulative reward E 1 7'r"), where r is the reward at time and 7 E [0, 1) a discount factor.
We also formulate a multi-agent single-policy MDP setting in which m agents collaborate in shared environment in state Senv Senv. At each time step, each collaborating agent (CA) has its own state E Sea. action E Aca. and observations o, E O, but, for computation feasibility, share a single policy To Sea -> Aca- State transitions for the environment and all m agents occur simultaneously according to a state transition function T Seny S x Am + Sanv X Sca and result in single shared reward R Senv S x A + and discount factor. The objective is to find single shared policy Ne that maximizes the expected cumulative reward. This can be thought of as special case of a multi-agent MDP 31 or Markov game (30 and we adapt a formulation from Huang et 23
Method
The goal of RLQP is to learn policy to adapt the Im vector used in the ADMM update in (1)
(see Fig. []. As the dimensions of this vector vary between QPs, we propose two methods that can
handle the variation in The first method leams policy to adapt scalar á and then applies (
to populate the coefficients of the p vector. The second method learns policy to adapt individual coefficients of the p vector.

---

Algorithm/ TD3 for P (scalar)
Algorithm 2 TD3 for (vector)
I: Input: exploration noise a, buffer size rs
1: Input: exploration noise a, buffer size re
2: q, Q + initialize policy and critic (see TD3)
π. Q < initialize policy and critic (see TD3)
3: D 4-ree --replay buffer w/ rs
D replay buffer w/ ravg no. of constraints)
4: env, s(0) - new QP, state
env, ( m new QP, state, no, of constraints for i E [0, ........ T) do
5: fort {O....,' T do
6: p(o) + --((s +e, e o)
p (t) T(s + e ((0,o) Vi E [] m]
7: s(t=1), ,((t) done (t) sttep(env, ,())
s g(++1) ,r(() done + step(env, s ())
8: store (s , ,(t) ( in D
store (D, s (1) (4) ,r(t), s((t)) vi E [1 ml
9: done())) then
if done (t) then
10: env, ((t) + new QP, state
10: env,s"" m + new QP, state, no, of constr.
update π and Q using data sampled from D
II: update and Q using data sampled from D
Since both the number of variables and the number of constraints can vary from problem to problem, and the same QP can be written in (n! m!) permutations, we propose learning policies that problem size and permutation invariant. To do this, we provide permutation-invariinn fixed-size state of the QP solver to either policy.
4.1 RL Policy for Scalar Adaptation
To speed up convergence of OSQP, we hypothesize that RL can learn a scalar 5 adaptation policy (Tacalar) that can perform as-well-as or better than the current handcrafted policy (The) of OSQP. The handcrafted policy in OSQP periodically adapts by computing a single scalar p, then sets the coefficients of p based on the value of p. In both handcrafted and RL cases, the policy a function π: S. + Ap, where S3 E IR2 are the norms of the primal and dual residuals stacked into vector, Ap the value to set to p. One advantage of this approach is that simple heuristic can check that the proposed change to P is sufficiently small and leave the KKT matrix unchanged to avoid costly matrix factorization.
To compute this policy, т, we use Twin-Delayed DDPG TD3 13 an extension of deep-deterministic policy gradients (DDPG) [29]. as the action space is continuous. We summarize TD3 in Alg. [ TD3 learns the parameters 0 of a policy Tacalar network and critic Q network, where Tscalar determines r(s, a)) +3 (T( [=xx (s', . (<s')) is the expected reward for given state-action pair following the recursive Bellman equation. TD3 updates Q₂ by minimizing the loss on the Bellman equation, and updates the policy network using policy gradient 45] of the objective
the action to take and Qr (s,
J(0) EEnDDR Tscalar (s))
that is,
VeJ = BB V scalar (s) (l
where D is the discounted state visitation distribution TD3 in the algorithms, including: Q is composed of two networks, the minimum value of the two networks estimates the reward, exploration noise is clamped, and Tscalar updates are staggered.
43 For brevity, we leave out some details of
In RLQP, the "eevvirnment" env is an instance of a randomized QP problem, and a call to step() applies a change ý (and thus via (2) to p), advances a QP fixed number of ADMM iterations, and returns the updated internal state 8, a reward r, and a termination flag done. In this case, the internal state s is a vector containing the current norms of the primal and dual residuals of the QP. The reward r is -1 if not done, and 0 if the QP is solved.
We train with randomized QPs across various problem classes (Sec. 5) that have solutions guaranteed by construction. To ensure progress, we set a step limit (not shown in the algorithm) since bad actions can cause the solver to fail to converge in timely manner. During training, also always adapt p in each step and ignore the heuristic adapt/no-adas adapt policy.
For well-scaled QPs, the residuals and p can reasonably range between 10-6 and 105, Since this can cause issues with training the policy networks, we train the policy network with logs of the residuals, and exponentiate the network's 's output get the action to apply.
5

---

4.2 RL Policy for Vector Coefficient Adaptation
For some classes of QPs, the solver can further speed up convergence by adapting all coefficients of the vector p. instead of applying (2) to scalar p. Conceptually, this could be accomplished with policy vver : Sqr + Avec. where Sop E go(n+mm is the internal state of the solver and Avec R is the new value for p. However, due to variation in problem size and permutation, we instead propose simplification in which Teec is formulated as policy `p : Sp + Ap that is applied per coefficient of p. Here, S, E IR is state corresponding to single coefficient in p. and Ap IR is the value to set for that coefficient.
To define Sp. we observe that coefficients in are one-to-one with coefficients in y, 2, I, u, and Az. We observe that constraint bounds are likely to have an impact on an ADMM iteration when coefficients of are "close" to their bounds in I or A coefficient in is also "close" to solution when is nearly equal to the corresponding coefficient in Az. Finally, to include a permutation- invariant signal on the overall convergence, we borrow the idea of max- max-looning inputs from graph neural networks [40] 3 and include the infinity norms of the primal and dual residuals of the QP
solver. We thus define coefficient's s state as:
min(2; 2 4, uh
2i)
2; (Ax);
Vi
E Sp.
Pi
I| ISprimaillos [Edual
In practice, we clamp values in each state 8; to reasonable ranges (e.g., [10-8, 810-8,10 108) [-106, 10%) [-106, 10%), [10-6, 10%) |10-6 10%) [10-6, 10 for the coefficients of 8t, in order). Empirically, training is more efficient if the policy operates on states with the log of the first and last 3 coefficients.
Since each step in the vector formulation applies m actions and updates m states simultaneously, we adapt the multi-agent single-policy TD3 formulation from Huang et al. [23], and show it in Alg. 2 next to Alg. with the main differences highlighted in blue. Before each step, step applies the policy with exploration noise to generate m actions corresponding to m coefficient updates to p. After each step. Alg. addds the tuples to the replay buffer with each tuple consisting of coefficient-spect states and actions, along with the single shared reward for the step. Since each step results in m tuples added to the replay buffer, Alg. 2 allocates replay buffer large enough to hold the average number of tuples expected to be in the individual QPs in the training set.
The hypothesis of this approach is that the some coefficients, and thus policy actions for coefficients, will have more of an effect on convergence, and thus the reward, than others. When the domain for the policy function has more of effect, the range of the actions will have lower variance. Similarly, when the policy values have less effect, the variance will be higher. This suggests that when training the policy network in this case, having a lower learning rate, and higher batch size can help. A lower learning rate will cause smaller gradient steps when training the network so that it does not overfit to some part of the high variance training data. A higher batch size will allow gradients average out in high variance training data so that the gradient step better matches the true mean of the data.
5 Experiments
To train and test the proposed methods, we modify OSQP to support direct querying and modification of its o vector, and integrate both गe and Vee policies for benchmarking, and runtime flag to switch between policies. We train the network using randomly generated QPs from OSQP's benchmark suite. The form of these QPs falls into classes (see below), but the specific coefficient values in the objective and constraints are generated from a audom-number generator. These QPs are also guaranteed to be feasible by construction (e.g.. by reverse engineering constraint values from pre-generated solution). To separate train and test sets, we ensure that each set is generated from uniquely seeded random-number generators. Training is performed in PyTorch with a Python wrapper around the modified OSQP which is written C/C++ During benchmarking, the solver performs runtime adaptation of p using PyTorch's C++ API on the already policy network. We train a small model to keep runtime network inference fast possible.

---

Gurobi OSQP
Shited Goonsrrie
REQP (scalar)
500
RLQP
400
100
Control
Huber
SVM
Lasso
Pontolio
Eq.
Randonn
All
090P
OSQP
RLOP (vee) cold
RLOP (vec)
001 9am uan
warm
Comparison of general adaptation policy applied to different classes. We train an RL policy using multiple classes, and show the performance per class, along with each class. The y-axis is the shifted geometric mean across problems within each class, and the value of is always assigned to the best in class. The right-most most All class is the aggregate of all classes to the left of it. Right: Comparison of warm-starting performance using OSQP's warm-start benchmark.
Figure 2: Left:
We evaluate all policies with 7 problem domains (referred as the "benchmark problem") ") defined in Appendix A of the paper on OSQP [4).. These policies cover control, Huber fitting, support-vector machines (SVM), Lasso regression, Portfolio optimization, equality constrained, and random QP domains. Alongside RIQQP, we benchmark the unmodified OSQP solver to evaluate how the RI. policy improves convergence. For both RLQP and OSQP, we evaluate to the high-accuracy settings (10-5) of the OSQP benchmarks. While our focus is on improving the first-order method in OSQP with an RL policy, we include some benchmarks against the state-of-the-arr commercial Gurobi solver [00 (using default settings) as it may be of interest to practitioner.
We consider three evaluation configurations: (1) multi-task policy learning in which we train single RLQP policy on suite of random benchmark problems and test it across all problems, (2) class-specific policy learning in which we train and test the policy for single problem domain and (3) zero-shot generalization where we test a general policy on novel unseen problem class.
We evaluate speedups with the shifted geometric mean 19 problems have wide variations in runtime across several orders of magnitude. This metric is the standard benchmark used by optimization community. The shifted geometric mean computed as:
exp (1/N) log(max(1, u + s)) -
where u; compute time in seconds, 10, and N is the number of values (e.g., QPs solved).
We also evaluate on QPLIB [14], Netlib [16], and Maros and Mészáros 32 as they are well- established benchmark problems in the optimization community.
In all experiments, the policy network architecture has fully-connected hidden layers of 48 with ReLU activations between the input and output layers. The input layer is normalized, and the output activation is Tanh. The critic network architectures use the identity function as the output activation, but otherwise matches the policy. As small networks for fast CPU inferences are desirable here, we attempted to keep the network as small as possible. We performed minimal experimentation before settling this architecture- finding that smaller networks fail to converge during training.
We trained on system with 256 GiB RAM, two Intel Xeon E5-2650 v4 CPUs 2.20 GHz for total of 24 cores (48 hyperthreads), and five NVIDIA Tesla V100s. We ran benchmarks on a system with Intel 19 8-core CPU 2.4 GHz and without GPU acceleration.
5.1 Multi-task/Genentt RLQP Policy
We train a general policy on broad set of problem classes and compare solve times with different classes. During training, sample of seven QP domains from benchmark problem. From that sampled problem domain, we generate a random problem.
In Fig. 2 we compare the shifted geometric mean of solving 10 problems of 20 different dimension, for total of 200 runs per class per solver. The problem dimensions for Control, Huber, SVM, Lasso (10, 11, 12, 13, 14, 16, 17, 20, 23, 26. 31, 37, 45, 55, 68, 84, 105, 132, 166, 209); for Random

---

10a
Solve Time (seconds)
10a
100
Gurobi OSQP
10
RIQP((calla)) RLQP(vector)
10 10-2
500
1000
1500
2000
Problem Dimension
Figure 3: Solve time with increasing dimension the Random QP problem set. We train and benchmark two vector RL adaptation policies: (dashed) on problems ranging from dimension 10 to 50, and (solid) on problems ranging from 10 to 2000. The gray box shows the range of the training data for the dashed line. When the benchmark run is in the same problem-dimension distribution as the training data, the relative performance between solvers is consistent, however, when the problem dimension is outside of he training distribution, the performance diverges.
and Eq are (10, 11, 12, 13, 15, 18, 23, 29, 53, 73, 103, 146, 211, 304, 442, 644, 940, 1373, 2009), and for Portfolio are (5, 6, 7, 8, 9, 10, 12, 14, 16, 20, 24, 28, 35, 43, 52, 65, 80, 99, 124, 154). From the results, we observe that both RLQP adaptation policies typically improve upon convergence rate from the handcrafted policy in OSQP, and some cases, e.g. Portfolio optimization, by up to 3x.
5.2 Problem Dimension Scaling
To test how trained policy scales higher dimensions, train a policy low dimensional problems (10 to 50), and solve problems with varying dimensions, including dimensions higher than the training (up to 2000). For comparison, also include a policy trained on the full dimension range (10 to 2000). From the results plotted in Fig. 3 we observe that a policy trained on lower dimensional training set, can show improvement beyond its training range. However, the problem size diverges more from the training set, its performance suffers and it eventually loses to the handcrafted policy. Both low-dimensional and full-dimension range polices, were trained using the same network architecture, we hypothesize that this behavior is a function of the training data and not a limitation of the network expressiveness. While this is disadvantage of using smaller problems for training, in practice it may be outweighed by the advantage in training time as each RL step requires O(n m) compute time.
5.3 Training Class-Specific Policy
Many applications in control (25 and optimization 226 require QPs from the same class to be repeatedly solved. To test if training a policy specific to a QP class can outperform a policy trained on the benchmark suite, train policies specific to the problems generated by the trust- region 8 based solver for sequential quadratic program (SQP) from a grasp-optimized motion planner (GOMP) 25 24 for robots. With these problems, RLQP trained
the benchmarks converges more slowly than the handcrafted policy included in OSQP. With a vector policy trained on the the QPs from the SQP, the shifted geometric mean of OSQP is 1.37. This result suggests that while general policy may work for multiple problem classes, there are cases in which it is beneficial to train a policy specific a problem class, particularly if the QPs from that problem class are repeatedly solved.
5.4 Warm Starting QPs
One benefit of first-order method such as OSQP is their ability to warm start-that is, rapidly converge from a good initial guess. We test if RLQP retains benefit of warm start on OSQP's warm-ste startt benchmark and show the results in Fig. 2 (right). As warm starts require fewer iterations, and thus

---

RLQP
RLQP
Inst.
71
W/1
zeros
OSQP
(scalar)
(vector)
8845
1546
777
10999
6.386
timeout
5,435
9002
2890
1649
12580
6,000
timeout
timeout
8906
5223
838
20781
1.108
1.447
0.741
8559
10000
5000
24998
59.648
205.372
24.083
8938
4001
11999
31997
timeout
timcout
0.991
8567
10000
7500
32497
98.511
284.112
22.222
8616
13870
10404
41610
0.126
0.113
0.141
8515
16002
8002
56005
0.105
timcout
timcout
8785
10399
11362
63023
6,334
timeout
2.972
8495
27543
8000
73029
1.612
0.742
1.174
8602
34552
52983
242887
99.872
timeout
55.629
8547
1003001
1001000
6003001
timcout
timcout
timcout
Table QPLIB problems. Timing results for solving the convex continuous QPs with constraints from QPLIB [14]. The Inst. column is QPLIB's instance number. The columns (number of variables), m (number of constraints), and non-zeros indicate the QP's complexity. A timeout result indicates the solver terminated due reaching an iteration or time limit (300 s). We hypothesize that the RLQP timeouts are due to out distribution test problems, as the policy here was trained on benchmark classes.
fewer adaptations than cold starts, we expect RLQP to show smaller improvement here. In the plot, we can see that RLQP retains the benefit of warm starting, and also gains a improvement over OSQP.
5.5 QPLIB
We benchmark convex continuous QP instances with constraints from QPLIB [4], and show the results in Table 2 Since there are only few such QPLIB instances and they come from varying classes, creating a train/test split is problematic. We thus use the general policy trained on the benchmark classes. From the table, we observe that the general RLQP policy beats OSQP's heuristic policy in all but three cases. In two cases RLQP fails due to reaching an iteration or time limit. Training similar problems should help avoid timeout.
5.6 Netlib Linear Programming benchmark
The Netlib Linear Programming benchmark [16] contains 98 challenging real-world problems includ- ing supply-chain optimization, scheduling and control problems. As with the QPLIB benchmark, we evaluate results with a general policy trained on the benchmark classes. We solve problems many of these benchmarks poorly scaled. Overall, vector formulation of RLQP is 1.30x faster than OSQP by the scaled geomean of runtimes. We include problem-specific breakdown in the supplementary materials.
to high-accuracy
5.7 Maros and Mészáros
manner similar to the QPLIB problems, we also benchmark on Maros and Mészáros repository of QPs. [32] This collection of 138 QP problems, includes many poorly scaled problems that cause OSQP to fail to converge. We compute the shifted geometric mean for problems solved by both OSQP and RLQP with the general vector policy. RLQP converges faster, with OSQP's shifted geometric mean 1.829 times that of RLQP. Because the dataset contains 138 problems, a table of the full results is included in the Supplementary Material.
5.8 Learned Policy Analysis
We plot and evaluate learned policy in Fig. From the plot, we see that when approaches either bound, the output p increases. We also observe that with higher y, the policy outputs higher Both of these observations are consistent with the intent and observations behind OSQP's heuristic policy: a high is desirable when the primal residual is smaller than the dual, and low is desirable

---

Model evaluated with varying and y, and with fixed:
10
10
103
(k+11
=
(k) = 0.1
10
1: 10
ui = 10
0
5
10
Figure 4: Trained model for general vector policy, evaluated with varying and y, and fixed Ax, p Ji, ug. As approaches either bound and with increasing the policy outputs higher p.
when the dual is smaller than the primal. However, the learned policy is not simple square root of residuals like OSQP. The results suggest that the optimal policy is non-linear and problem specific.
Limitations
RLQP has limitations. For QPs that converge after few iterations, and thus do not adapt p. having better adaptation policy is moot. Training RLQP can take a prohibitively long time and require a large replay buffer for some applications, for example, to train the benchmark suite of QPs required several days on a high-end computer with 256 Ghi-this may be mitigated to an extent by sharing learned policies between interested practitioners. The time it takes to evaluate the RL policy, especially the vector version, may reduce the performance benefit of faster convergence thirs may be mitigated by learning more efficient representations, or by using dedicated netwolk processing hardware.
Conclusion
We presented RLQP, a method for using reinforcement learning (RL) to speed up the convergence rate of first-order method quadratic program solver. RIQQ uses RI. to learn a policy to adapt the internal parameters of the solver allow for fewer iterations and faster convergence. In experiments, we trained a generic policy and results suggest that a single policy can improve convergence rates for broad class of problems. Results for problem-specific policy suggest that fine-tuning can further accelerate convergence rates.
In future work, we will explore whether additional RL policy options can speed up convergence rate further, such as training hierarchical policy [ in which the higher-level policy determines the interval between adaptation, performing a neural-archiecctree search [10], using meta-learning [12] 38 to speed up problem-specific training, and online-learning to adjust the policy at runtime adapt to changing problems. Furthermore, we will investigate how to analyze the learned policies (e.g.,
Fig. 4 to devise new optimization algorithms with analytical step-size updates and faster theoretical convergence rates.
Acknowledgements
This research was performed at the AUTOLAB at UC Berkeley in affiliation with the Berkeley AI Research (BAIR) Lab, and the CITRIS "People and Robots" (CPAR) Initiative. In addition to NSF CISE Expeditions Award CCF-1730628, this research is supported by gifts from Amazon Web Services, Ant Group, Ericsson, Facebook, Futurewei, Google, Intel, Microsoft, Nvidia, Scotiabank, Splunk and VMware. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors. We thank Ashwin Balakrishna, Arnav Gulati as well as other colleagues for their helpful feedback.
10

---

References
[1] Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Eilen Vitereik. Learning to branch. In International conference on machine learning, pages 344-353. PMLR, 2018.
[2] Andrew G Barto and Sridhar Mahadevan. Recent advances in hierarchical reinforcement learning. Discrele event dynamic systems, 13(1):41-77,2000 2003.
[3] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1rXiv:1886.01221, 2018.
[4] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' d'horizon. European Journal of Operational Research, 2020.
[5] Dimitris Bertsimas and Bartolomeo Stellato. The voice of optimization. Machine Learning, pages 1-29, 2020.
[6] Stephen Boyd, Neal Parikh, and Eric Chu. Distributed optimization and statistical learning via the alternating direction method of multipliers. Now Publishers Inc, 2011.
[7] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In Conference on Neural Information Processing Systems (NeurIPS). 2018.
[8] Andrew R Conn, Nicholas IM Gould, and Philippe L Toint.. Trust region methods. SIAM, 2000.
[9] Hanjun Dai, Elias B Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Conference on Neural Information Processing Systems (NeurIPS), 2017. (arXiv preprint arXiv:1704.0I6 01665..
[10] Thomas Elsken, Jan Hendrik Metzen, Frank Hutter, et al. Neural architecture search: A survey.
J. Mach. Learn. Res., 20(55):1-21, 2019.
[11] Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures, 2018.
[12] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In International Conference on Machine Learning, pages 1126-1 135. PMLR, 2017.
[13] Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In International Conference on Machine Learning, pages 1587-1596. PMLR, 2018
[14] Fabio Furini al. QPLIB: A library of quadratic programming instances. Mathematical Programming Computation, 2018. doi: 10.0007/112332-008-0014444 URL https://doi org/10. 10.
[15) Daniel Gabay and Bertrand Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers & mathematics with applications, 2(1):
17-40, 1976.
[16] David M Gay. Electronic mail distribution of linear programming test problems. 1985.
[17] Giselsson and S. Boyd. Linear convergence and metric selection for douglas-rachford splitting and ADMM. IEEE Transactions on Automatic Control, 62(2):532-544 2017. doi:
[18] Roland Glowinski and A Marroco. Sur l'approximation, par éléments finis d' d'ordre un, et la résolution, par pénalisation-dualit d' dnu classe de problèmes de dirichlet non linéaires. ESAIM: Mathematical Modelling and Numerical Analysis Modééissatinn Mathématique et Anal- yse Numérique, 9R2))411-7, 1975.

---

[19]
Nicholas Gould and Jennifer Scott. A note on performance profiles for benchmarking software. ACM Transactions on Mathematical Software (TOMS). 43(2):1-5, 2016.
[20] Gurobi Optimization, LLC. Gurobi optimizer. 2021-01-28.
https://wwx.guroohe com/
Accessed:
[21] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning, pages 1861-1870. PMLR, 2018.
[22] B. He, Yang, and S. L. Wang. Alternating Direction Method with Self-Adaptive Penalty Parameters for Monotone Variational Inequalities, Journal of Optimization Theory and Applica- tions, 106(2):337 356, August 2000. ISSN 1573-2878. doi: 10.1023/A11004403311444
URL
https://doi org 10.g/..../. 10. 1023:1:2334:: 1101::011100011100000511515155 10040035413000
[23] Wenlong Huang, Igor Mordatch, and Deepak Pathak. One policy control them all: Shared modular policies for agent-agnostic control. In International Conference on Machine Learning, pages 4455-4464. PMLR, 2020.
[24] Jeffrey Ichnowski, Yahav Avigal, Vishal Satish, and Ken Goldberg. Deep learning can accelerate grasp-optimized motion planning. Science Robotics, 5(48), 2020.
[25] Jeffrey Ichnowski. Michael Danielczuk, Jingyi Xu, Vishal Satish, and Ken Goldberg. GOMP: Grasp-optimized motion planning for bin picking. 2020 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2020.
[26] Paras Jain, Ajay Jain, Aniruddha Nrusimha, Amir Gholami, Pieter Abbeel, Joseph Gonzalez, Kurt Keutzer, and Ion Stoica. Checkmate: Breaking the memory wall with optimal tensor rematerialization. In Proceedings of Machine Learning and Systems 2020, pages 497-511. 2020.
[27] Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
[28] Ke Li and Jitendra Malik. Learning to optimize. In International Conference on Machine Learning, 2017. (arXiv preprint 1606v (085).
[29] 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 500.0097,, 2015.
[30] Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
[31] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-compettivve environments. In Conference on Neural Information Processing Systems (NeurIPS), 2017. (arXiv preprint Ttt::17006002775)
[32] Istvan Maros and Csaba Mészáros. A repository of convex quadratic programming problems. Optimization Methods and Sofware, 11(1-))6771-81) 1999.
[33] Jacob Mattingley and Stephen Boyd. CVXGEN: A code generator for embedded convex optimization. Optimization and Engineering, 13(1):1-27, 2012.
[34] Luke Metz, Niru Maheswaranathan, Jeremy Nixon, Daniel Freeman, and Jascha Sohl-Dickstein. Understanding and correcting pathologies in the training of learned optimizers. In International Conference on Machine Learning, pages 4556-4565. PMLR, 2019.
[35] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing Atari with deep reinforcement learning, 2013.
[36] MOSEK ApS. Mosek optimization toolbox. httpps//wwwt //ww: http:///www.o......m///m com/
Accessed: 2021-01-
28.
12

---

[37] Yurii Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in comvex programming. SIAM, 1994.
[38] Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv preprini 17X3:0/80000299 2018.
[39] Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
[40]
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
[41] John Schulman, Jonathan Ho, Alex Lee, Ibrahim Awwal, Henry Bradlow, and Pieter Abbeel. Finding locally optimal, collision-free trajectories with sequential convex optimization. In Robotics: science and systems, volume pages 1-10. Citeseer, 2013.
[42] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint vrXiv:1777006447 2017.
[43] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference on machine learning. pages 387-395. PMLR, 2014.
[44] B. Stellato, Banjac, P. Goulart, Bemporad, and S. Boyd. OSQP: an operator splitting solver for quadratic programs. Mathematical Programming Computation, 12(4):637-672, 2020. doi: URL http://///oo...//..../ /0w11000///220000-200
[45] Richard $ Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in neural information processing systems, pages 1057-1063, 2000.
[46] Kaixuan Wei, Angelica Aviles-Rivero, Jingwei Liang. Ying Fu, Carola-Bibiang Schöulieb, and Hua Huang. Tuning-free plug-and-ples and-play proximal algorithm for inverse imaging problems. In International Conference on Machine Learning, pages 10158-10169. PMLR, 2020.
[47] Philip Wolfe The simplex method for quadratic programming. Econometrica: Journal of the Econometric Society, pages 382-398, 1959.
13


Reviews:
[{"review_id": "OAQbKeIY_Lz", "reviewer": "Reviewer_THP1", "summary": "The authors use RL to tune the step size policy of OSQP, an ADMM-based solver for quadratic programming problems. They develop policies for both a scalar and a diagonal step size. Numerical tests are performed on the suite of benchmark instances used by the OSQP developers and external benchmark sets (QPLIB, Netlib, and Maros-Meszaros). The results show clear gains within specific problem classes and some evidence of generalization across problem classes.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Updated review: The authors have appropriately replied to my comments and seem to be making interesting progress on understanding the structure of the learned policy. I believe this paper will be useful for the optimization community, so I have changed my score from 5 to 7.** If the paper is accepted, or for future iterations, please be sure to focus on the clarity of the presentation (as other reviewers have noted) and not to overstate the significance of the comparison with Gurobi at moderate tolerances, as Gurobi's methods don't offer a trade-off between speed and solution quality (i.e., they probably take about the same time to solve to 1e-5 as they do to 1e-8). Finally, the ablation studies should show that all the components/features of the model are necessary, otherwise you should remove them in favor of a simpler model.\n\n--\n\nOverall, the paper provides a useful datapoint for the optimization community in terms of what parts of ADMM can be “learned”. On the other hand, this paper sits a bit outside the “learning to optimize” literature (e.g., as reviewed by https://arxiv.org/abs/2103.12828) in its application to OSQP and quadratic programming using RL. It would be interesting to have the authors’ thoughts on what makes application to OSQP/ADMM an easier or harder problem than the more common applications to unconstrained optimization. The significance of the paper, therefore, seems to be best judged by its direct impact for ADMM and quadratic programming, which is a somewhat narrow area for the NeurIPS audience. The improvements themselves are notable and promising. However, there’s quite a long road ahead for these improvements to be realized by practitioners, given, e.g., OSQP’s focus on embedded applications.\n\nAs is, I believe the paper is slightly below the bar for acceptance given some of my comments below on quality and presentation. The authors should be able to address most of these, in which case I would revise my recommendation upward.\n\nThe paper could be made much stronger, and a clear accept in my view, if the authors are able to derive some insight from the learned policies that could be distilled and translated into practice, perhaps without the need for an ML library as a runtime dependency. The dimensionality of the features used is quite low, which makes me think this could be possible, although clearly a stretch during the short period for discussion.\n\nI have not reviewed the RL methodology aspects, as they are outside my domain of expertise.\n\nComments:\n\n1. Can changing rho also be interpreted as dynamically rescaling the problem data? If so, consider discussing the connections with Adil et al. (https://arxiv.org/abs/2103.00736) and related work.\n\n2. In the supplement, the README refers to a train_benchmark_problems.sh script that doesn’t seem to exist.\n\n3. The convergence tolerances used in the experiments should be mentioned in the paper. How does the impact of the learned rho policies vary at higher and lower convergence tolerances?\nI found the comparison with Gurobi misleading without a discussion of how Gurobi solves to much higher precision than OSQP. Why are comparisons with Gurobi shown in Figure 2 and 3 but not in Table 1?\n\n4. The discussion of ML-accelerated combinatorial optimization in the related work seemed overly emphasized in comparison with the work on learning in first-order methods. Consider expanding the latter discussion to include the body of literature that applies gradient descent to meta-parameters by “unrolling” the iterations. See the recent review by Chen et al: https://arxiv.org/abs/2103.12828. \n\n5. The authors treat OSQP as a block box algorithm, and hence apply RL. Is it possible to extract derivatives to apply a gradient-descent type approach? The authors at https://arxiv.org/abs/2107.10254 discuss differentiating through SCS, which is very similar algorithmically to OSQP.\n\n6. Many aspects of OSQP were designed to be used in embedded systems, e.g., its lack of external dependencies. How could this RL-based approach, with its dependencies on ML libraries, ultimately be made available to users?\n\n7. There are a few scattered allusions (e.g. page 4 line 146) to the cost of refactorizing the linear system in equation (1). I believe this could use a full discussion. What does it mean for a change to rho to be sufficiently small to avoid a factorization? How often is rho actually changed in the numerical experiments? \n\n8. Given that the policy for scalar adaptation takes only two input features, can we plot it and derive some insight? In what parts of the space does it differ from the current policy? Can it be approximated by a simpler rule that could be used in embedded applications?\n\n9. I would like to see more ablation of the input features, as I think this would be useful for the community to gain insight into what is important for deciding rho. Section B in the appendix reports on a study (“Vector 1”) where the xi_primal and xi_dual residuals are dropped from the features. The method performs about as well as the others tested. Why are these features used then?\n\nMinor:\n\nPage 1 line 19: “ADMM performs a linear solve … and then projects the step onto the constraint bounds.” Clarify that this describes OSQP’s instantiation of ADMM in particular.\n\nPage 3 line 78: “Reinforcement learning overview” -> “Reinforcement learning”, for consistency with other section titles.\n\nPage 3 line 98: “OSQP [...] iteratively refines a solution”. As far as I’m aware, “iterative refinement” refers to a specific procedure for improving the accuracy of solutions to systems of linear equations, not to any iterative procedure like ADMM. I found the use of this term out of place. \n\nPage 4 line 112: Given that the residuals are key input features, consider defining them more formally.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I agree with the authors' evaluation that a discussion of the societal impact is not necessary given the algorithmic focus of the paper. In terms of other limitations, the authors should clarify the convergence tolerances used, and hence the quality of the solutions that the method can deliver.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "MEbAcZ6M3Wt", "reviewer": "Reviewer_nymS", "summary": "In this paper, the authors proposed a novel method to accelerate the QP  (quadratic programming) solving process using reinforcement learning. In their formulation, the state of the problem is the internal variables of the QP solver (in this case, OSQP's internal variables), the action space consists of the ADMM step size vector rho. Since the vector/matrix sizes of the QP can change between different problems, the authors used a multi-agent single-policy formulation, so each agent only observes the internal states that are relevant for a single coefficient in the step vector rho. The authors demonstrated that after training, their RLQP can converge faster for different classes of problems in the benchmark suite, especially if the problem is cold-started. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the method in this is novel, i.e. training a RL agent to help accelerate QP solving. The results are strong as well, the authors show that their general purpose agent can help the convergence of many classes of problems, and can scale to problem dimensions that are outside the training regime. The authors also compare their general framework with problem specific policies and note the cons and pros", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main limitations of the paper include:\n\n(1) The clarity of the writing. The authors proposed two variants for scalar and vector rho training. However, it is not straightforward to see how the state/action space changes between the two cases, and in which case a multi-agent training is adopted. Consider revising the method section.\n\n(2) Also, some paragraphs are hard to understand. For example the paragraph between lines 195-202 is difficult to parse. Consider revising.\n\n(3) Alternative architecture to solve the dimensionality problem. The multi-agent approach seems to completely decouple the states and actions inside the network.  However, it is possible that different internal states will affect each other. The authors can consider some alternative approach that entangles the inputs. For example, the PointNet is one such approach that can handle arbitrary numbers of points as inputs. Maybe it is possible to add shared and encoded states on top of individual states during training. \n\n(4) Benchmark on other real problems. I am curious about learning RLQP's performance on some robotic problems that involve QP solving. For example, the MIT Cheetah uses QP to solve their MPC problem. This can be a good real world example for comparison.\n", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "L10_EY5_e5Y", "reviewer": "Reviewer_cZUC", "summary": "The paper introduces a RL formulation and training pipeline to accelerate quadratic programming. The main idea is based on learning the multi-dimensional multiplier for ADMM. The paper shows some empirical performance gains over a number of setups.\n\n====== updated post rebuttal =====\n\nThanks the reviewers for the replies. Aggregating all information so far, I think the major weakness of the paper is the following:\n\nIt does not provide a clear reason why formulating the whole problem as a multi-agent Markov game is useful (I am not fully convinced by the rebuttal). The algorithm I can see is still essentially a single agent policy but with a specialized architecture.\n\nNow that after exchanging messages with the author a few times, I have understood how the detailed architecture works, and I am convinced about my point above. I would suggest that the authors present their architecture (such as mapping from R^6 to R^1) in a clear way, so as to make the architecture easier to understand. Also, I would like to see less stress on the Markov games, because it does not provide much gains -- once again, I'd like to frame it as a form of specialized architecture for single agent problem.\n\nThe paper is overall an application of RL to optimization problem. The gains are ok though the idea-wise contributions are not very novel (no extremely novel architecture or formulation).\n\nStill, overall I think the paper provides a solid contribution and I am willing to raise my eval to 6.", "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": "======= Originality =======\n\nThis work is another application of RL to accelerating optimization algorithms. I feel the paper is a bit lacking in terms of idea originality, because it seems that highly similar ideas have been explored in Wei et al, 2020, where they accelerate proximal algorithms using RL. \n\n======= Quality ========\n\nThe paper is relatively solid in terms of its experiment results.\n\n======= Clarity ========\n\nThe paper is clearly written and the logic flow is easy to follow.\n\n======= Significance ========\n\nThe paper is another application of RL to accelerating first-order algorithms. Since there are relatively fewer pieces of work on applying ML/RL to continuous optimization, this work is certainly another contribution to the field. However, one critical issue is that work in this space might take on a quite similar look: they take an algorithm, formulate its sequential making process as a MDP, and plug in RL algorithms to train. In terms of significance, one might expect high-quality contributions to look at a vastly different problem, offer a different formulation, or display very high performance gains. In these aspects, the current paper is still a bit lacking.\n\n======= Detailed questions =====\n\n1. The multiplier rho can be either treated as a full dimension vector or a scalar. I wonder what is the typical range of the value of rho? The paper plugs in continuous action RL algorithms to train the agent, however, in many standard continuous control task, the action space is well bounded (e.g., between -1 and 1). In this case, the multiplier is lower bounded by zero, but does it have a sensible upper bound? My experience is that last-layer parameterization is quite important for continuous control, then is there any additional scaling applied to the RELU output of the policy network?\n\n2. At training time, since r=-1 the agent aims to solve the problem to optimality as quickly as possible. But this assumes that we have a problem which can be solved to optimality (at least we don't terminate the episode by truncating iterations).  Have you tried cases where the ADMM cannot solve the problem within reasonable num of iterations, and maybe a more informative reward function is useful? For example, can we set r=difference of objective at consecutive steps?\n\n3. In Fig 2 (a), what is the y-axis? Is it the geometric shifted mean of the number of iterations, or the run time? Since the RL agent is trained on minimizing iterations, I assume it should be iterations? Then is there a comparison in terms of run time?\n\n4. Do you think running policy network at each step of ADMM introduces much overhead to the process? It might be interesting to see if you repeat the same action a few steps, what will happen to the performance. In Atari games, such techniques are called 'sticky actions', where they repeat the same action 4 times in a row. This leads to better performance because as a good inductive bias, one might not need very frequent switches of policy output. Also, the NN does not need to forward pass at each step.\n\n5. Compared to Wei et al, 2014, what are the major differences except it is applied to ADMM vs. proximal algorithm? Wei et al, 2014 also tackles the proximal algorithm and outputs actions that include the trade-off parameter between the objective and regularization, which bears a similar flavor to the multiplier in ADMM. It seems that the formulation and training techniques are also highly similar.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper discusses the limitations of the work, mainly in computational aspect of the pipeline.", "review_text": "", "extra_scores": {"ethical_concerns": "No obvious ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: QSQP is among the state of the art QP solvers currently. The use of RL to adapt the step size of the ADMM engine underlying OSQP appears to show clear gains within specific problem classes and some evidence of generalization across problem classes. As such the paper may be of interest to RL researchers interested in such flavors of adaptive optimization, and also application-focused practitioners using OSQP in specific engineering contexts to improve speed and robustness.
Decision: Accept (Poster)