Efficiently Solving Discounted MDPs via Predictions with Unknown Prediction Errors

We study infinite-horizon discounted Markov decision processes (DMDPs) under a generative model. Motivated by the Algorithms with Advice framework (Mitzenmacher and Vassilvitskii, 2022), we propose a novel framework to investigate how black-box predictions of the transition matrix can enhance sample efficiency in solving DMDPs and improve sample complexity bounds. We focus on DMDPs with $N$ state–action pairs and discount factor $\gamma$. We first provide an impossibility result showing that, in the presence of predictions with unknown accuracy, no sampling policy can compute an $\epsilon$-optimal policy with a sample complexity better than $\tilde{O}((1-\gamma)^{-3} N \epsilon^{-2})$, which matches the state-of-the-art minimax sample complexity bound without prediction. In complement, we design an algorithm based on minimax optimization techniques that leverages predictions of the transition matrix without requiring knowledge of the prediction error. Our algorithm achieves a sample complexity bound that depends on the prediction error and is uniformly better than $\tilde{O}((1-\gamma)^{-4} N \epsilon^{-2})$, the previous best result derived from convex optimization methods. In some cases, our bound even improves upon the state-of-the-art $\tilde{O}((1-\gamma)^{-3} N \epsilon^{-2})$, despite not having access to the prediction quality.

Teaching a computer to make good decisions, like navigating a maze or managing resources, typically requires it to try thousands of actions and observe what happens. This process, called sampling, can be expensive or time-consuming. We asked: what if the computer already had a rough "cheat sheet" predicting how the environment behaves? Could that help it learn faster, even if the cheat sheet isn't perfectly accurate? We studied this question in the context of a mathematical framework for decision-making called Markov decision processes. We first proved a fundamental limitation: if the computer doesn't know how wrong its cheat sheet is, there's a hard floor on how much it can reduce its trial-and-error effort: no algorithm can do better than a certain baseline. But we also designed a new algorithm that makes smart use of the cheat sheet without needing to know its accuracy. This algorithm learns more efficiently than previous methods, and in favorable cases, it even surpasses the best known limits, despite having no guarantee on the quality of the predictions it receives.