Abstract: In this paper, we consider the problem of online learning of Markov decision processes (MDPs) with very\nlarge state spaces. Under the assumptions of realizable function approximation and low Bellman ranks, we\ndevelop an online learning algorithm that learns the optimal value function while at the same time achieving\nvery low cumulative regret during the learning process. Our learning algorithm, Adaptive Value-function\nElimination (AVE), is inspired by the policy elimination algorithm proposed in Jiang et al. (2017), known\nas OLIVE. One of our key technical contributions in AVE is to formulate the elimination steps in OLIVE as\ncontextual bandit problems. This technique enables us to apply the active elimination and expert weighting\nmethods from Dudik et al. (2011), instead of the random action exploration scheme used in the original\nOLIVE algorithm, for more efficient exploration and better control of the regret incurred in each policy\n elimination step. To the best of our knowledge, this is the first in stochastic MDPs with general value function approximation.