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

Davide Maran, Gianmarco Tedeschi, Enea Gusmeroli, Marcello Restelli
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:3052-3060, 2026.

Abstract

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 a much more general, non-parametric, family of densities and when the model is misspecified. The algorithm achieving the regret bound is not computationally efficient, as it relies on a very computationally intensive online regression method. To bridge this gap, we propose a practical variant that draws inspiration from theoretical principles but incorporates 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-maran26a, title = { Provably Efficient Reinforcement Learning for Sparse Dynamical Systems with Non-Gaussian Noise }, author = {Maran, Davide and Tedeschi, Gianmarco and Gusmeroli, Enea and Restelli, Marcello}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {3052--3060}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/maran26a/maran26a.pdf}, url = {https://proceedings.mlr.press/v300/maran26a.html}, abstract = { 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 a much more general, non-parametric, family of densities and when the model is misspecified. The algorithm achieving the regret bound is not computationally efficient, as it relies on a very computationally intensive online regression method. To bridge this gap, we propose a practical variant that draws inspiration from theoretical principles but incorporates 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. } }
Endnote
%0 Conference Paper %T Provably Efficient Reinforcement Learning for Sparse Dynamical Systems with Non-Gaussian Noise %A Davide Maran %A Gianmarco Tedeschi %A Enea Gusmeroli %A Marcello Restelli %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-maran26a %I PMLR %P 3052--3060 %U https://proceedings.mlr.press/v300/maran26a.html %V 300 %X 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 a much more general, non-parametric, family of densities and when the model is misspecified. The algorithm achieving the regret bound is not computationally efficient, as it relies on a very computationally intensive online regression method. To bridge this gap, we propose a practical variant that draws inspiration from theoretical principles but incorporates 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.
APA
Maran, D., Tedeschi, G., Gusmeroli, E. & Restelli, M.. (2026). Provably Efficient Reinforcement Learning for Sparse Dynamical Systems with Non-Gaussian Noise . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:3052-3060 Available from https://proceedings.mlr.press/v300/maran26a.html.

Related Material