Toric hyperkähler varieties and Q-factorial terminalizations

Yoshinori Namikawa

Introduction.

A toric hyperkähler variety is defined as a hyperkähler reduction of a
quarternionic space $\mathbf{H}^{n}$ with the standard hyperkähler structure
$(g,I,J,K)$, by an action of a compact torus $T^{d}_{\mathbf{R}}$ (cf. [BD],
[Go], [HS], [Ko 1]). If we identify $\mathbf{H}^{n}$ with $\mathbf{C}^{2n}$ by
the complex structure $I$, a toric hyperkähler variety is regarded as a
holomorphic symplectic reduction of $(\mathbf{C}^{2n},\omega)$ by a
Hamiltonian action of an algebraic torus $T^{d}$. Here $\omega$ is the
standard symplectic 2-form on $\mathbf{C}^{2n}$. Recently it has been studied
from various points of view such as symplectic dulality, biratonal geometry
and Poisson deformatons ([BLPW], [Nag]). In this article we denote by
$Y(A,\alpha)$ a toric hyperkähler variety according to [HS]. Here $A$ is a
$d\times n$ integer valued matrix such that
$\mathbf{Z}^{n}\stackrel{{\scriptstyle A}}{{\to}}\mathbf{Z}^{d}$ is a
surjection, and $\alpha$ is an element of
$\mathrm{Hom}_{alg.gp}(T^{d},\mathbf{C}^{*})$. Let us introduce an
$n\times(n-d)$ integer valued matrix $B$ in such a way that the sequence

$0\to\mathbf{Z}^{n-d}\stackrel{{\scriptstyle
B}}{{\to}}\mathbf{Z}^{n}\stackrel{{\scriptstyle A}}{{\to}}\mathbf{Z}^{d}\to 0$

is exact. $Y(A,\alpha)$ essentially depends on this $B$ rather than $A$, and
certain properties of $B$ often reflect the geometry of $Y(A,\alpha)$. We
assume that all row vectors of $B$ are nonzero. When $\alpha=0$, $Y(A,\alpha)$
is a conical symplectic variety, and $Y(A,\alpha)$ is a crepant, projective
partial resolution of $Y(A,0)$ for any $\alpha$. When one chooses $\alpha$
generic, $Y(A,\alpha)$ has only quotient singularities. In particular, if $A$
is unimodular, then $Y(A,\alpha)$ is nonsingular for a generic $\alpha$, and
it gives a crepant resolution of $Y(A,0)$. But, in general, $Y(A,0)$ does not
have any crepant resolution. A substitute for a crepant resolution is a good
crepant partial resolution called a Q-factorial terminalization. It would be
natural to expect that $Y(A,\alpha)$ is a Q-factorial terminalization of
$Y(A,0)$ if $\alpha$ is chosen generic. But, this is not true because
$Y(A,\alpha)$ may possibly have singularities of codimension 2 even if
$\alpha$ is generic. In this article, we realize $Y(A,0)$ as another toric
hyperkähler variety $Y(A^{\sharp},0)$ so that $Y(A^{\sharp},\alpha^{\sharp})$
is a Q-factorial terminalization of $Y(A^{\sharp},0)$ for a generic
$\alpha^{\sharp}$ (Theorem 11). More precisely, this $A^{\sharp}$ is
charactrized by the property that $B^{\sharp}$ is the primitivization of $B$.
For the notion of a primitivization, see (4.3). As an application we give a
necessary and sufficient condition for $Y(A,0)$ to have a crepant projective
resolution. In fact, $Y(A,0)$ has a crepant projective resolution if and only
if the primitivization $B^{\sharp}$ of $B$ is unimodular (Corollary 13).
Moreover, we construct very explicitly the universal Poisson deformation of
$Y(A,0)$ in terms of $A^{\sharp}$ (see (4.1), (4.2) and (4.3)).

§1.

Let $\mathbf{C}^{2n}$ be an affine space with coordinates $z_{1}$, …, $z_{n}$,
$w_{1}$, …, $w_{n}$. An $n$ dimensional algebraic torus $T^{n}$ acts on
$\mathbf{C}^{2n}$ by

$(z_{1},...,z_{n},w_{1},...,w_{n})\to(t_{1}z_{1},...,t_{n}z_{n},t_{1}^{-1}w_{1},...,t_{n}^{-1}w_{n})$

By an integer valued $d\times n$-matrix $A:=(a_{ij})$, we determine a
homomorphism of algebraic tori $\phi:T^{d}\to T^{n}$ by

$(t_{1},...,t_{d})\to(t_{1}^{a_{11}}\cdot\cdot\cdot
t_{d}^{a_{d1}},...,t_{1}^{a_{1n}}\cdot\cdot\cdot t_{d}^{a_{dn}}).$

Then $T^{d}$ acts on $\mathbf{C}^{2n}$ by

$(z_{1},...,z_{n},w_{1},...,w_{n})\to$ $(t_{1}^{a_{11}}\cdot\cdot\cdot
t_{d}^{a_{d1}}z_{1},...,t_{1}^{a_{1n}}\cdot\cdot\cdot
t_{d}^{a_{dn}}z_{n},t_{1}^{-a_{11}}\cdot\cdot\cdot
t_{d}^{-a_{d1}}w_{1},...,t_{1}^{-a_{1n}}\cdot\cdot\cdot t_{d}^{-a_{dn}}w_{n})$

The homomorphism $\phi$ induces a map of characters:
$\phi^{*}:\mathrm{Hom}_{alg.gp}(T^{n},\mathbf{C}^{*})\to\mathrm{Hom}_{alg.gp}(T^{n},\mathbf{C}^{*})$.
When we identify the character groups respectively with $\mathbf{Z}^{n}$ and
$\mathbf{Z}^{d}$ in a natural way, $\phi^{*}$ is nothing but the homomorphism
$\mathbf{Z}^{n}\stackrel{{\scriptstyle A}}{{\to}}\mathbf{Z}^{d}$ determined by
$A$. We assume that the map $A$ is a surjection. Let $B$ be an integer valued
$n\times(n-d)$-matrix such that the following sequence is exact:

$0\to\mathbf{Z}^{n-d}\stackrel{{\scriptstyle
B}}{{\to}}\mathbf{Z}^{n}\stackrel{{\scriptstyle A}}{{\to}}\mathbf{Z}^{d}\to
0.$

We assume that all row vectors of $B$ are non-zero.

Define a symplectic 2-form $\omega$ on $\mathbf{C}^{2n}$ by

$\omega:=\sum_{1\leq i\leq n}dw_{i}\wedge dz_{i}.$

Then the $T^{d}$-action is a Hamiltonian action on $(\mathbf{C}^{2n},\omega)$.
Writing $A=(\mathbf{a}_{1},...,\mathbf{a}_{n})$ by the column vectors, the
moment map $\mu:\mathbf{C}^{2n}\to\mathbf{C}^{d}$ is given by

$(z_{1},...,z_{n},w_{1},...,w_{n})\to\sum_{1\leq i\leq
n}\mathbf{a}_{i}z_{i}w_{i}.$

Lemma 1. $\mu^{-1}(0)$ is of complete intersection. In particular,
$\dim\>\mu^{-1}(0)=2n-d$.

Proof. Put $W:=\mathrm{Spec}\mathbf{C}[z_{1}w_{1},...,z_{n}w_{n}]$. Then $\mu$
factorizes as
$\mathbf{C}^{2n}\stackrel{{\scriptstyle\iota}}{{\to}}W\stackrel{{\scriptstyle\nu}}{{\to}}\mathbf{C}^{d}$.
Here $\nu$ is determined by the ring homomorphism

$\mathbf{C}[s_{1},...,s_{d}]\to\mathbf{C}[z_{1}w_{1},....,z_{n}w_{n}],\>\>\
(s_{i}\to\sum_{j=1}^{n}z_{j}w_{j}a_{ij})$

and $\iota$ is determined by the inclusion

$\mathbf{C}[z_{1}w_{1},...,z_{n}w_{n}]\to\mathbf{C}[z_{1},...,z_{n},w_{1},...,w_{n}].$

$W$ is an $n$ dimensional affine space, Since $\mathrm{rank}\>A=d$,
$\nu^{-1}(0)$ is an $n-d$ dimensional linear subspace of $W$. It is easily
checked that $\iota$ is a flat map. Hence
$\mu^{-1}(0)=\iota^{-1}(\nu^{-1}(0))$ has dimension $n+(n-d)=2n-d$. Since
$\mu^{-1}(0)$ is defined by $d$ equations in $\mathbf{C}^{2n}$, we see that
$\mu^{-1}(0)$ is of complete intersection. $\square$

Note that $T^{d}$ acts on each fiber of $\mu$. Put
$M:=\mathrm{Hom}_{alg.gp}(T^{d},\mathbf{C}^{*})$. For $\alpha\in M$, we define

$X(A,\alpha):=\mathbf{C}^{2n}//_{\alpha}T^{d},\>\>\>Y(A,\alpha):=\mu^{-1}(0)//_{\alpha}T^{d}.$

When $\alpha=0$,

$X(A,0)=\mathrm{Spec}\>\mathbf{C}[z_{1},...,z_{n},w_{1},...,w_{n}]^{T_{d}},\>\>Y(A,0)=\mathrm{Spec}\>\mathbf{C}[\mu^{-1}(0)]^{T_{d}}.$

Denote by $(\mathbf{C}^{2n})^{\alpha-ss}$ and $(\mu^{-1})^{\alpha-ss}(0)$
respectivelt the $\alpha$-semistable locus for the $T^{d}$-action on
$\mathbf{C}^{2n}$ and $\mu^{-1}(0)$. The inclusion maps
$(\mathbf{C}^{2n})^{\alpha-ss}\to\mathbf{C}^{2n}$ and $(\mu^{-1})^{\alpha-
ss}(0)\to\mu^{-1}(0)$ respectively induce maps $\nu_{X,\alpha}:X(A,\alpha)\to
X(A,0)$ and $\nu_{Y,\alpha}:Y(A,\alpha)\to Y(A,0)$. They are birational
projective morphisms. The moment map $\mu:\mathbf{C}^{2n}\to\mathbf{C}^{d}$
induces a map $X(A,0)\stackrel{{\scriptstyle\bar{\mu}}}{{\to}}\mathbf{C}^{d}$
with $\bar{\mu}^{-1}(0)=Y(A,0)$ and we have a commutative diagram

$\begin{CD}Y(A,\alpha)@>{}>{}>X(A,\alpha)\\\ @V{}V{}V@V{}V{}V\\\
Y(A,0)@>{}>{}>X(A,0)\\\ @V{}V{}V@V{\bar{\mu}}V{}V\\\
0@>{}>{}>\mathbf{C}^{d}\end{CD}$ (1)

Let $\\{\mathbf{a}_{1},...,\mathbf{a}_{n}\\}$ be the set of column vectors of
$A$. Then its subset generates a subspace of $M_{\mathbf{R}}$. Consider all
such subspaces $H_{1}$, …, $H_{l}$ of $M_{\mathbf{R}}$ with codimension $1$.
Then $\alpha\in M$ is called generic if $\alpha$ is not contained in any
$H_{i}$. When $\alpha$ is generic, every point $p$ of $(\mu^{-1}(0))^{\alpha-
ss}$ is $\alpha$-stable, i.e. $(\mu^{-1}(0))^{\alpha-
ss}=(\mu^{-1}(0))^{\alpha-s}$ (cf. [Ko 2, Proposition 3.6], [HS, Proposition
6.2]). In particular, the stabilizer group $T^{d}$ of $p$ is a finite. This
means that $Y(A,\alpha)$ admits only quotient singularties. The symplectic
2-form $\omega$ on $\mathbf{C}^{2n}$ reduced to a symplectic orbifold 2-form
$\omega_{Y(A,\alpha)}$ on the orbifold $Y(A,\alpha)$. In particular,
$\omega_{Y(A,\alpha)}$ restricts to a usual symplectic 2-form on
$Y(A,\alpha)_{reg}$. Similarly, $\omega$ is reduced to a symplectic 2-form
$\omega_{Y(A,0)}$ on $Y(A,0)_{reg}$. We have
$\omega_{Y(A,\alpha)}=\nu_{Y,\alpha}^{*}\omega_{Y(A,0)}$. Then $Y(A,\alpha)$
has symplectic singularities by [Be, Proposition 2.4]. Hence $Y(A,0)$ also has
symplectic singularities. As $Y(A,0)$ has a natural $\mathbf{C}^{*}$-action
induced from the scaling $\mathbf{C}^{*}$-action on $\mathbf{C}^{2n}$,
$Y(A,0)$ is a conical symplectic variety with $wt(\omega_{Y(A,0)})=2$. As
$Y(A,\alpha)$ has symplectic singularities, $\mathrm{Sing}(Y(A,\alpha))$ has
even codimension in $Y(A,\alpha)$ by [Ka]. By [Na 4, Corollary 03],
$Y(A,\alpha)$ has terminal singularities if and only if
$\mathrm{Codim}_{Y(A,\alpha)}\mathrm{Sing}(Y(A,\alpha))\geq 4$. But it may
happen that $\mathrm{Codim}_{Y(A,\alpha)}\mathrm{Sing}(Y(A,\alpha))=2$. Here
is a criterion when $\mathrm{Codim}_{Y(A,\alpha)}\mathrm{Sing}(Y(A,\alpha))=2$
for a generic $\alpha$.

Proposition 2. The following conditions are equivalent:

(1) For every generic element $\alpha\in M$,
$\mathrm{Codim}_{Y(A,\alpha)}\mathrm{Sing}(Y(A,\alpha))=2$.

(2) For some $j_{0}\in\\{1,2,...,n\\}$, the matrix
$\bar{A}:=(\mathbf{a}_{1},...,\mathbf{a}_{j_{0}-1},\mathbf{a}_{j_{0}+1},...,\mathbf{a}_{n})$
satisfies the following conditions:

(2-a): $\mathrm{rank}(\bar{A})=d$,

(2-b): The homomorphism
$\mathbf{Z}^{n-1}\stackrel{{\scriptstyle\bar{A}}}{{\to}}\mathbf{Z}^{d}$ is not
surjective.

Proof. (1) $\Rightarrow$ (2): For a subset $J$ of $\\{1,2,...,n\\}$, collect
the column vectors $\mathbf{a}_{j}$ with $j\in J$ and form a matrix
$d\times|J|$-matrix $A_{J}$. Take $J$ so that it is maximal among those with
the following properties

(i) $\mathrm{rank}(A_{J})=d$

(ii) the homomorphism $\mathbf{Z}^{|J|}\stackrel{{\scriptstyle
A_{J}}}{{\to}}\mathbf{Z}^{d}$ is not surjective.

We put

$(\mu^{-1}(0))_{J}:=\\{\mathbf{x}\in(\mu^{-1}(0))\>|\>z_{j}(\mathbf{x})=w_{j}(\mathbf{x})=0,\>\>\forall
j\notin J\\}.$

and define

$(\mu^{-1}(0))^{\alpha-s}_{J}:=(\mu^{-1}(0))_{J}\cap(\mu^{-1}(0))^{\alpha-s}$

Let us consider the quotient map

$\pi:(\mu^{-1}(0))^{\alpha-s}\to Y(A,\alpha).$

We then have

$\mathrm{Sing}\>Y(A,\alpha)=\bigcup_{J}\pi((\mu^{-1}(0))^{\alpha-s}_{J}).$

Claim 3. Assume that $(\mu^{-1}(0))^{\alpha-s}_{J}\neq\emptyset$. Then we
have:

  * •

$\dim\>(\mu^{-1}(0))^{\alpha-s}_{J}=2|J|-d$

  * •

$\dim\>\pi((\mu^{-1}(0))^{\alpha-s}_{J})=2|J|-2d$

Proof. Let us consider the linear subspace $L$ of $\mathbf{C}^{2n}$ defined by
$z_{j}=w_{j}=0$, $j\notin J$. Then $L\cong\mathbf{C}^{2|J|}$ and we can take
$z_{j},w_{j}$ $(j\in J)$ as coordinates of $\mathbf{C}^{2|J|}$. Restrict the
moment map $\mu$ to $L=\mathbf{C}^{2|J|}$. Then
$\mu|_{L}:\mathbf{C}^{2|J|}\to\mathbf{C}^{d}$ is given by

$(\\{z_{j}\\},\\{w_{j}\\})_{j\in J}\to\sum_{j\in J}\mathbf{a}_{j}z_{j}w_{j}.$

