Title: Learning Sampling Policy to Achieve Fewer  Queries for  Zeroth-Order Optimization. Abstract: Zeroth-order (ZO) methods, which use the finite difference of two function evaluations (also called ZO gradient) to approximate first-order gradient, have attracted much attention recently in machine learning because of its broad applications.
The accurateness of ZO gradient highly depends on how many finite differences are averaged, which are intrinsically determined by the number of  perturbations randomly drawn from a distribution. 
Existing ZO methods try to learn a data-driven distribution for sampling the perturbations to improve the efficiency of ZO optimization (ZOO) algorithms. 
In this paper, we explore  a  new and parallel direction, i.e. , learn an optimal sampling policy  instead of using totally random strategy  to generate perturbations based on the techniques of reinforcement
learning (RL), which makes it possible to  approximate the gradient  with only two function evaluations.  Specifically, we first formulate the problem of learning a sampling policy as a Markov decision process. Then, we propose our ZO-RL algorithm,  \textit{i.e.}, using deep deterministic policy gradient, an actor-critic RL algorithm to  learn a  sampling policy which can guide the generation of perturbed vectors in getting ZO gradients as accurate as possible. Importantly, the existing ZOO algorithms of learning a distribution can be plugged in  to improve the exploration of  ZO-RL.
Experimental results  with different ZO estimators show that our ZO-RL algorithm can effectively reduce the query complexity of ZOO algorithms  and converge faster than existing ZOO algorithms especially in the later stage of the  optimization process.