# Differentially Private Exploration in
Reinforcement Learning with Linear Representation

Paul Luyo111Work done while at Facebook AI Research. Ecole Polytechnique
Evrard Garcelon  Facebook AI Research  CREST, ENSAE  Alessandro Lazaric
Facebook AI Research  Matteo Pirotta  Facebook AI Research

###### Abstract

This paper studies privacy-preserving exploration in Markov Decision Processes
(MDPs) with linear representation. We first consider the setting of linear-
mixture MDPs (Ayoub et al., 2020) (a.k.a. model-based setting) and provide an
unified framework for analyzing joint and local differential private (DP)
exploration. Through this framework, we prove a
$\widetilde{O}(K^{3/4}/\sqrt{\epsilon})$ regret bound for
$(\epsilon,\delta)$-local DP exploration and a
$\widetilde{O}(\sqrt{K/\epsilon})$ regret bound for $(\epsilon,\delta)$-joint
DP. We further study privacy-preserving exploration in linear MDPs (Jin et
al., 2020) (a.k.a. model-free setting) where we provide a
$\widetilde{O}\left(K^{\frac{3}{5}}/\epsilon^{\frac{2}{5}}\right)$ regret
bound for $(\epsilon,\delta)$-joint DP, with a novel algorithm based on low-
switching. Finally, we provide insights into the issues of designing local DP
algorithms in this model-free setting.

###  1 INTRODUCTION

Privacy-preserving techniques are fundamental for deploying machine learning
solutions to applications involving sensitive data. Differential privacy
(Dwork et al., 2014, DP) is the standard technique for building algorithms
with privacy guarantees on individual data. While the standard framework
applies to a batch setting where the training data is available before hand
(e.g., Erlingsson et al., 2014; Dwork et al., 2014; Abadi et al., 2016; Abowd,
2018), only recently the literature has focused on studying privacy-preserving
techniques for sequential decision-making problems (e.g., Shariff and Sheffet,
2018; Zheng et al., 2020; Vietri et al., 2020; Garcelon et al., 2020).

In this paper, we contribute to the study of DP in online reinforcement
learning (RL). For online RL on sensitive data, we assume that a single user
enters the system at each episode $k$ and interacts with the system for a fix-
horizon $H$. Through the interaction, the user reveals states and rewards that
contain sensitive information. In the non-private case the goal of the
learning agent is to select actions maximizing the cumulative reward of the
users. The agent thus needs to balance exploration to get information about
users and exploitation to maximize the reward. In privacy-preserving RL, we
additionally aim to provide privacy guarantees on users’ data (i.e., states,
rewards or any function of these values). The literature around privacy-
preserving exploration in RL has focused on joint and local DP (Vietri et al.,
2020; Garcelon et al., 2020). In the JDP setting, users are willing to reveal
sensitive data to the agent but they want to prevent third-parties from
inferring sensitive information by observing the behavior of the learning
agent. On the other hand, in the local model, users are more wary about
privacy and additionally require the learning agent to observe only privatized
information. These works come with provably efficient guarantees, but their
algorithms and analysis are limited to tabular settings. This limitation makes
it difficult to extract insights about the design and analysis of more
practical algorithms.222While preparing this draft, we noticed a very recent
concurrent work that studied _only_ JDP in linear-mixture MDPs (Liao et al.,
2021). We recover the same bound when $C_{w}=\sqrt{d}$, see Cor. 5. Our scope
is broader, we study both JDP and LDP in linear-mixture MDP and also JDP in
linear MDPs.

In this paper, we take a first step in this direction, by providing
theoretical-grounded insights on the design of private RL algorithms using
parametric representations. We show that, in this setting, designing efficient
and private algorithms is not simple and it poses new challenges w.r.t. the
tabular setting that require novel solutions. More precisely, we consider
(continuous) sequential decision-making problems with linear parametric
representations, and provide novel algorithm with provably efficient
guarantees for privacy-preserving exploration. For the linear-mixture
representation (Ayoub et al., 2020), we provide a unified framework which
allows to study both joint and local DP. Through this framework, we prove a
$\widetilde{O}(K^{3/4}/\sqrt{\epsilon})$ regret bound over $K$ episodes for
$(\epsilon,\delta)$-local DP exploration and a
$\widetilde{O}(\sqrt{K/\epsilon})$ regret bound for $(\epsilon,\delta)$-joint
DP. The key feature enabling these results is the intrinsic model-based nature
of this setting, which, similarly to the tabular setting, allows to build a
private estimate of the model. In the case of linear model (Jin et al., 2020),
the model-free nature poses additional challenges compared to the tabular or
linear-mixture scenario. Thanks to the use of batching, we provide a novel
$(\epsilon,\delta)$-JDP algorithm whose regret bound is
$\widetilde{O}\left(K^{\frac{3}{5}}/\epsilon^{\frac{2}{5}}\right)$. Notably,
batching is not used to improve the computational efficiency but it is
critical for achieving the improved $K^{\frac{3}{5}}$ rate. Indeed, without
batching, we are only able to prove a $\widetilde{O}(K^{3/4}/\sqrt{\epsilon})$
regret bound, see Sec. 4. On the other hand, we were not able to derive an LDP
exploration result for this setting and we conjecture it may require a
substantially different approach. As far as we know, these are the first
model-free private algorithm for exploration in the literature able to scale
beyond the tabular setting. We summarize all the results in Tab. 1.

Algorithm | Setting | JDP | LDP | Regret
---|---|---|---|---
Garcelon et al. (2020) | Tab. | $\epsilon,0$ | $\epsilon,0$ | $\widetilde{O}(H^{\frac{3}{2}}S\sqrt{AK}+\frac{H^{3}S^{2}A\sqrt{K}}{\epsilon})$
Vietri et al. (2020) | Tab. | $\epsilon,0$ | N/A | $\widetilde{O}\left(H^{2}\sqrt{SAK}+\frac{SAH^{3}+S^{2}AH^{3}}{\epsilon}\right)$
Our - Cor. 5 | LM | $\epsilon,\delta$ | N/A | $\widetilde{O}\left(C_{w}d^{\frac{3}{4}}H^{\frac{9}{4}}\sqrt{K}/\epsilon^{\frac{1}{2}}+dH^{2}\sqrt{K}\right)$
Our - Cor. 6 | LM | $\epsilon,\delta$ | $\epsilon,\delta$ | $\widetilde{O}\left(C_{w}d^{\frac{3}{4}}H^{\frac{5}{2}}K^{\frac{3}{4}}/\epsilon^{\frac{1}{2}}+dH^{2}\sqrt{K}\right)$
Our - Thm. 8 | L | $\epsilon,\delta$ | N/A | $\widetilde{O}\left(d^{\frac{8}{5}}H^{\frac{11}{5}}K^{\frac{3}{5}}/\epsilon^{\frac{2}{5}}+d^{\frac{3}{2}}H^{2}\sqrt{K}\right)$
Table 1: Summary of privacy/regret values for exploration in RL (Tab. =
tabular, LM=linear mixture, L=linear). Refer to Rem. 1 and 2 for a discussion
around pure differential privacy ($\delta=0$).

###  2 PRELIMINARIES

We consider a time-inhomogeneous finite-horizon Markov decision process (MDP)
$M=\big{(}\mathcal{S},\mathcal{A},H,$
$\\{r_{h}\\}_{h=1}^{H},\\{p_{h}\\}_{h=1}^{H}\big{)}$ where $\mathcal{S}$ is
the state space and $\mathcal{A}$ is the action space, $H$ is the length of
the episode, $\\{r_{h}\\}$ and $\\{p_{h}\\}$ are the reward function and
state-transition probability measure. We assume that
$r_{h}:\mathcal{S}\times\mathcal{A}\to[0,1]$ is the deterministic reward
function at step $h$.333While we consider deterministic rewards, our work can
be easily generalized to unknown stochastic rewards. We assume that
$\mathcal{S}$ is a measurable space with a possibly infinite number of
elements and $\mathcal{A}$ is a finite set. A deterministic policy
$\pi=(\pi_{1},\ldots,\pi_{H})\in\Pi$ is a sequence of decision rules
$\pi_{h}:\mathcal{S}\to\mathcal{A}$. For every $h\in[H]:=\\{1,\ldots,H\\}$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$, we define the value functions of a
policy $\pi$ as $V^{\pi}_{h}(s,a)=Q_{h}^{\pi}(s,\pi_{h}(s))$ and
$Q_{h}^{\pi}(s,a)=r_{h}(s,a)+\mathbb{E}_{\pi}\left[\sum_{i=h+1}^{H}r_{i}(s_{i},a_{i})\right]$,
where the expectation is over probability measures induced by the policy and
the MDP over state-action sequences of length $H-h$. Under certain regularity
conditions (e.g., Bertsekas and Shreve, 2004), there always exists an optimal
deterministic policy $\pi^{\star}$, such that
$V^{\pi^{\star}}_{h}(s):=V^{\star}_{h}(s)=\sup_{\pi}V^{\pi}_{h}(s)$ and
$Q^{\pi^{\star}}_{h}(s,a):=Q^{\star}_{h}(s,a)=\sup_{\pi}Q^{\pi}_{h}(s,a)$.

When the state space is large or continuous, it is common to resort to a
parametric representation of the MDP. In this paper, we consider MDPs having
linear structure (Jin et al., 2020) or linear-mixture structure (Ayoub et al.,
2020), two common assumptions which enables efficient learning through model-
free and model-based algorithms.

######  Assumption 1 (Linear MDP).

Let $\phi:\mathcal{S}\times\mathcal{A}\to\mathbb{R}^{d}$ be a feature map. An
MDP has linear structure if

$\displaystyle\forall s,a,h,s^{\prime},\quad r_{h}(s,a)$
$\displaystyle=\phi(s,a)^{\mathsf{T}}\theta_{h},$ $\displaystyle
p_{h}(s^{\prime}|s,a)$
$\displaystyle=\phi(s,a)^{\mathsf{T}}\mu_{h}(s^{\prime})$

where $\mu_{h}:\mathcal{S}\to\mathbb{R}^{d}$. We assume
$\|\theta_{h}\|_{2}\leq\sqrt{d}$,
$\|\int_{\mathcal{S}}\mu_{h}(s^{\prime})v(s^{\prime})\mathrm{d}s^{\prime}\|_{2}\leq\sqrt{d}\|v\|_{\infty}$
and $\|\phi(s,a)\|_{2}\leq 1$, for any $s,a,h$ and function
$v:\mathcal{S}\to\mathbb{R}$.

This definition implies that the value function of any policy is linear in the
features, i.e., for any policy $\pi\in\Pi$, $\exists
w_{h}^{\pi}\in\mathbb{R}^{d}$ such that
$Q^{\pi}_{h}(s,a)=\phi(s,a)^{\mathsf{T}}w_{h}^{\pi}$. In the context of regret
minimization, Jin et al. (2020) proposed a model-free algorithm that achieves
a $\widetilde{O}(\sqrt{d^{3}H^{4}K})$ regret bound.

######  Assumption 2 (Linear-Mixture MDP).

Let $\phi:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to\mathbb{R}^{d}$ be a
feature map. An MDP has linear-mixture structure if

$\displaystyle\forall s,a,s^{\prime},h\quad
p_{h}(s^{\prime}|s,a)=\phi(s^{\prime}|s,a)^{\mathsf{T}}w_{h}$

where $w_{h}\in\mathbb{R}^{d}$ and $\|w_{h}\|_{2}\leq C_{w}$. Furthermore, for
any bounded function $v:\mathcal{S}\to[0,1]$, we have that
$\|\phi_{v}(s,a)\|\leq 1$ where
$\phi_{v}(s,a)=\int_{s^{\prime}\in\mathcal{S}}\phi(s^{\prime}|s,a)v(s^{\prime})\mathrm{d}s^{\prime}$
is computable.

In contrast to Asm. 1, this structure allows to directly estimate the
transition model (i.e., $(w_{h})_{h}$) through a linear regression problem.
This property was used by Ayoub et al. (2020) to design a model-based
algorithm whose regret bound is $\widetilde{O}(dH^{2}\sqrt{K})$. This bound
was refined to $\widetilde{O}(dH^{3/2}\sqrt{K})$ in (Zhou et al., 2021),
through the use of variance-aware concentrations.

####  2.1 Privacy-Preserving Exploration

We consider the standard online interaction protocol where users interact with
a learning algorithm (also called _server_ in the privacy literature). As
common, we assume $r$ is known and $p$ is unknown. At each episode $k$, a new
user $\mathfrak{u}_{k}$444Similarly to (Vietri et al., 2020; Garcelon et al.,
2020), a user here is represented by a tree of depth $H$, where each node
contains the state, reward and the features associated to this state. arrives
and their personal information is encoded in state $s_{1k}$. The learning
algorithm provides a policy $\pi_{k}$ that is executed by the user, and a
trajectory $\tau_{k}=(s_{hk},a_{hk},r_{hk})_{h\in[H]}$ is collected and sent
to the algorithm. We evaluate the performance of a learning algorithm by its
cumulative regret $R(K)=\sum_{k=1}^{K}V^{\star}(s_{1k})-V^{\pi_{k}}(s_{1k})$.
In addition, we want to guarantee that the algorithm preserves users’ privacy
while minimizing the regret.

In RL, two notions of differential privacy (Dwork et al., 2006) has been
considered. Joint DP (e.g. Vietri et al., 2020) is the analogous of central DP
normally considered in machine learning. Given two sequences of $K$ users
$\mathfrak{U}_{K}=(\mathfrak{u}_{1},\dots,\mathfrak{u}_{K})$ and
$\mathfrak{U}^{\prime}_{K}=(\mathfrak{u}^{\prime}_{1},\dots,\mathfrak{u}^{\prime}_{K})$,
these sequences are said to be $k_{0}$-neighbors if
$\mathfrak{u}_{i}=\mathfrak{u}^{\prime}_{i}$ for all $i\neq k_{0}$ and
$\mathfrak{u}_{k_{0}}\neq\mathfrak{u}^{\prime}_{k_{0}}$. For any
$k_{0}\in[K]$, let $\mathcal{A}_{-k_{0}}(\mathfrak{U}^{K})$ be the set of
possible sequence of actions (excluding the one from user $k_{0}$) produced by
an algorithm $\mathcal{A}$.

######  Definition 3 (Joint DP).

An algorithm $\mathcal{A}$ is $(\epsilon,\delta)$-JDP under continual
observation if for any $k_{0}\in[K]$, any pair of $k_{0}$-neighboring user’s
sequences $\mathfrak{U}_{K}$, $\mathfrak{U}^{\prime}_{K}$, we have:

$\mathbb{P}\left(\mathcal{A}_{-k_{0}}(\mathfrak{U}_{K})\in E\right)\leq
e^{\epsilon}\mathbb{P}\left(\mathcal{A}_{-k_{0}}(\mathfrak{U}^{\prime}_{K})\in
E\right)+\delta$

where $E\subseteq A^{H\times[K-1]}\times\Pi$ is a set of sequence of actions
and a policy.

In terms of privacy model, _users trust the RL algorithm with their raw data_
(i.e., states, rewards, features, etc.) and the adversary can only observe the
output of the algorithm. The privacy guarantee ensures that when a user
changes, the actions computed by the algorithm for the other $K-1$ users stay
the same, hence the adversary can not infer the sequence of states, actions,
features and rewards associated to the changed user.

Garcelon et al. (2020) studied the stronger _local differential privacy_ (LDP)
notion. In contrast to JDP, users do not trust the algorithm with their
sensitive data. Instead, the algorithm has access to user information only
through samples that have been privatized, i.e., _it cannot observe directly
states, actions, features and rewards_. The appeal of this local model is that
privatization can be done on the user’s side using a randomizer $\mathcal{M}$,
making the protocol more secure.

######  Definition 4 (Local DP).

For any $\epsilon\geq 0$ and $\delta\geq 0$, a privacy preserving-mechanism
$\mathcal{M}$ is said to be $(\epsilon,\delta)$-LDP iff for all users
$\mathfrak{u},\mathfrak{u}^{\prime}\in\mathfrak{U}$, trajectories
$(\tau_{\mathfrak{u}},\tau_{\mathfrak{u}^{\prime}})\in\mathcal{T}_{\mathfrak{u}}\times\mathcal{T}_{\mathfrak{u}^{\prime}}$
and all
$E\subset\\{\mathcal{M}(\mathcal{T}_{\mathfrak{u}})|\mathfrak{u}\in\mathfrak{U}\\}$:

$\mathbb{P}(\mathcal{M}(\tau_{\mathfrak{u}})\in E)\leq
e^{\epsilon}\mathbb{P}(\mathcal{M}(\tau_{\mathfrak{u}^{\prime}})\in E)+\delta$

where $\mathcal{T}_{\mathfrak{u}}$ is the space of trajectories associated to
the user $\mathfrak{u}$.

###  3 PRIVACY IN LINEAR-MIXTURE MDPS

Input: episodes $K$, horizon $H$, ambient dimension $d$, privacy parameters
$\epsilon,\delta$, failure probability $p$, bound $C_{w}$

Initialize $\lambda=H^{2}$ and, $\forall h\in[H]$,
$\widetilde{\Lambda}_{1,h}=\lambda\cdot I_{d\times d}$,
$\widetilde{u}_{1,h}=0_{d}$, $\widetilde{w}_{1,h}=0_{d}$

Initialize $\beta_{k}$ satisfying the condition in Thm. 7

for  _$k=1,\dots,K$_ do

// User’s side

Receive $(\widetilde{\Lambda}_{k,h})_{h\in[H]}$ and
$(\widetilde{w}_{k,h})_{h\in[H]}$

for  _$h=1,\dots,H$_ do

Observe $s^{k}_{h}$

Choose action $a^{k}_{h}=\operatorname*{arg\,max}_{a\in
A}\widetilde{Q}_{k,h}(s^{k}_{h},a)$

$\widetilde{Q}_{k,h}(\cdot,\cdot)=\min\Big{\\{}H,r_{h}(\cdot,\cdot)+\langle\phi_{\widetilde{V}_{k,h+1}}(\cdot,\cdot),\widetilde{w}_{k,h}\rangle+\beta_{k}\Big{\lVert}\phi_{\widetilde{V}_{k,h+1}}(\cdot,\cdot)\Big{\rVert}_{\widetilde{\Lambda}^{-1}_{k,h}}\Big{\\}}$

$\widetilde{V}_{k,h}(\cdot)=\max_{a\in A}\widetilde{Q}_{k,h}(\cdot,a)$

end for

For any $h\in[H]$, let
$X_{k,h}=\phi_{\widetilde{V}_{k,h+1}}(s^{k}_{h},a^{k}_{h})$,
$y_{k,h}=\widetilde{V}_{k,h+1}(s^{k}_{h+1})$

Send
$\left\\{X_{k,h}X^{\intercal}_{k,h}+B^{1}_{k,h},X_{k,h}y_{k,h}+g^{1}_{k,h}\right\\}_{h\in[H]}$

// Server’s side (i.e., algorithm)

Update design matrix and target $\forall h\in[H]$

for  _$h=1,\dots,H$_ do

$B_{k+1,h}=\left(\sum_{1\leq i\leq k}B^{1}_{i,h}\right)+B^{2}_{k,h}$

$g_{k+1,h}=\left(\sum_{1\leq i\leq k}g^{1}_{i,h}\right)+g^{2}_{k,h}$

$\widetilde{\Lambda}_{k+1,h}=\lambda I_{d\times
d}+\sum_{i=1}^{k}X_{i,h}X^{\intercal}_{i,h}+B_{k+1,h}$

$\widetilde{u}_{k+1,h}=\sum_{i=1}^{k}X_{i,h}y_{i,h}+g_{k+1,h}$

$\widetilde{w}_{k+1,h}=\widetilde{\Lambda}^{-1}_{k+1,h}\cdot\widetilde{u}_{k+1,h}$

end for

end for

Algorithm 1 Privacy-Preserving UCRL-VTR

In the non-private setting, efficient algorithms for exploration leverage the
structure in Asm. 2 to build an estimate of the dynamics. At each episode $k$,
they compute an estimate $w_{k,h}$ of the unknown transitions and a confidence
ellipsoid

$\widehat{\mathcal{C}}_{k,h}=\\{w|(w-w_{k,h})^{\mathsf{T}}\Lambda_{k,h}(w-w_{k,h})\leq\beta_{k}\\}.$

Then, following the optimism in the face of uncertainty principle, they
construct an optimistic estimate of the optimal Q-function

$Q_{k,h}(\cdot,\cdot)=\min\Big{\\{}H,r_{h}(\cdot,\cdot)+\max_{w\in\widehat{\mathcal{C}}_{k,h}}\langle
w,\phi_{V_{k,h+1}}(\cdot,\cdot)\rangle\Big{\\}},$

and $V_{k,h}(\cdot)=\max_{a}Q_{k,h}(\cdot,a)$. The main difference resides in
the way these confidence intervals are built. For example, UCRL-VTR (Ayoub et
al., 2020) uses a standard self-normalized concentration inequality, while
UCRL-VTR+ (Zhou et al., 2021) a variance-aware concentration bound. For ease
of presentation, we focus on UCRL-VTR in this section, the reader may refer to
App. D for the variant based on UCRL-VTR+.

Guaranteeing privacy presents the additional challenge of privatizing these
estimates without significantly deteriorating the regret. By noticing that
$w_{k,h}$ is computed through ridge regression (e.g., Ayoub et al., 2020, Eq.
4), we can take inspiration from the linear bandit literature (Shariff and
Sheffet, 2018; Zheng et al., 2020) to build private estimates. Denote by
$\widetilde{w}_{k,h}=(\widetilde{\Lambda}_{k,h})^{-1}\widetilde{u}_{k,h}$ the
model estimate, where555In all the paper, we use the notation
$\,\widetilde{\cdot}\,$ to denote private (i.e., perturbed) quantities.

$\displaystyle\widetilde{\Lambda}_{k,h}$ $\displaystyle=\underbrace{\lambda
I_{d\times
d}+\sum_{i=1}^{k-1}X_{i,h}X_{i,h}^{\mathsf{T}}}_{:=\Lambda_{k,h}}+B_{k,h}$ (1)
$\displaystyle\widetilde{u}_{k,h}$
$\displaystyle=\sum_{i=1}^{k-1}X_{i,h}y_{i,h}+g_{k,h}$ (2)

and $X_{k,h}=\phi_{\widetilde{V}_{k,h+1}}(s_{h}^{k},a_{h}^{k})$. First, note
that setting $B_{k,h}=0$ and $g_{k,h}=0$ yields the non-private UCRL-VTR.666To
be precise, we should set $B^{1}_{k,h}=B^{2}_{k,h}=0_{d\times d}$ and
$g^{1}_{k,h}=g^{2}_{k,h}=0_{d}$. On the other hand, by making $B_{k,h}$ and
$g_{k,h}$ carefully designed noise terms, we can guarantee either JDP or LDP
privacy for the sequence
$(\widetilde{w}_{k,h},\widetilde{\Lambda}_{k,h})_{k,h}$ observed by the users.

Before proceeding, note that $B_{k,h}$ and $g_{k,h}$ can be further decompose
as follows: $B_{k,h}=B_{k,h}^{2}+\sum_{i=1}^{k-1}B_{i,h}^{1}$ and
$g_{k,h}=g_{k,h}^{2}+\sum_{i=1}^{k-1}g_{i,h}^{1}$. While the terms
$B^{1}_{i,h}$ and $g^{1}_{i,h}$ regulates the LDP level, the terms
$B^{2}_{i,h}$ and $g^{2}_{i,h}$ are responsible for the JDP guarantees. We can
already notice that, as expected, the impact of LDP is much larger than the
one of JDP since it is cumulated over episodes. For example, in order to
ensure JDP, we set $B^{1}_{k,h}=0_{d\times d}$ and $g^{1}_{k,h}=0_{d}$,
whereas $B^{2}_{k,h}$ and $g^{2}_{k,h}$ are perturbations associated to the
tree-based method (see App. C). On the other way, the LDP algorithm follows by
adding gaussian noises in the information sent to the server (i.e.,
$B^{1}_{k,h},g^{1}_{k,h}$) and setting $g^{2}_{k,h}=0_{d}$ and $B^{2}_{k,h}$
as a deterministic matrix (see Cor. 6). This shows the flexibility of the
proposed unified framework.

We are now ready to present the privacy/regret results for the unified
algorithm in Alg. 1.

######  Corollary 5 (JDP-UCRL-VTR).

Fix any privacy level $\epsilon,\delta\in(0,1)$. Set $B^{1}_{k,h}=0_{d\times
d}$, $g^{1}_{k,h}=0_{d}$ and $B^{2}_{k,h}$, $g^{2}_{k,h}$ as the noises
associated to the $k$-th prefix of trees containing in each node symmetric
matrices/vectors with all of its entries $\mathcal{N}(0,\sigma^{2}_{B})$,
where
$\sigma_{B}=\frac{32H^{2}}{\epsilon}\sqrt{2HK_{0}\log\left(\frac{8H}{\delta}\right)\log\left(\frac{4}{\delta}\right)\log\left(\frac{16HK_{0}}{\delta}\right)}$
and $K_{0}=\lceil\log_{2}(K)+1\rceil$. Let
$\Upsilon^{J}_{\frac{p}{6KH}}=\sigma_{B}\sqrt{K_{0}}\left(4\sqrt{d}+2\log\left(\frac{6KH}{p}\right)\right)$
and choose $\beta_{k}$ as:

$\beta_{k}=3(C_{w}+1)\sqrt{\lambda+\Upsilon^{J}_{\frac{p}{6KH}}}+\sqrt{2H^{2}\log\left(\frac{3H\cdot\left(1+KH\right)^{\frac{d}{2}}}{p}\right)}$

Then, for any $p\in(0,1)$, Alg. 1 is $(\epsilon,\delta)$-JDP and with
probability at least $1-p$, its regret is bounded by:

$R(K)=\widetilde{O}\left((C_{w}+1)\cdot\frac{d^{\frac{3}{4}}H^{\frac{9}{4}}\sqrt{K}}{\sqrt{\epsilon}}+dH^{2}\sqrt{K}\right)$

where $\widetilde{O}(\cdot)$ hides
polylog$\left(\frac{1}{p},\frac{1}{\delta},H,K\right)$ factors.

In the following corollary, we show that by simply changing the noise
perturbations we can achieve LDP guarantees. Note that the algorithm does not
need to know the features $\phi(s^{\prime}|s,a)$ and thus we can preserve
_local_ privacy over those features. On the other hand, we assume the users
have access to the features for planning and computing the information
$X_{h,k}$ and $y_{k,h}$ for the algorithm.

######  Corollary 6 (LDP-UCRL-VTR).

Fix any privacy level $\epsilon,\delta\in(0,1)$. Set
$B^{2}_{k,h}=2\Upsilon^{L}_{\frac{p}{6KH}}\cdot I_{d\times d}$,
$g^{2}_{k,h}=0_{d}$ and $B^{1}_{k,h}\sim\mathcal{N}(0,\sigma_{B}^{2}1_{d\times
d})$, $g^{1}_{k,h}\sim\mathcal{N}(0,\sigma_{B}^{2}I_{d\times d})$, where
$\sigma_{B}=\frac{4H^{3}}{\epsilon}\sqrt{2\log\left(\frac{4H}{\delta}\right)}$
and
$\Upsilon^{L}_{\frac{p}{6KH}}=\sigma_{B}\sqrt{K}\left(4\sqrt{d}+2\log\left(\frac{6KH}{p}\right)\right)$.
Then, choosing $\beta_{k}$ as follows:

$\beta_{k}=3(C_{w}+1)\sqrt{\lambda+\Upsilon^{L}_{\frac{p}{6KH}}}+\sqrt{2H^{2}\log\left(\frac{3H\cdot\left(1+KH\right)^{\frac{d}{2}}}{p}\right)}$

Alg. 1 is $(\epsilon,\delta)$-LDP and, for any $p\in(0,1)$, with probability
at least $1-p$, its regret is bounded as follows:

$R(K)=\widetilde{O}\left((C_{w}+1)\cdot\frac{d^{\frac{3}{4}}H^{\frac{5}{2}}K^{\frac{3}{4}}}{\sqrt{\epsilon}}+dH^{2}\sqrt{K}\right).$

These corollaries show a clear separation between tabular and linear-mixture
settings. Indeed, while we obtain a $\sqrt{T}$ regret bound for JDP as in the
tabular setting, the cost of privacy is not anymore additive but rather
multiplicative. We pay an ever higher price in LDP where we are not able to
recover a $\sqrt{T}$ regret bound. On the other hand, these results are
aligned with the one available for linear contextual bandits (Shariff and
Sheffet, 2018; Zheng et al., 2020) with JDP and LDP. The higher dependences in
$d$ and $H$ compared to the non-private setting are due to the need of
enlarging the confidence intervals to deal with the added noise. See the proof
sketch for more details.

######  Remark 1 (Pure DP).

Both corollaries exploit two properties of gaussian distributions: _i)_ they
are bounded with high probability; _ii)_ gaussian noise is enough to ensure
_approximate_ differential privacy by properly tuning the variance of the
distribution. Note that these properties also hold for other distributions
(e.g., Laplace noise). For example, replacing the gaussian mechanisms by the
Laplace mechanisms provides an algorithm that can achieve pure differential
privacy ($\delta=0$) at the cost of worsening the dependency on $d$ and $H$ in
the regret bounds of both corollaries. Indeed, every application of the
advanced composition theorem would be replaced by the simple composition and
hence, the variance of the noise would increase by a factor $\sqrt{H}$.
Similarly, $\Upsilon_{\frac{p}{6KH}}$ increases by a factor $\sqrt{d}$. These
changes translate into an additional factor $(dH)^{\frac{1}{4}}$ in Cor. 5 and
$d^{\frac{1}{4}}$ in Cor. 6 (see App. C).

Finally, we refer to the reader to App. D for a detailed comparison with the
variant based on UCRL-VTR+. Notably, similarly to the tabular setting
(Garcelon et al., 2020), the use of variance-aware concentrations does not
bring any advantage (in the main term) since the noise used for privacy
dominates the regret bound.

####  3.1 Proof Sketch of Corollary 5 and 6

In this section, we provide a sketch of the proof. We start providing an
intuition about the privacy analysis.

JDP privacy. The tree-based method (see App. F.4) ensures that the released
matrix $B_{k+1,h}$ is a sum of at most $K_{0}\approx\log_{2}(K)$ matrices with
gaussian entries $\mathcal{N}\left(0,\sigma^{2}_{B}\right)$. Due to the choice
of $\sigma_{B}$ and remarking that the sensitivity of
$X_{i,h}X^{\intercal}_{i,h}$ is at most $2H^{2}$ (since the Frobenius norm
$\Big{\lVert}X_{i,h}X^{\intercal}_{i,h}\Big{\rVert}_{F}\leq H^{2}$),
$(\widetilde{\Lambda}_{k,h})_{k}$ is indeed
$\Big{(}\epsilon\Big{(}2\sqrt{8H\log\left(\frac{4}{\delta}\right)}\Big{)}^{-1},\frac{\delta}{4H}\Big{)}$-DP
for any $h\in[H]$. The same result can be shown for the sequences
$(\widetilde{u}_{k,h})_{k}$. Then, by advanced composition (App. F.6),
$\left(\widetilde{\Lambda}_{k,h}\right)_{k,h}$ and
$\left(\widetilde{u}_{k,h}\right)_{k,h}$ are
$\left(\frac{\epsilon}{2},\frac{\delta}{2}\right)$-DP. By simple composition
(App. F.5) and the post-processing property (App. F.1), then we prove that the
sequence $\left(\widetilde{\Lambda}_{k,h},\widetilde{u}_{k,h}\right)_{(k,h)}$
is $(\epsilon,\delta)$-DP and by the post-processing property,
$(\widetilde{\Lambda}_{k,h},\widetilde{w}_{k,h})$ follows. As a consequence,
Alg. 1 is $(\epsilon,\delta)$-JDP due to the Billboard lemma (App. F.7) since
the $Q$-functions $Q^{P}_{k,h}(\cdot,\cdot)$ are a function of
$\widetilde{\Lambda}_{k,h}$, $\widetilde{w}_{k,h}$ and user’s private data.

LDP privacy. It suffices to show that
$\left(X_{k,h}X^{\intercal}_{k,h}+B^{1}_{k,h}\right)_{h}$ and
$\left(X_{k,h}y_{k,h}+g^{1}_{k,h}\right)_{h}$ are each
$\left(\frac{\epsilon}{2},\frac{\delta}{2}\right)$-LDP. Due to simple
composition of independent mechanisms, it is enough to prove that each
$(k,h)$-term is $\left(\frac{\epsilon}{2H},\frac{\delta}{2H}\right)$-LDP. This
claim follows from the choice of $\sigma_{B}$, the sensitivity of each of the
terms $X_{i,h}X^{\intercal}_{i,h}$, $X_{i,h}y_{i,h}$ ($2H^{2}$ in both cases)
and the design of the gaussian mechanisms.

Regret analysis. By leveraging the boundness of the noise, we can provide an
unified regret analysis of Alg. 1. Cor. 5 and Cor. 6 follows from a specific
instantiation of the parameters in the following theorem.

######  Theorem 7.

Assume that the following hypothesis hold with probability at least
$1-\frac{p}{3}$:

  1. 1.

There exist two sequences of non-negative real numbers
$(\Upsilon^{k}_{low})_{k},(\Upsilon^{k}_{high})_{k}$ such that all the
eigenvalues of $B_{k,h}$ belong to $[\Upsilon^{k}_{low},\Upsilon^{k}_{high}]$,
for all $h\in[H]$.

  2. 2.

There exists a sequence of non-negative real numbers $(C_{k})_{k}$ such that
$\Big{\lVert}g_{k,h}\Big{\rVert}_{2}\leq C_{k}$ for all $h\in[H]$.

  3. 3.

$(\beta_{k})_{k}$ is a non-decreasing777Any sequence $(\beta_{k})_{k}$ can be
converted into the non-decreasing sequence
$(\max\left\\{\beta_{1},\dots,\beta_{k}\right\\})_{k}$ sequence satisfying the
following inequality:

$\beta_{k}\geq\frac{(\lambda+\Upsilon^{k}_{high})C_{w}+C_{k}}{\sqrt{\lambda+\Upsilon^{k}_{low}}}+\sqrt{2H^{2}\log\left(\frac{3H\left(1+KH\right)^{\frac{d}{2}}}{p}\right)}$

Then, for any $p\in(0,1)$, with probability at least $1-p$, the regret of Alg.
1 is bounded as follows:

$R(K)=\widetilde{O}\left(\left(Hd^{\frac{1}{2}}\beta_{K}+H^{\frac{3}{2}}\right)\cdot
K^{\frac{1}{2}}\right)$

This theorem shows that the regret bound is directly proportional to the width
of the confidence interval. Indeed, in JDP, we obtain the same width as in the
non-private case, recovering the standard $\sqrt{K}$ rate. On the other hand,
LDP requires to enlarge the confidence intervals by a factor $K^{1/4}$ to
balance the noise for privacy, leading to a higher regret bound. The
corollaries follow by noticing that the perturbations described before are
bounded with high probability. We have that
$\Upsilon^{k}_{low}=\Upsilon^{J}_{\frac{p}{6KH}}$ (resp.
$\Upsilon^{L}_{\frac{p}{6KH}}$),
$\Upsilon^{k}_{high}=3\Upsilon^{J}_{\frac{p}{6KH}}$ (resp.
$3\Upsilon^{L}_{\frac{p}{6KH}}$), while
$C_{k}=\sigma_{B}\sqrt{\underline{K}}\left(\sqrt{d}+2\sqrt{\log\left(\frac{6KH}{p}\right)}\right)$
where $\underline{K}\approx\log_{2}(K)$ for JDP and $\underline{K}\approx K$
for LDP. Furthermore, $\beta_{k}\approx\sqrt{\log(K)}$ for JDP and
$\beta_{k}\approx K^{1/4}$ for LDP satisfy the third condition.

###  4 PRIVACY IN LINEAR MDPS

Input: episodes $K$, horizon $H$, ambient dimension $d$, privacy parameters
$\epsilon,\delta$ and failure probability $p$.

Initialize
$K_{0},B,\sigma_{u},\sigma_{\Lambda},\Upsilon^{J}_{\frac{p}{6KH}},\lambda,c_{K}$
and $\beta$ as in App. E.1

Initialize $\widetilde{\Lambda}_{0,h}=\lambda I_{d\times d}$,
$\widetilde{w}_{0,h}=0_{d}$ $\forall h\in[H]$, batch counter $b=0$,
$(\eta^{i}_{h})_{(i,h)\in[B]\times[H]}\in\mathbb{R}^{d}$ s.t.
$\eta^{i}_{h}\sim\mathcal{N}(0,\sigma^{2}_{u}\cdot I_{d\times d})$.

Build $H$ trees $(H_{h})_{h\in[H]}$ with $2B$ nodes, each node initialized
with a $d\times d$ symmetric matrix
$Z_{\Lambda}=\frac{Z^{\prime}_{\Lambda}+Z^{\prime T}_{\Lambda}}{2}$, where
$Z^{\prime}_{\Lambda}$ is a matrix of Gaussian noises
$\mathcal{N}(0,\sigma^{2}_{\Lambda})$.

For each $0\leq i<B$, $k_{i}=i\cdot\lceil\frac{K}{B}\rceil+1$.

for  _$k=1,\dots,K$_ do

// user’s side

Receive $(\widetilde{\Lambda}_{b,h})_{h\in[H]}$,
$(\widetilde{w}_{b,h})_{h\in[H]}$

for  _$h=1,\dots,H$_ do

Observe $D^{k}_{h}=\\{\phi(s_{k,h},a)|a\in\mathcal{A}\\}$

Take action
$a_{k,h}=\operatorname*{arg\,max}_{a\in\mathcal{A}}Q_{k,h}(s_{k,h},a)=\Pi_{[0,H]}\left[\widetilde{w}^{\intercal}_{b,h}\cdot\phi(s_{k,h},a)+\beta\lVert\phi(s_{k,h},a)\rVert_{\widetilde{\Lambda}^{-1}_{b,h}}\right]$

end for

Send $(D^{k}_{h})_{h\in[H]}$ and
$X_{u_{k}}=\\{(s_{k,h},a_{k,h},r_{k,h})_{h\in[H]}\\}$

// server’s side (algorithm)

if  _$k=k_{b+1}-1$_ then

$\widetilde{w}_{b+1,H+1}=0$, $Q_{k+1,H+1}(\cdot,\cdot)=0$

for  _$h=H,\dots,1$_ do

$\Lambda_{k+1,h}=\lambda\cdot I_{d\times
d}+\sum_{i=1}^{k}\phi(s_{i,h},a_{i,h})\phi(s_{i,h},a_{i,h})^{\mathsf{T}}$

$\widetilde{\Lambda}_{b+1,h}=\Lambda_{k+1,h}+\left(c_{K}+\Upsilon^{J}_{\frac{p}{6KH}}\right)I_{d\times
d}+H^{b+1}_{h}$ // $H^{b+1}_{h}$: $b+1$-th prefix of tree $H_{h}$

$u_{k+1,h}=\sum_{i=1}^{k}\phi(s_{i,h},a_{i,h})\left[r_{h}(s_{i,h},a_{i,h})+V_{k+1,h+1}(s_{i,h+1})\right]$

$\widetilde{u}_{b+1,h}=u_{k+1,h}+\eta^{b+1}_{h}$

$\widetilde{w}_{b+1,h}=\widetilde{\Lambda}^{-1}_{b+1,h}\cdot\widetilde{u}_{b+1,h}$

$Q_{k+1,h}(\cdot,\cdot)=\Pi_{[0,H]}\left[\phi(\cdot,\cdot)^{\mathsf{T}}\cdot\widetilde{w}_{b+1,h}+\beta\lVert\phi(\cdot,\cdot)\rVert_{\widetilde{\Lambda}^{-1}_{b+1,h}}\right]$,
$V_{k+1,h}(\cdot)=\max_{a\in\mathcal{A}}Q_{k+1,h}(\cdot,a)$

end for

$b=b+1$ // New batch, increase counter

end if

end for

Algorithm 2 Privacy-Preserving LSVI-UCB through Batching and JDP

In this section, we provide the first privacy-preserving algorithm for
exploration in linear MDPs. While we are able to design an efficient algorithm
with JDP guarantees, the design of an LDP algorithm remains an open question.
We anticipate that the model-free structure of algorithms plays a critical
role. In fact, the algorithms need to directly use features to perform
planning, thus making unclear how to perform efficiently this step in a local
model (see Rem. 5).

We based our algorithm on LSVI-UCB (Jin et al., 2020), an efficient optimistic
algorithm for exploration with $\widetilde{O}(\sqrt{d^{3}H^{4}K})$ minimax
regret bound. However, simply adapting LSVI-UCB to JDP leads to a sub-optimal
$\widetilde{O}(K^{3/4}/\sqrt{\epsilon})$ regret bound since to guarantee
privacy on all the $K$ outputs of the algorithm, the variance of the noise
scales with $\sqrt{K}$ and hence the regret increases by a $K^{1/4}$ factor
(see Rem. 3 and 7). We thus rely on batching techniques to decrease the number
of policy switching and thus the number of elements that we need to privatize.
Batching techniques have been investigate in the non-private literature for
improving the computational efficiency of algorithms (e.g., Gao et al., 2021;
Wang et al., 2021). In our case, batching is critical for improving the
minimax rate to $K^{\frac{3}{5}}$. To the best of our knowledge, Alg. 2 is the
first model-free exploration algorithm with JDP guarantees.

Similarly to (Wang et al., 2021), we employ a static batching scheme. Let
$b_{k}$ denote the batch at episode $k$ and $k_{b}$ the episode when batch $b$
started. Then, our algorithm updates the estimated $Q$-function every
$\Big{\lceil}\frac{K}{B}\Big{\rceil}$ episodes. The new private estimates of
$(w_{h}^{\pi^{\star}})_{h}$ are then computed through a _perturbed_ optimistic
least-square value iteration. Formally, we denote by
$\widetilde{w}_{b_{k},h}=\widetilde{\Lambda}_{b_{k},h}^{-1}\widetilde{u}_{b_{k},h}$
the estimated value with

$\displaystyle\widetilde{\Lambda}_{b_{k},h}$
$\displaystyle=\Lambda_{k_{b_{k}},h}+\left(c_{K}+\Upsilon^{J}_{\frac{p}{6KH}}\right)\cdot
I_{d\times d}+H^{b_{k}}_{h}$ $\displaystyle\widetilde{u}_{b_{k},h}$
$\displaystyle=\eta_{h}^{b_{k}}+\sum_{i=1}^{k_{b_{k}}-1}\phi(s_{i,h},a_{i,h})\left(r_{i,h}+V^{k_{b_{k}}}_{h+1}(s_{i,h+1})\right)$

$\widetilde{\Lambda}_{b_{k},h}$ is the design matrix perturbed through the
tree-based method, $\widetilde{u}_{b_{k},h}$ is the response vector perturbed
through Gaussian mechanism, $c_{K}$ is a regularizer that depends on the noise
injected for privacy and $\Lambda_{k,h}=\lambda I_{d\times
d}+\sum_{i=1}^{k-1}\phi(s_{i,h},a_{i,h})\phi(s_{i,h},a_{i,h})^{\mathsf{T}}$.
When a new user $u_{k}$ arrives, the algorithm provides the terms
$(\widetilde{w}_{b_{k},h},\widetilde{\Lambda}_{b_{k},h})_{h}$ so that the user
can play the optimistic greedy action. Then, we can guarantee that the
sequence of values is central-DP and the resulting algorithm is JDP.

The following theorem states the privacy/regret properties of Alg. 2.

######  Theorem 8.

Fix any privacy level $\epsilon,\delta\in(0,1)$. For any $p\in(0,1)$, Alg. 2
is $(\epsilon,\delta)$-JDP and, with probability at least $1-p$, its regret is
bounded as follows:

