Is there a general framework for recognition and representation of states in markov decision process?

Let's say, I want to train an agent to play tic-tac-toe and I use simple Q-learning and $\epsilon$-greedy policy to find the optimal Q-function.

I would proceed like this:

  • Let $\mathbb{S}$ be a set of all possible states and $\forall s \in S: s = (s_1, \ldots , s_n) $ and $ s_i \in \mathbb{R}$
  • Define hash function $F:\mathbb{S}\longrightarrow \mathbb{N}$ as an injective function.
  • Use values of $F$ as links to Q-table with estimates of Q-function

Now this attitude seems quite clumsy, since the hash function for more complex or more dimensional state spaces could be pretty difficult to write. Also it could be difficult to ensure that the function be injective.

So my question is: Is there a better way to store list of states other than in integer form? Can I avoid converting the state of the board through some hash function to a unique integer code? Is there an overview of state recognition and representation methods with advantages and drawbacks of them?

Edit: The question is meant to be about general methodology of state representation. Specific implementations of different languages are not the subject of interest.

  • 1
    $\begingroup$ If this is for an implementation in a specific language, it might be worth adding that. Most high-level languages have a built in hash or dictionary data type that will handle keying the table direct from a string or vector representation of your state. Most low-level languages will have a library to do the same. You would typically only get into defining hash functions yourself for efficiency. In addition, many problems (but not tic-tac-toe of course) are too large to apply tabular Q-learning, and hashing algorithms generally won't help with function approximation, you want feature vectors. $\endgroup$ – Neil Slater Sep 1 '17 at 16:40
  • $\begingroup$ @NeilSlater Thank you. I understand, that hashing would not help me, if the Tic-Tac-Toe would be say 10X10 board, which would yield 3^100 states (many of them impossible though). Regarding the feature vectors for the specific case of 10X10 TTT game, would using linear estimation with 100 "dummy" features (0,1,2 for nothing, X, O) help me in any way with value function approximation, or would it be necessary to do some sort of coarse coding? Maybe, I should write a separate question just for the value approximation in the TTT game, since this is what I am trying to do anyways. $\endgroup$ – Jan Vainer Sep 1 '17 at 17:31
  • $\begingroup$ I cannot really answer in a comment. But course coding is often used for continuous state variables, so I would not initially try it for a larger TTT board. Probably I would start with a vector of 100 $\{-1,0,1\}$ values, although that would not be good for a linear function approximator, so you might want to get into some feature engineering, because linear approximators in RL are better understood and more stable $\endgroup$ – Neil Slater Sep 1 '17 at 18:10
  • $\begingroup$ @NeilSlater Feature engineering is a new term to me. I will definitelly check it out. $\endgroup$ – Jan Vainer Sep 1 '17 at 21:25
  • $\begingroup$ It just means figuring out a good representation, by applying your knowledge of the problem and/or trial and error. $\endgroup$ – Neil Slater Sep 1 '17 at 21:29

You can easily use multi-level indexing that may capture your problem more naturally. This is implemented in standard libraries such as pandas in python.

| cite | improve this answer | |

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.