| Popis: |
University of Technology Sydney. Faculty of Science. This thesis presents a subgradient and duality approach towards solving an important class of Markov decision processes. The key assumptions lie in the linear state dynamics and in the convexity of the functions in the Bellman recursion. Approximations of the value functions are then constructed using convex piecewise linear functions formed using operations on tangents. This approach can be efficiently implemented with most of the computational effort reduced to simple matrix additions and multiplications. The quality of the approximations can then be gauged using pathwise duality methods which return confidence intervals for the true unknown value. This thesis will then explore the use of nearest neighbour algorithms in reducing the computational effort. Numerical experiments demonstrate that the subgradient and duality approach returns tight confidence intervals indicating good quality results. These methods are tested on a wide range of applications such as financial option pricing, optimal liquidation problems, battery control, and natural resource extraction. Extension to uncontrolled hidden Markov models is also considered. These methods have all been implemented in a 𝑅 package with scripts posted online to reproduce most of the numerical results within this thesis. |
