Approximate Dynamic Programming with Basis Function Learning
Organizations: Dynamic Optimization and Reinforcement Learning (DORL) Lab, Department of Mechanical and Industrial Engineering, University of Toronto.
Abstract
This work presents a novel approach for approximating the value function in Markov decision processes (MDPs). Our approach is grounded in the approximate linear programming (ALP) framework, wherein basis functions (BFs) play an important role. Traditionally, BFs have been pre-defined, randomly generated, or restricted to specific structures, which both limits the accuracy that can be achieved and leaves no mechanism for improving a given approximation. We instead learn BFs from the model itself, by repeatedly applying the Bellman operator to the current value estimate. We introduce the Bellman operator basis function (BOBF) learning method, and prove that each learned BF improves the approximation by a quantifiable amount and that the method converges to the optimal value function. Its shrunken counterpart (SBOBF) retains this guarantee while capping the number of BFs, and therefore the computational effort per iteration. For large-scale problems, where the number of constraints is prohibitive, we develop hybrid variants (HBOBF and SHBOBF) that combine constraint sampling with BF learning, and we show that the improvement and finite-termination guarantees are preserved under explicitly stated conditions. Numerical experiments on (continuous) perishable inventory and queueing control problems demonstrate that our BF learning techniques significantly outperform existing methods in the literature.
Figures & tables
| Setting and instance group | BOBF / HBOBF | SBOBF(5) / SHBOBF(5) | Fixed | Random (ReLU) | Random (Fourier) | |
|---|---|---|---|---|---|---|
| PIC, full | 1.31e-07 | 1.43e-05 | 4.06e+00 | 6.78e+00 | 3.20e+01 | |
| 3.58e-07 | 1.73e-04 | 3.09e+00 | 6.11e+00 | 2.89e+01 | ||
| Average | 2.45e-07 | 9.36e-05 | 3.57e+00 | 6.44e+00 | 3.04e+01 | |
| PIC, sampled | 3.07e-05 | 3.07e-05 | 3.06e+01 | 5.56e+01 | 1.23e+02 | |
| 2.04e-05 | 2.04e-05 | 1.94e+01 | 6.12e+01 | 9.99e+01 | ||
| Average | 2.56e-05 | 2.56e-05 | 2.50e+01 | 5.84e+01 | 1.11e+02 | |
| Ingredient | PIC | QC |
|---|---|---|
| Nominal state | Empty pipeline, units in every shelf bucket: | Empty system: |
| Policy parameter | with , , | with , |
| Policy | if ; if ; the same quantity if and , and otherwise | |
| Exploratory action law | if , and otherwise | |
| Admissibility filter in Subsample |
| Quantity | PIC | QC |
| Sampled constraints per iteration, | 50,000 | 50,000 |
| Shaped / dispersed weights in | — | |
| Curated states, | 10,000 | 10,000 |
| Candidate actions per curated state, | 20 | 20 |
| Chain-walk fraction, | 0.7 | 0.7 |
| Parallel trajectories, | 512 | 512 |
| Instance parameters | Conservative relative error bound | ||||||
| ( , ) | ( , ) | BOBF | SBOBF(5) | Fixed | Random (ReLU) | Random (Fourier) | |
| (2,2) | (10, 5) | 0.95 | 1.96e-07 | 3.12e-05 | 6.13e+00 | 5.48e+00 | 1.44e+01 |
| 0.99 | 5.72e-07 | 5 .65e-05 | 6.71e+00 | 5.90e+00 | 1.43e+01 | ||
| (10, 20) | 0.95 | 8.66e-08 | 5.24e-06 | 3.30e+00 | 1.33e+01 | 5.02e+01 | |
| 0.99 | 1.93e-07 | 2.13e-05 | 9.68e+00 | 1.51e+01 | 4.99e+01 | ||
| (100, 5) | 0.95 | 1.55e-12 | 4.85e-08 | 9.68e-01 | 2.41e+00 | 1.48e+01 | |
| Instance parameters | Empirical relative error bound | ||||||
| ( ) | ( ) | HBOBF | SHBOBF(5) | Fixed | Random (ReLU) | Random (Fourier) | |
| (5,6) | (10,5) | 0.95 | 5.20e-05 | 5.20e-05 | 1.82e+01 | 3.12e+01 | 5.42e+01 |
| 0.99 | 7.40e-05 | 7.40e-05 | 2.12e+01 | 3.52e+01 | 5.42e+01 | ||
| (10,20) | 0.95 | 4.76e-05 | 4.76e-05 | 3.27e+01 | 1.08e+02 | 1.91e+02 | |
| 0.99 | 7.23e-05 | 7.23e-05 | 3.96e+01 | 1.25e+02 | 1.91e+02 | ||
| (100,5) | 0.95 | 8.46e-15 | 5.42e-15 | 2.97e+01 | 1.83e+01 | 5.42e+01 | |
| Instance parameters | Conservative relative error bound | |||||
|---|---|---|---|---|---|---|
| ( , ) | BOBF | SBOBF(5) | Fixed | Random (ReLU) | Random (Fourier) | |
| (3, 15) | 0.8 | 1.66e-08 | 9.07e-08 | 1.00e+00 | 1.61e-01 | 1.00e+00 |
| 1 | 1.10e-08 | 4.62e-07 | 6.41e-01 | 2.50e-01 | 6.41e-01 | |
| 3 | 6.30e-07 | 5.05e-06 | 8.31e-01 | 2.64e-01 | 7.40e-01 | |
| 5 | 9.07e-06 | 8.91e-05 | 1.50e+00 | 1.93e-01 | 9.07e-01 | |
| 10 | 6.45e-05 | 5.01e-05 | 1.80e+00 | 1.40e-01 | 1.00e+00 | |
| Instance parameters | Empirical relative error bound | |||||
|---|---|---|---|---|---|---|
| ( ) | HBOBF | SHBOBF(5) | Fixed | Random (ReLU) | Random (Fourier) | |
| (8, 80) | 0.8 | 6.48e-14 | 6.48e-14 | 1.00e+00 | 1.00e+00 | 1.00e+00 |
| 1 | 1.12e-13 | 1.12e-13 | 1.00e+00 | 1.00e+00 | 1.00e+00 | |
| 3 | 3.75e-05 | 7.11e-05 | 8.34e-01 | 7.99e-01 | 1.00e+00 | |
| 5 | 3.78e-05 | 6.85e-07 | 1.76e+00 | 1.00e+00 | 1.00e+00 | |
| 10 | 6.26e-05 | 9.20e-05 | 2.24e+00 | 1.00e+00 | 1.00e+00 | |
| Instance parameters | Empirical relative error bound | ||||||
| ( ) | ( ) | HBOBF | SHBOBF(5) | Fixed | Random (ReLU) | Random (Fourier) | |
| (5,6) | (10,5) | 0.95 | 3.47e-07 | 3.47e-07 | 2.43e+01 | 3.90e+01 | 4.58e+01 |
| 0.99 | 4.93e-07 | 4.93e-07 | 2.46e+01 | 3.86e+01 | 4.58e+01 | ||
| (10,20) | 0.95 | 1.09e-05 | 1.09e-05 | 3.15e+01 | 1.37e+02 | 1.63e+02 | |
| 0.99 | 1.58e-05 | 1.58e-05 | 3.62e+01 | 1.38e+02 | 1.63e+02 | ||
| (100,5) | 0.95 | 6.32e-10 | 6.32e-10 | 2.63e+01 | 3.54e+01 | 4.58e+01 | |
Value Function Estimation
Value function estimation predicts long-term returns or outcomes from states and actions to support reinforcement learning, planning, and policy evaluation.
See all 73 papers