# The Geometry of Mehler’s Kernel

Jesus Sanchez Jr

(December 2023)

###### Abstract

We study the relationship between the Getzler calculus of a spin Riemannian
manifold and the Riemannian geometry of the corresponding principal spin
bundle. We then use the calculus of Gaussian-Grassmann integrals developed by
Berline–Vergne to compute the Getzler symbol of the spinor heat flow.

##  1 Introduction

Given a closed smooth manifold $M$ and an elliptic pseudo-differential
operator $P:\Gamma(M,E)\rightarrow\Gamma(M,F)$ acting between the sections of
complex vector bundles over $M$, global analysis tells us that $P$ is Fredholm
and the Atiyah-Singer index theorem [3] computes the Fredholm index via a
topological expression

$\text{Index}P=(-1)^{\text{dim}M}\int_{T^{*}M}ch(\sigma(P))\wedge\widehat{Td}(TM^{\mathbb{C}}).$

To date, there are many approaches to the index theorem in the general case of
pseudo-differential operators, most of which focus on the global aspects of
$\sigma(P)$ as an element of a (possibly noncommutative) generalized
cohomology theory, e.g. $K$-theory. While these approaches are incredibly
powerful and have built various bridges with other subjects in mathematics
such as operator $K$-theory, deformation quantization, and Lie groupoids to
name a few, these approaches also wash away the relationship between the
operator $P$ and geometric structures on $M$. The subject of local index
theory is aimed at deriving index theorems by studying the interplay of the
local coefficients of $P$ and a suitably chosen geometric structure $(M,G)$ on
$M$.

The case when $P=D$ is a Dirac-type operator and the geometric structure is
Riemannian has been well studied in the literature and begins with the work of
Atiyah-Bott-Patodi [2]. The major drawback of [2] was its implicit extraction
of the characteristic forms relevant for the index calculation. This was later
clarified with the work of Alvarez-Guamé [1] and Witten [11] on supersymmetric
quantum mechanics and localization on loop space. Rigorous proofs of these
claims have been given, the three techniques which stand out are of Bismut
[6], Berline–Vergne [5], and Getzler [7], each technique using and developing
different machinery to handle the problem. The goal of the present article is
to build a bridge between the two different approaches of Getzler [7] and
Berline–Vergne [5]. We will show that one can use the Berline–Vergne approach
to evaluate the Getzler symbol of the heat kernel, demystifying the geometry
of the terms within the Getzler-Mehler kernel, in particular shedding light on
the geometry of the Gaussian term. In all approaches to the local index
theorem, the heat semi-group $\\{e^{-t\not{D}^{2}}\\}_{t>0}$ plays a vital
role. How one approaches the small time behaviour of $e^{-t\not{D}^{2}}$ is
different for Getzler and Berline–Vergne. Let us briefly explain the
approaches.

In Getzler’s original approach, one views the super-manifold
$C^{\infty}(\mathscr{N})=\Gamma(T^{*}M,\pi^{*}\wedge T^{*}M)$ as the cotangent
superbundle bundle to the super-manifold $\mathcal{M}$ with
$C^{\infty}(\mathcal{M})=\Gamma(M,\mathscr{S})$, the sections of the spinor
bundle. While this idea is heuristic (because $\Gamma(M,\mathscr{S})$ is not a
true supermanifold) it motivates the definition of the Getzler symbol calculus
as a combination of the dequantization of the pseudodifferential operators on
$C^{\infty}(M)$ to functions on $T^{*}M$ and the dequantization of the
Clifford algebra $\Gamma(M,C\ell(T^{*}M))$ to the exterior algebra
$\Gamma(M,\wedge T^{*}M)$. In a follow up article [8], Getzler explains the
symbol calculus as a rescaling at the level of Schwartz kernel which is
particularly simple for differential operators and smoothing operators. The
main achievement of this technique is to show that the symbol of the heat
kernel is the Mehler kernel

$\sigma^{Par-G}(e^{-t\not{D}^{2}})(\bm{\mathrm{x}})=(4\pi
t)^{-n/2}\text{det}^{1/2}\left(\frac{tR/2}{\text{sinh}(tR/2)}\right)\text{exp}\left(-\frac{1}{4t}\left\langle\bm{\mathrm{x}}\middle|\frac{tR}{2}\text{coth}\left(\frac{tR}{2}\right)\middle|\bm{\mathrm{x}}\right\rangle\right)$

which, when evaluated at $(\bm{\mathrm{x}},t)=(\bm{\mathrm{0}},1)$, recovers
the quantity

$(4\pi)^{-n/2}\text{det}^{1/2}\left(\frac{R/2}{\text{sinh}(R/2)}\right),$

the $\hat{A}$-genus of the manifold $M$.

Coming at the problem from a different angle, Berline–Vergne studied the
geometry of a principal spin bundle $P_{Spin}(M)$ of a given Riemannian
manifold $(M,g)$. The key reason for doing this is that one can lift
$\not{D}^{2}$ on the base $M$ to $P_{Spin}(M)$ via

${C^{\infty}\left(P_{Spin}(M),\wedge\mathbb{C}^{n/2}\right)^{\rho}}$${C^{\infty}\left(P_{Spin}(M),\wedge\mathbb{C}^{n/2}\right)^{\rho}}$${\Gamma(\mathscr{S})}$${\Gamma(\mathscr{S})}$$\scriptstyle{\Delta+\pi^{*}k/4-n(n-1)/2}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{\not{D}^{2}}$

which gives rise to the following expression for the heat kernel on the base

$\left\langle
p\middle|e^{-t\not{D}^{2}}\middle|q\right\rangle=e^{n(n-1)t/2}\int_{\textnormal{Spin}(n)}\left\langle
p\cdot g\middle|e^{-t(\Delta+\pi^{*}k/4)}\middle|q\right\rangle\rho(g)dg.$ (1)

The appearance of the $\hat{A}$-genus of $M$ can be understood by making two
observations. The first is that, from this perspective, it is only the _first_
term in the heat kernel asymptotics of $\langle
p|e^{-t(\Delta+\pi^{*}k/4)}|q\rangle$ which contributes to the local
supertrace in the limit as $t\rightarrow 0^{+}$. The second is that the first
term in the heat asymptotics of $\langle p|e^{-t(\Delta+\pi^{*}k/4)}|q\rangle$
only depends on the local Jacobian of the exponential map. It is here that the
geometry of $P_{Spin}(M)$ is utilized to show that the $\hat{A}$-genus appears
_explicitly_ by studying the Jacobian of the exponential map restricted to the
horizontal distribution defined by the Levi–Civita connection on $M$.

######  Theorem 1.1 (Berline–Vergne, [5]).

Fix $p\in P_{Spin}(M)$, $\pi(p)=x$ and consider the function $\Phi$ defined
for $A\in\mathfrak{spin}(n)$ small

$\displaystyle\Phi(A)$
$\displaystyle=\textup{det}^{-1/2}(\textup{exp}_{p})_{*,A}$
$\displaystyle=\textup{det}^{-1/2}\left(\frac{\sinh
ad_{A}/2}{ad_{A}/2}\right)\cdot\textup{det}^{-1/2}\left(\frac{\sinh\tau(A\cdot\Omega_{p})/4}{\tau(A\cdot\Omega_{p})/4}\right).$

Then one has (after making an identification
$\bigwedge\mathbb{R}^{n}\simeq\bigwedge T^{*}_{x}M$)

$\displaystyle\Phi(2e\wedge e^{*})$
$\displaystyle=\textup{det}^{1/2}\left(\frac{R_{x}/2}{\sinh(R_{x}/2)}\right).$

On the surface, these two methods seem unrelated. Moreover, Getzler does more
by constructing a full symbol calculus and recovering the full Mehler kernel,
not just the $\hat{A}$-genus. In this article, we will use the techniques
developed by Berline–Vergne to uncover the geometry behind the Mehler kernel.
Here is the approach: following Berline–Vergne we will use the equivariant
averages (1) and heat kernel asymptotics of the operator $\Delta+\pi^{*}k/4$
on $P_{Spin}(M)$ to obtain an asymptotic expansion of $e^{-t\not{D}^{2}}$.
What we will find is that the terms of the heat kernel asymptotic expansion
are expressed as Gaussian averages along the fibers of $P_{Spin}(M)$. From
here we will combine the Riemannian geometry of $P_{Spin}(M)$ and the Getzler
rescaling on the base $M$ to lift the Getzler rescaling to $P_{Spin}(M)$ (see
Sec 4.2). The combination of the Getzler rescaling and the Gaussian averages
will convert the problem to an evaluation of Gaussian-Grassman integrals. The
latter have already been developed by Berline–Vergne, our only addition will
be to work with Taylor expansions of such integrals. The added insight is that
the Gaussian term of the Mehler kernel is governed by the geodesic distance
function on $P_{Spin}(M)$.

######  Theorem 1.2.

Fix $p\in P_{Spin}(M)$, $\pi(p)=x$, and $v\in\mathcal{H}_{p}$ small. Consider
the function $\Psi$ defined for $A\in\mathfrak{spin}(n)$ small

$\displaystyle\Psi(A)$ $\displaystyle=\left\langle
v,\left(\frac{I-\textup{exp}(-\tau(A\cdot\Omega_{p})/2)}{\tau(A\cdot\Omega_{p})/2}\right)^{-1}v\right\rangle.$

Then one has (after making an identification
$\bigwedge\mathbb{R}^{n}\simeq\bigwedge T^{*}_{x}M$)

$\displaystyle\Psi(2e\wedge e^{*})$ $\displaystyle=\left\langle
v,\frac{R_{x}}{2}\coth\left(\frac{R_{x}}{2}\right)v\right\rangle$

When studying the asymptotics of the Getzler-rescaled heat kernel through the
lenses of the geometry on $P_{Spin}(M)$, we fully recover the Mehler kernel.

######  Theorem 1.3.

Fix $p\in P_{Spin}(M)$, $\pi(p)=x$, and $v\in\mathcal{H}_{p}$ small. For
$0<|u|\leq 1$, we have

$\displaystyle\sigma(k_{u^{2}}(\exp_{p}(uv),p))$ $\displaystyle\sim(4\pi
u)^{-n}\sum_{j=0}^{n/2}u^{2j}\left(\textup{det}^{1/2}\left(\frac{R_{x}/2}{\sinh(R_{x}/2)}\right)\textup{exp}\left(-\frac{1}{4}\left\langle
v,\frac{R_{x}}{2}\coth\left(\frac{R_{x}}{2}\right)v\right\rangle\right)\right)_{2j}$
$\displaystyle\hskip
28.45274pt+u^{-n+1}\sum_{j=0}^{n/2}u^{2j}\omega_{2j}(\vec{v})+\cdots$

where $\omega_{2j}(v)$ is analytic in $v$. Evaluating $\lim_{u\rightarrow
0}u^{n}\sum_{j=0}^{n}u^{-j}\sigma_{j}(k_{u^{2}}(\exp_{p}(uv),p))$ gives

$(4\pi)^{-n/2}\textup{det}^{1/2}\left(\frac{R_{x}/2}{\sinh(R_{x}/2)}\right)\exp\left(-\frac{1}{4}\left\langle
v,\frac{R_{x}}{2}\coth\left(\frac{R_{x}}{2}\right)v\right\rangle\right).$

### Acknowledgments

The author is indebted to Matthew Bernstein and Sergio Zamora Barrera who gave
many insightful comments to the first draft of the article. The author is
further indebted to Ahmad Reza Haj Saeedi Sadegh for the exciting discussions
on this topic which influenced this work.

##  2 The Setup

We briefly orient the reader with our set of notations and background theorems
we will be using throughout the article. We consider $(M^{n},g)$ to be a
closed, oriented, spin Riemannian manifold of even dimension $n$. We choose an
equivariant double cover $P_{Spin}(M)$ of $P_{SO}(M)$ given by the diagram
below (R is the right action)

${P_{Spin}(M)\times\textnormal{Spin}(n)}$${P_{Spin}(M)}$${P_{SO}(M)\times\textnormal{SO}(n)}$${P_{SO}(M)}$$\scriptstyle{R}$$\scriptstyle{p\times\widetilde{Ad}}$$\scriptstyle{p}$$\scriptstyle{R}$

If we let $\omega^{LC}\in\Omega^{1}_{Ad,v}(P_{SO}(M),\mathfrak{so}(n))$ denote
the Levi-Civita connection 1-form, then we obtain the induced spinorial Levi-
Civita connection 1-form
$\omega^{LC}_{s}:=\tau^{-1}\left(p^{*}\omega^{LC}\right)\in\Omega^{1}_{Ad,v}(P_{Spin}(M),\mathfrak{spin}(n))$
where
$\tau=D(\widetilde{Ad}):\mathfrak{spin}(n)\xrightarrow{\sim}\mathfrak{so}(n)$.
If $\rho:\textnormal{Spin}(n)\rightarrow U(\wedge\mathbb{C}^{n/2})$ denotes
the complex unitary spinor representation, then we form the complex vector
bundle of spinors over $M$ via
$\mathscr{S}:=P_{Spin}(M)\times_{\rho}\wedge\mathbb{C}^{n/2}$. Since the
spinor representation $\rho$ is unitary, the spinor bundle $\mathscr{S}$ comes
equipped with a Hermitian fiber metric. The spinor bundle comes equiped with
the spinorial Levi-Civita connection, denoted $\nabla^{LC}$, which is defined
by the commutative diagram

${\Omega_{\rho,h}^{k}(P_{Spin}(M),\wedge\mathbb{C}^{n/2})}$${\Omega^{k+1}_{\rho,h}(P_{Spin}(M),\wedge\mathbb{C}^{n/2})}$${\Omega^{k}(M,\mathscr{S})}$${\Omega^{k+1}(M,\mathscr{S})}$$\scriptstyle{d+\rho\left(\omega^{LC}_{s}\right)\wedge}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{d^{\nabla^{LC}}}$

