I did a very similar exercise after reading the original post. You can get the EV a lot closer to the optimal +0.2 (Although I was unable to prove how close) b

I did a very similar exercise after reading the original post. You can get the EV a lot closer to the optimal +0.2 (Although I was unable to prove how close) by dropping the requirement "do not increase worst-case complexity for the binary search" as this is lost with initial guesses outside 36-64 anyway. Deviating at a higher depth makes punishing specific guesses in the tails a lot cheaper, only giving up 1-2 cents of EV.