# Quantum cohomology: is it still relevant?

Martin A. Guest

###### Abstract.

This article, intended for a general mathematical audience, is an informal
review of some of the many interesting links which have developed between
quantum cohomology and “classical” mathematics. It is based on a talk given at
the Autumn Meeting of the Mathematical Society of Japan in September 2021.

##  1\. Preamble

If you are a geometer, you probably know that quantum cohomology came into
prominence over 20 years ago, but you might not have followed developments
since then. If you are not a geometer, you might ask first “What is quantum
cohomology?”. To answer this, this article will begin with some brief
historical remarks.

Even before that, as preliminary orientation, I should say that quantum
cohomology belongs to the “structure building” kind of mathematics, not to the
“problem solving” kind. As far as I know, quantum cohomology was not motivated
by the desire to solve any particular problem. There are no famous open
problems in the subject. There are no easily-stated conjectures.

In fact there are relatively few general theorems (at least, in the
traditional 20th century sense of the word). More precisely, most theorems in
the subject apply to rather special situations, or even to special examples.
In this sense, quantum cohomology theory shares some of the features of
integrable systems theory (which will appear later in the article), in
particular an emphasis on examples. Both could be described as unfinished
theories — they are “work in progress”.

On the other hand, quantum cohomology has revealed many remarkable links
between previously-unrelated areas of mathematics. Many of these have led to
very concrete results. Thus, quantum cohomology has provided answers to
interesting problems — but, in many cases, the problems were recognised only
after the answers had been obtained. We shall describe some of these links in
order to demonstrate that quantum cohomology continues to have a strong impact
— that it is indeed still relevant.

Acknowledgements:  The author was partially supported by JSPS grant 18H03668.

##  2\. Some history

Here we sketch the general ideas (and some sociology) of quantum cohomology.
Technical material is postponed to the following sections.

The “quantum” in quantum cohomology comes from physics, of course. In quantum
theory it is necessary to consider integrals over “the space of all paths”,
but a rigorous mathematical formulation of such integrals (over infinite-
dimensional spaces) is a difficult problem.

Various approaches have been tried, with varying degrees of success. One
approach is to ignore the original problem, and focus on direct proofs of its
expected consequences. As a simple analogy, consider Cauchy’s Theorem and the
theory of residues in complex analysis. By integrating meromorphic functions
with infinitely many poles, one can obtain interesting identities, such as

$\pi^{2}/6=1+1/2^{2}+1/3^{2}+\cdots.$

A rigorous proof of Cauchy’s Theorem requires knowledge of topology and
function theory, but direct proofs of identities — such as this one — can
often be given without using complex analysis.

Another approach is to impose a (large) symmetry group and then hope for a
localization principle which reduces the problem to the analysis of (small)
fixed point sets.

From such considerations, physicists were led to consider the space

$\text{Hol}(\Sigma,M)=\\{f:\Sigma\to M\ |\ f\text{ is holomorphic}\\}$

of holomorphic maps from a Riemann surface $\Sigma$ to a Kähler manifold $M$.
The connected components of this space are generally noncompact, and may have
singularities, but at least they are finite-dimensional.

For example, holomorphic maps from the Riemann sphere $\Sigma=\mathbb{C}P^{1}$
to $n$-dimensional complex projective space $M=\mathbb{C}P^{n}$ are given by
$(n+1)$-tuples of polynomials

$[p_{0}(z);\dots;p_{n}(z)]$

and the connected components of $\text{Hol}(\Sigma,M)$ are indexed by
$d=0,1,2,\dots$ where $d=\text{max}\\{\deg p_{0},\dots,\deg p_{n}\\}$ (and
where $p_{0},\dots,p_{n}$ are assumed to have no common factor). It is
plausible that a theory of integration over such spaces might exist.

In fact, a mathematical foundation for such a theory of integration — much
more generally, for pseudo-holomorphic curves in symplectic manifolds — was
constructed by Mikhael Gromov in the 1980’s. This involved a deep study of the
(non)compactness of the space. Algebraic geometers provided another approach:
in the 1990’s Maxim Kontsevich introduced the concept of stable map, in order
to construct an “improved” version of $\text{Hol}(\Sigma,M)$. Both approaches
— moduli spaces of curves, in symplectic geometry and algebraic geometry — are
nontrivial and became major areas of research. Some references for this are
[42], [44].

###  2.1. Phase I

Quantum cohomology was born (into the mathematical world) in the 1990’s as
“intersection theory” on such moduli spaces. The value of this kind of
intersection theory had been demonstrated in the 1980’s by Simon Donaldson in
the context of Yang-Mills theory on four-dimensional manifolds. Physicists had
already carried out many ad hoc, but very promising, calculations. Thus, the
scene was set.

When the holomorphic maps are constant, quantum cohomology reduces to
intersection theory on the target manifold $M$ itself, i.e. ordinary
cohomology. Thus, quantum cohomology appeared to be a rather natural
generalization. On the other hand, quantum cohomology is very different from
ordinary cohomology in several respects. First, it is not (in any naive sense)
functorial. This means that quantum cohomology is difficult to compute
systematically. Second, it does not (directly) measure any topological
quantity, as the symplectic/complex structure plays an essential role.

In view of the lack of functoriality, early research on quantum cohomology
concentrated on “Gromov-Witten invariants”. These are the raw data of
intersection theory. They amount to giving a list of all possible
intersections. This is not as bad as it sounds, as it suffices to “choose a
basis” and take all possible intersections of the basis elements (a countable
set). Moreover, for physicists, this is a perfectly satisfactory method — it
is what they always do. There is also a mathematical antecedent: computing
Gromov-Witten invariants “one by one” is the analogue of Schubert calculus.
Schubert calculus could be described as “intersection theory on Grassmannian
manifolds, before the invention of cohomology”.

Incidentally, quantum Schubert calculus was one of the early applications of
quantum cohomology. It has interesting applications to topics far from
topology and physics, for example the “multiplicative eigenvalue problem” in
linear algebra [1]. (This is an example of discovering the answer first, then
recognising the problem later.)

###  2.2. Phase II

The story so far could be called Phase I of quantum cohomology theory. We
regard Phase II as the next period of development, when these rather unruly
Gromov-Witten invariants were organised more systematically. This involved
something quite new: a relation with differential equations. (The relation was
discovered by physicists, and in this sense pre-dates Phase I, but we are
ordering the “Phases” in logical order, not time order.)

The famous predictions of Mirror Symmetry — counting rational curves in
Calabi-Yau manifolds — came from solving differential equations. This was
carried out in a 1991 paper [5] by Philip Candelas, Xenia de la Ossa, Paul
Green, and Linda Parkes. But we shall take the starting point of Phase II as
the address by Alexander Givental at the 1994 ICM in Zürich [21].

Givental introduced the “quantum differential equations”, a linear system of
partial differential equations. The key property of the quantum differential
equations is that there exists a solution whose series expansion is a
generating function of the (generalized) Gromov-Witten invariants.

A simple example of this type of differential equation is

(2.1) $\tfrac{d^{2}u}{dx^{2}}+\tfrac{1}{x}\tfrac{du}{dx}-u=0.$

This example was studied in a 19th century article [48] by Stokes. It is
essentially the Bessel equation, but we mention it here because the Stokes
Phenomenon for this o.d.e. will enter the story later, in section 4.

A great advantage of this point of view is that the theory of linear
differential equations is more familiar than intersection theory on moduli
spaces, and differential equations are closer to the original physics. On the
other hand it is hard to imagine which differential equations are related to
quantum cohomology (clearly, not arbitrary ones), and it is hard to imagine
how to extract intersection-theoretic information. Nevertheless, Mirror
Symmetry gave us some nontrivial examples. Exploring this phenomenon was the
task of Phase II.

The dependent and independent variables of the quantum differential equations
were coordinates on cohomology vector spaces. This means cohomology with
complex coefficients; the coefficients of quantum differential equations were
holomorphic. To a topologist, doing calculus on cohomology spaces is unusual,
to say the least. Givental called this phenomenon “homological geometry”.

In this new world of homological geometry, the foundations of quantum
cohomology (Phase I), at least for “nice” target spaces $M$, could be taken
for granted. Relying on these hard-won foundations, armed only with
undergraduate knowledge of differential equations (and a little algebraic
topology), many more researchers could plunge into quantum cohomology theory.

This was a very fruitful exercise, because quantum differential equations
could be postulated — that is, guessed — even for target spaces $M$ where the
foundations were not yet secure. For example: target spaces with
singularities, target spaces with boundary, noncompact target spaces,
infinite-dimensional target spaces, and so on. Even if the differential
equations did not quite fit the (known) geometry, one could take the self-
righteous view that the differential equations were “correct” and the geometry
“wrong”. In turn, these efforts led to further development of the foundations.

It was a major achievement to give a mathematical treatment of the physicists’
original Mirror Symmetry predictions for (certain) Calabi-Yau manifolds. This
was done by Givental [22] and also by Bong Lian, Kefeng Liu, and Shing-Tung
Yau [41]. The work of Lian-Liu-Yau also led to intriguing connections with
arithmetic and modular forms.

Toric varieties (and their subvarieties) provided the most important class of
target spaces for these results. The lack of functoriality of quantum
cohomology made it necessary to focus on examples, and toric varieties came to
the rescue here.

Contrarily, and perhaps with “tongue in cheek”, it could be said that Mirror
Symmetry came to the rescue of toric varieties. Certainly the theory of toric
varieties became much more widely known, because of Mirror Symmetry. It was a
happy coincidence, and another unexpected benefit of quantum cohomology.

A good reference for Phase II of quantum cohomology theory is [9].

Before going on to Phase III, it should be mentioned that the symplectic
approach saw its own dramatic developments. The key words here were Floer
theory and Witten’s version of Morse theory. Floer theory for the loop space
$\Lambda M$ is closely related to the quantum cohomology of $M$, but Floer
theory developed in its own way. In particular the case of a target manifold
$M$ with Lagrangian submanifold $L$, and Gromov-Witten invariants based on
maps from $(D,\partial D)$ to $(M,L)$, became a major theme, developed by
Kenji Fukaya, Yong-Geun Oh, Hiroshi Ohta, and Kaoru Ono [19]. Here $D$ is a
two-dimensional disk with boundary $\partial D$.

###  2.3. Phase III

In this (admittedly very subjective) narrative, Phase III started with another
ICM talk, namely that of Boris Dubrovin in 1998 [14]. Here another
mathematical leap forward was made: from linear to nonlinear differential
equations.

As always in this story, physicists had anticipated such a leap, with their
WDVV (Witten-Dijkgraaf-Verlinde-Verlinde) equations and tt* (topological-
antitopological fusion) equations. These equations involve more general kinds
of quantum cohomology:

— WDVV describes “big” quantum cohomology

— tt* describes “quantum cohomology with a real structure”.

Both are complicated and difficult to appreciate, partly because of the
physicists’ preference for coordinates and tensor notation. Dubrovin
introduced a more intrinsic point of view for both, based on his concept of
Frobenius manifold [13].

In the context of quantum cohomology, the Frobenius manifold is the cohomology
vector space of the target manifold, endowed with further differential
geometric data. (After all, having started to do calculus on cohomology vector
spaces, why not introduce connections and curvature as well?)

Independently from quantum cohomology, this kind of structure had already been
investigated by Kyoji Saito in the 1980’s, in the context of singularity
theory. Thus Frobenius manifolds linked quantum cohomology with singularity
theory in a systematic way. To mathematicians, this was remarkable, but it was
entirely consistent with the physical principles of Mirror Symmetry.

The stage was set for another unexpected application of quantum cohomology:
the mere existence of a target space $M$ (or rather, its quantum cohomology)
implies the existence of a solution of a highly nontrivial nonlinear p.d.e.

For example, Dubrovin showed that the WDVV equation for $\mathbb{C}P^{2}$
reduces to a case of the Painlevé VI equation, so the “big” quantum cohomology
of $\mathbb{C}P^{2}$ corresponds to a certain solution of this equation. While
this was by no means the first time that Painlevé equations had appeared in
geometry and physics, it was a radically new example. Dubrovin also began the
study of integrable hierarchies generated by the quantum differential
equations, in analogy with the KdV hierarchy which is generated by the
Schrödinger equation. Such hierarchies represent a further generalization,
which could be called “very big” quantum cohomology.

###  2.4. Next steps

Many of the research areas started by, or influenced by, quantum cohomology
during the past 20 years have reached a certain level of maturity; they have
become part of mainstream mathematics. As often happens, some have become
highly specialized. As often happens, specialists in one area may not be able
to talk to specialists in another.

A glance at the lists of ICM talks shows that quantum cohomology was most
prominent in the period 1990-2002. That was 20 years ago. The question in the
title “Is it still relevant?” was suggested by this.

##  3\. Some terminology

We shall now give some simple examples related to Phase II and Phase III, to
prepare some terminology for the next section. We use only undergraduate-level
material in this section.

The simplest version of the quantum differential equation for
$M=\mathbb{C}P^{n}$ (and $\Sigma=\mathbb{C}P^{1}$) is