$R(K)=\widetilde{O}\left(\sqrt{d^{3}H^{4}K}+\frac{d^{\frac{8}{5}}H^{\frac{11}{5}}K^{\frac{3}{5}}}{\epsilon^{\frac{2}{5}}}\right)$

This theorem shows that it is possible to obtain a non-trivial
$K^{\frac{3}{5}}/\epsilon^{\frac{2}{5}}$ regret bound for JDP exploration,
leaving a $(K\epsilon)^{\frac{1}{10}}$ gap w.r.t. the linear-mixture setting.
However, the model-free nature of this setting calls for a different technique
for achieving such improved result result. We further notice that, compared to
the non-private case, in the worst case, we have a looser dependence w.r.t.
$H$ and $d$ induced by the noise injected for privacy and the static batching
schedule. We conclude this section with remarks.

######  Remark 2 (Pure DP).

Similarly to the linear-mixture setting, it is possible to obtain pure joint
DP ($\delta=0$) with polynomially worse regret bounds (see App. E.3).

######  Remark 3 (Non-Batched Algorithm).

As already mentioned, following a similar approach, it is possible to design
an $(\epsilon,\delta)$-JDP algorithm based on LSVI-UCB. The regret bound would
be $\widetilde{O}(K^{3/4}/\sqrt{\epsilon})$, a
$\widetilde{O}(K^{\frac{3}{20}}/\epsilon^{\frac{1}{10}})$-factor worse than
the one of Alg. 2. The intuition is that batching leads to less than
$B=O\left((K\epsilon)^{\frac{2}{5}}/(d^{\frac{3}{5}}H^{\frac{1}{5}})\right)$
policy switches, thus requiring privacy composition over a polynomially
smaller number of objects. Without batching, the number of elements would be
$K$ thus requiring to increase the noise variance $\sigma_{u}$ by a factor
scaling with $K^{\frac{3}{5}}/\epsilon^{\frac{2}{5}}$ compared to the one used
in Alg. 2. This change would result in the additional multiplicative factor to
the regret.

######  Remark 4 (Data-Dependent Batches).

An alternative approach for low-switching bandit is to leverage dynamic
batching, e.g., using a determinant (e.g., Abbasi-yadkori et al., 2011; Gao et
al., 2021) or a trace-based condition (e.g., Calandriello et al., 2020;
Garcelon et al., 2021). While these schemes will lead to a logarithmic number
of batches and to a potential improvement in the regret bound, it is unclear
how to carry out the privacy analysis. The main issue is that the starting
time of each batch becomes a random variable that depends on the specific user
sequence. Thus changing a user at episode $k_{0}$ may affect the time of _all_
the subsequent baches, making the current technique for privacy analysis not
applicable. It may be possible to protect batch times using the _sparse vector
technique_ (e.g. Hardt and Rothblum, 2010) for checking the condition.
However, it is unclear to us at the moment how to adapt their privacy analysis
to our setting. We leave this as an open question.

######  Remark 5 (Local Differential Privacy).

A key feature we leverage in the design of Alg. 2 is that in the JDP setting
the algorithm can directly access user’s data (features, states, rewards,
etc.). Indeed the JDP model assumes the attacker can only observe the output
of the algorithm and should not be able to infer user’s information from it.
On the other hand, LDP requires information to be privatized locally,
preventing the algorithm to have access to clean features. In linear-mixture
models, we overcome this limitation by leveraging the possibility of
estimating the model and performing planning on the user’s side. Indeed, all
the information required to estimate the model can be computed locally and
privatized before being sent to the algorithm. However, in the linear MDP
setting, planning is performed on the server side using a model-free approach
(least-square value iteration) which requires the knowledge of the features.

At each episode, LSVI requires to know the design matrix $\Lambda_{k+1,h}$ and
the response vector
$u_{k+1,h}=\sum_{i=1}^{k}\phi(s_{i,h},a_{i,h})\left(r_{i,h}+V_{k+1,h+1}(s_{i,h+1})\right)$
to compute the new estimate. The matrix $\Lambda_{k+1,h}$ is a simple sum of
independent rank-1 matrices, and it can be privatized using a standard local
randomizer (similarly to what done in the previous section). However, the
response vector requires to re-evaluate the entire sum by using the current
estimate $V_{k+1,h+1}$. A solution may be to provide to the algorithm with an
LDP version of the feature $\phi(s_{i,h},a)$ and of the reward $r_{i,h}$.
Unfortunately, the noise required to compute these independent private terms
compounds, leading to a linear regret. Note that we would have to deal with
the product of private terms (e.g., $\phi\cdot r$ and $\phi\cdot V$), thus
multiplying the noise level. Note that even in the case of contextual linear
bandit, privatizing independently rewards and contexts leads to a linear
regret bound.

Furthermore, even if a mechanism protecting the response vector $u_{k+1,h}$ is
available, the privacy analysis of Alg. 8 leverages the advanced composition
of adaptive DP mechanisms to reduce the amount of noise injected to
$u_{k+1,h}$, by noticing that its sensitivity is bounded by a term independent
of $K$. While composition of adaptive theorems are available for DP, we are
not aware of this result for LDP. As a consequence, the variance should scale
linearly with $K$ as the sensitivity of $u_{k+1,h}$ can be bounded this time
only by a linear term on $K$. We leave the design of an LDP algorithm for
linear MDPs as an open question. We believe a substantial different approach
is required to solve this problem.

####  4.1 Proof Sketch of Theorem 8

Full details of the proof are reported in App. E.2. We present here a sketch
of the regret and privacy analysis. As it can be easily observed, the number
of different policies played in Alg. 2, $N_{K}$, is at most $B$. We recall
that $0\leq b_{k}<N_{K}$ is the batch at episode $k$ and $k_{b}$ the first
episode of the $b$-th batch.

###### Privacy analysis.

For a sequence of $K$ users $\mathfrak{U}^{K}$ and for each $h\in[H]$, let
$M^{\Lambda}_{h}$ and $M^{u}_{h}$ be the following mechanisms acting on
$\mathfrak{U}^{K}$:
$M^{\Lambda}_{h}(\mathfrak{U}^{K})=(\widetilde{\Lambda}_{b_{k},h})_{k\in[K]},M^{u}_{h}(\mathfrak{U}^{K},\mathfrak{a}_{h+1})=(\bar{u}_{b_{k},h})_{k\in[K]}$
where $\mathfrak{a}_{h+1}$ corresponds to the output at the next stage
$\left(M^{\Lambda}_{h+1}(\mathfrak{U}^{K}),M^{u}_{h+1}(\mathfrak{U}^{K},\mathfrak{a}_{h+2})\right)$,
$\mathfrak{a}_{H+1}:=\emptyset$ and $\bar{u}_{b_{k},h}$:

$\displaystyle\bar{u}_{b_{k},h}=\sum_{i=1}^{k_{b_{k}}-1}\phi^{i}_{h}\Big{\\{}r^{i}_{h}+\Pi_{[0,H]}\Big{[}\max_{a\in
A}\Big{\langle}\left(\mathfrak{a}^{\Lambda}_{k,h+1}\right)^{-1}\mathfrak{a}^{u}_{k,h+1},$
(3)
$\displaystyle\phi(s^{i}_{h+1},a)\Big{\rangle}+\beta\Big{\lVert}\phi(s^{i}_{h+1},a)\Big{\rVert}_{(\mathfrak{a}^{\Lambda}_{k,h+1})^{-1}}\Big{]}\Big{\\}}+\eta^{b_{k}}_{h}$

It turns out that for the choice of Alg. 2,
$\mathfrak{a}_{h+1}=\left(\mathfrak{a}^{\Lambda}_{h+1},\mathfrak{a}^{u}_{h+1}\right)=\left((\widetilde{\Lambda}_{b_{k},h+1})_{k},(\widetilde{u}_{b_{k},h+1})_{k}\right)$,
we have $\bar{u}_{b_{k},h}=\widetilde{u}_{b_{k},h}$. We notice that
$(M^{\Lambda}_{h},M^{u}_{h})_{h}$ are adaptive mechanisms and hence, they are
perfectly suited to apply the advanced composition theorem.

Fix any $h\in[H]$ and notice that the choice of $\sigma_{\Lambda}$ ensures
that adding $H^{b+1}_{h}$ to $\Lambda_{k+1,h}$ protects it as an
$(\epsilon^{\prime},\delta^{\prime})$-DP mechanism, where
$\epsilon^{\prime}=\frac{\epsilon}{2\sqrt{8H\log\left(\frac{2}{\delta}\right)}}$,
$\delta^{\prime}=\frac{\delta}{4H}$. The mechanism
$M^{\Lambda}_{h}(\mathfrak{U}^{K})=(\widetilde{\Lambda}_{b_{k},h})_{k}$ is
$(\epsilon^{\prime},\delta^{\prime})$-DP as well since for two
$k_{0}$-neighboring sequences of users $\mathfrak{U}^{K}$ and
$\mathfrak{U}^{\prime K}$, the released matrices
$\widetilde{\Lambda}_{b_{k},h},\widetilde{\Lambda}^{\prime}_{b_{k},h}$ protect
the same matrix $\Lambda_{k_{b_{k}},h}$ given that the value of $b_{k}$ is
independent of the sequence of users.

The next step is to show that $M^{u}_{h}(\mathfrak{U}^{K},\mathfrak{a}_{h+1})$
is $(\epsilon^{\prime},\delta^{\prime})$-DP for each possible output
$\mathfrak{a}_{h+1}=(\mathfrak{a}^{\Lambda}_{h+1},\mathfrak{a}^{u}_{h+1})$888It
is necessary to prove it for any $\mathfrak{a}^{u}_{h+1}$ to apply advanced
composition. The key observation is that the term protected by $M^{u}_{h}$:

$\displaystyle\sum_{i=1}^{k_{b_{k}}-1}\phi^{i}_{h}\Big{\\{}r^{i}_{h}+\Pi_{[0,H]}\Big{[}\max_{a\in
A}\Big{\langle}\left(\mathfrak{a}^{\Lambda}_{k,h+1}\right)^{-1}\mathfrak{a}^{u}_{k,h+1},$
(4)
$\displaystyle\phi(s^{i}_{h+1},a)\Big{\rangle}+\beta\Big{\lVert}\phi(s^{i}_{h+1},a)\Big{\rVert}_{(\mathfrak{a}^{\Lambda}_{k,h+1})^{-1}}\Big{]}\Big{\\}}$

has a bounded sensitivity for two $k_{0}$-neighboring sequence of users since
the only difference would be at the term $k_{0}$ in the sum above as
$k_{b_{k}}$ is the same for both sequence of users (static batch scheme). It
then follows that the sensitivity is at most $2(H+1)$. Then, due to the choice
of $\sigma_{u}$, adding $\eta^{b}_{h}$ to $u^{k_{b}}_{h}$ with Gaussian
entries $\mathcal{N}(0,\sigma^{2}_{u})$ makes the mechanism $\bar{u}^{k}_{h}$
roughly
$\left(\frac{\epsilon^{\prime}}{\sqrt{B}},\frac{\delta^{\prime}}{2B}\right)$-DP.
By advanced composition, it follows that
$M^{u}_{h}(\mathfrak{U}^{K},\mathfrak{a}_{h+1})=(\bar{u}_{b_{k},h})_{k}$ is
$(\epsilon^{\prime},\delta^{\prime})$-DP since we have at most $B$ different
values for $\bar{u}_{b_{k},h}$. By advanced composition, it follows that
$(M^{\Lambda}_{h},M^{u}_{h})$ is
$\left(\epsilon\big{(}\sqrt{8H\log\left(\frac{2}{\delta}\right)}\big{)}^{-1},\delta/2H\right)$-DP
for each $h\in[H]$. A last application of advanced composition leads to prove
that $(M^{\Lambda}_{h},M^{u}_{h})_{h}$ is $(\epsilon,\delta)$-DP. It follows
that Alg. 2 is $(\epsilon,\delta)$-JDP as a consequence of the Billboard
lemma.

###### Regret analysis.

The analysis is fairly similar to the one in the non-private setting (e.g.,
Wang et al., 2021). The perturbations used for $\widetilde{\Lambda}_{b_{k},h}$
and $\widetilde{u}_{b_{k},h}$ impact the definition of the confidence set.
Indeed, assuming that we are in the “good” event, where the perturbations are
bounded, $\beta$ will scale with $\widetilde{O}(H\sqrt{d(\lambda+c_{K})})$,
since $\lambda+c_{K}$ is the new smallest eigenvalue of the perturbed design
matrix $\widetilde{\Lambda}_{b_{k},h}$. It is also easy to prove that under
the good event, the value functions are optimist and hence a very similar
argument to the one in (Wang et al., 2021, Thm. 5.1) leads to $R(K)\leq
2\sqrt{2KH^{3}\log\left(\frac{3}{p}\right)}+\sum_{k=1}^{K}\sum_{h=1}^{H}\min\left\\{H,2\beta\Big{\lVert}\phi^{k}_{h}\Big{\rVert}_{\widetilde{\Lambda}^{-1}_{k_{b_{k}},h}}\right\\}.$
In contrast to Wang et al. (2021), we build the set $\underline{\mathcal{C}}$
of pairs $(k,h)$ such that
$\Big{\lVert}\phi(s^{k}_{h},a^{k}_{h})\Big{\rVert}_{\widetilde{\Lambda}^{-1}_{b_{k},h}}>4\Big{\lVert}\phi(s^{k}_{h},a^{k}_{h})\Big{\rVert}_{\left(\Lambda_{k,h}+\left(c_{K}+2\Upsilon^{J}_{\frac{p}{6KH}}\right)I_{d\times
d}\right)^{-1}}$. Similarly,
$\lvert\underline{\mathcal{C}}\rvert\leq\Big{\lfloor}dH\cdot\Big{\lceil}\frac{K}{B}\Big{\rceil}\cdot\frac{\log\left(\frac{K}{d\lambda}+1\right)}{2\log
4-2}\Big{\rfloor}$, hence $R(K)\leq
2\sqrt{2KH^{3}\log(3/p)}+H\Big{\lfloor}dH\cdot\Big{\lceil}\frac{K}{B}\Big{\rceil}\cdot\frac{\log\left(\frac{K}{d\lambda}+1\right)}{2\log
4-2}\Big{\rfloor}+8\beta
H\sqrt{2dK\log\left(\frac{K}{\lambda+c_{K}}+1\right)}$. Carefully choosing
$B=\Big{\lceil}\frac{(K\epsilon)^{\frac{2}{5}}}{d^{\frac{3}{5}}H^{\frac{1}{5}}}\Big{\rceil}$
makes
$\beta=\widetilde{O}\left(dH+d^{\frac{11}{10}}H^{\frac{6}{5}}K^{\frac{1}{10}}/\epsilon^{\frac{2}{5}}\right)$
and the regret
$R(K)=\widetilde{O}\left(d^{\frac{3}{2}}H^{2}\sqrt{K}+d^{\frac{8}{5}}H^{\frac{11}{5}}K^{\frac{3}{5}}/\epsilon^{\frac{2}{5}}\right)$.

###  5 CONCLUSIONS

In this paper, we provided the first analysis of privacy-preserving
exploration in MDPs with linear structure. For linear-mixture MDPs, we
presented a unified framework that allowed us to prove a
$\widetilde{O}(\sqrt{K/\varepsilon})$ regret bound for JDP and
$\widetilde{O}(K^{3/4}/\sqrt{\varepsilon})$ for $(\epsilon,\delta)$-LDP. In
the case of linear MDPs, we presented a batched algorithm (Alg. 2) for
$(\epsilon,\delta)$-JDP exploration, whose regret bound is
$\widetilde{O}(K^{\frac{3}{5}}/\epsilon^{\frac{2}{5}})$.

Two interesting questions raised by our paper are whether it is possible to
design a JDP algorithm matching the
$\widetilde{O}\left(\sqrt{K/\epsilon}\right)$ regret bound of linear
contextual bandits or a LDP algorithm for linear MDPs. Another direction can
be to investigate the use of shuffle privacy model (e.g., Cheu et al., 2019;
Balle et al., 2019) to get guarantees akin to local privacy but better regret
bounds.

### References

  * Abadi et al. (2016) Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , pages 308–318, 2016.
  * Abbasi-yadkori et al. (2011) Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In _Advances in Neural Information Processing Systems_ , volume 24. Curran Associates, Inc., 2011.
  * Abowd (2018) John M Abowd.  The us census bureau adopts differential privacy.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 2867–2867, 2018.
  * Ayoub et al. (2020) Alex Ayoub, Zeyu Jia, Csaba Szepesvári, Mengdi Wang, and Lin Yang.  Model-based reinforcement learning with value-targeted regression.  In _ICML_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 463–474. PMLR, 2020.
  * Azuma (1967) Kazuoki Azuma.  Weighted sums of certain dependent random variables.  _Tohoku Mathematical Journal_ , 19(3):357 – 367, 1967.
  * Balle et al. (2019) Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim.  The privacy blanket of the shuffle model.  In _CRYPTO (2)_ , volume 11693 of _Lecture Notes in Computer Science_ , pages 638–667. Springer, 2019.
  * Bertsekas and Shreve (2004) Dimitir P Bertsekas and Steven Shreve.  _Stochastic optimal control: the discrete-time case_.  2004\.
  * Calandriello et al. (2020) Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, and Lorenzo Rosasco.  Near-linear time gaussian process optimization with adaptive batching and resparsification.  In _ICML_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 1295–1305. PMLR, 2020.
  * Chan et al. (2010) T.-H. Hubert Chan, Elaine Shi, and Dawn Song.  Private and continual release of statistics.  _IACR Cryptol. ePrint Arch._ , page 76, 2010.
  * Cheu et al. (2019) Albert Cheu, Adam D. Smith, Jonathan R. Ullman, David Zeber, and Maxim Zhilyaev.  Distributed differential privacy via shuffling.  In _EUROCRYPT (1)_ , volume 11476 of _Lecture Notes in Computer Science_ , pages 375–403. Springer, 2019.
  * Dwork et al. (2006) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith.  Calibrating noise to sensitivity in private data analysis.  In _TCC_ , volume 3876 of _Lecture Notes in Computer Science_ , pages 265–284. Springer, 2006.
  * Dwork et al. (2010a) Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum.  Differential privacy under continual observation.  In Leonard J. Schulman, editor, _Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010_ , pages 715–724. ACM, 2010a.
  * Dwork et al. (2010b) Cynthia Dwork, Guy N. Rothblum, and Salil Vadhan.  Boosting and differential privacy.  In _2010 IEEE 51st Annual Symposium on Foundations of Computer Science_ , pages 51–60, 2010b.
  * Dwork et al. (2014) Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  _Foundations and Trends® in Theoretical Computer Science_ , 9(3–4):211–407, 2014.
  * Erlingsson et al. (2014) Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova.  Rappor: Randomized aggregatable privacy-preserving ordinal response.  In _Proceedings of the 2014 ACM SIGSAC conference on computer and communications security_ , pages 1054–1067, 2014.
  * Gao et al. (2021) Minbo Gao, Tianle Xie, Simon S. Du, and Lin F. Yang.  A provably efficient algorithm for linear markov decision process with low switching cost, 2021.
  * Garcelon et al. (2020) Evrard Garcelon, Vianney Perchet, Ciara Pike-Burke, and Matteo Pirotta.  Local differentially private regret minimization in reinforcement learning.  _CoRR_ , abs/2010.07778, 2020.
  * Garcelon et al. (2021) Evrard Garcelon, Vianney Perchet, and Matteo Pirotta.  Homomorphically encrypted linear contextual bandit.  _CoRR_ , abs/2103.09927, 2021.
  * Hardt and Rothblum (2010) Moritz Hardt and Guy N. Rothblum.  A multiplicative weights mechanism for privacy-preserving data analysis.  In _FOCS_ , pages 61–70. IEEE Computer Society, 2010.
  * Hsu et al. (2016) Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, and Zhiwei Steven Wu.  Private matchings and allocations.  _SIAM Journal on Computing_ , 45(6):1953–1984, Jan 2016.  ISSN 1095-7111.
  * Jia et al. (2020) Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang.  Model-based reinforcement learning with value-targeted regression.  In _Proceedings of the 2nd Conference on Learning for Dynamics and Control_ , volume 120 of _Proceedings of Machine Learning Research_ , pages 666–686. PMLR, 2020.
  * Jin et al. (2018) Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan.  Is q-learning provably efficient?  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.
  * Jin et al. (2020) Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan.  Provably efficient reinforcement learning with linear function approximation.  In _COLT_ , volume 125 of _Proceedings of Machine Learning Research_ , pages 2137–2143. PMLR, 2020.
  * Kairouz et al. (2015) Peter Kairouz, Sewoong Oh, and Pramod Viswanath.  The composition theorem for differential privacy, 2015.
  * Kearns et al. (2014) Michael J. Kearns, Mallesh M. Pai, Aaron Roth, and Jonathan R. Ullman.  Mechanism design in large games: incentives and privacy.  In _ITCS_ , pages 403–410. ACM, 2014.
  * Laurent (2005) Béatrice Laurent.  Adaptive estimation of a quadratic functional of a density by model selection.  _Esaim: Probability and Statistics_ , 9:1–18, 2005.
  * Liao et al. (2021) Chonghua Liao, Jiafan He, and Quanquan Gu.  Locally differentially private reinforcement learning for linear mixture markov decision processes.  _CoRR_ , abs/2110.10133, 2021.
  * Mishra and Thakurta (2015) Nikita Mishra and Abhradeep Thakurta.  (nearly) optimal differentially private stochastic multi-arm bandits.  In _UAI_ , pages 592–601. AUAI Press, 2015.
  * Sajed and Sheffet (2019) Touqir Sajed and Or Sheffet.  An optimal private stochastic-mab algorithm based on optimal private stopping rule.  In _ICML_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 5579–5588. PMLR, 2019.
  * Shariff and Sheffet (2018) Roshan Shariff and Or Sheffet.  Differentially private contextual linear bandits.  In _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.
  * Tao (2011) Terence Tao.  _Topics in random matrix theory_.  2011\.
  * Tossou and Dimitrakakis (2016) Aristide C. Y. Tossou and Christos Dimitrakakis.  Algorithms for differentially private multi-armed bandits.  In _AAAI_ , pages 2087–2093. AAAI Press, 2016.
  * Vietri et al. (2020) Giuseppe Vietri, Borja de Balle Pigem, Akshay Krishnamurthy, and Steven Wu.  Private reinforcement learning with pac and regret guarantees.  In _ICML_ , 2020.
  * Wang et al. (2021) Tianhao Wang, Dongruo Zhou, and Quanquan Gu.  Provably efficient reinforcement learning with linear function approximation under adaptivity constraints, 2021.
  * Zhang (2011) Fuzhen Zhang.  _Matrix Theory: Basic Results and Techniques_.  Springer, New York, NY, second edition, 2011.
  * Zheng et al. (2020) Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang.  Locally differentially private (contextual) bandits learning.  In _NeurIPS_ , 2020.
  * Zhou et al. (2021) Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari.  Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.  In _Proceedings of Thirty Fourth Conference on Learning Theory_ , volume 134 of _Proceedings of Machine Learning Research_ , pages 4532–4576. PMLR, 2021.

