5
$\begingroup$

In reinforcement learning, in general, successive states (actions and rewards) are highly correlated. An "experience replay" buffer was used, in the DQN architecture, to avoid training the neural network (NN), which represents the $Q$ function, with correlated (or non-independent) data. In statistics, the i.i.d. ("independently and identically distributed") assumption is often made. See e.g. this question. This is another related question. Intuitively, if consecutive data points are often correlated, then we, as humans, might learn slowly (because the differences between the consecutive data points are not sufficient to infer more about the associated distribution).

Mathematically, why exactly do (feed-forward) neural networks (or multi-layer perceptrons) require i.i.d. data (when being trained)? Is this only because we use back-propagation to train NNs? If yes, why would back-propagation require i.i.d. data? Or is actually the optimisation algorithm (like gradient-descent) which requires i.i.d. data? Back-propagation is just the algorithm used to compute the gradients (which is e.g. used by GD to update the weights), so I think that back-propagation isn't really the problem.

When using recurrent neural networks (RNNs), we apparently do not make this assumption, given that we expect consecutive data points to be highly correlated. So, why do feed-forward NNs required the i.i.d. assumption but not RNNs?

I'm looking for a rigorous answer (ideally, a proof) and not just the intuition behind it. If there is a paper which answers this question, you can simply link us to it.

$\endgroup$
2
$\begingroup$

There is an assumption behind the theory training a neural network, or using any piece-wise learning method, that a training sample is representative of the data set as a whole - that it has been sampled fairly from the population that the learning algorithm has been set up to approximate.

The term i.i.d. stands for "independent and identically distributed". If you pick trajectories from RL then the sampling (per individual* record as used to train with) is not independent. Even if you choose the start of the trajectory randomly, you will have made one random choice then your remaining choices are made according to the trajectory - technically they are chosen by the policy and environment dynamics over a single step, which is usually not enough to make the second, third etc steps from a trajectory fully independent random samples from the training population. To make the sampled observations independent, you should make a new random choice, and to be identically distributed that choice has to be made fairly over the whole dataset.

If a subset of samples drawn for a mini-batch (or as consecutive individual samples) are correlated for an online algorithm like gradient descent, it causes a problem. For the algorithm to converge towards a globally optimal solution, it needs errors and the gradients they generate to be unbiased samples of the "true" function gradients across the loss function. Whilst correlated data from a trajectory does not do this at all - it exhibits a strong sampling bias, causing weight updates to move consistently in the wrong direction.

You can demonstrate this effect trying to learn any simple function like $y = x^2$ with $x$ from $-1$ to $+1$. Training a NN with randomly selected $x,y$ pairs results in far better results than training it serially with ~2000 records starting $(-1.000, 1.000) (-0.999, 0.998) (-0.998, 0.996)$ etc

So, why do feed-forward NNs required the i.i.d. assumption but not RNNs?

RNNs do need i.i.d. data, but the "unit" of sampling here is each sequence.


* By "individually" I mean in terms of how they are used in the training process. A "unit" here is the smallest set of records that leads to a complete measure of loss in your optimisation.

It is ok to draw longer trajectories at random if your smallest unit of measurable error is from a trajectory, as in Monte Carlo or TD($\lambda$) for RL, or for RNNs. There can be subtle problems with this - the trajectories still have to be i.i.d. as in they represent fair samples from the assumed population of trajectories.

If you are working at the level of longer trajectories, typically this reduces systemic bias: In RL it reduces bias from initial conditions due to bootstrap process. For RNNs I am less sure what this would mean, but suspect there is some equivalent. Typically, it also increases variance, meaning you may need more training samples. There is a bias/variance trade-off, which is why setting $\lambda$ somewhere between 0 and 1 in TD($\lambda$) is often the optimal choice. Note in RL this is a different source of bias and variance than discussed when considering number of parameters and regularisation in supervised learning.

