@article{Liu_Xie_Deng_Ge_Ye_2024,
 abstractnote = {Value Iteration (VI) is one of the most classic algorithms for solving Markov Decision Processes (MDPs), which lays the foundations for various more advanced reinforcement learning algorithms, such as Q-learning. VI may take a large number of iterations to converge as it is a first-order method. In this paper, we introduce the Newton Value Iteration (NVI) algorithm, which eliminates the impact of action space dimension compared to some previous second-order methods. Consequently, NVI can efficiently handle MDPs with large action spaces. Building upon NVI, we propose a novel approach called Sketched Newton Value Iteration (SNVI) to tackle MDPs with both large state and action spaces. SNVI not only inherits the stability and fast convergence advantages of second-order algorithms, but also significantly reduces computational complexity, making it highly scalable. Extensive experiments demonstrate the superiority of our algorithms over traditional VI and previously proposed second-order VI algorithms.},
 author = {Liu, Jinsong and Xie, Chenghan and Deng, Qi and Ge, Dongdong and Ye, Yinyu},
 doi = {10.1609/aaai.v38i12.29301},
 journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
 month = {Mar.},
 number = {12},
 pages = {13936-13944},
 title = {Sketched Newton Value Iteration for Large-Scale Markov Decision Processes},
 url = {https://ojs.aaai.org/index.php/AAAI/article/view/29301},
 volume = {38},
 year = {2024}
}