The Levi-Civita connection on $\mathscr{S}$ is compatible with the Hermitian
fiber metric. The spinor bundle comes with an action of the Clifford bundle of
$T^{*}M$,

$c:\Gamma(\mathbb{C}\ell(T^{*}M,g))\times\Gamma(\mathscr{S})\rightarrow\Gamma(\mathscr{S})$

By simplicity and dimension comparison we have that
$\mathbb{C}\ell(T^{*}M,g)\simeq_{c}\textnormal{End}{\mathscr{S}}$ where the
isomorphism is of algebra-bundles over $M$. The Clifford action has the
property that $c(\omega)^{*}=-c(\omega)$, for every $\omega\in\Gamma(T^{*}M)$,
where the ∗ denotes the adjoint operation in
$\Gamma(\textnormal{End}{\mathscr{S}})$ given by the Hermitian fiber metric.
This allows us to define the main operator of interest for us, the spinor
Dirac operator $\not{D}$, given by the following diagram

${\Gamma(\mathscr{S})}$${\Omega^{1}(M,\mathscr{S})}$${\Gamma(\mathscr{S}).}$$\scriptstyle{\not{D}}$$\scriptstyle{\nabla^{LC}}$c

The orientation on $M$ guarantees the existence of the volume form
$dV\in\Gamma(\wedge^{n}T^{*}M)$. We define the complex volume form
$dV_{\mathbb{C}}:=i^{n/2}dV$, which has the property that
$c(dV_{\mathbb{C}})^{2}=1$. This allows us to introduce a
$\mathbb{Z}_{2}$-grading on the spinor bundle via $\mathscr{S}^{\pm}:=(1\pm
c(dV_{\mathbb{C}}))\mathscr{S}$. All of the structure introduced allows us to
conclude that $\not{D}$ is an odd, self-adjoint, first order elliptic operator
on $\Gamma(\mathscr{S})$. In particular, the operator

$\not{D}^{+}:=\not{D}|_{\Gamma(\mathscr{S}^{+})}:\Gamma(\mathscr{S}^{+})\longrightarrow\Gamma(\mathscr{S}^{-})$

is a first order elliptic operator between the sections of $\mathscr{S}^{+}$
and $\mathscr{S}^{-}$. We wish to compute its Fredholm index.

###  2.1 Heat Flow and Index Theory

The classic route to computing $\textnormal{index}{\,\not{D}^{+}}$ is to study
the interplay between the local coefficients of the operator $\not{D}$ and the
geometry of $(M,g)$. The first step is to study heat flow on spinors.
Functional analytic properties of $\not{D}$ guarantee the existence of the
heat semi-group $\\{e^{-t\not{D}^{2}}\\}_{t\geq 0}$ as a semi-group of bounded
operators acting on $L^{2}(M,\mathscr{S})$. Further Sobolev theory guarantees
the existence of a smooth time dependent kernel
$k_{t}\in\Gamma(\mathscr{S}\boxtimes\mathscr{S}^{*})$ for $t>0$, such that

  * •

$e^{-t\not{D}^{2}}s(x)=\int_{M}k_{t}(x,y)s(y)\text{d}V(y)$,
$s\in\Gamma(\mathscr{S})$

  * •

$(\partial_{t}+\not{D}^{2}_{x})k_{t}(x,y)\equiv 0$ for all
$(t,x,y)\in(0,\infty)\times M\times M$.

Thus $e^{-t\not{D}^{2}}$ is a smoothing operator, and we call $k_{t}$ the heat
kernel. The $\pm$-grading on $\mathscr{S}$ induces a $\pm$-grading on
$L^{2}(M,\mathscr{S})$ and thus a $\pm$-grading on
$B(L^{2}(M,\mathscr{}{S}))$. We use this to define a graded trace
$\text{Str}:\mathscr{L}^{1}(L^{2}(M,\mathscr{S}))\rightarrow\mathbb{C}$, via
the formula

$\text{Str}(T):=\textnormal{Tr}(c(dV_{\mathbb{C}})T),\hskip
14.22636ptT\in\mathscr{L}^{1}(L^{2}(M,\mathscr{S})).$

The reason for studying heat flow in this setting is because of the Mckean-
Singer formula [9], which computes $\text{Index}{\,\not{D}^{+}}$ as

$\text{Index}{\,\not{D}^{+}}=\text{Str}(e^{-t\not{D}^{2}}),\hskip
14.22636ptt>0.$

Using the heat kernel, we conclude that

$\displaystyle\text{Index}{\,\not{D}^{+}}$
$\displaystyle=\text{Str}(e^{-t\not{D}^{2}})$
$\displaystyle=\int_{M}\text{str}(k_{t}(x,x))dV(x).$

where $\text{str}:\Gamma(\textnormal{End}{\mathscr{S}})\rightarrow
C^{\infty}(M)$ is the local supertrace given by

$\text{str}(T):=\text{tr}(c(dV_{\mathbb{C}})T),\hskip
14.22636ptT\in\Gamma(\textnormal{End}\mathscr{S}).$

The goal of _local index theory_ is to understand the small time behaviour of
$\text{str}(k_{t}(x,x))$. The reason for doing this is as follows. Functional
analytic arguments show that as $t\rightarrow\infty$, the heat kernel
approaches the smooth kernel given by projection onto the kernel of $\not{D}$
and in particular completely delocalizes (by delocalize we mean that when
evaluating the kernel on a section, the result depends on the values of the
section all across the manifold, rather than only local values of the given
section). Thus we conclude that in the limit $t\rightarrow\infty$, the kernel
$k_{t}(x,y)$ shouldn’t contain any local geometric information. However, in
the limit $t\rightarrow 0^{+}$, functional analytic arguments show that the
kernel $k_{t}(x,y)$ localizes around the diagonal of $M\times M$. Moreover,
intuition tells us that the small time behaviour of heat flow should be
governed by the local geometry of our manifold $M$ and the bundle
$\mathscr{S}$.

###  2.2 Differential Forms and The Local Supertrace

As we mentioned earlier, there needs to be a bridge between the local
coefficients of our operator and the local geometry of the manifold. In the
spinorial setting it is given by the isomorphism
$\Gamma(\mathbb{C}\ell(T^{*}M,g))\simeq\Gamma(\textnormal{End}\mathscr{S})$.
More precisely, we have that $\mathbb{C}\ell(T^{*}M,g)$ is isomorphic, as a
vector bundle, to $\wedge T^{*}M^{\mathbb{C}}$, which is given by

$\sigma:\mathbb{C}\ell(T^{*}M,g)\xrightarrow{\sim}\wedge
T^{*}M^{\mathbb{C}},\hskip 14.22636pt\sigma(e^{i_{1}}\cdots
e^{i_{j}})=e^{i_{1}}\wedge\cdots\wedge e^{i_{j}},$

where $\\{e^{i}\\}_{i=1}^{n}$ is a local orthonormal frame for $T^{*}M$. This
means that we can view a section $T\in\Gamma(\textnormal{End}\mathscr{S})$ as
Clifford multiplication by a differential form on the base $M$. Part of the
utility in this description of $\Gamma(\textnormal{End}\mathscr{S})$ is in its
ability to express str in geometric terms. To see this, first define the
_Berezin integral_ $\mathcal{B}:\Gamma(\wedge T^{*}M^{\mathbb{C}})\rightarrow
C^{\infty}(M)$, which is

$\mathcal{B}(\omega)=\omega_{n},$

where $\omega_{n}dV$ is the component of $\omega$ in
$\wedge^{n}T^{*}M^{\mathbb{C}}$. Since $\wedge T^{*}M^{\mathbb{C}}$ is a
bundle of graded commutative algebras, the Berezin integral is a graded trace.
Moreover, given
$T\in\Gamma(\textnormal{End}\mathscr{S})\simeq\Gamma(\mathbb{C}\ell(T^{*}M,g))$,
we have

$\text{str}(T)=(2/i)^{n/2}\mathcal{B}(\sigma(T)).$

##  3 A Recap of Getzler’s Work

For our purposes, the topic in Getzler’s work we want to focus on is the
_Getzler rescaling_ appearing in [8]. The key will be to use the differential
form perspective on $\Gamma(\textnormal{End}\mathscr{S})$ to define a symbol
calculus for $\Gamma(\mathscr{S}\boxtimes\mathscr{S}^{*})$ which will allow us
to understand the local behaviour of
$\kappa\in\Gamma(\mathscr{S}\boxtimes\mathscr{S}^{*})$ around the diagonal in
$M\times M$.

######  Definition 3.1.

Consider a smooth kernel
$\kappa\in\Gamma(\mathscr{S}\boxtimes\mathscr{S}^{*})$, a fixed point $y\in
M$, and a normal neighborhood $(U_{y},\vec{x})$ of $y$. For a given $x\in
U_{y}$, let $P_{x\rightarrow
y}:\mathscr{S}_{x}\xrightarrow{\sim}\mathscr{S}_{y}$ denote parallel
translation along the unit speed radial geodesic connecting $x$ and $y$ in
$U_{y}$. We obtain

$\bm{\kappa}_{y}(\vec{x}):=P_{x\rightarrow y}(\kappa(x,y))\in
C^{\infty}(U_{y},\textnormal{End}\mathscr{S}_{y}),\hskip
14.22636ptx=\exp^{M}_{y}(\vec{x})$

Using
$\textnormal{End}\mathscr{S}_{y}\simeq_{c}\mathbb{C}\ell(T^{*}_{y}M)\simeq_{\sigma}\wedge
T^{*}_{y}M^{\mathbb{C}}$, we get

$\sigma(\bm{\kappa}_{y}(\vec{x}))\in C^{\infty}(U_{y},\wedge
T^{*}_{y}M^{\mathbb{C}})$

The _Getzler rescaling_ of $\kappa$ at $y\in M$ is defined to be

$\delta_{u,y}(\kappa)(\vec{x}):=\sum_{j=0}^{n}u^{-j}\sigma_{j}(\bm{\kappa}_{y}(u\vec{x})),\hskip
14.22636pt0<|u|\leq 1.$

Note that if we allow $u$ to vary then the Getzler rescaling of $\kappa$ at
$y$ may be viewed as a smooth function

$\delta_{y}(\kappa):[-1,1]^{\times}\times U_{y}\rightarrow\wedge
T^{*}_{y}M^{\mathbb{C}},$

where $[-1,1]^{\times}$ denotes $[-1,1]$ without $0$.

######  Definition 3.2.

We say that $\kappa\in\Gamma(\mathscr{S}\boxtimes\mathscr{S}^{*})$ has Getzler
order $m\in\mathbb{Z}$ at $y\in M$ if $\delta_{y}(\kappa)$ extends past $u=0$
to a smooth function $\delta_{y}(\kappa):[-1,1]\times U_{y}\rightarrow\wedge
T^{*}_{y}M^{\mathbb{C}}$. In this case, the limit below

$\sigma^{G}_{m,y}(\kappa)(\vec{x}):=\lim_{u\rightarrow
0}u^{m}\delta_{u,y}(\kappa)(\vec{x})\in S(T^{*}M)\otimes\wedge
T^{*}_{y}M^{\mathbb{C}}.$

defines the _Getzler symbol_ of $\kappa$ at $y\in M$. Elements of
$S(T^{*}M)\otimes\wedge T^{*}_{y}M^{\mathbb{C}}$ are to be viewed as
polynomials on $T_{y}M$ with coefficients in the algebra $\wedge
T^{*}_{y}M^{\mathbb{C}}$.

The way this computation is done in practice is to Taylor expand
$\delta_{u,y}(\kappa)(\vec{x})$ in $\vec{x}$ and collect terms of the same $u$
power. When this is done, an aymptotic expansion of
$\delta_{u,y}(\kappa)(\vec{x})$ is obtained that has the form

$\displaystyle\delta_{u,y}(\kappa)(\vec{x})$
$\displaystyle\sim\sum_{j=-n}^{\infty}u^{j}\gamma_{-j}(\vec{x})$
$\displaystyle\sim
u^{m}\gamma_{-m}(\vec{x})+u^{m+1}\gamma_{-m-1}(\vec{x})+\cdots,\hskip
14.22636ptm\geq-n$

where each $\gamma_{j}(\vec{x})$ is a polynomial in $\vec{x}$ whose
coefficients lie in the algebra $\wedge T^{*}_{y}M^{\mathbb{C}}$. The Getzler
symbol of $\kappa$ at $y$ will be the first $m$ such that $\gamma_{-m}\neq 0$,

$\sigma^{G}_{-m,y}(\kappa)(\vec{x})=\gamma_{-m}(\vec{x})$

It is clear from its definition that the Getzler symbol of $\kappa$ gives
information about the local behavior of $\kappa$ around the diagonal of
$M\times M$. Moreover, we have a relation for computing local supertraces. If
the Getzler order of $\kappa$ at y is $m$, then

$\text{str}(\kappa(y,y))=\begin{cases}0\quad&\text{if}\,\,\,m<n\\\
(2/i)^{n/2}\mathcal{B}\big{(}\sigma^{G}_{n,y}(\kappa)(\vec{0})\big{)}\quad&\text{if}\,\,\,m=n\\\
\end{cases}$

A slight modification of this rescaling will be needed to deal with time
dependent sections of $\mathscr{S}\boxtimes\mathscr{S}^{*}$.

######  Definition 3.3.

Suppose $\kappa_{t}$ is a smooth time dependent section of
$\mathscr{S}\boxtimes\mathscr{S}^{*}$, $t>0$. Repeating the construction of
(3.1), we obtain a smooth time dependent function

$\sigma(\bm{\kappa}_{t,y})(\vec{x})\in C^{\infty}((0,\infty)\times
U_{y},\wedge T^{*}_{y}M^{\mathbb{C}})$

The _parabolic Getzler rescaling_ of $\kappa_{t}$ at $y$ to be

