Name: The art and theory of dynamic programming
ISBN: 9780122218606

What Hacker News says

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,

thread

graycatSep 2022

Just looked at the "Course Description" of the "Syllabus" as at

https://ocw.mit.edu/courses/6-006-introduction-to-algorithms...

The course takes itself very seriously and seems to ask each student to devote a lot of time to the course.

My summary reaction is that it would be a shame to devote that much time to what is basically so little material.

Yes, the "Syllabus" mentions

Introduction to Algorithms, Cormen, Leiserson, Rivest, and Stein, CLRS.

Years ago I downloaded a PDF and didn't see much beyond what I'd gotten from Knuth, etc.

I can give a fast overview here:

There I see their lists of topics:

dynamic arrays, heaps, balanced binary search trees, hash tables

and

sorting, graph searching, dynamic programming

I'm a little surprised at how old these topics are: I first learned several of the topics almost entirely from

Donald E. Knuth, The Art of Computer Programming, Volume 3, Sorting and Searching, 1973.

(1) Dynamic Array

A glance at how it works explains why I never heard of it:

Can see

"Dynamic array"

https://en.wikipedia.org/wiki/Dynamic_array

So, if have an array A and need more space, then allocate a larger array B and copy over the contents of array A to array B and continue with array B.

A guess is that in nearly all cases a better solution would be a tree where the array subscripts are used as keys and the array elements, as leaves.

Maybe the main reason to include dynamic arrays is to do some applied math to analyze by how much bigger array B should be than array A.

(2) Heaps

I like heaps.

At one point in the software of my startup, I have to search through maybe 1 million numbers and end up with the, say, 20 largest. For that I programmed a heap, and it has worked out great.

There are versions of the heap algorithm that are better on locality of reference and when the heap is carried mostly on slow, secondary storage.

(3) Balanced Binary Search Trees

AVL (Adelson-Velskii, Landis) trees are in the Knuth reference, and they are terrific. An alternative is red-black trees. One of those two is likely the key to .NET collection classes, and my startup uses two instances for a simple, light, fast key-value store instead of Redis.

(4) Hash Tables

Those are also in Knuth. Hashing usually leaves me in doubt due to its various possible problems. But better still sometimes is perfect hashing as I recall also in Knuth.

For hashing in general, a good step forward is in

Ronald Fagin, Jurg Nievergelt, Nicholas Pippenger, H. Raymond Strong, Extendible hashing-a fast access method for dynamic files, "ACM Transactions on Database Systems", ISSN 0362-5915, Volume 4, Issue 3, September 1979, Pages: 315 - 344.

We used that in an AI (artificial intelligence) product we shipped.

(5) Sorting

Knuth covers heap sort and shows that it meets the Gleason bound for sorting by comparing pairs of keys.

(6) Graph Searching

Looking at their lecture notes, it appears that they mean versions of shortest paths on networks.

These are all fairly simple except for minimum cost single commodity network flows where each arc has a maximum flow and also a cost per unit of flow. The problem is linear programming, and the classic simplex algorithm applies and takes on an especially simple form -- a basic solution corresponds to a spanning tree of arcs.

Some good news is that if the arc capacities are all integers and if start the algorithm with an integer solution, then the simplex algorithm maintains an integer solution and will terminate with one.

It is tempting to see that "good news" as a case of progress in NP-complete integer linear programming.

For such content, I recommend

Mokhtar S. Bazaraa and John J. Jarvis, Linear Programming and Network Flows, ISBN 0-471-06015-1, John Wiley and Sons, New York, 1977.

(7) Dynamic Programming

That can be a big subject but does not have to be. I got a good introduction from an expert in about 90 seconds while my cab was waiting to take me to the airport. I ended up writing my Ph.D. dissertation in dynamic programming. For an easy introduction, can have fun, like eating from the appetizer plate at Thanksgiving, say, a half hour at a bite from

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

One of the amazing advantages of dynamic programming is how well it handles randomness -- then have stochastic optimal control, Markov decision theory, etc.

The flavor of dynamic programming in computer science can be a bit different, e.g., applied to search for some string A in some string B.

Maybe another purpose of the course is to get everyone all wound up and fired up about the question of

P versus NP

My recommendation is to try quite hard to ignore that question.

thread

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.

thread

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.

thread

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.

thread

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!

thread