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.

  • $\begingroup$ 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? $\endgroup$
    – nbro
    Jan 28 '19 at 11:47
  • $\begingroup$ @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) $\endgroup$
    – Gulzar
    Jan 28 '19 at 12:22
  • $\begingroup$ 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! $\endgroup$
    – nbro
    Feb 20 '19 at 16:49

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.

  • $\begingroup$ 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. ai.stackexchange.com/questions/10298/… $\endgroup$
    – Gulzar
    Jan 29 '19 at 18:04
  • $\begingroup$ "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. $\endgroup$
    – nbro
    Feb 20 '19 at 16:46
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Feb 20 '19 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.