2022/12/01 by Jinghan Wang, Mengdi Wang, Wang, Jinghan +3 · 2 citations
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.2212.00603
openalex publication_date 2022/12/01 · openalex created_date 2022/12/13 · openalex updated_date 2026/07/28
This work considers the sample complexity of obtaining an ε-optimal policy in an average reward Markov Decision Process (AMDP), given access to a generative model (simulator). When the ground-truth MDP is weakly communicating, we prove an upper bound of \widetilde O(H ε-3 ln \frac1δ) samples per state-action pair, where H := sp(h^*) is the span of bias of any optimal policy, ε is the accuracy and δ is the failure probability. This bound improves the best-known mixing-time-based approaches in [Jin & Sidford 2021], which assume the mixing-time of every deterministic policy is bounded. The core of our analysis is a proper reduction bound from AMDP problems to discounted MDP (DMDP) problems, which may be of independent interests since it allows the application of DMDP algorithms for AMDP in other settings. We complement our upper bound by proving a minimax lower bound of Ω(|\mathcal S| |\mathcal A| H ε-2 ln \frac1δ) total samples, showing that a linear dependent on H is necessary and that our upper bound matches the lower bound in all parameters of (|\mathcal S|, |\mathcal A|, H, ln \frac1δ) up to some logarithmic factors.