(3.1) $(\hbar\partial)^{n+1}y=qy$

where $y=y(q)$, $q$ is a complex variable, $\partial=q\frac{d}{dq}$, and
$\hbar$ is a parameter. The case $n=1$ is Stokes’ equation (2.1) above, if we
put $y=u$, $q=x^{2}$ (and $\hbar=2$).

This is related to the cohomology of $\mathbb{C}P^{n}$ in the following way.
The cohomology vector space $H^{\ast}(\mathbb{C}P^{n};\mathbb{C})$ has
$1,b,b^{2},\dots,b^{n}$ as a basis, where $b$ is an (additive) generator of
$H^{2}(\mathbb{C}P^{n};\mathbb{C})$. It is generated multiplicatively by $b$,
with the relation $b^{n+1}=0$. The quantum cohomology is equal to
$H^{\ast}(\mathbb{C}P^{n};\mathbb{C})$ as a vector space, but it has a
“deformed” product operation, leading to the relation $b^{n+1}=q$. (Ordinary
cohomology is recovered from quantum cohomology by setting $q=0$.) The
relation $b^{n+1}-q$ corresponds to the operator $(\hbar\partial)^{n+1}-q$ in
an obvious way.

Although $q=0$ is a singular point for the quantum differential equation, a
basis $y^{[0]},\dots,y^{[n]}$ of solutions (near $q=0$) may easily be found by
the Frobenius Method. Givental observed that, if we write

$J=(y^{[0]},\dots,y^{[n]})\ \longleftrightarrow\
y^{[0]}1+y^{[1]}b+\cdots+y^{[n]}b^{n},$

then this Frobenius solution is given by the attractive formula

$J(q)=q^{b/\hbar}\
\sum_{k=0}^{\infty}\frac{q^{k}}{[(b+\hbar)(b+2\hbar)\cdots(b+k\hbar)]}.$

At first this looks strange, as $b$ is a cohomology class, but it makes sense
as $b^{n+1}=0$ (in cohomology). With this understanding, it is easy to verify
that $(\hbar\partial)^{n+1}J=qJ,$ as asserted. There are good reasons to
identify

$q\ \longleftrightarrow\ qb\in H^{2}(\mathbb{C}P^{n};\mathbb{C}),$

so we have a map $J:H^{2}(\mathbb{C}P^{n};\mathbb{C})\to
H^{\ast}(\mathbb{C}P^{n};\mathbb{C})$ (strictly speaking, a multivalued map,
as $q^{b/\hbar}=e^{(b/\hbar)\log q}$ gives rise to logarithms). The solution
of the quantum differential equation is a cohomology-valued function on a
cohomology vector space!

For $M=\mathbb{C}P^{n}$ the relation between the quantum cohomology ring (i.e.
the cohomology vector space with the deformed product) and the quantum
differential equation is deceptively simple. In particular we do not really
need $\hbar$ there. A less obvious example is the case of a (smooth)
hypersurface $M$ of degree $3$ in $\mathbb{C}P^{4}$. There is a generator
$b\in H^{2}(M;\mathbb{C})\cong\mathbb{C}$ which satisfies $b^{4}=27qb^{2}$,
but the quantum differential equation is

$\left((\hbar\partial)^{4}-27q(\hbar\partial)^{2}-27\hbar
q(\hbar\partial)-6\hbar^{2}q\right)y=0.$

Replacing $\hbar\partial$ by $b$ in the differential operator gives
$b^{4}-27qb^{2}-27\hbar qb-6\hbar^{2}q$, and this gives $b^{4}-27qb^{2}$ after
putting $\hbar=0$. Here the inverse procedure is not immediately visible.
However, it turns out that there is such a procedure (see [24]), and here the
parameter $\hbar$ plays an essential role.

More generally, if $\dim H^{2}(M;\mathbb{C})=r$, then we have a system of
linear p.d.e. in variables $q_{1},\dots,q_{r}$. A new source of difficulty
appears: while an o.d.e. $Py=0$ of order $k$ always has a (local) solution
space of dimension $k$, there is no such dimension formula in terms of the
orders $k_{1},k_{2},\dots$ of the operators $P_{1},P_{2},\dots$ of a system.
In the situation of the quantum differential equations this dimension must be
equal to $\dim H^{\ast}(M;\mathbb{C})$; knowledge of this dimension is a
nontrivial property of quantum cohomology.

In fact, systems of linear p.d.e. with (nonzero, but) finite-dimensional local
solution space are quite rare. They correspond to flat connections in vector
bundles, or D-modules of finite rank. Examples of this correspondence (related
to geometry in general, and quantum cohomology in particular) are explored in
detail in [25].

Recall that a connection in a vector bundle on $(q_{1},\dots,q_{r})$-space may
be expressed locally as $\nabla=d+\omega$, where $\omega$ is a matrix-valued
$1$-form. It is said to be flat if $d\omega+\omega\wedge\omega=0$. In the case
of quantum cohomology (or a Frobenius manifold), the connection is called the
Givental connection (or Dubrovin connection).

In general, if the coefficients of a connection form are written in terms of
functions $f_{1}(q_{1},\dots,q_{r}),f_{2}(q_{1},\dots,q_{r}),\dots$ then the
flatness condition is a system of nonlinear p.d.e. for $f_{1},f_{2},\dots$ and
there is a close relation between this nonlinear p.d.e. and the original
linear p.d.e. The theory of “integrable p.d.e.” amounts to studying this kind
of relation. For example, the (nonlinear) KdV equation is related to the
(linear) Schrödinger equation in exactly this way.

Quantum cohomology (in the sense of most of this article, i.e. small quantum
cohomology of Fano manifolds) fits into this nonlinear p.d.e. framework, but
only in a trivial way. This is because the entries of the Dubrovin connection
form are just polynomials on $H^{2}(M;\mathbb{C})$. For small quantum
cohomology, the WDVV equations are trivial. However, big quantum cohomology
involves functions on $H^{\ast}(M;\mathbb{C})$, which are “known” only to the
extent that they are solutions of the WDVV equations. Later we shall encounter
another nonlinear system, the tt* equations, which is nontrivial even for
small quantum cohomology.

##  4\. Some recent developments

After all this preparation we can review some topics of current research
(restricted by the interests and knowledge of the author).

In the past 10 years, Fano manifolds (like $\mathbb{C}P^{n}$) have played a
greater role than Calabi-Yau manifolds, partly because Calabi-Yau manifolds
were the main focus in the early years, and partly because Fano manifolds
require new methods. While Calabi-Yau manifolds are closely related to
variations of Hodge structure (VHS), Fano manifolds require “semi-infinite” or
“nonabelian” Hodge structures ($\frac{\infty}{2}$-VHS). In terms of the
quantum differential equations, the new feature of Fano manifolds is that
irregular singularities appear.

The Hodge-theoretic aspects are a huge challenge, and major achievements have
been made by Claude Sabbah, and by Takuro Mochizuki, and their collaborators.

The irregular singularity aspects also suggest new directions of research.
This holds even in the simplest situation where the quantum differential
equation is an o.d.e. — although the classical theory goes back to the 19th
century, the relation with quantum cohomology is relatively unexplored. We
shall focus on this aspect for the rest of the article.

###  4.1. Stokes data of the quantum differential equation

The quantum differential equation (3.1) for $M=\mathbb{C}P^{n}$ has a regular
singularity at $q=0$ and an irregular singularity at $q=\infty$. Near $q=0$ we
have seen a nice series expansion, related to Gromov-Witten invariants. Near
$q=\infty$ we certainly have (local, possibly multivalued) solutions, but
“series expansions at infinity” always diverge. This is the Stokes Phenomenon:
such series represent only asymptotic expansions of solutions, and only on
specific Stokes sectors of the complex plane.

Remarkably (and non-intuitively) the asymptotic expansion — which depends only
on the equation — determines a unique solution on a given Stokes sector. Two
such solutions on overlapping sectors must differ by a constant matrix; this
is called a Stokes matrix. Analytically continuing a given solution one
circuit around $q=\infty$, we pass through a finite number of sectors, so we
see that the monodromy of that solution is (essentially) a product of Stokes
matrices.

In general, Stokes matrices are difficult to compute, and their entries are
usually highly transcendental, but in the case of the quantum differential
equations we might expect them to contain geometric/physical information. This
is indeed the case. For $M=\mathbb{C}P^{n}$ the Stokes data reduces to $n$
real numbers $s_{1},\dots,s_{n}$. These were computed by Dubrovin for $n=2$,
and by Davide Guzzetti for general $n$, and the answer is surprisingly simple:
$s_{k}=\binom{n+1}{k}$ (see [14]). Physicists had also arrived at this fact by
“counting solitons” in the supersymmetric sigma model of $\mathbb{C}P^{n}$.
Clearly something interesting was happening.

A further piece of information can be extracted from the differential
equation, by comparing the Frobenius solution near $q=0$ with (any of) the
Stokes solutions near $q=\infty$. In the differential equations literature,
the matrices which occur here are called connection matrices. For
$M=\mathbb{C}P^{n}$, Dubrovin computed these as well (see [14]).

A remarkable geometrical interpretation of this was found by Hiroshi Iritani
(see [36], [37]), which conjecturally also applies to more general Fano
manifolds $M$. It involves the “gamma class”

$\hat{\Gamma}_{M}=\prod_{i=1}^{n}\,\Gamma(1+x_{i})$

where $x_{1},\dots,x_{n}$ are the Chern roots of the complex tangent bundle
$TM$, and where $\Gamma(1+x_{i})$ is interpreted as the (Taylor expansion of)
the gamma function. This is very much in the spirit of Givental’s homological
geometry. Moreover, it strengthens a surprising link with “helices” of
holomorphic vector bundles on $M$ (see [49]). This has been developed further
in [20], [8] — another major new direction of research based on quantum
cohomology.

###  4.2. Isomonodromy

The Stokes data of the quantum differential equation can be approached most
directly by converting the quantum differential equation (a p.d.e. in
$q_{1},\dots,q_{r}$ with parameter $\hbar$) to an o.d.e. in $\hbar$ with
parameters $q_{1},\dots,q_{r}$. This “trick” is made possible by homogeneity.
An important property of the o.d.e. in $\hbar$ is that it is isomonodromic:
its monodromy data (Stokes and connection matrices) do not depend on
$q_{1},\dots,q_{r}$. (The reverse is also true, i.e. the monodromy data of the
p.d.e. in $q_{1},\dots,q_{r}$ is independent of $\hbar$, but this is obvious.)

For big quantum cohomology the isomonodromy property shows that the monodromy
data gives conserved quantities of solutions of the WDVV equations. This
provides another link with the theory of integrable systems. Indeed, Dubrovin
proposed this as a general approach to the study of Frobenius manifolds. There
is a well-developed method — the Riemann Hilbert Method — for studying the
relation between monodromy data of linear o.d.e. and solutions of nonlinear
p.d.e. (in the case of the Painlevé equations, a good reference is [16]).

As we have mentioned, the WDVV equation for $\mathbb{C}P^{2}$ reduces to a
case of the Painlevé VI equation, so this example fits well. Nevertheless, the
general WDVV equations are a “can of worms”. On the other hand, if we restrict
to small quantum cohomology, the WDVV equations become trivial. Fortunately,
between these two extremes, there is a situation of intermediate difficulty,
which appears when we consider Frobenius manifolds with “real structure”. The
nonlinear p.d.e. here is the (system of) tt* equations.

###  4.3. The topological-antitopological fusion equations.

The tt* equations were introduced by Sergio Cecotti and Cumrun Vafa in the
context of supersymmetric quantum field theory [6], [7]. Dubrovin formulated
these equations as an isomonodromic system [12], so the Riemann-Hilbert Method
of [16] can, in principle, be applied here.

Before stating the equations, which may look unmotivated, we can state the
underlying (mathematical) idea, which is simple. A Frobenius manifold is a
holomorphic object, but, if it has a real structure, then there is a “complex
conjugate” Frobenius manifold, which is an antiholomorphic object. Now, a
Frobenius manifold has, as part of its definition, a “holomorphic metric”.
Thus, the real structure produces a Hermitian metric. The tt* equations are
the equations for this metric — the tt* metric.

For Frobenius manifolds, e.g. big quantum cohomology, the tt* equations are
extremely complicated (they are worse than the WDVV equations, which they
contain). However, even after restricting to small quantum cohomology (where
the WDVV equations are trivial), some nonlinear equations remain. As Dubrovin
pointed out in [12], these nonlinear equations are very familiar to
differential geometers: they are the equations for pluriharmonic maps from
$(q_{1},\dots,q_{r})$-space to the Riemannian symmetric space
$\textrm{GL}_{n+1}\mathbb{C}/\textrm{O}_{n+1}$ (where $n+1$ is the dimension
of the Frobenius manifold). In fact, the pluriharmonic map represents the
variation of Hodge structure which was mentioned earlier.

When $r=1$, a pluriharmonic map is just a harmonic map. Here the theory of
harmonic maps from surfaces into symmetric spaces (which was comprehensively
developed by differential geometers in the 1980’s) provides an effective tool.
We shall focus on this situation.

