Sharp Analysis of Smoothed Bellman Error Embedding
This work offers incremental theoretical improvements for researchers in reinforcement learning, focusing on convergence guarantees for a specific algorithm.
The paper provides a theoretical analysis of the Smoothed Bellman Error Embedding (SBEED) algorithm in batch-mode reinforcement learning, proving a near-optimal performance guarantee that improves upon prior results in terms of dependence on planning horizon and sample size.
The \textit{Smoothed Bellman Error Embedding} algorithm~\citep{dai2018sbeed}, known as SBEED, was proposed as a provably convergent reinforcement learning algorithm with general nonlinear function approximation. It has been successfully implemented with neural networks and achieved strong empirical results. In this work, we study the theoretical behavior of SBEED in batch-mode reinforcement learning. We prove a near-optimal performance guarantee that depends on the representation power of the used function classes and a tight notion of the distribution shift. Our results improve upon prior guarantees for SBEED in ~\citet{dai2018sbeed} in terms of the dependence on the planning horizon and on the sample size. Our analysis builds on the recent work of ~\citet{Xie2020} which studies a related algorithm MSBO, that could be interpreted as a \textit{non-smooth} counterpart of SBEED.