17
$\begingroup$

I know that Markov Chains and Markov Decision Processes have been studied in the OR community too. But, I was wondering what is the relationship of Operations Research (OR) and Reinforcement Learning (RL)?

Does any other sub-field of OR (e.g., integer programming, convex optimization) actually study RL? If so, is there any reference that explains the connection?

$\endgroup$
  • 3
    $\begingroup$ Not completely related, but this paper provides a nice overview of machine learning and combinatorial optimization problems. arxiv.org/abs/1811.06128 $\endgroup$ – Albert Schrotenboer May 31 '19 at 13:14
  • 2
    $\begingroup$ You may want to take a look at this paper by Prof. Powell. sciencedirect.com/science/article/pii/S0377221718306192 $\endgroup$ – Katatonia May 31 '19 at 13:21
  • 1
    $\begingroup$ We can not say one belongs to the other one, or one solves the other one. In my view, O.R. is a collection of tools and techniques to use mathematics to solve problems that arise in real-life, where RL is a higher-level study (i.e., more algorithms involved, not a set of `tools') Also, there are two directions of relationships available. Some people recently started to apply RL techniques to solve hard OR problems, mainly hard optimization problems. We can also see the other way around, if you think RL as a collection of Markov Processes, then you can use OR techniques to solve RL problems. $\endgroup$ – independentvariable May 31 '19 at 13:24
  • $\begingroup$ I know that in inventory control there has been put a lot of effort in finding solutions in stochastic dynamic environments by modelling it as a MDP and then solving it with dynamic programming. Reinforcement learning can solve MDP's as well, but because the value function is not scalable, the relationship between DEEP reinforcement learning and inventory control is more clear. $\endgroup$ – Steven31415 Jun 3 '19 at 14:04
16
$\begingroup$

In the operations research community, many study dynamic programming models and solution approaches. Since many interesting dynamic programming problems attempt to model information uncertainty over time, the term stochastic dynamic programming is sometimes used. The Markov decision process model is an example.

Finding optimal policies to many dynamic programming models is often very difficult computationally. Therefore, a subfield known as approximate dynamic programming emerged. The focus of this subfield in general is developing approaches for finding near-optimal policies. From my viewpoint, there is not too much difference between reinforcement learning and ADP. The classic two-volume text on dynamic programming by Bertsekas (1st edition was 1995, currently on 4th edition 2017/2012) is a good first introduction that may help you see the connection.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ The difference between Dynamic Programming(DP) and Reinforcement Learning (RL) is that we know system parameters or not. In DP including Stochastic DP, MDP even ADP, we know rewards(can be stochastic), state transition probability, and so on. In RL, we don’t know the system parameters. Therefore the agent learn the system parameters by doing. Overall goal. Is the same maximize the rewards. DP try’s to find the optimal policy (no need to exploring) while RL try’s to update value functions of each state so that eventually the against can reach the optimal policy by keep exploring. $\endgroup$ – S. Phil Kim Jun 1 '19 at 9:41
  • 2
    $\begingroup$ @Phil Kim I appreciate your viewpoint but do not agree with all of your points. What is most important in this discussion is the following: just like when "OR people" who begin exploring RL/ML approaches to problems need to be aware of the history and progress of the RL/ML field, it is also imperative that "RL/ML people" are aware of all of the work that has been conducted in OR on DP/ADP. $\endgroup$ – alerera Jun 2 '19 at 18:44
10
$\begingroup$

RL (and Machine Learning in general) often use specialized forms of continuous optimization problems that enable one to use elegant solving techniques (e.g. training/learning on the GPU or even special hardware (TPU and friends)). See here for a nice overview of the underlying optimization problems in Machine Learning and Deep Learning.

As @albert-schroteboer already wrote in the comments, there are some activities to bring ML/DL/RL and combinatorial problems together. There have been some efforts with graph neural nets to tackle some problems traditionally solved via combinatorial algorithms. See here for an overview and some more papers here (TSP, Knapsack), here (VRP variants), here (MaxCut, TSP) or here (Quadratic Assignment).

Note that ML/DL/RL algorithms usually do not give a guarantee for the solution quality whereas traditional combinatorial algorithms might have this property (sometimes it is inherently in the algorithms, sometimes extra effort is taken to prove optimality). For large problem instances when the traditional algorithms take a long time to produce a solution or cases where a "good" (but not necessary optimal) solution is sufficient, these new approaches might be a good addition to the other algorithms.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ True, for example, the classification algorithms are hard to interpret and manipulate. But in this paper: pubsonline.informs.org/doi/pdf/10.1287/ijoo.2018.0001 you can see that after formulating the classification methods in OR-optimization fashion, you can add robustness techniques to change the main objective $\endgroup$ – independentvariable May 31 '19 at 14:01
  • $\begingroup$ Thank you for the excellent paper links! I will be using these when updating my optimization course contents. $\endgroup$ – AndyT Jun 4 '19 at 18:06
7
$\begingroup$

Something that I think is becoming more prominent is the use of RL for what would have traditionally been solved using exact solutions.

https://medium.com/octavian-ai/finding-shortest-paths-with-graph-networks-807c5bbfc9c8

This is something that I'm following and will hopefully try and implement for a Prize Collecting Steiner Tree (PCST) and/or assignment model.

The open question is why would you use this method?

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?

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ sort of like using RL as a heuristic, no? $\endgroup$ – LarrySnyder610 Jun 2 '19 at 11:12
  • 2
    $\begingroup$ Would you move your last line to a new question (with context, obviously) and post that? Answers aren't supposed to be used to ask new questions, but more than that, I think that's a good question on its own. (And I have an answer. ;) ) $\endgroup$ – LarrySnyder610 Jun 2 '19 at 11:13
  • $\begingroup$ Sure! Excited to see what you share $\endgroup$ – fhk Jun 3 '19 at 15:28
  • $\begingroup$ moved here: or.stackexchange.com/questions/183/… $\endgroup$ – fhk Jun 3 '19 at 15:45

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.