The tt* equations are then

(4.1) $\tfrac{\partial}{\partial\bar{t}}\left(g\tfrac{\partial}{\partial
t}g^{-1}\right)-[C,gC^{\dagger}g^{-1}]=0,$

where $C$ is the (holomorphic) chiral matrix of the theory, $C^{\dagger}$ is
the conjugate-transpose of $C$, and $g^{-1}$ is the Hermitian matrix
representing the tt* metric. In the situation of quantum cohomology, $C$ is
the matrix of quantum multiplication by a generator $b\in H^{2}(M;\mathbb{C})$
(in the situation of singularity theory, $C$ is the analogous matrix of
multiplication in the Milnor ring).

Let us now specialize to the case $M=\mathbb{C}P^{n}$. Then, with respect to
suitable bases, we have

$C=\left(\begin{array}[]{c|c|c|c}&&&\ q\\\ \hline\cr 1&&&\\\
\hline\cr&\ddots&&\\\ \hline\cr&&\ 1&\end{array}\right),$

and the tt* metric can be written

$g=\text{diag}(e^{-2w_{0}},\dots,e^{-2w_{n}}),$

where $w_{0},\dots,w_{n}$ are real-valued functions of $q$, and where
$q=\alpha t^{\beta}$ for suitable constants $\alpha,\beta$. The homogeneity
property of quantum cohomology implies that $w_{i}$ depends only on $|q|$.
Then the tt* equations become

(4.2) $2(w_{i})_{{t\bar{t}}}=-e^{2(w_{i+1}-w_{i})}+e^{2(w_{i}-w_{i-1})},\
i=0,1,\dots,n$

together with the extra condition $w_{i}+w_{n-i}=0$. This is a version of the
periodic Toda equations. (We interpret $w_{n+1},w_{-1}$ here as $w_{0},w_{n}$
respectively.)

These “Toda type” tt* equations were, in fact, one of the main examples
considered by Cecotti and Vafa (formula (7.4) in [6]). We call them the
tt*-Toda equations.

Physically, a solution is a massive deformation of a conformal field theory,
and the existence of such a deformation says something about that theory.
Cecotti and Vafa made a series of conjectures about the solutions:

—there should exist (globally smooth) solutions $w$ on $\mathbb{C}^{\ast}$
which are radial, i.e. $w=w(|t|)$

—these solutions should be characterized by asymptotic data at $t=0$ (the
“ultra-violet point”; here the data is equivalent to the chiral charges,
essentially the holomorphic matrix function $C$)

—these solutions should equally be characterized by asymptotic data at
$t=\infty$, (the “infra-red point”; here the data is equivalent to the Stokes
parameters $s_{i}$, or soliton multiplicities, about which we shall say more
later on).

A global solution can then be interpreted as a “flow” between these two kinds
of data (the renormalization group flow).

The Toda equation is a very familiar p.d.e., which has been well studied in
the theory of integrable systems (as well as in differential geometry). In
addition to the methods of these areas, we have available the Riemann-Hilbert
Method from isomonodromy theory. Unfortunately none of these methods work
directly, because it is an important physical requirement that $w_{i}$ should
be defined for all $t\neq 0$ in the complex plane. Obtaining globally defined
solutions is the main obstacle.

Nevertheless, when Cecotti and Vafa introduced these equations, some
information was available for $n=1$, as this case had been studied in detail
by Barry McCoy, Craig Tracy, and Tai Tsun Wu in their pioneering work [43] on
the Ising Model. For $n=1$ equation (4.2) reduces to the sinh-Gordon equation

(4.3) $(w_{0})_{{t\bar{t}}}=\sinh 4w_{0}.$

Moreover, because of the radial condition, it is equivalent to a special case
of the Painlevé III equation. From their work it was known that radial
solutions $w_{0}$ on $\mathbb{C}^{\ast}$ are in one to one correspondence with
real numbers $\gamma_{0}\in[-1,1]$, where $2w_{0}(|t|)\sim\gamma_{0}\log|t|$
as $t\to 0$. From isomonodromy theory it was known that the Stokes parameter
$s_{1}$ is given by

(4.4) $s_{1}=2\sin\frac{\pi}{2}\gamma_{0}\ \in\ [-2,2]$

(as $n=1$ there is only one Stokes parameter).

At this point we should clarify what we mean by “the tt* equations for
$\mathbb{C}P^{n}$”. In fact (the quantum cohomology of) $\mathbb{C}P^{n}$
corresponds to just one solution of (4.2); the other solutions are also
expected to have geometric/physical significance, but this would not
necessarily be the quantum cohomology of anything.

In the case $n=1$, the solution corresponding to the quantum cohomology of
$\mathbb{C}P^{1}$ is given by $\gamma_{0}=1$ (or $\gamma_{0}=-1$). Although
quantum cohomology was new in physics at that time (and still unknown in
mathematics), Cecotti and Vafa were aware of this fact. On the basis of this,
and a small number of similar examples, and much physical reasoning, they
proposed that only the solutions with integer Stokes data represent
“realistic” physical models. Cecotti and Vafa used this hypothesis to propose
a classification of supersymmetric field theories [7]. From (4.4) we can
observe that, in the case $n=1$, the Stokes parameter $s_{1}$ is an integer
only for $\gamma_{0}=0,\pm\frac{1}{3},\pm 1$. The solution with
$\gamma_{0}=\pm\frac{1}{3}$ corresponds to the Ising Model, and the solution
with $\gamma_{0}=0$ corresponds to a trivial model (here $w_{0}\equiv 0$).
Thus, all solutions with $s_{1}\in\mathbb{Z}$ are meaningful.

The above predictions were investigated for the tt*-Toda equation (4.2) in the
series of papers [33], [34], [30], [31], [32], [45], [46]. A summary of the
main results can be found in section 3 of [26]. Amongst these are:

(i) solutions of (4.2) on $\mathbb{C}^{\ast}$ are in one to one correspondence
with $(n+1)$-tuples $(\gamma_{0},\dots,\gamma_{n})$ such that
$\gamma_{i+1}-\gamma_{i}\geq-2$ (and $\gamma_{i}+\gamma_{n-i}=0$); one has
$2w_{i}(|t|)\sim\gamma_{i}\log|t|$ as $t\to 0$

(ii) the corresponding Stokes parameters $s_{1},\dots,s_{n}$ are the $i$-th
symmetric functions of
$e^{(n-\gamma_{0})\frac{\pi{\scriptscriptstyle\sqrt{-1}}\,}{n+1}},e^{(n-2-\gamma_{1})\frac{\pi{\scriptscriptstyle\sqrt{-1}}\,}{n+1}},\dots,e^{(-n-\gamma_{n})\frac{\pi{\scriptscriptstyle\sqrt{-1}}\,}{n+1}}$
(thus $s_{i}=s_{n-i+1}$).

The relation between (i) and the chiral data, and between (ii) and the soliton
data, will be explained later. We just remark here that the asymptotics at
$t=\infty$ is related to the Stokes parameters $s_{i}$ by the formula

(4.5)
$-\tfrac{4}{n+1}\sum_{p=0}^{[\frac{1}{2}(n-1)]}w_{p}(|t|)\sin\tfrac{(2p+1)k\pi}{n+1}\sim
s_{k}\,F(L_{k}|t|),\quad t\to\infty$

where $F(x)=\tfrac{1}{2}(\pi x)^{-\frac{1}{2}}e^{-2x}$,
$L_{k}=2\sin\tfrac{k}{n+1}\pi$, and $[\tfrac{1}{2}(n+1)]$ means
$\tfrac{1}{2}(n+1)$ if $n$ is odd, $\tfrac{1}{2}n$ if $n$ is even.

The solution corresponding to the quantum cohomology of $\mathbb{C}P^{n}$ is
given by $(\gamma_{0},\dots,\gamma_{n})=(n,n-2,\dots,-n)$. Then all
exponentials in (ii) above are equal to $1$, so $s_{k}=\binom{n+1}{k}$, in
agreement with section 4.1.

The methods used to obtain the above results were conventional ones: harmonic
map theory (specifically, loop group factorizations), isomonodromy theory, and
p.d.e. theory. Rather less expected was the fact that all three methods played
essential roles — if used in isolation, none of the methods would have been
sufficient to give the complete picture.

Although the global solutions were the main physical motivation, we note that
these methods give information also on wider classes of solutions, in
particular solutions defined “near zero” (i.e. on regions of the form
$0<|t|<\epsilon$), and to solutions defined “near infinity” (i.e. on regions
of the form $R<|t|<\infty$). It is of mathematical interest to consider such
solutions from the Hamiltonian/symplectic point of view, as a possible
generalization of the rich theory which exists in the case $n=1$ for the
Painlevé III equation (and for any Painlevé equation). Some initial results in
this direction can be found in [47].

###  4.4. Lie-theoretic aspects

The Lie group $\textrm{SL}_{n+1}\mathbb{C}$ has been our silent companion so
far — the space $\mathbb{C}P^{n}$ is a homogeneous space of
$\textrm{SL}_{n+1}\mathbb{C}$, and equations (4.2) are (a real form of) the
$\mathfrak{s}\mathfrak{l}_{n+1}\mathbb{C}$-Toda equations. It is natural to
consider other Lie groups. Although this Lie-theoretic direction has not been
developed very extensively, it is already clear that there are benefits in
doing so, for physics as well as mathematics. Regarding quantum cohomology,
for example, it was shown in [38] that minuscule flag manifolds for $G$ play
the same role as $\mathbb{C}P^{n}$ for $\textrm{SL}_{n+1}\mathbb{C}$.

The most comprehensive results (at present) concern the Lie-theoretic
generalization of the Stokes data. In classical o.d.e. theory the Lie group
$\textrm{SL}_{n+1}\mathbb{C}$ is implicit, but the Stokes Phenomenon for other
Lie groups $G$ was investigated by Philip Boalch in his work [2] on hyper-
Kähler moduli spaces of meromorphic $G$-connections. We make use of this in
the next section.

##  5\. Some applications

We have not yet explained how the chiral matrix $C$ (and the Stokes data of
the quantum differential equations) are related to the tt* metric $g=e^{-2w}$.
Nor is this explained in the original work of Cecotti and Vafa, because their
Stokes data is for the isomonodromic version of the tt*-Toda equations, not
the quantum differential equations. In fact the two kinds of Stokes data
coincide, as far as the global solutions are concerned. This was proved in
[32], as a consequence of the differential geometric approach to the tt*-Toda
equations, and it is this approach which gives the most direct relation
between $C$ and $g$.

In the case of the tt*-Toda equations, the procedure is as follows. We
consider the (more general) holomorphic matrix function

$C=\left(\begin{array}[]{c|c|c|c}\vphantom{\dfrac{1}{2}}&&&q^{k_{0}}\\\
\hline\cr\vphantom{\dfrac{1}{2}}q^{k_{1}}&&&\\\
\hline\cr\vphantom{\dfrac{1}{2}}&\ \ddots&&\\\
\hline\cr\vphantom{\dfrac{1}{2}}&&q^{k_{n}}&\\!\end{array}\right)$

and then introduce a holomorphic $1$-form

$\omega=\tfrac{1}{\lambda}Cdq,\quad\lambda\in S^{1}.$

Regarding this as a $1$-form with values in the loop algebra
$\Lambda\mathfrak{s}\mathfrak{l}_{n+1}\mathbb{C}$, we can write (locally)
$\omega=L^{-1}dL$, where $L$ is an $\Lambda\textrm{SL}_{n+1}\mathbb{C}$-valued
holomorphic function (of $q$ and $\lambda$). For a suitable choice of $L$, and
a suitable loop group Iwasawa factorization $L=L_{\mathbb{R}}L_{+}$, it can be
shown that the $1$-form $(L_{\mathbb{R}})^{-1}dL_{\mathbb{R}}$ is exactly the
$1$-form which appears in the isomonodromic formulation of the tt*-Toda
equations. The details (given in [32]) are somewhat subtle, but the method
itself is well known to differential geometers — it is the DPW construction,
or generalized Weierstrass representation, of the corresponding harmonic map.
This method can be used to produce local solutions of the tt*-Toda equations
near $t=0$ (although significantly more work is needed to investigate when
these are actually global solutions).

The global solutions of tt*-Toda equations were described in section 4.3 in
terms of (i) asymptotic data, and (ii) Stokes data. The chiral data $C$ gives
a third description:

(iii) Fix $N>0$. Solutions of (4.2) on $\mathbb{C}^{\ast}$ are in one to one
correspondence with $(n+1)$-tuples $(k_{0},\dots,k_{n})$ such that
$k_{i}\geq-1$, $n+1+\sum_{i=0}^{n}k_{i}=N$ (and $k_{i}=k_{n-i+1}$ for
$i=1,\dots,n$).

