Generating a discretized state space for an MDP (Markov Decision Process) model seems to suffer from the curse of dimensionality.

Supposed my state has a few simple features:

  • Feeling: Happy/Neutral/Sad
  • Feeling: Hungry/Neither/Full
  • Food left: Lots/Some/Low/Empty
  • Time of day: Morning/Afternoon/Evening/Night
  • Located: Home/Work/Library/Shops
  • Money in wallet: \$0, \$0-\$50, \$51-\$200, \$200-\$1000, \$1000+

This is a relatively compact set of information however since the number of states multiplies out, the corresponding MDP state space is 3 x 3 x 4 x 4 x 4 x 5 = 2880.

For a non-trivial problem with a greater number of choices per factor, the state space quickly becomes unmanageably large.

It seems to me that the usefulness of MDPs with large complex problems would be very limited.

Is that the case, or are there ways of keeping the state space manageable for more complex problems?

In general, what is a manageable number of states for an MDP to have, considering the need to generate the transition matrix and reward matrix?


1 Answer 1


tl:dr Read chapter 9 of an Introduction of Reinforcement Learning

There is definitely a problem (a curse if you will) when the dimensionality of a task (MDP) grows. For fun, lets extend your problem to a much harder case, continuous variables, and see how we deal with it.

Mood: range [-1, 1]   // 1 is Happy, 0 is Neutral, -1 is Sad

Hunger: range [0, 1]  // 0 is Very Hungry, 1 is Full

Food: range [0, 100] // amount of food, capping at 100 for numbers sake

Time of day: [0, 23] // Hours, 9.5 would be 9:30 am

Position x: range [-10, 10] // assuming the area the agent stays in is 10x10 km

Position y: range [-10, 10]

Money: range [0, 2000]

Now its impossible to even count the number of states the agent could be in. An example of one state would be:

Mood, Hunger, Food, Time, PosX, PosY, Money
.5, .3, 67.4, 4.5, 0, 0, 5

This would mean that our agent has a neutral mood, is kind of hungry, has 67.4% food, the time is 4:30 am, they are in the center of the city (0,0), and have 5 dollars. Which has happened to me once or twice before too so this is reasonable. If we we still wanted to generate a transition matrix and a reward matrix we would have to represent this state uniquely from other possibly similar states such as if the time was 5 pm with all other things equal.

So now how would we approach this? First lets discretize or breakup each range into little chunks. Then we could have an array of 0s representing our chunks and assign a 1 to the index of the chunk we are in. Lets call this array our feature array. If we did this for each dimension of our state information, we would end up with some state similar to what you originally proposed. I've chosen some arbitrary numbers to break up the state space and lets see what it does to the example state.

If we broke the Mood range up into 8 chunks of .25 we would have these ranges:

m = Mood

  1. -1.0 ≤ m < -.75

  2. -.75 ≤ m < -.50

  3. -.50 ≤ m < -.25

  4. -.25 ≤ m < 0.0

  5. 0.0 ≤ m < .25

  6. .25 ≤ m < .50

  7. .50 ≤ m < .75

  8. .75 ≤ m < 1.0

If we took the mood from the example state (.5), it would land in the 7th range, so then our feature vector for mood would look like:

[0,0,0,0,0,0,1,0] <- represents a mood of .5

Lets do the same for hunger by splitting it into 8 chunks of .125:

[0,0,1,0,0,0,0,0] <- represents a hunger of .3

We could then do something similar for each other state variable and break each state variable's range up into 8 chunks of equal sizes as well. Then after calculating their feature vectors, we would concatenate them all together and have a feature vector that is 56 elements long (7 state variables * 8 chunks each).

Although this would give us 2^56 different combinations of feature vectors, it actually doesn't represent what we wanted to represent. We need features that activate (are 1) when events happen together. We need a feature that is 1 when we are hungry AND when we have food. We could do this by doing a cross product of our 56 element feature vector with itself.

Now we have a 3136 element feature vector that has features like: 1 if its 3pm and am happy 1 if am full and out of food 1 if at coordinate -3, 4 (Position x, Position y)

This is a step in the right direction but still isn't enough to represent or original example state. So lets keep going with the cross products!

If we do 6 cross products we would have 30,840,979,456 features and only 1 of them would be on when our agent has a neutral mood, is kind of hungry, has 67.4% food, the time is 4:30 am, they are in the center of the city (0,0), and have 5 dollars.

At this point you are probably like "Well.. thats a bit much", to which I would agree. This would be the curse of dimensionality, and is the reason transition tables stop being fun (if they ever were).

Instead lets take a different approach, rather than trying to represent an individual state with an individual feature and saying whether that feature is good, lets go back to our nice 56 element feature vector. From here lets instead give a weight (w_i) to each of our 56 features. We have now entered the world of linear function approximation. Although I could explain it here, I think its better explained in Chapter 9 of the Introduction of Reinforcement Learning.


You must log in to answer this question.