# Differentially Private Reinforcement Learning with Linear Function
Approximation

Xingyu Zhou Wayne State University. Email<EMAIL_ADDRESS>
###### Abstract

Motivated by the wide adoption of reinforcement learning (RL) in real-world
personalized services, where users’ sensitive and private information needs to
be protected, we study regret minimization in finite horizon Markov decision
processes (MDPs) under the constraints of differential privacy (DP). Compared
to existing private RL algorithms that work only on tabular finite-state,
finite-actions MDPs, we take the first step towards privacy-preserving
learning in MDPs with large state and action spaces. Specifically, we consider
MDPs with linear function approximation (in particular linear mixture MDPs)
under the notion of joint differential privacy (JDP), where the RL agent is
responsible for protecting users’ sensitive data. We design two private RL
algorithms that are based on value iteration and policy optimization,
respectively, and show that they enjoy sub-linear regret performance while
guaranteeing privacy protection. Moreover, the regret bounds are independent
of the number of states, and scale at most logarithmically with the number of
actions, making the algorithms suitable for privacy protection in nowadays
large scale personalized services. Our results are achieved via a general
procedure for learning in linear mixture MDPs under _changing regularizers_ ,
which not only generalizes previous results for non-private learning, but also
serves as a building block for general private reinforcement learning.

##  1 Introduction

Reinforcement learning (RL) is a control-theoretic protocol, which adaptively
learns to make sequential decisions in an unknown environment through trial
and error. RL has shown to have significant success for delivering a wide
variety of personalized services, including online news and advertisement
recommendation (Li et al., 2010), medical treatment design (Zhao et al.,
2009), natural language processing (Sharma and Kaushik, 2017), and social
robot (Gordon et al., 2016). In these applications, an RL agent improves its
personalization algorithm by interacting with users to maximize the reward. In
particular, in each round, the RL agent offers an action based on the user’s
current state, and then receives the feedback from the user (e.g., next state
and reward, etc.). This feedback is used by the agent to learn the unknown
environment and improve its action selection strategy.

However, in most practical scenarios, the feedback from the users often
encodes their sensitive information. Let us consider the user-agent
interactions in Google Keyboard (Gboard) application. Here, each user is
associated with a sequence of interactions with GBoard, e.g., the complete
input of a sentence (or several sentences) can be viewed as an episode in the
RL protocol. For each step in the episode, the state is the current typed
words, and the action recommended by the GBoard agent is the most promising
next words. The reward generated by the user depends on whether or not the
user has adopted the offered next words as their actual input. It is easy to
see that in this case each user’s states and rewards contain her sensitive
information. Similarly, in a personalized healthcare setting, the states of a
patient include personal information such as age, gender, height, weight,
state of the treatment etc. Another intriguing example is the social robot for
second language education of children (Gordon et al., 2016). The states
include facial expressions, and the rewards contain whether they have passed
the quiz. In all of these RL-based personalized applications, users may not
want any of their sensitive information to be inferred by adversaries. This
directly results in an increasing concern about privacy protection in nowadays
personalized services. To be more specific, although a user might be willing
to share her own information to the agent to obtain a better tailored service,
she would not like to allow third parties to infer her private information
from the output of the learning algorithm. For example, in the GBoard example,
one would like to ensure that an adversary with arbitrary side knowledge and
computation power cannot infer her sensitive information by looking at the
recommended words to other users.

To this end, _differential privacy_ (DP) (Dwork, 2008) has become a standard
mechanism for designing interactive learning algorithms under a rigorous
privacy guarantee for individual data. Most of the previous works on
differentially private learning under partial feedback focus on the simpler
bandit setting (i.e., no notion of states) (Tossou and Dimitrakakis, 2016,
2017; Basu et al., 2019; Mishra and Thakurta, 2015; Zhou and Tan, 2020;
Shariff and Sheffet, 2018). For the general RL problem, there are only a few
works that consider differential privacy (Vietri et al., 2020; Garcelon et
al., 2020). More importantly, only the _tabular MDPs_ are considered in these
works where the states and actions are discrete and finite, and the value
function is represented by a table. However, in real-world applications
mentioned above, the number of states and actions are often very large and can
even be infinite. As a result, the existing private RL algorithms could even
fail and moreover their regret bounds (Vietri et al., 2020; Garcelon et al.,
2020) become quite loose in this case since they are polynomial functions in
terms of the number of states and actions. Thus, one fundamental question that
remains elusive is: _Is it possible to design private RL algorithms under
large state and action spaces with tight regret guarantees?_ Furthermore,
existing regret bounds in both (Vietri et al., 2020; Garcelon et al., 2020)
are only for value-based RL algorithms, and a study on policy-based private RL
algorithms remains open. Recently, policy optimization (PO) has seen great
success in many real-world applications, especially when coupled with function
approximations (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., 2019) and
statistical (i.e., regret) perspective (Cai et al., 2020; Efroni et al.,
2020). Unfortunately, all of these algorithm are non-private and thus a direct
application of them on the above personalized services may lead to privacy
concerns. The recent work (Chowdhury and Zhou, 2021) takes the first step
towards private policy optimization in the tabular setting. Thus, another
fundamental question is: _Can we also design sample-efficient policy-based
private RL algorithms with linear function approximations?_

In this paper, we take a systematic approach to affirmatively answer the above
two fundamental questions. In particular, our contributions can be summarized
as follows.

  * •

We take the first step towards designing privacy preserving RL algorithms with
rigorous statistical guarantees (i.e., regrets) in MDPs with large state and
action spaces. Specifically, under the linear function approximations (i.e.,
linear mixture MDPs), we design both value iteration and policy optimization
based optimistic private RL algorithms and show that they enjoy sublinear
regret in total number of steps while guaranteeing _joint differential
privacy_ (JDP), which, informally, implies that sensitive information about a
given user is protected even if an adversary has access to the actions
prescribed to all other users.

  * •

The regret bound of the value-based algorithm – Private-LinOpt-VI – is
independent of the number of states and actions whereas the regret of the
policy-based algorithm – Private-LinOpt-PO – depends at most logarithmically
on the number of actions making them suitable for large scale MDPs. Moreover,
the cost of privacy under $(\varepsilon,\delta)$-JDP for both Private-LinOpt-
VI and Private-LinOpt-PO scale only with
$\frac{\log(1/\delta)^{1/4}}{\varepsilon^{1/2}}$ given the permitted privacy
budgets $\varepsilon>0$ and $\delta\in(0,1]$.

  * •

The above results are achieved via a general procedure for learning in linear
mixture MDPs under _changing regularizers_ , which not only generalizes
previous results for non-private learning for both valued-based and policy-
based RL, but also serves as a building block for general private RL under
various privacy schemes and different privacy guarantees. In particular, as
opposed to the existing works, where same regularizers are used in every
episode, our approach yields robust parameter estimates and confidence sets
against possible adversarial attacks, paving the way for protecting data
privacy.

###  1.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). In the linear bandit setting with
contextual information, (Shariff and Sheffet, 2018) shows an impossibility
result, i.e., no algorithm can achieve a standard $(\varepsilon,\delta)$-DP
privacy guarantee while guaranteeing a sublinear regret and thus the relaxed
notion of JDP is considered in their paper. This result also implies that
standard DP is incompatible with regret minimization in RL. Recently, another
variant of DP, called _local differential privacy_ (LDP) (Duchi et al., 2013)
has 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; Dubey, 2021). 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. Note that although our main focus is on private RL under JDP
constraints, our proposed framework provides a straightforward way to design
private RL algorithms under LDP constraints.

In the context of value-based tabular MDPs, (Vietri et al., 2020) gives the
first regret bound under JDP while (Garcelon et al., 2020) presents the first
regret bound under LDP constraint. As mentioned before, both bounds become
loose in the presence of large state and action spaces. In addition to regret
minimization, (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 _only_ 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., 2020; Zhou et al., 2021a; He et al., 2021a), we are not
aware of any existing work on private policy optimization.

Concurrent and independent work: There are two concurrent and independent
works (Liao et al., 2021) and (Luyo et al., 2021)111While we upload to Arxiv
after our acceptatnce, which is later than both works, we submit our work
before Oct. 20, 2021, which is the fall deadline of ACM Sigmetrics
conference.. In particular, Liao et al. (2021) also studied differentially
private reinforcement learning under linear mixture MDPs. In particular, they
focused on local differential privacy (LDP) and proposed a private variant of
UCRL-VTR (Ayoub et al., 2020). In contrast, we mainly focus on joint
differential privacy (JDP) and investigated private variants for both value-
based (i.e., UCRL-VTR) and policy-based (i.e., OPPO) algorithms. As already
highlighted in our paper, although our main focus is JDP, our established
framework (relying a general Regularizer and general regret bounds) also
provides a convenient way to obtain the regret bounds under LDP constraints as
in (Liao et al., 2021), following the same modifications in our previous work
(Chowdhury and Zhou, 2021) (see Remarks 6.9 and 6.6). The key difference
compared to the JDP case is that now the Privatizer is placed at each local
user and in total $O(K)$ private noise rather than $O(\log K)$ is added since
each Privatizer at each user adds one independent noise. Nevertheless, for a
direct and detailed treatment of privacy guarantee and regret bounds under LDP
constraints, we refer readers to (Liao et al., 2021). Finally, in addition to
a regret upper bound, (Liao et al., 2021) also presented a lower bound under
LDP constraints.

In the concurrent work (Luyo et al., 2021), the authors also proposed a
unified analysis for private UCRL-VTR under both JDP and LDP constraints,
which shares a similar high-level idea as ours but more detailed results on
the LDP part is provided in (Luyo et al., 2021). While we further study
private policy-based algorithms with linear function approximation, Luyo et
al. (2021) further investigates private model-free algorithms and highlights
interesting and unique issues in the model-free setting.

##  2 Problem Formulation and Preliminaries

In this section, we present the basics of episodic Markov decision processes
with linear function approximations and introduce various notions of
differential privacy in reinforcement learning.

###  2.1 Learning Problem and Linear Function Approximations

In this paper, we consider an episodic MDP
$(\mathcal{S},\mathcal{A},H,(\mathbb{P}_{h})_{h=1}^{H},(r_{h})_{h=1}^{H})$,
where $\mathcal{S}$ and $\mathcal{A}$ are state and action spaces, $H$ is the
length of each episode, $\mathbb{P}_{h}(s^{\prime}|s,a)$ is the probability of
transitioning to state $s^{\prime}$ from state $s$ provided action $a$ is
taken at step $h$ and $r_{h}(s,a)$ is the mean of the reward distribution at
step $h$ 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 maximizes the long term expected reward
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}r_{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}r_{h^{\prime}}(s_{h^{\prime}},a_{h}^{\prime}))\mid
s_{h}=s,a_{h}=a,\pi\right],$

we obtain
$Q^{\pi}_{h}(s,a)=r_{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 maximizes the value for all
states $s$ and step $h$ simultaneously, and the corresponding optimal value
function is denoted by $V^{*}_{h}(s)=\max_{\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 $\mathbb{P}_{h}(s^{\prime}|s,a)$ and mean rewards
$r_{h}(s,a)$, and thus, in turn, the optimal policy $\pi^{*}$. At each episode
$k$, the agent chooses a policy $\pi^{k}=(\pi_{h}^{k})_{h=1}^{H}$ and samples
a trajectory
$\\{s_{1}^{k},a_{1}^{k},r_{1}^{k},\ldots,s_{H}^{k},a_{H}^{k},r_{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, $r_{h}^{k}\in[0,1]$ denotes the (random) reward collected by the agent
with the mean value $r_{h}(s_{h}^{k},a_{h}^{k})$ and
$s_{h+1}^{k}\sim\mathbb{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}^{*}(s_{1}^{k})-V_{1}^{\pi^{k}}(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.

In this paper, we consider episodic MDPs with linear function approximations
that allows us to work with large state and action spaces. Specifically, we
consider the setting where both the transition dynamics and reward functions
are linear with respect to some corresponding feature maps. This setting is
often called _linear mixture MDPs_ (a.k.a., linear kennel MDPs), see (Ayoub et
al., 2020; Zhou et al., 2021b) for various examples of linear mixture MDPs
including the tabular MDPs.

######  Assumption 1 (Linear mixture MDPs).

We assume that the MDP
$(\mathcal{S},\mathcal{A},H,\\{\mathbb{P}_{h}\\}_{h=1}^{H},\\{r_{h}\\}_{h=1}^{H})$
is a linear mixture MDP with a _known_ transition feature mapping
${\psi}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to\mathbb{R}^{d_{1}}$
and a _known_ value feature mapping
${\varphi}:\mathcal{A}\times\mathcal{S}\to\mathbb{R}^{d_{2}}$. That is, for
any $h\in[H]$, there exists an unknown vector
${\theta}_{h,p}\in\mathbb{R}^{d_{1}}$ with
$\left\lVert{\theta}_{h,p}\right\rVert_{2}\leq\sqrt{d_{1}}$ such that

$\displaystyle\mathbb{P}(s^{\prime}|s,a)=\langle{\psi}(s,a,s^{\prime}),{\theta}_{h,p}\rangle$

for any $(s,a,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$,
and there exists an unknown vector ${\theta}_{h,r}\in\mathbb{R}^{d_{2}}$ with
$\left\lVert{\theta}_{h,r}\right\rVert_{2}\leq\sqrt{d_{2}}$ such that

$\displaystyle r_{h}(s,a)=\langle{\varphi}(s,a),{\theta}_{h,r}\rangle$

for any $(s,a)\in\mathcal{S}\times\mathcal{A}$. Moreover, we assume
$\left\lVert{\varphi}(s,a)\right\rVert\leq 1$ for any
$(s,a)\in\mathcal{S}\times\mathcal{A}$ and let
$\phi(s,a):=\int_{s^{\prime}}{\psi}(s^{\prime}|s,a)V(s^{\prime})\,ds^{\prime}$
and assume that for any function $V:\mathcal{S}\to[0,H]$,
$\left\lVert\phi(s,a)\right\rVert_{2}\leq\sqrt{d_{1}}H$ for any
$(s,a)\in\mathcal{S}\times\mathcal{A}$, and $\max\\{d_{1},d_{2}\\}\leq d$.

The class of linear mixture MDPs has been adopted in a series of recent (non-
private) RL works with linear function approximation including both value-
based algorithms (Jia et al., 2020; Ayoub et al., 2020; Zhou et al., 2021b, a;
He et al., 2021b) and policy-based algorithms (Cai et al., 2020; Ding et al.,
2021). Another line of works with linear function approximation adopt _linear
MDP_ model (Jin et al., 2020; Yang and Wang, 2019), which assumes that
$\mathbb{P}(\cdot|s,a)=\langle\tau(s,a),\mu(\cdot)\rangle$ where $\tau(s,a)$
is a known feature mapping and $\mu(\cdot)$ is an unknown measure. Note that
the two commonly used linear models are different and one cannot be recovered
by the other, see a detailed discussions in (Zhou et al., 2021b).

###  2.2 Differential Privacy in Episodic RL

In RL-based personalized services, it is common to view each episode $k\in[K]$
as a trajectory associated to a specific user (cf. Google GBoard application).
To this end, we let $U_{K}=(u_{1},\ldots,u_{K})\in\mathcal{U}^{K}$ to denote a
sequence of $K$ unique222Uniqueness is assumed for simplicity, as for a
returning user one can group her with her previous occurrences and use the
notion of group privacy to provide tight privacy guarantee. users
participating in the private RL protocol with an RL agent $\mathcal{M}$, where
$\mathcal{U}$ is the set of all users. Formally speaking, as in (Vietri et
al., 2020; Garcelon et al., 2020), a user can be captured with a tree of depth
$H$ encoding the state and reward responses she would give to all the $A^{H}$
possible sequences of actions the agent can choose. During the learning
process, user $k$ for episode $k$ is identified by the reward and state
responses $(r_{h}^{k},s_{h+1}^{k})_{h=1}^{H}$ she gives to the actions
$(a_{h}^{k})_{h=1}^{H}$ chosen by the agent under policy $\pi^{k}$. 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~{}.$

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 standard DP requires that changing the states (or reward
response) of a user, the recommended actions to this user will not change too
much, which is in conflict with personalization. In fact, even in the simpler
linear contextual bandit setting, a negative result says that no algorithm can
achieve a sublinear regret while guaranteeing standard DP (Shariff and
Sheffet, 2018). Hence, to preserve the privacy of individual users while
obtaining a nontrivial regret in our RL setting, as in previous works (Shariff
and Sheffet, 2018; Vietri et al., 2020), 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 with
respect to 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 reward responses), which is indeed the intrinsic requirement of
personalization services. 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$ and $\delta\in[0,1]$, a mechanism
$\mathcal{M}\\!:\\!\mathcal{U}^{K}\\!\rightarrow\\!\mathcal{A}^{KH}$ is
$(\varepsilon,\delta)$-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]+\delta.$

Intuitively speaking, JDP in RL means that upon changing one of the
participating users (say user $k$), the information observed by the other
$K-1$ participants will not change substantially. 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), linear quadratic systems (Chowdhury et al., 2021) and it has been
introduced in private tabular RL by Vietri et al. (2020).

In this work, we mainly focus on algorithms that are
$(\varepsilon,\delta)$-JDP to illustrate the power of our proposed general
framework for private RL algorithms. However, in addition to JDP guarantees,
our framework also easily carries out to RL with stringer notion of privacy
protection, called the _local differential privacy_ (LDP) (Duchi et al.,
2013), which is often applied to scenarios where the users may not even be
willing to share it’s data with the agent directly. 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},r_{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 RL
protocol.

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

For any $\varepsilon\geq 0$ and $\delta\in[0,1]$, a mechanism
$\mathcal{M}^{\prime}$ is $(\varepsilon,\delta)$-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]+\delta.$

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).

##  3 Confidence Bounds with Changing Regularizers

In this section, we focus on the key component of both algorithm design and
regret analysis under linear mixture MDPs for both value-based and policy-
based algorithms. That is, the confidence bounds over the regularized least-
squared estimators for unknown $\theta_{h,p}$ and $\theta_{h,r}$. In
particular, we consider a general setting with _changing regularizers_ , which
not only allows us to generalize previous non-private ones, but more
importantly servers a general procedure for designing private RL algorithms
with linear function approximations in later sections.

To begin with, let’s briefly introduce the intuitions behind the regularized
linear regression problem under linear mixture MDPs (cf. (Ayoub et al., 2020;
Zhou et al., 2021a)). In particular, for any step $h$ at episode $k$, the
following equation holds based on the linear mixture MDP model assumption in
Assumption 1

$\displaystyle[\mathbb{P}_{h}V_{h+1}^{k}](s_{h}^{k},a_{h}^{k})=\langle\int_{s^{\prime}}{\psi}(s^{\prime}|s_{h}^{k},a_{h}^{k})V_{h+1}^{k}(s^{\prime})\,ds^{\prime},\theta_{h,p}\rangle=\langle\phi_{h}^{k}(s_{h}^{k},a_{h}^{k}),\theta_{h,p}\rangle,$

where $\\{V_{h}^{k}(\cdot)\\}_{(k,h)\in[K]\times[H]}$ is any value function
maintained based on data collected before episode $k$, and
$\phi_{h}^{k}(\cdot,\cdot):=\int_{s^{\prime}}{\psi}(s^{\prime}|\cdot,\cdot)V_{h+1}^{k}(s^{\prime})\,ds^{\prime}$.
Therefore, learning the true $\theta_{h,p}$ could be translated into solving a
‘linear bandit’ problem where the feature is
$\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})$ and the noise is
$V_{h+1}^{k}(s_{h+1}^{k})-[\mathbb{P}_{h}V_{h+1}^{k}](s_{h}^{k},a_{h}^{k})$.
To this end, one can solve the following regularized linear regression
problem:

