# Differentially Private Regret Minimization in Episodic Markov Decision
Processes

Sayak Ray Chowdhury 111Indian Institute of Science, Bangalore, India. Email:
<EMAIL_ADDRESS>Xingyu Zhou11footnotemark: 1 222Wayne State University,
Detroit, USA. Email<EMAIL_ADDRESS>Equal contributions

###### Abstract

We study regret minimization in finite horizon tabular Markov decision
processes (MDPs) under the constraints of differential privacy (DP). This is
motivated by the widespread applications of reinforcement learning (RL) in
real-world sequential decision making problems, where protecting users’
sensitive and private information is becoming paramount. We consider two
variants of DP – joint DP (JDP), where a centralized agent is responsible for
protecting users’ sensitive data and local DP (LDP), where information needs
to be protected directly on the user side. We first propose two general
frameworks – one for policy optimization and another for value iteration – for
designing private, optimistic RL algorithms. We then instantiate these
frameworks with suitable privacy mechanisms to satisfy JDP and LDP
requirements, and simultaneously obtain sublinear regret guarantees. The
regret bounds show that under JDP, the cost of privacy is only a lower order
additive term, while for a stronger privacy protection under LDP, the cost
suffered is multiplicative. Finally, the regret bounds are obtained by a
unified analysis, which, we believe, can be extended beyond tabular MDPs.

##  1 Introduction

Reinforcement learning (RL) is a fundamental sequential decision making
problem, where an agent learns to maximize its reward in an unknown
environment through trial and error. Recently, it is ubiquitous in various
personalized services, including healthcare (Gottesman et al., 2019), virtual
assistants (Li et al., 2016), social robots (Gordon et al., 2016) and online
recommendations (Li et al., 2010). In these applications, the learning agent
continuously improves its decision by learning from users’ personal data and
feedback. However, nowadays people are becoming increasingly concerned about
potential privacy leakage in these interactions. For example, in personalized
healthcare, the private data of a patient can be sensitive informations such
as her age, gender, height, weight, medical history, state of the treatment,
etc. Therefore, developing RL algorithms which can protect users’ private data
are of paramount importance in these applications.

| Algorithm | Regret ($\varepsilon$-JDP) | Regret ($\varepsilon$-LDP)
---|---|---|---
PO | Private-UCB-PO | $\widetilde{O}\left(\sqrt{S^{2}AH^{3}T}+S^{2}AH^{3}/\varepsilon\right)$ | $\widetilde{O}\left(\sqrt{S^{2}AH^{3}T}+S^{2}A\sqrt{H^{5}T}/\varepsilon\right)$
VI | Private-UCB-VI | $\widetilde{O}\left(\sqrt{SAH^{3}T}+S^{2}AH^{3}/\varepsilon\right)$ | $\widetilde{O}\left(\sqrt{SAH^{3}T}+S^{2}A\sqrt{H^{5}T}/\varepsilon\right)$
PUCB (Vietri et al., 2020) |  $\widetilde{O}\left(\sqrt{S^{2}AH^{3}T}+S^{2}AH^{3}/\varepsilon\right)$ 333Vietri et al. (2020) claim a $\widetilde{O}\left(\sqrt{SAH^{3}T}+S^{2}AH^{3}/\varepsilon\right)$ regret bound for PUCB. However, to the best of our understanding, we believe the current analysis has gaps (see Section 4), and the best achievable regret for PUCB should have an additional $\sqrt{S}$ factor in the first term. | NA
LDP-OBI (Garcelon et al., 2020) | NA |  $\widetilde{O}\left(\sqrt{S^{2}AH^{3}T}+S^{2}A\sqrt{H^{5}T}/\varepsilon\right)$444Garcelon et al. (2020) consider stationary transition kernels, and show a $\widetilde{O}\left(\sqrt{S^{2}AH^{2}T}+S^{2}A\sqrt{H^{5}T}/\varepsilon\right)$ regret bound for LDP-OBI. For non-stationary transitions, as considered in this work, an additional multiplicative $\sqrt{H}$ factor would appear in the first term of the bound.
Table 1:  Regret comparisons for private RL algorithms on episodic tabular
MDP. $T=KH$ is 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. $\varepsilon>0$ is the desired
privacy level. $\widetilde{O}(\cdot)$ hides
$\operatorname{polylog}\left(S,A,T,1/\delta\right)$ factors, where
$\delta\in(0,1]$ is the desired confidence level.

_Differential privacy_ (DP) (Dwork, 2008) has become a standard in designing
private sequential decision-making algorithms both in the full information
(Jain et al., 2012) and partial or bandit information (Mishra and Thakurta,
2015; Tossou and Dimitrakakis, 2016) settings. Under DP, the learning agent
collects users’ raw data to train its algorithm while ensuring that its output
will not reveal users’ sensitive information. This notion of privacy
protection is suitable for situations, where a user is willing to share her
own information to the agent in order to obtain a service specially tailored
to her needs, but meanwhile she does not like to allow any third party to
infer her private information seeing the output of the learning algorithm
(e.g., Google GBoard). However, a recent body of work (Shariff and Sheffet,
2018; Dubey, 2021) show that the standard DP guarantee is irreconcilable with
sublinear regret in contextual bandits, and thus, a variant of DP, called
_joint differential privacy_ (JDP) (Kearns et al., 2014) is considered.
Another variant of DP, called _local differential privacy_ (LDP) (Duchi et
al., 2013) has recently gained increasing popularity in personalized services
due to its stronger privacy protection. It has been studied in various bandit
settings recently (Ren et al., 2020; Zheng et al., 2020; Zhou and Tan, 2020).
Under LDP, each user’s raw data is directly protected before being sent to the
learning agent. Thus, the learning agent only has access to privatized data to
train its algorithm, which often leads to a worse regret guarantee compared to
DP or JDP.

In contrast to the vast amount of work in private bandit algorithms, much less
attention are given to address privacy in RL problems. To the best of our
knowledge, Vietri et al. (2020) propose the first RL algorithm – PUCB – for
regret minimization with JDP guarantee in tabular finite state, finite action
MDPs. On the other hand, Garcelon et al. (2020) design the first private RL
algorithm – LDP-OBI – with regret and LDP guarantees. Recently, Chowdhury et
al. (2021) study linear quadratic regulators under the JDP constraint. It is
worth noting that all these prior work consider only value-based RL
algorithms, and a study on policy-based private RL algorithms remains elusive.
Recently, policy optimization (PO) has seen great success in many real-world
applications, especially when coupled with deep neural networks (Silver et
al., 2017; Duan et al., 2016; Wang et al., 2018), and a variety of PO based
algorithms have been proposed (Williams, 1992; Kakade, 2001; Schulman et al.,
2015, 2017; Konda and Tsitsiklis, 2000). The theoretical understandings of PO
have also been studied in both computational (i.e., convergence) perspective
(Liu et al., 2019; Wang et al., 2019a) and statistical (i.e., regret)
perspective (Cai et al., 2020; Efroni et al., 2020a). Thus, one fundamental
question to ask is how to build on existing understandings of non-private PO
algorithms to design sample-efficient policy-based RL algorithms with general
privacy guarantees (e.g., JDP and LDP), which is the main motivation behind
this work. Also, the existing regret bounds in both Vietri et al. (2020) and
Garcelon et al. (2020) for private valued-iteration (VI) based RL algorithms
are loose. Moreover, the algorithm design and regret analysis under JDP in
Vietri et al. (2020) and the ones under LDP in Garcelon et al. (2020) follow
different approaches (e.g., choice of exploration bonus terms and
corresponding analysis). Thus, another important question to ask is whether
one can obtain tighter regret bounds for VI based private RL algorithms via a
unified framework under general privacy requirements.

Contributions. Motivated by the two questions above, we make the following
contributions.

  * •

We present a general framework – Private-UCB-PO – for designing private
policy-based optimistic RL algorithms in tabular MDPs. This framework enables
us to establish the first regret bounds for PO under both JDP and LDP
requirements by instantiating it with suitable private mechanisms – the
Central-Privatizer and the Local-Privatizer – respectively.

  * •

We revisit private optimistic value-iteration in tabular MDPs by proposing a
general framework – Private-UCB-VI – for it. This framework allows us to
improve upon the existing regret bounds under both JDP and LDP constraints
using a unified analysis technique.

  * •

Our regret bounds show that for both policy-based and value-based private RL
algorithms, the cost of JDP guarantee is only a lower-order additive term
compared to the non-private regret. In contrast, under the stringer LDP
requirement, the cost suffered is multiplicative and is of the same order. Our
regret bounds and their comparison to the existing ones is summarised in Table
1.

Related work. Beside the papers mentioned above, there are other related work
on differentially private online learning (Guha Thakurta and Smith, 2013;
Agarwal and Singh, 2017) and multi-armed bandits (Tossou and Dimitrakakis,
2017; Hu et al., 2021; Sajed and Sheffet, 2019; Gajane et al., 2018; Chen et
al., 2020). In the RL setting, in addition to Vietri et al. (2020); Garcelon
et al. (2020) that focus on value-iteration based regret minimization
algorithms under privacy constraints, Balle et al. (2016) considers private
policy evaluation with linear function approximation. For MDPs with continuous
state spaces, Wang and Hegde (2019) proposes a variant of $Q$-learning to
protect the rewards information by directly injecting noise into value
functions. Recently, a distributed actor-critic RL algorithm under LDP is
proposed in Ono and Takahashi (2020) but without any regret guarantee. While
there are recent advances in regret guarantees for policy optimization (Cai et
al., 2020; Efroni et al., 2020a), we are not aware of any existing work on
private policy optimization. Thus, our work takes the first step towards a
unified framework for private policy-based RL algorithms in tabular MDPs with
general privacy and regret guarantees.

##  2 Problem formulation

In this section, we recall the basics of episodic Markov Decision Processes
and introduce the notion of differential privacy in reinforcement learning.

###  2.1 Learning model and regret in episodic MDPs

We consider episodic reinforcement learning (RL) in a finite horizon
stochastic Markov decision process (MDP) (Puterman, 1994; Sutton, 1988) given
by a tuple $(\mathcal{S},\mathcal{A},H,(P_{h})_{h=1}^{H},(c_{h})_{h=1}^{H})$,
where $\mathcal{S}$ and $\mathcal{A}$ are state and action spaces with
cardinalities $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
$c_{h}(s,a)$ is the mean of the cost distribution at step $h$ supported on
$[0,1]$. 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 all $s\in\mathcal{S}$. The agent
would like to find a policy $\pi$ that minimizes the long term expected cost
starting from every state $s\in\mathcal{S}$ and every step $h\in[H]$, defined
as

$\displaystyle
V^{\pi}_{h}(s):=\mathbb{E}\left[\sum\nolimits_{h^{\prime}=h}^{H}c_{h^{\prime}}(s_{h^{\prime}},a_{h}^{\prime})\mid
s_{h}=s,\pi\right],$

where the expectation is with respect to the randomness of the transition
kernel and the policy. We call $V_{h}^{\pi}$ the value function of policy
$\pi$ at step $h$. Now, defining the $Q$-function of policy $\pi$ at step $h$
as

$\displaystyle
Q^{\pi}_{h}(s,a):=\mathbb{E}\left[\sum\nolimits_{h^{\prime}=h}^{H}c_{h^{\prime}}(s_{h^{\prime}},a_{h}^{\prime}))\mid
s_{h}=s,a_{h}=a,\pi\right],$

we obtain
$Q^{\pi}_{h}(s,a)=c_{h}(s,a)+\sum_{s^{\prime}\in\mathcal{S}}V^{\pi}_{h+1}(s^{\prime})P_{h}(s^{\prime}|s,a)$
and $V_{h}^{\pi}(s)=\sum_{a\in\mathcal{A}}Q^{\pi}_{h}(s,a)\pi_{h}(a|s)$.

A policy $\pi^{*}$ is said to be optimal if it minimizes the value for all
states $s$ and step $h$ simultaneously, and the corresponding optimal value
function is denoted by $V^{*}_{h}(s)=\min_{\pi\in\Pi}V^{\pi}_{h}(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 costs $c_{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
$\\{s_{1}^{k},a_{1}^{k},c_{1}^{k},\ldots,s_{H}^{k},a_{H}^{k},c_{H}^{k},s_{H+1}^{k}\\}$
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, $c_{h}^{k}\in[0,1]$ denotes the (random) cost suffered by the agent
with the mean value $c_{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. The initial state
$s_{1}^{k}$ is assumed to be fixed and history independent. We measure
performance of the agent by the cumulative (pseudo) regret accumulated over
$K$ episodes, defined as

$\displaystyle
R(T):=\sum\nolimits_{k=1}^{K}\left[V_{1}^{\pi^{k}}(s_{1}^{k})-V_{1}^{*}(s_{1}^{k})\right],$

where $T=KH$ denotes the total number of steps. We seek algorithms with regret
that is sublinear in $T$, which demonstrates the agent’s ability to act near
optimally.

###  2.2 Differential privacy in episodic RL

In the episodic RL setting described above, it is natural to view each episode
$k\in[K]$ as a trajectory associated to 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$
unique555Uniqueness is assumed wlog, as for a returning user one can group her
with her previous occurrences. 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 cost and state responses
$(c_{h}^{k},s_{h+1}^{k})_{h=1}^{H}$ she gives to the actions
$(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}$. Informally, we will be interested in (centralized)
randomized mechanisms (in this case, RL agents) $\mathcal{M}$ so that the
knowledge of the output $\mathcal{M}(U_{k})$ and all but the $k$-th user
$u_{k}$ does not reveal ‘much’ information about $u_{k}$. We formalize this in
the following definition.

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

For any $\varepsilon\geq 0$ and $\delta\in[0,1]$, a mechanism
$\mathcal{M}:\mathcal{U}^{K}\rightarrow\mathcal{A}^{KH}$ is
$(\varepsilon,\delta)$-differentially private if for all
$U_{K},U^{\prime}_{K}\in\mathcal{U}^{K}$ differing on a single user and for
all subset of actions $\mathcal{A}_{0}\subset\mathcal{A}^{KH}$,

$\mathbb{P}\left[{\mathcal{M}(U_{K})\in\mathcal{A}_{0}}\right]\leq\exp(\varepsilon)\mathbb{P}\left[{\mathcal{M}(U^{\prime}_{K})\in\mathcal{A}_{0}}\right]+\delta~{}.$

If $\delta=0$, we call the mechanism $\mathcal{M}$ to be
$\varepsilon$-differentially private ($\varepsilon$-DP).

This is a direct adaptation of the classic notion of differential privacy
(Dwork et al., 2014). However, we need to relax this definition for our
purpose, because although the actions recommended to the user $u_{k}$ have
only a small effect on the types (i.e., state and cost responses) of other
users participating in the RL protocol, those can reveal a lot of information
about the type of the user $u_{k}$. Thus, it becomes hard to privately
recommend the actions to user $u_{k}$ while protecting the privacy of it’s
type, i.e., it’s state and cost responses to the suggested actions. Hence, to
preserve the privacy of individual users, we consider the notion of _joint
differential privacy_ (JDP) (Kearns et al., 2014), which requires that
simultaneously for all user $u_{k}$, the joint distribution of the actions
recommended to all users other than $u_{k}$ be differentially private in the
type of the user $u_{k}$. It weakens the constraint of DP only in that the
actions suggested specifically to $u_{k}$ may be sensitive in her type (state
and cost responses). However, JDP is still a very strong definition since it
protects $u_{k}$ from any arbitrary collusion of other users against her, so
long as she does not herself make the actions suggested to her public. To this
end, we let
$\mathcal{M}_{-k}(U_{k}):=\mathcal{M}(U_{k})\setminus(a_{h}^{k})_{h=1}^{H}$ to
denote all the actions chosen by the agent $\mathcal{M}$ excluding those
recommended to $u_{k}$ and formally define JDP as follows.

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

For any $\varepsilon\\!\geq\\!0$, a mechanism
$\mathcal{M}\\!:\\!\mathcal{U}^{K}\\!\rightarrow\\!\mathcal{A}^{KH}$ is
$\varepsilon$-joint differentially private if for all $k\\!\in\\![K]$, for all
user sequences $U_{K},U^{\prime}_{K}\\!\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}(U_{K})\in\mathcal{A}_{-k}}\right]\leq\exp(\varepsilon)\mathbb{P}\left[{\mathcal{M}_{-k}(U^{\prime}_{K})\in\mathcal{A}_{-k}}\right].$

