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

Hyukjun Yang; Han-Dong Lim; Donghwan Lee

cs.LGApr 8, 2026

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

Authors: Hyukjun Yang, Han-Dong Lim, Donghwan Lee

Organizations: the Department of Electrical Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, 34141, South Korea

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.

Figures & tables

Fig. 1 : Monotonic decay of $C(p)$ and its convergence as $p\to\infty$ .

\delta_{\theta_{k}}=F_{\lambda}(\Phi\theta_{k})-\Phi\theta_{k}

Algorithm 1 Normalized Gradient Descent for PSBRM

Panel of Figure 3 — Fig. 2 : Experimental results on the simple MDP.

Function Approximation in RL

See all 20 papers

Adaptive Resolving Methods for Markov Decision Processes with Function Approximations
May 17, 2025Jiashuo Jiang, Yinyu Ye, Yiming ZongMarkov Decision Processes Reinforcement Learning
Department of Industrial Engineering & Decision Analytics, The Hong Kong University of Science and Technology · Department of Management Science & Engineering, Stanford University
Mathematical methods of reinforcement learning
Jul 8, 2026Denis Belomestny, Alexander Gasnikov, Egor Gladin +5Markov Decision Processes Reinforcement Learning
Duisburg-Essen University, HSE University · Innopolis University, MIPT, HSE University · HSE University +1
Bellman Error Minimization Via Linear Programming Normalization
Oct 2, 2026Haining YuFunction Approximation in RL Dynamic Programming
Independent Consultant

May 17, 2025J/K move · Enter open · S save

Adaptive Resolving Methods for Markov Decision Processes with Function Approximations

Jiashuo Jiang, Yinyu Ye, Yiming Zong

Department of Industrial Engineering & Decision Analytics, The Hong Kong University of Science and Technology · Department of Management Science & Engineering, Stanford University

Markov Decision Processes Reinforcement Learning Markov Models Policy Learning Sample-Efficient RL Function Approximation in RL

Open paper AskPDF arXiv

Learning the optimal policy for Markov decision process problems (MDPs) from samples is a fundamental problem in online and data-driven decision-making. Function approximations are usually deployed to handle large or infinite state-action space. In our work, we consider the MDP problems with function approximation and we develop a new algorithm to solve it efficiently. Our algorithm is based on a linear programming (LP) reformulation and repeatedly resolves the identified reduced linear system as new transition samples arrive. After the optimal basis is identified, we show that, after

N

resolving rounds, the expected averaged iterate achieves an instance-dependent

\widetilde O(C_{\mathrm{inst}}/N)

objective shortfall and signed constraint residual. We separately account for the historical samples used for basis identification and the

d_2

transition queries used in each resolving round, which yields the corresponding total transition-query complexity. We further complement our result with a robust

O(1/\sqrt{N})

bound that is independent of

Δ

. In comparison to the guarantees established in the previous literature, our instance dependent guarantee is tighter when the underlying instance is favorable, and the numerical experiments also reveal the wide applications and efficient empirical performances of our algorithms.

Abstract

Function Approximation in RL

Explore similar work

Adaptive Resolving Methods for Markov Decision Processes with Function Approximations

Mathematical methods of reinforcement learning

Bellman Error Minimization Via Linear Programming Normalization