5 ms·

Fwiw, reinforcement learning offers objectively better optimization and more efficient inference than LP in many cases.

by vonnik 3y ago

ashish01 3y ago
Any good examples or notebooks using RL to solve typical optimization problems?
- bshipp 3y ago
  I also am curious about this statement. If a problem becomes too complex for linear programming solutions, how easy is it to know that a reinforcement learning solution is actually a global optima and not just local?
  - ke88y 3y ago
    > how easy is it to know that a reinforcement learning solution is actually a global optima and not just local? If the problem is too complex for LP then you're probably not going to get a global optimal from RL either.
    - bshipp 3y ago
      Fair enough. I'm not invested in LP or RL, but my background is in agriculture and LP forms the basis of a lot of cropping/feeding decision trees. I'd be curious to explore new techniques, but it sounds like the discussion here is for a different set of linear programming problems than the ones I see most often, and that there's likely a limited upside toward implementing RL.
      - ke88y 3y ago
        If you have a working LP solution without any glaring compromises in the problem formulation, then I'm not sure why one would want to throw out a perfectly good working solution... algorithms are the means, not the ends :)
        bshipp 3y ago
        I'm pretty sure the main reason for throwing out old tools that still function in favor of the new hotness is developer boredom.
        ke88y 3y ago
        This is why my teams always provide explicit opportunities and spaces for professional development. People should have the opportunity to stretch and grow; if you don't provide those opportunities explicitly, then your most motivated employees will find them implicitly. And you can't afford to not keep your most motivated employees, so you'll end up paying with tech debt instead of Engineeer prof development time.
  - tnecniv 3y ago
    While I disagree with the RL assertion without a source, linear programs are convex, so local optima are global optima. However, unless there is some aspect of the problem which is not known (e.g., you don’t exactly know the objective or constraints), so you model it as a distribution over LPs, I really don’t know how RL will help you. Gradient-based methods can give you improvements if your problem is very large scale and doesn’t have, e.g., sparse structure, but the above claim is bold.
    - bshipp 3y ago
      That's an excellent point. I think one complex agriculture issue I've encountered that LP would struggle to handle is something like inventory control of perishable goods, where there's variance in incoming quality, degradation during storage, and variance in shelf-life based on age of crop, growing conditions, etc. LP would work great for handling grain storage, where a crop generally maintains a known quality profile over time with limited shrinkage, but I could see a use for a machine learning algorithm that handles perishable goods stochastic variables in a more direct way.
ke88y 3y ago
The cons are that RL sometimes requires more babysitting, more non-subject-matter (ie, optimization-method-specific) expertise, and can be a bit less... predictable... at inference time. Also, LP often offers perfectly acceptable optimization and latency. The only case where this isn't true for offline problems is where LP times out or where relaxations of the problem are required to prevent timeout. If I had to choose one method to learn, I guess I would learn RL. But it's a false choice. Given that I know both well, I'd reach for LP unless there was a good reason to use RL instead. And from a user perspective LP is much easier to learn than RL (see cons), so I think this is good general advice. Definitely worth having both tools on your belt if you plan on working on problems where either is a good fit.
- taeric 3y ago
  I would think you'd pick LP if your problem's decision space is modeled in a way that is compatible with it. And if all you have is effectively a simulator and a cost function, then RL is the way to go?
