BGonline.org Forums

Variance Reduction

Posted By: Tom Keith
Date: Monday, 21 July 2014, at 5:53 p.m.

In Response To: Variance Reduction (rambiz)

Hi Rambiz,

I think, there exists some consensus on how to calculate a confidence interval for a long Bernoulli experiment (by using the normal distribution). However, I don't know how to factor in the effect of Variance Reduction. I know that Variance Reduction virtually increases the number of trials but I don't know by how much!

It turns out you don't need to factor in the effect of VR. The method of calculating confidence intervals is exactly the same whether you are using VR or not. Just use the actual number of trials (not the virtual one).

A rollout (whether using VR or not) essentially takes a sample of the possible rollout results. You then calculate a sample standard deviation using the formula:

std dev = sqrt( 1/(n-1) * (sum from 1 to n of (x[i]-xMean)^2) )

where "n" is the number of trials, "x[i]" is the rollout result of the ith trial. and "xMean" is the average of all the x[i]'s. Then use the standard deviation to calculate confidence intervals. The fact that there is VR going doesn't affect how the formula works. The formula is working with the final numbers -- it doesn't know (or care) how those numbers were produced.

Since I can't reproduce the reported numbers, I have no faith in what the bot says, in the first place.

If you doubt the bot's numbers, maybe you could do a series of 1-trial rollouts, each time with a different seed, and save the results. (Hopefully there is a way to write a script to do this.) Then you could take the variance-reduced numbers and go through the calculations yourself or just scan the numbers and observe how much (or how little) variance there is.

It appears to me that the confidence intervals XG reports converge too fast

In the position you posted earlier, I would expect narrow confidence intervals if a one-sided database is available. A one-sided database gives very accurate estimates of the luck associated with each roll, at least until the positions get lop-sided and one side is desperate for doubles.

Just to illustrate the effect, suppose you set up a rollout with both sides having all their checkers home, and used a two-sided database. In that case, a single trial with VR is enough to get an exact result. The two-sided database allows the VR to work perfectly.

Post Response

Subject:
Message: