Answers.Body: <p>Speed and size, no. That's because speed is dependent on processor clock periods and the effective parallel nature of the particular deep RL design in the environment, which is also dependent on cores and host clustering. Size is not really quantifiable in a way that is meaningful in this relationship because there is a broader and more complex structure of a network that might be trained to produce a value to use in the RL algorithm chosen.</p>
  
  <ul>
  <li>Width for each layer</li>
  <li>Cell type and possibly activation function for each layer</li>
  <li>Hyper-parameters</li>
  </ul>
  
  <p>One can say that number of clock cycles times number of effective parallel processors is correlated to all the above, the overhead of the RL algorithm used, and the size of each data tensor.</p>
  
  <p>There are a few inequalities developed in the PAC (probably approximately correct) framework, so it would not be surprising if there were some bounding rules for the relationship between clock cycles, effective parallelism, data widths, activation functions, and RL algorithms for deep RL.</p>
  
  <p>Study of the algorithm, perhaps in conjunction with experimentation, may reveal the primary factors, essentially the processing bottlenecks. Further study of the factors involved in controlling loop iteration counts, which cause the bottleneck, could permit the quantification of computing effort required to maintain a particular maximum allowable response time, but that would be specific to a particular design.</p>
  
  <p>Such might produce a metric that is effectively a count of clock cycles across the system's potentially parallel architecture for a worst case or mean RL action selection. That could then be used to determine the response time for a given system with all of the factors mentioned above fixed, including the priority and scheduling of the processes in each operating system involved.</p>
  
  <p>Here's a guess. Feel free to critique, since such a formulation is a project far beyond the effort that should be put into answering a question online.</p>
  
  <p><span class="math-container">$$ t_r \propto e^{k_v} \, n_v \, \eta_v \, t_v \, \mu_v \, \sum c_v + e^{k_d} \, n_d \, \eta_d \, t_d \, \mu_d \, \sum c_d \; \text{,} $$</span></p>
  
  <p>where <span class="math-container">$t$</span> is time, <span class="math-container">$k$</span> is tensor complexity, <span class="math-container">$n$</span> is number of cores, <span class="math-container">$\eta$</span> is the effective efficiency of the parallel processing, <span class="math-container">$\mu$</span> is the effective overhead cost of the glue code, <span class="math-container">$c$</span> is the cycles require of the significant (and probably repetitive) elements in the algorithms, <span class="math-container">$t_r$</span> is the total time to response, and the subscripts <span class="math-container">$v$</span> and <span class="math-container">$d$</span> designate the variable subscripted as either RL value determination metrics or deep network metrics respectively.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-20T16:46:50.803Z
Answers.Text: "Size is not really quantifiable in a way that is meaningful in this relationship because there is a broader and more complex structure of a network that might be trained to produce a value to use in the RL algorithm chosen.", what? The term "size" has not been defined in this context, but it can be precisely defined. It can e.g. mean the number of layers, or the number of neurons, etc. So, this statement is not really valid. Before answering, you should have asked for clarifications.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-20T16:48:19.470Z
Answers.Text: Furthermore, "speed", in this context, can be used as a synonym for "number of iterations" (or something like that) required to train. So, your answer, in my opinion, is quite, at least, misleading.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-29T18:04:21.987Z
Answers.Text: 1. WOW. just wow. Thank you! I would never have expected such detail! 2. I asked a new question that is hopefully more answerable, because your answer helped me understand more precisely what I wanted to ask. https://ai.stackexchange.com/questions/10298/how-many-gradient-descent-iterations-does-it-take-for-a-neural-network-to-over-f
Answers.UserDisplayName: Gulzar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-29T16:49:36.540Z
Answers.LastActivityDate: 2019-01-29T16:49:36.540Z
Answers.UserDisplayName: Douglas Daseeco
Body: <p>Is there a connection between the approximator network sizes in a RL task and the speed of convergence to an (near) optimal policy or value function?</p>
  
  <p>When thinking about this, I came across the following thoughts:</p>
  
  <ol>
  <li><p>If the network would be too small, the problem won't get enough representation and would never be solved, and the network would converge to its final state quickly.</p></li>
  <li><p>If the network would be infinitely big (assuming no vanishing gradients and the likes), the network would converge to some (desirable) over-fitting, and the network would converge to its final state very slowly, if at all.</p></li>
  <li><p>This probably means there is some golden middle ground.</p></li>
  </ol>
  
  <p>Which leads me to the interesting question:</p>
  
  <p><strong>4. Assuming training time is insignificant relative to running the environment (like in real life environments), then if a network of size M converges to an optimal policy in average after N episodes, would changing M make a predictable change on N?</strong></p>
  
  <p>Is there any research, or known answer to this?</p>
  
  <p>How to know that there is no more need to increase the network size?</p>
  
  <p>How to know if the current network is too large?</p>
  
  <p>Note: please regard question 4 as the main question here.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-20T16:49:27.000Z