$\displaystyle{{\theta}}_{h,p}^{k}$
$\displaystyle:=\mathop{\mathrm{argmin}}_{{\theta}\in\mathbb{R}^{d_{1}}}\left\lVert{\theta}\right\rVert_{Z_{h,p}^{k}}+\sum_{j=1}^{k-1}[V_{h+1}^{j}(s_{h+1}^{j})-\langle\phi_{h}^{k}(s_{h}^{j},a_{h}^{j}),{\theta}\rangle]^{2}$
$\displaystyle=[\underbrace{Z_{h,p}^{k}+\sum_{j=1}^{k-1}\phi_{h}^{k}(s_{h}^{j},a_{h}^{j})\phi_{h}^{k}(s_{h}^{j},a_{h}^{j})^{\top}}_{\mathcal{T}_{1,p}}]^{-1}[\underbrace{\sum_{j=1}^{k-1}\phi_{h}^{k}(s_{h}^{j},a_{h}^{j})V_{h+1}^{j}(s_{h+1}^{j})}_{\mathcal{T}_{2,p}}],$

where $Z_{h,p}^{k}\in\mathbb{R}^{d_{1}\times d_{1}}$ is possibly changing
positive definite matrix. Setting $\Lambda_{h,p}^{k}=\mathcal{T}_{1,p}$ and
$u_{h,p}^{k}=\mathcal{T}_{2,p}+z_{h,p}^{k}$ for some
$z_{h,p}^{k}\in\mathbb{R}^{d_{1}}$ , we can define a new estimator
$\widehat{{\theta}}_{h,p}^{k}$ under changing regularizers
$\\{Z_{h,p}^{k}\\}_{k\in[K],h\in[H]}$ and
$\\{z_{h,p}^{k}\\}_{k\in[K],h\in[H]}$ as

$\displaystyle\widehat{{\theta}}_{h,p}^{k}=[\Lambda_{h,p}^{k}]^{-1}u_{h,p}^{k}.$
(1)

In particular, choosing $Z_{h,p}^{k}=\lambda I$ and $z_{h,p}^{k}=0$ for all
$h,k$ reduces to the standard non-private value-based algorithms (Ayoub et
al., 2020; Zhou et al., 2021a; Cai et al., 2020) and policy-based algorithm
(Cai et al., 2020; Ding et al., 2021) under linear mixture MDPs. Here,
$Z_{h,p}^{k}$ serves as a general regularizer while $z_{h,p}^{k}$ can be used
to account for the noisy version of $\mathcal{T}_{2,p}$ where the noise could
arise from approximation error of $\phi_{h}^{k}$, or, from the added Gaussian
noise in DP mechanisms in later sections.

In this paper, we also consider a random reward as opposed to a deterministic
reward in previous works. To this end, for the estimator of $\theta_{h,r}$, we
consider the minimizer of the following linear regression problem with a
positive definite matrix $Z_{h,r}^{k}$.

$\displaystyle{{\theta}}_{h,r}^{k}$
$\displaystyle:=\mathop{\mathrm{argmin}}_{{\theta}\in\mathbb{R}^{d_{2}}}\left\lVert{\theta}\right\rVert_{Z_{h,r}^{k}}+\sum_{j=1}^{k-1}[r_{h}^{j}(s_{h}^{j},a_{h}^{j})-\langle{\varphi}(s_{h}^{j},a_{h}^{j}),{\theta}\rangle]^{2}$
$\displaystyle=[\underbrace{Z_{h,r}^{k}+\sum_{j=1}^{k-1}{\varphi}(s_{h}^{j},a_{h}^{j}){\varphi}(s_{h}^{j},a_{h}^{j})^{\top}}_{\mathcal{T}_{1,r}}]^{-1}[\underbrace{\sum_{j=1}^{k-1}{\varphi}(s_{h}^{j},a_{h}^{j})r_{h}^{j}(s_{h}^{j},a_{h}^{j})}_{\mathcal{T}_{2,r}}].$

Setting $\Lambda_{h,r}^{k}=\mathcal{T}_{1,r}$ and
$u_{h,r}^{k}=\mathcal{T}_{2,r}+z_{h,r}^{k}$ for some
$z_{h,r}^{k}\in\mathbb{R}^{d_{2}}$, we can define a new estimator
$\widehat{{\theta}}_{h,r}^{k}$ under changing regularizers
$\\{Z_{h,r}^{k}\\}_{k\in[K],h\in[H]}$ and
$\\{z_{h,r}^{k}\\}_{k\in[K],h\in[H]}$ as

$\displaystyle\widehat{{\theta}}_{h,r}^{k}=[\Lambda_{h,r}^{k}]^{-1}u_{h,r}^{k}.$
(2)

One key question now is to guarantee that the two estimators
$\widehat{\theta}_{h,p}^{k}$ and $\widehat{\theta}_{h,r}^{k}$ are close to the
true parameters $\theta_{h,p}$ and $\theta_{h,r}$ with properly constructed
ellipsoids. That is, even under changing regularizers, both $\theta_{h,p}$ and
$\theta_{h,r}$ lie in the following ellipsoids with probability at least
$1-\alpha$ for any $\alpha\in(0,1]$, respectively

$\displaystyle\mathcal{C}_{h,p}^{k}=\left\\{\theta:\left\lVert\theta-\widehat{{\theta}}_{h,p}^{k}\right\rVert_{\Lambda_{h,p}^{k}}\leq\beta_{p}(\alpha)\right\\}\text{
and
}\mathcal{C}_{h,r}^{k}=\left\\{\theta:\left\lVert\theta-\widehat{{\theta}}_{h,r}^{k}\right\rVert_{\Lambda_{h,r}^{k}}\leq\beta_{r}(\alpha)\right\\},$

where $\beta_{p}(\alpha)$ and $\beta_{r}(\alpha)$ are properly chosen
parameters to balance between exploration and exploitation. Throughout this
paper, we will make the following assumptions on the sequence of regularizers
$\\{Z_{h,p}^{k}\\}_{k\in[K],h\in[H]}$, $\\{z_{h,p}^{k}\\}_{k\in[K],h\in[H]}$,
$\\{Z_{h,r}^{k}\\}_{k\in[K],h\in[H]}$ and
$\\{z_{h,r}^{k}\\}_{k\in[K],h\in[H]}$.

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

For any $\alpha\in(0,1]$, there exist constants
$\lambda_{\max,p},\lambda_{\max,r}$, $\lambda_{\min,p},\lambda_{\min,r}$ and
$\nu_{p},\nu_{r}$ depending on $\alpha$ such that, with probability at least
$1-\alpha$, for all $k\in[K]$ and $h\in[H]$, the following relations hold
simultaneously

$\displaystyle\left\lVert
Z_{h,p}^{k}\right\rVert\leqslant\lambda_{\max,p},\;\;\left\lVert(Z_{h,p}^{k})^{-1}\right\rVert\leqslant
1/\lambda_{\min,p}\;\;\text{and}\;\;\left\lVert
z_{h,p}^{k}\right\rVert_{(Z_{h,p}^{k})^{-1}}\leqslant\nu_{p},$

and

$\displaystyle\left\lVert
Z_{h,r}^{k}\right\rVert\leqslant\lambda_{\max,r},\;\;\left\lVert(Z_{h,r}^{k})^{-1}\right\rVert\leqslant
1/\lambda_{\min,r}\;\;\text{and}\;\;\left\lVert
z_{h,r}^{k}\right\rVert_{(Z_{h,r}^{k})^{-1}}\leqslant\nu_{r}.$

With this regularity assumption, we have the following high-probability
confidence bounds over the two estimators, i.e., $\widehat{\theta}_{h,p}^{k}$
in (1) and $\widehat{\theta}_{h,r}^{k}$ in (2).

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

Let Assumptions 1 and 2 hold and $V_{h}^{k}(\cdot)$ in (1) be within $[0,H]$
for all $h\in[H],k\in[K]$. Then, for any $\alpha\in(0,1]$, with probability at
least $1-3\alpha$, the following relations hold simultaneously for all
$k\in[K]$ and $h\in[H]$

$\displaystyle\left\lVert{\theta}_{h,p}-\widehat{{\theta}}_{h,p}^{k}\right\rVert_{\Lambda_{h,p}^{k}}\leq\beta_{p}(\alpha),\text{
and
}\left\lVert{\theta}_{h,r}-\widehat{{\theta}}_{h,r}^{k}\right\rVert_{\Lambda_{h,r}^{k}}\leq\beta_{r}(\alpha),$

where

$\displaystyle\beta_{p}(\alpha)=\frac{H}{2}\sqrt{2\ln\left(\frac{H}{\alpha}\right)+d_{1}\ln\left(1+\frac{KH^{2}}{\lambda_{\min,p}}\right)}+\sqrt{d_{1}\lambda_{\max,p}}+\nu_{p},$
$\displaystyle\beta_{r}(\alpha)=\frac{1}{2}\sqrt{2\ln\left(\frac{H}{\alpha}\right)+d_{2}\ln\left(1+\frac{K}{d_{2}\lambda_{\min,r}}\right)}+\sqrt{d_{2}\lambda_{\max,r}}+\nu_{r}.$

###### Proof.

See Appendix A. ∎

In the next two sections, we will utilize the two confidence bounds to
investigate general value-based and policy-based RL algorithms under changing
regularizers. These results not only generalize the standard results for fixed
regularizers, but allow us to present a general framework for designing
private RL algorithms with differential privacy guarantees in Section 6.

##  4 Optimistic Value-based Algorithm with Changing Regularizers

In this section, we propose an optimistic value-based RL algorithm under
linear mixture MDPs with changing regularizers. Our algorithm can be regarded
as a generalization of UCRL-VTR (Ayoub et al., 2020) where fixed regularizers
are adopted. This generalization serves a basis for designing private value-
based algorithm in Section 6.

As shown in Algorithm 1, compared to UCRL-VTR, the main difference of our
LinOpt-VI-Reg is the adoption of the Regularizer that properly chooses the
four sequences of regularizers $\\{Z_{h,p}^{k}\\}_{k\in[K],h\in[H]}$,
$\\{z_{h,p}^{k}\\}_{k\in[K],h\in[H]}$, $\\{Z_{h,r}^{k}\\}_{k\in[K],h\in[H]}$
and $\\{z_{h,r}^{k}\\}_{k\in[K],h\in[H]}$. Similar to UCRL-VTR, LinOpt-VI-Reg
follows the procedure of optimistic value iteration. Specifically, at each
episode $k$, it first computes the two estimators and the corresponding
exploration bonus terms based on regularized statistics. Then, it computes the
estimated $Q$-function and value function 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 the Regularizer translates these statistics into
regularized ones via the way in Section 3, i.e., using the four regularizers
$\\{Z_{h,p}^{k}\\}_{k\in[K],h\in[H]}$, $\\{z_{h,p}^{k}\\}_{k\in[K],h\in[H]}$,
$\\{Z_{h,r}^{k}\\}_{k\in[K],h\in[H]}$ and
$\\{z_{h,r}^{k}\\}_{k\in[K],h\in[H]}$. The following theorem presents a
general regret bound when the Regularizer in LinOpt-VI-Reg satisfies
Assumption 2.

Input: Number of episodes $K$, time horizon $H$, a Regularizer, confidence
level $\alpha\in(0,1]$

