# Differentially Private Episodic Reinforcement Learning
with Heavy-tailed Rewards

Yulian Wu  Xingyu Zhou  Sayak Ray Chowdhury  Di Wang

###### Abstract

In this paper, we study the problem of (finite horizon tabular) Markov
decision processes (MDPs) with heavy-tailed rewards under the constraint of
differential privacy (DP). Compared with the previous studies for private
reinforcement learning that typically assume rewards are sampled from some
bounded or sub-Gaussian distributions to ensure DP, we consider the setting
where reward distributions have only finite $(1+v)$-th moments with some
$v\in(0,1]$. By resorting to robust mean estimators for rewards, we first
propose two frameworks for heavy-tailed MDPs, i.e., one is for value iteration
and another is for policy optimization. Under each framework, we consider both
joint differential privacy (JDP) and local differential privacy (LDP) models.
Based on our frameworks, we provide regret upper bounds for both JDP and LDP
cases and show that the moment of distribution and privacy budget both have
significant impacts on regrets. Finally, we establish a lower bound of regret
minimization for heavy-tailed MDPs in JDP model by reducing it to the
instance-independent lower bound of heavy-tailed multi-armed bandits in DP
model. We also show the lower bound for the problem in LDP by adopting some
private minimax methods. Our results reveal that there are fundamental
differences between the problem of private RL with sub-Gaussian and that with
heavy-tailed rewards.

differential privacy, Markov decision processes, heavy-tailed rewards

##  1 Introduction

As a fundamental paradigm in decision-making problems, reinforcement learning
(RL), where an agent aims to maximize its long-term reward from interacting
with an environment, has been widely applied in various fields such as
finance(Xu & Wang, 2022), healthcare (Gottesman et al., 2019), transportation
(Li et al., 2019) and online recommendations (Zong et al., 2016). However, in
these applications, there are some privacy issues as they always involve
sensitive data (Pan et al., 2019). And users are less willing to disclose
information and are more concerned about how their personal data are used (Das
et al., 2021). These privacy concerns in RL require us to design some
reinforcement learning algorithms that achieve good performance while can also
protect the training environment’s privacy.

In order to protect the information of sensitive data, differential privacy
(DP)(Dwork et al., 2006) has become a de facto technique for private data
analysis. Over the past decade, differentially private reinforcement learning
(DP-RL) has been extensively studied for various settings, including full
information RL (Jain et al., 2012) and partial information RL, e.g., Mishra &
Thakurta (2015); Chowdhury & Zhou (2022b, a); Vietri et al. (2020). For
private RL problems, it is natural to first consider achieving privacy
protection in the standard DP model in Dwork et al. (2006) where we treat each
episode as a specific user and the agent collects the raw data of users and
aims to achieve privacy protection for history trajectories. However, Shariff
& Sheffet (2018) and Dubey (2021) show that the standard differential privacy
provably incurs linear regret in contextual bandits (hence in RL as well) and
such linear dependency is unavoidable. Therefore, for general DP-RL, it is
more reasonable to consider a relaxation of DP, namely joint differential
privacy (JDP) (Kearns et al., 2014), in which for each user $i$, knowledge of
the other users does not reveal much about user $i$’s data. Moreover, in some
situations, users are unwilling to share their data with the agent, so it is
also common to consider another DP model, local differential privacy (LDP),
which perturbs users’ data locally before sending them to the central server
so that only the data owners can access the original data.

As we mentioned above, sensitive information is contained in the states and
rewards of trajectories for RL. Several methods of preserving the privacy of
rewards have been proposed in the past few years. However, these methods
always need to assume the rewards are sampled from light-tailed distributions,
such as sub-Gaussian distributions, to ensure DP. However, in a wide variety
of real-world systems such as economics (Ibragimov et al., 2015), medicine
(Zhao et al., 2020), and market crashes (Schluter & Trede, 2008), rewards are
often generated by certain heavy-tailed distributions. For example, it has
been shown that RL is quite suitable to recommendation systems (Afsar et al.,
2022), and more and more companies such as Google (Chen et al., 2019) are
utilizing the power of RL to recommend better items to their customers.
However, in such scenarios, the rewards, which correspond to users’ feedback
such as click, not click, or rating, always contain sensitive information and
always follow heavy-tailed or even long-tailed distributions (Park & Tuzhilin,
2008; Celma & Celma, 2010). Therefore, it is necessary to design private
algorithms for these RL problems with heavy-tailed rewards.

Motivated by these facts, in this paper, we focus on one fundamental model in
RL under DP constraints, i.e., private (finite horizon tabular) Markov
decision processes (MDPs) (Sutton & Barto, 2018), with heavy-tailed rewards in
that the reward distribution of each state-action pair has only bounded
$(1+v)$-th moment for some $v\in(0,1]$. To the best of our knowledge, we are
the first to consider MDPs with heavy-tailed rewards in both joint and local
DP models. And our contributions can be summarized as follows.

1\. We start from the most commonly used method, i.e., the value-iteration
(VI) algorithm. Specifically, we present a general framework, Private-Heavy-
UCBVI, for designing private optimistic VI algorithms based on some robust
mean estimator for heavy-tailed distributions. To guarantee privacy, we use an
adaptive version of the Tree-based mechanism and a new noise allocation method
to achieve JDP, and we use the Laplacian mechanism for LDP. Based on this
framework, we establish regret upper bounds for the problem in both JDP and
LDP models to measure the performance of the framework.

2\. Based on our private mechanisms, we then consider policy optimization (PO)
based algorithms and propose a framework, namely Private-Heavy-UCBPO. We also
analyze the regret bounds for both JDP and LDP models based on this framework
by developing some new theoretical techniques as byproducts. It is notable
that this is also the first PO-based algorithm for heavy-tailed MDPs, and
there is even no previous PO algorithm in the non-private case.

3\. Finally, we study the lower bounds of our problem in JDP and LDP. In
particular, for the JDP model, two unique challenges arise when applying the
standard reduction from RL to MAB for minimax lower bounds. First, it is still
open for the lower bound in the MAB case as highlighted in Tao et al. (2022b).
We resolve this open problem by deriving the first lower bound for heavy-
tailed MAB under the central DP model. Second, additional care is required to
translate the lower bound for MAB under DP to the lower bound for RL under
JDP. We resolve these challenges by using the notion of JDP with the public
initial state as a bridge. For the LDP case, we derive the lower bound by
providing some new hard instances of MDPs and using some private minimax
methods. All the instances and methods can also be used in other private RL
problems.

We summarize our theoretical results in Table 1. Due to space limitations,
some additional algorithms and sections, and all proofs and experiments are
included in Appendix.

Problem | Reward/ Cost | DP | Algorithm | Upper bound | Lower bound
---|---|---|---|---|---
MAB | Heavy-tailed |  $\epsilon$-DP | Robust-SE |  $\widetilde{O}\left(\left(\frac{A}{\epsilon}\right)^{\frac{v}{1+v}}K^{\frac{1}{1+v}}\right)$ (Tao et al., 2022b) | $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\Omega\left(\left(\frac{A}{\epsilon}\right)^{\frac{v}{1+v}}K^{\frac{1}{1+v}}\right)}$
$\epsilon$-LDP | Robust-SE |  $\widetilde{O}\left(\left(\frac{A}{\epsilon^{2}}\right)^{\frac{v}{1+v}}K^{\frac{1}{1+v}}\right)$ (Tao et al., 2022b) |  $\Omega\left(\left(\frac{A}{\epsilon^{2}}\right)^{\frac{v}{1+v}}K^{\frac{1}{1+v}}\right)$ (Tao et al., 2022b)
MDPs | Bounded | $\epsilon$-JDP | UCB-VI |  $\widetilde{O}\left(\sqrt{SAH^{3}T}+S^{2}AH^{3}/\epsilon\right)$(Chowdhury & Zhou, 2021) | $\Omega\left(\sqrt{HSAT}+\frac{SAH\log T}{\epsilon}\right)$(Vietri et al., 2020)
UCB-PO |  $\widetilde{O}\left(\sqrt{S^{2}AH^{3}T}+S^{2}AH^{3}/\epsilon\right)$(Chowdhury & Zhou, 2021)
$\epsilon$-LDP | UCB-VI |  $\widetilde{O}\left(\sqrt{SAH^{3}T}+S^{2}A\sqrt{H^{5}T}/\epsilon\right)$(Chowdhury & Zhou, 2021) | $\Omega\left(\frac{H\sqrt{SAK}}{\min\\{e^{\epsilon}-1,1\\}}\right)$ (Garcelon et al., 2021)
UCB-PO |  $\widetilde{O}\left(\sqrt{S^{2}AH^{3}T}+S^{2}A\sqrt{H^{5}T}/\epsilon\right)$(Chowdhury & Zhou, 2021)
MDPs | Heavy-tailed | $\epsilon$-JDP | UCB-VI | $\widetilde{O}\left(\sqrt{SAH^{3}T}+\frac{S^{2}AH^{3}}{\epsilon}+\left(\frac{SAH^{2}}{\epsilon}\right)^{\frac{v}{1+v}}T^{\frac{1}{1+v}}\right)$ | $\Omega\left(\left(\frac{SA}{\epsilon}\right)^{\frac{v}{1+v}}K^{\frac{1}{1+v}}\right)$
UCB-PO | $\widetilde{O}\left(\sqrt{S^{2}AH^{3}T}+\frac{S^{2}AH^{3}}{\epsilon}+\left(\frac{SAH^{2}}{\epsilon}\right)^{\frac{v}{1+v}}T^{\frac{1}{1+v}}\right)$
$\epsilon$-LDP | UCB-VI | $\widetilde{O}\left(\sqrt{SAH^{3}T}+\frac{S^{2}A\sqrt{H^{5}T}}{\epsilon}+\left(\frac{H^{3}SA}{\epsilon^{2}}\right)^{\frac{v}{2(1+v)}}T^{\frac{2+v}{2(1+v)}}\right)$ | $\Omega\left(\left(\frac{SA}{\epsilon^{2}}\right)^{\frac{v}{1+v}}K^{\frac{1}{1+v}}\right)$
UCB-PO | $\widetilde{O}\left(\sqrt{S^{2}AH^{3}T}+\frac{S^{2}A\sqrt{H^{5}T}}{\epsilon}+\left(\frac{H^{3}SA}{\epsilon^{2}}\right)^{\frac{v}{2(1+v)}}T^{\frac{2+v}{2(1+v)}}\right)$

Table 1: Summary of our results and regret comparisons for private RL. All
results are in the expected regret form. For the heavy-tailed reward
distribution case, we assume the $(1+v)$-th raw moment of each reward
distribution is bounded by 1 for some known $v\in(0,1]$. For the bounded
reward case, we assume the rewards are in $[0,1]$. Here $T=KH$ is the total
number of steps, where $K$ is the total number of episodes and $H$ is the
number of steps per episode. $S$ is the number of states and $A$ is the number
of actions. $\epsilon\in(0,1]$ is the privacy budget. $\widetilde{O}(\cdot)$
hides $poly\log(S,A,T,1/\delta)$ factors, where $\delta\in(0,1]$ is the
desired confidence level. In MAB problem, $S=1,H=1$. We highlight our results
in blue color.

##  2 Preliminaries

###  2.1 MDPs with Heavy-tailed Rewards

In a finite horizon Markov decision process (MDP), an agent needs to interact
with the environment to make sequential decisions. We can formalize the
problem by a tuple
$(\mathcal{S},\mathcal{A},H,(P_{h})_{h=1}^{H},(r_{h})_{h=1}^{H})$, where
$\mathcal{S}$ and $\mathcal{A}$ is the state and the action space with
cardinality $S$ and $A$ respectively, $H\in\mathbb{N}$ is the episode length,
$P_{h}(s^{\prime}|s,a)$ is the probability of transitioning to state
$s^{\prime}$ from state $s$ provided action $a$ is taken at step $h$ and
$r_{h}(s,a)$ is the mean of the reward distribution at step $h$. The actions
are chosen following some policy $\pi=(\pi_{h})_{h=1}^{H}$, where each
$\pi_{h}$ is a mapping from the state space $\mathcal{S}$ into a probability
distribution over the action space $\mathcal{A}$ i.e. $\pi_{h}(a|s)\geq 0$ and
$\sum_{a\in\mathcal{A}}\pi_{h}(a|s)=1$ for each $s\in\mathcal{S}$. Solving a
reinforcement learning task means finding a policy $\pi$ that maximizes the
long-term expected reward starting from every state $s\in\mathcal{S}$ and
every step $h\in[H]$, defined as
$V_{h}^{\pi}(s):=\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}\left(s_{h^{\prime}},a_{h^{\prime}}\right)\mid
s_{h}=s,\pi\right],$ where the expectation takes over the randomness of the
transition kernel $P=(P_{h})_{h=1}^{H}$ and the policy $\pi$. We call
$V_{h}^{\pi}(s)$ as the _value function_ of a state $s$ under policy $\pi$ at
step $h$. Now, defining the _Q-function_ of taking action $a$ in state $s$
under policy $\pi$ at step $h$ as
$Q_{h}^{\pi}(s,a):=\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}\left(s_{h^{\prime}},a_{h^{\prime}}\right)\mid
s_{h}=s,a_{h}=a,\pi\right],$ we obtain
$Q_{h}^{\pi}(s,a)=r_{h}(s,a)+\sum_{s^{\prime}\in\mathcal{S}}V_{h+1}^{\pi}(s^{\prime})P_{h}(s^{\prime}|s,a)$
and $V_{h}^{\pi}(s)=\sum_{a\in\mathcal{A}}Q_{h}^{\pi}(s,a)\pi_{h}(a|s)$.

We call a policy $\pi^{*}$ optimal if it maximizes the value function of all
states $s$ and steps $h$ simultaneously, and the corresponding optimal value
function is denoted by $V_{h}^{*}(s)=\max_{\pi\in\Pi}V_{h}^{\pi}(s)$ for all
$h\in[H]$, where $\Pi$ is the set of all non-stationary policies. The agent
interacts with the environment for $K$ episodes to learn the unknown
transition probabilities $P_{h}(s^{\prime}|s,a)$ and mean rewards
$r_{h}(s,a)$, and thus, in turn, the optimal policy $\pi^{*}$. At each episode
$k$, the agent chooses a policy $\pi^{k}=(\pi_{h}^{k})_{h=1}^{H}$ and samples
a trajectory
$\left\\{s_{1}^{k},a_{1}^{k},r_{1}^{k},\ldots,s_{H}^{k},a_{H}^{k},r_{H}^{k},s_{H+1}^{k}\right\\}$
by interacting with the MDP using this policy. Here, at a given step $h$,
$s_{h}^{k}$ denotes the state of the MDP,
$a_{h}^{k}\sim\pi_{h}^{k}(\cdot|s_{h}^{k})$ denotes the action taken by the
agent, $r_{h}^{k}$ denotes the random reward obtained by the agent with the
mean value $r_{h}(s_{h}^{k},a_{h}^{k})$ and $s_{h+1}^{k}\sim
P_{h}(\cdot|s_{h}^{k},a_{h}^{k})$ denotes the next state.

We consider a heavy-tailed setting in this paper where the reward distribution
of each state-action pair $(s,a)$ at step $h$ only has the finite raw moment
of order $1+v$ for some $v\in(0,1]$. Concretely, we assume that there is a
constant $u>0$ such that at step $h$, for each state-action pair $(s,a)$
reward distribution $\mathcal{R}_{h}(s,a)$,
$\mathbb{E}_{X\sim\mathcal{R}_{h}(s,a)}[|X|^{1+v}]\leq u.$ In this paper, we
assume both $v$ and $u$ are known constants. Since this raw moment of $(1+v)$
for reward is finite, the expectation of reward random variable is also
finite, and we denote
$|r_{h}(s,a)|=|\mathbb{E}_{X\sim\mathcal{R}_{h}(s,a)}[X]|\leq\tau.$ where
$\tau$ is a known constant.

We measure the agent’s performance by using the cumulative regret accumulated
over $K$ episodes, which is defined as
$Reg(T):=\sum_{k=1}^{K}\left[V_{1}^{*}\left(s_{1}^{k}\right)-V_{1}^{\pi^{k}}\left(s_{1}^{k}\right)\right],$
where $T=KH$ denotes the total number of steps and $s_{1}^{k}$ is the initial
state.

###  2.2 DP in Episodic Reinforcement Learning

In the episodic RL setting described above, it is natural to view each episode
$k\in[K]$ as a trajectory associated with a specific user. To this end, we let
$U_{k}=(u_{1},\ldots,u_{K})\in\mathcal{U}^{K}$ to denote a sequence of $K$
unique users participating in the private RL protocol with an RL agent
$\mathcal{M}$, where $\mathcal{U}$ is the set of all users. Each user $u_{k}$
is identified by the reward and state responses
$(r_{h}^{k},s_{h+1}^{k})_{h=1}^{H}$ she/he gives to the action
$(a_{h}^{k})_{h=1}^{H}$ chosen by the agent. We let
$\mathcal{M}(U_{K})=(a_{1}^{1},\ldots,a_{H}^{K})\in\mathcal{A}^{KH}$ to denote
the set of all actions chosen by the agent $\mathcal{M}$ when interacting with
the user sequence $U_{K}$ and let
$\mathcal{M}_{-k}\left(U_{K}\right):=\mathcal{M}\left(U_{K}\right)\backslash\left(a_{h}^{k}\right)_{h=1}^{H}$
to denote all the actions chosen by the agent $\mathcal{M}$ excluding those
recommended to $u_{k}$.

######  Definition 1 (Joint Differential Privacy (Kearns et al., 2014)).

For any $\epsilon\geq 0$, a mechanism
$\mathcal{M}:\mathcal{U}^{K}\rightarrow\mathcal{A}^{KH}$ is $\epsilon$-joint
differential privacy (JDP) if for all $k\in[K]$, for all user sequences
$U_{K},U_{K}^{\prime}\in\mathcal{U}^{K}$ differing only on the $k$-th user and
for all set of actions $\mathcal{A}_{-k}\subset\mathcal{A}^{(K-1)H}$ given to
all but the $k$-th user
$\mathbb{P}\left[\mathcal{M}_{-k}\left(U_{K}\right)\in\mathcal{A}_{-k}\right]\leq\exp(\varepsilon)\mathbb{P}\left[\mathcal{M}_{-k}\left(U_{K}^{\prime}\right)\in\mathcal{A}_{-k}\right].$

Local differential privacy is a more user-friendly model since it requires
protecting each user’s data
$X=(s_{h}^{k},a_{h}^{k},r_{h}^{k},s_{h+1}^{k})_{h=1}^{H}$ before collection.
We define local differential privacy for finite-horizon RL as follows:

######  Definition 2 (Local Differential Privacy (Duchi et al., 2013)).

For any $\epsilon\geq 0$, a mechanism $\mathcal{M}^{\prime}$ is
$\epsilon$-local differentially private (LDP) if for all trajectories
$X,X^{\prime}\in\mathcal{X}$ and for all possible subsets
$\mathcal{E}_{0}\subset\left\\{\mathcal{M}^{\prime}(X)\mid
X\in\mathcal{X}\right\\}$ we have
$\mathbb{P}\left[\mathcal{M}^{\prime}(X)\in\mathcal{E}_{0}\right]\leq\exp(\varepsilon)\mathbb{P}\left[\mathcal{M}^{\prime}\left(X^{\prime}\right)\in\mathcal{E}_{0}\right].$

