7 ms·

Hamilton-Jacobi-Bellman Equation: Reinforcement Learning and Diffusion Models

171 points by sebzuddas 6mo ago

measurablefunc 6mo ago
It's not clear or obvious why continuous semantics should be applicable on a digital computer. This might seem like nitpicking but it's not, there is a fundamental issue that is always swept under the rug in these kinds of analysis which is about reconciling finitary arithmetic over bit strings & the analytical equations which only work w/ infinite precision over the real or complex numbers as they are usually defined (equivalence classes of cauchy sequences or dedekind cuts). There are no dedekind cuts or cauchy sequences on digital computers so the fact that the analytical equations map to algorithms at all is very non-obvious.
- jampekka 6mo ago
  Continuous formulations are used with digital computers all the time. Limited precision of floats sometimes causes numerical instability for some algorithms, but usually these are fixable with different (sometimes less efficient) implementations. Discretizing e.g. time or space is perhaps a bigger issue, but the issues are usually well understood and mitigated by e.g. advanced numerical integration schemes, discrete-continuous formulations or just cranking up the discretization resolution. Analytical tools for discrete formulations are usually a lot less developed and don't as easily admit closed-form solutions.
- phreeza 6mo ago
  Doesn't continuous time basically mean "this is what we expect for sufficiently small time steps"? Very similar to how one would for example take the first order Taylor dynamics and use them for "sufficiently small" perturbations from equilibrium. Is there any other magic to continuous time systems that one would not expect to be solved by sufficiently small time steps?
  - measurablefunc 6mo ago
    You should look into condition numbers & how that applies to numerical stability of discretized optimization. If you take a continuous formulation & naively discretize you might get lucky & get a convergent & stable implementation but more often than not you will end up w/ subtle bugs & instabilities for ill-conditioned initial conditions.
    - phreeza 6mo ago
      I understand that much, but it seems like "your naive timestep may need to be smaller than you think or you need to do some extra work" rather than the more fundamental objection from OP?
      - measurablefunc 6mo ago
        The translation from continuous to discrete is not automatic. There is a missing verification in the linked analysis. The mapping must be verified for stability for the proper class of initial/boundary conditions. Increasing the resolution from 64 bit floats to 128 bit floats doesn't automatically give you a stable discretized optimizer from a continuous formulation.
        phyalow 6mo ago
        Or you can just try stuff and see if it works
        measurablefunc 6mo ago
        Point still stands, translation from continuous to discrete is not as simple as people think.
        phreeza 6mo ago
        Numerical issues totally exist but the reason has nothing to do with the fact that Cauchy sequences don't exist on a computer imo.
  - heyethan 6mo ago
    [flagged]
  - tsimionescu 6mo ago
    Infinity has properties that finite approximations of it just don't have, and this can lead to serious problems for certain theorems. In the general case, the integral of a continuous function can be arbitrarily different from the sum of a finite sequence of points sampled from that function, regardless of how many points you sample - and it's even possible that the discrete version is divergent even if the continous one is convergent. I'm not saying that this is the case here, but there generally needs to be some justification to say that a certain result that is proven for a continuous function also holds for some discrete version of it. For a somewhat famous real-world example, it's not currently known how to produce a version of QM/QFT that works with discrete spacetime coordinates, the attempted discretizations fail to maintain the properties of the continuous equations.
- cubefox 6mo ago
  Real numbers mostly appear in calculus (e.g. the chain rule in gradient descent/backpropagation), but "discrete calculus" is then used as an approximation of infinitesimal calculus. It uses "finite differences" rather than derivatives, which doesn't require real numbers: https://en.wikipedia.org/wiki/Finite_difference https://en.wikipedia.org/wiki/Finite_difference I'm not sure about applications of real numbers outside of calculus, and how to replace them there.
- sfpotter 6mo ago
  This is what the field of numerical analysis exists for. These details definitely have been treated, but this was done mainly early in the field's history; for example, by people like Wilkinson and Kahan...
  - magicalhippo 6mo ago
    I just took some basic numerical courses at uni, but every time we discretized a problem with the aim to implement it on a computer, we had to show what the discretization error would lead to, eg numerical dispersion[1] etc, and do stability analysis and such, eg ensure CFL[2] condition held. So I guess one might want to do a similar exercise to deriving numerical dispersion for example in order to see just how discretizing the diffusion process affects it and the relation to optimal control theory. [1]: https://en.wikipedia.org/wiki/Numerical_dispersion https://en.wikipedia.org/wiki/Numerical_dispersion [2]: https://en.wikipedia.org/wiki/Courant%E2%80%93Friedrichs%E2%80%93Lewy_condition https://en.wikipedia.org/wiki/Courant%E2%80%93Friedrichs%E2%...
