Answers.Body: <p>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 <em>no gradient</em> here and so we are not using SGD. Many Tabular methods are proven to converge, for instance the paper by Chris Watkins titled &quot;Q-Learning&quot; 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.</p>
  <p>Now for non-tabular methods, i.e. Deep Reinforcement Learning. Here we are using SGD <em>only to optimise the parameters of the networks</em> (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.</p>
  <p>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 <em>guaranteed</em> 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 <a href="https://ai.stackexchange.com/questions/10839/why-exactly-do-neural-networks-require-i-i-d-data?noredirect=1&amp;lq=1">here</a>.</p>
  <p>To address your edit, Replay Buffers are not <em>required</em> 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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-30T22:54:27.380Z
Answers.Text: 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 https://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.
Answers.UserDisplayName: quest ions
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-30T23:04:04.583Z
Answers.Text: 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
Answers.UserDisplayName: quest ions
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-31T00:11:50.760Z
Answers.Text: @questions You may be interested in [this question](https://ai.stackexchange.com/q/11679/2444).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-31T00:12:44.760Z
Answers.Text: 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.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-31T06:58:00.573Z
Answers.Text: Your provide an anecdotal example of an on-policy algorithm that worked for you in one case, your reason speculates why it may or may not have worked for you in this context. I'm looking for a rigorous answer that can address the following points 1) If SGD conditions are violated should convergence ever occur? 2) if convergence can occur why? does it converge to the right place? under what cases? Although its useful to know about practical implementations and features such as replay buffers that can help, I'm just focused purely on these algos from a theoretical standpoint
Answers.UserDisplayName: quest ions
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-31T06:58:42.607Z
Answers.Text: Also, non-tabular methods doesn't mean Deep RL as i mention in the original question there are other function approximators, not just DNNs. In fact there is a lot more theory that exists for linear function approximators since they have convex cost functions and the fact they can be easily expressed, but again correlated sampling should mean we violate the conditions of the very algorithms we use to optimise them
Answers.UserDisplayName: quest ions
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-31T09:43:06.777Z
Answers.Text: 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.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-31T09:44:30.640Z
Answers.Text: 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.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-31T12:01:58.153Z
Answers.Text: "IID data is required to guarantee convergence to a local optima" That is just paraphrasing what I said in the question. "Just because it isn’t satisfied it doesn’t mean it wont happen" - When you use any tool in any context, if the use case conditions of the tool are not  satisfied why should you expect the tool to work at all let alone "most of the time".
Answers.UserDisplayName: quest ions
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-31T12:10:46.250Z
Answers.Text: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/119154/discussion-between-david-ireland-and-quest-ions).
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-30T19:47:22.117Z
Answers.LastActivityDate: 2021-01-30T19:47:22.117Z
Answers.UserDisplayName: David
Answers.Body: <p>As David Ireland has mentioned in his answer, despite correlated sampling, learning algorithms can still converge to the optimal policy/value function.</p>
  <p>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</p>
  <ul>
  <li><p>Page 26 of the slides available from the computer science department at the university of British Columbia <a href="https://www.cs.ubc.ca/%7Eschmidtm/Courses/340-F15/L19.pdf" rel="nofollow noreferrer">Machine Learning and Data mining</a></p>
  </li>
  <li><p><a href="http://opt.kyb.tuebingen.mpg.de/papers/opt2011_agarwal.pdf" rel="nofollow noreferrer">The introduction of a paper discussing non-iid stochastic optimisation</a> - A. Agarwal and John C. Duchi</p>
  </li>
  </ul>
  <p>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.</p>
  <p><strong>Extra</strong></p>
  <p>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 <a href="https://www.youtube.com/watch?v=k3AiUhwHQ28" rel="nofollow noreferrer">in an MIT lecture on stochastic gradient descent</a> 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.</p>
  <hr />
  <p><strong>caveat</strong></p>
  <p>I'm not 100% sure what the implication of minimising regret means but given regret is of the form</p>
  <p><span class="math-container">$$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)$$</span></p>
  <p>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!</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-02T11:44:18.123Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-02T15:02:56.777Z