JDP has been used extensively in private mechanism design (Kearns et al.,
2014), in private matching and allocation problems (Hsu et al., 2016), in
designing privacy-preserving algorithms for linear contextual bandits (Shariff
and Sheffet, 2018), and it has been introduced in private tabular RL by Vietri
et al. (2020).

JDP allows the agent to observe the data (i.e., the entire trajectory of
state-action-cost sequence) associated with each user and the privacy burden
lies on the agent itself. In some scenarios, however, the users may not even
be willing to share it’s data with the agent directly. This motivates a
stringer notion of privacy protection, called the _local differential privacy_
(LDP) (Duchi et al., 2013). In this setting, each user is assumed to have her
own privacy mechanism that can do randomized mapping on its data to guarantee
privacy. To this end, we denote by $X$ a trajectory
$(s_{h},a_{h},c_{h},s_{h+1})_{h=1}^{H}$ and by $\mathcal{X}$ the set of all
possible trajectories. We write $\mathcal{M}^{\prime}(X)$ to denote the
privatized trajectory generated by a (local) randomized mechanism
$\mathcal{M}^{\prime}$. With this notation, we now formally define LDP for our
RL protocol.

######  Definition 2.3 (Local Differential Privacy (LDP)).

For any $\varepsilon\geq 0$, a mechanism $\mathcal{M}^{\prime}$ is
$\varepsilon$-local differentially private if for all trajectories
$X,X^{\prime}\in\mathcal{X}$ and for all possible subsets
$\mathcal{E}_{0}\subset\\{\mathcal{M}^{\prime}(X)|X\in\mathcal{X}\\}$,

$\mathbb{P}\left[{\mathcal{M}^{\prime}(X)\in\mathcal{E}_{0}}\right]\leq\exp(\varepsilon)\mathbb{P}\left[{\mathcal{M}^{\prime}(X^{\prime})\in\mathcal{E}_{0}}\right].$

LDP ensures that if any adversary (can be the RL agent itself) observes the
output of the privacy mechanism $\mathcal{M}^{\prime}$ for two different
trajectories, then it is statistically difficult for it to guess which output
is from which trajectory. This has been used extensively in multi-armed
bandits (Zheng et al., 2020; Ren et al., 2020), and introduced in private
tabular RL by Garcelon et al. (2020).

Input: Number of episodes $K$, time horizon $H$, privacy level
$\varepsilon>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{C}_{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_{\varepsilon,\delta,1},E_{\varepsilon,\delta,2}$ 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{c}_{h}^{k}(s,a)$ and $\widetilde{P}_{h}^{k}(s,a)$
$\forall(s,a)$ as in (1) using the private counts

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

9 Compute: $\forall(s,a)$,
$\widetilde{{Q}}_{h}^{k}(s,a)=\min\\{H-h+1,\max\\{0,\widetilde{c}_{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)\\}\\}$

10 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)$

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

12 Receive private counts $\widetilde{C}_{h}^{k+1}(s,a)$,
$\widetilde{N}_{h}^{k+1}(s,a)$, $\widetilde{N}_{h}^{k+1}(s,a,s^{\prime})$ from
the Privatizer

13 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))}$

Algorithm 1 Private-UCB-PO

##  3 Private Policy Optimization

In this section, we introduce a policy-optimization based private RL algorithm
Private-UCB-PO (Algorithm 1) that can be instantiated with any private
mechanism (henceforth, referred as a Privatizer) satisfying a general
condition. We derive a generic regret bound for Private-UCB-PO, which can be
applied to obtain bounds under JDP and LDP requirements by instantiating
Private-UCB-PO with a Central-Privatizer and a Local-Privatizer, respectively.
All the proofs are deferred to the appendix.

Let us first introduce some notations. We denote by
$N_{h}^{k}(s,a):=\sum_{k^{\prime}=1}^{k-1}\mathbb{I}\\{s_{h}^{k^{\prime}}=s,a_{h}^{k^{\prime}}=a\\}$,
the number of times that the agent has visited state-action pair $(s,a)$ at
step $h$ _before_ episode $k$. Similarly,
$N_{h}^{k}(s,a,s^{\prime}):=\sum_{k^{\prime}=1}^{k-1}\mathbb{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,
$C_{h}^{k}(s,a):=\sum_{k^{\prime}=1}^{k-1}\mathbb{I}\\{s_{h}^{k^{\prime}}=s,a_{h}^{k^{\prime}}=a\\}c_{h}^{k^{\prime}}$
denotes the total cost suffered by taking action $a$ on state $s$ and step $h$
_before_ episode $k$. In non-private learning, these counters are sufficient
to find estimates of the transition kernels $(P_{h})_{h}$ and mean cost
functions $(c_{h})_{h}$ to design the policy $(\pi_{h}^{k})_{h}$ for episode
$k$. However, in private learning, the challenge is that the counters depend
on users’ state and cost responses to suggested actions, which is considered
sensitive information. Therefore, the Privatizer must release the counts in a
privacy-preserving way on which the learning agent would rely. To this end, we
let $\widetilde{N}_{h}^{k}(s,a)$, $\widetilde{C}_{h}^{k}(s,a)$, and
$\widetilde{N}_{h}^{k}(s,a,s^{\prime})$ to denote the privatized versions of
$N_{h}^{k}(s,a)$, $C_{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 (both Local and Central), which roughly means that with high
probability the private counts are close to the actual ones.

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

For any $\varepsilon>0$ and $\delta\in(0,1]$, there exist functions
$E_{\varepsilon,\delta,1},E_{\varepsilon,\delta,2}>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)
$|\widetilde{N}_{h}^{k}(s,a)-{N}_{h}^{k}(s,a)|\leq E_{\varepsilon,\delta,1}$,
(ii) $|\widetilde{C}_{h}^{k}(s,a)-{C}_{h}^{k}(s,a)|\leq
E_{\varepsilon,\delta,1}$, and (iii)
$|\widetilde{N}_{h}^{k}(s,a,s^{\prime})-{N}_{h}^{k}(s,a,s^{\prime})|\leq
E_{\varepsilon,\delta,2}$.

In the following, we assume Assumption 1 holds. Then, we define, for all
$(s,a,h,k)$, the _private_ mean empirical costs and _private_ empirical
transition probabilities as

$\begin{split}\widetilde{c}_{h}^{k}(s,a)&:=\frac{\widetilde{C}_{h}^{k}(s,a)}{\max\\{1,\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\\}}\\\
\widetilde{P}_{h}^{k}(s^{\prime}|s,a)&:=\frac{\widetilde{N}_{h}^{k}(s,a,s^{\prime})}{\max\\{1,\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\\}}~{}.\end{split}$
(1)

The following concentration bounds on the private estimates will be the key to
our algorithm design.

######  Lemma 3.1 (Concentration of private estimates).

Fix any $\varepsilon>0$ and $\delta\in(0,1]$. Then, under Assumption 1, with
probability at least $1-2\delta$, uniformly over all $(s,a,h,k)$,

$\displaystyle|c_{h}(s,a)-\widetilde{c}_{h}^{k}(s,a)|\leq\beta_{h}^{k,c}(s,a),\;\;\left\lVert
P_{h}(\cdot|s,a)-\widetilde{P}_{h}^{k}(\cdot|s,a)\right\rVert_{1}\leq\beta_{h}^{k,p}(s,a),$

where
$\beta_{h}^{k,c}(s,a):=\frac{L_{c}(\delta)}{\sqrt{\max\\{1,\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\\}}}+\frac{3E_{\varepsilon,\delta,1}}{\max\\{1,\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\\}}$,
$L_{c}(\delta):=\sqrt{2\ln\frac{4SAT}{\delta}}$,
$\beta_{h}^{k,p}(s,a):=\frac{L_{p}(\delta)}{\sqrt{\max\\{1,\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\\}}}+\frac{SE_{\varepsilon,\delta,2}+2E_{\varepsilon,{\delta},1}}{\max\\{1,\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\\}}$,
and $L_{p}(\delta):=\sqrt{4S\ln\frac{6SAT}{\delta}}$.

Private-UCB-PO algorithm. Private-UCB-PO (Algorithm 1) is a private policy
optimization (PO) algorithm based on the celebrated upper confidence bound
(UCB) philosophy (Auer et al., 2002; Jaksch et al., 2010). Similar to the non-
private setting (Efroni et al., 2020a), it basically has two stages at each
episode $k$: _policy evaluation_ and _policy improvement_. In the policy
evaluation stage, it evaluates the policy $\pi^{k}$ based on $k-1$ historical
trajectories. In contrast to the non-private case, Private-UCB-PO relies only
on the private counts (returned by the Privatizer) to calculate the private
mean empirical costs and private empirical transitions. These two along with a
UCB exploration bonus term (which also depends only on private counts) are
used to compute $Q$-function estimates. The $Q$-estimates are then truncated
and corresponding value estimates are computed by taking their expectation
with respect to the policy. Next, a new trajectory is rolled out by acting the
policy $\pi^{k}$ and the Privatizer translates all non-private counts into the
private ones to be used for the policy evaluation in the next episode.
Finally, in the policy improvement stage, Private-UCB-PO employs a ‘soft’
update of the current policy $\pi^{k}$ by following a standard mirror-descent
step together with a Kullback–Leibler (KL) divergence proximity term (Beck and
Teboulle, 2003; Cai et al., 2020; Efroni et al., 2020a). The following theorem
presents a general regret bound of Private-UCB-PO (Algorithm 1) when
instantiated with any Privatizer (Local or Central) that satisfies Assumption
1.

######  Theorem 3.2 (Regret bound of Private-UCB-PO).

Fix any $\varepsilon>0$ and $\delta\in(0,1]$ and set $\eta=\sqrt{2\log
A/(H^{2}K)}$. Then, under Assumption 1, with probability at least $1-\delta$,
the cumulative regret of Private-UCB-PO is

$\displaystyle\mathcal{R}(T)$
$\displaystyle=\widetilde{O}\left(\sqrt{S^{2}AH^{3}T}+\sqrt{S^{3}A^{2}H^{4}}\right)+\widetilde{O}\left(E_{\varepsilon,\delta,2}S^{2}AH^{2}+E_{\varepsilon,\delta,1}SAH^{2}\right).$

######  Remark 3.3 (Cost of privacy).

Theorem 3.2 shows that regret of Private-UCB-PO is lower bounded by the regret
in non-private setting (Efroni et al., 2020a, Theorem 1), and depends directly
on the privacy parameter $\varepsilon$ through the permitted precision levels
$E_{\varepsilon,\delta,1}$ and $E_{\varepsilon,\delta,2}$ of the Privatizer.
Thus, choosing $E_{\varepsilon,\delta,1},E_{\varepsilon,\delta,2}$
appropriately to guarantee JDP or LDP, we can obtain regret bounds under both
forms of privacy. The cost of privacy, as we shall see in Section 5, is lower
order than the non-private regret under JDP, and is of the same order under
the stringer requirement of LDP.666The lower order terms scale with $S^{2}$,
which is quite common for optimistic tabular RL algorithms (Azar et al., 2017;
Dann et al., 2017).

Proof sketch. We first decompose the regret as in the non-private setting
(Efroni et al., 2020a):

$\displaystyle\mathcal{R}(T)$
$\displaystyle=\sum\nolimits_{k=1}^{K}\left(V_{1}^{\pi^{k}}(s_{1}^{k})-V_{1}^{\pi^{*}}(s_{1}^{k})\right)=\sum\nolimits_{k=1}^{k}\left(V_{1}^{\pi^{k}}(s_{1}^{k})-\widetilde{V}_{1}^{k}(s_{1}^{k})+\widetilde{V}_{1}^{k}(s_{1}^{k})-V_{1}^{\pi^{*}}(s_{1}^{k})\right)$
$\displaystyle=\underbrace{\sum\nolimits_{k=1}^{k}\left(V_{1}^{\pi^{k}}(s_{1}^{k})-\widetilde{V}_{1}^{k}(s_{1}^{k})\right)}_{\mathcal{T}_{1}}+\underbrace{\sum\nolimits_{k=1}^{K}\sum\nolimits_{h=1}^{H}\mathbb{E}\left[\langle\widetilde{Q}_{h}^{k}(s_{h},\cdot),\pi_{h}^{k}(\cdot|s_{h})-\pi_{h}^{*}(\cdot|s_{h})\rangle|s_{1}^{k},\pi^{*}\right]}_{\mathcal{T}_{2}}$
$\displaystyle\quad\quad+\underbrace{\sum\nolimits_{k=1}^{K}\sum\nolimits_{h=1}^{H}\mathbb{E}\left[\widetilde{Q}_{h}^{k}(s_{h},a_{h})-c_{h}(s_{h},a_{h})-P_{h}(\cdot|s_{h},a_{h})\widetilde{V}_{h+1}^{k}|s_{1}^{k},\pi^{*}\right]}_{\mathcal{T}_{3}}.$

We then bound each of the three terms. In particular, $\mathcal{T}_{2}$ and
$\mathcal{T}_{3}$ have the same bounds as in the non-private case.
Specifically, by setting $\eta=\sqrt{2\log A/(H^{2}K)}$, we can show that
$\mathcal{T}_{2}\leq\sqrt{2H^{4}K\log A}$ via a standard online mirror descent
analysis, because $\widetilde{Q}_{h}^{k}\in[0,H]$ by design. Furthermore, due
to Lemma 3.1 and our choice of bonus terms, we have $\mathcal{T}_{3}\leq 0$.
The key is to bound $\mathcal{T}_{1}$. By the update rule of $Q$-estimate and
the choice of bonus terms in Private-UCB-PO, we can bound $\mathcal{T}_{1}$ by
the sum of expected bonus terms, i.e.,

$\displaystyle\mathcal{T}_{1}\leq\underbrace{\sum\nolimits_{k=1}^{K}\sum\nolimits_{h=1}^{H}\mathbb{E}\left[2\beta_{h}^{k,c}(s_{h},a_{h})|s_{1}^{k},\pi^{k}\right]}_{\text{Term(i)}}+\underbrace{H\sum\nolimits_{k=1}^{K}\sum\nolimits_{h=1}^{H}\mathbb{E}\left[2\beta_{h}^{k,p}(s_{h},a_{h})|s_{1}^{k},\pi^{k}\right]}_{\text{Term(ii)}}$

Now, by Assumption 1 and the definition of exploration bonus
$\beta_{h}^{k,c}(s,a)$ in Lemma 3.1, we have

Term(i)
$\displaystyle\leq\sum\nolimits_{k=1}^{K}\sum\nolimits_{h=1}^{H}\mathbb{E}\left[\frac{L_{c}(\delta)}{\sqrt{\max\\{{N}_{h}^{k}(s_{h},a_{h}),1\\}}}+\frac{3E_{\varepsilon,\delta,1}}{\max\\{N_{h}^{k}(s_{h},a_{h}),1\\}}|s_{1}^{k},\pi^{k}\right].$

Note the presence of an additive privacy dependent term. Similarly, we obtain

$\displaystyle\text{Term(ii)}\leq
H\sum\nolimits_{k=1}^{K}\sum\nolimits_{h=1}^{H}\mathbb{E}\left[\frac{L_{p}(\delta)}{\sqrt{\max\\{N_{h}^{k}(s_{h},a_{h}),1\\}}}+\frac{SE_{\varepsilon,\delta,2}+2E_{\varepsilon,\delta,1}}{\max\\{{N}_{h}^{k}(s_{h},a_{h}),1\\}}|s_{1}^{k},\pi^{k}\right].$

We bound Term(i) and Term(ii) by showing that

$\displaystyle\sum\nolimits_{k=1}^{K}\sum\nolimits_{h=1}^{H}\mathbb{E}\left[\frac{1}{\max\\{1,N_{h}^{k}(s_{h},a_{h})\\}}|\mathcal{F}_{k-1}\right]$
$\displaystyle=O\left(SAH\log T+H\log(H/\delta)\right),$
$\displaystyle\sum\nolimits_{k=1}^{K}\sum\nolimits_{h=1}^{H}\mathbb{E}\left[\frac{1}{\sqrt{\max\\{1,N_{h}^{k}(s_{h},a_{h})\\}}}|\mathcal{F}_{k-1}\right]$
$\displaystyle=O\left(\sqrt{SAHT}+SAH\log T+H\log(H/\delta)\right)$

with high probability. These are generalization of results proved under
stationary transition model (Efroni et al., 2019; Zanette and Brunskill, 2019)
to our non-stationary setting (similar results were stated in (Efroni et al.,
2020b, a), but without proofs). Finally, putting everything together, we
complete the proof. ∎

##  4 Private UCB-VI Revisited

In this section, we turn to investigate value-iteration based private RL
algorithms. It is worth noting that private valued-based RL algorithms have
been studied under both JDP and LDP requirements (Vietri et al., 2020;
Garcelon et al., 2020). However, to the best of our understanding, the regret
analysis of the JDP algorithm presented in Vietri et al. (2020) has gaps and
does not support the claimed result.777The gap lies in Vietri et al. (2020,
Lemma 18) in which the private estimates were incorrectly used as the true
cost and transition functions. This lead to a simpler but incorrect regret
decomposition since it omits the ‘error’ term between the private estimates
and true values. Moreover, the error term cannot be simply upper bounded by
its current bonus term ($\widetilde{\text{conf}}_{t}$ in Vietri et al. (2020,
Algorithm 3)) since one cannot directly use Hoeffding’s inequality due to the
fact that the value function is not fixed in this term (please refer to
Appendix for more detailed discussions). Under LDP, the regret bound presented
in Garcelon et al. (2020) is sub-optimal in the cardinality of the state space
and as the authors have remarked, it is possible to achieve the optimal
scaling using a refined analysis. Motivated by this, we revisit private value
iteration by designing an optimistic algorithm Private-UCB-VI (Algorithm 2)
that can be instantiated with a Privatizer (Central and Local) to achieve both
JDP and LDP.

Private-UCB-VI algorithm. Our algorithm design principle is again based on the
UCB philosophy, the private estimates defined in (1) and a value-aware
concentration result for the estimates stated in Lemma 4.1 below. Similar to
the non-private setting (Azar et al., 2017), Private-UCB-VI (Algorithm 2)
follows the procedure of optimistic value iteration. Specifically, at each
episode $k$, using the private counts and a private UCB bonus term, it first
compute private $Q$-estimates and value estimates using optimistic Bellman
recursion. Next, a greedy policy $\pi^{k}$ is obtained directly from the
estimated $Q$-function. Finally, a trajectory is rolled out by acting the
policy $\pi^{k}$ and then Privatizer translates all non-private statistics
into private ones to be used in the next episode.

######  Lemma 4.1 (Refined concentration of private estimates).

Fix any $\varepsilon>0$ and $\delta\in(0,1)$. Then, under Assumption 1, with
probability at least $1-3\delta$, uniformly over all $(s,a,s^{\prime},h,k)$,

$\displaystyle|c_{h}(s,a)-\widetilde{c}_{h}^{k}(s,a)|$
$\displaystyle\leq\beta_{h}^{k,c}(s,a),$
$\displaystyle\left|(\widetilde{P}_{h}^{k}-P_{h}){V}_{h+1}^{*}(s,a)\right|$
$\displaystyle\leq\beta_{h}^{k,pv}(s,a),$
$\displaystyle|P_{h}(s^{\prime}|s,a)-\widetilde{P}_{h}^{k}(s^{\prime}|s,a)|$
$\displaystyle\leq
C\sqrt{\frac{L^{\prime}(\delta)P_{h}(s^{\prime}|s,a)}{\max\\{1,\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\\}}}+\frac{CL^{\prime}(\delta)+2E_{\varepsilon,\delta,1}+E_{\varepsilon,\delta,2}}{\max\\{1,\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\\}},$

where $\beta_{h}^{k,c}(s,a)$ and $L_{c}(\delta)$ is as defined in Lemma 3.1,
$(PV_{h+1})(s,a):=\sum_{s^{\prime}}P(s^{\prime}|s,a)V_{h+1}(s^{\prime})$,
$\beta_{h}^{k,pv}(s,a):=\frac{HL_{c}(\delta)}{\sqrt{\max\\{1,\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\\}}}+\frac{H(SE_{\varepsilon,\delta,2}+2E_{\varepsilon,\delta,1})}{\max\\{1,\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1}\\}}$,
$C>0$ is some constant, and
$L^{\prime}(\delta):=\log\left(\frac{6SAT}{\delta}\right)$.

The bonus term $\beta_{h}^{k,pv}$ in Private-UCB-VI does not have the factor
$\sqrt{S}$ in the leading term compared to $\beta_{h}^{k,p}$ in Private-UCB-
PO. This is achieved by following a similar idea in UCB-VI (Azar et al.,
2017). That is, instead of bounding the transition dynamics as in Lemma 3.1,
we maintain a confidence bound directly over the optimal value function (the
second result in Lemma 4.1). Due to this, we have an extra term in the regret
bound, which can be carefully bounded by using a Bernstein-type inequality
(the third result in Lemma 4.1). These two steps enable us to obtain an
improved dependence on $S$ in the regret bound compared to existing private
value-based algorithms (Vietri et al., 2020; Garcelon et al., 2020) under both
JDP and LDP. This is stated formally in the next theorem, which presents a
general regret bound of Private-UCB-VI (Algorithm 2) when instantiated with
any Privatizer (Local or Central).

######  Theorem 4.2 (Regret bound for Private-UCB-VI).

Fix any $\varepsilon>0$ and $\delta\in(0,1]$. Then, under Assumption 1, with
probability $\geq 1-\delta$, the regret of Private-UCB-VI is

$\displaystyle\mathcal{R}(T)$
$\displaystyle=\widetilde{O}\left(\sqrt{SAH^{3}T}+S^{2}AH^{3}\right)+\widetilde{O}\left(S^{2}AH^{2}E_{\varepsilon,\delta,1}+S^{2}AH^{2}E_{\varepsilon,\delta,2}\right).$

######  Remark 4.3 (Cost of privacy).

Similar to Private-UCB-PO, the regret of Private-UCB-VI is lower bounded by
the regret in non-private setting (see Azar et al. (2017, Theorem 1)),888In
the non-private setting, Azar et al. (2017) assume stationary transition
kernels $P_{h}=P$ for all $h$. We consider non-stationary kernels, which adds
a multiplicative $\sqrt{H}$ factor in our non-private regret. and the privacy
parameter appear only in the lower order terms.

######  Remark 4.4 (VI vs. PO).

The regret bound of Private-UCB-VI is a $\sqrt{S}$ factor better in the
leading privacy-independent term compared to Private-UCB-PO. This follows the
same pattern as in the non-private case, i.e., UCB-VI (Azar et al., 2017) vs.
OPPO (Efroni et al., 2020a).

Input: Number of episodes $K$, time horizon $H$, privacy level
$\varepsilon>0$, a Privatizer (Local or Central) and confidence level
$\delta\in(0,1]$

1 Initialize private counts $\widetilde{C}_{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)$

2 Set precision levels $E_{\varepsilon,\delta,1},E_{\varepsilon,\delta,2}$ of
the Privatizer

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

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

5 for  _$h=H,H-1,\ldots,1$_ do

6 Compute $\widetilde{c}_{h}^{k}(s,a)$ and
$\widetilde{P}_{h}^{k}(s^{\prime}|s,a)$ $\forall(s,a,s^{\prime})$ as in (1)
using the private counts

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

8 Compute: $\forall(s,a)$,
$\widetilde{{Q}}_{h}^{k}(s,a)=\min\\{H-h+1,\max\\{0,\widetilde{c}_{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)\\}\\}$

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

10 Compute policy: $\forall(s,h)$,
$\pi_{h}^{k}(s)=\mathop{\mathrm{argmin}}_{a\in\mathcal{A}}\widetilde{Q}_{h}^{k}(s,a)$
(with breaking ties arbitrarily)

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

12 Receive private counts $\widetilde{C}_{h}^{k+1}(s,a)$,
$\widetilde{N}_{h}^{k+1}(s,a)$, $\widetilde{N}_{h}^{k+1}(s,a,s^{\prime})$ from
the Privatizer

Algorithm 2 Private-UCB-VI

##  5 Privacy and regret guarantees

In this section, we instantiate Private-UCB-PO and Private-UCB-VI using a
Central-Privatizer and a Local-Privatizer, and derive corresponding privacy
and regret guarantees.

###  5.1 Achieving JDP using Central-Privatizer

The Central-Privatizer runs a private $K$-bounded binary-tree mechanism
(counter) (Chan et al., 2010) for each count
$N_{h}^{k}(s,a),C_{h}^{k}(s,a),N_{h}^{k}(s,a,s^{\prime})$, i.e. it uses
$2SAH+S^{2}AH$ counters in total. Let us focus on the counters – there are
$SAH$ many of thems – for the number of visited states $N_{h}^{k}(s,a)$. Each
counter takes as input the data stream $\sigma_{h}(s,a)\in\\{0,1\\}^{K}$,
where the $j$-th bit
$\sigma_{h}^{j}(s,a):=\mathbb{I}\\{s_{h}^{j}=s,a_{h}^{j}=a\\}$ denotes whether
the pair $(s,a)$ is encountered or not at step $h$ of episode $j$, and at the
start of each episode $k$, release a private version
$\widetilde{N}_{h}^{k}(s,a)$ of the count
$N_{h}^{k}(s,a):=\sum_{j=1}^{k-1}\sigma_{h}^{j}(s,a)$. Let us now discuss how
private counts are computed. To this end, we let
$N_{h}^{i,j}(s,a)=\sum_{k=i}^{j}\sigma_{h}^{k}(s,a)$ to denote a partial sum
($\mathrm{P}\text{-}\mathrm{sum}$) of the counts in episodes $i$ through $j$,
and consider a binary interval tree, each leaf node of which represents an
episode (i.e., the tree has $k-1$ leaf nodes at the start of episode $k$).
Each interior node of the tree represents the range of episodes covered by its
children. At the start of episode $k$, first a noisy
$\mathrm{P}\text{-}\mathrm{sum}$ corresponding to each node in the tree is
released by perturbing it with an independent Laplace noise
$\text{Lap}(\frac{1}{\varepsilon^{\prime}})$, where $\varepsilon^{\prime}>0$
is a given privacy parameter.999A random variable $X\sim\text{Lap}(b)$, with
scale parameter $b>0$, if $\forall x\in\mathbb{R}$, it’s p.d.f. is given by
$f_{X}(x)=\frac{1}{2b}\exp(-|x|/b)$. Then, the private count
$\widetilde{N}_{h}^{k}(s,a)$ is computed by summing up the noisy
$\mathrm{P}\text{-}\mathrm{sums}$ released by the set of nodes – which has
cardinality at most $O(\log k)$ – that uniquely cover the range $[1,k-1]$.
Observe that, at the end of episode $k$, the counter only needs to store noisy
$\mathrm{P}\text{-}\mathrm{sums}$ required for computing private counts at
future episodes, and can safely discard $\mathrm{P}\text{-}\mathrm{sums}$
those are no longer needed.

The counters corresponding to empirical rewards $C_{h}^{k}(s,a)$ and state
transitions $N_{h}^{k}(s,a,s^{\prime})$ follow the same underlying principle
to release the respective private counts $\widetilde{C}_{h}^{k}(s,a)$ and
$\widetilde{N}_{h}^{k}(s,a,s^{\prime})$. The next lemma sums up the properties
of the Central-Privatizer.

######  Lemma 5.1 (Properties of Central-Privatizer).

For any $\varepsilon>0$, Central-Privatizer with parameter
$1/\varepsilon^{\prime}=\frac{3H\log K}{\varepsilon}$ is $\varepsilon$-DP.
Furthermore, for any $\delta\in(0,1]$, it satisfies Assumption 1 with
$E_{\varepsilon,\delta,1}=\frac{3H}{\varepsilon}\sqrt{8\log^{3}K\log(6SAT/\delta)}$,
and
$E_{\varepsilon,\delta,2}=\frac{3H}{\varepsilon}\sqrt{8\log^{3}K\log(6S^{2}AT/\delta)}$.

Lemma 5.1 follows from the privacy guarantee of the Laplace mechanism, and the
concentration bound on the sum of i.i.d. Laplace random variables (Dwork et
al., 2014). Using Lemma 5.1, as corollaries of Theorem 3.2 and Theorem 4.2, we
obtain the regret and privacy guarantees for Private-UCB-PO and Private-UCB-VI
with the Central-Privatizer.

######  Corollary 5.2 (Regret under JDP).

For any $\varepsilon>0$ and $\delta\in(0,1]$, both Private-UCB-PO and Private-
UCB-VI, if instantiated using Central-Privatizer with parameter
$1/\varepsilon^{\prime}=\frac{3H\log K}{\varepsilon}$, satisfy
$\varepsilon$-JDP. Furthermore, with probability at least $1-\delta$, we
obtain the regret bounds:

$\displaystyle\mathcal{R}^{\text{{Private-UCB-PO}}}(T)$
$\displaystyle=\widetilde{O}\left(\sqrt{S^{2}AH^{3}T}+S^{2}AH^{3}/\varepsilon\right),$
$\displaystyle\mathcal{R}^{\text{{Private-UCB-VI}}}(T)$
$\displaystyle=\widetilde{O}\left(\sqrt{SAH^{3}T}+S^{2}AH^{3}/\varepsilon\right).$

We prove the JDP guarantees using the _billboard model_ (Hsu et al., 2016,
Lemma 9) which, informally, 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 quantity
computed using a standard DP mechanism. Note that by Lemma 5.1 and the post-
processing property of DP (Dwork et al., 2014), the sequence of policies
$(\pi^{k})_{k}$ are $\varepsilon$-DP. Therefore, by the billboard model, the
actions $(a_{h}^{k})_{h,k}$ suggested to all the users are $\varepsilon$-JDP.

######  Remark 5.3.

Corollary 5.2, to the best of our understanding, provides the first regret
bound for private PO, and a correct regret bound for private VI as compared to
Vietri et al. (2020), under the requirement of JDP.

###  5.2 Achieving LDP using Local-Privatizer

The Local-Privatizer, at each episode $k$, release the private counts by
injecting Laplace noise into the aggregated statistics computed from the
trajectory generated in that episode. Let us discuss how private counts for
the number of visited states are computed. At each episode $j$, given privacy
parameter $\varepsilon^{\prime}>0$, Local-Privatizer perturbs
$\sigma_{h}^{j}(s,a)$ with an independent Laplace noise
$\text{Lap}(\frac{1}{\varepsilon^{\prime}})$, i.e. it makes $SAH$ noisy
perturbations in total. 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)$,
where $\widetilde{\sigma}_{h}^{j}(s,a)$ denotes the noisy perturbations. The
private counts corresponding to empirical rewards $C_{h}^{k}(s,a)$ and state
transitions $N_{h}^{k}(s,a,s^{\prime})$ are computed similarly. The next lemma
sums up the properties of the Local-Privatizer.

######  Lemma 5.4 (Properties of Local-Privatizer).

For any $\varepsilon>0$, Local-Privatizer with parameter
$1/\varepsilon^{\prime}=\frac{3H}{\varepsilon}$ is $\varepsilon$-LDP.
Furthermore, for any $\delta\in(0,1]$, it satisfies Assumption 1 with
$E_{\varepsilon,\delta,1}=\frac{3H}{\varepsilon}\sqrt{8K\log(6SAT/\delta)}$
and
$E_{\varepsilon,\delta,2}=\frac{3H}{\varepsilon}\sqrt{8K\log(6S^{2}AT/\delta)}$.

