Randomized least-squares value iteration (RLSVI), proposed in [1]}, uses random perturbations to approximate the posterior. Recently, several works focussed on the theoretical analysis of RLSVI [2]}, [3]}, [4]}. [2]} provides the first worst-case regret \(\widetilde{O}(H^{5/2}S^{3/2}\sqrt{AT})\)  for tabular MDP and [4]} improves it to \(\widetilde{O}(H^2S\sqrt{AT})\) . [7]} proves \(\widetilde{O}(H^2d^2\sqrt{T})\)  regret bound for linear MDP. However, [4]}, [7]} both need to compute the confidence width as a warm-up stage, which is complicated and computationally costly.
