We review the proof by Robbins and Munro for finding fixed points. Stochastic gradient descent, Q-learning and a bunch of other stochastic algorithms can be seen as variants of this basic algorithm. We review the basic ingredients of the original proof.

Often it is important to find a solution to the equation

by evaluating at a sequence of points. For instance Newton’s method would perform the updates . However, Robbins and Munro consider the setting where we cannot directly observe but we might observe some random variable whose mean is . Thus we observe

and hope solve for . Notice in this setting, even if we can find , Newton’s method may not converge. The key idea of Robbins and Munro is to use a schema

where we chose the sequence so that

Before proceeding here are a few different use cases:

**Quartiles.**We want to find such that for some fixed . But we can only sample the random variable .**Regression.**We preform regression , but rather than estimate we want to know where .**Optimization.**We want to optimize a convex function whose gradient is . Assume that for some large . To find the optimum at we randomly sample (uniformly) whose gradient, , is an bias estimate of .

## Robbins-Munro Proof.

We now go through the main steps of Robbins and Munro’s proof. This proof is intentionally not the most general but instead gives the key ideas.

We assume that is an increasing, smooth, real-valued function from to and that there is a unique point such that . Further assume and that samples belong to the interval and .

In the steps below we prove the following:

**Thrm** [Robbins-Munro] If we chose acording to the Robbin-Munro step rule then we have that

where here satisfies .

**Ex 1.** Let . Show that for Robbins-Munro

for terms

**Ans 1.**

as required.

**Ex 2.** Argue that for some constant .

**Ans 2.** Since is increasing, smooth and it must be that

Thus

**Ex 3.** Argue that if then and exists.

**Ans 3.** Summing the expression for [[RM:1]] over gives

Since is bounded and is finite it must be that and exists.

**Ex 4.** Finally argue that if then

**Ans 4.** We know from [3] and [3] that

Since we choose so that . It must be that . Further since we know the limit exists it must be that , as required.