Efficiently Solving Discounted MDPs with Predictions on Transition Matrices
This work addresses sample efficiency in reinforcement learning for researchers, offering incremental improvements in theoretical bounds for DMDPs with predictions.
The paper tackles the problem of solving discounted Markov Decision Processes (DMDPs) more efficiently by using predictions on transition matrices, showing that without prediction accuracy knowledge, no algorithm beats the minimax bound of Õ((1-γ)^{-3} N ε^{-2}), but with predictions, their algorithm achieves a bound better than Õ((1-γ)^{-4} N ε^{-2}).
We study infinite-horizon Discounted Markov Decision Processes (DMDPs) under a generative model. Motivated by the Algorithm with Advice framework Mitzenmacher and Vassilvitskii 2022, we propose a novel framework to investigate how a prediction on the transition matrix can enhance the sample efficiency in solving DMDPs and improve sample complexity bounds. We focus on the DMDPs with $N$ state-action pairs and discounted factor $γ$. Firstly, we provide an impossibility result that, without prior knowledge of the prediction accuracy, no sampling policy can compute an $ε$-optimal policy with a sample complexity bound better than $\tilde{O}((1-γ)^{-3} Nε^{-2})$, which matches the state-of-the-art minimax sample complexity bound with no prediction. In complement, we propose an algorithm based on minimax optimization techniques that leverages the prediction on the transition matrix. Our algorithm achieves a sample complexity bound depending on the prediction error, and the bound is uniformly better than $\tilde{O}((1-γ)^{-4} N ε^{-2})$, the previous best result derived from convex optimization methods. These theoretical findings are further supported by our numerical experiments.