The variable $q$ is related to the variable $t$ of the tt*-Toda equations by
$t=\tfrac{n+1}{N}q^{\frac{N}{n+1}}$. The $(k_{0},\dots,k_{n})$ are related to
the $(\gamma_{0},\dots,\gamma_{n})$ of (i) by
$\gamma_{i}-\gamma_{i-1}+1=\frac{n+1}{N}(k_{i}+1)$. Thus the chiral data
(represented by the $k_{i}$) is close to the asymptotic data at $t=0$
(represented by the $\gamma_{i}$), as stated earlier.

From now on it will be convenient to introduce the notation

$m_{i}=-\tfrac{1}{2}\gamma_{i}$

(thus we have $w_{i}\sim-m_{i}\log|t|$ as $t\to 0$). The relation between the
$k_{i}$ and the $m_{i}$ is given by

(5.1) $m_{i-1}-m_{i}+1=\tfrac{n+1}{N}(k_{i}+1).$

###  5.1. The Coxeter Plane

We begin with a Lie-theoretic description of the Stokes data, taken from [28].
We include it in this section as it could be described as an application of
the tt*-Toda equations to Lie theory. It will also be fundamental for the
applications to physics given in the next two subsections.

Let $\mathfrak{g}$ be a complex simple Lie algebra, with corresponding simply-
connected Lie group $G$. Let
$\alpha_{1},\dots,\alpha_{l}\in{\mathfrak{h}}^{\ast}$ be a choice of simple
roots of ${\mathfrak{g}}$ with respect to the Cartan subalgebra
${\mathfrak{h}}$. The Weyl group $W$ is the finite group generated by the
reflections $r_{\alpha}$ in all root planes $\ker\alpha$, $\alpha\in\Delta$.
The Coxeter element is the element $\gamma=r_{\alpha_{1}}\dots r_{\alpha_{l}}$
of $W$. Its order is called the Coxeter number of ${\mathfrak{g}}$, and we
denote it by $s$. We shall mainly be concerned with the case
${\mathfrak{g}}=\mathfrak{s}\mathfrak{l}_{n+1}\mathbb{C}$. Here $l=n$,
$s=n+1$, and $W$ is the permutation group on $n+1$ objects.

Figure 5.1. The Coxeter Plane for
${\mathfrak{g}}=\mathfrak{s}\mathfrak{l}_{5}\mathbb{C}$.

The Coxeter Plane is the result of projecting $\Delta$ orthogonally onto a
certain real plane in ${\mathfrak{h}}^{\ast}$. Several versions of this
definition can be found in the Appendix B of [28]. As an example, the Coxeter
Plane for ${\mathfrak{g}}=\mathfrak{s}\mathfrak{l}_{5}\mathbb{C}$ is shown in
Figure 5.1. Here there are $20$ roots $x_{i}-x_{j}$, $0\leq i\neq j\leq 4$,
denoted by $ij$ in Figure 5.1. The Coxeter element acts on the roots by the
permutation $(43210)$; there are $l=4$ orbits, each containing $s=5$ elements.

It was proved by Kostant (see [39]) that the Coxeter element $\gamma$ always
acts on the set of roots $\Delta$ with $l$ orbits, each containing $s$
elements. The Coxeter Plane provides a visualization of this fact. Remarkably,
it also provides a visualization of the Stokes data for the tt*-Toda
equations. Namely (see [28], [29]):

(a) The Coxeter Plane is a diagram of the Stokes sectors for the tt*-Toda
equations.

(b) The Stokes matrices can be computed Lie-theoretically in terms of a Lie
group element

$M^{(0)}=C(s_{1},\dots,s_{l})\in\textrm{SL}_{n+1}\mathbb{C}$

where $C$ is a “Steinberg cross-section” of the regular elements of
$\textrm{SL}_{n+1}\mathbb{C}$.

To be more precise, the rays in the Coxeter Plane are the mid-points of the
intersections of consecutive Stokes sectors, so for each ray we have a Stokes
matrix. To each ray in the Coxeter Plane is associated a set of roots, and
these roots determine the shape of the Stokes matrix. The Stokes matrices are
related to the above matrix $M^{(0)}$ by a simple explicit formula (which we
omit here).

The corresponding asymptotic data at $t=0$ also has a Lie-theoretic
interpretation. Recall that the solutions are parametrized by $(n+1)$-tuples
$(m_{0},\dots,m_{n})$ satisfying

(*) $m_{i-1}-m_{i}+1\geq 0$ (equivalently, $k_{i}\geq-1$)

(**) $m_{i}+m_{n-i}=0$ (equivalently, $k_{i}=k_{n-i+1}$)

where $w_{i}\sim-m_{i}\log|t|$ as $t\to 0$. The inequalities (*) define a
convex polytope. Let us write

$m=\text{diag}(m_{0},m_{1},\dots,m_{n}),\quad\rho=\text{diag}(\tfrac{n}{2},\tfrac{n}{2}-1,\dots,-\tfrac{n}{2}).$

With this notation the semisimple part of the matrix $M^{(0)}$ is

$\exp\,\tfrac{2\pi{\scriptscriptstyle\sqrt{-1}}\,}{n+1}(m+\rho),$

and the convex polytope given by the points $\tfrac{1}{n+1}(m+\rho)$ which
satisfy (*) is the Fundamental Weyl Alcove of the Lie algebra.

We have already remarked that the solution corresponding to the quantum
cohomology of $\mathbb{C}P^{n}$ is given by
$(\gamma_{0},\dots,\gamma_{n})=(n,n-2,\dots,-n)$; this corresponds to
$m=-\rho$, which is just the origin of the Fundamental Weyl Alcove.

###  5.2. Particles and polytopes

Using the material in the previous subsection, we can show how the Coxeter
Plane and the tt*-Toda equations give a mathematical foundation for certain
field theory models proposed by mathematical physicists in the 1990’s ([18],
[10], [11]).

These authors proposed (amongst other things) the correspondence

particle $\displaystyle\leftrightarrow\ \text{ orbit of root in Coxeter
Plane}$ mass of particle $\displaystyle\leftrightarrow\ \text{ distance of
root from origin}$

(if ${\mathfrak{g}}=\mathfrak{s}\mathfrak{l}_{n+1}\mathbb{C}$ the mass of the
particle corresponding to the orbit of the root $x_{i}-x_{j}$ is
$2\sin|i-j|\tfrac{\pi}{n+1}$).

They checked that these proposals (as well as the other things) were
consistent with the expected properties of a field theory.

A variant of this proposal was made (see [15], [40]) for “polytopic models”.
In this kind of model, a finite-dimensional representation $\theta$ of the Lie
algebra ${\mathfrak{g}}$ on a vector space $V$ is chosen, and the “polytope”
is the polytope in ${\mathfrak{h}}^{\ast}$ spanned by the weights of the
representation. The weight vectors (in $V$) are taken to be the vacua of the
theory. In this theory, “solitonic particles” tunnel between vacua: a soliton
connects two vacua $v_{i},v_{j}$ if and only if the corresponding weights
$\lambda_{i},\lambda_{j}$ differ by a single root, i.e.
$\lambda_{i}-\lambda_{j}\in\Delta$. The physical characteristics of this
particle are those of the root (in the model described above).

The discussion so far is purely algebraic (there is no differential equation).
However, the polytopic models include certain Landau-Ginzburg models. The
quantum cohomology of $\mathbb{C}P^{n}$ is of this type, with:
$\theta=\lambda_{n+1}$ (standard representation of
$\mathfrak{s}\mathfrak{l}_{n+1}\mathbb{C}$). Thus one can expect a role for
solitons in the quantum cohomology of $\mathbb{C}P^{n}$.

For example, in Figure 5.2, the solitons are illustrated for
$\mathfrak{s}\mathfrak{l}_{4}\mathbb{C}$ with $\theta=\lambda_{4}$. The first
part shows the projections of the weights $x_{0},x_{1},x_{2},x_{3}$, denoted
by $0,1,2,3$ in Figure 5.2. The second part shows (as heavy lines) the four
solitons of type $x_{0}-x_{1}$ (and of mass $2\sin\frac{\pi}{4}=\sqrt{2}$).
The third part shows the two solitons of type $x_{0}-x_{2}$ (and of mass
$2\sin\frac{\pi}{2}=2$). In this example, any two vacua are connected by a
soliton.

Figure 5.2. Solitons for
${\mathfrak{g}}=\mathfrak{s}\mathfrak{l}_{4}\mathbb{C}$, $\theta=\lambda_{4}$.

Other examples can be found in [29] and in the original articles.

The “soliton particle interpretation” fits well with the tt*-Toda equations.
From a physical point of view this was already implicit in the articles of
Cecotti and Vafa. From a mathematical point of view it arises from the formula
(4.5) on the asymptotics at $t=\infty$. Namely, the linear combination on the
left hand side of

$-\tfrac{4}{n+1}\sum_{p=0}^{[\frac{1}{2}(n-1)]}w_{p}\sin\tfrac{(2p+1)k\pi}{n+1}\sim
s_{k}\,F(L_{k}|t|)$

corresponds to a certain basis vector of ${\mathfrak{h}}$ (or
${\mathfrak{h}}^{\ast}$) associated to an orbit of the Coxeter group (see
section 4.3 of [26]). Thus we can say that the Stokes parameter $s_{k}$ on the
right hand side is naturally associated to the $k$-th orbit, or particle.
Physicists call $s_{k}$ the soliton multiplicity.

For any $n$, the model with $\theta=\lambda_{n+1}$ is related to the quantum
cohomology of $\mathbb{C}P^{n}$. If we choose $\theta=\wedge^{k}\lambda_{n+1}$
we obtain a different model, related to the quantum cohomology of the
Grassmannian $Gr_{k}(\mathbb{C}^{n+1})$. Cecotti and Vafa used this to give a
physical argument for an “equivalence”

$\wedge^{k}QH^{\ast}(\mathbb{C}P^{n})\approx
QH^{\ast}(Gr_{k}(\mathbb{C}^{n+1}))$

(more precisely, an equivalence of underlying field theories). This tt*
argument was explained in some detail in [3].

