Can stochastic gradient descent be properly used in any sample based learning algorithm in Reinforcement Learning?

Question

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.

Answer 1

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.

Answer 2

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

• The introduction of a paper discussing non-iid stochastic optimisation - 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 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!