Provably Efficient Reinforcement Learning for Sparse Dynamical Systems with Non-Gaussian Noise

The recent development of sparse methods for identifying nonlinear dynamical systems has opened new avenues for efficient and interpretable model-based reinforcement learning (RL). In this work, we study online RL in environments where the system dynamics, modeled as $s'=f(s,a)+$noise, is assumed to be sparse with respect to a big feature map, a structural idea inspired by the SINDy framework. We introduce an optimistic algorithm that combines online sparse regression with confidence set construction to guide exploration and planning. On the theoretical side, we provide the first regret bounds for sparse nonlinear dynamics, showing that regret scales with the sparsity level $d_0$. This result holds even when relaxing standard Gaussian noise assumptions by allowing general a much general, non-parametric, family of densities and when the model is misspecified. The algorithm enjoying the regret bound is not computationally efficient, as it builds on a very heavy online regression method. To bridge this gap, we propose a practical variant that takes inspiration from the theoretical principles but adopts more scalable components. We adopt SINDy for sparse system identification algorithm and couple it with SAC in a Dyna-style planning framework. Empirical results on classic continuous control tasks demonstrate the practical viability and robustness of our approach.