- imtringued 6mo ago
  I can't tell if this a troll attempt or not. If your definition of "algorithm" is "list of instructions", then there is nothing surprising. It's very obvious. The "algorithm" isn't perfect, but a mapping with an error exists. If your definition of "algorithm" is "error free equivalent of the equations", then the analytical equations do not map to "algorithms". "Algorithms" do not exist. I mean, your objection is kind of like questioning how a construction material could hold up a building when it is inevitably bound to decay and therefore result in structural collapse. Is it actually holding the entire time or is it slowly collapsing the entire time?
- shiandow 6mo ago
  It is definitely not obvious, but I wouldn't say it is completely unclear. For instance we know that algorithms like the leapfrog integrator not only approximate a physical system quite well but even conserve the energy, or rather a quantity that approximates the true energy. There are plenty of theorems about the accuracy and other properties of numerical algorithms.
  - measurablefunc 6mo ago
    How do they apply in this case?
nareyko 6mo ago
[dead]
Cloudly 6mo ago
Ever since the control bug bit me in my EE undergrad years I am happy to see how useful the knowledge remains. Of course the underlying math of optimization remains general but the direct applications of control theory made it much more appetizing for me to struggle through.
- sebzuddas 6mo ago
  My favourite subject!
lain98 6mo ago
I find myself completely outclassed by mathematicians in my own field. I tried to learn a little math on the side after my regular software engineer gig but I'm completely outclassed by phd's. I am unsure of the next course of action or if software will survive another 5 years and how my career will look like in the future. Seems like I am engaged in the ice trade and they are about to invent the refrigerator.
- rsp1984 6mo ago
  Don't despair. The key to becoming proficient in advanced subjects like this one is to first try to understand the fundamentals in plain language and pictures in your mind. Ignore the equations. Ask AI to explain the topic at hand at the most fundamental level. Once the fundamental concepts are understood, what problem is being solved and where the key difficulties are, only then the equations will start to make sense. If you start out with the math, you're making your life unnecessarily hard. Also, not universally true but directionally true as a rule of thumb, the more equations a text contains the less likely it is that the author itself has truly grasped the subject. People who really grasp a subject can usually explain it well in plain language.
  - griffzhowl 6mo ago
    > People who really grasp a subject can usually explain it well in plain language. That's very much a matter of style. An equation is often the plainest way of expressing something
    - rsp1984 6mo ago
      The problem is that equations give the illusion of conciseness and brevity but in reality always heavily depend on context. You give a physicist an equation of a completely unrelated field in mathematics and it will make zero sense to them because they lack the context. And vice versa. The only people who can readily read and understand your equations are those that already understand the subject and have learned all the context around the math. Therefore it's pointless to try to start with the math when you're foreign to a field. It simply won't make any sense without the context.
jesuslop 6mo ago
Nice summary, saving it. If author is around, Bellman equation label ended overlapped to eqn., and pargraph quoting signs got into HJB displayed one. Suggest changes is 404 not found. Liked the presentation overall, thank you!
lukko 6mo ago
I've just started to try and learn the basics of RL and the Bellman Equation - are there any good books or resources I should look at? I think this post is beyond my current level. I'm most interested in how the equation can be implemented step by step in an ML library - worked examples would be very helpful. Thank you!
- ActivePattern 6mo ago
  Reinforcement Learning by Sutton & Barto is an excellent introduction by two of the founders of the field. Read here: http://incompleteideas.net/book/the-book-2nd.html http://incompleteideas.net/book/the-book-2nd.html
- srean 6mo ago
  I would recommend that you start with one of the classics (not much of deep RL) https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutto... This will have a gentler learning curve. After this you can move on to more advanced material. The other resource I will recommend is everything by Bertsekas. In this context, his books on dynamic programming and neurodyanamic programming. Happy reading.
- brandonb 6mo ago
  OpenAI's spinning up in deep RL is free and pretty good: https://spinningup.openai.com/en/latest/ https://spinningup.openai.com/en/latest/ It includes both mathematical formulas and PyTorch code. I found it a bit more practical than the Sutton & Barto book, which is a classic but doesn't cover some of the more modern methods used in deep reinforcement learning.
  - jmalicki 6mo ago
    Cool! It's also nice that Sutton & Barto belabors a lot of old stuff that is no longer obsessed over, and this skims through that and gets to the stuff that is much more relevant today.
  - empiricus 6mo ago

