Even random search (in the weight space) can outperform gradient-based deep reinforcement learning algorithms on some Atari games. Genetic algorithms are quite competitive. Paper: https://arxiv.org/abs/1712.06567v1