1 Initialize regularized statistics ${\Lambda}_{h,p}^{1}=0$,
${\Lambda}_{h,r}^{1}=0$, ${u}_{h,p}^{1}=0$ and ${u}_{h,r}^{1}=0$

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

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

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

5
$\widehat{{\theta}}_{h,p}^{k}\leftarrow({\Lambda}_{h,p}^{k})^{-1}{u}_{h,p}^{k}$

6
$\widehat{{\theta}}_{h,r}^{k}\leftarrow({\Lambda}_{h,r}^{k})^{-1}{u}_{h,r}^{k}$

7
${\phi}_{h}^{k}\leftarrow\int_{s^{\prime}}{\psi}(s^{\prime}|s,a){V}_{h+1}^{k}(s^{\prime})\,ds$

8
${\Gamma}_{h,p}^{k}\leftarrow\beta_{p}(\alpha)[\phi_{h}^{k}(\cdot,\cdot)^{\top}({\Lambda}_{h,p}^{k})^{-1}\phi_{h}^{k}(\cdot,\cdot)]^{1/2}$

9
${\Gamma}_{h,r}^{k}\leftarrow\beta_{r}(\alpha)[\varphi(\cdot,\cdot)^{\top}({\Lambda}_{h,r}^{k})^{-1}\varphi(\cdot,\cdot)]^{1/2}$

10
${Q}_{h}^{k}(\cdot,\cdot)\leftarrow\max\\{0,\min\\{H-h+1,{\varphi}(\cdot,\cdot)^{\top}\widehat{{\theta}}_{h,r}^{k}+\phi_{h}^{k}(\cdot,\cdot)^{\top}\widehat{{\theta}}_{h,p}^{k}+({\Gamma}_{h,p}^{k}+{\Gamma}_{h,r}^{k})(\cdot,\cdot)\\}\\}$

11 ${V}_{h}^{k}(\cdot)\leftarrow\max_{a\in\mathcal{A}}{Q}_{h}^{k}(\cdot,a)$

12 $\forall
h,\pi_{h}^{k}(\cdot)\leftarrow\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}{Q}_{h}^{k}(\cdot,a)$

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

14 Receive regularized statistics ${\Lambda}_{h,p}^{k+1}$,
${\Lambda}_{h,r}^{k+1}$, ${u}_{h,p}^{k+1}$ and ${u}_{h,r}^{k+1}$ from the
Regularizer

Algorithm 1 LinOpt-VI-Reg

######  Theorem 4.1.

Let Assumption 1 hold and the Regularizer in Algorithm 1 satisfy Assumption 2.
Then, for any $\alpha\in(0,1]$, with probability at least $1-4\alpha$,
Algorithm 1 achieves regret

$\displaystyle\mathcal{R}(T)$
$\displaystyle=O\left(\sqrt{TH^{3}}\left(\ln\frac{H}{\alpha}+d\kappa_{\lambda_{\min}}\right)+\sqrt{THd\kappa_{\lambda_{\min}}}\left(\sqrt{d\lambda_{\max}}+\nu\right)\right)$

where $\kappa_{\lambda_{\min}}:=\ln\left(1+KH^{2}/(\lambda_{\min})\right)$ and
$\lambda_{\min}=\min\\{\lambda_{\min,p},\lambda_{\min,r}\\}$,
$\lambda_{\max}=\max\\{\lambda_{\max,p},\lambda_{\max,r}\\}$ and
$\nu=\max\\{\nu_{p},\nu_{r}\\}$

###### Proof Sketch.

Let $\mathcal{E}(\alpha):=\\{\theta_{h,p}\in\mathcal{C}_{h,p}^{k}\text{ and
}\theta_{h,r}\in\mathcal{C}_{h,r}^{k},\forall h\in[H],k\in[K]\\}$ denote the
‘good’ event, which by Lemma 3.1, holds with probability at least $1-3\alpha$.
Under this good event, we can first show that $Q_{h}^{k}$ maintained in
Algorithm 1 is optimistic with respect to the optimal $Q$-value $Q^{*}_{h}$.
With this property and the linear mixture MDPs assumption, the regret can be
decomposed as follows.

$\displaystyle\sum_{k=1}^{K}V_{k,1}(s_{1}^{k})-V_{1}^{\pi^{k}}(s_{1}^{k})$
$\displaystyle\leq\underbrace{\sum_{k=1}^{K}\sum_{h=1}^{H}2\beta_{p}(\alpha)\min\left\\{1,\left\lVert\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,p}^{k})^{-1}}\right\\}}_{\mathcal{T}_{1}}$
$\displaystyle+\underbrace{\sum_{k=1}^{K}\sum_{h=1}^{H}2H\beta_{r}(\alpha)\min\left\\{1,\left\lVert{\varphi}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,r}^{k})^{-1}}\right\\}}_{\mathcal{T}_{2}}$
$\displaystyle+\underbrace{\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{P}_{h}[V_{h+1}^{k}-V_{h}^{\pi^{k}}](s_{h}^{k},a_{h}^{k})-[V_{h+1}^{k}-V_{h}^{\pi^{k}}](s_{h+1}^{k})}_{\mathcal{T}_{3}}.$

With a properly defined filtration, $\mathcal{T}_{3}$ is a sum of bounded
martingale difference sequence. Therefore, by Azuma-Hoeffding inequality, we
have with probability at least $1-\alpha$, $\mathcal{T}_{3}\leq
H\sqrt{2KH\log(1/\alpha)}$, where we have used boundedenss of value function
in Algorithm 1. To bound $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$, we will use
the trace-determinant lemma and elliptical potential lemma (cf. (Abbasi-
Yadkori et al., 2011, Lemmas 10 and 11)). In particular, by the boundedness of
$\left\lVert\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\right\rVert\leq\sqrt{d_{1}}H$
and $\left\lVert{\varphi}(s_{h}^{k},a_{h}^{k})\right\rVert\leq 1$, and the
Assumption 2 on the Regularizer, we obtain that

$\displaystyle\mathcal{T}_{1}\leq
2\beta_{p}(\alpha)\sqrt{KH}\sqrt{2Hd_{1}\log(1+KH^{2}/(\lambda_{\min,p}))}$
$\displaystyle\mathcal{T}_{2}\leq
2H\beta_{r}(\alpha)\sqrt{KH}\sqrt{2Hd_{2}\log(1+K/(d_{2}\lambda_{\min,r}))}.$

Finally, plugging in the choices of $\beta_{p}(\alpha)$ and
$\beta_{r}(\alpha)$ in Lemma 3.1 and putting everything together, yields the
required result. The full proof is given at Section 7.1. ∎

######  Remark 4.2.

This theorem serves as a building block for analyzing private value-based RL
algorithm under linear mixture MDPs. In particular, the general procedure is
to first instantiate the Regularizer with a specific privacy protection
scheme, and then determine the corresponding values of
$\lambda_{\max},\lambda_{\min},\nu$. Finally, with Theorem 4.1, one can easily
obtain the private regret. One key feature of this result is that it provides
a general analytical framework for private value-based algorithms under
different private schemes and even different types of privacy guarantees
(e.g., JDP and LDP). See more discussions in Section 6.

##  5 Optimistic Policy-based Algorithm with Changing Regularizers

In this section, we turn to focus on policy-based algorithm under linear
mixture MDPs. Our proposed algorithm can be regarded as a bandit-feedback
variant of the OPPO algorithm in (Cai et al., 2020) where the full information
of the reward is observed and the regularizer is fixed. As in the last
section, this generalization serves as a basis for designing private policy-
based algorithm in later section.

As shown in Algorithm 2, our proposed LioOpt-PO-Reg basically consists of two
stages at each episode $k$: _policy evaluation_ and _policy improvement_. In
the policy evaluation stage, it uses the Least-Squares Temporal Difference
(LSTD) (Boyan, 1999; Bradtke and Barto, 1996) to evaluate policy $\pi^{k}$
based on previous $k-1$ historical trajectories. In contrast to standard
process, LinOpt-PO-Reg uses regualrized statistics produced by possible
changing regularizers at this stage. In particular, it estimates
$\mathbb{P}_{h}V_{h+1}^{k}$ with
$(\phi_{h}^{k})^{\top}\widehat{\theta}_{h,p}^{k}$ and estimates $r_{h}$ with
${\varphi}^{\top}\widehat{\theta}_{h,r}^{k}$. These two estimates along with
two UCB exploration bonuses are used to iteratively compute $Q$-function
estimates. The $Q$-estimates are then truncated to the interval $[0,H]$ since
the reward is within $[0,1]$. Then, the corresponding value estimates are
computed by taking the expectation of $Q$-estimates with respect to the
policy. Next, a new trajectory is rolled out by acting the policy $\pi^{k}$
and the Regularizer translates the collected statistics into regularized ones
via the four changing regularizers. Finally, in the policy improvement stage,
LinOpt-PO-Reg 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 (Cai et al., 2020). The following theorem presents a
general regret bound when the Regularizer in LinOpt-PO-Reg satisfies
Assumption 2.

######  Theorem 5.1.

Let Assumption 1 hold and the Regularizer in Algorithm 2 satisfy Assumption 2.
Then, for any $\alpha\in(0,1]$, with probability at least $1-4\alpha$,
Algorithm 2 achieves regret

$\displaystyle\mathcal{R}(T)=O\left(\sqrt{TH^{3}}\left(\log\frac{H}{\alpha}+d\kappa_{\lambda_{\min}}\right)+\sqrt{TH^{3}\log|\mathcal{A}|}+\sqrt{THd\kappa_{\lambda_{\min}}}\left(\sqrt{d\lambda_{\max}}+\nu\right)\right),$

where $\kappa_{\lambda_{\min}}:=\ln\left(1+KH^{2}/(\lambda_{\min})\right)$ and
$\lambda_{\min}=\min\\{\lambda_{\min,p},\lambda_{\min,r}\\}$,
$\lambda_{\max}=\max\\{\lambda_{\max,p},\lambda_{\max,r}\\}$ and
$\nu=\max\\{\nu_{p},\nu_{r}\\}$. Further, suppose
$\sqrt{\log|\mathcal{A}|}=O(\log\frac{H}{\alpha}+d\kappa_{\lambda_{\min}})$,
the regret satisfies

$\displaystyle\mathcal{R}(T)=O\left(\sqrt{TH^{3}}\left(\log\frac{H}{\alpha}+d\kappa_{\lambda_{\min}}\right)+\sqrt{THd\kappa_{\lambda_{\min}}}\left(\sqrt{d\lambda_{\max}}+\nu\right)\right).$

###### Proof Sketch.

As in (Cai et al., 2020), our regret analysis starts with the following regret
decomposition.

$\displaystyle\mathcal{R}(T)$
$\displaystyle=\sum_{k=1}^{K}\left(V_{1}^{*}(s_{1}^{k})-V_{1}^{\pi_{k}}(s_{1}^{k})\right)$
$\displaystyle=\underbrace{\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}_{\pi^{*}}\left[\langle
Q_{h}^{k}(s_{h}^{k}),\pi_{h}^{*}(\cdot|s_{h})-\pi_{h}^{\pi_{k}}(\cdot|s_{h})\rangle\mid
s_{1}=s_{1}^{k}\right]}_{(i)}+\underbrace{\mathcal{M}_{K,H,2}}_{(ii)}$
$\displaystyle+\underbrace{\sum_{k=1}^{K}\sum_{h=1}^{H}\left(\mathbb{E}_{\pi^{*}}[\iota_{h}^{k}(x_{h},a_{h})\mid
s_{1}=s_{1}^{k}]-\iota_{h}^{k}(s_{h}^{k},a_{h}^{k})\right)}_{(iii)},$

where $\iota_{h}^{k}:=r_{h}+\mathbb{P}_{h}V_{h+1}^{k}-Q_{h}^{k}$ and
$\mathcal{M}_{K,H,2}$ is a martingale adapted to a properly defined
filtration. Hence, by the boundedness of both $Q$-function and value function
and Azuma-Hoeffding inequality, we can establish that with probability at
least $1-\alpha$, $(ii)\leq 4H\sqrt{2T\log(1/\alpha)}$. For $(i)$, we can
bound it by using standard properties of KL-divergence and mirror-descent
update along with the fact that $\pi^{1}$ is a uniform distribution. In
particular, we have $(i)\leq\sqrt{2H^{3}T\log|\mathcal{A}|}$. The key part in
the proof is to bound $(iii)$. To this end, we will first show that under good
event $\mathcal{E}(\alpha)$, we have for all $s,a,k,h$,

$\displaystyle
2({\Gamma}_{h,p}^{k}+{\Gamma}_{h,r}^{k})(s,a)\geq-\iota_{h}^{k}(s,a)\geq 0.$
(3)

Therefore, with the above property, we can see that bounding $(iii)$ reduces
to bounding the summation of both bonus terms. Similar to the analysis in the
last section, we have

$\displaystyle(iii)=O\left(\sqrt{TH^{3}}\left(\log\frac{H}{\alpha}+d\kappa_{\lambda_{\min}}\right)+\sqrt{THd\kappa_{\lambda_{\min}}}\left(\sqrt{d\lambda_{\max}}+\nu\right)\right),$

where $\kappa_{\lambda_{\min}}:=\log\left(1+KH^{2}/(\lambda_{\min})\right)$
and $\lambda_{\min}=\min\\{\lambda_{\min,p},\lambda_{\min,r}\\}$,
$\lambda_{\max}=\max\\{\lambda_{\max,p},\lambda_{\max,r}\\}$ and
$\nu=\max\\{\nu_{p},\nu_{r}\\}$. Finally, putting the three terms together,
yields the required result. The full proof is given at Section 8. ∎

######  Remark 5.2.

This theorem provides a clean result to design the first private PO algorithms
with linear function approximations in the next section. As in the last
section, this result offers a simple approach to designing private PO
algorithms under different privacy guarantees, which will be explored in the
next section.

Input: Number of episodes $K$, time horizon $H$, parameter $\eta$, a
Regularizer, confidence level $\alpha\in(0,1]$

1 Initialize regularized statistics ${\Lambda}_{h,p}^{1}=0$,
${\Lambda}_{h,r}^{1}=0$, ${u}_{h,p}^{1}=0$ and ${u}_{h,r}^{1}=0$

2 Initialize policy $\pi^{1}=(\pi_{h}^{1})_{h=1}^{H}$ be uniform distributions
over $\mathcal{A}$

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

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

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

6
$\widehat{{\theta}}_{h,p}^{k}\leftarrow({\Lambda}_{h,p}^{k})^{-1}{u}_{h,p}^{k}$

7
$\widehat{{\theta}}_{h,r}^{k}\leftarrow({\Lambda}_{h,r}^{k})^{-1}{u}_{h,r}^{k}$

8
${\phi}_{h}^{k}\leftarrow\int_{s^{\prime}}{\psi}(s^{\prime}|s,a){V}_{h+1}^{k}(s^{\prime})\,ds$

9
${\Gamma}_{h,p}^{k}(\cdot,\cdot)\leftarrow\beta_{p}[\phi_{h}^{k}(\cdot,\cdot)^{\top}({\Lambda}_{h,p}^{k})^{-1}\phi_{h}^{k}(\cdot,\cdot)]^{1/2}$

10
${\Gamma}_{h,r}^{k}(\cdot,\cdot)\leftarrow\beta_{r}[\varphi(\cdot,\cdot)^{\top}({\Lambda}_{h,r}^{k})^{-1}\varphi(\cdot,\cdot)]^{1/2}$

