I’m delighted to share that Statistical Complexity of Soft Bellman Residual Minimization has been accepted to the NeurIPS 2026 Main Track as a poster!
Authors: Enoch Hyunwook Kang*, Kyoungseok Jang*
* Equal contribution.
How reliably can reinforcement learning learn from a fixed dataset?
Offline reinforcement learning uses previously collected data to learn without further interaction with the environment. Bellman residual minimization (BRM) approaches this problem by making a value function consistent with the Bellman equation, which relates present decisions to future rewards. Our paper studies the statistical reliability of its entropy-regularized, or “soft,” formulation.
We analyze stochastic gradient descent-ascent (SGDA) through algorithmic stability: how much does the learned solution change when one training example is replaced? Using a new Lyapunov-based analysis under the paper’s PL–strongly-concave assumptions, we establish an O(1/n) statistical term in the stability and generalization bounds, where n is the dataset size. At finite training time, the bounds also include a term that decreases as optimization proceeds.
The analysis connects optimization with generalization and separates optimization error from statistical error in a population excess-risk bound. It applies to the soft BRM objective under the stated assumptions without requiring variance reduction. This provides a theoretical basis for understanding how more offline data improves the reliability of BRM-based learning; translating residual guarantees into policy-performance guarantees requires additional coverage assumptions.
An earlier version of this work was presented as a poster at the ICML 2026 DEMO Workshop.