Monte Carlo Value Estimates and the Meaning of Quadratic Convergence

Summary

The document raises a terminology question about Monte Carlo estimates in reinforcement learning. It contrasts the familiar result that the standard deviation of an average of independent, finite-variance samples shrinks in proportion to the inverse square root of the sample count with a textbook statement that every-visit Monte Carlo estimates converge quadratically. The author asks whether quadratic refers to a squared rate and whether the statement also applies to first-visit estimates.

The excerpt supplies the variance-scaling result and identifies the point of confusion, but it contains no answer or derivation resolving the terminology. It therefore serves as a prompt for distinguishing convergence of an estimate from the rate at which its error or variance decreases. It gives no trading application, empirical evidence, or detailed conditions for the every-visit result, so readers should consult the underlying reinforcement-learning discussion for those details.

Key ideas

• Averages of independent estimates with finite variance have standard errors that decrease with sample count at an inverse square-root rate.
• The document questions how that rate relates to a textbook description of Monte Carlo convergence as quadratic.
• It asks whether the convergence claim applies to both every-visit and first-visit estimates.
• No answer or proof is provided in the document.

Tags

# Why do Monte-Carlo methods converge quadratically?


# Why do Monte-Carlo methods converge quadratically?












I'm reading Sutton's Reinforcemant Learning: An Introduction, and here's a part from page 93 of this book:

> In this case each return is an independent, identically distributed estimate of $v_\pi(s)$ with finite variance. By the law of large numbers the sequence of averages of these estimates converges to their expected value. Each average is itself an unbiased estimate, and the standard deviation of its error falls as $1/\sqrt{n}$, where $n$ is the number of returns averaged. Every-visit MC is less straightforward, but its estimates also converge quadratically to $v_\pi(s)$

I'm aware that $Var(\bar{X}_n)=\dfrac{\sigma^2}{n}$ and thus "the standard deviation of its error falls as $\dfrac{1}{\sqrt{n}}$". But why does he say that every-visit MC also (which implies that fisrt-MC does too) converge quadratically?

Doesn't the word "quadratic" mean "square"?

Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)

This summary was written by Stratmill's research agent from the original; it is not a copy of the source.