Since $\mathrm{rank}\>A_{J}=d$, we can apply Lemma 1 to see that
$(\mu|_{L})^{-1}(0)$ is of complete intersection with $\dim=2|J|-d$. (In the
proof of Lemma 1, we only use the fact that $\mathrm{rank}\>A=d$.) Since
$(\mu|_{L})^{-1}(0)=(\mu^{-1}(0))_{J}$, we have
$\dim\>(\mu^{-1}(0))^{\alpha-s}_{J}=\dim\>(\mu^{-1}(0))_{J}=2|J|-d$. The
second equality follows from the fact that every point
$\mathbf{x}\in(\mu^{-1}(0))^{\alpha-s}_{J}$ has a finite stabilizer subgroup
of $T^{d}$. $\square$

Return to the proof (1) $\Rightarrow$ (2). Assume that
$\mathrm{Codim}_{Y(A,\alpha)}\mathrm{Sing}\>Y(A,\alpha)=2$ for a generic
$\alpha$. Then, by Claim 3, there is a $J$ such that $|J|=n-1$ and
$(\mu^{-1}(0))^{\alpha-s}_{J}\neq\emptyset$. If we put
$j_{0}=\\{1,2,...,n\\}-J$, then this $j_{0}$ satisfies the condition of (2).

(2) $\Rightarrow$ (1): We may assume $j_{0}=n$ without loss of generality.
Restrict the moment map $\mu$ to the $2n-2$-dimensional subspace
$\mathbf{C}^{2n-2}:=\\{(z_{1},...,z_{n-1},0,w_{1},...,w_{n-1},0)\\}$ of
$\mathbf{C}^{2n}$. Then

$\mu|_{\mathbf{C}^{2n-2}}:\mathbf{C}^{2n-2}\to\mathbf{C}^{d}$

is given by

$(z_{1},...,z_{n-1},w_{1},...,w_{n-1})\to\sum_{1\leq j\leq
n-1}\mathbf{a}_{j}z_{j}w_{j}.$

Since $\mathrm{rank}\>(\mathbf{a}_{1},...,\mathbf{a}_{n-1})=d$, we have
$\dim(\mu|_{\mathbf{C}^{2n-2}})^{-1}(0)=2n-2-d$ by Lemma 1. In other words,
$\dim(\mu^{-1}(0)\cap\\{z_{n}=w_{n}=0\\})=2n-2-d$. Let $\alpha\in M$ be a
generic element. To prove that
$\mathrm{Codim}_{Y(A,\alpha)}\mathrm{Sing}(Y(A,\alpha))=2$, it suffices to
show that $(\mu^{-1}(0))^{\alpha-s}\cap\\{z_{n}=w_{n}=0\\})\neq\emptyset.$ In
fact, if $(\mu^{-1}(0))^{\alpha-s}\cap\\{z_{n}=w_{n}=0\\})\neq\emptyset$, then
$(\mu^{-1}(0))^{\alpha-s}\cap\\{z_{n}=w_{n}=0\\})$ is a non-empty open subset
of $\mu^{-1}(0)\cap\\{z_{n}=w_{n}=0\\}$, which has dimension $2n-2-d$. Since
$\mathrm{rank}\>(\mathbf{a}_{1},...,\mathbf{a}_{n-1})=d$, we can take a
sufficiently large positive integer $N$ so that $N\alpha$ can be written as

$N\alpha=d_{1}\mathbf{a}_{1}+\cdot\cdot\cdot+d_{n-1}\mathbf{a}_{n-1}\>\>(d_{i}\in\mathbf{Z})$

We put

$J:=\\{j\>|\>1\leq j\leq n-1,\>d_{j}>0\\},\>\>J^{\prime}:=\\{j\>|\>1\leq j\leq
n-1,\>d_{j}<0\\},$ $K:=\\{j\>|\>1\leq j\leq n-1,\>d_{j}=0\\}.$

Take $\mathbf{x}=(z_{1},...,z_{n-1},0,w_{1},...,w_{n-1},0)$ so that

  * •

for $j\in J$, $z_{j}\neq 0$ and $w_{j}=0$

  * •

for $j\in J^{\prime}$, $z_{j}=0$ and $w_{j}\neq 0$

  * •

for $j\in K$, $z_{j}\neq 0$ and $w_{j}=0$

Since $z_{j}w_{j}=0$ for all $j$ with $1\leq j\leq n-1$, we have
$\mathbf{x}\in\mu^{-1}(0)$. Moreover, if we put

$f:=\prod_{j\in J}z_{j}^{d_{j}}\prod_{j\in J^{\prime}}w_{j}^{-d_{j}},$

then $f\in\mathbf{C}[z_{1},...,z_{n},w_{1},...,w_{n}]_{N\alpha}$ and
$f(\mathbf{x})\neq 0$. This means that $\mathbf{x}\in\mu^{-1}(0)^{\alpha-ss}$.
Since $\alpha$ is generic, this also means that
$\mathbf{x}\in\mu^{-1}(0)^{\alpha-s}$. Therefore,
$\mathbf{x}\in\mu^{-1}(0)^{\alpha-s}\cap\\{z_{n}=w_{n}=0\\}$; hence,
$(\mu^{-1}(0))^{\alpha-s}\cap\\{z_{n}=w_{n}=0\\})\neq\emptyset.$ $\square$

§2.

(2.1) We study in details a matrix $A$ satisfying the condition (2) of
Proposition 2. Let $A$ and $B$ be integer valued matrices of size $d\times n$
and $n\times(n-d)$ with an exact sequence

$0\to\mathbf{Z}^{n-d}\stackrel{{\scriptstyle
B}}{{\to}}\mathbf{Z}^{n}\stackrel{{\scriptstyle A}}{{\to}}\mathbf{Z}^{d}\to
0.$

Let us consider two conditions respectively on $A$ and $B$:

($\sharp_{A}$): Writing $A=(\mathbf{a}_{1},\mathbf{a}_{2},...,\mathbf{a}_{n})$
with the column vectors, the $d\times(n-1)$-matrix
$\bar{A}=(\mathbf{a}_{2},...,\mathbf{a}_{n})$ satisfies

(a) $\mathrm{rank}\>\bar{A}=d$, and

(b) the homomorphism
$\mathbf{Z}^{n-1}\stackrel{{\scriptstyle\bar{A}}}{{\to}}\mathbf{Z}^{d}$ is not
surjective.

($\sharp_{B}$): Writing

$B=\left(\begin{array}[]{ccccccc}\mathbf{b}_{1}\\\ \mathbf{b}_{2}\\\ ...\\\
\mathbf{b}_{n}\end{array}\right)\>\>\mathrm{with}\>\>\mathrm{row}\>\>\mathrm{vectors}\>\>\\{\mathbf{b_{i}}\\},$

the 1-st row vector $\mathbf{b}_{1}$ is not a primitive vector with
$\mathbf{b}_{1}\neq 0$.

Proposition 4. $A$ satisfies ($\sharp_{A}$) if and only if $B$ satisfies
($\sharp_{B}$).

Before proving Proposition 4, we prepare a technical lemma, which will be also
used in the proof of Lemma 6.

Lemma 5. Assume that $A$ satisfies ($\sharp_{A}$). If necessary, replacing $A$
by $PA$ with an invertible integer valued matrix $P$ of size $d\times d$, we
may assume that $A$ has the following form

$A=\left(\begin{array}[]{cccccccc}a_{11}&ma_{12}&...&ma_{1n}\\\
a_{21}&a_{22}&...&a_{2n}\\\ ...&...&...&...\\\
a_{d1}&a_{d2}&...&a_{dn}\end{array}\right)$

Here $m$ and $a_{ij}$ are both integers, $m>1$ and $GCD(a_{11},m)=1$.
Moreover, we may assume that the matrix

$\left(\begin{array}[]{cccccccc}1&a_{12}&...&a_{1n}\\\ 0&a_{22}&...&a_{2n}\\\
...&...&...&...\\\ 0&a_{d2}&...&a_{dn}\end{array}\right)$

determines a surjection $\mathbf{Z}^{n}\to\mathbf{Z}^{d}$.

Proof. Since $\mathrm{rank}\>\bar{A}=d$, we can take an invertible $d\times
d$-matrix $P$ and an invertible $(n-1)\times(n-1)$-matrix $Q$ so that

$P\bar{A}Q=\left(\begin{array}[]{ccccccc}m_{1}&&&&0&...&0\\\
&m_{2}&&&0&...&0\\\ &&...&&0&...&0\\\ &&&m_{d}&0&...&0\end{array}\right),$

where all $m_{i}$ are positive integers. Moreover, $m_{1}>1$ and each $m_{i}$
is a divisor of $m_{i-1}$. Then we have

$PA\left(\begin{array}[]{cc}1&\mathbf{0}\\\
\mathbf{0}&Q\end{array}\right)=P\cdot(\mathbf{a}_{1},\bar{A})\cdot\left(\begin{array}[]{cc}1&\mathbf{0}\\\
\mathbf{0}&Q\end{array}\right)=\left(\begin{array}[]{cccccccc}a^{\prime}_{11}&m_{1}&&&&0&...&0\\\
a^{\prime}_{21}&&m_{2}&&&0&...&0\\\ ...&&&...&&0&...&0\\\
a^{\prime}_{d1}&&&&m_{d}&0&...&0\end{array}\right),$

where

$\left(\begin{array}[]{cccccc}a^{\prime}_{11}\\\ a^{\prime}_{21}\\\ ...\\\
a^{\prime}_{d1}\end{array}\right)=P\mathbf{a}_{1}.$

By assumption, the homomorphism $\mathbf{Z}^{n}\to\mathbf{Z}^{d}$ determined
by

$PA\left(\begin{array}[]{cc}1&\mathbf{0}\\\ \mathbf{0}&Q\end{array}\right)$

is a surjection. It follows from this fact that
$m_{2}=\cdot\cdot\cdot=m_{d}=1$ and $GCD(a^{\prime}_{11},m_{1})=1$. We next
write

$Q^{-1}=\left(\begin{array}[]{cc}Q^{\prime}\\\
Q^{\prime\prime}\end{array}\right)$

with a $d\times(n-1)$-matrix $Q^{\prime}$ and an $(n-d-1)\times n-1$-matrix
$Q^{\prime\prime}$. Then we get

$PA=\left(\begin{array}[]{cccccccc}a^{\prime}_{11}&m_{1}&&&&0&...&0\\\
a^{\prime}_{21}&&1&&&0&...&0\\\ ...&&&...&&0&...&0\\\
a^{\prime}_{d1}&&&&1&0&...&0\end{array}\right)\cdot\left(\begin{array}[]{cc}1&\mathbf{0}\\\
\mathbf{0}&Q^{-1}\end{array}\right)$

$=\left(\begin{array}[]{cccccc}a^{\prime}_{11}\\\ a^{\prime}_{21}\\\ ...\\\
a^{\prime}_{d1}\end{array}\left(\begin{array}[]{cccccccc}m_{1}&&&\\\ &1&&\\\
&&...&\\\ &&&1\end{array}\right)Q^{\prime}\right)$

Here we can write

$\left(\begin{array}[]{cccccccc}m_{1}&&&\\\ &1&&\\\ &&...&\\\
&&&1\end{array}\right)Q^{\prime}=\left(\begin{array}[]{cccccccc}m_{1}a^{\prime}_{12}&...&m_{1}a^{\prime}_{1n}\\\
a^{\prime}_{22}&...&a^{\prime}_{2n}\\\ ...&...&...\\\
a^{\prime}_{d2}&...&a^{\prime}_{dn}\end{array}\right)$

with suitable integers $a^{\prime}_{ij}$. Then

$PA=\left(\begin{array}[]{cccccccc}a^{\prime}_{11}&m_{1}a^{\prime}_{12}&...&m_{1}a^{\prime}_{1n}\\\
a^{\prime}_{21}&a^{\prime}_{22}&...&a^{\prime}_{2n}\\\ ...&...&...&...\\\
a^{\prime}_{d1}&a^{\prime}_{d2}&...&a^{\prime}_{dn}\end{array}\right).$

This calculation also shows that

$\left(\begin{array}[]{cccccccc}1&m_{1}&&&&0&...&0\\\ 0&&1&&&0&...&0\\\
...&&&...&&0&...&0\\\
0&&&&1&0&...&0\end{array}\right)\cdot\left(\begin{array}[]{cc}1&\mathbf{0}\\\
\mathbf{0}&Q^{-1}\end{array}\right)=\left(\begin{array}[]{cccccccc}1&m_{1}a^{\prime}_{12}&...&m_{1}a^{\prime}_{1n}\\\
0&a^{\prime}_{22}&...&a^{\prime}_{2n}\\\ ...&...&...&...\\\
0&a^{\prime}_{d2}&...&a^{\prime}_{dn}\end{array}\right)$

Since

$\left(\begin{array}[]{cccccccc}1&m_{1}&&&&0&...&0\\\ 0&&1&&&0&...&0\\\
...&&&...&&0&...&0\\\ 0&&&&1&0&...&0\end{array}\right)$

determines a surjection $\mathbf{Z}^{n}\to\mathbf{Z}^{d}$,

$\left(\begin{array}[]{cccccccc}1&m_{1}a^{\prime}_{12}&...&m_{1}a^{\prime}_{1n}\\\
0&a^{\prime}_{22}&...&a^{\prime}_{2n}\\\ ...&...&...&...\\\
0&a^{\prime}_{d2}&...&a^{\prime}_{dn}\end{array}\right)$

also determines a surjection $\mathbf{Z}^{n}\to\mathbf{Z}^{d}$. By elementary
transformations of column vectors, this matrix can be transformed to the
matrix

$\left(\begin{array}[]{cccccccc}1&a^{\prime}_{12}&...&a^{\prime}_{1n}\\\
0&a^{\prime}_{22}&...&a^{\prime}_{2n}\\\ ...&...&...&...\\\
0&a^{\prime}_{d2}&...&a^{\prime}_{dn}\end{array}\right).$

Hence this matrix also determines a surjection
$\mathbf{Z}^{n}\to\mathbf{Z}^{d}$. $\square$

Proof of Proposition 4. Assume that $A$ satisfies ($\sharp_{A}$). We may
assume that $A$ has the form in Lemma 5. If the 1-st row vector
$\mathbf{b}_{1}$ of $B$ is zero, then

$AB=\bar{A}\left(\begin{array}[]{cccccccc}\mathbf{b}_{2}\\\ ...\\\ ...\\\
\mathbf{b}_{n}\end{array}\right)=0$

. Since $\mathrm{rank}(\bar{A})=d$,

$\mathrm{we}\>\>\mathrm{have}\>\>\mathrm{rank}\left(\begin{array}[]{cccccccc}\mathbf{b}_{2}\\\
...\\\ ...\\\
\mathbf{b}_{n}\end{array}\right)=n-1-d,\>\>\mathrm{which}\>\>\mathrm{means}\>\>\mathrm{that}\>\>\mathrm{rank}(B)=n-1-d.$

This is a contradiction. Hence $\mathbf{b}_{1}\neq 0$. The first row vector of
$AB$ is then

$(a_{11}b_{11}+m(a_{12}b_{21}+\cdot\cdot\cdot),a_{11}b_{12}+m(a_{12}b_{22}+\cdot\cdot\cdot),...,a_{11}b_{1,n-d}+m(a_{12}b_{2,n-d}+\cdot\cdot\cdot))$

which must be zero. Since $GCD(a_{11},m)=1$, $m$ must divide $b_{1j}$ for any
$j$. Therefore $B$ satisfies ($\sharp_{B}$).

We prove the converse implication. Assume that $B$ satisfies ($\sharp_{B}$).
Let us prove that $A$ satisfies (a) of ($\sharp_{A}$). Suppose to the contrary
that $\mathrm{rank}(\bar{A})\leq d-1$. Since $\mathrm{rank}(A)=d$,
$\mathrm{rank}(\bar{A})=d-1$. Then

$\mathrm{Ker}[\mathbf{Z}^{n-1}\stackrel{{\scriptstyle\bar{A}}}{{\to}}\mathbf{Z}^{d}]$

is a free abelian group of rank $n-d$. We take a generator

$\left(\begin{array}[]{cccccccc}b^{\prime}_{21}\\\ ...\\\ ...\\\
b^{\prime}_{n1}\end{array}\right),\cdot\cdot\cdot,\left(\begin{array}[]{cccccccc}b^{\prime}_{2,n-d}\\\
...\\\ ...\\\
b^{\prime}_{n,n-d}\end{array}\right)\>\>\mathrm{of}\>\>\mathrm{this}\>\>\mathrm{group},\mathrm{and}\>\>\mathrm{put}\>\>B^{\prime}:=\left(\begin{array}[]{cccccccc}0&...&0\\\
b^{\prime}_{21}&...&b^{\prime}_{2,n-d}\\\ ...&...&...\\\
b^{\prime}_{n1}&...&b^{\prime}_{n,n-d}\end{array}\right).$

