summaries: This paper presents a method to improve QP solving speed via reinforcement learning.  A regularization parameter used in OSQP solver is being updated via a RL policy. The approach is shown to improve OSQP performance on various benchmarks.  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.  ====== updated post rebuttal =====  Thanks the reviewers for the replies. Aggregating all information so far, I think the major weakness of the paper is the following:  It 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.  Now 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.  The 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).  Still, overall I think the paper provides a solid contribution and I am willing to raise my eval to 6. 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. 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. 
abstractText: 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-ofthe-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észáros problems. Code, models, and videos are available at https://berkeleyautomation.github.io/rlqp/.
authors.name: Jeffrey Ichnowski
authors.name: Paras Jain
authors.name: Bartolomeo Stellato
authors.name: Goran Banjac
authors.name: Michael Luo
authors.name: Francesco Borrelli
authors.name: Joseph E. Gonzalez
authors.name: Ion Stoica
authors.name: Ken Goldberg
references.authors: Maria-Florina Balcan Travis Dick Tuomas Sandholm Ellen Vitercik
references.title: Learning to branch
references.venue: In International conference on machine learning,
references.authors: Andrew G Barto Sridhar Mahadevan
references.title: Recent advances in hierarchical reinforcement learning
references.venue: Discrete event dynamic systems,
references.authors: Peter W Battaglia Jessica B Hamrick Victor Bapst Alvaro Sanchez-Gonzalez Vinicius Zambaldi Mateusz Malinowski Andrea Tacchetti David Raposo Adam Santoro Ryan Faulkner
references.title: Relational inductive biases, deep learning, and graph networks
references.venue: arXiv preprint arXiv:1806.01261,
references.authors: Yoshua Bengio Andrea Lodi Antoine Prouvost
references.title: Machine learning for combinatorial optimization: a methodological tour d’horizon
references.venue: European Journal of Operational Research,
references.authors: Dimitris Bertsimas Bartolomeo Stellato
references.title: The voice of optimization
references.venue: Machine Learning,
references.authors: Stephen Boyd Neal Parikh Eric Chu
references.title: Distributed optimization and statistical learning via the alternating direction method of multipliers
references.venue: Now Publishers Inc,
references.authors: Xinyun Chen Yuandong Tian
references.title: Learning to perform local rewriting for combinatorial optimization
references.venue: In Conference on Neural Information Processing Systems (NeurIPS),
references.authors: Andrew R Conn Nicholas IM Gould Philippe L Toint
references.title: Trust region methods
references.authors: Hanjun Dai Elias B Khalil Yuyu Zhang Bistra Dilkina Le Song
references.title: Learning combinatorial optimization algorithms over graphs
references.venue: In Conference on Neural Information Processing Systems (NeurIPS),
references.authors: Thomas Elsken Jan Hendrik Metzen Frank Hutter
references.title: Neural architecture search: A survey
references.venue: J. Mach. Learn. Res.,
references.authors: Lasse Espeholt Hubert Soyer Remi Munos Karen Simonyan Volodymir Mnih Tom Ward Yotam Doron Vlad Firoiu Tim Harley Iain Dunning Shane Legg Koray Kavukcuoglu
references.title: IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures, 2018
references.authors: Chelsea Finn Pieter Abbeel Sergey Levine
references.title: Model-agnostic meta-learning for fast adaptation of deep networks
references.venue: In International Conference on Machine Learning,
references.authors: Scott Fujimoto Herke Hoof David Meger
references.title: Addressing function approximation error in actor-critic methods
references.venue: In International Conference on Machine Learning,
references.authors: Fabio Furini
references.title: QPLIB: A library of quadratic programming instances
references.venue: Mathematical Programming Computation,
references.authors: Daniel Gabay Bertrand Mercier
references.title: A dual algorithm for the solution of nonlinear variational problems via finite element approximation
references.venue: Computers & mathematics with applications,
references.authors: David M Gay
references.title: Electronic mail distribution of linear programming test problems
references.authors: P. Giselsson S. Boyd
references.title: Linear convergence and metric selection for douglas-rachford splitting and ADMM
references.venue: IEEE Transactions on Automatic Control,
references.authors: Roland Glowinski A Marroco
references.title: Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de dirichlet non linéaires
references.venue: ESAIM: Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique,
references.authors: Nicholas Gould Jennifer Scott
references.title: A note on performance profiles for benchmarking software
references.venue: ACM Transactions on Mathematical Software (TOMS),
references.authors: Tuomas Haarnoja Aurick Zhou Pieter Abbeel Sergey Levine
references.title: Soft actor-critic: Offpolicy maximum entropy deep reinforcement learning with a stochastic actor
references.venue: In International conference on machine learning,
references.authors: B.S. He H. Yang S.L. Wang
references.title: Alternating Direction Method with Self-Adaptive Penalty Parameters for Monotone Variational Inequalities
references.venue: Journal of Optimization Theory and Applications,
references.authors: Wenlong Huang Igor Mordatch Deepak Pathak
references.title: One policy to control them all: Shared modular policies for agent-agnostic control
references.venue: In International Conference on Machine Learning,
references.authors: Jeffrey Ichnowski Yahav Avigal Vishal Satish Ken Goldberg
references.title: Deep learning can accelerate grasp-optimized motion planning
references.venue: Science Robotics,
references.authors: Jeffrey Ichnowski Michael Danielczuk Jingyi Xu Vishal Satish Ken Goldberg
references.title: GOMP: Grasp-optimized motion planning for bin picking
references.venue: IEEE International Conference on Robotics and Automation (ICRA)
references.authors: Paras Jain Ajay Jain Aniruddha Nrusimha Amir Gholami Pieter Abbeel Joseph Gonzalez Kurt Keutzer Ion Stoica
references.title: Checkmate: Breaking the memory wall with optimal tensor rematerialization
references.venue: In Proceedings of Machine Learning and Systems
references.authors: Elias Khalil Pierre Le Bodic Le Song George Nemhauser Bistra Dilkina
references.title: Learning to branch in mixed integer programming
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Ke Li Jitendra Malik
references.title: Learning to optimize
references.venue: In International Conference on Machine Learning,
references.authors: Timothy P Lillicrap Jonathan J Hunt Alexander Pritzel Nicolas Heess Tom Erez Yuval Tassa David Silver Daan Wierstra
references.title: Continuous control with deep reinforcement learning
references.venue: arXiv preprint arXiv:1509.02971,
references.authors: Michael L Littman
references.title: Markov games as a framework for multi-agent reinforcement learning
references.venue: In Machine learning proceedings
references.authors: Ryan Lowe Yi Wu Aviv Tamar Jean Harb Pieter Abbeel Igor Mordatch
references.title: Multi-agent actorcritic for mixed cooperative-competitive environments
references.venue: In Conference on Neural Information Processing Systems (NeurIPS),
references.authors: Istvan Maros Csaba Mészáros
references.title: A repository of convex quadratic programming problems
references.venue: Optimization Methods and Software,
references.authors: Jacob Mattingley Stephen Boyd
references.title: CVXGEN: A code generator for embedded convex optimization
references.venue: Optimization and Engineering,
references.authors: Luke Metz Niru Maheswaranathan Jeremy Nixon Daniel Freeman Jascha Sohl-Dickstein
references.title: Understanding and correcting pathologies in the training of learned optimizers
references.venue: In International Conference on Machine Learning,
references.authors: Yurii Nesterov Arkadii Nemirovskii
references.title: Interior-point polynomial algorithms in convex programming
references.authors: Alex Nichol Joshua Achiam John Schulman
references.title: On first-order meta-learning algorithms
references.venue: arXiv preprint arXiv:1803.02999,
references.authors: Franco Scarselli Marco Gori Ah Chung Tsoi Markus Hagenbuchner Gabriele Monfardini
references.title: The graph neural network model
references.venue: IEEE transactions on neural networks,
references.authors: John Schulman Jonathan Ho Alex X Lee Ibrahim Awwal Henry Bradlow Pieter Abbeel
references.title: Finding locally optimal, collision-free trajectories with sequential convex optimization
references.venue: In Robotics: science and systems,
references.authors: John Schulman Filip Wolski Prafulla Dhariwal Alec Radford Oleg Klimov
references.title: Proximal policy optimization algorithms
references.venue: arXiv preprint arXiv:1707.06347,
references.authors: David Silver Guy Lever Nicolas Heess Thomas Degris Daan Wierstra Martin Riedmiller
references.title: Deterministic policy gradient algorithms
references.venue: In International conference on machine learning,
references.authors: B. Stellato G. Banjac P. Goulart A. Bemporad S. Boyd
references.title: OSQP: an operator splitting solver for quadratic programs
references.venue: Mathematical Programming Computation,
references.authors: Richard S Sutton David A McAllester Satinder P Singh Yishay Mansour
references.title: Policy gradient methods for reinforcement learning with function approximation
references.venue: In Advances in neural information processing systems,
references.authors: Kaixuan Wei Angelica Aviles-Rivero Jingwei Liang Ying Fu Carola-Bibiane Schönlieb Hua Huang
references.title: Tuning-free plug-and-play proximal algorithm for inverse imaging problems
references.venue: In International Conference on Machine Learning,
references.authors: Philip Wolfe
references.title: The simplex method for quadratic programming
references.venue: Econometrica: Journal of the Econometric Society,
sections.heading: 1 Introduction
sections.text: Solving quadratic programs (QPs) efficiently is critical to applications in finance, robotic control and operations research. While state-of-the-art 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 [33]. 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 is the basis for the widely used and state-of-the art Operator-Splitting QP (OSQP) solver [44]. ADMM performs a linear solve on a 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-art, the ADMM algorithm has numerous hyperparameters that must be tuned with heuristics to regularize and control optimization. Most importantly, the step size parameter ρ 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 ρ [17], they rely on solving semidefinite optimization problems which are much harder than solving the QP itself. Alternatively, some heuristics introduce “feedback” by adapting ρ throughout optimization in order to balance primal and dual residuals [44, 6, 22].
  We propose RLQP (see Fig. 1), 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 a policy πθ : S → A, parameterized by θ (e.g., the weights of a neural network), that maps states in a set S to actions in setA such that the selected action maximizes the accumulated reward r. To train the policy for RLQP, we define S to be the internal state of the
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  QP solver (e.g., the constraint bounds, the primal and dual estimates), A to be the adaptation to the internal parameter (ρ) vector, and r to minimize the number of ADMM iterations taken.
  RLQP’s policy can be trained either jointly across general classes of QPs or with respect to a specific class. The general version of RLQP is trained once on a broad class of QPs and can be used out-ofthe-box on new problems. The specialized version of RLQP is trained on a specific class of 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 a set 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 of classes contained in the test set, 3) the train set contains a 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 to 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 or 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
