# How to solve Stochastic Dynamic Program with huge state space?

I am modelling a stochastic dynamic program but because I need to store all information related to former sales, the state of the dynamic program increases and potentially it can growth so much which results in curse-of-dimensionality. I am wondering if there is any general trick to convert it to a Markovian model? If not, is this model valuable to publish a paper in a top-tier journal (just based on modelling and solving appraoch)? What are the general approaches to handle this growing state space?

• Look into "Approximate Dynamic Programming." Sep 22 at 11:08

Just to expand very slightly the comments by Mark: in general exact stochastic dynamic programming scales quite poorly.

Value iteration complexity for each iteration is $$O(A S^2)$$ where $$A$$ is the number of actions and $$S$$ is the number of states. And the number of iterations goes up with the discount factor $$\beta$$ as the worse case number of iterations is $$\frac{1}{1-\beta} \log \left( \frac{1}{1-\beta} \right)$$;

see Littman, M. L., Dean, T. L., & Kaelbling, L. P. (1995). On the complexity of solving Markov decision problems. In Proceedings of the Eleventh conference on Uncertainty in artificial intelligence (pp. 394–402).

So basically what you want is to reduce the number of states. The way "reinforcement learning"/"Approximate Dynamic Programming" goes about it is to basically substitute the problem of computing the Q-table $$Q(s,a)$$ with some statistical approximation (for example, you summarise any state $$s$$ through some features $$f(\cdot)$$ and then the value of that state is just a linear combination $$Q(s,a) = w_1 f_1(s) + w_2 f_2(s) + \dots + w_n f_n(s)$$ ).
Of course you are now stuck with the training problem, but it is usually much easier to scale.

• Thank you so much. One case where the curse of dimensionality happens is when the possible values of $S$ increase and can go to infinity. For example, the Inventory level can go to infinity if we don't have any capacity and in this situation, a function approximation works. But, it is in a form of $s \in R$ or $(s_1,s_2) \in R^2$. I am wondering how to model a case when information is gathered over time because in this case, it is possible to store information in a tuple with a fixed length. For example, we need to record inventory level, information related to first, second, .... customers. Sep 24 at 18:09
• Yes, "information gathered" is usually folded as part of the state of the world and as such you need to manage it carefully and try to summarize it too like you are suggesting. Old-fashioned way is simply to discretize (for example "high inventory vs low inventory") but I guess if the data is really abundant (or it is simulated fast enough) you are better off using a non-linear regression to try and come up on its own with a good way to predict the value of state-action pairs you are considering. I mean, look at the zero go paper: very few features were used to become superhuman! Sep 24 at 19:41
• Ooo. Sorry I had a typo. When we have new information and store then as our state, then, it is Not possible to store them in a tuple with a fixed length. For example, in period 1, we have one customer, period 2, we have 2 customers and in period n, we have n customers. So, the size of the tuple changes over time and it gets larger and larger. How do you use approximation models when the state variables size gets bigger? Suppose it is not possible to compact all information to convert it to an MDP. Sep 30 at 21:00
• I am wondering if I wanna use regression for approximation, how should I map the increasing state to a model? I would be thankful if you can share a paper that has modelled something similar. Sep 30 at 21:00