Controlled Markov processes

What Hacker News says

1. graycatSep 2021
   The basic idea is dirt simple. After that, apparently the OP has an overview. After that, the math gets quite pure. E.g., the Markov assumption is that in the underlying process, the past and future are conditionally independent given the present. Fairly quickly start discussing this assumption in terms of sigma algebras from measure theory instead of just random variables. The sigma algebras are pretty: (a) If have the sigma algebra generated by a random variable, the random variable is determined (from memory from 20 years ago; my source was

   I. I. Gihman and A. V. Skorohod, The Theory of Stochastic Processes I, ISBN 0-387-06573-3, Springer-Verlag, New York, 1974.

   and I lost my copy in a move and have yet to order another from Springer). (b) If have infinitely many random variables, discussing conditional independence is at least clumsy but the sigma algebra they generate makes talking about conditional independence easy. Where to get infinitely many random variables? In the continuous time case, the past one second will do. In the discrete time case, the full past of the process if assume the process goes back all the way in time.

   But, sure, in practice, can't do anything very direct with sigma algebras, that is, they are pretty theory.

   Here is the whole idea in a reasonably general case in brief:

   Do some financial planning for the next five years. Make time discrete, say, one point in time for each month. Have a point at the beginning and also at the end for a total of 61 points.

   Build a spreadsheet with one column for each of the 61 points in time and one row for each of the relevant variables. To make this stochastic optimal control, Markov decision theory, or other equivalent names, in the spreadsheet have some cells that get their values from the built-in random number generator.

   Also at each of the first 60 points in time, have some variables that are the decisions get to make.

   In the last column, have the value of the business then.

   Our mission, and we have to accept it, is to determine the decisions (values in the decision cells) that maximize the value of the business at the end. Ah, since we have the random cells, typically we want to maximize the expected (average) value at the end.

   So, we start at column 60 and consider all the possible data we could have in column 60. Sure, that data fills maybe a few exabytes. Then we pick values for the decisions in column 60 and reevaluate the spreadsheet many times letting the random cells generate random numbers, average, and see what average value we get in column 61. We do this for all possible decisions. Sure, now we are keeping busy a few million square feet of computing. But the work is highly parallel. That's what we would about have to do using a general purpose program, but in practice we would look at the specific problem, note special structure (properties, assumptions, simplifications), and get some speedups.

   To be more clear, at column 60 set aside the random cells and the decision cells -- the rest have the state at column 60. So, for each possible state, we try all the possible decisions, and for each decision we reevaluate many times and get the expected value of the business in column 61 and pick the best decision. So, there in column 60, for each of the possible states, we get the best decision and the corresponding expected business value in column 61. We store this -- that is, we store the best decisions and expected value for each state. Here we fill some exabytes of storage.

   Now we back up to column 59. For each state we try all the possible decisions. For each of those decisions we recalculate, that is, exercise the random number generators, and see what state we get in column 60 and the corresponding business value in column 61. So, for each state in column 59 we find the best decisions.

   Now we continue in this way back to columns 58, 57, ..., 1. In column 1 we know the state we are in because that is our present. So our calculation for column 1 told us what decision to make there in column 1.

   Then in reality, soon we get to column 2, see what state we are in, and use the decision we tabulated for that state. We continue with column 3, 4, ..., 60, make our decisions in column 60, and see what business value we get in column 61.

   The whole thing is the same except much faster if we have no random cells.

   There are also continuous time treatments, essentially the same intuitively.

   For some books,

   Dimitri P. Bertsekas, Dynamic Programming: Deterministic and Stochastic Models.

   George L. Nemhauser, Dynamic Programming.

   Stuart E. Dreyfus and Averill M. Law, The Art and Theory of Dynamic Programming.

   E. B. Dynkin and A. A. Yushkevich, Controlled Markov Processes.

   Wendell H. Fleming and Raymond W. Rishel, Deterministic and Stochastic Optimal Control.

   There is more from R. T. Rockafellar and R. J.-B. Wets.

   And of course we should mention R. Bellman, the father of this subject.

   Show morethread