We introduce some notations for later analysis. We denote the number of times
that the agent has visited the state-action pair $(s,a)$ at step $h$ before
episode $k$ as
$N_{h}^{k}(s,a):=\sum_{k^{\prime}=1}^{k-1}\mathbbm{I}\\{s_{h}^{k^{\prime}}=s,a_{h}^{k^{\prime}}=a\\}$.
Similarly,
$N_{h}^{k}(s,a,s^{\prime}):=\sum_{k^{\prime}=1}^{k-1}\mathbbm{I}\\{s_{h}^{k^{\prime}}=s,a_{h}^{k^{\prime}}=a,s_{h+1}^{k^{\prime}}=s^{\prime}\\}$
denotes the count of going to state $s^{\prime}$ from $s$ upon playing action
$a$ at step $h$ before episode $k$. Finally, we denotes the total truncated
rewards obtained by taking action $a$ on state $s$ and at step $h$ before
episode $k$ as

$\vspace{-1ex}R_{h}^{k}(s,a)=\sum_{k^{\prime}=1}^{k-1}\mathbbm{I}\\{s_{h}^{k^{\prime}}=s,a_{h}^{k^{\prime}}=a,|r_{h}^{k^{\prime}}|\leq
B_{N_{h}^{k^{\prime}}(s,a)}\\}r_{h}^{k^{\prime}},$ (1)

where $B_{N_{h}^{k^{\prime}}(s,a)}$ is truncation threshold which is a non-
decreasing function of ${N_{h}^{k^{\prime}}(s,a)}$ and to be set later. In the
non-private case, these counters are sufficient to find estimates of the
transition kernels $(P_{h})_{h}$ and mean reward functions $(r_{h})_{h}$ to
design policy $(\pi_{h}^{k})_{h}$ for episode $k$ for model-based MDP by using
the table lookup model (Agarwal et al., 2019). However, in the private case,
the challenge is that these counters depend on users’ states and reward
responses to suggest further actions, which are considered as sensitive
information. Therefore, we must release these counts through some privacy-
preserving mechanism namely PRIVATIZER on which the learning agent would rely.
To this end, we let $\tilde{N}_{h}^{k}(s,a)$, $\tilde{R}_{h}^{k}(s,a)$, and
$\tilde{N}_{h}^{k}(s,a,s^{\prime})$ to denote the privatized version of
$N_{h}^{k}(s,a)$, $R_{h}^{k}(s,a)$, and $N_{h}^{k}(s,a,s^{\prime})$,
respectively.

Now we make a general assumption on the counts released by the PRIVATIZER,
which roughly means that the errors of private counts w.r.t the actual ones
are bounded by some terms with high probability. Later on, we will show the
specific PRIVATIZERs we use will automatically satisfy such an assumption.

######  Assumption 1 (Properties of private counts).

For any $\epsilon>0$ and $\delta\in(0,1]$, there exist functions
$E_{\epsilon,\delta,1},E_{\epsilon,\delta,k,2},E_{\epsilon,\delta,3}>0$ such
that with probability at least $1-\delta$, uniformly over all $(s,a,h,k)$, the
private counts returned by the PRIVATIZER (both LOCAL and CENTRAL) satisfy:
(i)$|\tilde{N}_{h}^{k}(s,a)-N_{h}^{k}(s,a)|\leq E_{\epsilon,\delta,1}$, (ii)
$|\tilde{R}_{h}^{k}(s,a)-R_{h}^{k}(s,a)|\leq E_{\epsilon,\delta,k,2}$, and
(iii)$|\tilde{N}_{h}^{k}(s,a,s^{\prime})-N_{h}^{k}(s,a,s^{\prime})|\leq
E_{\epsilon,\delta,3}.$

Based on the above, then we define the private mean empirical rewards and
private empirical transition probabilities for all $(s,a,h,k)$ as

$\displaystyle\widetilde{r}_{h}^{k}(s,\\!a)\\!=\\!\frac{\widetilde{R}_{h}^{k}(s,a)}{1\\!\vee\\!(\widetilde{N}_{h}^{k}(s,a)\\!+\\!E_{\varepsilon,\delta,1\\!})},\\!\widetilde{P}_{h}^{k}\\!(s^{\prime}\\!|\\!s,\\!a)\\!=\\!\frac{\widetilde{N}_{h}^{k}\left(s,a,s^{\prime}\right)}{\\!1\\!\vee\\!(\widetilde{N}_{h}^{k}(s,a)\\!+\\!E_{\varepsilon,\delta,1}\\!)}.$
(2)

We refer the readers to Table 2 in Appendix for all the above notations for
convenience.

##  3 Private Value-iteration for Heavy-tailed Rewards

In the standard non-private RL setting, a straightforward way to get the
optimal policy is to find the optimal value function, which can be determined
by a simple iterative algorithm called value iteration (VI) that has been
shown to converge to the correct $V^{*}$ (Bellman, 1957; Beutler, 1989). Based
on Upper Confidence Bound (UCB) philosophy, the non-private UCB-VI method is
proposed by Azar et al. (2017), which takes some value-aware concentration
results as the exploration bonus. Due to its simplicity, there are several
private valued-based RL algorithms for private RL with bounded rewards
(Chowdhury & Zhou, 2021; Vietri et al., 2020; Garcelon et al., 2021). However,
there is no UCB-VI algorithm for private RL with heavy-tailed rewards. In this
section, we will start by designing value iteration-based algorithms for our
problem in both JDP and LDP models.

Our general framework, Private-Heavy-UCBVI algorithm, is presented in
Algorithm 1. The key idea of our algorithm is that we first establish $SAH$
parallel private counters for each tuple $(s,a,h)$ and $S^{2}AH$ parallel
private counters for each tuple $(s,a,h,s^{\prime})$, by using the (adaptive)
Tree-based mechanism in JDP or the Laplacian mechanism in LDP to guarantee
privacy. Based on these private counts, we design our algorithm by using a
private and robust version of UCB at steps $7-9$ where the UCB bonus term is
from the concentration results for our private estimators in Lemma 15 or Lemma
17. At steps $9-10$, we compute private versions of the $Q$-function and the
value function by using the optimistic Bellman recursion. Then a greedy policy
$\pi^{k}$ is obtained by maximizing the private estimated $Q$-function at step
12. After rolling out the trajectory by acting the policy $\pi^{k}$, we
truncate the rewards by an adaptive and non-decreasing truncation threshold
$B_{N_{h}^{k}(s,a)}$ and translate all non-private statistics into private
ones.

Algorithm 1 Private-Heavy-UCBVI

0: Number of episodes $K$, time horizon $H$, privacy level $\epsilon>0$,
reward mean bound $\tau$, a PRIVATIZER (Local or Central) and confidence level
$\delta\in(0,1]$

1: Initialize private counts
$\tilde{R}_{h}^{1}(s,a)=0,\tilde{N}_{h}^{1}(s,a)=0,\tilde{N}_{h}^{1}(s,a,s^{\prime})=0$
for all $(s,a,s^{\prime},h)$

2: Set precision levels
$E_{\epsilon,\delta,1},E_{\epsilon,\delta,k,2},E_{\epsilon,\delta,3}$ of the
PRIVATIZER

3: for $k=1,\dots,K$ do

4: Initialize private value estimates: $\tilde{V}_{H+1}^{k}(s)=0$

5: for $h=H,H-1,\dots,1$ do

6: Compute $\widetilde{r}_{h}^{k}(s,a)$ and
$\widetilde{P}_{h}^{k}\left(s^{\prime}|s,a\right)$ for
$\forall(s,a,s^{\prime})$ as in (2) using the private counts

7: Set exploration bonus using Lemma 15:
$\beta_{h}^{k}(s,a)=\beta_{h}^{k,r}(s,a)+\beta_{h}^{k,pv}(s,a)\forall(s,a)$

8: Compute: $\forall(s,a),$
$\tilde{Q}_{h}^{k}(s,a)=\max\\{-(H-h+1)\tau,\min\\{(H-h+1)\tau,\widetilde{r}_{h}^{k}(s,a)+\sum_{s^{\prime}\in\mathcal{S}}\tilde{V}_{h+1}^{k}(s^{\prime})\widetilde{P}_{h}^{k}\left(s^{\prime}|s,a\right)+\beta_{h}^{k}(s,a)\\}\\}$

9: Compute private value function: $\forall
s,\tilde{V}_{h}^{k}(s)=\max_{a\in\mathcal{A}}\tilde{Q}_{h}^{k}(s,a)$

10: end for

11: Compute policy:
$\forall(s,h),\pi_{h}^{k}(s)=\arg\max_{a\in\mathcal{A}}\tilde{Q}_{h}^{k}(s,a)$

12: Roll out a trajectory $(s_{1}^{k},a_{1}^{k},r_{1}^{k},\dots,s_{H+1}^{k})$
by acting the policy $\pi^{k}=(\pi_{h}^{k})_{h=1}^{H}$

13: Receive private counts
$\tilde{N}_{h}^{k+1}(s,a),\tilde{N}_{h}^{k+1}(s,a,s^{\prime})$ and truncated
private rewards summation $\tilde{R}_{h}^{k+1}(s,a)$

14: end for

###  3.1 Heavy-tailed Value-iteration in JDP

As we mentioned earlier, different instances of PRIVATIZER correspond to
different privacy models. For JDP, we will use CENTRAL-PRIVATIZER, which runs
an adaptive version of the binary-tree mechanism for each count
$N_{h}^{k}(s,a),R_{h}^{k}(s,a),N_{h}^{k}(s,a,s^{\prime})$, i.e., it uses
$2SAH+S^{2}AH$ counters in total. In Algorithm 2 of Appendix we provide the
details of the mechanism. In total, based on the composition theorem of DP we
have the following result.

######  Lemma 1 (Privacy and Utility Guarantees of CENTRAL-PRIVATIZER).

For any $\epsilon>0$, the CENTRAL-PRIVATIZER we mentioned above with Laplace
noise $\text{Lap}\left(\frac{6B_{k}H\log K}{\epsilon}\right)$ for
$\widetilde{R}_{h}^{k}(s,a)$ and $\text{Lap}\left(\frac{3H\log
K}{\epsilon}\right)$ for $\widetilde{N}_{h}^{k}(s,a)$ and
$\widetilde{N}_{h}^{k}(s,a,s^{\prime})$ is $\epsilon$-DP. Furthermore, for any
$\delta\in(0,1]$, it satisfies Assumption 1 with
$E_{\epsilon,\delta,1}=\frac{3H\log^{1.5}K\ln\frac{3SAT}{\delta}}{\epsilon},\quad
E_{\epsilon,\delta,k,2}=\frac{6B_{k}H\log^{1.5}K\ln\frac{3SAT}{\delta}}{\epsilon},\quad
E_{\epsilon,\delta,3}=\frac{3H\log^{1.5}K\ln\frac{3S^{2}AT}{\delta}}{\epsilon}.$

Failure of using total $\ell_{1}$ distance of all streams to get the counter
error of rewards. It is notable that our PRIVATIZER is quite different from
the previous methods in Vietri et al. (2020); Chowdhury & Zhou (2021). If we
adopt their methods then we will get larger errors. In detail, if we use their
methods, then we need to allocate or add the same noise for each episode. For
each counter, it will take the data stream
$\sigma_{h}(s,a)\in[-B_{K},B_{K}]^{K}$ as input since the $B_{k}$ is non-
decreasing on $k$, where the $j$-th entry

$\sigma_{h}^{j}(s,a):=\mathbbm{I}\\{s_{h}^{j}=s,a_{h}^{j}=a,|r_{h}^{j}|\leq
B_{N_{h}^{j}(s,a)}\\}r_{h}^{j}$ (3)

denotes whether the pair $(s,a)$ is encountered or not at step $h$ of episode
$j$ and if the pair is encountered, we will take the truncated reward.
Consider its one adjacent data stream
$\sigma_{h}^{\prime}(s,a)\in[-B_{K},B_{K}]^{K}$ which differs from
$\sigma_{h}(s,a)$ only in one entry, then we will have
$\|\sigma_{h}(s,a)-\sigma_{h}^{\prime}(s,a)\|_{1}\leq 2B_{K}$. Furthermore,
since at every episode at most $H$ state-action pairs are encountered, we
obtain
$\sum_{(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]}\left\|\sigma_{h}(s,a)-\sigma_{h}^{\prime}(s,a)\right\|_{1}\leq
2HB_{K}.$ Then we will get in each episode $k\in[K]$, we need to add noise
$\text{Lap}\left(\frac{6B_{K}H\log K}{\epsilon}\right)$ which will make us get
a loose error bound for reward count as in Lemma 1 we just need
$\text{Lap}(\frac{6B_{k}H\log K}{\epsilon})$ with $k\leq K$.

Based on the Billboard lemma in Hsu et al. (2016), the composition of all $K$
episodes satisfies $\epsilon$-JDP if the policy $\pi^{k}$ is computed with an
$\epsilon$-DP mechanism for all $k\in[K]$.

######  Theorem 1.

For any $\epsilon>0$, Algorithm 1 is $\epsilon$-JDP if we use the CENTRAL-
PRIVATIZER in Lemma 1.

In the following, we will show the regret bound of our algorithm in the JDP
model.

######  Theorem 2 (Regret Bound for Private-Heavy-UCBVI in JDP).

For any $\epsilon\in(0,1]$ and $\delta\in(0,1]$ and take
$B_{n}=\left(\frac{\epsilon
un}{H\log^{1.5}K\log(3SAT/\delta)}\right)^{\frac{1}{1+v}}$ in (1). Then if we
use the CENTRAL-PRIVATIZER in Lemma 1, with probability $1-\delta$ the regret
of Private-Heavy-UCBVI is upper bounded by

$\widetilde{O}\left(\sqrt{SAH^{3}T}+\frac{S^{2}AH^{3}}{\epsilon}+u^{\frac{1}{1+v}}\left(\frac{SAH^{2}}{\epsilon}\right)^{\frac{v}{1+v}}T^{\frac{1}{1+v}}\right).$

######  Remark 1.

In the above bound, there are three terms. The first one corresponds to regret
due to the uncertainty in transition probabilities. The second term comes from
the estimation error of private counts and the third term is caused by the
heavy-tailed nature of rewards. Tao et al. (2022b) gives a regret rate of
$O\left(\left(\frac{A\log
T}{\epsilon}\right)^{\frac{v}{1+v}}T^{\frac{1}{1+v}}\right)$ for private
heavy-tailed MAB in the DP model where there are no transition probabilities
and counts and $S=H=1$. Thus, our regret in JDP matches their bound in DP.

In the non-private case of our problem, Zhuang & Sui (2021) establishes a
regret bound of
$\widetilde{O}(\sqrt{H^{3}SAT}+H^{2}(SA)^{\frac{v}{1+v}}T^{\frac{1}{1+v}}+\sqrt{H^{9}S^{3}A^{3}}+\sqrt{H^{\frac{1+4v}{v}}S^{2}A^{2}}+H^{\frac{1+3v}{v}}\sqrt{S^{3}A^{3}})$
by proposing the Heavy-Q-Learning with UCB-Bernstein algorithm. Compared with
it, we can see the price of privacy is an additional factor of
$\frac{1}{\epsilon}$ for private counts and
$\left(\frac{1}{\epsilon}\right)^{\frac{v}{1+v}}$ for private estimation of
heavy-tailed reward distributions. Besides, for the terms related to heavy-
tailed distributions estimation , the dependency on $H$ is better in our bound
by a factor of $H^{\frac{2}{1+v}}$ ($H^{\frac{2v}{1+v}}$ v.s. $H^{2}$).

Compared with the result of
$\widetilde{O}\left(\sqrt{SAH^{3}T}+\frac{S^{2}AH^{3}}{\epsilon}\right)$ given
by Chowdhury & Zhou (2021) for private MDPs with bounded rewards in JDP, we
can see there is an additional term due to the assumption of the heavy-tailed
reward in our problem. This is because Chowdhury & Zhou (2021) assumes the
rewards are in $[0,1]$ so that these rewards have the same sensitivity as
counts. Hence, the regret corresponding to estimating the mean of heavy-tailed
rewards is also bounded by ${S^{2}AH^{3}}/{\epsilon}$. Compared with the
regret bound of $\widetilde{O}(\sqrt{SAH^{2}T}+S^{2}AH^{3}/\epsilon)$ given by
Qiao & Wang (2023) under JDP by adopting DP-UCBVI for bounded rewards, the
difference of the first term comes from the type of bonus since Qiao & Wang
(2023) adopts Bernstein type but we use Hoeffding type. And the additional
third term in our bound is due to the heavy-tailed nature of the rewards.

###  3.2 Heavy-tailed Value-iteration in LDP

Next, we consider the LDP case. We first introduce its corresponding
PRIVATIZER, namely LOCAL-PRIVATIZER. For each episode $k$, LOCAL-PRIVATIZER
releases the private counts by injecting Laplace noise into each data stream.
At each episode $j$, given privacy parameter $\epsilon^{\prime}>0$, LOCAL-
PRIVATIZER perturbs each entry $\sigma_{h}^{j}(s,a)$ of the data stream
$\sigma_{h}(s,a)$ with an independent Laplace noise
$\text{Lap}(\frac{1}{\epsilon^{\prime}})$, i.e.,
$\widetilde{\sigma}_{h}^{j}(s,a)=\sigma_{h}^{j}(s,a)+\text{Lap}(\frac{1}{\epsilon^{\prime}})$,
where $\sigma_{h}^{j}(s,a)$ is in (3). The private counts for the $k$-th
episode are computed as
$\widetilde{N}_{h}^{k}(s,a)=\sum_{j=1}^{k-1}\widetilde{\sigma}_{h}^{j}(s,a)$.
The private counts corresponding to empirical rewards $R_{h}^{k}(s,a)$ and
state transitions $N_{h}^{k}(s,a,s^{\prime})$ are computed similarly. On the
one hand, for $N_{h}^{k}(s,a)$ with a fixed episode $k\in[K]$, we run $SAH$
parallel private counters, one for each tuple $(s,a,h)$. Thus, from the DP
parallel Lemma (Lemma 3), if we want to guarantee the privacy mechanism
satisfying $\epsilon/3$-LDP for all $\widetilde{N}_{h}^{k}(s,a)$, we just need
to make every $\widetilde{N}_{h}^{k}(s,a)$ be $\epsilon/3$-LDP. On the other
hand, at each episode at most $H$ state-action pairs are encountered, so
according to the composition theorem (Lemma 4), we need to guarantee
$\widetilde{\sigma}_{h}^{j}(s,a)$ is $\frac{\epsilon}{3H}$-LDP at each step
$h$. Then from the Laplacian mechanism, we use independent noise
$\text{Lap}(\frac{3H}{\epsilon})$ in $N_{h}^{k}(s,a)$ and
$N_{h}^{k}(s,a,s^{\prime})$. Similarly we set independent noise as
$\text{Lap}(\frac{6HB_{j}}{\epsilon})$ to protect the privacy of
$R_{h}^{k}(s,a)$. Based on the concentration property of Laplacian
distributions (Lemma 10), we can get the following error bounds for counts
under LOCAL-PRIVATIZER.

######  Lemma 2 (Privacy and utility guarantees of LOCAL-PRIVATIZER).

For any $\epsilon\in(0,1]$, the LOCAL-PRIVATIZER above is $\epsilon$-LDP.
Furthermore, for any $\delta\in(0,1]$, it satisfies Assumption 1 with
$E_{\epsilon,\delta,1}=\frac{6H}{\epsilon}\sqrt{K\log\frac{6SAT}{\delta}},E_{\epsilon,\delta,k,2}=\frac{12HB_{k}}{\epsilon}\sqrt{k\log\frac{6SAT}{\delta}},E_{\epsilon,\delta,3}=\frac{6H}{\epsilon}\sqrt{K\log\frac{6S^{2}AT}{\delta}}$

######  Remark 2.

