Best Policy Identification in Linear MDPs

2022/08/11 by Taupin, Jerome, Jedra, Yassir, Proutiere, Alexandre · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2208.05633

Abstract

We investigate the problem of best policy identification in discounted linear Markov Decision Processes in the fixed confidence setting under a generative model. We first derive an instance-specific lower bound on the expected number of samples required to identify an ε-optimal policy with probability 1-δ. The lower bound characterizes the optimal sampling rule as the solution of an intricate non-convex optimization program, but can be used as the starting point to devise simple and near-optimal sampling rules and algorithms. We devise such algorithms. One of these exhibits a sample complexity upper bounded by \cal O((d)/((ε+Δ)²) (log(\frac1δ)+d)) where Δ denotes the minimum reward gap of sub-optimal actions and d is the dimension of the feature space. This upper bound holds in the moderate-confidence regime (i.e., for all δ), and matches existing minimax and gap-dependent lower bounds. We extend our algorithm to episodic linear MDPs.

Cited by

• Policy Testing in Markov Decision Processes

Related

• Adaptive Sampling for Best Policy Identification in Markov Decision Processes
• Policy Testing in Markov Decision Processes
• Near-Optimal Sample Complexity for MDPs via Anchoring
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP
• Finding good policies in average-reward Markov Decision Processes without prior knowledge