Stability and Generalization for Bellman Residuals

• URL: http://arxiv.org/abs/2508.18741v1
• Date: Tue, 26 Aug 2025 07:15:36 GMT
• Title: Stability and Generalization for Bellman Residuals
• Abstract summary: Bellman residual minimization (BRM) has emerged as an attractive remedy for offline reinforcement learning.<n>This paper introduces a single Lyapunov potential that couples SGDA runs on neighbouring datasets and yields an O (1/n) on-average argument-stability bound.<n>The results hold for standard neural-network parameterizations and minibatch SGD.
• Score: 8.250374560598493
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Offline reinforcement learning and offline inverse reinforcement learning aim to recover near-optimal value functions or reward models from a fixed batch of logged trajectories, yet current practice still struggles to enforce Bellman consistency. Bellman residual minimization (BRM) has emerged as an attractive remedy, as a globally convergent stochastic gradient descent-ascent based method for BRM has been recently discovered. However, its statistical behavior in the offline setting remains largely unexplored. In this paper, we close this statistical gap. Our analysis introduces a single Lyapunov potential that couples SGDA runs on neighbouring datasets and yields an O(1/n) on-average argument-stability bound-doubling the best known sample-complexity exponent for convex-concave saddle problems. The same stability constant translates into the O(1/n) excess risk bound for BRM, without variance reduction, extra regularization, or restrictive independence assumptions on minibatch sampling. The results hold for standard neural-network parameterizations and minibatch SGD.

Related papers

• Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Making [12.04727482907937]
  CML addresses the problem of tracking the noise of primal feedback multipliers under mini-batch conditions.<n>We decompose the multiplier into an effective pressure signal for primal descent and a finite-gain multiplier.
  arXiv  Detail & Related papers  (2026-06-05T09:35:22Z)
• Clipping Bottleneck: Stabilizing RLVR via Stochastic Recovery of Near-Boundary Signals [83.0127582612634]
  Near-boundary Rescue (NSR) is a minimal, plug-and-play modification that retains out-of-bound tokens to recover lost signals.<n>NSR substantially improves training stability and delivers consistent gains over strong baselines such as DAPO and GSPO.
  arXiv  Detail & Related papers  (2026-05-21T16:45:31Z)
• Sharp Convergence Rates for Masked Diffusion Models [53.117058231393834]
  We develop a total-variation based analysis for the Euler method that overcomes limitations.<n>Our results relax assumptions on score estimation, improve parameter dependencies, and establish convergence guarantees.<n>Overall, our analysis introduces a direct TV-based error decomposition along the CTMC trajectory and a decoupling-based path-wise analysis for FHS.
  arXiv  Detail & Related papers  (2026-02-26T00:47:51Z)
• Breaking the Stochasticity Barrier: An Adaptive Variance-Reduced Method for Variational Inequalities [0.0]
  We propose VR-A-A (VarianceReduced-Ascent with Armijo) as a novel algorithm for non-con optimization tasks.<n>We show that our method effectively suppresses limit cycles and accelerates convergence with reduced dependence on manual learning scheduling.
  arXiv  Detail & Related papers  (2026-01-30T14:43:07Z)
• MaP: A Unified Framework for Reliable Evaluation of Pre-training Dynamics [72.00014675808228]
  Instability in Large Language Models evaluation process obscures true learning dynamics.<n>We introduce textbfMaP, a framework that integrates underlineMerging underlineand the underlinePass@k metric.<n>Experiments show that MaP yields significantly smoother performance curves, reduces inter-run variance, and ensures more consistent rankings.
  arXiv  Detail & Related papers  (2025-10-10T11:40:27Z)
• Convergence and Generalization of Anti-Regularization for Parametric Models [0.0]
  Anti-regularization (AR) adds a sign-reversed reward term to the loss to intentionally increase model expressivity in the small-sample regime.<n>We formalize spectral safety and trust-region conditions, and design a lightweight stability safeguard that combines a projection operator with gradient clipping.
  arXiv  Detail & Related papers  (2025-08-24T15:34:17Z)
• Trajectory Bellman Residual Minimization: A Simple Value-Based Method for LLM Reasoning [55.33984461046492]
  Policy-based methods currently dominate reinforcement learning pipelines for large language model (LLM) reasoning.<n>We introduce Trajectory Bellman Residual Minimization (TBRM), an algorithm that naturally adapts this idea to LLMs.<n>We prove convergence to the near-optimal KL-regularized policy from arbitrary off-policy via an improved change-of-trajectory-measure analysis.
  arXiv  Detail & Related papers  (2025-05-21T09:41:53Z)
• An Empirical Risk Minimization Approach for Offline Inverse RL and Dynamic Discrete Choice Model [9.531082746970286]
  We study the problem of estimating Dynamic Choice (DDC) models, also known as offline Maximum Entropy-Regularized Inverse Reinforcement Learning ( offline MaxEnt-IRL) in machine learning.<n>The objective is to recover reward or $Q*$ functions that govern agent behavior from offline behavior data.<n>We propose a globally convergent gradient-based method for solving these problems without the restrictive assumption of linearly parameterized rewards.
  arXiv  Detail & Related papers  (2025-02-19T22:22:20Z)
• Model-Based Uncertainty in Value Functions [89.31922008981735]
  We focus on characterizing the variance over values induced by a distribution over MDPs. Previous work upper bounds the posterior variance over values by solving a so-called uncertainty Bellman equation. We propose a new uncertainty Bellman equation whose solution converges to the true posterior variance over values.
  arXiv  Detail & Related papers  (2023-02-24T09:18:27Z)
• Convergence of uncertainty estimates in Ensemble and Bayesian sparse model discovery [4.446017969073817]
  We show empirical success in terms of accuracy and robustness to noise with bootstrapping-based sequential thresholding least-squares estimator. We show that this bootstrapping-based ensembling technique can perform a provably correct variable selection procedure with an exponential convergence rate of the error rate.
  arXiv  Detail & Related papers  (2023-01-30T04:07:59Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  We prove the first high-probability results with logarithmic dependence on the confidence level for methods for solving monotone and structured non-monotone VIPs. Our results match the best-known ones in the light-tails case and are novel for structured non-monotone problems. In addition, we numerically validate that the gradient noise of many practical formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.
  arXiv  Detail & Related papers  (2022-06-02T15:21:55Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  We study the problem of least squares linear regression where the data-points are dependent and are sampled from a Markov chain. We establish sharp information theoretic minimax lower bounds for this problem in terms of $tau_mathsfmix$. We propose an algorithm based on experience replay--a popular reinforcement learning technique--that achieves a significantly better error rate.
  arXiv  Detail & Related papers  (2020-06-16T04:26:50Z)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
  We introduce a new stability measure called on-average model stability, for which we develop novel bounds controlled by the risks of SGD iterates. This yields generalization bounds depending on the behavior of the best model, and leads to the first-ever-known fast bounds in the low-noise setting. To our best knowledge, this gives the firstever-known stability and generalization for SGD with even non-differentiable loss functions.
  arXiv  Detail & Related papers  (2020-06-15T06:30:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.