Contraction-Aligned Analysis of Soft Bellman Residual Minimization with Weighted Lp-Norm for Markov Decision Problem

• URL: http://arxiv.org/abs/2604.06837v1
• Date: Wed, 08 Apr 2026 08:58:30 GMT
• Title: Contraction-Aligned Analysis of Soft Bellman Residual Minimization with Weighted Lp-Norm for Markov Decision Problem
• Abstract summary: We consider a soft formulation of Bellman residual minimization and extend it to a generalized weighted Lp -norm.<n>We show that this formulation aligns the optimization objective with the contraction geometry of the Bellman operator as p increases.<n>Our analysis provides a principled connection between residual minimization and Bellman contraction, leading to improved control of error propagation.
• Score: 9.333190920811626
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of solving Markov decision processes under function approximation remains a fundamental challenge, even under linear function approximation settings. A key difficulty arises from a geometric mismatch: while the Bellman optimality operator is contractive in the Linfty-norm, commonly used objectives such as projected value iteration and Bellman residual minimization rely on L2-based formulations. To enable gradient-based optimization, we consider a soft formulation of Bellman residual minimization and extend it to a generalized weighted Lp -norm. We show that this formulation aligns the optimization objective with the contraction geometry of the Bellman operator as p increases, and derive corresponding performance error bounds. Our analysis provides a principled connection between residual minimization and Bellman contraction, leading to improved control of error propagation while remaining compatible with gradient-based optimization.

Related papers

• Stochastic Non-Smooth Convex Optimization with Unbounded Gradients [10.350093268971836]
  We show that clipped AdamW is theoretically better than other popular optimization methods, such as SGDW and AdaGrad.<n>We also establish the critical role of AdamW's exponentially weighted accumulation, as opposed to simple averaging.
  arXiv  Detail & Related papers  (2026-05-15T01:43:22Z)
• Central Limit Theorem for Two-Time-Scale Approximate Distributionally Robust RL [8.809468023364703]
  Design of robust reinforcement learning algorithms poses fundamental challenges.<n>We propose an approximate DRRL framework based on a first-order expansion of the relevant robust functional.<n>To learn the fixed point of this approximate equation, we propose Mean-Variance Approximation (MVSA)
  arXiv  Detail & Related papers  (2026-05-08T19:24:28Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Analysis of Control Bellman Residual Minimization for Markov Decision Problem [6.622208195193136]
  Bellman residual minimization can be used to minimize the squared Bellman residual objective function.<n>We establish foundational results for the control Bellman residual minimization for policy optimization.
  arXiv  Detail & Related papers  (2026-01-26T10:58:27Z)
• Towards a Unified Analysis of Neural Networks in Nonparametric Instrumental Variable Regression: Optimization and Generalization [66.08522228989634]
  We establish the first global convergence result of neural networks for two stage least squares (2SLS) approach in nonparametric instrumental variable regression (NPIV)<n>This is achieved by adopting a lifted perspective through mean-field Langevin dynamics (MFLD)
  arXiv  Detail & Related papers  (2025-11-18T17:51:17Z)
• From Noisy Traces to Stable Gradients: Bias-Variance Optimized Preference Optimization for Aligning Large Reasoning Models [90.45197506653341]
  Large reasoning models generate intermediate reasoning traces before producing final answers.<n> aligning LRMs with human preferences, a crucial prerequisite for model deployment, remains underexplored.<n>A common workaround optimized a single sampled trajectory, which introduces substantial gradient variance from trace sampling.
  arXiv  Detail & Related papers  (2025-10-06T17:58:01Z)
• Fractional-Boundary-Regularized Deep Galerkin Method for Variational Inequalities in Mixed Optimal Stopping and Control [3.514024064150887]
  Mixed optimal stopping and control problems define variational inequalities with non-linear Hamilton-Jacobi-Bellman operators.<n>We first use the dual approach to transform it into a linear operator, and then introduce a Fractional-Boundary-Regularized Deep Galerkin Method.<n>The improved accuracy allows the network to be converted back to the original solution using the dual transform.
  arXiv  Detail & Related papers  (2025-05-25T20:49:00Z)
• Alternating Minimization Schemes for Computing Rate-Distortion-Perception Functions with $f$-Divergence Perception Constraints [9.788112471288057]
  We study the computation of the rate-distortion-perception function (RDPF) for discrete memoryless sources.<n>We characterize optimal parametric solutions for the convex programming problem.<n>We show, by deriving necessary and sufficient conditions, that both schemes guarantee a globally optimal solution.
  arXiv  Detail & Related papers  (2024-08-27T12:50:12Z)
• Regularized Q-Learning with Linear Function Approximation [2.765106384328772]
  We consider a bi-level optimization formulation of regularized Q-learning with linear functional approximation.<n>We show that, under certain assumptions, the proposed algorithm converges to a stationary point in the presence of Markovian noise.
  arXiv  Detail & Related papers  (2024-01-26T20:45:40Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Logistic Q-Learning [87.00813469969167]
  We propose a new reinforcement learning algorithm derived from a regularized linear-programming formulation of optimal control in MDPs. The main feature of our algorithm is a convex loss function for policy evaluation that serves as a theoretically sound alternative to the widely used squared Bellman error.
  arXiv  Detail & Related papers  (2020-10-21T17:14:31Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Support recovery and sup-norm convergence rates for sparse pivotal estimation [79.13844065776928]
  In high dimensional sparse regression, pivotal estimators are estimators for which the optimal regularization parameter is independent of the noise level. We show minimax sup-norm convergence rates for non smoothed and smoothed, single task and multitask square-root Lasso-type estimators.
  arXiv  Detail & Related papers  (2020-01-15T16:11:04Z)

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.