bwestergard 3y ago
"reinforcement learning offers objectively better optimization" I don't follow. Linear programming (with the simplex method) finds the optimal solution set for any linear program eventually. How can reinforcement learning be "better" apart from efficiency?
- choeger 3y ago
  It can't. They're talking out of their backend.
  - mathisfun123 3y ago
    >Founder of Pathmind/Skymind (W16) - Pathmind: Deep reinforcement learning to optimize supply chain and scheduling actually i guess they're shilling - not that there's that much of a differnce.
  - vonnik 3y ago
    Speaking from years of experience comparing RL results to those of LP done with tools like Gurobi on industrial operations and supply chain optimization problems while at my former startup, which was acquired two years ago, so I am not shilling anything. There are many problems that are hard to represent such that LP can compute them. That process alone is long, and hard to adjust even though clients need to make those adjustments. These problems include multi-echelon inventory optimizations, and load-balancing across multiple assembly lines in factories when using hundreds of delivery vehicles, among others. These are properly multi-agent problems that RL solves well if given a valid simulation of the environment. LP often cannot solve it at all. In cases where we went head to head with well known LP software vendors, we were able to move the Pareto frontier by double digit percentages. We open sourced our software here after the acquihire. Depends on Gym among other repositories. Does something similar to Microsoft’s Bonsai. All are welcome to use. https://github.com/PathmindAI https://github.com/PathmindAI
    - whatever1 3y ago
      In operations and supply chains it is not hard to find *A* solution. Operators literally make these decisions manually every day without the need for any computer. The main challenge is to optimize these decisions. With optimality guarantees. Consistently. Day in, day out, with various uncertainties. That is what math optimization has been doing for decades. And no, RL is nowhere to be seen in production, except from some consulting projects that are abandoned.
ashley93 3y ago
This is such a sweeping generalization with no context whatsoever, that it's really hard to say anything about this. They're two different methodologies that are most of the time applied to vastly different problems.
PartiallyTyped 3y ago
Citation needed. RL makes sense when you don’t know the dynamics of the environment and have interactions with it. Linear programming can be done when you can encode a problem as linear constraints which means you know the dynamics. You can then find the optimal set of points of the convex polyhedron defined by the constraints via interior point methods. That’s it. You don’t need exploration and you can get an optimal solution to the constraints because the feasible space is convex.
- deleted 3y ago
  [deleted]
whatever1 3y ago
Not only you provide no evidence, but also your statements are flat out wrong. Not even the founding fathers of RL (Bertsekas et al) have made such claims. RL almost always solves an approximation of the dynamic program. Aka no guarantees of consistent optimality. RL does not guarantee constraint satisfaction. RL needs tons of data to learn the state space and still is not enough. LPs solve nowadays Traveling salesman problems to optimality with millions of nodes. RL close to optimality for less than 1000 nodes.
graycat 3y ago
I studied LP (linear programming) from some of the most advanced researchers in optimization, including LP, in the world, led the class in a Ph.D. qualifying exam mostly on LP, wrote a Ph.D. dissertation in optimization, taught linear programing in college and graduate school, and applied it in business. From that background, given a problem in LP, there are three cases, the problem is (1) infeasible, (2) feasible and bounded, and (3) feasible and unbounded. In case (2), at least one of the extreme points (intuitively, a sharp point) of the set of feasible points is optimal. For an algorithm, the famous simplex algorithm will find an optimal extreme point in finitely many iterations in finite time. For the computing, about all that can go wrong is from a problem being too big or causing poor numerical accuracy. Thus, given an LP, the claim "objectively better optimization", that there was any "optimization" at all means that the problem is in case (2), feasible and bounded. Then claim "objectively better optimization" is essentially not possible.
- taeric 3y ago
  Your response makes me wonder if the idea is not that RL can give more optimal solutions, but perhaps more robust ones? This is giving a ton of charity to the opening post, but fun for me to consider. As you say, given a model, if it is bounded than LP is an obvious route to get optimal. However, models being what they are, there are often times when the prescribed solution is unrealizable for reasons. Reinforcement learning being what it is, is an interesting way to add new features to a model that can "cost in" the penalties that come from non-realized optimal solutions. That make sense? I'm assuming this has been studied, and I simply don't know the names to look into.
  - whatever1 3y ago
    If you need robustness you can explicitly model an uncertainty set for your problem coefficients, and solve to optimality the robust optimization problem. That way you know exactly your degree of “insurance” to uncertainty. You also know that this is the absolute best you can do in view of this uncertainty set.
    - 3y ago