sections.heading: 2 Related Work
sections.text: This work touches a number of related research areas, including convex optimization, ML-accelerated optimization, learning in 1st-order methods and RL. We summarize related work in Table 1.
  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-known are Gurobi [20] 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 as solving a sequential quadratic program [41] and solving QPs for model-predictive control.
  ML-accelerated combinatorial optimization Accelerating combinatorial optimization problems with deep learning has been explored with wide application [4, 5], including branch-and-bound for
  mixed-integer linear programming [1, 27], graph algorithms [9] and boolean satisfiability problems (SAT) [7]. Many combinatorial optimization problems have exponential search spaces and are NP-hard in a general setting. However, learning-augmented combinatorial algorithms utilize very different methods to RLQP as 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 a 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 et al. [46] recently proposed an RL agent to tune parameters for an ADMM-based inverse imaging solver.
  Reinforcement Learning Overview Reinforcement learning (RL) algorithms include both onpolicy algorithms, such as Proximal Policy Optimization [42], REINFORCE [45], and IMPALA [11], and off-policy algorithms, such as DQN [35] and Soft Actor Critic [21]. RLQP extends the offpolicy Twin-Delayed DDPG (TD3) [13], an actor-critic framework with an exploration policy for continuous action spaces that extends Deep Deterministic Policy Gradient (DDPG) algorithm [29] while addressing approximation errors. Furthermore, in one formulation of RLQP, we train a 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 a QP.
