  In this paper, we introduce Randomized Q-learning (RandQL), a novel
randomized model-free algorithm for regret minimization in episodic Markov
Decision Processes (MDPs). To the best of our knowledge, RandQL is the first
tractable model-free posterior sampling-based algorithm. We analyze the
performance of RandQL in both tabular and non-tabular metric space settings. In
tabular MDPs, RandQL achieves a regret bound of order
$\widetilde{\mathcal{O}}(\sqrt{H^{5}SAT})$, where $H$ is the planning horizon,
$S$ is the number of states, $A$ is the number of actions, and $T$ is the
number of episodes. For a metric state-action space, RandQL enjoys a regret
bound of order $\widetilde{\mathcal{O}}(H^{5/2} T^{(d_z+1)/(d_z+2)})$, where
$d_z$ denotes the zooming dimension. Notably, RandQL achieves optimistic
exploration without using bonuses, relying instead on a novel idea of learning
rate randomization. Our empirical study shows that RandQL outperforms existing
approaches on baseline exploration environments.
