Contrasting Exploration in Parameter and Action Space: A Zeroth-Order Optimization Perspective

Anirudh Vemula, Wen Sun, J. Andrew Bagnell

Abstract

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.

Introduction

In Reinforcement Learning (RL), the mechanism for exploration is a critical design choice. Traditionally, researchers have focused on perturbing the actions an agent takes (e.g., REINFORCE, Policy Gradients). However, recent empirical results have shown that "black-box" parameter-space methods—which perturb the policy weights directly (e.g., Augmented Random Search, Evolution Strategies)—often outperform state-of-the-art policy gradient methods on complex benchmarks.

This paper addresses the underlying reasons for this performance gap. By viewing these approaches through the lens of zeroth-order optimization, we identify a fundamental trade-off: parameter-space exploration scales poorly with the number of model weights but is independent of the task's time horizon, whereas action-space exploration is independent of model size but scales poorly with the length of the task.

Methods: Two Families of Exploration

The authors categorize exploration strategies into two algorithmic families based on where noise is injected.

Parameter Space Exploration

These methods treat the environment as a complete black box. They add noise directly to the policy weights $\theta$ and evaluate the resulting performance. Because they do not utilize the internal structure of the policy or the sequential nature of the task, they are considered "fully zeroth-order."

Algorithm 3: Policy Search in Parameter Space

Action Space Exploration

In contrast, action-space methods (such as "ExAct") inject noise into the actions. These methods are hybrid: they are zeroth-order with respect to the environment's rewards and dynamics, but first-order with respect to the policy itself, as they leverage the Jacobian of the policy (how actions change with respect to parameters) to propagate updates.

Theoretical Analysis: Dimensionality vs. Horizon

The core contribution of this work is the derivation of sample complexity bounds for reaching a stationary point.

  • Parameter Space Exploration: The complexity depends on the number of parameters ($d^2$), but is independent of the horizon ($H$). The sample complexity is approximately $O(d^2/\epsilon^3)$.
  • Action Space Exploration: The complexity is independent of $d$, but depends heavily on the horizon ($H$). Specifically, the authors find a dependence of $O(p^2 H^4 / \epsilon^4)$, where $p$ is the action dimensionality.

The Jacobian serves as the "secret sauce" for action-space methods, allowing them to translate "good actions" into "good parameter updates" regardless of the total number of parameters. However, the sequential nature of RL means that action-space methods must estimate gradients through a sequence of noisy transitions, leading to the $H^4$ penalty.

Experimental Results

The theoretical trade-offs were validated across several experimental setups:

  1. MNIST as a Contextual Bandit: With a large parameter space ($d \approx 21,000$) but a horizon of $H=1$, action-space exploration (REINFORCE) significantly outperformed parameter-space search (ARS).
  2. Synthetic Linear Regression: As input dimensionality ($d$) increased, parameter-space methods degraded, while action-space methods remained steady.
  3. Continuous Control (MuJoCo): In environments like "Swimmer-v2" and "HalfCheetah-v2," action-space methods were superior for short horizons ($H < 10$). However, as $H$ increased toward 100 and beyond, parameter-space methods (ARS) quickly overtook them, confirming the $H$-dependence theory.
  4. Linear Quadratic Regulator (LQR): Tests on environmental stochasticity showed that while noise slows both methods, the impact is more pronounced for action-space methods.

Conclusion

This research provides a clear framework for choosing an exploration strategy. Parameter-space methods like ARS are preferred for long-horizon tasks with relatively compact parameterizations. Action-space methods are superior for short-horizon tasks or when using massive neural networks where $d$ is very large.

While the $H^4$ dependence for action-space methods represents an upper bound, it highlights an unavoidable challenge in sequential decision-making. Future work may investigate how variance reduction techniques or alternative noise distributions might mitigate these scaling laws.

Summary updated

Abstract

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.
BibTeX
@inproceedings{vemula2019contrasting,
  author = {Anirudh Vemula and Wen Sun and J. Andrew Bagnell},
  title = {{Contrasting Exploration in Parameter and Action Space: A Zeroth-Order Optimization Perspective}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=ruO-YnuXSxq},
}
Figure