Remark 4.9 Along with being a competitive algorithm in statistical efficiency, we want to emphasize that our algorithm has good computational efficiency. LSVI-PHE with linear function class only involves linear programming to find the greedy policy while LSVI-UCB [1]} requires solving a quadratic programming. The optimization problem in OPT-RLSVI [2]} is hard too because the Q-function there is a piecewise continuous function and in one piece, it includes the product of the square root of a quadratic term and a linear term.

