Location
MC 5501
Speaker
Peyman Mohajerin Esfahani, University of Toronto
Title
From Optimization to Control: An Algorithmic Perspective
Abstract
In this talk, we draw an explicit analogy among four problem classes in optimization and control with a unified solution characterization. This viewpoint allows for a systematic transformation of algorithms from one domain to another. With this in mind, we exploit two linear structural constraints specific to control problems with finite state action pairs to approximate the Hessian in a second order type algorithm from optimization. This leads to novel first order control algorithms with the same computational complexity as model based value iteration and model free Q learning, while exhibiting empirical convergence behaviour similar to model based policy iteration and model free Zap Q learning, with very low sensitivity to the discount factor. If time permits, we also discuss how an interesting analogy between the convex conjugate operator and the Fourier transform can reduce the typical time complexity of the dynamic programming operation from O(XU) to O(X + U), where X and U denote the sizes of the discrete state and input spaces, respectively.