2. graycatMay 2015
   Your first reference is good enough -- it's okay.

   All I saw was the Github page of gibberish -- I don't use Github whatever the heck it is. But your URL was fine.

   So, the work is a relatively routine application of classic work from optimization going way back, e.g., to Bellman.

   The "Reinforcement learning" terminology looks like a new label for some quite ancient wine.

   I've wondered what machine learning had that was good and new, and so far I've seen some that is good but not new and some that is new but not good.

   For an application, it would be good to justify the Markov assumption, that is, that the past and future of the process are conditionally independent given the present.

   For a more detailed treatment, I'd recommend, say,

   E. B. Dynkin and A. A. Yushkevich, 'Controlled Markov Processes'.

   Show morethread
3. graycatJul 2025
   Yup: And stochastic dynamic programming and stochastic optimal control! Suppose a cargo plane is to fly from Kansas City to St. Louis, Chicago, Indianapolis, Dayton, Nashville, and Memphis and at each city pickup cargo. Suppose the cargo weights are known only in probability distribution from history and otherwise are probabilistically independent. Have weather reports for the winds and temperatures, but the actual values can vary from the reports. And suppose the fuel prices vary significantly among the stops but are known.

   Then, how much fuel should the pilot buy at each stop to minimize expected cost for the trip? I.e., in simple terms, buy extra fuel where it's cheap and carry (tanker) it to where it's expensive but in so doing burn extra fuel from the extra weight of the extra fuel.

   Solution: Stochastic dynamic programming.

   Hint: In Canada, the solution is illegal!

   Was meeting with Nemhauser (see references below); my cab back to the airport was waiting; and he gave me a 15 second lecture. On the plane thought about his lecture, ..., and stood for my Ph.D. orals and passed (extra credit for guessing my employer).

   Some references (with TeX markup):

   Stuart E.\ Dreyfus and Averill M.\ Law, {\it The Art and Theory of Dynamic Programming,\/} ISBN 0-12-221860-4, Academic Press, New York.\ \

   Dimitri P.\ Bertsekas, {\it Dynamic Programming: Deterministic and Stochastic Models,\/} ISBN 0-13-221581-0, Prentice-Hall.\ \

   George L.\ Nemhauser, {\it Dynamic Programming,\/} ISBN 0-471-63150-7, John Wiley and Sons, New York\ \

   E.\ B.\ Dynkin and A.\ A.\ Yushkevich, {\it Controlled Markov Processes,\/} ISBN 0-387-90387-9, Springer-Verlag, Berlin.\ \

   Wendell H.\ Fleming and Raymond W.\ Rishel, {\it Deterministic and Stochastic Optimal Control,\/} ISBN 0-387-90155-8, Springer-Verlag, Berlin.\ \

   Michael Athans and Peter L.\ Falb, {\it Optimal Control:\ \ An Introduction to the Theory and Its Applications,\/} McGraw-Hill Book Company, New York.\ \

   Dimitri P.\ Bertsekas and Steven E.\ Shreve, {\it Stochastic Optimal Control: The Discrete Time Case,\/} ISBN 0-12-093260-1, Academic Press, New York.\ \

   E.\ B.\ Lee and L.\ Markus, {\it Foundations of Optimal Control Theory,\/} ISBN 0471-52263-5, John Wiley, New York,

   Show morethread
4. graycatAug 2021
   Here are some references for Markov decision theory, stochastic optimal control, stochastic dynamic programming:

   Dimitri P. Bertsekas, Dynamic Programming: Deterministic and Stochastic Models.

   George L. Nemhauser, Dynamic Programming.

   Stuart E. Dreyfus and Averill M. Law, The Art and Theory of Dynamic Programming.

   E. B. Dynkin and A. A. Yushkevich, Controlled Markov Processes.

   Wendell H. Fleming and Raymond W. Rishel, Deterministic and Stochastic Optimal Control.

   There is more from R. T. Rockafellar and R. J.-B. Wets.

   And of course we should mention R. Bellman.

   IIRC, Dreyfus was a Bellman student, and Dynkin's dissertation advisors were Gelfand and Kolmogorov.

   Show morethread