Later, mathematicians gave proofs of mathematically precise, but physically
somewhat artificial, interpretations of this isomorphism (which they regarded
as a special case of the quantum Satake isomorphism, or abelian-nonabelian
correspondence (cf. [23]).

Our Lie-theoretic description of the solutions of the tt*-Toda equations
supports the original physics argument, because

solution with $m=-\rho$ $\displaystyle\overset{\ \
\theta=\lambda_{n+1}}{\longleftrightarrow}\ \ QH^{\ast}(\mathbb{C}P^{n})$
solution with $m=-\rho$ $\displaystyle\overset{\ \ \
\theta=\wedge^{k}\lambda_{n+1}}{\longleftrightarrow}QH^{\ast}(Gr_{k}(\mathbb{C}^{n+1}))$

i.e. both $QH^{\ast}(\mathbb{C}P^{n})$ and
$QH^{\ast}(Gr_{k}(\mathbb{C}^{n+1}))$ arise from the same solution of the
tt*-Toda equations.

The Stokes matrices of the respective quantum differential equations are
different (they can be read off from $M^{(0)}$ and $\wedge^{k}M^{(0)}$
respectively), but the Stokes parameters $s_{k}=\binom{n+1}{k}$ are the same
for $QH^{\ast}(\mathbb{C}P^{n})$ and $QH^{\ast}(Gr_{k}(\mathbb{C}^{n+1}))$.
For further explanation we refer to [26].

###  5.3. Minimal models

Recall that solutions of the tt*-Toda equations can be interpreted as harmonic
maps; in fact they are (rather special) examples of harmonic bundles. From
this point of view the chiral data

$\eta=\left(\begin{array}[]{c|c|c|c}\vphantom{\dfrac{1}{2}}&&&z^{k_{0}}\\\
\hline\cr\vphantom{\dfrac{1}{2}}z^{k_{1}}&&&\\\
\hline\cr\vphantom{\dfrac{1}{2}}&\ \ddots&&\\\
\hline\cr\vphantom{\dfrac{1}{2}}&&z^{k_{n}}&\\!\end{array}\right)$

(more precisely the $1$-form $\eta dz$) can be interpreted as a Higgs field.
Here we have $k_{i}\geq-1$, $n+1+\sum_{i=0}^{n}k_{i}=N$, $k_{i}=k_{n-i+1}$ for
$i=1,\dots,n$. As stated at the beginning of section 5, for fixed $N>0$, such
Higgs fields parametrize solutions of the tt*-Toda equations.

In this section, following Fredrickson and Neitzke [17], we consider $\eta dz$
with $k_{i}\in\mathbb{Z}_{\geq 0}$, $n+1+\sum_{i=0}^{n}k_{i}=N$, such that $N$
is coprime to $k=\sum_{i=0}^{n}k_{i}$. (We write $z$ instead of $q$, and
$\eta$ instead of $C$, in recognition of the fact that we are moving away from
the tt* interpretation. However, it should be noted that those Higgs fields
with the additional property $k_{i}=k_{n-i+1}$ for $i=1,\dots,n$ do form a
dense subset of the set of all solutions of the tt*-Toda equations.)

Given (coprime) $k$ and $N$, there are only a finite number of Higgs fields of
the above type. The authors of [17] describe these as those points of a
certain moduli space of Higgs field which are fixed under a
$\mathbb{C}^{\ast}$-action. This moduli space is associated to a certain four-
dimensional supersymmetric quantum field theory, namely Argyres-Douglas theory
of type $(A_{n},A_{k-1})$.

They observe a “curious 1-1 correspondence” between these fixed points and
certain representations of the vertex algebra $W_{n+1}$. The representations
constitute the $(n+1,N)$ $W_{n+1}$ minimal model, a type of conformal field
theory. The vertex algebra $W_{n+1}$ is known (or conjectured) to appear also
in Argyres-Douglas theory of type $(A_{n},A_{k-1})$, Fredrickson and Neitzke
propose this as a basis for relating the two models.

As an application of the Lie-theoretic Stokes formula

$M^{(0)}=C(s_{1},\dots,s_{l})\in\textrm{SL}_{n+1}\mathbb{C}$

we can show (see [35]) that there is a rather direct mathematical path from
$\eta dz$ to the representation.

This depends on the theory of positive energy representations of the affine
Kac-Moody algebra $\widehat{\mathfrak{s}\mathfrak{l}}_{n+1}\mathbb{C}$.
Irreducible representations of this type are parametrized by pairs
$(\Lambda,l)$, where $l\in\mathbb{Z}_{\geq 0}$ and $\Lambda$ is a dominant
weight of $\mathfrak{s}\mathfrak{l}_{n+1}\mathbb{C}$ of level $l$.

Let us review this notation briefly (cf. Remark 4.1 of [35]). First we denote
the simple roots $x_{0}-x_{1},\dots,x_{n-1}-x_{n}$ by
$\alpha_{1},\dots,\alpha_{n}$, then define the basic weights
$\epsilon_{1},\dots,\epsilon_{n}$ by the condition
$\langle\alpha_{i},\epsilon_{j}\rangle=\delta_{i,j}$. The dominants weights
are then given by $\Lambda=\sum_{i=1}^{k}k_{i}\epsilon_{i}$ where
$k_{i}\in\mathbb{Z}_{\geq 0}$, and $\Lambda$ is said to have level $l$ if
$\sum_{i=1}^{k}k_{i}\leq l$.

Let $P_{+}$ denote the set of dominants weights, and $P_{l}$ those of level
$l$. It is well known that

$P_{l}+\rho=P_{+}\cap(l+n+1)\mathring{A}$

where $\mathring{A}$ denotes the interior of the Fundamental Weyl Alcove $A$.

The assumption $k_{i}\in\mathbb{Z}_{\geq 0}$ implies (see [28]) (a) that
$M^{(0)}$ is semisimple, so it is conjugate to the diagonal matrix

$\exp\,{\tfrac{2\pi{\scriptscriptstyle\sqrt{-1}}\,}{n+1}(m+\rho)},$

and also (b) that $\frac{1}{n+1}(m+\rho)$ is in $\mathring{A}$.

Now, it is easy to verify that our formula (5.1) is equivalent to the formula

(5.2) $\tfrac{N}{n+1}(m+\rho)=\rho+\sum_{i=1}^{n}k_{i}\epsilon_{i}.$

We have $\sum_{i=1}^{n}k_{i}\leq k=\sum_{i=0}^{n}k_{i}$. Thus, from the Stokes
data $M^{(0)}$ we obtain the positive energy representation corresponding to
the pair $(\sum_{i=1}^{n}k_{i}\epsilon_{i},k)$.

It is well known (see [4], [35]) that $W_{n+1}$ intertwines with any such
representation, and that the effective central charge is then given by the
formula

$\textstyle
c_{\text{eff}}=n-12\tfrac{n+1}{N}\,|\sum_{i=1}^{n}k_{i}\epsilon_{i}-\tfrac{k}{n+1}\rho|^{2}.$

By (5.2) we have
$\sum_{i=1}^{n}k_{i}\epsilon_{i}-\tfrac{k}{n+1}\rho=\tfrac{N}{n+1}m$, so

$c_{\text{eff}}=n-12\tfrac{N}{n+1}\,|m|^{2}.$

This is the formula used by Fredrickson and Neitzke to relate representations
of $W_{n+1}$ and Higgs fields.

## References

  * [1] S. Agnihotri and C. Woodward, _Eigenvalues of products of unitary matrices and quantum Schubert calculus_ , Math. Res. Lett. 5 (1998), 817–836.
  * [2] P. Boalch, _G-Bundles, isomonodromy, and quantum Weyl groups_ , Int. Math. Res. Notices 2002 (2002), 1129–1166.
  * [3] M. Bourdeau, _Grassmannian $\sigma$-models and topological–anti-topological fusion_, Nuclear Phys. B 439 (1995), 421–440.
  * [4] P. Bouwknegt and K. Schoutens, _W-symmetry in conformal field theory_ , Physics Reports 223 (1993), 183–276.
  * [5] P. Candelas, X. C. de la Ossa, P. S. Green, and L. Parkes, _A pair of Calabi-Yau manifolds as an exactly soluble superconformal theory_ , Nuclear Phys. B 359 (1991), 21–74.
  * [6] S. Cecotti and C. Vafa, _Topological—anti-topological fusion_ , Nuclear Phys. B 367 (1991), 359–461.
  * [7] S. Cecotti and C. Vafa, _On classification of $N=2$ supersymmetric theories_, Comm. Math. Phys. 158 (1993), 569–644.
  * [8] G. Cotti, B. Dubrovin, and D. Guzzetti, _Helix structures in quantum cohomology of Fano varieties_ , arXiv:1811.09235
  * [9] D. A. Cox and S. Katz, _Mirror Symmetry and Algebraic Geometry_ , Math. Surveys and Monographs 68, Amer. Math. Soc., 1999\.
  * [10] P. Dorey, _Root systems and purely elastic S-matrices_ , Nuclear Phys. B 358 (1991), 654–676.
  * [11] P. E. Dorey, _Root systems and purely elastic S-matrices (II)_ , Nuclear Phys. B 374 (1992), 741–761.
  * [12] B. Dubrovin, _Geometry and integrability of topological-antitopological fusion_ , Comm. Math. Phys. 152 (1993), 539–564.
  * [13] B. Dubrovin, _Geometry of 2D topological field theories_ , Integrable Systems and Quantum Groups, eds. M. Francaviglia et al., Lecture Notes in Math. 1620, Springer, 1996, pp. 120–348.
  * [14] B. Dubrovin, _Geometry and analytic theory of Frobenius manifolds_ , Proc. Int. Congress of Math. II, Berlin 1998, Doc. Math., Extra Volume ICM 1998 II, pp. 315–326.
  * [15] P. Fendley, W. Lerche, S. D. Mathur, and N. P. Warner, _$N=2$ supersymmetric integrable models from affine Toda theories_, Nuclear Phys. B 348 (1991), 66–88.
  * [16] A. S. Fokas, A. R. Its, A. A. Kapaev, and V. Y. Novokshenov, _Painlevé Transcendents: The Riemann-Hilbert Approach_ , Math. Surveys and Monographs 128, Amer. Math. Soc., 2006\.
  * [17] L. Fredrickson and A. Neitzke, _Moduli of wild Higgs bundles on $\mathbb{C}P^{1}$ with $\mathbb{C}^{\times}$ actions_, Math. Proc. Camb. Phil. Soc. 171 (2021), 623–656.
  * [18] M. D. Freeman, _On the mass spectrum of affine Toda field theory_ , Phys. Lett. B 261 (1991), 57–61.
  * [19] K. Fukaya, Y.-G. Oh, H. Ohta, and K. Ono, _Lagrangian intersection Floer theory: anomaly and obstruction_ , AMS/IP Studies in Advanced Mathematics 46.1 (Part I) and 46.2 (Part II) Amer. Math. Soc., 2009\.
  * [20] S. Galkin, V. Golyshev, and H. Iritani, _Gamma classes and quantum cohomology of Fano manifolds: gamma conjectures_ , Duke Math. J. 165 (1993), 2005–2077.
  * [21] A. B. Givental, _Homological geometry and mirror symmetry_ , Proc. Int. Congress of Math. I, Zürich 1994, ed. S. D. Chatterji, Birkhäuser, 1995, pp. 472–480.
  * [22] A. B. Givental, _Equivariant Gromov-Witten invariants_ , Int. Math. Res. Notices 1996 (1996), 1–63.
  * [23] V. Golyshev and L. Manivel, _Quantum cohomology and the Satake isomorphism_ , arXiv:1106.3120
  * [24] M. A. Guest, _Quantum cohomology via D-modules_ , Topology 44 (2005) 263–281.
  * [25] M. A. Guest, _From Quantum Cohomology to Integrable Systems_ , Oxford Univ. Press, 2008\.
  * [26] M. A. Guest, _Topological-antitopological fusion and the quantum cohomology of Grassmannians_ , Jpn. J. Math. 16 (2021), 155–183.
  * [27] M. A. Guest and N.-K. Ho, _A Lie-theoretic description of the solution space of the tt*-Toda equations_ , Math. Phys. Anal. Geom. 20 (2017), article 24.
  * [28] M. A. Guest and N.-K. Ho, _Kostant, Steinberg, and the Stokes matrices of the tt*-Toda equations_ , Sel. Math. New Ser. 25 (2019), article 50.
  * [29] M. A. Guest and N.-K. Ho, _Polytopes, supersymmetry, and integrable systems_ , Josai Math. Monographs 13 (2021), 109–136.
  * [30] M. A. Guest, A. R. Its, and C.-S. Lin, _Isomonodromy aspects of the tt* equations of Cecotti and Vafa I. Stokes data_ , Int. Math. Res. Notices 2015 (2015), 11745–11784.
  * [31] M. A. Guest, A. R. Its, and C.-S. Lin, _Isomonodromy aspects of the tt* equations of Cecotti and Vafa II. Riemann-Hilbert problem_ , Comm. Math. Phys. 336 (2015), 337–380.
  * [32] M. A. Guest, A. R. Its and C. S. Lin, _Isomonodromy aspects of the tt* equations of Cecotti and Vafa III. Iwasawa factorization and asymptotics_ , Comm. Math. Phys. 374 (2020), 923–973.
  * [33] M. A. Guest and C.-S. Lin, _Some tt* structures and their integral Stokes data_ , Comm. Number Theory Phys. 6 (2012), 785–803.
  * [34] M. A. Guest and C.-S. Lin, _Nonlinear PDE aspects of the tt* equations of Cecotti and Vafa_ , J. reine angew. Math. 689 (2014), 1–32.
  * [35] M. A. Guest and T. Otofuji, _Positive energy representations of affine algebras and Stokes matrices of the affine Toda equations_ , Adv. Theor. Math. Phys., to appear.
  * [36] H. Iritani, _An integral structure in quantum cohomology and mirror symmetry for toric orbifolds_ , Adv. Math. 222 (2009), 1016–1079.
  * [37] H. Iritani, _On the gamma structure of quantum cohomology (in Japanese)_ , Sugaku 68 (2016), 337–360.
  * [38] Y. Kaneko, _Solutions of the tt*-Toda equations and quantum cohomology of minuscule flag manifolds_ , Nagoya Math. J., to appear.
  * [39] B. Kostant, _The principal three-dimensional subgroup and the Betti numbers of a complex simple Lie group_ , Am. J. Math. 81 (1959), 973–1032.
  * [40] W. Lerche and N. P. Warner, _Polytopes and solitons in integrable $N=2$ supersymmetric Landau-Ginzburg theories_, Nuclear Phys. B 358 (1991), 571–599.
  * [41] B. H. Lian, K. Liu, and S.-T. Yau, _Mirror principle I_ , Asian J. Math. 1 (1997), 729–763.
  * [42] Y. Manin, _Frobenius Manifolds, Quantum Cohomology and Moduli Spaces_ , Colloquium Publications 47, Amer. Math. Soc., 1999\.
  * [43] B. M. McCoy, C. A. Tracy, and T. T. Wu, _Painlevé functions of the third kind_ , J. Math. Phys. 18 (1977), 1058–1092.
  * [44] D. McDuff and D. Salamon, _J-holomorphic Curves and Symplectic Topology_ , Colloquium Publications 52, Amer. Math. Soc., 2004\.
  * [45] T. Mochizuki, _Harmonic bundles and Toda lattices with opposite sign_ , arXiv:1301.1718
  * [46] T. Mochizuki, _Harmonic bundles and Toda lattices with opposite sign II_ , Comm. Math. Phys. 328 (2014), 1159–1198.
  * [47] R. Odoi, _Symplectic aspects of the tt*-Toda equations_ , J. Phys. A: Math. Theor. 55 (2022), article 165201.
  * [48] G. G. Stokes, _On the discontinuity of arbitrary constants which appear in divergent developments_ , Trans. Camb. Phil. Soc. 10 (1864), 106–128.
  * [49] E. Zaslow, _Solitons and helices: the search for a Math-Physics bridge_ , Comm. Math. Phys. 175 (1996), 337–375.

Department of Mathematics
Faculty of Science and Engineering
Waseda University
3-4-1 Okubo, Shinjuku, Tokyo 169-8555
JAPAN


# Monte Carlo Grid Dynamic Programming: Almost Sure Convergence and
Probability Constraints

Mohammad S. Ramadan<EMAIL_ADDRESS>Mohamed Shouman
<EMAIL_ADDRESS>Ahmed Atallah<EMAIL_ADDRESS>Department
of Mechanical & Aerospace Engineering, University of California, San Diego, La
Jolla CA 92093-0411, USA.  Research center of the smart vehicle, Toyota
Technological Institute (TTI), Nagoya, Aichi, Japan.

###### Abstract

Dynamic Programming is bedeviled by the ”curse of dimensionality”, which is
intensified by the expectations over the process noise. In this paper we
present a Monte Carlo-based sampling of the state-space and an interpolation
procedure of the resulting value function dependent on the process noise
density in a ”self-approximating” fashion. Proof of almost sure convergence is
presented. The proposed sampling and interpolation algorithm alleviates the
burden of gridding of Dynamic Programming and avoids the construction of a
piecewise constant value function over the grid. The sampling nature, and the
interpolation procedure of this approach make it adequate to deal with
probabilistic constraints.

###### keywords:

State Estimation, Stochastic Model Predictive Control, Chance Constraints,
Partially Observed Markov Decision Process.

,

and

##  1 Introduction

The Dynamic Programming (DP) algorithm [1] is haunted by the curse of
dimensionality, which is intensified by the expectations over the process
noise [5, ch 25]. Thus, DP is rendered infeasible in many practical problems
of interest.

This hedge, into the application of optimal control, had been breached by
different methods. For instance, the DP algorithm can be approximated under
some stochastic approximation procedures [15], to form what is called
Approximate DP [14], or more famously, Reinforcement Learning [10]. Another
very successful approach, that is conceptually simple and can handle complex
systems and constraints, is model predictive control [7]. Under this approach,
a finite-horizon optimal control problem is solved in open-loop, online, i.e.
at each time-step, and the first control input in the optimal control sequence
is applied. Thus, dodging the need to solve optimal control at many points in
the state-space and the need for a function approximation procedure of a value
function or an explicit feedback policy over the state-space [9].

Nevertheless, DP is an important algorithm that is still in use in many
problems, such as Hamilton-Jacobi Reachability analysis [6]. Moreover, a value
function as a measure of goodness and/or safety a state is, in the state-
space, can be of a significant importance to a decision maker. Several
efficient toolboxes have been developed as optimized DP solvers [4], such
toolboxes can work efficiently up to state-dimension 6, as typically reported.

In this paper, we present a Monte-Carlo-based sampling algorithm of the state-
space, with an interpolation procedure of the resulting value function and the
corresponding feedback law, that is dependent on the process noise density. In
[12], a similar randomization and interpolation procedure is presented with
its proof of convergence and upper bounds on its computational complexity.
Different from [12]: we allow sampling of distributions other than uniform,
which is essential, especially when certain regions in the state-space require
more attention therefore more samples; importance sampling arguments and the
Borel-Cantelli Lemma [11] are used in establishing our proofs; the formulation
of the algorithm easily allows the inclusion of probability constraints.

The paper follows a path analogous to that of Bertsekas [2], except, rather
than refining the grid to yield a better estimate, we use the Borel-Cantelli
lemma to reach similar convergence results, but in the “almost sure” sense.
Moreover, the convergence results in this paper are based on estimating a
value function represented by a self-approximating interpolation scheme, as
described by [12], not a piece-wise constant over the grid as in [2]. We also
present a nonlinear $2^{nd}$ order system with probability constraints,
showing how the presented algorithms are naturally suitable for dealing with
such problems.

##  2 Finite-Horizon

Consider the finite-horizon optimal control problem of minimizing the cost
functional

$\displaystyle J(x_{0},u_{0:T-1})$
$\displaystyle=\textbf{E}_{x_{1:T}}\\{\sum_{k=1}^{T-1}\ell_{k}(x_{k},u_{k})+\ell_{N}(x_{T})\mid
x_{0},u_{0:T-1}\\}$

over the space of finite input sequences
$u_{0:T-1}=\\{u_{i},\,i\in\mathbb{I}_{T-1}\\}$, where
$\mathbb{I}_{T}=\\{0,1,\ldots,T\\}$, subject to: the discrete-time state
dynamics

$\displaystyle
x_{k+1}=f(x_{k},u_{k})+w_{k},\,x_{0}\in\mathbb{X}_{0}\subset\mathbb{R}^{r_{x}}\text{is
given,}$ (1)

where $\\{w_{k}\\}$ is independent and identically distributed according to
$\mathcal{W}(.)$; and the input constraints $u_{k}\in
U_{k}(x_{k})\subset\mathbb{R}^{r_{u}}$ for all $k\in\mathbb{I}_{N}$, where
$U_{k}(x_{k})=\\{u_{k}\in\mathbb{U}_{k}\mid\text{Pr}(x_{k+1}\in\mathbb{X}_{k+1}\mid
x_{k},u_{k})\geq 1-\epsilon\\}$, following a probability constraint [13, 16],
is non-empty for all $x_{k}\in\mathbb{X}_{k}\subset\mathbb{R}^{r_{x}}$,
$\mathbb{U}_{k}\subset\mathbb{R}^{r_{u}}$ is finite, and $\epsilon\in(0,1)$:
the probability of exceeding the state constraints, is predetermined by the
user.

The Dynamic Programming algorithm corresponding to this optimal control
problem is

$\displaystyle V_{N}(x_{N})$
$\displaystyle=\ell_{N}(x_{N}),\,x_{N}\in\mathbb{X}_{N}\subset\mathbb{R}^{r_{x}},$
(2) $\displaystyle V_{k}(x_{k})$ $\displaystyle=\min_{u_{k}\in
U_{k}}\\{\ell(x_{k},u_{k})+$ $\displaystyle\hskip
56.9055pt\textbf{E}_{x_{k+1}}[V_{k+1}(x_{k+1})\mid x_{k},u_{k}]\\},$ (3)
$\displaystyle x_{k}\in\mathbb{X}_{k},\,u_{k}\in
U_{k}(x_{k}),\,k\in\mathbb{I}_{T},$ (4)

######  Assumption 1.

The Euclidean sets $\\{\mathbb{X}_{k},\,k\in\mathbb{I}_{T}\\}$ are compact.

######  Assumption 2.

The functions $f(x_{k},u_{k})$ and $\ell(x_{k},u_{k})$ are Lipschitz on
$\mathbb{X}_{k}$ for all $k\in\mathbb{I}_{T}$ and $u_{k}\in U_{k}(x_{k})$.

######  Assumption 3.

$\ell(x_{k},u_{k})\geq 0$ for all $x_{k}\in\mathbb{X}_{k}$ and $u_{k}\in
U_{k}(x_{k})$.

Let: $\mathcal{X}_{k}(.)$ be a density function on $\mathbb{X}_{k}$ such that
$\textit{supp}(\mathcal{X}_{k})=\mathbb{X}_{k}$, for all $k\in\mathbb{I}_{T}$;
the set of particles $\\{\xi^{j}_{k}\\}_{j=1}^{N_{k}}$ be independent and
distributed according to $\mathcal{X}_{k}$, for all $k\in\mathbb{I}_{T}$.

Algorithm 1 Particle Finite-Horizon Dynamic Programming

1:Initialize the set of particles $\\{\xi^{j}_{k}\\}_{j=1}^{N_{k}}$ in
$\mathbb{X}_{k}$, for all $k\in\mathbb{I}_{T}$.

2:Evaluate the weights $\\{\Omega^{l}_{T}\\}_{l=1}^{N_{T}}$
$\displaystyle\Omega^{l}_{T}=V_{T}(\xi^{l}_{T})=\ell(\xi^{l}_{T}),\,l=1,\ldots,N_{T}.$
(5)

3:For each $k=T-1$ down to $k=0$,  $\displaystyle\Omega^{l}_{k}$
$\displaystyle=\min_{u_{k}\in
U_{k}(\xi^{l}_{k})}\\{\ell(\xi^{l}_{k},u_{k})+\sum_{j=1}^{N_{k+1}}\Omega^{j}_{k+1}c^{j}(\xi^{l}_{k},u_{k})\\},$
(6) $\displaystyle\hskip 14.22636ptl=1,2,\ldots,N_{k},$ where  $\displaystyle
c^{j}(x_{k},u_{k})$
$\displaystyle=\frac{\mathcal{W}(\xi^{j}-f(x_{k},u_{k}))}{\sum_{j=1}^{N_{k+1}}\mathcal{W}(\xi^{j}-f(x_{k},u_{k}))}.$
(7)

We shall show next that Algorithm 1 can be used to generate an approximation
$\tilde{V}_{k}^{N_{k}}$,

$\displaystyle\tilde{V}_{k}^{N_{k}}(x_{k})=\min_{u_{k}\in
U_{k}(x_{k})}\\{\ell(x_{k},u_{k})+\sum_{j=1}^{N_{k+1}}\Omega^{j}_{k+1}c^{j}(x_{k},u_{k})\\},$
(8)

that converges, almost surely, to $V_{k}(.)$, for all $x_{k}\in\mathbb{X}_{k}$
and $k=1,2,\ldots,T$.

######  Remark.

The control law corresponding to this approximation of the value function can
be found as follows:

$\displaystyle u_{k}^{*}=\text{arg min}_{u_{k}\in
U_{k}(x_{k})}\\{\ell(x_{k},u_{k})+\sum_{j=1}^{N_{k+1}}\Omega^{j}_{k+1}c^{j}(x_{k},u_{k})\\}$
(9)

######  Lemma 1.

The approximation $\tilde{V}_{T-1}^{N_{T-1}}(x_{k})$, in (8), converges,
almost surely, to $V_{T-1}(x_{T-1})$ for all
$x_{T-1}=\xi_{T-1}^{j},\,j=1,2,\ldots,N_{T-1}$, as $N_{T}\to\infty$.

###### Proof.

We start with the expectation in the Dynamic Programming Equation (3) for
$k=T-1$, i.e.,

$\displaystyle\textbf{E}_{x_{T}}\\{V_{T}(x_{T})\mid x_{T-1},u_{T-1}\\}=$
$\displaystyle\hskip 14.22636pt\int_{\mathbb{X}_{T}}V_{T}(x_{T})p(x_{T}\mid
x_{T-1},u_{T-1})\,dx_{T},$

where $p(x_{T}\mid x_{T-1},u_{T-1})$ is the prediction density which, for the
dynamical system (1), equals $\mathcal{W}(x_{T}-f(x_{T-1},u_{T-1}))$. Since
$\\{\xi_{T}^{j}\\}$ is i.i.d. with density $\mathcal{X}_{T}$ over
$\mathbb{X}_{T}$, if the support of the prediction density
$\mathcal{W}(\cdot-f(x_{T-1},u_{T-1}))\subset\mathbb{X}_{T}$ for all
$x_{T-1}\in\mathbb{X}_{T-1}$ and $u_{T-1}\in U_{T-1}$, then the summation

$\displaystyle\sum_{j=1}^{N}\Omega^{j}_{T}c^{j}(x_{T-1},u_{T-1})$
$\displaystyle=\sum_{j=1}^{N}V_{T}(\xi^{j}_{T})c^{j}(x_{T-1},u_{T-1})$

is the self-normalizing importance sampling estimate [8] of the above
expectation. This estimate is unbiased and converges, almost surely, as
$N_{T}\to\infty$. Therefore,

$\displaystyle\ell(\xi^{l}_{T-1},u_{T-1})+\sum_{j=1}^{N_{T}}\Omega^{j}_{T}c^{j}(\xi^{l}_{T-1},u_{T-1})$

converges, almost surely, to

$\displaystyle\ell(\xi^{l}_{T-1},u_{T-1})+\textbf{E}_{x_{T}}[V_{T}(x_{T})\mid\xi^{l}_{T-1},u_{T-1}]$

as $N_{T}\to\infty$, for all $u_{T-1}\in U_{T-1}$ and
$\xi^{l}_{T-1},\,l=1,2,\ldots,N_{T-1}$. Since $U_{T-1}(x_{T-1})$ is finite,
then the minimum of each of the above over $U_{T-1}(x_{T-1})$ is equal, almost
surely, as $N_{T}\to\infty$. ∎

######  Proposition 1.

The approximation $\tilde{V}_{T-2}^{N_{T-2}}(x_{T-2})$, in (8), converges,
almost surely, to $V_{T-2}(x_{T-2})$ for all
$x_{T-2}=\xi_{T-2}^{j},\,j=1,2,\ldots,N_{T-2}$, as $N_{T},N_{T-1}\to\infty$.

###### Proof.

From Lemma 1, we have

$\displaystyle\lim_{N_{T}\to\infty}\ell(\xi^{l}_{T-2},u_{T-2})+\sum_{j=1}^{N_{T-1}}\Omega^{j}_{T-1}c^{j}(\xi^{l}_{T-2},u_{T-2})$
$\displaystyle=\ell(\xi^{l}_{T-2},u_{T-2})+\sum_{j=1}^{N_{T-1}}\lim_{N_{T}\to\infty}\Omega^{j}_{T-1},c^{j}(\xi^{l}_{T-2},u_{T-2})$
$\displaystyle=\ell(\xi^{l}_{T-2},u_{T-2})+\sum_{j=1}^{N_{T-1}}V_{T-1}(\xi_{T-1}^{j})c^{j}(\xi^{l}_{T-2},u_{T-2}).$

Which is the self-normalizing importance sampling estimate [8], since
$\text{supp}(\mathcal{W}(\cdot-f(x_{T-2},u_{T-2}))$ for all
$x_{T-2}\in\mathbb{X}_{T-1},\,u_{T-2}\in U_{T-2}(x_{T-2})$. Again, this
estimate is unbiased and converges, almost surely, to

$\displaystyle\ell(\xi^{l}_{T-2},u_{T-2})+\textbf{E}_{x_{T-1}}[V_{T-1}(x_{T-1})\mid
x_{T-2},u_{T-2}]$

for all $x_{T-2}\in\mathbb{X}_{T-2}$ and $u_{T-2}\in U_{T-2}(x_{T-2})$.
Therefore,

$\displaystyle\lim_{N_{T},N_{T-1}\to\infty}\min_{u_{T-2}\in
U_{T-2}(x_{T-2})}\\{\ell(\xi^{l}_{T-2},u_{T-2})+$ $\displaystyle\hskip
56.9055pt\sum_{j=1}^{N_{T-1}}\Omega^{j}_{T-1}c^{j}(\xi^{l}_{T-2},u_{T-2})\\}$
$\displaystyle=\min_{u_{T-2}\in
U_{T-2}(x_{T-2})}\\{\ell(\xi^{l}_{T-2},u_{T-2})+$ $\displaystyle\hskip
56.9055pt\textbf{E}_{x_{T-1}}[V_{T-1}(x_{T-1})\mid\xi^{l}_{T-2},u_{T-2}]\\}$
$\displaystyle=V_{T-2}(\xi_{T-2}^{l}),\,l=1,2,\ldots,N_{T-2}.$

∎

######  Remark.

The necessity of having
$\mathcal{W}(\cdot-f(x_{k-1},u_{k-1}))\subset\mathbb{X}_{k}$ for all
$k,\,x_{k-1}$ and $u_{k-1}$ might not be possible, for example, due to having
Gaussian process noise. This might dictate reformulating the original optimal
control problem, for instance, truncating and re-normalizing the densities
and/or changing the feasible sets.

######  Corollary 1.

The approximation $\tilde{V}_{k}^{N_{k}}(x)$, in (8), converges, almost
surely, to $V_{k}(x)$ for all $x=\xi_{k}^{j},\,j=1,2,\ldots,N_{k}$, as
$N_{T},N_{T-1},\ldots,N_{k}\to\infty$.

###### Proof.

By induction and using Proposition 1. ∎

######  Lemma 2.

(Proposition 1 in [2]) $V_{k}(.)$ is Lipschitz on $\mathbb{X}_{k}$ for all
$k\in\mathbb{I}_{T}$.

###### Proof.

Provided in [2], with the therein sum replaced by the expectation in

$\displaystyle V_{T-1}(x_{T-1})$
$\displaystyle=\inf_{u_{T-1}\in\mathbb{U}_{T-1}}\textbf{E}_{x_{T}}\\{\ell(x_{T-1},u_{T-1})$
$\displaystyle\hskip 42.67912pt+V_{T}(x_{T})\mid x_{T-1},u_{T-1}\\},$
$\displaystyle=\inf_{u_{T-1}\in\mathbb{U}_{T-1}}\\{\ell(x_{T-1},u_{T-1})+$
$\displaystyle\hskip 42.67912pt\int_{\mathbb{X}_{T}}V_{T}(x_{T})p(x_{T}\mid
x_{T-1},u_{T-1})\,dx_{T}\\},$

then all the consequent steps hold true. ∎

Let the sequence of sets $\\{A_{j}^{k}\\}$, for each $k\in\mathbb{I}_{T}$, be
such that

$\displaystyle
A_{k}^{j}=\\{x\in\mathbb{X}_{k}:\text{arg}\min_{i\in\mathbb{I}_{N_{k}}}\mid\mid
x-\xi_{k}^{j}\mid\mid=j\\},$

where $\mid\mid\cdot\mid\mid$ denotes the Euclidean norm. Then
$\\{A_{k}^{j},\,j\in\mathbb{I}_{N_{k}}\\}$ partitions $\mathbb{X}_{k}$. Also,
as in [2], define

$\displaystyle
d_{s}=\max_{k\in\mathbb{I}_{T}}\,\max_{j\in\mathbb{I}_{N}}\,\sup_{x\in
A_{j}^{k}}\mid\mid x-\xi_{k}^{j}\mid\mid$

######  Lemma 3.

As $N_{k}\to\infty$, $d_{s}\to 0$ almost surely.

###### Proof.

For any $x\in\mathbb{X}_{k}$, fix $\epsilon>0$. Define the open ball of radius
$\epsilon$ and center $x$ as $B_{\epsilon}(x)=\\{y\in\mathbb{X}_{k}:\mid\mid
y-x\mid\mid<\epsilon\\}$. Define the event $C_{j}=[\xi_{j}\in
B_{\epsilon}(x)]$. Since $\mathcal{X}_{k}$ is continuous on $\mathbb{X}_{k}$,
then $\text{Pr }(C_{j})=\text{constant}>0$. Hence, $\sum_{j=1}^{N_{k}}\text{Pr
}(C_{j})\to\infty$ as $N_{k}\to\infty$. By the Borel-Cantelli Zero-One Law
[11], $\text{Pr }[C_{j}\text{, infinitely often}]=1$, therefore, there exists
some finite positive integer $\bar{N}$, such that $\xi^{\bar{N}}_{k}\in
B_{\epsilon}(x)$. This holds for all $\epsilon>0$. ∎

######  Proposition 2.

The approximation $\tilde{V}_{k}^{N_{k}}(x_{k})$ converges, almost surely, to
$V_{k}(x_{k})$, for all $x_{k}\in\mathbb{X}_{k}$, as $N_{k}\to\infty$.

###### Proof.

For any $x_{k}\in A_{k}^{j}$,

$\displaystyle\mid\tilde{V}_{k}^{N_{k}}(x_{k})-V_{k}(x_{k})\mid$
$\displaystyle\hskip
28.45274pt=\mid\tilde{V}_{k}^{N_{k}}(x_{k})-V_{k}(x_{k})+$
$\displaystyle\hskip
56.9055pt\tilde{V}_{k}^{N_{k}}(\xi_{k}^{j})-V_{k}(\xi^{j}_{k})-\tilde{V}_{k}^{N_{k}}(\xi_{k}^{j})+V_{k}(\xi^{j}_{k})\mid,$

and by applying the triangular inequality, twice,

$\displaystyle\mid\tilde{V}_{k}^{N_{k}}(x_{k})-V_{k}(x_{k})\mid$
$\displaystyle\hskip
28.45274pt\leq\mid\tilde{V}_{k}^{N_{k}}(x_{k})-\tilde{V}_{k}^{N_{k}}(\xi_{k}^{j})\mid+\mid
V_{k}(x_{k})-V_{k}(\xi^{j}_{k})\mid$ $\displaystyle\hskip
56.9055pt+\mid\tilde{V}_{k}^{N_{k}}(\xi_{k}^{j})-V_{k}(\xi^{j}_{k})\mid.$

By the Lipschitzness of $\tilde{V}_{k}^{N_{k}}(\cdot)$ and $V_{k}(\cdot)$ on
$\mathbb{X}_{k}$,

$\displaystyle\mid\tilde{V}_{k}^{N_{k}}(x_{k})-\tilde{V}_{k}^{N_{k}}(\xi_{k}^{j})\mid+\mid
V_{k}(x_{k})-V_{k}(\xi^{j}_{k})\mid\leq$ $\displaystyle\hskip
28.45274pt\mathcal{A}\mid\mid x_{k}-\xi^{j}_{k}\mid\mid+\mathcal{B}\mid\mid
x_{k}-\xi^{j}_{k}\mid\mid,$

for some $\mathcal{A},\,\mathcal{B}>0$, hence

$\displaystyle\mid\tilde{V}_{k}^{N_{k}}(x_{k})-\tilde{V}_{k}^{N_{k}}(\xi_{k}^{j})\mid+\mid
V_{k}(x_{k})-V_{k}(\xi^{j}_{k})\mid\leq$ $\displaystyle\hskip
28.45274pt(\mathcal{A}+\mathcal{B})d_{s},$

which goes to zero, almost surely, as $N_{T},N_{T-1},\ldots,N_{k}\to\infty$.
Also, by Corollary 1,
$\mid\tilde{V}_{k}^{N_{k}}(\xi_{k}^{j})-V_{k}(\xi^{j}_{k})\mid\to 0$, almost
surely, as $N_{T},N_{T-1},\ldots,N_{k}\to\infty$. Therefore,
$\mid\tilde{V}_{k}^{N_{k}}(x_{k})-V_{k}(x_{k})\mid$ goes to zero, almost
surely, as $N_{T},N_{T-1},\ldots,N_{k}\to\infty$. ∎

##  3 Infinite-Horizon Discounted Cost

The Dynamic Programming Equation (DPE) of the infinite-horizon discounted cost
optimal control problem, for the system described in (1), is [3]

$\displaystyle V(x_{k})$
$\displaystyle=\min_{u_{k}\in\mathbb{U}}\\{\ell(x_{k},u_{k})+\alpha.\textbf{E}_{x_{k+1}}\\{V(x_{k+1})\mid\,x_{k},u_{k}\\}\\},$
(10) $\displaystyle=\min_{u_{k}\in\mathbb{U}}\\{\ell(x_{k},u_{k})+$
$\displaystyle\hskip 28.45274pt\alpha.\int_{\mathbb{X}}V(x_{k+1})p(x_{k+1}\mid
x_{k},u_{k})\,dx_{k+1}\\},$ (11)

with $\mathbb{X}_{k}=\mathbb{X}$ and $\mathbb{U}_{k}=\mathbb{U}$ for all
$k=1,2,\ldots$, and $\mathbb{U}$ is finite. The prediction density
$p(x_{k+1}\mid x_{k},u_{k})$

$\displaystyle p(x_{k+1}\mid
x_{k},u_{k})=\mathcal{W}(x_{k+1}-f(x_{k},u_{k})).$ (12)

The Dynamic Programming algorithm corresponds to the additive cost function is
stated as follows:

$\displaystyle\lim_{T\to\infty}\textbf{E}_{w_{0},\ldots,w_{T}}\left\\{\sum_{k=0}^{T}\alpha^{k}\ell(x_{k},u_{k})\right\\}.$
(13)

Suppose that the support of $\mathcal{W}(\cdot-f(x_{k},u_{k}))$ is a subset of
$\mathbb{X}$ for all $x_{k}\in\mathbb{X}$ and $u_{k}\in\mathbb{U}$. And
suppose that $\\{\xi^{j}\in\mathbb{R}^{r_{x}},\,j=1,2,\ldots,N\\}$ is
independent and distributed according to $\mathcal{X}$, such that the support
of $\mathcal{X}$ is $\mathbb{X}$. Then, the following weighted mass density

$\displaystyle p(x_{k+1}\mid x_{k},u_{k})$
$\displaystyle=\frac{\sum_{j=1}^{N}\mathcal{W}(\xi^{j}-f(x_{k},u_{k})).\delta(x_{k+1}-\xi^{j}).}{\sum_{m=1}^{N}\mathcal{W}(\xi^{m}-x_{k+1})}$
$\displaystyle=\sum_{j=1}^{N}c^{j}(x_{k},u_{k}).\delta(x_{k+1}-\xi^{j})$ (14)

where

$\displaystyle c^{j}(x_{k},u_{k})$
$\displaystyle=\frac{\mathcal{W}(\xi^{j}-f(x_{k},u_{k}))}{\sum_{m=1}^{N}\mathcal{W}(\xi^{m}-f(x_{k},u_{k}))},$
(15)

is the self-normalized importance sampling approximation of the prediction
density in the left-hand-side; since
$\text{supp}\mathcal{W}(\cdot-f(x_{k},u_{k})\subset\text{supp}\mathcal{X}(.)$,
for all $x_{k},\,u_{k}$.

The following algorithm,

Algorithm 2 Particle Value Iteration

1:Initialize the set of i.i.d. particles $\\{\xi^{j}\\}_{j=1}^{N}$ according
to $\mathcal{X}(\cdot)$ in $\mathbb{X}$,

2:Randomly initialize the weights $\\{\Omega^{j}_{0}\\}_{j=1}^{N}$ in
$\mathbb{R}$, set $i\leftarrow 0$.

3:Update the weights by  $\displaystyle\Omega^{l}_{i+1}$
$\displaystyle=\min_{u_{k}\in\mathbb{U}}\\{\ell(\xi^{l},u_{k})+\alpha.\sum_{j=1}^{N}\Omega^{j}_{i}c^{j}(\xi^{l},u_{k})\\},$
(16) $\displaystyle l=1,2,\ldots N$

4:If $\\{\Omega^{j}_{i}\\}$ satisfies a convergence criterion as $i$
increases, terminate and set $\Omega^{j}=\Omega^{j}_{i+1}$ for all $j$.
Otherwise, set $i\leftarrow i+1$ and go to Step 3.

generates an approximation

$\displaystyle\tilde{V}^{N}(x)=\min_{u\in\mathbb{U}}\\{\ell(x,u)+\alpha.\sum_{j=1}^{N}\Omega^{j}c^{j}(x,u)\\}.$
(17)

Similarly to [2], by the equations (51)-(55) therein, and appealing to Lemma 3
in this paper, it can be shown that

$\displaystyle\sup_{x\in\mathbb{X}}\mid V(x)-\tilde{V}^{N}(x)\mid\to 0,$ (18)

almost surely, as $N\to\infty$.

##  4 Probabilistic Constraints

In this section, we show the two DP algorithms extended to handle probability
constraints. This extension is developed for the infinite-horizon algorithm.
The application of this extension to the finite-horizon follows naturally.

We start with the optimal control problem introduced in Section 2, but subject
to the probabilistic constraints

$\displaystyle\textbf{Pr}(x_{k}\in\mathbb{S})\geq 1-\epsilon,\text{ for all
$k$},$

where $\mathbb{S}\subset\mathbb{X}$, can be seen as the safe set, which not to
be left by the state for more than some probabilistic tolerance
$\epsilon\in[0,1)$, supposedly very low. This probability constraint can be
augmented to the DP algorithm in Section 2 without a major change; we can
restrict the control space to

$\displaystyle U(x_{k})$
$\displaystyle=\\{u_{k}\in\mathbb{U}_{k}\mid\,\text{Pr}(x_{k+1}\in\mathbb{S}\mid
x_{k},u_{k})\geq 1-\epsilon\\}.$ (19)

If $\mathbb{S}$ is a bounded set, the probabilistic constraints can be checked
through the Monte Carlo approximations over the state-space grid.

Using the density in (14), the violation probability in (19) is the integral

$\displaystyle\text{Pr}(x_{k+1}\in\mathbb{S}\mid
x_{k},u_{k})=\int_{\mathbb{S}}p(x_{k+1}\mid x_{k},u_{k})\,dx_{k+1}$ (20)

From the particles $\\{\xi^{j}_{k}\\}_{j=1}^{N_{k}}$, let the set of indices
$\mathbb{I}$ correspond to the particles inside the unsafe set, the complement
of $\mathbb{S}$ in $\mathbb{X}$. That is

$\displaystyle\mathbb{I}=\left\\{j\in\\{1,\ldots,N\\}\mid\xi^{j}\in\mathbb{S}^{c}\right\\}.$

The violation probability is then approximated by

$\displaystyle\text{Pr}(x_{k+1}\in\mathbb{S}^{c}\mid
x_{k},u_{k})=\sum_{j\in\mathbb{I}}c^{j}(x_{k},u_{k}),$ (21)

hence, the input constraint set (19) is then replaced by

$\displaystyle U^{N}(x_{k})$
$\displaystyle=\\{u_{k}\in\mathbb{U}_{k}\mid\,\sum_{j\in\mathbb{I}}c^{j}(x_{k},u_{k})<\epsilon\\}.$
(22)

Algorithm 3 Particle Value Iteration with probabilistic constraints

1:Initialize the set of i.i.d. particles $\\{\xi^{j}\\}_{j=1}^{N}$ according
to $\mathcal{X}(\cdot)$ in $\mathbb{X}$,

2:Identify the set $\mathbb{I}$,

3:Randomly initialize the weights $\\{\Omega^{j}_{0}\\}_{j=1}^{N}$ in
$\mathbb{R}$, set $i\leftarrow 0$.

4:Update the weights by  $\displaystyle\Omega^{l}_{i+1}$
$\displaystyle=\min_{u_{k}\in
U^{N}(\xi^{l})}\\{\ell(\xi^{l},u_{k})+\alpha.\sum_{j=1}^{N}\Omega^{j}_{i}c^{j}(\xi^{l},u_{k})\\},$
(23) $\displaystyle l=1,2,\ldots N$

5:If $\\{\Omega^{j}_{i}\\}$ satisfies a convergence criterion as $i$
increases, terminate and set $\Omega^{j}=\Omega^{j}_{i+1}$ for all $j$.
Otherwise, set $i\leftarrow i+1$ and go to Step 3.

##  5 Numerical Examples

Two numerical examples are presented in this section. The first example is a
simple scalar linear Gaussian state-space model in which infinite-horizon
discounted cost value function is known and can be compared to that generated
by Algorithm 2. The second example is a two states nonlinear system which is
to respect some probability constraint.

###  5.1 Discounted cost LQR

Consider the following linear Gaussian state-space model111The notation
$\mathcal{N}(\mu,\Sigma)$ denotes a Gaussian density with $\mu$ mean and
$\Sigma$ covariance.:

$\displaystyle x_{k+1}=Fx_{k}+Gu_{k}+w_{k},\,w_{k}\sim\mathcal{N}(\mu_{w},W),$
(24)

with full state feedback, i.e., $y_{k}=x_{k}$.

The infinite horizon, discounted-cost LQR [3] value function can be found by
solving the following DPE:

$\displaystyle V(x_{k})$
$\displaystyle=\min_{u}\\{x_{k}^{T}Qx_{k}+u_{k}^{T}Ru_{k}+$
$\displaystyle\hskip
28.45274pt\alpha.\textbf{E}_{w_{k}}\\{V(Fx_{k}+Bu_{k}+w_{k})\\}\\},$

where the value function has the form $V(x_{k})=x_{k}^{T}Xx_{k}+q$ for some
positive definite matrix $X$ and constant $q>0$.

The matrix $X$ can be found by solving the following Algebraic Riccati
Equation:

$\displaystyle X=\alpha F^{T}XF-\alpha^{2}A^{T}XB(R+\alpha
B^{T}XB)^{-1}B^{T}XA+Q,$ (25)

and

$\displaystyle q=\frac{\alpha}{1-\alpha}\text{trace}\\{XW\\}.$ (26)

Now for (24), suppose

$\displaystyle
x_{k+1}=0.95x_{k}+u_{k}+w_{k},\,w_{k}\sim\mathcal{N}(0,0.5\,\mathbb{I}_{3\times
3}).$ (27)

and $Q=R=1$. The value function, after substituting the corresponding values
in (25) and (26), is

$\displaystyle V(x_{k})=1.460x_{k}^{2}+6.570.$

Towards comparing the above value function to a one acquired by Algorithm 2:
we use $2000$ particles $\\{\xi^{j}\\}_{j=1}^{2000}$ where
$\xi^{j}\sim\mathcal{N}(0,4)$, and sampled control actions
$\\{\nu^{j}\\}_{j=1}^{50}$ such that $\nu^{j}\sim\mathcal{N}(0,1)$. Value
Iteration via Algorithm 2 is then conducted, and the resulting particle value
function is approximated by the quadratic polynomial

$\displaystyle V(x_{k})=1.410x_{k}^{2}-0.0023x_{k}+5.52.$

The feedback control law of the particle approximation as in (9) is compared
to the discounted-cost LQR controller. This is shown in Figure 1.

Figure 1: The response of the linear Gaussian system (27), with identical
initial conditions disturbance realizations, to each: the exact LQR optimal
control (in blue), and the particle approximation (9) (in red).

###  5.2 Nonlinear system with probabilistic constraints

Given the dynamics:

$\displaystyle x^{1}_{k+1}$
$\displaystyle=0.9x^{1}_{k}+0.2x^{2}_{k}+w_{k}^{1},$ $\displaystyle
x^{2}_{k+1}$
$\displaystyle=-0.15x^{1}_{k}+0.9x^{2}_{k}+0.05x^{1}_{k}x^{2}_{k}+u_{k}+w_{k}^{2},$

where $x_{k}=(x^{1}_{k},x^{2}_{k})^{T}$ is the state vector, and the
disturbance,
$(w_{k}^{1},w_{k}^{2})^{T}=w_{k}\sim\mathcal{N}(0,.3\mathbb{I}_{2\times 2})$,
is white. To better visualize the dynamics, Figure 2 represents the
streamlines of the state dynamics with zero input and state disturbances.

Figure 2: The streamlines of the difference vector field
$f(x_{k},u_{k},w_{k})-x_{k}$ with $u_{k}$ and $w_{k}$ set to zero.

Suppose the L-shaped state set,
$\mathcal{L}=[3,5]\times[-4,2]\cup[-2,5]\times[-7,-4]$, is to be avoided, that
is, $\mathbb{S}$ is the complement of $\mathcal{L}$ in $\mathbb{X}$.

Figure 3: Colormap of $\kappa$ acquired by Algorithm 3 and fitted by a piece-
wise surface. White regions correspond to infeasible states.

Towards defining an optimal control law $\kappa$, let $V$ be the value
function, the optimal cost, of the infinite horizon discounted cost whose
stage costs are $\ell_{k}(x_{k},u_{k})=x_{k}^{T}x_{k}+u_{k}^{2}$ and with a
discount factor $\gamma=0.9$ [3]. Following the Value Iteration in Algorithm
3, uniformly randomized grids of $2000$ points over
$\mathbb{X}=[-10,10]\times[-5,15]$ and $50$ points in $\mathbb{U}=[-3,3]$, are
generated. Convergence is considered achieved if the maximum absolute relative
error is less than $5\%$. Figure 3 shows the colormap of the resulting
$\kappa$, and the empty regions are infeasible states. A Pythoncode of this
example can be found at https://github.com/msramada/MC_DynamicProgramming.

##  6 Conclusion

The convergence of the value function and feedback law approximants to their
continuous state and input spaces counterparts is implied under regularity
conditions. This number is highly dependent on the corresponding dimension of
these spaces and the complexity of the involved dynamics and distributions.
Hence, the curse of dimensionality cannot be avoided by this approach.
However, the flexibility of the sampling procedure and the self-approximating
forms provided alleviate some burden in the implementation of DP and make it
more natural to handle constraints of probabilistic nature. Regions of the
state-space of higher importance can tantamount to regions of higher
distribution in the sampling procedure.

## References

  * [1] Richard E Bellman and Stuart E Dreyfus.  Applied dynamic programming.  Princeton university press, 2015.
  * [2] Dimitri Bertsekas.  Convergence of discretization procedures in dynamic programming.  IEEE Transactions on Automatic Control, 20(3):415–419, 1975.
  * [3] Dimitri Bertsekas.  Dynamic programming and optimal control: Volume I, volume 1.  Athena scientific, 2012.
  * [4] M. Chen.  “Optimized Dynamic Programming-Based Algorithms Solver”.
  * [5] Arnaud Doucet, Nando De Freitas, Neil James Gordon, et al.  Sequential Monte Carlo methods in practice, volume 1.  Springer, 2001.
  * [6] Sylvia Herbert, Jason J Choi, Suvansh Sanjeev, Marsalis Gibson, Koushil Sreenath, and Claire J Tomlin.  Scalable learning of safety guarantees for autonomous systems using hamilton-jacobi reachability.  arXiv preprint arXiv:2101.05916, 2021.
  * [7] SSa Keerthi and Elmer G Gilbert.  Optimal infinite-horizon feedback laws for a general class of constrained discrete-time systems: Stability and moving-horizon approximations.  Journal of optimization theory and applications, 57(2):265–293, 1988.
  * [8] Jun S Liu and Jun S Liu.  Monte Carlo strategies in scientific computing, volume 10.  Springer, 2001.
  * [9] David Q Mayne.  Model predictive control: Recent developments and future promise.  Automatica, 50(12):2967–2986, 2014.
  * [10] Benjamin Recht.  A tour of reinforcement learning: The view from continuous control.  Annual Review of Control, Robotics, and Autonomous Systems, 2:253–279, 2019.
  * [11] Sidney Resnick.  A probability path.  Springer, 2019.
  * [12] John Rust.  Using randomization to break the curse of dimensionality.  Econometrica: Journal of the Econometric Society, pages 487–516, 1997.
  * [13] Alexander T Schwarm and Michael Nikolaou.  Chance-constrained model predictive control.  AIChE Journal, 45(8):1743–1752, 1999.
  * [14] Jennie Si, Andrew G Barto, Warren B Powell, and Don Wunsch.  Handbook of learning and approximate dynamic programming, volume 2.  John Wiley & Sons, 2004.
  * [15] Christopher JCH Watkins and Peter Dayan.  Q-learning.  Machine learning, 8(3-4):279–292, 1992.
  * [16] Jun Yan and Robert R Bitmead.  Incorporating state estimation into model predictive control and its application to network traffic control.  Automatica, 41(4):595–604, 2005.