Answers.Body: <blockquote>
  <p>It seems to fail if a variable is not a power of two (bonus question: why doesn't it work?).</p>
  </blockquote>
  <p>This does not work because you are wasting some space, some values are not used in your representation.</p>
  <p>For example with your 0-4 variables, you need 3 bits, but you only use <code>000</code>, <code>001</code>, <code>010</code>, <code>011</code> and <code>100</code> values. The values <code>101</code>, <code>110</code> and <code>111</code> are still part of the representation you are using. It doesn't matter that you don't need to use them, you have created a representation where they exist. Every time you encode 5 values as 3 bits, you are being 62.5% efficient, and the efficiencies <em>multiply</em> to get the overall efficiency of your representation (proportion of states you need to represent compared to the size of the representation).</p>
  <p>Sometimes this is acceptable. Your example state representation using bitwise coding per variable would still fit easily into a 32 bit integer for storage, and you also have the convenience of easily extracting the individual values quickly using bit masks. It's a bit less convenient if you were hoping to build a Q table as an array with the state as a simple offset.</p>
  <p>In your example case it is not super-wasteful, your array will be around 4 times larger than optimal due to wastage in 3 separate places. For convenience of coding simplicity you might accept this 8MB space per action over 2MB space per action (assuming 32 bit floating point values for action values). 6MB of dead space is not much to worry about - the chances are that the programming language you have loaded to run it wastes far more space on features that you are not using.</p>
  <p>If you have a few more variables and a few more wasted bit patterns, then the waste could be more noticeable and important. That might also be true if you are using a space-efficient compiled language on a system where memory resources are low.</p>
  <blockquote>
  <p>Let's say in my problem there are following variables which i'm using to compute state . . . So the state space is equal to 64000 (4 * 4 * 4 * 2 * 2 * 5 * 5 * 5 * 2)</p>
  </blockquote>
  <p>You are very close to a working answer for the most efficient representation here. You can use products of each variable's size to separate terms, to create multiplication factors for each variable. Imagine building up a cuboid out of the first three terms, and needing to address each cubic building block sequentially with an index position <span class="math-container">$i$</span>. You would do this:</p>
  <p><span class="math-container">$$i = x + 4y + (4 \times 4)d = x + 4y + 16d$$</span></p>
  <p>If you had only thie first 5 variables you would do this:</p>
  <p><span class="math-container">$$i = x + 4y + (4 \times 4)d + (4 \times 4 \times 4)g + (4 \times 4 \times 4 \times 2)a = x + 4y + 16d + 64g + 128a$$</span></p>
  <p>To cover your whole set of variables, keep extending the same pattern. Each variable added to the end of the list is multiplied by the product of the space required by all previous variables. The last variable in your example, <code>gl</code>, would be multiplied by <span class="math-container">$32000$</span>.</p>
  <p>Reversing this encoding is more involved, especially if you only want to access a single variable. You need to start with the value of <span class="math-container">$i$</span> then repeatedly use an <a href="https://www.w3schools.com/python/ref_func_divmod.asp" rel="nofollow noreferrer">integer divmod operation</a> to find the next unknown variable at the end of the list - using the same multiplier for that variable as when constructing the code - and a remainder for calculating the next variable along.</p>
  <p>Luckily in reinforcement learning you probably don't need to do any reversing of state id to individual variables - you can maintain a structure of all current variables for the state when running the environment, and only need this compressed version to create an offset into the Q table for lookups for the policy or updates to stored values.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-11T22:48:50.977Z
Answers.LastActivityDate: 2021-03-11T23:05:35.883Z
Answers.LastEditDate: 2021-03-11T23:05:35.883Z
Answers.UserDisplayName: Neil Slater
Body: <p>I'm trying to use Q-learning, but I'm stuck because I don't know how to compute the state.</p>
  <p>Let's say, in my problem, there are the following variables, which I'm using to compute state:</p>
  <p><code>x in range 0-3</code><br />
  <code>y in range 0-3</code><br />
  <code>d in range 0-3</code><br />
  <code>g in range 0-1</code><br />
  <code>a in range 0-1</code><br />
  <code>s in range 0-4</code><br />
  <code>br in range 0-4</code><br />
  <code>bu in range 0-4</code><br />
  <code>gl in range 0-1</code></p>
  <p>So, the state space is equal to <span class="math-container">$64000$</span> (<span class="math-container">$4 * 4 * 4 * 2 * 2 * 5 * 5 * 5 * 2$</span>). I'd like to create a number, from the above variables, which is contained in the range <span class="math-container">$[0, 63999]$</span>.</p>
  <p>My previous idea was to create a binary number from the binary representation of state variables (just write them next to each other and convert into an <code>int</code>). It seems to fail if a variable is not a power of two (bonus question: why doesn't it work?).</p>
  
Tags: <reinforcement-learning><q-learning><state-spaces>
Title: Compute state space from variables in Q-learning (RL)
UserDisplayName: Geperd
ThreadText: # Compute state space from variables in Q-learning (RL)
  
  (Asked by: username_0 on 2021-03-11)
  
  I'm trying to use Q-learning, but I'm stuck because I don't know how to compute the state.
  
  Let's say, in my problem, there are the following variables, which I'm using to compute state:
  
  `x in range 0-3`  
  `y in range 0-3`  
  `d in range 0-3`  
  `g in range 0-1`  
  `a in range 0-1`  
  `s in range 0-4`  
  `br in range 0-4`  
  `bu in range 0-4`  
  `gl in range 0-1`
  
  So, the state space is equal to $64000$ ($4 \* 4 \* 4 \* 2 \* 2 \* 5 \* 5 \* 5 \* 2$). I'd like to create a number, from the above variables, which is contained in the range $[0, 63999]$.
  
  My previous idea was to create a binary number from the binary representation of state variables (just write them next to each other and convert into an `int`). It seems to fail if a variable is not a power of two (bonus question: why doesn't it work?).
  
  **Tags:** reinforcement-learning, q-learning, state-spaces
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-03-11. Score: 0 | Accepted answer
  
  > It seems to fail if a variable is not a power of two (bonus question: why doesn't it work?).
  
  This does not work because you are wasting some space, some values are not used in your representation.
  
  For example with your 0-4 variables, you need 3 bits, but you only use `000`, `001`, `010`, `011` and `100` values. The values `101`, `110` and `111` are still part of the representation you are using. It doesn't matter that you don't need to use them, you have created a representation where they exist. Every time you encode 5 values as 3 bits, you are being 62.5% efficient, and the efficiencies *multiply* to get the overall efficiency of your representation (proportion of states you need to represent compared to the size of the representation).
  
  Sometimes this is acceptable. Your example state representation using bitwise coding per variable would still fit easily into a 32 bit integer for storage, and you also have the convenience of easily extracting the individual values quickly using bit masks. It's a bit less convenient if you were hoping to build a Q table as an array with the state as a simple offset.
  
  In your example case it is not super-wasteful, your array will be around 4 times larger than optimal due to wastage in 3 separate places. For convenience of coding simplicity you might accept this 8MB space per action over 2MB space per action (assuming 32 bit floating point values for action values). 6MB of dead space is not much to worry about - the chances are that the programming language you have loaded to run it wastes far more space on features that you are not using.
  
  If you have a few more variables and a few more wasted bit patterns, then the waste could be more noticeable and important. That might also be true if you are using a space-efficient compiled language on a system where memory resources are low.
  
  > Let's say in my problem there are following variables which i'm using to compute state . . . So the state space is equal to 64000 (4 \* 4 \* 4 \* 2 \* 2 \* 5 \* 5 \* 5 \* 2)
  
  You are very close to a working answer for the most efficient representation here. You can use products of each variable's size to separate terms, to create multiplication factors for each variable. Imagine building up a cuboid out of the first three terms, and needing to address each cubic building block sequentially with an index position $i$. You would do this:
  
  $$i = x + 4y + (4 \times 4)d = x + 4y + 16d$$
  
  If you had only thie first 5 variables you would do this:
  
  $$i = x + 4y + (4 \times 4)d + (4 \times 4 \times 4)g + (4 \times 4 \times 4 \times 2)a = x + 4y + 16d + 64g + 128a$$
  
  To cover your whole set of variables, keep extending the same pattern. Each variable added to the end of the list is multiplied by the product of the space required by all previous variables. The last variable in your example, `gl`, would be multiplied by $32000$.
  
  Reversing this encoding is more involved, especially if you only want to access a single variable. You need to start with the value of $i$ then repeatedly use an [integer divmod operation](https://www.w3schools.com/python/ref_func_divmod.asp) to find the next unknown variable at the end of the list - using the same multiplier for that variable as when constructing the code - and a remainder for calculating the next variable along.
  
  Luckily in reinforcement learning you probably don't need to do any reversing of state id to individual variables - you can maintain a structure of all current variables for the state when running the environment, and only need this compressed version to create an offset into the Q table for lookups for the policy or updates to stored values.
  
  
  ---
  
  