In this paper, we consider the model-free reinforcement learning problem and study the popular Q-learning algorithm with linear function approximation for finding the optimal policy. Despite its popularity, it is known that Q-learning with linear function approximation may diverge in general due to off-policy sampling. Our main contribution is to provide a finite-time bound for the performance of Q-learning with linear function approximation with constant step size under an assumption on the sampling policy. Unlike some prior work in the literature, we do not need to make the unnatural assumption that the samples are i.i.d. (since they are Markovian), and do not require an additional projection step in the algorithm. To show this result, we first consider a more general nonlinear stochastic approximation algorithm with Markovian noise, and derive a finite-time bound on the mean-square error, which we believe is of independent interest. Our proof is based on Lyapunov drift arguments and exploits the geometric mixing of the underlying Markov chain. We also provide numerical simulations to illustrate the effectiveness of our assumption on the sampling policy, and demonstrate the rate of convergence of Q-learning. Preprint. Under review. Given the popularity and success of Q-learning, its performance has been studied in the literature. The asymptotic convergence of Q-learning has been studied in [29, 12, 27] using martingale-based approach, while the rate of convergence has been characterized in [8, 25, 2, 9, 7] . However, since Q-learning requires to store the Q-function values for all state-action pairs, it has been limited to problems with small state and action spaces, and this challenge is often referred to as the curse of dimensionality in RL. To overcome this drawback, we can approximate the Q-function by a parameterized function class with much smaller dimension. However, Q-learning with function approximation can in general diverge [1, 23] . The main reason is that Q-learning uses off-policy sampling to collect the data, making it potentially an expansion mapping [10, 1] . For this reason, the convergence of Q-learning with function approximation has been limited to special cases, such as, for optimal stopping problems [28], or when using state aggregation functions [4] , or when using non-parametric regression method (nearest neighbor Q-learning) [19] . In this paper, we focus on studying Q-learning with linear function approximation [16, 31] , where the Q-function is approximated by a linear combination of a given set of basis functions (or features). Q-learning with linear function approximation can diverge in general as illustrated by the counter examples in [1, 23] . So, we need to impose certain conditions on the sampling policy to guarantee the stability of this approach. One such condition was proposed in [16] to restrict the sampling policy to be close enough to the optimal policy. However, we could not verify the correctness of the proof of the main theorem (Theorem 1) in [16] even after personal communication with the corresponding author. On the other hand, the work in [31] studies the finite-time analysis of Q-learning with linear function approximation. In particular, the approach in [31] is mainly motivated by the work in [5] , where the convergence rate of the popular temporal-difference learning method for solving policy evaluation problems was studied. One drawback of the techniques used in [5, 31] is that their algorithm requires an additional projection step onto a bounded set related to the unknown stationary distribution of the underlying Markov chain. Such a projection step used to control the size of the iterates is impractical. We also note that the work in [31] is based on the result in [16] , of which we could not verify the correctness, as mentioned above.
A similar analysis was also extended to Q-learning with linear function approximation REF .
Performance of Q-learning with Linear Function Approximation: Stability and Finite-Time Analysis
arXiv: Optimization and Control
Mathematics Computer Science