# Why do terms in the computation of state space size scale exponentially?

The image below is from a Berkeley AI course pdf I found.

My question is, why do the terms accounting for the ghosts and pellets come in raised to the number of units?

For example, there are two ghosts so the exponent is 2, there are 30 foods so the exponent is 30.

Intuitively, I feel like if there are 30 foods, each with 2 states, then that is 60 states, no $$2^{30}$$.

New contributor
user1029384756 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

Intuitively, I feel like if there are 30 foods, each with 2 states, then that is 60 states, no $$2^{30}$$.

Let's try it with 3 pellets. If you are right there would be $$2 \times 3 = 6$$ states, if the authors are right there would be $$2^3 = 8$$ states.

Using * for a pellet, and - for a space, we have the following states:

1. * * *
2. * * -
3. * - *
4. * - -
5. - * *
6. - * -
7. - - *
8. - - -

That's 8 states. The authors are correct.

In this case, intuitively the state is essentially one long 30-bit number - you can replace pellets with 1 and spaces with 0. In general, the rule is that if some component of the state can vary into $$n$$ different sub-states independently of other components, then the size of the whole state space multiplies by $$n$$.

There is a slight oversimplification, in that the pacman might not be able eat the pellets arbitrarily (although in the example given it looks like they can). Some states might not be reachable. However, trying to figure out all the reachable states and enumerate them in a useful way so that there is still a simple vector model to learn from would be complicated - possibly more complicated than solving the reinforcement learning problem for the same game. It is easier to simplify the state representation and have a larger overspecified state space.

• Wonderful. Thank you for the explanation. I have accepted the answer. Jan 13 at 22:43