Eliezer is right that a randomized algorithm can't be Bayesian-optimal in this problem, so for any given prior there's a deterministic algorithm with even higher expected benefit

I think the claim is that there must a deterministic algorithm that does at least as well as the randomized algorithm. The randomized algorithm is allowed to be optimal, just not uniquely optimal.