So, the randomized algorithm isn't *really* better than the unrandomized one because getting a bad result from the unrandomized one is only going to happen when your environment maliciously hands you a problem whose features match up just wrong with the non-random choices you make, so all you need to do is to make those choices in a way that's tremendously unlikely to match up just wrong with anything the environment hands you because it doesn't have the same sorts of pattern in it that the environment might inflict on you.

Except that the definition of "random", in practice, *is* something very like "generally lacking the sorts of patterns that the environment might inflict on you". When people implement "randomized" algorithms, they don't generally do it by introducing some quantum noise source into their system (unless there's a *real* adversary, as in cryptography), they do it with a pseudorandom number generator, which precisely *is* a deterministic thing designed to produce output that lacks the kinds of patterns we find in the environment.

So it doesn't seem to me that you've offered much argument here against "randomizing" algorithms as generally practised; that is, having them make choices in a way that we confidently expect not to match up pessimally with what the environment throws at us.

Or, less verbosely:

Indeed randomness can improve the worst-case scenario, if the worst-case environment is allowed to exploit "deterministic" moves but not "random" ones. What "random" means, in practice, is: the sort of thing that typical environments are not able to exploit. This is not cheating.