Justification for removing bisection for computing KL-confidence regions

[jklaise]

Hi @marcotcr, whilst browsing the repo I noticed that you've removed the bisection part for computing the upper and lower confidence bounds: https://github.com/marcotcr/anchor/commit/ff0924e6bcaaa7149e2940303cd0b22994112157.

The bisection is required to compute the KL-bounds (4) and (5) defined in the bandit paper so I'm a bit puzzled as to why you've removed it. The new behaviour is also not Hoeffding-bound based (3) but rather is equivalent to running bisection just once and then returning whatever is found (note - there is also no guarantee that the bound returned will satisfy the inequalities in (4) and (5) - in practice I think this will result in looser bounds).

[ishcha]

Based on my understanding, I agree with you, @jklaise. The bounds will be looser, but I guess that's the way to scale this method to a larger number of input features.