A1608
Title: Consistent order determination of Markov decision process
Authors: Chuyun Ye - Beijing Normal University (China) [presenting]
Lixing Zhu - Beijing Normal University (China)
Ruoqing Zhu - University of Illinois at Urbana-Champaign (United States)
Abstract: The Markov assumption in Markov decision processes (MDPs) is fundamental in reinforcement learning, influencing both theoretical research and practical applications. Existing methods that rely on the Bellman equation benefit tremendously from this assumption for policy evaluation and inference. Testing the Markov assumption or selecting the appropriate order is important for further analysis. Existing tests primarily utilize sequential hypothesis testing methodology, increasing the tested order if the previously-tested one is rejected. However, this methodology cumulates type-I and type-II errors in sequential testing procedures that cause inconsistent order estimation, even with large sample sizes. To tackle this challenge, a procedure is developed that consistently distinguishes the true order from others. A novel estimator is first proposed that equivalently represents any order Markov assumption. Based on this estimator, a signal function and an associated signal statistic are thus constructed to achieve estimation consistency. Additionally, the curve pattern of the signal statistic facilitates easy visualization, assisting the order determination process in practice. Numerical studies validate the efficacy of the approach.
