# DQN exploration strategy for large grid-world environment

My task involves a large grid-world type of environment (grid size may be $$30\times30$$, $$50\times50$$, $$100\times100$$, at the largest $$200\times200$$). Each element in this grid either contains a 0 or a 1, which are randomly initialized in each episode. My goal is to train an agent, which starts in a random position on the grid, and navigate to every cell with the value 1, and set it to 0. (Note that in general, the grid is mostly 0s, with sparse 1s).

I am trying to train a DQN model with 5 actions to accomplish this task:

1. Move up

2. Move right

3. Move down

4. Move left

5. Clear (sets current element to 0)

The "state" that I give the model is the current grid ($$N\times N$$ tensor). I provide the agent's current location through the concatenation of a flattened one-hot ($$1\times(N^2)$$) tensor to the output of my convolutional feature vector (before the FC layers).

However, I find that the epsilon-greedy exploration policy does not lead to sufficient exploration. Also, early in the training (when the model is essentially choosing random actions anyway), the pseudo-random action combinations end up "canceling out", and my agent does not move far enough away from the starting location to discover that there is a cell with value 1 in a different quadrant of the grid, for example. I am getting a converging policy on a $$5\times5$$ grid w/ a non-convolutional MLP model, so I think that my implementation is sound.

1. How I might encourage exploration that will not always "cancel out" to only explore a very local region to my starting location?

2. Is this approach a good way to accomplish this task (assuming I want to use RL)?

3. I would think that attempting to work with a "continuous" action space (model outputs 2 values: vertical and horizontal indices of grid cells that contain 1s) would be more difficult to achieve convergence. Is it wise to always try to use discrete action spaces?

• The bottleneck isn't the epsilon-greedy policy but the action model. According to the description the robot can move in four directions, that means the action vocabulary is limited to four skills. Putting more words into the vocabulary will increase the performance. – Manuel Rodriguez Dec 6 '18 at 6:05
• @ManuelRodriguez what exactly do you mean by this? I was under the impression that you should use the minimum number of actions possible. It would seem that the fewer actions there are, the less complex the Q* function is that we are trying to approximate. – Mink Dec 6 '18 at 14:55
• In the given description the largest grid is 200x200, moving up only one field takes very long to explore the map. A simple additional action like “move 10up” produces a tunnel effect in the state-space, as a result the complexity will decrease. In the literature, the concept is known as “multimodal DQN”. – Manuel Rodriguez Dec 6 '18 at 16:50
• @ManuelRodriguez That concept is not known as "multimodal". Multimodal would be if you combine very different types of inputs (e.g. combining visual inputs and audio inputs). What you're describing is known as "hierarchical" Reinforcement Learning. Other relevant terms would be "macro-actions" and "temporal abstraction". Such approaches could indeed be one way to alleviate the problem in this question. Mink is right though, the problem described is also very much an exploration problem, and better exploration mechanisms can also help (e.g. curiosity-driven exploration) – Dennis Soemers Dec 6 '18 at 18:06

What does your Q-network look like?

If you're using Convolutional Neural Networks (CNNs), I would advise against using pooling layers since the spatial translation data matters in this application (i.e. a cell with '1' top right of the agent is not the same as a cell with '1' below).

1) How I might encourage exploration that will not always "cancel out" to only explore a very local region to my starting location?

This is referred to as exploration vs exploitation dilemma.

One way to add tackle this is by adding extra logic to the way you're choosing random actions. To elaborate, the chosen random action shouldn't be the same as the opposite of the previous action: if the agent went LEFT, the next random shouldn't be RIGHT as that is not exploring.

Another method is to use different action selection strategies such as Boltzmann Policy rather than epsilon-greedy. Click here for a quick crash course on the mainstream strategies by Arthur Juliani.

2) Is this approach a good way to accomplish this task (assuming I want to use RL)?

RL is well suited for this application. Try different parameters for your network. I'd start with a small network and add more layers/neurons as necessary if it does not converge. However, keep in mind that it might take a while (hours or days) to converge so don't get hasty.

3) I would think that attempting to work with a "continuous" action space (model outputs indexes of "1" elements) would be more difficult to achieve convergence. Is it wise to always try to use discrete action spaces?

I'm not sure I fully understand your question. Mind elaborating? What do you mean by the indexes of "1" elements that the model outputs?

• Thanks for the suggestions. To answer your last question, it seems that another potential way to tackle this problem would be to ditch to "moving agent" approach entirely. Instead, I could use a "continuous" action space by having my network output 2 values: a vertical index and horizontal index. For example, if the network outputted 38 and 71, the value at grid[38][71] would be cleared to 0. Of course, I then could not use Q-learning at all, and use actor critic instead. – Mink Dec 6 '18 at 14:52