$\delta_{u,y}(\kappa_{t})(\vec{x}):=\sum_{j=0}^{n}u^{-j}\sigma_{j}(\bm{\kappa}_{u^{2}t,y}(u\vec{x})),\hskip
14.22636pt0<|u|\leq 1.$

We say in this case that $\kappa_{t}$ has _parabolic Getzler order_
$m\in\mathbb{Z}$ at $y\in M$ if $u^{m}\delta_{u,y}(\kappa_{t})$ extends past
$u=0$ to a smooth function
$u^{m}\delta_{u,y}(\kappa_{t}):[-1,1]\times(0,\infty)\times
U_{y}\rightarrow\wedge T^{*}_{y}M^{\mathbb{C}}$ and define the _parabolic
Getzler symbol_ of $\kappa_{t}$ via the limit below

$\sigma^{Par-G}_{m,y}(\kappa_{t})(\vec{x}):=\lim_{u\rightarrow
0}u^{m}\delta_{u,y}(\kappa_{t})(\vec{x})\in C^{\infty}((0,\infty)\times
U_{y},\wedge T^{*}_{y}M^{\mathbb{C}}).$

It is not always the case that if we are given $\kappa_{t}$, its parabolic
Getzler rescaling $\delta_{u,y}(\kappa_{t})(\vec{x})$ will have good behaviour
as $u\rightarrow 0$. To take an example, consider multiplying _any_
$\kappa\in\Gamma(\mathscr{S}\boxtimes\mathscr{S}^{*})$ by $e^{-1/t}$. The time
dependent section $e^{-1/t}\kappa$ will not have good rescaled behaviour in
the limit as $u\rightarrow 0$. Part of the reason for this is that as
$t\rightarrow 0$, we do not have any amount of control on the behaviour of a
general $\kappa_{t}$, i.e. we cannot Taylor expand at $t=0$. However, it will
be the case for us that the rescaled heat kernel has great behaviour as
$u\rightarrow 0$. We aim to understand this behaviour, and our main technique
will be to follow Berline–Vergne and lift the problem to $P_{Spin}(M)$.

##  4 A Recap of Berline-Vergne’s Approach

In the approach of Berline–Vergne [5], one should lift the heat kernel of
$e^{-t\not{D}^{2}}$ to $P_{Spin}(M)$. In doing so, one is allowed to use the
extra symmetries present in $P_{Spin}(M)$ to enable a simple approach to the
small time asymptotics of $e^{-t\not{D}^{2}}$. Let $\mathcal{V}$ denote the
vertical subbundle of $TP_{Spin}(M)$. If we consider
$\langle\cdot,\cdot\rangle:\mathfrak{spin}(n)\rightarrow\mathbb{R}$ to be an
Ad-$\textnormal{Spin}(n)$-invariant inner product on $\mathfrak{spin}(n)$,
then using the global trivialization of $\mathcal{V}\simeq
P_{Spin}(M)\times\mathfrak{spin}(n)$ allows us to transfer the inner product
$\langle\cdot,\cdot\rangle$ to a fiber metric on $\mathcal{V}$. Furthermore,
if we let $\mathcal{H}:=\textnormal{ker}\,\omega^{LC}_{s}$, then
$\pi^{*}TM\simeq\mathcal{H}$ and we use this isomorphism to pull the metric
$g$ on $M$ to a fiber metric on $\mathcal{H}$. The splitting
$TP_{Spin}(M)=\mathcal{V}\oplus\mathcal{H}$ defines a Riemannian geometry on
$P_{Spin}(M)$ by declaring the sum $\mathcal{V}\oplus\mathcal{H}$ to be
orthogonal. We note that this geometry on $P_{Spin}(M)$ is acted on
isometrically by the right action of $\textnormal{Spin}(n)$. Now let
$\Delta^{S}$ denote the scalar (or vector valued) Riemannian Laplacian on
$P_{Spin}(M)$.

######  Proposition 4.1 ([5]).

We have the following commutative diagram

${C^{\infty}(P_{Spin}(M),\wedge\mathbb{C}^{n/2})^{\rho}}$${C^{\infty}(P_{Spin}(M),\wedge\mathbb{C}^{n/2})^{\rho}}$${\Gamma(\mathscr{S})}$${\Gamma(\mathscr{S})}$$\scriptstyle{\Delta^{S}+\pi^{*}k/4-n(n-1)/2}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$$\scriptstyle{\not{D}^{2}}$

Recall that the product representation
$\rho\times\rho^{t}:\textnormal{Spin}(n)\times\textnormal{Spin}(n)\rightarrow\textnormal{End}\wedge\mathbb{C}^{n/2}$
given by

$(\rho\times\rho^{t})(g,h)T=\rho(g)T\rho(h)^{-1},\hskip
14.22636pt(g,h)\in\textnormal{Spin}(n)\times\textnormal{Spin}(n),\hskip
2.84544ptT\in\textnormal{End}\wedge\mathbb{C}^{n/2}$

gives rise to the following isomorphism of vector bundles

$\Gamma(\mathscr{S}\boxtimes\mathscr{S}^{*})\simeq
C^{\infty}(P_{Spin}(M)\times
P_{Spin}(M),\textnormal{End}\wedge\mathbb{C}^{n/2})^{\rho\times\rho^{t}}.$

Thus, for each $t>0$, we may consider the heat kernel $k_{t}$ as a smooth
function on $P_{Spin}(M)\times P_{Spin}(M)$ with values in
$\textnormal{End}\wedge\mathbb{C}^{n/2}$ which is equivariant with respect to
the $\textnormal{Spin}(n)\times\textnormal{Spin}(n)$ action. Using (4.1), we
obtain the following equality relating the heat kernel $h_{t}$ of
$e^{-t(\Delta^{S}+\pi^{*}k/4)}$ to $k_{t}$

$k_{t}(p,q)=e^{tn(n-1)/2}\int_{Spin(n)}h_{t}(p\cdot g,q)\rho(g)dg,\hskip
14.22636pt(p,q)\in P_{Spin}(M)\times P_{Spin}(M).$ (2)

###  4.1 Heat Kernel Asymptotics

The operator $\Delta^{S}+\pi^{*}k/4$ is a generalized Laplacian which acts on
scalar (or vector) valued functions on $P_{Spin}(M)$. Following [4], there is
a formal power series

$(4\pi t)^{-n(n+1)/4}e^{-d(p,q)^{2}/4t}\sum_{j=0}^{\infty}t^{j}\Phi_{j}(p,q)$

with $\Phi_{j}$ smooth scalar functions on $P_{Spin}(M)\times P_{Spin}(M)$
satisfying the following properties:

  * (I)

$d(p,q)$ is the Riemannian distance on $P_{Spin}(M)$

  * (II)

There is a small neighborhood $U_{\Delta}$ of the diagonal such that each
$\Phi_{j}$ is supported in this neighborhood

  * (III)

In a neighborhood $V_{\Delta}\subset U_{\Delta}$ of the diagonal, the formal
power series formally solves the heat equation

$(\partial_{t}+\Delta^{S}_{p}+\pi^{*}k(p)/4)(4\pi
t)^{-n(n+1)/4}e^{-d(p,q)^{2}/4t}\sum_{j=0}^{\infty}t^{j}\Phi_{j}(p,q)=0$

  * (IV)

In the neighborhood $V_{\Delta}$, the $\Phi_{j}$ are given by

$\displaystyle\Phi_{0}(\exp^{S}_{p}(\vec{x}),p)$
$\displaystyle=\text{det}^{-1/2}((\exp^{S}_{p})_{*,\vec{x}})$
$\displaystyle\Phi_{j}(\exp^{S}_{p}(\vec{x}),p)$
$\displaystyle=-\text{det}^{-1/2}((\exp^{S}_{p})_{*,\vec{x}})\int_{0}^{1}t^{j-1}\left(\Delta^{S}_{p}+\pi^{*}k(p)/4\right)\Phi_{j-1}(\exp^{S}_{p}(\vec{tx}),p)dt$

Lastly, the formal power series above approximates the heat kernel $h_{t}$ in
the following sense:

######  Theorem 4.2 ([4] Ch.2, [10] Ch.7).

For every $j,\ell\geq 0$ there exists $k_{j}$ such that for every $k\geq
k_{j}$ there is a $C_{j,k,\ell}>0$ such that

$\left\lVert h_{t}-(4\pi
t)^{-n(n+1)/4}e^{-d^{2}/4t}\sum_{i=0}^{k}t^{i}\Phi_{i}\right\rVert_{C^{\ell}}\leq
C_{j,k,\ell}t^{j},$

where $||\cdot||_{C^{\ell}}$ denotes the $C^{\ell}$-norm of
$C^{l}(P_{Spin}(M)\times
P_{Spin}(M),\textnormal{End}(\wedge_{\mathbb{C}}\mathbb{C}^{n/2}))$. Moreover,
the formal sum $\partial_{t}^{k}(4\pi
t)^{-n(n+1)/4}e^{-d^{2}/4t}\sum_{j=0}^{\infty}t^{j}\Phi_{j}$ remains
asymptotic to $\partial_{t}^{k}h_{t}$ under any finite amount of partial
derivatives in $t$.

Applying (4.2) to our equivariant formula for $k_{t}$, the compactness of
$\textnormal{Spin}(n)$ shows that the equivariant averages remain asymptotic.
Thus, we have

$k_{t}(p,q)\sim\sum_{j=0}^{\infty}t^{j}(4\pi
t)^{-n(n+1)/4}\int_{\textnormal{Spin}(n)}e^{-d(p\cdot
g,q)^{2}/4t}\Phi_{j}(p\cdot g,q)\rho(g)dg$

###  4.2 The Getzler Rescaling on $P_{Spin}(M)$

Let us now discuss what the Getzler rescaling looks like on $P_{Spin}(M)$.
Consider $\kappa\in\Gamma(\mathscr{S}\boxtimes\mathscr{S}^{*})$, $y\in M$,
$p\in P_{Spin}(M)$ with $\pi(p)=y$. Note that under the isomorphism
$\mathcal{H}_{p}\simeq T_{y}M$, if $v\in\mathcal{H}_{p}$, one has
$\pi\exp^{S}_{p}(v)=\exp^{M}_{y}(v)$. Thus if we think of $\exp^{S}_{p}(v)$ as
the radial parallel propagation of the spin frame $p$ along $\exp^{M}_{y}(v)$,
then we have that the operator $P_{\exp^{M}_{y}v\rightarrow
y}\kappa(\exp^{M}_{y}(v),y)$ on $\mathscr{S}_{y}$ has matrix
$\kappa(\exp^{S}_{p}(v),p)\in\textnormal{End}(\wedge\mathbb{C}^{n/2})$ if we
use the spin frame $p$ at $y$. Combining this with
$\textnormal{End}(\wedge\mathbb{C}^{n/2})\simeq_{c}\mathbb{C}\ell((\mathbb{R}^{n})^{*})\simeq_{\sigma}\wedge(\mathbb{R}^{n})^{*}$,
the matrix of the Getzler rescaled symbol $\delta_{u,y}(\kappa)(v)$ relative
to the spin frame $p$ is

$\sum_{j=0}^{n}u^{-j}\sigma_{j}(\kappa(\exp^{S}_{p}(uv),p)),\hskip
14.22636pt0<|u|\leq 1.$

Applying the parabolic Getzler rescaling to our heat kernel asymptotic
expansion above, we see that the asymptotic sum of interest is

$\displaystyle\delta_{u,y}$
$\displaystyle(k_{t})(v)=\sum_{j=0}^{n}u^{-j}\sigma_{j}(k_{u^{2}t}(\exp^{S}_{p}(uv),p))$
$\displaystyle\sim\sum_{k=0}^{\infty}\sum_{j=0}^{n}(u^{2}t)^{k}(4\pi
u^{2}t)^{-n(n+1)/4}u^{-j}\int_{\textnormal{Spin}(n)}e^{-d(\exp^{S}_{p}(uv)\cdot
g,p)^{2}/4u^{2}t}\Phi_{k}(\exp^{S}_{p}(uv)\cdot g,p)\sigma_{j}(\rho(g))dg$

We will focus for now on a particular term $\Phi_{j}$ in the asymptotic
expansion above, which gives

$(4\pi
u^{2}t)^{-n(n+1)/2}\sum_{j=0}^{n}u^{-j}\int_{\textnormal{Spin}(n)}e^{-d(\exp^{S}_{p}(uv)\cdot
g,p)^{2}/4u^{2}t}\Phi_{j}(\exp^{S}_{p}(uv)\cdot g,p)\sigma_{j}(\rho(g))dg$

The last simplification we make is to note that we can assume (by compactness
of $P_{Spin}(M)$) that the neighborhood $U_{\Delta}$ is contained in an
exponential tubular neighborhood of the diagonal $\Delta_{P_{Spin}}\subset
P_{Spin}(M)\times P_{Spin}(M)$. Thus, we may replace the above integral over
$\textnormal{Spin}(n)$ with an integral over $\mathfrak{spin}(n)$, and obtain

$(4\pi
u^{2}t)^{-n(n+1)/2}\sum_{j=0}^{n}u^{-j}\int_{\mathfrak{spin}(n)}e^{-d(\exp^{S}_{p}(uv)\cdot\exp
A,p)^{2}/4u^{2}t}\Phi_{j}(\exp^{S}_{p}(uv)\cdot\exp A,p)\sigma_{j}(\rho(\exp
A))J(A)dA$

where $J(A)$ is the Jacobian factor for exponential coordinates. It will
become apparent later that each such term in this asymptotic expansion has
parabolic Getzler order $n$. Since each such $\Phi_{j}$ term has a factor of
$(u^{2}t)^{j}$, we have that the only term that will be of any importance when
computing the Getzler symbol of $k_{t}$ is $\Phi_{0}$.

###  4.3 The Geometry of $P_{Spin}(M)$

