I'm having trouble understanding the concept of states in RL.

The Policy maps an action to a state. I'm thinking about the state as clearly defined situation. E.g. in connect four assuming a 8x8 grid, there would be $2^{64}$ possible states. (Actually $3^{64}$ since every field can be red yellow or empty...) Finding a policy for all of those states sure works, but is definitely not RL. This would be memorizing.

How can one imagine a state e.g. in the case of connect four?

More complex RL applications like Mari/o even use CNN. They are observing the game to know which state they're in. Since in this CNN pooling isn't used there will be something like 800x800 RGB pixels... My idea of a state clearly defined by its pixel has definitely to be wrong.

up vote 4 down vote accepted

You are right that the state space is $3^{64}$. If you had a table of $Q$ values for each of these states, that would be valid RL. However, such a large table is probably infeasible to store.

In the "learning from pixels" setting, the state size is $256^{3HW}$, where $H$ and $W$ are the height and width of the display respectively.

In these environments, instead of using a table to map $(s,a)$ pairs to a $q$-value, it is more feasible to find a function $\hat q(s,a; \theta)$ which maps state and action to (an approximated) $q$-value. The parameters $\theta$ of this function can be stored compactly compared to the table you would need.

Also see this question on how CNNs are involved.

  • ou okay... so basically I need generalization in form of some supervised learning, otherwise it ends in memorizing the complete table of states for the game „four connect“? – Mr.Sh4nnon Oct 11 at 15:39
  • 2
    @Mr.Sh4nnon yes, and hopefully your function approximator can generalize from one state to a very similar but not-quite-the-same state, much as the brain can pattern-match against similar previously seen states in order to make quick decisions. – shimao Oct 11 at 15:41
  • wow okay... it more and more looks like RL can be reduced to finding optimal policy and MDPs and the rest is stuff from general machine and deep learning 😅 thank you for the quick precise answer! – Mr.Sh4nnon Oct 11 at 15:43

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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