## Appendix

###  Appendix A Related Work

Privacy-preserving exploration has been initially studied in the context of
multi-armed bandits (e.g., Mishra and Thakurta, 2015; Tossou and Dimitrakakis,
2016). More recently, Shariff and Sheffet (2018) showed that the standard DP
notion (central-DP) is incompatible with regret minimization in contextual
bandits, by showing a linear lower-bound. To overcome this limitation, they
considered the notion of _joint_ DP, originally introduced for mechanism
design (Kearns et al., 2014). They proposed a $(\epsilon,\delta)$-JDP
algorithm for contextual linear bandit whose regret bound is
$\widetilde{O}\Big{(}\frac{d^{3/4}\sqrt{K}}{\sqrt{\epsilon}}\Big{)}$. This
show that the cost of JDP is multiplicative in contextual linear bandit rather
than being additive as in central-DP exploration for MABs (e.g., Tossou and
Dimitrakakis, 2016; Sajed and Sheffet, 2019). More recently, Zheng et al.
(2020) studied the problem of local-DP exploration in contextual linear bandit
–they also considered the generalized linear case– and proved a
$\widetilde{O}\Big{(}\frac{(dK)^{3/4}}{\sqrt{\epsilon}}\Big{)}$.999In the
paper, Zheng et al. (2020) reported a linear dependence w.r.t. $\epsilon$. By
checking the analysis we noticed that a $\sqrt{\epsilon}$-dependence can be
obtained, improving the bound when $\epsilon<1$ that is the relevant regime in
privacy-preserving exploration. While our findings are aligned with the ones
in the contextual bandit literature, the design of our algorithms is much more
involved than the one for contextual linear bandits, as showed by the need of
batching for JDP in linear MDPs and the challenges for designing LDP
algorithms in the such a setting. Zheng et al. (2020) also conjectured that
the lower bound for LDP exploration is $\Omega(K^{3/4})$ in contextual linear
bandits, but we are not aware of any proof of this conjecture.

In the RL literature, privacy-preserving exploration was only studied in
tabular MDPs with $S$ states, $A$ actions and horizon $H$. Vietri et al.
(2020) introduced an $(\epsilon,0)$-JDP algorithm with
$\widetilde{O}\left(H^{2}\sqrt{SAK}+\frac{SAH^{3}+S^{2}AH^{3}}{\epsilon}\right)$
showing that, similarly to MABs, the cost of privacy is only additive to the
regret. On the other hand, Garcelon et al. (2020) showed that the cost of LDP
is multiplicative by deriving a
$\Omega\Big{(}\frac{H\sqrt{SAK}}{\min\\{e^{\epsilon}-1,1\\}}\Big{)}$ lower-
bound. They also introduce an $(\epsilon,0)$-LDP algorithm with
$\widetilde{O}(H^{\frac{3}{2}}S\sqrt{AK}+\frac{H^{3}S^{2}A\sqrt{K}}{\epsilon})$
regret bound. In this paper, we focus for the first time on privacy-preserving
exploration in MDPs with parametric structure.

###  Appendix B Table of notations

We provide the following table for reference.

Notation for linear-mixture MDPs
---
$C_{w}$ |  | parameter bound (i.e., $\|w_{h}\|_{2}\leq C_{w}$)
$\epsilon$ |  | privacy level
$\delta$ |  | privacy approximation
$p$ |  | probability (for regret bound)
$\widetilde{\Lambda}_{k,h}$ |  | perturbed design matrix
$\widetilde{u}_{k,h}$ |  | perturbed response vector
$\widetilde{w}_{k,h}$ |  | perturbed estimated vector
$B_{k,h}^{1}$ |  | LDP noise for design matrix
$B_{k,h}^{2}$ |  | JDP noise for design matrix
$g_{k,h}^{1}$ |  | LDP noise for response vector
$g_{k,h}^{2}$ |  | JDP noise for response vector
$\phi_{v}(s,a)$ | $=$ | $\int_{s^{\prime}\in\mathcal{S}}\phi(s^{\prime}|s,a)v(s^{\prime})\mathrm{d}s^{\prime}$
$\widetilde{Q}_{k,h}$ | $=$ | $\min\Big{\\{}H,r_{h}(\cdot,\cdot)+\langle\phi_{\widetilde{V}_{k,h+1}}(\cdot,\cdot),\widetilde{w}_{k,h}\rangle+\beta_{k}\Big{\lVert}\phi_{\widetilde{V}_{k,h+1}}(\cdot,\cdot)\Big{\rVert}_{(\widetilde{\Lambda}_{k,h})^{-1}}\Big{\\}}$
$\widetilde{V}_{k,h}(\cdot)$ | $=$ | $\max_{a}\widetilde{Q}_{k,h}(\cdot,a)$
$X_{k,h}$ | $=$ | $\phi_{\widetilde{V}_{k,h+1}}(s_{h}^{k},a_{h}^{k})$
$\eta_{h}^{b}$ |  | JDP noise for response vector
$[n]$ | $=$ | $\left\\{1,2,\dots,n\right\\}$
Notation for linear MDPs
---
$\epsilon$ |  | privacy level
$\delta$ |  | privacy approximation
$p$ |  | probability (for regret bound)
$b_{k}$ |  | batch at episode $k$
$k_{b}$ |  | starting episode of batch $b$
$\widetilde{\Lambda}_{b,h}$ |  | perturbed design matrix
$\widetilde{u}_{b,h}$ |  | perturbed response vector
$\widetilde{w}_{b,h}$ |  | perturbed estimated vector
$\eta_{h}^{b}$ |  | JDP noise for response vector
$H_{h}^{b}$ |  | noise from tree method
$[n]$ | $=$ | $\left\\{1,2,\dots,n\right\\}$
$B$ |  | Upper-bound to the total number of batches
$\Pi_{[0,H]}(x)$ |  | projection of $x$ on the interval $[0,H]$–i.e $\max\left\\{0,\min\left\\{H,x\right\\}\right\\}$

###  Appendix C Analysis of privacy-preserving UCRL-VTR

####  C.1 Proof of Thm. 7

We follow the proof given in Jia et al. (2020), but adopt the strategy of
Ayoub et al. (2020) relying on the self-normalized bound for vector-valued
martingales to provide high-probability confidence sets for the unknown
parameters $(w_{h})_{h}$.

#####  C.1.1 Confidence set of value target regression

We follow the generic idea in (Ayoub et al., 2020, E.4). Let
$\mathcal{E}_{hyp}$ be the event where the hypothesis of Thm. 7 hold. Hence,
$\mathbb{P}\left(\mathcal{E}_{hyp}\right)\geq 1-\frac{p}{3}$

Conditioned on the event $\mathcal{E}_{hyp}$, we will prove that
$\Big{\lVert}w_{h}-\widetilde{w}_{k,h}\Big{\rVert}_{\widetilde{\Lambda}_{k,h}}\leq\beta_{k}$
simultaneously for all $(k,h)\in[K]\times[H]$, with probability at least
$1-\frac{p}{3}$.

Fix any $h\in[H]$,

$\Big{\lVert}w_{h}-\widetilde{w}_{k,h}\Big{\rVert}_{\widetilde{\Lambda}_{k,h}}=\Big{\lVert}\widetilde{\Lambda}_{k,h}\left(w_{h}-\widetilde{w}_{k,h}\right)\Big{\rVert}_{\widetilde{\Lambda}^{-1}_{k,h}}$
$\Big{\lVert}w_{h}-\widetilde{w}_{k,h}\Big{\rVert}_{\widetilde{\Lambda}_{k,h}}=\Big{\lVert}\sum_{1\leq
i<k}X_{i,h}X^{\intercal}_{i,h}\cdot w_{h}+B_{k-1,h}w_{h}+\lambda\cdot
w_{h}-\sum_{1\leq
i<k}X_{i,h}y_{i,h}-g_{k-1,h}\Big{\rVert}_{\widetilde{\Lambda}^{-1}_{k,h}}$

Let $\eta_{k,h}=y_{k,h}-X^{\intercal}_{k,h}\theta^{\star}_{h}$ and observe
that $\eta_{k,h}$ is $H$-subgaussian since $\lvert\eta_{k,h}\rvert\leq H$.
Thus,

$\Big{\lVert}w_{h}-\widetilde{w}_{k,h}\Big{\rVert}_{\widetilde{\Lambda}_{k,h}}=\Big{\lVert}\sum_{1\leq
i<k}X_{i,h}\eta_{i,h}+B_{k-1,h}w_{h}+\lambda\cdot
w_{h}-g_{k-1,h}\Big{\rVert}_{\widetilde{\Lambda}^{-1}_{k,h}}$

Since $\left(\sum_{1\leq
i<k}X_{i,h}X^{\intercal}_{i,h}\right)+\left(\lambda+\Upsilon^{k-1}_{low}\right)\cdot
I_{d\times d}\preceq\widetilde{\Lambda}_{k,h}\preceq\left(\sum_{1\leq
i<k}X_{i,h}X^{\intercal}_{i,h}\right)+\left(\lambda+\Upsilon^{k-1}_{high}\right)\cdot
I_{d\times d}$, we conclude by Clm. 30 that:

$\Big{\lVert}w_{h}-\widetilde{w}_{k,h}\Big{\rVert}_{\widetilde{\Lambda}_{k,h}}\leq\Big{\lVert}\sum_{1\leq
i<k}X_{i,h}\eta_{i,h}\Big{\rVert}_{\widetilde{\Lambda}^{-1}_{k,h}}+\frac{\left(\lambda+\Upsilon^{k-1}_{high}\right)\cdot
C_{w}}{\sqrt{\lambda+\Upsilon^{k-1}_{low}}}+\frac{C_{k-1}}{\sqrt{\lambda+\Upsilon^{k-1}_{low}}}$
$\Big{\lVert}w_{h}-\widetilde{w}_{k,h}\Big{\rVert}_{\widetilde{\Lambda}_{k,h}}\leq\Big{\lVert}\sum_{1\leq
i<k}X_{i,h}\eta_{i,h}\Big{\rVert}_{\left(\left(\sum_{1\leq
i<k}X_{i,h}X^{\intercal}_{i,h}\right)+\lambda\cdot I_{d\times
d}\right)^{-1}}+\frac{\left(\lambda+\Upsilon^{k-1}_{high}\right)\cdot
C_{w}}{\sqrt{\lambda+\Upsilon^{k-1}_{low}}}+\frac{C_{k-1}}{\sqrt{\lambda+\Upsilon^{k-1}_{low}}}$

We apply the self-normalized bound inequality for vector-valued martingales
(Abbasi-yadkori et al., 2011) to the martingale $\eta_{k,h}$ with respect to
the filtration $\mathcal{G}_{k,h}$ generated by the random paths
$\left\\{(s^{k^{\prime}}_{h^{\prime}},a^{k^{\prime}}_{h^{\prime}},r^{k^{\prime}}_{h^{\prime}})\right\\}_{(k^{\prime},h^{\prime})\leq(k,h)}$
and the noises
$\left(g^{1}_{k^{\prime},h^{\prime}}\right)_{(k^{\prime},h^{\prime})\leq(k,h)}$,
$\left(g^{2}_{k^{\prime},h^{\prime}}\right)_{(k^{\prime},h^{\prime})\leq(k,h)}$,
$\left(B^{1}_{k^{\prime},h^{\prime}}\right)_{(k^{\prime},h^{\prime})\leq(k,h)}$,
$\left(B^{2}_{k^{\prime},h^{\prime}}\right)_{(k^{\prime},h^{\prime})\leq(k,h)}$101010The
notation $(k^{\prime},h^{\prime})\leq(k,h)$ is lexicographic. It is,
$k^{\prime}<k$ or $k^{\prime}=k$ and $h^{\prime}\leq h$..

That is $\mathbb{E}\left[\eta_{k,h}|\mathcal{G}_{k,h}\right]=0$ and observe
that $X_{k,h}$ and $\eta_{k+1,h}$ are $\mathcal{G}_{k,h}$-measurable.
We conclude that with probability at least $1-\frac{p}{3H}$:

$\Big{\lVert}\sum_{1\leq
i<k}X_{i,h}\eta_{i,h}\Big{\rVert}_{\left(\left(\sum_{1\leq
i<k}X_{i,h}X^{\intercal}_{i,h}\right)+\lambda\cdot
Id_{d}\right)^{-1}}\leq\sqrt{2H^{2}\log\left(\frac{3H\cdot\left(1+KH\right)^{\frac{d}{2}}}{p}\right)},\forall
k\in[K]$

Then,

$\Big{\lVert}w_{h}-\widetilde{w}_{k,h}\Big{\rVert}_{\widetilde{\Lambda}_{k,h}}\leq\sqrt{2H^{2}\log\left(\frac{3H\cdot\left(1+KH\right)^{\frac{d}{2}}}{p}\right)}+\frac{C_{w}\cdot\left(\lambda+\Upsilon^{k-1}_{high}\right)+C_{k-1}}{\sqrt{\lambda+\Upsilon^{k-1}_{low}}}=\beta_{k-1}\leq\beta_{k},\forall
k\in[K]$

In the union event, holding with probability at least $1-\frac{p}{3}$
conditioned on $\mathcal{E}_{hyp}$,
$\Big{\lVert}w_{h}-\widetilde{w}_{k,h}\Big{\rVert}_{\widetilde{\Lambda}_{k,h}}\leq\beta_{k}$
for any $(k,h)\in[K]\times[H]$ as initially wished.
Thus, since $\mathbb{P}\left(\mathcal{E}_{hyp}\right)\geq 1-\frac{p}{3}$,
$\Big{\lVert}w_{h}-\widetilde{w}_{k,h}\Big{\rVert}_{\widetilde{\Lambda}_{k,h}}\leq\beta_{k}$
for any $(k,h)\in[K]\times[H]$ occurs with probability at least
$1-\frac{2p}{3}$.

#####  C.1.2 Regret analysis

