Tropical Dynamic Programming for discrete time stochastic optimal control

Benoît Tran

Ecole Polytechnique, France

Seminar Information

Seminar Series
Dynamic Systems & Controls

Seminar Date - Time
May 14, 2021, 3:00 pm
-
4:00

Seminar Location
Zoom Meeting ID: 858 822 1269


Abstract

In this presentation we present an iterative forward-backward algorithm which aims to solve discrete time stochastic optimal control problems. It is inspired by both max-plus numerical methods introduced by McEneaney and the Stochastic Dual Dynamic Programming (SDDP) algorithm of Pereira and Pinto.

At each time step, our algorithm builds two sequences of approximations of the (Bellman) value function respectively as a max-plus linear combinations of basic functions and as a min-plus linear combinations of other basic functions.

At each iteration, in a forward pass a sequence of states is generated according to a deterministic criterium first introduced by Philpott and al. in 2013 for the SDDP algorithm. In a backward pass, we improve the current approximations by adding one basic function to the max-plus linear combination and another one for the min-plus linear combination. The basic functions are choosen in such a way that the approximate value functions satisfy a Bellman equation locally and a Bellman inequality globally.

Assuming that the noise process has finite support and under Lipschitz type regularity conditions, we prove asymptotic convergence of the generated approximations toward the true value function at every limit point of the sequence of states generated in the forward passes.

We illustrate our algorithm and convergence result in synthetic examples of medium size.

Speaker Bio

Dr. Benoît Tran graduated from Paris-Saclay University (ex Université Paris-Sud) and obtained a Ph.D. from Ecole des Ponts ParisTech in 2020. He is currently a postdoc at the School of Applied Mathematics of FGV Brazil.