DQN exploration strategy for large grid-world environment

Question

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?

Answer 1

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?