Fwiw, reinforcement learning offers objectively better optimization and more efficient inference than LP in many cases.

by vonnik 3y ago

Fwiw, reinforcement learning offers objectively better optimization and more efficient inference than LP in many cases.

ashish01 3y ago

Any good examples or notebooks using RL to solve typical optimization problems?

bshipp 3y ago
I also am curious about this statement. If a problem becomes too complex for linear programming solutions, how easy is it to know that a reinforcement learning solution is actually a global optima and not just local?
- ke88y 3y ago
  > how easy is it to know that a reinforcement learning solution is actually a global optima and not just local? If the problem is too complex for LP then you're probably not going to get a global optimal from RL either.
  - bshipp 3y ago
    Fair enough. I'm not invested in LP or RL, but my background is in agriculture and LP forms the basis of a lot of cropping/feeding decision trees. I'd be curious to explore new techniques, but it sounds like the discussion here is for a different set of linear programming problems than the ones I see most often, and that there's likely a limited upside toward implementing RL.
    - ke88y 3y ago
      If you have a working LP solution without any glaring compromises in the problem formulation, then I'm not sure why one would want to throw out a perfectly good working solution... algorithms are the means, not the ends :)
      - bshipp 3y ago
        I'm pretty sure the main reason for throwing out old tools that still function in favor of the new hotness is developer boredom.
        ke88y 3y ago
        This is why my teams always provide explicit opportunities and spaces for professional development. People should have the opportunity to stretch and grow; if you don't provide those opportunities explicitly, then your most motivated employees will find them implicitly. And you can't afford to not keep your most motivated employees, so you'll end up paying with tech debt instead of Engineeer prof development time.
- tnecniv 3y ago
  While I disagree with the RL assertion without a source, linear programs are convex, so local optima are global optima. However, unless there is some aspect of the problem which is not known (e.g., you don’t exactly know the objective or constraints), so you model it as a distribution over LPs, I really don’t know how RL will help you. Gradient-based methods can give you improvements if your problem is very large scale and doesn’t have, e.g., sparse structure, but the above claim is bold.
  - bshipp 3y ago
    That's an excellent point. I think one complex agriculture issue I've encountered that LP would struggle to handle is something like inventory control of perishable goods, where there's variance in incoming quality, degradation during storage, and variance in shelf-life based on age of crop, growing conditions, etc. LP would work great for handling grain storage, where a crop generally maintains a known quality profile over time with limited shrinkage, but I could see a use for a machine learning algorithm that handles perishable goods stochastic variables in a more direct way.

ke88y 3y ago

The cons are that RL sometimes requires more babysitting, more non-subject-matter (ie, optimization-method-specific) expertise, and can be a bit less... predictable... at inference time. Also, LP often offers perfectly acceptable optimization and latency. The only case where this isn't true for offline problems is where LP times out or where relaxations of the problem are required to prevent timeout. If I had to choose one method to learn, I guess I would learn RL. But it's a false choice. Given that I know both well, I'd reach for LP unless there was a good reason to use RL instead. And from a user perspective LP is much easier to learn than RL (see cons), so I think this is good general advice. Definitely worth having both tools on your belt if you plan on working on problems where either is a good fit.

taeric 3y ago
I would think you'd pick LP if your problem's decision space is modeled in a way that is compatible with it. And if all you have is effectively a simulator and a cost function, then RL is the way to go?

bwestergard 3y ago

"reinforcement learning offers objectively better optimization" I don't follow. Linear programming (with the simplex method) finds the optimal solution set for any linear program eventually. How can reinforcement learning be "better" apart from efficiency?

choeger 3y ago
It can't. They're talking out of their backend.
- mathisfun123 3y ago
  >Founder of Pathmind/Skymind (W16) - Pathmind: Deep reinforcement learning to optimize supply chain and scheduling actually i guess they're shilling - not that there's that much of a differnce.
