cs.AINov 10, 2026

An Augmented Lagrangian Approach to Lifted Bellman Linear Programming

Authors: Jongchan Park, Hyukjun Yang, Narim Jeong, Donghwan Lee

Organizations: NAVER LABS, Seongnam, Republic of Korea · Department of EE, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Republic of Korea

Abstract

Temporal-difference critics regress onto a bootstrapped target and usually need a target network. Lifted Bellman Linear Programming (LBLP) instead expresses the in-sample optimal values of offline RL as the solution to a linear program over the dataset. Its neural solver ALBUM relaxes the constraints into hinge penalties with fixed coefficients, and its guarantees are conditions on coefficients chosen in advance. We solve the same program with the method of multipliers: the coefficients become multipliers learned by dual ascent, with one penalty parameter ρρ. In the convex case the fixed points are the KKT pairs of LBLP, and at every stationary point the applied constraint weights balance the objective exactly. The critic can serve a Gaussian actor, a flow actor, and best-of-N sampling, and for the Gaussian actor we propose an advantage-normalized DDPG+BC objective. With a single QQ and VV and no target network, our AL-LBLP with best-of-N reaches 60.1% average success on the 50 state-based OGBench tasks. On long-horizon tasks, it reaches 81.5% on humanoidmaze-giant and 79.8% on antmaze-giant. It does not collapse up to batch size 8192.

Figures & tables

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Lifted Bellman Linear Programming for Offline Reinforcement Learning

    Sep 21, 2026Hyukjun Yang, Jongchan Park, Narim Jeong +1Reinforcement LearningOffline RL

  2. Augmented Lagrangian Multiplier Network for State-wise Safety in Reinforcement Learning

    May 1, 2026Jiaming Zhang, Yujie Yang, Yao Lyu +2Constrained RLAugmented Lagrangian Method

  3. Neural Actor--Critic Learning with Minimax Critics and Reflected Langevin Sampling

    Nov 2, 2026Kunqi Huang, Lican Kang, Hongrui Shu +1Actor-Critic MethodsContinuous Control