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.