Reducing the Sample Complexity of Sampling-based Control via Horizon Splitting

Sampling-based methods such as MPPI, CMA-ES, and CEM are gaining traction for computing optimal control trajectories in robotics. We present sample complexity analysis, showing that zeroth-order methods require a number of samples exponential in the planning horizon, limiting their applicability to long-horizon tasks. Motivated by this analysis, we propose a rigorous horizon splitting algorithm to reduce the required sample complexity by sequentially solving sub-problems. Validation on an optimal linear quadratic regulator (LQR) problem substantiates our theoretical predictions, and we show that our sample complexity bounds also model settings with no access to ground truth optimal solutions. On five robotics benchmarks, horizon splitting led to lower costs, especially over longer horizons, and typically outperformed the best sampling-based control setting without horizon splitting.