Answers.Body: <p>What does your Q-network look like?</p>
  
  <p>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).</p>
  
  <blockquote>
    <p><strong>1) How I might encourage exploration that will not always "cancel out" to only explore a very local region to my starting location?</strong></p>
  </blockquote>
  
  <p>This is referred to as <em>exploration vs exploitation dilemma</em>.</p>
  
  <p>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.</p>
  
  <p>Another method is to use different action selection strategies such as Boltzmann Policy rather than epsilon-greedy. Click <a href="https://medium.com/emergent-future/simple-reinforcement-learning-with-tensorflow-part-7-action-selection-strategies-for-exploration-d3a97b7cceaf" rel="nofollow noreferrer">here</a> for a quick crash course on the mainstream strategies by Arthur Juliani.</p>
  
  <blockquote>
    <p><strong>2) Is this approach a good way to accomplish this task (assuming I want to use RL)?</strong></p>
  </blockquote>
  
  <p>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.</p>
  
  <blockquote>
    <p><strong>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?</strong></p>
  </blockquote>
  
  <p>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?</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-06T14:52:03.847Z
Answers.Text: 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.
Answers.UserDisplayName: Mink
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-06T03:26:36.600Z
Answers.LastActivityDate: 2018-12-06T03:26:36.600Z
Answers.UserDisplayName: Sanavesa
Body: <p>My task involves a large grid-world type of environment (grid size may be <span class="math-container">$30\times30$</span>, <span class="math-container">$50\times50$</span>, <span class="math-container">$100\times100$</span>, at the largest <span class="math-container">$200\times200$</span>). 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). </p>
  
  <p>I am trying to train a DQN model with 5 actions to accomplish this task:</p>
  
  <ol>
  <li><p>Move up</p></li>
  <li><p>Move right</p></li>
  <li><p>Move down</p></li>
  <li><p>Move left</p></li>
  <li><p>Clear (sets current element to 0)</p></li>
  </ol>
  
  <p>The "state" that I give the model is the current grid (<span class="math-container">$N\times N$</span> tensor). I provide the agent's current location through the concatenation of a flattened one-hot (<span class="math-container">$1\times(N^2)$</span>) tensor to the output of my convolutional feature vector (before the FC layers).</p>
  
  <p>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 <span class="math-container">$5\times5$</span> grid w/ a non-convolutional MLP model, so I think that my implementation is sound.</p>
  
  <ol>
  <li><p><strong>How I might encourage exploration that will not always "cancel out" to only explore a very local region to my starting location?</strong></p></li>
  <li><p><strong>Is this approach a good way to accomplish this task (assuming I want to use RL)?</strong></p></li>
  <li><p><strong>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?</strong></p></li>
  </ol>
  
Tags: <deep-learning><reinforcement-learning><dqn>
Title: DQN exploration strategy for large grid-world environment
UserDisplayName: Mink
ThreadText: # DQN exploration strategy for large grid-world environment
  
  (Asked by: username_0 on 2018-12-05)
  
  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?**
  
  **Tags:** deep-learning, reinforcement-learning, dqn
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-12-06. Score: 2
  
  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](https://medium.com/emergent-future/simple-reinforcement-learning-with-tensorflow-part-7-action-selection-strategies-for-exploration-d3a97b7cceaf) 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?
  
  > **Comments:**
  > **username_0**: 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.  
  
  ---
  
  