$\endgroup$
  • $\begingroup$ What is "bias" (or biased samples) with respect to the concept of i.i.d. (random variables)? $\endgroup$ – nbro Feb 23 at 21:43
  • $\begingroup$ @nbro: Sampling bias is when when you do not sample fairly from a population, such that expected values (such as expected mean) are not the same as the population as a whole. $\endgroup$ – Neil Slater Feb 24 at 9:37
  • $\begingroup$ @NeilSlater I understand that. But, more specifically, what is the relation between bias and i.i.d.? For example, if your sample is unbalanced or not representative of the population, then which property of i.i.d. is violated? Identical distribution? The independence property should still be respected (because you might draw your sample randomly). This is one thing that is missing from your answer (even though I understand your idea). I asked about i.i.d. and you do not even mention it. $\endgroup$ – nbro Feb 24 at 10:11
  • $\begingroup$ @nbro: Actually it is independence that is broken - if you sample a whole trajectory then use its components individually you have generated only one random selection and the remainder of your choices are not independent. This typically also breaks the identically distributed constraint. I have added this to the answer. $\endgroup$ – Neil Slater Feb 24 at 11:16
  • 1
    $\begingroup$ "you have generated only one random selection and the remainder of your choices are not independent", you mean that the "random selection" is the first choice in your trajectory and that successive (states, actions, rewards) depend on the initial choice, so they would be dependent on the initial choice? $\endgroup$ – nbro Feb 24 at 13:08
2
$\begingroup$

Suppose that we have some optimization criterion $J(x)$, which we aim to optimize (maybe maximize, maybe minimize), which we can compute for a single example $x$.

In an "ideal world", where we have no restrictions on computation time and memory, we would generally want to run training algorithms on the complete "ground truth" population. For example, if we're training a model (may be a DNN, but may also be some other kind of Machine Learning model), we'd ideally train it on the complete population of all "real-world" images that have ever been produced, ever will be produced, or ever could be produced (and, of course, all with accurate labels). We could write our full optimization criterion as:

$$\sum_{x \in \mathcal{P}} J(x),$$

where $\mathcal{P}$ denotes the complete population. If we have a model that we would like to train using gradient descent (such as a Neural Network), this means we have to compute the gradient with respect to some trainable parameters $\theta$:

$$\nabla_{\theta} \sum_{x \in \mathcal{P}} J(x).$$


In practice, we do not have this ideal scenario, we do not have access to the complete population $\mathcal{P}$. Often, we find ourselves approximating the population with a (hopefully rather large) dataset $\mathcal{D}$. This could be a collection of images like ImageNet, or in (Deep) Reinforcement Learning it could be a large experience replay buffer. If the dataset $\mathcal{D}$ is an accurate representation of the complete population's distribution, we can estimate the gradient of the objective we ultimately care about (computed over the complete population) by the gradient computed over the dataset $\mathcal{D}$:

$$\nabla_{\theta} \sum_{x \in \mathcal{P}} J(x) \approx \nabla_{\theta} \sum_{x \in \mathcal{D}} J(x).$$

Collecting such a dataset rather than the complete population is often actually feasible in practice. If we can afford to compute the objective/gradient over such a complete dataset, that's great. Note that in such a case, the data can already be viewed as being i.i.d.: it's the best approximation we have of a single, complete distribution (the population distribution).


However, computing the objective / gradient over a large complete dataset is often still prohibitively expensive in terms of computation time. This is one of the reasons (not the only one) why we often use minibatches $B$. Then, we approximate the gradient of the objective of the dataset (which is itself an approximation of the gradient for the complete population) by computing it only over a minibatch $B$:

$$\nabla_{\theta} \sum_{x \in \mathcal{P}} J(x) \approx \nabla_{\theta} \sum_{x \in \mathcal{D}} J(x) \approx \nabla_{\theta} \sum_{x \in \mathcal{B}} J(x).$$

