A slight tangent here, but Blum loses me even before the considerations that Eliezer has so clearly pointed out. Comparing an upper bound for the worst case of one algorithm with an upper bound for the average case of the other is meaningless. Even were like things being compared, mere upper bounds of the true values are only weak evidence of the quality of the algorithms.
FWIW, I ran a few simulations (for the case of complete independence of all experts from themselves and each other), and unsurprisingly, the randomised algorithm performed on average worse than the unrandomised one. In addition, the weighting algorithm converges to placing all of the weight on the best expert. If the experts’ errors are at all independent, this is suboptimal.
Actual performance of both algorithms was far better than the upper bounds, and rather worse than one using optimal weights. I cannot see these upper bounds as anything more than a theoretical irrelevance.
A slight tangent here, but Blum loses me even before the considerations that Eliezer has so clearly pointed out. Comparing an upper bound for the worst case of one algorithm with an upper bound for the average case of the other is meaningless. Even were like things being compared, mere upper bounds of the true values are only weak evidence of the quality of the algorithms.
FWIW, I ran a few simulations (for the case of complete independence of all experts from themselves and each other), and unsurprisingly, the randomised algorithm performed on average worse than the unrandomised one. In addition, the weighting algorithm converges to placing all of the weight on the best expert. If the experts’ errors are at all independent, this is suboptimal.
Actual performance of both algorithms was far better than the upper bounds, and rather worse than one using optimal weights. I cannot see these upper bounds as anything more than a theoretical irrelevance.