171 points by sebzuddas 6mo ago

It's not clear or obvious why continuous semantics should be applicable on a digital computer. This might seem like nitpicking but it's not, there is a fundamental issue that is always swept under the rug in these kinds of analysis which is about reconciling finitary arithmetic over bit strings & the analytical equations which only work w/ infinite precision over the real or complex numbers as they are usually defined (equivalence classes of cauchy sequences or dedekind cuts). There are no dedekind cuts or cauchy sequences on digital computers so the fact that the analytical equations map to algorithms at all is very non-obvious.

jampekka 6mo ago
Continuous formulations are used with digital computers all the time. Limited precision of floats sometimes causes numerical instability for some algorithms, but usually these are fixable with different (sometimes less efficient) implementations. Discretizing e.g. time or space is perhaps a bigger issue, but the issues are usually well understood and mitigated by e.g. advanced numerical integration schemes, discrete-continuous formulations or just cranking up the discretization resolution. Analytical tools for discrete formulations are usually a lot less developed and don't as easily admit closed-form solutions.
phreeza 6mo ago
Doesn't continuous time basically mean "this is what we expect for sufficiently small time steps"? Very similar to how one would for example take the first order Taylor dynamics and use them for "sufficiently small" perturbations from equilibrium. Is there any other magic to continuous time systems that one would not expect to be solved by sufficiently small time steps?
- measurablefunc 6mo ago
  You should look into condition numbers & how that applies to numerical stability of discretized optimization. If you take a continuous formulation & naively discretize you might get lucky & get a convergent & stable implementation but more often than not you will end up w/ subtle bugs & instabilities for ill-conditioned initial conditions.
  - phreeza 6mo ago
    I understand that much, but it seems like "your naive timestep may need to be smaller than you think or you need to do some extra work" rather than the more fundamental objection from OP?
    - measurablefunc 6mo ago
      The translation from continuous to discrete is not automatic. There is a missing verification in the linked analysis. The mapping must be verified for stability for the proper class of initial/boundary conditions. Increasing the resolution from 64 bit floats to 128 bit floats doesn't automatically give you a stable discretized optimizer from a continuous formulation.
      - phyalow 6mo ago
        Or you can just try stuff and see if it works
        measurablefunc 6mo ago
        Point still stands, translation from continuous to discrete is not as simple as people think.
        phreeza 6mo ago
        Numerical issues totally exist but the reason has nothing to do with the fact that Cauchy sequences don't exist on a computer imo.
- heyethan 6mo ago
  [flagged]
- tsimionescu 6mo ago
  Infinity has properties that finite approximations of it just don't have, and this can lead to serious problems for certain theorems. In the general case, the integral of a continuous function can be arbitrarily different from the sum of a finite sequence of points sampled from that function, regardless of how many points you sample - and it's even possible that the discrete version is divergent even if the continous one is convergent. I'm not saying that this is the case here, but there generally needs to be some justification to say that a certain result that is proven for a continuous function also holds for some discrete version of it. For a somewhat famous real-world example, it's not currently known how to produce a version of QM/QFT that works with discrete spacetime coordinates, the attempted discretizations fail to maintain the properties of the continuous equations.
cubefox 6mo ago
Real numbers mostly appear in calculus (e.g. the chain rule in gradient descent/backpropagation), but "discrete calculus" is then used as an approximation of infinitesimal calculus. It uses "finite differences" rather than derivatives, which doesn't require real numbers: https://en.wikipedia.org/wiki/Finite_difference https://en.wikipedia.org/wiki/Finite_difference I'm not sure about applications of real numbers outside of calculus, and how to replace them there.
sfpotter 6mo ago
This is what the field of numerical analysis exists for. These details definitely have been treated, but this was done mainly early in the field's history; for example, by people like Wilkinson and Kahan...
- magicalhippo 6mo ago
  I just took some basic numerical courses at uni, but every time we discretized a problem with the aim to implement it on a computer, we had to show what the discretization error would lead to, eg numerical dispersion[1] etc, and do stability analysis and such, eg ensure CFL[2] condition held. So I guess one might want to do a similar exercise to deriving numerical dispersion for example in order to see just how discretizing the diffusion process affects it and the relation to optimal control theory. [1]: https://en.wikipedia.org/wiki/Numerical_dispersion https://en.wikipedia.org/wiki/Numerical_dispersion [2]: https://en.wikipedia.org/wiki/Courant%E2%80%93Friedrichs%E2%80%93Lewy_condition https://en.wikipedia.org/wiki/Courant%E2%80%93Friedrichs%E2%...
