2010 Poster Sessions : Approximate Dynamic Programming for Linear Convex Stochastic Control

Student Name : Brendan O'Donoghue
Advisor : Stephen Boyd
Research Areas: Information Systems
We describe a method for finding a convex surrogate value function for a stochastic control problem with linear dynamics and convex stage cost. With such a surrogate value function, evaluating the approximate policy reduces to solving a convex optimization problem, and so is tractable; in particular it scales well with dimension. Following the standard linear programming formulation used in approximate dynamic programming with finite state space, we get a convex optimization problem involving an infinite set of linear inequalities. We use a cutting-plane (or column generation) technique to handle the infinite set of constraints, using the convex-concave procedure to identify state-action pairs that violate the constraint. The method yields a conditional bound on performance, in the following sense: If the infinite set of constraints were satisfied everywhere, our solution would be a guaranteed lower bound on the optimal solution. The approximate policies are shown to work well on several numerical examples, in terms of performance, and in some cases, when compared to performance bounds obtained by other methods.

Brendan O'Donoghue is a Ph.D. candidate in the Electrical Engineering department at Stanford. His research interests include optimization, dynamic systems and control and their applications. Brendan hails from Dublin, Ireland and graduated from Cambridge University in 2007.