Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation

We consider the problem of learning an \varepsilon -optimal policy in controlled dynamical systems with low-rank latent structure. In the latter, the algorithm estimates the low-rank matrix corresponding to the (state, action) value function of the current policy using the following two-phase procedure. The entries of the matrix are first sampled uniformly at random to estimate, via a spectral method, the *leverage scores* of its rows and columns. These scores are then used to extract a few important rows and columns whose entries are further sampled. The algorithm exploits these new samples to complete the matrix estimation using a CUR-like method.