We study matrix estimation problems arising in reinforcement learning (RL)
with low-rank structure. In low-rank bandits, the matrix to be recovered
specifies the expected arm rewards, and for low-rank Markov Decision Processes
(MDPs), it may for example characterize the transition kernel of the MDP. In
both cases, each entry of the matrix carries important information, and we seek
estimation methods with low entry-wise error. Importantly, these methods
further need to accommodate for inherent correlations in the available data
(e.g. for MDPs, the data consists of system trajectories). We investigate the
performance of simple spectral-based matrix estimation approaches: we show that
they efficiently recover the singular subspaces of the matrix and exhibit
nearly-minimal entry-wise error. These new results on low-rank matrix
estimation make it possible to devise reinforcement learning algorithms that
fully exploit the underlying low-rank structure. We provide two examples of
such algorithms: a regret minimization algorithm for low-rank bandit problems,
and a best policy identification algorithm for reward-free RL in low-rank MDPs.
Both algorithms yield state-of-the-art performance guarantees.

研究低秩结构引发的强化学习中的矩阵估计问题，通过简单的基于谱的方法高效地恢复矩阵的奇异子空间并实现最小的逐项误差，从而设计了充分利用低秩结构的强化学习算法，包括低秩赌博机问题的最小遗憾算法和低秩马尔可夫决策过程中的无奖励 RL 的最佳策略识别算法，两种算法均具有最先进的性能保证。