9

I was wondering when one would decide to resort to Reinforcement Learning to problems that have been previously tackled by mathematical optimisation methods - think the Traveling Salesman Problem or Job Scheduling or Taxi Sharing Problems.

Since Reinforcement Learning aims at minimising/maximising a certain cost/reward function in a similar way as Operational Research attempts at optimising the result of a certain cost function, I would assume that problems that could be solved by one of the two parties may be tackled by the other. However, is this the case? Are there tradeoffs between the two? I haven't really seen too much research done on RL regarding the problems stated above but I may be mistaken.

If anyone has any insights at all, they would be highly appreciated!!

Nelewout
  • 6,281
  • 3
  • 29
  • 39
Antonia Calvi
  • 127
  • 1
  • 3
  • 5
    I'd like to add that Reinforcement Learning is often referred to as Approximate Dynamic Programming in the Operations Research society (more or less, of course there might be differences). Which makes sense, as the whole RL 'hype' is actually a (in some applications very good) toolbox for solving stochastic dynamic programs heuristically. Until now, the RL approaches for solving traditional OR problems like the TSP have not been very successful. Or to put it in other words, Operations Researchers are very very good in solving such problems and RL is (until now) only moderately good. – Albert Schrotenboer May 13 '19 at 07:57

2 Answers2

6

Here is my two cents. I think that although both approximations have a common goal (optimal decision making), their fundamental working principles are different. In essence, Reinforcement Learning is a data driven approach, where the optimization process is achieved by agent-environment interaction (i.e., data). On the other hand, Optimisation Research uses other methods that require deeper knowledge of the problem and/or imposes more assumptions.

There are many problems, especially academic or toy problems, where both approximations, RL and OR, can be applied. In real world applications, I guess that if you can meet all the assumptions required by OR, RL wouldn't achieve better results. Unfortunately, this is no always the case, so RL is more useful in such cases.

Notice, however, that there exist methods in which is not clear the difference between RL and OR.

Pablo EM
  • 6,190
  • 3
  • 29
  • 37
6

Pablo provided a great explanation. My research is actually in reinforcement learning vs model predictive control. And MPC is a control approach based on trajectory optimization. Reinforcement learning is just a data driven optimization algorithm and can be used for your above examples. Here is a paper for the traveling salesman problem using RL.

The biggest differences are really these:

Reinforcement Learning Method

  • Does not need a model, but a "playground" to try different actions in the environment and learn from it (ie. data driven approach)
  • does NOT guarantee optimality in complex problems due to nonlinear mapping of states to actions. In multiple input multiple output problems, RL uses nonlinear function approximators to solve tasks. But there is no guaranteed convergence the moment these are used
  • Great for problems where it is hard or impossible to derive a model for.
  • Extremely difficult to train, but cheap online calculation
  • Inherent adaptive nature. If the conditions of an environment change, RL can usually adapt by learning the new environment.
  • Worst of all, decisions made by RL is uninterpretable. Advanced RL algorithms are made up of multiple neural networks, therefore, if our RL car driver drives off a cliff, it is nearly impossible to identify just why it would do such a thing.

Optimzation Approaches

  • Performance is dependent on the model. If the model is bad, the optimization will be terrible.

  • Because performance is based on model, identifying a "perfect" model is extremely expensive. In the energy industry, such a model for one plant costs millions, especially because the operating conditions change over time.

  • GUARANTEES optimality. There are many papers published that goes into the proofs regarding that these approaches guarantee robustness, feasibility, and stability.

  • Easy to interpret. Controls and decisions using a optimization approach is easy to interpret because you can go into the model and calculate for why a certain action was performed. In the RL case, this is usually a neural network and completely a black box. Therefore, for safety sensitive problems, RL is currently RARELY used.

  • Very expensive online calculation depending on prediction horizon, because at each time step, we have to optimize the trajectory given the current states.

Rui Nian
  • 2,544
  • 18
  • 32
  • 1
    Appreciate the answer, I'm wondering if there are any academic papers or books that explain those differences in details? – Subaru Spirit Apr 30 '22 at 20:29