An Augmented Lagrangian Approach to Lifted Bellman Linear Programming
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 and 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
| Gaussian policy | Flow policy | Best-of- | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Environment | IQL | ReBRAC | ALBUM | AL-LBLP | FQL | DROL | FAC | AL-LBLP | IFQL | AL-LBLP |
| antmaze-large | 53 3 | 81 5 | 89.8 1.0 | 92.2 1.5 | 79 3 | 89 | 92.6 | 89.0 2.9 | 28.0 | 76.8 4.3 |
| antmaze-giant | 4 1 | 26 8 | 28.1 5.1 | 47.5 7.4 | 9 6 | 45 | 23.0 | 29.4 4.0 | 2.6 | 34.9 3.4 |
| humanoidmaze-medium | 33 2 | 22 8 | 35.5 1.8 | 85.6 2.7 | 58 5 | 68 | 75.6 | 78.5 3.8 | 60.4 | 96.1 1.2 |
| humanoidmaze-large | 2 1 | 2 1 | 1.6 0.5 | 17.4 1.0 | 4 2 | 11 | 8.3 | 12.4 3.5 | 11.0 | 47.7 4.3 |
| antsoccer-arena | 8 2 | 0 0 | 36.1 3.8 | 48.5 4.5 | 60 2 | 65 | 67.7 | 56.5 5.9 | 33.2 | 56.1 4.4 |
| Batch size | ||||
|---|---|---|---|---|
| Environment | 256 | 2048 | 4096 | 8192 |
| antmaze-giant ( ) | 47.5 7.4 | 56.1 4.0 | 53.7 3.9 | 52.2 4.5 |
| antmaze-giant ( ) | 64.6 3.8 | 70.8 3.7 | 66.0 2.2 | 59.5 3.6 |
| antmaze-giant ( ) † | 64.6 3.8 | 78.4 3.0 | 79.8 2.5 | 77.4 2.5 |
| humanoidmaze-large ( ) | 17.4 1.0 | 32.9 7.0 | 39.9 6.5 | 33.1 7.5 |
| humanoidmaze-giant ( ) | 71.0 3.5 | 77.8 7.7 | 79.7 4.3 | 79.3 5.7 |
| [ ] | srank [ ] | |
|---|---|---|
| 0.1 | 26.7 1.6 | 408 1 |
| 0.5 | 65.7 2.3 | 317 7 |
| 1 | 93.7 7.5 | 297 8 |
| AL-LBLP | ALBUM | ||||
|---|---|---|---|---|---|
| Family | |||||
| Bellman | (%) | 47.3 0.9 | 39.9 1.0 | 37.3 0.4 | 33.0 0.9 |
| 1.38 0.06 | 0.82 0.04 | 0.63 0.03 | 0.84 0.15 | ||
| Epigraph | (%) | 46.8 0.9 | 42.3 0.7 | 37.1 0.5 | 31.7 2.8 |
| 1.41 0.07 | 0.80 0.02 | 0.60 0.02 | 0.59 0.07 | ||
| -step | (%) | 34.7 0.6 | 15.2 0.7 | 9.6 0.1 | 7.0 1.8 |
| Penalty | lr | Coeff. | Actor | 1M | 3M | ||
|---|---|---|---|---|---|---|---|
| AL-LBLP | quadratic | 47.6 1.1 | 58.0 2.7 | 0.71 0.02 | |||
| quadratic | 46.3 1.7 | 51.7 3.7 | 0.71 0.02 | ||||
| multipliers | quadratic | 42.1 0.8 | 45.3 2.5 | 0.98 0.05 | |||
| quadratic term | hinge | 30.0 1.7 | 26.7 2.7 | 5.50 0.88 | |||
| quadratic term | hinge | 45.7 5.5 | 33.8 2.9 | 3.32 0.32 | |||
| ALBUM | hinge | 43.0 1.0 | 44.9 4.2 | 5.17 2.53 |
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
| Hyperparameter | Value |
|---|---|
| Rollout length | 10 |
| Discount | 0.995 |
| Penalty parameter | per environment; ( Table 7 , Table 8 ) |
| Objective weights | |
| Multiplier parameterization | initialized at |
| Optimizer | Adam |
| antmaze-l | antmaze-g | humanoid-m | humanoid-l | antsoccer | cube-s | cube-d | scene | puzzle-3 | puzzle-4 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Gaussian policy | 0.05 | 0.1 | 0.1 | 0.5 | 0.5 | 0.05 | 0.5 | 0.5 | 0.05 | 0.05 | |
| 3 | 1 | 1 | 3 | 3 | 10 | 10 | 3 | 3 | 10 | ||
| Flow policy | 0.1 | 0.1 | 0.1 | 0.5 | 0.5 | 0.1 | 0.5 | 0.5 | 0.1 | 0.1 | |
| 3 | 3 | 10 | 30 | 10 | 30 | 30 | 10 | 30 | 30 | ||
| Best-of- | 0.5 | 0.1 | 0.1 | 0.1 | 0.5 | 0.5 | 0.5 | 0.5 | 0.1 | 0.5 | |
| 8 | 8 | 32 | 16 | 16 | 8 | 8 | 8 | 16 | 16 |
| cube-single | cube-double | scene | puzzle-3x3 | puzzle-4x4 | |
|---|---|---|---|---|---|
| 1 | 2 | 1 | 0.5 | 0.5 | |
| 100 | 30 | 10 | 10 | 10 |
| Batch size | |||||
|---|---|---|---|---|---|
| Environment | Method | 256 | 2048 | 4096 | 8192 |
| humanoidmaze-large | FQL | 4 2 | 4.9 6.3 | 0.0 0.0 | – |
| FAC | 8.3 5.5 | 0.0 0.0 | 0.0 0.0 | – | |
| AL-LBLP | 17.4 1.0 | 32.9 7.0 | 39.9 6.5 | 33.1 7.5 | |
| antmaze-giant | FQL | 9 6 | 0.0 0.0 | 0.0 0.0 | – |
| FAC | 23.0 5.1 | 0.1 0.2 | 0.0 0.0 | – | |
| Critics | GPU-h | Speed-up | |||
|---|---|---|---|---|---|
| per run | |||||
| Separate runs | |||||
| one at a time | 1 | 0.71 | 1.41 | 1.0 | 1.0 |
| concurrent | 1 | 0.77 | 1.55 | 0.9 | 0.9 |
| One run | |||||
| a critic per | 0.38 | 0.56 | 1.8 | 2.5 | |
| AL-LBLP (ours), offline RL | ALBUM, offline RL | Off2On RL | Offline GCRL | |||||
|---|---|---|---|---|---|---|---|---|
| Task | batch 256 | batch 2048 | batch 4096 | batch 8192 | batch 256 | batch 4096 | LQL | TRL |
| antmaze-giant task1 | 45.5 9.5 | 56.8 6.1 | 47.2 11.9 | 37.0 14.1 | 0.2 0.7 | 0.0 0.0 | – | – |
| antmaze-giant task2 | 82.5 4.6 | 80.2 5.5 | 78.0 3.7 | 75.5 6.2 | 82.5 9.7 | 87.8 5.4 | – | – |
| antmaze-giant task3 | 39.8 12.3 | 47.2 9.7 | 35.5 8.5 | 25.2 10.2 | 0.0 0.0 | 50.0 15.3 | – | – |
| antmaze-giant task4 | 75.8 9.5 | 83.5 6.5 | 82.5 5.0 | 70.5 6.6 | 63.8 9.5 | 78.8 9.6 | – | – |
| antmaze-giant task5 | 79.5 12.3 | 86.2 4.5 | 86.8 5.2 | 89.5 5.8 | 1.0 1.5 | 0.5 0.9 | – | – |
| Gaussian policy | Flow policy | Best-of- | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Task | IQL | ReBRAC | ALBUM | AL-LBLP | FQL | DROL | FAC | AL-LBLP | IFQL | AL-LBLP |
| antmaze-large task1 (default) | 48 9 | 91 10 | 92.5 3.1 | 92.5 4.9 | 80 8 | 98 | 94.0 | 89.8 5.3 | 24 17 | 76.0 15.6 |
| antmaze-large task2 | 42 6 | 88 4 | 80.2 6.0 | 85.8 3.8 | 57 10 | 84 | 86.0 | 79.0 9.0 | 8 3 | 72.2 6.5 |
| antmaze-large task3 | 72 7 | 51 18 | 91.8 2.7 | 95.8 2.7 | 93 3 | 90 | 97.5 | 90.2 7.1 | 52 17 | 76.8 6.9 |
| antmaze-large task4 | 51 9 | 84 7 | 92.5 4.0 | 93.2 4.8 | 80 4 | 79 | 89.5 | 92.0 4.3 | 18 8 | 77.2 8.6 |
| antmaze-large task5 | 54 22 | 90 2 | 92.0 4.7 | 93.8 2.7 | 83 4 | 93 | 96.0 | 93.8 4.3 | 38 18 | 81.8 3.6 |
| Environment | Gaussian policy | Flow policy | Best-of- |
|---|---|---|---|
| antmaze-large | 94.7 1.2 98.7 2.3 | 85.3 3.1 96.0 2.0 | 78.0 15.6 97.3 3.1 |
| antmaze-giant | 34.7 11.4 94.7 1.2 | 10.0 0.0 63.3 54.9 | 0.0 0.0 93.3 2.3 |
| humanoidmaze-medium | 84.7 7.0 99.3 1.2 | 90.0 6.0 100.0 0.0 | 96.7 1.2 98.0 2.0 |
| humanoidmaze-large | 47.3 2.3 38.0 11.1 | 14.7 8.1 23.3 9.5 | 59.3 7.0 86.7 4.6 |
| antsoccer-arena | 26.7 8.1 57.3 4.2 | 44.0 3.5 54.0 13.1 | 45.3 12.1 38.7 6.1 |
| cube-single | 94.7 4.2 90.7 6.1 | 94.0 6.0 94.0 8.7 | 98.0 0.0 97.3 2.3 |
| Environment | IQL | ReBRAC | FQL | FAC | AL-LBLP |
|---|---|---|---|---|---|
| cube-single | 70 | 83 | 81 | 82.0 | 79.5 8.2 |
| cube-double | 34 | 4 | 21 | 48.0 | 52.5 4.1 |
| scene | 97 | 98 | 98 | 99.0 | 95.0 2.6 |
| puzzle-3x3 | 7 | 88 | 94 | 95.0 | 93.0 6.2 |
| puzzle-4x4 | 0 | 26 | 33 | 56.0 | 3.5 4.7 |
| Average | 41.6 | 59.8 | 65.4 | 76.0 | 64.7 2.6 |
| Task | 1M | 2M | 3M | 1M | 2M | 3M | 1M | 2M | 3M |
|---|---|---|---|---|---|---|---|---|---|
| antmaze-large (default) | 95.3 | 92.7 | 91.3 | 95.3 | 95.3 | 97.3 | 87.3 | 92.7 | 94.7 |
| antmaze-giant (default) | 31.3 | 35.3 | 29.3 | 0.0 | 38.7 | 54.7 | 0.0 | 0.0 | 32.0 |
| humanoidmaze-med. (default) | 91.3 | 90.7 | 90.0 | 82.0 | 92.0 | 97.3 | 48.7 | 76.7 | 94.0 |
| humanoidmaze-large (default) | 34.7 | 21.3 | 24.7 | 40.0 | 52.0 | 54.0 | 16.7 | 39.3 | 57.3 |
| antsoccer (default) | 24.0 | 17.3 | 7.3 | 27.3 | 24.0 | 28.0 | 27.3 | 38.0 | 22.0 |
| Environment | LHS ( ) | LHS ( ) | ||||
|---|---|---|---|---|---|---|
| antmaze-large | 0.150 0.010 | 0.145 0.001 | 0.004 0.001 | 0.222 0.007 | 0.072 0.001 | 0.198 0.007 |
| antmaze-giant | 0.150 0.009 | 0.144 0.001 | 0.010 0.006 | 0.252 0.016 | 0.071 0.001 | 0.229 0.016 |
| humanoidmaze-medium | 0.150 0.009 | 0.144 0.001 | 0.005 0.001 | 0.238 0.006 | 0.071 0.000 | 0.214 0.007 |
| humanoidmaze-large | 0.148 0.008 | 0.145 0.001 | 0.004 0.000 | 0.232 0.015 | 0.072 0.001 | 0.208 0.015 |
| antsoccer-arena | 0.151 0.011 | 0.139 0.001 | 0.009 0.000 | 0.350 0.036 | 0.068 0.001 | 0.328 0.037 |
| cube-single | 0.154 0.011 | 0.143 0.002 | 0.012 0.001 | 0.336 0.019 | 0.067 0.001 | 0.312 0.020 |
Offline RL
Offline reinforcement learning learns decision-making policies from fixed datasets without interacting with the environment during training.
See all 325 papers