Answers.Text: 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
Answers.UserDisplayName: quest ions
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-02T07:29:30.433Z
Answers.LastActivityDate: 2021-02-02T15:22:24.203Z
Answers.LastEditDate: 2021-02-02T15:22:24.203Z
Answers.UserDisplayName: quest ions
Body: <p>Assuming we use an MSE cost function of the form</p>
  <p><span class="math-container">$$ \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])$$</span></p>
  <p>The Stochastic Gradient Descent is used to approximate the true update algorithm, which looks like this</p>
  <p><span class="math-container">$$\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])$$</span></p>
  <p>to this</p>
  <p><span class="math-container">$$\theta_{t+1} = \theta_{t} - \frac{\eta_t}{2}\nabla_{\theta}(U_t-\hat{V}(S_t,\theta_t))^2$$</span></p>
  <p>where, for simplicity, <span class="math-container">$U_t$</span> represents an unbiased estimate of the true value function <span class="math-container">$V_{\pi}(s_t)$</span>. This expression is the source of many learning algorithms used in reinforcement learning.</p>
  <p>One of the conditions for SGD requires that samples used for updating the parameters must be I.I.D according to the distribution <span class="math-container">$\mu(s)$</span>. 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 <span class="math-container">$s_{t+1}$</span> depends on the state at <span class="math-container">${s_t}$</span>, this means that the sample used to update <span class="math-container">$\theta_t$</span> and <span class="math-container">$\theta_{t+1}$</span> are not independent. Many, if not all, sample-based learning algorithms used in RL rely on using SGD, such as the <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=224" rel="nofollow noreferrer">Gradient Monte Carlo Algorithm</a> but I've not really seen anywhere that mentions these algorithms have the &quot;issue&quot; that I mention so I feel like I'm missing something. More formally,</p>
  <hr />
  <p>My Question: <em>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 &quot;work&quot;?</em></p>
  <hr />
  <p>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</p>
  <p>*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!</p>
  <hr />
  <p><strong>Edit:</strong></p>
  <p>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.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-29T10:46:10.547Z
Comments.Text: 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.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-29T10:58:38.813Z
Comments.Text: 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.
Comments.UserDisplayName: quest ions
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-29T11:05:20.777Z
Comments.Text: 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.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-29T11:06:55.430Z
Comments.Text: 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
Comments.UserDisplayName: quest ions
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-29T11:13:10.227Z
Comments.Text: 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.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-29T11:18:17.437Z
Comments.Text: Also the general form of the TD/MC update algorithms stem from using SGD. The general form can then be reduced to special cases depending on the type of function approximator used (such as the tabular approximator)
Comments.UserDisplayName: quest ions
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-29T11:21:33.640Z
Comments.Text: they don't use SGD explicitly, there is no gradient being taken anywhere in the updates. Either way, the answer to your question regarding tabular methods is that there is no assumption that the updates must require i.i.d samples. All of the 'main' methods that you will have seen for the tabular case (MC/TD learning/Q-learning) all are proven to converge.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-29T11:29:54.423Z
Comments.Text: SGD theory is used, the "stepsize" is the learning rate and the different between the target and our estimate is the gradient. Here's a link to another SE question where this is briefly discussed
  
  https://ai.stackexchange.com/questions/18187/is-there-a-simple-proof-of-the-convergence-of-td0
