Approximate Dynamic Programming via Sum of Squares Programming

Abstract¶

We describe an approximate dynamic programming method for stochastic control problems on infinite state and input spaces. The optimal value function is approximated by a linear combination of basis functions with coefficients as decision variables. By relaxing the Bellman equation to an inequality, one obtains a linear program in the basis coefficients with an infinite set of constraints. We show that a recently introduced method, which obtains convex quadratic value function approximations, can be extended to higher order polynomial approximations via sum of squares programming techniques. An approximate value function can then be computed offline by solving a semidefinite program, without having to sample the infinite constraint. The policy is evaluated online by solving a polynomial optimization problem, which also turns out to be convex in some cases. We experimentally validate the method on an autonomous helicopter testbed using a 10-dimensional helicopter model.

Summary¶

Extends linear-programming approaches to approximate dynamic programming from quadratic value approximations to higher-order polynomial bases through sum-of-squares relaxations. The useful insight is that the infinite Bellman inequality can be enforced offline as an SDP, while the online policy step becomes a polynomial optimization problem, making the method plausible for continuous stochastic-control systems such as the helicopter testbed.

Links¶

Tags¶

Similar Papers¶