This is a question about reinforcement learning with subgoals related to this post:
In the link above, we gave an assumption that a transition probability exists. My question now is therefore:
What if we do not need to learn the transition probabilities? We want to learn the Q values (say for Q learning or for SARSA) so that we can eventually learn the optimal policy. How will the current state representation ensure that learning will take place if a reward will only be given in the end?
We start at the state S and the aim is to finish in goal state G by visiting states 1, 2, 3, 4 sequentially. So, we can write the state like this: $(x,y,m)$. $x,y$ will be row and column number of the box (like coordinates). $m$ will be from 0 to 4, as it visits the numbered states sequentially. (top left corner would be $(1,1)$.)
Hence, the desired order would something be like $(5,1,0) \rightarrow (4,5,1) \rightarrow (2,2,2) \cdots (1,5,4)$. The last being the position of the goal, but only after passing through 4.
If reward can only be given when reaching the final state, and $-1$ is given as a penalty for each time step, how will this kind of state representation reinforce the good habit of passing through numbered states sequentially? Would it be necessary to put rewards for each time you get to a numbered state in order?