sections.heading: 3 Background
sections.text: In this section, we summarize QPs, the OSQP solver, and an MDP formalization.
sections.heading: 3.1 Quadratic Programs
sections.text: A quadratic program with n variables and m constraints takes the form:
  minimize (1/2)xTPx+ qTx subject to l ≤ Ax ≤ u,
  where x ∈ Rn is the optimization variable, P is an n× n symmetric positive semi-definite matrix that defines the quadratic cost, q ∈ Rn defines the linear cost, A is an m × n matrix that defines the m linear constraints, and l, u ∈ Rm are the constraint’s lower and upper bounds. Here, ≤ is an element-wise less-than-or-equal-to operator. In this form, to specify an equality constraint, the lower and upper bounds are set to the same value, and to specify a constraint unbounded from one side, a sufficiently large value (or ±∞) is specified for the other side.
sections.heading: 3.2 First-Order QP Solver Algorithm
sections.text: The solver we speed up is OSQP, which uses a first-order ADMM method to solve QPs. We summarize OSQP here. Given a QP, OSQP first forms a KKT matrix (below), then iteratively refines a solution from an initialization point for vectors x(0) ∈ Rn, y(0) ∈ Rm, and z(0) ∈ Rm, 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 LDLT solver):[
  P + σI AT
  A diag(ρ)−1 ] ︸ ︷︷ ︸
  KKT matrix
  [ x(k+1)
  v(k+1)
  ] = [ σx(k) − q z(k) − diag(ρ)−1y(k) ]
  (1)
  and then performing the following updates:
  z̃(k+1) ← z(k) + diag(ρ)−1(v(k+1) − y(k)) z(k+1) ← Π[l,u] ( z̃(k+1) + diag(ρ)−1y(k) ) y(k+1) ← y(k) + diag(ρ) ( z̃(k+1) − z(k+1) ) ,
  where σ ∈ R+ and ρ ∈ Rm+ are regularization and step-size parameters, and Π[l,u] : Rm → Rm projects its argument on the constraint bounds. We use the notation diag : Rm → Sm to denote the operator that maps a vector to a diagonal matrix. We define the primal and the dual residual vectors as
  ξ (k) primal = Ax (k) − z(k), and ξ(k)dual = Px (k) + q +AT y(k).
  When the primal and dual residual vectors are small enough in norm after k iterations, x(k+1) and y(k+1) are primal and dual (approximate) solutions to the QP.
  Internally, OSQP has a single scalar ρ̄ that it uses to form ρ according to the following formula:
  ρ = ρ̄ h1... hm  , where hi = {1 if li ̸= ui (inequality constraints) 103 if li = ui (equality constraints),
  (2)
  where the subscript i denotes the i-th coefficient of h, and the bounds l and u.
  Periodically, between ADMM iterations, OSQP will adapt the value of ρ̄. The existing handcrafted formula for adapting ρ attempts to balance between primal and dual residuals, by setting ρ̄(k+1) ← ρ̄(k) √ ∥ξprimal∥∞/∥ξdual∥∞. Empirically, adapting ρ between iterations can speed up the convergence rate.
sections.heading: 3.3 Multi-Agent Single-Policy MDP
sections.text: In a Markov Decision Process (MDP), an agent can be in any state s ∈ S, take an action a ∈ A, and with the transition dynamics function, T (· | s, a), transitions from state s to state s′ after taking action a. The agent receives a reward R : S ×A → R for transitioning from s to s′ by taking action a. Given a tuple (S,A, T,R, γ), the MDP optimization objective is to find a policy πθ : S → A, parameterized by θ, that maximizes the expected cumulative reward E [ ∑∞ t=0 γ
  trt] , where rt is the reward at time t and γ ∈ [0, 1) is a discount factor. We also formulate a multi-agent single-policy MDP setting in which m agents collaborate in a shared environment in state senv ∈ Senv. At each time step, each collaborating agent (CA) i has its own state si ∈ Sca, action ai ∈ Aca, and observations oi ∈ O, but, for computation feasibility, share a single policy πθ : Sca → Aca. State transitions for the environment and all m agents occur simultaneously according to a state transition function T : Senv × Smca ×Amca → Senv × Sca
  m and result in a single shared reward R : Senv×Smca×Amca → R and discount factor. The objective is to find a single shared policy πθ that maximizes the expected cumulative reward. This can be thought of as a special case of a multi-agent MDP [31] or Markov game [30], and we adapt a formulation from Huang et al. [23].
sections.heading: 4 Method
sections.text: The goal of RLQP is to learn a policy to adapt the ρ ∈ Rm vector used in the ADMM update in (1) (see Fig. 1). As the dimensions of this vector vary between QPs, we propose two methods that can handle the variation in m. The first method learns a policy to adapt a scalar ρ̄ and then applies (2) to populate the coefficients of the ρ vector. The second method learns a policy to adapt individual coefficients of the ρ vector.
  Algorithm 1 TD3 for ρ̄ (scalar) 1: Input: exploration noise σ, buffer size rs 2: π,Q← initialize policy and critic (see TD3) 3: D ← replay buffer w/ rs 4: env, s(0) ← new QP, state 5: for t ∈ {0, . . . , T} do 6: ρ̄
  (t) ← π(s(t)) + ϵ, ϵ ∼ N (0, σ) 7: s(t+1), r(t), done(t)←step(env, s(t), a(t)) 8: store (s(t), ρ̄(t), r(t), s(t+1)) in D 9: if done(t) then 10: env, s(t) ← new QP, state 11: update π and Q using data sampled from D
  Algorithm 2 TD3 for ρ (vector) 1: Input: exploration noise σ, buffer size rs 2: π,Q← initialize policy and critic (see TD3) 3: D ← replay buffer w/ rs×(avg no. of constraints) 4: env, s(0),m← new QP, state, no. of constraints 5: for t ∈ {0, . . . , T} do 6: ρ
  (t) i ← π(s (t) i ) + ϵ, ϵ ∼ N (0, σ) ∀i ∈ [1 . . m]
  7: s(t+1), r(t), done(t) ← step(env, s(t),ρ(t)) 8: store (D, s(t)i , ρ (t) i , r (t), s (t+1) i ) ∀i ∈ [1 . . m]
  9: if done(t) then 10: env, s(t),m← new QP, state, no. of constr. 11: update π and Q using data sampled from D
  Since both the number of variables n and the number of constraints m can vary from problem to problem, and the same QP can be written in (n!m!) permutations, we propose learning policies that are problem size and permutation invariant. To do this, we provide a permutation-invariant fixed-size state of the QP solver to either policy.
sections.heading: 4.1 RL Policy for Scalar Adaptation
sections.text: To speed up convergence of OSQP, we hypothesize that RL can learn a scalar ρ̄ adaptation policy (πscalar) that can perform as-well-as or better than the current handcrafted policy (πhc) of OSQP. The handcrafted policy in OSQP periodically adapts ρ by computing a single scalar ρ̄, then sets the coefficients of ρ based on the value of ρ̄. In both handcrafted and RL cases, the policy is a function π : Sρ̄ → Aρ̄, where Sρ̄ ∈ R2 are the norms of the primal and dual residuals stacked into a vector, Aρ̄ ∈ R is the value to set to ρ̄. One advantage of this approach is that a simple heuristic can check that the proposed change to ρ̄ is sufficiently small and leave the KKT matrix unchanged to avoid a 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. 1. TD3 learns the parameters θ of a policy πscalar network and critic Q network, where πscalar determines the action to take and Qπ(s, a) = r(s, a) + γEs′∼T (·|s,a)[Qπ(s′, π(s′))] is the expected reward for a 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 a policy gradient [45] of the objective
  J(θ) = Es∼D[R(s, πscalar(s))],
  that is, ∇θJ = Es∼D[∇θπscalar(s)∇aQπ(s, a)|a=πscalar(s)]
  where D is the discounted state visitation distribution [43]. For brevity, we leave out some details of 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 πscalar updates are staggered.
  In RLQP, the “environment” env is an instance of a randomized QP problem, and a call to step() applies a change to ρ̄ (and thus via (2) to ρ), advances a QP a fixed number of ADMM iterations, and returns the updated internal state s, 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 a timely manner. During training, we also always adapt ρ in each step and ignore the heuristic adapt/no-adapt policy.
  For well-scaled QPs, the residuals and ρ can reasonably range between 10−6 and 106. 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 output to get the action to apply.
sections.heading: 4.2 RL Policy for Vector Coefficient Adaptation
sections.text: For some classes of QPs, the solver can further speed up convergence by adapting all coefficients of the vector ρ, instead of applying (2) to a scalar ρ̄. Conceptually, this could be accomplished with a policy πvec : SQP → Avec, where SQP ∈ RO(n+m) is the internal state of the solver and Avec ∈ Rm+ is the new value for ρ. However, due to variation in problem size and permutation, we instead propose a simplification in which πvec is formulated as a policy πρ : Sρ → Aρ that is applied per coefficient of ρ. Here, Sρ ∈ R6 is state corresponding to a single coefficient in ρ, and Aρ ∈ R is the value to set for that coefficient.
  To define Sρ, we observe that coefficients in ρ are one-to-one with coefficients in y, z, l, u, and Ax. We observe that constraint bounds are likely to have an impact on an ADMM iteration when coefficients of z are “close” to their bounds in l or u. A coefficient in z is also “close” to a solution when it is nearly equal to the corresponding coefficient in Ax. Finally, to include a permutationinvariant signal on the overall convergence, we borrow the idea of max-pooling 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 a coefficient’s state as:
  si =  min(zi − li, ui − zi) zi − (Ax)i yi ρi
  ∥ξprimal∥∞ ∥ξdual∥∞
   ∈ Sρ.
  In practice, we clamp values in each state si to reasonable ranges (e.g., [10−8, 106], [−106, 106], [−106, 106], [10−6, 106], [10−6, 106], [10−6, 106] for the coefficients of si, 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. 1, 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 ρ. After each step, Alg. 2 adds the m tuples to the replay buffer with each tuple consisting of coefficient-specific 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 a 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 an 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 to average out in high variance training data so that the gradient step better matches the true mean of the data.
sections.heading: 5 Experiments
sections.text: To train and test the proposed methods, we modify OSQP to support direct querying and modification of its ρ vector, and integrate both πρ̄ and πvec policies for benchmarking, and a 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 7 classes (see below), but the specific coefficient values in the objective and constraints are generated from a random-number generator. These QPs are also guaranteed to be feasible by construction (e.g., by reverse engineering constraint values from a 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 ρ using PyTorch’s C++ API on the already-trained policy network. We train a small model to keep runtime network inference as fast as possible.
  We evaluate all policies with 7 problem domains (referred to as the “benchmark problem”) defined in Appendix A of the paper on OSQP [44]. These policies cover control, Huber fitting, support-vector machines (SVM), Lasso regression, Portfolio optimization, equality constrained, and random QP domains. Alongside RLQP, we benchmark the unmodified OSQP solver to evaluate how the RL 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-art commercial Gurobi solver [20] (using default settings) as it may be of interest to a practitioner.
  We consider three evaluation configurations: (1) multi-task policy learning in which we train a single RLQP policy on a 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 a single problem domain and (3) zero-shot generalization where we test a general policy on a novel unseen problem class.
  We evaluate speedups with the shifted geometric mean [19] as 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 is computed as:
  exp N∑ i=1 (1/N) log(max(1, vi + s))− s,
  where vi is compute time in seconds, s = 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 wellestablished benchmark problems in the optimization community.
  In all experiments, the policy network architecture has 3 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 on this architecture—finding that smaller networks fail to converge during training.
  We trained on a system with 256 GiB RAM, two Intel Xeon E5-2650 v4 CPUs @ 2.20 GHz for a total of 24 cores (48 hyperthreads), and five NVIDIA Tesla V100s. We ran benchmarks on a system with Intel i9 8-core CPU @ 2.4 GHz and without GPU acceleration.
sections.heading: 5.1 Multi-task/General RLQP Policy
sections.text: We train a general policy on a broad set of problem classes and compare solve times with different classes. During training, we sample one 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 a total of 200 runs per class per solver. The problem dimensions for Control, Huber, SVM, Lasso are (10, 11, 12, 13, 14, 16, 17, 20, 23, 26, 31, 37, 45, 55, 68, 84, 105, 132, 166, 209); for Random
  and Eq are (10, 11, 12, 13, 15, 18, 23, 29, 39, 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 in some cases, e.g. Portfolio optimization, by up to 3x.
sections.heading: 5.2 Problem Dimension Scaling
sections.text: To test how a trained policy scales to higher dimensions, we train a policy on low dimensional problems (10 to 50), and solve problems with varying dimensions, including dimensions higher than the training set (up to 2000). For comparison, we 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 a lower dimensional training set, can show improvement beyond its training range. However, as 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 a 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)3) compute time.
sections.heading: 5.3 Training a Class-Specific Policy
sections.text: Many applications in control [25] and optimization [26] 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, we train policies specific to the problems generated by the trustregion [8] based solver for sequential quadratic program (SQP) from a grasp-optimized motion planner (GOMP) [25, 24] for robots. With these problems, RLQP trained on 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 a general policy may work for multiple problem classes, there are cases in which it is beneficial to train a policy specific to a problem class, particularly if the QPs from that problem class are repeatedly solved.
sections.heading: 5.4 Warm Starting QPs
sections.text: 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 the benefit of warm start on OSQP’s warm-start benchmark and show the results in Fig. 2 (right). As warm starts require fewer iterations, and thus
  fewer adaptations than cold starts, we expect RLQP to show a smaller improvement here. In the plot, we can see that RLQP retains the benefit of warm starting, and also gains a improvement over OSQP.
sections.heading: 5.5 QPLIB
sections.text: We benchmark convex continuous QP instances with constraints from QPLIB [14], and show the results in Table 2. Since there are only a 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 on similar problems should help avoid a timeout.
sections.heading: 5.6 Netlib Linear Programming benchmark
sections.text: The Netlib Linear Programming benchmark [16] contains 98 challenging real-world problems including 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 to high-accuracy as many of these benchmarks are poorly scaled. Overall, vector formulation of RLQP is 1.30× faster than OSQP by the scaled geomean of runtimes. We include a problem-specific breakdown in the supplementary materials.
sections.heading: 5.7 Maros and Mészáros
sections.text: In a manner similar to the QPLIB problems, we also benchmark on the 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 is 1.829 times that of RLQP. Because the dataset contains 138 problems, a table of the full results is included in the Supplementary Material.
sections.heading: 5.8 Learned Policy Analysis
sections.text: We plot and evaluate a learned policy in Fig. 4. From the plot, we see that when z approaches either bound, the output ρ increases. We also observe that with higher y, the policy outputs a 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 a low ρ is desirable
  when the dual is smaller than the primal. However, the learned policy is not a simple square root of residuals like OSQP. The results suggest that the optimal policy is non-linear and problem specific.
sections.heading: 6 Limitations
sections.text: RLQP has limitations. For QPs that converge after few iterations, and thus do not adapt ρ, having a 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 GiB—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—this may be mitigated by learning more efficient representations, or by using dedicated neural-network processing hardware.
sections.heading: 7 Conclusion
sections.text: We presented RLQP, a method for using reinforcement learning (RL) to speed up the convergence rate of a first-order method quadratic program solver. RLQP uses RL to learn a policy to adapt the internal parameters of the solver to 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 a broad class of problems. Results for a 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 a hierarchical policy [2] in which the higher-level policy determines the interval between adaptation, performing a neural-architecture search [10], using meta-learning [12, 38] to speed up problem-specific training, and online-learning to adjust the policy at runtime to 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.
sections.heading: Acknowledgements
sections.text: 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.
title: Accelerating Quadratic Optimization with Reinforcement Learning