Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

Eliezer_Yudkowsky comments on Worse Than Random - Less Wrong

25 Post author: Eliezer_Yudkowsky 11 November 2008 07:01PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (99)

Sort By: Old

You are viewing a single comment's thread.

Comment author: Eliezer_Yudkowsky 12 November 2008 03:27:22AM 1 point [-]

To be precise, in every case where the environment only cares about your actions and not what algorithm you use to produce them, any algorithm that can be improved by randomization can always be improved further by derandomization.

Comment author: timtyler 23 January 2010 05:33:27PM 1 point [-]

Even the passing of http://en.wikipedia.org/wiki/Diehard_tests?

Randomness works pretty well!

Comment author: Eliezer_Yudkowsky 23 January 2010 05:36:19PM 1 point [-]

Sure. Start with random numbers. Then run the Diehard tests over them. If the Diehard tests fail, try different random numbers. There you go, algorithm derandomized.

Comment author: timtyler 23 January 2010 10:03:37PM 2 points [-]

That's an "improvement" that's unlikely to happen before universal heat death.

Improving an algorithm by adding randomness is simple in many cases - while improving it further may be totally impractical and ineffectual.

Comment author: Eliezer_Yudkowsky 23 January 2010 10:27:51PM 2 points [-]

Certainly. That, however, is a mere matter of limited computing power, not of theory.

Comment author: timtyler 23 January 2010 11:09:49PM *  4 points [-]

The uncertainty principle would appear to represent a problem for the thesis. Secure hardware random number generators are "really difficult" to predict. That appears to be a case where you can't - in practice - beat a random strategy - whereas a random strategy beats all kinds of stupid strategies.

The "any algorithm that can be improved by randomization" is redundant - and does no useful conceptual work. Idiotic algorithms that can be improved by adding randomness are two-a-penny.

The "can always be improved further by derandomization" is not true - in practice. Sometimes, you just can't find a way to do any better than the random algorithm.

I think the correct principle in this area is that a deterministic algorithm can always do at least as well as a random one - provided its workings can be kept secret.

The main problem case for this principle occurs when you face an opponent with a lot of resources and cryptographic skills - but with sufficient care you should be able to keep them busy until the universal heat death.

Comment author: Tyrrell_McAllister 23 January 2010 10:34:57PM *  5 points [-]

I think that this is a better de-randomization: Presumably there is some set S of numbers that have been observed to pass Diehard tests reliably. The de-randomized algorithm is simply to read off S. Computationally, this is cheaper than generating your own random set and reading it off.

ETA: And, if I'm not mistaken, if S has already been observed to pass Diehard tests reliably, then it is even more likely to pass them in the future than is a newly generated random set.

Comment author: Wei_Dai 24 January 2010 01:45:30AM *  8 points [-]

It seems that randomization can serve as a general substitute for memory. It's not a perfect substitute, but whenever you don't want to, or can't, remember something for some reason, randomization might help.

Besides the example of The Absent-Minded Driver, I've realized there are other examples in cryptography:

  • nonces - Many encryption schemes require a unique nonce to be generated for each message to be encrypted. You can either pick random nonces, or keep a counter. But keeping a counter might be too troublesome, and you might be running in a virtual machine that can be rolled back from time to time, so it's usually better to use a random nonce, even though you'll need a longer nonce than if you used a counter (to keep the probability of collision sufficiently small).
  • distributed key search - You can either have a central server that hands out regions of the key space to search, or each participant can search a random region. The latter is less efficient in computing time, but more efficient in communications cost.

I might do a post on this, if I could figure out a way to think about why randomization substitutes for memory.

Comment author: pengvado 24 January 2010 04:27:33AM *  5 points [-]

if I could figure out a way to think about why randomization substitutes for memory.

Let A and B be actions leading to deterministic outcomes, and let C be some lottery between A and B. A rational agent will never prefer both C>A and C>B.

When you repeat the scenario without memory, the lottery is no longer exactly over choices the agent could deterministically make: the randomness is re-rolled in places where the agent doesn't get another decision. Despite what the options are labeled, you're really choosing between 2xA, 2xB, and a lottery over {2xA, 2xB, A+B}. Since the lottery contains an outcome that isn't available to the deterministic decision, it may be preferred.

I think this is equivalent to the role played by observational evidence in UDT1: Observations allow a constant strategy to take different actions in different places, whereas without any observations to distinguish agent instances you have to pick one action to optimize both situations. Of course good evidence is reliably correlated with the environment whereas randomness doesn't tell you which is which, but it's better than nothing.

Comment author: Tyrrell_McAllister 29 January 2010 09:50:14PM 0 points [-]

I might do a post on this, if I could figure out a way to think about why randomization substitutes for memory.

I had some comments in this thread that outline the way that I think about this.