From now onwards, the proof is exactly the same as in (Jia et al., 2020, D.1),
the only changes are that every time we need to bound
$\lVert\cdot\rVert_{\widetilde{\Lambda}^{-1}_{k,h}}$ from above, we will
rather bound the term $\lVert\cdot\rVert_{\left(\lambda\cdot
Id_{d}+\sum_{1\leq i<k}X_{i,h}X^{\intercal}_{i,h}\right)^{-1}}$. Also, notice
that we initialize $\lambda=H^{2}$ instead of $\lambda=H^{2}d$ as in (Jia et
al., 2020) since a stationary transition probability is considered in their
case, where
$\Big{\lVert}X_{k,h}\Big{\rVert}^{2}=\Big{\lVert}\phi_{\widetilde{V}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\Big{\rVert}^{2}$
is bounded by $H^{2}d$, while in the setting we are considering (Asm. 2),
$\Big{\lVert}\phi_{\widetilde{V}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\Big{\rVert}^{2}\leq
H^{2}$ since $\widetilde{V}_{k,h+1}\left(\cdot\right)\leq H$ by definition.
We conclude then that with probability at least $1-p$111111Intersection of the
event where the the parameters $w_{h}$ belong to the confidence sets and the
Azuma’s inequality bounding the second term of the regret.:

$R(K)\leq
4\sqrt{H^{2}dK\beta_{K}\log\left(1+HK\right)}+\sqrt{2H^{3}K\log\left(\frac{3}{p}\right)}$
$R(K)=\widetilde{O}\left(\left(Hd^{\frac{1}{2}}\beta_{K}+H^{\frac{3}{2}}\right)K^{\frac{1}{2}}\right)$

####  C.2 Proof of Cor. 5

###### Full formulation of Cor. 5:

Fix any privacy level $\epsilon,\delta\in(0,1)$. Set $B^{1}_{k,h}=0_{d\times
d}$, $g^{1}_{k,h}=0_{d}$ and $B^{2}_{k,h}$, $g^{2}_{k,h}$ as the noises
associated to the $k$-th prefix of trees containing in each node symmetric
matrices/vectors with all of its entries $\mathcal{N}(0,\sigma^{2}_{B})$,
where
$\sigma_{B}=\frac{32H^{2}}{\epsilon}\sqrt{2HK_{0}\log\left(\frac{8H}{\delta}\right)\log\left(\frac{4}{\delta}\right)\log\left(\frac{16HK_{0}}{\delta}\right)}$
and $K_{0}=\lceil\log_{2}(K)+1\rceil$. More precisely, the trees are
initialized in a similar way as done in Sec. 4.2 from Shariff and Sheffet
(2018). It is, we instantiate $2H$ trees, each with $K$ leaves ($2K$ nodes)
and the first $H$ of them contain a symmetric matrix
$Z=(Z^{\prime}+Z^{\prime\intercal})/\sqrt{2}$ in each node, where
$Z^{\prime}\in\mathbb{R}^{d\times d}$ and each of its entries
$(Z^{\prime})_{i,j}$ is drawn according to i.i.d
$\mathcal{N}(0,\sigma^{2}_{B})$. The other $H$ of them will be instantiated
with gaussian vectors, each of them drawn from
$\mathcal{N}(0,\sigma^{2}_{B}\cdot I_{d\times d})$. Let
$\Upsilon^{J}_{\frac{p}{6KH}}=\sigma_{B}\sqrt{K_{0}}\left(4\sqrt{d}+2\log\left(\frac{6KH}{p}\right)\right)$.
$B^{2}_{k,h}$ is the $k$-th prefix of the $h$-th tree of random matrices
described above shifted by $2\Upsilon^{J}_{\frac{p}{6KH}}I_{d\times d}$.
Similarly, $g^{2}_{k,h}$ is the $k$-th prefix of the $h$-th tree of random
vectors described above. Finally, choose $\beta_{k}$ as:

$\beta_{k}=3(C_{w}+1)\sqrt{\lambda+\Upsilon^{J}_{\frac{p}{6KH}}}+\sqrt{2H^{2}\log\left(\frac{3H\cdot\left(1+KH\right)^{\frac{d}{2}}}{p}\right)}$

Then, for any $p\in(0,1)$, Alg. 1 is $(\epsilon,\delta)$-JDP and with
probability at least $1-p$, its regret is bounded by:

$R(K)=\widetilde{O}\left(\left((C_{w}+1)\cdot\frac{d^{\frac{3}{4}}H^{\frac{9}{4}}}{\sqrt{\epsilon}}+H^{2}d\right)\sqrt{K}\right)$

where $\widetilde{O}(\cdot)$ hides
polylog$\left(\frac{1}{p},\frac{1}{\delta},H,K\right)$ factors.

###### Regret analysis:

As explained in Shariff and Sheffet (2018); Zheng et al. (2020), due to Clm.
26, the eigenvalues of $B_{k,h}=B^{2}_{k,h}$ are in the interval
$\left[\Upsilon^{J}_{\frac{p}{6KH}},3\Upsilon^{J}_{\frac{p}{6KH}}\right]$ with
probability at least $1-\frac{p}{6KH}$ for each $(k,h)\in[K]\times[H]$ since
the eigenvalues of the tree-based mechanism are in
$\left[-\Upsilon^{J}_{\frac{p}{6KH}},\Upsilon^{J}_{\frac{p}{4KH}}\right]$ due
that it is the sum of at most $K_{0}$ matrices, each of them with gaussian
entries $\mathcal{N}(0,\sigma^{2}_{B})$. By a similar argument, due to Clm. 27
for each $(k,h)\in[K]\times[H]$, $g_{k,h}=g^{2}_{k,h}$ is in the interval
$\left[-C^{J}_{\frac{p}{6KH}},C^{J}_{\frac{p}{6KH}}\right]$ with probability
at least $1-\frac{p}{6KH}$, where
$C^{J}_{\frac{p}{6KH}}=\sigma_{B}\sqrt{K_{0}}\left(\sqrt{d}+2\sqrt{\log\left(\frac{6KH}{p}\right)}\right)$.
In the union event, with probability at least $1-\frac{p}{3}$, the eigenvalues
of $B_{k,h}$ are in the interval
$\left[\Upsilon^{k}_{low},\Upsilon^{k}_{high}\right]$ with
$\Upsilon^{k}_{low}=\Upsilon^{J}_{\frac{p}{6KH}}$,
$\Upsilon^{k}_{high}=3\Upsilon^{J}_{\frac{p}{6KH}}$ for any
$(k,h)\in[K]\times[K]$. Also, $\Big{\lVert}g_{k,h}\Big{\rVert}\leq C_{k}$,
where $C_{k}=C^{J}_{\frac{p}{6KH}}$ for any $(k,h)\in[K]\times[H]$.

The choice of
$\beta_{k}=3(C_{w}+1)\sqrt{\lambda+\Upsilon^{J}_{\frac{p}{6KH}}}+\sqrt{2H^{2}\log\left(\frac{3H\cdot\left(1+KH\right)^{\frac{d}{2}}}{p}\right)}$
is a constant sequence (independent of $k$) and hence, non-decreasing
satisfying that
$\beta_{k}\geq\frac{\left(\lambda+3\Upsilon^{J}_{\frac{p}{6KH}}\right)C_{w}+C^{J}_{\frac{p}{6KH}}}{\sqrt{\lambda+\Upsilon^{J}_{\frac{p}{6KH}}}}+\sqrt{2H^{2}\log\left(\frac{3H\left(1+KH\right)^{\frac{d}{2}}}{p}\right)}\geq\frac{(\lambda+\Upsilon^{k}_{up})C_{w}+C_{k}}{\sqrt{\lambda+\Upsilon^{k}_{low}}}+\sqrt{2H^{2}\log\left(\frac{3H\left(1+KH\right)^{\frac{d}{2}}}{p}\right)}$
since $\Upsilon^{J}_{\frac{p}{6KH}}\geq C^{J}_{\frac{p}{6KH}}$. The regret
bound just follows from Thm. 7 by replacing
$\beta_{k}=3(C_{w}+1)\sqrt{\lambda+\Upsilon^{J}_{\frac{p}{6KH}}}+\sqrt{2H^{2}\log\left(\frac{3H\cdot\left(1+KH\right)^{\frac{d}{2}}}{p}\right)}=\widetilde{O}\left((C_{w}+1)d^{\frac{1}{4}}H^{\frac{5}{4}}\frac{1}{\sqrt{\epsilon}}+H\sqrt{d}\right)$.

###### Privacy analysis:

First, we show that the mechanism
$(\widetilde{\Lambda}_{k,h},\widetilde{u}_{k,h})_{(k,h)\in[K]\times[H]}$ is
$(\epsilon,\delta)$-DP.
Notice that proving that the mechanisms
$(\widetilde{\Lambda}_{k,h})_{k\in[K]}$ and $(\widetilde{u}_{k,h})_{k\in[K]}$
are
$\left(\frac{\epsilon}{2\sqrt{8H\log\left(\frac{4}{\delta}\right)}},\frac{\delta}{4H}\right)$-DP
for each $h\in[H]$ imply by advanced composition (see App. F.6) that
$(\widetilde{\Lambda}_{k,h})_{(k,h)\in[K]\times[H]}$ and
$(\widetilde{u}_{k,h})_{(k,h)\in[K]\times[H]}$ are individually
$\left(\frac{\epsilon}{2},\frac{\delta}{2}\right)$-DP, a final application of
simple composition (see App. F.5) let us conclude the initial claim.

Then, fix $h\in[H]$ and remark that the Frobenius norm
$\Big{\lVert}X_{i,h}X^{\intercal}_{i,h}\Big{\rVert}_{F}\leq H^{2}$ implying
that the $L_{2}$-sensitivity of each of these terms is bounded by $2H^{2}$. We
follow the same reasoning as in Shariff and Sheffet (2018), the tree-based
method ensures that the released matrix will be the private design matrix
$\lambda\cdot Id+\sum_{1\leq i<k}X_{i,h}X^{\intercal}_{i,h}$, plus the
deterministic matrix $2\Upsilon^{J}_{\frac{p}{6KH}}I_{d\times d}$, plus the
sum of at most $K_{0}$ matrices, each of them with gaussian entries
$\mathcal{N}(0,\sigma^{2}_{B})$.

Hence, in order to ensure
$\left(\frac{\epsilon}{2\sqrt{8H\log\left(\frac{4}{\delta}\right)}},\frac{\delta}{4H}\right)$-DP,
we need $\sigma_{B}\geq
2H^{2}\cdot\frac{16\sqrt{HK_{0}\log\left(\frac{8H}{\delta}\right)\log\left(\frac{4}{\delta}\right)}}{\epsilon}\sqrt{2\log\left(\frac{16HK_{0}}{\delta}\right)}=\frac{32H^{2}}{\epsilon}\sqrt{2HK_{0}\log\left(\frac{8H}{\delta}\right)\log\left(\frac{4}{\delta}\right)\log\left(\frac{16HK_{0}}{\delta}\right)}$
due to the design of gaussian mechanisms (see App. F.3) and remarking that the
sum of at most $K_{0}$ nodes in the tree of noises can be interpreted as the
sum of at most $K_{0}$ private mechanisms, each of them ensuring
$\left(\frac{\epsilon}{16\sqrt{HK_{0}\log\left(\frac{8H}{\delta}\right)\log\left(\frac{4}{\delta}\right)}},\frac{\delta}{8HK_{0}}\right)$-DP
and guaranteeing privacy of $k$-th prefix sum of the tree by advanced
composition.

Exactly the same argument allows to conclude that
$(\widetilde{u}_{k,h})_{k\in[K]}$ is
$\left(\frac{\epsilon}{2\sqrt{8H\log\left(\frac{4}{\delta}\right)}},\frac{\delta}{4H}\right)$-DP
for each $h\in[H]$. Again, the $L_{2}$-sensitivity of $X_{i,h}y_{i,h}$ is
bounded by $2H^{2}$. This time the released private quantities are the sum of
$\sum_{1\leq i<k}X_{i,h}y_{i,h}$, plus the sum of at most $K_{0}$ matrices,
each of them with gaussian entries $\mathcal{N}(0,\sigma^{2}_{B})$. Due to the
design of gaussian mechanisms, we need $\sigma_{B}\geq
2H^{2}\cdot\frac{16\sqrt{HK_{0}\log\left(\frac{8H}{\delta}\right)\log\left(\frac{4}{\delta}\right)}}{\epsilon}\sqrt{2\log\left(\frac{16HK_{0}}{\delta}\right)}=\frac{32H^{2}}{\epsilon}\sqrt{2HK_{0}\log\left(\frac{8H}{\delta}\right)\log\left(\frac{4}{\delta}\right)\log\left(\frac{16HK_{0}}{\delta}\right)}$,
which is again true due to the choice of $\sigma_{B}$.

As stated at the beginning, we conclude that
$(\widetilde{\Lambda}_{k,h},\widetilde{u}_{k,h})_{(k,h)\in[K]\times[H]}$ is
$(\epsilon,\delta)$-DP. By the post-processing property (see App. F.1), it
follows that
$(\widetilde{\Lambda}_{k,h},\widetilde{w}_{k,h})_{(k,h)\in[K]\times[H]}$ is
$(\epsilon,\delta)$-DP since
$\widetilde{w}_{k,h}=\widetilde{\Lambda}^{-1}_{k,h}\cdot\widetilde{u}_{k,h}$.
A similar argument to the one in Vietri et al. (2020) allows to conclude that
Alg. 1 is $(\epsilon,\delta)$-JDP. Notice that $\widetilde{Q}_{k,h}$ is a
function of the mechanism
$(\widetilde{\Lambda}_{k,h},\widetilde{w}_{k,h})_{k,h}$. In particular, the
policy $\pi_{k}$ is also a function of the same mechanism and user’s private
data (trajectories), therefore, by the Billboard Lemma (see App. F.7), we
conclude that Alg. 1 is $(\epsilon,\delta)$-JDP.

####  C.3 Proof of Cor. 6

###### Regret analysis:

Due to Clm. 26, the eigenvalues of $B_{k,h}=\left(\sum_{1\leq i\leq
k}B^{1}_{i,h}\right)+2\Upsilon^{L}_{\frac{p}{4KH}}$ are in the interval
$\left[\Upsilon^{L}_{\frac{p}{6KH}},3\Upsilon^{L}_{\frac{p}{6KH}}\right]$ with
probability at least $1-\frac{p}{6KH}$ for each $(k,h)\in[K]\times[H]$ since
each of the matrices $B^{1}_{k,h}$ has gaussian entries
$\mathcal{N}(0,\sigma^{2}_{B})$. Similarly, due to Clm. 27, for each
$(k,h)\in[K]\times[H]$, $g_{i,h}=\left(\sum_{1\leq i\leq k}g^{1}_{i,h}\right)$
is in the interval $\left[-C^{L}_{\frac{p}{6KH}},C^{L}_{\frac{p}{6KH}}\right]$
with probability at least $1-\frac{p}{6KH}$, where
$C^{L}_{\frac{p}{6KH}}=\sigma_{B}\sqrt{K}\left(\sqrt{d}+2\sqrt{\log\left(\frac{6KH}{p}\right)}\right)$.

In the union event, with probability at least $1-\frac{p}{3}$, the eigenvalues
of $B_{k,h}$ are in the interval
$\left[\Upsilon^{k}_{low},\Upsilon^{k}_{up}\right]$ with
$\Upsilon^{k}_{low}=\Upsilon^{L}_{\frac{p}{4KH}}$,
$\Upsilon^{k}_{high}=3\Upsilon^{L}_{\frac{p}{4KH}}$
$\forall(k,h)\in[K]\times[H]$. Also, $\Big{\lVert}g_{k,h}\Big{\rVert}\leq
C_{k}$, where $C_{k}=C^{L}_{\frac{p}{6KH}}$ $\forall(k,h)\in[K]\times[H]$.

The choice of
$\beta_{k}=3(C_{w}+1)\sqrt{\lambda+\Upsilon^{L}_{\frac{p}{6KH}}}+\sqrt{2H^{2}\log\left(\frac{3H\cdot\left(1+KH\right)^{\frac{d}{2}}}{p}\right)}$
is a constant sequence (independent of $k$) and hence, non-decreasing
satisfying that

$\displaystyle\beta_{k}$
$\displaystyle\geq\frac{\left(\lambda+3\Upsilon^{L}_{\frac{p}{6KH}}\right)C_{w}+C^{L}_{\frac{p}{6KH}}}{\sqrt{\lambda+\Upsilon^{L}_{\frac{p}{6KH}}}}+\sqrt{2H^{2}\log\left(\frac{3H\left(1+KH\right)^{\frac{d}{2}}}{p}\right)}$
$\displaystyle\geq\frac{(\lambda+\Upsilon^{k}_{high})C_{w}+C_{k}}{\sqrt{\lambda+\Upsilon^{k}_{low}}}+\sqrt{2H^{2}\log\left(\frac{3H\left(1+KH\right)^{\frac{d}{2}}}{p}\right)}$

since $\Upsilon^{L}_{\frac{p}{6KH}}\geq C^{L}_{\frac{p}{6KH}}$. The regret
bound just follows from Thm. 7 by replacing
$\beta_{k}=3(C_{w}+1)\sqrt{\lambda+\Upsilon^{L}_{\frac{p}{6KH}}}+\sqrt{2H^{2}\log\left(\frac{3H\cdot\left(1+KH\right)^{\frac{d}{2}}}{p}\right)}=\widetilde{O}\left((C_{w}+1)d^{\frac{1}{4}}H^{\frac{3}{2}}K^{\frac{1}{4}}\frac{1}{\sqrt{\epsilon}}+H\sqrt{d}\right)$.

###### Privacy analysis:

The procedure is similar to the one explained in (Zheng et al., 2020), since
we aim to ensure that Alg. 1 is $(\epsilon,\delta)$-LDP, we need to show that
the mechanism
$\left(X_{k,h}X^{\intercal}_{k,h}+B^{1}_{k,h},X_{k,h}y_{k,h}+g^{1}_{k,h}\right)_{h\in[H]}$
is $(\epsilon,\delta)$-LDP for any fixed $k\in[K]$. To that end, we show that
each of the mechanisms $\left(X_{k,h}X^{\intercal}_{k,h}+B^{1}_{k,h}\right)$
and $(X_{k,h}y_{k,h}+g^{1}_{k,h})$ is
$\left(\frac{\epsilon}{2H},\frac{\delta}{2H}\right)$-LDP for each $h\in[H]$
and then conclude by simple composition of $H$ independent mechanisms.
Finally, we know that gaussian mechanisms (see App. F.3) can ensure local
privacy for appropriate variances depending on the sensitivity of the private
quantity, in this case, given that
$\Big{\lVert}X_{k,h}X^{\intercal}_{k,h}\Big{\rVert}_{F},\Big{\lVert}X_{k,h}y_{k,h}\Big{\rVert}_{2}\leq
H^{2}$, it is enough with $\sigma_{B}\geq
2H^{2}\cdot\frac{2H}{\epsilon}\cdot\sqrt{2\log\left(\frac{4H}{\delta}\right)}=\frac{4H^{3}}{\epsilon}\sqrt{2\log\left(\frac{4H}{\delta}\right)}$.
Given that $\sigma_{B}$ is precisely chosen in this way, the proof is
complete.

####  C.4 Pure DP in the UCRL-VTR Framework

It is worthwhile to notice that even if all of our results (Cor. 5, Cor 6,
Thm. 8, Cor. 10 and Cor. 11) ensure approximate joint/local DP, they can be
slighlty modified to also guarantee pure DP.
In this section, we will focus on the results presented for the Linear Mixture
Setting (Cor. 5 and 6) for the ease of comprenhension.

The regrets in both corollaries are consequences of Thm. 7 and the main
difference is in the value of $\beta_{K}$.

  * •

Cor. 5 (approximate JDP guarantees):
$\beta_{K}=\widetilde{O}\left((C_{w}+1)d^{\frac{1}{4}}H^{\frac{5}{4}}\cdot\frac{1}{\sqrt{\epsilon}}+H\sqrt{d}\right)$

  * •

Cor. 6 (approximate LDP guarantees):
$\beta_{K}=\widetilde{O}\left((C_{w}+1)d^{\frac{1}{4}}H^{\frac{3}{2}}K^{\frac{1}{4}}\cdot\frac{1}{\sqrt{\epsilon}}+H\sqrt{d}\right)$

As it can be noticed, if we dismiss the second term $H\sqrt{d}$ coming from
the self-normalized bound inequality, the gap between both values of
$\beta_{K}$ is $H^{\frac{1}{4}}K^{\frac{1}{4}}$. The term $H^{\frac{1}{4}}$ is
proper from the additional difficulty of ensuring $(\epsilon,\delta)$-LDP,
where we rely on simple composition of gaussian mechanisms and hence, we need
to prove that each of the terms $X_{k,h}X^{\intercal}_{k,h},X_{k,h}y_{k,h}$
for each $h\in[H]$ is $(\epsilon/H,\delta/H)$-LDP. On the other hand, proving
JDP only requires to show that $X_{k,h}X^{\intercal}_{k,h},X_{k,h}y_{k,h}$ are
$\approx(\epsilon/\sqrt{H},\delta/H)$-DP since we are able to apply the
advanced composition theorem (available for DP, but not for LDP).

The $\sqrt{H}$ gap on the level of privacy for $X_{k,h}X^{\intercal}_{k,h}$
and $X_{k,h}y_{k,h}$ becomes a $\sqrt{H}$ gap in the variance $\sigma_{B}$ and
given that $\beta_{K}$ scales with $\sqrt{\sigma_{B}}$, we have the
$H^{\frac{1}{4}}$ gap in the results above.

In the pure DP case, we do not apply the advanced composition theorem even for
JDP guarantees since advanced composition theorem always yields approximate DP
only. Hence, we need to use the simple composition theorem and as explained
before, it increases the variance $\sigma_{B}$ of the noises injected by
$\sqrt{H}$. Remark that it does not affect the reasoning to achieve LDP
guarantees since we were already applying the simple composition for gaussian
mechanisms.

The composition of mechanisms alone is not enough ensure pure DP guarantees,
we also need to change gaussian noises to laplace noises (see App. F.3 and
F.2). This change is reflected on the eigenvalues of the random matrix with
gaussian (laplace) entries that can be bounded this time only by
$\widetilde{\Theta}(d)$ instead of $\widetilde{\Theta}(\sqrt{d})$ (see Clms.
26 and 29).

Thus, we can conclude that after changing gaussian by laplace noises and
increasing the variance by $\approx\sqrt{H}$, the new regret bounds
$R(K)=\widetilde{O}\left(Hd^{\frac{1}{2}}\beta_{K}+H^{\frac{3}{2}}\right)K^{\frac{1}{2}}$
would be:

  * •

Cor. 5 (pure JDP guarantees):
$\beta_{K}=\widetilde{O}\left(\max\left\\{H\sqrt{d},(C_{w}+1)\sqrt{\Upsilon^{J}_{\frac{p}{6KHd}}}\right\\}\right)$,
since $\Upsilon^{J}_{\frac{p}{6KHd}}$ is the upper bound of the absolute value
of the eigenvalues of a random matrix with laplace entries, we have
$\Upsilon^{J}_{\frac{p}{6KHd}}=\widetilde{O}\left(d\sigma_{B}\right)$, where
$\sigma_{B}$ is $\approx\sqrt{H}$ times its counterpart in Cor. 5. It makes
$\beta_{K}=\widetilde{O}\left(H\sqrt{d}+(C_{w}+1)\cdot
d^{\frac{1}{2}}H^{\frac{3}{2}}/\sqrt{\epsilon}\right)$ and the corresponding
regret
$R(K)=\widetilde{O}\left(\left(H^{2}d+(C_{w}+1)H^{\frac{5}{2}}d/\sqrt{\epsilon}\right)\sqrt{K}\right)$.

  * •

Cor. 6 (pure LDP guarantees):
$\beta_{K}=\widetilde{O}\left(\max\left\\{H\sqrt{d},(C_{w}+1)\sqrt{\Upsilon^{L}_{\frac{p}{6KHd}}}\right\\}\right)$
and we have
$\Upsilon^{L}_{\frac{p}{6KHd}}=\widetilde{O}\left(d\sigma_{B}\sqrt{K}\right)$,
where $\sigma_{B}$ is of the same order as the one in Cor. 6, since we did not
use the advanced composition theorem. Hence,
$\beta_{K}=\widetilde{O}\left(H\sqrt{d}+(C_{w}+1)\cdot
d^{\frac{1}{2}}H^{\frac{3}{2}}K^{\frac{1}{4}}/\sqrt{\epsilon}\right)$ and
$R(K)=\widetilde{O}\left(H^{2}d\sqrt{K}+(C_{w}+1)H^{\frac{5}{2}}dK^{\frac{3}{4}}/\sqrt{\epsilon}\right)$.

###  Appendix D Analysis of privacy-preserving UCRL-VTR+

Input : episodes $K$, horizon $H$, ambient dimension $d$, privacy parameters
$\epsilon,\delta$, failure probability $p$, bound $C_{w}$

Initialize $\lambda=1$, and $\forall h\in[H]$,
$\widehat{\Lambda}_{1,h}=\widetilde{\Lambda}_{1,h}=\lambda\cdot I_{d\times
d}$, $\widehat{u}_{1,h}=\widetilde{u}_{1,h}=0_{d}$,
$\widehat{w}_{1,h}=\widetilde{w}_{1,h}=0_{d}$

Initialize $\widehat{\beta}_{k},\check{\beta}_{k}$ and $\widetilde{\beta}_{k}$
satisfying (5) $\forall k\in[K]$, e.g. as defined in (6) or (7) for JDP or LDP
guarantees

for  _$k=1,\dots,K$_ do

// User’s side

Receive $\widehat{w}_{k,h},\widetilde{w}_{k,h},\widehat{\Lambda}_{k,h}$ and
$\widetilde{\Lambda}_{k,h}$

for  _$h=1,\dots,H$_ do

Observe $s^{k}_{h}$

Choose action $a^{k}_{h}=\operatorname*{arg\,max}_{a\in
A}\widehat{Q}_{k,h}(s^{k}_{h},a)$

$\widehat{Q}_{k,h}(\cdot,\cdot)=\min\left\\{H,r_{h}(\cdot,\cdot)+\langle\phi_{\widehat{V}_{k,h+1}}(\cdot,\cdot),\widehat{w}_{k,h}\rangle+\widehat{\beta}_{k}\Big{\lVert}\phi_{\widehat{V}_{k,h+1}}(\cdot,\cdot)\Big{\rVert}_{(\widehat{\Lambda}_{k,h})^{-1}}\right\\}$

$\widehat{V}_{k,h}(\cdot,\cdot)=\max_{a\in A}\widehat{Q}_{k,h}(\cdot,a)$

end for

for  _$h=1,\dots,H$_ do

$\bar{\mathbb{V}}_{k,h}\widehat{V}_{k,h+1}(s^{k}_{h},a^{k}_{h})=\left[\Big{\langle}\phi_{\widehat{V}^{2}_{k,h+1}}(s^{k}_{h},a^{k}_{h}),\widetilde{w}_{k,h}\Big{\rangle}\right]_{[0,H^{2}]}-\left[\Big{\langle}\phi_{\widehat{V}_{k,h+1}}(s^{k}_{h},a^{k}_{h}),\widehat{w}_{k,h}\Big{\rangle}\right]^{2}_{[0,H]}$

$E_{k,h}=\min\left\\{H^{2},2H\check{\beta}_{k}\Big{\lVert}\left(\widehat{\Lambda}_{k,h}\right)^{-\frac{1}{2}}\cdot\phi_{\widehat{V}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\Big{\rVert}_{2}\right\\}+\min\left\\{H^{2},\widetilde{\beta}_{k}\Big{\lVert}\left(\widetilde{\Lambda}_{k,h}\right)^{-\frac{1}{2}}\cdot\phi_{\widetilde{V}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\Big{\rVert}_{2}\right\\}$

$\bar{\sigma}_{k,h}=\left(\max\left\\{H^{2}/d,\left[\bar{\mathbb{V}}_{k,h}\widehat{V}_{k,h+1}(s^{k}_{h},a^{k}_{h})+E_{k,h}\right]\right\\}\right)^{1/2}$

end for

Send
$\left\\{\bar{\sigma}^{-2}_{k,h}\cdot\phi_{\widehat{V}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\phi^{\intercal}_{\widehat{V}_{k,h+1}}(s^{k}_{h},a^{k}_{h})+B^{1}_{k,h}\right\\}_{h\in[H]}$,$\left\\{\bar{\sigma}^{-2}_{k,h}\phi_{\widehat{V}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\widehat{V}_{k,h+1}(s^{k}_{h+1})+f^{1}_{k,h}\right\\}_{h\in[H]}$,

$\left\\{\phi_{\widehat{V}^{2}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\phi^{\intercal}_{\widehat{V}^{2}_{k,h+1}}(s^{k}_{h},a^{k}_{h})+B^{2}_{k,h}\right\\}_{h\in[H]}$,
$\left\\{\phi_{\widehat{V}^{2}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\widehat{V}^{2}_{k,h+1}(s^{k}_{h+1})+g^{1}_{k,h}\right\\}_{h\in[H]}$

// Server’s side (i.e., algorithm)

Update design matrix and target $\forall h\in[H]$

for  _$h=1,\dots,H$_ do

$D^{1}_{k,h}=\left(\sum_{1\leq i\leq k}B^{1}_{i,h}\right)+B^{3}_{k,h}$

$D^{2}_{k,h}=\left(\sum_{1\leq i\leq k}B^{2}_{i,h}\right)+B^{4}_{k,h}$

$f_{k,h}=\left(\sum_{1\leq i\leq k}f^{1}_{i,h}\right)+f^{2}_{k,h}$

$g_{k,h}=\left(\sum_{1\leq i\leq k}g^{1}_{i,h}\right)+g^{2}_{k,h}$

$\widehat{\Lambda}_{k+1,h}=\lambda\cdot Id+\sum_{1\leq i\leq
k}\bar{\sigma}^{-2}_{i,h}\phi_{\widehat{V}_{i,h+1}}(s^{i}_{h},a^{i}_{h})\phi^{\intercal}_{\widehat{V}_{i,h+1}}(s^{i}_{h},a^{i}_{h})+D^{1}_{k,h}$

$\widetilde{\Lambda}_{k+1,h}=\lambda\cdot Id+\sum_{1\leq i\leq
k}\phi_{\widehat{V}^{2}_{i,h+1}}(s^{i}_{h},a^{i}_{h})\phi^{\intercal}_{\widehat{V}^{2}_{i,h+1}}(s^{i}_{h},a^{i}_{h})+D^{2}_{k,h}$

$\widehat{u}_{k+1,h}=\sum_{1\leq i\leq
k}\bar{\sigma}^{-2}_{i,h}\phi_{\widehat{V}_{i,h+1}}(s^{i}_{h},a^{i}_{h})\widehat{V}_{i,h+1}(s^{i}_{h+1})+f_{k,h}$

$\widetilde{u}_{k+1,h}=\sum_{1\leq i\leq
k}\phi_{\widehat{V}^{2}_{i,h+1}}(s^{i}_{h},a^{i}_{h})\widehat{V}^{2}_{i,h+1}(s^{i}_{h+1})+g_{k,h}$

$\widehat{w}_{k+1,h}=\left(\widehat{\Lambda}_{k+1,h}\right)^{-1}\cdot\widehat{u}_{k+1,h}$

$\widetilde{w}_{k+1,h}=\left(\widetilde{\Lambda}_{k+1,h}\right)^{-1}\cdot\widetilde{u}_{k+1,h}$

end for

end for

Algorithm 3 Privacy-Preserving UCRL-VTR+

In this section, the Privacy-Preserving UCRL-VTR+ algorithm (Alg. 3) is
presented, a framework inspired in UCRL-VTR+ also taking the second moment
covariance matrix and response vector of the value function into account.

######  Theorem 9 (Regret bound of Alg. 3).

Assume that the following hypothesis hold with probability at least
$1-\frac{p}{6}$:

  1. 1.

There exist two sequences of non-negative real numbers
$(\Upsilon^{k}_{1,low})_{k}$ and $(\Upsilon^{k}_{1,high})_{k}$ such that all
the eigenvalues of $D^{1}_{k,h}$ belong to
$[\Upsilon^{k}_{1,low},\Upsilon^{k}_{1,high}]$ $\forall h\in[H]$.

  2. 2.

There exist two sequences of non-negative real numbers
$(\Upsilon^{k}_{2,low})_{k}$ and $(\Upsilon^{k}_{2,high})_{k}$ such that all
the eigenvalues of $D^{2}_{k,h}$ belong to
$[\Upsilon^{k}_{2,low},\Upsilon^{k}_{2,high}]$ $\forall h\in[H]$.

  3. 3.

There exists a sequence $(C_{1,k})_{k}$ such that
$\Big{\lVert}f_{k,h}\Big{\rVert}_{2}\leq C_{1,k}$ $\forall h\in[H]$.

  4. 4.

There exists a sequence $(C_{2,k})_{k}$ such that
$\Big{\lVert}g_{k,h}\Big{\rVert}_{2}\leq C_{2,k}$ $\forall h\in[H]$.

  5. 5.

$\widehat{\beta}_{k},\widetilde{\beta}_{k},\check{\beta}_{k}$ are non-
decreasing sequences satisfying the following inequalities:

$\displaystyle\check{\beta}_{k}\geq\frac{C_{w}\left(\lambda+\Upsilon^{k}_{1,high}\right)+C_{1,k}}{\sqrt{\lambda+\Upsilon^{k}_{1,low}}}+8d\sqrt{\log\left(1+\frac{K}{\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right)$
(5)
$\displaystyle\widehat{\beta}_{k}\geq\frac{C_{w}\left(\lambda+\Upsilon^{k}_{1,high}\right)+C_{1,k}}{\sqrt{\lambda+\Upsilon^{k}_{1,low}}}+8\sqrt{d\log\left(1+\frac{K}{\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right)$
$\displaystyle\widetilde{\beta}_{k}\geq\frac{C_{w}\left(\lambda+\Upsilon^{k}_{2,high}\right)+C_{2,k}}{\sqrt{\lambda+\Upsilon^{k}_{2,low}}}+8\sqrt{dH^{4}\log\left(1+\frac{KH^{4}}{d\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4H^{2}\log\left(\frac{24k^{2}H}{p}\right)$

Then, for any $p\in(0,1)$, with probability at least $1-p$, the regret of Alg.
3 is bounded as follows:

$R(K)=\widetilde{O}\left(H^{\frac{1}{2}}d^{\frac{1}{2}}\widehat{\beta}_{K}\left(\max\left\\{H^{\frac{5}{2}}d^{\frac{1}{2}}\widehat{\beta}_{K},H^{\frac{7}{4}}K^{\frac{1}{4}},\frac{H^{\frac{3}{2}}K^{\frac{1}{2}}}{d^{\frac{1}{2}}},HK^{\frac{1}{2}},H^{\frac{1}{2}}d^{\frac{1}{4}}\sqrt{\widetilde{\beta}_{K}}K^{\frac{1}{4}},H^{\frac{3}{2}}d^{\frac{1}{4}}\sqrt{\check{\beta}_{K}}K^{\frac{1}{4}}\right\\}\right)+H^{\frac{3}{2}}K^{\frac{1}{2}}\right)$

where the $\widetilde{O}(\cdot)$ notation hides
$\log\left(\frac{1}{p}\right),\log(K)$ and $\log(H)$ factors.

######  Corollary 10 (JDP-UCRL-VTR+).

Fix any privacy level $\epsilon,\delta\in(0,1)$. Setting
$B^{1}_{k,h}=B^{2}_{k,h}=0_{d\times d}$, $f^{1}_{k,h}=g^{1}_{k,h}=0_{d}$ for
each $(k,h)\in[K]\times[H]$, while $B^{3}_{k,h},B^{4}_{k,h},f^{2}_{k,h}$ and
$g^{2}_{k,h}$ will come from 4 trees (initialized as done in the tree-based
method). More precisely, we follow a similar approach to the one of Section
4.2 in Shariff and Sheffet (2018). Indeed, we instantiate 4H trees, each with
K leaves (2K nodes), the first $H$ of them contain symmetric matrices
$Z_{1}=(Z^{\prime}_{1}+Z^{\prime\intercal}_{1})/\sqrt{2}$, where
$Z^{\prime}_{1}\in\mathbb{R}^{d\times d}$ and each of its entries follow a
gaussian distribution $\mathcal{N}(0,\sigma^{2}_{B,1})$ with
$\sigma_{B,1}=\frac{64d}{\epsilon}\sqrt{2HK_{0}\log\left(\frac{16H}{\delta}\right)\log\left(\frac{8}{\delta}\right)\log\left(\frac{32HK_{0}}{\delta}\right)}$and
$K_{0}=\lceil\log_{2}(K)+1\rceil$, the next $H$ of them contain a
$d$-dimensional vector following a gaussian distribution
$\mathcal{N}(0,\sigma^{2}_{B,1}I_{d\times d})$, the next H of them contain
symmetric matrices $Z_{2}=(Z^{\prime}_{2}+Z^{\prime\intercal}_{2})/\sqrt{2}$,
where $Z^{\prime}_{2}\in\mathbb{R}^{d\times d}$ and each of its entries follow
a gaussian distribution $\mathcal{N}(0,\sigma^{2}_{B,2})$ with
$\sigma_{B,2}=\frac{64H^{4}}{\epsilon}\sqrt{2HK_{0}\log\left(\frac{16H}{\delta}\right)\log\left(\frac{8}{\delta}\right)\log\left(\frac{32HK_{0}}{\delta}\right)}$,
finally the last $H$ trees contain a $d$-dimensional vector following a
gaussian distribution $\mathcal{N}(0,\sigma^{2}_{B,2}I_{d\times d})$.
We then set $B^{3}_{k,h}$ as the sum of the $k$-th prefix in the $h$-th tree
(of those instantiated with gaussian entries
$\mathcal{N}(0,\sigma^{2}_{B,1})$) shifted by
$2\Upsilon^{J,1}_{\frac{p}{24KH}}I_{d\times d}$, where
$\Upsilon^{J,1}_{\frac{p}{24KH}}=\sigma_{B,1}\sqrt{K_{0}}\left(4\sqrt{d}+2\log\left(\frac{24KH}{p}\right)\right)$.
In the same way, $B^{4}_{k,h}$ is set to the sum of the $k$-th prefix in the
$h$-th tree (of those instantiated with gaussian entries
$\mathcal{N}(0,\sigma^{2}_{B,2})$) shifted by
$2\Upsilon^{J,2}_{\frac{p}{24KH}}I_{d\times d}$, where
$\Upsilon^{J,2}_{\frac{p}{24KH}}=\sigma_{B,2}\sqrt{K_{0}}\left(4\sqrt{d}+2\log\left(\frac{24KH}{p}\right)\right)$.
Finally, we set $f^{2}_{k,h}$ as the $k$-th prefix in the $h$-th tree (of
those instantiated with $\mathcal{N}(0,\sigma^{2}_{B,1}I_{d\times d})$) and
$g^{2}_{k,h}$ as the $k$-th prefix in the $h$-th tree (of those instantiated
with $\mathcal{N}(0,\sigma^{2}_{B,2}I_{d\times d})$).
Then, choosing $\check{\beta}_{k},\widehat{\beta}_{k},\widetilde{\beta}_{k}$
as follows:

$\displaystyle\check{\beta}_{k}=3(C_{w}+1)\sqrt{\lambda+\Upsilon^{J,1}_{\frac{p}{24KH}}}+8d\sqrt{\log\left(1+\frac{K}{\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right)$
(6)
$\displaystyle\widehat{\beta}_{k}=3(C_{w}+1)\sqrt{\lambda+\Upsilon^{J,1}_{\frac{p}{24KH}}}+8\sqrt{d\log\left(1+\frac{K}{\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right)$
$\displaystyle\widetilde{\beta}_{k}=3(C_{w}+1)\sqrt{\lambda+\Upsilon^{J,2}_{\frac{p}{24KH}}}+8\sqrt{dH^{4}\log\left(1+\frac{KH^{4}}{d\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4H^{2}\log\left(\frac{24k^{2}H}{p}\right)$

Alg. 3 is $(\epsilon,\delta)$-JDP and with probability at least $1-p$, its
regret is bounded as follows:

$R(K)=\widetilde{O}\left((C_{w}+1)^{2}\frac{H^{\frac{7}{2}}d^{\frac{5}{2}}}{\epsilon}+\frac{(C_{w}+1)}{\sqrt{\epsilon}}\cdot\left(\left(H^{\frac{5}{2}}d^{\frac{5}{4}}+H^{\frac{9}{4}}d^{2}\right)K^{\frac{1}{4}}+\left(H^{\frac{7}{4}}d^{\frac{5}{4}}+H^{\frac{9}{4}}d^{\frac{3}{4}}\right)K^{\frac{1}{2}}\right)\right)$

where the $\widetilde{O}(\cdot)$ notation hides
polylog$\left(\frac{1}{p},\frac{1}{\delta},H,K\right)$ factors.

######  Corollary 11 (LDP-UCRL-VTR+).

Fix any privacy level $\epsilon,\delta\in(0,1)$. Setting
$B^{3}_{k,h}=2\Upsilon^{L,1}_{\frac{p}{24KH}}\cdot I_{d\times
d},B^{4}_{k,h}=2\Upsilon^{L,2}_{\frac{p}{24KH}}\cdot I_{d\times d}$ for each
$(k,h)\in[K]\times[H]$ and $B^{1}_{k,h},B^{2}_{k,h},f^{1}_{k,h}$,
$g^{1}_{k,h}$ will be gaussian mechanism (see App. F.3), where
$\sigma_{B,1}=\frac{8dH}{\epsilon}\sqrt{2\log\left(\frac{8H}{\delta}\right)},\Upsilon^{L,1}_{\frac{p}{24KH}}=\sigma_{B,1}\sqrt{K}\left(4\sqrt{d}+2\log\left(\frac{24KH}{p}\right)\right)$,
$\sigma_{B,2}=\frac{8H^{5}}{\epsilon}\sqrt{2\log\left(\frac{8H}{\delta}\right)}$
and
$\Upsilon^{L,2}_{\frac{p}{24KH}}=\sigma_{B,2}\sqrt{K}\left(4\sqrt{d}+2\log\left(\frac{24KH}{p}\right)\right)$.
Indeed, $B^{1}_{k,h}$ is a $d\times d$ matrix with each of its entries drawn
from $\mathcal{N}(0,\sigma^{2}_{B,1})$. In the same way, $B^{2}_{k,h}$ is a
$d\times d$ matrix with each of its entries drawn from
$\mathcal{N}(0,\sigma^{2}_{B,2})$. Similarly, $f^{1}_{k,h}$ and $g^{1}_{k,h}$
are drawn from $\mathcal{N}(0,\sigma^{2}_{B,1}I_{d\times d})$ and
$\mathcal{N}(0,\sigma^{2}_{B,2}I_{d\times d})$ respectively.
Then, choosing $\check{\beta}_{k},\widehat{\beta}_{k},\widetilde{\beta}_{k}$
as follows:

$\displaystyle\check{\beta}_{k}=3(C_{w}+1)\sqrt{\lambda+\Upsilon^{L,1}_{\frac{p}{24KH}}}+8d\sqrt{\log\left(1+\frac{K}{\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right)$
(7)
$\displaystyle\widehat{\beta}_{k}=3(C_{w}+1)\sqrt{\lambda+\Upsilon^{L,1}_{\frac{p}{24KH}}}+8\sqrt{d\log\left(1+\frac{K}{\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right)$
$\displaystyle\widetilde{\beta}_{k}=3(C_{w}+1)\sqrt{\lambda+\Upsilon^{L,2}_{\frac{p}{24KH}}}+8\sqrt{dH^{4}\log\left(1+\frac{KH^{4}}{d\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4H^{2}\log\left(\frac{24k^{2}H}{p}\right)$

Alg. 3 is $(\epsilon,\delta)$-LDP and with probability at least $1-p$, its
regret is bounded as follows:

$R(K)=\widetilde{O}\left(\frac{(C_{w}+1)^{2}}{\epsilon}\cdot
H^{4}d^{\frac{5}{2}}K^{\frac{1}{2}}+\frac{(C_{w}+1)}{\sqrt{\epsilon}}\left(H^{\frac{11}{4}}d^{\frac{5}{4}}+H^{\frac{5}{2}}d^{2}\right)K^{\frac{1}{2}}+\frac{(C_{w}+1)}{\sqrt{\epsilon}}\left(H^{2}d^{\frac{5}{4}}+H^{\frac{5}{2}}d^{\frac{3}{4}}\right)K^{\frac{3}{4}}\right)$

where the $\widetilde{O}(\cdot)$ notation hides
polylog$\left(\frac{1}{p},\frac{1}{\delta},H,K\right)$ factors.

######  Remark 6.

As pointed out in the case of the UCRL-VTR Framework (Alg. 1), we can also
ensure pure DP instead of approximate DP by replacing each gaussian mechanism
in Alg. 3 by a Laplace mehcanism and increasing the variance roughly by a
factor $\sqrt{H}$. On the other hand, the most interesting result here is that
the regret bounds obtained for the private version of UCRL-VTR+ are not
asymptotically better than the ones of UCRL-VTR. We believe that the main
reason is that in difference to the non-private versions of both algorithms,
the dominant term in the size of the confidence sets comes from the noise
added and it is then of the same order for both of our algorithms (no
improvement in the size of the confidence set).

####  D.1 Privacy Preserving UCRL-VTR vs UCRL-VTR+

Thms. 7 and 9 offer two ways to bound the regret of privacy-preserving
algorithms in the Linear-Mixture setting.

Let’s take a step back and consider the non-private versions of Algs. 1 and 3,
i.e. all the tuning vectors/matrices equal to 0.

It is very well known that in this case, UCRL-VTR+ (Alg. 3) manages to improve
the regret of UCRL-VTR (Alg. 1) by a factor of $\sqrt{H}$ in the regime $d\geq
H$ leveraging the usage of Bernstein-type concentration inequalities instead
of Hoeffding inequalities. This improvement can be perceived through our
results in the following way:

  * •

Thm. 1: $R_{UCRL-
VTR}(K)\approx\widetilde{O}\left(Hd^{\frac{1}{2}}\beta_{K}\cdot
K^{\frac{1}{2}}\right)$

  * •

Thm. 3: $R_{UCRL-
VTR+}(K)\approx\widetilde{O}\left(H^{\frac{1}{2}}d^{\frac{1}{2}}\widehat{\beta}_{K}\cdot\left(H+\frac{H^{\frac{3}{2}}}{d^{\frac{1}{2}}}\right)K^{\frac{1}{2}}\right)=\widetilde{O}\left(H^{\frac{3}{2}}d^{\frac{1}{2}}\widehat{\beta}_{K}K^{\frac{1}{2}}\right)$
in the regime $d\geq H$

It suffices to observe that $\beta_{K}=\widetilde{\Theta}(H\sqrt{d})$ and
$\widehat{\beta}_{K}=\widetilde{\Theta}(\sqrt{d})$ and hence, a simple
comparison of the expressions above already reflects the $\sqrt{H}$ gap
between their regrets in favor of UCRL-VTR+.

Consider now the private case and more particularly, the results provided in
Cor. 5/ Cor. 10 for joint DP guarantees and Cor. 6/Cor. 11 for local DP
guarantees. Moreover, for ease of simplicity, consider the former case, since
the comparison in the latter scenario is fairly similar.

Indeed, in this case, the size of the confidence sets can be decomposed in two
terms, one coming from the noise added to ensure privacy, while the other one
is inherent to the type of concentration inequality used to build the
intervals:

$\beta_{K}=\underbrace{3(C_{w}+1)\sqrt{\lambda+\Upsilon^{J}_{\frac{p}{6KH}}}}_{\text{1st:
Due to the
noise}}+\underbrace{\sqrt{2H^{2}\log\left(\frac{3H\cdot(1+KH)^{\frac{d}{2}}}{p}\right)}}_{\text{2nd:
Hoeffding's inequality}}$
$\widehat{\beta}_{k}=\underbrace{3(C_{w}+1)\sqrt{\lambda+\Upsilon^{J,1}_{\frac{p}{24KH}}}}_{\text{1st:
Due to the
noise}}+\underbrace{8\sqrt{d\log\left(1+\frac{K}{\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right)}_{\text{2nd:
Bernstein's inequality}}$

Notice that in the non-private case, where
$\Upsilon^{J}_{\frac{p}{6KH}}=0,\Upsilon^{J,1}_{\frac{p}{24KH}}=0$, the 2nd
term of both expressions are dominant with respect to the 1st one. However, in
the private case, the noise produces the reverse effect of making the 1st term
(in the past a low-order term) now comparable to (or greater than) the 2nd
term.

In the JDP setting,

$\beta_{K}=\widetilde{O}\left((C_{w}+1)\cdot\sqrt{\sigma_{B}}\cdot
d^{\frac{1}{4}}+H\sqrt{d}\right)=\widetilde{O}\left((C_{w}+1)\cdot
d^{\frac{1}{4}}H^{\frac{5}{4}}\cdot\frac{1}{\sqrt{\epsilon}}+H\sqrt{d}\right)$
$\widehat{\beta}_{K}=\widetilde{O}\left((C_{w}+1)\cdot\sqrt{\sigma_{B,1}}\cdot
d^{\frac{1}{4}}+\sqrt{d}\right)=\widetilde{O}\left((C_{w}+1)\cdot
d^{\frac{3}{4}}H^{\frac{1}{4}}\cdot\frac{1}{\sqrt{\epsilon}}\right)$

Therefore, the regrets of Algs. 1 and 3 will be:

  * •

Cor. 5: $R_{UCRL-VTR}(K)=\widetilde{O}\left(\left((C_{w}+1)\cdot
d^{\frac{3}{4}}H^{\frac{9}{4}}\cdot\frac{1}{\sqrt{\epsilon}}+H^{2}d\right)K^{\frac{1}{2}}\right)$

  * •

Cor. 10: $R_{UCRL-
VTR+}(K)\approx\widetilde{O}\left(\frac{(C_{w}+1)}{\sqrt{\epsilon}}\cdot\left(d^{\frac{5}{4}}H^{\frac{7}{4}}+d^{\frac{3}{4}}H^{\frac{9}{4}}\right)K^{\frac{1}{2}}\right)$

Noticing that
$\frac{(C_{w}+1)}{\sqrt{\epsilon}}\cdot\left(d^{\frac{5}{4}}H^{\frac{7}{4}}+d^{\frac{3}{4}}H^{\frac{9}{4}}\right)\geq
2H^{2}d$ due to AM-GM inequality and recalling that $\epsilon<1$. We can then
observe that the regret bound of Cor. 5 is in this case not better than the
one of Cor. 10.

####  D.2 Proof of Thm. 9

We follow the proof given in Zhou et al. (2021) for the non-private version of
UCRL-VTR+.

#####  D.2.1 Confidence sets

The proof proceeds as in (Zhou et al., 2021, App. C.1) and relies also in
Theorem 4.1 (Bernstein inequality for vector-valued martingales) from the same
work. The differences on the sizes of the confidence sets,
$\check{\beta}_{k},\widehat{\beta}_{k}$ and $\widetilde{\beta}_{k}$, are due
to the perturbations
$B^{1}_{k,h},B^{2}_{k,h},B^{3}_{k,h},B^{4}_{k,h},f^{1}_{k,h},f^{2}_{k,h},g^{1}_{k,h}$
and $g^{2}_{k,h}$ such as it was observed in the proof of Thm. 7.

Similarly, let $\check{\mathcal{C}}_{k,h},\widehat{\mathcal{C}}_{k,h}$ and
$\widetilde{\mathcal{C}}_{k,h}$ be the following confidence sets:

$\check{\mathcal{C}}_{k,h}=\left\\{w\in\mathbb{R}^{d}:\Big{\lVert}\widehat{\Lambda}^{\frac{1}{2}}_{k,h}\cdot\left(w-\widehat{w}_{k,h}\right)\Big{\rVert}_{2}\leq\check{\beta}_{k}\right\\}$
$\widehat{\mathcal{C}}_{k,h}=\left\\{w\in\mathbb{R}^{d}:\Big{\lVert}\widehat{\Lambda}^{\frac{1}{2}}_{k,h}\cdot\left(w-\widehat{w}_{k,h}\right)\Big{\rVert}_{2}\leq\widehat{\beta}_{k}\right\\}$
$\widetilde{\mathcal{C}}_{k,h}=\left\\{w\in\mathbb{R}^{d}:\Big{\lVert}\widetilde{\Lambda}^{\frac{1}{2}}_{k,h}\cdot\left(w-\widetilde{w}_{k,h}\right)\Big{\rVert}_{2}\leq\widetilde{\beta}_{k}\right\\}$

######  Lemma 12 (Adapted from lemma C.1 in Zhou et al. (2021)).

Let
$\widehat{V}_{k,h+1},\widehat{w}_{k,h},\widehat{\Lambda}_{k,h},\widetilde{w}_{k,h},\widetilde{\Lambda}_{k,h}$
be defined in Alg. 3, then we have

$\displaystyle\lvert\mathbb{V}_{h}\widehat{V}_{k,h+1}(s^{k}_{h},a^{k}_{h})-\bar{\mathbb{V}}_{k,h}\widehat{V}_{k,h+1}(s^{k}_{h},a^{k}_{h})\rvert\leq$
$\displaystyle\min\left\\{H^{2},\Big{\lVert}\widetilde{\Lambda}^{-\frac{1}{2}}_{k,h}\cdot\phi_{\widehat{V}^{2}_{k,h+1}}\left(s^{k}_{h},a^{k}_{h}\right)\Big{\rVert}_{2}\cdot\Big{\lVert}\widetilde{\Lambda}^{\frac{1}{2}}_{k,h}\cdot\left(\widetilde{w}_{k,h}-w_{h}\right)\Big{\rVert}_{2}\right\\}+$
$\displaystyle\min\left\\{H^{2},2H\Big{\lVert}\widehat{\Lambda}^{-\frac{1}{2}}_{k,h}\cdot\phi_{\widehat{V}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\Big{\rVert}_{2}\cdot\Big{\lVert}\widehat{\Lambda}^{\frac{1}{2}}_{k,h}\cdot\left(\widehat{w}_{k,h}-w_{h}\right)\Big{\rVert}_{2}\right\\}$

###### Proof.

The proof is the same of Lemma C.1 in Zhou et al. (2021), the only changes are
replacing
$V_{k,h+1},\widehat{\theta}_{k,h},\widehat{\Sigma}_{k,h},\widetilde{\theta}_{k,h},\widetilde{\Sigma}_{k,h}$
by
$\widehat{V}_{k,h+1},\widehat{w}_{k,h},\widehat{\Lambda}_{k,h},\widetilde{w}_{k,h},\widetilde{\Lambda}_{k,h}$.
∎

Let $\mathcal{E}_{hyp}$ be the event where the assumptions of Thm. 9 hold,
$\mathbb{P}\left(\mathcal{E}_{hyp}\right)\geq 1-\frac{p}{6}$.

From now onwards, all the results will be proved conditioned on the event
$\mathcal{E}_{hyp}$.
Fix $h\in[H]$ and apply Thm. 4.1 Zhou et al. (2021) for the following
parameters:

$\displaystyle
x_{i}=\bar{\sigma}^{-1}_{i,h}\cdot\phi_{\widehat{V}_{i,h+1}}(s^{i}_{h},a^{i}_{h}),\eta_{i}=\bar{\sigma}^{-1}_{i,h}\cdot\widehat{V}_{i,h+1}(s^{i}_{h+1})-\bar{\sigma}^{-1}_{i,h}\cdot\Big{\langle}\phi_{\widehat{V}_{i,h+1}}(s^{i}_{h},a^{i}_{h}),w_{h}\Big{\rangle}$
$\displaystyle\mathcal{G}_{i}=\sigma\left(\left\\{s^{k^{\prime}}_{h^{\prime}},a^{k^{\prime}}_{h^{\prime}},r^{k^{\prime}}_{h^{\prime}}\right\\}_{(k^{\prime},h^{\prime})\leq(k,h)}\cup\left(g^{1}_{k^{\prime},h^{\prime}},g^{2}_{k^{\prime},h^{\prime}},f^{1}_{k^{\prime},h^{\prime}},f^{2}_{k^{\prime},h^{\prime}},B^{1}_{k^{\prime},h^{\prime}},B^{3}_{k^{\prime},h^{\prime}}\right)_{(k^{\prime},h^{\prime})\leq(k,h)}\right),$
$\displaystyle\mu^{\star}=w_{h},y_{i}=\Big{\langle}\mu^{\star},x_{i}\Big{\rangle}+\eta_{i}=\bar{\sigma}^{-1}_{i,h}\cdot\widehat{V}_{i,h+1}(s^{i}_{h+1}),Z_{i}=\lambda\cdot
I_{d\times d}+\sum_{i^{\prime}=1}^{i}x_{i^{\prime}}\cdot
x^{\intercal}_{i^{\prime}}$

Since $\lVert x_{i}\rVert_{2}\leq\bar{\sigma}^{-1}_{i,h}H\leq\sqrt{d}$,
$\lvert\eta_{i}\rvert_{2}\leq\bar{\sigma}^{-1}_{i,h}H\leq\sqrt{d},\mathbb{E}\left[\eta_{i}|\mathcal{G}_{i}\right]=0,\mathbb{E}\left[\eta^{2}_{i}|\mathcal{G}_{i}\right]\leq
d$, it can be concluded that with probability at least $1-\frac{p}{6H}$,
$\forall k\leq K$:

$\Big{\lVert}\sum_{i=1}^{k}x_{i}\eta_{i}\Big{\rVert}_{Z^{-1}_{k}}\leq
8d\sqrt{\log\left(1+k/\lambda\right)\log\left(24k^{2}H/p\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right)$
(8)

Eq. 8 is used to prove that
$w_{h}\in\bigcap_{k\in[K]}\check{\mathcal{C}}_{k,h}$ with probability at least
$1-p/6H$.

$\Big{\lVert}\widehat{\Lambda}^{\frac{1}{2}}_{k,h}\cdot\left(w_{h}-\widehat{w}_{k,h}\right)\Big{\rVert}_{2}=\Big{\lVert}\widehat{\Lambda}_{k,h}\cdot\left(w_{h}-\widehat{w}_{k,h}\right)\Big{\rVert}_{\widehat{\Lambda}^{-1}_{k,h}}$
$=\Big{\lVert}\left(\lambda+D^{1}_{k-1,h}\right)w_{h}+\sum_{1\leq
i<k}\bar{\sigma}^{-2}_{i,h}\phi_{\widehat{V}_{i,h+1}}(s^{i}_{h},a^{i}_{h})\phi^{\intercal}_{\widehat{V}_{i,h+1}}(s^{i}_{h},a^{i}_{h})\cdot
w_{h}-f_{k-1,h}-\sum_{1\leq
i<k}\bar{\sigma}^{-2}_{i,h}\phi_{\widehat{V}_{i,h+1}}(s^{i}_{h},a^{i}_{h})\widehat{V}_{i,h+1}(s^{i}_{h+1})\Big{\rVert}_{\widehat{\Lambda}^{-1}_{k,h}}$
$=\Big{\lVert}\left(\lambda+D^{1}_{k-1,h}\right)w_{h}+\sum_{1\leq
i<k}x_{i}\eta_{i}-f_{k-1,h}\Big{\rVert}_{\widehat{\Lambda}^{-1}_{k,h}}\leq\Big{\lVert}\left(\lambda+D^{1}_{k-1,h}\right)w_{h}\Big{\rVert}_{\widehat{\Lambda}^{-1}_{k,h}}+\Big{\lVert}\sum_{1\leq
i<k}x_{i}\eta_{i}\Big{\rVert}_{\widehat{\Lambda}^{-1}_{k,h}}+\Big{\lVert}f_{k-1,h}\Big{\rVert}_{\widehat{\Lambda}^{-1}_{k,h}}$
$\leq\frac{C_{w}\cdot\left(\lambda+\Upsilon^{k-1}_{1,high}\right)}{\sqrt{\lambda+\Upsilon^{k-1}_{1,low}}}+\Big{\lVert}\sum_{1\leq
i<k}x_{i}\eta_{i}\Big{\rVert}_{Z^{-1}_{k-1}}+\frac{C_{1,k-1}}{\sqrt{\lambda+\Upsilon^{k-1}_{1,low}}}$

Then,

$\Big{\lVert}\widehat{\Lambda}^{\frac{1}{2}}_{k,h}\cdot\left(w_{h}-\widehat{w}_{k,h}\right)\Big{\rVert}_{2}\leq\frac{C_{w}\cdot\left(\lambda+\Upsilon^{k-1}_{1,high}\right)+C_{1,k-1}}{\sqrt{\lambda+\Upsilon^{k-1}_{1,low}}}+8d\sqrt{\log\left(1+k/\lambda\right)\log\left(24k^{2}H/p\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right)$
$\Big{\lVert}\widehat{\Lambda}^{\frac{1}{2}}_{k,h}\cdot\left(w_{h}-\widehat{w}_{k,h}\right)\Big{\rVert}_{2}\leq\check{\beta}_{k-1}\leq\check{\beta}_{k}$

It means that for a fixed $h\in[H]$,
$w_{h}\in\bigcap_{k\in[K]}\check{\mathcal{C}}_{k,h}$ with probability at least
$1-\frac{p}{6H}$.

The same reasoning can be followed with the proper changes to prove that
$w_{h}\in\bigcap_{k\in[K]}\widetilde{C}_{k,h}$ with high probability. It
suffices to notice that this time
$\eta_{i}=\phi_{\widehat{V}^{2}_{i,h+1}}(s^{i}_{h},a^{i}_{h})\cdot\widehat{V}^{2}_{i,h+1}(s^{i}_{h+1})-\Big{\langle}\phi_{\widehat{V}^{2}_{i,h+1}}(s^{i}_{h},a^{i}_{h}),w_{h}\Big{\rangle}$
is bounded by $H^{2}$ instead of $d$ and it can be similarly concluded that

$\Big{\lVert}\widetilde{\Lambda}^{\frac{1}{2}}_{k,h}\cdot\left(w_{h}-\widetilde{w}_{k,h}\right)\Big{\rVert}_{2}\leq\frac{C_{w}\cdot\left(\lambda+\Upsilon^{k-1}_{2,high}\right)+C_{2,k-1}}{\sqrt{\lambda+\Upsilon^{k-1}_{2,low}}}+8\sqrt{dH^{4}\log\left(1+\frac{kH^{4}}{d\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4H^{2}\log\left(\frac{24k^{2}H}{p}\right)$
$\Big{\lVert}\widetilde{\Lambda}^{\frac{1}{2}}_{k,h}\cdot\left(w_{h}-\widetilde{w}_{k,h}\right)\Big{\rVert}_{2}\leq\widetilde{\beta}_{k-1}\leq\widetilde{\beta}_{k}$

with probability at least $1-\frac{p}{6H}$ $\forall k\in[K]$. It follows that
for a fixed $h\in[H]$,
$w_{h}\in\bigcap_{k\in[K]}\widetilde{\mathcal{C}}_{k,h}$ with probability at
least $1-\frac{p}{6H}$.
We finally prove that for a fixed $h\in[H]$,
$\left\\{w_{h}\in\bigcap_{k\in[K]}\widehat{\mathcal{C}}_{k,h}\right\\}$ holds
with probability at least $1-\frac{p}{2H}$, using again Thm. 4.1 in Zhou et
al. (2021) and Lem. 12.

Considering the following parameters:

$\displaystyle
x_{i}=\bar{\sigma}^{-1}_{i,h}\cdot\phi_{\widehat{V}_{i,h+1}(s^{i}_{h},a^{i}_{h})},\eta_{i}=\bar{\sigma}^{-1}_{i,h}\cdot\mathds{1}_{\left\\{w_{h}\in\check{\mathcal{C}}_{i,h}\cap\widetilde{\mathcal{C}}_{i,h}\right\\}}\cdot\left[\widehat{V}_{i,h+1}(s^{i}_{h+1})-\Big{\langle}\phi_{\widehat{V}_{i,h+1}}(s^{i}_{h},a^{i}_{h}),w_{h}\Big{\rangle}\right]$
$\displaystyle\mathcal{G}_{i}=\sigma\left(\left\\{s^{k^{\prime}}_{h^{\prime}},a^{k^{\prime}}_{h^{\prime}},r^{k^{\prime}}_{h^{\prime}}\right\\}_{(k^{\prime},h^{\prime})\leq(k,h)}\cup\left(g^{1}_{k^{\prime},h^{\prime}},g^{2}_{k^{\prime},h^{\prime}},f^{1}_{k^{\prime},h^{\prime}},f^{2}_{k^{\prime},h^{\prime}},B^{1}_{k^{\prime},h^{\prime}},B^{3}_{k^{\prime},h^{\prime}}\right)_{(k^{\prime},h^{\prime})\leq(k,h)}\right),$
$\displaystyle\mu^{\star}=w_{h},y_{i}=\Big{\langle}\mu^{\star},x_{i}\Big{\rangle}+\eta_{i}=\bar{\sigma}^{-1}_{i,h}\cdot\mathds{1}_{\left\\{w_{h}\in\check{\mathcal{C}}_{i,h}\cap\widetilde{\mathcal{C}}_{i,h}\right\\}}\cdot\widehat{V}_{i,h+1}(s^{i}_{h+1}),Z_{i}=\lambda\cdot
I_{d\times d}+\sum_{i^{\prime}=1}^{i}x_{i^{\prime}}\cdot
x^{\intercal}_{i^{\prime}}$

and remark that $\mathbb{E}\left[\eta_{i}|\mathcal{G}_{i}\right]=0$,
$\lvert\eta_{i}\rvert\leq\bar{\sigma}^{-1}_{i,h}\leq\sqrt{d}$, $\lVert
x_{i}\rVert_{2}\leq\sqrt{d}$. As done in Zhou et al. (2021), using Lem. 12, we
obtain that $\mathbb{E}\left[\eta^{2}_{i}|\mathcal{G}_{i}\right]\leq 1$.

Then, applying Thm. 4.1 from Zhou et al. (2021), with probability at least
$1-\frac{p}{6H}$:

$\Big{\lVert}\sum_{i=1}^{k}x_{i}\eta_{i}\Big{\rVert}_{Z^{-1}_{k}}\leq
8\sqrt{d\log\left(1+k/\lambda\right)\log\left(24k^{2}H/p\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right),\forall
k\in[K]$ (9)

On the event
$\left\\{w_{h}\in\bigcap_{k\in[K]}\check{\mathcal{C}}_{k,h}\right\\}\cap\mathcal{E}_{hyp}$
and Eq. 9 holds,
$\eta_{i}=\bar{\sigma}^{-1}_{i,h}\cdot\left[\widehat{V}_{i,h+1}(s^{i}_{h+1})-\Big{\langle}\phi_{\widehat{V}_{i,h+1}}(s^{i}_{h},a^{i}_{h}),w_{h}\Big{\rangle}\right]$
and it implies that as proved previously:

$\Big{\lVert}\widehat{\Lambda}^{\frac{1}{2}}_{k,h}\cdot\left(w-\widehat{w}_{k,h}\right)\Big{\rVert}_{2}\leq\frac{C_{w}\cdot\left(\lambda+\Upsilon^{k-1}_{1,high}\right)}{\sqrt{\lambda+\Upsilon^{k-1}_{1,low}}}+\Big{\lVert}\sum_{1\leq
i<k}x_{i}\eta_{i}\Big{\rVert}_{Z^{-1}_{k-1}}+\frac{C_{1,k-1}}{\sqrt{\lambda+\Upsilon^{k-1}_{1,low}}}$
$\Big{\lVert}\widehat{\Lambda}^{\frac{1}{2}}_{k,h}\cdot\left(w-\widehat{w}_{k,h}\right)\Big{\rVert}_{2}\leq\frac{C_{w}\cdot\left(\lambda+\Upsilon^{k-1}_{1,high}\right)+C_{1,k-1}}{\sqrt{\lambda+\Upsilon^{k-1}_{1,low}}}+8\sqrt{d\log\left(1+k/\lambda\right)\log\left(24k^{2}H/p\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right)$
$\Big{\lVert}\widehat{\Lambda}^{\frac{1}{2}}_{k,h}\cdot\left(w-\widehat{w}_{k,h}\right)\Big{\rVert}_{2}\leq\widehat{\beta}_{k-1}\leq\widehat{\beta}_{k}$

Hence, recalling that
$\mathbb{P}\left(\bigcap_{k\in[K]}\check{C}_{k,h}|\mathcal{E}_{hyp}\right),\mathbb{P}\left(\bigcap_{k\in[K]}\widetilde{C}_{k,h}|\mathcal{E}_{hyp}\right)\geq
1-\frac{p}{6H}$ and that Eq. 9 holds with probability $1-\frac{p}{6H}$, we
conclude that
$\left\\{w_{h}\in\bigcap_{k\in[K]}\widehat{\mathcal{C}}_{k,h}\right\\}$ with
probability at least $1-\frac{p}{2H}$, conditioned on the event
$\mathcal{E}_{hyp}$. Finally, the proof is finished by remarking that in the
event
$\left\\{w_{h}\in\bigcap_{k\in[K]}\widehat{\mathcal{C}}_{k,h}\cap\widetilde{\mathcal{C}}_{k,h}\right\\}$,

$\lvert\bar{\mathbb{V}}_{k,h}\widehat{V}_{k,h+1}(s^{k}_{h},a^{k}_{h})-\mathbb{V}_{h}\widehat{V}_{k,h+1}(s^{k}_{h},a^{k}_{h})\rvert\leq
E_{k,h}$

follows directly from Lem. 12 and the definition of $E_{k,h}$.

#####  D.2.2 Regret analysis

The procedure is almost exactly the same as in (Zhou et al., 2021, App. C.2),
the adaptations are stated here for instructive reasons. Again, all the lemmas
hold under $\mathcal{E}_{hyp}$.

######  Lemma 13 (Lemma C.2 in Zhou et al. (2021), Azuma-Hoeffding inequality
(Azuma, 1967)).

Let $M>0$ be a constant. Let $\left\\{x_{i}\right\\}^{n}_{i=1}$ be a
martingale difference sequence with respect to a filtration
$\left\\{\mathcal{G}_{i}\right\\}_{i}$
($\mathbb{E}\left[x_{i}|\mathcal{G}_{i}\right]=0$ a.s. and $x_{i}$ is
$\mathcal{G}_{i+1}$-measurable) such that for all $i\in[n]$, $\lvert
x_{i}\rvert\leq M$ holds almost surely. Then, for any $0<p<1$, with
probability at least $1-p$, we have

$\sum_{i=1}^{n}x_{i}\leq M\sqrt{2n\log\left(\frac{1}{p}\right)}$

Let
$\mathcal{E}=\left\\{w_{h}\in\bigcap_{k\in[K]}\widehat{\mathcal{C}}_{k,h}\cap\widetilde{\mathcal{C}}_{k,h}\right\\}$
be the event where the conclusion of Lem. 12 is true. Then,
$\mathbb{P}\left(\mathcal{E}|\mathcal{E}_{hyp}\right)\geq 1-\frac{p}{2}$.

Similarly, the events $\mathcal{E}_{1},\mathcal{E}_{2}$ are defined as
follows:

$\mathcal{E}_{1}=\left\\{\forall
h^{\prime}\in[H],\sum_{k=1}^{K}\sum_{h=h^{\prime}}^{H}\left[\left[\mathbb{P}_{h}(\widehat{V}_{k,h+1}-V^{\pi_{k}}_{h+1})\right](s^{k}_{h},a^{k}_{h})-\left[\widehat{V}_{k,h+1}-V^{\pi_{k}}_{h+1}\right](s^{k}_{h+1})\right]\leq
4H\sqrt{2KH\log\left(\frac{6H}{p}\right)}\right\\}$
$\mathcal{E}_{2}=\left\\{\sum_{k=1}^{K}\sum_{h=1}^{H}\left[\mathbb{V}_{h}V^{\pi_{k}}_{h+1}\right](s^{k}_{h},a^{k}_{h})\leq
3\left(HT+H^{3}\log\left(\frac{6}{p}\right)\right)\right\\}$

Then, $\mathbb{P}\left(\mathcal{E}_{1}|\mathcal{E}_{hyp}\right)\geq
1-\frac{p}{6}$ is due to Lem. 13 and
$\mathbb{P}\left(\mathcal{E}_{2}\right)\geq 1-\frac{p}{6}$ is due to the next
lemma.

######  Lemma 14 (Lemma C.3 in (Zhou et al., 2021), Total variance lemma ,
lemma C.5 in (Jin et al., 2018)).

With probability at least $1-p$, we have

$\sum_{k=1}^{K}\sum_{h=1}^{H}\left[\mathbb{V}_{h}V^{\pi_{k}}_{h+1}\right](s^{k}_{h},a^{k}_{h})\leq
3\left(HT+H^{3}\log\left(\frac{1}{p}\right)\right)$

######  Lemma 15 (Optmism, Lemma C.4 in (Zhou et al., 2021)).

Let $\widehat{Q}_{k,h}$, $\widehat{V}_{k,h}$ be defined in Alg. 3. Then, on
the event $\mathcal{E}\cap\mathcal{E}_{hyp}$, for any $s,a,k,h$, we have that
$Q^{\star}_{h}(s,a)\leq\widehat{Q}_{k,h}(s,a)$,
$V^{\star}_{h}(s)\leq\widehat{V}_{k,h}(s)$.

######  Lemma 16 (Lemma C.5 in (Zhou et al., 2021)).

Let $\widehat{V}_{k,h}$, $\bar{\sigma}_{k,h}$ be defined in Alg. 3. Then, on
the event $\mathcal{E}\cap\mathcal{E}_{1}\cap\mathcal{E}_{hyp}$, we have

$\sum_{k=1}^{K}\left[\widehat{V}_{k,1}(s^{k}_{1})-V^{\pi_{k}}_{1}(s^{k}_{1})\right]\leq
2\widehat{\beta}_{K}\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\bar{\sigma}^{2}_{k,h}}\sqrt{2Hd\log\left(1+\frac{K}{\lambda}\right)}+4H\sqrt{2T\log\left(\frac{6H}{p}\right)}$
$\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{P}_{h}\left[\widehat{V}_{k,h+1}-V^{\pi_{k}}_{h+1}\right](s^{k}_{h},a^{k}_{h})\leq
2\widehat{\beta}_{K}\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\bar{\sigma}^{2}_{k,h}}\sqrt{2dH^{3}\log\left(1+\frac{K}{\lambda}\right)}+4H^{2}\sqrt{2T\log\left(\frac{6H}{p}\right)}$

######  Lemma 17 (Lemma C.6 in (Zhou et al., 2021)).

Let $\widehat{V}_{k,h}$, $\bar{\sigma}_{k,h}$ be defined in Alg. 3. Then, on
the event $\mathcal{E}\cap\mathcal{E}_{2}\cap\mathcal{E}_{hyp}$, we have

$\sum_{k=1}^{K}\sum_{h=1}^{H}\bar{\sigma}^{2}_{k,h}\leq\frac{H^{2}T}{d}+3\left(HT+H^{3}\log\left(\frac{6}{p}\right)\right)+2H\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{P}_{h}\left[\widehat{V}_{k,h+1}-V^{\pi_{k}}_{h+1}(s^{k}_{h},a^{k}_{h})\right]$
$+2\widetilde{\beta}_{K}\sqrt{T}\sqrt{2dH\log\left(1+\frac{KH^{4}}{d\lambda}\right)}+7\check{\beta}_{K}H^{2}\sqrt{T}\sqrt{2dH\log\left(1+\frac{K}{\lambda}\right)}$

Thus,
$\mathbb{P}\left(\mathcal{E}\cap\mathcal{E}_{1}\cap\mathcal{E}_{2}|\mathcal{E}_{hyp}\right)\geq
1-\frac{5p}{6}\implies\mathbb{P}\left(\mathcal{E}\cap\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}_{hyp}\right)\geq
1-p$, we can bound the regret as follows due to Lems. 15 and 16:

$R(K)\leq
2\widehat{\beta}_{k,h}\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\bar{\sigma}^{2}_{k,h}}\sqrt{2Hd\log\left(1+\frac{KH}{d\lambda}\right)}+4H\sqrt{2T\log\left(\frac{6H}{p}\right)}$
$R(K)=\widetilde{O}\left(H^{\frac{1}{2}}d^{\frac{1}{2}}\widehat{\beta}_{k,h}\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\bar{\sigma}^{2}_{k,h}}+H^{\frac{3}{2}}K^{\frac{1}{2}}\right)$
(10)

We focus now on bounding $\sum_{k=1}^{K}\sum_{h=1}^{H}\bar{\sigma}^{2}_{k,h}$
using Lems. 16 and 17:

$\sum_{k=1}^{K}\sum_{h=1}^{H}\bar{\sigma}^{2}_{k,h}\leq\frac{H^{2}T}{d}+3\left(HT+H^{3}\log\left(\frac{6}{p}\right)\right)+2H\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{P}_{h}\left[\widehat{V}_{k,h+1}-V^{\pi_{k}}_{h+1}(s^{k}_{h},a^{k}_{h})\right]$
$+2\widetilde{\beta}_{K}\sqrt{T}\sqrt{2dH\log\left(1+\frac{KH^{4}}{d\lambda}\right)}+7\check{\beta}_{K}H^{2}\sqrt{T}\sqrt{2dH\log\left(1+\frac{K}{\lambda}\right)}$
$\leq\frac{H^{2}T}{d}+3\left(HT+H^{3}\log\left(\frac{6}{p}\right)\right)+$
$2H\cdot\left(2\widehat{\beta}_{K}\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\bar{\sigma}^{2}_{k,h}}\sqrt{2dH^{3}\log\left(1+\frac{K}{\lambda}\right)}+4H^{2}\sqrt{2T\log\left(\frac{6H}{p}\right)}\right)$
$+2\widetilde{\beta}_{K}\sqrt{T}\sqrt{2dH\log\left(1+\frac{KH^{4}}{d\lambda}\right)}+7\check{\beta}_{K}H^{2}\sqrt{T}\sqrt{2dH\log\left(1+\frac{K}{\lambda}\right)}$

At this point, we recall that $x\leq a\sqrt{x}+b\implies
x\leq\frac{9}{4}\left(a^{2}+b\right)$, we conclude that

$\sum_{k=1}^{K}\sum_{h=1}^{H}\bar{\sigma}^{2}_{k,h}=\widetilde{O}\left(H^{5}d\cdot\widehat{\beta}^{2}_{K}+H^{\frac{7}{2}}K^{\frac{1}{2}}+\frac{H^{3}K}{d}+H^{2}K+\widehat{\beta}_{K}Hd^{\frac{1}{2}}K^{\frac{1}{2}}+\check{\beta}_{K}H^{3}d^{\frac{1}{2}}K^{\frac{1}{2}}\right)$
$\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\bar{\sigma}^{2}_{k,h}}=\widetilde{O}\left(\max\left\\{H^{\frac{5}{2}}d^{\frac{1}{2}}\widehat{\beta}_{K},H^{\frac{7}{4}}K^{\frac{1}{4}},\frac{H^{\frac{3}{2}}K^{\frac{1}{2}}}{d^{\frac{1}{2}}},HK^{\frac{1}{2}},H^{\frac{1}{2}}d^{\frac{1}{4}}\sqrt{\widehat{\beta}_{K}}K^{\frac{1}{4}},H^{\frac{3}{2}}d^{\frac{1}{4}}\sqrt{\check{\beta}_{K}}K^{\frac{1}{4}}\right\\}\right)$

Replacing the inequality above in Eq. 10, we have that under the event
$\mathcal{E}\cap\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}_{hyp}$,
holding with probability at least $1-p$:

$R(K)=\widetilde{O}\left(H^{\frac{1}{2}}d^{\frac{1}{2}}\widehat{\beta}_{k,h}\cdot\max\left\\{H^{\frac{5}{2}}d^{\frac{1}{2}}\widehat{\beta}_{K},H^{\frac{7}{4}}K^{\frac{1}{4}},\frac{H^{\frac{3}{2}}K^{\frac{1}{2}}}{d^{\frac{1}{2}}},HK^{\frac{1}{2}},H^{\frac{1}{2}}d^{\frac{1}{4}}\sqrt{\widehat{\beta}_{K}}K^{\frac{1}{4}},H^{\frac{3}{2}}d^{\frac{1}{4}}\sqrt{\check{\beta}_{K}}K^{\frac{1}{4}}\right\\}+H^{\frac{3}{2}}K^{\frac{1}{2}}\right)$

####  D.3 Proof of Cor. 10

###### Regret analysis:

Due to Clm. 26, the eigenvalues of $D^{1}_{k,h}=B^{3}_{k,h}$ are in the
interval
$\left[\Upsilon^{J,1}_{\frac{p}{24KH}},3\Upsilon^{J,1}_{\frac{p}{24KH}}\right]$
with probability at least $1-\frac{p}{24KH}$ for each $(k,h)\in[K]\times[H]$.
Similarly, the eigenvalues of $D^{2}_{k,h}=B^{4}_{k,h}$ are in the interval
$\left[\Upsilon^{J,2}_{\frac{p}{24KH}},3\Upsilon^{J,2}_{\frac{p}{24KH}}\right]$
with probability at least $1-\frac{p}{24KH}$ for each $(k,h)\in[K]\times[H]$.

Due to Clm. 27, for each $(k,h)\in[K]\times[H]$, $f_{k,h}=f^{2}_{k,h}$ is in
the interval $\left[-C^{J,1}_{\frac{p}{24KH}},C^{J,1}_{\frac{p}{24KH}}\right]$
with probability at least $1-\frac{p}{24KH}$, where
$C^{J,1}_{\frac{p}{24KH}}=\sigma_{B,1}\sqrt{K_{0}}\left(\sqrt{d}+2\sqrt{\log\left(\frac{24KH}{p}\right)}\right)$.
For the same reason, for each $(k,h)\in[K]\times[H]$, $g_{k,h}=g^{2}_{k,h}$ is
in the interval
$\left[-C^{J,1}_{\frac{p}{24KH}},C^{J,2}_{\frac{p}{24KH}}\right]$ with
probability at least $1-\frac{p}{24KH}$, where
$C^{J,2}_{\frac{p}{24KH}}=\sigma_{B,2}\sqrt{K_{0}}\left(\sqrt{d}+2\sqrt{\log\left(\frac{24KH}{p}\right)}\right)$.

In the union event, holding with probability at least $1-\frac{p}{6}$, we can
choose $\Upsilon^{k}_{1,low}=\Upsilon^{J,1}_{\frac{p}{24KH}}$,
$\Upsilon^{k}_{1,high}=3\Upsilon^{J,1}_{\frac{p}{24KH}}$,
$\Upsilon^{k}_{2,low}=\Upsilon^{J,2}_{\frac{p}{24KH}}$ and
$\Upsilon^{k}_{2,high}=3\Upsilon^{J,2}_{\frac{p}{24KH}}$
$\forall(k,h)\in[K]\times[H]$. Also, $C_{1,k}$ and $C_{2,k}$ can be taken
equal to $C^{J,1}_{\frac{p}{24KH}}$ and $C^{J,2}_{\frac{p}{24KH}}$,
respectively.
The choices of $\check{\beta}_{k},\widehat{\beta}_{k}$ and
$\widetilde{\beta}_{k}$ guarantee the following properties:

$\check{\beta}_{k}\geq\frac{C_{w}\left(\lambda+\Upsilon^{k}_{1,high}\right)+C_{1,k}}{\sqrt{\lambda+\Upsilon^{k}_{1,low}}}+8d\sqrt{\log\left(1+\frac{K}{\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right)$
$\widehat{\beta}_{k}\geq\frac{C_{w}\left(\lambda+\Upsilon^{k}_{1,high}\right)+C_{1,k}}{\sqrt{\lambda+\Upsilon^{k}_{1,low}}}+8\sqrt{d\log\left(1+\frac{K}{\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right)$
$\widetilde{\beta}_{k}\geq\frac{C_{w}\left(\lambda+\Upsilon^{k}_{2,high}\right)+C_{2,k}}{\sqrt{\lambda+\Upsilon^{k}_{2,low}}}+8\sqrt{dH^{4}\log\left(1+\frac{KH^{4}}{d\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4H^{2}\log\left(\frac{24k^{2}H}{p}\right)$

since

$3(C_{w}+1)\sqrt{\lambda+\Upsilon^{J,1}_{\frac{p}{24KH}}}\geq\frac{C_{w}\left(\lambda+3\Upsilon^{J,1}_{\frac{p}{24KH}}\right)+C^{J,1}_{\frac{p}{24KH}}}{\sqrt{\lambda+\Upsilon^{J,1}_{\frac{p}{24KH}}}}=\frac{C_{w}\left(\lambda+\Upsilon^{k}_{1,high}\right)+C_{1,k}}{\sqrt{\lambda+\Upsilon^{k}_{1,low}}}$
$3(C_{w}+1)\sqrt{\lambda+\Upsilon^{J,2}_{\frac{p}{24KH}}}\geq\frac{C_{w}\left(\lambda+3\Upsilon^{J,2}_{\frac{p}{24KH}}\right)+C^{J,2}_{\frac{p}{4KH}}}{\sqrt{\lambda+\Upsilon^{J,2}_{\frac{p}{24KH}}}}=\frac{C_{w}\left(\lambda+\Upsilon^{k}_{2,high}\right)+C_{2,k}}{\sqrt{\lambda+\Upsilon^{k}_{2,low}}}$

and $\Upsilon^{J,1}_{\frac{p}{24KH}}\geq C^{J,1}_{\frac{p}{24KH}}$,
$\Upsilon^{J,2}_{\frac{p}{24KH}}\geq C^{J,2}_{\frac{p}{24KH}}$. It is also
easy to notice that $\check{\beta}_{k},\widehat{\beta}_{k}$ and
$\widetilde{\beta}_{k}$ are non-decreasing sequences.
The regret bound just follows from Thm. 9 by replacing the values of
$\check{\beta}_{k},\widehat{\beta}_{k}$ and $\widetilde{\beta}_{k}$.

###### Privacy analysis:

The analysis resembles the privacy analysis of Cor. 5. We also show that the
mechanism
$\left(\widehat{u}_{k,h},\widetilde{u}_{k,h},\widehat{\Lambda}_{k,h},\widetilde{\Lambda}_{k,h}\right)_{(k,h)\in[K]\times[H]}$
is $(\epsilon,\delta)$-DP. In order to do it, for each $h\in[H]$, we prove
that the mechanisms $(\widehat{\Lambda}_{k,h})_{k\in[K]}$,
$(\widehat{u}_{k,h})_{k\in[K]}$, $(\widetilde{\Lambda}_{k,h})_{k\in[K]}$ and
$(\widetilde{u}_{k,h})_{k\in[K]}$ are
$\left(\frac{\epsilon}{4\sqrt{8H\log\left(\frac{8}{\delta}\right)}},\frac{\delta}{8H}\right)$-DP
for each $h\in[H]$ and conclude by advanced composition that
$(\widehat{\Lambda}_{k,h})_{(k,h)\in[K]\times[H]},(\widehat{u}_{k,h})_{(k,h)\in[K]\times[H]},(\widetilde{\Lambda}_{k,h})_{(k,h)\in[K]\times[H]}$
and $(\widetilde{u}_{k,h})_{(k,h)\in[K]\times[H]}$ are
$\left(\frac{\epsilon}{4},\frac{\delta}{4}\right)$-DP.
Remarking that
$\Big{\lVert}\bar{\sigma}^{-2}_{k,h}\phi_{\widehat{V}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\phi^{\intercal}_{\widehat{V}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\Big{\rVert}_{F}\leq
d$ and due to the design of gaussian mechanisms, it is enough with
$\sigma_{B,1}\geq
2d\cdot\frac{32\sqrt{HK_{0}\log\left(\frac{16H}{\delta}\right)\log\left(\frac{8}{\delta}\right)}}{\epsilon}\sqrt{2\log\left(\frac{32HK_{0}}{\delta}\right)}$,
to prove that the mechanism is
$\left(\frac{\epsilon}{4\sqrt{8H\log\left(\frac{8}{\delta}\right)}},\frac{\delta}{8H}\right)$-DP.
The same argument holds for
$\Big{\lVert}\bar{\sigma}^{-2}_{k,h}\phi_{\widehat{V}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\widehat{V}_{k,h+1}(s^{k}_{h+1})\Big{\rVert}_{2}\leq
d$ and the choice of the variance $\sigma_{B,1}$.
Again, since
$\Big{\lVert}\phi_{\widehat{V}^{2}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\phi^{\intercal}_{\widehat{V}^{2}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\Big{\rVert}_{F}\leq
H^{4}$ and due to the choice of

$\sigma_{B,2}\geq
2H^{4}\cdot\frac{32\sqrt{HK_{0}\log\left(\frac{16H}{\delta}\right)\log\left(\frac{8}{\delta}\right)}}{\epsilon}\sqrt{2\log\left(\frac{32HK_{0}}{\delta}\right)},$

it follows that the mechanism is
$\left(\frac{\epsilon}{4\sqrt{8H\log\left(\frac{8}{\delta}\right)}},\frac{\delta}{8H}\right)$-DP
as well. Exactly the same argument is true for
$\Big{\lVert}\phi_{\widehat{V}^{2}_{k,h+1}}(s^{k}_{h},a^{k}_{h})\cdot\widehat{V}^{2}_{k,h+1}(s^{k}_{h+1})\Big{\rVert}_{2}\leq
H^{2}$ and $\sigma_{B,2}$.

Using the post-processing property
$\widehat{w}_{k,h}=\widehat{\Lambda}^{-1}_{k,h}\cdot\widehat{u}_{k,h}$,
$\widetilde{w}_{k,h}=\widetilde{\Lambda}^{-1}_{k,h}\cdot\widetilde{u}_{k,h}$,
we conclude that
$\left(\widehat{w}_{k,h},\widetilde{w}_{k,h},\widehat{\Lambda}_{k,h},\widetilde{\Lambda}_{k,h}\right)_{(k,h)\in[K]\times[H]}$
is $(\epsilon,\delta)$-DP. As in Cor. 5, we rely on the Billboard Lemma and
remark that the $Q$-function, $\widehat{Q}_{k}$, is a function of the
mechanism
$\left(\widehat{\Lambda}_{k,h},\widehat{w}_{k,h}\right)_{(k,h)\in[K]\times[H]}$
to guarantee that Alg. 3 is $(\epsilon,\delta)$-JDP.

####  D.4 Proof of Cor. 11

###### Regret analysis:

Due to Clm. 26, the eigenvalues of $D^{1}_{k,h}=\left(\sum_{1\leq i\leq
k}B^{1}_{i,h}\right)+2\Upsilon^{L,1}_{\frac{p}{24KH}}$ are in the interval
$\left[\Upsilon^{L,1}_{\frac{p}{24KH}},3\Upsilon^{L,1}_{\frac{p}{24KH}}\right]$
with probability at least $1-\frac{p}{24KH}$ for each $(k,h)\in[K]\times[H]$.
For the same reason, the eigenvalues of $D^{2}_{k,h}=\left(\sum_{1\leq i\leq
k}B^{2}_{i,h}\right)+2\Upsilon^{L,2}_{\frac{p}{24KH}}$ are in the interval
$\left[\Upsilon^{L,2}_{\frac{p}{24KH}},3\Upsilon^{L,2}_{\frac{p}{24KH}}\right]$
with probability at least $1-\frac{p}{24KH}$.
Due to Clm. 27, for each $(k,h)\in[K]\times[H]$, $f_{k,h}=\left(\sum_{1\leq
i\leq k}f^{1}_{i,h}\right)$ is in the interval
$\left[-C^{L,1}_{\frac{p}{24KH}},C^{L,1}_{\frac{p}{24KH}}\right]$ with
probability at least $1-\frac{p}{24KH}$, where
$C^{L,1}_{\frac{p}{24KH}}=\sigma_{B,1}\sqrt{K}\left(\sqrt{d}+2\sqrt{\log\left(\frac{24KH}{p}\right)}\right)$
and $g_{k,h}=\sum_{1\leq i\leq k}g^{1}_{i,h}$ is in the interval
$\left[-C^{L,2}_{\frac{p}{24KH}},C^{L,2}_{\frac{p}{24KH}}\right]$ with
probability at least $1-\frac{p}{24KH}$, where
$C^{L,2}_{\frac{p}{24KH}}=\sigma_{B,2}\sqrt{K}\left(\sqrt{d}+2\sqrt{\log\left(\frac{24KH}{p}\right)}\right)$.
In the union event, holding with probability at least $1-\frac{p}{6}$,
choosing $\Upsilon^{k}_{1,low}=\Upsilon^{L,1}_{\frac{p}{24KH}}$,
$\Upsilon^{k}_{1,high}=3\Upsilon^{L,1}_{\frac{p}{24KH}}$,
$\Upsilon^{k}_{2,low}=\Upsilon^{L,2}_{\frac{p}{24KH}}$ and
$\Upsilon^{k}_{2,high}=\Upsilon^{L,2}_{\frac{p}{24KH}}$ for each
$(k,h)\in[K]\times[H]$. Also, $C_{1,k}$ and $C_{2,k}$ can be chosen as
$C^{L,1}_{\frac{p}{24KH}}$ and $C^{L,2}_{\frac{p}{24KH}}$.
The choices of $\check{\beta}_{k},\widehat{\beta}_{k}$ and
$\widetilde{\beta}_{k}$ guarantee the following properties:

$\check{\beta}_{k}\geq\frac{C_{w}\left(\lambda+\Upsilon^{k}_{1,high}\right)+C_{1,k}}{\sqrt{\lambda+\Upsilon^{k}_{1,low}}}+8d\sqrt{\log\left(1+\frac{K}{\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right)$
$\widehat{\beta}_{k}\geq\frac{C_{w}\left(\lambda+\Upsilon^{k}_{1,high}\right)+C_{1,k}}{\sqrt{\lambda+\Upsilon^{k}_{1,low}}}+8\sqrt{d\log\left(1+\frac{K}{\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4\sqrt{d}\log\left(\frac{24k^{2}H}{p}\right)$
$\widetilde{\beta}_{k}\geq\frac{C_{w}\left(\lambda+\Upsilon^{k}_{2,high}\right)+C_{2,k}}{\sqrt{\lambda+\Upsilon^{k}_{2,low}}}+8\sqrt{dH^{4}\log\left(1+\frac{KH^{4}}{d\lambda}\right)\log\left(\frac{24k^{2}H}{p}\right)}+4H^{2}\log\left(\frac{24k^{2}H}{p}\right)$

since

$3(C_{w}+1)\sqrt{\lambda+\Upsilon^{L,1}_{\frac{p}{24KH}}}\geq\frac{C_{w}\left(\lambda+3\Upsilon^{L,1}_{\frac{p}{24KH}}\right)+C^{J,1}_{\frac{p}{24KH}}}{\sqrt{\lambda+\Upsilon^{L,1}_{\frac{p}{24KH}}}}=\frac{C_{w}\left(\lambda+\Upsilon^{k}_{1,high}\right)+C_{1,k}}{\sqrt{\lambda+\Upsilon^{k}_{1,low}}}$