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

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.

Accepted at AISTATS 2019

Cited by in corpus (11)

• Diversity Policy Gradient for Sample Efficient Quality-Diversity Optimization
• A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning
• Average-reward model-free reinforcement learning: a systematic review and literature mapping
• MULEX: Disentangling Exploitation from Exploration in Deep RL
• Fast and Efficient Locomotion via Learned Gait Transitions
• Transform2Act: Learning a Transform-and-Control Policy for Efficient Agent Design
• Learning to Guide Random Search
• Learning Branching Heuristics for Propositional Model Counting
• Trajectory-wise Control Variates for Variance Reduction in Policy Gradient Methods
• MLE-guided parameter search for task loss minimization in neural sequence modeling
• Parameter Critic: a Model Free Variance Reduction Method Through Imperishable Samples