I'm not sure why the author picks Myth #5 as the big pro-frequentist point. The "online learning" problem he's describing is a simple multi-armed bandit problem. The magical frequentist algorithm that he's touting is UCB-1. It's a great algorithm, it has finite-time optimality guarantees like he mentions. However, it still has a tuning parameter that can matter quite a bit in practice. Also, the Bayesian approach to MABs is Thompson sampling, which is also finite-time optimal. I guess I don't get the big deal on this point.

From a machine learning perspective, frequentist methods are great because they scale. All of these fancy nonparametric Bayes methods coming out these days take weeks to run and include so many approximations that you've got no idea whether what you're actually inferring is truly similar to the original model.

The biggest problem with frequentist methods is that they are conceptually odd in their approach. Bayesians take the view that you should fix the data and integrate over the possible parameters. Frequentists take the view that you should fix the parameters and integrate over the data. That is kind of weird to me.

So you either start out conceptually pure as a Bayesian and compromise to the point of meaninglessness or you abandon your morals at the start as a frequentist and things go smoothly from there.

Edit: As noted below, it's actually Exp3 rather than UCB-1. I glossed over the part about potentially adversarial bandits.