Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01sb397b684
Title: LOW RANK APPROXIMATIONS TO MARKOV DECISION PROCESSES
Authors: El Tonbari, Mohamed
Advisors: Powell, Warren
Department: Operations Research and Financial Engineering
Class Year: 2016
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.
Extent: 71 pages
URI: http://arks.princeton.edu/ark:/88435/dsp01sb397b684
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Operations Research and Financial Engineering, 2000-2016

Files in This Item:
File SizeFormat 
El_Tonbari_Mohamed_final_thesis.pdf1.47 MBAdobe PDF    Request a copy


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.