Contrasting Exploration in Parameter and Action Space: A Zeroth-Order
  Optimization Perspective
  Black-box optimizers that explore in parameter space have often been shown to
outperform more sophisticated action space exploration methods developed
specifically for the reinforcement learning problem. We examine these black-box
methods closely to identify situations in which they are worse than action
space exploration methods and those in which they are superior. Through simple
theoretical analyses, we prove that complexity of exploration in parameter
space depends on the dimensionality of parameter space, while complexity of
exploration in action space depends on both the dimensionality of action space
and horizon length. This is also demonstrated empirically by comparing simple
exploration methods on several model problems, including Contextual Bandit,
Linear Regression and Reinforcement Learning in continuous control.