imtringued 6mo ago
I can't tell if this a troll attempt or not. If your definition of "algorithm" is "list of instructions", then there is nothing surprising. It's very obvious. The "algorithm" isn't perfect, but a mapping with an error exists. If your definition of "algorithm" is "error free equivalent of the equations", then the analytical equations do not map to "algorithms". "Algorithms" do not exist. I mean, your objection is kind of like questioning how a construction material could hold up a building when it is inevitably bound to decay and therefore result in structural collapse. Is it actually holding the entire time or is it slowly collapsing the entire time?
shiandow 6mo ago
It is definitely not obvious, but I wouldn't say it is completely unclear. For instance we know that algorithms like the leapfrog integrator not only approximate a physical system quite well but even conserve the energy, or rather a quantity that approximates the true energy. There are plenty of theorems about the accuracy and other properties of numerical algorithms.
- measurablefunc 6mo ago
  How do they apply in this case?

nareyko 6mo ago

[dead]

Cloudly 6mo ago

Ever since the control bug bit me in my EE undergrad years I am happy to see how useful the knowledge remains. Of course the underlying math of optimization remains general but the direct applications of control theory made it much more appetizing for me to struggle through.

sebzuddas 6mo ago
My favourite subject!

lain98 6mo ago

I find myself completely outclassed by mathematicians in my own field. I tried to learn a little math on the side after my regular software engineer gig but I'm completely outclassed by phd's. I am unsure of the next course of action or if software will survive another 5 years and how my career will look like in the future. Seems like I am engaged in the ice trade and they are about to invent the refrigerator.

rsp1984 6mo ago
Don't despair. The key to becoming proficient in advanced subjects like this one is to first try to understand the fundamentals in plain language and pictures in your mind. Ignore the equations. Ask AI to explain the topic at hand at the most fundamental level. Once the fundamental concepts are understood, what problem is being solved and where the key difficulties are, only then the equations will start to make sense. If you start out with the math, you're making your life unnecessarily hard. Also, not universally true but directionally true as a rule of thumb, the more equations a text contains the less likely it is that the author itself has truly grasped the subject. People who really grasp a subject can usually explain it well in plain language.
- griffzhowl 6mo ago
  > People who really grasp a subject can usually explain it well in plain language. That's very much a matter of style. An equation is often the plainest way of expressing something
  - rsp1984 6mo ago
    The problem is that equations give the illusion of conciseness and brevity but in reality always heavily depend on context. You give a physicist an equation of a completely unrelated field in mathematics and it will make zero sense to them because they lack the context. And vice versa. The only people who can readily read and understand your equations are those that already understand the subject and have learned all the context around the math. Therefore it's pointless to try to start with the math when you're foreign to a field. It simply won't make any sense without the context.

jesuslop 6mo ago

Nice summary, saving it. If author is around, Bellman equation label ended overlapped to eqn., and pargraph quoting signs got into HJB displayed one. Suggest changes is 404 not found. Liked the presentation overall, thank you!

lukko 6mo ago

I've just started to try and learn the basics of RL and the Bellman Equation - are there any good books or resources I should look at? I think this post is beyond my current level. I'm most interested in how the equation can be implemented step by step in an ML library - worked examples would be very helpful. Thank you!

ActivePattern 6mo ago
Reinforcement Learning by Sutton & Barto is an excellent introduction by two of the founders of the field. Read here: http://incompleteideas.net/book/the-book-2nd.html http://incompleteideas.net/book/the-book-2nd.html
srean 6mo ago
I would recommend that you start with one of the classics (not much of deep RL) https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutto... This will have a gentler learning curve. After this you can move on to more advanced material. The other resource I will recommend is everything by Bertsekas. In this context, his books on dynamic programming and neurodyanamic programming. Happy reading.
brandonb 6mo ago
OpenAI's spinning up in deep RL is free and pretty good: https://spinningup.openai.com/en/latest/ https://spinningup.openai.com/en/latest/ It includes both mathematical formulas and PyTorch code. I found it a bit more practical than the Sutton & Barto book, which is a classic but doesn't cover some of the more modern methods used in deep reinforcement learning.
- jmalicki 6mo ago
  Cool! It's also nice that Sutton & Barto belabors a lot of old stuff that is no longer obsessed over, and this skims through that and gets to the stuff that is much more relevant today.
- empiricus 6mo ago