Answers.Body: <p>Before we start to tweak with you Agent-Environment setup, there are couple of important things to note</p>
  
  <ul>
  <li><p>Q-Learning</p>
  
  <p>Q-learning as a fundamental is a <strong>greedy</strong> approach based on <strong>Action Value</strong> functions. When I say action value what I mean to say is this
  <span class="math-container">$q_\pi(s,a) = p(\hat{s},r | s, a)[r + \gamma(V(\hat{s}))]$</span>. </p>
  
  <p>This means according to <span class="math-container">$\pi$</span> policy the <strong>Action value</strong> for taking action "<span class="math-container">$a$</span>" at state "<span class="math-container">$s$</span>" is the probability of taking reaching state "<span class="math-container">$\hat{s}$</span>" and getting a reward "<span class="math-container">$r$</span>" given the current state is "<span class="math-container">$s$</span>" and action taken is "<span class="math-container">$a$</span>" multiplied by sum of immediate reward "<span class="math-container">$r$</span>" and <strong>expected</strong> future reward given by future state value(s) "<span class="math-container">$V(\hat{s})$</span>". </p>
  
  <p>Please note the <span class="math-container">$p(\hat{s},r | s, a)$</span> is only available in <strong><em>deterministic modelling technique (model based methods)</em></strong> and this part is not available for <strong><em>stochastic modelling techniques (model-free methods)</em></strong>. For model-free methods we execute multiple <strong>experiments</strong> and take the <em>expected</em> value in accordance with <strong>Law of Large Numbers</strong>. Which is what we do in common <em>Deep Reinforced Learning</em> implementations.</p>
  
  <p>The above formulation for future rewards can be expanded in series using the state-value formulation as <span class="math-container">$V(s) = \pi(a,s)q_\pi(s,a)$</span>, where <span class="math-container">$\pi$</span> is the policy we are following aka probability of taking action <span class="math-container">$a$</span> when in state <span class="math-container">$s$</span>.  </p>
  
  <p>Why is it termed <em>Greedy</em>?</p>
  
  <p>This is because while using the fundamental of multiple experiments, with every action I take the immediate reward, and the <strong>max</strong> q_value (<span class="math-container">$q$</span>) associated with the <strong>next_state</strong> to update my current q_value.</p></li>
  </ul>
  
  <p>In Q-learning the future state reward is what you calculate by submitting the <strong><em>next_state</em></strong> to the network and taking <strong><em>max</em></strong> of the <strong><em>q_values</em></strong> attained. (Hence, Greedy!!)</p>
  
  <p><strong>Crux of the above</strong></p>
  
  <p>Having said all the above (Duh!), what is in it for us?</p>
  
  <p>In Q-Learning, your reward is key for your model learn, i.e. "<span class="math-container">$r$</span>" <strong>immediate reward</strong> and the <strong>future reward</strong> (<span class="math-container">$V(\hat{s})$</span>)</p>
  
  <ul>
  <li><p>When the state-space is limited</p>
  
  <p>For example, a <a href="https://en.wikipedia.org/wiki/Tic-tac-toe_variants#Numerical_Tic-tac-toe" rel="nofollow noreferrer">numerical tic-tac-toe game</a>, in such cases it is ideal to have discrete reward system, such as the one suggested by you. </p></li>
  <li><p>When the state-space is very large (the problem statement you are tackling)</p>
  
  <p>In such cases, it is ideal to have a <strong>continuous</strong> reward mechanism, i.e. rewards should be more variable in nature, like continuous values.</p></li>
  <li><p>Suggestions</p>
  
  <ol>
  <li><p>You can define the reward function in the environment has the <strong>10<span class="math-container">$\sqrt{2}$</span> - Euclidean distance</strong> between the face of your <em>snake</em> and the <em>fruit</em> it is trying to reach. The reason I am doing it (10<span class="math-container">$\sqrt{2}$</span> minus) is because the maximum distance could be 10<span class="math-container">$\sqrt{2}$</span> (considering it is 10X10 board). This would help you to have a more variable/continuous rewards for your model to learn with (since you are using neural networks for training them). As your <em>Snake</em> goes closer to the <em>fruit</em> this value will keep on increasing. One cavet, if by taking an action, your snake reaches fruit, you can provide it a specific constant (extra) reward, and if it hits its own self, or the borders you penalize it with a specific constant. So that the model understand better.</p></li>
  <li><p>You can define your state (input vector to your NN) as 100 dimension array (10X10 grid) with each element signifying if there a object in the that area or not. <strong>1</strong> means it is fruit, <strong>0</strong> means it is <em>snakes</em> own body and <strong>0.5</strong> means it is free for movement. The idea is to limit the input values of the vectors between 0~1.  As your agent takes action, the values in the state will keep on changing.</p></li>
  <li><p>The output of your network should have 3 neurons, each signifying the <strong><span class="math-container">$q$</span></strong> of each of action (front/right/left movement). For <em>get_action</em> function you will get the action pertaining to <em>max(q_value)</em>, and keep on adding things in your <strong>memory d_que</strong>. Subsequently you can trigger <strong>model_train</strong> methods at every episode/or even at after every step.</p></li>
  <li><p>Lastly, the hyper parameters would be the discount factor <em><span class="math-container">$\gamma$</span></em> you choose and the learning rate <em><span class="math-container">$\alpha$</span></em> you use for the NN network. That's something you will have to experiment. Along the depth of your ANN. I think a single hidden layer should be enough.</p></li>
  <li><p>For the last layer of your NN, please use a <em>linear</em> activation function, and not a <em>relu</em> activation function.</p></li>
  <li><p>Please run many-many-many experiments, something in millions for optimum training. There could be multiple ways of monitoring your model's learning process. How many games won, how much <em>fruit</em> eating it is able to achieve in 1 game etc.</p></li>
  </ol></li>
  </ul>
  
  <p>Hope the above helps.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-14T08:18:32.050Z