Compared with the errors of private counts under JDP which depend on $\log K$
in Lemma 1, the above errors under LDP depend on polynomial of $K$. The reason
is that in the LDP model, we add noise to the data of each user, so we add
more noise in total than it in the JDP model to guarantee stronger privacy.

######  Theorem 3 (Regret Bound for Private-Heavy-UCBVI in LDP).

For any $\epsilon\in(0,1]$ and $\delta\in(0,1]$ and take
$B_{n}=\left(\frac{u\epsilon\sqrt{n}}{H\log(6SAT/\delta)}\right)^{\frac{1}{1+v}}$
in equation (1). Then if we use the LOCAL-PRIVATIZER in Lemma 2, with
probability $1-\delta$ the regret $Reg(T)$ of Private-Heavy-UCBVI satisfies

$\widetilde{O}\left(\sqrt{SAH^{3}T}+\frac{S^{2}A\sqrt{H^{5}T}}{\epsilon}+u^{\frac{1}{(1+v)}}\left(\frac{H^{3}SA}{\epsilon^{2}}\right)^{\frac{v}{2(1+v)}}T^{\frac{2+v}{2(1+v)}}\right).$

######  Remark 3.

Compared with the regret bound for JDP, the differences of the second term and
the third term in the above bound for LDP come from the fact that the noise
magnitude of private count is $\log k$ for JDP while it will be $\sqrt{k}$ for
LDP. Moreover, compared with LDP heavy-tailed MAB, our bound cannot recover
the optimal rate of $O\left(\left({A\log
T}/{\epsilon^{2}}\right)^{\frac{v}{1+v}}T^{\frac{1}{1+v}}\right)$ in Tao et
al. (2022b) with $S=H=1$. This is because to achieve the optimal rate for MAB,
Tao et al. (2022b) proposes a locally private and robust version of the
successive elimination algorithm while we use UCB-based method for our LDP
case. Since the key ideas of these algorithms are quite different, we cannot
adopt successive elimination methods for RL problems directly because of the
existence of transition probabilities and states. We may get some regret
bounds that match the optimal rate in LDP heavy-tailed MAB by using some
variants of the UCB method, and we leave it as an open problem. Compared with
the bound of
$\widetilde{O}\left(\sqrt{SAH^{2}T}+S^{2}A\sqrt{H^{5}T}/\epsilon\right)$
provided by Qiao & Wang (2023) under LDP based on value iteration method for
bounded rewards case, except for the difference in the first term as in JDP,
the third term is different due to heavy-tailed rewards and the noise
magnitude of private count is $\sqrt{k}$ for LDP.

##  4 Private Policy Optimization for Heavy-tailed Rewards

In the previous section, we proposed a value-iteration-based framework for
private heavy-tailed MDPs. However, in our algorithm, the value iteration
function runs through all possible actions to find the maximum action value,
i.e., Algorithm 1 is computationally heavy. In the non-private MDPs with
bounded/sub-Gaussian rewards case, it is well known that policy optimization
(PO) based algorithms proposed by Pashenkova et al. (1996) are more efficient
than the value iteration based ones from the computational perspective. And
due to this, in practice, researchers are more willing to use PO-based
algorithms. Thus, a natural question is whether we can design some private PO-
based algorithm for MDPs with heavy-tailed rewards. In this section, we give
an affirmative answer to the question by proposing a policy-optimization-based
framework, namely Private-Heavy-UCBPO, for private MDPs with heavy-tailed
rewards. See Algorithm 3 for details.

The key idea of Private-Heavy-UCBPO is that we start by choosing a policy
$\pi^{1}$ from the uniform distribution and then we iteratively evaluate and
improve the policy. In the policy evaluation stage, we use the UCB framework
to compute a $Q$-function estimation where we use the estimation errors of
private empirical reward means and private empirical transition probabilities
as the exploration bonus, which is similar to Algorithm 1. Then based on
Bellman expectation equation, we compute the corresponding value function at
step 11. Next, we roll out a new trajectory by acting the policy and receive
the private sum of truncated rewards and private counts from the same
PRIVATIZER as in Algorithm 1. Finally, in the policy improvement stage, we
update the policy by leveraging a standard mirror-descent step.

Similar to the previous section, we will show the regrets for Algorithm 3 in
JDP and LDP models, respectively.

######  Theorem 4.

Given $\epsilon>0$, by using the same CENTRAL-PRIVATIZER (LOCAL-PRIVATIZER) as
in Lemma 1 (Lemma 2), Algorithm 3 is $\epsilon$-JDP ($\epsilon$-LDP).

######  Theorem 5 (Regret bound of Private-Heavy-UCBPO in JDP).

Fix any $\epsilon\in(0,1]$ and $\delta\in(0,1]$ and set $\eta=\sqrt{2\log
A/(\tau^{2}H^{2}K)}$ and take $B_{n}=\left(\frac{\epsilon
un}{H\log^{1.5}K\log(3SAT/\delta)}\right)^{\frac{1}{1+v}}$ in equation (1).
Then, if we use the CENTRAL-PRIVATIZER in Lemma 1, with probability at least
$1-\delta$, the cumulative regret of Private-Heavy-UCBPO (Algorithm 3) is
upper bounded by

$\widetilde{O}\left(\sqrt{S^{2}AH^{3}T}+\frac{S^{2}AH^{3}}{\epsilon}+u^{\frac{1}{1+v}}\left(\frac{SAH^{2}}{\epsilon}\right)^{\frac{v}{1+v}}T^{\frac{1}{1+v}}\right).$

######  Theorem 6 (Regret bound of Private-Heavy-UCBPO in LDP).

Fix any $\epsilon\in(0,1]$, $\delta\in(0,1]$ and set $\eta=\sqrt{2\log
A/(\tau^{2}H^{2}K)}$. Take
$B_{n}=\left(\frac{u\epsilon\sqrt{n}}{H\log(6SAT/\delta)}\right)^{\frac{1}{1+v}}$
in (1). Then if we use the same LOCAL-PRIVATIZER as in Lemma 2, with
probability at least $1-\delta$, the cumulative regret of Private-Heavy-UCBPO
(Algorithm 3) is upper bounded by

$\widetilde{O}\left(\sqrt{S^{2}AH^{3}T}+\frac{S^{2}A\sqrt{H^{5}T}}{\epsilon}+u^{\frac{1}{1+v}}\left(\frac{H^{3}SA}{\epsilon^{2}}\right)^{\frac{v}{2(1+v)}}T^{\frac{2+v}{2(1+v)}}\right).$

Compared with the regret bounds of Private-Heavy-UCBVI, there is an additional
factor of $\sqrt{S}$ in the leading privacy-independent term in the bounds of
Private-Heavy-UCBPO. This follows the same pattern as in private bounded MDPs
case (Chowdhury & Zhou, 2021). Actually, there is no previous policy-
optimization-based algorithm, even for non-private heavy-tailed MDPs.
Therefore, our proof techniques (such as the results of Lemma 21 in Appendix)
can be considered as byproducts that can be used to design policy-
optimization-based algorithms for non-private heavy-tailed RL problems.

##  5 Lower Bounds

###  5.1 Regret Lower Bound under JDP

We first focus on establishing a lower bound on the regret for heavy-tailed
MDPs under JDP constraint. In the literature, a common approach for proving
lower bounds in RL is via a reduction to MAB. However, in our setting, two
challenges will arise when we adopt the above approach. First, the regret of
our problem corresponds to the instance-independent regret in MAB.
Unfortunately, there is no existing private minimax (instance-independent)
regret lower bound for heavy-tailed MAB in the central DP model. In fact, such
a lower bound is listed as an open problem in Tao et al. (2022b). Second, in
the private case, the reduction from RL to MAB needs additional care. This is
due to the difference in privacy definition, i.e., JDP for RL and DP for MAB.
In other words, even if one has established a regret lower bound for MAB in
the central DP model, it cannot be directly used to establish a lower bound
for RL in JDP.

To address the aforementioned challenges, we take the following steps in this
section. First, we establish the first private minimax lower bound for heavy-
tailed MAB in central DP, hence resolving the open problem in Tao et al.
(2022b). The key step behind this result is a _private_ version of KL-
divergence for the hard instances. Then, to tackle the second challenge, we
use the notion called JDP with _public_ initial state as a bridge between the
classic JDP for RL and DP for MAB, which allows us to build upon our lower
bound for MAB under DP to establish the lower bound for RL in JDP. Here we
only show our intuition for overcoming the first challenge and our hard
instances for heavy-tailed MDPs. See Appendix 5 for the details of overcoming
the second challenge.

We now start with the MAB lower bound. In particular, we consider the agent
interacts with the environment sequentially for $K$ rounds. The agent is faced
with a set of $A$ independent arms $\\{1,\dots,A\\}$. In each round $k\in K$,
the agent selects an arm $a_{k}\in[A]$ to pull and obtains a reward that is
drawn i.i.d. from a fixed but unknown heavy-tailed distribution associated
with the chosen arm.

######  Definition 3 (Differential Privacy (DP) for MAB (Vietri et al.,
2020)).

For any $\epsilon\geq 0$, a mechanism
$\mathcal{M}:\mathcal{U}^{K}\rightarrow\mathcal{A}^{K}$ is $\epsilon$-DP if
for all user sequences $U_{K},U_{K}^{\prime}\in\mathcal{U}^{K}$ differing only
in a single user and for all events $E\subset\mathcal{A}^{K}$,we have
$\mathbb{P}\left[\mathcal{M}{\left(U_{K}\right)\in E}\right]\leq
e^{\varepsilon}\mathbb{P}\left[\mathcal{M}\left(U_{K}^{\prime}\right)\in
E\right].$

######  Theorem 7 (Instance-independent Lower Bound for DP Heavy-tailed MAB).

There exists a heavy-tailed $A$-armed bandit instance with the $(1+v)$-th
bounded moment of each reward distribution is bounded by 1. Moreover, if $K$
is large enough, for any $\epsilon$-DP algorithm $\mathcal{M}$ with
$\epsilon\in(0,1]$, the expected regret must satisfy

${Reg}_{K}\geq\Omega\left(\left(A/\epsilon\right)^{\frac{v}{1+v}}K^{\frac{1}{1+v}}\right).$

######  Remark 4.

Tao et al. (2022b) gives an instance-independent upper bound of
$O\left(\left({A\log
K}/{\epsilon}\right)^{\frac{v}{1+v}}K^{\frac{1}{1+v}}\right)$ for heavy-tailed
MAB in central DP by proposing a private and robust version of the successive
elimination algorithm. Our above lower bound almost matches the upper bound up
to a factor of $(\log K)^{\frac{v}{1+v}}$. Thus, the above lower bound is
already near optimal.

Now, inspired by (Vietri et al., 2020), we construct hard instances for MDPs
as depicted in Figure 1. Within the class of MDPs, state space is denoted as
$\mathcal{S}:=[n]\cup\\{+,-\\}$ and action space is denoted as
$\mathcal{A}:=[m]$. During each episode, the agent initiates from one of the
initial states, randomly selected with equal probability from the set. Now, we
construct hard instances for MDPs as depicted in Figure 1. Within the class of
MDPs, state space is denoted as $\mathcal{S}:=[n]\cup\\{+,-\\}$ and action
space is denoted as $\mathcal{A}:=[m]$. During each episode, the agent
initiates from one of the initial states, randomly selected with equal
probability from the set. For each initial state, the agent faces $m$
potential actions, and transitions can only lead it to either of the two
terminal states, $\\{+,-\\}$.

Figure 1: Hard MDP instance for JDP model

Such an instance can be regarded as the composition of $n$ parallel MAB
instances. The transition probabilities between the initial state
$s\in\\{1,\dots,n\\}$ and the absorbing states $\\{+,-\\}$ are determined by
each instance of the MAB. We assign an index to each MAB instance based on its
optimal arm (or action) $I_{s}\in\\{1,\dots,m\\}$ within each initial state.
Then we transfer the randomness of the Bernoulli reward distribution in the
MAB to transition probabilities in the MDP. Therefore, based on the instances
for proof of Theorem 7, we define the transition probabilities in Figure 1
such that in the MAB instance where the optimal arm $I_{s}=1$, we have
$P(+|s,1)=\frac{5}{10}\gamma^{1+v},\ P(-|s,1)=1-P(+|s,1)$ and
$P(+|s,a)=\frac{3}{10}\gamma^{1+v},\ P(-|s,a)=1-P(+|s,a)\ \text{for}\ a\neq
1.$ And for the MAB instance with $I_{s}\neq 1$, we have similar transition
probabilities as above except the $I_{s}$-th arm, i.e.,
$P(+|s,I_{s})=\frac{7}{10}\gamma^{1+v},\ P(-|s,I_{s})=1-P(+|s,I_{s}),$ where
$\gamma>0$ is a parameter to be determined later. Every action which transits
to state $+$ provides reward $1/\gamma$ while actions transitioning to state
$-$ provide reward $0$.

Based on all the above results and instances, now we have our main theorem.

######  Theorem 8 (JDP Regret Lower Bound for Heavy-tailed MDPs).

For any $\epsilon$-JDP algorithm $\mathcal{M}$ there exists a heavy-tailed MDP
with $S$ states and $A$ actions over $H(=1)$ time steps per episode such that
for any initial state $s\in\mathcal{S}$ the expected regret of $\mathcal{M}$
after $K$ episodes satisfies

$Reg(T)\geq\Omega\left(\left(SA/\epsilon\right)^{\frac{v}{1+v}}K^{\frac{1}{1+v}}\right).$

######  Remark 5.

For episodic MDPs in JDP model with bounded rewards, the regret lower bound is
$\Omega\left(\sqrt{HSAK}+{SAH\log K}/{\epsilon}\right)$ (Vietri et al., 2020),
where the additional term of $\Omega\left({SAH\log K}/{\epsilon}\right)$ is
the price of privacy compared with the non-private case. However, in the case
of the heavy-tailed reward, the lower bound in the above theorem shows that
the price to pay for JDP is a factor of
$\left(\frac{1}{\epsilon}\right)^{\frac{v}{1+v}}$ compared with the lower
bound in the non-private case (Zhuang & Sui, 2021). Our above lower bound also
matches the error due to private estimation for heavy-tailed distributions in
our upper bounds (the third term of the result in Theorem 2 and the third term
of the result in Theorem 5) for JDP model on parameters $\epsilon,S,A,K$. It
is also notable that here we only present the lower bound for JDP MDPs with
heavy-tailed rewards under the case where there is just one step in each
episode. For the multiple-step MDPs with heavy-tailed rewards case, the lower
bound is more challenging. We leave the problem of tight lower bound for
multiple-step MDPs with heavy-tailed rewards in JDP model as an open problem.

###  5.2  Regret Lower Bound under LDP

Unlike the techniques in the JDP case which make a reduction from MDPs to MAB,
here we can directly construct an instance of MDPs to get the lower bound.

Inspired by (Garcelon et al., 2021), we construct the following MDP instance
for a given number of states $S$ and actions $A$. Such MDP instance can be
represented by a tree whose root is the initial state $0$ with $A$ actions
that deterministically lead to the next state. Moreover, each node in the tree
has $A$ children and there are exactly $S-2$ states, excluding terminal
states. The leaves of the tree, denoted as $\mathcal{L}={x_{1},\dots,x_{L}}$,
represent the set of possible transitions from the intermediate states to two
terminal states, labeled as $+$ and $-$. At the terminal states, the agent
will receive the reward of $1/\gamma$ and $0$, respectively, where $\gamma>0$
is a parameter to be determined later. The tree without nodes $+$ and $-$ is a
perfect $A$-ary tree. We show the instance with $S=15$ and $A=3$ in Figure 2
as an example.

Figure 2: Hard MDP instance for LDP model

Assume $d>0$ represents the depth of the tree where the depth of the tree with
$S-2$ nodes is $d-1$ and nodes $+,-$ are located at depth $d$. Without loss of
generality, we assume that all leaves, $x_{1},\dots,x_{L}$, are positioned at
depth $d-1$, implying that the number of leaves satisfies
$L=A^{d-1}\geq(S-2)/2$. Furthermore, we make the assumption that $H=d+1$. That
means once the agent arrives at $+$ or $-$, it arrives at the end of the
episode. Next, we provide the distributions for these leaves.

We assume there exists a unique action $a^{*}$ and leaf $x_{i^{*}}$ such that:
$P(+|x_{i^{*}},a^{*})=\gamma^{1+v}\ \text{and}\
P(-|x_{i^{*}},a^{*})=1-\gamma^{1+v}.$ where $\gamma^{1+v}\in(0,\frac{3}{4}]$.
Each of the other leaves has a transition probability
$P(+|x_{i},a)=\frac{1}{2}\gamma^{1+v}\ \text{and}\
P(-|x_{i},a)=1-\frac{1}{2}\gamma^{1+v}.$ We denote above instance by
$\mathbb{P}_{(x_{i^{*}},a^{*})}$. In order to get the regret lower bound, we
also consider another instance $\mathbb{P}_{0}$ where for all leaf states and
any action, the transition probabilities are
$P(+|x_{i},a)=\frac{1}{2}\gamma^{1+v}\ \text{and}\
P(-|x_{i},a)=1-\frac{1}{2}\gamma^{1+v}.$ Based on the above instances, we
provide a lower bound on the regret for our problem.

######  Theorem 9 (LDP Regret Lower Bound).

For any $\epsilon$-LDP algorithm $\mathcal{M}$ where $\epsilon\in(0,1]$, there
exists a heavy-tailed MDP instance with $S(\geq 3)$ states, $A(\geq 2)$
actions and one-step heavy-tailed reward per episode such that the expected
regret of $\mathcal{M}$ after $K$ episodes is

$Reg(T)\geq\Omega\left(\left(SA/\epsilon^{2}\right)^{\frac{v}{1+v}}K^{\frac{1}{1+v}}\right).$

######  Remark 6.

Compared with the lower bound of
$\Omega\left(\frac{H\sqrt{SAK}}{\min\\{e^{\epsilon}-1,1\\}}\right)$ for the
bounded case in Garcelon et al. (2021), we can see the price of privacy in the
heavy-tailed case is a factor of
$\left(\frac{1}{\epsilon^{2}}\right)^{\frac{v}{1+v}}$. When $v=1$ and $H=1$,
our lower bound can recover the lower bound of the bounded case. Compared with
the optimal instance-independent lower bound of
$\Omega\left(\left({A}/{\epsilon^{2}}\right)^{\frac{v}{1+v}}K^{\frac{1}{1+v}}\right)$
for heavy-tailed MAB in LDP model given by Tao et al. (2022b), our above lower
bound with $S=1$ can also recover the result.

##  6 Conclusion and Future Work

In this work, we provided the first study on finite horizon Markov decision
processes (MDPs) with heavy-tailed rewards in both joint (JDP) and local
differential privacy (LDP) models. We mainly focused on the case where the
reward distributions have only finite $(1+v)$-th raw moment for $v\in(0,1]$.
We first proposed a private and robust version of both UCB-based value-
iteration and policy-optimization algorithms. To guarantee privacy, we adopted
the adaptive Tree-based mechanism for JDP and the Laplacian mechanism for LDP.
Based on the algorithm, we established regret bounds for both JDP and LDP
cases. Finally, we established lower bounds for finite-horizon MDPs with
heavy-tailed rewards in both JDP and LDP models. Through these results, we
also found some differences between our problem and the problem of private
MDPs with bounded rewards and some differences between our problem and the
problem in the non-private case. All of our ideas, techniques, and frameworks
can also potentially be applied to other related private reinforcement
learning problems.