######  Corollary 5.5 (Regret under LDP).

For any $\varepsilon>0$ and $\delta\in(0,1]$, instantiating Private-UCB-PO and
Private-UCB-VI using Local-Privatizer with parameter
$1/\varepsilon^{\prime}=\frac{3H}{\varepsilon}$, we obtain, with probability
$\geq 1-\delta$, the regret bounds:

$\displaystyle\mathcal{R}^{\text{{Private-UCB-PO}}}(T)$
$\displaystyle=\widetilde{O}\left(\sqrt{S^{2}AH^{3}T}+S^{2}A\sqrt{H^{5}T}/\varepsilon\right),$
$\displaystyle\mathcal{R}^{\text{{Private-UCB-VI}}}(T)$
$\displaystyle=O\left(\sqrt{SAH^{3}T}+S^{2}A\sqrt{H^{5}T}/\varepsilon\right).$

######  Remark 5.6.

Corollary 5.5, to the best of our knowledge, provides the first regret
guarantee for private PO, and an improved regret bound for private VI as
compared to Garcelon et al. (2020), under the requirement of LDP.

######  Remark 5.7 (JDP vs. LDP).

The noise level in the private counts is $O(\log k)$ under JDP and $O(k)$
under LDP. Due to this, the privacy cost for LDP is
$\tilde{O}(\sqrt{T}/\varepsilon)$, whereas for JDP it is only
$\tilde{O}(1/\varepsilon)$.

######  Remark 5.8 (Alternative LDP mechanisms).

Other than the Laplace noise, one can also use Bernoulli and Gaussian noise in
the Local-Privatizer to achieve LDP (Kairouz et al., 2016; Wang et al.,
2019b). Thanks to Theorem 3.2 and Theorem 4.2, the regret bounds are readily
obtained by plugging in the corresponding $E_{\varepsilon,\delta,1}$ and
$E_{\varepsilon,\delta,2}$.

##  6 Experiments

In this section, we conduct simple numerical experiments to verify our
theoretical results for both policy-based and value-based algorithms101010The
code is available at https://github.com/XingyuZhou989/PrivateTabularRL.

###  6.1 Settings

Our experiment is based on the standard tabular MDP environment RiverSwim
(Strehl and Littman, 2008; Osband et al., 2013), illustrated in Fig. 1. It
consists of six states and two actions ‘left’ and ‘right’, i.e., $S=6$ and
$A=2$. It starts with the left side and tries to reach the right side. At each
step, if it chooses action ‘left’, it will always succeed (cf. the dotted
arrow). Otherwise it often fails (cf. the solid arrow). It only receives a
small amount of reward if it reaches the leftmost side while obtaining a
larger reward once it arrives at the rightmost state. Thus, this MDP naturally
requires a sufficient exploration to obtain the optimal policy. Each episode
is reset every $H=20$ steps.

Figure 1: RiverSwim MDP – solid and dotted arrows denote the transitions under
actions ‘right’ and ‘left’, respectively (Osband et al., 2013).

###  6.2 Results

We evaluate both Private-UCB-PO and Private-UCB-VI under different privacy
budget $\varepsilon$ and also compare them with the corresponding non-private
algorithms UCB-VI (Azar et al., 2017) and OPPO (Efroni et al., 2020a),
respectively. We set all the parameters in our proposed algorithms as the same
order as the theoretical results and tune the learning rate $\eta$ and the
scaling of the confidence interval. We run $20$ independent experiments, each
consisting of $K=2\cdot 10^{4}$ episodes. We plot the the average cumulative
regret along with standard deviation for each setting, as shown in Fig. 2

Figure 2: Cumulative regret vs. Episode under Private-UCB-PO and Private-UCB-
VI

As suggested by theory, in both PO and VI cases, we can see that the cost of
privacy under the JDP requirement becomes negligible as number of episodes
increases (since the cost is only a lower order additive term). But, under the
stricter LDP requirement, the cost of privacy remains high (since the cost is
multiplicative and is of the same order). Furthermore, it is worth noting that
the cost of privacy increases with increasing protection level, i.e. with
decreasing $\varepsilon$.

##  7 Conclusions

In this work, we presented the first private policy-optimization algorithm in
tabular MDPs with regret guarantees under both JDP and LDP requirements. We
also revisited private value-iteration algorithms by improving the regret
bounds of existing results. These are achieved by developing a general
framework for algorithm design and regret analysis in private tabular RL
settings. Though we focus on statistical guarantees of private RL algorithms,
it will be helpful to understand these from a practitioner’s perspective. We
leave this as a possible future direction. Another important direction is to
apply our general framework to MDPs with function approximation, e.g., linear
MDPs (Jin et al., 2019), kernelized MDPs (Chowdhury and Gopalan, 2019) and
generic MDPs (Ayoub et al., 2020).

## References

  * Gottesman et al. (2019) Omer Gottesman, Fredrik Johansson, Matthieu Komorowski, Aldo Faisal, David Sontag, Finale Doshi-Velez, and Leo Anthony Celi.  Guidelines for reinforcement learning in healthcare.  _Nature medicine_ , 25(1):16–18, 2019.
  * Li et al. (2016) Jiwei Li, Will Monroe, Alan Ritter, Michel Galley, Jianfeng Gao, and Dan Jurafsky.  Deep reinforcement learning for dialogue generation.  _arXiv preprint arXiv:1606.01541_ , 2016.
  * Gordon et al. (2016) Goren Gordon, Samuel Spaulding, Jacqueline Kory Westlund, Jin Joo Lee, Luke Plummer, Marayna Martinez, Madhurima Das, and Cynthia Breazeal.  Affective personalization of a social robot tutor for children’s second language skills.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 30, 2016.
  * Li et al. (2010) Lihong Li, Wei Chu, John Langford, and Robert E Schapire.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th international conference on World wide web_ , pages 661–670, 2010.
  * Vietri et al. (2020) Giuseppe Vietri, Borja Balle, Akshay Krishnamurthy, and Steven Wu.  Private reinforcement learning with pac and regret guarantees.  In _International Conference on Machine Learning_ , pages 9754–9764. PMLR, 2020.
  * Garcelon et al. (2020) Evrard Garcelon, Vianney Perchet, Ciara Pike-Burke, and Matteo Pirotta.  Local differentially private regret minimization in reinforcement learning.  _arXiv preprint arXiv:2010.07778_ , 2020.
  * Dwork (2008) Cynthia Dwork.  Differential privacy: A survey of results.  In _International conference on theory and applications of models of computation_ , pages 1–19. Springer, 2008.
  * Jain et al. (2012) Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta.  Differentially private online learning.  In _Conference on Learning Theory_ , pages 24–1. JMLR Workshop and Conference Proceedings, 2012.
  * Mishra and Thakurta (2015) Nikita Mishra and Abhradeep Thakurta.  (nearly) optimal differentially private stochastic multi-arm bandits.  In _Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence_ , pages 592–601, 2015.
  * Tossou and Dimitrakakis (2016) Aristide Tossou and Christos Dimitrakakis.  Algorithms for differentially private multi-armed bandits.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 30, 2016.
  * Shariff and Sheffet (2018) Roshan Shariff and Or Sheffet.  Differentially private contextual linear bandits.  _arXiv preprint arXiv:1810.00068_ , 2018.
  * Dubey (2021) Abhimanyu Dubey.  No-regret algorithms for private gaussian process bandit optimization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2062–2070. PMLR, 2021.
  * Kearns et al. (2014) Michael Kearns, Mallesh Pai, Aaron Roth, and Jonathan Ullman.  Mechanism design in large games: Incentives and privacy.  In _Proceedings of the 5th conference on Innovations in theoretical computer science_ , pages 403–410, 2014.
  * Duchi et al. (2013) John C Duchi, Michael I Jordan, and Martin J Wainwright.  Local privacy and statistical minimax rates.  In _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_ , pages 429–438. IEEE, 2013.
  * Ren et al. (2020) Wenbo Ren, Xingyu Zhou, Jia Liu, and Ness B Shroff.  Multi-armed bandits with local differential privacy.  _arXiv preprint arXiv:2007.03121_ , 2020.
  * Zheng et al. (2020) Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang.  Locally differentially private (contextual) bandits learning.  _arXiv preprint arXiv:2006.00701_ , 2020.
  * Zhou and Tan (2020) Xingyu Zhou and Jian Tan.  Local differential privacy for bayesian optimization.  _arXiv preprint arXiv:2010.06709_ , 2020.
  * Chowdhury et al. (2021) Sayak Ray Chowdhury, Xingyu Zhou, and Ness Shroff.  Adaptive control of differentially private linear quadratic systems.  In _2021 IEEE International Symposium on Information Theory (ISIT)_ , pages 485–490. IEEE, 2021.
  * Silver et al. (2017) David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al.  Mastering the game of go without human knowledge.  _nature_ , 550(7676):354–359, 2017.
  * Duan et al. (2016) Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel.  Benchmarking deep reinforcement learning for continuous control.  In _International conference on machine learning_ , pages 1329–1338. PMLR, 2016.
  * Wang et al. (2018) William Yang Wang, Jiwei Li, and Xiaodong He.  Deep reinforcement learning for nlp.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics: Tutorial Abstracts_ , pages 19–21, 2018.
  * Williams (1992) Ronald J Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ , 8(3-4):229–256, 1992.
  * Kakade (2001) Sham M Kakade.  A natural policy gradient.  _Advances in neural information processing systems_ , 14, 2001.
  * Schulman et al. (2015) John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz.  Trust region policy optimization.  In _International conference on machine learning_ , pages 1889–1897. PMLR, 2015.
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Konda and Tsitsiklis (2000) Vijay R Konda and John N Tsitsiklis.  Actor-critic algorithms.  In _Advances in neural information processing systems_ , pages 1008–1014. Citeseer, 2000.
  * Liu et al. (2019) Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang.  Neural proximal/trust region policy optimization attains globally optimal policy.  _arXiv preprint arXiv:1906.10306_ , 2019.
  * Wang et al. (2019a) Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang.  Neural policy gradient methods: Global optimality and rates of convergence.  _arXiv preprint arXiv:1909.01150_ , 2019a.
  * Cai et al. (2020) Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang.  Provably efficient exploration in policy optimization.  In _International Conference on Machine Learning_ , pages 1283–1294. PMLR, 2020.
  * Efroni et al. (2020a) Yonathan Efroni, Lior Shani, Aviv Rosenberg, and Shie Mannor.  Optimistic policy optimization with bandit feedback.  _arXiv preprint arXiv:2002.08243_ , 2020a.
  * Guha Thakurta and Smith (2013) Abhradeep Guha Thakurta and Adam Smith.  (nearly) optimal algorithms for private online learning in full-information and bandit settings.  _Advances in Neural Information Processing Systems_ , 26:2733–2741, 2013.
  * Agarwal and Singh (2017) Naman Agarwal and Karan Singh.  The price of differential privacy for online learning.  In _International Conference on Machine Learning_ , pages 32–40. PMLR, 2017.
  * Tossou and Dimitrakakis (2017) Aristide Tossou and Christos Dimitrakakis.  Achieving privacy in the adversarial multi-armed bandit.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 31, 2017.
  * Hu et al. (2021) Bingshan Hu, Zhiming Huang, and Nishant A Mehta.  Optimal algorithms for private online learning in a stochastic environment.  _arXiv preprint arXiv:2102.07929_ , 2021.
  * Sajed and Sheffet (2019) Touqir Sajed and Or Sheffet.  An optimal private stochastic-mab algorithm based on optimal private stopping rule.  In _International Conference on Machine Learning_ , pages 5579–5588. PMLR, 2019.
  * Gajane et al. (2018) Pratik Gajane, Tanguy Urvoy, and Emilie Kaufmann.  Corrupt bandits for preserving local privacy.  In _Algorithmic Learning Theory_ , pages 387–412. PMLR, 2018.
  * Chen et al. (2020) Xiaoyu Chen, Kai Zheng, Zixin Zhou, Yunchang Yang, Wei Chen, and Liwei Wang.  (locally) differentially private combinatorial semi-bandits.  In _International Conference on Machine Learning_ , pages 1757–1767. PMLR, 2020.
  * Balle et al. (2016) Borja Balle, Maziar Gomrokchi, and Doina Precup.  Differentially private policy evaluation.  In _International Conference on Machine Learning_ , pages 2130–2138. PMLR, 2016.
  * Wang and Hegde (2019) Baoxiang Wang and Nidhi Hegde.  Privacy-preserving q-learning with functional noise in continuous state spaces.  _arXiv preprint arXiv:1901.10634_ , 2019.
  * Ono and Takahashi (2020) Hajime Ono and Tsubasa Takahashi.  Locally private distributed reinforcement learning.  _arXiv preprint arXiv:2001.11718_ , 2020.
  * Puterman (1994) Martin L. Puterman.  _Markov Decision Processes — Discrete Stochastic Dynamic Programming_.  John Wiley & Sons, Inc., New York, NY, 1994.
  * Sutton (1988) Richard S Sutton.  Learning to predict by the methods of temporal differences.  _Machine learning_ , 3(1):9–44, 1988.
  * Dwork et al. (2014) Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  2014\.
  * Hsu et al. (2016) Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, and Zhiwei Steven Wu.  Private matchings and allocations.  _SIAM Journal on Computing_ , 45(6):1953–1984, 2016.
  * Auer et al. (2002) P. Auer, N. Cesa-Bianchi, and P. Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine Learning_ , 47(2-3):235–256, 2002.
  * Jaksch et al. (2010) Thomas Jaksch, Ronald Ortner, and Peter Auer.  Near-optimal regret bounds for reinforcement learning.  _Journal of Machine Learning Research_ , 11(Apr):1563–1600, 2010.
  * Beck and Teboulle (2003) Amir Beck and Marc Teboulle.  Mirror descent and nonlinear projected subgradient methods for convex optimization.  _Operations Research Letters_ , 31(3):167–175, 2003.
  * Azar et al. (2017) Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos.  Minimax regret bounds for reinforcement learning.  In _International Conference on Machine Learning_ , pages 263–272. PMLR, 2017.
  * Dann et al. (2017) Christoph Dann, Tor Lattimore, and Emma Brunskill.  Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning.  _arXiv preprint arXiv:1703.07710_ , 2017.
  * Efroni et al. (2019) Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor.  Tight regret bounds for model-based reinforcement learning with greedy policies.  _arXiv preprint arXiv:1905.11527_ , 2019.
  * Zanette and Brunskill (2019) Andrea Zanette and Emma Brunskill.  Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds.  In _International Conference on Machine Learning_ , pages 7304–7312. PMLR, 2019.
  * Efroni et al. (2020b) Yonathan Efroni, Shie Mannor, and Matteo Pirotta.  Exploration-exploitation in constrained mdps.  _arXiv preprint arXiv:2003.02189_ , 2020b.
  * Chan et al. (2010) TH Hubert Chan, Elaine Shi, and Dawn Song.  Private and continual release of statistics.  In _International Colloquium on Automata, Languages, and Programming_ , pages 405–417. Springer, 2010.
  * Kairouz et al. (2016) Peter Kairouz, Keith Bonawitz, and Daniel Ramage.  Discrete distribution estimation under local privacy.  In _International Conference on Machine Learning_ , pages 2436–2444. PMLR, 2016.
  * Wang et al. (2019b) Teng Wang, Jun Zhao, Xinyu Yang, and Xuebin Ren.  Locally differentially private data collection and analysis.  _arXiv preprint arXiv:1906.01777_ , 2019b.
  * Strehl and Littman (2008) Alexander L Strehl and Michael L Littman.  An analysis of model-based interval estimation for Markov decision processes.  _Journal of Computer and System Sciences_ , 74(8):1309–1331, 2008.
  * Osband et al. (2013) Ian Osband, Dan Russo, and Benjamin Van Roy.  (more) efficient reinforcement learning via posterior sampling.  In _Advances in Neural Information Processing Systems 26 (NIPS)_ , pages 3003–3011, 2013.
  * Jin et al. (2019) Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  _arXiv preprint arXiv:1907.05388_ , 2019.
  * Chowdhury and Gopalan (2019) Sayak Ray Chowdhury and Aditya Gopalan.  Online learning in kernelized markov decision processes.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 3197–3205. PMLR, 2019.
  * Ayoub et al. (2020) Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin F Yang.  Model-based reinforcement learning with value-targeted regression.  _arXiv preprint arXiv:2006.01107_ , 2020.
  * Weissman et al. (2003) Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger.  Inequalities for the L1 deviation of the empirical distribution.  _Hewlett-Packard Labs, Technical Report_ , 2003.
  * Jin et al. (2020) Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu.  Learning adversarial markov decision processes with bandit feedback and unknown transition.  In _International Conference on Machine Learning_ , pages 4860–4869. PMLR, 2020.
  * Maurer and Pontil (2009) A Maurer and M Pontil.  Empirical Bernstein bounds and sample variance penalization.  In _22nd Conference on Learning Theory (COLT)_ , 2009.

