An Augmented Lagrangian Approach to Lifted Bellman Linear Programming

Jongchan Park, Hyukjun Yang, Narim Jeong, Donghwan LeearXiv 2026 · arXiv

TL;DR

AL-LBLP is a novel offline reinforcement learning (RL) algorithm that replaces traditional, unstable temporal-difference learning with a robust linear programming formulation. By using an Augmented Lagrangian approach to "learn" constraint weights, it achieves state-of-the-art performance on challenging long-horizon tasks—like giant mazes—without needing target networks or ensembles.

What Problem Does This Paper Address?

Offline RL is notoriously difficult because the agent must learn a policy from a fixed dataset without any further environment interaction. Most current methods rely on Temporal-Difference (TD) learning, which regresses values onto a "bootstrapped" target. This often leads to overestimation errors when the policy chooses actions not well-represented in the data. To combat this, researchers use "hacks" like target networks, ensembles of critics, and heavy regularization.

An alternative is Linear Programming (LP), which characterizes optimal values as the solution to a set of constraints. While theoretically elegant, LP methods have historically struggled to scale to deep RL benchmarks. A recent method called ALBUM showed promise by relaxing these constraints into fixed "hinge" penalties, but it required manual, problem-specific tuning of those penalty weights to work correctly.

Methods

The authors introduce AL-LBLP (Augmented Lagrangian Lifted Bellman Linear Programming). Its core innovations are:

  • The Method of Multipliers: Instead of using fixed penalty weights for constraint violations, AL-LBLP uses an Augmented Lagrangian framework. It treats the constraint weights as "multipliers" that are learned via dual ascent during training. This allows the algorithm to automatically adjust how much to penalize different types of Bellman errors.
  • No Moving Targets: Because it solves an LP, the critic is trained directly on the dataset transitions. There is no regression onto a moving target network, which simplifies the architecture and improves stability.
  • Advantage-Normalized Actor: They propose a new objective for the actor (the policy) where the improvement term is normalized by the mean absolute advantage $|Q - V|$. This makes the policy update invariant to shifts in reward scales or value offsets, leading to much more stable training across different environments.
  • Policy-Agnostic Critic: The critic is trained entirely on dataset actions and doesn't need to "query" the policy during its update. This allows one critic to be shared among multiple different types of actors (Gaussian, Flow-based, etc.) or even different hyperparameters simultaneously.

Datasets

The researchers evaluated their method on OGBench, a comprehensive suite of 50 state-based tasks and 5 pixel-based manipulation tasks. These include navigation (like mazes) and robotic manipulation (like puzzles and cube stacking).

Crucially, they tested on "Giant" versions of the AntMaze and HumanoidMaze, which represent extremely long-horizon navigation challenges where traditional RL often fails to propagate value signals from the goal back to the start.

Key Insights and Ideas

  • Quadratic Penalties for Better Propagation: Unlike the "hinge" loss in ALBUM which applies a constant gradient to any violation, the Augmented Lagrangian's quadratic term applies a penalty that grows with the size of the violation. This is the "aha" moment for long-horizon tasks: it forces the value function to be much more precise, allowing the "reward signal" to travel further across the state space.
  • Robustness to Batch Size: One of the most surprising findings is that AL-LBLP is incredibly stable at high batch sizes. While TD-based methods often collapse when the batch size reaches 2048 or 4096, AL-LBLP maintains or even improves its performance up to a batch size of 8192.
  • Invariance as a Feature: By normalizing the actor update by the advantage, the authors created a system that doesn't care if you add 100 to every reward or scale them by 10. This robustness is a significant practical advantage for real-world robotics where reward engineering is difficult.
Figure 1. (a) Offline-to-online fine-tuning of the three AL-LBLP policies and ALBUM: mean success (%) over the 10 default tasks during offline training (grey) and online fine-tuning; mean ± std over 3 seeds. (b) Training to 3M steps with ρ ∈{0.1, 0.5, 1} (α of Figure 2(a)) and ALBUM: mean success (%) over the 10 default tasks, evaluated every 0.5M steps; mean ± std over 3 seeds. (c), (d) Learned value (1 −γ)V (s) of AL-LBLP (K = 50, γ = 0.999, batch 4096, (ρ, α) of the † rows of Table 2) on task 1 (details in Section C).

Key Results

  • State-of-the-Art on OGBench: AL-LBLP achieved a 60.1% average success rate across the 50 state-based tasks, outperforming established baselines like IQL and FQL.
  • Conquering Giant Mazes: On the most difficult long-horizon tasks, it reached 81.5% success on humanoidmaze-giant and 79.8% on antmaze-giant. For comparison, many previous methods score near zero on these tasks.
  • Training Efficiency: Because the critic doesn't depend on the actor, the authors could train six different policy versions at once with a single shared critic, achieving a 4.3x speedup in total training time.
  • Successful Fine-tuning: The method also excels at "offline-to-online" fine-tuning, where an agent pre-trained on data is allowed to interact with the environment to further improve.

Limitations and Future Work

  • Manipulation Gap: While AL-LBLP dominates in navigation, it is slightly less dominant in complex manipulation tasks compared to some specialized TD-based methods.
  • Hyperparameter Selection: Although it removes the need to tune constraint weights, a single penalty parameter $\rho$ and a behavior-cloning coefficient $\alpha$ still need to be selected per environment.
  • VLA Integration: The authors see a major opportunity in attaching AL-LBLP critics to massive Vision-Language-Action (VLA) models. Since the critic can be trained without querying the policy, it could provide a "value-based" filter for the high-dimensional outputs of these foundation models.

Summary updated

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 $Q$ and $V$ 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.
BibTeX
@misc{park2026augmented,
  author = {Jongchan Park and Hyukjun Yang and Narim Jeong and Donghwan Lee},
  title = {{An Augmented Lagrangian Approach to Lifted Bellman Linear Programming}},
  year = {2026},
  eprint = {2611.14183},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.14183},
}
Figure