There are still some open problems left. First of all, in the whole paper, we
assume the parameters $u$ and $v$ are known in advance, but how to deal with
the case where $u$ and $v$ are unknown which is a more practical situation in
the real world. Secondly, the order of $T$ is $\frac{2+v}{2(1+v)}$ in our
regret upper bound under the LDP model, which is larger than the order of
$\frac{1}{1+v}$ in our lower bound for the problem under LDP. Thus, can we
further close the gap between these two bounds by designing other algorithms?
Finally, in this paper, while we mainly focus on the finite-horizon problem,
we proposed some private mean estimators and some new hard instances to prove
the lower bounds. Can we extend these techniques and ideas to other related
problems such as private MDPs with finite diameters with heavy-tailed rewards
or some model-free reinforcement learning problems?

## Acknowledgments

Yulian Wu and Di Wang are supported in part by BAS/1/1689-01-01,
URF/1/4663-01-01, FCC/1/1976-49-01 of King Abdullah University of Science and
Technology (KAUST). Di Wang is also supported by the funding of the SDAIA-
KAUST Center of Excellence in Data Science and Artificial Intelligence (SDAIA-
KAUST AI). Xingyu Zhou is supported in part by NSF CNS-2153220.

## References

  * Afsar et al. (2022) Afsar, M. M., Crump, T., and Far, B.  Reinforcement learning based recommender systems: A survey.  _ACM Computing Surveys_ , 55(7):1–38, 2022.
  * Agarwal et al. (2019) Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W.  Reinforcement learning: Theory and algorithms.  _CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep_ , pp. 10–4, 2019.
  * Agrawal et al. (2020) Agrawal, S., Juneja, S., and Glynn, P.  Optimal $\delta$-correct best-arm selection for heavy-tailed distributions.  In _Proceedings of the 31st International Conference on Algorithmic Learning Theory (ALT)_ , pp. 61–110, 2020.
  * Agrawal et al. (2021) Agrawal, S., Juneja, S., and Koolen, W. M.  Regret minimization in heavy-tailed bandits.  In _Proceedings of 34th Conference on Learning Theory (COLT)_ , pp. 26–62, 2021.
  * Azar et al. (2017) Azar, M. G., Osband, I., and Munos, R.  Minimax regret bounds for reinforcement learning.  In _International Conference on Machine Learning_ , pp. 263–272. PMLR, 2017.
  * Azize & Basu (2022) Azize, A. and Basu, D.  When privacy meets partial information: A refined analysis of differentially private bandits, 2022.  URL https://arxiv.org/abs/2209.02570.
  * Barber & Duchi (2014) Barber, R. F. and Duchi, J. C.  Privacy and statistical risk: Formalisms and minimax bounds.  _arXiv preprint arXiv:1412.4451_ , 2014.
  * Bellman (1957) Bellman, R.  Dynamic programming.  _Princeton, USA: Princeton University Press_ , 1(2):3, 1957.
  * Beutler (1989) Beutler, F. J.  Dynamic programming: Deterministic and stochastic models (dimitri p. bertsekas).  _SIAM Review_ , 31(1):132, 1989.
  * Brunel & Avella-Medina (2020) Brunel, V.-E. and Avella-Medina, M.  Propose, test, release: Differentially private estimation with high probability.  _arXiv preprint arXiv:2002.08774_ , 2020.
  * Bubeck et al. (2013) Bubeck, S., Cesa-Bianchi, N., and Lugosi, G.  Bandits with heavy tail.  _IEEE Transactions on Information Theory_ , 59(11):7711–7717, 2013.
  * Celma & Celma (2010) Celma, Ò. and Celma, Ò.  The long tail in recommender systems.  _Music Recommendation and Discovery: The Long Tail, Long Fail, and Long Play in the Digital Music Space_ , pp. 87–107, 2010.
  * Chan et al. (2011) Chan, T.-H. H., Shi, E., and Song, D.  Private and continual release of statistics.  _ACM Transactions on Information and System Security (TISSEC)_ , 14(3):1–24, 2011.
  * Chen et al. (2019) Chen, M., Beutel, A., Covington, P., Jain, S., Belletti, F., and Chi, E. H.  Top-k off-policy correction for a reinforce recommender system.  In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_ , pp. 456–464, 2019.
  * Chen et al. (2021) Chen, X., Miao, S., and Wang, Y.  Differential privacy in personalized pricing with nonparametric demand models.  _arXiv preprint arXiv:2109.04615_ , 2021.
  * Chowdhury & Zhou (2021) Chowdhury, S. R. and Zhou, X.  Differentially private regret minimization in episodic markov decision processes.  _arXiv preprint arXiv:2112.10599_ , 2021.
  * Chowdhury & Zhou (2022a) Chowdhury, S. R. and Zhou, X.  Distributed differential privacy in multi-armed bandits.  _arXiv preprint arXiv:2206.05772_ , 2022a.
  * Chowdhury & Zhou (2022b) Chowdhury, S. R. and Zhou, X.  Shuffle private linear contextual bandits.  _arXiv preprint arXiv:2202.05567_ , 2022b.
  * Das et al. (2021) Das, S., Gutzwiller, R. S., Roscoe, R. D., Rajivan, P., Wang, Y., Camp, L. J., and Hoyle, R.  Panel: Humans and technology for inclusive privacy and security.  _arXiv preprint arXiv:2101.07377_ , 2021.
  * Domingues et al. (2021) Domingues, O. D., Ménard, P., Kaufmann, E., and Valko, M.  Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited.  In _Algorithmic Learning Theory_ , pp. 578–598. PMLR, 2021.
  * Dubey (2021) Dubey, A.  No-regret algorithms for private gaussian process bandit optimization.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 2062–2070. PMLR, 2021.
  * Duchi et al. (2013) Duchi, J. C., Jordan, M. I., and Wainwright, M. J.  Local privacy and statistical minimax rates.  In _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_ , pp. 429–438. IEEE, 2013.
  * Dwork et al. (2006) Dwork, C., McSherry, F., Nissim, K., and Smith, A.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_ , pp. 265–284. Springer, 2006.
  * Dwork et al. (2014) Dwork, C., Roth, A., et al.  The algorithmic foundations of differential privacy.  _Found. Trends Theor. Comput. Sci._ , 9(3-4):211–407, 2014.
  * Garcelon et al. (2021) Garcelon, E., Perchet, V., Pike-Burke, C., and Pirotta, M.  Local differential privacy for regret minimization in reinforcement learning.  _Advances in Neural Information Processing Systems_ , 34:10561–10573, 2021.
  * Garivier et al. (2019) Garivier, A., Ménard, P., and Stoltz, G.  Explore first, exploit next: The true shape of regret in bandit problems.  _Mathematics of Operations Research_ , 44(2):377–399, 2019.
  * Gottesman et al. (2019) Gottesman, O., Johansson, F., Komorowski, M., Faisal, A., Sontag, D., Doshi-Velez, F., and Celi, L. A.  Guidelines for reinforcement learning in healthcare.  _Nature medicine_ , 25(1):16–18, 2019.
  * Hsu et al. (2016) Hsu, J., Huang, Z., Roth, A., Roughgarden, T., and Wu, Z. S.  Private matchings and allocations.  _SIAM Journal on Computing_ , 45(6):1953–1984, 2016.
  * Hu et al. (2022) Hu, L., Ni, S., Xiao, H., and Wang, D.  High dimensional differentially private stochastic optimization with heavy-tailed data.  In _Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_ , pp. 227–236, 2022.
  * Ibragimov et al. (2015) Ibragimov, M., Ibragimov, R., and Walden, J.  _Heavy-tailed distributions and robustness in economics and finance_ , volume 214.  Springer, 2015.
  * Jain et al. (2012) Jain, P., Kothari, P., and Thakurta, A.  Differentially private online learning.  In _Conference on Learning Theory_ , pp. 24–1. JMLR Workshop and Conference Proceedings, 2012.
  * Jin et al. (2020) Jin, C., Jin, T., Luo, H., Sra, S., and Yu, T.  Learning adversarial markov decision processes with bandit feedback and unknown transition.  In _International Conference on Machine Learning_ , pp. 4860–4869. PMLR, 2020.
  * Jin et al. (2022) Jin, C., Zhou, K., Han, B., Cheng, J., and Yang, M.-C.  Efficient private sco for heavy-tailed data via clipping.  _arXiv preprint arXiv:2206.13011_ , 2022.
  * Kamath et al. (2020) Kamath, G., Singhal, V., and Ullman, J.  Private mean estimation of heavy-tailed distributions.  In _Proceedings of 33rd Conference on Learning Theory (COLT)_ , pp. 2204–2235, 2020.
  * Kamath et al. (2022) Kamath, G., Liu, X., and Zhang, H.  Improved rates for differentially private stochastic convex optimization with heavy-tailed data.  In _International Conference on Machine Learning_ , pp. 10633–10660. PMLR, 2022.
  * Kearns et al. (2014) Kearns, M., Pai, M., Roth, A., and Ullman, J.  Mechanism design in large games: Incentives and privacy.  In _Proceedings of the 5th conference on Innovations in theoretical computer science_ , pp. 403–410, 2014.
  * Lattimore (2017) Lattimore, T.  A scale free algorithm for stochastic bandits with bounded kurtosis.  In _Proceedings of the 31st Conference on Advances in Neural Information Processing Systems (NeurIPS)_ , pp. 1583–1592, 2017.
  * Lattimore & Szepesvári (2020) Lattimore, T. and Szepesvári, C.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Lee et al. (2020) Lee, K., Yang, H., Lim, S., and Oh, S.  Optimal algorithms for stochastic multi-armed bandits with heavy tailed rewards.  In _Proceedings of the 34th Conference on Advances in Neural Information Processing Systems (NeurIPS)_ , 2020.
  * Lei et al. (2020) Lei, Y. M., Miao, S., and Momot, R.  Privacy-preserving personalized revenue management.  _HEC Paris Research Paper No. MOSI-2020-1391_ , 2020.
  * Li et al. (2022) Li, F., Zhou, X., and Ji, B.  Differentially private linear bandits with partial distributed feedback.  In _2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt)_ , pp. 41–48. IEEE, 2022.
  * Li et al. (2023) Li, F., Zhou, X., and Ji, B.  (private) kernelized bandits with distributed biased feedback.  _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ , 7(1):1–47, 2023.
  * Li et al. (2019) Li, M., Qin, Z., Jiao, Y., Yang, Y., Wang, J., Wang, C., Wu, G., and Ye, J.  Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning.  In _The world wide web conference_ , pp. 983–994, 2019.
  * Li & Sun (2023) Li, X. and Sun, Q.  Variance-aware robust reinforcement learning with linear function approximation with heavy-tailed rewards.  _arXiv preprint arXiv:2303.05606_ , 2023.
  * Liao et al. (2021) Liao, C., He, J., and Gu, Q.  Locally differentially private reinforcement learning for linear mixture markov decision processes.  _arXiv preprint arXiv:2110.10133_ , 2021.
  * Liu et al. (2021) Liu, X., Kong, W., Kakade, S., and Oh, S.  Robust and differentially private mean estimation.  _arXiv preprint arXiv:2102.09159_ , 2021.
  * Mishra & Thakurta (2015) Mishra, N. and Thakurta, A.  (nearly) optimal differentially private stochastic multi-arm bandits.  In _Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence_ , pp. 592–601, 2015.
  * Orabona (2023) Orabona, F.  A modern introduction to online learning.  _arxiv.org/abs/1912.13213_ , 2023.
  * Osband et al. (2013) Osband, I., Russo, D., and Van Roy, B.  (more) efficient reinforcement learning via posterior sampling.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Pan et al. (2019) Pan, X., Wang, W., Zhang, X., Li, B., Yi, J., and Song, D.  How you act tells a lot: Privacy-leaking attack on deep reinforcement learning.  In _AAMAS_ , pp. 368–376, 2019.
  * Park & Tuzhilin (2008) Park, Y.-J. and Tuzhilin, A.  The long tail of recommender systems and how to leverage it.  In _Proceedings of the 2008 ACM conference on Recommender systems_ , pp. 11–18, 2008.
  * Pashenkova et al. (1996) Pashenkova, E., Rish, I., and Dechter, R.  Value iteration and policy iteration algorithms for markov decision problem.  In _AAAI’96: Workshop on Structural Issues in Planning and Temporal Reasoning_. Citeseer, 1996.
  * Qiao & Wang (2023) Qiao, D. and Wang, Y.-X.  Near-optimal differentially private reinforcement learning.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 9914–9940. PMLR, 2023.
  * Ren et al. (2020) Ren, W., Zhou, X., Liu, J., and Shroff, N. B.  Multi-armed bandits with local differential privacy.  _arXiv preprint arXiv:2007.03121_ , 2020.
  * Sajed & Sheffet (2019) Sajed, T. and Sheffet, O.  An optimal private stochastic-mab algorithm based on optimal private stopping rule.  In _International Conference on Machine Learning_ , pp. 5579–5588. PMLR, 2019.
  * Schluter & Trede (2008) Schluter, C. and Trede, M.  Identifying multiple outliers in heavy-tailed distributions with an application to market crashes.  _Journal of Empirical Finance_ , 15(4):700–713, 2008.
  * Shani et al. (2020) Shani, L., Efroni, Y., Rosenberg, A., and Mannor, S.  Optimistic policy optimization with bandit feedback.  In _International Conference on Machine Learning_ , pp. 8604–8613. PMLR, 2020.
  * Shariff & Sheffet (2018) Shariff, R. and Sheffet, O.  Differentially private contextual linear bandits.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Tao et al. (2022a) Tao, Y., Wu, Y., Cheng, X., and Wang, D.  Private stochastic convex optimization and sparse learning with heavy-tailed data revisited.  International Joint Conferences on Artificial Intelligence Organization, 2022a.
  * Tao et al. (2022b) Tao, Y., Wu, Y., Zhao, P., and Wang, D.  Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 1546–1574. PMLR, 2022b.
  * Vakili et al. (2013) Vakili, S., Liu, K., and Zhao, Q.  Deterministic sequencing of exploration and exploitation for multi-armed bandit problems.  _IEEE Journal of Selected Topics in Signal Processing_ , 7(5):759–767, 2013.
  * Vershynin (2018) Vershynin, R.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Vietri et al. (2020) Vietri, G., Balle, B., Krishnamurthy, A., and Wu, S.  Private reinforcement learning with pac and regret guarantees.  In _International Conference on Machine Learning_ , pp. 9754–9764. PMLR, 2020.
  * Wang & Xu (2022) Wang, D. and Xu, J.  Differentially private $\ell_{1}$-norm linear regression with heavy-tailed data.  _arXiv preprint arXiv:2201.03204_ , 2022.
  * Wang et al. (2018) Wang, D., Gaboardi, M., and Xu, J.  Empirical risk minimization in non-interactive local differential privacy revisited.  In _Proceedings of the 32nd Conference on Advances in Neural Information Processing Systems (NeurIPS)_ , 2018.
  * Wang et al. (2020) Wang, D., Xiao, H., Devadas, S., and Xu, J.  On differentially private stochastic convex optimization with heavy-tailed data.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , pp. 10081–10091, 2020.
  * Weissman et al. (2003) Weissman, T., Ordentlich, E., Seroussi, G., Verdu, S., and Weinberger, M. J.  Inequalities for the l1 deviation of the empirical distribution.  _Hewlett-Packard Labs, Tech. Rep_ , 2003.
  * Xu & Wang (2022) Xu, J. and Wang, Y.-X.  Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 9643–9662. PMLR, 2022.
  * Yu et al. (2018) Yu, X., Shao, H., Lyu, M. R., and King, I.  Pure exploration of multi-armed bandits with heavy-tailed payoffs.  In _Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence (UAI)_ , pp. 937–946, 2018.
  * Zhao et al. (2020) Zhao, W., Khosa, S. K., Ahmad, Z., Aslam, M., and Afify, A. Z.  Type-i heavy tailed family with applications in medicine, engineering and insurance.  _PloS one_ , 15(8):e0237462, 2020.
  * Zheng et al. (2020) Zheng, K., Cai, T., Huang, W., Li, Z., and Wang, L.  Locally differentially private (contextual) bandits learning.  _Advances in Neural Information Processing Systems_ , 33:12300–12310, 2020.
  * Zhou (2022) Zhou, X.  Differentially private reinforcement learning with linear function approximation.  _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ , 6(1):1–27, 2022.
  * Zhou & Tan (2021) Zhou, X. and Tan, J.  Local differential privacy for bayesian optimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 11152–11159, 2021.
  * Zhuang & Sui (2021) Zhuang, V. and Sui, Y.  No-regret reinforcement learning with heavy-tailed rewards.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 3385–3393. PMLR, 2021.
  * Zong et al. (2016) Zong, S., Ni, H., Sung, K., Ke, N. R., Wen, Z., and Kveton, B.  Cascading bandits for large-scale recommendation problems.  _arXiv preprint arXiv:1603.05359_ , 2016.

## Appendix

##  Appendix A Related work and challenges

Besides the work we mentioned above, there are other numerous previous studies
on either private RL/bandits with bounded/sub-Gaussian rewards (Sajed &
Sheffet, 2019; Liao et al., 2021; Chen et al., 2021; Lei et al., 2020; Zheng
et al., 2020; Zhou, 2022; Ren et al., 2020; Zhou & Tan, 2021; Li et al., 2022,
2023) or non-private RL/bandits with heavy-tailed rewards (Zhuang & Sui, 2021;
Bubeck et al., 2013; Lee et al., 2020; Yu et al., 2018; Lattimore, 2017;
Agrawal et al., 2021; Vakili et al., 2013; Agrawal et al., 2020; Li & Sun,
2023). In the following, we only discuss the work that is most related to
ours.

For the studies of non-private RL with heavy-tailed rewards, Bubeck et al.
(2013) first considers the finite-armed bandit problem in which the reward
distributions have only finite $(1+v)$-th moments for some $v\in(0,1]$. It
develops a robust UCB algorithm by leveraging several mean estimators for
heavy-tailed distributions, such as the truncated mean estimators and the
median of mean estimator. Leveraging techniques from these robust mean
estimators, Zhuang & Sui (2021) considers the heavy-tailed rewards in the
problem of undiscounted reinforcement learning and proposes the method of
Heavy-UCRL2 and Heavy-Q-learning for model-based and model-free settings
respectively. It also generalizes the algorithms to deep reinforcement
learning and presents Heavy-DQN as an example. Motivated by these, we use the
idea of a truncated mean estimator as the backbone in our frameworks to deal
with heavy-tailed rewards in our problem. However, as we mentioned earlier
there are several additional challenges by injecting additional noises.
Moreover, in this paper, we also propose policy-optimization-based algorithms
which have not been studied before for heavy-tailed rewards even in the non-
private case.

For private RL/bandits with heavy-tailed rewards, to the best of our
knowledge, Tao et al. (2022b) is the only one which investigates MAB with
heavy-tailed rewards in both central and local DP models. It proposes robust
versions of successive elimination (SE) algorithms for the problem in central
DP and local DP models and establishes (near) optimal rates. However, for the
problem we studied, it is unsuitable for the central DP model since several
recent works Shariff & Sheffet (2018); Dubey (2021) show that the standard DP
model is irreconcilable with sub-linear regret for contextual bandits. Thus,
we consider a relaxation of central DP, i.e., the joint differential privacy.
Besides, we cannot use an arm elimination algorithm for our problem because of
the existence of states. Since our private heavy-tailed MDPs with $H=1$ are
just the private heavy-tailed contextual bandit problem and that with
$H=1,S=1$ is a private heavy-tailed MAB problem, our problem could be
considered as a more general case. There are also some studies on private MDPs
recently. However, all of them only consider the bounded reward case and
cannot be extended to the heavy-tailed one. For example, Chowdhury & Zhou
(2021) studies DP episodic MDPs with bounded rewards and proposes policy
optimization and value iteration frameworks, and presents the regret upper
bounds for these frameworks. Motivated by these frameworks, we propose
Private-Heavy-UCBVI and Private-Heavy-UCBPO for our problem for both JDP and
LDP. However, here we cannot directly use their Tree-based mechanism for JDP
and the allocation methods for the privacy budget since the heavy-tailed
rewards are now unbounded. Besides, Garcelon et al. (2021) establishes the
lower bound of regret minimization for MDPs with bounded rewards in LDP model
by constructing some MDP examples satisfying bounded rewards. However, we
cannot directly use the MDP instance to get the regret lower bound since our
rewards are heavy-tailed with bounded $(1+v)$-th moment. See Table 1 for a
detailed comparison.

