Dynamic programming approach for multidimensional problem

Question

I use a dynamic programming approach to optimize the behaviour of individuals playing a game.I have one strategy matrix that describes the behaviour of individuals in situation 1, which depends on some state variables. Now suppose I would like to add a situation 2. Then I would basically two strategy matrices at the same time which I am trying to optimize. What algorithms I should use for this multidimensional optimization case and can you give me any references for examples?

Answer 1

Dynamic Programming can be set up in principle to deal with as large (high a dimension) state space as needed. But there is something called the curse of dimensionality which strikes Dynamic Programming particularly hard as the dimension increases.

The key to Dynamic Programming is judicious definition of the state space. There is a large amount of intuition and art in that. So think through carefully what you need your state space to be. If you have enough (correct) states, then it's straightforward to write out the optimization problems which have to be solved at each stage in the Dynamic Program. If you can't write out the optimization problem at each stage, it may indicate your state space is inadequate. It may not be so straightforward to actually solve them quickly, however.

Generally state spaces which are just big enough are the best, although not necessarily. However, if you are having trouble, it may help if you start with a bigger than needed state space, and once you have that set up, see if you can be more clever and pare back the dimension of the state space.

I leave the definition of the state space as an exercise to you.