  We present a new method of blackbox optimization via gradient approximation
with the use of structured random orthogonal matrices, providing more accurate
estimators than baselines and with provable theoretical guarantees. We show
that this algorithm can be successfully applied to learn better quality compact
policies than those using standard gradient estimation techniques. The compact
policies we learn have several advantages over unstructured ones, including
faster training algorithms and faster inference. These benefits are important
when the policy is deployed on real hardware with limited resources. Further,
compact policies provide more scalable architectures for derivative-free
optimization (DFO) in high-dimensional spaces. We show that most robotics tasks
from the OpenAI Gym can be solved using neural networks with less than 300
parameters, with almost linear time complexity of the inference phase, with up
to 13x fewer parameters relative to the Evolution Strategies (ES) algorithm
introduced by Salimans et al. (2017). We do not need heuristics such as fitness
shaping to learn good quality policies, resulting in a simple and theoretically
motivated training mechanism.
