Uniform-PAC Guarantees for Model-Based RL with Bounded Eluder Dimension
Yue Wu Jiafan He Quanquan Gu
Recently, there has been remarkable progress in reinforcement learning (RL)
with general function approximation. However, all these works only provide
regret or sample complexity guarantees. It is still an open question if one can
achieve stronger performance guarantees, i.e., the uniform probably approximate
correctness (Uniform-PAC) guarantee that can imply both a sub-linear regret
bound and a polynomial sample complexity for any target learning accuracy. We
study this problem by proposing algorithms for both nonlinear bandits and
model-based episodic RL using the general function class with a bounded eluder
dimension. The key idea of the proposed algorithms is to assign each action to
different levels according to its width with respect to the confidence set. The
achieved uniform-PAC sample complexity is tight in the sense that it matches
the state-of-the-art regret bounds or sample complexity guarantees when reduced
to the linear case. To the best of our knowledge, this is the first work for
uniform-PAC guarantees on bandit and RL that goes beyond linear cases.