Sample-Efficient Reinforcement Learning under Sparse Dynamics
2026 · Exploiting sparse dynamics for sample-efficient model-based reinforcement learning.
Sample inefficiency remains a major challenge in reinforcement learning, as learning to act in an unknown dynamical system typically requires costly interactions with that system. Many systems, however, have a sparse structure: a state variable is directly coupled to only a few other variables. We propose SAMBL (Sparsity-Aware Model-Based Learning), which exploits this structure to reduce the number of interactions needed to learn a policy to control the system. For the archetypal setting of linear-quadratic control of a \(d\)-dimensional system with \(p\) inputs, we show that using an \(\ell_1\)-penalised dynamics estimator substantially improves sample efficiency when the true dynamics are row-sparse with at most \(s\) nonzeros per row. Our analysis of cumulative regret identifies an initial learning phase, after which cumulative regret grows only logarithmically. Because sparse dynamics can be estimated from fewer samples, SAMBL provably enters this logarithmic low-regret phase sooner than a dense baseline by up to a factor of order \((d+p)/(s\log(d+p))\). Our empirical studies with both synthetic and physical systems confirm this earlier entry into the low-regret regime and the resulting regret improvement. Structure thus makes learning from experience affordable in high-dimensional environments, where SAMBL provides an efficient blueprint for real-world reinforcement learning.