What is the double sample problem in reinforcement learning?

According to the SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation for convergent reinforcement learning, the Smoothed Bellman operator is a way to dodge the double sample problem? Can someone explain to me what the double sample problem is and how SBEED solves it?

The double sampling problem is referenced in Chaper 11.5 Gradient Descent in the Bellman Error in Reinforcement Learning: An Introduction (2nd edition).

From the book, this is the full gradient descent (as opposed to semi-gradient descent) update rule for weights of an estimator that should converge to a minimal distance from the Bellman error:

$$w_{t+1} = w_t + \alpha[\mathbb{E}_b[\rho_t[R_{t+1} + \gamma\hat{v}(S_{t+1},\mathbf{w})] - \hat{v}(S_{t},\mathbf{w})][\nabla\hat{v}(S_{t},\mathbf{w})- \gamma\mathbb{E}_b[\rho_t\nabla\hat{v}(S_{t+1},\mathbf{w})]]$$

[...] But this is naive, because the equation above involves the next state, $$S_{t+1}$$, appearing in two expectations that are multiplied together. To get an unbiased sample of the product, two independent samples of the next state are required, but during normal interaction with an external environment only one is obtained. One expectation or the other can be sampled, but not both.

Basically, unless you have an environment that you can routinely re-wind and re-sample to get two independent estimates (for $$\hat{v}(S_{t+1},\mathbf{w})$$ and $$\nabla\hat{v}(S_{t+1},\mathbf{w})$$) then the update rule that naturally arises from gradient descent on the Bellman error does will work any better than other approaches, such as semi-gradient methods. If you can do this rewind process on every step, then it may be worth it because of the guarantees of convergence, even in off-policy with non-linear approximators.

The paper proposes a workaround for this issue, keeping the robust convergence guarantees, but dropping the need to collect two independent samples of the same estimate on each step.

We cannot approximate $$E^2(x)$$ by $$\frac{1}{N} \sum_i x_i \frac{1}{N} \sum_j x_j$$. Because $$cov(x)=E(x^2)-E^2(x)$$.

• Hello. This answer is quite short. Maybe you could elaborate a little bit more and tell us more in detail how this answers the question(s). For example, how does this answer the question "what is the double sample problem"?
– nbro
May 28 '21 at 13:40