RL with Function Approximation.
Many recent works have studied RL with function approximation, especially in the linear case [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}. Under the assumption that the agent has access to a well-designed feature extractor, these works design provably efficient algorithms for linear MDPs and linear kernel MDPs. LSVI-UCB [1]}, the first work with both polynomial runtime and polynomial
sample complexity with linear function approximation, has a regret of \(\widetilde{\mathcal {O}}(\sqrt{d^3H^3T})\) . The state-of-the-art regret bound is \(\widetilde{\mathcal {O}}(Hd\sqrt{T})\) , achieved by ELEANOR [4]}. However, ELEANOR needs to solve an optimization problem in each episode, which is computationally intractable. [12]} introduces a new expressivity condition named optimistic closure for generalized linear function approximation under which they propose a variant of optimistic LSVI with regret bound \(\widetilde{\mathcal {O}}(\sqrt{d^3H^3T})\) . [5]}, [6]} focus on online RL with general function approximation and their analysis is based on the eluder dimension [15]}. Other complexity measures of general function classes include disagreement coefficient [7]}, Bellman rank [8]} and Witness rank [9]}.
