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.
Looked at APL long ago. My guess is that since it is interpretive it would be too slow. I wrote my dissertation code in just quite portable Fortran.
As I suggested, I do believe that some progress in execution time could be had from some new machine instructions, new language features to use those instructions, and some compiling help. For the compiling part, the language would have some well defined semantics the compiler could exploit. E.g., for something simple, the semantics could let the compiler exploit the idea of non-inferior sets.
E.g., say have 100,000 points in 2-space. Say, just for intuitive visualization, plot them on a standard X-Y coordinate system. Say that the X coordinate is time and the Y direction is fuel. Part of the work is to minimize the cost of time and fuel. At this point in the computation, we don't know how the costs of time and fuel trade off, but we do know that with time held constant, less fuel saves cost, and with fuel held constant, less time saves cost.
So, in the plot of the 100,000 options, we look at the lower left, that is, the south-west parts of the 100,000 points.
Point (X2,Y2) is inferior to point (X1,Y1) if X1 <= X2 and Y1 <= Y2. That is, point (X2,Y2) is just equal to point (X1,Y1) or is to the upper right, north east of (X1,Y1). If point (X1,Y1) is not inferior to any other of the 100,000 points, then point (X1,Y1) is non-inferior.
So, there in the work, can just discard and ignore all the inferior points and work only with the non-inferior points. May have only 100 non-inferior points. Then, presto, bingo, just saved a factor of 1000 in the work. Okay, have sufficiently restricted programming language semantics that the compiler could figure out all that and take advantage of it. When I wrote my code in Fortran, I had to write and call a subroutine to find the non-inferior points -- bummer, that work should be automated in the compiler, but to do that the compiler will need some help from some semantic guarantees.
The above is for just two dimensions, but in practice might have a dozen or more. So, what's the fast way with algorithms, programming language semantics, and hardware to find the non-inferior points for a dozen dimensions?
Non-inferior points are simple -- lots more is possible.
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
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.