11
${Q}_{h}^{k}(\cdot,\cdot)\leftarrow\max\\{0,\min\\{H-h+1,{\varphi}(\cdot,\cdot)^{\top}\widehat{{\theta}}_{h,r}^{k}+\phi_{h}^{k}(\cdot,\cdot)^{\top}\widehat{{\theta}}_{h,p}^{k}+({\Gamma}_{h,p}^{k}+{\Gamma}_{h,r}^{k})(\cdot,\cdot)\\}\\}$

12
${V}_{h}^{k}(\cdot)\leftarrow\langle{Q}_{h}^{k}(\cdot,\cdot),\pi_{h}^{k}(\cdot|\cdot)\rangle_{\mathcal{A}}$

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

14 Receive regularized statistics ${\Lambda}_{h,p}^{k+1}$,
${\Lambda}_{h,r}^{k+1}$, ${u}_{h,p}^{k+1}$ and ${u}_{h,r}^{k+1}$ from the
Regularizer

15 Update policy $\forall h$ ,
$\pi_{h}^{k+1}(\cdot|\cdot)\propto{\pi}_{h}^{k}(\cdot|\cdot)\exp\\{\eta{Q}_{h}^{k}(\cdot,\cdot)\\}$

Algorithm 2 LinOpt-PO-Reg

##  6 Privacy and Regret Guarantees

In this section, we shall see how to instantiate the Regularizer in previous
two algorithms with a specific privacy protection scheme–called Privatizer
hereafter–to guarantee JDP while achieving sublinear regret.

###  6.1 Privatizer Design

The main idea behind the Privatizer is to inject Gaussian noise as the
changing regularizers, i.e., $Z_{h,p}^{k}$ and $Z_{h,r}^{k}$ are chosen to be
Gaussian random matrices and $z_{h,p}^{k}$ and $z_{h,r}^{k}$ are Gaussian
random vectors so that the standard Gaussian mechanism (Dwork et al., 2014)
can be applied. These noise are used to privatize the non-private statistics
$G_{h,p}^{k}:=\sum_{j=1}^{k-1}\phi_{h}^{k}(s_{h}^{j},a_{h}^{j})\phi_{h}^{k}(s_{h}^{j},a_{h}^{j})^{\top}$,
$G_{h,r}^{k}:=\sum_{j=1}^{k-1}{\varphi}(s_{h}^{j},a_{h}^{j}){\varphi}(s_{h}^{j},a_{h}^{j})^{\top}$,
$g_{h,p}^{k}:=\sum_{j=1}^{k-1}\phi_{h}^{k}(s_{h}^{j},a_{h}^{j})V_{h+1}^{j}(s_{h+1}^{j})$
and
$g_{h,r}^{k}:=\sum_{j=1}^{k-1}{\varphi}(s_{h}^{j},a_{h}^{j})r_{h}^{j}(s_{h}^{j},a_{h}^{j})$,
all of which are in the form of sums. This motivates us to consider the
_binary counting mechanism_ (Chan et al., 2011), which is a tree-based
utility-efficient scheme for releasing private counts. In the following, let’s
take the design of $Z_{h,p}^{k}$ and $z_{h,p}^{k}$ as an example and the same
method applies to $Z_{h,r}^{k}$ and $z_{h,r}^{k}$. We first initialize $2H$
counters, $\mathcal{B}_{h,p,1}$ and $\mathcal{B}_{h,p,2}$ for each $h\in[H]$.
In particular, $\mathcal{B}_{h,p,1}$ maintains a binary interval tree in which
each node represents a partial sum (P-sum) in the form of
$\Sigma_{p,1}[i,j]=\sum_{k=i}^{j}\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})^{\top}$
involving the features in episodes $i$ through $j$. Each leaf node represents
a P-sum with a single episode (i.e., $i=j$ and hence the tree has $k-1$ leaf
nodes at the start of episode $k$), and each interior node represents the
range of episodes covered by its children. The same construction applies to
$\mathcal{B}_{h,p,2}$ with the P-sum given by
$\Sigma_{p,2}[i,j]=\sum_{k=i}^{j}\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})V_{h+1}^{k}(s_{h+1}^{k})$.
Now, to release the private version of $G_{h,p}^{k}$ for each $k$ denoted by
$\widehat{G}_{h,p}^{k}$, $\mathcal{B}_{h,p,1}$ first release a noisy P-sum
$\widehat{\Sigma}_{p,1}[i,j]$ corresponding to each node in the tree. Here
$\widehat{\Sigma}_{p,1}[i,j]$ is obtained by perturbing both $(p,q)$-th and
$(q,p)$-th, $1\leq p\leq q\leq d_{1}$, entries of $\Sigma_{p,1}[i,j]$ with
i.i.d Gaussian noise $\mathcal{N}(0,\sigma_{p,1}^{2})$333This will ensure
symmetric of the P-sums even after adding noise.. Then the private
$\widehat{G}_{h,p}^{k}$ is computed by summing up the noisy P-sums that
uniquely cover the range $[1,k-1]$. Algorithmically speaking,
$\mathcal{B}_{h,p,1}$ is constructed and maintained by simply replacing the
input stream of 0/1 bit in Algorithm 2 of (Chan et al., 2011) with the stream
of
$\\{\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})^{\top}\\}_{k=1}^{K}$
in our case. To guarantee the resultant matrix is still positive definite,
$\mathcal{B}_{h,p,1}$ shifts $\widehat{G}_{h,p}^{k}$ by $\gamma I$ for some
$\gamma>0$ specified later. Thus, the final matrix $\Lambda_{h,p}^{k}$ is the
sum of non-private statistics $G_{h,p}^{k}$ and noise matrix $Z_{h,p}^{k}$,
where $Z_{h,p}^{k}=N_{h,p}^{k}+\gamma I$ and $N_{h,p}^{k}$ is the total noise
added via the summation of noisy P-sums. Similarly, for the counter
$\mathcal{B}_{h,p,2}$, the noisy P-sum $\widehat{\Sigma}_{p,2}[i,j]$ is
generated by perturbing each element of the $d_{1}\times 1$ vector with i.i.d
Gaussian noise $\mathcal{N}(0,\sigma_{p,2}^{2})$. Then, the private
$\widehat{g}_{h,p}^{k}$ is computed by summing up the noisy P-sums that
uniquely cover the range $[1,k-1]$. As a result, the final vector
$u_{h,p}^{k}$ is the sum of $g_{h,p}^{k}$ and $z_{h,p}^{k}$, where
$z_{h,p}^{k}$ is the total noise added in the covering noisy P-sums. We follow
the same way to maintain the counters $\mathcal{B}_{h,r,1}$ and
$\mathcal{B}_{h,r,2}$ to privatize $G_{h,r}^{k}$ and $g_{h,r}^{k}$ and hence
obtaining $Z_{h,r}^{k}$ and $z_{h,r}^{k}$. Note that, at the end of each
episode, the counters only need to store noisy P-sums required for computing
private statistics at future episodes, and hence can safely discard P-sums
that are no longer needed.

One key problem in differential privacy is to balance between privacy
guarantee and utility (i.e., regret in our case). That is, if more noise is
added during the process, it becomes easier to guarantee privacy but meanwhile
suffers from a worse regret. The distinguishing feature of binary counting
mechanism discussed above is the ability to maintain a nice trade-off between
privacy and utility, which is demonstrated via the following fundamental
properties (Chan et al., 2011).

######  Lemma 6.1 (Fundamental properties of binary counting mechanism).

Let $m:=\lceil\log K\rceil$. For all the counters $\mathcal{B}_{h,p,1}$,
$\mathcal{B}_{h,p,2}$, $\mathcal{B}_{h,r,1}$ and $\mathcal{B}_{h,r,2}$
introduced above, we have

  1. (i)

Each episode appears only in at most $m$ P-sums.

  2. (ii)

There are at most $m$ P-sums that uniquely cover the range $[1,k-1],~{}\forall
k\in[K]$ .

In the following, we will rely on the two properties in Lemma 6.1 to analyze
the privacy and regret guarantees, respectively. Before that, we first
formally define two private RL algorithms by instantiating the Regularizer in
Algorithm 1 and 2 with the Privatizer that consists of the four counters
$\mathcal{B}_{h,p,1}$, $\mathcal{B}_{h,p,2}$, $\mathcal{B}_{h,r,1}$ and
$\mathcal{B}_{h,r,2}$ introduced above.

######  Definition 6.2 (Private-LinOpt-VI).

Private-LinOpt-VI is defined as an instance of Algorithm 1 with the
Regularizer being instantiated by a Privatizer that consists of the four
private counters $\mathcal{B}_{h,p,1}$, $\mathcal{B}_{h,p,2}$,
$\mathcal{B}_{h,r,1}$ and $\mathcal{B}_{h,r,2}$.

######  Definition 6.3 (Private-LinOpt-PO).

Private-LinOpt-PO is defined as an instance of Algorithm 2 with the
Regularizer being instantiated by a Privatizer that consists of the four
private counters $\mathcal{B}_{h,p,1}$, $\mathcal{B}_{h,p,2}$,
$\mathcal{B}_{h,r,1}$ and $\mathcal{B}_{h,r,2}$.

###  6.2 Privacy Guarantee

In this section, we will show that both private algorithms provide JDP
guarantee, which is summarized in the following theorem.

######  Theorem 6.4.

Let Assumption 1 hold. For any $\varepsilon>0$ and $\delta\in(0,1]$, both
Private-LinOpt-VI and Private-LinOpt-PO can guarantee
$O(\varepsilon,\delta)$-JDP.

###### Proof.

We first show that with proper choices of noise parameter in the four counters
(i.e., $\sigma_{p,1},\sigma_{p,2},\sigma_{r,1},\sigma_{r,2}$), all the four
counters are $(\varepsilon/4,\delta/4)$-DP. We begin with the counter
$\mathcal{B}_{h,p,1}$. To this end, we need to determine a global upper bound
$\Delta_{p,1}$ over the $L_{2}$-sensitivity so as to apply Gaussian mechanism
(Dwork et al., 2014). Here, $\Delta_{p,1}$ encodes the maximum change in the
Frobenious norm of each P-sum if the state-action pair of a single episode is
changed. By the boundedness assumptions in Assumption 1, we have
$\left\lVert\phi_{h}^{k}(s,a)\right\rVert\leq\sqrt{d_{1}}H,\forall s,a,h,k$,
and hence $\Delta_{p,1}=d_{1}H^{2}\leq dH^{2}$. Since the noisy P-sums are
obtained via Gaussian noise, we have that each $\widehat{\Sigma}_{p,1}[i,j]$
is $(\Delta_{p,1}^{2}/2\sigma_{p,1}^{2})$-CDP (Bun and Steinke, 2016,
Proposition 1.6). Now, by the property (i) in Lemma 6.1 and the composition
property of DP, the whole counter $\mathcal{B}_{h,p,1}$ is
$(m\Delta_{p,1}^{2}/2\sigma_{p,1}^{2})$-CDP, and thus, in turn,
$\left(\frac{m\Delta_{p,1}^{2}}{2\sigma_{p,1}^{2}}\\!+\\!2\sqrt{\frac{m\Delta_{p,1}^{2}}{2\sigma_{p,1}^{2}}\ln\left(\frac{4}{\delta}\right)},\frac{\delta}{4}\right)$-DP
for any $\delta\\!>\\!0$ (Bun and Steinke, 2016, Lemma 3.5). Now, setting
$\sigma_{p,1}^{2}=32m\Delta_{p,1}^{2}\ln(4/\delta)/\varepsilon^{2}$, we can
ensure that $\mathcal{B}_{h,p,1}$ is $O(\varepsilon/4,\delta/4)$-DP. We then
follow the same approach to establish that $\mathcal{B}_{h,p,2}$ is
$O(\varepsilon/4,\delta/4)$-DP with
$\sigma_{p,2}^{2}=32m\Delta_{p,2}^{2}\ln(4/\delta)/\varepsilon^{2}$ and
$\Delta_{p,2}=\sqrt{d_{1}}H^{2}\leq\sqrt{d}H^{2}$. Similarly, we have
$\mathcal{B}_{h,r,1}$ and $\mathcal{B}_{h,r,2}$ are both
$O(\varepsilon/4,\delta/4)$-DP with
$\sigma_{r,1}^{2}=\sigma_{r,2}^{2}=32m\Delta^{2}\ln(4/\delta)/\varepsilon^{2}$
with $\Delta=\Delta_{r,1}=\Delta_{r,2}=1$.

To prove the final result, we now use the _billboard lemma_ (Hsu et al., 2016,
Lemma 9), which states that an algorithm is JDP under continual observation if
the output sent to each user is a function of the user’s private data and a
common quantity computed using standard differential privacy. Note that at
each step $h$ of any episode $k$, in both algorithms, the estimators (e.g.,
$\widehat{\theta}_{h,p}^{k}$) and bonus terms (e.g., $\Gamma_{h,p}^{k}$) are
computed via the four counters, each with $O(\varepsilon/4,\delta/4)$-DP
guarantee. By composition and post-processing properties of DP, we can
conclude that the sequences of policies $\\{\pi^{k}\\}_{k\in[K]}$ are computed
using an $O(\varepsilon,\delta)$-DP mechanism. Now, the actions
$\\{a_{h}^{k}\\}_{h\in H}$ during episode $k$ are generated via the policy
$\pi^{k}$ and the user’s data $s_{h}^{k}$ as $a_{h}^{k}=\pi^{k}(s_{h}^{k})$.
Then, by the billboard lemma, the composition of the controls
$\\{a_{h}^{k}\\}_{k\in K,h\in H}$ sent to all the users is
$O(H\varepsilon,H\delta)$-JDP. Hence, replacing $\varepsilon$ and $\delta$ by
$\varepsilon/H$ and $\delta/H$, yields the final result. ∎

###  6.3 Regret Guarantee

In this section, we will utilize the general regret bounds for LinOpt-VI-Reg
and LinOpt-PO-Reg to derive the private regret bounds. In particular, thanks
to the results in Theorems 4.1 and 5.1, we only need to determine the three
constants $\lambda_{\max},\lambda_{\min}$ and $\nu$ under the Privatizer
(equivalently the Regularizer in Algorithms 1 and 2) such that Assumption 2
holds. To this end, we will use concentration results for random Gaussian
matrix (Lemma B.4) and chi-square random variable (Lemma B.5) to arrive at the
following theorem.

######  Theorem 6.5.

Let Assumption 1 hold. For any privacy parameters $\varepsilon>0$ and
$\delta\in(0,1]$, and for any $\alpha\in(0,1]$, with probability at least
$1-4\alpha$, Private-LinOpt-VI enjoys the regret bound

$\displaystyle\mathcal{R}(T)=O\left(d\sqrt{TH^{3}}\log(T/\alpha)+\frac{\log(H/\delta)^{1/4}}{\varepsilon^{1/2}}d^{7/4}\sqrt{TH^{4}}\log
T\log(T/\alpha)^{1/4}\right).$ (4)

Similarly, for any $\alpha\in(0,1]$, with probability at least $1-4\alpha$,
Private-LinOpt-PO enjoys the regret bound

$\displaystyle\mathcal{R}(T)=O\left(d\sqrt{TH^{3}}\log(T/\alpha)+\sqrt{TH^{3}\log|\mathcal{A}|}+\frac{\log(H/\delta)^{1/4}}{\varepsilon^{1/2}}d^{7/4}\sqrt{TH^{4}}\log
T\log(T/\alpha)^{1/4}\right).$ (5)

Moreover, if
$\sqrt{\log|\mathcal{A}|}=O(\log\frac{H}{\alpha}+d\log(1+KH^{2}))$, then
Private-LinOpt-PO has the same regret bound as given in (4).