5. graycatSep 2018
   Start with books on dynamic programming, discrete time, discrete space space, no uncertainty. There's a nice one by Dreyfus and Law, The Art and Theory of Dynamic Programming that also gets into the stochastic case. It's called dynamic programming because the program, that is, the planning, changes dynamically over time as learn more and more as time passes.

   D&L show a nice result that could be used for some first cut approximations: If are minimizing a quadratic cost, if the algebraic expressions in that spreadsheet I mentioned are all linear, and if the randomness is all just Gaussian, then get "certainty equivalence" -- that is, get to f'get about the Gaussian, random, stochastic part and use just the expectations themselves. Huge speedup.

   For more, there is Dynkin and Yushkevich, Controlled Markov Processes -- one of the key assumptions that permits treating the spreadsheet columns one at a time is that the stochastic part obeys a Markov assumption (the past and future are conditionally independent given the present).

   There is, from MIT and CMU,

   Dimitri P. Bertsekas and Steven E. Shreve, Stochastic Optimal Control: The Discrete Time Case.

   And there is

   Wendell H. Fleming and Raymond W. Rishel, Deterministic and Stochastic Optimal Control.

   There are papers by R. Rockafellar, long at U. Washington.

   There is now an ambitious program at Princeton in the department of Operations Research and Financial Engineering.

   I tried to get IBM's Watson lab interested; by now they would have been nicely ahead. The guys I was working for wanted me to do software architecture for the OSI/ISO CMIS/P data standards. Garbage direction. A really big mistake for Big Blue, not so big now.

   One of the reasons for IBM to have done SOC was that they had some vector hardware instructions, that is, that would do an inner product, that is, for positive integer n, given arrays A and B, each of length n, find the sum, i = 1, 2, ..., n of

        A(i)*B(i).  
   

   Well inevitably work in probability does a LOT of this. So, if thinking about hardware instructions for SOC, such a vector instruction would be one of the first features. Then maybe more for neural net approximations to some big tables of several dimensions, e.g., computer language arrays A(m, n, p, q) for 4 dimensions but in practice several more. And multivariate splines can play a role.

   Commonly can get some nice gains by finding non-inferior points -- so will want some fast ways to work with those. The software for my dissertation did that; got a speedup of maybe 100:1; on large problems, commonly could get much more.

   There is some compiling that can get some big gains -- some of the big gains I got were from just my doing the compiling by hand, but what I did could be a feature in a compiler -- there's likely still a stream of publications there if anyone is interested in publications (my interests are in business, the money making kind, now my startup).

   There is a cute trick if, say, all the spreadsheet column logic is the same -- can "double up on number of stages".

   There are lots of speedup techniques known. A big theme will be various approximations.

   If there's an opportunity to exploit sufficient statistics, then that could yield big speedups and shouldn't be missed. Having the compiling, sufficient statistics, and non-inferior exploitation all work together could yield big gains -- that should all be compiled. Get some papers out of that! No doubt similarly for other speedups.

   There's lots to be done.

   Show morethread
6. graycatMay 2018
   So, the OP has:

   > Dynamic Programming – 7 Steps to Solve any DP Interview Problem

   Here I see "any"!!!

   Dynamic programming is a huge field from work of R. Bellman, G. Nemhauser, R. Rockafellar, R. Wetts, D. Bertsekas, E. Dynkin, W. Fleming, S. Shreve, and more.

   E.g., there is, with TeX markup,

   Stuart E.\ Dreyfus and Averill M.\ Law, {\it The Art and Theory of Dynamic Programming,\/} ISBN 0-12-221860-4, Academic Press, New York, 1977.\ \

   Dimitri P.\ Bertsekas, {\it Dynamic Programming: Deterministic and Stochastic Models,\/} ISBN 0-13-221581-0, Prentice-Hall, Englewood Cliffs, NJ, 1987.\ \

   George L.\ Nemhauser, {\it Dynamic Programming,\/} ISBN 0-471-63150-7, John Wiley and Sons, New York, 1966.\ \

   E.\ B.\ Dynkin and A.\ A.\ Yushkevich, {\it Controlled Markov Processes,\/} ISBN 0-387-90387-9, Springer-Verlag, Berlin, 1979.\ \

   Dimitri P.\ Bertsekas and Steven E.\ Shreve, {\it Stochastic Optimal Control: The Discrete Time Case,\/} ISBN 0-12-093260-1, Academic Press, New York, 1978.\ \

   Wendell H.\ Fleming and Raymond W.\ Rishel, {\it Deterministic and Stochastic Optimal Control,\/} ISBN 0-387-90155-8, Springer-Verlag, Berlin, 1979.\ \

   some of my work, etc.

   Dynamic programming has been and is a major interest of the Department of Operations Research and Financial Engineering (ORFE) at Princeton.

   Uh, "any" seems a bit optimistic!

   Show morethread