Efficiently Solving Discounted MDPs with Predictions on Transition Matrices

2025/02/21 by Lyu, Lixing, Jiang, Jiashuo, Cheung, Wang Chi · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2502.15345

Abstract

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 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 O((1-γ)^-4 N ε^-2), the previous best result derived from convex optimization methods. These theoretical findings are further supported by our numerical experiments.

Cited by

• On the Hardness of Reinforcement Learning with Transition Look-Ahead
• Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach

Related

• Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
• Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model
• Near-Optimal Sample Complexity for MDPs via Anchoring
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs