A Least-Squares Temporal Difference based method for solving resource allocation problems. (September 2020) - Forootani, Ali; Tipaldi, Massimo; Zarch, Majid Ghaniee; Liuzza, Davide; Glielmo, Luigi
Abstract: Value function approximation has a central role in Approximate Dynamic Programming (ADP) to overcome the so-called curse of dimensionality associated to real stochastic processes. In this regard, we propose a novel Least-Squares Temporal Difference (LSTD) based method: the "Multi-trajectory Greedy LSTD" (MG-LSTD). It is an exploration-enhanced recursive LSTD algorithm with the policy improvement embedded within the LSTD iterations. It makes use of multi-trajectories Monte Carlo simulations in order to enhance the system state space exploration. This method is applied for solving resource allocation problems modeled via a constrained Stochastic Dynamic Programming (SDP) based framework. In particular, such problems are formulated as a set of parallel Birth–Death Processes (BDPs). Some operational scenarios are defined and solved to show the effectiveness of the proposed approach. Finally, we provide some experimental evidence on the MG-LSTD algorithm convergence properties in function of its key-parameters. Highlights: Least-Squares Temporal Difference (LSTD) based method to solve real stochastic processes. Multi-trajectory Greedy LSTD as an exploration-enhanced recursive LSTD algorithm. Policy improvement embedded into LSTD iterations. Modeling of resource allocation problems as a set of Birth–Death Processes. Calculation of pricing policies by means of the Multi-trajectory Greedy LSTD algorithm.