Hi there! I'm one of the authors of the work. I can assure you the numbers are not incorrect: random search did not achieve good results in the semantic segmentation experiment. We had similar skepticism with reviewers at ICLR initially, and our new experiments convinced them.

Random search is a good alternative and it did produce good results for the car counting experiment. We do not claim that RL is the best way to solve the problem at any point in our work. We just observe that random search did not perform well in the segmentation experiment while RL did perform well in all of our experiments. We think the RL formulation is a good one since it is flexible (can be easily adapted to neural network policies with thousands of weights for example).

Hope this helped!