Then $\mathrm{rank}(B^{\prime})=n-d$ and $AB^{\prime}=0$. This menas that
$\mathrm{Im}(B)/\mathrm{Im}(B^{\prime})$ is a torsion group. By the condition
($\sharp_{B}$), $b_{1j}\neq 0$ for some $j$. Then

$\left(\begin{array}[]{cccccccc}b_{1,j}\\\ ...\\\ ...\\\
b_{n,j}\end{array}\right)\in\mathrm{Im}(B).\>\>\mathrm{Then}\>\>\mathrm{there}\>\>\mathrm{is}\>\>\mathrm{a}\>\>\mathrm{positive}\>\>\mathrm{integer}\>\>N\>\>\mathrm{such}\>\>\mathrm{that}\>\>N\left(\begin{array}[]{cccccccc}b_{1,j}\\\
...\\\ ...\\\ b_{n,j}\end{array}\right)\in\mathrm{Im}(B^{\prime}).$

But this is absurd because $Nb_{1j}\neq 0$. We next prove that $A$ satisfies
(b) of ($\sharp_{A}$). Assume, to the contrary, that $\bar{A}$ is a
surjection. Consider the linear equation

$(\mathbf{a}_{1},\bar{A})\left(\begin{array}[]{cccccccc}1\\\ x_{2}\\\ ...\\\
x_{n}\end{array}\right)=\mathbf{a}_{1}+\bar{A}\left(\begin{array}[]{cccccccc}x_{2}\\\
...\\\ ...\\\ x_{n}\end{array}\right)=0$

Since $\bar{A}$ is a surjection, this equation has a solution, say

$\left(\begin{array}[]{cccccccc}c_{2}\\\ ...\\\ ...\\\
c_{n}\end{array}\right).\>\>\mathrm{Then}\>\>\mathbf{c}=\left(\begin{array}[]{cccccccc}1\\\
c_{2}\\\ ...\\\ ...\\\ c_{n}\end{array}\right)\in\mathrm{Ker}(A).$

By assumption, the first row vector $\mathbf{b}_{1}$ of $B$ is not primitive.
This menas that, there is an integer $m$ with $m>1$ such that, for any
$\mathbf{c}\in\mathrm{Ker}(A)$, $m$ divides $c_{1}$. This is a contradiction.
$\square$

(2.2) For the matrix $A$ in Lemma 5, we introduce a new matrix $A^{\prime}$ of
size $(d+m-1)\times(n+m-1)$

$A^{\prime}:=\left(\begin{array}[]{ccccccccccc}a_{11}&0&...&...&...&0&a_{12}&a_{13}&...&a_{1n}\\\
a_{21}&a_{21}&...&...&...&a_{21}&a_{22}&a_{23}&...&a_{2n}\\\
...&...&...&...&...&...&...&...&...&...\\\
a_{d1}&a_{d1}&...&...&...&a_{d1}&a_{d2}&a_{d3}&...&a_{dn}\\\
1&-1&&&&&0&0&...&0\\\ &1&-1&&&&0&0&...&0\\\ &&&...&&&...&...&...&...\\\
&&&&1&-1&0&0&...&0\end{array}\right)$

Lemma 6. $A^{\prime}$ determines a surjection
$\mathbf{Z}^{n+m-1}\to\mathbf{Z}^{d+m-1}$.

Proof. By assumption the homomorphism $\mathbf{Z}^{n}\stackrel{{\scriptstyle
A}}{{\to}}\mathbf{Z}^{d}$ is a surjection. Hence, one can find a vector

$\left(\begin{array}[]{cccc}c_{1}\\\ c_{2}\\\ ...\\\
c_{n}\end{array}\right)\>\>\>\mathrm{such}\>\>\mathrm{that}\>\>\>\left(\begin{array}[]{cccccccc}a_{11}&ma_{12}&...&ma_{1n}\\\
a_{21}&a_{22}&...&a_{2n}\\\ ...&...&...&...\\\
a_{d1}&a_{d2}&...&a_{dn}\end{array}\right)\left(\begin{array}[]{cccc}c_{1}\\\
c_{2}\\\ ...\\\ c_{n}\end{array}\right)=\left(\begin{array}[]{cccc}1\\\ 0\\\
...\\\ 0\end{array}\right).$

Then we have

$\left(\begin{array}[]{ccccccccccc}a_{11}&0&...&...&...&0&a_{12}&a_{13}&...&a_{1n}\\\
a_{21}&a_{21}&...&...&...&a_{21}&a_{22}&a_{23}&...&a_{2n}\\\
...&...&...&...&...&...&...&...&...&...\\\
a_{d1}&a_{d1}&...&...&...&a_{d1}&a_{d2}&a_{d3}&...&a_{dn}\\\
1&-1&&&&&0&0&...&0\\\ &1&-1&&&&0&0&...&0\\\ &&&...&&&...&...&...&...\\\
&&&&1&-1&0&0&...&0\end{array}\right)\left(\begin{array}[]{ccccccc}c_{1}\\\
c_{1}\\\ ...\\\ c_{1}\\\ mc_{2}\\\ ...\\\
mc_{n}\end{array}\right)=\left(\begin{array}[]{ccccccc}1\\\ 0\\\ ...\\\ ...\\\
...\\\ ...\\\ 0\end{array}\right).$

We next take a vector

$\left(\begin{array}[]{cccc}d_{1}\\\ d_{2}\\\ ...\\\
d_{n}\end{array}\right)\>\>\>\mathrm{such}\>\>\mathrm{that}\>\>\>\left(\begin{array}[]{cccccccc}a_{11}&ma_{12}&...&ma_{1n}\\\
a_{21}&a_{22}&...&a_{2n}\\\ ...&...&...&...\\\
a_{d1}&a_{d2}&...&a_{dn}\end{array}\right)\left(\begin{array}[]{cccc}d_{1}\\\
d_{2}\\\ ...\\\ d_{n}\end{array}\right)=\left(\begin{array}[]{cccc}0\\\ 1\\\
...\\\ 0\end{array}\right).$

Then we have

$\left(\begin{array}[]{ccccccccccc}a_{11}&0&...&...&...&0&a_{12}&a_{13}&...&a_{1n}\\\
a_{21}&a_{21}&...&...&...&a_{21}&a_{22}&a_{23}&...&a_{2n}\\\
...&...&...&...&...&...&...&...&...&...\\\
a_{d1}&a_{d1}&...&...&...&a_{d1}&a_{d2}&a_{d3}&...&a_{dn}\\\
1&-1&&&&&0&0&...&0\\\ &1&-1&&&&0&0&...&0\\\ &&&...&&&...&...&...&...\\\
&&&&1&-1&0&0&...&0\end{array}\right)\left(\begin{array}[]{ccccccc}d_{1}\\\
0\\\ ...\\\ 0\\\ d_{2}\\\ ...\\\ ...\\\
d_{n}\end{array}\right)=\left(\begin{array}[]{cccccccccc}*\\\ 1\\\ 0\\\ ...\\\
0\\\ d_{1}\\\ 0\\\ ...\\\ 0\end{array}\right).$

$\mathrm{Since}\>\>\left(\begin{array}[]{ccccccc}1\\\ 0\\\ ...\\\ ...\\\
...\\\ ...\\\ ...\\\ ...\\\
0\end{array}\right),\left(\begin{array}[]{cccccccccc}*\\\ 1\\\ 0\\\ ...\\\
0\\\ d_{1}\\\ 0\\\ ...\\\
0\end{array}\right)\in\mathrm{Im}(A^{\prime}),\>\>\mathrm{we}\>\>\mathrm{see}\>\>\mathrm{that}\>\>\left(\begin{array}[]{cccccccccc}0\\\
1\\\ 0\\\ ...\\\ 0\\\ d_{1}\\\ 0\\\ ...\\\
0\end{array}\right)\in\mathrm{Im}(A^{\prime}).$
$\mathrm{Similarly},\>\>\mathrm{we}\>\>\mathrm{see}\>\>\mathrm{that}\>\>\mathrm{Im}(A^{\prime})\>\>\mathrm{contains}\>\>\mathrm{the}\>\>\mathrm{vectors}\>\>\mathrm{of}\>\>\mathrm{the}\>\>\mathrm{form}\>\>\left(\begin{array}[]{cccccccccc}0\\\
0\\\ 1\\\ ...\\\ 0\\\ \\\ 0\\\ ...\\\
0\end{array}\right),\cdot\cdot\cdot,\left(\begin{array}[]{cccccccccc}0\\\ 0\\\
...\\\ 0\\\ 1\\\ \\\ 0\\\ ...\\\ 0\end{array}\right).$

Recall that

$\left(\begin{array}[]{cccccccc}1&a_{12}&...&a_{1n}\\\ 0&a_{22}&...&a_{2n}\\\
...&...&...&...\\\ 0&a_{d2}&...&a_{dn}\end{array}\right)$

determines a surjection $\mathbf{Z}^{n}\to\mathbf{Z}^{d}$. Hence we can write

$\left(\begin{array}[]{cccccccccc}0\\\ a_{21}\\\ ...\\\
a_{d1}\end{array}\right)=\lambda_{1}\left(\begin{array}[]{cccccccccc}1\\\ 0\\\
...\\\
0\end{array}\right)+\lambda_{2}\left(\begin{array}[]{cccccccccc}a_{12}\\\
...\\\ ...\\\
a_{d2}\end{array}\right)+\cdot\cdot\cdot+\lambda_{n}\left(\begin{array}[]{cccccccccc}a_{1n}\\\
....\\\ ...\\\
a_{dn}\end{array}\right)\>\>\mathrm{with}\>\>\lambda_{i}\in\mathbf{Z}$

Therefore we have

$\left(\begin{array}[]{cccccccccc}0\\\ a_{21}\\\ ...\\\ a_{d1}\\\ 0\\\ ...\\\
0\end{array}\right)=\lambda_{1}\left(\begin{array}[]{cccccccccc}1\\\ 0\\\
...\\\ 0\\\ 0\\\ ...\\\
0\end{array}\right)+\lambda_{2}\left(\begin{array}[]{cccccccccc}a_{12}\\\
...\\\ ...\\\ a_{d2}\\\ 0\\\ ...\\\
0\end{array}\right)+\cdot\cdot\cdot+\lambda_{n}\left(\begin{array}[]{cccccccccc}a_{1n}\\\
....\\\ ...\\\ a_{dn}\\\ 0\\\ ...\\\ 0\end{array}\right).$

$\mathrm{Since}\>\>\left(\begin{array}[]{cccccccccc}1\\\ 0\\\ ...\\\ 0\\\ 0\\\
...\\\ 0\end{array}\right),\left(\begin{array}[]{cccccccccc}a_{12}\\\ ...\\\
...\\\ a_{d2}\\\ 0\\\ ...\\\
0\end{array}\right),\cdot\cdot\cdot,\left(\begin{array}[]{cccccccccc}a_{1n}\\\
....\\\ ...\\\ a_{dn}\\\ 0\\\ ...\\\
0\end{array}\right)\in\mathrm{Im}(A^{\prime}),\>\>\mathrm{we}\>\>\mathrm{see}\>\>\mathrm{that}\>\>\left(\begin{array}[]{cccccccccc}0\\\
a_{21}\\\ ...\\\ a_{d1}\\\ 0\\\ ...\\\
0\end{array}\right)\in\mathrm{Im}(A^{\prime}).$
$\mathrm{Since}\>\>\left(\begin{array}[]{cccccccccc}0\\\ ...\\\ ...\\\ 0\\\
-1\\\ 1\\\ 0\\\ ...\\\
0\end{array}\right)=\left(\begin{array}[]{cccccccccc}0\\\ a_{21}\\\ ...\\\
a_{d1}\\\ -1\\\ 1\\\ 0\\\ ...\\\
0\end{array}\right)-\left(\begin{array}[]{cccccccccc}0\\\ a_{21}\\\ ...\\\
a_{d1}\\\ 0\\\ ...\\\ ...\\\ ...\\\
0\end{array}\right)\>\>\mathrm{and}\>\>\left(\begin{array}[]{cccccccccc}0\\\
a_{21}\\\ ...\\\ a_{d1}\\\ -1\\\ 1\\\ 0\\\ ...\\\
0\end{array}\right)\in\mathrm{Im}(A^{\prime}),\>\>\left(\begin{array}[]{cccccccccc}0\\\
...\\\ ...\\\ 0\\\ -1\\\ 1\\\ 0\\\ ...\\\
0\end{array}\right)\in\mathrm{Im}(A^{\prime}).$
$\mathrm{Similary}\>\>\mathrm{we}\>\>\mathrm{see}\>\>\mathrm{that}\left(\begin{array}[]{cccccccccc}0\\\
...\\\ ...\\\ 0\\\ 0\\\ -1\\\ 1\\\ 0\\\ 0\\\ ...\\\
0\end{array}\right),\left(\begin{array}[]{cccccccccc}0\\\ ...\\\ ...\\\ 0\\\
0\\\ 0\\\ -1\\\ 1\\\ 0\\\ ...\\\
0\end{array}\right),\cdot\cdot\cdot,\left(\begin{array}[]{cccccccccc}0\\\
...\\\ ...\\\ 0\\\ 0\\\ 0\\\ 0\\\ 0\\\ 0\\\ ...\\\
-1\end{array}\right)\in\mathrm{Im}(A^{\prime}).$

Now let us consider the $(d+m-1)\times(d+m-1)$-matrix

$\left(\begin{array}[]{cccccccccccc}1&0&...&...&0&0&0&...&...&...&0\\\
0&1&...&...&0&0&0&...&...&...&0\\\
...&0&...&...&...&...&...&...&...&...&...\\\
...&...&...&...&...&...&...&...&...&...&...\\\
...&0&...&...&1&0&0&...&...&...&0\\\ ...&*&...&...&*&-1&0&...&...&...&0\\\
...&0&...&...&0&1&-1&...&...&...&0\\\ ...&...&...&...&...&0&1&...&...&...&0\\\
...&...&...&...&...&...&0&...&...&...&...\\\
...&...&...&...&...&...&...&...&...&...&0\\\
0&0&...&...&0&0&0&...&...&...&-1\end{array}\right)$

whose column vectors are all contained in $\mathrm{Im}(A^{\prime})$. Then its
determinant is $(-1)^{m-1}$, which implies the lemma. $\square$

By Proposition 4, we can take

$B=\left(\begin{array}[]{cccccccc}mb_{11}&mb_{12}&...&mb_{1,n-d}\\\
b_{21}&b_{22}&...&b_{2,n-d}\\\ ...&...&...&...\\\
b_{n1}&b_{n2}&...&b_{n,n-d}\end{array}\right)\>\>\mathrm{with}\>\>m>1.$

Now we put

$B^{\prime}=\left(\begin{array}[]{cccccccc}b_{11}&b_{12}&...&b_{1,n-d}\\\
b_{11}&b_{12}&...&b_{1,n-d}\\\ ...&...&...&...\\\
b_{11}&b_{12}&...&b_{1,n-d}\\\ b_{21}&b_{22}&...&b_{2,n-d}\\\
...&...&...&...\\\ b_{n1}&b_{n2}&...&b_{n,n-d}\end{array}\right).$

Here $B^{\prime}$ is a $(n+m-1)\times(n-d)$-matrix and its first $m$ row
vectors are $(b_{11},b_{12},...,b_{1,n-d})$.

Lemma 7. The sequence

$0\to\mathbf{Z}^{n-d}\stackrel{{\scriptstyle
B^{\prime}}}{{\to}}\mathbf{Z}^{n+m-1}\stackrel{{\scriptstyle
A^{\prime}}}{{\to}}\mathbf{Z}^{d+m-1}\to 0$

is exact.

Proof. One can directly check that $A^{\prime}B^{\prime}=0$. It is enough to
show that $(B^{\prime})^{t}:\mathbf{Z}^{n+m-1}\to\mathbf{Z}^{n-d}$ is
surjective. Since $B^{t}:\mathbf{Z}^{n}\to\mathbf{Z}^{n-d}$ is surjective, we
see that $(B^{\prime})^{t}$ is also surjective by the definition of
$B^{\prime}$. $\square$

§3.

Let $A$ and $B$ be the matrices in Proposition 4; namely,

$A=\left(\begin{array}[]{cccccccc}a_{11}&ma_{12}&...&ma_{1n}\\\
a_{21}&a_{22}&...&a_{2n}\\\ ...&...&...&...\\\
a_{d1}&a_{d2}&...&a_{dn}\end{array}\right),\>\>\>B=\left(\begin{array}[]{cccccccc}mb_{11}&mb_{12}&...&mb_{1,n-d}\\\
b_{21}&b_{22}&...&b_{2,n-d}\\\ ...&...&...&...\\\
b_{n1}&b_{n2}&...&b_{n,n-d}\end{array}\right),$

