Formulation of states for this RL problem and other questions.

Consider a gridworld 100 $\times$ 100 with a starting position, $S$, on the lower left corner and a goal position, $G$, somewhere at the center. Both $S$ and $G$ are fixed and does not move.

Furthermore, subgoals exist one at a time. For example, '1' appears in a random position. If '1' is reached, then '2' appears and so on. The succeeding numbers appear randomly but will have a distance closer and closer to the final goal $G$. The transition probability is not available and will not be learned, so model free learning will be used.

Agent can move in 4 cardinal directions.

I have many serious questions:

1. What could be a nice state space representation for this? The fact that it is 100 $\times$ 100 means that I am avoiding the usual $(x,y)$ 'coordinate' position or the cardinality of the state space will be so big.

My idea would be to choose the 'relative' position between the agent and the goal. Something like: $(x,y)$, $x = \{ -1, 0, 1\}$. $-1$ if the goal is to the left of the agent, 1 if the goal is to the right, and 0 if the goal is at the same $x$ coordinate as the agent. $y = \{ -1,0,1\}$, $-1$ if the goal is below, $1$ if above the agent. 0 if they the same $y-$coordinate.

So maybe the state space formulation can follow this form found here:

Model free reinforcement learning with subgoals: how to reinforce learning with only one reward?

$(x,y,k)$ where $k$ is the number subgoal attained?

1. Is this a tractable problem? I mean, I understand that this may have been poorly written, but I want to share my intuition. The number of subgoals that I have here might not be known apriori. But they are definitely going nearer and nearer to the goal position.

Is there a way to write the states to include the subgoal positions without giving multiple rewards? I thought about giving multiple rewards to the agent after getting each subgoal, but that would be 'cheating'. I believe it is standard in RL that the reward is given at the end of the task.

I would some your valued insights into this problem. Feel free to send comments or more questions if there are any.

• Is there a particular reason that the coordinate representation is too big? Aug 16 '16 at 20:19
• On second read, it's really not clear what the point of all this is. Sure, you can reduce the state space to just position relative to the goal and subgoal, but then why not just handcraft a policy? Aug 16 '16 at 22:24
• Since the gridworld does not change after collecting a subgoal, I wonder whether it is more efficient to learn all shortest paths beforehand (using RL or Floyd–Warshall algorithm or A*, although the latter ones contradict the demonstrational purpose of gridworlds, right ?) and then just apply them successively or learning Q(.) for each subgoal respectively, but then for a lesser number of paths. Learning all shortest paths via RL could be done by updating all Q(.) for all starting points in parallel. Aug 17 '16 at 12:35
• @steffen Exactly. We don't really use reinforcement learning on gridworlds because they're the best method for the problem; we use gridworlds to benchmark RL methods because they're straightforward as a toy problem. If we wanted to speed Q-learning on this, we could just initialize Q, say to something like inverse Manhattan distance to the nearest subgoal. I wonder whether the OP is interested out of general RL curiosity, or because gridworld is a useful abstraction for a more practical problem. Aug 17 '16 at 14:06
• @SeanEaster Yes, the coordinate representation is intentionally big so that I will not have to use the 'coordinate positions' $(x,y)$, or resort to using linear functional approximations. By saying this, I want to keep my state representation as 'simple' as I can, taking in as much information as I can.
– cgo
Aug 23 '16 at 4:48

Summary

1. The state space follows from the problem. "Niceness" depends on the method, as does "too big."
2. You can alter the reward function to speed learning if you know the optimal policy is invariant to the transformation.
3. Tractable depends on more than just state space. RL has been applied to much larger problems, though those methods aren't exactly out-of-the-box.

Defining the state space

It's unclear what you mean by "nice." Consider what you know:

• The goal is in the center.
• The agent starts in the bottom left.
• The first subgoal appears somewhere other than these two spaces.
• Sometimes upon reaching a subgoal, another appears; sometimes not.
• So long as a subgoal is present, the agent must reach it prior to reaching the goal.

Meaning, the number of subgoals doesn't seem particularly material to the optimal policy.

In a discrete representation, the agent can be in one of $10,000$ positions, and if a subgoal is present it can appear in any of $9,998$. (Assuming it can never be in the goal state, and knowing it can never be in the agent's starting position, which follows from knowing that subgoals only get closer to the goal.)

Big? Sure. Too big for standard Q-learning? Likely, if you'd like your learner to return a policy before the heat death of the universe. But this would seem to be the full, irreducible representation of your problem.

My idea would be to choose the 'relative' position between the agent and the goal. Something like: $(x,y)$, $x = \{ -1, 0, 1\}$. $-1$ if the goal is to the left of the agent, 1 if the goal is to the right, and 0 if the goal is at the same $x$ coordinate as the agent. $y = \{ -1,0,1\}$, $-1$ if the goal is below, $1$ if above the agent. 0 if they the same $y-$coordinate.

I sense what you're getting at here: You'd like to map a large state space $S$ to smaller one $\hat S$ such that $\pi^*_{S}(s) = \pi^*_{\hat S}(\hat s)$. This makes intuitive sense, as relative distance to subgoals and goal are just about all the agent needs to make optimal decisions.

This is basically handcrafting a policy; it's fine if that suits your problem, but then one wonders if you need RL at all.

Is this tractable?

Well, it's learnable, in the sense that it's well within the current state of the art. Consider the state space described in the paper on learning to play Atari games via deep neural networks and Q-learning:

Working directly with raw Atari frames, which are 210 × 160 pixel images with a 128 color palette, can be computationally demanding, so we apply a basic preprocessing step aimed at reducing the input dimensionality. The raw frames are preprocessed by first converting their RGB representation to gray-scale and down-sampling it to a 110×84 image. The final input representation is obtained by cropping an 84 × 84 region of the image that roughly captures the playing area. [...] For the experiments in this paper, the function $\phi$ from algorithm 1 applies this preprocessing to the last 4 frames of a history and stacks them to produce the input to the Q-function.

You could view your state space as a subset of the $100 \times 100$ images, and the state space above dwarfs yours. All to say that likely solutions exist even for bigger state spaces, but in this you probably needn't get that fancy.

On 'cheating'

I believe it is standard in RL that the reward is given at the end of the task.

I'd urge you to quickly disabuse yourself of this notion: It simply isn't true. Firstly because the reward function follows from the application, full stop. If an application entails different rewards, they should naturally be included, i.e. a single reward is hardly standard. Secondly because optimal policies are invariant under certain transformations of the reward function, which can speed learning (emphasis mine):

This paper investigates conditions under which modifications to the reward function of a Markov decision process preserve the optimal policy. It is shown that [...] one can add a reward for transitions between states that is expressible as the difference in value of an arbitrary potential function applied to those states. [...] In particular, some well-known "bugs" in reward shaping procedures are shown to arise from non-potential-based rewards, and methods are given for constructing shaping potentials corresponding to distance-based and subgoal-based heuristics. We show that such potentials can lead to substantial reductions in learning time.

If your problem has one goal state, a single reward is a natural representation, and you're right that arbitrarily adding rewards to states is a bad idea. But it's only so when one cannot show policy invariance under the transformation; otherwise it's fair game.

What should you actually do?

As you know, you can expect any action under the optimal policy to generally either be moving toward the subgoal or moving toward the goal. I think you'll find that you can create potential-based reward shaping functions from these facts, ones that would quickly speed learning.

You could also view this as an option learning problem, wherein one option was to pursue the subgoal, the other to pursue the goal. (Option is a term used to describe temporally extended actions. You can view it as using a certain policy until a certain state is reached.)

You could also just initialize $Q$ such that the starting policy was close to optimal.