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. This paper provides a theoretical and empirical framework to explain this phenomenon, proving a fundamental trade-off: action-space exploration is sensitive to the length of the time horizon, while parameter-space exploration is sensitive to the number of model parameters.

Introduction

In Reinforcement Learning (RL), the choice of exploration strategy is critical. Traditionally, methods explore in the action space, where the agent tries different actions at each step (e.g., REINFORCE). Recently, however, simple "black-box" methods that explore in the parameter space—by perturbing the weights of the entire policy network (e.g., Augmented Random Search, ARS)—have surprisingly outperformed state-of-the-art action-space methods on complex benchmarks. This paper investigates the theoretical underpinnings of this performance gap, framing both paradigms as zeroth-order optimization problems.

The $d$ vs. $H$ Trade-off

The authors identify a fundamental trade-off between the number of model parameters ($d$) and the time horizon of the task ($H$).

  • Parameter Space Exploration: This approach treats the entire episode as a black box. Its sample complexity depends heavily on the dimensionality of the parameters ($d$) but is largely independent of the horizon length ($H$).
  • Action Space Exploration: These methods leverage the internal structure of the policy (the Jacobian) to guide search. Consequently, their complexity is independent of $d$ but grows polynomially with $H$.

This explains why ARS can win in environments with long horizons ($H \approx 1000$) and relatively simple policies (low $d$), while action-space methods struggle with the high variance induced by long sequences of actions.

Empirical Evidence

High-Dimensional Parameters: MNIST

To test the impact of parameter dimensionality, the researchers recast MNIST digit recognition as a one-step RL problem ($H=1$). With approximately 21,000 parameters, this setting favors action-space methods.

MNIST Experiment: Action-space exploration (REINFORCE) converges much faster than parameter-space exploration (ARS) when dimensionality is high and the horizon is short.

As shown in the MNIST experiment, REINFORCE significantly outperforms ARS. The $O(d^2)$ dependency of parameter-space methods makes them inefficient when the model is large but the task is short-lived.

The Impact of Horizon Length: MuJoCo

The researchers further validated the $H$ dependency using the Swimmer-v2 and HalfCheetah-v2 environments. By manually varying the horizon length, they observed a clear crossover point.

Horizon Length Experiments: As the horizon $H$ increases, the performance of action-space methods (ExAct) degrades, while parameter-space methods (ARS) remain stable and eventually dominate.

For short horizons, action-space methods are superior due to their "smarter" use of policy gradients. However, as $H$ grows, the variance of these estimates increases, allowing the simpler black-box parameter search to take the lead.

Conclusion

This work provides a formal explanation for the surprising success of simple random search in RL. The choice between parameter and action space exploration should be guided by the specific constraints of the task: action-space exploration is preferable for high-dimensional models with short horizons, while parameter-space exploration excels in long-horizon tasks with compact policy representations. Future work remains to reconcile these findings with the success of parameter-space methods in overparameterized deep networks.

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 pr...
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