What are the tradeoffs between "exact" and Reinforcement Learning methods for solving optimization problems

Exact methods, e.g., models that utilize an MIP approach with a specified objective and constraints, have advantages like the following:

• Using off the shelf solvers
• Optimality gap provability
• Modelling approaches for domain problems is well understood

Reinforcement Learning (RL) presents the opportunity to train a model and then have it "predict" a solution.

Why would you use this method?

What is the effectiveness of this as a methodology?

It may be possible to get "better" solutions in less compute time given a pre-trained model.

Is any one else working on this type of approach? Or have references?

(Specifically for solving network flow and assignment problems on graphs.)

• Note that RL does not only rely on (as you call it) "predicting" a solution and being "pre-trained". RL can also be used to find solutions/policies for MDPs with state spaces that are way too large to be stored into memory if you would use an exact approach such as value iteration without applying techniques from approximate dynamic programming (which isnt exact either). Jun 3 '19 at 16:32
• RL is NOT one of the supervised learning techniques (Most of the predictive analytics). And it is NOT unsupervised learning techniques (clustering, association rule) either. Jun 6 '19 at 16:13

As far as I understand it, all machine learning approaches used for solving (combinatorial) optimization problems, and in particular reinforcement learning, work as follows:

Use a greedy algorithm to iteratively construct a solution (e.g., by iteratively selecting edges into a path or a tour), and "learn" the ranking (i.e., the ordering) of the next items to pick (e.g., an edge). This said, again, as far as I understand it, any ML based approach that follows these lines, is necessarily a local (search) approach.

It certainly is a heuristic.

It appears to need training for specialties of instances you see and does not (yet?) work generally.

Here is a reference: Dai et al.

A benefit of using an ML approach for optimization is (in my view): we may get a computational intuition about (patterns in) the solution that would not have spotted otherwise. If we would see such patterns, throw away all ML, get paper and pencil and try to prove what we see.

• (Please allow me to misuse the comments option) Hi Marco, good to see another well-known OR name on our forum! Please keep posting :) Jun 4 '19 at 6:41
• Suppose that you're trying to find the optimal policy for a finite MDP. If the underlying graph is acyclic, this is possible by visiting each (state, action, state) triple only once (starting at a sink, at each step, run Bellman optimality on an unvisited state whose actions all lead to visited states). This requires no heuristics, so it doesn't count as RL? Jun 27 '19 at 7:34

Reinforcement learning is set of the algorithms which are used to solve Markov Decision Processes and its variants, e.g. Partially Observed MDP (POMDP).

Most of the problems that we deal with them in the industrial engineering departments and in a larger extent in the Informs community, can be modeled as a MDP or POMDP. Although, in MDP we assume that we know the transition probability distribution for transiting between states, and also assume know the reward distribution too, which are not realistic assumptions. On the other hand, RL does assume availability of those distributions and tries to learn them, which is viable option since nowadays we have huge datasets. So, it might be a good idea to consider RL in OR community too.

Here are some papers which get better results with RL than the classical approaches:

VRP:

Inventory Optimization:

just to mention a few.

Disclaimer: I am one of the co-authors of the first two papers, and I am not posting the links to advertise them!

• You might want to add a disclaimer that the first two papers are yours. :) Jun 4 '19 at 16:34
• @fhk these are the papers I was hinting at on the other post. Jun 4 '19 at 16:34
• @LarrySnyder610, do I need really add the disclaimer? Jun 4 '19 at 17:59
• "Need", no. But, from here: "The community tends to vote down overt self-promotion and flag it as spam. ... However, you must disclose your affiliation in your answers." There's nothing wrong with the way you did it, but adding a little disclaimer couldn't hurt. Jun 4 '19 at 18:02
• Exactly. When we know transition probability and reward distribution, there is no need RL. MDP and RL try to solve the same problem but in totally different situations. Jun 6 '19 at 3:05

A main reason to use Reinforced Learning (RL) is because you don't know the dynamics (update rules) of the system. If you don't know the details of how the system will update, you will not be able to construct tight constraints for MIPs. For example, you may be able to write an MIP for the system with constraint $$Ax = b$$. However, the values of some elements in $$A$$ or $$b$$ maybe unknown.

Since we don't know the dynamics of the system, RL usually requires a huge number of samples from the system to learn the dynamics. There are two major solving approaches for RL.

• Model-based: Use samples to identify a proper model and then use more samples to calibrate that model.
• Model-free: Update the solution with upcoming samples according to certain rules. (Policy Gradient)

In terms of sample complexity, RL in general is quite inefficient comparing to methods with a known fitting model. But the strength of RL comes from its ability to learn the unknown dynamics.

I am not an expert in this field. But I would recommend Ben Recht's paper on the connection between RL and optimal control problems.

Reinforcement learning does not seem to be the most obvious choice in machine learning for optimisation. I have heard a lot of using supervised learning to decide the decisions to take when exploring a B&B tree (which could very straightforwardly be transformed into a reinforcement learning problem).

You also have research in ML giving directly a good answer to your problem. For instance, using recurrent neural networks to deal with graphs: the output is a probability distribution on "interesting" edges of your graph, the ones you should consider taking for your solution.

One reference for all of this: Machine Learning for Combinatorial Optimization:a Methodological Tour d’Horizon. Section 3.2.1 to get complete solutions from ML, 3.2.3 to use ML within the B&B exploration.