Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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?
