Minimax Optimal <i>Q</i> Learning With Nearest Neighbors

Markov decision process (MDP) is an important model of sequential decision making problems. Existing theoretical analysis focus primarily on finite state spaces. For continuous state spaces, a recent interesting work (Shah and Xie, 2018) proposes a nearest neighbor Q learning approach. Under the streaming setting, in shich samples are received in a sequential manner, the sample complexity of this method is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\tilde {O}\left ({{\frac {|\mathcal {A}|}{\epsilon ^{d+3}(1-\gamma)^{d+7}}}}\right)$ </tex-math></inline-formula> for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula>-accurate Q function estimation of infinite horizon discounted MDP with discount factor <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\gamma $ </tex-math></inline-formula>, in which <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$|\mathcal {A}|$ </tex-math></inline-formula> is the size of the action space. However, the sample complexity is not optimal, and the method is suitable only for bounded state spaces. In this paper, we propose two new nearest neighbor Q learning methods, one for the offline setting and the other for the streaming setting. We show that the sample complexities of these two methods are <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\tilde {O}\left ({{\frac {|\mathcal {A}|}{\epsilon ^{d+2}(1-\gamma)^{d+2}}}}\right)$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\tilde {O}\left ({{\frac {|\mathcal {A}|}{\epsilon ^{d+2}(1-\gamma)^{d+3}}}}\right)$ </tex-math></inline-formula> for offline and streaming settings respectively, which significantly improve over existing results and have minimax optimal dependence over <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula>. We achieve such improvement by utilizing samples more efficiently. In particular, the method by Shah and Xie, 2018, clears up all samples after each iteration, thus these samples are somewhat wasted. On the other hand, our offline method does not remove any samples, and our streaming method only removes samples with time earlier than <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\beta t$ </tex-math></inline-formula> at time t, thus our methods significantly reduce the loss of information. Apart from the sample complexity, our methods also have additional advantages of better computational complexity, as well as suitability to unbounded state spaces. Finally, we extend our work to the case where both state and action spaces are continuous.