###### Proof.

As mentioned above, we only need to verify that the Privatizer satisfies
Assumption 2 with proper choices of $\lambda_{\max,p},\lambda_{\max,r}$,
$\lambda_{\min,p},\lambda_{\min,r}$ and $\nu_{p},\nu_{r}$. We will illustrate
the idea behind $\lambda_{\max,p},\lambda_{\min,p}$ and $\nu_{p}$ here and the
same approach applies to the other three constants. By property (ii) in Lemma
6.1, we know that the total noise added into $\Lambda_{h,p}^{k}$ is a
summation of $m$ symmetric random Gaussian matrix. That is, $N_{h,p}^{k}$ is a
symmetric matrix with its $(i,j)$-th entry, $1\leq i\leq j\leq d_{1}$, being
i.i.d $\mathcal{N}(0,m\sigma_{p,1}^{2})$. Therefore, by a tighter
concentration bound for symmetric random Gaussian matrix (Lemma B.4 in the
appendix), we have with probability at least $1-\alpha/(4KH)$, for all
$k\in[K],h\in[H]$

$\displaystyle\left\lVert
N_{h,p}^{k}\right\rVert\leq\Sigma_{p,1}:=\sigma_{p,1}\sqrt{m}\left(4\sqrt{d}+\sqrt{8\log(8KH/\alpha)}\right).$

Recall that $Z_{h,p}^{k}$ is a shift version of $N_{h,p}^{k}$ to guarantee
that it is positive definite. In particular, we choose
$Z_{h,p}^{k}=N_{h,p}^{k}+2\Sigma_{p,1}I$, which leads to
$\lambda_{\max,p}=3\Sigma_{p,1}$ and $\lambda_{\min,p}=\Sigma_{p,1}$.

Similarly, the total noise in $u_{h,p}^{k}$ is a summation of $m$ random
Gaussian vectors. That is, $z_{h,p}^{k}$ is a $d_{1}\times 1$ vector whose
each entry is i.i.d $\mathcal{N}(0,m\sigma_{p,2}^{2})$. As a result,
$\left\lVert z_{h,p}^{k}\right\rVert^{2}/(m\sigma_{p,2}^{2})$ a
$\chi^{2}$-statistic with $d_{1}$ degrees of freedom, and hence by
concentration bound of chi-square random variable (Lemma B.5 in the appendix),
we have with probability at least $1-\alpha/(4KH)$, for all $k\in[K],h\in[H]$

$\displaystyle\left\lVert
z_{h,p}^{k}\right\rVert\leq\sqrt{m}\sigma_{p,2}\left(\sqrt{d_{1}}+\sqrt{2\log(4KH/\alpha)}\right).$

Thus, via a union bound, we have with probability at least $1-\alpha/2$, for
all $h\in[H]$ and $k\in[K]$,

$\displaystyle\left\lVert
Z_{h,p}^{k}\right\rVert\leqslant\lambda_{\max,p},\;\;\left\lVert(Z_{h,p}^{k})^{-1}\right\rVert\leqslant
1/\lambda_{\min,p}\;\;\text{and}\;\;\left\lVert
z_{h,p}^{k}\right\rVert_{(Z_{h,p}^{k})^{-1}}\leqslant\nu_{p},$

where
$\nu_{p}=\sigma_{p,2}\sqrt{m/\Sigma_{p,1}}\left(\sqrt{d_{1}}+\sqrt{2\log(4KH/\alpha)}\right)$.
Moreover, via the same analysis, we also have with probability at least
$1-\alpha/2$, for all $h\in[H]$ and $k\in[K]$,

$\displaystyle\left\lVert
Z_{h,r}^{k}\right\rVert\leqslant\lambda_{\max,r},\;\;\left\lVert(Z_{h,r}^{k})^{-1}\right\rVert\leqslant
1/\lambda_{\min,r}\;\;\text{and}\;\;\left\lVert
z_{h,r}^{k}\right\rVert_{(Z_{h,r}^{k})^{-1}}\leqslant\nu_{r},$

where $\lambda_{\max,r}=3\lambda_{\min,r}=3\Sigma_{r}$,
$\nu_{p}=\sigma_{r,2}\sqrt{m/\Sigma_{r}}\left(\sqrt{d_{2}}+\sqrt{2\log(4KH/\alpha)}\right)$
and

$\displaystyle\Sigma_{r}=\sigma_{r,1}\sqrt{m}\left(4\sqrt{d_{2}}+\sqrt{8\log(8KH/\alpha)}\right).$

Recall that to guarantee $O(\varepsilon,\delta)$-JDP in Theorem 6.4, we choose
$\sigma_{p,1}=\frac{H\Delta_{p,1}}{\varepsilon}\sqrt{32m\ln(4H/\delta)},\sigma_{p,2}=\frac{H\Delta_{p,2}}{\varepsilon}\sqrt{32m\ln(4H/\delta)},\sigma_{r,1}=\frac{H\Delta_{r,1}}{\varepsilon}\sqrt{32m\ln(4H/\delta)},\sigma_{r,2}=\frac{H\Delta_{r,2}}{\varepsilon}\sqrt{32m\ln(4H/\delta)}$
with $\Delta_{p,1}=d_{1}H^{2}\leq dH^{2}$,
$\Delta_{p,2}=\sqrt{d_{1}}H^{2}\leq\sqrt{d}H^{2}$,
$\Delta_{r,1}=\Delta_{r,2}=1$. Substituting these constants into the regret
bound in Theorems 4.1 and 5.1, yields the final results. ∎

######  Remark 6.6 (Bound on $d$).

Note that $d^{7/4}$ in the second term (i.e., private term) of both regret
bounds comes from simply bounding both $d_{1}$ and $d_{2}$ by $d$. A tighter
bound on $d$ is straightforward if it is written in an explicit form of
$d_{1}$ and $d_{2}$. Note that if we assume that
$\left\lVert\phi(s,a)\right\rVert\leq H$ (as in (He et al., 2021b; Zhou et
al., 2021a) ) rather than $\sqrt{d}H$ in Assumption 1, the private dependency
on $d$ then reduces from $d^{7/4}$ to $d^{5/4}$.

######  Remark 6.7 (Comparisons with non-private algorithms).

The non-private value-based algorithm UCRL-VTR (Jia et al., 2020) enjoys a
regret upper bound $\widetilde{O}(d\sqrt{H^{3}T})$ and the non-private policy-
based algorithm OPPO (Cai et al., 2020) has a regret upper bound
$\widetilde{O}(d\sqrt{TH^{3}}+\sqrt{TH^{3}\log|\mathcal{A}|})$. On the other
hand, Private-LinOpt-VI has a regret bound
$\widetilde{O}(d^{7/4}\sqrt{TH^{4}}(\log(H/\delta)^{1/4})\sqrt{1/\varepsilon})$
and Private-LinOpt-PO has a regret bound
$\widetilde{O}(d^{7/4}\sqrt{TH^{4}}(\log(H/\delta)^{1/4})\sqrt{1/\varepsilon}+\sqrt{TH^{3}\log|\mathcal{A}|})$.

######  Remark 6.8 (Comparisons tabular private RL result).

We compare our results to (Vietri et al., 2020), which establishes regret for
tabular value-based RL under $(\varepsilon,0)$-JDP guarantee by injecting
Laplace noise via binary counting mechanism. In particular, the claimed regret
is $\widetilde{O}\left(\sqrt{SAH^{3}T}+S^{2}AH^{3}/\varepsilon\right)$, i.e.,
both non-private and private terms are polynomial in terms of the number of
states and actions while ours are independent of them. Moreover, the
dependence of $\varepsilon$ is an additive term of $1/\varepsilon$ in (Vietri
et al., 2020) while ours have a multiplicative factor $1/\sqrt{\varepsilon}$
under $(\varepsilon,\delta)$-JDP. Finally, since tabular MDP is a special case
of linear mixture MDP, our established regret bounds directly imply bounds for
the tabular case (although may not be optimal in general through this
reduction.)

######  Remark 6.9 (General private RL design).

As mentioned before, our two proposed algorithms (LinOpt-VI-Reg and LinOpt-PO-
Reg) along with their regret bounds (Theorems 4.1 and 5.1) provide a unified
procedure to designing various private RL algorithms by varying the choice of
Regularizer (or equivalently Privatizer). This not only enables to design new
private RL algorithms with JDP guarantees, but allows us to establish RL
algorithms with LDP guarantees. In this case, instead of a central Privatizer
at the agent, a local Privatizer at each user’s side is used to inject
independent Gaussian noise to user’s trajectories before being collected by
the agent. However, our analysis smoothly carries out and the only change is
to determine the three new constants $\lambda_{\max},\lambda_{\min},\nu$ under
stronger noise in the LDP setting, which can be obtained via the same approach
in our current analysis.

###  6.4 Discussions

In this paper, for the purpose of theoretical analysis, we assume
realizability, i.e. the MDP in fact lies within the class of linear mixture
MDPs. One important future direction is to consider misspecified linear models
(cf. (Jin et al., 2020; Lattimore et al., 2020)). Another important direction
is to apply our flexible framework to MDPs with other types of function
approximation, e.g., kernelized MDPs or overparameterized neural network (Yang
et al., 2020) and generic MDPs (Ayoub et al., 2020). Specifically, at least in
the kernelized MDPs settings (i.e., reproducing kernel Hilbert space (RKHS)),
it turns out that our current analysis can be easily carried out by using the
standard Quadrature Fourier Features (QFF) approximations (Mutnỳ and Krause,
2019). It is worth noting that one drawback of QFF approximation is that it
only works with standard squared exponential kernel but not with more
practical Matérn kernel (Calandriello et al., 2019). One interesting question
is whether it is possible to use adaptive approximation methods (e.g., Nyström
Embedding (Calandriello et al., 2019)) that works for both kernels in the
private RL learning. The difficulty here is that the truncated dimension is
changing in each round. In the setting with general function approximations,
it is still not clear how to generalize our current analysis with a
computationally efficient private scheme such as the binary counting mechanism
used in our paper. Finally, it will also be interesting to consider other
privacy guarantees beyond JDP and LDP, e.g., _shuffle model of DP_ (Cheu et
al., 2019), that achieves a smooth transition between JDP and LDP. This is
particularly useful even in the simpler linear bandit setting as the regret
under LDP is $O(T^{3/4})$ (Zheng et al., 2020) while the regret under JDP is
$O(\sqrt{T})$ (Shariff and Sheffet, 2018). Thus, one interesting question is
whether the shuffle model of DP can be utilized to achieve a similar regret as
in JDP while providing the same strong privacy guarantee as in LDP, which is
one of ongoing works.

##  7 Proofs of Theorems 4.1 and 5.1

In this section, we present the detailed proofs for Theorems 4.1 and 5.1. To
start with, we define the following filtration which will be frequently used
in the proofs. This filtration can be regarded as the bandit-variant of the
one in (Cai et al., 2020).

######  Definition 7.1 (Filtration).

For any $(k,h)\in[K]\times[H]$, we define $\mathcal{F}_{k,h,1}$ as the
$\sigma$-algebra generated by the following state-action-reward sequence,

$\displaystyle\\{(s_{i}^{\tau},a_{i}^{\tau},r_{i}^{\tau})\\}_{(\tau,i)\in[k-1]\times[H]}\cup\\{(s_{i}^{k},a_{i}^{k},r_{i}^{k})_{i\in[h]}\\}$

and $\mathcal{F}_{k,h,2}$ as the $\sigma$-algebra generated by

$\displaystyle\\{(s_{i}^{\tau},a_{i}^{\tau},r_{i}^{\tau})\\}_{(\tau,i)\in[k-1]\times[H]}\cup\\{(s_{i}^{k},a_{i}^{k},r_{i}^{k})_{i\in[h]}\\}\cup\\{s_{h+1}^{k}\\},$

where we define $s_{H+1}^{k}$ as a null state for any $k\in[K]$. The
$\sigma$-algebra sequence
$\\{\mathcal{F}_{k,h,m}\\}_{(k,h,m)\in[K]\times[H]\times 2}$ is a filtration
with respect to the timestep index

$\displaystyle t(k,h,m)=2H(k-1)+2(h-1)+m.$

In other words, for any $t(k,h,m)\leq t(k^{\prime},h^{\prime},m^{\prime})$, it
holds that
$\mathcal{F}_{k,h,m}\subseteq\mathcal{F}_{k^{\prime},h^{\prime},m^{\prime}}$.

By the definition, we immediately see that the estimated value function
$V_{h}^{k}$ and $Q$-function $Q_{h}^{k}$ in both algorithms are measurable to
$\mathcal{F}_{k,1,1}$ as they are obtained based on the $(k-1)$ historical
trajectories. Moreover, throughout the proofs, we let
$\mathcal{E}(\alpha):=\\{\theta_{h,p}\in\mathcal{C}_{h,p}^{k}\text{ and
}\theta_{h,r}\in\mathcal{C}_{h,r}^{k},\forall h\in[H],k\in[K]\\}$ denote the
‘good’ event, which by Lemma 3.1, holds with probability at least $1-3\alpha$.

###  7.1 Proof of Theorem 4.1

We first show that the estimated $Q$-function and value function in Algorithm
1 is optimistic. First note that, under the nice event given by
$\mathcal{E}(\alpha)$, we have that for all $s,a,k,h$

$\displaystyle{\varphi}(s,a)^{\top}\widehat{{\theta}}_{h,r}^{k}+\phi_{h}^{k}(s,a)^{\top}\widehat{{\theta}}_{h,p}^{k}+({\Gamma}_{h,p}^{k}+{\Gamma}_{h,r}^{k})(s,a)\geq
r_{h}(s,a)+[\mathbb{P}_{h}V_{h+1}^{k}](s,a)\geq 0$

Thus, under event $\mathcal{E}(\alpha)$, we can remove the truncation at zero
in the update of $Q$ function in Algorithm 1.

######  Lemma 7.2.

Under event $\mathcal{E}(\alpha)$, for any $s,a,k,h$, we have
$Q_{h}^{k}(s,a)\geq Q^{*}_{h}(s,a)$ and $V_{h}^{k}(s,a)\geq V^{*}_{h}(s,a)$.

###### Proof.

The proof is standard (cf. (Ding et al., 2021, Lemma C.4)). We present the
proof here for ease of reference. The result is proved by induction. First
note that the base case for $h=H+1$ holds trivially since all the values are
zero. Fix a $k$, suppose the result holds $h+1$, i.e.,
$Q_{h}^{k+1}(\cdot,\cdot)\geq Q^{*}_{h+1}(\cdot,\cdot)$,
$V_{h+1}^{k}(\cdot,\cdot)\geq V^{*}_{h+1}(\cdot,\cdot)$. Given $s,a$, if
$Q_{h}^{k}(s,a)\geq H$, then $Q_{h}^{k}(s,a)\geq H\geq Q^{*}_{h}(s,a)$.
Otherwise, we have

$\displaystyle Q_{h}^{k}(s,a)-Q^{*}_{h}(s,a)$
$\displaystyle\mathop{=}\limits^{(a)}$
$\displaystyle\langle\widehat{{\theta}}_{h,p}^{k}-{\theta}_{h,p},\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\rangle\\!+\\!\langle\widehat{{\theta}}_{h,r}^{k}-{\theta}_{h,r},{\varphi}(s_{h}^{k},a_{h}^{k})\rangle\\!+\\![\mathbb{P}_{h}V_{h+1}^{k}](s_{h}^{k},a_{h}^{k})$
$\displaystyle\\!+\\!\beta_{p}(\alpha)\left\lVert\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,p}^{k})^{-1}}+\beta_{r}(\alpha)\left\lVert{\varphi}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,r}^{k})^{-1}}\\!-\\![\mathbb{P}_{h}V_{h+1}^{*}](s_{h}^{k},a_{h}^{k})$
$\displaystyle\mathop{\geq}\limits^{(b)}$
$\displaystyle[\mathbb{P}_{h}V_{h+1}^{k}](s,a)-[\mathbb{P}_{h}V_{h+1}^{*}](s,a)$
$\displaystyle\mathop{\geq}\limits^{(c)}$ $\displaystyle 0$

