Near-Optimal PAC Learning for Low-rank MDPs

Low-rank Markov decision processes (MDPs) provide a general framework for reinforcement learning in large or continuous state spaces with unknown representations. However, whether near-optimal sample complexity can be achieved using only a maximum-likelihood estimation (MLE) oracle and polynomial additional computation remains unclear. In this work, we resolve this question for probably approximately correct (PAC) learning with known per-step rewards in $[0,1]$. We propose an uncertainty marking algorithm for both time-homogeneous and time-inhomogeneous MDPs. Its exploration bonus controls the model error over a whole trajectory using the probability of at least one uncertainty mark. The algorithm uses MLE as its only optimization oracle, with bonus estimation and optimistic planning implemented in polynomial time using fitted-model evaluations and samples. We show that, with probability at least $1-\delta$, our algorithm returns an $\epsilon$-optimal policy using $\tilde{O}(H^{3}dA\log |\Theta |/{\epsilon }^2)$ episodes in the homogeneous setting and $\tilde{O}(H^{4}dA\log |\Theta |/{\epsilon }^2)$ episodes in the inhomogeneous setting, where $H$ is the horizon, $d$ is the rank, $A$ is the number of actions, and $\Theta$ is the common finite realizable kernel class with $|\Theta |\ge 2$. Moreover, we establish lower bounds that match these rates up to logarithmic factors, showing that our algorithm achieves near-optimal PAC sample complexity in both settings. Finally, we validate our algorithm through experiments on homogeneous block MDPs.