Comments.Text: No, I can't simply decide what you want (or don't pretend to receive an exhaustive and precise answers to your questions, given that you're asking a lot of vague questions) To reach a conclusion regarding this question, one may need to do some experiments, and, to do that, these parameters need to be precisely defined. I think you should have just asked a simple question like "How does the number of layers in the NN to represent the value function affect the speed of convergence of a DQN"? This would have been a nice question, IMHO!
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-28T11:47:14.867Z
Comments.Text: What network are you talking about? Feed-forward? What is a network of size M? What is M? The number of layers or the number of nodes per layer?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-28T12:22:37.840Z
Comments.Text: @nbro M can be either the amount of layers, or the amount of nodes, whichever one helps you answer the question more conveniently. The trained network would be either a policy gradient network (of some type), or a q-learning network (again, type is irrelevant). I just want to get a feeling, or an idea how the RL task convergence would be effected by the network architecture (in the most abstract way, that is the network's size)
Comments.UserDisplayName: Gulzar
Tags: <neural-networks><machine-learning><reinforcement-learning><deep-rl>
Title: Is there a relation between the size of the neural networks and speed of convergence in deep reinforcement learning?
UserDisplayName: Gulzar
ThreadText: # Is there a relation between the size of the neural networks and speed of convergence in deep reinforcement learning?
  
  (Asked by: username_0 on 2019-01-28)
  
  Is there a connection between the approximator network sizes in a RL task and the speed of convergence to an (near) optimal policy or value function?
  
  When thinking about this, I came across the following thoughts:
  
  1. If the network would be too small, the problem won't get enough representation and would never be solved, and the network would converge to its final state quickly.
  2. If the network would be infinitely big (assuming no vanishing gradients and the likes), the network would converge to some (desirable) over-fitting, and the network would converge to its final state very slowly, if at all.
  3. This probably means there is some golden middle ground.
  
  Which leads me to the interesting question:
  
  **4. Assuming training time is insignificant relative to running the environment (like in real life environments), then if a network of size M converges to an optimal policy in average after N episodes, would changing M make a predictable change on N?**
  
  Is there any research, or known answer to this?
  
  How to know that there is no more need to increase the network size?
  
  How to know if the current network is too large?
  
  Note: please regard question 4 as the main question here.
  
  **Tags:** neural-networks, machine-learning, reinforcement-learning, deep-rl
  > **Comments:**
  > **username_1**: What network are you talking about? Feed-forward? What is a network of size M? What is M? The number of layers or the number of nodes per layer?  
  > **username_0**: @nbro M can be either the amount of layers, or the amount of nodes, whichever one helps you answer the question more conveniently. The trained network would be either a policy gradient network (of some type), or a q-learning network (again, type is irrelevant). I just want to get a feeling, or an idea how the RL task convergence would be effected by the network architecture (in the most abstract way, that is the network's size)  
  > **username_1**: No, I can't simply decide what you want (or don't pretend to receive an exhaustive and precise answers to your questions, given that you're asking a lot of vague questions) To reach a conclusion regarding this question, one may need to do some experiments, and, to do that, these parameters need to be precisely defined. I think you should have just asked a simple question like "How does the number of layers in the NN to represent the value function affect the speed of convergence of a DQN"? This would have been a nice question, IMHO!  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-01-29. Score: 0 | Accepted answer
  
  Speed and size, no. That's because speed is dependent on processor clock periods and the effective parallel nature of the particular deep RL design in the environment, which is also dependent on cores and host clustering. Size is not really quantifiable in a way that is meaningful in this relationship because there is a broader and more complex structure of a network that might be trained to produce a value to use in the RL algorithm chosen.
  
  * Width for each layer
  * Cell type and possibly activation function for each layer
  * Hyper-parameters
  
  One can say that number of clock cycles times number of effective parallel processors is correlated to all the above, the overhead of the RL algorithm used, and the size of each data tensor.
  
  There are a few inequalities developed in the PAC (probably approximately correct) framework, so it would not be surprising if there were some bounding rules for the relationship between clock cycles, effective parallelism, data widths, activation functions, and RL algorithms for deep RL.
  
  Study of the algorithm, perhaps in conjunction with experimentation, may reveal the primary factors, essentially the processing bottlenecks. Further study of the factors involved in controlling loop iteration counts, which cause the bottleneck, could permit the quantification of computing effort required to maintain a particular maximum allowable response time, but that would be specific to a particular design.
  
  Such might produce a metric that is effectively a count of clock cycles across the system's potentially parallel architecture for a worst case or mean RL action selection. That could then be used to determine the response time for a given system with all of the factors mentioned above fixed, including the priority and scheduling of the processes in each operating system involved.
  
  Here's a guess. Feel free to critique, since such a formulation is a project far beyond the effort that should be put into answering a question online.
  
  $$ t\_r \propto e^{k\_v} \, n\_v \, \eta\_v \, t\_v \, \mu\_v \, \sum c\_v + e^{k\_d} \, n\_d \, \eta\_d \, t\_d \, \mu\_d \, \sum c\_d \; \text{,} $$
  
  where $t$ is time, $k$ is tensor complexity, $n$ is number of cores, $\eta$ is the effective efficiency of the parallel processing, $\mu$ is the effective overhead cost of the glue code, $c$ is the cycles require of the significant (and probably repetitive) elements in the algorithms, $t\_r$ is the total time to response, and the subscripts $v$ and $d$ designate the variable subscripted as either RL value determination metrics or deep network metrics respectively.
  
  > **Comments:**
  > **username_0**: 1. WOW. just wow. Thank you! I would never have expected such detail! 2. I asked a new question that is hopefully more answerable, because your answer helped me understand more precisely what I wanted to ask. https://ai.stackexchange.com/questions/10298/how-many-gradient-descent-iterations-does-it-take-for-a-neural-network-to-over-f  
  > **username_1**: "Size is not really quantifiable in a way that is meaningful in this relationship because there is a broader and more complex structure of a network that might be trained to produce a value to use in the RL algorithm chosen.", what? The term "size" has not been defined in this context, but it can be precisely defined. It can e.g. mean the number of layers, or the number of neurons, etc. So, this statement is not really valid. Before answering, you should have asked for clarifications.  
  > **username_1**: Furthermore, "speed", in this context, can be used as a synonym for "number of iterations" (or something like that) required to train. So, your answer, in my opinion, is quite, at least, misleading.  
  
  ---
  
  