Solving the Bellman equation: Second-order type methods and the dual domain approach
Abstract: Recent control algorithms for Markov decision processes (MDPs) have been designed using an implicit analogy with well-established optimization algorithms. In the first part of this talk, we make this analogy explicit across four problem classes with a unified solution characterization. This framework, in turn, allows for a systematic transformation of algorithms from one domain to the other. In particular, we identify equivalent optimization and control algorithms that have already been pointed out in the existing literature. With this unifying framework in mind, we then exploit structural constraints specific to MDPs for approximating the Hessian for developing second-order-type algorithms. In the second part of the talk, we approach the Bellman equation through the lens of the conjugate duality. Here, we show that by exploiting the operational duality of infimal convolution and addition (with respect to the conjugate transform), one can transform the minimization in the Bellman equation in the primal domain into an addition in the conjugate domain. In particular, for a specific class of problems with separable data in the state and input variables, this property can be used to reduce the typical time complexity of the Bellman operation.
Bio sketch: Amin Kolarijani has a B.Sc. degree in Electrical Engineering from University of Tehran, Iran, and an M.Sc. degree in Biomedical Engineering from Amirkabir University of Technology, Iran. He received his Ph.D. degree in Systems and Control from Delft University of Technology, The Netherlands, in 2022. He is currently an assistant professor at Delft Center for Systems and Control. His research is mainly focused on developing algorithms for solving dynamic programming and reinforcement learning problems using tools from computational convex analysis, max-plus algebra, and algorithmic optimization. He won the Bronze Medal at the Iranian National Olympiad in Physics in 2005 and was ranked third in Iran’s National Matriculation Exam for Graduate Studies in 2017.
Bio sketch: Amin Kolarijani has a B.Sc. degree in Electrical Engineering from University of Tehran, Iran, and an M.Sc. degree in Biomedical Engineering from Amirkabir University of Technology, Iran. He received his Ph.D. degree in Systems and Control from Delft University of Technology, The Netherlands, in 2022. He is currently an assistant professor at Delft Center for Systems and Control. His research is mainly focused on developing algorithms for solving dynamic programming and reinforcement learning problems using tools from computational convex analysis, max-plus algebra, and algorithmic optimization. He won the Bronze Medal at the Iranian National Olympiad in Physics in 2005 and was ranked third in Iran’s National Matriculation Exam for Graduate Studies in 2017.
Practical information
- Informed public
- Registration required
Organizer
- Professor Daniel Kuhn