where (a) holds by adding and subtracting the same term, which holds by the
linear kernel MDP model; (b) holds by event $\mathcal{E}(\alpha)$ and Cauchy-
Schwarz inequality; (c) holds by the induction assumption and the fact that
$\mathbb{P}_{h}$ is a monotone operator with respect the partial ordering of
functions. Thus, for all $(s,a)$, we have established that $Q_{h}^{k}(s,a)\geq
Q^{*}_{h}(s,a)$, which directly implies that $V_{h}^{k}(s,a)\geq
V^{*}_{h}(s,a)$. ∎

Now, we are ready to present the proof of Theorem 4.1.

###### Proof.

First, we have under event $\mathcal{E}(\alpha)$,

$\displaystyle V_{h}^{k}(s_{h}^{k})-V_{h}^{\pi^{k}}(s_{h}^{k})$
$\displaystyle\mathop{\leq}\limits^{(a)}$
$\displaystyle\langle\widehat{{\theta}}_{h,p}^{k},\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\rangle+\langle\widehat{{\theta}}_{h,r}^{k},{\varphi}(s_{h}^{k},a_{h}^{k})\rangle+\beta_{p}(\alpha)\left\lVert\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,p}^{k})^{-1}}+\beta_{r}(\alpha)\left\lVert{\varphi}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,r}^{k})^{-1}}$
$\displaystyle
r_{h}(s_{h}^{k},a_{h}^{k})-[\mathbb{P}_{h}V_{h+1}^{\pi^{k}}](s_{h}^{k},a_{h}^{k})$
$\displaystyle\mathop{=}\limits^{(b)}$
$\displaystyle\langle\widehat{{\theta}}_{h,p}^{k}-{\theta}_{h,p},\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\rangle\\!+\\!\langle\widehat{{\theta}}_{h,r}^{k}-{\theta}_{h,r},{\varphi}(s_{h}^{k},a_{h}^{k})\rangle\\!+\\![\mathbb{P}_{h}V_{h+1}^{k}](s_{h}^{k},a_{h}^{k})$
$\displaystyle\\!+\\!\beta_{p}(\alpha)\left\lVert\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,p}^{k})^{-1}}+\beta_{r}(\alpha)\left\lVert{\varphi}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,r}^{k})^{-1}}\\!-\\![\mathbb{P}_{h}V_{h+1}^{\pi^{k}}](s_{h}^{k},a_{h}^{k})$
$\displaystyle\mathop{\leq}\limits^{(c)}$
$\displaystyle[\mathbb{P}_{h}V_{h+1}^{k}](s_{h}^{k},a_{h}^{k})-[\mathbb{P}_{h}V_{h+1}^{\pi^{k}}](s_{h}^{k},a_{h}^{k})+2\beta_{p}(\alpha)\left\lVert\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,p}^{k})^{-1}}+2\beta_{r}(\alpha)\left\lVert{\varphi}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,r}^{k})^{-1}}$
(6)

where (a) holds by the update of $V_{h}^{k}$ in Algorithm 1, the Bellman
equation for $V_{h}^{\pi^{k}}$, and the greedy selection of the algorithm; (b)
holds by the linear mixture MDP model; (c) holds by Cauchy-Schwarz inequality
and the event of $\mathcal{E}(\alpha)$.

Now, by using Lemma 7.2, we can further bound (6) as follows.

$\displaystyle V_{h}^{k}(s_{h}^{k})-V_{h}^{\pi^{k}}(s_{h}^{k})$
$\displaystyle\mathop{\leq}\limits^{(a)}$
$\displaystyle\min\left\\{H,[\mathbb{P}_{h}V_{h+1}^{k}](s_{h}^{k},a_{h}^{k})-[\mathbb{P}_{h}V_{h+1}^{\pi^{k}}](s_{h}^{k},a_{h}^{k})+2\beta_{p}(\alpha)\left\lVert\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,p}^{k})^{-1}}+2\beta_{r}(\alpha)\left\lVert{\varphi}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,r}^{k})^{-1}}\right\\}$
$\displaystyle\mathop{\leq}\limits^{(b)}$
$\displaystyle\min\left\\{H,2\beta_{p}(\alpha)\left\lVert\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,p}^{k})^{-1}}+2\beta_{r}(\alpha)\left\lVert{\varphi}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,r}^{k})^{-1}}\right\\}+[\mathbb{P}_{h}V_{h+1}^{k}](s_{h}^{k},a_{h}^{k})-[\mathbb{P}_{h}V_{h+1}^{\pi^{k}}](s_{h}^{k},a_{h}^{k})$
$\displaystyle\mathop{\leq}\limits^{(c)}$ $\displaystyle
2\beta_{p}(\alpha)\min\left\\{1,\left\lVert\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,p}^{k})^{-1}}\right\\}+2H\beta_{r}(\alpha)\min\left\\{1,\left\lVert{\varphi}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,r}^{k})^{-1}}\right\\}$
$\displaystyle+[\mathbb{P}_{h}V_{h+1}^{k}](s_{h}^{k},a_{h}^{k})-[\mathbb{P}_{h}V_{h+1}^{\pi^{k}}](s_{h}^{k},a_{h}^{k})$

where (a) holds by the fact that value function is bounded in the range
$[0,H]$; (b) is true since $V_{h+1}^{k}(\cdot)\geq V_{h+1}^{\pi^{k}}(\cdot)$
by Lemma 7.2 on event $\mathcal{E}(\alpha)$; (c) is truce since
$2\beta_{p}(\alpha)\geq H$ and $2H\beta_{r}(\alpha)\geq H$ by the definitions
of $\beta_{p}(\alpha)$ and $\beta_{r}(\alpha)$ in Lemma 3.1. Therefore, we
have

$\displaystyle
V_{h}^{k}(s_{h}^{k})-V_{h}^{\pi^{k}}(s_{h}^{k})-\left(V_{h+1}^{k}(s_{h+1}^{k})-V_{h+1}^{\pi^{k}}(s_{h+1}^{k})\right)$
$\displaystyle\leq$ $\displaystyle
2\beta_{p}(\alpha)\min\left\\{1,\left\lVert\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,p}^{k})^{-1}}\right\\}+2H\beta_{r}(\alpha)\min\left\\{1,\left\lVert{\varphi}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,r}^{k})^{-1}}\right\\}$
$\displaystyle+\mathbb{P}_{h}[V_{h+1}^{k}-V_{h}^{\pi^{k}}](s_{h}^{k},a_{h}^{k})-[V_{h+1}^{k}-V_{h}^{\pi^{k}}](s_{h+1}^{k}).$

Therefore, taking a summation over $k\in[K]$ and $h\in[H]$, yields that under
event $\mathcal{E}(\alpha)$

$\displaystyle\sum_{k=1}^{K}V_{1}^{k}(s_{1}^{k})-V_{1}^{\pi^{k}}(s_{1}^{k})$
$\displaystyle\leq\underbrace{\sum_{k=1}^{K}\sum_{h=1}^{H}2\beta_{p}(\alpha)\min\left\\{1,\left\lVert\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,p}^{k})^{-1}}\right\\}}_{\mathcal{T}_{1}}$
$\displaystyle+\underbrace{\sum_{k=1}^{K}\sum_{h=1}^{H}2H\beta_{r}(\alpha)\min\left\\{1,\left\lVert{\varphi}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,r}^{k})^{-1}}\right\\}}_{\mathcal{T}_{2}}$
$\displaystyle+\underbrace{\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{P}_{h}[V_{h+1}^{k}-V_{h}^{\pi^{k}}](s_{h}^{k},a_{h}^{k})-[V_{h+1}^{k}-V_{h}^{\pi^{k}}](s_{h+1}^{k})}_{\mathcal{T}_{3}}.$

Now, we are left to bound each of the two terms. First, $\mathcal{T}_{3}$ is a
summation of a bounded martingale difference sequence, with boundedness being
$H$. To see this, we let
$Y_{k,h}:=\mathbb{P}_{h}[V_{h+1}^{k}-V_{h}^{\pi^{k}}](s_{h}^{k},a_{h}^{k})-[V_{h+1}^{k}-V_{h}^{\pi^{k}}](s_{h+1}^{k})$.
Then, we have $Y_{k,h}\in\mathcal{F}_{k,h,2}$ and
$\mathbb{E}\left[Y_{k,h}\mid\mathcal{F}_{k,h,1}\right]=0$. Thus, by the
Azuma–Hoeffding inequality, we have that for any fixed $\alpha\in(0,1]$, with
probability at least $1-\alpha$,

$\displaystyle\mathcal{T}_{3}\leq H\sqrt{2KH\log(1/\alpha)}.$

To bound $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$, we will use the standard
elliptical potential lemma (cf. (Abbasi-Yadkori et al., 2011, Lemma 11)). In
particular, we have

$\displaystyle\mathcal{T}_{1}$
$\displaystyle\mathop{\leq}\limits^{(a)}2\beta_{p}(\alpha)\sqrt{KH}\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\min\left\\{1,\left\lVert\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,p}^{k})^{-1}}^{2}\right\\}}$
$\displaystyle\mathop{\leq}\limits^{(b)}2\beta_{p}(\alpha)\sqrt{KH}\sqrt{2Hd_{1}\log(1+KH^{2}/(\lambda_{\min,p}))},$

where (a) holds by Cauchy-Schwarz inequality; (b) follows from Lemma 11 in
(Abbasi-Yadkori et al., 2011) and the last step in the proof of Lemma 3.1.
Similarly, we have

$\displaystyle\mathcal{T}_{2}$ $\displaystyle\leq
2H\beta_{r}(\alpha)\sqrt{KH}\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\min\left\\{1,\left\lVert{\varphi}(s_{h}^{k},a_{h}^{k})\right\rVert_{(\Lambda_{h,r}^{k})^{-1}}^{2}\right\\}}$
$\displaystyle\leq
2H\beta_{r}(\alpha)\sqrt{KH}\sqrt{2Hd_{2}\log(1+K/(d_{2}\lambda_{\min,r}))}.$

Finally, note that $V_{1}^{*}(s_{1}^{k})\leq V_{1}^{k}(s_{1}^{k})$ for all $k$
by Lemma 7.2. Putting everything together, we have for any $\alpha\in(0,1]$,
with probability at least $1-4\alpha$, Algorithm 1 achieves a regret bound

$\displaystyle\mathcal{R}(T)$
$\displaystyle=O\left(\sqrt{TH^{3}}\left(\log\frac{H}{\alpha}+d\kappa_{\lambda_{\min}}\right)+\sqrt{THd\kappa_{\lambda_{\min}}}\left(\sqrt{d\lambda_{\max}}+\nu\right)\right)$

where $\kappa_{\lambda_{\min}}:=\log\left(1+KH^{2}/(\lambda_{\min})\right)$
and $\lambda_{\min}=\min\\{\lambda_{\min,p},\lambda_{\min,r}\\}$,
$\lambda_{\max}=\max\\{\lambda_{\max,p},\lambda_{\max,r}\\}$ and
$\nu=\max\\{\nu_{p},\nu_{r}\\}$ ∎

##  8 Proof of Theorem 5.1

###### Proof.

We start with the following standard regret decomposition (cf. (Cai et al.,
2020, Lemma 4.2)).

$\displaystyle\mathcal{R}(T)$
$\displaystyle=\sum_{k=1}^{K}\left(V_{1}^{*}(s_{1}^{k})-V_{1}^{\pi_{k}}(s_{1}^{k})\right)$
$\displaystyle=\underbrace{\sum_{k=1}^{K}\sum_{h=1}^{H}\mathbb{E}_{\pi^{*}}\left[\langle
Q_{h}^{k}(s_{h}^{k}),\pi_{h}^{*}(\cdot|s_{h})-\pi_{h}^{\pi_{k}}(\cdot|s_{h})\rangle\mid
s_{1}=s_{1}^{k}\right]}_{(i)}+\underbrace{\mathcal{M}_{K,H,2}}_{(ii)}$
$\displaystyle+\underbrace{\sum_{k=1}^{K}\sum_{h=1}^{H}\left(\mathbb{E}_{\pi^{*}}[\iota_{h}^{k}(x_{h},a_{h})\mid
s_{1}=s_{1}^{k}]-\iota_{h}^{k}(s_{h}^{k},a_{h}^{k})\right)}_{(iii)},$

where $\iota_{h}^{k}:=r_{h}+\mathbb{P}_{h}V_{h+1}^{k}-Q_{h}^{k}$ and
$\mathbb{E}_{\pi}[\cdot]$ is taking expectation with respect to $\pi$ with
transitions $\mathbb{P}_{h}$.

Here, $\\{\mathcal{M}_{k,h,m}\\}_{(k,h,m)\in[K]\times[H]\times[2]}$ is a
martingale adapted to the filtration
$\\{\mathcal{F}_{k,h,,}\\}_{(k,h,m)\in[K]\times[H]\times[2]}$ with respect to
the timestep in Definition 7.1. Specifically, we have

$\displaystyle\mathcal{M}_{K,H,2}=\sum_{k=1}^{K}\sum_{h=1}^{H}(D_{k,h,1}+D_{k,h,2}),$

where

$\displaystyle
D_{k,h,1}=\left(\mathbb{J}_{k,h}(Q_{h}^{k}-Q_{h}^{\pi^{k}})\right)(s_{h}^{k})-(Q_{h}^{k}-Q_{h}^{\pi^{k}})(s_{h}^{k},a_{h}^{k})$
$\displaystyle
D_{k,h,2}=\mathbb{P}_{h}[V_{h+1}^{k}-V_{h}^{\pi^{k}}](s_{h}^{k},a_{h}^{k})-[V_{h+1}^{k}-V_{h}^{\pi^{k}}](s_{h+1}^{k}),$

and $(\mathbb{J}_{k,h}f)(x):=\langle f(x,\cdot),\pi_{h}^{k}(\cdot\mid
x)\rangle$. Thus, by the boundedness of value functions and $Q$-functions
along with Azuma–Hoeffding inequality, we have $(ii)\leq
4H\sqrt{2T\log(1/\alpha)}$. The first term can be bounded by using standard
property of mirror-descent update and the fact that $\pi^{1}$ is a uniform
distribution. In particular, as in (Cai et al., 2020, Eq. C.2), we have
$(i)\leq\sqrt{2H^{3}T\log|\mathcal{A}|}$ when
$\eta=\sqrt{2\log|\mathcal{A}|/(HT)}$ in Algorithm 2. The key part is to bound
the third term. To this end, we will show that under good event
$\mathcal{E}(\alpha)$, we have for all $s,a,k,h$,

$\displaystyle
2({\Gamma}_{h,p}^{k}+{\Gamma}_{h,r}^{k})(s,a)\geq-\iota_{h}^{k}(s,a)\geq 0.$
(7)

To show this result, we first note that under $\mathcal{E}(\alpha)$, for all
$s,a,k,h$