Comments.UserDisplayName: quest ions
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-29T11:31:23.303Z
Comments.Text: that link does not mention SGD, they talk about stochastic approximation theory which is not the same thing (thought they may be related). You are certainly drawing analogs to SGD, which you are correct because they have similar update rules. But our estimate is _not_ a gradient of any function.
Comments.UserDisplayName: David
Tags: <reinforcement-learning><deep-rl><function-approximation><experience-replay><stochastic-gradient-descent>
Title: Can stochastic gradient descent be properly used in any sample based learning algorithm in Reinforcement Learning?
UserDisplayName: quest ions
ThreadText: # Can stochastic gradient descent be properly used in any sample based learning algorithm in Reinforcement Learning?
  
  (Asked by: username_0 on 2021-01-29)
  
  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](http://incompleteideas.net/book/RLbook2020.pdf#page=224) 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.
  
  **Tags:** reinforcement-learning, deep-rl, function-approximation, experience-replay, stochastic-gradient-descent
  > **Comments:**
  > **username_1**: 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.  
  > **username_0**: 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.  
  > **username_1**: 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.  
  > **username_0**: 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  
  > **username_1**: 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.  
  > **username_0**: Also the general form of the TD/MC update algorithms stem from using SGD. The general form can then be reduced to special cases depending on the type of function approximator used (such as the tabular approximator)  
  > **username_1**: they don't use SGD explicitly, there is no gradient being taken anywhere in the updates. Either way, the answer to your question regarding tabular methods is that there is no assumption that the updates must require i.i.d samples. All of the 'main' methods that you will have seen for the tabular case (MC/TD learning/Q-learning) all are proven to converge.  
  > **username_0**: SGD theory is used, the "stepsize" is the learning rate and the different between the target and our estimate is the gradient. Here's a link to another SE question where this is briefly discussed  https://ai.stackexchange.com/questions/18187/is-there-a-simple-proof-of-the-convergence-of-td0  
  > **username_1**: that link does not mention SGD, they talk about stochastic approximation theory which is not the same thing (thought they may be related). You are certainly drawing analogs to SGD, which you are correct because they have similar update rules. But our estimate is _not_ a gradient of any function.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2021-01-30. Score: 3
  
  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](https://ai.stackexchange.com/questions/10839/why-exactly-do-neural-networks-require-i-i-d-data?noredirect=1&lq=1).
  
  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.
  
  > **Comments:**
  > **username_0**: 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 https://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.  
  > **username_0**: 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  
  > **username_2**: @questions You may be interested in [this question](https://ai.stackexchange.com/q/11679/2444).  
  > **username_1**: 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.  
  > **username_0**: Your provide an anecdotal example of an on-policy algorithm that worked for you in one case, your reason speculates why it may or may not have worked for you in this context. I'm looking for a rigorous answer that can address the following points 1) If SGD conditions are violated should convergence ever occur? 2) if convergence can occur why? does it converge to the right place? under what cases? Although its useful to know about practical implementations and features such as replay buffers that can help, I'm just focused purely on these algos from a theoretical standpoint  
  > **username_0**: Also, non-tabular methods doesn't mean Deep RL as i mention in the original question there are other function approximators, not just DNNs. In fact there is a lot more theory that exists for linear function approximators since they have convex cost functions and the fact they can be easily expressed, but again correlated sampling should mean we violate the conditions of the very algorithms we use to optimise them  
  > **username_1**: 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.  
  > **username_1**: 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.  
  > **username_0**: "IID data is required to guarantee convergence to a local optima" That is just paraphrasing what I said in the question. "Just because it isn’t satisfied it doesn’t mean it wont happen" - When you use any tool in any context, if the use case conditions of the tool are not  satisfied why should you expect the tool to work at all let alone "most of the time".  
  > **username_1**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/119154/discussion-between-david-ireland-and-quest-ions).  
  
  ---
  
  ### Answer by username_0 on 2021-02-02. Score: -1
  
  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
  
  * Page 26 of the slides available from the computer science department at the university of British Columbia [Machine Learning and Data mining](https://www.cs.ubc.ca/%7Eschmidtm/Courses/340-F15/L19.pdf)
  * [The introduction of a paper discussing non-iid stochastic optimisation](http://opt.kyb.tuebingen.mpg.de/papers/opt2011_agarwal.pdf) - A. Agarwal and John C. Duchi
  
  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](https://www.youtube.com/watch?v=k3AiUhwHQ28) 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!
  
  > **Comments:**
  > **username_2**: 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.  
  > **username_0**: 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  
  
  ---
  
  