Answers.Body: <blockquote>
  <p>Intuitively, I feel like if there are 30 foods, each with 2 states, then that is 60 states, no <span class="math-container">$2^{30}$</span>.</p>
  </blockquote>
  <p>Let's try it with 3 pellets. If you are right there would be <span class="math-container">$2 \times 3 = 6$</span> states, if the authors are right there would be <span class="math-container">$2^3 = 8$</span> states.</p>
  <p>Using <code>*</code> for a pellet, and <code>-</code> for a space, we have the following states:</p>
  <ol>
  <li><code>* * *</code></li>
  <li><code>* * -</code></li>
  <li><code>* - *</code></li>
  <li><code>* - -</code></li>
  <li><code>- * *</code></li>
  <li><code>- * -</code></li>
  <li><code>- - *</code></li>
  <li><code>- - -</code></li>
  </ol>
  <p>That's 8 states. The authors are correct.</p>
  <p>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 <span class="math-container">$n$</span> different sub-states independently of other components, then the size of the whole state space multiplies by <span class="math-container">$n$</span>.</p>
  <p>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 <em>reachable</em> 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-13T20:48:28.723Z
Answers.LastActivityDate: 2022-01-14T13:25:33.613Z
Answers.LastEditDate: 2022-01-14T13:25:33.613Z
Answers.UserDisplayName: Neil Slater
Body: <p>The image below is from <a href="https://inst.eecs.berkeley.edu/%7Ecs188/fa18/assets/notes/n1.pdf" rel="nofollow noreferrer">a Berkeley AI course pdf I found</a>.</p>
  <p><a href="https://i.sstatic.net/lFwR5.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/lFwR5.png" alt="enter image description here" /></a></p>
  <p>My question is, why do the terms accounting for the ghosts and pellets come in raised to the number of units?</p>
  <p>For example, there are two ghosts so the exponent is 2, there are 30 foods so the exponent is 30.</p>
  <p>Intuitively, I feel like if there are 30 foods, each with 2 states, then that is 60 states, no <span class="math-container">$2^{30}$</span>.</p>
  
Tags: <machine-learning><reinforcement-learning><state-spaces>
Title: Why do terms in the computation of state space size scale exponentially?
UserDisplayName: user1029384756
ThreadText: # Why do terms in the computation of state space size scale exponentially?
  
  (Asked by: username_0 on 2022-01-13)
  
  The image below is from [a Berkeley AI course pdf I found](https://inst.eecs.berkeley.edu/%7Ecs188/fa18/assets/notes/n1.pdf).
  
  [![enter image description here](https://i.sstatic.net/lFwR5.png)](https://i.sstatic.net/lFwR5.png)
  
  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}$.
  
  **Tags:** machine-learning, reinforcement-learning, state-spaces
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-01-13. Score: 1 | Accepted answer
  
  > 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.
  
  
  ---
  
  