If we're repeatedly (over many, many training iterations) going to use such an approximation to take gradient descent steps, it is crucial that the gradient computed over this minibatch is actually an accurate approximation of the "true" gradient over the complete population; if it's not an accurate approximation, we're optimizing the wrong objective! In my opinion, this means that we have an even stronger requirement for our minibatch than just wanting it to be identically distributed. It's not sufficient for our minibatch to be sampled from any arbitrary identical distribution. We want the instances in our minibatch to be sampled from one very specific identical distribution; the dataset/population distribution! If they're not all sampled from that particular distribution, they're an unreliable approximation of the objective we truly care about.


Now, you may wonder if it wouldn't be possible for multiple biased, "unrepresentative" minibatches with "opposite" biases to "cancel each other out" if they're used in different, subsequent gradient descent steps. Couldn't we first run a bunch of gradient descent steps on minibatches that only contain images of dogs, and afterwards "cancel out" any errors by also running a bunch of updates on minibatches containing only images of cats?

If you're lucky, it might work sometimes, but it's unreliable. One problem is that the first iterations using only dog images may cause you to end up in a poor area of the "parameter space", which you would never have ended up in if had used a correct mix of cat and dog images all along. Escaping that poor area may be much more difficult than simply ensuring you never reach it. Another problem is that it would be extremely difficult to find the "correct" number of gradient descent updates to run with cat images. Run too few, you're still stuck recognising only dogs. Run too many, and you may forget how to recognise dogs at all and only start recognising cats. Things like momentum in more sophisticated optimizers will exacerbate this issue.


Note that I don't think the requirement for i.i.d. batches is necessarily unique to gradient descent. Other learning techniques may have the same requirement (maybe for similar reasons, maybe for different reasons).

$\endgroup$
  • $\begingroup$ I don't fully get this part: "Note that in such a case, the data can already be viewed as being i.i.d.: it's the best approximation we have of a single, complete distribution (the population distribution).". If we have a good (that is, that covers the whole population) dataset, then these data points (as a whole) would be identically distributed. But why would they be independent? Does the dependence depend on the order of the data points in the dataset? I understand the concept of i.i.d. in terms of random variables, but maybe I don't fully understand it in the case of realisations (or data). $\endgroup$ – nbro Feb 23 at 21:38
  • $\begingroup$ @nbro If you reach the utopia of an infinitely-sized dataset representative of your true population, in Reinforcement Learning for example this would mean you get an infinitely-sized experience replay buffer with all possible transitions represented in the correct proportions. "the correct proportions" in there are technically still determined by dependencies (the correct proprtions of early-episode transitions influence what the correct proportions for late-episode transitions are). Any individual sample in the infinite dataset can be viewed as independent of any other sample though. $\endgroup$ – Dennis Soemers Feb 24 at 11:29
  • $\begingroup$ Such a "utopia-infinite" experience replay buffer would ideally be constructed simply according to the probabilities of the involved policy and/or environment dynamics, they wouldn't necessarily be generated by truly-experienced trajectories. But yes, as soon as we try to approximate such a dataset by experienced trajectories, we're pretty much doomed to introduce dependenices $\endgroup$ – Dennis Soemers Feb 24 at 11:31
  • $\begingroup$ The exception would be if you choose to only include a single, randomly-selected transition for every complete trajectory you experience. I believe this was done in AlphaGo for example, or maybe it was AlphaGo Zero (not 100% sure). For every full game of self-play they generated, they only added a single randomly-selected game state to their dataset. This eliminates dependencies between the samples, and if you do this for an infinite amount of time, you still get a representative dataset. Of course it's horrible for sample efficiency. $\endgroup$ – Dennis Soemers Feb 24 at 11:33
  • $\begingroup$ "in Reinforcement Learning for example this would mean you get an infinitely-sized experience replay buffer with all possible transitions represented in the correct proportions", if you use experience replay. But what if you don't use it and learn online? $\endgroup$ – nbro Feb 24 at 13:12

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.