Local Differential Privacy for Regret Minimization in Reinforcement Learning
Authors: Evrard Garcelon
Vianney Perchet
Ciara Pike-Burke
Matteo Pirotta
Venue: NeurIPS 2021 Poster (2021)
Keywords: Regret
Optimism
Local Differential Privacy
Theory RL

Abstract: Reinforcement learning algorithms are widely used in domains where it is desirable to provide a personalized service. In these domains it is common that user data contains sensitive information that needs to be protected from third parties. Motivated by this, we study privacy in the context of finite-horizon Markov Decision Processes (MDPs) by requiring information to be obfuscated on the user side. We formulate this notion of privacy for RL by leveraging the local differential privacy (LDP) framework. We establish a lower bound for regret minimization in finite-horizon MDPs with LDP guarantees which shows that guaranteeing privacy has a multiplicative effect on the regret. This result shows that while LDP is an appealing notion of privacy, it makes the learning problem significantly more complex. Finally, we present an optimistic algorithm that simultaneously satisfies $\varepsilon$-LDP requirements, and achieves $\sqrt{K}/\varepsilon$ regret in any finite-horizon MDP after $K$ episodes,  matching the lower bound dependency on the number of episodes $K$.

Local Differential Privacy for Regret Minimization in Reinforcement Learning
Evrard Garcelon
Vianney Perchet
Facebook Al Research & CREST, ENSAE Paris, France evrard@fb.co com
CREST, ENSAE Paris & Criteo Al Lab Palaiseau, France,
vianney@ensae.ff
Ciara Pike-Burke
Matteo Pirotta
Imperial College London London, United Kingdom
Facebook AI Research
Paris, France
c. pikeburke@gmail.ccmmmm com
matteo matteo. www..ptttoottaaa...... com
Abstract
Reinforcement learning algorithms are widely used in domains where it desirable provide personalized service. In these domains it is common that user data contains sensitive information that needs to be protected from third parties. Moti- vated by this, study privacy in the context of finite-horizon Markov Decision Processes (MDPs) by requiring information to be obfuscated on the user side. We formulate this notion of privacy for RL by leveraging the local differential privacy (LDP) framework. We establish a lower bound for regret minimization in fmite-horizonn MDPs with LDP guarantees which shows that guaranteeing privacy has multiplicative effect on the regret. This result shows that while LDP is an appealing notion of privacy, it makes the learning problem significantly more complex. Finally, we present an optimistic algorithm that simultancously satisfies
e-LDP requirements, and achieves /K/e regret in any episodes, matching the lower bound dependency on the number of episodes K.
MDP after
1 Introduction
The practical successes of Reinforcement Learning (RL) algorithms have led to them becoming ubiquitous in many settings such as digital marketing, healthcare and finance, where it desirable to provide a personalized service [e.g.. 1, 2]. However, users are becoming increasingly wary of the amount of personal information that these services require. This particularly pertinent in many of the aforementioned domains where the data obtained by the RI. algorithm are highly sensitive. For example, healthcare, the state encodes personal information such as gender, age, vital signs, etc. In advertising, it is normal for states to include browser history, geolocalized information, etc. Unfortunately, [3] has shown that, unless sufficient precautions are taken, the RL agent leaks information about the environment (i.e., states containing sensitive information). That is to say, observing the policy computed by the RL algorithm is sufficient to infer information about the data (e.g., states and rewards) used to compute the policy (scenario D). This puts users' privacy jeopardy. Users therefore want to keep their sensitive information private, not only to an observer but also to adapting provide
the service provider itself (i.e., the RI. agent). In response, many services stronger protection of user privacy and personal data, for example by guaranteeing privacy directly the user side (scenario @2). This often means that data (i.e., trajectories of states, actions, rewards) are privatized before being observed by the RL agent. In this paper, we study the effect that this has the learning problem in RL.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Differential privacy (DP) [4] is a standard mechanism for preserving data privacy, both on the al- gorithm and the user side. The (e, 8)- definition guarantees that it is statistically hard to infer information about the data used to train model by observing its predictions, thus addressing scenario @. In online learning, (e, 5)-DP has been studied in the multi-armed bandit framework [e.g.. 5, 6]. However, [7] showed that DP is incompatible with regret minimization in the contextual bandit problems. This led to considering weaker or different notions of privacy [e.g.. 7, 8J. Recently. [9] transferred some of these techniques to RL, presenting the first private algorithm for regret mini- mization in finite-horizon problems. In [9], they considered a relaxed definition of DP called joint differential privacy (JDP) and showed that, under JDP constraints, the regret only increases by an additive term which is logarithmic in the number of episodes. Similarly to DP, in the JDP setting the privacy burden lies with the learning algorithm which directly observes user states and trajectories containing sensitive data. In particular, this means that the data itself is not private and could poten- tially be used for example by the owner of the application- train other algorithms with no privacy guarantees. An alternative and stronger definition of privacy is Local Differential Privacy (LDP) [10]. This requires that the user's data is protected at collection time before the learning agent has access to it. This covers scenario @ and implies that the learner is DP. Intuitively, in RL, LDP ensures that each sample (states and rewards associated to an user) is already private when observed by the learning agent, while JDP requires computation on the entire set of samples to be DP. Recently, [11] showed that, in contrast to DP, LDP is compatible with regret minimization in contextual bandits." LDP is thus a stronger definition of privacy, simpler to understand and more user friendly. These characteristics make LDP more suited for real-world applications. However, as we show in this paper. guaranteeing LDP in RL makes the learning problem more challenging.
Contributions. In this paper, we study LDP for regret minimization in finite horizon reinforcement learning problems with S states, A actions, and a horizon of H.² Our contributions are as follows. 1) We provide regret lower bound for (e, () 8-PL of Q(H / SAK/ min(e= - 1. 13). showing LDP is inherently harder than JDP, where the lower- is only R(HVSAK + SAH (og(KH) 2) We propose the first LDP algorithm for regret minimization in RL. We use a general privacy- preserving mechanism to perturb information associated to each trajectory and derive LDP-OBI, an optimistic model-based (e, o)-LDP algorithm with regret guarantees. 3) We present multiple privacy- Sewacy-preserving mechanisms that are compatible with LDP- and show that their regret is O(VK/E) up to some mechanism dependent terms depending on S, A, H. 4) We perform numerical simulations to evaluate the impact of LDP on the learning process. For comparison, we build a Thompson sampling algorithm [e.g.. 12] for which we provide LDP guarantees but no regret bound.
[9].
The notion of differential privacy was introduced in [4] and is now a standard in machine learning [e.g., 13, 14, 15). Several notions of DP have been studied in the literature, including the standard DP and LDP notions. While LDP is stronger definition of privacy compared to DP, recent works have highlighted that it possible to achieve a trade-off between the two settings in terms of privacy and utility. The shuffling model of privacy [16, 17, 18, 19, 20] allows to build (e, DD algorithm with an additional (e', D-DPP guarantee (for e' s2 E + In(r)). any 8 >> 0 where is the number of samples), hence it is possible to trade-off between DP, LDP, and utility in this setting. However, the scope of this paper is ensuring (s, 5)-LDP guarantees for a fixed e. In this case, shuffling will not provide an improvement in utility (error) (see Thm 5.2 in Sec. 5.1 of [17] and App. I).
Related Work.
The bandit literature has investigated different privacy notions, including DP, JDP and LDP [5, 6, 21, 22, 23, 11. 24]. In contextual bandits. [7] derived an impossibility result for learning under DP by showing a regret lower-bound ?(T) for any (c, -DD algorithm. Since the contextual bandit problem is a morte-horizon RL problem with horizon H 1, this implies that DP is incompatible with regret minimization in RL as well. Regret minimization in RL with privacy guarantees has only been considered in [9], where the authors extended the JDP approach from bandit to finite-horizon
1 'This shows that there are peculiarities in the DP definitions that are unique sequential decision-making problems such as RL. The discrepancy between DP and LDP in RL is due to the fact that, when guaranteeing DP, actions taken by the learner cannot depend on the current state (this would break the privacy guarantee). On the other hand, in the LDP setting, the user executes a policy prescribed by the learner on its end (i.e., directly on non- poi-private states) and send privatized result (sequence of states and rewards observed by executing the policy) to the learner. Hence the user can execute actions based on current state leading to sublinear regret.
We do not explicitly focus on preventing malicious attacks or securing the communication between the RL algorithm and the users. This is outside the scope of the paper.

---

RL problems. They proposed a variation of UBEV [25] using a randomized response mechanism to guarantee E-JDP with an additive cost the regret bound. While local differential privacy [10] has attracted increasing interest in the bandit literature [e.g.. 21, 23, 11, 24], it remains unexplored in the RI. literature, and we provide the first contribution in that direction. Finally, outside regret minimization, DP has been studied in off-policy evaluation [26], in control with DP guarantees on only the reward function [27], and in distributional RL [28].
2 Preliminaries
We consider a finite-horizon time-homogeneous Markov Decision Process (MDP) [29, Chp. 4] M = (S,A, p.r, H) with state space S, action space A, and horizon H E N+ Every state-action pair is characterized by a reward distribution with mean r(8, a) supported in [0. and a transition distribution p(- a) over next state. We denote by S |8] and A ||A] the number of states and actions. A non-stationary Markovian deterministic (MD) policy is defined as collection π - (T (m , of MD policies Th S + A. For any [M] = {1..... H and state 8 S, defined QT r(s, a) + E,, E r(s;, a.) and (s) = Q" (s. (8)). There exists optimal Markovian and deterministic policy x² [29, Sec. 4.4] such that (s) = Vg (s) max, (s). The Bellman equations at stage h E [H] are defined as Q% a) = ( a) + max,' Ex'sp, [V (s')] The value iteration algorithm (a.k.a. backward induction) computes Q* by applying the Bellman equations starting from stage H down to 1. with + (s) = 0 for any The optimal policy is simply the greedy policy: o (s) = arg max, Q7 (s, a). By boundness of the reward, all value functions V7, are bounded in [0, H h + 1] for any h and s.
the value functions of a policy
The general interaction protocol. The learning agent (e.g., a personalization service) interacts with an unknown MDP with multiple users in sequence of episodes & E [K] of fixed length H. At each episode k, an user u, arrives and their personal information (e.g., location, gender, health status, etc.) is encoded by the state si.k. The learner selects a policy ग. that is sent to the user ug for local execution on "clear" states. The outcome of the execution, i.e., a trajectory, X2 = (SkA, akh, rkh,, 8k, ( is sent to the learner to update the policy. Note that we have not yet explicitly taken into consideration privacy in here. We evaluate the performance of a learning algorithm 2 which plays policies π ,,,..., Th by its cumulative regret after K episodes
K
A(K) = (Vr((1 - (s1x))
(1)
k=
2.1 Local Differential Privacy in RL
In many application settings, when modelling decision problem finite horizon MDP, it is natural to view each episode k E [K] as a trajectory associated to a specific user. In this paper, we assume that the sensitive information is contained in the states and rewards of the trajectory. Those quantities need to be kept private. This is reasonable in many settings such as healthcare, advertising, and finance, where states encode personal information, such location, health, income etc. For example, an investment service may aim to provide each user with investment suggestions tailored to their income, deposit amount, age, risk level, properties owned, etc. This information is encoded in the user state and evolves over time as a consequence of investment decisions. The service provides guidances in the form of a policy (e.g., where, when and how much invest) and the user follows the strategy for a certain amount of time. After that and based on the newly acquired information the provider may decide change the policy. However, the user may want to keep their personal and sensitive information private to the company, while still receiving personalised and meaningful service. This poses a fundamental challenge since in many cases, this information about actions taken in each state is essential for learning and creating personalized experience for the user. The goal of a private RL. algorithm is thus to ensure that the sensitive information remains private, while preserving the learnability of the problem.
Privacy in RL has been tackled in [9] through the lens of joint differential privacy (JDP). Intuitively, JDP requires that when a user changes, the actions observed by the other K - 1 users will not
'e can simply modify the algorithm to handle step dependent transitions and rewards. The regret then multiplied by factor H / H.
3

---

change much [9]. The privacy burden thus lies with the RL algorithm. The algorithm has access to all the information about the users (i.e., trajectories) containing sensitive data. then has to provide guarantees about the privacy of the data and carefully select the policies to execute in order to guarantee JDP. This approach to privacy requires the user to trust the RI. algorithm to privately handle the data and not to expose or share sensitive information, and does not cover the examples mentioned above.
In contrast to prior work, in this paper, we consider local differential privacy (LDP) in RL. This removes the requirement that the RL algorithm observes the true sensitive data, achieving stronger privacy guarantees. LDP requires that an algorithm has access to user information (trajectories in RL) only through samples that have been privatized before being passed to the learning agent. This is different to JDP or DP where the trajectories are directly fed to the RL agent. In LDP, information is secured locally by the user using a private randomizer M, before being sent to the RI. agent. The appeal of this local model is that privatization can be done locally on the user-side. Since nobody other than the user has ever access to any piece of non private data, this local setting is far more private. There are several variations of LDP available in the literature. In this paper, we focus on the non-interactive setting. We argue that this is more appropriate for RL. Indeed, due to the RL interaction framework, the data generated by user k is a function of the data of all users < k, therefore the data are not i...d. and the standard definition of sequential interactivity for LDP (Eq. 1 in [10]) is not applicable. It is therefore more natural to study the con-interective setting (Eq. 2 in [10)) in RL. We formally define this below.
Following the definition in [9], user u is characterized by starting state distribution Ao,,. (i.e., for user u, 81 ~ po... and a tree of depth H, describing all the possible sequence of states and rewards corresponding to all possible sequences of actions. Alg. describes the LDP private interaction protocol between K unique users {uI,..., 3K} C UR with U the set of all users, and an RL algorithm 21 For any k E [K]. let 81,k pa,ux be the initial state for user uy and denote by [ E X.,, the trajectory corresponding to user un executing a
Xn,, = (SK.A, AR,A, Tk.A) | policy TT- We write M(X... u.) to denote the privatized data generated by the randomizer for user uk- The goal of mechanism M is to privatize sensitive informations while encoding sufficient information for learning. With these notions in mind, LDP in RL can be defined follows:
Definition 1. For any e 2 O and 8 2 O, a privacy preserving mechanism M is said to be (e, 8)- Locally Differential Private (LDP) if and only if for all users u, u' U, trajectories (Xu, Xwr
Nu x Xy and all O C (M(X.) u E U):
(MM(X.) E 0) < e (M((x.) +0+
(2)
where Xy is the space of trajectories associated to user u.
Def. 1 ensures that if the RI. algorithm observes the output of the privacy mechanism M for two different input trajectories, then it is statistically difficult to guess which output is from which input trajectory. As a consequence, the users' privacy is preserved.
3 Lower Bound
We provide lower bound the regret that any LDP RL algorithm must ineur. For this, as is standard when proving lower bounds on the regret in RL. [e.g.. 30, 31], we construct a hard instance of the problem. The proof (see App. B) relies on the fact that LDP acts Lipschitz function, with respect to the KL-divergence, in the space of probability distribution.
Theorem Bownd..Bound). For any algorithm X associated
e-LDP mechanism, any number of states S 2 3, actions A 2 2 and H 2 2 A - 2) + 2, there exists an MDP M with S states and A actions such that: E (A(K) 2 min (exp(e)
HVSAK
The lower bound of Thm. 2 shows that the price pay for LDP in the RL setting is factor 1 1/(exp(e) 1) compared to the non-private lower bound of H HVKA.. The regret lower bound scales multiplicatively with the privacy parameter e. The recent work of [9] shows that for JDP, the regret in finite-horizon MDPs is lower-hounded by S (HVSAK + + Thm. shows that the local differential privacy setting is inherently harder than the joint differential privacy one for small e, as our lower-bound scales with / K when 83 0. Both bounds scale with VK K when +00.

---

Algorithm/ Locally Private Episodic RL
Algorithm 2 L.DP-OBI (M)
Input: Agent: 21, Local Randomizer: M, Users:
Input: 8 E (0.1), a > 1. randomizer M with paramcters (fo, du)
u1......4 UKK
for k 1 to K do
for l: = to K do
Agent 21 computes TA using (M(X.,,) heik-1]
Computc Pk and Pk in Eq. (4) using (MM(X,))IE(K-X PE and S as in Prop. us-
User un receives me from agent 2 and observes
$1, ~ Pa,e,
ing (cu, 6u; 2x zz==z) ):, and by.
User Up executes policy Tee on "non-private" states and observes a trajectory X k, ah,k, hh,,))
Compute ITA as Eq. (5) and send it to user ue User uy executes policy Th, collects trajectory Xx and sends back privatized value M(Xx) end for
User us sends back private data M(X
end for
Exploration with Local Differential Privacy
A standard approach to the design of the private randomizer M is to inject noise into the data to be preserved [14]. A key challenge in RL is that we cannot simply inject noise to each component the trajectory since this will break the temporal consistency of the trajectory and possibly prevent learning. In fact, a trajectory not an arbitrary sequence of states, actions, and rewards but obeys the Markov reward process induced by policy. Fortunately, Def. 1 shows that the output of the randomizer need not necessarily be a trajectory but could be any private information built from it. In the next section, show how to leverage this key feature to output succinct information that preserves the information encoded in a trajectory while satisfying the privacy constraints. We show that the output of such randomizer can be used by an RI. algorithm to build estimates of the unknown rewards and transitions. While these estimates are biased, we show that they carry enough information to derive optimistic policies for exploration. We leverage these tools to design LDP-OBI, optimistic model-based algorithm for exploration with LDP guarantees.
4.1 Privacy-Preserving Mechanism
Consider the locally-private episodic RL protocol described in Alg. 1. At the end of each episode E [K]. user 02 uses a private randomizer M to generate a private statistic MM(X.,) to pass the RL algorithm 2. This statistic should encode sufficient information for the RL algorithm to improve the policy while maintaining the user's privacy. model-basee settings, a sufficient statistic is a local estimate of the rewards and transitions. Since this cannot be reliably obtained from a single trajectory, we resort to counters of visits and rewards that can be aggregated by the RL algorithm.
For given trajectory X {(sh, ah, ra)me(HH let (x, = E rh (ar=saa (s, Σ (s,==sa,,=a) and No (s) Ein H--1 (oa==s,,,aass4411
be the true non non-private statistics, which the agent will never observe. We design the mechanism M so that for a given trajectory X, M returns private versions M(X) = (Rx, No, Ng of these statistics. Here, Rx(s, a) is noisy version of the cumulative reward Rx (s, a), and Ny and No perturbed counters of visits to state-action and itateaaction-nex state tuples, respectively. At the beginning of episode k, the algorithm has access to the aggregated private statistics:
as)
Rx.,, (s, as) Σ N Nxx (s, (E(s, = ΣNx,, (s, (3) Icc
1sk
1ek
We denote the non-private counterparts these aggregated statistics as Ru Eier Rx., (s, a). NY (8, a) = Σiek N (s,a) and (T(s a, 8') = Σiek No, (s, a, s'), these are also unknown to the RL agent. Using these private statistics, we can define conditions that private randomizer must satisfy in order for our RL agent, LDP-OBI, to be able to learn the reward and dynamics of the MDP.
Assumption 3. The private randomizer M satisfies (Eo, bDD-L Def. 1, with En, 8n 2 O. Moreover, for any 8 > and k. 2 O. there exist four finite strictly positive function, C (Eo, 80, 8), ck 2E0, do, 8), cx.a(Eo, do 8), Ca ( 20, 8) E Ri, such that with probabilty at least
5

---

1 1- 8 for all (s) E x A:
Rx( - (x) S (,,,
[g(s, - - a) s cx.2(60. 60.
N a S CR.alEn, 60. 6),
Ng(s,,, Ng( a')) I cn. 60,0)
The functions cs.1(5o, og, 8), cr,2(50, 6o, 8), Ch (E0, do. and ca,a do, 8) must be increasing functions of k and decreasing functions of 8. We also write (x,1 0), cx,2(50, 8), ck,s 6) and Ck, 8) when dg- = O.
In Sec. 5, we will present schemas satisfying Asm. 3 and discuss their impacts on privacy and regret.
4.2 Our LDP Algorithm For Exploration
In this section, we introduce LDP-OBI (Local Differentially Private Optimistic Backward Induction), a flexible optimistic model-based algorithm for exploration that can be paired with any privacy mechanism satisfying Asm. 3. When developing optimistic algorithms it is necessary to define confidence intervals using an estimated model that are broad enough to capture the true model with high probability, but narrow enough to ensure low regret. This is made more complicated in the LDP setting, since the estimated model is defined using randomized counters. In particular, this means we cannot use standard concentration inequalities such as those used in [32, 33]. Moreover, when working with randomized counters, classical estimators like the empirical mean can even be ill-defined as the number of visits to state-action pair, for example, can be negative.
Nevertheless, we show that by exploiting the properties of the mechanism M in Asm. 3, it still possible to define an empirical model which can be shown to be close to the true model with high probability. To construct this empirical estimator, we rely on the fact that for each state-action pair (s, a). Ng(s,, a) + cx.2 6a, 6) 2 (T(s, a) 2 0 with high probability where the precision 22,2(E0, do, 8) ensures the positivity of the noisy number of visits to state action-pair. A similar argument holds for the transitions. Formally, the estimated private rewards and transitions before episode i are defined as follows:
Rs(s, a)
N (f(s,,,8)
Th (8, ④)
( 8, a) = (E(s, + acck acc,,o do
(4)
(E(s, a) + 2 6)
Note that unlike in classic optimistic algorithms, Pu is not a probability measure but a signed sub- probability measure. However, this does not preclude good performance. By leveraging properties of Asm. 3 we are able to build confidence intervals using these private quantities (see App. E).
Proposition 4. For any Eo > O, da 2 0, 5 > 0, a > 1 and episode k using mechanism M satisfying Asm. 3. then with probability at least - 28, for any (s, a) E S
2 2nn
SAHHS
(a 1)c,,2(E0, 6n, 6) + CR. (Eu, 80, 6)
(r(s,a) Fs(s (8
Ny(s, a) + 200,2 5o.
Ng(s, a) + 200,2((E,, 80,
(p(-(s,)) - Fu(-1s,))ll (((s,))
14S
452SAHE?
35
Sco, 80,
Nf(s, a) + ack,s 80,
N (s, a) + act, do, 6) (a + 1)cx,a(Eo, So.
(s a) acu ou, 6)
The shape of the bonuses in Prop. 4 highlights two terms. The first term is reminiscent of Hoeffding bonuses as it scales with O 011/ L// Ng) The other term is of order O (1/Nz) and accounts for the variance (and potentially bias) of the noise added by the privacy-preserving mechanism.
As commonly done in the literature [e.g., 32, 34, 35], we use these concentration results to define a bonus function (s, a) ;= (H / + 1)- (8 a) + ( a) which is used to define optimistic value function and policy by running the following backward induction procedure:
Qn, (s, a)s = Fi(( a) + bn. (s, a) + Pi ( (s, a) VA-IAK: Th. (8) = arg max Qs, (5)
where Vh,((s) min(H - h + 1, max, Qn. a)} and VH+1,(($) = 0.

---

M
Noise
(c, level
Regret A(T)
Laplace
Lap(6H/e)
(e,0)
Gaussian
N(0,(H/))
(e, 6u)
Ö(H A(H"S*A/KInn11/ (n((//6))//))
Randomized
Ber((e=/M - 1
(e,0) 0)
Respouse
Hounded
See [37] and App. F.3
(e, O(H'S (ll(1/60)/e)
Noise
Table Summary of the guarantees of LDP-OBL with different randomizers for > and 6y >
For the mechanism in this table, we have approximately c, = ((vkH/s) for E {1, 4} (ignoring
log terms) and CR = ((VSkH/E)
4.3 Regret Guarantees
get the following general guarantees for any LDP mechanism satisfying Asm. 3 in LDP-OBI.
Theorem 5. For any privacy mechanism M satisfying Asm. with E > 0, 60 2 0, and for any 5 > 0
the regret of LDP-OBI is bounded with probability at least 1 by:
30
36
A(K) =
HSV AT
+SAH CK.3
(,,0,
17a52AcK,
(c,
2T²K²
2
K²
(6)
35
35 E, 00
+SAHcK2
E, E, 2T²
+ SAHcK11
K2
2T²222
The combination of M and LDP-OBI is also (e, 6o)-
Thm. 5 shows that the regret of LDP-OBI /) is lower bounded by the regret in non non-private settings; and 2) depends directly on the precision of the privacy mechanism used though ck.l..... CK,4- Thus improving the precision, that is to say reducing the amount of noise that needs to be added the data to guarantee I.P of the privacy mechanism, directly improves the regret bounds of LDP-OBI. The first term in the regret bound
is of the order expected in the non- non-private setting (see e.g. [36]). Classical results in DP suggest that the {C is4 terms should be approximately of order vK /e (this is indeed the case for many natural choices of randomizer). In such a case, the dominant term in (38), is no longer O but rather a term of order 2 S2 Av K /s (from e.g. C..)). A. The dependency on S, A, H larger than in the non-private setting. This is because the cost of LDP is multiplicative, so it also impacts the lower order terms in the concentration results (see e.g. the second term in 4), which are typically ignored in the non-private setting. In addition, this implies that variance reduction techniques for RL (e.g., based on Bernstein) classically used to decrease the dependence on S, H will not lead any improvement here. This is be contrasted with the JDP setting where [9] shows that the cost of privacy is additive using variance reduction techniques can reduce the dependency of the regret on S, A, H.
5 Choice of Randomizer
There are several randomizers that satisfy Asm. 3, for example Laplace [14], randomized response [13, 38], Gaussian [39] and bounded noise [40] mechanisms. Since one method can be preferred to another depending on the application, we believe it is important to understand the regret and privacy guarantees achieved by LDP-OBI with these randomizers. Tab. 1 provides global overview of the properties of LDP-OBI with different randomized mechanism. The detailed derivations are deferred to App. F.
Privacy. All the mechanisms satisfy Asm. but only the Laplace and Randomized Response mechanisms guarantees (c, 0)-LPP Note that all cases, in order to guarantee a e level of privacy (or (e, 8) for the Gaussian and bounded noise mechanisms), it is necessary to scale the parameter proportional to 1/H. This is because the statistics computed by the crivacy-preserving mechanism are the sum of H observations which are bounded in [0, 1], the sensitivity* of those statisties bounded
For function f X + R. the sensitivity is defined as S()) maxx,vex' [f()) f(y)l
7

---

by H. Directly applying the composition theorem for DP [14, Thm 3.14] over the different counters, would lead an upper-bound on the privacy of the mechanism of S AHE and corresponding regret bound of Ô
For the randomizers that use, the impact on is lower thanks to fact that they are designed to exploit the structure of the input data (a trajectory).
Regret Bound. From looking at Table 1, we see that while all the mechanisms achieve a regret bound of order ŌVVK) the dependence on the privacy level & varies well as the privacy guarantees. The regret of Laplace, Gaussian and bounded noise mechanisms scale with g_ whereas the randomized response has an exponential dependence in similar to the lower bound. However, this improvement comes at the price of worse dependency in H when é is small, and worse multiplicative constant in the regret. This is due the randomized response mechanism perturbing the counters for each stage h E [ leading to up to H A obfuscated elements. This worse dependence is also observed in our numerical simulations.
For many of the randomizers, our regret bounds scale as SHHHSAAAKAA Aside from the VK rate which is expected, our bounds exhibit worse dependence the MDP characteristics when compared to the non-private setting. We believe that this is unavoidable due to the fact that we have to make 2 A terms private, while the extra dependence privacy over the whole trajectory. Moreover, the DP literature [e.g.. 41, 42, 43] suggests that the extra dependency on S, A, H may be inherent model-based algorithms due to the explicit estimation of private rewards and transitions. Indeed, [43] shows that the minimax error rate in & norm for
H comes from dividing by H to ensure
V=(osp(c)-T) with n samples in the high privacy regime (E 1). while there is no change in the low privacy regime. This means that in the high privacy regime the concentration scales with multiplicative VS term which would translate directly into the regret bound. Furthermore, this results assumes that the number n of samples is known to the learner. In our setting, n maps to (s,ssa) a) which is unknown to the algorithm. Since we only observe a perturbed estimate of n, estimating p(- [ss a) here is strictly harder than the aforementioned setting.² 5 This suggests that it is impossible for any model-based algorithm which directly estimates the transition probabilities to match the lower bound. However, this does not rule out the possibility of model-free algorithm being able to match the lower bound. Designing such model-free algorithm which is able to work with LDP trajectories is non-trivial and we leave it to future work.
estimating a distribution over S states
Another direction for future work is to investigate whether the recently developed shuffling model [45] may be used to improve our regret bounds in the LDP setting. Preliminary investigations of the shuffling model (see App. I) show that it is not possible while preserving fixed E-LDP constraint, which is the focus of this paper. Nonetheless, if we were to relax the privacy constraint to only guarantee e-JDP then the shuffling model could be used to retrieve the regret bound in [9] while guaranteeing some level of local differential privacy, although the level of LDP would be much weaker than the one considered in this paper. We believe the study of this model sitting in-between the joint and local DP settings for RL is a promising direction for future work and that the tools developed in this paper will be helpful for tackling this problem.
6 Numerical Evaluation
In this section, we evaluate the empirical performance of LDP-OBI on a toy MDP. We compare LDP-OBI with the non- non-private algorithm UCB-VI [32]. To the best of our knowledge there is no other LDP algorithm for regret minimization in MDPs in the literature. To increase the comparators, we introduce novel LDP algorithm based on Thompson sampling [e.g.. 12].
LDP-PSRL. Thompson sampling algorithms [e.g.. PSRL, 12] have proved to be effective in several applications [46]. Due to their inherent randomization, one may imagine that they are also well
'ee are not aware of any lower-bound the literature that applies to this setting but we believe that the 8 AAAKK KH/ dependence may be unavoidable for model-based algorithms. This is because Nu a) and Na(s, a) differ by most / H ASA (which is a well-known lower bound for the counting elements problem see [44]). Intuitively this difference creates bias when estimating each component p(+1 a). bias that would scale with the size of the support p(-1s, a) and the relative difference between Ni, a) and Nx a). Hence, the bias would scale with SykH /Na a). Summing over all episodes and S.A counters gives the conjectured result.
8

---

-10"
==
-100
f=2
-10P
20
Commiativ Degret
0.3
Rogre
Cuamlative Regret
0.3
0.2
6-00000
0.5
0.4
0.8
10
0.2
0.6
Time
Time
0.5
0
0.5
0.5
120 0RT L2P ORE
-10*
Time
-10P
30
UCBAVI
LDP-05HL -
1DP-0B--RX
LDR-0BL-Be -0-
LDP-05LE
Figure 1: Evaluation of LDP-OBI with the Laplace mechanism and LDP-PSRL. Left) Cumulative regret. Right) per-step regret (k + Ra/k).
Figure 2: Regret for LDP-OBI coupled with different mechanisms. For all e, 5 0.1 for the Gaussian and Bounded Noise mechanism.
suited to LDP regret minimization. Here, introduce and evaluate LDP-PSRL, an LDP variant of PSRL and provide a first empirical evaluation. Informally, by defining by Wi = {(S, p, H): |pp - Pll I -g F| S } the private set of plausible MDPs constructed using the definition in Prop. 4, we can see posterior sampling as drawing an MDP from this set at each episode & and running the associated optimal policy:
i) M PP(W)),
i) Th max (VC (M&)).
More formally, we consider Gaussian and Dirichlet prior for rewards and transition which lead to Normal-Gamma and Dirichlet distributions as posteriors. We use the private counters defined in Asm. 3 update the parameters of the posterior distribution and thus the distribution over plausible models. We provide full details of this schema in App. G and show that it is LDP. However, we were not able to provide a regret bound for this algorithm.
Simulations. We consider the RandomMDP environment described [25] where for each state- action pair transition probabilities are sampled from Dirichlet(a:) distribution (with as,a,' 0.1 for all (s, s,,,,')) and rewards are deterministic in {0, with r(s, a) = 50.5) for (U..) (). ~ [0, 1]) sampled once when generating the MDP. We set the number of states S = 2, number of actions A 2 and horizon H 2. We evaluate the regret of our algorithm for 8 E [0.2, 2, 20} and K = x 10 episodes. For each e, we run 20 simulations. Confidence intervals the minimum and maximum runs. Fig. shows that the learning speed of the optimistic algorithm LDP-OBI is severely impacted by the LDP constraint. This is consistent with our theoretical results. The reason for this the very large confidence intervals that are needed to deal with the noise from the privacy preserving mechanism that is necessary to guarantee privacy. While the regret looks almost linear for & 0.2, the decreasing trend of the per-step regret shows that LDP-OBI-L is learning. Although these experimental results only consider small MDP, we expect that many of the observations will carry across larger, more practical settings. However, further experiments are needed to conclusively assess the impact of LDP in large MDPs. Fig. also shows that LDP-PSRL performs slightly better than LDP-OBI. This is to be expected, since even in the non-prios non-private case PSRL usually outperforms optimistic algorithm empirically. Finally, Fig. 2 compares the mechanisms with different privacy levels and illustrates the empirical impact of the prevacc-preeerving mechanism on the performance of LDP-OBI. We observe empirically that the bounded noise mechanism is the most effective approach, followed by the Laplace mechanism. However, the former suffers from a higher variance in its performance.
Conclusion
We have introduced the definition of local differential privacy in RL and designed the first LDP algorithm, LDP-OBI, for regret minimization in finite-horizon MDPs. We provided an intuition why model-based approaches may suffer a higher dependence in the MDP characteristics. Designing a model-free algorithm able to reduce or close the gap with the lower-bound is an interesting technical question for future works. As mentioned in the paper, the shuffling privacy model does not provide any privacy/regret improvement in the strong LDP setting. An interesting direction is to investigate the trade-off berween JDP and LDP that can obtained in RL using shuffling. In particular, we believe that, sacrificing LDP guarantees, it is possible to achieve better regret leveraging variance reduction

---

techniques (that are not helpful in strong LDP settings). Finally, there are other privacy definition that can be interesting for RL. For example, profile-based privacy [47, 48] allows privatize only specific information geo-privacy [49] focuses on privacy between elements that are "similar".
Acknowledgments and Disclosure of Funding
V. Perchet acknowledges support from the French National Research Agency (ANR) under grant number LANR-199CF2330026 as well as the support grant, as well as from the grant "Investissements l'Avenir" (LabEEx Coodee/ANR-11-LABX--00
References
[1] Hongzi Mao, Shannon Chen, Drew Dimmery, Shaun Singh, Drew Blaisdell, Yuandong Tian, Mohammad Alizadeh, and Eytan Bakshy. Real-world video adaptation with reinforcement learning, 2020.
[2] Haoran Wang and Shi Yu. Robo-advising: Enhancing investment with inverse optimization and deep reinforcement learning. 2021.
[3] Xinlei Pan, Weiyao Wang, Xiaoshuai Zhang. Bo Li, Jinfeng Yi, and Dawn Song. How you act tells lot: Privacy-leaking attack deep reinforcement learning. In AAMAS, pages 368-376. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
[4] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, volume 3876 of Lecture Notes in Computer Science, pages 265-284. Springer, 2006.
[5] Nikita Mishra and Abhradeep Thakurta. (nearly) optimal differentially private stochastic multi-arm bandits. In Proceedings the Thirty-First Conference Uncertainty in Artificial Intelligence, UAI 15, page 592-601, Arlington, Virginia, USA, 2015. AUAI Press.
[6] Aristide C. Y. Tossou and Christos Dimitrakakis. Algorithms for differentially private multi- armed bandits. In AAAI, pages 2087-2093, AAAI Press, 2016.
[7] Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits. In NeurlPS, pages 4301-431 1301-4311, 2018.
[8] Etienne Boursier and Vianney Perchet. Utility/privacy trade-off through the lens of optimal transport. In International Conference on Artificial Intelligence and Statistics, pages 591-601, 2020.
[9] Giuseppe Vietri, Borja de Balle Pigem, Akshay Krishnamurthy, and Steven Wu. Private reinforcement learning with pac and regret guarantees. In ICML, 2020.
[10] John C Duchi, Michael I Jordan, and Martin J Wainwright. Local privacy, data processing inequalities, and statistical minimax rates. arXiv preprint arXiv:1302.3200 2013.
[11] Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang. Locally differentially private (contextual) bandits learning. CoRR, abs/2006.00701, 2020.
[12] Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. In NIPS, pages 3003-3011, 2013.
[13] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference computer and communications security, pages 1054-1067, 2014.
[14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Founda- tions and Trends in Theoretical Computer Science, 9(3-4)211-4077 2014.
[15] John M Abowd. The us census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2867-2867, 2018
10

---

[16] Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shufiling. Lecture Notes in Computer Science, page 375-403, 2019.
[17] Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: simple and nearly optimal analysis of privacy amplification by shuffling, 2020.
[18] Lijie Chen, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. On distributed differential privacy and counting distinct elements. ITCS, volume 185 of L/Plcs, pages 56:1-56:18, Schloss Dagstuhl- Leibniz-Zentruu für Informatik, 2021.
[19] Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. The privacy blanket of the shuffle model. In CRYPTO (2), volume 11693 of Lecture Notes Computer Science, pages 638 -88-677 Springer, 2019.
[20] Ülfar Erlingsson, Vitaly Feldman, Ily Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta. Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation. CoRR, 02//2001.03615 2020.
[21] Pratik Gajane, Tanguy Urvoy, and Emilie Kaufmann. Corrupt bandits for preserving local privacy. In ALT, volume 83 of Proceedings of Machine Learning Research, pages 387-412. PMLR, 2018.
[22] Touqir Sajed and Or Sheffet. An optimal private soohassticmab algorithm based on optimal private stopping rule. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 5579-5588. PMLR, 2019.
[23] Xiaoyu Chen, Kai Zheng, Zixin Zhou, Yunchang Yang. Wei Chen, and Liwei Wang. (locally) differentially private combinatorial semi-bandits. In ICML, 2020.
[24] Wenbo Ren, Xingyu Zhou, Jia Liu, and Ness B Shroff. Multi-armed bandits with local differential privacy. arXiv preprint arXiv:200..03/21, 2020.
[25] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, pages 5713-5723, 2017.
[26] Borja Balle, Maziar Gomrokchi, and Doina Precup. Differentially private policy evaluation. In ICML, volume 48 of JMLR Workshop and Conference Proceedings, pages 2130-2138. JMLR.org, 2016.
[27] Baoxiang Wang and Nidhi Hegde. Privacy-preserving q-learning with functional noise in continuous spaces. In NewrIPS, pages 1 11323-1133,, 2019.
[28] Hajime Ono and Tsubasa Takahashi. Locally private distributed reinforcement learning. arXiv preprint arXiv:2001.11718, 2020.
[29] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, USA, 1994.
[30] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(1):48-77, 200.
[31] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[32] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In ICML, volume 70 of Proceedings of Machine Learning Research, pages 263-272. PMLR, 2017,
[33] Andrea Zanette and Emma Brunskill. Tighter prohlem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In ICML,, volume 97 of Proceedings of Machine Learning Research, pages 7304-7312. PMLR, 2019.
[34] Jian Qian, Ronan Fruit, Mateo Pirotta, and Alessandro Lazaric. Exploration bonus for regret minimization discrete and continuous average reward mdps. NeurlPS, pages 4891-4900 2019.
11

---

[35] Gergely Neu and Ciara Pike-Burke. A unifying view of optimism in episodic reinforcement learning. arviv preprint arXiv:2007.0189), 2020.
[36] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning, Journal of Machine Learning Research, 11:1563-1600, 2010.
[37] Yuval Dagan and Gil Kur. A bounded-noise mechanism for differential privacy, 2020.
[38] Peter Kairouz, Keith Bonawitz, and Daniel Ramage. Discrete distribution estimation under local privacy. arXiv preprint 1rQ.v 2016.
[39] Teng Wang, Jun Zhao, Xinyu Yang. and Xuebin Ren. Locally differentially private data collection and analysis. arXiv preprini 1rXiv:1906.01/ 2019.
[40] Yuval Dagan and Gil Kur. A bounded-noise mechanism for differential privacy, arXiv preprint arXiv:2012.03817 2020.
[41] John C. Duchi, Martin J. Wainwright, and Michael I. Jordan. Minimax optimal procedures for locally private estimation. CoRR, abs/1604.02333 (2090,0 2016.
[42] John Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity, 2019.
[43] Min Ye and Alexander Barg. Optimal schemes for discrete distribution estimation under locally differential privacy. IEEE Trans. Inf. Theory, 64(8):5662-5676, 2018.
[44] Raef Bassily and Adam Smith. Local, private, efficient protocols for succinct histograms. Proceedings of the sertt- annual ACM symposium Theory of Computing, Jun 2015.
[45] Úlfar Erlingsson, Vitaly Feldman, Ily Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shufffing: From local to central differential privacy via anonymity. In SODA, pages 2468-2482 2479. SIAM, 2019.
[46] Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Oshand, and Zheng Wen. A tutorial on thompson sampling. Found. Trends Mach. Learn., 11(1):1-96, 2018.
[47] Joseph Geumlek and Kamalika Chaudhuri. Profile-based privacy for locally private computa- tions. In ISIT, pages 537-541. JEEE, 2019.
[48] Jayadev Acharya, Kallista Bonawitz, Peter Kairouz, Daniel Ramage, and Ziteng Sun. Context aware local differential privacy. ICML, volume 119 of Proceedings of Machine Learning Research, pages 52-62. PMLR, 2020.
[49] Miguel E. Andrés, Nicolás Emilio Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. geeo-ndissingusshablliyy differential privacy for location- based systems. In CCS, pages 901-914. ACM, 2013.
[50] Aristide Tossou and Christos Dimitrakakis. Differentially private multi-agent agent multi-armed bandits. In European Workshop on Reinforcement Learning (EWRL-15), 2015.
[51] Abhimanyu Dubey and Alex Pentland. Differentially-priinn -pivvate federated linear bandits. Technical report, Massachusetts Institute of Technology, 2020.
[52] Abhimanyu Dubey and Alex Pentland. Private and byzantine-prodd cooperative decision-making. In AAMAS, pages 357-365. International Foundation for Autonomous Agents and Multiagent Systems, 2020.
[53] Awni Y. Hannun, Brian Knott, Shubho Sengupta, and Laurens van der Maaten. Privacy- preserving multi-party contextual bandits. CoRR, abs/1910.05299, 2019.
[54] Mohammad Malekzadeh, Dimitrios Athanasakis, Hamed Haddadi, and Benjamin Livshits. Privacy-preserinng bandits. In MLSys. misys.org, 2020.
[55] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinherger. Inequalities for the 11 deviation of the empirical distribution. 2003.
12

---

[56] Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Improved analysis of ucr12 with empirical bernstein inequality. arXiv preprint wrXiv:2007.05450 2020.
[57] Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. Prochlo. Proceedings of the 26th Symposium on Operating Systems Principles, Oct 2017.
[58] Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. Differentially private summation with multi-messes shuffling. CoRR, abs/1906.091 09, 2019.
[59] Victor Balcer and Albert Cheu. Separating local & shuffled differential privacy via histograms. In für Informatik,
ITC, volume 163 of L/Plcs, pages 1111::1. Schloss Dagstuhl 2020.
13


Reviews:
[{"review_id": "b6shYHsQ6Nr", "reviewer": "Reviewer_fiXi", "summary": "An interesting study on discrete MDP under LDP.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This manuscript investigates discrete MDPs under LDP constraints. The contribution is two-fold. First, it shows that the problem incurs a regret at least \\Omega(K^1/2). The hardness is through the information theory-based technique previously used in bandits and a construction of an A-fold tree MDP. The contribution is significant. Second, armed with an LDP mechanism, it proposes a model-based exploration method for discrete MDP. The regret is upper bounded by O(H^3 S^2 A K^1/2) up to some logarithm factors. The upper bound is reasonably tight though there leaves a gap between the upper and the lower bounds. The techniques used in the proof of the upper bound are standard in discrete MDPs.\n\nI suggest the authors have a thorough revision of their manuscript. The reading might not be very smooth. Here are a few examples:\nline 17 - Privacy should be protected. It is not just due to that \"users are becoming increasingly wary of that\"\nline 29 - circle 2 can be confusing (say something more explicitly when you define your scenarios)\nline 55 - I don't see this footnote 2 very useful\nline 57 - I don't think you can conclude that one problem is harder than another one simply by comparing their best known lower bounds. You'll need to compare a lower and an upper, or use a direct argument.\nAlso, the way the mathematical formulation are presented are not very professional (like the use of terms and punctuation). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "IlpTXR90zNz", "reviewer": "Reviewer_u5vy", "summary": "The paper examines reinforcement learning under local differential privacy constraints. The paper proposes an algorithm, LDP-OBI, derives its regret bounds as well as privacy guarantees, and provided some simulation results.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- Originality: the paper focuses on the new intersection between local differential privacy and reinforcement learning. The author proposes local differential privacy adapted to RL and also applied existing privacy mechanisms in a RL setting, differentiating it from existing private RL works. Related works are cited and discussed thoroughly.\n\n- Quality: the technical proofs are sound and simulations support the authors' claims in simple tasks. While implementation is not included in the supplement, the paper is largely theoretical and the experiment results should be sound. \n\n- Clarity: the paper is clear and well-written.\n\n- Significance: while local DP + RL is an interesting problem with great significance, LDP-OBI appears to be a direct combination of existing privacy mechanisms and existing RL algorithms and its regret bound is much greater than the derived lower bound. However, the results in the paper are still worth examining and the could pave way for future studies at the intersection of privacy and RL. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the paper are clearly stated.\n\nThere are no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "EpRoPUTr-vI", "reviewer": "Reviewer_QJNv", "summary": "This paper introduces the concept of Local Differential Privacy for RL, a stronger notion of privacy than Joint Differential Privacy for RL. The authors both prove a regret bound for LDP in RL and provide a novel algorithm that achieves good regret in this setting. Furthermore, empirical experiments are provided that validate the method.  \n", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Unfortunately I am not familiar with this literature at all, but I will try to provide some good feedback. \n\nMy main concerns are that it seems that LDP is simply too strict of a privacy guarantee for RL, and that this will make it impractical in practice. With that being said, it seems that the main results in this paper show that decent results are possible in this setting, so this worry might be unfounded. \n\nThe authors submitted this work to two conferences before. At the first conference the reviewers said that the work was not well written and that the main contributions and importance of the problem were missing. I think these points have been solved, as the paper is very well written and the main contributions are clear. In the second conference, reviewers thought that the regret bound could be improved with shuffling. In lines 69 - 73 the authors address this issue, but not enough in my opinion. They refer to Theorem 5.2 in Feldman et. al., but it is not immediately clear to me why that theorem backs their claim. This could be because I am not familiar with the field, but regardless I think the paper could be improved with a more extensive discussion of this issue, perhaps in the appendix. \n\nOther than that issue, I was not able to find any faults in the paper. The problem seems well motivated and the theory looks good. The experimental results back up the theory and the paper is well written.   \n\n--------------------------------\nI have read the rebuttal and do not change my score. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "D-aui9ZpP2", "reviewer": "Reviewer_kXoY", "summary": "This paper studied the regret analysis of reinforcement learning under the tabular setting and the LDP (local differential privacy) constraint. The authors first showed a minimax lower bound that, unlike the additive dependence on $\\varepsilon$ under the JDP (joint differential privacy) constraint, the stronger LDP constraint must incur a minimax regret multiplicative in $1/\\varepsilon$. Then the authors provided a general paradigm of the upper bound analysis: find private versions of aggregated statistics (rewards, number of visits), and then carry out an optimistic policy (called the LDP-OBI algorithm) based on (UCBs of) these noisy statistics. Depending on the usage of different private mechanisms, a regret multiplicative in $\\sqrt{K}/\\varepsilon$ could be obtained, but with worse dependence on other parameters $(H,S,A)$. Discussions and numerical experiments on the result are also provided. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I like this paper. The LDP constraint in reinforcement learning is useful to preserve privacy, and the separation between LDP and JDP constraints shown in the paper is interesting. The authors proposed a general paradigm for the upper bound analysis which could be useful in other papers, and also gave a lower bound analysis with a tight dependence on $(K,\\varepsilon)$ to support the optimality of the proposed mechanism. The writing is mostly clear to me. \n\nHowever, I can also list some drawbacks of this work: \n\n1. The upper bound analysis, mainly Section 4.2, is technical while quite standard. I do like the current presentation which summarizes all necessary conditions as Assumption 3 and proves a general result in Proposition 4, but the essentially the same argument was applied in the non-constrained RL setting, and it seems that this part does not add much novelty to the RL literature. If this is the case, then the contribution of just applying various private mechanisms to obtain aggregated statistics is limited. I suggest the authors to highlight the main novel points in Section 4.2 to differentiate from the non-constrained RL regret analysis.\n\n2. The current upper bound has a potentially loose dependence on parameters (H,S,A). This may suggest that the privacy constraint is currently not handled in a most appropriate way, and there might be room for significant improvement. In fact, Table I already shows that using one private mechanism could have a much worse performance than using another one. \n\n3. In the discussion the authors provided some evidence that the current dependence on (H,S,A) might not be tight. If this is the case, ideally I hope the authors could provide a rigorous argument (a partial result is okay) instead of only conjecturing it. I have to say that the current lower bound analysis is pretty standard - it is essentially the estimation of the bias of a coin under the LDP constraint (or in other words, a simple combination of the non-constrained case and the strong data-processing inequality applied to the LDP constraint). So a stronger lower bound would also increase the significance of the lower bound. \n\nOne minor comment: I do not understand why a minimum is present in Eqn. (14). Isn't it the case that by the data-processing inequality for general f-divergences, the first term is always no greater than the second term? Consequently, I also do not understand why these two terms need to be obtained from two different equations (11) and (13). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studied the regret analysis of reinforcement learning under the tabular setting and the LDP (local differential privacy) constraint. All the reviewers believe that the paper is above the acceptance line. The reviewers also raised various minor concerns, e.g., the paper might read very smooth, there exists a gap in the upper and lower bound. I encourage the authors to address these comments in the next revision.
Decision: Accept (Poster)