where $m$ is an integer with $m>1$, and all $a_{ij}$, $b_{ij}$ are integers.
Consider the affine space $\mathbf{C}^{2n}$ with coordinates
$(z_{m},...,z_{n+m-1},w_{m},...,w_{n+m-1})$ and put

$\omega:=\sum_{m\leq i\leq n+m-1}dw_{i}\wedge dz_{i}.$

As in §1, the matrix $A$ determines a $T^{d}$ action on $\mathbf{C}^{2n}$ (the
coordinates suffixes being shifted) :

$(z_{m},...,z_{n+m-1},w_{m},...,w_{n+m-1})\to$
$(t_{1}^{a_{11}}t_{2}^{a_{21}}\cdot\cdot\cdot
t_{d}^{a_{d1}}z_{m},...,t_{1}^{ma_{1n}}t_{2}^{a_{2n}}\cdot\cdot\cdot
t_{d}^{a_{dn}}z_{n+m-1},t_{1}^{-a_{11}}t_{2}^{-a_{21}}\cdot\cdot\cdot
t_{d}^{-a_{d1}}w_{m},...,t_{1}^{-ma_{1n}}t_{2}^{-a_{2n}}\cdot\cdot\cdot
t_{d}^{-a_{dn}}w_{n+m-1})$

Let

$I=(i_{m+1},...,i_{n+m-1})\in\mathbf{Z}^{n-1}_{\geq
0},\>\>\mathrm{and}\>\>J:=(j_{m+1},...,j_{n+m-1})\in\mathbf{Z}^{n-1}_{\geq 0}$

be $(n-1)$-tuples of non-negative integers such that $i_{k}=0$ or $j_{k}=0$
for every $k$ with $m+1\leq k\leq n+m-1$. We then define

$(\mathbf{z}^{\prime})^{I}(\mathbf{w}^{\prime})^{J}:=z_{m+1}^{i_{m+1}}\cdot\cdot\cdot
z_{n+m-1}^{i_{n+m-1}}w_{m+1}^{j_{m+1}}\cdot\cdot\cdot w_{n+m-1}^{j_{n+m-1}}.$

Claim 8. We have an inclusion

$\mathbf{C}[z_{m},...,z_{n+m-1},w_{m},...,w_{n+m-1}]^{T^{d}}\subset\mathbf{C}[z_{m}^{m},w_{m}^{m},z_{m}w_{m},...,z_{n+m-1}w_{n+m-1},\\{(\mathbf{z}^{\prime})^{I}(\mathbf{w}^{\prime})^{J}\\}_{I,J}].$

Proof. For $(\lambda_{1},...,\lambda_{n-d})\in\mathbf{Z}^{n-d}$, we put

$\left(\begin{array}[]{cccccccc}\tau_{m}\\\ ...\\\ ...\\\
\tau_{n+m-1}\end{array}\right):=\lambda_{1}\left(\begin{array}[]{cccccccc}mb_{11}\\\
b_{21}\\\ ...\\\
b_{n1}\end{array}\right)+\cdot\cdot\cdot+\lambda_{n-d}\left(\begin{array}[]{cccccccc}mb_{1,n-d}\\\
b_{2,n-d}\\\ ...\\\ b_{n,n-d}\end{array}\right).$

Then the Laurent monomial $z_{m}^{\tau_{m}}\cdot\cdot\cdot
z_{n+m-1}^{\tau_{n+m-1}}$ is $T^{d}$-invariant. When $z_{j}^{\tau_{j}}$ with
$\tau_{j}<0$ appears in the Laurent monomial, substitute $w_{j}^{-\tau_{j}}$
for it. Then we get a $T^{d}$-invariant (usual) monomial of
$z_{m},...,z_{n+m-1},w_{m},...,w_{n+m-1}$. Such a monomial obtained in this
way has the form

$(z_{m}^{m})^{i}(\mathbf{z}^{\prime})^{I}(\mathbf{w}^{\prime})^{J}\>\>\mathrm{or}\>\>(w_{m}^{m})^{j}(\mathbf{z}^{\prime})^{I}(\mathbf{w}^{\prime})^{J}.\>\>\>(*)$

Conversely, the invariant ring
$\mathbf{C}[z_{m},...,z_{n+m-1},w_{m},...,w_{n+m-1}]^{T^{d}}$ is generated by
such monomials and $z_{m}w_{m}$, …, $z_{n+m-1}w_{n+m-1}$. Hence the claim
holds. $\square$

Let $A^{\prime}$ and $B^{\prime}$ be the matrices introduced in (2.2):

$A^{\prime}=\left(\begin{array}[]{ccccccccccc}a_{11}&0&...&...&...&0&a_{12}&a_{13}&...&a_{1n}\\\
a_{21}&a_{21}&...&...&...&a_{21}&a_{22}&a_{23}&...&a_{2n}\\\
...&...&...&...&...&...&...&...&...&...\\\
a_{d1}&a_{d1}&...&...&...&a_{d1}&a_{d2}&a_{d3}&...&a_{dn}\\\
1&-1&&&&&0&0&...&0\\\ &1&-1&&&&0&0&...&0\\\ &&&...&&&...&...&...&...\\\
&&&&1&-1&0&0&...&0\end{array}\right),\>\>\>\>B^{\prime}=\left(\begin{array}[]{cccccccc}b_{11}&b_{12}&...&b_{1,n-d}\\\
b_{11}&b_{12}&...&b_{1,n-d}\\\ ...&...&...&...\\\
b_{11}&b_{12}&...&b_{1,n-d}\\\ b_{21}&b_{22}&...&b_{2,n-d}\\\
...&...&...&...\\\ b_{n1}&b_{n2}&...&b_{n,n-d}\end{array}\right).$

Consider the affine space $\mathbf{C}^{2(n+m-1)}$ with coordinates
$(z_{1},...,z_{n+m-1},w_{1}...,w_{n+m-1})$ and put

$\omega^{\prime}:=\sum_{1\leq i\leq n+m-1}dw_{i}\wedge dz_{i}.$

As in §1, the matrix $A^{\prime}$ determines a $T^{d+m-1}$ action on
$\mathbf{C}^{2(n+m-1)}$. Then the moment map

$\mu^{\prime}:\mathbf{C}^{2(n+m-1)}\to\mathbf{C}^{d+m-1}$

is given by

$\left(\begin{array}[]{cccccccccc}z_{1}\\\ ...\\\ ...\\\ z_{n+m-1}\\\ w_{1}\\\
...\\\ ...\\\ ...\\\
w_{n+m-1}\end{array}\right)\to\left(\begin{array}[]{cccccccccc}a_{11}z_{1}w_{1}\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>+a_{12}z_{m+1}w_{m+1}+\cdot\cdot\cdot+a_{1n}z_{n+m-1}w_{n+m-1}\\\
a_{21}z_{1}w_{1}+\cdot\cdot\cdot+a_{21}z_{m}w_{m}+a_{22}z_{m+1}w_{m+1}+\cdot\cdot\cdot+a_{2n}z_{n+m-1}w_{n+m-1}\\\
...\\\
a_{d1}z_{1}w_{1}+\cdot\cdot\cdot+a_{d1}z_{m}w_{m}+a_{d2}z_{m+1}w_{m+1}+\cdot\cdot\cdot+a_{dn}z_{n+m-1}w_{n+m-1}\\\
z_{1}w_{1}-z_{2}w_{2}\\\ z_{2}w_{2}-z_{3}w_{3}\\\ ...\\\ ...\\\
z_{m-1}w_{m-1}-z_{m}w_{m}\end{array}\right)$

Define a $d$-dimensional subspace $L$ of $\mathbf{C}^{d+m-1}$ by

$L:=\\{(u_{1},...,u_{d+m-1})\in\mathbf{C}^{d+m-1}\>|\>u_{d+1}=\cdot\cdot\cdot=u_{d+m-1}=0\\}$

and consider the inverse image $(\mu^{\prime})^{-1}(L)$ of $L$ by
$\mu^{\prime}$. Since $(\mu^{\prime})^{*}u_{d+1}=z_{1}w_{1}-z_{2}w_{2}$, …,
$(\mu^{\prime})^{*}u_{d+m-1}=z_{m-1}w_{m-1}-z_{m}w_{m}$, we have

$\mathbf{C}[(\mu^{\prime})^{-1}(L)]=\mathbf{C}[z_{1},...,z_{n+m-1},w_{1},...,w_{n+m-1}]/(z_{1}w_{1}-z_{2}w_{2},...,z_{m-1}w_{m-1}-z_{m}w_{m}).$

Claim 9. The invariant ring $\mathbf{C}[(\mu^{\prime})^{-1}(L)]^{T^{d+m-1}}$
is a subring of

$\mathbf{C}[z_{1}z_{2}\cdot\cdot\cdot z_{m},\>\>\>w_{1}w_{2}\cdot\cdot\cdot
w_{m},\>\>\>z_{1}w_{1},...,z_{n+m-1}w_{n+m-1},\\{(\mathbf{z}^{\prime})^{I}(\mathbf{w}^{\prime})^{J}\\}_{I,J}]/(\\{z_{i}w_{i}-z_{i+1}w_{i+1}\\}_{1\leq
i\leq m-1})$

Proof. For $(\lambda_{1},...,\lambda_{n-d})\in\mathbf{Z}^{n-d}$, we put

$\left(\begin{array}[]{cccccccc}\tau_{1}\\\ ...\\\ ...\\\
\tau_{n+m-1}\end{array}\right):=\lambda_{1}\left(\begin{array}[]{cccccccc}b_{11}\\\
...\\\ b_{11}\\\ b_{21}\\\ ...\\\
b_{n1}\end{array}\right)+\cdot\cdot\cdot+\lambda_{n-d}\left(\begin{array}[]{cccccccc}b_{1,n-d}\\\
...\\\ b_{1,n-d}\\\ b_{2,n-d}\\\ ...\\\ b_{n,n-d}\end{array}\right).$

Then the Laurent monomial $z_{1}^{\tau_{1}}\cdot\cdot\cdot
z_{n+m-1}^{\tau_{n+m-1}}$ is $T^{d}$-invariant. When $z_{j}^{\tau_{j}}$ with
$\tau_{j}<0$ appears in the Laurent monomial, substitute $w_{j}^{-\tau_{j}}$
for it. Then we get a $T^{d}$-invariant (usual) monomial of
$z_{1},...,z_{n+m-1},w_{1},...,w_{n+m-1}$. Such a monomial obtained in this
way has the form

$(z_{1}z_{2}\cdot\cdot
z_{m})^{i}(\mathbf{z}^{\prime})^{I}(\mathbf{w}^{\prime})^{J}\>\>\mathrm{or}\>\>(w_{1}\cdot\cdot
w_{m})^{j}(\mathbf{z}^{\prime})^{I}(\mathbf{w}^{\prime})^{J}.\>\>\>\>(**)$

Conversely, the invariant ring
$\mathbf{C}[(\mu^{\prime})^{-1}(L)]^{T^{d+m-1}}$ is generated by such
monomials and $z_{1}w_{1}$, …, $z_{n+m-1}w_{n+m-1}$. Hence the claim holds.
$\square$

Remark 10. The triplets $(i,I,J)$, $(j,I,J)$ appeared in (**) coincide wth
those appeared in (*) in the proof of Claim 8 because of the choice of $B$ and
$B^{\prime}$.

Now let us consider a subring $R$ of
$\mathbf{C}[u,v,w,z_{m+1},...,z_{n+m-1},w_{m+1},...,w_{n+m-1}]/(uv-w^{m})$
defined by

$R:=\mathbf{C}[u,v,w,z_{m+1}w_{m+1},...,z_{n+m-1}w_{n+m-1},\\{(\mathbf{z}^{\prime})^{I}(\mathbf{w}^{\prime})^{J}\\}_{I,J}]/(uv-w^{m}).$

Then the ring

$\mathbf{C}[z_{1}z_{2}\cdot\cdot\cdot z_{m},\>\>\>w_{1}w_{2}\cdot\cdot\cdot
w_{m},\>\>\>z_{1}w_{1},...,z_{n+m-1}w_{n+m-1},\\{(\mathbf{z}^{\prime})^{I}(\mathbf{w}^{\prime})^{J}\\}_{I,J}]/(\\{z_{i}w_{i}-z_{i+1}w_{i+1}\\}_{1\leq
i\leq m-1})$

appeared in Claim 9 is identified with $R$ by putting
$u=m^{m}z_{1}z_{2}\cdot\cdot\cdot z_{m}$ and $v=w_{1}w_{2}\cdot\cdot\cdot
w_{m}$ and $w=mz_{m}w_{m}$.

On the other hand, the ring

$\mathbf{C}[z_{m}^{m},w_{m}^{m},z_{m}w_{m},...,z_{n+m-1}w_{n+m-1},\\{(\mathbf{z}^{\prime})^{I}(\mathbf{w}^{\prime})^{J}\\}_{I,J}]$

appeared in Claim 8 is also identified with $R$ by putting $u=z_{m}^{m}$,
$v=w_{m}^{m}$ and $w=z_{m}w_{m}$.

Therefore, these two rings are mutually identified via $R$. This
identification induces an isomorphism

$\phi^{*}:\mathbf{C}[z_{m},...,z_{n+m-1},w_{m},...,w_{n+m-1}]^{T^{d}}\to\mathbf{C}[(\mu^{\prime})^{-1}(L)]^{T^{d+m-1}}$

by Remark 10. Notice that $\phi^{*}(z_{m}w_{m})=mz_{m}w_{m}$ and
$\phi^{*}(z_{j}w_{j})=z_{j}w_{j}$ for $j\geq m+1$. The isomorphism $\phi^{*}$
induces an isomorphism

$\phi:(\mu^{\prime})^{-1}(L)//_{0}T^{d+m-1}\to\mathbf{C}^{2n}//_{0}T^{d}.$

Let $\mu:\mathbf{C}^{2n}\to\mathbf{C}^{d}$ be the moment map for
$(\mathbf{C}^{2n},\omega)$. Then $\mu$ induces a map
$\bar{\mu}:\mathbf{C}^{2n}//_{0}T^{d}\to\mathbf{C}^{d}$, which is given by

$\overline{\left(\begin{array}[]{cccccccccc}z_{m}\\\ ...\\\ ...\\\
z_{n+m-1}\\\ w_{m}\\\ ...\\\ ...\\\ ...\\\
w_{n+m-1}\end{array}\right)}\in\mathbf{C}^{2n}//_{0}T^{d}\to\left(\begin{array}[]{cccccccccc}a_{11}z_{m}w_{m}+ma_{12}z_{m+1}w_{m+1}+\cdot\cdot\cdot+ma_{1n}z_{n+m-1}w_{n+m-1}\\\
a_{21}z_{m}w_{m}+a_{22}z_{m+1}w_{m+1}+\cdot\cdot\cdot+a_{2n}z_{n+m-1}w_{n+m-1}\\\
...\\\ ...\\\ ...\\\
a_{d1}z_{m}w_{m}+a_{d2}z_{m+1}w_{m+1}+\cdot\cdot\cdot+a_{dn}z_{n+m-1}w_{n+m-1}\end{array}\right)$

On the other hand, $\mu^{\prime}$ induces a map
$\bar{\mu^{\prime}}_{L}:(\mu^{\prime})^{-1}(L)//_{0}T^{d+m-1}\to L$. Since
$z_{1}w_{1}=\cdot\cdot\cdot=w_{m}z_{m}$ on
$(\mu^{\prime})^{-1}(L)//_{0}T^{d+m-1}$, $\bar{\mu^{\prime}}_{L}$ is given by

$\overline{\left(\begin{array}[]{cccccccccc}z_{1}\\\ ...\\\ ...\\\
z_{n+m-1}\\\ w_{1}\\\ ...\\\ ...\\\ ...\\\
w_{n+m-1}\end{array}\right)}\to\left(\begin{array}[]{cccccccccc}a_{11}z_{m}w_{m}+a_{12}z_{m+1}w_{m+1}+\cdot\cdot\cdot+a_{1n}z_{n+m-1}w_{n+m-1}\\\
ma_{21}z_{m}w_{m}+a_{22}z_{m+1}w_{m+1}+\cdot\cdot\cdot+a_{2n}z_{n+m-1}w_{n+m-1}\\\
...\\\ ...\\\ ...\\\
ma_{d1}z_{m}w_{m}+a_{d2}z_{m+1}w_{m+1}+\cdot\cdot\cdot+a_{dn}z_{n+m-1}w_{n+m-1}\end{array}\right)$

Then we have a $\mathbf{C}^{*}$-equivariant commutative diagram

