  We study computationally and statistically efficient Reinforcement Learning
algorithms for the linear Bellman Complete setting, a setting that uses linear
function approximation to capture value functions and unifies existing models
like linear Markov Decision Processes (MDP) and Linear Quadratic Regulators
(LQR). While it is known from the prior works that this setting is
statistically tractable, it remained open whether a computationally efficient
algorithm exists. Our work provides a computationally efficient algorithm for
the linear Bellman complete setting that works for MDPs with large action
spaces, random initial states, and random rewards but relies on the underlying
dynamics to be deterministic. Our approach is based on randomization: we inject
random noise into least square regression problems to perform optimistic value
iteration. Our key technical contribution is to carefully design the noise to
only act in the null space of the training data to ensure optimism while
circumventing a subtle error amplification issue.