Appendix

##  Appendix A Proofs for Section 3

We first define the _non-private_ mean empirical costs and empirical
transition probabilities as follows.

$\displaystyle\bar{c}_{h}^{k}(s,a):=\frac{{C}_{h}^{k}(s,a)}{{{N}_{h}^{k}(s,a)}\vee
1},\quad\bar{P}_{h}^{k}(s^{\prime}|s,a):=\frac{{N}_{h}^{k}(s,a,s^{\prime})}{{{N}_{h}^{k}(s,a)}\vee
1}~{}.$

Based on them, we define the following events

$\displaystyle F^{c}=\left\\{\exists
s,a,h,k:|c_{h}(s,a)-\bar{c}_{h}^{k}(s,a)|\geq\sqrt{\frac{2\ln\frac{4SAT}{\delta^{\prime}}}{{N_{h}^{k}(s,a)\vee
1}}}\right\\}$ $\displaystyle F^{p}=\left\\{\exists s,a,h,k:\left\lVert
P_{h}(\cdot|s,a)-\bar{P}_{h}^{k}(\cdot|s,a)\right\rVert_{1}\geq\sqrt{\frac{4S\ln\frac{6SAT}{\delta^{\prime}}}{{N_{h}^{k}(s,a)\vee
1}}}\right\\}$

and $\bar{G}:=F^{c}\cup F^{p}$, which is the the complement of the good event
$G$. The next lemma states that the good event happens with high probability.

######  Lemma A.1.

For any $\delta\in(0,1]$, $\mathbb{P}\left[{G}\right]\geq 1-\delta$.

###### Proof.

We first have $\mathbb{P}\left[{F^{c}}\right]\leq\delta/2$. This follows from
Hoeffding’s inequality and union bound over all $s,a$ and all possible values
of $N_{h}^{k}(s,a)$ and $k$. Note that when $N_{h}^{k}(s,a)=0$, this bound
holds trivially. We also have $\mathbb{P}\left[{F^{p}}\right]\leq\delta/2$.
This holds by (Weissman et al., 2003, Theorem 2.1) along with the application
of union bound over all $s,a$ and all possible values of $N_{h}^{k}(s,a)$ and
$k$. Note that when $N_{h}^{k}(s,a)=0$, this bound holds trivially. ∎

Now, we are ready to present the proof for Lemma 3.1.

###### Proof of Lemma 3.1.

Assume that both the good event $G$ and the event in Assumption 1 hold. We
first study the concentration of the private cost estimate. Note that under
the event in Assumption 1,

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

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

