Answers.Body: <p>You don't say, but I suspect from your description, that you have designed the neural network to operate over one-hot-encoding representations of states and actions. Using such a representation offers no benefit whatsoever compared to a simple table. That is because the intended benefit of using neural networks, or any kind of approximation, is <em>generalisation</em>.</p>
  <p>It is not possible to generalise results between states and actions, if those states and actions are simply enumerated. If you represent <span class="math-container">$\mathcal{S}$</span> as <span class="math-container">$\{s_0, s_1, s_2 ... s_{13}\}$</span> and <span class="math-container">$\mathcal{A}$</span> as <span class="math-container">$\{a_0, a_1, a_2 ... a_{168}\}$</span> to <em>any</em> function, then the best generalisation that can be made are only based on the mean of <span class="math-container">$Q(s, a)$</span> for all states or all actions. You cannot use experience gained for <span class="math-container">$Q(s_0, a_0)$</span> to say anything about expected return for <span class="math-container">$Q(s_1, a_1)$</span>. That is true even if <span class="math-container">$s_0$</span> and <span class="math-container">$s_1$</span> are similar in some way - the representation does not capture that similarity, so the approximator cannot use it.</p>
  <p>State and action <em>representation</em> are very important details when adding approximation to reinforcement learning.</p>
  <p>To gain generalisation, an approximation scheme needs to have feature data that encapsulates how elements in the space are similar or different to each other. For example, if the 169 actions are arranged on a 13x13 grid, then each action can be represented as a 2-element vector. This will work for approximation if actions that are close to each other in this 13x13 space usually have similar expected returns.</p>
  <blockquote>
  <p><strong>Space complexity/memory-wise, isn't storing a look-up q-table of 2366 size better than storing 8000 parameters of neural net?</strong></p>
  </blockquote>
  <p>Yes, typically neural network parameters are 32-bit floats, which would also a suitable storage type for the q table values.</p>
  <p>It is not common to have a neural network use more space to store its parameters than would be required to fully describe the entire function domain that it is approximating. So you are right to find it unwanted/unexpected. The answer to this puzzle is likely to be in your choices for state and action representation.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-20T07:48:07.947Z
Answers.LastActivityDate: 2022-06-20T14:38:01.030Z
Answers.LastEditDate: 2022-06-20T14:38:01.030Z
Answers.UserDisplayName: Neil Slater
Body: <p>I want to <strong>compare the space complexity/memory requirement of tabular Q-learning v.s. deep neural Q-network</strong> (DQN). I think DQN would be faster and Q-table has a disadvantage at large table sizes but consider the following case.</p>
  <p>A Q-table has the size 14 states *169 actions= 2366 entries and (say) a fully connected DNN whose number of parameters comes out to be like &gt;8000. <strong>Space complexity/memory-wise, isn't storing a look-up q-table of 2366 size better than storing 8000 parameters of neural net?</strong>  I never implemented a DNN before so no idea how much space neural net parameters take.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-20T09:17:30.840Z
