cs.LGNov 18, 2026

Approximate Dynamic Programming with Basis Function Learning

Authors: Mohammadreza Fathi, Chi-Guhn Lee

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

Explore similar work

CardsList
  1. Adaptive Resolving Methods for Markov Decision Processes with Function Approximations

    May 17, 2025Jiashuo Jiang, Yinyu Ye, Yiming ZongMarkov Decision ProcessesReinforcement Learning

  2. Weakly Time-Coupled Approximation of Markov Decision Processes

    Mar 13, 2026Negar Soheili, Selvaprabu Nadarajah, Bo YangMarkov Decision ProcessesSequential Decision Making