$Q$-learning with Logarithmic Regret

Q-learning [Watkins and Dayan, 1992] is one of the most popular classes of methods for solving reinforcement learning (RL) problems. Q-learning tries to estimate the optimal state-action value function (Q-function). With a Q-function, at every state, one can greedily choose the action with the largest Q value to interact with the RL environment while achieving near optimal expected cumulative rewards in the long run. Compared to another popular classes of methods, e.g., modelbased RL, Q-learning algorithms (or more generally, model-free algorithms) often enjoy better memory and time efficiency