Similar algorithms have been shown to work empirically, including SUNRISE [1]}, NoisyNet [2]} and bootstrapped DQN [3]}. However, the theoretical analysis of perturbation-based exploration is still missing. We prove that it enjoys near optimal regret \(\widetilde{O}(\sqrt{H^3d^3T})\)  for linear MDP and the sampling time is only \(M=\widetilde{O}(d)\) . We also prove similar bounds for the general function approximation case, by using the notion of eluder dimension [4]}, [5]}. In addition, this algorithm is computationally efficient, as we no longer need to compute the upper confidence bound. In the experiments, we find that a small sampling time \(M\)  is sufficient to achieve good performance, which suggests that the theoretical choice of \(M=\widetilde{O}(d)\)  is too conservative in practice.
