1
$\begingroup$

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?).

$\endgroup$
0
$\begingroup$

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 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.

$\endgroup$
1
  • $\begingroup$ Thank you, it works $\endgroup$ – Geperd Mar 12 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.