Comments.Text: Please, **do not ask for opinions**. Ask for evidence and facts. We have a specific close reason that can be used to close posts that ask for opinions. Moreover, please, reformulate your title in the form of a question. I see only one question in the body of your post and it's slightly different than what you have in the title, which is more general.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-20T13:10:53.923Z
Comments.Text: Ok thanks. I will be careful in future questions. I have edited the title now. I thought I can ask this question since it is based on some actual numbers that I am dealing with. And not any general theory question. I asked for the opinion of people who have experienced such scenario so that I get clear as I don't have experience with dnn but only with q table..thanks for keeping the question though.. Do you know of any other site where you think this is more appropriate to post (for future reference I mean)?
Comments.UserDisplayName: knowledge_seeker
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-20T14:22:31.697Z
Comments.Text: I think your problem is fine for our site, but the way you had formulated the question wasn't ideal (you can ask people to share with you their experience and empirical findings - that would not really be an opinion). So, every question on theoretical/conceptual/mathematical aspects of AI (including RL) can and probably should be asked here. I think your question can actually be asked here (because you're asking about the theoretical computational requirements - you're not asking e.g. which GPU you need to buy, which would be more a hardware question, and so off-topic), so don't worry!
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><deep-learning><deep-rl><q-learning><deep-neural-networks>
Title: How to compare memory requirements for tabular Q-learning vs deep neural network?
UserDisplayName: knowledge_seeker
ThreadText: # How to compare memory requirements for tabular Q-learning vs deep neural network?
  
  (Asked by: username_0 on 2022-06-19)
  
  I want to **compare the space complexity/memory requirement of tabular Q-learning v.s. deep neural Q-network** (DQN). I think DQN would be faster and Q-table has a disadvantage at large table sizes but consider the following case.
  
  A Q-table has the size 14 states \*169 actions= 2366 entries and (say) a fully connected DNN whose number of parameters comes out to be like >8000. **Space complexity/memory-wise, isn't storing a look-up q-table of 2366 size better than storing 8000 parameters of neural net?** I never implemented a DNN before so no idea how much space neural net parameters take.
  
  **Tags:** reinforcement-learning, deep-learning, deep-rl, q-learning, deep-neural-networks
  > **Comments:**
  > **username_1**: Please, **do not ask for opinions**. Ask for evidence and facts. We have a specific close reason that can be used to close posts that ask for opinions. Moreover, please, reformulate your title in the form of a question. I see only one question in the body of your post and it's slightly different than what you have in the title, which is more general.  
  > **username_0**: Ok thanks. I will be careful in future questions. I have edited the title now. I thought I can ask this question since it is based on some actual numbers that I am dealing with. And not any general theory question. I asked for the opinion of people who have experienced such scenario so that I get clear as I don't have experience with dnn but only with q table..thanks for keeping the question though.. Do you know of any other site where you think this is more appropriate to post (for future reference I mean)?  
  > **username_1**: I think your problem is fine for our site, but the way you had formulated the question wasn't ideal (you can ask people to share with you their experience and empirical findings - that would not really be an opinion). So, every question on theoretical/conceptual/mathematical aspects of AI (including RL) can and probably should be asked here. I think your question can actually be asked here (because you're asking about the theoretical computational requirements - you're not asking e.g. which GPU you need to buy, which would be more a hardware question, and so off-topic), so don't worry!  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-06-20. Score: 1 | Accepted answer
  
  You don't say, but I suspect from your description, that you have designed the neural network to operate over one-hot-encoding representations of states and actions. Using such a representation offers no benefit whatsoever compared to a simple table. That is because the intended benefit of using neural networks, or any kind of approximation, is *generalisation*.
  
  It is not possible to generalise results between states and actions, if those states and actions are simply enumerated. If you represent $\mathcal{S}$ as $\{s\_0, s\_1, s\_2 ... s\_{13}\}$ and $\mathcal{A}$ as $\{a\_0, a\_1, a\_2 ... a\_{168}\}$ to *any* function, then the best generalisation that can be made are only based on the mean of $Q(s, a)$ for all states or all actions. You cannot use experience gained for $Q(s\_0, a\_0)$ to say anything about expected return for $Q(s\_1, a\_1)$. That is true even if $s\_0$ and $s\_1$ are similar in some way - the representation does not capture that similarity, so the approximator cannot use it.
  
  State and action *representation* are very important details when adding approximation to reinforcement learning.
  
  To gain generalisation, an approximation scheme needs to have feature data that encapsulates how elements in the space are similar or different to each other. For example, if the 169 actions are arranged on a 13x13 grid, then each action can be represented as a 2-element vector. This will work for approximation if actions that are close to each other in this 13x13 space usually have similar expected returns.
  
  > **Space complexity/memory-wise, isn't storing a look-up q-table of 2366 size better than storing 8000 parameters of neural net?**
  
  Yes, typically neural network parameters are 32-bit floats, which would also a suitable storage type for the q table values.
  
  It is not common to have a neural network use more space to store its parameters than would be required to fully describe the entire function domain that it is approximating. So you are right to find it unwanted/unexpected. The answer to this puzzle is likely to be in your choices for state and action representation.
  
  
  ---
  
  