LSPI-CAS: Least-Squares Policy Iteration for Compact Action Set MDPs

Simulation-based, model-free solutions to Markov Decision Processes (MDPs) using the algorithm Least Squares Policy Iteration (LSPI) have been applied to multiple practical settings and in several variants. An optimal policy in an MDP is that policy, or a description of which action to take in a state of the MDP, which performs best according to a given metric such as infinite-horizon d iscounted c ost. A s imulation-based a lgorithm f or a n M DP o btains the optimal policy for an MDP in a model-free manner, i.e. without requiring to know apriori any transition probabilities of the MDP under any policy. This work proposes LSPI-CAS, a version of LSPI for compact action-sets, thus avoiding the discretization of the available action set in a state and thereby improving control over the system. Regular LSPI works by repeatedly picking the current best action in a state x from a finite feasible set of actions Ax, requiring finding a minimum over |Ax| values. Our variant uses two kinds of parametrization, a feature vector f(x) for the state called the actor, and ?(x, a) for the state-action pair which is the critic. LSPI-CAS employs a stochastic gradient algorithm called Simultaneous Perturbation Stochastic Approximation (SPSA) to update the actor in each iteration. Regular LSPI has a module named Least-Squares Q-Value (LSQ) which we employ as critic to evaluate perturbed policy iterates, and further update the policy iterate in direction of improving performance. Our algorithm is for infinite-horizon discounted-cost/reward MDPs, the case of finite-horizon compact-action set MDPs having been solved in an earlier work. Numerical results on three settings, a. control of an inverted pendulum, b. Exercise Policy calculation for an American Put option, and c. M/ M/1/K queue control problem are provided for the algorithm, alongside comparison with LSPI. Improvements in both performance and run-time to find an optimal policy are demonstrated.