Consider a two-player zero-sum stochastic game where the transition function can be embedded in a given feature space. We propose a two-player Q-learning algorithm for approximating the Nash equilibrium strategy via sampling. The algorithm is shown to find an $\epsilon$-optimal strategy using sample size linear to the number of features. To further improve its sample efficiency, we develop an accelerated algorithm by adopting techniques such as variance reduction, monotonicity preservation and two-sided strategy approximation. We prove that the algorithm is guaranteed to find an $\epsilon$-optimal strategy using no more than $\tilde{\mathcal{O}}(K/(\epsilon^{2}(1-\gamma)^{4}))$ samples with high probability, where $K$ is the number of features and $\gamma$ is a discount factor. The sample, time and space complexities of the algorithm are independent of original dimensions of the game.

提出在给定特征空间中嵌入转移函数的二人零和随机博弈中，通过采样逼近纳什均衡策略的二人Q-learning算法，已证明可使用与特征数线性相关的样本大小找到ε最优策略；进一步改进算法的样本效率，采用方差约减、单调性保持和双侧策略逼近等技术来加速算法，证明了该算法最多只需要使用O~(K/(ε^2(1-γ)^4))个样本即可以高概率找到ε最优策略，其中K是特征数，γ是折扣系数；算法的样本、时间和空间复杂度与游戏的原始维度无关。

基于特征的Q学习在双人随机博弈中的应用