$\displaystyle{\varphi}(s,a)^{\top}\widehat{{\theta}}_{h,r}^{k}+\phi_{h}^{k}(s,a)^{\top}\widehat{{\theta}}_{h,p}^{k}+({\Gamma}_{h,p}^{k}+{\Gamma}_{h,r}^{k})(s,a)\geq
r_{h}(s,a)+[\mathbb{P}_{h}V_{h+1}^{k}](s,a)\geq 0$

Thus, under event $\mathcal{E}(\alpha)$, we can remove the truncation at zero
in the update of $Q$ function in Algorithm 2. Thus, we have

$\displaystyle-\iota_{h}^{k}(s,a)$
$\displaystyle=Q_{h}^{k}(s,a)-(r_{h}(s,a)+[\mathbb{P}_{h}V_{h+1}^{k}](s,a))$
$\displaystyle\leq{\varphi}(s,a)^{\top}\widehat{{\theta}}_{h,r}^{k}+\phi_{h}^{k}(s,a)^{\top}\widehat{{\theta}}_{h,p}^{k}+({\Gamma}_{h,p}^{k}+{\Gamma}_{h,r}^{k})(s,a)-(r_{h}(s,a)+[\mathbb{P}_{h}V_{h+1}^{k}](s,a))$
$\displaystyle\leq 2({\Gamma}_{h,p}^{k}+{\Gamma}_{h,r}^{k})(s,a).$

Meanwhile, we have under event $\mathcal{E}(\alpha)$

$\displaystyle\iota_{h}^{k}(s,a)$ $\displaystyle=$
$\displaystyle(r_{h}(s,a)+[\mathbb{P}_{h}V_{h+1}^{k}](s,a))-Q_{h}^{k}(s,a)$
$\displaystyle=$
$\displaystyle(r_{h}(s,a)+[\mathbb{P}_{h}V_{h+1}^{k}](s,a))-\min\\{H,{\varphi}(s,a)^{\top}\widehat{{\theta}}_{h,r}^{k}+\phi_{h}^{k}(s,a)^{\top}\widehat{{\theta}}_{h,p}^{k}+({\Gamma}_{h,p}^{k}+{\Gamma}_{h,r}^{k})(s,a)\\}$
$\displaystyle=$
$\displaystyle\max\\{r_{h}(s,a)+[\mathbb{P}_{h}V_{h+1}^{k}](s,a)-H,r_{h}(s,a)+[\mathbb{P}_{h}V_{h+1}^{k}](s,a)-{\varphi}(s,a)^{\top}\widehat{{\theta}}_{h,r}^{k}-\phi_{h}^{k}(s,a)^{\top}\widehat{{\theta}}_{h,p}^{k}-({\Gamma}_{h,p}^{k}+{\Gamma}_{h,r}^{k})(s,a)\\}$
$\displaystyle\leq$ $\displaystyle 0$

Therefore, similar to the proof of Theorem 4.1, we have

$\displaystyle(iii)=O\left(\sqrt{TH^{3}}\left(\log\frac{H}{\alpha}+d\kappa_{\lambda_{\min}}\right)+\sqrt{THd\kappa_{\lambda_{\min}}}\left(\sqrt{d\lambda_{\max}}+\nu\right)\right)$

where $\kappa_{\lambda_{\min}}:=\log\left(1+KH^{2}/(\lambda_{\min})\right)$
and $\lambda_{\min}=\min\\{\lambda_{\min,p},\lambda_{\min,r}\\}$,
$\lambda_{\max}=\max\\{\lambda_{\max,p},\lambda_{\max,r}\\}$ and
$\nu=\max\\{\nu_{p},\nu_{r}\\}$.

Putting everything together, we have

$\displaystyle\mathcal{R}(T)=O\left(\sqrt{TH^{3}}\left(\log\frac{H}{\alpha}+d\kappa_{\lambda_{\min}}\right)+\sqrt{TH^{3}\log|\mathcal{A}|}+\sqrt{THd\kappa_{\lambda_{\min}}}\left(\sqrt{d\lambda_{\max}}+\nu\right)\right)$

∎

##  9 Conclusion

In this work, we took first step towards private RL algorithms with linear
function approximations. We proposed both value-based and policy-based
optimistic private RL algorithms and show that they enjoy sublinear regret in
total number of steps while guaranteeing joint differential privacy (JDP).
Moreover, these regret bounds are independent of the number of states and at
most depends logarithmically on the number of actions in the policy
optimization setting. Our established results build on a flexible procedure
that also allows us to design general private RL algorithms with different
privacy schemes under JDP and even under LDP guarantees by injecting Gaussian
noise directly to each user’s data. As discussed before, our work also opens
the door to a series of interesting future works.

##  10 Acknowledgement

The author would like to thank Sayak Ray Chowdhury for insightful discussions
and Quanquan Gu for the discussion on the concurrent work.

## References

  * 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.
  * Zhao et al. (2009) Yufan Zhao, Michael R Kosorok, and Donglin Zeng.  Reinforcement learning design for cancer clinical trials.  _Statistics in medicine_ , 28(26):3294–3315, 2009\.
  * Sharma and Kaushik (2017) Akanksha Rai Sharma and Pranav Kaushik.  Literature survey of statistical, deep and reinforcement learning in natural language processing.  In _2017 International Conference on Computing, Communication and Automation (ICCCA)_ , pages 350–354. IEEE, 2017.
  * 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.
  * 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.
  * 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.
  * 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.
  * Basu et al. (2019) Debabrota Basu, Christos Dimitrakakis, and Aristide Tossou.  Differential privacy for multi-armed bandits: What is it and what is its cost?  _arXiv preprint arXiv:1905.12298_ , 2019.
  * 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.
  * Zhou and Tan (2020) Xingyu Zhou and Jian Tan.  Local differential privacy for bayesian optimization.  _arXiv preprint arXiv:2010.06709_ , 2020.
  * Shariff and Sheffet (2018) Roshan Shariff and Or Sheffet.  Differentially private contextual linear bandits.  _arXiv preprint arXiv:1810.00068_ , 2018.
  * 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.
  * 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. (2019) Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang.  Neural policy gradient methods: Global optimality and rates of convergence.  _arXiv preprint arXiv:1909.01150_ , 2019.
  * 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. (2020) Yonathan Efroni, Lior Shani, Aviv Rosenberg, and Shie Mannor.  Optimistic policy optimization with bandit feedback.  _arXiv preprint arXiv:2002.08243_ , 2020.
  * Chowdhury and Zhou (2021) Sayak Ray Chowdhury and Xingyu Zhou.  Differentially private regret minimization in episodic markov decision processes.  _arXiv preprint arXiv:2112.10599_ , 2021.
  * 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.
  * 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.
  * 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.
  * 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.
  * 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.
  * Zhou et al. (2021a) Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari.  Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.  In _Conference on Learning Theory_ , pages 4532–4576. PMLR, 2021a.
  * He et al. (2021a) Jiafan He, Dongruo Zhou, and Quanquan Gu.  Nearly optimal regret for learning adversarial mdps with linear function approximation.  _arXiv preprint arXiv:2102.08940_ , 2021a.
  * Liao et al. (2021) Chonghua Liao, Jiafan He, and Quanquan Gu.  Locally differentially private reinforcement learning for linear mixture markov decision processes.  _arXiv preprint arXiv:2110.10133_ , 2021.
  * Luyo et al. (2021) Paul Luyo, Evrard Garcelon, Alessandro Lazaric, and Matteo Pirotta.  Differentially private exploration in reinforcement learning with linear representation.  _arXiv preprint arXiv:2112.01585_ , 2021.
  * Ayoub et al. (2020) Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang.  Model-based reinforcement learning with value-targeted regression.  In _International Conference on Machine Learning_ , pages 463–474. PMLR, 2020.
  * Zhou et al. (2021b) Dongruo Zhou, Jiafan He, and Quanquan Gu.  Provably efficient reinforcement learning for discounted mdps with feature mapping.  In _International Conference on Machine Learning_ , pages 12793–12802. PMLR, 2021b.
  * Jia et al. (2020) Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang.  Model-based reinforcement learning with value-targeted regression.  In _Learning for Dynamics and Control_ , pages 666–686. PMLR, 2020\.
  * He et al. (2021b) Jiafan He, Dongruo Zhou, and Quanquan Gu.  Logarithmic regret for reinforcement learning with linear function approximation.  In _International Conference on Machine Learning_ , pages 4171–4180. PMLR, 2021b.
  * Ding et al. (2021) Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo Jovanovic.  Provably efficient safe exploration via primal-dual policy optimization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3304–3312. PMLR, 2021.
  * Jin et al. (2020) Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  In _Conference on Learning Theory_ , pages 2137–2143, 2020.
  * Yang and Wang (2019) Lin Yang and Mengdi Wang.  Sample-optimal parametric q-learning using linearly additive features.  In _International Conference on Machine Learning_ , pages 6995–7004. PMLR, 2019.
  * Dwork et al. (2014) Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  2014\.
  * 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.
  * 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.
  * 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.
  * Abbasi-Yadkori et al. (2011) Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  _Advances in neural information processing systems_ , 24:2312–2320, 2011.
  * Boyan (1999) Justin A Boyan.  Least-squares temporal difference learning.  In _ICML_ , pages 49–56, 1999.
  * Bradtke and Barto (1996) Steven J Bradtke and Andrew G Barto.  Linear least-squares algorithms for temporal difference learning.  _Machine learning_ , 22(1):33–57, 1996.
  * Chan et al. (2011) T-H Hubert Chan, Elaine Shi, and Dawn Song.  Private and continual release of statistics.  _ACM Transactions on Information and System Security (TISSEC)_ , 14(3):1–24, 2011.
  * Bun and Steinke (2016) Mark Bun and Thomas Steinke.  Concentrated differential privacy: Simplifications, extensions, and lower bounds.  In _Theory of Cryptography Conference_ , pages 635–658. Springer, 2016.
  * Lattimore et al. (2020) Tor Lattimore, Csaba Szepesvari, and Gellert Weisz.  Learning with good feature representations in bandits and in rl with a generative model.  In _International Conference on Machine Learning_ , pages 5662–5670. PMLR, 2020.
  * Yang et al. (2020) Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I Jordan.  On function approximation in reinforcement learning: Optimism in the face of large state spaces.  _arXiv preprint arXiv:2011.04622_ , 2020.
  * Mutnỳ and Krause (2019) Mojmír Mutnỳ and Andreas Krause.  Efficient high dimensional bayesian optimization with additivity and quadrature fourier features.  _Advances in Neural Information Processing Systems 31_ , pages 9005–9016, 2019.
  * Calandriello et al. (2019) Daniele Calandriello, Luigi Carratino, Alessandro Lazaric, Michal Valko, and Lorenzo Rosasco.  Gaussian process optimization with adaptive sketching: Scalable and no regret.  In _Conference on Learning Theory_ , pages 533–557. PMLR, 2019.
  * Cheu et al. (2019) Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev.  Distributed differential privacy via shuffling.  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , pages 375–403. Springer, 2019.
  * Vershynin (2010) Roman Vershynin.  Introduction to the non-asymptotic analysis of random matrices.  _arXiv preprint arXiv:1011.3027_ , 2010.
  * Ledoux (2001) Michel Ledoux.  _The concentration of measure phenomenon_.  Number 89. American Mathematical Soc., 2001.
  * Laurent and Massart (2000) Beatrice Laurent and Pascal Massart.  Adaptive estimation of a quadratic functional by model selection.  _Annals of Statistics_ , pages 1302–1338, 2000.

##  Appendix A Proof of Lemma 3.1

###### Proof.

Fix $h\in[H]$. Define $X_{h,p}^{k}\in\mathbb{R}^{(k-1)\times d_{1}}$ to be a
matrix whose $j$-th row is $(\phi_{h}^{j}(s_{h}^{j},a_{h}^{j}))^{\top}$, and a
‘noise’ column vector $\eta_{h,p}^{k}$ whose $j$-th row is
$V_{h+1}^{j}(s_{h+1}^{j})-\langle\phi_{h}^{j}(s_{h}^{j},a_{h}^{j}),{\theta}_{h,p}\rangle$.
Then, we have for any $k\geq 1$,

$\displaystyle{\theta}_{h,p}-\widehat{{\theta}}_{h,p}^{k}$ $\displaystyle=$
$\displaystyle{\theta}_{h,p}-[\Lambda_{h,p}^{k}]^{-1}u_{h,p}^{k}$
$\displaystyle=$
$\displaystyle{\theta}_{h,p}-[\Lambda_{h,p}^{k}]^{-1}\left((X_{h,p}^{k})^{\top}X_{h,p}^{k}{\theta}_{h,p}+(X_{h,p}^{k})^{\top}\eta_{h,p}^{k}+z_{h,p}^{k}\right)$
$\displaystyle=$
$\displaystyle{\theta}_{h,p}-[\Lambda_{h,p}^{k}]^{-1}\left(\Lambda_{h,p}^{k}{\theta}_{h,p}-Z_{h,p}^{k}{\theta}_{h,p}+(X_{h,p}^{k})^{\top}\eta_{h,p}^{k}+z_{h,p}^{k}\right)$
$\displaystyle=$
$\displaystyle[\Lambda_{h,p}^{k}]^{-1}\left(Z_{h,p}^{k}{\theta}_{h,p}-(X_{h,p}^{k})^{\top}\eta_{h,p}^{k}-z_{h,p}^{k}\right).$

Therefore, we have

$\displaystyle\left\lVert{\theta}_{h,p}-\widehat{{\theta}}_{h,p}^{k}\right\rVert_{\Lambda_{h,p}^{k}}$
$\displaystyle=\left\lVert
Z_{h,p}^{k}{\theta}_{h,p}-(X_{h,p}^{k})^{\top}\eta_{h,p}^{k}-z_{h,p}^{k}\right\rVert_{[\Lambda_{h,p}^{k}]^{-1}}$
$\displaystyle\mathop{\leq}\limits^{(a)}\left\lVert(X_{h,p}^{k})^{\top}\eta_{h,p}^{k}\right\rVert_{[\Lambda_{h,p}^{k}]^{-1}}+\left\lVert
Z_{h,p}^{k}{\theta}_{h,p}\right\rVert_{[\Lambda_{h,p}^{k}]^{-1}}+\left\lVert
z_{h,p}^{k}\right\rVert_{[\Lambda_{h,p}^{k}]^{-1}}$
$\displaystyle\mathop{\leq}\limits^{(b)}\left\lVert(X_{h,p}^{k})^{\top}\eta_{h,p}^{k}\right\rVert_{[\Lambda_{h,p}^{k}]^{-1}}+\left\lVert
Z_{h,p}^{k}{\theta}_{h,p}\right\rVert_{[Z_{h,p}^{k}]^{-1}}+\left\lVert
z_{h,p}^{k}\right\rVert_{[Z_{h,p}^{k}]^{-1}}$
$\displaystyle=\underbrace{\left\lVert(X_{h,p}^{k})^{\top}\eta_{h,p}^{k}\right\rVert_{[\Lambda_{h,p}^{k}]^{-1}}}_{\mathcal{B}_{1,p}}+\underbrace{\left\lVert{\theta}_{h,p}\right\rVert_{Z_{h,p}^{k}}+\left\lVert
z_{h,p}^{k}\right\rVert_{[Z_{h,p}^{k}]^{-1}}}_{\mathcal{B}_{2,p}},$

where (a) follows from triangle inequality; (b) holds by
${\Lambda}_{h,p}^{k}\succeq Z_{h,p}^{k}$.

By the same argument, we have