Robust and differentially private estimation has drawn much attention in
recent years. Barber & Duchi (2014) provided the first study on private mean
estimation for distributions with the bounded moment, which is extended by
Kamath et al. (2020); Liu et al. (2021); Brunel & Avella-Medina (2020)
recently. However, all of them need to assume the underlying distribution has
the second-order moment, while in this paper we only need to assume the reward
distributions have the $(1+v)$-th moment for some $v\in(0,1]$. Moreover, all
of these works only focus on the central DP model and offline setting and it
is unknown whether they could be extended to the stream setting. Thus, our
problem is more general. Besides the mean estimation problem, recently Wang et
al. (2020); Kamath et al. (2022); Jin et al. (2022); Hu et al. (2022) study
differentially private stochastic convex optimization with heavy-tailed data.
However, all of them need to assume the distribution of the gradient has the
second-order moment and cannot be used in the stream setting. Wang & Xu (2022)
studies private $\ell_{1}$-regression where the covariate $x$ has bounded
$(1+v)$-th moment. However, its method cannot be generalized to other
problems. Tao et al. (2022a) considers the differentially private stochastic
convex optimization with heavy-tailed data where the distribution of each
coordinate of the gradient has bounded $(1+v)$-th moment. However, its method
cannot be used in the online stream setting.

Challenges. Compared with the previous related work, there are additional
challenges for private MDPs with heavy-tailed rewards, which are mainly from
the following three aspects. First, in the non-private case, Zhuang & Sui
(2021) proposes methods that truncate each reward via a certain threshold.
However, due to the additional privacy constraint in our problem, we need to
be more careful in choosing the threshold, which is related to three kinds of
error: an error from truncating rewards, an error due to using a finite number
of truncated rewards to estimate heavy-tailed reward distributions and an
error due to the noise for ensuring privacy. In detail, we need to first get a
general upper bound and then based on the trade-off among these three terms of
errors we can determine the optimal threshold. However, getting such a trade-
off in general is still more difficult than in the non-private case, as here
we will have more biased estimators due to the noise we added. For example, we
need to add noise to the count of each state-action pair and this will make
empirical transition probabilities be biased. Secondly, in private MDPs with
bounded rewards case, Chowdhury & Zhou (2021) assumes that all rewards are
bounded by $1$ and it determines and allocates the noise added for each step
in an episode by using the total $\ell_{1}$ distance of all data streams.
However, we cannot adopt the same strategy as the heavy-tailed rewards now are
unbounded. The problem is still challenging even if we just adopt similar
reward-truncating based methods in some previous related work (Zhuang & Sui,
2021; Tao et al., 2022b), as the thresholds of truncated rewards are
increasing, which makes these truncated rewards not uniformly bounded.
Thirdly, in the stateless case, i.e., private heavy-tailed MAB, Tao et al.
(2022b) achieves the optimal regret rates for both central DP and local DP
models via successive elimination algorithms. However, we cannot use similar
methods in the RL setting since the states and transition probabilities can
also affect policy.

##  Appendix B Notations and Technical Lemmas

Table 2: List of Notations Notations | Descriptions
---|---
$\mathcal{S}$ | state space with cardinality $S$
$\mathcal{A}$ | action space with cardinality $A$
$\Pi$ | set of all non-stationary policies
$K$ | number of episodes
$H$ | episode length
$P_{h}$ | transition kernel at step $h$
$r_{h}$ | mean of the reward distribution at step $h$
$\pi_{h}$ | policy at step $h$
$s_{h}^{k}$ | state at episode $k$ and step $h$
$a_{h}^{k}$ | the action taken by agent at episode $k$ and step $h$
$r_{h}^{k}$ | random reward at episode $k$ and step $h$
$V_{h}^{\pi}(s)$ | value function of a state $s$ under policy $\pi$ at step $h$
$V_{h}^{*}(s)$ | optimal value function
$Q_{h}^{\pi}(s,a)$ | Q-function of taking action $a$ in state $s$ under policy $\pi$ at step $h$
$\pi^{*}$ | optimal policy
$\mathcal{R}_{h}(s,a)$ | reward distribution for state-action pair $(s,a)$ at step $h$
$T$ |  $T=KH$ is the total number of steps
$N_{h}^{k}(s,a)$ | count of visiting state-action pair $(s,a)$ at step $h$ before episode $k$
$N_{h}^{k}(s,a,s^{\prime})$ | count of going to state $s^{\prime}$ from $s$ upon playing action $a$ at step $h$ before episode $k$
$R_{h}^{k}(s,a)$ | sum of truncated rewards obtained by taking action $a$ on state $s$ at step $h$ before episode $k$
$\epsilon$ | privacy budget
$\widetilde{N}_{h}^{k}(s,a)$ | the privatized version of $N_{h}^{k}(s,a)$
$\widetilde{N}_{h}^{k}(s,a,s^{\prime})$ | the privatized version of $N_{h}^{k}(s,a,s^{\prime})$
$\widetilde{R}_{h}^{k}(s,a)$ | the privatized version of $R_{h}^{k}(s,a)$
$\widetilde{r}_{h}^{k}(s,a)$ | the private empirical mean estimation of truncated rewards for state-action pair $(s,a)$
at step $h$ before episode $k$
$\widetilde{P}_{h}^{k}(s^{\prime}|s,a)$ | the private empirical transition probability
$[n]$ | the set of $\\{1,2,\dots,n\\}$
$a\vee b$ | the maximal value between $a$ and $b$

######  Lemma 3 (Parallel Composition).

Suppose there are $k$ number of $\epsilon$-differentially private mechanisms
$\\{\mathcal{M}_{i}\\}_{i=1}^{k}$ and $k$ disjoint datasets denoted by
$\\{D_{i}\\}_{i=1}^{k}$. Then the algorithm, which applies each
$\mathcal{M}_{i}$ on the corresponding $D_{i}$, preserves $\epsilon$-DP in
total.

######  Lemma 4 (Composition Theorem (Dwork et al., 2014)).

Let $\mathcal{M}_{1},\mathcal{M}_{2},\dots,\mathcal{M}_{h}$ be a sequence of
randomized algorithms, where
$\mathcal{M}_{1}:\mathcal{X}^{n}\rightarrow\mathcal{Y}_{1}$,
$\mathcal{M}_{2}:\mathcal{Y}_{1}\times\mathcal{X}^{n}\rightarrow\mathcal{Y}_{2},\dots$,
$\mathcal{M}_{h}:\mathcal{Y}_{1}\times\mathcal{Y}_{2}\times\mathcal{Y}_{h-1}\times\mathcal{X}^{n}\rightarrow\mathcal{Y}_{h}$.
Suppose for every $i\in[h]$ and
$y_{1}\in\mathcal{Y}_{1},y_{2}\in\mathcal{Y}_{2},\dots,y_{h}\in\mathcal{Y}_{h}$,
we have
$\mathcal{M}_{i}(y_{1},\dots,y_{i-1},\cdot):\mathcal{X}^{n}\rightarrow\mathcal{Y}_{i}$
is $\epsilon_{i}$-DP. Then the algorithm
$\mathcal{M}:\mathcal{X}^{n}\rightarrow\mathcal{Y}_{1}\times\mathcal{Y}_{2}\times\dots\mathcal{Y}_{h}$
that runs the algorithm $\mathcal{M}_{i}$ sequentially is $\epsilon$-DP for
$\epsilon=\sum_{i=1}^{h}\epsilon_{i}$.

######  Lemma 5 (Laplace Mechanism).

Given a dataset $D\in\mathcal{X}^{n}$ and a function
$q:\mathcal{X}^{n}\rightarrow\mathbb{R}^{d}$, the Laplace Mechanism is defined
as $q(D)+(Y_{1},Y_{2},\cdots,Y_{d}),$ where each $Y_{i}$ is i.i.d. sampled
from the Laplace Distribution
$\operatorname{Lap}(\frac{\Delta_{1}(q)}{\epsilon})$, where $\Delta_{1}(q)$ is
the $\ell_{1}$-sensitivity of the function $q$, i.e.,
$\Delta_{1}(q)=\sup_{D\sim D^{\prime}}||q(D)-q(D^{\prime})||_{1}.$ The density
of the Laplace distribution with parameter $\lambda$ is
$\operatorname{Lap}(\lambda)(x)=\frac{1}{2\lambda}\exp(-\frac{x}{\lambda})$.
Laplace mechanism preserves $\epsilon$-DP.

######  Lemma 6 (Hoeffding’s inequality).

Let $X_{1},\dots,X_{n}$ be independent random variables such that
${\displaystyle a_{i}\leq X_{i}\leq b_{i}}$ almost surely. Consider the sum of
these random variables, ${\displaystyle S_{n}=X_{1}+\cdots+X_{n}}$, then for
all $t>0$, we have

$\mathbb{P}\left(\left|S_{n}-\mathbb{E}\left[S_{n}\right]\right|\geq
t\right)\leq
2\exp\left(-\frac{2t^{2}}{\sum_{i=1}^{n}\left(b_{i}-a_{i}\right)^{2}}\right).$

######  Lemma 7 (Bernstein’s Inequality (Vershynin, 2018)).

Let $X_{1},\cdots X_{n}$ be $n$ independent zero-mean random variables.
Suppose $|X_{i}|\leq M$ and $\mathbb{E}[X_{i}^{2}]\leq s$ for all $i\in[n]$.
Then for any $t>0$, we have

$\mathbb{P}\left\\{\frac{1}{n}\sum_{i=1}^{n}X_{i}\geq
t\right\\}\leq\exp\left(-\frac{\frac{1}{2}t^{2}n}{s+\frac{1}{3}Mt}\right)$

######  Lemma 8 (Lemma 7 in (Tao et al., 2022b)).

Given a random variable $X$ with $\mathbb{E}[|X|^{1+v}]\leq u$ for some
$v\in(0,1]$, for any $B>0$ we have

$\mathbb{E}\left[X\cdot\mathbb{I}_{|X|>B}\right]\leq\frac{u}{B^{v}}.$

######  Lemma 9 (Hölder’s inequality).

For $p,q\in(1,\infty)$ with $1/p+1/q=1$,

$\sum_{k=1}^{n}\left|x_{k}y_{k}\right|\leq\left(\sum_{k=1}^{n}\left|x_{k}\right|^{p}\right)^{\frac{1}{p}}\left(\sum_{k=1}^{n}\left|y_{k}\right|^{q}\right)^{\frac{1}{q}}.$

######  Lemma 10 (Concentration of Laplace Variables (Wang et al., 2018)).

If $X_{1},\cdots X_{n}\sim\operatorname{Lap}(s/\epsilon)$, then with
probability at least $1-\beta$, we have

$\left|\frac{1}{n}\sum_{i=1}^{n}X_{i}\right|\leq\frac{2s}{\epsilon\sqrt{n}}\sqrt{\log\frac{2}{\beta}}.$

######  Lemma 11 (Markov Inequality).

If $X$ is a non-negative random variable and $a>0$, then the probability that
$X$ is at least $a$ is at most the expectation of $X$ divided by $a$:

$P(X\geq a)\leq\frac{\mathbb{E}(X)}{a}$

######  Lemma 12 (Lemma 1 in (Garivier et al., 2019)).

Consider a measurable space $(\Omega,\mathcal{F})$ equipped with two
distributions $\mathbb{P}_{1}$ and $\mathbb{P}_{2}$. For any
$\mathcal{F}$-measurable function $Z:\Omega\rightarrow[0,1]$, we have

$\mathrm{KL}\left(\mathbb{P}_{1},\mathbb{P}_{2}\right)\geq\operatorname{kl}\left(\mathbb{E}_{1}[Z],\mathbb{E}_{2}[Z]\right)$

where $\mathbb{E}_{1}$ and $\mathbb{E}_{2}$ are the expectations under
$\mathbb{P}_{1}$ and $\mathbb{P}_{2}$ respectively.

##  Appendix C Algorithms and Proofs of Section 3

###  C.1 Details of the Tree-based Mechanism

Note that our CENTRAL-PRIVATIZER is established by an adaptive version of the
Tree-based mechanism, we first give details of this mechanism.

Algorithm 2 (Adaptive) Tree-based Mechanism

0: time horizon $K$, privacy budget $\epsilon$, a stream $\sigma$.

0: A private version $\widehat{S}(k)$ for
$S(k)=\sum\nolimits_{i=1}^{k}{\sigma(i)}$ at each $k\in[K]$

1: Initialize each p-sum $\alpha_{i}$ and noisy p-sum $\widehat{\alpha}_{i}$
to $0$.

2: $\epsilon^{\prime}\leftarrow\epsilon/\log K$.

3: for $k=1,\ldots,K$ do

4: Express $k$ in binary form: $k=\sum_{j}{\rm Bin}_{j}(k)\cdot 2^{j}$.

5: $i\leftarrow\min\\{j:{\rm Bin}_{j}(k)\neq 0\\}$.

6: $\alpha_{i}\leftarrow\sum_{j<i}{\alpha_{j}}+\sigma(k)$.

7: for $j=0,\ldots,i-1$ do

8: $\alpha_{j}\leftarrow 0$, $\widehat{\alpha}_{j}\leftarrow 0$.

9: end for

10: $\widehat{\alpha}_{i}\leftarrow\alpha_{i}+{\rm
Lap}(2B_{k}/\epsilon^{\prime})$.

11: Return $\hat{S}(k)\leftarrow\sum_{j:{\rm
Bin}_{j}(k)=1}{\widehat{\alpha}_{j}}$.

12: end for

######  Definition 4 (p-sum).

A p-sum is a partial sum of consecutive data items. Let $1\leq i\leq j$. For a
data stream $\sigma$ of length $K$, we use $\sigma(k)$ to denote the data item
at time $k\in[K]$ and $\sum[i,j]\triangleq\sum_{k=i}^{j}\sigma(k)$ to denote a
partial sum involving data items $i$ through $j$. We use the notation
$\alpha_{i}^{k}$ to denote the p-sum $\sum[k-2^{i}+1,k]$.

######  Lemma 13 ((Adaptive) Tree-based Mechanism (Tao et al., 2022b)).

Given a stream $\sigma$ such that $\sigma(k)\in[-B_{k},B_{k}]$ for $\forall
k\in[K]$, where $B_{k}$ is non-decreasing with $k$, we want to privately and
continually release the sum of the stream
$S(k)\triangleq\sum\nolimits_{i=1}^{k}{\sigma(i)}$ for each $k\in[K]$. The
(adaptive) tree-based Mechanism (Algorithm 2) outputs an estimation
$\widehat{S}(k)$ for $S(k)$ at each $k\in[K]$ such that $\widehat{S}(k)$
preserves $\epsilon$-differential privacy and guarantees the following noise
bound with probability at least $1-\delta$ for any $\delta>0$,

$\left|\widehat{S}(k)-S(k)\right|\leq\frac{2B_{k}}{\epsilon}\log^{1.5}K\cdot\ln\frac{1}{\delta}.$
(4)

It is notable that when each $B_{k}=m$ for some $m$ then Algorithm 2 is just
the standard $m$-bounded tree-based mechanism in (Chan et al., 2011). Thus,
Algorithm 2 is a generalization compared with the standard one. To ensure
$\epsilon^{\prime}$-DP for some given $\epsilon^{\prime}$, for counter
$R_{h}^{k}(s,a)$, we use adaptive tree-based mechanism and add
$\text{Lap}(\frac{2B_{k}}{\epsilon^{\prime}})$ for some non-decreasing $B_{k}$
to every p-sum before releasing them. Then we get private count
$\widetilde{R}_{h}^{k}(s,a)$. For $N_{h}^{k}(s,a)$ and
$N_{h}^{k}(s,a,s^{\prime})$, we use $1$-bounded binary-tree mechanisms with
Laplace noise $\text{Lap}(\frac{1}{\epsilon^{\prime}})$ to release the
respective private counts $\widetilde{N}_{h}^{k}(s,a)$ and
$\widetilde{N}_{h}^{k}(s,a,s^{\prime})$.

###  C.2 Proof of Lemma 1

###### Proof of Lemma 1.

Therefore, we first focus on $E_{\epsilon,\delta,2}$ which is the error bound
between the private count for the sum of rewards $\widetilde{R}_{h}^{k}(s,a)$
and the non-private count $R_{h}^{k}(s,a)$.

