Robust Data-Driven Dynamic Programming
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 minmax 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.
Summary: This paper considers a stochastic optimal 
      control problem in discrete time with continuous state and action spaces, 
      where at any time t, the state of the underlying system has two components 
      (endogenous, exogenous). The endogenous state captures all 
      decision-dependent information, while the exogenous state captures the 
      external random disturbances. Stochastic optimal control problems have 
      many applications in various domains, yet solving these problems via 
      dynamic programming (DP) is challenging due to a number of reasons. In 
      particular, computing backward recursions is burdensome and the 
      distribution of the exogenous states is typically unknown and must be 
      inferred from historical observations, i.e., training data. The main 
      motivation behind this work is to handle the second issue, i.e., when 
      training data is very limited (as compared to the dimension of the 
      problem), the estimated cost-to-go functions display high variability and 
      bias, the resulting control policies perform poorly in out-of-sample 
      tests. To this end, the authors propose a robust data-driven DP approach, 
      where given a set of sample trajectories of the exogenous state, kernel 
      regression is used together with parametric value function approximations 
      to estimate the conditional expectations in DP ([3] shows that the 
      resulting approach is asymptotically consistent). However when the number 
      of sample trajectories is limited, this is still not of much use, due to 
      the noise in the estimates. Therefore, in this paper the authors further 
      propose to replace the expectations in the DP recursions with worst-case 
      expectations over a set of distributions close to the best estimate. The 
      resulting optimization problems are shown to be of conic form and via 
      numerical experiments, they show that new algorithm dominates two 
      non-robust approaches from the literature in two main applications from 
      stock index tracking and wind energy commitment. Quality: The 
      proposed data driven approach in this paper is appealing. But I am not 
      convinced that the existing algorithms from the literature are unable to 
      capture the same phenomena. In particular, the authors claim that the 
      robust value iteration methods from the robust Markov decision process 
      (MDP) are not fundamentally data-driven, as their primitives are 
      uncertainty sets for the transition kernels instead of historical 
      observations. Moreover, seemingly the main theoretical contribution of 
      this paper is to show that the resulting optimization problems are conic 
      optimization problems. While arriving at nice conic problems is valuable, 
      I have found no motivation for the Assumption 4.1., which underlies this 
      result. In fact, I find the overall theoretical contribution a bit 
      limited; see my comments in the Originality & Significance part. 
      I am not convinced that the Assumption 4.1 used is reasonable 
      in a real situation. It seems like this assumption is there to rather make 
      sure that everything fits to the setup of Lemma A.1. Moreover, there is no 
      new algorithmic contribution, as the resulting algorithm is pretty 
      straightforward, and was solved by utilizing the standard solvers SeDuMi 
      and CPLEX. By the way, there is no support offered on how \gamma 
      parameter, which controls the level of robustness desired, should be 
      chosen. Clearly selecting \gamma is very important, as setting it to zero 
      will get us back to the usual data-driven DP approach. Also the brief 
      discussion on this at the beginning of page 5 is not very useful in a real 
      scenario with an unknown distribution. Finally numerical 
      experiments only demonstrate that this approach is superior to the 
      non-robust standard data-driven DP and the least-squares policy iteration 
      algorithms. None of these methods addresses the robustness issue, a better 
      comparison would be against one of the robust approaches such as robust 
      value iteration method, or actually building uncertainty sets and solving 
      the larger problem described on page 5, lines 234-245, even if it meant 
      imposing additional assumptions on the structure of value functions. 
      Clarity: The paper is mostly written in a clear fashion, with 
      a reasonable logical structure, and a lot of examples. Originality 
      & Significance: This paper studies an important problem and to the 
      best of my knowledge, the approach is original in robust DP framework. 
      Yet, I believe there is little theoretical contribution in this work. 
      Proof of Lemma A.1, follows trivially from conic duality, note that 
      \triangle(q) =\{p\in\triangle: \exists u s.t. (2(p_i-q_i); u_i-p_i; 
      u_i+p_i )\in\mathcal{L}_3 \forall i=1,…, n\} where \mathcal{L}_3 is the 3 
      dimensional Lorentz cone, i.e., \mathcal{L}_3=\{x\in\R^3: x_3 \geq 
      \sqrt{x_1^2+ x_2^2}, so \triangle(q) is a conic representable set. 
      Moreover the cones involved are nonnegative orthant and also based on only 
      \ell_1 and \ell_2 norms, so strong conic duality applies here, directly 
      leading to the equivalent formulation given in A.1. I.,e., proof of Lemma 
      A.1, is trivial, in particular, there is no need to use Lagrangian 
      duality. The other proofs for the Theorem and Corollary were already only 
      two lines, following from either Lemma A.1, or previous work. As I stated 
      before, numerical evidence only proves the value of following a robust 
      approach, it does not necessarily prove the value of this particular 
      robust approach.