http://www.google.com/search?hl=en&q=tigers+climb+trees
On a more serious note, you may be interested in Marcus Hutter’s 2007 paper “The Loss Rank Principle for Model Selection”. It’s about modeling, not about action selection, but there’s a loss function involved, so there’s a pragmatist viewpoint here, too.
@ comingstorm: Quasi Monte Carlo often outperforms Monte Carlo integration for problems of small dimensionality involving “smooth” integrands. This is, however, not yet rigorously understood. (The proven bounds on performance for medium dimensionality seem to be extremely loose.)
Besides, MC doesn’t require randomness in the “Kolmogorov complexity == length” sense, but in the “passes statistical randomness tests” sense. Eliezer has, as far as I can see, not talked about the various definitions of randomness.