Recent years have witnessed great progress in reinforcement learning, both on the applied and theoretical fronts. However, there remain a number of major gaps between theory and practice. One fact is that algorithms used in practice almost always perform far better than the guarantees provided by existing worst-case bounds. How to close this gap between theory and practice? Instance-dependent minimax bounds allow one to formalize the notion that “not all problems are equal”—some are easier than others. In this talk, we describe some recent progress on obtaining non-asymptotic, instance-dependent, and optimal bounds in reinforcement learning, including various types of TD algorithms for policy evaluation, as well as Q-learning for policy optimization.