16
$\begingroup$

Recently, I attended a very nice talk given by someone at the place I work about applying Deep Reinforcement Learning (DRL) for a design optimization problem. It was particularly interesting to me because I was not aware about this domain in optimization that is emerging.

However, one thing which I could not understand is that what is the motivation behind using DRL approach for such problems? If the problem is extremely complex, then one way to solve them can be by building black box data-driven models and then using heuristics. What advantages does DRL offers over gradient-based or gradient-free optimization?

Would anyone, who has experience in working on such topic like to share their opinion? Also, is there some standard text or paper that you can point me to?

$\endgroup$
21
$\begingroup$

"General purpose optimization" is quite broad, so I'll take a step back first, to better identifying the motivation of using ML in optimization settings.

To keep things simple, I'll consider a single-objective minimization problem with decision vector $x$, objective function $f$ and some constraints $x \in X$, i.e., \begin{align} (P) \ \ \ \min_{x} \ \ \ & f(x)\\ \text{s.t.} \ \ \ & x \in X. \end{align} "Solving" $(P)$ means

  1. finding $x^{*} \in X$ such that $f(x^{*})$ is as small as possible, and
  2. proving that there does not exist an $\bar{x} \in X$ with $f(\bar{x}) < f(x^{*})$.

Heuristic methods will only handle 1., approximation algorithms handle 1. with some guarantee w.r.t 2., and exact methods ensure both 1. and 2.

Now, where can ML come into play? I will outline two of the most common avenues in combinatorial optimization.

For background:

ML-based heuristic solutions

A first and perhaps most intuitive approach is to use a model to predict $x^{*}$ based on the problem's data: give me $f$ and $X$ and I will tell you $x^{*}$ (see also Part 2 of the IJCAI tutorial). For problems where feasibility is not hard (e.g. unconstrained problems or problems with a simple constraint structure), this can give decent results. In the general case, however, one must ensure that the predicted solution is feasible, or tolerate some amount of infeasibility.

A more refined approach consists in using ML techniques to learn heuristics. A typical example is a greedy algorithm wherein ones uses a learning scheme (typically trained offline) to select the next move. Some examples: Neural Combinatorial Optimization with Reinforcement Learning, Learning Combinatorial Optimization Algorithms over Graphs or Learning chordal extensions.

Tailored algorithmic strategies

A lot of optimization algorithms, from simple gradient descent to sophisticated branch-and-bound methods, rely on a number of heuristic decisions. Some are static: should the problem be linearized or not? which algorithm should I use?; some are dynamic: which variable should I branch on? which cuts should be added? should I perform a restart now?

In any case, ML techniques offer the possibilities of tuning those heuristic decisions to a particular distribution of instances (see Part 3 of the ML4CO Tutorial @ IJCAI). Again, some examples:

Some intrinsic limitations

There are two theoretical elements that, I think, underlie some intrinsic limitations to the above approaches: computational complexity and the no free lunch theorem.

First, unless P=NP, problems that are NP-hard cannot be solved in polynomial time. This means that any algorithm (whether based on ML or not) that only performs polynomially many operations cannot return an optimal solution all the time. However, this does not prevent highly-tuned heuristics from obtaining excellent-quality solutions in practice. Likewise, sometimes even finding a feasible solution $x \in X$ can be NP-hard in itself, and it becomes impossible to guarantee that a polynomial-time oracle (whether based on ML or not) can always return a feasible solution.

Second, the no free lunch theorem essentially states that, if an algorithm performs well on a set of problems, then there exists a set of problems on which it will perform badly. In practice, this means one likely must re-train their ML models when dealing with a new problem distribution; this comes at a computational and financial cost.

$\endgroup$
2
  • $\begingroup$ Cannot thank you enough for this one! $\endgroup$ – your_boy_gorja Jan 10 at 6:49
  • 1
    $\begingroup$ +1, very useful answer to a very interesting question. This should be the link to the video of the tutorial. $\endgroup$ – k88074 Jan 10 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.