Sparsity in Partially Controllable Linear Systems

Yonathan Efroni · Sham Kakade · Akshay Krishnamurthy · Cyril Zhang

Hall E #932

Keywords: [ OPT: Control and Optimization ] [ T: Reinforcement Learning and Planning ] [ Reinforcement Learning ]

[ Abstract ]
[ Paper PDF
Wed 20 Jul 3:30 p.m. PDT — 5:30 p.m. PDT
Spotlight presentation: Miscellaneous Aspects of Machine Learning/Reinforcement Learning
Wed 20 Jul 1:30 p.m. PDT — 3 p.m. PDT


A fundamental concept in control theory is that of controllability, where any system state can bereached through an appropriate choice of control inputs. Indeed, a large body of classical and modernapproaches are designed for controllable linear dynamical systems. However, in practice, we oftenencounter systems in which a large set of state variables evolve exogenously and independently of thecontrol inputs; such systems are only partially controllable. The focus of this work is on a large classof partially controllable linear dynamical systems, specified by an underlying sparsity pattern. Our mainresults establish structural conditions and finite-sample guarantees for learning to control such systems. Inparticular, our structural results characterize those state variables which are irrelevant for optimal control,an analysis which departs from classical control techniques. Our algorithmic results adapt techniquesfrom high-dimensional statistics—specifically soft-thresholding and semiparametric least-squares—toexploit the underlying sparsity pattern in order to obtain finite-sample guarantees that significantly improveover those based on certainty-equivalence. We also corroborate these theoretical improvements overcertainty-equivalent control through a simulation study.

Chat is not available.