$\begin{CD}(\mu^{\prime})^{-1}(L)//_{0}T^{d+m-1}@>{\phi}>{}>\mathbf{C}^{2n}//_{0}T^{d}\\\
@V{\bar{\mu^{\prime}}_{L}}V{}V@V{\bar{\mu}}V{}V\\\
L@>{\bar{\phi}}>{}>\mathbf{C}^{d},\end{CD}$ (2)

where $\bar{\phi}$ is defined by
$(u_{1},u_{2},...,u_{d})\to(mu_{1},u_{2},...,u_{d})$. The horizontal maps
$\phi$ and $\bar{\phi}$ are both isomorphisms. There is a relative symplectic
form $\bar{\omega^{\prime}}$ (with respect to $\bar{\mu^{\prime}}$) on
$(\mu^{\prime})^{-1}(L)//_{0}T^{d+m-1}$. Then
$(\phi^{-1})^{*}\bar{\omega^{\prime}}$ is a relative symplectic 2-form with
respect to $\bar{\mu}$. Restrict $(\phi^{-1})^{*}\bar{\omega^{\prime}}$ to
$\bar{\mu}^{-1}(0)=Y(A,0)$. Then it is a symplectic form on $Y(A,0)$, which is
denoted by $\omega^{\prime}_{Y(A,0)}$. There is a natural symplectic form
$\omega_{Y(A,0)}$ on $Y(A,0)$ defined by $\omega$. Since both
$\omega_{Y(A,0)}$ and $\omega^{\prime}_{Y(A,0)}$ have weight $2$, by [Na 1,
Theorem 3.1], there is a $\mathbf{C}^{*}$-equivariant isomorphism of
symplectic varieties

$(Y(A,0),\omega_{Y(A,0)})\cong(Y(A,0),\omega^{\prime}_{Y(A,0)}).$

In particular, we have
$(Y(A,0),\omega_{Y(A,0)})\cong(\bar{\mu}^{-1}(0),\bar{\omega^{\prime}}|_{\bar{\mu}^{-1}(0)})$
and

$\bar{\mu^{\prime}}:\mathbf{C}^{2(m+n-1)}//_{0}T^{d+m-1}\to\mathbf{C}^{d+m-1}$

is regarded as a Poisson deformation of $(Y(A,0),\omega_{Y(A,0)})$.