$\displaystyle\left|\frac{{C}_{h}^{k}(s,a)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}-c_{h}(s,a)\right|$ $\displaystyle\leq$
$\displaystyle\left|c_{h}(s,a)\left(\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}-1\right)\right|+\left|\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}\left(\frac{C_{h}^{k}(s,a)}{N_{h}^{k}(s,a)\vee 1}-c_{h}(s,a)\right)\right|$
$\displaystyle\mathop{\leq}\limits^{(a)}$ $\displaystyle
c_{h}(s,a)\left|1-\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}\right|+\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}\frac{L_{c}(\delta)}{\sqrt{N_{h}^{k}(s,a)\vee 1}}$ $\displaystyle\leq$
$\displaystyle\frac{2E_{\varepsilon,\delta,1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}+\frac{L_{c}(\delta)\sqrt{N_{h}^{k}(s,a)\vee
1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee 1},$

where (a) holds by the concentration of the cost estimate under good event $G$
with $L_{c}(\delta):=\sqrt{2\ln\frac{4SAT}{\delta}}$. Furthermore, we have

$\displaystyle\frac{L_{c}(\delta)\sqrt{N_{h}^{k}(s,a)\vee
1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}\leq\frac{L_{c}(\delta)\sqrt{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}=\frac{L_{c}(\delta)}{\sqrt{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}}.$

Putting everything together, yields

$\displaystyle|c_{h}(s,a)-\widetilde{c}_{h}^{k}(s,a)|\leq\frac{3E_{\varepsilon,\delta,1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}+\frac{L_{c}(\delta)}{\sqrt{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}}.$

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_{\varepsilon,\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_{\varepsilon,\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_{\varepsilon,\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_{\varepsilon,\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_{\varepsilon,\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_{\varepsilon,\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_{\varepsilon,\delta,1})\vee
1}\left\lVert\bar{P}_{h}^{k}(\cdot|s,a)-P_{h}(\cdot|s,a)\right\rVert_{1}+\sum_{s^{\prime}}\left(P_{h}(s^{\prime}|s,a)\frac{2E_{\varepsilon,\delta,1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}\right)$ $\displaystyle\mathop{\leq}\limits^{(a)}$
$\displaystyle\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}\frac{L_{p}(\delta)}{\sqrt{N_{h}^{k}(s,a)\vee
1}}+\frac{2E_{\varepsilon,\delta,1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}$ $\displaystyle\leq$
$\displaystyle\frac{L_{p}(\delta)}{\sqrt{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}}+\frac{2E_{\varepsilon,\delta,1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1},$

where (a) holds by concentration of transition probability under good event
$G$ with $L_{p}(\delta):=\sqrt{4S\ln\frac{6SAT}{\delta^{\prime}}}$. For
$\mathcal{P}_{2}$, we have

$\displaystyle\mathcal{P}_{2}\leq\sum_{s^{\prime}}\frac{|E_{\varepsilon,\delta,2}|}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}=\frac{SE_{\varepsilon,\delta,2}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}.$

Putting together $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$, yields

$\displaystyle\left\lVert
P_{h}(\cdot|s,a)-\widetilde{P}_{h}^{k}(\cdot|s,a)\right\rVert_{1}\leq\frac{L_{p}(\delta)}{\sqrt{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,1})\vee
1}}+\frac{SE_{\varepsilon,\delta,2}+2E_{\varepsilon,\delta,1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}.$

Finally, applying union bound over good event $G$ and the event in Assumption
1, yields the required result in Lemma 3.1. ∎

We turn to present the proof for Theorem 3.2 as follows.

###### Proof of Theorem 3.2.

As in the non-private case, we first decompose the regret by using the
extended value difference lemma (Efroni et al., 2020a, Lemma 1).

$\displaystyle\mathcal{R}(T)$
$\displaystyle=\sum\nolimits_{k=1}^{K}\left(V_{1}^{\pi^{k}}(s_{1}^{k})-V_{1}^{\pi^{*}}(s_{1}^{k})\right)=\sum\nolimits_{k=1}^{k}\left(V_{1}^{\pi^{k}}(s_{1}^{k})-\widetilde{V}_{1}^{k}(s_{1}^{k})+\widetilde{V}_{1}^{k}(s_{1}^{k})-V_{1}^{\pi^{*}}(s_{1}^{k})\right)$
$\displaystyle=\underbrace{\sum\nolimits_{k=1}^{k}\left(V_{1}^{\pi^{k}}(s_{1}^{k})-\widetilde{V}_{1}^{k}(s_{1}^{k})\right)}_{\mathcal{T}_{1}}+\underbrace{\sum\nolimits_{k=1}^{K}\sum\nolimits_{h=1}^{H}\mathbb{E}\left[\langle\widetilde{Q}_{h}^{k}(s_{h},\cdot),\pi_{h}^{k}(\cdot|s_{h})-\pi_{h}^{*}(\cdot|s_{h})\rangle|s_{1}^{k},\pi^{*}\right]}_{\mathcal{T}_{2}}$
$\displaystyle\quad\quad+\underbrace{\sum\nolimits_{k=1}^{K}\sum\nolimits_{h=1}^{H}\mathbb{E}\left[\widetilde{Q}_{h}^{k}(s_{h},a_{h})-c_{h}(s_{h},a_{h})-P_{h}(\cdot|s_{h},a_{h})\widetilde{V}_{h+1}^{k}|s_{1}^{k},\pi^{*}\right]}_{\mathcal{T}_{3}}.$

We then need to bound each of the three terms.

Analysis of $\mathcal{T}_{2}$. To start with, we can bound $\mathcal{T}_{2}$
by following standard mirror descent analysis under KL divergence.
Specifically, by (Efroni et al., 2020a, Lemma 17), we have for any $h\in[H]$,
$s\in\mathcal{S}$ and any policy $\pi$

$\displaystyle\sum_{k=1}^{K}\langle\widetilde{Q}_{h}^{k}(s,\cdot),\pi_{h}^{k}(\cdot|s)-\pi_{h}(\cdot|s)\rangle$
$\displaystyle\leq\frac{\log
A}{\eta}+\frac{\eta}{2}\sum_{k=1}^{K}\sum_{a}\pi_{h}^{k}(a|s)(Q_{h}^{k}(s,a))^{2}$
$\displaystyle\mathop{\leq}\limits^{(a)}\frac{\log A}{\eta}+\frac{\eta
H^{2}K}{2},$

where (a) holds by $Q_{h}^{k}(s,a)\in[0,H]$, which follows from the truncated
update of $Q$-value in Algorithm 1 (line 9). Thus, we can bound
$\mathcal{T}_{2}$ as follows.

$\displaystyle\mathcal{T}_{2}$
$\displaystyle=\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\left[\langle\widetilde{Q}_{h}^{k}(s_{h}^{k},\cdot),\pi_{h}^{k}(\cdot|s_{h}^{k})-\pi_{h}^{*}(\cdot|s_{h}^{k})\rangle|s_{1}^{k},\pi^{*}\right]\leq\frac{H\log
A}{\eta}+\frac{\eta H^{3}K}{2}.$

Choosing $\eta=\sqrt{2\log A/(H^{2}K)}$, yields

$\displaystyle\mathcal{T}_{2}\leq\sqrt{2H^{4}K\log A}.$ (2)

Analysis of $\mathcal{T}_{3}$. First, by the update rule of $Q$-value in
Algorithm 1 and
$P_{h}(\cdot|s,a)V_{h+1}:=\sum_{s^{\prime}}P_{h}(s^{\prime}|s,a)V_{h+1}(s^{\prime})$,
we have

$\displaystyle\widetilde{Q}_{h}^{k}(s,a)$
$\displaystyle=\min\\{H,\max\\{0,\widetilde{c}_{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)\\}\\}$
$\displaystyle=\min\\{H,\max\\{0,\widetilde{c}_{h}^{k}(s,a)+\widetilde{P}_{h}(\cdot|s_{h}^{k},a_{h}^{k})\widetilde{V}_{h+1}^{k}-\beta_{h}^{k}(s,a)\\}\\}$
$\displaystyle\leq\max\left\\{0,{\widetilde{c}_{h}^{k}(s,a)}-\beta_{h}^{k,c}(s,a)+\widetilde{P}_{h}(\cdot|s_{h}^{k},a_{h}^{k})\widetilde{V}_{h+1}^{k}-H\beta_{h}^{k,p}(s,a)\right\\}$
$\displaystyle\mathop{\leq}\limits^{(a)}\max\left\\{0,{\widetilde{c}_{h}^{k}(s,a)}-\beta_{h}^{k,c}(s,a)\right\\}+\max\left\\{0,\widetilde{P}_{h}(\cdot|s_{h}^{k},a_{h}^{k})\widetilde{V}_{h+1}^{k}-\beta_{h}^{k,pv}(s,a)\right\\}$

where (a) holds since for any $a,b$,
$\max\\{a+b,0\\}\leq\max\\{a,0\\}+\max\\{b,0\\}$. Thus, for any $(k,h,s,a)$,
we have

$\displaystyle\widetilde{Q}_{h}^{k}(s,a)-c_{h}(s,a)-P_{h}(\cdot|s,a)\widetilde{V}_{h+1}^{k}$
$\displaystyle\leq$
$\displaystyle\max\left\\{0,{\widetilde{c}_{h}^{k}(s,a)}-\beta_{h}^{k,c}(s,a)\right\\}+\max\left\\{0,\widetilde{P}_{h}^{k}(\cdot|s,a)\widetilde{V}_{h}^{k}-H\beta_{h}^{k,p}(s,a)\right\\}-c_{h}(s,a)-P_{h}(\cdot|s,a)\widetilde{V}_{h+1}^{k}$
$\displaystyle=$
$\displaystyle\max\left\\{-c_{h}(s,a),{\widetilde{c}_{h}^{k}(s,a)}-c_{h}(s,a)-\beta_{h}^{k,c}(s,a)\right\\}$
$\displaystyle+\max\left\\{-P_{h}(\cdot|s,a)\widetilde{V}_{h+1}^{k},\widetilde{P}_{h}^{k}(\cdot|s,a)\widetilde{V}_{h}^{k}-P_{h}(\cdot|s,a)\widetilde{V}_{h+1}^{k}-H\beta_{h}^{k,p}(s,a)\right\\}$
$\displaystyle\leq$
$\displaystyle\max\left\\{0,{\widetilde{c}_{h}^{k}(s,a)}-c_{h}(s,a)-\beta_{h}^{k,c}(s,a)\right\\}$
(3)
$\displaystyle+\max\left\\{0,\widetilde{P}_{h}^{k}(\cdot|s,a)\widetilde{V}_{h}^{k}-P_{h}(\cdot|s,a)\widetilde{V}_{h+1}^{k}-H\beta_{h}^{k,p}(s,a)\right\\}.$
(4)

We are going to show that both (3) and (4) are less than zero for all
$(k,h,s,a)$ with high probability by Lemma 3.1. First, conditioned on the
first result in Lemma 3.1, we have (3) is less than zero. Further, we have
conditioned on the second result in Lemma 3.1

$\displaystyle\widetilde{P}_{h}^{k}(\cdot|s,a)\widetilde{V}_{h}^{k}-P_{h}(\cdot|s,a)\widetilde{V}_{h+1}^{k}-H\beta_{h}^{k,p}(s,a)$
$\displaystyle\mathop{\leq}\limits^{(a)}$
$\displaystyle\left\lVert\widetilde{P}_{h}^{k}(\cdot|s,a)-P_{h}(\cdot|s,a)\right\rVert_{1}\left\lVert\widetilde{V}_{h+1}^{k}\right\rVert_{\infty}-H\beta_{h}^{k,p}(s,a)$
$\displaystyle\mathop{\leq}\limits^{(b)}$ $\displaystyle
H\left\lVert\widetilde{P}_{h}^{k}(\cdot|s,a)-P_{h}(\cdot|s,a)\right\rVert_{1}-H\beta_{h}^{k,p}(s,a)$
$\displaystyle\mathop{\leq}\limits^{(c)}$ $\displaystyle 0$ (5)

where (a) holds by Holder’s inequality; (b) holds since
$0\leq\widetilde{V}_{h+1}^{k}\leq H$ based on our update rule; (c) holds by
Lemma 3.1. Thus, we have shown that

$\displaystyle\mathcal{T}_{3}\leq 0.$ (6)

Analysis of $\mathcal{T}_{1}$. Assume the good event $G$ and the event in
Assumption 1 hold (which implies the concentration results in Lemma 3.1). We
have

$\displaystyle\mathcal{T}_{1}=$
$\displaystyle\sum_{k=1}^{K}V_{1}^{\pi_{k}}(s_{1})-\widetilde{V}_{1}^{k}(s_{1})$
$\displaystyle\mathop{=}\limits^{(a)}$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\left[c_{h}(s_{h},a_{h})+P_{h}(\cdot|s_{h},a_{h})\widetilde{V}_{h+1}^{k}-\widetilde{Q}_{h+1}^{k}(s_{h},a_{h})|s_{1}^{k},\pi_{k}\right]$
$\displaystyle\mathop{=}\limits^{(b)}$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\left[c_{h}(s_{h},a_{h})+P_{h}(\cdot|s_{h},a_{h})\widetilde{V}_{h+1}^{k}|s_{1}^{k},\pi_{k}\right]$
$\displaystyle-$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\left[\max\left\\{\widetilde{c}_{h}^{k}(s_{h},a_{h})-\beta_{h}^{k,c}(s_{h},a_{h})+\widetilde{P}_{h}^{k}(\cdot|s_{h},a_{h})\widetilde{V}_{h+1}^{k}-H\beta_{h}^{k,p}(s_{h},a_{h}),0\right\\}|s_{1}^{k},\pi_{k}\right]$
(7)

where (a) holds by the extended value difference lemma (Efroni et al., 2020a,
Lemma 1); (b) holds by the update rue of Q-value in Algorithm 1. Note that
here we can directly remove the the truncation at $H$ since by Lemma 3.1,
$\widetilde{c}_{h}^{k}(s_{h},a_{h})-\beta_{h}^{k,c}(s_{h},a_{h})+\widetilde{p}(\cdot|s_{h},a_{h})\widetilde{V}_{h+1}^{k}-H\beta_{h}^{k,p}(s_{h},a_{h})\leq
c_{h}(s,a)+P_{h}(\cdot|s,a)\widetilde{V}_{h+1}^{k}\leq 1+H-h\leq H$.

Now, observe that for any $(k,h,s,a)$, we have

$\displaystyle
c_{h}(s,a)+P_{h}(\cdot|s,a)\widetilde{V}_{h+1}^{k}-\max\left\\{\widetilde{c}_{h}^{k}(s_{h},a_{h})-\beta_{h}^{k,c}(s,a)+\widetilde{P}_{h}^{k}(\cdot|s,a)\widetilde{V}_{h+1}^{k}-H\beta_{h}^{k,p}(s,a),0\right\\}$
$\displaystyle\leq
c_{h}(s,a)-{\widetilde{c}_{h}^{k}(s,a)}+\beta_{h}^{k,c}(s,a)+P_{h}(\cdot|s,a)\widetilde{V}_{h+1}^{k}-\widetilde{P}_{h}^{k}(\cdot|s,a)\widetilde{V}_{h+1}^{k}+H\beta_{h}^{k,p}(s,a)$
$\displaystyle\mathop{\leq}\limits^{(a)}2\beta_{h}^{k,c}(s,a)+2H\beta_{h}^{k,p}(s,a),$
(8)

where (a) holds by Lemma 3.1 and a similar analysis as in (5). Plugging (8)
into (7), yields

$\displaystyle\mathcal{T}_{1}\leq\underbrace{\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\left[2\beta_{h}^{k,c}(s_{h},a_{h})|s_{1}^{k},\pi^{k}\right]}_{\text{Term(i)}}+\underbrace{H\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\left[2\beta_{h}^{k,p}(s_{h},a_{h})|s_{1}^{k},\pi^{k}\right]}_{\text{Term(ii)}}$
(9)

By the definition of $\beta_{h}^{k,c}$ and $\beta_{h}^{k,p}$ in Lemma 3.1 and
Assumption 1, we have with probability $1-2\delta$,

Term(i)
$\displaystyle\leq\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\left[\frac{L_{c}(\delta)}{\sqrt{\max\\{{N}_{h}^{k}(s_{h},a_{h}),1\\}}}+\frac{3E_{\varepsilon,\delta,1}}{\max\\{N_{h}^{k}(s_{h},a_{h}),1\\}}|s_{1}^{k},\pi^{k}\right]$
Term(ii) $\displaystyle\leq
H\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\left[\frac{L_{p}(\delta)}{\sqrt{\max\\{N_{h}^{k}(s_{h},a_{h}),1\\}}}+\frac{SE_{\varepsilon,\delta,2}+2E_{\varepsilon,\delta,1}}{\max\\{{N}_{h}^{k}(s_{h},a_{h}),1\\}}|s_{1}^{k},\pi^{k}\right].$

We bound the two terms above by using the following lemma. These are
generalization of results proved under stationary transition model Efroni et
al. (2019); Zanette and Brunskill (2019) to our non-stationary setting. The
proof is given at the end of this section.

######  Lemma A.2.

With probability $1-2\delta$, we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\left[\frac{1}{\max\\{1,N_{h}^{k}(s_{h},a_{h})\\}}|\mathcal{F}_{k-1}\right]=O\left(SAH\ln
KH+H\ln(H/\delta)\right),$

and

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\left[\frac{1}{\sqrt{\max\\{1,N_{h}^{k}(s_{h},a_{h})\\}}}|\mathcal{F}_{k-1}\right]=O\left(\sqrt{SAH^{2}K}+SAH\ln
KH+H\ln(H/\delta)\right),$

where the filtration $\mathcal{F}_{k}$ includes all the events until the end
of episode $k$.

Therefore, by Lemma A.2 (since $\pi^{k}$ is determined by
$\mathcal{F}_{k-1}$), we have with probability at least $1-4\delta$,

Term(i)
$\displaystyle\leq\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\left[\frac{L_{c}(\delta)}{\sqrt{\max\\{{N}_{h}^{k}(s_{h},a_{h}),1\\}}}+\frac{3E_{\varepsilon,\delta,1}}{\max\\{N_{h}^{k}(s_{h},a_{h}),1\\}}|s_{1}^{k},\pi^{k}\right]$
$\displaystyle\leq\tilde{O}\left(\sqrt{SAH^{2}K}+SAH+E_{\varepsilon,\delta,1}SAH\right).$
(10)

and

Term(ii) $\displaystyle\leq
H\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\left[\frac{L_{p}(\delta)}{\sqrt{\max\\{N_{h}^{k}(s_{h},a_{h}),1\\}}}+\frac{SE_{\varepsilon,\delta,2}+2E_{\varepsilon,\delta,1}}{\max\\{{N}_{h}^{k}(s_{h},a_{h}),1\\}}|s_{1}^{k},\pi^{k}\right]$
$\displaystyle\leq\tilde{O}\left(\sqrt{S^{2}AH^{4}K}+\sqrt{S^{3}A^{2}H^{4}}+E_{\varepsilon,2}S^{2}AH^{2}+E_{\varepsilon,1}SAH^{2}\right).$
(11)

Plugging (10) and (11) into (9), yields ($T=KH$)

$\displaystyle\mathcal{T}_{1}=O\left(\left(\sqrt{S^{2}AH^{3}T}+\sqrt{S^{3}A^{2}H^{4}}+E_{\varepsilon,\delta,2}S^{2}AH^{2}+E_{\varepsilon,\delta,1}SAH^{2}\right)\log(S,A,T,1/\delta)\right)$

Finally, putting the bounds on $\mathcal{T}_{1}$, $\mathcal{T}_{2}$ and
$\mathcal{T}_{3}$ together, completes the proof. ∎

We are left to present the proof for Lemma A.2. In the case of a stationary
transition, Efroni et al. (2019); Zanette and Brunskill (2019) resort to the
method of properly defining a ‘good’ set of episodes (cf. (Zanette and
Brunskill, 2019, Definition 6)). We prove our results in the non-stationary
case via a different approach. In particular, inspired by Jin et al. (2020),
we will use the following Bernstein-type concentration inequality for
martingale as our main tool, which is adapted from Lemma 9 in Jin et al.
(2020).

######  Lemma A.3.

Let $Y_{1},\ldots,Y_{K}$ be a martingale difference sequence with respect to a
filtration $\mathcal{F}_{0},\mathcal{F}_{1},\ldots,\mathcal{F}_{K}$. Assume
$Y_{k}\leq R$ a.s. for all $i$. Then, for any $\delta\in(0,1)$ and
$\lambda\in[0,1/R]$, with probability $1-\delta$, we have

$\displaystyle\sum_{k=1}^{K}Y_{k}\leq\lambda\sum_{k=1}^{K}\mathbb{E}\left[Y_{k}^{2}|\mathcal{F}_{k-1}\right]+\frac{\ln(1/\delta)}{\lambda}.$

Now, we are well-prepared to present the proof of Lemma A.2.

###### Proof of Lemma A.2.

Let $\mathcal{I}_{h}^{k}(s,a)$ be the indicator so that
$\mathbb{E}\left[\mathcal{I}_{h}^{k}(s,a)|\mathcal{F}_{k-1}\right]=w_{h}^{k}(s,a)$,
which is the probability of visiting state-action pair $(s,a)$ at step $h$ and
episode $k$. First note that

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\left[\frac{1}{\max\\{1,N_{h}^{k}(s_{h},a_{h})\\}}|\mathcal{F}_{k-1}\right]$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{h,s,a}w_{h}^{k}(s,a)\frac{1}{\max\\{1,N_{h}^{k}(s,a)\\}}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{h,s,a}\frac{\mathcal{I}_{h}^{k}(s,a)}{\max\\{1,N_{h}^{k}(s,a)\\}}+\sum_{k=1}^{K}\sum_{h,s,a}\frac{w_{h}^{k}(s,a)-\mathcal{I}_{h}^{k}(s,a)}{\max\\{1,N_{h}^{k}(s,a)\\}}.$

The first term can be bounded as follows.

$\displaystyle\sum_{k=1}^{K}\sum_{h,s,a}\frac{\mathcal{I}_{h}^{k}(s,a)}{\max\\{1,N_{h}^{k}(s,a)\\}}$
$\displaystyle\leq\sum_{h,s,a}\sum_{k=1}^{K}\frac{1}{\max\\{1,N_{h}^{k}(s,a)\\}}$
$\displaystyle=\sum_{h,s,a}\sum_{i=1}^{N_{h}^{K}(s,a)}\frac{1}{i}$
$\displaystyle\leq c^{\prime}\sum_{h,s,a}\ln(N_{h}^{K}(s,a))$
$\displaystyle\leq c^{\prime}SAH\ln\left(\sum_{s,a,h}N_{h}^{K}(s,a)\right)$
$\displaystyle=O\left(SAH\ln(KH)\right).$

To bound the second term, we will use Lemma A.3. In particular, consider
$Y_{k,h}:=\sum_{s,a}\frac{w_{h}^{k}(s,a)-\mathcal{I}_{h}^{k}(s,a)}{\max\\{1,N_{h}^{k}(s,a)\\}}\leq
1$, $\lambda=1$, and the fact that for any fixed $h$,

$\displaystyle\mathbb{E}\left[Y_{k,h}^{2}|\mathcal{F}_{k-1}\right]$
$\displaystyle\leq\mathbb{E}\left[\left(\sum_{s,a}\frac{\mathcal{I}_{h}^{k}(s,a)}{\max\\{1,N_{h}^{k}(s,a)\\}}\right)^{2}\mid\mathcal{F}_{k-1}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{s,a}\frac{\mathcal{I}_{h}^{k}(s,a)}{\max\\{1,(N_{h}^{k}(s,a))^{2}\\}}\mid\mathcal{F}_{k-1}\right]$
$\displaystyle\leq\sum_{s,a}\frac{w_{h}^{k}(s,a)}{\max\\{1,N_{h}^{k}(s,a)\\}}.$

Then, via Lemma A.3, we have with probability at least $1-\delta$,

$\displaystyle\sum_{k=1}^{K}\sum_{h,s,a}\frac{w_{h}^{k}(s,a)-\mathcal{I}_{h}^{k}(s,a)}{\max\\{1,N_{h}^{k}(s,a)\\}}=\sum_{h=1}^{H}\sum_{k=1}^{K}Y_{k,h}$
$\displaystyle\leq\sum_{h=1}^{H}\sum_{k=1}^{K}\sum_{s,a}\frac{w_{h}^{k}(s,a)}{\max\\{1,N_{h}^{k}(s,a)\\}}+H\ln(H/\delta)$
$\displaystyle=O\left(SAH\ln(KH)+H\ln(H/\delta)\right),$

which completes the proof of the first result in Lemma A.2. To show the second
result, similarly, we decompose it as

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}\left[\frac{1}{\sqrt{\max\\{1,N_{h}^{k}(s_{h},a_{h})\\}}}|\mathcal{F}_{k-1}\right]$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{h,s,a}w_{h}^{k}(s,a)\frac{1}{\sqrt{\max\\{1,N_{h}^{k}(s,a)\\}}}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{h,s,a}\frac{\mathcal{I}_{h}^{k}(s,a)}{\sqrt{\max\\{1,N_{h}^{k}(s,a)\\}}}+\sum_{k=1}^{K}\sum_{h,s,a}\frac{w_{h}^{k}(s,a)-\mathcal{I}_{h}^{k}(s,a)}{\sqrt{\max\\{1,N_{h}^{k}(s,a)\\}}}$

The first term can be bounded as follows.

$\displaystyle\sum_{k=1}^{K}\sum_{h,s,a}\frac{\mathcal{I}_{h}^{k}(s,a)}{\max\\{1,N_{h}^{k}(s,a)\\}}$
$\displaystyle\leq\sum_{h,s,a}\sum_{k=1}^{K}\frac{1}{\sqrt{\max\\{1,N_{h}^{k}(s,a)\\}}}=\sum_{h,s,a}\sum_{i=1}^{N_{h}^{K}(s,a)}\frac{1}{\sqrt{i}}\leq
c^{\prime}\sum_{h,s,a}\sqrt{N_{h}^{K}(s,a)}$ $\displaystyle\leq
c^{\prime}\sqrt{\left(\sum_{h,s,a}1\right)\left(\sum_{h,s,a}N_{h}^{K}(s,a)\right)}$
$\displaystyle=O\left(\sqrt{SAH^{2}K}\right)$

To bound the second term, we apply Lemma A.3 again. Consider
$Y_{k,h}:=\sum_{s,a}\frac{w_{h}^{k}(s,a)-\mathcal{I}_{h}^{k}(s,a)}{\sqrt{\max\\{1,N_{h}^{k}(s,a)\\}}}\leq
1$, $\lambda=1$ and the fact that for any fixed $h$,

$\displaystyle\mathbb{E}\left[Y_{k,h}^{2}|\mathcal{F}_{k-1}\right]$
$\displaystyle\leq\mathbb{E}\left[\left(\sum_{s,a}\frac{\mathcal{I}_{h}^{k}(s,a)}{\sqrt{\max\\{1,N_{h}^{k}(s,a)\\}}}\right)^{2}\mid\mathcal{F}_{k-1}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{s,a}\frac{\mathcal{I}_{h}^{k}(s,a)}{\max\\{1,N_{h}^{k}(s,a)\\}}\mid\mathcal{F}_{k-1}\right]$
$\displaystyle=\sum_{s,a}\frac{w_{h}^{k}(s,a)}{\max\\{1,N_{h}^{k}(s,a)\\}}.$

Then, via Lemma A.3, we have with probability at least $1-\delta$,

$\displaystyle\sum_{k=1}^{K}\sum_{h,s,a}\frac{w_{h}^{k}(s,a)-\mathcal{I}_{h}^{k}(s,a)}{\sqrt{\max\\{1,N_{h}^{k}(s,a)\\}}}=\sum_{h=1}^{H}\sum_{k=1}^{K}Y_{k,h}$
$\displaystyle\leq\sum_{h=1}^{H}\sum_{k=1}^{K}\sum_{s,a}\frac{w_{h}^{k}(s,a)}{\max\\{1,N_{h}^{k}(s,a)\\}}+H\ln(H/\delta)$
$\displaystyle=O\left(SAH\ln(KH)+H\ln(H/\delta)\right)$

Putting the two bounds together, yields the second result and completes the
proof. ∎

##  Appendix B Proofs for Section 4

In this section, we presents proof for Lemma 4.1 and Theorem 4.2. We also
discuss the gaps in the regret analysis of Vietri et al. (2020) at the end of
this section. To start with, we present the proof of Lemma 4.1 as follows.

###### Proof of Lemma 4.1.

Assume the event in Assumption 1 hold. The first result in Lemma 4.1 follows
the same analysis as in the proof of Lemma 3.1. In particular, we have with
probability at least $1-\delta/2$,

$\displaystyle|c_{h}(s,a)-\widetilde{c}_{h}^{k}(s,a)|\leq\beta_{h}^{k,c}(s,a).$

To show the second result, we first note that $V^{*}$ is fixed and
$V^{*}_{h}(s)\leq H$ for all $h$ and $s$. This enables us to use standard
Hoeffding’s inequality. Specifically, we have

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

We are going to bound the two terms respectively, For the first term, we have
with probability at least $1-\delta/2$

$\displaystyle\left|\sum_{s^{\prime}}\left(\frac{{N}_{h}^{k}(s,a,s^{\prime})}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}-P_{h}(s^{\prime}|s,a)\right)V_{h+1}^{*}(s^{\prime})\right|$
$\displaystyle\leq$
$\displaystyle\left|\sum_{s^{\prime}}V_{h+1}^{*}(s^{\prime})\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_{\varepsilon,\delta,1})\vee 1}\right|$
$\displaystyle+\left|\sum_{s^{\prime}}V_{h+1}^{*}(s^{\prime})P_{h}(s^{\prime}|s,a)\left(\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}-1\right)\right|$ $\displaystyle\mathop{\leq}\limits^{(a)}$
$\displaystyle\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}H\sqrt{\frac{L(\delta)}{N_{h}^{k}(s,a)\vee 1}}$
$\displaystyle+\left|\sum_{s^{\prime}}V_{h+1}^{*}(s^{\prime})P_{h}(s^{\prime}|s,a)\left(\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\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_{\varepsilon,\delta,1})\vee
1}H\sqrt{\frac{L(\delta)}{N_{h}^{k}(s,a)\vee
1}}+H\frac{2E_{\varepsilon,\delta,1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,1})\vee
1}$ $\displaystyle\leq$ $\displaystyle
H\sqrt{\frac{L(\delta)}{{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}}}+\frac{2HE_{\varepsilon,\delta,1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}$

where in (a) we use standard Hoeffding inequality with
$L(\delta^{\prime}):=2\ln\frac{4SAT}{\delta}$ and $V_{h+1}^{*}(s^{\prime})\leq
H$.

For the second term, we have

$\displaystyle\left|\sum_{s^{\prime}}\frac{\widetilde{N}_{h}^{k}(s,a,s^{\prime})-{N}_{h}^{k}(s,a,s^{\prime})}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}V_{h+1}^{*}(s^{\prime})\right|\leq\frac{HSE_{\varepsilon,\delta,2}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}$

Putting the two bounds together, we have

$\displaystyle\left|(\widetilde{P}_{h}^{k}-P_{h}){V}_{h+1}^{*}(s,a)\right|\leq
H\sqrt{\frac{L(\delta^{\prime})}{{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}}}+\frac{H(SE_{\varepsilon,\delta,2}+2E_{\varepsilon,\delta,1})}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}$

