Gap-Dependent Bounds for Two-Player Markov Games

Recently, designing an effective and efficient algorithm to obtain a nea r-optimal strategy in sequential decision-making tasks has attracted more and more interest in the field of modern reinforcement learning (RL) [ SB88 ]. By estimating the optimal state-action value function (a.k.a Q-fun ction), Q-learning method [ WD92 ] is one of the most popular classes of algorithms. In each iteration o f Q-learning algorithms, the agent greedily chooses the action with th e largest Q value and achieve his reward and the next state by interacting with the underlying RL e nvironment. At the same time, the algorithm keeps updating the Q-values by using Bellman Equa tion. In comparison, the model-based methods attempt to reveal the structure of the en vironment, which lead to more memory and worse time efficiency. That's why Q-learning, a typical model-free method, is playing an important role in a wide range of RL problems [ MKS