TT-QI: Faster Value Iteration in Tensor Train Format for Stochastic Optimal Control

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Abstract: The problem of general non-linear stochastic optimal control with small Wiener noise is studied. The problem is approximated by a Markov Decision Process. Bellman Equation is solved using Value Iteration (VI) algorithm in the low rank Tensor Train format (TT-VI). In this paper a modification of the TT-VI algorithm called TT-Q-Iteration (TT-QI) is proposed by authors. In it, the nonlinear Bellman Optimality Operator is iteratively applied to the solution as a composition of internal Tensor Train algebraic operations and TT-CROSS algorithm. We show that it has lower asymptotic complexity per iteration than the method existing in the literature, provided that TT-ranks of transition probabilities are small. In test examples of an underpowered inverted pendulum and Dubins cars our method shows up to 3–10 times faster convergence in terms of wall clock time compared with the original method.

Original languageEnglish
Pages (from-to)836-846
Number of pages11
JournalComputational Mathematics and Mathematical Physics
Volume61
Issue number5
DOIs
Publication statusPublished - May 2021

Keywords

  • dynamic programming
  • low rank decomposition
  • Markov chain approximation
  • Markov decision process
  • MCA
  • MDP
  • optimal control

Fingerprint

Dive into the research topics of 'TT-QI: Faster Value Iteration in Tensor Train Format for Stochastic Optimal Control'. Together they form a unique fingerprint.

Cite this