We let $\Omega\in\Omega^{2}_{Ad,h}(P_{Spin}(M),\mathfrak{spin}(n))$ denote the
curvature of the distribution $\mathcal{H}$. Given $p\in P_{Spin}(M)$,
$A\in\mathfrak{spin}(n)$, we define the operator
$\tau(A\cdot\Omega_{p})\in\mathfrak{so}(\mathcal{H}_{p})$ via

$\langle\tau(A\cdot\Omega_{p})v,w\rangle_{\mathcal{H}_{p}}:=2\langle
A,\Omega_{p}(v,w)\rangle_{\mathfrak{spin}(n)}$

where $v,w\in\mathcal{H}_{p}$. Consider $x\in M$ and a point $p\in
P_{Spin}(M)_{x}$. We have

$\exp^{S}_{p}:T_{p}P_{Spin}(M)\rightarrow P_{Spin}(M)$

A bit of Jacobi field gymnastics (see [4] Ch.5 for details) will show that
given $A\in\mathfrak{spin}(n)$ small, and using
$T_{q}P_{Spin}(M)\simeq\mathfrak{spin}(n)\oplus T_{x}M$ for $\pi(q)=x$, we
have

$(\exp^{S}_{p})_{*,A}=\left[\begin{array}[]{cc}\frac{I-\exp(-ad_{A})}{ad_{A}}&0\\\
0&\frac{I-\exp(-\tau(A\cdot\Omega_{p})/2)}{\tau(A\cdot\Omega_{p})/2}\end{array}\right]$

In particular

$\text{det}(\exp^{S}_{p})_{*,A}=\text{det}\left(\frac{I-\exp(-ad_{A})}{ad_{A}}\right)\cdot\text{det}\left(\frac{I-\exp(-\tau(A\cdot\Omega_{p})/2)}{\tau(A\cdot\Omega_{p})/2}\right)$

Thus, when computing $\Phi_{0}(p\cdot\exp A,p)$, we have

$\displaystyle\Phi_{0}(p\cdot\exp A,p)$
$\displaystyle=\text{det}^{-1/2}(\exp^{S}_{p})_{*,A}$
$\displaystyle=\text{det}^{-1/2}\left(\frac{\sinh
ad_{A}/2}{ad_{A}/2}\right)\cdot\text{det}^{-1/2}\left(\frac{\sinh\tau(A\cdot\Omega_{p})/4)}{\tau(A\cdot\Omega_{p})/4}\right).$

Next, consider $p\in P_{Spin}(M)$, $v\in\mathcal{H}_{p}$ and
$A\in\mathfrak{spin}(n)$, both small. Then further Jacobi field backflips (see
[4] Ch.6) lead one to the small $u$ Taylor expansion

$d(\exp^{S}_{p}uv\cdot\exp
A,p)^{2}=|A|^{2}+u^{2}\Big{\langle}v,\left(\frac{I-\exp(-\tau(A\cdot\Omega_{p})/2)}{\tau(A\cdot\Omega_{p})/2}\right)^{-1}v\Big{\rangle}+u^{3}f(u,A)$

for a smooth function $f$ in $(u,A)$. Now observe that since
$\tau(A\cdot\Omega_{p})\in\mathfrak{so}(\mathcal{H}_{p})$, we have $\langle
v,\tau(A\cdot\Omega_{p})v\rangle=0$. Thus we have

$\Big{\langle}v,\left(\frac{I-\exp(-\tau(A\cdot\Omega_{p})/2)}{\tau(A\cdot\Omega_{p})/2}\right)^{-1}v\Big{\rangle}=\langle
v,(\tau(A\cdot\Omega_{p})/4)\coth(\tau(A\cdot\Omega_{p})/4)v\rangle$

###  4.4 The Grassmann Calculus

We recall ([4] Ch.5) how one is to compute small time asymptotics of integrals
of the form

$(4\pi
t)^{-n(n-1)/4}\int_{\mathfrak{spin}(n)}e^{-|A|^{2}/4t}\Psi(A)\exp_{C}(A)dA$

where $\exp_{C}$ denotes the exponential of $A$ in
$\mathbb{C}\ell((\mathbb{R}^{n})^{*})$ and $\Psi$ is a decent smooth function
on $\mathfrak{spin}(n)$. The key is to define what it means for $\Psi$ to be
evaluated on a differential form in $\wedge^{even}(\mathbb{R}^{n})^{*}$. To do
this, note that if we restrict
$\sigma:\mathbb{C}\ell((\mathbb{R}^{n})^{*})\xrightarrow{\sim}\wedge(\mathbb{R}^{n})^{*}$
to $\mathfrak{spin}(n)$, we get the isomorphism

$\mathfrak{spin}(n)\simeq\wedge^{2}(\mathbb{R}^{n})^{*},\hskip
28.45274pt\sigma(e^{i}e^{j})=e^{i}\wedge e^{j}$

Given $A=\sum_{i<j}a_{ij}e^{i}e^{j}\in\mathfrak{spin}(n)$ and $\Psi\in
C^{\infty}(\mathfrak{spin}(n))$, a Taylor expansion at $A$ gives an element

$T_{A}(\Psi)\in S^{\infty}(\mathfrak{spin}(n)^{*}),$
$\Psi(A+x)\sim\sum_{\alpha}\frac{1}{\alpha!}\big{(}\partial_{e^{1}e^{2}}^{\alpha_{12}}\cdots\partial_{e^{n-1}e^{n}}^{\alpha_{n-1,n}}\Psi\big{)}(A)\prod_{i<j}x_{ij}^{\alpha_{ij}}$

Taking $e^{i}e^{j}$ as orthonormal gives an
Ad-$\textnormal{Spin}(n)$-invariant inner product on $\mathfrak{spin}$ which
allows us to identify $\mathfrak{spin}(n)$ with its dual
$\mathfrak{spin}(n)^{*}$. The evaluation of $\Psi$ at $A+e\wedge e^{*}$ is
defined by composing the Taylor expansion $T_{A}(\Psi)$ with
$\sigma:S^{\infty}(\mathfrak{spin}(n)^{*})\rightarrow\wedge^{even}(\mathbb{R}^{n})^{*}$

$\Psi(A+e\wedge
e^{*}):=\sigma\left(T_{A}(\Psi)\right)\in\wedge^{even}(\mathbb{R}^{n})^{*},$
$\Psi(A+e\wedge
e^{*})=\sum_{\alpha}\frac{1}{\alpha!}\big{(}\partial_{e^{1}e^{2}}^{\alpha_{12}}\cdots\partial_{e^{n-1}e^{n}}^{\alpha_{n-1,n}}\Psi\big{)}(A)\prod_{i<j}(e^{i}\wedge
e^{j})^{\alpha_{ij}}\in\wedge^{even}(\mathbb{R}^{n})^{*}$

To give two examples demonstrating the utility of the Grassmann calculus, we
first cite Berline-Vergne who showed that, when evaluating
$\Phi_{0}(p\cdot\exp A,p)$ on $2e\wedge e^{*}$ at $A=0$, one recovers

$\Phi_{0}(2e\wedge e^{*})=\text{det}^{1/2}(\frac{R_{y}/2}{\sinh R_{y}/2}),$

where $\pi(p)=y$. Our extension is to use the Grassman calculus to compute the
second order term of $d(\exp_{p}(uv)\cdot\exp A,p)^{2}$ on $2e\wedge e^{*}$.
What we find is that

