- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes Lifted Bellman Linear Programming (LBLP), an offline reinforcement learning method that learns value functions by enforcing Bellman inequalities rather than minimizing squared Bellman errors. The formulation jointly optimizes Q and V functions and introduces multi-step trajectory constraints to accelerate value propagation. The authors establish that the exact LP and its hinge-penalty relaxation recover the in-sample optimal value functions under specified conditions.
For practical implementation, the paper introduces ALBUM, which approximates the formulation using neural networks and stop-gradient multi-step targets. On OGBench, ALBUM achieves performance comparable to FQL while requiring fewer parameters and less GPU memory, without target networks or critic ensembles.
Critical strengths
The LP formulation provides an interesting alternative to conventional Bellman regression. The theoretical results establish the exactness of the tabular formulation and characterize how multi-step constraints can accelerate value propagation.
The empirical performance and computational efficiency are promising. ALBUM achieves an average success rate of 43.4, comparable to FQL's 43.6, while using approximately half as many parameters and substantially less GPU memory. Its ability to train without target networks or critic ensembles is particularly interesting.
Critical weaknesses
- (Major weakness) The main theoretical contribution does not adequately explain the behavior of the actual algorithm.
Propositions 4.3 and 4.7 characterize the exact LP and its tabular relaxation, while Theorem 4.5 analyzes an idealized update. However, ALBUM uses neural function approximation and a detached update that differs from the gradient of the proposed objective. The theoretical results therefore do not establish convergence of the implemented algorithm. More importantly, Appendix L.11 shows that the learned critics do not satisfy the theoretical formulation: the Bellman inequality holds on only 50%–81% of samples, and the learned mean values exceed the empirical optimum in nine of ten environments. Thus, the empirical success of ALBUM cannot be directly explained by the exactness results. The paper needs stronger evidence connecting its theoretical formulation to the observed improvements.
- (Major weakness) The main theoretical contribution does not adequately explain the behavior of the actual algorithm.
Propositions 4.3 and 4.7 characterize the exact LP and its tabular relaxation, while Theorem 4.5 analyzes an idealized update. However, ALBUM uses neural function approximation and a detached update that differs from the gradient of the proposed objective. The theoretical results therefore do not establish convergence of the implemented algorithm. More importantly, Appendix L.11 shows that the learned critics do not satisfy the theoretical formulation: the Bellman inequality holds on only 50%–81% of samples, and the learned mean values exceed the empirical optimum in nine of ten environments. Thus, the empirical success of ALBUM cannot be directly explained by the exactness results. The paper needs stronger evidence connecting its theoretical formulation to the observed improvements.
- (Major weakness) The paper does not establish why ALBUM can avoid the instability associated with the well-known deadly triad in reinforcement learning.
The deadly triad arises from combining function approximation, bootstrapping, and off-policy learning, potentially causing divergence. ALBUM retains all three ingredients despite replacing squared Bellman regression with inequality-based penalties. Proposition 5.1 provides only a necessary condition preventing unbounded descent along a particular direction, not a general stability or convergence guarantee. This is particularly important because one of the paper's main practical advantages is training without target networks or critic ensembles, which are commonly used to stabilize off-policy learning. Although the experiments demonstrate stability in the evaluated environments, they do not establish whether the proposed formulation fundamentally mitigates the deadly triad. Controlled comparisons on classical off-policy divergence examples would be informative.
- (Major weakness) The deterministic dynamics assumption substantially limits the theoretical justification of the practical algorithm.
The interpretation of sampled multi-step returns as valid lower bounds relies on deterministic transitions. Under stochastic dynamics, sampled returns need not satisfy the corresponding expected Bellman inequalities. Although the exact LP formulation is more general, its sampled neural implementation does not inherit the same guarantees. Since stochastic transitions are common in reinforcement learning, the paper should demonstrate how ALBUM behaves under transition noise. Without such evidence, the applicability of the proposed multi-step learning mechanism remains unclear.
Questions for authors
Given that the learned neural critics are generally infeasible for LBLP, what evidence establishes that the empirical performance improvements arise from the proposed LP formulation rather than from the particular heuristic updates? Since ALBUM retains all three ingredients of the deadly triad, can the authors provide theoretical or empirical evidence that its inequality-based updates are more stable than conventional off-policy TD learning? In particular, how does ALBUM perform on classical divergence examples such as Baird's counterexample? How does ALBUM perform under stochastic transitions, where sampled multi-step returns may no longer provide valid lower bounds? What explains the substantial sensitivity to rollout horizons and penalty coefficients despite satisfying Proposition 5.1? Can the authors provide a principled procedure for selecting these parameters?
7 comments
Response to Reviewer KDbs (2/6)
(ii) Fraction of satisfied constraints. Appendix L.11 states that the learned pair is not feasible for LBLP. This statement was intended as a statement of scope. Our exactness results characterize the solution of the program, not the values that the neural critic attains (Appendix A). Infeasibility itself is expected of any approximate critic, just as a TD critic does not satisfy the Bellman equation exactly. However, we realize that Appendix L.11 reported the fraction of satisfied constraints without a reference level and without the size of the violations. Under deterministic dynamics and continuous states, each state of carries a single action, and holds with equality on every pair. Every one-step constraint is therefore active at the solution. Near the solution, the fraction of violated constraints is determined by the sign of the approximation error and not by its size. The reference level is 50% when positive and negative errors are equally likely. To measure the fraction and the size of the violations against this reference, we compared the constraint residual of ALBUM with the TD error of FQL and ReBRAC. Each quantity is computed with the training target of each method on the same dataset pairs after 1M steps over 4 seeds.
| Task | Method | or (%) | or : Mean | or : p90 | or : p99 |
|---|---|---|---|---|---|
| antmaze-large | ALBUM | 67.9 | 0.05 | 0.13 | 0.66 |
| FQL | 54.3 | 0.10 | 0.30 | 1.07 | |
| ReBRAC | 51.8 | 0.07 | 0.22 | 0.60 | |
| scene | ALBUM | 64.1 | 0.32 | 0.96 | 3.59 |
| FQL | 50.3 | 0.59 | 1.74 | 5.37 | |
| ReBRAC | 49.6 | 0.81 | 2.51 | 6.21 | |
| puzzle-3x3 | ALBUM | 68.7 | 0.37 | 1.11 | 4.60 |
| FQL | 48.2 | 1.19 | 3.36 | 12.01 | |
| ReBRAC | 48.8 | 1.82 | 5.55 | 16.41 |
The fraction for the TD critics is close to the reference level, and ALBUM violates fewer constraints, by a smaller mean amount than the positive TD error of both TD critics. In the revision, Appendix L.11 states this comparison level and reports the residual comparison above.
(iii) Learned values above . We realize that Appendix L.11 closes with the infeasibility of the learned pair, and this framing presented the departure from as a failure. Since each state of carries a single action, is the return of the behavior trajectory through . The behavior trajectories reach the goal far less often than ALBUM, which succeeds in 92.5% of the episodes on antmaze-large. The value at a state is determined jointly with the values at neighboring states of other trajectories through shared parameters. A value above is therefore consistent with generalization from neighboring trajectories with higher returns. This generalization lies outside our exactness results. To determine whether this behavior is specific to the LP formulation, we evaluated the critics of FQL and ReBRAC against on the same dataset pairs, with the relative gap for each method. Both TD critics also exceed on scene and puzzle-3x3, so a mean above is not specific to ALBUM (Appendix L.11).
| Task | Method | Mean of | Relative gap |
|---|---|---|---|
| antmaze-large | ALBUM | 21.8 ± 0.3 | 13.7 ± 0.2% |
| FQL | -2.4 ± 0.2 | -2.7 ± 0.2% | |
| ReBRAC | 2.7 ± 0.1 | 3.0 ± 0.1% | |
| scene | ALBUM | 217.6 ± 3.2 | 43.1 ± 0.6% |
| FQL | 94.0 ± 1.6 | 33.0 ± 0.6% | |
| ReBRAC | 63.2 ± 2.3 | 22.2 ± 0.8% | |
| puzzle-3x3 | ALBUM | 350.3 ± 2.6 | 48.6 ± 0.4% |
| FQL | 174.5 ± 2.5 | 43.0 ± 0.6% | |
| ReBRAC | 128.3 ± 4.2 | 31.6 ± 1.0% |
Response to Reviewer KDbs (3/6)
Answer W2. We thank the reviewer for this question and would like to clarify the scope of our claims. The paper does not claim that ALBUM resolves or mitigates the deadly triad in general. To our knowledge, such a general guarantee is not available for any deep off-policy method with nonlinear function approximation. Our claim is narrower. ALBUM does not require target networks or critic ensembles. Appendix L.1 of the submission already explains this claim by tracing each device to the failure mode it was introduced to control and showing that the LBLP critic objective does not contain that failure mode, and the revised Section 6.1 states this mechanism in the main text. On Baird's counterexample in the new Appendix L.1.1, TD methods diverge without a target network, whereas ALBUM remains bounded at every step size (Please see (iii)).
(i) Critic ensembles. The upward bias that critic ensembles counteract arises because the bootstrapped target queries the maximum of the estimated values at the next state, either through or through a policy action chosen to maximize the estimated . Selecting the largest of noisy estimates biases the target upward, and Double Q-learning (van Hasselt, 2010) and its successors (van Hasselt et al., 2016; Fujimoto et al., 2018) reduce this bias by decorrelating the estimates over which the maximum is taken. In offline RL, the queried action can lie outside the dataset, and ensembles such as SAC-N and EDAC (An et al., 2021) also counteract the resulting overestimation. In LBLP, the bootstrapped quantity is , which is a decision variable rather than the result of selecting an action. The objective lowers , and the epigraph constraint bounds it from below only through at dataset actions. The critic update therefore contains no step that selects an action by maximizing estimated values, and it never evaluates at an action outside the dataset.
(ii) Target networks. Target networks in DQN and DDPG (Mnih et al., 2015; Lillicrap et al., 2015) stabilize the regression of onto a target that depends on itself. A squared loss produces an update proportional to the error against a target that moves with the parameters, and the slowly updated copy limits this feedback. Neither LBLP nor its relaxation in ALBUM involves such a regression. Every bootstrapped quantity enters only as a bound inside a hinge, so a violation contributes a gradient with a fixed coefficient, independent of the size of the constraint residual.
(iii) Controlled comparison. Following the reviewer's suggestion, we ran Baird's counterexample with linear features and , and Appendix L.1.1 reports the learning curves. All rewards are zero, so is also the LBLP solution. The table reports the final max error after SGD steps, mean ± std over 5 seeds, and the initial error is 12. The last column uses the decaying step size , and div. denotes in all 5 seeds. Without a target network, TD(0), Q-learning, and clipped double Q-learning diverge. A target network () mitigates divergence, but its error increases throughout training at a step size of and remains above 7 under the decaying schedule. ALBUM and subgradient descent on the relaxed LBLP objective remain bounded in every setting. At a constant step size they settle in a neighborhood of whose radius scales with the step size, as expected for updates on a nonsmooth objective. Under the decaying schedule they reach the smallest errors among all methods. This difference is consistent with the mechanism in (ii). These results concern linear features, and for neural networks with the detached -step term, we do not have a stability guarantee. On OGBench, Section 6.1 shows that removing target networks and critic ensembles degrades ReBRAC and FQL, whereas ALBUM trains without either.
| Method | ||||
|---|---|---|---|---|
| TD(0) | div. | div. | div. | div. |
| TD(0) + target | 0.031 ± 0.002 | 0.077 ± 0.001 | 7.5 ± 3.4 | |
| Q-learning | 2000 ± 150 | div. | div. | div. |
| Q-learning + target | 1400 ± 99 | 168 ± 48 | 0.27 ± 0.01 | 12.0 ± 1.0 |
| Clipped double Q | 2000 ± 150 | div. | div. | div. |
| Clipped double Q + target | 1300 ± 97 | 143 ± 38 | 0.26 ± 0.01 | 11.6 ± 0.7 |
| Relaxed LBLP | 0.027 ± 0.001 | 0.27 ± 0.01 | 2.7 ± 0.2 | 0.027 ± 0.002 |
| ALBUM | 0.054 ± 0.001 | 0.53 ± 0.01 | 5.4 ± 0.2 | 0.053 ± 0.001 |
[refrences] Other cited works are listed in the references of the paper.
(An et al., 2021) An, G., Moon, S., Kim, J. H., & Song, H. O. (2021). Uncertainty-based offline reinforcement learning with diversified q-ensemble. Advances in neural information processing systems, 34, 7436-7447.
Response to Reviewer KDbs (1/6)
weaknesses
Answer W1.
We share this concern, and it is the reason Appendix L.11 compares the learned critic with the in-sample optimum.
Summary.
Our theory does not establish convergence of the neural update. However, the theory characterizes the solution that the update targets, why the stop gradient preserves this solution, and when the update diverges ((i)). A fraction of satisfied constraints near 50% is the reference level for an approximate critic, and the TD critics of FQL and ReBRAC stay near this level, whereas ALBUM satisfies more constraints with smaller violations ((ii)). Learned values above GD also occur for both TD critics on scene and puzzle-3x3 ((iii)).
Details.
(i) Theoretical relation of the implemented update to LBLP. We agree that our theory does not fully establish convergence of the neural update, as is the case for deep off-policy methods with nonlinear function approximation, and Appendix A states this. However, Appendix A also divides our results into two groups according to whether the neural parameterization affects them, and the second group concerns the implemented update itself.
The detached update of ALBUM differs from the gradient of the proposed objective only in the K-step term. The objective terms, the one-step hinge, and the epigraph hinge, which define the relaxed LBLP without the K-step term (Lemma 4.2), are differentiated without stop gradient. Under the conditions of Appendix I, (QD∗,VD∗) remains a stationary point of the detached update field (Proposition I.4, Corollary I.5), so the stop gradient preserves the solution. Proposition 5.1 gives a necessary condition for the boundedness of the neural update, whose violation certifies divergence, as Section 6.1 confirms, but within the region where the condition holds, the condition does not predict how well the update performs. The theory explains the behavior of the implemented update in three respects, the solution that the update targets, why the stop gradient preserves this solution, and when the update diverges.