- vonnik 3y ago
  Speaking from years of experience comparing RL results to those of LP done with tools like Gurobi on industrial operations and supply chain optimization problems while at my former startup, which was acquired two years ago, so I am not shilling anything. There are many problems that are hard to represent such that LP can compute them. That process alone is long, and hard to adjust even though clients need to make those adjustments. These problems include multi-echelon inventory optimizations, and load-balancing across multiple assembly lines in factories when using hundreds of delivery vehicles, among others. These are properly multi-agent problems that RL solves well if given a valid simulation of the environment. LP often cannot solve it at all. In cases where we went head to head with well known LP software vendors, we were able to move the Pareto frontier by double digit percentages. We open sourced our software here after the acquihire. Depends on Gym among other repositories. Does something similar to Microsoft’s Bonsai. All are welcome to use. https://github.com/PathmindAI https://github.com/PathmindAI
  - whatever1 3y ago
    In operations and supply chains it is not hard to find *A* solution. Operators literally make these decisions manually every day without the need for any computer. The main challenge is to optimize these decisions. With optimality guarantees. Consistently. Day in, day out, with various uncertainties. That is what math optimization has been doing for decades. And no, RL is nowhere to be seen in production, except from some consulting projects that are abandoned.

ashley93 3y ago

This is such a sweeping generalization with no context whatsoever, that it's really hard to say anything about this. They're two different methodologies that are most of the time applied to vastly different problems.

PartiallyTyped 3y ago

Citation needed. RL makes sense when you don’t know the dynamics of the environment and have interactions with it. Linear programming can be done when you can encode a problem as linear constraints which means you know the dynamics. You can then find the optimal set of points of the convex polyhedron defined by the constraints via interior point methods. That’s it. You don’t need exploration and you can get an optimal solution to the constraints because the feasible space is convex.

deleted 3y ago
[deleted]

whatever1 3y ago

Not only you provide no evidence, but also your statements are flat out wrong. Not even the founding fathers of RL (Bertsekas et al) have made such claims. RL almost always solves an approximation of the dynamic program. Aka no guarantees of consistent optimality. RL does not guarantee constraint satisfaction. RL needs tons of data to learn the state space and still is not enough. LPs solve nowadays Traveling salesman problems to optimality with millions of nodes. RL close to optimality for less than 1000 nodes.

graycat 3y ago

I studied LP (linear programming) from some of the most advanced researchers in optimization, including LP, in the world, led the class in a Ph.D. qualifying exam mostly on LP, wrote a Ph.D. dissertation in optimization, taught linear programing in college and graduate school, and applied it in business. From that background, given a problem in LP, there are three cases, the problem is (1) infeasible, (2) feasible and bounded, and (3) feasible and unbounded. In case (2), at least one of the extreme points (intuitively, a sharp point) of the set of feasible points is optimal. For an algorithm, the famous simplex algorithm will find an optimal extreme point in finitely many iterations in finite time. For the computing, about all that can go wrong is from a problem being too big or causing poor numerical accuracy. Thus, given an LP, the claim "objectively better optimization", that there was any "optimization" at all means that the problem is in case (2), feasible and bounded. Then claim "objectively better optimization" is essentially not possible.

taeric 3y ago
Your response makes me wonder if the idea is not that RL can give more optimal solutions, but perhaps more robust ones? This is giving a ton of charity to the opening post, but fun for me to consider. As you say, given a model, if it is bounded than LP is an obvious route to get optimal. However, models being what they are, there are often times when the prescribed solution is unrealizable for reasons. Reinforcement learning being what it is, is an interesting way to add new features to a model that can "cost in" the penalties that come from non-realized optimal solutions. That make sense? I'm assuming this has been studied, and I simply don't know the names to look into.
- whatever1 3y ago
  If you need robustness you can explicitly model an uncertainty set for your problem coefficients, and solve to optimality the robust optimization problem. That way you know exactly your degree of “insurance” to uncertainty. You also know that this is the absolute best you can do in view of this uncertainty set.
  - 3y ago