Are there any guidelines on how to map the state space to integers in the case tabular RL algorithms?

Question

Let's say that you want to solve a problem with a tabular reinforcement learning algorithm, for example, Q-learning. You can represent the value function $Q(s, a)$ as a $|\mathcal{S}|\times |\mathcal{A}|$ matrix. In practice, we could use an array to represent $Q$. To index this array, you need integers, unless you use e.g. hash maps or another data structure. Let's call the (NumPy) array Q, then Q[i, j] would be the value of action j at state s.

My question is: are there any guidelines on how to map the state space to integers, so that we can index our table? In the case of a grid environment, you can try to enumerate all possible states and use some convention to map a state to an integer. However, in more complex environments, this might not be straightforward. Do you know any other ways to try to solve this implementation problem?

Note that this is a design/implementation question rather than a programming issue. I am looking for guidelines or common practices (other than the one that I mentioned). Feel free to share with me examples of how this has been done in other projects/environments (links to the projects/repos are also appreciated).

Answer 1

It's hard to prove a negative, but I don't think there are any special considerations for reinforcement learning (RL) when enumerating and tabulating discrete states and actions. Instead, this is a computer science data structures issue. Depending on the problem at hand, it could be easy or hard to map states to something concise and useful. Unless there are hard constraints on the available memory or CPU, then it is common to pick a simple solution that fits into available RAM.

One important detail is that with tabular learning there is no meaning to records being adjacent or close. All Q values are completely independent. Which means that any map to a position in a table can be completely arbitrary. This is true even if your tabular states are a discretised approximation to a larger state space (although how you perform that discretisation is important - you should make some effort to group states with similar expected returns and next states). Which in turn means the primary concerns are:

• Compactness. The state ids should ideally be short, and also the table of all states should not be wasteful.

• Simplicity. Ideally the conversion between observable/usable state information for the environment to process actions, and the storage format for the table should not be taxing so that it takes lots of effort to code it.

• Speed. Related to simplicity, but sometimes at odds with it, both converting the state to a table entry and accessing the table entry should be fast so that the machinery of RL is not a limiting factor when running the agent.

These three concerns interact, so you may need to compromise. Multi-dimensional arrays are faster and more compact in general than dictionaries/hashes, so it is common to use over-specified integer states, provided there are not too many wasted indices.

In examples in literature, you will commonly find:

• Converting state representation into an integer, either using binary digits, decimal digits, or a "flattened index" (e.g. if state consists of 3 different traits A, B, C which can be enumerated as A $\in$ [0,5], B $\in$ [0,3], C $\in$ [0,7], then create a state_id = A + B * 6 + C * 24)

  • In the example, B is multiplied by the length of A, so that any allowed combination of A and B is a unique numer, without gaps. Then C is multiplied by the product of sizes of A and B for the same reason. Many implementations of multi-dimensional arrays do this internally (although they might start with C as opposed to A).
  • You could also implement the Q table itself with more dimensions, effectively having NumPy (or whatever) do the calculation for you. So you would use e.g. Q[A, B, C, action].

• Concatenate state traits into a string or binary representation, and use that as a key to a hash/dictionary structure.

You can combine the two methods. If there would be lots of gaps of unreachable states from a numerical state id, then you may still prefer to use a dictionary for compactness. Integer keys to hashes may be faster to process and take less memory than string keys.

There are also other structures, such as tries, that may be more efficient for certain kinds of state representation. However, on a modern CPU, if you need extra efficiency to represent a tabular action value function, you may be hitting the size of problem where the speed improvement of generalisation from some kind of function approximation is more desirable than attempting to solve the MDP perfectly by visiting all state/action combinations exhaustively.