LOW RANK APPROXIMATIONS TO MARKOV DECISION PROCESSES

Abstract

Popular among inventory problems, backward dynamic programming (BDP) is an efficient tool to solve many complex problems in many di erent applications that can be formulated as finite-horizon Markov decision processes. Rolling backwards in time, the algorithm computes the value of being in a certain state which can be described by multiple state variables. Although the policy we obtain from the BDP is optimal, each state must be visited at each time step, making it very computationally difficult as we increase the dimensions of the state space, the action space or the outcome space, especially when dealing with non-convex value functions. In this thesis, we implement and develop an approximate dynamic programming (ADP) algorithm that takes advantage of value functions that are of low rank. In our algorithm, we perform matrix completion at each time step to recover an approximation of the value function. We evaluate the performance of this method by applying it to different problems including a battery storage problem for energy arbitrage and frequency regulation, and an hour-ahead bidding problem in real time electricity markets. We note that in the battery storage problem, we get near-optimal policies using our ADP algorithm. In the bidding problem, we run into issues due to a more complex value function that forces us to modify our ADP algorithm.