Planning in Markov Decision Processes with Gap-Dependent Sample Complexity

2020/06/10 by Anders Jönsson, Emilie Kaufmann, Jonsson, Anders +9 · 2 citations
Computer Science · #AI-based Problem Solving and Planning #Advanced Database Systems and Queries #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.2006.05879

openalex publication_date 2020/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose MDP-GapE, a new trajectory-based Monte-Carlo Tree Search algorithm for planning in a Markov Decision Process in which transitions have a finite support. We prove an upper bound on the number of calls to the generative models needed for MDP-GapE to identify a near-optimal action with high probability. This problem-dependent sample complexity result is expressed in terms of the sub-optimality gaps of the state-action pairs that are visited during exploration. Our experiments reveal that MDP-GapE is also effective in practice, in contrast with other algorithms with sample complexity guarantees in the fixed-confidence setting, that are mostly theoretical.

Cited by

• Q-Learning with Fine-Grained Gap-Dependent Regret
• SPiDR: A Simple Approach for Zero-Shot Safety in Sim-to-Real Transfer

Related

• Monte Carlo Tree Search for Verifying Reachability in Markov Decision\n Processes
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
• Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves
• Navigating to the Best Policy in Markov Decision Processes
• Bounded Optimal Exploration in MDP