1
$\begingroup$

Assuming we use an MSE cost function of the form

$$ \sum_s\mu(s)(V_{\pi}(S_t)-\hat{V}(S_t,\theta_t))^2 = E_{\mu(s)}[(V_{\pi}(S_t)-\hat{V}(S_t,\theta_t))^2])$$

The Stochastic Gradient Descent is used to approximate the true update algorithm, which looks like this

$$\theta_{t+1} = \theta_{t} - \frac{\eta_t}{2}\nabla_{\theta}(E_{\mu(s)}[(V_{\pi}(S_t)-\hat{V}(S_t,\theta_t))^2])$$

to this

$$\theta_{t+1} = \theta_{t} - \frac{\eta_t}{2}\nabla_{\theta}(U_t-\hat{V}(S_t,\theta_t))^2$$

where, for simplicity, $U_t$ represents an unbiased estimate of the true value function $V_{\pi}(s_t)$. This expression is the source of many learning algorithms used in reinforcement learning.

One of the conditions for SGD requires that samples used for updating the parameters must be I.I.D according to the distribution $\mu(s)$. However, in both on-policy and off-policy learning methods, updates at each time-step are based on trajectories generated. Since, along a trajectory, the state $s_{t+1}$ depends on the state at ${s_t}$, this means that the sample used to update $\theta_t$ and $\theta_{t+1}$ are not independent. Many, if not all, sample-based learning algorithms used in RL rely on using SGD, such as the Gradient Monte Carlo Algorithm but I've not really seen anywhere that mentions these algorithms have the "issue" that I mention so I feel like I'm missing something. More formally,


My Question: Does the fact that parameter updates are not I.I.D mean we can't really use stochastic gradient descent AT ALL in learning algorithms, and, if so, why then do these algorithms "work"?


As far as I know, this question applies equally to all forms of parameterised function approximation that are used with learning algorithms (tabular functions*, linear functions and non-linear functions). But, if anyone knows a special reason as to whether these cases should be treated separately could they make clear why

*I understand that when learning algorithms with tabular functions, there exists theory beyond SGD that ensures convergence, however, I'm not entirely sure what this theory is and whether if this makes them exempt, so if anyone knows whether or not it does make them exempt could they also make this clear!


Edit:

It has been highlighted in the comments that replay buffers have been used to resolve the issue of correlated sampling in cases such as DQN and variants of it. This implies correlated sampling is an issue in these cases. Aside from this, I've not heard of replay buffers being used elsewhere (correct me if I'm wrong), so why are replay buffers needed with this off-policy NN approach but not in other learning algorithms given that they all suffer from the issue of correlated sampling.

$\endgroup$
9
  • 1
    $\begingroup$ off-policy methods uses samples from trajectories but they are typically sampled uniformly at random from a replay buffer, so at any given time the samples you're using to perform the update are i.i.d. (there would be a non-zero probability that you could draw two samples that 'consecutively' followed each other in a trajectory but this probability will be extremely small for a large replay buffer). Also, tabular methods are not parameterised function approximations. There are no parameters involved and we are not approximating the value functions. $\endgroup$ – David Ireland Jan 29 at 10:46
  • $\begingroup$ Addressing your second point, can't tabular methods be considered as a parameterised function approximation where we have a parameter corresponding to each state/state-action pair? furthermore, even when using tabular methods, we start of with an initial estimate of value functions and update them using value-iteration or a similar algorithm, this estimate/approximation only converges to the true value function as the number of updates tend to infinity. $\endgroup$ – quest ions Jan 29 at 10:58
  • $\begingroup$ hmm, yes, I suppose they can, but usually in RL if you refer to function approximation you are talking about using a parameterised function to represent the look-up table. Yes, okay, you are technically always 'approximating' the value functions, unless as you say you can allow the algorithms to run for an infinite amount of time. The latter part of your question asks whether tabular methods are 'exempt' from your main question about SGD which is yes they absolutely are because tabular methods don't use SGD. $\endgroup$ – David Ireland Jan 29 at 11:05
  • $\begingroup$ As for your first point, replay buffers do help resolve the issue of iid sampling but i've only ever seen it in discussed in special cases such DQNs (off-policy non-linear function approximators) whereas the issue I raise is, i believe, more general than this. Replay buffers could probably be used to resolve this issue in general but I guess I am wondering if it is even an issue because it doesn't really seem to be mentioned anywhere $\endgroup$ – quest ions Jan 29 at 11:06
  • $\begingroup$ replay buffers solve the problem in general, as long as they can be used, and they can be used in theory for any off-policy learning algorithm. They are used in many algorithms such as DQN as its variants, DDPG, Soft Actor Critic. It is hard to say whether it is a problem in general as there is much more research involving off-policy algorithms due to their superior sample efficiency. I have certainly trained an algorithm using on-policy algorithms (e.g. actor-critic) and not encountered any issues but this was on very simple environments. $\endgroup$ – David Ireland Jan 29 at 11:13
3
$\begingroup$

First I will address the issue of Tabular methods. These do not use SGD at all. Although the updates are very similar to an SGD update there is no gradient here and so we are not using SGD. Many Tabular methods are proven to converge, for instance the paper by Chris Watkins titled "Q-Learning" introduces and proves that Q-learning converges. Also you include tabular methods as being parameterised function approximators. This is not true. Tabular methods maintain an estimate of the value function in a look-up table for each state-action pair and there is no function approximator being used.

Now for non-tabular methods, i.e. Deep Reinforcement Learning. Here we are using SGD only to optimise the parameters of the networks (assuming of course that we are using NN's as our function approximators, but this is a fair assumption if you read the literature). This is why off-policy methods are typically preferred because they can use a replay buffer which allows the use of data from any past trajectory. When using a replay buffer we sample random past experiences which de-correlates the data and allows the i.i.d. assumption to hold when using SGD.

If we were to use an on-policy algorithm, in theory SGD may not converge to any local optima because we are violating the i.i.d. assumption. However, all this means is that we are not guaranteed to converge. For instance, I have run an experiment using REINFORCE (an on-policy learning algorithm) using NN's as function approximators and they were able to obtain an optimal policy. However, this was for a very simple environment using modestly sized networks, so this is likely why they were able to be trained using non-i.i.d. data. A more in depth question/answer as to why NN's require i.i.d. data can be found here.

To address your edit, Replay Buffers are not required but if we can use them, then why would we not? It helps to maintain the i.i.d. assumption and so it helps us obtain a local optima. If we did not use them then there would not be the guarantee that it would converge. As an aside, Replay Buffers are typically used because they make the algorithm have a greater sample efficiency - this means we can obtain an optimal policy using much less data.

If you are wondering why don't on-policy methods use a replay buffer, the answer is because they are on-policy. The actions used in updates must be taken according to our current policy that we are learning the value functions for (or are optimising the policy of in Policy Gradient Methods). This is not the case in off-policy algorithms - e.g. in Q-learning we are learning the value functions of the greedy policy but we follow a different policy that allows for exploration.

$\endgroup$
10
  • $\begingroup$ Thanks for the thoughtful answer, I didn't know replay buffers couldn't be used on-policy that was interesting to find out. I had a look at the proof by Watkins, even there the robinson monroe conditions need to be satisfied for the proof, bounded learning rates, which is a requirement for stochastic approximation en.wikipedia.org/wiki/Stochastic_approximation, so i'm not convinced on this point still i'm afraid. Although I'm happy to concede that correlated sampling is not a concern in this case as a result of Chris Watkins proof. $\endgroup$ – quest ions Jan 30 at 22:54
  • $\begingroup$ i thought I may have missed something but I guess there are no assurances of convergence in non-tabular on-policy methods which is surprising and even in off-policy methods replay buffers only mitigate the issue. I guess in practice convergence is never really achieved anyway, and sometimes not even preferred, as long as these methods can reduce the error to some degree they are appropriate $\endgroup$ – quest ions Jan 30 at 23:04
  • 1
    $\begingroup$ what exactly are you not convinced by? if you could be clear with your question maybe I can shed some more light on it, but as for the actual question you asked in your main question, I have answered this so there’s nothing left to be ‘convinced’ about. $\endgroup$ – David Ireland Jan 31 at 0:12
  • 1
    $\begingroup$ I explained this in the answer. IID data is required to guarantee convergence to a local optima. Just because it isn’t satisfied it doesn’t mean it wont happen. I know DRL are not the only non-function approximators, but they will never (except in extremely rare cases) be used in practice whilst DRL offers such great performance. There a proofs out there (if I remember correctly) that show that using linear function approximators to approximate a value function will still converge for certain algorithms. $\endgroup$ – David Ireland Jan 31 at 9:43
  • 1
    $\begingroup$ I don’t think you will find an answer as to why these methods using eg NNs as function approximators still converge in practice (most of the time). It is a huge gap in the theory of RL and an open research question. $\endgroup$ – David Ireland Jan 31 at 9:44
-1
$\begingroup$

As David Ireland has mentioned in his answer, despite correlated sampling, learning algorithms can still converge to the optimal policy/value function.

The reason learning algorithms still may produce the correct results despite the use of correlated sampling is to do with another property, that does not rely on i.i.d sampling, that is, the average regret of SGD tends to zero at the limit. A couple of sources I found that highlight this are

Minimising average regret implies that the SGD will, at the limit, produce the best set of parameters that perform well on the encountered samples however this is does not indicate whether the best set of parameters actually performs well.

Extra

This is in fact a general issue that extends beyond the reinforcement learning algorithms. Programs that implement SGD don't typically sample IID! as mentioned in an MIT lecture on stochastic gradient descent at around 40 minutes the lecturer discusses it's more efficient to sample without replacement from the training set making it non IID for which there is not much theory about.


caveat

I'm not 100% sure what the implication of minimising regret means but given regret is of the form

$$regret(\theta_1,\ldots,\theta_t) = \sum_{t=0}^T\left(L(v_\pi(s_t),\hat{v}(s_t,\theta_i) -L(v_\pi(s_t),\hat{v}(s_t,\theta_*)\right)$$

Then I understand the model that minimises regret at time T as the one that has the minimum loss for all training samples encountered up to time T . But what I'm not sure about is how this relates to minimising the cost function, it probably requires another question!

$\endgroup$
2
  • $\begingroup$ The fact that your answer seems quite different from the other answer shows that your question was originally unclear. Please, next time, before asking a question make sure to clarify what you're really looking for. I would also suggest that you make the title of your question more consistent with your actual question and the question in the body, so that people do not intepret your question in multiple ways, depending on what they think your doubt is. $\endgroup$ – nbro Feb 2 at 11:44
  • $\begingroup$ I think this is more an issue with the clarity of my answer, what I'm trying to explain here is why reinforcement learning algorithms may work despite samples not being I.I.D although I haven't explicitly said this which I should probably do. My answer is more of a supplement to the other answer that indicates reinforcement learning algorithms can work despite non-iid sampling and suggests ways to circumvent the issue of non-iid sampling. I'll edit my answer to highlight this $\endgroup$ – quest ions Feb 2 at 15:02

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.