Optimization Online


Robust Data-Driven Dynamic Programming

Grani A. Hanasusanto (g.hanasusanto11***at***imperial.ac.uk)
Daniel Kuhn (daniel.kuhn***at***epfl.ch)

Abstract: In stochastic optimal control the distribution of the exogenous noise is typically unknown and must be inferred from limited data before dynamic programming (DP)-based solution schemes can be applied. If the conditional expectations in the DP recursions are estimated via kernel regression, however, the historical sample paths enter the solution procedure directly as they determine the evaluation points of the cost-to-go functions. The resulting data-driven DP scheme is asymptotically consistent and admits an efficient computational solution when combined with parametric value function approximations. If training data is sparse, however, the estimated cost-to-go functions display a high variability and an optimistic bias, while the corresponding control policies perform poorly in out-of-sample tests. To mitigate these small sample effects, we propose a robust data-driven DP scheme, which replaces the expectations in the DP recursions with worst-case expectations over a set of distributions close to the best estimate. We show that the arising min-max problems in the DP recursions reduce to tractable conic programs. We also demonstrate that the proposed robust DP algorithm dominates various non-robust schemes in out-of-sample tests across several application domains.

Keywords: robust optimization, dynamic programming, stochastic programming, conic optimization

Category 1: Robust Optimization

Category 2: Other Topics (Dynamic Programming )

Category 3: Stochastic Programming


Download: [PDF]

Entry Submitted: 10/29/2013
Entry Accepted: 10/29/2013
Entry Last Modified: 11/16/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society