Noting that $L_{c}(\delta)=\sqrt{L(\delta)}$, we have obtained the second
result in Lemma 4.1.

Now, we turn to focus on the third result in Lemma 4.1. Note that

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

For $\mathcal{P}_{1}$, we have with probability at least $1-\delta$,

$\displaystyle\mathcal{P}_{1}=\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)+\alpha
E_{\varepsilon,\delta,1})\vee 1}-P_{h}(s^{\prime}|s,a)\right|$
$\displaystyle=$
$\displaystyle\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_{\varepsilon,\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_{\varepsilon,\delta,1})\vee
1}-1\right)\right|$ $\displaystyle\mathop{\leq}\limits^{(a)}$
$\displaystyle\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}{|\bar{P}_{h}^{k}(s^{\prime}|s,a)-P_{h}(s^{\prime}|s,a)|}+\left(P_{h}(s^{\prime}|s,a)\frac{2E_{\varepsilon,\delta,1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}\right)$ $\displaystyle\mathop{\leq}\limits^{(b)}$ $\displaystyle
C\frac{N_{h}^{k}(s,a)\vee
1}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}\left(\sqrt{\frac{L^{\prime}(\delta)P_{h}(s^{\prime}|s,a)}{{N_{h}^{k}(s,a)\vee
1}}}+\frac{L^{\prime}(\delta)}{N_{h}^{k}(s,a)\vee
1}\right)+\frac{2E_{\varepsilon,\delta,1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}$ $\displaystyle\leq$ $\displaystyle
C\sqrt{\frac{L^{\prime}(\delta)P_{h}(s^{\prime}|s,a)}{{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}}}+C\frac{L^{\prime}(\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}+\frac{2E_{\varepsilon,\delta,1}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1},$

where in (a) holds by
$\bar{P}_{h}^{k}(\cdot|s,a)=\frac{N_{h}^{k}(s,a,s^{\prime})}{N_{h}^{k}(s,a)\vee
1}$ and Assumption 1 for the second term; (b) holds by Lemma 8 in Efroni et
al. (2020b) for some constant $C$ and
$L^{\prime}(\delta):=\ln\left(\frac{6SAHK}{\delta}\right)$, which is an
application of empirical Bernstein inequality (cf. (Maurer and Pontil, 2009,
Theorem 4)).

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

$\displaystyle\mathcal{P}_{2}\leq\frac{E_{\varepsilon,\delta,2}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}$

Putting everything together, we obtain

$\displaystyle\sum_{s^{\prime}}|P_{h}(s^{\prime}|,s,a)-\widetilde{P}_{h}^{k}(s^{\prime}|s,a)|\leq
C\sqrt{\frac{L^{\prime}(\delta)P_{h}(s^{\prime}|s,a)}{{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}}}+\frac{CL^{\prime}(\delta)+2E_{\varepsilon,\delta,1}+E_{\varepsilon,\delta,2}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}.$

Finally, applying union bound over all the events, yields the required results
in Lemma 4.1. ∎

Now, we turn to establish Theorem 4.2. First, the next lemma establishes that
the value function maintained in our algorithm is optimistic.

######  Lemma B.1.

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

###### Proof.

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}^{k}(s)\leq V_{h}^{*}(s)$ for all $s$. Then, by the
update rule, we have

$\displaystyle\widetilde{{Q}}_{h}^{k}(s,a)=\min\\{H,\max\\{0,\widetilde{c}_{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$ does not affect the
analysis. To see this, first observe that under Lemma 4.1

$\displaystyle\widetilde{c}_{h}^{k}(s,a)+(\widetilde{P}_{h}^{k}\widetilde{V}_{h+1}^{k})(s,a)-\beta_{h}^{k}(s,a)$
$\displaystyle\mathop{\leq}\limits^{(a)}c_{h}(s,a)+(\widetilde{P}_{h}^{k}\widetilde{V}_{h+1}^{k})(s,a)-\beta_{h}^{k,pv}(s,a)$
$\displaystyle\mathop{\leq}\limits^{(b)}c_{h}(s,a)+(\widetilde{P}_{h}^{k}{V}_{h+1}^{*})(s,a)-\beta_{h}^{k,pv}(s,a)$
$\displaystyle\mathop{\leq}\limits^{(c)}c_{h}(s,a)+(P_{h}V_{h+1}^{*})(s,a)=Q_{h}^{*}(s,a)\leq
H$ (12)

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

$\displaystyle\widetilde{{Q}}_{h}^{k}(s,a)=\max\\{0,\widetilde{c}_{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 zero, then
$\widetilde{{Q}}_{h}^{k}(s,a)\leq Q_{h}^{*}(s,a)$ trivially holds since
$Q_{h}^{*}(s,a)\in[0,H]$. Otherwise, by Eq. (12), we also have
$\widetilde{{Q}}_{h}^{k}(s,a)\leq Q_{h}^{*}(s,a)$. Therefore, we have
$\widetilde{Q}_{h}^{k}(s,a)\leq Q_{h}^{*}(s,a)$, and hence
$\widetilde{V}_{h}^{k}(s)\leq V_{h}^{*}(s)$. ∎

Based on the result above, we are now able to present the proof of Theorem
4.2.

###### Proof of Theorem 4.2.

By the optimistic result in Lemma B.1, we have

$\displaystyle\mathcal{R}(K)=\sum_{k=1}^{K}(V_{1}^{\pi_{k}}(s_{1})-V_{1}^{*}(s_{1}))\leq\sum_{k=1}^{K}({V}_{1}^{\pi_{k}}(s_{1})-\widetilde{V}_{1}^{k}(s_{1}))$
(13)

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

$\displaystyle(V_{h}^{\pi_{k}}-\widetilde{V}_{h}^{k})(s_{h}^{k})=(Q_{h}^{\pi_{k}}-\widetilde{Q}_{h}^{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(Q_{h}^{\pi_{k}}-\widetilde{Q}_{h}^{k})(s_{h}^{k},a_{h}^{k})$
$\displaystyle\mathop{\leq}\limits^{(a)}$ $\displaystyle
2\beta_{h}^{k,c}(s_{h}^{k},a_{h}^{k})+(P_{h}V_{h+1}^{\pi_{k}}-\widetilde{P}_{h}^{k}\widetilde{V}_{h+1}^{k})(s_{h}^{k},a_{h}^{k})+\beta_{h}^{k,pv}(s,a)$
$\displaystyle=$
$\displaystyle\left[(P_{h}-\widetilde{P}_{h}^{k})\widetilde{V}_{h+1}^{k}\right](s_{h}^{k},a_{h}^{k})+\left[P_{h}(V_{h+1}^{\pi_{k}}-\widetilde{V}_{h+1}^{k})\right](s_{h}^{k},a_{h}^{k})+2\beta_{h}^{k,c}(s_{h}^{k},a_{h}^{k})+\beta_{h}^{k,pv}(s,a)$
$\displaystyle=$
$\displaystyle\left[(P_{h}-\widetilde{P}_{h}^{k}){V}_{h+1}^{*}\right](s_{h}^{k},a_{h}^{k})+\left[(\widetilde{P}_{h}^{k}-P_{h})({V}_{h+1}^{*}-\widetilde{V}_{h+1}^{k})\right](s_{h}^{k},a_{h}^{k})$
$\displaystyle+\left[P_{h}(V_{h+1}^{\pi_{k}}-\widetilde{V}_{h+1}^{k})\right](s_{h}^{k},a_{h}^{k})+2\beta_{h}^{k,c}(s_{h}^{k},a_{h}^{k})+\beta_{h}^{k,pv}(s,a)$
$\displaystyle\mathop{\leq}\limits^{(b)}$
$\displaystyle\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}(V_{h+1}^{\pi_{k}}-\widetilde{V}_{h+1}^{k})\right](s_{h}^{k},a_{h}^{k})$
$\displaystyle+2\beta_{h}^{k,c}(s_{h}^{k},a_{h}^{k})+2\beta_{h}^{k,pv}(s_{h}^{k},a_{h}^{k}),$
(14)

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

$\displaystyle(V_{h}^{\pi_{k}}-\widetilde{V}_{h}^{k})(s_{h}^{k})$
$\displaystyle\leq\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}(V_{h+1}^{\pi_{k}}-\widetilde{V}_{h+1}^{k})\right](s_{h}^{k},a_{h}^{k})$
$\displaystyle+2\beta_{h}^{k,c}(s_{h}^{k},a_{h}^{k})+2\beta_{h}^{k,pv}(s_{h}^{k},a_{h}^{k}).$
(15)

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

$\displaystyle\left[(P_{h}-\widetilde{P}_{h}^{k})(\widetilde{V}_{h+1}^{k}-{V}_{h+1}^{*})\right](s_{h}^{k},a_{h}^{k})$
$\displaystyle=$
$\displaystyle\sum_{s^{\prime}}\left(P_{h}(s^{\prime}|s_{h}^{k},a_{h}^{k})-\widetilde{P}_{h}^{k}(s^{\prime}|s_{h}^{k},a_{h}^{k})\right)G(s^{\prime})$
$\displaystyle\mathop{\leq}\limits^{(a)}$ $\displaystyle
c\sum_{s^{\prime}}\left(\sqrt{\frac{L^{\prime}(\delta)P_{h}(s^{\prime}|s_{h}^{k},a_{h}^{k})}{{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}}}+\frac{L^{\prime}(\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}+\frac{2E_{\varepsilon,\delta,1}+E_{\varepsilon,\delta,2}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}\right)G(s^{\prime})$ $\displaystyle\mathop{\leq}\limits^{(b)}$
$\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{cHL^{\prime}(\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}\right)G(s^{\prime})$
$\displaystyle+c\sum_{s^{\prime}}\left(\frac{L^{\prime}(\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}\right)G(s^{\prime})+c\sum_{s^{\prime}}\left(\frac{2E_{\varepsilon,\delta,1}+E_{\varepsilon,\delta,2}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}\right)G(s^{\prime})$ $\displaystyle\mathop{\leq}\limits^{(c)}$
$\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}L^{\prime}(\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}\right)$
$\displaystyle+c\sum_{s^{\prime}}\left(\frac{2HE_{\varepsilon,\delta,1}+HE_{\varepsilon,\delta,2}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}\right),$ (16)

where (a) holds by the third result in Lemma 4.1 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$ by the boundedness of $V$-value. Now,
plugging the definition for $G(s^{\prime})$ into (16), yields

$\displaystyle\left[(P_{h}-\widetilde{P}_{h}^{k})({V}_{h+1}^{*}-\widetilde{V}_{h+1}^{k})\right](s_{h}^{k},a_{h}^{k})$
$\displaystyle=$
$\displaystyle\frac{1}{H}\left[P_{h}(V_{h+1}^{*}-\widetilde{V}_{h+1}^{k})\right](s_{h}^{k},a_{h}^{k})+\frac{c^{\prime}SH^{2}L^{\prime}(\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}+\frac{2cSHE_{\varepsilon,\delta,1}+cSHE_{\varepsilon,\delta,2}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}$ $\displaystyle\mathop{=}\limits^{(a)}$
$\displaystyle\frac{1}{H}\left[P_{h}(V_{h+1}^{*}-\widetilde{V}_{h+1}^{k})\right](s_{h}^{k},a_{h}^{k})+\xi_{h}^{k}+\zeta_{h}^{k}$
$\displaystyle\mathop{\leq}\limits^{(b)}$
$\displaystyle\frac{1}{H}\left[P_{h}(V_{h+1}^{\pi_{k}}-\widetilde{V}_{h+1}^{k})\right](s_{h}^{k},a_{h}^{k})+\xi_{h}^{k}+\zeta_{h}^{k},$
(17)

where (a) holds by definitions
$\xi_{h}^{k}=:\frac{c^{\prime}SH^{2}L^{\prime}(\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}$ and
$\zeta_{h}^{k}:=\frac{2cSHE_{\varepsilon,\delta,1}+cSHE_{\varepsilon,\delta,2}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}$; (b) holds since $V_{h+1}^{\pi_{k}}\geq V_{h+1}^{*}$. Plugging (17) into
(15), yields the following recursive formula.

$\displaystyle(V_{h}^{\pi_{k}}-\widetilde{V}_{h}^{k})(s_{h}^{k})$
$\displaystyle\mathop{\leq}\limits^{(a)}\left(1+\frac{1}{H}\right)\left[P_{h}(V_{h+1}^{\pi_{k}}-\widetilde{V}_{h+1}^{k})\right](s_{h}^{k},a_{h}^{k})+\xi_{h}^{k}+\zeta_{h}^{k}+2\beta_{h}^{k}$
$\displaystyle\mathop{=}\limits^{(b)}\left(1+\frac{1}{H}\right)\left[(V_{h+1}^{\pi_{k}}-\widetilde{V}_{h+1}^{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}(V_{h+1}^{\pi_{k}}-\widetilde{V}_{h+1}^{k})\right](s_{h}^{k},a_{h}^{k})-(V_{h+1}^{\pi_{k}}-\widetilde{V}_{h+1}^{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}).$ (18)

Therefore, plugging (18) into (13), we have the regret decomposition as
follows.

$\displaystyle\mathcal{R}(K)\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 focus on $\beta_{h}^{k,pv}(s,a)$ in particular since it upper bounds
the term $\beta_{h}^{k,c}(s,a)$ as shown in Lemma 4.1. 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{H\sum_{k=1}^{K}\sum_{h=1}^{H}\frac{L_{c}(\delta)}{\sqrt{{(\widetilde{N}_{h}^{k}(s_{h}^{k},a_{h}^{k})+E_{\varepsilon,\delta,1})\vee
1}}}}_{\mathcal{T}_{1}}+\underbrace{H\sum_{k=1}^{K}\sum_{h=1}^{H}\frac{(SE_{\varepsilon,\delta,2}+2E_{\varepsilon,\delta,1})}{(\widetilde{N}_{h}^{k}(s_{h}^{k},a_{h}^{k})+E_{\varepsilon,\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
H{L_{c}(\delta)}\sum_{k=1}^{K}\sum_{h=1}^{H}\sqrt{\frac{1}{{{N}_{h}^{k}(s,a)\vee
1}}}$
$\displaystyle=H{L_{c}(\delta)}\sum_{h,s,a}\sum_{i=1}^{N_{h}^{K}(s,a)}\frac{1}{\sqrt{i}}$
$\displaystyle\leq
c^{\prime}H{L_{c}(\delta)}\sum_{h,s,a}\sqrt{N_{h}^{K}(s,a)}$
$\displaystyle\leq
c^{\prime}H{L_{c}(\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_{\varepsilon,\delta,2}+E_{\varepsilon,\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_{\varepsilon,\delta,2}+E_{\varepsilon,\delta,1})\sum_{h,s,a}\sum_{i=1}^{N_{h}^{K}(s,a)}\frac{1}{i}$
$\displaystyle\leq
c^{\prime}H(SE_{\varepsilon,\delta,2}+E_{\varepsilon,\delta,1})\sum_{h,s,a}\ln(N_{h}^{K}(s,a))$
$\displaystyle=\widetilde{O}\left(H^{2}S^{2}AE_{\varepsilon,\delta,2}+H^{2}SAE_{\varepsilon,\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_{\varepsilon,\delta,2}+H^{2}SAE_{\varepsilon,\delta,1}\right).$

By following the same analysis as in $\mathcal{T}_{2}$, we can bound the
summation over
$\xi_{h}^{k}=:\frac{c^{\prime}SH^{2}L^{\prime}(\delta)}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\delta,1})\vee
1}$ and
$\zeta_{h}^{k}:=\frac{2cSHE_{\varepsilon,\delta,1}+cSHE_{\varepsilon,\delta,2}}{(\widetilde{N}_{h}^{k}(s,a)+E_{\varepsilon,\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_{\varepsilon,2}+E_{\varepsilon,1})\right).$

Finally, we are going to bound the summation over
$\chi_{h}^{k}:=\left[P_{h}(V_{h+1}^{\pi_{k}}-\widetilde{V}_{h+1}^{k})\right](s_{h}^{k},a_{h}^{k})-(V_{h+1}^{\pi_{k}}-\widetilde{V}_{h+1}^{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 $X_{h+1}^{k}:=\chi_{h}^{k}$. Then, we have

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

This holds since the expectation only captures randomness over $s_{h+1}^{k}$.
Thus, $X_{h+1}^{k}$ is a martingale difference sequence. Moreover, we have
$|X_{h+1}^{k}|\leq 4H$ 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}X_{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\mathcal{R}(T)=O\left(\left(\sqrt{SAH^{3}T}+S^{2}AH^{3}+S^{2}AH^{2}E_{\varepsilon,\delta,1}+S^{2}AH^{2}E_{\varepsilon,\delta,2}\right){\log}(S,A,T,1/\delta)\right).$
(20)

∎

###  B.1 Discussions

We end this section by comparing our results with existing works on private
value-iteration RL, i.e., Garcelon et al. (2020) on LDP and Vietri et al.
(2020) on JDP.

  * •

In Garcelon et al. (2020), the privacy-independent leading term has a
dependence on $S$ rather than $\sqrt{S}$ in our result (i.e., the first term
in (20)). This is because they directly bound the transition term $\left\lVert
P_{h}(\cdot|s,a)-\widetilde{P}_{h}^{k}(\cdot|s,a)\right\rVert_{1}$, which
incurs the additional $\sqrt{S}$. In particular, after step (a) in (B), they
directly bound $\widetilde{P}_{h}^{k}\widetilde{V}_{h+1}^{k}$ by
$P_{h}\widetilde{V}_{h+1}^{k}+H\beta_{h}^{k,p}$ and then recursively expand
the term. Note that $\beta_{h}^{k,p}$ has an additional factor $\sqrt{S}$,
which directly leads to the dependence $S$ in the final result. In contrast,
we handle (a) in (B) by following the idea in Azar et al. (2017). That is, we
first extract the term $(P_{h}-\widetilde{P}_{h}^{k})V_{h+1}^{*}$, which can
be bounded by standard Hoeffding’s inequality since $V_{h+1}^{*}$ is fixed and
hence no additional $\sqrt{S}$ is introduced. Due to this extraction, we have
an additional ‘correction’ term, i.e.,
$\left[(P_{h}-\widetilde{P}_{h}^{k})(\widetilde{V}_{h+1}^{k}-{V}_{h+1}^{*})\right]$.
To bound it, we use Bernstein’s-type inequality to bound
$(P_{h}(s^{\prime}|s,a)-\widetilde{P}_{h}^{k}(s^{\prime}|s,a))$ in (16). This
allows us to obtain the final recursive formula.

  * •

In Vietri et al. (2020), although the claimed result has the same regret bound
as ours, its current analysis has gaps. First, to derive the regret
decomposition in Lemma 18 therein, the private estimates were incorrectly used
as the true cost and transition functions. This lead to a simpler but
incorrect regret decomposition since it omits the ‘error’ term between the
private estimates and true values. Second, even if we add the omitted ‘error’
term (between private estimates and true values) into the regret
decomposition, its current analysis cannot achieve the same result as ours.
This is due to a similar argument in bullet one. That is, in order to use its
current confidence bound $\widetilde{\text{conf}}_{t}$ to avoid the additional
$\sqrt{S}$ factor, it needs to use Bernstein’s-type inequality to bound the
‘correction’ term. They fail to consider this since the regret decomposition
does not have the ‘error’ term as it was incorrectly omitted in Lemma 18.

##  Appendix C Proofs for Section 5

First, we present the proof of Lemma 5.1. Corollary 5.2 is a direct
consequence of Lemma 5.1 and Theorems 3.2 and 4.2.

###### Proof of Lemma 5.1.

We start with the privacy guarantee of the Central-Privatizer. First, consider
the counters for number of visited states $N_{h}^{k}(s,a)$. Note that there
are $SAH$ many counters, and each counter is a $K$-bounded binary mechanism of
Chan et al. (2010). Now, consider the counter corresponding to a fixed tuple
$(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$. Note that, at every episode
$k\in[K]$, the private count $\widetilde{N}_{h}^{k}(s,a)$ is the sum of at
most $\log K$ noisy $\mathrm{P}\text{-}\mathrm{sums}$, where each
$\mathrm{P}\text{-}\mathrm{sum}$ is corrupted by an independent Laplace noise
$\text{Lap}\left(\frac{3H\log K}{\varepsilon}\right)$. Therefore, by (Chan et
al., 2010, Theorem 3.5), the private counts
$\\{\widetilde{N}_{h}^{k}(s,a)\\}_{k\in[K]}$ satisfy
$\frac{\varepsilon}{3H}$-DP.

Now, observe that each counter takes as input the data stream
$\sigma_{h}(s,a)\in\\{0,1\\}^{K}$, where the $j$-th bit
$\sigma_{h}^{j}(s,a):=\mathbb{I}\\{s_{h}^{j}=s,a_{h}^{j}=a\\}$ denotes whether
the pair $(s,a)$ is encountered or not at step $h$ of episode $j$. Consider,
some other data stream $\sigma^{\prime}_{h}(s,a)\in\\{0,1\\}^{K}$ which
differs from $\sigma_{h}(s,a)$ only in one entry. Then, we have
$\left\lVert\sigma_{h}(s,a)-\sigma^{\prime}_{h}(s,a)\right\rVert_{1}=1$.
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\lVert\sigma_{h}(s,a)-\sigma^{\prime}_{h}(s,a)\right\rVert_{1}\leq
H,$

Therefore, by (Hsu et al., 2016, Lemma 34), the composition of all these $SAH$
different counters, each of which is $\frac{\varepsilon}{3H}$-DP, satisfies
$\frac{\varepsilon}{3}$-DP.

Using similar arguments, one can show that composition of the counters for
empirical rewards $C_{h}^{k}(s,a)$ and state transitions
$N_{h}^{k}(s,a,s^{\prime})$ satisfy $\frac{\varepsilon}{3}$-DP individually.
Finally, employing the composition property of DP Dwork et al. (2014), we
obtain that the Central-Privatizer is $\varepsilon$-DP.

Let us now focus on the utility of the Central-Privatizer. First, fix a tuple
$(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$, and consider the private
counts $\widetilde{N}_{h}^{k}(s,a)$ corresponding to number of visited states
$N_{h}^{k}(s,a)$. Note that, at each episode $k\in[K]$, the cost of privacy
$\left|\widetilde{N}_{h}^{k}(s,a)-{N}_{h}^{k}(s,a)\right|$ is the sum of at
most $\log K$ i.i.d. random variables $\text{Lap}\left(\frac{3H\log
K}{\varepsilon}\right)$. Therefore, by (Chan et al., 2010, Theorem 3.6), we
have

$\mathbb{P}\left[{\left|\widetilde{N}_{h}^{k}(s,a)-{N}_{h}^{k}(s,a)\right|\leq\frac{3H}{\varepsilon}\sqrt{8\log^{3}K\log(6/\delta)}}\right]\geq
1-\delta/3.$

Now, by a union bound argument, we obtain

$\mathbb{P}\left[{\forall(s,a,k,h),\;\;\left|\widetilde{N}_{h}^{k}(s,a)-{N}_{h}^{k}(s,a)\right|\leq\frac{3H}{\varepsilon}\sqrt{8\log^{3}K\log(6SAT/\delta)}}\right]\geq
1-\delta/3.$

Using similar arguments, one can show that the private counts
$\widetilde{C}_{h}^{k}(s,a)$ and $\widetilde{N}_{h}^{k}(s,a,s^{\prime})$
corresponding rewards $C_{h}^{k}(s,a)$ and state transitions
$N_{h}^{k}(s,a,s^{\prime})$, respectively, satisfy

$\displaystyle\mathbb{P}\left[{\forall(s,a,k,h),\;\;\left|\widetilde{C}_{h}^{k}(s,a)-{C}_{h}^{k}(s,a)\right|\leq\frac{3H}{\varepsilon}\sqrt{8\log^{3}K\log(6SAT/\delta)}}\right]\geq
1-\delta/3,$
$\displaystyle\mathbb{P}\left[{\forall(s,a,s^{\prime},k,h),\;\;\left|\widetilde{N}_{h}^{k}(s,a,s^{\prime})-{N}_{h}^{k}(s,a,s^{\prime})\right|\leq\frac{3H}{\varepsilon}\sqrt{8\log^{3}K\log(6S^{2}AT/\delta)}}\right]\geq
1-\delta/3.$

Combining all the three guarantees together using a union bound, we obtain
that Central-Privatizer satisfies Assumption 1. ∎

Next, we present the proof of Lemma 5.4. Corollary 5.5 is a direct consequence
of Lemma 5.4 and Theorems 3.2 and 4.2.

###### Proof of Lemma 5.4.

We start with the utility guarantee of the Local-Privatizer. First, fix a
tuple $(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$, and consider the
private counts $\widetilde{N}_{h}^{k}(s,a)$ for the number of visited states
$N_{h}^{k}(s,a)$. Note that, at each episode $k\in[K]$, the cost of privacy
$\left|\widetilde{N}_{h}^{k}(s,a)-{N}_{h}^{k}(s,a)\right|$ is the sum of at
most $K$ i.i.d. random variables
$\text{Lap}\left(\frac{3H}{\varepsilon}\right)$. Therefore, by (Dwork et al.,
2014, Corollary 12.4), we have

$\mathbb{P}\left[{\left|\widetilde{N}_{h}^{k}(s,a)-{N}_{h}^{k}(s,a)\right|\leq\frac{3H}{\varepsilon}\sqrt{8K\log(6/\delta)}}\right]\geq
1-\delta/3.$

Now, by a union bound argument, we obtain

$\mathbb{P}\left[{\forall(s,a,k,h),\;\;\left|\widetilde{N}_{h}^{k}(s,a)-{N}_{h}^{k}(s,a)\right|\leq\frac{3H}{\varepsilon}\sqrt{8K\log(6SAT/\delta)}}\right]\geq
1-\delta/3,$

Using similar arguments, one can show that the private counts
$\widetilde{C}_{h}^{k}(s,a)$ and $\widetilde{N}_{h}^{k}(s,a,s^{\prime})$
corresponding rewards $C_{h}^{k}(s,a)$ and state transitions
$N_{h}^{k}(s,a,s^{\prime})$, respectively, satisfy

$\displaystyle\mathbb{P}\left[{\forall(s,a,k,h),\;\;\left|\widetilde{C}_{h}^{k}(s,a)-{C}_{h}^{k}(s,a)\right|\leq\frac{3H}{\varepsilon}\sqrt{8K\log(6SAT/\delta)}}\right]\geq
1-\delta/3,$
$\displaystyle\mathbb{P}\left[{\forall(s,a,s^{\prime},k,h),\;\;\left|\widetilde{N}_{h}^{k}(s,a,s^{\prime})-{N}_{h}^{k}(s,a,s^{\prime})\right|\leq\frac{3H}{\varepsilon}\sqrt{8K\log(6S^{2}AT/\delta)}}\right]\geq
1-\delta/3.$

Combining all the three guarantees together using a union bound, we obtain
that Local-Privatizer satisfies Assumption 1.

Now, we turn towards the privacy guarantee of the Local-Privatizer. First, we
fix an episode $k\in[K]$. Now, we fix a tuple
$(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$, and consider the private
version $\widetilde{\sigma}_{h}^{k}(s,a)$ of the bit
$\sigma_{h}^{k}(s,a)\in\\{0,1\\}$, where $\sigma_{h}^{k}(s,a)$ denotes whether
the pair $(s,a)$ is encountered or not at step $h$ of episode $k$. Note that
$\widetilde{\sigma}_{h}^{k}(s,a)$ is obtained from $\sigma_{h}^{k}(s,a)$ via a
Laplace mechanism with noise level $\frac{3H}{\varepsilon}$. Since, the
sensitivity of the input function is $1$, the Laplace mechanism is
$\frac{\varepsilon}{3H}$-DP, as well as it is $\frac{\varepsilon}{3H}$-LDP
Dwork et al. (2014). Furthermore, since at every episode at most $H$ state-
action pairs are encountered, by (Hsu et al., 2016, Lemma 34), the composition
of all these $SAH$ different Laplace mechanisms are $\varepsilon/3$-LDP.

Using similar arguments, one can show that composition of the corresponding
Laplace mechanisms for empirical rewards and state transitions satisfy
$\frac{\varepsilon}{3}$-LDP individually. Finally, employing the composition
property of DP Dwork et al. (2014), we obtain that the Local-Privatizer is
$\varepsilon$-LDP. ∎