$\langle v,(\tau(A\cdot\Omega)/4)\coth(\tau(A\cdot\Omega/4)v\rangle(2e\wedge
e^{*})=\langle v,\frac{R_{y}}{2}\coth(\frac{R_{y}}{2})v\rangle.$

Turning back to the evaluation of small time asymptotics of Gaussian integrals
on $\mathfrak{spin}(n)$, consider $\Psi$ a decent smooth function on
$\mathfrak{spin}(n)$. Recall that when $A$ is close to zero, when evaluating
$\sigma:\mathbb{C}\ell((\mathbb{R}^{n})^{*})\xrightarrow{\sim}\wedge((\mathbb{R}^{n})^{*})^{\mathbb{C}}$
on $\exp_{C}A$, we have

$\sigma(\exp_{C}A)=\mathscr{H}(\tau(A))\left(\exp_{\wedge}\sigma(A)\right),$
$\mathscr{H}(\tau(A))=\text{det}^{1/2}\left(\frac{\sinh(\tau(A)/2)}{\tau(A)/2}\right)\text{det}^{-1/2}\left(\frac{\tanh(\tau(A)/2)}{\tau(A)/2}\right)\bigwedge\left(\frac{\tanh(\tau(A)/2)}{\tau(A)/2}\right)^{1/2}.$

Note that $\mathscr{H}(\tau(A))$ is an _operator_ on
$\wedge(\mathbb{R}^{n})^{*}$. Thus, when apply the rescaling $t^{-j/2}$ on the
degree $j$ component of $\sigma(\exp_{C}A)$, denoted
$\delta_{t}\sigma(\exp_{C}A)$, we get

$\delta_{t}\sigma(\exp_{C}A)=\mathscr{H}(\tau(A))(\exp_{\wedge}\sigma(A)/t).$

Applying this to our Gaussian integral gives

$\displaystyle(4\pi
t)^{-n(n-1)/4}\int_{\mathfrak{spin}(n)}e^{-|A|^{2}/4t}\Psi(A)\delta_{t}\sigma(\exp_{C}A)dA$
$\displaystyle=$ $\displaystyle(4\pi
t)^{-n(n-1)/4}\int_{\mathfrak{spin}(n)}\mathscr{H}(\tau(A))$
$\displaystyle\exp\left(-\frac{|A-2e\wedge e^{*}|^{2}}{4t}\right)\Psi(A)dA$

which converges as $t\rightarrow 0^{+}$ to $\Psi(2e\wedge e^{*})$. It is clear
that if $\Psi$ also depends smoothly on $t$, for $t\in\mathbb{R}$, then a
Taylor expansion in $t$ allows for the following small $t$ asymptotic
expansion

$(4\pi
t)^{-n(n-1)/4}\int_{\mathfrak{spin}(n)}e^{-|A|^{2}/4t}\Psi(t,A)\delta_{t}\sigma(\exp_{C}A)dA\sim\sum_{k=0}^{\infty}\frac{t^{k}}{k!}\partial_{t}^{k}\Psi(0,2e\wedge
e^{*}).$

In particular,

$\lim_{t\rightarrow 0^{+}}(4\pi
t)^{-n(n-1)/4}\int_{\mathfrak{spin}(n)}e^{-|A|^{2}/4t}\Psi(t,A)\delta_{t}\sigma(\exp_{C}A)dA=\Psi(0,2e\wedge
e^{*}).$

To hint at the appearance of Mehler’s kernel, we have that if

$\Psi(v,A)=\exp(-\frac{1}{4}\langle
v,(\tau(A\cdot\Omega)/4)\coth(\tau(A\cdot\Omega/4)v\rangle)\Phi_{0}(p\cdot\exp
A,p)$

then evaluation of the Gaussian-Grassmann integral gives

$\displaystyle(4\pi
t)^{-n(n-1)/4}\int_{\mathfrak{spin}(n)}\mathscr{H}(\tau(A))$
$\displaystyle\exp\left(-\frac{|A-2e\wedge e^{*}|^{2}}{4t}\right)\Psi(v,A)dA$
$\displaystyle\xrightarrow[t\rightarrow
0^{+}]{}\text{det}^{1/2}\left(\frac{R_{y}/2}{\text{sinh}(R_{y}/2)}\right)\text{exp}\left(-\frac{1}{4}\left\langle
v\middle|\frac{R_{y}}{2}\text{coth}\left(\frac{R_{y}}{2}\right)\middle|v\right\rangle\right).$

The key to extracting the Mehler kernel from the Getzler rescaled heat kernel
asymptotic expansion will be to reduce the analysis to the above simple
computation.

##  5 The Getzler Symbol of The Heat Kernel

We begin our analysis of the Getzler rescaled heat kernel by restricting our
attention to a single term of our asymptotic expansion and show how a Mehler-
type kernel appears after rescaling. Thus consider the following term

$(4\pi
u^{2}t)^{-n(n+1)/4}\sum_{j=0}^{n}u^{-j}\int_{\mathfrak{spin}(n)}e^{-d(\exp^{S}_{p}(uv)\cdot\exp
A,p)^{2}/4u^{2}t}\Phi(\exp^{S}_{p}(uv)\cdot\exp A,p)\sigma_{j}(\rho(\exp
A))J(A)dA,$

where $\Phi$ is a smooth function on $P_{Spin}(M)\times P_{Spin}(M)$ with
support contained in $V_{\Delta}$. Using the small time asymptotics of the
distance function on $P_{Spin}(M)$, we can write the above integral as

$(4\pi
u^{2}t)^{-n(n+1)/4}\sum_{j=0}^{n/2}u^{-2j}\int_{\mathfrak{spin}(n)}e^{-|A|^{2}/4u^{2}t}\Psi(u,t,A)\sigma_{2j}(\exp_{C}A)dA$

with

$\Psi(u,t,v,A)=e^{-\langle
v,(\tau(A\cdot\Omega_{p})/4)\coth(\tau(A\cdot\Omega_{p})/4)v\rangle/4t}e^{-uf(u,A)/4t}\Phi(\exp_{p}^{S}(uv)\cdot\exp
A,p)J(A)$

Note that when $u=0$, we have

$\Psi(0,t,v,A)=e^{-\langle
v,(\tau(A\cdot\Omega_{p})/4)\coth(\tau(A\cdot\Omega_{p})/4)v\rangle/4t}\Phi(p\cdot\exp
A,p)J(A).$

Before doing anything too hasty, let us first re-express the above integral in
a simpler form and rescale the integral by $\sqrt{t}$, thus giving:

$(4\pi
t)^{-n/2}u^{-n}\int_{\mathfrak{spin}(n)}\mathscr{H}(\sqrt{t}\tau(A))\exp\left(-\frac{|A-2\sqrt{t}e\wedge
e^{*}|^{2}}{4u^{2}}\right)\Psi(u,t,v,\sqrt{t}A)dA.$

Recall that when computing the Getzler symbol we are concerned with the
behaviour as $u\rightarrow 0$ with fixed $(t,v)$. Multiplying the above
integral by $u^{n}$, we see that we have convergence as $u\rightarrow 0$ to
the Mehler-type kernel

$(4\pi t)^{-n/2}\Psi(0,t,v,2te\wedge e^{*})=(4\pi t)^{-n/2}\Phi(2te\wedge
e^{*})\text{exp}\left(-\frac{1}{4}\left\langle
v\middle|\frac{tR_{y}}{2}\text{coth}\left(\frac{tR_{y}}{2}\right)\middle|v\right\rangle\right).$

Thus we have that the parabolic Getzler rescaling, wehn multiplied by $u^{n}$,
extends continuously to $u=0$. To see why the extension is _smooth_ , simply
note that

$\partial_{u}(4\pi u^{2})^{-n(n-1)/4}\exp\left(-\frac{|A-2\sqrt{t}e\wedge
e^{*}|^{2}}{4u^{2}}\right)=2u\Delta_{\mathfrak{spin}(n)}(4\pi
u^{2})^{-n(n-1)/4}\exp\left(-\frac{|A-2\sqrt{t}e\wedge
e^{*}|^{2}}{4u^{2}}\right),$

and using integration by parts we may move the flat Laplacian
$\Delta_{\mathfrak{spin}(n)}$ to the other terms within the Gaussian-Grassmann
integral. Thus, we have shown that _every_ term in the equivariantly averaged
asymptotic expansion has parabolic Getzler order $n$. However, the $j$-th term
in the asymptotic expansion carries a $(u^{2}t)^{j}$ term which annihilates
the smooth extension at $u=0$. Thus, the only term within the asymptotic
expansion which extends smoothly to $u=0$, and is _not_ zero, is the
$j=0$-term whose smooth extenstion to $u=0$ is

$(4\pi
t)^{-n/2}\text{det}^{1/2}\left(\frac{tR_{y}/2}{\text{sinh}(tR_{y}/2)}\right)\text{exp}\left(-\frac{1}{4t}\left\langle
v\middle|\frac{tR_{y}}{2}\text{coth}\left(\frac{tR_{y}}{2}\right)\middle|v\right\rangle\right)$

Lastly, the $C^{k}$ estimates on the equivariantly averaged remainder term of
any sufficiently long finite expansion show that the remainder term will
extend to $0$ at $u=0$ in a differentiable manner up to order $k$, for $k$ as
large as we desire. Thus, we have shown that the parabolic Getzler order of
the spinor heat kernel $k_{t}$ is $n$ with

$\lim_{u\rightarrow 0}u^{n}\delta_{u,y}(k_{t})(v)=(4\pi
t)^{-n/2}\text{det}^{1/2}\left(\frac{tR_{y}/2}{\text{sinh}(tR_{y}/2)}\right)\text{exp}\left(-\frac{1}{4t}\left\langle
v\middle|\frac{tR_{y}}{2}\text{coth}\left(\frac{tR_{y}}{2}\right)\middle|v\right\rangle\right)$

## References

  * [1] Alvarez-Guamé, L. (1983). Supersymmetry and the Atiyah-Singer Index Theorem. In _Communications in Mathematical Physics_ , 90, 161-173.
  * [2] M.F. Atiyah, R. Bott, & V. K. Patodi, _On the heat equation and the index theorem_ , Invent. Math. 19 (1973), no. 4, 279–330.
  * [3] Atiyah, M. F., & Singer, I. M. (1968). The Index of Elliptic Operators: I. _Annals of Mathematics_. Vol 87. 484-530.
  * [4] Berline, N., Getzler, E., & Vergne, M., (2003). Heat kernels and Dirac operators. _Springer Science & Business Media_.
  * [5] Berline, N., & Vergne, M. (1985). A computation of the equivariant index of the Dirac operator. _Bulletin de la Société Mathématique de France_ , 113, 305-345.
  * [6] Bismut, J. M. (1984). The Atiyah—Singer theorems: a probabilistic approach. I. The index theorem. _Journal of functional analysis_ , 57(1), 56-99.
  * [7] Getzler, E. (1983). Pseudodifferential operators on supermanifolds and the Atiyah-Singer index theorem. _Communications in mathematical physics_ , 92(2), 163-178.
  * [8] Getzler, E. (1986). A short proof of the Atiyah-Singer index theorem. _Topology_ , 25, 111-117.
  * [9] McKean Jr, H. P., & Singer, I. M. (1967). Curvature and the eigenvalues of the Laplacian. _Journal of Differential Geometry_ , 1(1-2), 43-69.
  * [10] Roe, J. (1998). Elliptic Operators, Topology, and Asymptotic Methods. _Chapman & Hall/CRC Research Notes in Mathematics_ 395\.
  * [11] Witten, E. (1982). Constraints on Supersymmetry Breaking. _Nuclear Physics B_. 202. no. 2, 253-316.


# Adaptive Control of Differentially Private Linear Quadratic Systems

Sayak Ray Chowdhury1  Indian Institute of Science
Bangalore, India
Email<EMAIL_ADDRESS>Xingyu Zhou1  Wayne State University
Detroit, USA
Email<EMAIL_ADDRESS>Ness Shroff  The Ohio State University
Columbus, USA
Email<EMAIL_ADDRESS>
###### Abstract

In this paper we study the problem of regret minimization in reinforcement
learning (RL) under differential privacy constraints. This work is motivated
by the wide range of RL applications for providing personalized service, where
privacy concerns are becoming paramount. In contrast to previous works, we
take the first step towards _non-tabular_ RL settings, while providing a
rigorous privacy guarantee. In particular, we consider the adaptive control of
differentially private linear quadratic (LQ) systems. We develop the first
private RL algorithm,
$\mathrm{Private}\text{-}\mathrm{OFU}\text{-}\mathrm{RL}$ which is able to
attain a sub-linear regret while guaranteeing privacy protection. More
importantly, the additional cost due to privacy is only on the order of
$\frac{\ln(1/\delta)^{1/4}}{\varepsilon^{1/2}}$ given privacy parameters
$\varepsilon,\delta>0$. Through this process, we also provide a general
procedure for adaptive control of LQ systems under _changing regularizers_ ,
which not only generalizes previous non-private controls, but also serves as
the basis for general private controls.

11footnotetext: Equal contribution. This work was funded in part through NSF
grants: CNS-1901057 and CNS- 2007231, and an Office of Naval Research under
Grant N00014-17-1-241

##  I Introduction

Reinforcement learning (RL) is a control-theoretic problem, which adaptively
learns to make sequential decisions in an unknown environment through trial
and error. RL has shown to have significant success for delivering a wide
variety of personalized services, including online news and advertisement
recommendation [1], medical treatment design [2], natural language processing
[3], and social robot [4]. In these applications, an RL agent improves its
personalization algorithm by interacting with users to maximize the reward. In
particular, in each round, the RL agent offers an action based on the user’s
state, and then receives the feedback from the user (i.e., state information,
state transition, reward, etc.). This feedback is used by the agent to learn
the unknown environment and improve its action selection strategy.

However, in most practical scenarios, the feedback from the users often
encodes their sensitive information. For example, in a personalized healthcare
setting, the states of a patient include personal information such as age,
gender, height, weight, state of the treatment etc. Similarly, the states of a
virtual keyboard user (e.g., Google GBoard users) are the words and sentences
she typed in, which inevitably contain private information about the user.
Another intriguing example is the social robot for second language education
of children. The states include facial expressions, and the rewards contain
whether they have passed the quiz. Users may not want any of this information
to be inferred by others. This directly results in an increasing concern about
privacy protection in personalized services. To be more specific, although a
user might be willing to share her own information to the agent to obtain a
better tailored service, she would not like to allow third parties to infer
her private information from the output of the learning algorithm. For
example, in the healthcare application, we would like to ensure that an
adversary with arbitrary side knowledge cannot infer a particular patient’s
state from the treatments prescribed to her.

_Differential privacy_ (DP) [5] has become a standard mechanism for designing
interactive learning algorithms under a rigorous privacy guarantee for
individual data. Most of the previous works on differentially private learning
under partial feedback focus on the simpler bandit setting (i.e., no state
transition) [6, 7, 8, 9, 10]. For the general RL problem, there are only a few
works that consider differential privacy [11, 12, 13]. More importantly, only
the _tabula-rasa_ discrete-state discrete-action environments are considered
in these works. However, in real-world applications mentioned above, the
number of states and actions are often very large and can even be infinite.
Over the years, for various non-tabular environments, efficient and provably
optimal algorithms for _reward maximization_ or, equivalently, _regret
minimization_ have been developed (see, e.g., [14, 15, 16, 17, 18]). This
directly motivates the following question: _Is it possible to obtain the
optimal reward while providing individual privacy guarantees in the non-
tabular RL scenario?_

In this paper, we take the first step to answer the aforementioned question by
considering a particular non-tabular RL problem – adaptive control of linear
quadratic (LQ) systems, in which the state transition is a linear function and
the immediate reward (cost) is a quadratic function of the current state and
action. In particular, our main contributions can be summarized as follows.

  * •

First, we provide a general framework for adaptive control of LQ systems under
_changing regularizers_ using the optimism in the face of uncertainty (OFU)
principle, which covers both the extreme cases – non-private and fully private
LQ control.

  * •

We then develop the first private RL algorithm, namely
$\mathrm{Private}\text{-}\mathrm{OFU}\text{-}\mathrm{RL}$, for regret
minimization in LQ systems by adapting the _binary counting mechanism_ to
ensure differencial privacy.

  * •

In particular, we show that
$\mathrm{Private}\text{-}\mathrm{OFU}\text{-}\mathrm{RL}$ satisfies _joint
differential privacy_ (JDP), which, informally, implies that sensitive
information about a given user is protected even if an adversary has access to
the actions prescribed to all other users.

  * •

Finally, we prove that
$\mathrm{Private}\text{-}\mathrm{OFU}\text{-}\mathrm{RL}$ achieves a sub-
linear regret guarantee, where the regret due to privacy only grows as
$\frac{\ln(1/\delta)^{1/4}}{\varepsilon^{1/2}}$ with privacy levels
$\varepsilon,\delta\\!>\\!0$ implying that a high amount of privacy (low
$\varepsilon,\delta$) comes at a high cost and vice-versa.

##  II Preliminaries

###  II-A Stochastic Linear Quadratic Control

We consider the discrete-time episodic linear quadratic (LQ) control problem
with $H$ time steps at every episode. Let $x_{h}\\!\in\\!\mathbb{R}^{n}$ be
the state of the system, $u_{h}\\!\in\\!\mathbb{R}^{d}$ be the control and
$c_{h}\\!\in\\!\mathbb{R}$ be the cost at time $h$. An LQ problem is
characterized by linear dynamics and a quadratic cost function

$x_{h+1}\\!=\\!Ax_{h}+Bu_{h}+w_{h},\;\;c_{h}\\!=\\!x_{h}^{\top}Qx_{h}+u_{h}^{\top}Ru_{h}~{},$
(1)

where $A$, $B$ are _unknown_ matrices, and $Q$, $R$ are known positive
definite (p.d.) matrices. The starting state $x_{1}$ is fixed (can possibly be
chosen by an adversary) and the system noise $w_{h}\\!\in\\!\mathbb{R}^{n}$ is
zero-mean. We summarize the unknown parameters in
$\Theta\\!=\\![A,B]^{\top}\\!\in\\!\mathbb{R}^{(n+d)\times n}$ .

The goal of the agent is to design a closed-loop control policy
$\pi:[H]\times\mathbb{R}^{n}\to\mathbb{R}^{d}$ mapping states to controls that
minimizes the expected cost

$\displaystyle
J_{h}^{\pi}(\Theta,x):=\mathbb{E}_{\pi}\Big{[}\sum\nolimits_{h^{\prime}=h}^{H}c_{h^{\prime}}\;\big{|}\;x_{h}=x\Big{]},$
(2)

for all $h\in[H]$ and $x\in\mathbb{R}^{n}$. Here the expectation is over the
random trajectory induced by the policy $\pi$ starting from state $x$ at time
$h$. From the standard theory for LQ control (e.g., [19]), the optimal policy
$\pi^{*}$ has the form

$\displaystyle\pi_{h}^{*}(x)=K_{h}(\Theta)x~{},\quad\forall h\in[H]~{},$

where the gain matrices $K_{h}(\Theta)$ are given by

$\displaystyle\\!\\!K_{h}(\Theta)\\!=\\!-(R\\!+\\!B^{\top}P_{h}(\Theta)B)^{-1}B^{\top}P_{h}(\Theta)A.$
(3)

Here the symmetric positive semidefinite matrices $P_{h}(\Theta)$ are defined
recursively by the _Riccati iteration_

$\displaystyle P_{h}(\Theta)=Q+A^{\top}P_{h+1}(\Theta)A$ (4)
$\displaystyle\\!-\\!A^{\top}P_{h+1}(\Theta)B(R\\!+\\!B^{\top}P_{h+1}(\Theta)B)^{-1}B^{\top}P_{h+1}(\Theta)A.$

with $P_{H+1}(\Theta):=0$. The optimal cost is given by

$\displaystyle\\!\\!\\!\\!\\!J_{h}^{*}(\Theta,x)\\!=\\!x^{\top}\\!P_{h}(\Theta)x\\!+\\!\\!\\!\sum\nolimits_{h^{\prime}\\!=h}^{H}\\!\\!\\!\mathbb{E}\left[w_{h^{\prime}}^{\top}P_{h^{\prime}+1}(\Theta)w_{h^{\prime}}\right]\\!.$
(5)

We let the agent play $K$ episodes and measure the performance by cumulative
regret.111In the following, we add subscript $k$ to denote the variables for
the $k$-th episode – state $x_{k,h}$, control $u_{k,h}$, noise $w_{k,h}$ and
cost $c_{k,h}$. In particular, if the true system dynamics are
$\Theta_{*}\\!=\\![A_{*},B_{*}]^{\top}$, the cumulative regret of the first
$K$ episodes is given by

$\displaystyle\mathcal{R}(K)\\!:=\\!\sum\nolimits_{k=1}^{K}\left(J_{1}^{\pi_{k}}(\Theta_{*},x_{k,1})-J_{1}^{*}(\Theta_{*},x_{k,1})\right),$
(6)

where $J_{1}^{*}(\Theta_{*},x_{k,1})$ is the (expected) cost under an optimal
policy for episode $k$ (computed via (5)), and
$J_{1}^{\pi_{k}}(\Theta_{*},x_{k,1})$ is the (expected) cost under the chosen
policy $\pi_{k}$ at the start of episode $k$ (computed via (2)). We seek to
attain a sublinear regret $\mathcal{R}(K)\\!=\\!o(K)$, which ensures that the
agent finds the optimal policy as $K\\!\to\\!\infty$. We end this section by
presenting our assumptions on the LQ system (1), which are common in the LQ
control literature [17].

######  Assumption 1 (Boundedness).

(a) The true system dynamics $\Theta_{*}$ is a member of a set
$\mathcal{S}\\!:=\\!\\{\Theta\\!=\\![A,B]^{\top}\\!:\\!\left\lVert\Theta\right\rVert_{\operatorname{F}}\\!\leqslant\\!1\text{
and }[A,B]\text{ is controllable}\\}$. (b) There exist constants $C$, $C_{A}$,
$C_{B}$ such that $\left\lVert A_{*}\right\rVert\\!\leqslant\\!C_{A}\\!<\\!1$,
$\left\lVert B_{*}\right\rVert\\!\leqslant\\!C_{B}\\!<\\!1$, and $\left\lVert
Q\right\rVert\\!\leqslant\\!C$, $\left\lVert R\right\rVert\\!\leqslant\\!C$,
(c) For all $k\\!\geqslant\\!1$, $\left\lVert
x_{k,1}\right\rVert\\!\leqslant\\!1$. (d) The noise $w_{k,h}$ at any
$k\\!\geqslant\\!1$ and $h\\!\in\\![H]$, is (i) independent of all other
randomness, (ii) $\mathbb{E}\left[w_{k,h}\right]\\!=\\!0$, and (iii)
$\left\lVert w_{k,h}\right\rVert_{2}\\!\leqslant\\!C_{w}\\!<\\!1$. (e) There
exists a constant $\gamma$ such that $C_{A}+\gamma
C_{B}+C_{w}\\!\leqslant\\!1$.

###  II-B Differential Privacy

We now formally define the notion of differential privacy in the context of
episodic LQ control. We write
$v\\!=\\!(v_{1},\ldots,v_{K})\\!\in\\!\mathcal{V}^{K}$ to denote a sequence of
$K$ unique users participating in the private RL protocol with an RL agent
$\mathcal{M}$, where $\mathcal{V}$ is the set of all users. Each user $v_{k}$
is identified by the state responses $\\{x_{k,h+1}\\}_{h\in[H]}$ she gives to
the controls $\\{u_{k,h}\\}_{h\in[H]}$ chosen by the agent. We write
$\mathcal{M}(v)\\!=\\!\\{u_{k,h}\\}_{k\in[K],h\in[H]}\in(\mathbb{R}^{d})^{KH}$
to denote the privatized controls chosen by the agent $\mathcal{M}$ when
interacting with the users $v$. Informally, we will be interested in
randomized algorithms $\mathcal{M}$ so that the knowledge of the output
$\mathcal{M}(v)$ and all but the $k$-th user $v_{k}$ does not reveal ‘much’
about $v_{k}$. We formalize in the following definition, which is adapted from
[20].

######  Definition 1 (Differential Privacy (DP)).

For any $\varepsilon\\!\geqslant\\!0$ and $\delta\\!\in\\![0,1]$, an algorithm
$\mathcal{M}\\!:\\!\mathcal{V}^{K}\\!\rightarrow\\!(\mathbb{R}^{d})^{KH}$ is
$(\varepsilon,\delta)$-differentially private if for all
$v,v^{\prime}\in\mathcal{V}^{K}$ differing on a single user and all subset of
controls $\mathcal{U}\\!\\!\subset\\!\\!\left(\mathbb{R}^{d}\right)^{KH}$,

$\mathbb{P}\left[{\mathcal{M}(v)\in\mathcal{U}}\right]\leqslant\exp(\varepsilon)\mathbb{P}\left[{\mathcal{M}(v^{\prime})\in\mathcal{U}}\right]+\delta~{}.$

We now relax this definition motivated by the fact that the controls
recommended to a given user $v_{k}$ is only observed by her. We consider
_joint differential privacy_ [21], which requires that simultaneously for all
$k$, the joint distribution on controls sent to users other than $v_{k}$ will
not change substantially upon changing the state responses of the user
$v_{k}$. To this end, we let
$\mathcal{M}_{-k}(v)\\!:=\\!\mathcal{M}(v)\\!\setminus\\!\\{u_{k,h}\\}_{h\in[H]}$
to denote all the controls chosen by the agent $\mathcal{M}$ excluding those
recommended to $v_{k}$.

######  Definition 2 (Joint Differential Privacy (JDP)).

For any $\varepsilon\\!\geqslant\\!0$ and $\delta\\!\in\\![0,1]$, an algorithm
$\mathcal{M}\\!:\\!\mathcal{V}^{K}\\!\rightarrow\\!(\mathbb{R}^{d})^{KH}$ is
$(\varepsilon,\delta)$-jointly differentially private if for all
$k\\!\in\\![K]$, all $v,v^{\prime}\\!\in\\!\mathcal{V}$ differing on the
$k$-th user and all subset of controls
$\mathcal{U}_{-k}\\!\subset\\!\left(\mathbb{R}^{d}\right)^{(K\\!-\\!1)H}\\!\\!$
given to all but the $k$-th user,

$\mathbb{P}\left[{\mathcal{M}_{-k}(v)\in\mathcal{U}_{-k}}\right]\leqslant\exp(\varepsilon)\mathbb{P}\left[{\mathcal{M}_{-k}(v^{\prime})\in\mathcal{U}_{-k}}\right]+\delta~{}.$

This relaxation is necessary in our setting since knowledge of the controls
recommended to the user $v_{k}$ can reveal a lot of information about her
state responses. It weakens the constraint of DP only in that the controls
given specifically to $v_{k}$ may be sensitive in her state responses.
However, it is still a very strong definition since it protects $v_{k}$ from
any arbitrary collusion of other users against her, so long as she does not
herself make the controls reported to her public.

In this work, we look for algorithms that are $(\varepsilon,\delta)$-JDP. But,
we will build our algorithm upon standard DP mechanisms. Furthermore, to
establish privacy, we will use a different relaxation called _concentrated
differential privacy_ (CDP) [22]. Roughly, a mechanism is CDP if the privacy
loss has Gaussian tails. To this end, we let $\mathcal{M}$ to be a mechanism
taking as input a data-stream $x\\!\in\\!\mathcal{X}^{n}$ and releasing output
from some range $\mathcal{Y}$.

######  Definition 3 (Concentrated Differential Privacy (CDP)).

For any $\rho\geqslant 0$, an algorithm
$\mathcal{M}\\!:\\!\mathcal{X}^{n}\\!\to\\!\mathcal{Y}$ is $\rho$-zero-
concentrated differentially private if for all
$x,x^{\prime}\in\mathcal{X}^{n}$ differing on a single entry and all
$\alpha\in(1,\infty)$,

$\operatorname{D}_{\alpha}\left(\mathcal{M}(x)||\mathcal{M}(x^{\prime})\right)\leqslant\rho\;\alpha~{},$

where
$\operatorname{D}_{\alpha}\left(\mathcal{M}(x)||\mathcal{M}(x^{\prime})\right)$
is the $\alpha$-Renyi divergence between the distributions of $\mathcal{M}(x)$
and $\mathcal{M}(x^{\prime})$.222For two probability distributions $P$ and $Q$
on $\Omega$, the $\alpha$-Renyi divergence
$\operatorname{D}_{\alpha}(P||Q):=\frac{1}{\alpha-1}\ln\left(\int_{\Omega}P(x)^{\alpha}Q(x)^{1-\alpha}\operatorname{d}\\!x\right)$.

##  III OFU-Based Control

Our proposed private RL algorithm implements the optimism in the face of
uncertainty (OFU) principle in LQ systems. As in [14], the key to implementing
the OFU-based control is a high-probability confidence set for the unknown
parameter matrix $\Theta_{*}$.

###  III-A Adaptive Control with Changing Regularizers

We start with the adaptive LQ control with _changing regularizers_. This not
only allows us to generalize previous results for non-private control, but
more importantly serves as a basis for the analysis of private control in the
next section. We first define the following compact notations. For a state and
control pair at step $h$ in episode $k$, i.e., $x_{k,h}$ and $u_{k,h}$, we
write $z_{k,h}\\!=\\![x_{k,h}^{\top},u_{k,h}^{\top}]^{\top}$. For any
$k\\!\geqslant\\!1$, we define the following matrices:
$Z_{k}\\!:=\\![z_{k^{\prime},h^{\prime}}^{\top}]_{k^{\prime}\in[k-1],h^{\prime}\in[H]}$,
$X_{k}^{\text{next}}\\!:=\\![x_{k^{\prime},h^{\prime}+1}^{\top}]_{k^{\prime}\in[k-1],h^{\prime}\in[H]}$
and
$W_{k}\\!:=\\![w_{k^{\prime},h^{\prime}}^{\top}]_{k^{\prime}\in[k-1],h^{\prime}\in[H]}$.
For two matrices $A$ and $B$, we also define $\left\lVert
A\right\rVert_{B}^{2}\\!:=\\!\text{trace}(A^{\top}BA)$. Now, at every episode
$k$, we consider the following ridge regression estimate w.r.t. a regularizing
p.d. matrix $H_{k}\in\mathbb{R}^{(n+d)\times(n+d)}$:

$\displaystyle{\Theta}_{k}$
$\displaystyle:=\operatorname*{arg\,min}_{\Theta\in\mathbb{R}^{(n+d)\times
n}}\left\lVert
X_{k}^{\text{next}}-Z_{k}\Theta\right\rVert_{\operatorname{F}}^{2}+\left\lVert\Theta\right\rVert_{H_{k}}^{2}$
$\displaystyle=(Z_{k}^{\top}Z_{k}+H_{k})^{-1}Z_{k}^{\top}X_{k}^{\text{next}},$

In contrast to the standard online LQ control [14], here the sequence of
matrices $\\{Z_{k}^{\top}Z_{k}\\}_{k\geqslant 1}$ is perturbed by a sequence
of regularizers $\\{H_{k}\\}_{k\geqslant 1}$. In particular, when
$H_{k}\\!=\\!\lambda I$, we get back the standard estimate of [14]. In
addition, we also allow $Z_{k}^{\top}X_{k}^{\text{next}}$ to be perturbed by a
matrix $L_{k}$ at every episode $k$. Setting
$V_{k}\\!:=\\!Z_{k}^{\top}Z_{k}\\!+\\!H_{k}$ and
$U_{k}\\!:=\\!Z_{k}^{\top}X_{k}^{\text{next}}\\!+\\!L_{k}$, we now define the
estimate under changing regularizers $\\{H_{k}\\}_{k\geq 1}$ and
$\\{L_{k}\\}_{k\geq 1}$ as

$\displaystyle{\widehat{\Theta}}_{k}={V}_{k}^{-1}{U}_{k}~{}.$ (7)

We make the following assumptions on the sequence of regularizers
$\\{H_{k}\\}_{k\geq 1}$ and $\\{L_{k}\\}_{k\geq 1}$.

######  Assumption 2 (Regularity).

For any $\alpha\in(0,1]$, there exist constants $\lambda_{\max}$,
$\lambda_{\min}$ and $\nu$ depending on $\alpha$ such that, with probability
at least $1-\alpha$, for all $k\in[K]$,

$\displaystyle\left\lVert
H_{k}\right\rVert\leqslant\lambda_{\max},\;\;\left\lVert
H_{k}^{-1}\right\rVert\leqslant 1/\lambda_{\min}\;\;\text{and}\;\;\left\lVert
L_{k}\right\rVert_{H_{k}^{-1}}\leqslant\nu.$

######  Lemma 1 (Concentration under changing regularizers).

Under assumptions 1 and 2, the following holds:

$\forall\alpha\\!\in\\!(0,1],\quad\mathbb{P}\left[{\exists
k\\!\in\\!\mathbb{N}\\!:\;\left\lVert\Theta_{*}\\!-\\!\widehat{\Theta}_{k}\right\rVert_{{V}_{k}}\\!\geqslant\\!\beta_{k}(\alpha)}\right]\\!\leqslant\\!\alpha~{},$

where
${\beta_{k}(\alpha)}\\!:=\\!C_{w}\\!\sqrt{2\ln\\!\big{(}\frac{2}{\alpha}\big{)}\\!\\!+\\!n\ln\det\left(I\\!+\\!\lambda_{\min}^{-1}Z_{k}^{\top}Z_{k}\right)}\\!+\\!\sqrt{\lambda_{\max}}\\!+\\!\nu$.

Lemma 1 helps us to introduce the following high probability confidence set

$\displaystyle\mathcal{C}_{k}(\alpha):=\left\\{\Theta:\left\lVert\Theta-\widehat{\Theta}_{k}\right\rVert_{V_{k}}\leqslant\beta_{k}(\alpha)\right\\}.$
(8)

We then search for an optimistic estimate $\widetilde{\Theta}_{k}$ within this
confidence region $\mathcal{C}_{k}(\alpha)$, such that

$\displaystyle\widetilde{\Theta}_{k}\in\operatorname*{arg\,min}_{\Theta\in\mathcal{C}_{k}(\alpha)\cap\mathcal{S}}J_{1}^{*}(\Theta,x_{k,1}),$
(9)

where $J_{1}^{*}(\Theta,x_{k,1})$ is the optimal cost when system dynamics are
$\Theta$ (can be computed from (5)). With the estimate
$\widetilde{\Theta}_{k}$, the agent then chooses policy $\pi_{k}$ and selects
the controls recommended by this policy

$u_{k,h}:=\pi_{k,h}(x_{k,h})=K_{h}(\widetilde{\Theta}_{k})x_{k,h}~{},$ (10)

where $K_{h}(\widetilde{\Theta}_{k})$ can be computed from (3). We call this
procedure $\mathrm{OFU}\text{-}\mathrm{RL}$ and bound its regret as follows.

######  Theorem 1 (Regret under changing regularizers).

Under Assumptions 1 and 2, for any $\alpha\\!\in\\!(0,1]$, with probability at
least $1-\alpha$, the cumulative regret of $\mathrm{OFU}\text{-}\mathrm{RL}$
satisfies

$\displaystyle\mathcal{R}(K)$
$\displaystyle=O\left(H\sqrt{K}\big{(}\sqrt{H}+n(n+d)\psi_{\lambda_{\min}}+\ln(1/\alpha)\big{)}\right)$
$\displaystyle+$ $\displaystyle
O\left(H\sqrt{K}\left(\sqrt{\lambda_{\max}}+\nu\right)\sqrt{n(n+d)\psi_{\lambda_{\min}}}\right)~{},$

where
$\psi_{\lambda_{\min}}\\!:=\\!\ln\left(1\\!+\\!HK/(n+d)\lambda_{\min}\right)$.

Proof sketch. Inspired by [17], we first decompose the regret under the
following ‘good’ event:
$\mathcal{E}_{K}(\alpha)\\!:=\\!\\{\Theta_{*}\\!\in\\!\mathcal{C}_{k}(\alpha)\\!\cap\\!\mathcal{S},\forall
k\\!\in\\![K]\\},$ which, by Assumption 1 and Lemma 1, holds w.p. at least
$1\\!-\\!\alpha$. Then, under the ‘good’ event, the cumulative regret (6) can
be written as

$\displaystyle\mathcal{R}(K)\leqslant\sum\nolimits_{k=1}^{K}\sum\nolimits_{h=1}^{H}(\Delta_{k,h}+\Delta_{k,h}^{\prime}+\Delta_{k,h}^{\prime\prime}),\;\;\text{where}$
$\displaystyle\Delta_{k,h}\\!:=\\!\mathbb{E}\left[J_{h+1}^{\pi_{k}}(\Theta_{*},x_{k,h+1})\\!\\!\mid\\!\mathcal{F}_{k,h}\right]\\!-\\!J_{h+1}^{\pi_{k}}(\Theta_{*},x_{k,h+1}),$
$\displaystyle\Delta_{k,h}^{\prime}\\!:=\\!\left\lVert
x_{k,h+1}\right\rVert_{\widetilde{P}_{k,h+1}}\\!\\!\\!-\\!\mathbb{E}\left[\left\lVert
x_{k,h+1}\right\rVert_{\widetilde{P}_{k,h+1}}\\!\\!\mid\\!\mathcal{F}_{k,h}\right]\;\text{and}$
$\displaystyle\Delta_{k,h}^{\prime\prime}\\!:=\\!\left\lVert\Theta_{*}^{\top}z_{k,h}\right\rVert_{\widetilde{P}_{k,h+1}}\\!-\\!\left\lVert\widetilde{\Theta}_{k}^{\top}z_{k,h}\right\rVert_{\widetilde{P}_{k,h+1}},$

in which $\widetilde{P}_{k,h}\\!:=\\!P_{h}(\widetilde{\Theta}_{k})$ is given
by (4) and $\mathcal{F}_{k,h}$ denotes all the randomness present before time
$(k,h)$.

Now, we are going to bound each term, respectively. For the first two terms,
we can show that both of them are bounded martingale difference sequences.
Therefore, by Azuma–Hoeffding inequality, we have
$\sum_{k,h}\Delta_{k,h}\\!=\\!O\big{(}\sqrt{KH^{3}}\big{)}$ and
$\sum_{k,h}\Delta^{\prime}_{k,h}\\!=\\!O\big{(}\sqrt{KH}\big{)}$ with high
probability. We use Lemma 1 and the OFU principle (9) to bound the third term
as
$\sum_{k,h}\Delta^{\prime\prime}_{k,h}\\!=\\!O\big{(}H\sqrt{K}\beta_{k}(\alpha)\sqrt{\ln\det\left(I\\!+\\!\lambda_{\min}^{-1}Z_{k}^{\top}Z_{k}\right)}\big{)}$.
To put everything together, first note from Assumption 1 that

$\displaystyle\ln\det\left(I\\!+\\!\lambda_{\min}^{-1}Z_{k}^{\top}Z_{k}\right)\\!\leqslant\\!(n\\!+\\!d)\ln\left(1\\!+\\!\frac{HK(1+\gamma)^{2}}{(n+d)\lambda_{\min}}\right).$

Plugging this into $\beta_{k}(\alpha)$ given in Lemma 1 and the third term
above, yields the final result. ∎

We end the section with a proof sketch of Lemma 1.

Proof sketch (Lemma 1). Under Assumptions 1 and 2, with some basic algebra, we
first have

$\displaystyle\left\lVert{\Theta}_{*}-\widehat{\Theta}_{k}\right\rVert_{{V}_{k}}=\left\lVert
H_{k}\Theta_{*}-Z_{k}^{\top}W_{k}-L_{k}\right\rVert_{{V}_{k}^{-1}}$
$\displaystyle\leqslant$ $\displaystyle\underbrace{\left\lVert
Z_{k}^{\top}W_{k}\right\rVert_{(Z_{k}^{\top}Z_{k}+\lambda_{\min}I)^{-1}}}_{\mathcal{T}_{1}}+\underbrace{\left\lVert
H_{k}^{\frac{1}{2}}\right\rVert_{2}+\left\lVert
L_{k}\right\rVert_{H_{k}^{-1}}}_{\mathcal{T}_{2}}.$

By Assumption 2, we have w.p. at least $1-\alpha$,
$\mathcal{T}_{2}\leqslant\sqrt{\lambda_{\max}}+\nu$. To bound
$\mathcal{T}_{1}$, by the boundedness of $w_{k,h}$ in Assumption 1, we first
note that each row of the matrix $W_{k}$ is a sub-Gaussian random vector with
parameter $C_{w}$. We then generalize the self-normalized concentration
inequality of vector-valued martingales [23, Theorem 1] to the setting of
matrix-valued martingales. In particular, we show that w.p. at least
$1-\alpha$,

$\displaystyle\mathcal{T}_{1}\leqslant
C_{w}\sqrt{2\ln\left(1/\alpha\right)+n\ln\det(I\\!+\\!\lambda_{\min}^{-1}Z_{k}^{\top}Z_{k})}.$

Combining the bounds on $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ using a union
bound argument, yields the final result. ∎

###  III-B Private Control

In this section, we introduce the
$\mathrm{Private}\text{-}\mathrm{OFU}\text{-}\mathrm{RL}$ algorithm (Alg. 1).
At every episode $k$, we keep track of the history via private version of the
matrices $Z_{k}^{\top}Z_{k}$ and $Z_{k}^{\top}X_{k}^{\text{next}}$. To do so,
we first initialize two private counter mechanisms $\mathcal{B}_{1}$ and
$\mathcal{B}_{2}$, which take as parameters the privacy levels $\varepsilon$,
$\delta$, number of episodes $K$, horizon $H$ and a problem-specific constant
$\gamma$ (see Assumption 1). The counter $\mathcal{B}_{1}$ (resp.
$\mathcal{B}_{2}$) take as input an event stream of matrices
$\\{\sum_{h=1}^{H}z_{k,h}z_{k,h}^{\top}\\}_{k\in[K]}$ (resp.
$\\{\sum_{h=1}^{H}z_{k,h}x_{k,h+1}^{\top}\\}_{k\in[K]}$), and at the start of
each episode $k$, release the private version of the matrix
$Z_{k}^{\top}Z_{k}$ (resp. $Z_{k}^{\top}X_{k}^{\text{next}}$), which itself is
a matrix of the same dimension. Let $T_{1,k}$ and $T_{2,k}$ denote the
privatized versions for $Z_{k}^{\top}Z_{k}$ and
$Z_{k}^{\top}X_{k}^{\text{next}}$, respectively. For some $\eta>0$ (will be
determined later), we define $V_{k}\\!:=\\!T_{1,k}\\!+\\!\eta I$ and
$U_{k}\\!:=\\!T_{2,k}$. We now instantiate the general
$\mathrm{OFU}\text{-}\mathrm{RL}$ procedure under changing regularizers
(Section III-A) with these private statistics. First, we compute the point
estimate $\widehat{\Theta}_{k}$ from (7) and build the confidence set
$\mathcal{C}_{k}(\alpha)$ from (8). Then, we choose the most optimisitic
policy $\pi_{k}$ w.r.t. the entire set $\mathcal{C}_{k}(\alpha)$ from (9) and
(10). Finally, we execute the policy for the entire episode and update the
counters with observed trajectory.

We now describe the private counters $\mathcal{B}_{1}$ adapting the _Binary
counting mechanism_ of [24]. First, we write
$\Sigma_{1}[i,j]=\sum_{k=i}^{j}\sum_{h=1}^{H}z_{k,h}z_{k,h}^{\top}$ to denote
a partial sum ($\mathrm{P}\text{-}\mathrm{sum}$) involving the state-control
pairs in episodes $i$ through $j$. Next, we consider a binary interval tree,
where each leaf node represents an episode (i.e., the tree has $k-1$ leaf
nodes at the start of episode $k$), and each interior node represents the
range of episodes covered by its children. At the start of episode $k$, we
first release a noisy $\mathrm{P}\text{-}\mathrm{sum}$
$\widehat{\Sigma}_{1}[i,j]$ corresponding to each node in the tree. Here
$\widehat{\Sigma}_{1}[i,j]$ is obtained by perturbing both $(p,q)$-th and
$(q,p)$-th, $1\\!\leqslant\\!p\\!\leqslant\\!q\\!\leqslant\\!(n\\!+\\!d)$,
entries of $\Sigma_{1}[i,j]$ with i.i.d. Gaussian noise
$\zeta_{p,q}\\!\sim\\!\mathcal{N}(0,\sigma_{1}^{2})$.333This will ensure
symmetry of the $\mathrm{P}\text{-}\mathrm{sums}$ even after adding noise.
Then $T_{1,k}$ is computed by summing up the noisy
$\mathrm{P}\text{-}\mathrm{sums}$ released by the set of nodes that uniquely
cover the range $[1,k\\!-\\!1]$. Observe that, at the end each episode, the
mechanism only needs to store noisy $\mathrm{P}\text{-}\mathrm{sums}$ required
for computing private statistics at future episodes, and can safely discard
$\mathrm{P}\text{-}\mathrm{sums}$ that are no longer needed. For the private
counter $\mathcal{B}_{2}$, we maintain $\mathrm{P}\text{-}\mathrm{sums}$
$\Sigma_{2}[i,j]\\!=\\!\sum_{k=i}^{j}\sum_{h=1}^{H}z_{k,h}x_{k,h+1}^{\top}$
with i.i.d. noise $\mathcal{N}(0,\sigma_{2}^{2})$ and compute the private
statistics $T_{2,k}$ using a similar procedure. The noise levels $\sigma_{1}$
and $\sigma_{2}$ depends on the problem intrinsics ($K$, $H$, $\gamma$) and
privacy parameters ($\varepsilon$, $\delta$). These, in turn, govern the
constants $\lambda_{\max}$, $\lambda_{\min}$, $\nu$ appearing in the
confidence set $\mathcal{C}_{k}(\alpha)$ and the regularizer $\eta$. The
details will be specified in the next Section as needed.

Input: Number of episodes $K$, horizon $H$, privacy level
$\varepsilon\\!>\\!0$, $\delta\\!\in\\!(0,1]$, constants $\gamma$, $C_{w}$,
confidence level $\alpha\in(0,1]$

1 initialize private counters $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$ with
parameters $K,H,\varepsilon,\delta,\gamma$

2 for  _each episode $k\\!=\\!1,2,3,\ldots,K$_ do

3 compute private statistics $T_{1,k}$ and $T_{2,k}$

4 construct confidence set $\mathcal{C}_{k}(\alpha)$

5 find
$\widetilde{\Theta}_{k}\in\operatorname*{arg\,min}_{\Theta\in\mathcal{C}_{k}(\alpha)\cap\mathcal{S}}J_{1}^{*}(\Theta,x_{k,1})$

6 for  _each step $h\\!=\\!1,2,\ldots,H$_ do

7 execute control $u_{k,h}\\!=\\!K_{h}(\widetilde{\Theta}_{k})x_{k,h}$

8 observe cost $c_{k,h}$ and next state $x_{k,h+1}$

9

10 send $\sum_{h=1}^{H}z_{k,h}z_{k,h}^{\top}$ and
$\sum_{h=1}^{H}z_{k,h}x_{k,h+1}^{\top}$ to the counters $\mathcal{B}_{1}$ and
$\mathcal{B}_{2}$, respectively

Algorithm 1 $\mathrm{Private}\text{-}\mathrm{OFU}\text{-}\mathrm{RL}$

##  IV Privacy and Regret Guarantees

In this section, we show that
$\mathrm{Private}\text{-}\mathrm{OFU}\text{-}\mathrm{RL}$ is a JDP algorithm
with sublinear regret guarantee.

###  IV-A Privacy Guarantee

######  Theorem 2 (Privacy).

Under Assumption 1, for any $\varepsilon\\!>\\!0$ and $\delta\\!\in\\!(0,1]$,
$\mathrm{Private}\text{-}\mathrm{OFU}\text{-}\mathrm{RL}$ is
$(\varepsilon,\delta)$-JDP.

Proof sketch. We first show that both the counters $\mathcal{B}_{1}$ and
$\mathcal{B}_{2}$ are $(\varepsilon/2,\delta/2)$-DP. We begin with the counter
$\mathcal{B}_{1}$. To this end, we need to determine a global upper bound
$\Delta_{1}$ over the $\operatorname{L}_{2}$-sensitivity of all the
$\mathrm{P}\text{-}\mathrm{sums}$ $\Sigma_{1}[i,j]$. Informally, $\Delta_{1}$
encodes the maximum change in the Frobenious norm of each
$\mathrm{P}\text{-}\mathrm{sum}$ if the trajectory of a single episode is
changed. By Assumption 1, we have $\left\lVert
z_{k,h}\right\rVert\\!\leqslant\\!1\\!+\\!\gamma$, and hence
$\Delta_{1}\\!=\\!H(1\\!+\\!\gamma)^{2}$. Since the noisy
$\mathrm{P}\text{-}\mathrm{sums}$ $\widehat{\Sigma}_{1}[i,j]$ are obtained via
Gaussian mechanism, we have that each $\widehat{\Sigma}_{1}[i,j]$ is
$(\Delta_{1}^{2}/2\sigma_{1}^{2})$-CDP [22, Proposition 1.6]. We now see that
every episode appears only in at most $m\\!:=\\!\lceil\log_{2}K\rceil$
$\mathrm{P}\text{-}\mathrm{sums}$ $\Sigma_{1}[i,j]$. Therefore, by the
composition property, the whole counter $\mathcal{B}_{1}$ is
$(m\Delta_{1}^{2}/2\sigma_{1}^{2})$-CDP, and thus, in turn,
$\left(\frac{m\Delta_{1}^{2}}{2\sigma_{1}^{2}}\\!+\\!2\sqrt{\frac{m\Delta_{1}^{2}}{2\sigma_{1}^{2}}\ln\left(\frac{2}{\delta}\right)},\frac{\delta}{2}\right)$-DP
for any $\delta\\!>\\!0$ [22, Lemma 3.5]. Now, setting
$\sigma_{1}^{2}\\!\approx\\!8m\Delta_{1}^{2}\ln(2/\delta)/\varepsilon^{2}$, we
can ensure that $\mathcal{B}_{1}$ is $(\varepsilon/2,\delta/2)$-DP. A similar
analysis yields that counter $\mathcal{B}_{2}$ is
$(\varepsilon/2,\delta/2)$-DP if we set
$\sigma_{2}^{2}\\!\approx\\!8m\Delta_{2}^{2}\ln(2/\delta)/\varepsilon^{2}$,
where $\Delta_{2}\\!:=\\!H(1\\!+\\!\gamma)$.

To prove Theorem 2, we now use the _billboard lemma_ [25, Lemma 9] which,
informally, states that an algorithm is JDP under continual observation if the
output sent to each user is a function of the user’s private data and a common
quantity computed using standard differential privacy. Note that at each
episode $k$, $\mathrm{Private}\text{-}\mathrm{OFU}\text{-}\mathrm{RL}$
computes private statistics $T_{1,k}$ and $T_{2,k}$ for all users using the
counters $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$. These statistics are then
used to compute the policy $\pi_{k}$. By composition and post-processing
properties of DP, we can argue that the sequence of policies
$\\{\pi_{k}\\}_{k\in[K]}$ are computed using an $(\varepsilon,\delta)$-DP
mechanism. Now, the controls $\\{u_{k,h}\\}_{h\in[H]}$ during episode $k$ are
generated using the policy $\pi_{k}$ and the user’s private data $x_{k,h}$ as
$u_{k,h}\\!=\\!\pi_{k,h}(x_{k,h})$. Then, by the billboard lemma, the
composition of the controls $\\{u_{k,h}\\}_{k\in[K],h\in[H]}$ sent to all the
users is $(\varepsilon,\delta)$-JDP.∎

###  IV-B Regret Guarantee

######  Theorem 3 (Private regret).

Under Assumption 1, for any privacy parameters $\varepsilon\\!>\\!0$ and
$\delta\\!\in\\!(0,1]$, and for any $\alpha\\!\in\\!(0,1]$, with probability
at least $1\\!-\\!\alpha$,
$\mathrm{Private}\text{-}\mathrm{OFU}\text{-}\mathrm{RL}$ enjoys the regret
bound

$\displaystyle\mathcal{R}(K)=O\\!\left(H^{3/2}\sqrt{K}\big{(}n(n\\!+\\!d)\ln
K\\!+\\!\ln(1/\alpha)\big{)}\right)$
$\displaystyle\\!+\\!O\\!\left(\\!H^{3/2}\\!\sqrt{K}\ln
K\\!\left(n(n\\!+\\!d)\\!+\\!\\!\sqrt{\ln
K/\alpha}\right)\frac{\ln(1/\delta)^{1/4}}{\varepsilon^{1/2}}\right)\\!.$

Theorems 2 and 3 together imply that
$\mathrm{Private}\text{-}\mathrm{OFU}\text{-}\mathrm{RL}$ can achieve a sub-
linear regret under $(\varepsilon,\delta)$-JDP privacy guarantee. Furthermore,
comparing Theorem 3 with Theorem 1, we see that the first term in the regret
bound corresponds to the non-private regret, and the second term is the cost
of privacy. More importantly, the cost due to privacy grows only as
$\frac{\ln(1/\delta)^{1/4}}{\varepsilon^{1/2}}$ with $\varepsilon,\delta$.

Proof sketch (Theorem 3). First note that the private statistics $T_{1,k}$ can
be computed by summing at most $m\\!=\\!\lceil\log_{2}K\rceil$ noisy
$\mathrm{P}\text{-}\mathrm{sums}$ $\widehat{\Sigma}_{1}[i,j]$. We then have
that the total noise $N_{k}$ in each $T_{1,k}$ is a symmetric matrix with it’s
$(p,q)$-th entry,
$1\\!\leqslant\\!p\\!\leqslant\\!q\\!\leqslant\\!(n\\!+\\!d)$, being i.i.d.
$\mathcal{N}(0,m\sigma_{1}^{2})$. Therefore, by an adaptation of [26,
Corollary 4.4.8], we have w.p. at least $1\\!-\\!\alpha/2K$,

$\displaystyle\left\lVert
N_{k}\right\rVert\\!\leqslant\\!\Lambda\\!:=\\!\sigma_{1}\sqrt{m}\left(4\sqrt{n\\!+\\!d}\\!+\\!\sqrt{8\ln(4K/\alpha)}\right).$

Similarly, the total noise $L_{k}$ in each $T_{2,k}$ is an $(n+d)\times n$
matrix, whose each entry is i.i.d. $\mathcal{N}(0,m\sigma_{2}^{2})$. Hence
$\left\lVert L_{k}\right\rVert_{\operatorname{F}}^{2}/m\sigma_{2}^{2}$ is a
$\chi^{2}$-statistic with $n(n\\!+\\!d)$ degrees of freedom, and therefore, by
[27, Lemma 1], we have w.p. at least $1\\!-\\!\alpha/2K$,

$\displaystyle\\!\left\lVert
L_{k}\right\rVert_{\operatorname{F}}\\!\leqslant\\!\sigma_{2}\sqrt{m}\left(\\!\sqrt{2n(n\\!+\\!d)}\\!+\\!\sqrt{4\ln(2K/\alpha)}\right).$

By construction, we have the regularizer $H_{k}\\!=\\!N_{k}\\!+\\!\eta I$.
Setting $\eta\\!=\\!2\Lambda$, we ensure that $H_{k}$ is p.d., and hence
$\left\lVert
L_{k}\right\rVert_{H_{k}^{-1}}\\!\leqslant\\!\Lambda^{-1/2}\left\lVert
L_{k}\right\rVert_{\operatorname{F}}$. Then, by a union bound argument,
Assumption 2 holds for $\lambda_{\min}\\!=\\!\Lambda$,
$\lambda_{\max}\\!=\\!3\Lambda$ and
$\nu\\!=\\!\sigma_{2}\sqrt{m/\Lambda}\left(\sqrt{2n(n\\!+\\!d)}\\!+\\!\\!\sqrt{4\ln(2K/\alpha)}\right)$.
Appropriating noise levels $\sigma_{1},\sigma_{2}$ from Section IV-A, the
regret bound now follows from Theorem 1.∎

##  V Conclusion

We develop the first DP algorithm,
$\mathrm{Private}\text{-}\mathrm{OFU}\text{-}\mathrm{RL}$, for episodic LQ
control. Through the notion of JDP, we show that it can protect private user
information from being inferred by observing the control policy without losing
much on its regret performance. We leave as future work private control of
non-linear systems [16].

## References

  * [1] L. Li, W. Chu, J. Langford, and R. E. Schapire, “A contextual-bandit approach to personalized news article recommendation,” in _Proceedings of the 19th international conference on World wide web_ , 2010, pp. 661–670.
  * [2] Y. Zhao, M. R. Kosorok, and D. Zeng, “Reinforcement learning design for cancer clinical trials,” _Statistics in medicine_ , vol. 28, no. 26, pp. 3294–3315, 2009.
  * [3] A. R. Sharma and P. Kaushik, “Literature survey of statistical, deep and reinforcement learning in natural language processing,” in _2017 International Conference on Computing, Communication and Automation (ICCCA)_. IEEE, 2017, pp. 350–354.
  * [4] G. Gordon, S. Spaulding, J. K. Westlund, J. J. Lee, L. Plummer, M. Martinez, M. Das, and C. Breazeal, “Affective personalization of a social robot tutor for children’s second language skills,” in _Proceedings of the AAAI conference on artificial intelligence_ , vol. 30, no. 1, 2016.
  * [5] C. Dwork, “Differential privacy: A survey of results,” in _International conference on theory and applications of models of computation_. Springer, 2008, pp. 1–19.
  * [6] A. Tossou and C. Dimitrakakis, “Algorithms for differentially private multi-armed bandits,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 30, no. 1, 2016.
  * [7] ——, “Achieving privacy in the adversarial multi-armed bandit,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 31, no. 1, 2017.
  * [8] D. Basu, C. Dimitrakakis, and A. Tossou, “Differential privacy for multi-armed bandits: What is it and what is its cost?” _arXiv preprint arXiv:1905.12298_ , 2019.
  * [9] N. Mishra and A. Thakurta, “(nearly) optimal differentially private stochastic multi-arm bandits,” in _Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence_ , 2015, pp. 592–601.
  * [10] X. Zhou and J. Tan, “Local differential privacy for bayesian optimization,” _arXiv preprint arXiv:2010.06709_ , 2020.
  * [11] B. Balle, M. Gomrokchi, and D. Precup, “Differentially private policy evaluation,” in _International Conference on Machine Learning_. PMLR, 2016, pp. 2130–2138.
  * [12] G. Vietri, B. Balle, A. Krishnamurthy, and S. Wu, “Private reinforcement learning with pac and regret guarantees,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 9754–9764.
  * [13] E. Garcelon, V. Perchet, C. Pike-Burke, and M. Pirotta, “Local differentially private regret minimization in reinforcement learning,” _arXiv preprint arXiv:2010.07778_ , 2020.
  * [14] Y. Abbasi-Yadkori and C. Szepesvári, “Regret bounds for the adaptive control of linear quadratic systems,” in _Proceedings of the 24th Annual Conference on Learning Theory_ , 2011, pp. 1–26.
  * [15] I. Osband and B. V. Roy, “Model-based reinforcement learning and the eluder dimension,” in _Proceedings of the 27th International Conference on Neural Information Processing Systems-Volume 1_ , 2014, pp. 1466–1474.
  * [16] S. R. Chowdhury and A. Gopalan, “Online learning in kernelized markov decision processes,” in _The 22nd International Conference on Artificial Intelligence and Statistics_. PMLR, 2019, pp. 3197–3205.
  * [17] T. Wang and L. F. Yang, “Episodic linear quadratic regulators with low-rank transitions,” _arXiv preprint arXiv:2011.01568_ , 2020.
  * [18] C. Jin, Z. Yang, Z. Wang, and M. I. Jordan, “Provably efficient reinforcement learning with linear function approximation,” in _Conference on Learning Theory_ , 2020, pp. 2137–2143.
  * [19] D. Bertsekas, _Dynamic programming and optimal control_. Athena scientific Belmont, MA, 3 edition, 2004.
  * [20] C. Dwork, A. Roth _et al._ , “The algorithmic foundations of differential privacy.” 2014.
  * [21] M. Kearns, M. Pai, A. Roth, and J. Ullman, “Mechanism design in large games: Incentives and privacy,” in _Proceedings of the 5th conference on Innovations in theoretical computer science_ , 2014, pp. 403–410.
  * [22] M. Bun and T. Steinke, “Concentrated differential privacy: Simplifications, extensions, and lower bounds,” in _Theory of Cryptography Conference_. Springer, 2016, pp. 635–658.
  * [23] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári, “Improved algorithms for linear stochastic bandits,” in _Advances in Neural Information Processing Systems_ , 2011, pp. 2312–2320.
  * [24] T.-H. H. Chan, E. Shi, and D. Song, “Private and continual release of statistics,” _ACM Transactions on Information and System Security (TISSEC)_ , vol. 14, no. 3, pp. 1–24, 2011.
  * [25] J. Hsu, Z. Huang, A. Roth, T. Roughgarden, and Z. S. Wu, “Private matchings and allocations,” _SIAM Journal on Computing_ , vol. 45, no. 6, pp. 1953–1984, 2016.
  * [26] R. Vershynin, _High-dimensional probability: An introduction with applications in data science_. Cambridge university press, 2018, vol. 47.
  * [27] B. Laurent and P. Massart, “Adaptive estimation of a quadratic functional by model selection,” _Annals of Statistics_ , pp. 1302–1338, 2000.