Our strategy is as follows. Assume that
$\mathrm{Codim}_{Y(A,\alpha)}\mathrm{Sing}(Y(A,\alpha)=2$ for a generic
$\alpha$. Then we take $A_{1}:=A^{\prime}$ and consider $Y(A_{1},0)$. Then, as
we have seen above, $Y(A_{1},0)\cong Y(A,0)$. If $Y(A_{1},\alpha_{1})$ has
only quotient terminal singularities for a generic $\alpha_{1}$, then the
crepant partial resolution $Y(A_{1},\alpha_{1})\to Y(A_{1},0)$ gives a
Q-factorial terminalization of $Y(A,0)$. If
$\mathrm{Codim}_{Y(A_{1},\alpha_{1})}\mathrm{Sing}(Y(A_{1},\alpha_{1}))=2$,
then we put $A_{2}:=(A_{1})^{\prime}$ and consider $Y(A_{2},\alpha_{2})$ with
a generic $\alpha_{2}$, and so on. We claim that this operation eventually
terminates and we finally get $Y(A_{k},\alpha_{k})$ with only quotient
terminal singularities. When we take $A_{0}$, $A_{1}$, $A_{2}$, … starting
with $A_{0}:=A$, we have exact sequences

$0\to\mathbf{Z}^{n-d}\stackrel{{\scriptstyle
B_{i}}}{{\to}}\mathbf{Z}^{n+(m_{1}-1)+...+(m_{i}-1)}\stackrel{{\scriptstyle
A_{i}}}{{\to}}\mathbf{Z}^{d+(m_{1}-1)+...+(m_{i}-1)}\to 0\>\>\>(i=0,1,2...).$

What happens when we pass from $B_{i-1}$ to $B_{i}$ ? As we have seen in Lemma
7, some row vector of $B_{i-1}$ has the form
$(m_{i-1}b_{1},...,m_{i-1}b_{n-d})$. In $B_{i}$, it is broken into $m_{i-1}$
row vectors $(b_{1},...,b_{n-d})$. As long as there still exist a a non-
primitive row in $B_{i}$, the operation does not terminate because of
Proposition 4, and eventually all row vectors of $B_{i}$ become primitive at
some stage, say $i=k$. Then $Y(A_{k},\alpha_{k})$ must have quotient terminal
singularities again by Proposition 4. As a consequence, we have proved:

Theorem 11. For a toric hyperkähler variety $Y(A,0)$, we can take a suitable
matrix $A^{\sharp}$ so that

(1) $(Y(A,0),\omega_{Y(A,0)})\cong(Y(A^{\sharp},0),\omega_{Y(A^{\sharp},0)})$
as conical symplectic varieties, and

(2) $Y(A^{\sharp},\alpha^{\sharp})\to Y(A^{\sharp},0)$ is a Q-factorial
terminalization for a generic $\alpha^{\sharp}$.

Example 12. Let

$A={\left(\begin{array}[]{cccccccccc}1&0&-2&-2\\\
0&1&-3&-3\end{array}\right)}\>\>\mathrm{and}\>\>B={\left(\begin{array}[]{cccccccccc}2&2\\\
3&3\\\ 1&0\\\ 0&1\end{array}\right)}.$

These determine an exact sequence

$0\to\mathbf{Z}^{2}\stackrel{{\scriptstyle
B}}{{\to}}\mathbf{Z}^{4}\stackrel{{\scriptstyle A}}{{\to}}\mathbf{Z}^{2}\to
0.$

Since $A$ satisfies the conditions ($\sharp_{A}$) in Proposition 4, we have
$\mathrm{Codim}_{Y(A,\alpha)}\mathrm{Sing}(Y(A,\alpha))=2$ for a generic
$\alpha$. Accordng to (2.2), we introduce

$A^{\prime}:={\left(\begin{array}[]{cccccccccc}1&0&0&-1&-1\\\ 0&0&1&-3&-3\\\
1&-1&0&0&0\end{array}\right)}.$

Permute the 1-st column and the 3-rd column of $A^{\prime}$, and next permute
the 1-st row and the 2-nd row of the resulting matrix. Then we get

$A_{1}:={\left(\begin{array}[]{cccccccccc}1&0&0&-3&-3\\\ 0&1&0&-1&-1\\\
0&1&-1&0&0\end{array}\right)}.$

Then $A_{1}$ together with

$B_{1}:=\left(\begin{array}[]{cccccccccc}3&3\\\ 1&1\\\ 1&1\\\ 1&0\\\
0&1\end{array}\right)$

determines an exact sequence

$0\to\mathbf{Z}^{2}\stackrel{{\scriptstyle
B_{1}}}{{\to}}\mathbf{Z}^{5}\stackrel{{\scriptstyle
A_{1}}}{{\to}}\mathbf{Z}^{3}\to 0.$

The matrix ${A}_{1}$ still satisfies the conditions (a) and (b),
($\sharp_{A}$) in Proposition 4. We put

$A_{2}:=\left(\begin{array}[]{cccccccccc}1&0&0&0&0&-1&-1\\\ 0&0&0&1&0&-1&-1\\\
0&0&0&1&-1&0&0\\\ 1&-1&0&0&0&0&0\\\ 0&1&-1&0&0&0&0\end{array}\right).$

Then $A_{2}$ together with

$B_{2}:=\left(\begin{array}[]{cccccccccc}1&1\\\ 1&1\\\ 1&1\\\ 1&1\\\ 1&1\\\
1&0\\\ 0&1\end{array}\right)$

determines an exact sequence

$0\to\mathbf{Z}^{2}\stackrel{{\scriptstyle
B_{2}}}{{\to}}\mathbf{Z}^{7}\stackrel{{\scriptstyle
A_{2}}}{{\to}}\mathbf{Z}^{5}\to 0.$

Since $A_{2}$ is unimodular, $Y(A_{2},\alpha_{2})$ is nonsingular for a
generic $\alpha_{2}$. By construction, $Y(A,0)\cong Y(A_{1},0)\cong
Y(A_{2},0)$ and $Y(A_{2},\alpha_{2})$ gives a crepant resolution of $Y(A,0)$.
Notice that $\Sigma:=\mathrm{Sing}(Y(A,0))$ is irreducible and $\dim\Sigma=2$.
$Y(A,0)$ has $A_{4}$-singularities along $\Sigma-\\{\mathbf{0}\\}$. $\square$

§4.

Theorem 11 enables us to construct explicitly the universal Poisson
deformation of $(Y(A,0,),\omega_{Y(A,0)})$ for a toric hyperkähler variety
$Y(A,0)$. For general properties of Poisson deformations, see [Na 2], [Na 3].

(4.1) First we treat the case when $Y(A,\alpha)$ gives a Q-factorial
terminalization of $Y(A,0)$ for a generic $\alpha$. This is quite similar to
the case where $A$ is unimodular and $Y(A,\alpha)$ is a crepant resolution of
$Y(A,0)$ (cf. [BLPW, 9.3], [Nag, Theorem 3.1]). The moment map
$\mu:\mathbf{C}^{2n}\to\mathbf{C}^{d}$ induces a map
$\bar{\mu}_{\alpha}:X(A,\alpha)\to\mathbf{C}^{d}$ with
$\bar{\mu}_{\alpha}^{-1}(0)=Y(A,\alpha)$. $X(A,\alpha)$ is an orbifold, and
$\bar{\mu}_{\alpha}$ is a family of orbifolds. There is a
$\bar{\mu}_{\alpha}$-relative symplectic 2-form $\omega_{X(A,\alpha)}$ on the
orbifold $X(A,\alpha)$, which restricts to a symplectic 2-form
$\omega_{Y(A,\alpha)}$ on the orbifold $Y(A,\alpha)$. In particular,
$\omega_{X(A,\alpha)}$ determines a usual symplectic 2-form on the regualr
part $X(A,\alpha)_{reg}$, which induces a Poisson structure
$\\{\>\>,\>\>\\}_{X(A,\alpha)}$ on $X(A,\alpha)$. Similarly,
$\omega_{X(A,\alpha)}$ determines a Poisson structure
$\\{\>\>,\>\>\\}_{Y(A,\alpha)}$. The map $\bar{\mu}_{\alpha}$ is regarded as a
Poisson deformation of $(Y(A,\alpha),\\{\>\>,\>\>\\}_{Y(A,\alpha)})$.

$\begin{CD}Y(A,\alpha)@>{}>{}>X(A,\alpha)\\\
@V{}V{}V@V{\bar{\mu}_{\alpha}}V{}V\\\
0@>{}>{}>\mathbf{C}^{d}=(\mathbf{t}^{d})^{*}\end{CD}$ (3)

Each fber of $\bar{\mu}_{\alpha}$ is diffeomorphic (cf. [Ko 2, Proposition
3.6]), and $R^{2}(\bar{\mu}_{\alpha})_{*}\mathbf{C}$ is a constant sheaf of
rank $b_{2}(Y(A,\alpha))$. By using $\omega_{X(A,\alpha)}$, we get a period
map for $\bar{\mu}_{\alpha}$:

$p:\mathbf{C}^{d}\to
H^{2}(Y(A,\alpha),\mathbf{C})\>\>\>\>u\to[\omega_{X(A,\alpha)}|_{\bar{\mu}_{\alpha}^{-1}(u)}]$

Let us introduce a map $\kappa$ from $(\mathbf{t}^{d})^{*}$ to
$H^{2}(Y(A,0),\mathbf{C})$, called the Kirwan map. The quotient map
$\mu^{-1}(0)^{\alpha-s}\to Y(A,0)$ is an orbifold $T^{d}$-principal bundle. An
element $\lambda\in\mathrm{Hom}_{alg.gp}(T^{d},\mathbf{C}^{*})$ determines an
associated orbifold line bundle $L_{\lambda}$ on $Y(A,\alpha)$. We then have a
homomorphism

$\mathrm{Hom}_{alg.gp}(T^{d},\mathbf{C}^{*})\to
H^{2}(Y(A,\alpha),\mathbf{Q}),\>\>\>\lambda\to c_{1}(L_{\lambda}).$

This map naturally extends to the map from $(\mathbf{t}^{d})^{*}$ to
$H^{2}(Y(A,\alpha),\mathbf{C})$, which is the Kirwan map $\kappa$. The period
map $p$ coincides with $\kappa$ (cf. [DH], [Ko 2, Proposition 6.1, (2)], [Lo,
Proposition 3.2.1]). Moreover, the Kirwan map turns out to be an isomomorphism
if any row of the matrix $B$ is nonzero (cf. [Ko 2, Proposition 6.1, (1)]).
Therefore, $p$ is a linear isomorphism in our situation.

We next prove that $\bar{\mu}_{\alpha}$ is the universal Poisson deformation
of $Y(A,\alpha)$. Since $Y(A,0)^{an}$ has only rational singularities and
$Y(A,\alpha)^{an}$ is Stein, we have

$H^{i}(Y(A,\alpha)^{an},\mathcal{O}_{Y(A,\alpha)^{an}})=0\>\>\mathrm{for}\>\>i>0.$

Moreover, since
$\mathrm{Codim}_{Y(A,\alpha)^{an}}\mathrm{Sing}(Y(A,\alpha)^{an})\geq 4$ and
$Y(A,\alpha)^{an}$ is Cohen-Macaulay, we have
$H^{i}(Y(A,\alpha)^{an}_{reg},\mathcal{O}_{Y(A,\alpha)^{an}_{reg}})=0$ for
$i=1,2$ by the depth argument. By the exact sequences

$0\to\mathbf{Z}\to\mathcal{O}_{Y(A,\alpha)^{an}}\to\mathcal{O}^{*}_{Y(A,\alpha)^{an}}\to
1,$
$0\to\mathbf{Z}\to\mathcal{O}_{Y(A,\alpha)^{an}_{reg}}\to\mathcal{O}^{*}_{Y(A,\alpha)^{an}_{reg}}\to
1$

we have isomorphisms

$\mathrm{Pic}(Y(A,\alpha)^{an})\cong
H^{2}(Y(A,\alpha),\mathbf{Z})\>\>\mathrm{and}\>\>\mathrm{Pic}(Y(A,\alpha)^{an}_{reg})\cong
H^{2}(Y(A,\alpha)_{reg},\mathbf{Z}).$

On the other hand, we have
$\mathrm{Pic}(Y(A,\alpha)^{an})\otimes_{\mathbf{Z}}\mathbf{Q}\cong\mathrm{Pic}(Y(A,\alpha)^{an}_{reg})\otimes_{\mathbf{Z}}\mathbf{Q}$
because $Y(A,\alpha)$ has only quotient singularities. Therefore, the
restriction map

$H^{2}(Y(A,\alpha),\mathbf{Q})\to H^{2}(Y(A,\alpha)_{reg},\mathbf{Q})$

is an isomorphism. Since
$\mathrm{Codim}_{Y(A,\alpha)^{an}}\mathrm{Sing}(Y(A,\alpha)^{an})\geq 4$, the
1-st order Poisson deformations of $Y(A,\alpha)$ are controlled by
$H^{2}(Y(A,\alpha)_{reg},\mathbf{C})$. The Poisson deformation
$\bar{\mu}_{\alpha}$ determines the Poisson Kodaira-Spencer map

$\tau:T_{0}(\mathbf{C}^{d})\to H^{2}(Y(A,\alpha)_{reg},\mathbf{C})(\cong
H^{2}(Y(A,\alpha),\mathbf{C})),$

which conicides with the period map $p$. In particular, $\tau$ is an
isomorphism. This means that $\bar{\mu}_{\alpha}$ is the universal Poisson
deformation of $Y(A,\alpha)$.

(4.2) As in (4.1) we assume that $Y(A,\alpha)\to Y(A,0)$ is a Q-factorial
terminalization of $Y(A,0)$ for a generic $\alpha$. Let us consider $B$. By
Proposition 4, all row vectors of $B$ are primitive. We can assume that $B$
has the following form, after permuting the row vectors and changing their
signs if necessary.

$B:=\left(\begin{array}[]{cccccccccc}\mathbf{b}_{1}\\\ ...\\\
\mathbf{b}_{1}\\\ \mathbf{b}_{2}\\\ ...\\\ \mathbf{b}_{2}\\\ \mathbf{b}_{3}\\\
...\\\ \mathbf{b}_{3}\\\ ...\\\ ...\\\ ...\\\ \mathbf{b}_{r}\\\ ...\\\
\mathbf{b}_{r}\end{array}\right),$

where $\\{\mathbf{b}_{i}\\}$ are not mutually parallel, and each
$\mathbf{b}_{i}$ appears in $d_{i}$ times. Then, as in [BLPW, 9.3] and [Nag,
Theorem 3.11], the Weyl group $W$ of $Y(A,0)$ is isomorphic to
$\mathfrak{S}_{d_{1}}\times\cdot\cdot\cdot\times\mathfrak{S}_{d_{r}}$. The
product $\mathfrak{S}_{d_{1}}\times\cdot\cdot\cdot\times\mathfrak{S}_{d_{r}}$
is naturally a subgroup of $\mathfrak{S}_{d_{1}+d_{2}+...+d_{r}}$ where
$d_{1}+...+d_{r}=n$. Hence, an element of
$\mathfrak{S}_{d_{1}}\times\cdot\cdot\cdot\times\mathfrak{S}_{d_{r}}$ is
regarded as a permutation $\sigma$ of $\\{1,2,...,n\\}$. Then $\sigma\in W$
acts on $\mathbf{C}^{2n}$ by

$(z_{1},...,z_{n},w_{1},...,w_{n})\to(z_{\sigma(1)},...,z_{\sigma(n)},w_{\sigma(1)},...,w_{\sigma(n)})$

The $W$ also acts on $X(A,0):=\mathbf{C}^{2n}//_{0}T^{d}$. The map

$\mathbf{C}^{2n}\to\mathbf{C}^{n},\>\>\>\>(z_{1},...,z_{n},w_{1},...,w_{n})\to(z_{1}w_{1},...,z_{n}w_{n})$

descends to a map $f:X(A,0)\to\mathbf{C}^{n}$. The map $\bar{\mu}$ factorizes
as

$X(A,\alpha)\stackrel{{\scriptstyle
f}}{{\to}}\mathbf{C}^{n}\stackrel{{\scriptstyle A}}{{\to}}\mathbf{C}^{d}$

Introducing a $W$-action on $\mathbf{C}^{n}$ by natural permutations, the map
$f$ is $W$-equivariant. As $W$ preserves $\mathrm{Ker}(A)$ by definition, the
$W$-action on $\mathbf{C}^{n}$ descends to a $W$-action on $\mathbf{C}^{d}$.
In this way $\bar{\mu}$ is a $W$-equivariant map. We then have a commutative
diagram

$\begin{CD}X(A,0)@>{}>{}>X(A,0)/W\\\
@V{\bar{\mu}}V{}V@V{\bar{\bar{\mu}}}V{}V\\\
\mathbf{C}^{d}@>{}>{}>\mathbf{C}^{d}/W\end{CD}$ (4)

The map $\bar{\bar{\mu}}$ turns out to be the universal Poisson deformation of
$Y(A,0)$.

(4.3)

Let $Y(A,0)$ be an arbitrary toric hyperkähler variety. We can assume that $B$
has the following form, after permuting the row vectors and changing their
signs if necessary.

$B:=\left(\begin{array}[]{cccccccccc}m_{1}\mathbf{b}_{1}\\\ ...\\\
m_{d_{1}}\mathbf{b}_{1}\\\ m_{d_{1}+1}\mathbf{b}_{2}\\\ ...\\\
m_{d_{1}+d_{2}}\mathbf{b}_{2}\\\ m_{d_{1}+d_{2}+1}\mathbf{b}_{3}\\\ ...\\\
m_{d_{1}+d_{2}+d_{3}}\mathbf{b}_{3}\\\ ...\\\ ...\\\ ...\\\
m_{d_{1}+...+d_{r-1}+1}\mathbf{b}_{r}\\\ ...\\\
m_{d_{1}+...+d_{r-1}+d_{r}}\mathbf{b}_{r}\end{array}\right),$

where $m_{i}$ are positive integers, and $\mathbf{b}_{i}$ are primitive
vectors, which are not mutually pararllel. Let $A^{\sharp}$ be the matrix in
Theorem 11. Then $B^{\sharp}$ is the primitivization of $B$:

$B^{\sharp}:=\left(\begin{array}[]{cccccccccc}\mathbf{b}_{1}\\\ ...\\\
\mathbf{b}_{1}\\\ \mathbf{b}_{2}\\\ ...\\\ \mathbf{b}_{2}\\\ \mathbf{b}_{3}\\\
...\\\ \mathbf{b}_{3}\\\ ...\\\ ...\\\ ...\\\ \mathbf{b}_{r}\\\ ...\\\
\mathbf{b}_{r}\end{array}\right),$

where each $\mathbf{b}_{i}$ appears in
$m_{d_{1}+...+d_{i-1}+1}+\cdot\cdot\cdot+m_{d_{1}+...+d_{i-1}+d_{i}}$ times.
Therefore, the Weyl group $W$ of $Y(A^{\sharp},0)$ is isomorphic to

$\prod_{1\leq i\leq
r}\mathfrak{S}_{m_{d_{1}+...+d_{i-1}+1}+\cdot\cdot\cdot+m_{d_{1}+...+d_{i-1}+d_{i}}}.$

Since
$(Y(A,0),\omega_{Y(A,0)})\cong(Y(A^{\sharp},0),\omega_{Y(A^{\sharp},0)})$, $W$
is nothing but the Weyl group of $Y(A,0)$. In (4.2) we have already
constructed the universal Poisson deformation of $Y(A^{\sharp},0)$. Then it is
also the universal Poisson deformation of $Y(A,0)$.

(4.4) In the above, $Y(A^{\sharp},\alpha^{\sharp})$ is nonsingular if and only
if $A^{\sharp}$ is unimodular (cf. [HS, Proposition 6.2]). On the other hand,
$A^{\sharp}$ is unimodular if and only if $B^{\sharp}$ is unimodular by the
Gale duality. Therefore we have

Corollary 13. A toric hyperkähler variety $Y(A,0)$ has a projective crepant
resolution if and only if the primitivization $B^{\sharp}$ of $B$ is
unimodular.

Proof. Since we have already proved the “if” part, we only have to prove the
“only if” part. Assume that $B^{\sharp}$ is not unimodular. Then
$Y(A^{\sharp},\alpha^{\sharp})$ is a singular projectve Q-factorial
terminalization for a generic $\alpha^{\sharp}$. This means that any
projective Q-factorial terminalization of $Y(A^{\sharp},0)$ is singular111More
strongly, one can prove that any Q-factorial terminalization of
$Y(A^{\sharp},0)$ is obtained as the hyperkähler reduction
$Y(A^{\sharp},\alpha^{\sharp})$ with a generic $\alpha^{\sharp}$. by [Na 2,
Corollary 25]. $\square$

References

[Be] Beauville, A.: Symplectic singularities, Invent. Math. 139 (2000), no.3,
541-549

[BD] Bielawski, R., Dancer, A.: The geometry and topology of toric hyperkähler
manifolds. Comm. Anal. Geom. 8 (2000), no. 4, 727 - 760

[BLPW] Braden, T., Licata, A., Proudfoot, N., Webster, B.: Quantizations of
conical symplectic resolutions II: category O and symplectic duality. with an
appendix by I. Losev. Astérisque No. 384 (2016), 75 - 179.

[DS] Duistermaat, J. J., Heckman, G., J.: On the variation in the cohomology
of the symplectic form of the reduced phase space. Invent. Math. 69 (1982),
no. 2, 259 - 268

[Go] Goto, R.: On toric hyper-Kähler manifolds given by the hyper-Kähler
quotient method, in Infinite Analysis, World Scientific, 1992, pp. 317 - 338

[HS] Hausel, T.; Sturmfels, B.: Toric hyperkähler varieties. Doc. Math. 7
(2002), 495 - 534.

[Ka] Kaledin, D.: Symplectic singularities from the Poisson point of view. J.
Reine Angew. Math. 600 (2006), 135 - 156.

[Ko 1] Konno, H.: Cohomology rings of toric hyperkähler manifolds. Internat.
J. Math. 11 (2000), no. 8, 1001 - 1026.

[Ko 2] Konno, H.: The geometry of toric hyperkähler varieties. Toric topology,
241- 260, Contemp. Math., 460, Amer. Math. Soc., Providence, RI, 2008.

[Lo] Losev, I.: Isomorphisms of quantizations via quantization of resolutions.
Adv. Math. 231 (2012), no. 3-4, 1216 - 1270.

[Nag] Nagaoka, T.: The universal Poisson deformation of hypertoric varieties
and some classification results. Pacific J. Math. 313 (2021), no. 2, 459 -
508.

[Na 1] Namikawa, Y.: Equivalence of symplectic singularities. Kyoto J. Math.
53 (2013), no. 2, 483 - 514.

[Na 2] Namikawa, Y.: Flops and Poisson deformations of symplectic varieties.
Publ. Res. Inst. Math. Sci. 44 (2008), no. 2, 259 - 314.

[Na 3] Namikawa, Y.: Poisson deformations of affine symplectic varieties. Duke
Math. J. 156 (2011), no. 1, 51 - 85.

[Na 4] Namikawa, Y.: Birational geometry for the covering of a nilpotent orbit
closure. Selecta Math. (N.S.) 28 (2022), no. 4, Paper No. 75, 59 pp.

Research Institute for Mathematical Sciences, Kyoto University, Oiwake-cho,
Kyoto, Japan

E-mail address<EMAIL_ADDRESS>


# Multi-Objective Policy Gradients with Topological Constraints

Kyle Hollins Wray,∗1 Stas Tiomkin,∗2 Mykel J. Kochenderfer,1 and Pieter
Abbeel3 ∗ Equal contribution.1 Stanford University, Stanford, CA, USA.2 San
Jose State University, CA, USA.3 University of California, Berkeley, CA,
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>and
<EMAIL_ADDRESS>
###### Abstract

Multi-objective optimization models that encode ordered sequential constraints
provide a solution to model various challenging problems including encoding
preferences, modeling a curriculum, and enforcing measures of safety. A
recently developed theory of topological Markov decision processes (TMDPs)
captures this range of problems for the case of discrete states and actions.
In this work, we extend TMDPs towards continuous spaces and unknown transition
dynamics by formulating, proving, and implementing the policy gradient theorem
for TMDPs. This theoretical result enables the creation of TMDP learning
algorithms that use function approximators, and can generalize existing deep
reinforcement learning (DRL) approaches. Specifically, we present a new
algorithm for a policy gradient in TMDPs by a simple extension of the proximal
policy optimization (PPO) algorithm. We demonstrate this on a real-world
multiple-objective navigation problem with an arbitrary ordering of objectives
both in simulation and on a real robot.

##  I Introduction

In recent years, the theoretical foundations of Markov decision processes
(MDPs) [1] and reinforcement learning (RL) [2] algorithms have grown to
practical robotic applications in domains ranging from autonomous helicopter
flight [3] to autonomous vehicles [4]. However, larger real-world domains
often must consider multiple objectives such as in energy, comfort, and noise
management in buildings [5] and hybrid electric vehicles [6]. In reinforcement
learning, approaches like curriculum learning [7] and incorporating safety
considerations [8] often sequentially learn differing objectives to
incrementally develop skills. The topological MDP (TMDP) [9, 10] is a general
model that captures this space of problems. There are various methods for
multi-objective learning strategies such as constrained policy optimization
[11] for non-incremental constrained MDPs (CMDPs) for related problems like
robot walking [12]. However, there exists a gap in the theoretical foundation
for solving these general multi-objective models with policy gradient-based
algorithms, consequently limiting the principled development of deep RL
solutions.

In a TMDP, multiple objectives are ordered in a directed acyclic graph (DAG)
[9]. The ordering can capture preference, constraint, curriculum, or safety. A
slack term, or equivalently budget, is assigned to each edge in the DAG. It
represents the allowable deviation in value of an optimal policy in a parent
objective to improve the value of a child objective. This flexible structure
generalizes the constrained MDP (CMDP) [13], which is a fan-structured DAG,
and a lexicographic MDP (LMDP) [10], which is a chain-structured DAG (Figure
1). The agent can learn all the objectives simultaneously [13], or it can
incrementally step down the DAG in the order implied by its edges and learn
each parent objective before moving on to its children [10].

Consider a robot navigation domain where the robot can be tasked with
navigating to a goal location, monitoring a particular room, and avoiding
another room, all based on a customer’s preferences. Each customer may have a
preference, such as for example prioritizing monitoring over navigation or
navigation over avoiding a region. In each case, they may also have a
tolerance allowing one objective to be reduced in favor of improving another.
These preference structures and tolerances can be captured within a TMDP and
provided to the agent as it learns to complete its objectives.

In practice, solving these kinds of multi-objective problems optimally is not
feasible because all of the objectives depend on the current policy [14, 10,
11]. Chain-structured approaches that modify the value have been considered in
the tabular case [14].

Local action restriction (LAR) [10, 15] is a scalable approximate method to
solve TMDPs. It moves the global constraint into a set of local constraints
over the states. This reformulation removes the dependence of the policy on
the constraints’ values. Fan-structured approaches (Figure 1 (b)) have
considered policy gradients, such as in CPO [11]. However, the method only
works for CMDPs and cannot model a DAG’s topologically ordered constraints as
in TMDPs. Also, it requires computing expensive second-order terms as a
Hessian to approximate constraint satisfaction (see Section 6.1 [11]). In
general, these approaches are computationally expensive and/or do not admit a
direct policy gradient.

_The goal of this work is to provide a multiple objective generalization of
the policy gradient theorem for any given DAG of constraints and slack
values._ Our theorem derives a policy gradient that performs an accurate
optimization of the objectives, each being subject to the constraints of their
ancestors. We apply this general result in the specific case of extending
proximal policy optimization (PPO) [16] for use in TMDPs. The resulting new
algorithm is called topological policy optimization (TPO), integrating the new
policy gradient into the PPO objective.

Our main contributions include: (1) a formal definition and derivation a
multi-objective policy gradient within a TMDP (Section III); (2) the deep
reinforcement learning algorithm called TPO using this new policy gradient
(Section IV); (3) experiments demonstrating the success of TPO in both
simulation and on a real robot (Section V).

$V_{1}$$V_{2}$$V_{3}$$\delta_{12}$$\delta_{23}$ |  $V_{3}$$V_{1}$$V_{2}$$\delta_{13}$$\delta_{23}$ |  $V_{1}$$V_{2}$$V_{3}$$V_{4}$$\delta_{13}$$\delta_{34}$$\delta_{24}$$\delta_{12}$
---|---|---
(a) Chain |  (b) Fan |  (c) DAG
Figure 1: Example TMDP objective $V_{i}$ nodes and edges with slacks
$\delta_{ij}$.

##  II Background

###  II-A Markov Decision Process (MDP)

A Markov decision process (MDP) is defined by the tuple $\langle
S,A,T,R\rangle$. $S$ is a set of states. $A$ is a set of actions.
$T(s^{\prime}\mid s,a)$ is a Markovian state transition that captures the
probability of transitioning to a successor state $s^{\prime}$ given that
action $a$ was taken in state $s$. $R(s,a)$ is a reward function that
describes the effect of performing an action $a$ in a state $s$. For
discounted MDPs, $\gamma\in[0,1)$ is a discount factor on the reward over
time. It is also common to have an initial $s^{0}$.

Reinforcement learning can be described as the collection of algorithms that
do not assume $T$ is provided [2]. Moreover, many of these algorithms do not
assume $S$, $A$, or $R$ are fully provided a priori either. Instead, they are
only observed upon visiting a state and performing an action.

A policy $\pi(a\mid s)$ maps each state $s$ to a probability of performing
each action $a$. Let $\tau=\langle
s^{0},a^{0},r^{0},s^{1},a^{1},r^{1},\ldots\rangle$ denote a trajectory with
each state $a^{t}\sim\pi(\cdot\mid s^{t})$, $r^{t}=R(s^{t},a^{t})$, and
$s^{t+1}\sim T(\cdot\mid s^{t},a^{t})$. The goal in reinforcement learning is
to explore and use experienced trajectories $\tau$ to find a policy $\pi^{*}$
that maximizes expected reward.

Thus, the agent seeks an optimal policy $\pi^{*}$ such that:

$\pi^{*}=\underset{\pi}{\operatorname*{argmax}}~{}\mathbb{E}\Big{[}\sum_{t=0}^{\infty}\gamma^{t}R(s^{t},a^{t})\mid\pi,s^{0}\Big{]}.$

Let the value $V^{\pi}:S\rightarrow\mathbb{R}$ of a policy $\pi$ be its
expected reward. Given the model, we can solve the MDP by iteratively applying
the Bellman optimality equation at states $s$:

$V^{\pi}(s)=\max_{a}Q^{\pi}(s,a)$
$Q^{\pi}(s,a)=R(s,a)+\gamma\sum_{s^{\prime}}T(s^{\prime}\mid
s,a)V^{\pi}(s^{\prime})$

with $V^{*}$ and $Q^{*}$ denoting optimal values. The advantage is defined as
$A^{\pi}(s,a)=Q^{\pi}(s,a)-V^{\pi}(s)$ [16] and is useful in describing the
advantage in value of one action over another.

###  II-B Policy Gradient

Policy gradient methods improve the policy along a gradient and forms the
foundation for function approximation [17]. It assumes the policy $\pi$ is
parameterized by parameters $\theta$. Let $\rho(\pi)=V^{\pi}(s^{0})$ be the
value of the initial state $s^{0}$ following a policy $\pi$. The policy
gradient is:

$\frac{\partial\rho^{\pi}}{\partial\theta}=\sum_{s}d^{\pi}(s)\sum_{a}\frac{\partial\pi(a\mid
s)}{\partial\theta}Q^{\pi}(s,a)$

with $d^{\pi}$ denoting the stationary state distribution of $\pi$.

###  II-C Topological Markov Decision Process

A topological Markov decision process (TMDP) [9] generalizes the MDP to
multiple objectives and is defined by $\langle
S,A,T,{\mathbf{R}},E,{\mathbf{\delta}}\rangle$. ${\mathbf{R}}:S\times
A\rightarrow\mathbb{R}^{k}$ emits $k$ rewards; each $i\in K=\\{1,\ldots,k\\}$
can be written as $R_{i}(s,a)$. $E\subseteq K\times K$ forms a directed
acyclic graph (DAG) over the rewards, with one leaf node, assumed to be $k$
without loss of generality. ${\mathbf{\delta}}=\\{\delta_{wv}|(w,v)\in E\\}$
denotes the set of slack variables—allowable deviation from optimal value—for
each parent-child objective pair. The objective in a TMDP is: for each
objective $i\in K$, following the order of the DAG $E$, we solve:

$\displaystyle\underset{\pi}{\text{maximize}}$ $\displaystyle\quad
V_{i}^{\pi}(s^{0})$ (1) subject to $\displaystyle\quad
V_{w}^{*}(s^{0})-V_{w}^{\pi}(s^{0})\leq\delta_{wv},~{}~{}\forall
v\in\mathcal{A}_{i}\cup\\{i\\},\forall w\in\mathcal{P}_{v}$

with $\mathcal{P}_{v},\mathcal{A}_{i}\subset K$ denoting the parents and
ancestors of $v$ and $i$ in $E$ respectively; and $V_{j}^{*}(s^{0})$ denoting
the optimal value of $j$ following this same constrained objective. In other
words, the constraints state that every vertex $v$ must satisfy the slacks
$\eta_{wv}$ from its parents $w$ following an edge $e=(w,v)$. Also, let
$E_{i}=\\{e=\langle w,v\rangle\in E\mid v\in\mathcal{A}_{i}\cup\\{i\\}\text{
and }w\in\mathcal{P}_{v}\\}$ denote all $i$’s ancestral edges in $E$. An
optimal policy $\pi^{*}$ is the policy $\pi^{*}_{k}$ computed by the leaf node
$k$ in $E$. The leaf optimizes $V_{k}^{*}(s^{0})$ ensuring that the union of
all ancestral constraints are satisfied.

Local action restriction (LAR) [10, 9] is an approximation that restriction
actions locally by a local slack ${\mathbf{\eta}}$, rather than a global slack
${\mathbf{\delta}}$. It has been shown that if
$\eta_{i}=(1-\gamma)\delta_{i}$, then global slack can be preserved, if
desired. LAR enables scalable algorithms to be devised. The resulting TMDP
objective for each objective $i$ becomes:

$\displaystyle\underset{\pi}{\text{maximize}}$ $\displaystyle\quad
V_{i}^{\pi}(s^{0})$ (2) subject to $\displaystyle\quad
V_{w}^{*}(s)-Q_{w}^{*}(s,\pi(s))\leq\eta_{wv},$
$\displaystyle\quad\quad\quad\quad\quad\forall
v\in\mathcal{A}_{i}\cup\\{i\\},\forall w\in\mathcal{P}_{v},s\in S$

TMDPs generalize both LMDPs and feasible CMDPs. See Figure 1 for examples.

##  III Policy Gradient Theorem for TMDP

Solving the LAR optimization in Equation 2 can be done using a modified
Bellman optimality equation for tabular policy [10, 15, 9]. This formulation
does not admit function approximation, or specifically, the use of a policy
gradient or deep reinforcement learning methods. Our main result in this
section is a formulation and proof of a policy gradient theorem to solve
Equation 2.

The goal is to prove a TMDP policy gradient theorem. To accomplish this, we
need to formulate a constrained Bellman optimality equation corresponding to
Equation 2. LAR allows us to move the constraints into the Bellman optimality
equation [9]. However, this becomes a constrained optimization problem. We
seek to reduce this to an unconstrained optimization problem in order to
leverage the abundant prior work on (approximate) policy gradients [18, 16].
We convert the constrained Bellman equation into an unconstrained Bellman
equation using Lagrange multipliers. However, the standard approach results in
the reward itself being penalized by an arbitrary amount based on the
ancestors’ advantages. Consequently, this would change the optimization’s
value function.

We provide a solution that will not affect the reward in this manner. This
requires both: (1) the Lagrange multiplier to be assigned properly via a
bound, and (2) the constraint term to be transformed such that it is zero when
the constraint is not violated. We derive a bound on the Lagrange multiplier
to ensure it is large enough such that any action that violates the constraint
will not be chosen. We prove that the transformed constraint term preserves
the original constraint satisfaction. When these facts are combined, the
result is that the original value is preserved and the constraints are
satisfied.

With this new Bellman optimality equation, Lagrange multiplier bounds, and
transformed constraint, we prove the constrained policy gradient theorem for
the TMDP.

###  III-A Lagrangian Bellman Optimality Equation

We need to derive the corresponding Bellman optimality equation. However
directly writing a Bellman equation for the unconstrained optimization
formulation in Equation 1 can be onerous due to the extra terms. Instead, as
shown in prior work [10, 9], we can leverage LAR to move the constraints in
Equation 2 into the Bellman optimization problem over actions. Ensuring the
original constraints are satisfied at each state, implies they are satisfied
for the original optimization. This Bellman optimality equation with LAR at a
state $s$ is the constrained optimization [9]:

$\displaystyle\underset{a}{\text{maximize}}$ $\displaystyle\quad
Q_{i}^{\pi}(s,a)=R_{i}(s,a)+\gamma\sum_{s^{\prime}}T(s^{\prime}\mid
s,a)V_{i}^{\pi}(s^{\prime})$ subject to
$\displaystyle\quad{-}A_{w}^{*}(s,a)\leq\eta_{wv},\forall w,v$ (3)

with $V_{i}^{\pi}(s)=Q_{i}^{\pi}(s,a^{*})$ for constraint-optimal action
$a^{*}$.

The naive use of Lagrange multipliers would result in the undesirable Equation
4 below that arbitrarily modifies the rewards, affecting the values as a
consequence:

$\displaystyle\textbf{V}_{i}^{\pi}(s)$
$\displaystyle=\max_{a}\Big{(}R_{i}(s,a)+\gamma\sum_{s^{\prime}}T(s^{\prime}\mid
s,a)\textbf{V}_{i}^{\pi}(s^{\prime})$
$\displaystyle\quad\quad\quad-\sum_{v,w}\beta_{wvs}({-}A_{w}^{*}(s,a)-\eta_{wv})\Big{)}$
(4)

with Lagrange multipliers $\beta_{wvs}\geq 0$ and Lagrangian value function
$\textbf{V}_{i}^{\pi}$. To illustrate the issue, consider two cases. If
objective $i$ chooses an action beyond the budgeted slack $\eta_{wv}$, then
there should be a penalty. Otherwise, there should not be an increase in the
reward for an action less than the budgeted slack. Instead, the agent should
simply maximize its original reward. Thus, crucially, the extra constraint
terms should only be a penalty if the constraint is violated. Otherwise, the
reward should remain unaffected. To accomplish this, we need to transform the
constraint as follows.

###### Proposition 1

For an objective $i$ and state $s$, the optimization in Equation 3 is
equivalently solved by:

$\displaystyle\underset{a}{\text{maximize}}$ $\displaystyle\quad
Q_{i}^{\pi}(s,a)=R_{i}(s,a)+\gamma\sum_{s^{\prime}}T(s^{\prime}\mid
s,a)V_{i}^{\pi}(s^{\prime})$ subject to $\displaystyle\quad C_{wv}(s,a)\leq
0,\forall w,v$ (5)

with $C_{wv}(s,a)=\max\\{0,{-}A_{w}^{*}(s,a)-\eta_{wv}\\}$.

###### Proof:

The TMDP Bellman optimality equation with LAR at a state $s$ follows Equation
3. By definition, for the optimal policy’s values,
${-}A_{w}^{*}(s,a)=V_{w}^{*}(s)-Q_{w}^{*}(s,a)\geq 0$ and there always exists
an action $a^{*}$ such that ${-}A_{w}^{*}(s,a)=0$. Thus this optimization
always feasible and we have:

$\displaystyle{-}A_{w}^{*}(s,a)\leq\eta_{wv}$
$\displaystyle\Rightarrow{-}A_{w}^{*}(s,a)-\eta_{wv}\leq 0$
$\displaystyle\Rightarrow\max\\{0,{-}A_{w}^{*}(s,a)-\eta_{wv}\\}\leq 0$
$\displaystyle\Rightarrow C_{wv}(s,a)\leq 0$

This lets us rewrite the optimization problem as in Equation 5, yielding our
result. ∎

Now we can compute the Lagrangian of the constrained optimization problem in
Equation 5. The Lagrangian Bellman optimality equation is:

$\displaystyle\textbf{V}_{i}^{\pi}(s)$
$\displaystyle=\max_{a}\Big{(}R_{i}(s,a)+\gamma\sum_{s^{\prime}}T(s^{\prime}\mid
s,a)\textbf{V}_{i}^{\pi}(s^{\prime})$
$\displaystyle\quad\quad\quad-\sum_{v,w}\beta_{wvs}C_{wv}(s,a)\Big{)}$ (6)

For notational convenience, for any objective $j\in K$, the Lagrangian Q-value
is $\mathbf{Q}_{j}(s,a)$ and the Lagrangian advantage is:
$\mathbf{A}_{j}(s,\pi(s))=\mathbf{Q}_{j}(s,\pi(s))-\mathbf{V}_{j}(s)$. In
practice, $\mathbf{A}_{j}$ can be computed using a new form of generalized
advantage, discussed in the next section.

Equation 6 has two main properties. First, it converted the original
constrained optimization problem into an unconstrained Bellman optimality
equation. Second, if its constraints are satisfied, then it preserves the
original reward; otherwise it penalizes the reward.

The scale of the constraint terms $C_{wv}(s,a)$ can be arbitrary based on the
scale of the values. If we do not select a sufficiently large multiplier, then
it is possible that the penalty will not be enough to ensure constraint-
violating actions are never chosen.

Thus, we derive a lower bound on $\beta_{wvs}$ such that the application of
the Lagrangian Bellman optimality equation (Equation 6) will never select
constraint-violating actions. This is derived in Proposition 2.

Finally, we must also prove that it preserves optimality of the original
problem. In summary, the use of Equation 6 with $\beta_{wvs}$ as described
below will converge to the correct values and simultaneously enforce the LAR
constraints. This is proven in Theorem 1.

###### Proposition 2

Given objective $i$, state $s$, ancestor edges $\langle w,v\rangle\in E_{i}$,
values $Q_{i}$, at least one constraint-violating action (infeasibility)
exists, and optimal constraint-satisfying action $\hat{a}^{*}$, if all
$\beta_{wvs}$ satisfy:

$\beta_{wvs}\geq\max_{a}\left\\{\begin{array}[]{l
l}\frac{Q_{i}(s,a)-Q_{i}(s,\hat{a}^{*})}{\sum_{v,w}C_{wv}(s,a)}&\quad\text{if
}\sum_{v,w}C_{wv}(s,a)>0\\\ 0&\quad\text{otherwise}\end{array}\right.$ (7)

then no constraint-violating actions $\hat{a}$ will be chosen, i.e.,
$\max_{a}\mathbf{Q}_{i}^{\pi}(s,a)=\mathbf{Q}_{i}^{\pi}(s,\hat{a}^{*})$.

###### Proof:

At any iteration of the Bellman equation, for any states $s^{\prime}$, assume
no other states have chosen suboptimal action. By Proposition 1 and Equation
6, the Lagrangian values are identical to the constrained optimization
problems’ values $\mathbf{V}_{i}^{\pi}(s^{\prime})=V_{i}^{\pi}(s^{\prime})$.

Below, let $Q_{i}(s,a)$ be the result of applying the standard Bellman
equation. Let $\hat{a}^{*}$ be the optimal constraint-satisfying action
solving Equation 3. Note that both $Q_{i}(s,a)$ and $\hat{a}^{*}$ can be
computed separately without depending on the equation being considered
(Equation 6).

Consider the application of the Lagrangian Bellman optimality equation on a
state $s$ (Equation 6). Assume the existence of a constraint violating action
$\hat{a}$. (By construction in Proposition 1, any constraint-satisfying action
will result in the penalty constraint terms being $0$.) For this maximization,
it is sufficient to compare the actions $\hat{a}^{*}$ and $\hat{a}$:

$\mathbf{Q}_{i}^{\pi}(s,\hat{a}^{*})\geq\mathbf{Q}_{i}^{\pi}(s,\hat{a})$
$\displaystyle R_{i}(s,\hat{a}^{*})+\gamma\sum_{s^{\prime}}T(s^{\prime}\mid
s,\hat{a}^{*})\textbf{V}_{i}^{\pi}(s^{\prime})-\sum_{v,w}\beta_{wvs}C_{wv}(s,\hat{a}^{*})$
$\displaystyle\quad\geq
R_{i}(s,\hat{a})+\gamma\sum_{s^{\prime}}T(s^{\prime}\mid
s,\hat{a})\textbf{V}_{i}^{\pi}(s^{\prime})-\sum_{v,w}\beta_{wvs}C_{wv}(s,\hat{a})$

Since $\mathbf{V}_{i}^{\pi}(s^{\prime})=V_{i}^{\pi}(s^{\prime})$ and
$C_{wv}(s,\hat{a}^{*})=0$, we have:

$\displaystyle R_{i}(s,\hat{a}^{*})+\gamma\sum_{s^{\prime}}T(s^{\prime}\mid
s,\hat{a}^{*})V_{i}^{\pi}(s^{\prime})-\sum_{v,w}\beta_{wvs}0$
$\displaystyle\quad\geq
R_{i}(s,\hat{a})+\gamma\sum_{s^{\prime}}T(s^{\prime}\mid
s,\hat{a})V_{i}^{\pi}(s^{\prime})-\sum_{v,w}\beta_{wvs}C_{wv}(s,\hat{a})$
$Q_{i}(s,\hat{a}^{*})-Q_{i}(s,\hat{a})+\sum_{v,w}\beta_{wvs}C_{wv}(s,\hat{a})\geq
0$

Let $\beta_{s}$ be the same constant used for all $\beta_{wvs}$, yielding:

$Q_{i}(s,\hat{a}^{*})-Q_{i}(s,\hat{a})+\beta_{s}\sum_{v,w}C_{wv}(s,\hat{a})\geq
0$
$\beta_{s}\geq\frac{Q_{i}(s,\hat{a})-Q_{i}(s,\hat{a}^{*})}{\sum_{v,w}C_{wv}(s,\hat{a})}$

This inequality must be satisfied for all $\hat{a}$, enforcable with a
maximization over actions. This results in Equation 7. ∎

###### Theorem 1

Lagrangian Bellman optimality Equation 6 solves the optimization in Equation
2.

###### Proof:

By Proposition 2, there exists a $\beta_{wvs}$ such that the use of the
Lagrangian Bellman optimality equation (Equation 6) ensures the constraints:
$C_{wv}(s,a)\leq 0,\forall w,v$, are always satsified.

Since the constraints are satisfied, by construction Equation 6 has constraint
terms $0$, implying
$\mathbf{Q}_{i}^{*}(s,\hat{a}^{*})=Q_{i}^{*}(s,\hat{a}^{*})-0=Q_{i}^{*}(s,\hat{a}^{*})$.
Thus it solves the optimization in Equation 5.

By Proposition 1, it also solves the optimization problem in Equation 3. By
construction of Equation 3’s constraints, for all states $s$,
$-A_{w}^{*}(s,a)\leq\eta_{wv}$, and again
$\mathbf{V}_{i}^{*}(s,a)=V_{i}^{*}(s,a)$. Thus, all constraints of the
original optimization in Equation 2 are satified and return the same resulting
policy at all states, solving this original optimization. ∎

###  III-B Multi-Objective Lagrangian Policy Gradient Theorem

We have changed the objective into a form involving additional ancestor
objectives. Consequently, it is not a given that parameterized policies
learning from samples—such as in the case of deep reinforcement learning—is
able to converge to the optimal policy. Here we present a novel policy
gradient theorem [17] for any algorithm using this Lagrangian TMDP objective.
This _multi-objective Lagrangian policy gradient theorem_ is presented in
Proposition 3 below.

###### Proposition 3

For any TMDP, with an discounted infinite horizon objective (or an average-
reward objective), for each objective $i$:

$\frac{\partial\mathbf{\rho}_{i}^{\pi}}{\partial\theta}=\sum_{s}d^{\pi}(s)\sum_{a}\frac{\partial\pi(a\mid
s)}{\partial\theta}\mathbf{Q}_{i}^{\pi}(s,a).$ (8)

###### Proof:

We begin by rewriting Equation 6:

$\textbf{V}_{i}^{\pi}(s)=\max_{a}\Big{(}\mathbf{R}_{i}(s,a)+\gamma\sum_{s^{\prime}}T(s^{\prime}\mid
s,a)\textbf{V}_{i}^{\pi}(s^{\prime})\Big{)}$

with $\mathbf{R}_{i}(s,a)=R_{i}(s,a)-\sum_{v,w}\beta_{wvs}C_{wv}(s,a)$.
Consider the partial derivative of $\mathbf{R}_{i}$ with respect to policy
parameters $\theta$. First, $\frac{\partial}{\partial\theta}R_{i}(s,a)=0$.
Second, by definition in Equation 5, each $C_{wv}$ does not depend on the
current policy parameters $\theta$, as it is proportional to the optimal
advantages and slacks of ancestors:
$C_{wv}(s,a)=\max\\{0,{-}A_{w}^{*}(s,a)-\eta_{wv}\\}$. We have
$\frac{\partial}{\partial\theta}C_{wv}(s,a)=0$. Thus,
$\frac{\partial}{\partial\theta}\mathbf{R}_{i}(s,a)=0$.

The rest of this proof follows directly from the original policy gradient
theorem’s proof [17], using $\mathbf{R}_{i}$ as the reward and the fact that
$\frac{\partial}{\partial\theta}\mathbf{R}_{i}(s,a)=0$. ∎

Algorithm 1 Topological policy optimization

1:$k$: Number of objectives

2:$E$: DAG of objective relationships

3:$\delta$: Slacks for each objectives

4:$\theta^{0}$: Initial policy parameters

5:$\pi_{\theta},\hat{\mathbf{V}}$ $\leftarrow$ $\pi_{\theta^{0}}$, $\emptyset$

6:for $i\leftarrow$ TopologicalSort($E$) do

7: // $\hat{\mathbf{A}}_{i}$ is a function of trajectories computed during

8: // PPO’s rollouts; it uses the learned ancestral

9: // critics’ set $\hat{\mathbf{V}}$ as a parameter

10: $\hat{\mathbf{A}}_{i}$ $\leftarrow$ Eq. 10 using this iteration’s
$\hat{\mathbf{V}}$ in $C_{wv}$

11: $\pi_{\theta},\hat{V}_{i}$ $\leftarrow$ PPO($\pi_{\theta}$,
$\hat{\mathbf{A}}_{i}$) // Use $\hat{\mathbf{A}}_{i}$ for PPO’s adv.

12: $\hat{\mathbf{V}}$ $\leftarrow$ $\hat{\mathbf{V}}\cup\\{\hat{V}_{i}\\}$ //
Extend critic set for descendants

13:return $\pi_{\theta}$, $\hat{\mathbf{V}}$

$M$$A$$G$$\eta_{1}$$\eta_{2}$(a) | $0$$50$$100$$-800$$-600$$-400$$-200$$0$$\eta_{1}=\eta_{2}$$\mathbf{V}$ |  $A$$M$$G$$\eta_{1}$$\eta_{2}$(b) | $0$$50$$100$$-800$$-600$$-400$$-200$$0$$\eta_{2}$$\mathbf{V}$
---|---|---|---
$G$$M$$A$$\eta_{1}$$\eta_{2}$(c) | $0$$50$$100$$-1{,}000$$-800$$-600$$-400$$-200$$\eta_{1}$$\mathbf{V}$ |  $G$$A$$M$$\eta_{1}$$\eta_{2}$(d) | $0$$50$$100$$-800$$-600$$-400$$-200$$0$$\eta_{1}=\eta_{2}$$\mathbf{V}$
Figure 2: Results for four different DAGs and slack assignments on the robot
navigation domain. The x-axis denotes slack $\eta$. The y-axis denotes values
for all three objectives: $V_{\text{avoid}}$ (red), $V_{\text{monitor}}$
(blue), and $V_{\text{goal}}$ (green). Note that the units of the values for
the three objectives are distinct from one another.

##  IV Topological Policy Optimization

Proximal policy optimization (PPO) [16] uses a (clipped) surrogate objective,
computing an approximate policy gradient over batch trajectories $\tau$ of
length $h$, and using a generalized advantage estimation. We apply our
Lagrangian Bellman equation results from the previous section to PPO. The
following equations refer to this novel contribution. At time step $t$, the
objective $i$’s Lagrangian surrogate objective is:

$\mathbf{L}_{i}(\theta)=\hat{\mathbb{E}}^{t}\Big{[}\log\pi_{\theta}(a^{t}|s^{t})\hat{\mathbf{A}}_{i}^{t}\Big{]}$
(9)

with $\hat{\mathbf{A}}_{i}^{t}$ denoting advantages computed by generalized
Lagrangian advantage estimation (Equation 10 below).

The generalized Lagrangian advantage estimation defines
$\hat{\mathbf{A}}_{i}^{t}=\mathbf{\delta}_{i}^{t}+(\gamma\lambda)\mathbf{\delta}_{i}^{t+1}+\cdots+(\gamma\lambda)^{h-t+1}\mathbf{\delta}_{i}^{h-1}$
with single advantage estimates
$\mathbf{\delta}_{i}^{k}=\mathbf{r}_{i}^{k}+\gamma\mathbf{V}_{i}^{\pi}(s^{k+1})-\mathbf{V}_{i}^{\pi}(s^{k})$.
The sample-based estimate for this expression is computed by:

$\displaystyle\hat{\mathbf{A}}_{i}^{t}$
$\displaystyle=\sum_{k=t}^{h-1}(\gamma\lambda)^{k}\mathbf{\delta}_{i}^{k}=\sum_{k=t}^{h-1}(\gamma\lambda)^{k}\Big{(}\mathbf{r}_{i}^{k}+\gamma\mathbf{V}_{i}^{\pi}(s^{k+1})-\mathbf{V}_{i}^{\pi}(s^{k})\Big{)}$
$\displaystyle=\sum_{k=t}^{h-1}(\gamma\lambda)^{k}\Big{(}r_{i}^{k}-\sum_{v,w}\beta_{wvs^{k}}C_{wv}(s^{k},a^{k})$
$\displaystyle\quad\quad\quad\quad+\gamma(V_{i}^{\pi}(s^{k+1})-\sum_{v,w}\beta_{wvs^{k+1}}C_{wv}(s^{k+1},a^{k+1}))$
$\displaystyle\quad\quad\quad\quad-(V_{i}^{\pi}(s^{k})-\sum_{v,w}\beta_{wvs^{k}}C_{wv}(s^{k},a^{k}))\Big{)}$
$\displaystyle=\sum_{k=t}^{h-1}(\gamma\lambda)^{k}\Big{(}r_{i}^{k}+\gamma
V_{i}^{\pi}(s^{k+1})-V_{i}^{\pi}(s^{k})$
$\displaystyle\quad\quad\quad\quad-\gamma\sum_{v,w}\beta_{wvs^{k+1}}C_{wv}(s^{k+1},a^{k+1})\Big{)}$
(10)

with $C_{wv}$ incorporating the ancestral advantages $A_{wv}$ as defined by
Equation 5.

Additional components of PPO and similar algorithms may be used, which are
applied inside of the PPO routine in line 6, Algorithm 1. Specifically, we
employ PPO’s policy gradient entropy term and its clipped ratio for the
policy.

##  V Experiments

In this section, we consider experiments in the _multi-objective robot
navigation_ [19] domain, which is fully implemented on a real robot acting in
an actual household environment. Importantly, the main contribution of this
paper remains the multi-objective policy gradient’s theoretical results and
formulation, rather than the implementation of the approach in TPO and a real
world navigation domain. These results are included to provide evidence of the
approach’s usefulness and build intuitions in modeling objective structures
and behavioral customizability using slack.

###  V-A Multi-Objective Robot Navigation Domain

We consider navigation domains in which a robot is provided with the tuple
$\langle\mathcal{M},\mathcal{L}^{0},\mathcal{L}^{g},\mathcal{R}^{a},\mathcal{R}^{m}\rangle$.
$\mathcal{M}\in\\{0,1\\}^{m\times n}$ is a map, described here as a occupancy
grid (or binary matrix), with a starting location
$\mathcal{L}^{0}\in\mathcal{M}$ and a goal location
$\mathcal{L}^{g}\in\mathcal{M}$. All this information and the state
transitions, which describe the robot’s movement dynamics and its interaction
with walls or obstacles in the map, are unknown a priori.

The goal objective is to navigate from $\mathcal{L}^{0}$ to $\mathcal{L}^{g}$
as fast as possible. The robot receives a $-1$ for any non-goal state,
including when interacting with walls or obstacles. Once the robot reaches the
goal $\mathcal{L}^{g}$, its navigation ends.

Two additional objectives are also provided. The avoid objective is to
penalize entering a rectangular region $\mathcal{R}^{a}$. The robot receives a
$-1$ for each time step in this region. The monitor objective is to encourage
entering into a rectangular region $\mathcal{R}^{m}$. The robot receives a
$+1$ for each time step in this region. For both objectives, any interaction
with walls or obstacles is still met with a penalty of $-1$.

This domain builds on prior work on multi-objective (PO)MDPs for home
healthcare robots [19]. In particular, the navigation of a home healthcare
robot can be tailored to different homes via the map $\mathcal{M}$; delivering
medicine through the assignment of $\mathcal{L}^{0}$ and $\mathcal{L}^{g}$;
the preference of the human(s) or patients to avoid traversing rooms via
$\mathcal{R}^{a}$; the preference to monitor rooms while navigating via
$\mathcal{R}^{m}$; and so on.

Figure 3: Experiments that implement _home navigation_ on a real robot in an
actual household environment. This uses the $M\rightarrow A\rightarrow G$ DAG
with two paths: (1) constrained-to-monitor (blue path) with
$\eta_{1}=\eta_{2}=0$, and (2) constrained-to-avoid (red path) with
$\eta_{1}=100$ and $\eta_{2}=0$. The start point (S), goal point (G), avoid
region, and monitor region are shown.

###  V-B Experimental Setting

The thesis of this paper is to propose a novel multi-objective policy gradient
formulation for the new TMDP model, for which no algorithm currently exists
for continuous state spaces. Therefore, the theoretical result and formulation
must ideally be evaluated by comparing its efficacy at modeling different
permutations of multiple objective DAGs and slack assignments. Thus, the
primary metrics must be the values of all three objectives:
$V_{\text{avoid}}$, $V_{\text{monitor}}$, and $V_{\text{goal}}$. The results
indicate how effective the approach is at capturing the slack and the
preferences encoded by each of the DAGs.

The implementation of this theoretical approach is the approximate TPO
algorithm. For each of the configurations of DAG and slacks, the algorithm is
trained for $300000$ iterations. The experiments compute the value for each
objective via Monte Carlo simulations using the agent’s final policy network.
Analysing convergence is left to future work. The approach is implemented in
Julia 1.6.1 on Ubuntu 18.04.

###  V-C Results and Discussion

Figure 2 provides results of four distinct constraint DAGs, with each varying
the slack values. This figure illustrates the effect of the topological
structure of the constraint DAG and the slack assignments on the three
objectives’ values.

In Figures 2 (a) and (b), we see the desired effect: increasing the slack of
the constraining objectives avoid ($A$) and monitor ($M$) reduces their value
and enables the goal ($G$) objective to improve its value. Figure 2 (d) shows
a similar effect, except with a different fan DAG structure. In this case, the
result DAG structure enables a more drastic change. In Figure 2 (c), the goal
is the first objective. We observe now that by increasing the slack of the
$G$, the other two objectives ($A$ and $M$) are able to increase their values.

Figure 3 demonstrates the implementation of the approach on an actual robot
acting in a real household environment. With zero slack, the primary monitor
objective is favored, forcing the avoid objective to experience a penalty.
However when provided slack, the avoid objective is able to direct the path
away from the region while navigating to the goal.

##  VI Conclusion

This paper presents a policy gradient approach for capturing rich multi-
objective preference structures in reinforcement learning. While primarily a
theoretical paper, the method is demonstrated in a real robot navigation
domain. With this paper’s established theoretical foundation, future work will
introduce applications of this approach for a range of reinforcement learning
problems including formulations of curriculum learning and imitation learning.

## References

  * [1] R. E. Bellman, _Dynamic Programming_. Princeton University Press, 1957.
  * [2] R. S. Sutton and A. G. Barto, _Reinforcement Learning: An Introduction_. MIT Press, 2018.
  * [3] P. Abbeel and A. Y. Ng, “Apprenticeship learning via inverse reinforcement learning,” in _International Conference on Machine Learning (ICML)_ , 2004\.
  * [4] K. H. Wray, S. J. Witwicki, and S. Zilberstein, “Online decision-making for scalable autonomous systems,” in _International Joint Conference on Artificial Intelligence (IJCAI)_ , 2017, pp. 4768–4774.
  * [5] L. Klein, J. young Kwak, G. Kavulya, F. Jazizadeh, B. Becerik-Gerber, P. Varakantham, and M. Tambe, “Coordinating occupant behavior for building energy and comfort management using multi-agent systems,” _Automation in Construction_ , vol. 22, pp. 525–536, 2012.
  * [6] K. H. Wray, R. Lui, and L. Pedersen, “Engine activation planning for series hybrid vehicles,” in _IEEE Intelligent Vehicles Symposium_ , 2021, pp. 238–244.
  * [7] C. Florensa, D. Held, M. Wulfmeier, M. Zhang, and P. Abbeel, “Reverse curriculum generation for reinforcement learning,” 2017, pp. 482–495.
  * [8] A. Wachi and Y. Sui, “Safe reinforcement learning in constrained Markov decision processes,” in _International Conference on Machine Learning (ICML)_ , 2020, pp. 9797–9806.
  * [9] K. H. Wray, “Abstractions in reasoning for long-term autonomy,” Ph.D. dissertation, University of Massachusetts, Amherst, MA, 2019.
  * [10] K. H. Wray, S. Zilberstein, and A.-I. Mouaddib, “Multi-objective MDPs with conditional lexicographic reward preferences,” in _AAAI Conference on Artificial Intelligence (AAAI)_ , 2015, pp. 3418–3424.
  * [11] J. Achiam, D. Held, A. Tamar, and P. Abbeel, “Constrained policy optimization,” 2017.
  * [12] T. Haarnoja, S. Ha, A. Zhou, J. Tan, G. Tucker, and S. Levine, “Learning to walk via deep reinforcement learning,” _arXiv preprint arXiv:1812.11103_ , 2018.
  * [13] E. Altman, _Constrained Markov decision processes_. Chapman & Hall/CRC Press, 1999.
  * [14] Z. Gábor and Z. K. C. Szepesvári, “Multi-criteria reinforcement learning,” in _International Conference on Machine Learning (ICML)_ , 1998, pp. 197–205.
  * [15] K. H. Wray and S. Zilberstein, “Multi-objective POMDPs with lexicographic reward preferences,” in _International Joint Conference on Artificial Intelligence (IJCAI)_ , 2015, pp. 1719–1725.
  * [16] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _arXiv preprint arXiv:1707.06347_ , 2017\.
  * [17] R. S. Sutton, D. A. McAllester, S. P. Singh, and Y. Mansour, “Policy gradient methods for reinforcement learning with function approximation,” in _Advances in Neural Information Processing Systems (NIPS)_ , 2000, pp. 1057–1063.
  * [18] J. Schulman, S. Levine, P. Moritz, M. Jordan, and P. Abbeel, “Trust region policy optimization,” in _International Conference on Machine Learning (ICML)_ , 2015, pp. 1889–1897.
  * [19] K. H. Wray and K. Czuprynski, “Scalable gradient ascent for controllers in constrained POMDPs,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , 2022.