In other words, which existing reinforcement method learns in fewest episodes? R-Max comes to mind, but its very old and I'd like to know if there is something better now.
There is a very interesting learning agent. They call it Neural-Episodic-Control. Here is the link for the paper: https://arxiv.org/abs/1703.01988 . Their experiments show that NEC requires an order of magnitude fewer interactions with the environment than agents previously proposed.
There isn't really one specific method which makes any RL agent have faster learning. Rather there is a long list of methods which have shown to increase the speed of learning and they can sometimes play nicely with each other.
Some examples:
These are the most influential and promising methods I can think of but the list of techniques is not limited to these 3.