$\displaystyle\left\lVert{\theta}_{h,r}-\widehat{{\theta}}_{h,r}^{k}\right\rVert_{\Lambda_{h,r}^{k}}\leq\underbrace{\left\lVert(X_{h,r}^{k})^{\top}\eta_{h,r}^{k}\right\rVert_{[\Lambda_{h,r}^{k}]^{-1}}}_{\mathcal{B}_{1,r}}+\underbrace{\left\lVert{\theta}_{h,r}\right\rVert_{Z_{h,r}^{k}}+\left\lVert
z_{h,r}^{k}\right\rVert_{[Z_{h,r}^{k}]^{-1}}}_{\mathcal{B}_{2,r}},$

where $X_{h,r}^{k}\in\mathbb{R}^{(k-1)\times d_{2}}$ is a matrix whose rows
are
$({\varphi}(s_{h}^{1},a_{h}^{1}))^{\top},\ldots,({\varphi}(s_{h}^{k-1},a_{h}^{k-1}))^{\top}$
and $\eta_{h,r}^{k}$ is a ‘noise’ column vector whose $j$-th row is
$r_{h}^{j}(s_{h}^{j},a_{h}^{j})-r_{h}(s_{h}^{j},a_{h}^{j})$.

Now, by Assumption 2, we have for any $\alpha\in(0,1]$, with probability at
least $1-\alpha$, for all $k\in[K]$ and all $h\in[H]$

$\displaystyle\mathcal{B}_{1,p}\leq\left\lVert(X_{h,p}^{k})^{\top}\eta_{h,p}^{k}\right\rVert_{[G_{h,p}^{k}+\lambda_{\min,p}]^{-1}}\quad\text{and}\quad\mathcal{B}_{1,r}\leq\left\lVert(X_{h,r}^{k})^{\top}\eta_{h,r}^{k}\right\rVert_{[G_{h,r}^{k}+\lambda_{\min,r}]^{-1}}$
$\displaystyle\mathcal{B}_{2,p}\leq\sqrt{d_{1}\lambda_{\max,p}}+\nu_{p}\quad\text{and}\quad\mathcal{B}_{2,r}\leq\sqrt{d_{2}\lambda_{\max,r}}+\nu_{r},$

where $G_{h,p}^{k}:=(X_{h,p}^{k})^{\top}(X_{h,p}^{k})$ and
$G_{h,r}^{k}:=(X_{h,r}^{k})^{\top}(X_{h,r}^{k})$. Moreover, we also used the
assumption in Definition 1 that
$\left\lVert\theta_{h,p}\right\rVert\leq\sqrt{d_{1}}$ and
$\left\lVert\theta_{h,r}\right\rVert\leq\sqrt{d_{2}}$.

We are only left with two noise terms, which can be bounded by the standard
self-normalized inequality (cf. (Abbasi-Yadkori et al., 2011, Theorem 1)). In
particular, first note that $j$-th element of the ‘noise’ vector
$\eta_{h,p}^{j}$ is
$V_{h+1}^{j}(s_{h+1}^{j})-\langle\phi_{h}^{j}(s_{h}^{j},a_{h}^{j}),{\theta}_{h,p}\rangle=V_{h+1}^{j}(s_{h+1}^{j})-\mathbb{E}_{s^{\prime}\sim\mathbb{P}(\cdot\mid
s_{h}^{j},a_{h}^{j})}V_{h+1}^{j}(s^{\prime})$, which holds by the linear
kernel MDP model in Assumption 1. Note that, conditioning on
$\mathcal{F}_{j,h,1}$, $\eta_{h,p}^{j}$ is a zero-mean random variable. This
holds by the fact that conditioning on $\mathcal{F}_{j,h,1}$, the only
randomness comes from $s_{h+1}^{j}$. Moreover, since $V_{h+1}^{j}\in[0,H]$,
conditioning on $\mathcal{F}_{j,h,1}$, $\eta_{h,p}^{j}$ is an $H/2$-sub-
Gaussian random variable. Also, $\eta_{h,p}^{j}$ is $\mathcal{F}_{j,h,2}$
measurable and $\phi_{h}^{j}(s_{h}^{j},a_{h}^{j})$ is $\mathcal{F}_{j,h,1}$
measurable by Definition 7.1. Similarly, we can see that the noise
$\eta_{h,r}^{j}$ is a $1/2$-sub-Gaussian random variable conditioning on
$\mathcal{F}_{j,h-1,2}$ as $\pi^{j}$ is measurable with respect to
$\mathcal{F}_{j,h,1}$ and hence conditioning on $\mathcal{F}_{j,h-1,2}$, the
only randomness comes from the reward realization
$r_{h}^{j}(s_{h}^{j},a_{h}^{j})\in[0,1]$. Moreover, $\eta_{h,r}^{j}$ is
$\mathcal{F}_{j,h,1}$ measurable and ${\varphi}(s_{h}^{j},a_{h}^{j})$ is
$\mathcal{F}_{j,h-1,2}$ measurable. With such choices of filtrations, one can
now apply standard self-normalized inequality to obtain that for any fixed
$\alpha\in(0,1]$, with probability at least $1-3\alpha$, for all $k\in[K]$ and
$h\in[H]$

$\displaystyle\mathcal{B}_{1,p}\leq\frac{H}{2}\sqrt{2\log\left(\frac{H}{\alpha}\right)+\log\frac{\det({G}_{h,p}^{k}+\lambda_{\min,p}I)}{\det(\lambda_{\min,p}I)}}$

and

$\displaystyle\mathcal{B}_{1,r}\leq\frac{1}{2}\sqrt{2\log\left(\frac{H}{\alpha}\right)+\log\frac{\det({G}_{h,r}^{k}+\lambda_{\min,r}I)}{\det(\lambda_{\min,r}I)}}.$

Then, we can further bound the two terms by using the trace-determinant lemma
(cf. (Abbasi-Yadkori et al., 2011, Lemma 11)) and the boundedness assumptions
in Assumption 1, that is, for all all $h\in[H]$ and $k\in[K]$,
$\left\lVert\phi_{h}^{k}(s_{h}^{k},a_{h}^{k})\right\rVert\leq\sqrt{d_{1}}H$
and $\left\lVert{\varphi}(s_{h}^{k},a_{h}^{k})\right\rVert\leq 1$. In
particular, we obtain that with probability at least $1-3\alpha$, for all
$k\in[K]$ and $h\in[H]$

$\displaystyle\mathcal{B}_{1,p}\leq\frac{H}{2}\sqrt{2\log\left(\frac{H}{\alpha}\right)+d_{1}\log\left(1+\frac{KH^{2}}{\lambda_{\min,p}}\right)}$

and

$\displaystyle\mathcal{B}_{1,r}\leq\frac{1}{2}\sqrt{2\log\left(\frac{H}{\alpha}\right)+d_{2}\log\left(1+\frac{K}{d_{2}\lambda_{\min,r}}\right)}.$

Finally, putting everything together, we have for any fixed $\alpha\in(0,1]$,
with probability at least $1-3\alpha$ for all $k\in[K]$ and $h\in[H]$,

$\displaystyle\left\lVert{\theta}_{h,p}-\widehat{{\theta}}_{h,p}^{k}\right\rVert_{\Lambda_{h,p}^{k}}\leq\frac{H}{2}\sqrt{2\log\left(\frac{H}{\alpha}\right)+d_{1}\log\left(1+\frac{KH^{2}}{\lambda_{\min,p}}\right)}+\sqrt{d_{1}\lambda_{\max,p}}+\nu_{p}$

and

$\displaystyle\left\lVert{\theta}_{h,r}-\widehat{{\theta}}_{h,r}^{k}\right\rVert_{\Lambda_{h,r}^{k}}\leq\frac{1}{2}\sqrt{2\log\left(\frac{H}{\alpha}\right)+d_{2}\log\left(1+\frac{K}{d_{2}\lambda_{\min,r}}\right)}+\sqrt{d_{2}\lambda_{\max,r}}+\nu_{r}.$

∎

##  Appendix B Useful Lemmas

The following lemmas are the key components to prove Theorem 6.5.

######  Lemma B.1 (Slepian’s inequality; Lemma 5.33 in Vershynin (2010)).

Consider two Gaussian processes $(X_{t})_{t\in T}$ and $(Y_{t})_{t\in T}$
whose increments satisfy the inequality
$\mathbb{E}\left[|X_{s}-X_{t}|^{2}\right]\leq\mathbb{E}\left[|Y_{s}-Y_{t}|^{2}\right]$
for all $s,t\in T$, then, $\mathbb{E}\left[\sup_{t\in
T}X_{t}\right]\leq\mathbb{E}\left[\sup_{t\in T}Y_{t}\right]$.

######  Lemma B.2 (Concentration in the Gauss space).

Let $f$ be a real valued $1$-Lipschitz function on $\mathbb{R}^{n}$. Let $X$
be a Gaussian random vector in $\mathbb{R}^{n}$ whose entries $X_{i}$ is
$i.i.d$ $\mathcal{N}(0,\sigma^{2})$. Then, for every $t\geq 0$,

$\displaystyle\mathbb{P}\left\\{f(X)-\mathbb{E}\left[f(X)\right]\geq
t\right\\}\leq\exp\left(-\frac{t^{2}}{2\sigma^{2}}\right)$

###### Proof.

This result directly follows from Proposition 2.18 in Ledoux (2001) by
considering $\gamma$ as the Gaussian measure on $\mathbb{R}^{n}$ with density
of a multivariate normal distribution, i.e., $\mathcal{N}{(0,\sigma^{2}I)}$
and hence $c$ in Proposition 2.18 of Ledoux (2001) is equal to
$\frac{1}{\sigma^{2}}$. ∎

######  Lemma B.3 (Operator norm of Gaussian random matrices).

Let $A$ be an $m\times n$ random matrix whose entries $A_{ij}$ are $i.i.d$
Gaussian random variables $\mathcal{N}(0,\sigma^{2})$. Then, for any $t>0$, we
have

$\displaystyle\mathbb{P}\\{\left\lVert
A\right\rVert\geq\sigma(\sqrt{n}+\sqrt{m})+t\\}\leq\exp\left(-\frac{t^{2}}{2\sigma^{2}}\right).$

###### Proof.

We will first show that

$\displaystyle\mathbb{E}\left[\left\lVert
A\right\rVert\right]\leq\sigma(\sqrt{m}+\sqrt{n})$

by using Lemma B.1. To this end, note that the operator norm of $A$ can be
computed as follows.

$\displaystyle\left\lVert A\right\rVert=\max_{u\in S^{n-1},v\in
S^{m-1}}\langle Au,v\rangle.$

where $S^{n-1}$ and $s^{m-1}$ are unit spheres. Thus, $\left\lVert
A\right\rVert$ can be regarded as the supremum of the Gaussian process
$X_{u,v}:=\langle Au,v\rangle$ indexed by the pair of vectors $(u,v)\in
S^{n-1}\times S^{m-1}$. Let us define $Y_{u,v}:=\langle g,u\rangle+\langle
h,v\rangle$ where $g\in\mathbb{R}^{n}$ and $h\in\mathbb{R}^{m}$ are
independent Gaussian random vectors whose entries are $i.i.d$ Gaussian random
variables $\mathcal{N}(0,\sigma^{2})$. Now, we compare the increments of these
two Gaussian processes for every $(u,v),(u^{\prime},v^{\prime})\in
S^{n-1}\times S^{m-1}$.

$\displaystyle\mathbb{E}\left[|X_{u,v}-X_{u^{\prime},v^{\prime}}|^{2}\right]$
$\displaystyle=\sigma^{2}\sum_{i=1}^{n}\sum_{j=1}^{m}|u_{i}v_{j}-u^{\prime}_{i}v^{\prime}_{j}|^{2}$
$\displaystyle=\sigma^{2}\left\lVert uv^{T}-u^{\prime}v^{\prime
T}\right\rVert_{F}^{2}$
$\displaystyle=\sigma^{2}\left\lVert(u-u^{\prime})v^{T}+u^{\prime}(v-v^{\prime})^{T}\right\rVert_{F}^{2}$
$\displaystyle=\sigma^{2}\left(\left\lVert
u-u^{\prime}\right\rVert_{2}^{2}+\left\lVert
v-v^{\prime}\right\rVert_{2}^{2}\right)$
$\displaystyle\quad+2\sigma^{2}\text{trace}\left(v(u-u^{\prime})^{T}u^{\prime}(v-v^{\prime})^{T}\right)$
$\displaystyle=\sigma^{2}\left(\left\lVert
u-u^{\prime}\right\rVert_{2}^{2}+\left\lVert
v-v^{\prime}\right\rVert_{2}^{2}+2(u^{T}u^{\prime}-1)(1-v^{T}v^{\prime})\right)$
$\displaystyle\leq\sigma^{2}\left(\left\lVert
u-u^{\prime}\right\rVert_{2}^{2}+\left\lVert
v-v^{\prime}\right\rVert_{2}^{2}\right)$
$\displaystyle=\mathbb{E}\left[|Y_{u,v}-Y_{u^{\prime},v^{\prime}}|^{2}\right].$

Therefore, Lemma B.1 applies here, and hence

$\displaystyle\mathbb{E}\left[\left\lVert A\right\rVert\right]$
$\displaystyle=\mathbb{E}\left[\max_{(u,v)}{X_{u,v}}\right]\leq\mathbb{E}\left[\max_{(u,v)}{Y_{u,v}}\right]$
$\displaystyle=\mathbb{E}\left[\left\lVert
g\right\rVert_{2}\right]+\mathbb{E}\left[\left\lVert
h\right\rVert_{2}\right]\leq\sigma(\sqrt{m}+\sqrt{n}).$

Finally, note that $\left\lVert A\right\rVert$ is a $1$-Lipschitz function of
$A$ when considered as a vector in $\mathbb{R}^{mn}$. Then, consider the
function $f$ in Lemma B.2 as the operator norm, we directly obtain the result.
∎

######  Lemma B.4 (Operator norm of symmetric Gaussian random matrices).

Let $A$ be an $n\times n$ random symmetric matrix whose entries $A_{ij}$ on
and above the diagonal are $i.i.d$ Gaussian random variables
$\mathcal{N}(0,\sigma^{2})$. Then, for any $t>0$, we have

$\displaystyle\left\lVert A\right\rVert\leq 4\sigma\sqrt{n}+2t,$

with probability at least $1-2\exp(-\frac{t^{2}}{2\sigma^{2}})$.

###### Proof.

Decompose the matrix $A$ into the upper triangular matrix $A^{+}$ and the
lower triangular matrix $A^{-}$ such that $A=A^{+}+A^{-}$. Note that without
loss of generality, the entries on the diagonal are in $A^{+}$. Then, apply
Lemma B.3 to both $A^{+}$ and $A^{-}$, and by a union bound, we have that the
following inequalities hold simultaneously

$\displaystyle\left\lVert A^{+}\right\rVert\leq
2\sigma\sqrt{n}+t\quad\text{and}\quad\left\lVert A^{-}\right\rVert\leq
2\sigma\sqrt{n}+t$

with probability at least $1-2\exp(-\frac{t^{2}}{2\sigma^{2}})$ for any $t>0$.
Finally, by triangle inequality $\left\lVert A\right\rVert\leq\left\lVert
A^{+}\right\rVert+\left\lVert A^{-}\right\rVert$, we prove the result. ∎

######  Lemma B.5 (Concentration of chi-square; Corollary to Lemma 1 of
Laurent and Massart (2000)).

Let $U$ be a $\chi^{2}$ statistic with $D$ degrees of freedom. Then, for any
positive $x$,

$\displaystyle\mathbb{P}\left\\{U\geq D+2\sqrt{Dx}+2x\right\\}\leq\exp(-x).$