By 'random', he means evolutionary search. It's not really random, and is just a slower method for policy gradient. Here's the OpenAI blog post: https://blog.openai.com/evolution-strategies/