The exploration-exploitation trade-off is a core problem in reinforcement learning (RL): an agent may need to sacrifice short-term rewards to achieve better long-term returns. A good RL algorithm should explore efficiently and find a near-optimal policy as quickly and robustly as possible. A big open problem is the design of provably efficient exploration when general function approximation is used to estimate the value function, i.e., the expectation of long-term return. In this work, we propose an exploration strategy inspired by the popular Randomized Least Squares Value Iteration (RLSVI) algorithm [1]}, [2]}, [3]} as well as by the optimism principle [4]}, [5]}, [6]}, [7]}, [8]}, which is efficient in both statistical and computational sense, and can be easily plugged into common RL algorithms, including UCB-VI [9]}, UCB-Q [6]} and OPPO [11]}.