Answers.Text: Thanks for your reply. I have already added reward functions similar to what you're suggesting, and as I mentioned, I tried with an input state vector (10x10 = 100 elements), which is similar to what you say in point 2. I will try to run for longer time, but currently, after 300.000 steps, I did not improve one bit in the reward pr game, but the loss, calculated as the sum of the errors, does not change at all. I will try to upload my code to github and provide a link later if someone is interested.
Answers.UserDisplayName: johnhelt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-14T08:28:36.380Z
Answers.Text: Looking forward to the code link!
Answers.UserDisplayName: Anugraha Sinha
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-14T12:59:24.893Z
Answers.Text: You can find the code on [my github repo](https://github.com/johnhelt/DDQN). You can run the code from the main script (DDQN_algorithm_StackExhange.py))
Answers.UserDisplayName: johnhelt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-15T21:10:22.437Z
Answers.Text: I am wondering why you're suggesting to use a linear output function. I consider the problem to be a classification problem ("go straight", "go left", "go right"), and the NN to take the choice of the path with highest probability for maximizing the Q function. This post suggest the softmax function: https://stats.stackexchange.com/questions/218542/which-activation-function-for-output-layer
Answers.UserDisplayName: johnhelt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-16T02:41:41.990Z
Answers.Text: The ref given by you is a general suggestion for activation function for any type of NN. There is different between regression based problems and RL based problems. There are a couple of issues as to why you should not be using a softmax. It would be a little difficult to explain here, I will build markdown on github and share the link to explain this.
Answers.UserDisplayName: Anugraha Sinha
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-14T07:35:09.030Z
Answers.LastActivityDate: 2019-05-14T07:47:22.513Z
Answers.LastEditDate: 2019-05-14T07:47:22.513Z
Answers.UserDisplayName: Anugraha Sinha
Body: <p>I am designing a neural network using Deep Q-Learning, which teaches an agent how to play Snake (The classic Nokia game from the 90'ies). The goal of the game is to navigate the snake on a playing field (2D), and to eat a randomly placed fruit. As the Snake eats the fruit, it grows in length. The game ends if the snake hits the game border, or it self, so as the number of fruits consumed increases, so does the difficulty of navigating without hitting something.</p>
  
  <p>I have trained the Snake game on a 10x10 playing field using the following inputs:</p>
  
  <ol>
  <li>x direction of the snake</li>
  <li>y direction of the Snake </li>
  <li>The fraction of playing field occupied by the snake itself </li>
  <li>A bool which says if the fruit is in front of the snake (from it's current direction)</li>
  <li>A bool which says if the fruit is to the left of the snake (from
  it's current direction) </li>
  <li>A bool which says if collision (game over) in front of the snake is possible </li>
  <li>A bool which says if collision to the right is possible</li>
  <li>A bool which says if collision to the left is possible</li>
  </ol>
  
  <p>With this choice of inputs I am getting the Snake agent to work reasonably well, and score until it plateaus out. I have examined the cases where the snake dies, and it all happens when it has no way of escaping, for example, it turns around and blocks its own path, until it finally has no where to go. This is more likely to happen as the Snake increases in lenght.</p>
  
  <p>I was thinking on how I could improve this performance. It seems to me, that the reason the Snake can make a self-blocking turn is because of the inputs. Since the path it takes is clear, there's no information, that the next path is not, or that continuing further down will eventually lead to game over. If the Snake agent was aware of all obstacles in each step, i.e. the entire state-space, then I could imagine that would help train the network towards finding the optimal path without ending up blocking itself.</p>
  
  <p>Since I have made the Snake game myself, I can return to the agent a matrix, or an unfolded vector, which contains the inputs for each column / row on the playing field. A blocked cell would be set to 0, a free cell 1, the fruit cell has value 0.75 and the snake head (which moves) could be assigned value 0.25. After trying this approach, I have to say I was unsuccesful. The snake ends up just turning in circles, even if I use the same reward system as the 8 input case shown above.</p>
  
  <p>I am therefore trying to understand what is happening here. Am I missing information? I would think the full 10x10 state space would give me exactly enough information to lead to the correct evaluation of the next path. I would very much like to hear someone elses input to this approach.</p>
  
  <p>Thanks a lot</p>
  
Tags: <neural-networks><python><q-learning>
Title: Choice of inputs features for Snake game
UserDisplayName: johnhelt
ThreadText: # Choice of inputs features for Snake game
  
  (Asked by: username_0 on 2019-05-13)
  
  I am designing a neural network using Deep Q-Learning, which teaches an agent how to play Snake (The classic Nokia game from the 90'ies). The goal of the game is to navigate the snake on a playing field (2D), and to eat a randomly placed fruit. As the Snake eats the fruit, it grows in length. The game ends if the snake hits the game border, or it self, so as the number of fruits consumed increases, so does the difficulty of navigating without hitting something.
  
  I have trained the Snake game on a 10x10 playing field using the following inputs:
  
  1. x direction of the snake
  2. y direction of the Snake
  3. The fraction of playing field occupied by the snake itself
  4. A bool which says if the fruit is in front of the snake (from it's current direction)
  5. A bool which says if the fruit is to the left of the snake (from
     it's current direction)
  6. A bool which says if collision (game over) in front of the snake is possible
  7. A bool which says if collision to the right is possible
  8. A bool which says if collision to the left is possible
  
  With this choice of inputs I am getting the Snake agent to work reasonably well, and score until it plateaus out. I have examined the cases where the snake dies, and it all happens when it has no way of escaping, for example, it turns around and blocks its own path, until it finally has no where to go. This is more likely to happen as the Snake increases in lenght.
  
  I was thinking on how I could improve this performance. It seems to me, that the reason the Snake can make a self-blocking turn is because of the inputs. Since the path it takes is clear, there's no information, that the next path is not, or that continuing further down will eventually lead to game over. If the Snake agent was aware of all obstacles in each step, i.e. the entire state-space, then I could imagine that would help train the network towards finding the optimal path without ending up blocking itself.
  
  Since I have made the Snake game myself, I can return to the agent a matrix, or an unfolded vector, which contains the inputs for each column / row on the playing field. A blocked cell would be set to 0, a free cell 1, the fruit cell has value 0.75 and the snake head (which moves) could be assigned value 0.25. After trying this approach, I have to say I was unsuccesful. The snake ends up just turning in circles, even if I use the same reward system as the 8 input case shown above.
  
  I am therefore trying to understand what is happening here. Am I missing information? I would think the full 10x10 state space would give me exactly enough information to lead to the correct evaluation of the next path. I would very much like to hear someone elses input to this approach.
  
  Thanks a lot
  
  **Tags:** neural-networks, python, q-learning
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-05-14. Score: 1
  
  Before we start to tweak with you Agent-Environment setup, there are couple of important things to note
  
  * Q-Learning
  
    Q-learning as a fundamental is a **greedy** approach based on **Action Value** functions. When I say action value what I mean to say is this
    $q\_\pi(s,a) = p(\hat{s},r | s, a)[r + \gamma(V(\hat{s}))]$.
  
    This means according to $\pi$ policy the **Action value** for taking action "$a$" at state "$s$" is the probability of taking reaching state "$\hat{s}$" and getting a reward "$r$" given the current state is "$s$" and action taken is "$a$" multiplied by sum of immediate reward "$r$" and **expected** future reward given by future state value(s) "$V(\hat{s})$".
  
    Please note the $p(\hat{s},r | s, a)$ is only available in ***deterministic modelling technique (model based methods)*** and this part is not available for ***stochastic modelling techniques (model-free methods)***. For model-free methods we execute multiple **experiments** and take the *expected* value in accordance with **Law of Large Numbers**. Which is what we do in common *Deep Reinforced Learning* implementations.
  
    The above formulation for future rewards can be expanded in series using the state-value formulation as $V(s) = \pi(a,s)q\_\pi(s,a)$, where $\pi$ is the policy we are following aka probability of taking action $a$ when in state $s$.
  
    Why is it termed *Greedy*?
  
    This is because while using the fundamental of multiple experiments, with every action I take the immediate reward, and the **max** q\_value ($q$) associated with the **next\_state** to update my current q\_value.
  
  In Q-learning the future state reward is what you calculate by submitting the ***next\_state*** to the network and taking ***max*** of the ***q\_values*** attained. (Hence, Greedy!!)
  
  **Crux of the above**
  
  Having said all the above (Duh!), what is in it for us?
  
  In Q-Learning, your reward is key for your model learn, i.e. "$r$" **immediate reward** and the **future reward** ($V(\hat{s})$)
  
  * When the state-space is limited
  
    For example, a [numerical tic-tac-toe game](https://en.wikipedia.org/wiki/Tic-tac-toe_variants#Numerical_Tic-tac-toe), in such cases it is ideal to have discrete reward system, such as the one suggested by you.
  * When the state-space is very large (the problem statement you are tackling)
  
    In such cases, it is ideal to have a **continuous** reward mechanism, i.e. rewards should be more variable in nature, like continuous values.
  * Suggestions
  
    1. You can define the reward function in the environment has the **10$\sqrt{2}$ - Euclidean distance** between the face of your *snake* and the *fruit* it is trying to reach. The reason I am doing it (10$\sqrt{2}$ minus) is because the maximum distance could be 10$\sqrt{2}$ (considering it is 10X10 board). This would help you to have a more variable/continuous rewards for your model to learn with (since you are using neural networks for training them). As your *Snake* goes closer to the *fruit* this value will keep on increasing. One cavet, if by taking an action, your snake reaches fruit, you can provide it a specific constant (extra) reward, and if it hits its own self, or the borders you penalize it with a specific constant. So that the model understand better.
    2. You can define your state (input vector to your NN) as 100 dimension array (10X10 grid) with each element signifying if there a object in the that area or not. **1** means it is fruit, **0** means it is *snakes* own body and **0.5** means it is free for movement. The idea is to limit the input values of the vectors between 0~1. As your agent takes action, the values in the state will keep on changing.
    3. The output of your network should have 3 neurons, each signifying the **$q$** of each of action (front/right/left movement). For *get\_action* function you will get the action pertaining to *max(q\_value)*, and keep on adding things in your **memory d\_que**. Subsequently you can trigger **model\_train** methods at every episode/or even at after every step.
    4. Lastly, the hyper parameters would be the discount factor *$\gamma$* you choose and the learning rate *$\alpha$* you use for the NN network. That's something you will have to experiment. Along the depth of your ANN. I think a single hidden layer should be enough.
    5. For the last layer of your NN, please use a *linear* activation function, and not a *relu* activation function.
    6. Please run many-many-many experiments, something in millions for optimum training. There could be multiple ways of monitoring your model's learning process. How many games won, how much *fruit* eating it is able to achieve in 1 game etc.
  
  Hope the above helps.
  
  > **Comments:**
  > **username_0**: Thanks for your reply. I have already added reward functions similar to what you're suggesting, and as I mentioned, I tried with an input state vector (10x10 = 100 elements), which is similar to what you say in point 2. I will try to run for longer time, but currently, after 300.000 steps, I did not improve one bit in the reward pr game, but the loss, calculated as the sum of the errors, does not change at all. I will try to upload my code to github and provide a link later if someone is interested.  
  > **username_1**: Looking forward to the code link!  
  > **username_0**: You can find the code on [my github repo](https://github.com/username_0/DDQN). You can run the code from the main script (DDQN_algorithm_StackExhange.py))  
  > **username_0**: I am wondering why you're suggesting to use a linear output function. I consider the problem to be a classification problem ("go straight", "go left", "go right"), and the NN to take the choice of the path with highest probability for maximizing the Q function. This post suggest the softmax function: https://stats.stackexchange.com/questions/218542/which-activation-function-for-output-layer  
  > **username_1**: The ref given by you is a general suggestion for activation function for any type of NN. There is different between regression based problems and RL based problems. There are a couple of issues as to why you should not be using a softmax. It would be a little difficult to explain here, I will build markdown on github and share the link to explain this.  
  
  ---
  
  