Though the convergence of major reinforcement learning algorithms has been extensively studied, the finite-sample analysis to further characterize the convergence rate in terms of the sample complexity for problems with continuous state space is still very limited. Such a type of analysis is especially challenging for algorithms with dynamically changing learning policies and under non-i.i.d.\ sampled data. In this paper, we present the first finite-sample analysis for the SARSA algorithm and its minimax variant (for zero-sum Markov games), with a single sample path and linear function approximation. To establish our results, we develop a novel technique to bound the gradient bias for dynamically changing learning policies, which can be of independent interest. We further provide finite-sample bounds for Q-learning and its minimax variant. Comparison of our result with the existing finite-sample bound indicates that linear function approximation achieves order-level lower sample complexity than the nearest neighbor approach.

本文研究了在非独立同分布数据下具有线性函数逼近的 SARSA 算法，并开发了一种新的技术来显式表征随着时间变化的马尔科夫转移核的一类随机逼近过程的随机偏差，从而提供了基于有限样本的 SARSA 算法的均方误差有限样本分析以及配适的 SARSA 算法，后者包括原始 SARSA 算法及其变体，提供了比逐步更新策略迭代更高效的泛化框架。

基于线性函数逼近的SARSA有限样本分析