Fix O(N) fallbacking

[motiwari]

This has several steps:

• Understand whether min_impurity_reduction is normalized by dataset size or not

• Implement a min_impurity_reduction filter -- so filter those points whose LCB** is above the min_impurity_reduction

• Identified tied_arms as those with a UCB* within epsilon of the best candidate (default epsilon = 10%)

• If the only candidates are tied_arms, then stop sampling and choose the best candidate

• For exact ties, choose randomly

• we use UCB here because if there's extremely large variance, the LCB can be under the epsilon threshold --> not what we want ** Similar comment, arm could be discarded erroneously this time

[motiwari]

Yes, min_impurity_reduction is normalized by the dataset size. Since we use proportions, we're only using p in the calculation of impurity.

The same is true for entropy.

It looks like the same is true for MSE, but I'm not sure. Since it is "mean" I would expect so