# Representing state in Q-Learning

I have a fairly simple game in which I wish to use Q-learning to train an agent, but I have some questions regarding state representation. I'm new to RL so bare with me:

If you have a game where you and your enemy each have 3 players, each player has health and a location on a 10 x 10 grid. My understanding is that you would need to enumerate all possible states for this game in order to successfully implement Q-learning. How would this be done? If we forget about health for a second and we look at position alone, we have 6 players, each of which could be in any of the 100 locations so our state space for position alone would be 100^6. This seems like an exceptionally large matrix to be working with, and we haven'y even added a parameter for health. What am I missing? is this the point at which you look for alternative state representations?

Some guidance or links to relevant articles would be greatly appreciated. Thanks!

If we forget about health for a second and we look at position alone, we have 6 players, each of which could be in any of the 100 locations so our state space for position alone would be 100^6.

Yes, that is correct, adding health in, and assuming it was an integer from 1 to 20, then you would have $$20^6 \times 100^6$$ discrete states.

My understanding is that you would need to enumerate all possible states for this game in order to successfully implement Q-learning. How would this be done?

For the enumerated case with enough resources, there is a theoretical guarantee that Q learning (and other RL methods) will converge on the optimal result. However, in this case - and many others - there are clearly too many states to calculate or store values for in detail. So the answer is that you don't do that. Instead you need look into ways to calculate approximate calculating action values which you hope will also generalise to previously unseen state/action pairs, at the very least to unseen states and actions that are relevant in real games.

There are many ways to structure the state and action representations to help with approximation in RL. Sutton & Barto's Reinforcement Learning: An Introduction dedicates the whole of the second (of three) sections to approximation in general, and chapter 9 part 5 reviews some popular approaches to representations that work well with simpler linear function approximation.

This kind of approximation is also the main driver behind "Deep" Q-learning (DQN), which is essentially Q-learning with a neural network approximating the action value table. There are some details to add to get this to work well - but plenty of resources available to help with this on the internet: Tutorials, examples and fully coded agents ready to set up and solve problems.

So I would recommend moving to DQN when the state/action space gets too large for a simple tabular approach, and where it is not clear what other simpler approximation could get the job done more efficiently. If you do that, then the state and action representation becomes what will work as inputs to a neural network. There are some rules to follow for that. First, all inputs should be on a suitable scale. Neural networks like to work with inputs with mean 0, standard deviation 1 over the sample population. Often you don't know that for a RL problem, so you can go to the next best thing - scaling to fit in a range such as 0..1 or -1..1

I have also written an answer covering approaches to choices in state representation and feature engineering for another problem Reinforcement learning: easily learnable state representation which might help.

• Nice answer, but it would profit a lot from an example for problem given by OP. – hans May 8 '19 at 6:38