We start with the privacy guarantee of the CENTRAL-PRIVATIZER. First, note
that there are $SAH$ many counters for the sum of rewards $R_{h}^{k}(s,a)$,
and each counter is a $K$-bounded adaptive tree-based mechanism. For a fixed
tuple $(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$, the private count
$\widetilde{R}_{h}^{k}(s,a)$ is the sum of at most $\log K$ noisy p-sums,
where each p-sum is corrupted by an independent Laplace noise
$\text{Lap}\left(\frac{6B_{k}H\log K}{\epsilon}\right)$. By Lemma 13, the
private counts $\\{\widetilde{R}_{h}^{k}(s,a)\\}_{k\in[K]}$ satisfy
$\frac{\epsilon}{3H}$-DP. We leverage the fact that the total change across
all counters a user can have scales with the length of the episode $H$ to get
the composition of the $SAH$ $\frac{\epsilon}{3H}$-DP counters for
$\widetilde{R}(\cdot)$ satisfy $\frac{\epsilon}{3}$-DP.

Using similar arguments of Lemma 5.1 in (Chowdhury & Zhou, 2021), one can show
that composition of the counters for $\widetilde{N}_{h}^{k}(s,a)$ and
$\widetilde{N}_{h}^{k}(s,a,s^{\prime})$ satisfy $\frac{\epsilon}{3}$-DP
respectively. Finally, employing the composition property of DP in (Dwork et
al., 2014), we obtain that the CENTRAL-PRIVATIZER is $\epsilon$-DP.

Now we focus on the utility of CENTRAL-PRIVATIZER. First, for a fixed tuple
$(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$, we consider the private
counts $\widetilde{R}_{h}^{k}(s,a)$ corresponding to the sum of rewards
${R}_{h}^{k}(s,a)$. Note that, at each episode $k\in[K]$, the noise bound
$|\widetilde{R}_{h}^{k}(s,a)-{R}_{h}^{k}(s,a)|$ is the sum of at most $\log K$
random variables drawn from the Laplace distribution. From Lemma 13, we have

$\mathbb{P}\left[\left|\widetilde{R}_{h}^{k}(s,a)-R_{h}^{k}(s,a)\right|\leq\frac{6B_{k}H}{\epsilon}\log^{1.5}K\ln(3SAT/\delta)\right]\geq
1-\delta/(3SAT)$

By a union bound argument, we can obtain

$\mathbb{P}\left[\forall(s,a,k,h),\left|\widetilde{R}_{h}^{k}(s,a)-R_{h}^{k}(s,a)\right|\leq\frac{6B_{k}H}{\epsilon}\log^{1.5}K\ln(3SAT/\delta)\right]\geq
1-\delta/3$

By using the same arguments, we can get the values of error bounds
$E_{\epsilon,\delta,1}$ and $E_{\epsilon,\delta,3}$.

$\mathbb{P}\left[\forall(s,a,k,h),\left|\widetilde{N}_{h}^{k}(s,a)-N_{h}^{k}(s,a)\right|\leq\frac{3H}{\epsilon}\log^{1.5}K\ln(3SAT/\delta)\right]\geq
1-\delta/3$
$\mathbb{P}\left[\forall(s,a,k,h),\left|\widetilde{N}_{h}^{k}(s,a,s^{\prime})-N_{h}^{k}(s,a,s^{\prime})\right|\leq\frac{3H}{\epsilon}\log^{1.5}K\ln(3S^{2}AT/\delta)\right]\geq
1-\delta/3$

Combining all three guarantees together using a union bound, we obtain that
CENTRAL-PRIVATIZER satisfies Assumption 1. ∎

###  C.3 Proof of Theorem 1

###### Proof of Theorem 1.

To prove the JDP guarantee, we use the billboard lemma in (Hsu et al., 2016,
Lemma 9) which states that an algorithm is JDP if the output sent to each user
is a function of the user’s private data and a common quantified computed with
standard differential privacy. The formal lemma is stated as follows:

######  Lemma 14 (Billboard lemma (Hsu et al., 2016)).

Suppose $\mathcal{M}:U\to\mathcal{R}$ is $\epsilon$-differentially private.
Consider any set of functions
$f_{i}:U_{i}\times\mathcal{R}\to\mathcal{R}^{\prime}$ where $U_{i}$ is the
portion of the database containing the $i$’s user data. then composition
$\\{f_{i}(\Pi_{i}U,\mathcal{M}(U))\\}$ is $\epsilon$-joint differentially
private, where $\Pi_{i}:U\to U_{i}$ is the projection to $i$’s data.

Note that by the privacy guarantee in Lemma 1 and the post-processing property
of DP in (Dwork et al., 2014), the policies $(\pi^{k})_{k}$ are computed with
a $\epsilon$-DP. Therefore, by the above billboard lemma, the composition of
the output of all $K$ episodes satisfies $\epsilon$-JDP.

∎

###  C.4  Proof of Theorem 2

Before showing the proof of Theorem 2 we first consider the following two
lemmas.

The following lemma shows the estimation errors of our private mean empirical
rewards and private empirical transition probabilities, which are in step 7 of
the algorithm.

######  Lemma 15 (Concentration bounds of private estimators).

Fix any $\epsilon\in(0,1]$ and $\delta\in(0,1)$ and take
$B_{n}=\left(\frac{\epsilon
un}{H\log^{1.5}K\log(3SAT/\delta)}\right)^{\frac{1}{1+v}}$ in equation (1).
Then, under Assumption 1, with probability at least $1-3\delta$, uniformly
over all $(s,a,h,k)$ we have

$|\widetilde{r}_{h}^{k}(s,a)-{r}_{h}(s,a)|\leq\beta_{h}^{k,r}(s,a),\left|\left(\widetilde{P}_{h}^{k}-P_{h}\right)V_{h+1}^{*}(s,a)\right|\leq\beta_{h}^{k,pv}(s,a),$

$\left|P_{h}\left(s^{\prime}|s,a\right)-\widetilde{P}_{h}^{k}\left(s^{\prime}|s,a\right)\right|\leq
C\sqrt{\frac{P_{h}(s^{\prime}|s,a)\ln\frac{2SAT}{\delta}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}}+\frac{C\ln\frac{2SAT}{\delta}+2E_{\epsilon,\delta,1}+E_{\epsilon,\delta,3}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1},$ where $C$ is a constant, $a\vee b=\max\\{a,b\\}$,
$(PV_{h+1})(s,a)=\sum_{s^{\prime}}P(s^{\prime}|s,a)V_{h+1}(s^{\prime})$, and
$\beta_{h}^{k,r}(s,a)=\frac{2\tau
E_{\varepsilon,\delta,1}}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}+10u^{\frac{1}{1+v}}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon\left((\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1\right)}\right)^{\frac{v}{1+v}}$, $\beta_{h}^{k,pv}(s,a)=\tau
H\sqrt{\frac{2\ln(4SAT/\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}}+\frac{\tau
H(2E_{\epsilon,\delta,1}+SE_{\epsilon,\delta,3})}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}.$

######  Remark 7.

Actually, all the above errors are determined by three terms: an error from
truncating rewards, an error due to using the finite number of truncated
rewards to estimate heavy-tailed reward distributions and an error due to the
noise for ensuring privacy. In order to balance these three terms, we need to
take the truncation threshold $B_{n}=\left(\frac{\epsilon
un}{H\log^{1.5}K\log(3SAT/\delta)}\right)^{\frac{1}{1+v}}$. Compared with the
truncation value $B_{n}=\left(\frac{\epsilon
un}{\log^{1.5}T}\right)^{\frac{1}{1+v}}$ in (Tao et al., 2022b) where the
authors focus on DP-MAB with heavy-tailed rewards, the difference comes from
that the privacy budget in our problem is $\frac{\epsilon}{H}$ for each step
$h$ based on Composition Theorem in Lemma 4, while $H=1$ in MAB case. Compared
with the truncation threshold
$B_{n}=\left(\frac{un}{\log(2SAT/\delta)}\right)^{\frac{1}{1+v}}$ in non-
private RL with heavy-tailed rewards (Zhuang & Sui, 2021), we can see the
efficient number of samples in our problem becomes to $n\epsilon$ due to
privacy. From our truncation threshold value $B_{n}=\left(\frac{\epsilon
un}{H\log^{1.5}K\log(3SAT/\delta)}\right)^{\frac{1}{1+v}}$, we also can check
the trade-off between utility and privacy: larger $\epsilon$ value provides
weaker privacy guarantee but we will truncate the data with a larger range, so
more data information will be used, then the bias will be smaller so that we
get better utility .

###### Proof of Lemma 15.

We first define the non-private mean empirical rewards:
$\bar{r}_{h}^{k}(s,a):=\frac{R_{h}^{k}(s,a)}{N_{h}^{k}(s,a)\vee 1}$. We then
get the non-private estimation error. For a fixed tuple
$(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$, at every episode $k\in[K]$,
from Bernstein’s inequality in Lemma 7 for bounded random variables, with
probability at least $1-\frac{\delta}{2SAT}$, noting that

$\mathbb{E}(X^{2}\cdot\mathbb{I}_{|X|\leq
B})=\mathbb{E}(X^{1+v}X^{1-v}\cdot\mathbb{I}_{|X|\leq B})\leq
B^{1-v}\mathbb{E}(X^{1+v}\cdot\mathbb{I}_{|X|\leq B})\leq uB^{1-v}$ (5)

and

$\mathbb{E}[X\mathbb{I}_{|X|>B}]\leq\mathbb{E}[|X|^{1+v}|X|^{-v}\mathbb{I}_{|X|>B}]\leq\frac{u}{B^{v}}$
(6)

if $\mathbb{E}|X|^{1+v}\leq u$,

$\displaystyle\left|\bar{r}_{h}^{k}(s,a)-r_{h}(s,a)\right|$ (7)
$\displaystyle=$ $\displaystyle\left|\frac{R_{h}^{k}(s,a)}{N_{h}^{k}(s,a)\vee
1}-r_{h}(s,a)\right|$ $\displaystyle=$
$\displaystyle|\frac{1}{N_{h}^{k}(s,a)\vee
1}\sum_{i=1}^{N_{h}^{k}(s,a)}[r_{h,i}(s,a)\mathbbm{I}\\{|r_{h,i}(s,a)|\leq
B_{i}\\}-\mathbb{E}(X_{h}(s,a)\mathbbm{I}\\{|X_{h}(s,a)|\leq B_{i}\\})$
$\displaystyle+\mathbb{E}(X_{h}(s,a)\mathbbm{I}\\{|X_{h}(s,a)|\leq
B_{i}\\})-\mathbb{E}(X_{h}(s,a))]|$ $\displaystyle\leq$
$\displaystyle\left|\frac{1}{N_{h}^{k}(s,a)\vee
1}\sum_{i=1}^{N_{h}^{k}(s,a)}[r_{h,i}(s,a)\mathbbm{I}\\{|r_{h,i}(s,a)|\leq
B_{i}\\}-\mathbb{E}(X_{h}(s,a)\mathbbm{I}\\{|X_{h}(s,a)|\leq B_{i}\\})\right|$
$\displaystyle+\left|\frac{1}{N_{h}^{k}(s,a)\vee
1}\sum_{i=1}^{N_{h}^{k}(s,a)}\mathbb{E}(X_{h}(s,a)\mathbbm{I}\\{|X_{h}(s,a)|\geq
B_{i}\\})\right|$ $\displaystyle\leq$
$\displaystyle\sqrt{\frac{2uB_{N_{h}^{k}(s,a)}^{1-v}\log(\frac{2SAT}{\delta})}{N_{h}^{k}(s,a)\vee
1}}+\frac{B_{N_{h}^{k}(s,a)}\log\frac{2SAT}{\delta}}{3(N_{h}^{k}(s,a)\vee
1)}+\frac{1}{N_{h}^{k}(s,a)\vee
1}\sum_{i=1}^{N_{h}^{k}(s,a)}\frac{u}{B_{i}^{v}}$

Let
$L_{r,k}=\sqrt{\frac{2uB_{N_{h}^{k}(s,a)}^{1-v}\log(\frac{2SAT}{\delta})}{N_{h}^{k}(s,a)\vee
1}}+\frac{B_{N_{h}^{k}(s,a)}\log\frac{2SAT}{\delta}}{3(N_{h}^{k}(s,a)\vee
1)}+\frac{1}{N_{h}^{k}(s,a)\vee
1}\sum_{i=1}^{N_{h}^{k}(s,a)}\frac{u}{B_{i}^{v}}$, then we denote

$F^{c}=\left\\{\exists
s,a,h,k:\left|\bar{r}_{h}^{k}(s,a)-r_{h}(s,a)\right|\geq L_{r,k}\right\\}$ (8)

Then, by using union bound over all $s,a,h,k$, we have
$\mathbb{P}(F^{c})\leq\frac{\delta}{2}$. So,

$\displaystyle\mathbb{P}(F)$ $\displaystyle=\mathbb{P}\left(\left\\{\forall
s,a,h,k:\left|\bar{r}_{h}^{k}(s,a)-r_{h}(s,a)\right|\leq
L_{r,k}\right\\}\right)$ (9) $\displaystyle=1-\mathbb{P}(F^{c})$
$\displaystyle=1-\frac{\delta}{2}.$

We first study the concentration of the private reward estimate. Note that
under the event in Assumption 1,

$\left|\frac{\widetilde{R}_{h}^{k}(s,a)}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}-\frac{R_{h}^{k}(s,a)}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}\right|\leq\frac{E_{\varepsilon,\delta,k,2}}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1},$ (10)

since
$\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\geq{N}_{h}^{k}(s,a)\geq
0$ and $|\widetilde{R}_{h}^{k}(s,a)-{R}_{h}^{k}(s,a)|\leq
E_{\varepsilon,\delta,k,2}$.

$\displaystyle\left|\frac{R_{h}^{k}(s,a)}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}-r_{h}(s,a)\right|$ (11) $\displaystyle\leq$
$\displaystyle\left|r_{h}(s,a)\left(\frac{N_{h}^{k}(s,a)\vee
1}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}-1\right)\right|+\left|\frac{N_{h}^{k}(s,a)\vee
1}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}\left(\frac{R_{h}^{k}(s,a)}{N_{h}^{k}(s,a)\vee 1}-r_{h}(s,a)\right)\right|$
$\displaystyle\leq$ $\displaystyle|r_{h}(s,a)|\left|1-\frac{N_{h}^{k}(s,a)\vee
1}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}\right|+\frac{N_{h}^{k}(s,a)\vee
1}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}{L_{r,k}}$ $\displaystyle\leq$ $\displaystyle\frac{2\tau
E_{\varepsilon,\delta,1}}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}+\frac{L_{r,k}(N_{h}^{k}(s,a)\vee
1)}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee 1}$

We put two pieces together, then get

$|\widetilde{r}_{h}^{k}(s,a)-{r}_{h}(s,a)|\leq\frac{2\tau
E_{\varepsilon,\delta,1}}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}+\frac{L_{r,k}(N_{h}^{k}(s,a)\vee
1)}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}+\frac{E_{\varepsilon,\delta,k,2}}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}$ (12)

where
$E_{\epsilon,\delta,k,2}=\frac{6HB_{N_{h}^{k}(s,a)}}{\epsilon}\log^{1.5}K\ln(3SAT/\delta)$.
In order to get the trade-off between mean estimation error and private count
error, we set the truncation threshold $B_{n}=\left(\frac{\epsilon
un}{H\log^{1.5}K\log(3SAT/\delta)}\right)^{\frac{1}{1+v}}$. Then we can bound
each term in $L_{r,k}$ for $\epsilon\in(0,1]$ and $K\geq 2$:

$\begin{aligned}
\sqrt{\frac{2uB_{N_{h}^{k}(s,a)}^{1-v}\log(\frac{2SAT}{\delta})}{N_{h}^{k}(s,a)\vee
1}}&\leq\frac{\sqrt{2}u^{\frac{1}{1+v}}\epsilon^{\frac{1-v}{2(1+v)}}(\log(3SAT/\delta))^{\frac{v}{1+v}}}{(N_{h}^{k}(s,a)\vee
1)^{\frac{v}{1+v}}{(H\log^{1.5}K)}^{\frac{1-v}{2(1+v)}}}\\\
&\leq\sqrt{2}u^{\frac{1}{1+v}}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon(N_{h}^{k}(s,a)\vee
1)}\right)^{\frac{v}{1+v}}\end{aligned},$

$\frac{B_{N_{h}^{k}(s,a)}\log\frac{2SAT}{\delta}}{3(N_{h}^{k}(s,a)\vee
1)}\leq\frac{u^{\frac{1}{1+v}}(\log(3SAT/\delta))^{\frac{v}{1+v}}}{3(N_{h}^{k}(s,a)\vee
1)^{\frac{v}{1+v}}}\left(\frac{\epsilon}{H\log^{1.5}K}\right)^{\frac{1}{1+v}}\leq\frac{u^{\frac{1}{1+v}}}{3}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon(N_{h}^{k}(s,a)\vee
1)}\right)^{\frac{v}{1+v}},$

where the last inequality is based on the fact that $x^{\frac{1}{1+v}}\leq
x^{-\frac{v}{1+v}}$for $x\in(0,1]$,

$\begin{aligned} \frac{1}{N_{h}^{k}(s,a)\vee
1}\sum_{i=1}^{N_{h}^{k}(s,a)}\frac{u}{B_{i}^{v}}&\leq\frac{u}{N_{h}^{k}(s,a)\vee
1}\sum_{i=1}^{N_{h}^{k}(s,a)}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon
ui}\right)^{\frac{v}{1+v}}\\\ &\leq\frac{u^{\frac{1}{1+v}}}{N_{h}^{k}(s,a)\vee
1}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon}\right)^{\frac{v}{1+v}}\sum_{i=1}^{N_{h}^{k}(s,a)}i^{-\frac{v}{1+v}}\\\
&\leq\frac{u^{\frac{1}{1+v}}}{N_{h}^{k}(s,a)\vee
1}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon}\right)^{\frac{v}{1+v}}\cdot(1+v)\cdot(N_{h}^{k}(s,a))^{\frac{1}{1+v}}\\\
&\leq
2u^{\frac{1}{1+v}}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon(N_{h}^{k}(s,a)\vee
1)}\right)^{\frac{v}{1+v}}\end{aligned}.$

Thus, $L_{r,k}\leq
4u^{\frac{1}{1+v}}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon(N_{h}^{k}(s,a)\vee
1)}\right)^{\frac{v}{1+v}}.$

And

$E_{\epsilon,\delta,k,2}=\frac{6HB_{N_{h}^{k}(s,a)}}{\epsilon}\log^{1.5}K\ln(3SAT/\delta)=6(uN_{h}^{k}(s,a))^{\frac{1}{1+v}}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon}\right)^{\frac{v}{1+v}}.$

Since
$\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\geq{N}_{h}^{k}(s,a)\geq
0$ , we obtain

$|\widetilde{r}_{h}^{k}(s,a)-{r}_{h}(s,a)|\leq\frac{2\tau
E_{\varepsilon,\delta,1}}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}+10u^{\frac{1}{1+v}}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon\left((\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1\right)}\right)^{\frac{v}{1+v}}.$ (13)

To show the second result, we first note that $V^{*}$ is fixed and
$V_{h}^{*}(s)\leq\tau H$ for all $h$ and $s$. Based on Hoeffding’s inequality
in Lemma 6, we can use similar proof as Lemma 4.1 in (Chowdhury & Zhou, 2021)
to get with probability at least $1-\delta/2$

$\left|\left(\widetilde{P}_{h}^{k}-P_{h}\right)V_{h+1}^{*}(s,a)\right|\leq\tau
H\sqrt{\frac{2\ln(4SAT/\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}}+\frac{\tau
H(2E_{\epsilon,\delta,1}+SE_{\epsilon,\delta,3})}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}$

and with probability at least $1-\delta$,

