Decision making in large stochastic and adversarial environments : a complexity analysis of Policy Iteration
(2015)
Files
thesis-RomainHollanders.pdf
Open Access - Adobe PDF
- 2.58 MB
Details
- Authors
- Supervisors
- Abstract
- How to make the best decision in a complex environment is a question that has haunted many generations of researchers and practitioners. It has given rise to the field of Operations Research which is all about optimized decision making. If moreover, the environment in which decisions need to be made is stochastic, then one is probably trying to solve a Markov Decision Process. If above that, an adversary is to be taken into account, then we enter the framework of Two-Player Turn-Based Stochastic Games. Solving these problems is of critical importance in a huge variety of domains. With the constant growth in problem sizes, efficiency is a main focus. One of the best practical algorithms out there to solve these problems is Policy Iteration. However, the analysis of its performance is admittedly a complex task which is the one we undertake in this thesis. We take as starting point a recent breakthrough from Fearnley showing that Policy Iteration may require an exponential number of steps for two of the three classical objective functions. Despite this result, the gap between upper and lower bounds on the complexity of Policy Iteration is still huge and needs to be tightened. We analyze Policy Iteration through the angle of Unique Sink Orientations, an abstract framework that generalizes Markov Decision Processes and Two-Player Turn-Based Stochastic Games but also Linear Programming for instance. In our tools, we also exploit the Order-Regularity structure, a new line of ideas that has not yet been exploited. Our results include tighter bounds on the complexity of Policy Iteration, both from above and below, and they invalidate a conjectured upper bound related to the Fibonacci sequence. We also show the limits of the classical approaches to obtain new bounds. Finally, we extend Fearnley's result and show that Policy Iteration may exhibit exponential complexity for all three classical objective functions. Today with the recent results regarding its complexity, the full portrait of Policy Iteration is closer to completion than it ever was.
- Affiliations
Citations
Hollanders, R. (2015). Decision making in large stochastic and adversarial environments : a complexity analysis of Policy Iteration. https://hdl.handle.net/2078.5/187528