$\left|P_{h}\left(s^{\prime}\mid
s,a\right)-\widetilde{P}_{h}^{k}\left(s^{\prime}\mid s,a\right)\right|\leq
C\sqrt{\frac{P_{h}(s^{\prime}|s,a)\ln(2SAT/\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}}+\frac{C\ln(2SAT/\delta)+2E_{\epsilon,\delta,1}+E_{\epsilon,\delta,3}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1},$

which is based on the application of empirical Bernstein inequality. ∎

The next lemma claims that the value function maintained in Algorithm 1 is
optimistic.

######  Lemma 16.

Fix some $\delta\in(0,1]$, with probability at least $1-3\delta$,
$\widetilde{V}_{h}^{k}(s)\geq V_{h}^{*}(s)$ for all $(k,h,s)$.

###### Proof of Lemma 16.

For a fixed $k$, consider $h=H+1,H,\ldots,1$. In the base case $h=H+1$, it
trivially holds since $\widetilde{V}_{H+1}^{k}(s)=0=V_{H+1}^{*}(s)$. Assume
that $\widetilde{V}_{h+1}^{k}(s)\geq V_{h+1}^{*}(s)$ for all $s$. Then, by the
update rule, we have

$\displaystyle\widetilde{{Q}}_{h}^{k}(s,a)=\max\\{-(H-h+1)\tau,\min\\{(H-h+1)\tau,\widetilde{r}_{h}^{k}(s,a)+(\widetilde{P}_{h}^{k}\widetilde{V}_{h+1}^{k})(s,a)+\beta_{h}^{k}(s,a)\\}\\}$

First, we would like to show that the truncation at $-(H-h+1)\tau$ does not
affect the analysis. To see this, first, observe that under Lemma 15

$\displaystyle\widetilde{r}_{h}^{k}(s,a)+(\widetilde{P}_{h}^{k}\widetilde{V}_{h+1}^{k})(s,a)+\beta_{h}^{k}(s,a)$
$\displaystyle\overset{(a)}{\geq}r_{h}(s,a)+(\widetilde{P}_{h}^{k}\widetilde{V}_{h+1}^{k})(s,a)+\beta_{h}^{k,pv}(s,a)$
(14)
$\displaystyle\overset{(b)}{\geq}r_{h}(s,a)+(\widetilde{P}_{h}^{k}{V}_{h+1}^{*})(s,a)+\beta_{h}^{k,pv}(s,a)$
$\displaystyle\overset{(c)}{\geq}r_{h}(s,a)+(P_{h}V_{h+1}^{*})(s,a)=Q_{h}^{*}(s,a)$
$\displaystyle\geq-(H-h+1)\tau$

where (a) holds by the first result in Lemma 15; (b) holds by induction; (c)
holds by the second result in Lemma 15. This directly implies that

$\displaystyle\widetilde{{Q}}_{h}^{k}(s,a)=\min\\{(H-h+1)\tau,\widetilde{r}_{h}^{k}(s,a)+(\widetilde{P}_{h}^{k}\widetilde{V}_{h+1}^{k})(s,a)+\beta_{h}^{k}(s,a)\\}$

Hence, if the maximum is attained at $(H-h+1)\tau$, then
$\widetilde{{Q}}_{h}^{k}(s,a)\geq Q_{h}^{*}(s,a)$ trivially holds since
$Q_{h}^{*}(s,a)\in[-(H-h+1)\tau,(H-h+1)\tau]$. Otherwise, by Eq. (14), we also
have $\widetilde{{Q}}_{h}^{k}(s,a)\geq Q_{h}^{*}(s,a)$. Therefore, we have
$\widetilde{Q}_{h}^{k}(s,a)\geq Q_{h}^{*}(s,a)$, and hence
$\widetilde{V}_{h}^{k}(s)\geq V_{h}^{*}(s)$. ∎

###### Proof of Theorem 2.

By the optimistic result in Lemma 16, we have

$\displaystyle
Reg(T)=\sum_{k=1}^{K}(V_{1}^{*}(s_{1})-V_{1}^{\pi_{k}}(s_{1}))\leq\sum_{k=1}^{K}(\widetilde{V}_{1}^{k}(s_{1})-{V}_{1}^{\pi_{k}}(s_{1}))$
(15)

Now, we turn to upper bound
$\widetilde{V}_{h}^{k}(s_{h}^{k})-V_{h}^{\pi_{k}}(s_{h}^{k})$ by a recursive
form.

First, observe that

$\displaystyle(\widetilde{V}_{h}^{k}-V_{h}^{\pi_{k}})(s_{h}^{k})=(\widetilde{Q}_{h}^{k}-Q_{h}^{\pi_{k}})(s_{h}^{k},a_{h}^{k}),$

which holds since the action executed by $\pi_{k}$ at step $h$, and the action
used to update $\widetilde{V}_{h}^{k}$ is the same. Now, to bound the
$Q$-value difference, we have

$\displaystyle(\widetilde{Q}_{h}^{k}-Q_{h}^{\pi_{k}})(s_{h}^{k},a_{h}^{k})$
(16) $\displaystyle\overset{(a)}{\leq}$ $\displaystyle
2\beta_{h}^{k,r}(s_{h}^{k},a_{h}^{k})+(\widetilde{P}_{h}^{k}\widetilde{V}_{h+1}^{k}-P_{h}V_{h+1}^{\pi_{k}})(s_{h}^{k},a_{h}^{k})+\beta_{h}^{k,pv}(s,a)$
$\displaystyle=$
$\displaystyle\left[(\widetilde{P}_{h}^{k}-P_{h})\widetilde{V}_{h+1}^{k}\right](s_{h}^{k},a_{h}^{k})+\left[P_{h}(\widetilde{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})\right](s_{h}^{k},a_{h}^{k})+2\beta_{h}^{k,r}(s_{h}^{k},a_{h}^{k})+\beta_{h}^{k,pv}(s,a)$
$\displaystyle=$
$\displaystyle\left[(\widetilde{P}_{h}^{k}-P_{h}){V}_{h+1}^{*}\right](s_{h}^{k},a_{h}^{k})+\left[(P_{h}-\widetilde{P}_{h}^{k})({V}_{h+1}^{*}-\widetilde{V}_{h+1}^{k})\right](s_{h}^{k},a_{h}^{k})+\left[P_{h}(\widetilde{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})\right](s_{h}^{k},a_{h}^{k})$
$\displaystyle+2\beta_{h}^{k,r}(s_{h}^{k},a_{h}^{k})+\beta_{h}^{k,pv}(s,a)$
$\displaystyle\overset{(b)}{\leq}$
$\displaystyle\left[(\widetilde{P}_{h}^{k}-P_{h})(\widetilde{V}_{h+1}^{k}-{V}_{h+1}^{*})\right](s_{h}^{k},a_{h}^{k})+\left[P_{h}(\widetilde{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})\right](s_{h}^{k},a_{h}^{k})+2\beta_{h}^{k,r}(s_{h}^{k},a_{h}^{k})+2\beta_{h}^{k,pv}(s,a)$

where (a) we have used the reward concentration result in Lemma 15; (b) holds
by the transition concentration result in Lemma 15. Thus, so far we have
arrived at

$\displaystyle(\widetilde{V}_{h}^{k}-V_{h}^{\pi_{k}})(s_{h}^{k})\leq$
$\displaystyle\left[(\widetilde{P}_{h}^{k}-P_{h})(\widetilde{V}_{h+1}^{k}-{V}_{h+1}^{*})\right](s_{h}^{k},a_{h}^{k})+\left[P_{h}(\widetilde{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})\right](s_{h}^{k},a_{h}^{k})$
$\displaystyle+2\beta_{h}^{k,r}(s_{h}^{k},a_{h}^{k})+2\beta_{h}^{k,pv}(s_{h}^{k},a_{h}^{k}).$
(17)

We will first carefully analyze the first term. In particular, let
$G:=(\widetilde{V}_{h+1}^{k}-{V}_{h+1}^{*})$, we have

$\displaystyle\left[(\widetilde{P}_{h}^{k}-P_{h})(\widetilde{V}_{h+1}^{k}-{V}_{h+1}^{*})\right](s_{h}^{k},a_{h}^{k})$
$\displaystyle=$
$\displaystyle\sum_{s^{\prime}}\left(\widetilde{P}_{h}^{k}(s^{\prime}|s_{h}^{k},a_{h}^{k})-P_{h}(s^{\prime}|s_{h}^{k},a_{h}^{k})\right)G(s^{\prime})$
$\displaystyle\overset{(a)}{\leq}$ $\displaystyle
c\sum_{s^{\prime}}\left(\sqrt{\frac{\ln(2SAT/\delta)P_{h}(s^{\prime}|s_{h}^{k},a_{h}^{k})}{{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}}}+\frac{\ln(2SAT/\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}+\frac{2E_{\epsilon,\delta,1}+E_{\epsilon,\delta,3}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}\right)G(s^{\prime})$ $\displaystyle\overset{(b)}{\leq}$
$\displaystyle\sum_{s^{\prime}}\left(\frac{P_{h}(s^{\prime}|s_{h}^{k},a_{h}^{k})}{H}G(s^{\prime})\right)+c\sum_{s^{\prime}}\left(\frac{H\ln(2SAT/\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}\right)G(s^{\prime})$
$\displaystyle+c\sum_{s^{\prime}}\left(\frac{\ln(2SAT/\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}\right)G(s^{\prime})+c\sum_{s^{\prime}}\left(\frac{2E_{\epsilon,\delta,1}+E_{\epsilon,\delta,3}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}\right)G(s^{\prime})$ $\displaystyle\overset{(c)}{\leq}$
$\displaystyle\sum_{s^{\prime}}\left(\frac{P_{h}(s^{\prime}|s_{h}^{k},a_{h}^{k})}{H}G(s^{\prime})\right)+\sum_{s^{\prime}}\left(\frac{c^{\prime}H^{2}\tau\ln(2SAT/\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}\right)+c\sum_{s^{\prime}}\left(\frac{4\tau HE_{\epsilon,\delta,1}+2\tau
HE_{\epsilon,\delta,3}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}\right),$ (18)

where (a) holds by the third result in Lemma 15 and $c$ is some absolute
constant; (b) holds by $\sqrt{xy}\leq x+y$ for positive numbers $x,y$; (c)
holds since $G(s^{\prime})\leq 2H\tau$ by the boundedness of $V$-value. Now,
plugging the definition for $G(s^{\prime})$ into (18), yields

$\displaystyle\left[(\widetilde{P}_{h}^{k}-P_{h})(\widetilde{V}_{h+1}^{k}-{V}_{h+1}^{*})\right](s_{h}^{k},a_{h}^{k})$
$\displaystyle\leq$
$\displaystyle\frac{1}{H}\left[P_{h}(\widetilde{V}_{h+1}^{k}-V_{h+1}^{*})\right](s_{h}^{k},a_{h}^{k})+\frac{c^{\prime}\tau
SH^{2}\ln(2SAT/\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}+\frac{4c\tau SHE_{\epsilon,\delta,1}+2c\tau
SHE_{\epsilon,\delta,3}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}$ $\displaystyle\overset{(a)}{\leq}$
$\displaystyle\frac{1}{H}\left[P_{h}(\widetilde{V}_{h+1}^{k}-V_{h+1}^{*})\right](s_{h}^{k},a_{h}^{k})+\xi_{h}^{k}+\zeta_{h}^{k}$
$\displaystyle\overset{(b)}{\leq}$
$\displaystyle\frac{1}{H}\left[P_{h}(\widetilde{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})\right](s_{h}^{k},a_{h}^{k})+\xi_{h}^{k}+\zeta_{h}^{k},$
(19)

where (a) holds by definitions $\xi_{h}^{k}=:\frac{c^{\prime}\tau
SH^{2}\ln(2SAT/\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}$ and $\zeta_{h}^{k}:=\frac{4c\tau SHE_{\epsilon,\delta,1}+2c\tau
SHE_{\epsilon,\delta,3}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}$; (b) holds since $V_{h+1}^{\pi_{k}}\leq V_{h+1}^{*}$. Plugging (19) into
(17), yields the following recursive formula.

$\displaystyle(\widetilde{V}_{h}^{k}-V_{h}^{\pi_{k}})(s_{h}^{k})$
$\displaystyle\overset{(a)}{\leq}\left(1+\frac{1}{H}\right)\left[P_{h}(\widetilde{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})\right](s_{h}^{k},a_{h}^{k})+\xi_{h}^{k}+\zeta_{h}^{k}+2\beta_{h}^{k}$
$\displaystyle\overset{(b)}{=}\left(1+\frac{1}{H}\right)\left[(\widetilde{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h+1}^{k})+\chi_{h}^{k}\right]+\xi_{h}^{k}+\zeta_{h}^{k}+2\beta_{h}^{k}$

where in (a), we let
$\beta_{h}^{k}:=\beta_{h}^{k,r}(s_{h}^{k},a_{h}^{k})+\beta_{h}^{k,pv}(s_{h}^{k},a_{h}^{k})$
for notation simplicity; (b) holds by definition
$\chi_{h}^{k}:=\left[P_{h}(\widetilde{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})\right](s_{h}^{k},a_{h}^{k})-(\widetilde{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h+1}^{k})$.
Based on this, we have the following bound on
$(\widetilde{V}_{1}^{k}-V_{1}^{\pi_{k}})(s_{1}^{k})$,

$\displaystyle(\widetilde{V}_{1}^{k}-V_{1}^{\pi_{k}})(s_{1}^{k})$
$\displaystyle\leq$
$\displaystyle\left(1+\frac{1}{H}\right)(\chi_{1}^{k}+\xi_{1}^{k}+\zeta_{1}^{k}+2\beta_{1}^{k})+\left(1+\frac{1}{H}\right)^{2}(\chi_{2}^{k}+\xi_{2}^{k}+\zeta_{2}^{k}+2\beta_{2}^{k})+\ldots$
$\displaystyle+\left(1+\frac{1}{H}\right)^{H}(\chi_{H}^{k}+\xi_{H}^{k}+\zeta_{H}^{k}+2\beta_{H}^{k})$
$\displaystyle\leq$ $\displaystyle
3\sum_{h=1}^{H}(\chi_{h}^{k}+\xi_{h}^{k}+\zeta_{h}^{k}+2\beta_{h}^{k}).$ (20)

Therefore, plugging (20) into (15), we have the regret decomposition as
follows.

$\displaystyle Reg(T)\leq
3\sum_{k=1}^{K}\sum_{h=1}^{H}(\chi_{h}^{k}+\xi_{h}^{k}+\zeta_{h}^{k}+2\beta_{h}^{k})$

We are only left to bound each of them. To start with, we focus on the bonus
term. We first focus on $\beta_{h}^{k,r}(s,a)$ as shown in Lemma 15. By
definition, we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\beta_{h}^{k,r}(s,a)=\underbrace{\sum_{k=1}^{K}\sum_{h=1}^{H}\frac{2\tau
E_{\varepsilon,\delta,1}}{\left(\widetilde{N}_{h}^{k}(s_{h}^{k},a_{h}^{k})+E_{\varepsilon,\delta,1}\right)\vee
1}}_{\mathcal{O}_{1}}+\underbrace{10u^{\frac{1}{1+v}}\sum_{k=1}^{K}\sum_{h=1}^{H}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon\left((\widetilde{N}_{h}^{k}(s_{h}^{k},a_{h}^{k})+E_{\varepsilon,\delta,1})\vee
1\right)}\right)^{\frac{v}{1+v}}}_{\mathcal{O}_{2}},$

The first term can be upper bounded as follows $(T=KH)$ under assumption 1

$\displaystyle\mathcal{O}_{1}$ $\displaystyle\leq 2\tau
E_{\epsilon,\delta,1}\sum_{k=1}^{K}\sum_{h=1}^{H}\frac{1}{N_{h}^{k}(s_{h}^{k},a_{h}^{k})\vee
1}$ $\displaystyle=2\tau
E_{\epsilon,\delta,1}\sum_{h,s,a}\sum_{i=1}^{N_{h}^{K}(s,a)}\frac{1}{i}$
$\displaystyle\leq
c^{\prime}E_{\epsilon,\delta,1}\sum_{h,s,a}\ln(N_{h}^{K}(s,a))$
$\displaystyle=\widetilde{O}\left(HSAE_{\epsilon,\delta,1}\right).$

where $\widetilde{O}(\cdot)$ hides $polylog(S,A,T,1/\delta)$ factors.

The second term can be upper bounded as follows under Assumption 15.

$\displaystyle\mathcal{O}_{2}$ $\displaystyle\leq
cu^{\frac{1}{1+v}}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon}\right)^{\frac{v}{1+v}}\sum_{k=1}^{K}\sum_{h=1}^{H}\left(\frac{1}{{N}_{h}^{k}(s_{h}^{k},a_{h}^{k})\vee
1}\right)^{\frac{v}{1+v}}$
$\displaystyle=cu^{\frac{1}{1+v}}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon}\right)^{\frac{v}{1+v}}\sum_{h,s,a}\sum_{i=1}^{N_{h}^{K}(s,a)}\frac{1}{i^{\frac{v}{1+v}}}$
$\displaystyle\leq
c^{\prime}u^{\frac{1}{1+v}}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon}\right)^{\frac{v}{1+v}}\sum_{h,s,a}(N_{h}^{K}(s,a))^{\frac{1}{1+v}}$
$\displaystyle\overset{(a)}{\leq}c^{\prime}u^{\frac{1}{1+v}}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon}\right)^{\frac{v}{1+v}}\left(\sum_{h,s,a}1\right)^{\frac{v}{1+v}}\left(\sum_{h,s,a}N_{h}^{K}(s,a)\right)^{\frac{1}{1+v}}$
$\displaystyle\leq\widetilde{O}\left(u^{\frac{1}{1+v}}\left(\frac{H^{2}SA}{\epsilon}\right)^{\frac{v}{1+v}}T^{\frac{1}{1+v}}\right)$

where (a) is based on Hölder’s inequality with
$x_{k}=1,y_{k}=(N_{h}^{K}(s,a))^{\frac{1}{1+v}},q=1+v$ in Lemma 9.

Putting them together, we have the upper bound for the summation over
$\beta_{h}^{k,r}(s,a)$,

$\sum_{k=1}^{K}\sum_{h=1}^{H}\beta_{h}^{k,r}(s,a)=\widetilde{O}\left(HSAE_{\epsilon,\delta,1}+u^{\frac{1}{1+v}}\left(\frac{H^{2}SA}{\epsilon}\right)^{\frac{v}{1+v}}T^{\frac{1}{1+v}}\right)$

Now, we study the upper bound of $\beta_{h}^{k,pv}(s_{h}^{k},a_{h}^{k})$. By
definition, we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\beta_{h}^{k,pv}(s_{h}^{k},a_{h}^{k})$
$\displaystyle=$ $\displaystyle\underbrace{\tau
H\sum_{k=1}^{K}\sum_{h=1}^{H}\sqrt{\frac{2\ln(4SAT/\delta)}{{(\widetilde{N}_{h}^{k}(s_{h}^{k},a_{h}^{k})+E_{\epsilon,\delta,1})\vee
1}}}}_{\mathcal{T}_{1}}+\underbrace{\tau
H\sum_{k=1}^{K}\sum_{h=1}^{H}\frac{(SE_{\epsilon,\delta,3}+2E_{\epsilon,\delta,1})}{(\widetilde{N}_{h}^{k}(s_{h}^{k},a_{h}^{k})+E_{\epsilon,\delta,1})\vee
1}}_{\mathcal{T}_{2}}.$

The first term can be upper bounded as follows ($T:=KH$) under Assumption 1.

$\displaystyle\mathcal{T}_{1}$ $\displaystyle\leq\tau
H{\sqrt{2\ln(4SAT/\delta)}}\sum_{k=1}^{K}\sum_{h=1}^{H}\sqrt{\frac{1}{{{N}_{h}^{k}(s,a)\vee
1}}}$
$\displaystyle=\tau{\sqrt{2\ln(4SAT/\delta)}}\sum_{h,s,a}\sum_{i=1}^{N_{h}^{K}(s,a)}\frac{1}{\sqrt{i}}$
$\displaystyle\leq
c^{\prime}H{\sqrt{2\ln(4SAT/\delta)}}\sum_{h,s,a}\sqrt{N_{h}^{K}(s,a)}$
$\displaystyle\leq
c^{\prime}H{\sqrt{2\ln(4SAT/\delta)}}\sqrt{\left(\sum_{h,s,a}1\right)\left(\sum_{h,s,a}N_{h}^{K}(s,a)\right)}$
$\displaystyle=\widetilde{O}\left(\sqrt{H^{3}SAT}\right).$

The second term can be upper bounded as follows under Assumption 1.

$\displaystyle\mathcal{T}_{2}$ $\displaystyle\leq
cH(SE_{\epsilon,\delta,3}+E_{\epsilon,\delta,1})\sum_{k=1}^{K}\sum_{h=1}^{H}\frac{1}{N_{h}^{k}(s_{h}^{k},a_{h}^{k})\vee
1}$
$\displaystyle=cH(SE_{\epsilon,\delta,3}+E_{\epsilon,\delta,1})\sum_{h,s,a}\sum_{i=1}^{N_{h}^{K}(s,a)}\frac{1}{i}$
$\displaystyle\leq
c^{\prime}H(SE_{\epsilon,\delta,3}+E_{\epsilon,\delta,1})\sum_{h,s,a}\ln(N_{h}^{K}(s,a))$
$\displaystyle=\widetilde{O}\left(H^{2}S^{2}AE_{\epsilon,\delta,3}+H^{2}SAE_{\epsilon,\delta,1}\right).$

Putting them together, we have the following bound on the summation over
$\beta_{h}^{k}$.

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\beta_{h}^{k}=\widetilde{O}\left(\sqrt{H^{3}SAT}+H^{2}S^{2}AE_{\epsilon,\delta,3}+H^{2}SAE_{\epsilon,\delta,1}+u^{\frac{1}{1+v}}\left(\frac{H^{2}SA}{\epsilon}\right)^{\frac{v}{1+v}}T^{\frac{1}{1+v}}\right).$

By following the same analysis as in $\mathcal{T}_{2}$, we can bound the
summation over $\xi_{h}^{k}=:\frac{c^{\prime}\tau
SH^{2}\ln(2SAT/\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}$ and $\zeta_{h}^{k}:=\frac{4c\tau SHE_{\epsilon,\delta,1}+2c\tau
SHE_{\epsilon,\delta,3}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}$ as follows.

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\xi_{h}^{k}=\widetilde{O}\left(H^{3}S^{2}A\right)$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\zeta_{h}^{k}=\widetilde{O}\left(H^{2}S^{2}A(E_{\epsilon,\delta,3}+E_{\epsilon,\delta,1})\right).$

Finally, we are going to bound the summation over
$\chi_{h}^{k}:=\left[P_{h}(\widetilde{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})\right](s_{h}^{k},a_{h}^{k})-(\widetilde{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})(s_{h+1}^{k})$,
which turns out to be a martingale difference sequence. In particular, we
define a filtration $\mathcal{F}_{h}^{k}$ that includes all the randomness up
to the $k$-th episode and the $h$-th step. Then, we have
$\mathcal{F}_{1}^{1}\subset\mathcal{F}_{2}^{1}\ldots\subset\mathcal{F}_{H}^{1}\subset\mathcal{F}_{1}^{2}\subset\mathcal{F}_{2}^{2}\ldots$.
Also, we have
$(\widetilde{V}_{h+1}^{k}-V_{h+1}^{\pi_{k}})\in\mathcal{F}_{1}^{k}\subset\mathcal{F}_{h}^{k}$
since they are decided by data collected up to episode $k-1$. A bit abuse of
notation, we define $Y_{h+1}^{k}:=\chi_{h}^{k}$. Then, we have

$\displaystyle\mathbb{E}\left[Y_{h+1}^{k}|\mathcal{F}_{h}^{k}\right]=0.$ (21)

This holds since the expectation only captures randomness over $s_{h+1}^{k}$.
Thus, $Y_{h+1}^{k}$ is a martingale difference sequence. Moreover, we have
$|Y_{h+1}^{k}|\leq 4H\tau$ a.s. By Azuma-Hoeffding inequality, we have with
probability at least $1-\delta$

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\chi_{h}^{k}=\sum_{k=1}^{K}\sum_{h=1}^{H}Y_{h+1}^{k}=c^{\prime}\sqrt{H^{2}T\ln(2/\delta)}=\widetilde{O}\left(\sqrt{H^{2}T}\right)$

Putting everything together, and applying union bound on all high-probability
events, we have shown that with probability at least $1-\delta$,

$\displaystyle
Reg(T)=\widetilde{O}\left(\sqrt{SAH^{3}T}+S^{2}AH^{3}+S^{2}AH^{2}E_{\epsilon,\delta,1}+S^{2}AH^{2}E_{\epsilon,\delta,3}+u^{\frac{1}{1+v}}\left(\frac{H^{2}SA}{\epsilon}\right)^{\frac{v}{1+v}}T^{\frac{1}{1+v}}\right).$

Based on the value of $E_{\epsilon,\delta,1},E_{\epsilon,\delta,3}$ in Lemma
1, we obtain

$Reg(T)=\widetilde{O}\left(\sqrt{SAH^{3}T}+S^{2}AH^{3}/\epsilon+u^{\frac{1}{1+v}}\left(\frac{SAH^{2}}{\epsilon}\right)^{\frac{v}{1+v}}T^{\frac{1}{1+v}}\right).$

∎

###  C.5  Proof of Theorem 3

Similar to the JDP case we first provide some concentration bounds.

######  Lemma 17 (Concentration bounds of locally private estimators).

Fix any $\epsilon\in(0,1]$ and $\delta\in(0,1)$ and take
$B_{n}=\left(\frac{u\epsilon\sqrt{n}}{H\log(6SAT/\delta)}\right)^{\frac{1}{1+v}}$
in equation (1). Then, under Assumption 1, with probability at least
$1-3\delta$, uniformly over all $(s,a,h,k)$,
$|\widetilde{r}_{h}^{k}(s,a)-{r}_{h}(s,a)|\leq\beta_{h}^{k,r}(s,a),\quad\left|\left(\widetilde{P}_{h}^{k}-P_{h}\right)V_{h+1}^{*}(s,a)\right|\leq\beta_{h}^{k,pv}(s,a),\quad\left|P_{h}\left(s^{\prime}\mid
s,a\right)-\widetilde{P}_{h}^{k}\left(s^{\prime}\mid s,a\right)\right|\leq
C\sqrt{\frac{P_{h}(s^{\prime}|s,a)\ln(2SAT/\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}}+\frac{C\ln(2SAT/\delta)+2E_{\epsilon,\delta,1}+E_{\epsilon,\delta,3}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}$ where $C$ is a positive
constant,$(PV_{h+1})(s,a)=\sum_{s^{\prime}}P(s^{\prime}|s,a)V_{h+1}(s^{\prime})$,
$\beta_{h}^{k,r}(s,a)=\frac{2\tau
E_{\varepsilon,\delta,1}}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}+16u^{\frac{1}{1+v}}\left(\frac{H\log(6SAT/\delta)}{\epsilon\sqrt{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}}\right)^{\frac{v}{1+v}},$ and $\beta_{h}^{k,pv}(s,a)$ is defined in Lemma
15.

######  Remark 8.

Compared with the JDP case, we can see there are several differences. Firstly,
due to the error caused by the noise we added to guarantee privacy becomes
larger, in the LDP case we need to make $B_{n}$ smaller than it in the JDP
case and finally, we can get the optimal one
$B_{n}=\left(\frac{u\epsilon\sqrt{n}}{H\log(6SAT/\delta)}\right)^{\frac{1}{1+v}}$.
It also indicates that the bound for LDP will be less than that for JDP as we
leverage less data information. Secondly, due to the stronger privacy
guarantee in the local model, we can see the second term of in
$\beta_{h}^{k,r}(s,a)$ in above Lemma is worse than it in Lemma 15 by a factor
of $\left({\sqrt{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}}\right)^{-\frac{v}{1+v}}$.

###### Proof of Lemma 17.

Following the similar argue as proof of Lemma 15, we can get

$|\widetilde{r}_{h}^{k}(s,a)-{r}_{h}(s,a)|\leq\frac{2\tau
E_{\varepsilon,\delta,1}}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}+\frac{L_{r,k}(N_{h}^{k}(s,a)\vee
1)}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}+\frac{E_{\varepsilon,\delta,k,2}}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}$ (22)

where
$E_{\epsilon,\delta,k,2}=\frac{12HB_{N_{h}^{k}(s,a)}}{\epsilon}\sqrt{N_{h}^{k}(s,a)\log(6SAT/\delta)}$
and
$L_{r,k}=\sqrt{\frac{2uB_{N_{h}^{k}(s,a)}^{1-v}\log(\frac{2SAT}{\delta})}{N_{h}^{k}(s,a)\vee
1}}+\frac{B_{N_{h}^{k}(s,a)}\log\frac{2SAT}{\delta}}{3(N_{h}^{k}(s,a)\vee
1)}+\frac{1}{N_{h}^{k}(s,a)\vee
1}\sum_{i=1}^{N_{h}^{k}(s,a)}\frac{u}{B_{i}^{v}}$.

Let
$B_{n}=\left(\frac{u\epsilon\sqrt{n}}{H\log(6SAT/\delta)}\right)^{\frac{1}{1+v}}$,
then

$L_{r,k}=\sqrt{\frac{2uB_{N_{h}^{k}(s,a)}^{1-v}\log(\frac{2SAT}{\delta})}{N_{h}^{k}(s,a)\vee
1}}+16u^{\frac{1}{1+v}}\left(\frac{H\log(6SAT/\delta)}{\epsilon\sqrt{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}}\right)^{\frac{v}{1+v}}.$

∎

###### Proof of Theorem 3.

Following the same idea in the proof of Theorem 2, we need to calculate
$\beta_{h}^{k,r}(s,a)$ as shown in Lemma 17. By definition, we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\beta_{h}^{k,r}(s,a)=\underbrace{\sum_{k=1}^{K}\sum_{h=1}^{H}\frac{2\tau
E_{\varepsilon,\delta,1}}{\left(\widetilde{N}_{h}^{k}(s_{h}^{k},a_{h}^{k})+E_{\varepsilon,\delta,1}\right)\vee
1}}_{\mathcal{O}_{1}}+\underbrace{16u^{\frac{1}{1+v}}\sum_{k=1}^{K}\sum_{h=1}^{H}\left(\frac{H\log(6SAT/\delta)}{\epsilon\sqrt{(\widetilde{N}_{h}^{k}(s_{h}^{k},a_{h}^{k})+E_{\varepsilon,\delta,1})\vee
1}}\right)^{\frac{v}{1+v}}}_{\mathcal{O}_{2}},$

The first term can be upper bounded as follows $(T=KH)$ under assumption 1

$\displaystyle\mathcal{O}_{1}=\widetilde{O}\left(HSAE_{\epsilon,\delta,1}\right).$

where $\widetilde{O}(\cdot)$ hides $polylog(S,A,T,1/\delta)$ factors.

The second term can be upper bounded as follows under Assumption 15.

$\displaystyle\mathcal{O}_{2}$ $\displaystyle\leq
cu^{\frac{1}{1+v}}\left(\frac{H\log(6SAT/\delta)}{\epsilon}\right)^{\frac{v}{1+v}}\sum_{k=1}^{K}\sum_{h=1}^{H}\left(\frac{1}{\sqrt{{N}_{h}^{k}(s_{h}^{k},a_{h}^{k})\vee
1}}\right)^{\frac{v}{1+v}}$
$\displaystyle=cu^{\frac{1}{1+v}}\left(\frac{H\log(6SAT/\delta)}{\epsilon}\right)^{\frac{v}{1+v}}\sum_{h,s,a}\sum_{i=1}^{N_{h}^{K}(s,a)}\frac{1}{i^{\frac{v}{2(1+v)}}}$
$\displaystyle\leq
c^{\prime}u^{\frac{1}{1+v}}\left(\frac{H\log(6SAT/\delta)}{\epsilon}\right)^{\frac{v}{1+v}}\sum_{h,s,a}(N_{h}^{K}(s,a))^{\frac{2+v}{2(1+v)}}$
$\displaystyle\overset{(a)}{\leq}c^{\prime}u^{\frac{1}{1+v}}\left(\frac{H\log(3SAT/\delta)}{\epsilon}\right)^{\frac{v}{1+v}}\left(\sum_{h,s,a}1\right)^{\frac{v}{2(1+v)}}\left(\sum_{h,s,a}N_{h}^{K}(s,a)\right)^{\frac{2+v}{2(1+v)}}$
$\displaystyle\leq\widetilde{O}\left(u^{\frac{1}{(1+v)}}\left(\frac{H^{3}SA}{\epsilon^{2}}\right)^{\frac{v}{2(1+v)}}T^{\frac{2+v}{2(1+v)}}\right)$

where (a) is based on Hölder’s inequality with
$x_{k}=1,y_{k}=(N_{h}^{K}(s,a))^{\frac{2+v}{2(1+v)}},q=\frac{2(1+v)}{2+v}$ in
Lemma 9.

Hence,

$Reg(T)=\widetilde{O}\left(\sqrt{SAH^{3}T}+S^{2}AH^{3}+S^{2}AH^{2}E_{\epsilon,\delta,1}+S^{2}AH^{2}E_{\epsilon,\delta,3}+u^{\frac{1}{(1+v)}}\left(\frac{H^{3}SA}{\epsilon^{2}}\right)^{\frac{v}{2(1+v)}}T^{\frac{2+v}{2(1+v)}}\right).$

Plugging the value of error bound in Lemma 2 to the regret bound, we obtain

$Reg(T)=\widetilde{O}\left(\sqrt{SAH^{3}T}+\frac{S^{2}A\sqrt{H^{5}T}}{\epsilon}+u^{\frac{1}{(1+v)}}\left(\frac{H^{3}SA}{\epsilon^{2}}\right)^{\frac{v}{2(1+v)}}T^{\frac{2+v}{2(1+v)}}\right).$

∎

##  Appendix D Algorithm and Proofs of Section 4

Algorithm 3 Private-Heavy-UCBPO

0: Number of episodes $K$, time horizon $H$, privacy level $\epsilon>0$, a
PRIVATIZER (LOCAL or CENTRAL), confidence level $\delta\in(0,1]$ and parameter
$\eta>0$

1: Initialize policy $\pi_{h}^{1}(a|s)=1/A$ for all $(s,a,h)$

2: Initialize private counts $\widetilde{R}_{h}^{1}(s,a)=0$,
$\widetilde{N}_{h}^{1}(s,a)=0$ and $\widetilde{N}_{h}^{1}(s,a,s^{\prime})=0$
for all $(s,a,s^{\prime},h)$

3: Set precision levels
$E_{\epsilon,\delta,1},E_{\epsilon,\delta,2},E_{\epsilon,\delta,3}$ of the
PRIVATIZER

4: for $k=1,2,3,\ldots,K$ do

5: Initialize private value estimates: $\widetilde{V}^{k}_{H+1}(s)=0$

6: for $h=H,H-1,\ldots,1$ do

7: Compute $\widetilde{r}_{h}^{k}(s,a)$ and $\widetilde{P}_{h}^{k}(s,a)$
$\forall(s,a)$ as in (2) using the private counts

8: Set exploration bonus using Lemma 18:
$\beta_{h}^{k}(s,a)=\beta_{h}^{k,r}(s,a)+\tau H\beta_{h}^{k,p}(s,a)$
$\forall(s,a)$

9: Compute: $\forall(s,a)$,

10: $\begin{aligned} \ \ \ \
\widetilde{{Q}}_{h}^{k}(s,a)&=\max\\{-(H-h+1)\tau,\min\\{(H-h+1)\tau,\widetilde{r}_{h}^{k}(s,a)\\\
&+\sum_{s^{\prime}\in\mathcal{S}}\widetilde{V}_{h+1}^{k}(s^{\prime})\widetilde{P}_{h}^{k}(s^{\prime}|s,a)+\beta_{h}^{k}(s,a)\\}\\}\end{aligned}$

11: Compute private value estimates: $\forall s$,
$\widetilde{V}_{h}^{k}(s)=\sum_{a\in\mathcal{A}}\widetilde{Q}_{h}^{k}(s,a)\pi_{h}^{k}(a|s)$

12: end for

13: Roll out a trajectory $(s_{1}^{k},a_{1}^{k},r_{1}^{k},\ldots,s_{H+1}^{k})$
by acting the policy $\pi^{k}=(\pi_{h}^{k})_{h=1}^{H}$

14: Receive private counts $\widetilde{R}_{h}^{k+1}(s,a)$,
$\widetilde{N}_{h}^{k+1}(s,a)$, $\widetilde{N}_{h}^{k+1}(s,a,s^{\prime})$ from
the PRIVATIZER

15: Update policy: $\forall(s,a,h)$,
$\pi_{h}^{k+1}(a|s)=\frac{\pi_{h}^{k}(a|s)\exp(-\eta\widetilde{Q}_{h}^{k}(s,a))}{\sum_{a\in\mathcal{A}}\pi_{h}^{k}(a|s)\exp(-\eta\widetilde{Q}_{h}^{k}(s,a))}$

16: end for

###  D.1 Proof of Theorem 5

Before showing the proof of Theorem 5, we first prove the following lemma.

######  Lemma 18 (Concentration bounds of private estimators).

Fix any $\epsilon\in(0,1]$ and $\delta\in(0,1)$ and take
$B_{n}=\left(\frac{\epsilon
un}{H\log^{1.5}K\log(3SAT/\delta)}\right)^{\frac{1}{1+v}}$ in equation (1).
Then, under Assumption 1, with probability at least $1-2\delta$, uniformly
over all $(s,a,h,k)$,

$|\widetilde{r}_{h}^{k}(s,a)-{r}_{h}(s,a)|\leq\beta_{h}^{k,r}(s,a),\,\|{P_{h}(\cdot|s,a)-\widetilde{P}_{h}^{k}(\cdot|s,a)}\|_{1}\leq\beta_{h}^{k,p}(s,a),$

where

$\displaystyle\beta_{h}^{k,r}(s,a)=\frac{2\tau
E_{\varepsilon,\delta,1}}{\left(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\right)\vee
1}+10u^{\frac{1}{1+v}}\left(\frac{H\log^{1.5}K\log(3SAT/\delta)}{\epsilon\left((\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1\right)}\right)^{\frac{v}{1+v}},$
$\displaystyle\beta_{h}^{k,p}(s,a):=\frac{\sqrt{4S\ln({6AT}/{\delta)}}}{\sqrt{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}}+\frac{SE_{\epsilon,\delta,3}+2E_{\epsilon,{\delta},1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}.$

###### Proof of Lemma 18.

$\beta_{h}^{k,r}(s,a)$ is defined in Lemma 15. Now we prove the concentrated
upper bound for transition probability. From Theorem 2.1 in (Weissman et al.,
2003) and union bound over all $s,a,h,k$, we obtain with probability at least
$1-\delta/2$

$\|P_{h}(\cdot|s,a)-\bar{P}_{h}^{k}(\cdot|s,a)\|_{1}\leq\sqrt{\frac{4S\ln(6AT/\delta)}{{N_{h}^{k}(s,a)\vee
1}}}$ (23)

where
$\bar{P}_{h}^{k}(s^{\prime}|s,a):=\frac{{N}_{h}^{k}(s,a,s^{\prime})}{{{N}_{h}^{k}(s,a)}\vee
1}$ is non-private empirical transition probability.

Now, we turn to bound the transition dynamics. The error between the true
transition probability and the private estimate can be decomposed as

$\displaystyle\sum_{s^{\prime}}|P_{h}(s^{\prime}|,s,a)-\widetilde{P}_{h}^{k}(s^{\prime}|s,a)|$
$\displaystyle=$
$\displaystyle\sum_{s^{\prime}}\left|\frac{\widetilde{N}_{h}^{k}(s,a,s^{\prime})}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}-P_{h}(s^{\prime}|s,a)\right|$ $\displaystyle\leq$
$\displaystyle\underbrace{\sum_{s^{\prime}}\left|\frac{{N}_{h}^{k}(s,a,s^{\prime})}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}-P_{h}(s^{\prime}|s,a)\right|}_{\mathcal{P}_{1}}+\underbrace{\sum_{s^{\prime}}\left|\frac{\widetilde{N}_{h}^{k}(s,a,s^{\prime})-{N}_{h}^{k}(s,a,s^{\prime})}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}\right|}_{\mathcal{P}_{2}}.$

For $\mathcal{P}_{1}$, we have

$\displaystyle\mathcal{P}_{1}=\sum_{s^{\prime}}\left|\frac{N_{h}^{k}(s,a,s^{\prime})}{N_{h}^{k}(s,a)\vee
1}\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}-P_{h}(s^{\prime}|s,a)\right|$ $\displaystyle=$
$\displaystyle\sum_{s^{\prime}}\left|\left(\frac{N_{h}^{k}(s,a,s^{\prime})}{N_{h}^{k}(s,a)\vee
1}-P_{h}(s^{\prime}|s,a)\right)\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}+P_{h}(s^{\prime}|s,a)\left(\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee 1}-1\right)\right|$
$\displaystyle\leq$ $\displaystyle\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}\|\bar{P}_{h}^{k}(\cdot|s,a)-P_{h}(\cdot|s,a)\|_{1}+\sum_{s^{\prime}}\left(P_{h}(s^{\prime}|s,a)\frac{2E_{\epsilon,\delta,1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}\right)$ $\displaystyle\overset{(a)}{\leq}$
$\displaystyle\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\epsilon,\delta,1})\vee
1}\frac{\sqrt{4S\ln({6AT}/{\delta})}}{\sqrt{N_{h}^{k}(s,a)\vee