Privacy Preserving Reinforcement Learning for Population Processes
Authors: Samuel Yang-Zhao
Kee Siong Ng
Venue: Accepted by TMLR ()

Abstract: We consider the problem of privacy protection in Reinforcement Learning (RL) algorithms that operate over population processes, a practical but understudied setting that includes, for example, the control of epidemics in large populations of dynamically interacting individuals. In this setting, the RL algorithm interacts with the population over $T$ time steps by receiving population-level statistics as state and performing actions which can affect the entire population at each time step. An individual's data can be collected across multiple interactions and their privacy must be protected at all times. We clarify the Bayesian semantics of Differential Privacy (DP) in the presence of correlated data in population processes through a Pufferfish Privacy analysis. We then give a meta algorithm that can take any RL algorithm as input and make it differentially private. This is achieved by taking an approach that uses DP mechanisms to privatize the state and reward signal at each time step before the RL algorithm receives them as input. Our main theoretical result shows that the value-function approximation error when applying standard RL algorithms directly to the privatized states shrinks quickly as the population size and privacy budget increase. This highlights that reasonable privacy-utility trade-offs are possible for differentially private RL algorithms in population processes. Our theoretical findings are validated by experiments performed on a simulated epidemic control problem over large population sizes.

Published in Transactions on Machine Learning Research (12/2024)
Privacy Preserving Reinforcement Learning for Population Processes
Samuel Yang-Zhar Zhao Australian National University
samuel. mangel..ang-shhee www.sssaaaaaaaa...oooo
Kee Siong Ng Australian National University
Reviewed on OpenReview: https: // openreview. net/ met/ forum? id- 2ZFd aDDUEE
Abstract
We consider the problem of privacy protection in Reinforcement Learning (RI) algorithms that operate over population processes, a practical but understudied setting that includes, for example, the control of epidemics in large populations of dynamically interacting individuals. In this setting, the RL algorithm interacts with the population over T time steps by receiving population-level statistics as state and performing actions which can affect the entire population at each time step. An individual's data can be collected across multiple interactions and their privacy must be protected at all times. We clarify the Bayesian semantics of Differential Privacy (DP) in the presence of correlated data in population processes through a Pufferfish Privacy analysis. We then give a meta algorithm that can take any RL algorithm as input and make it differentially private. This is achieved by taking approach that uses DP mechanisms to privatize the state and reward signal at each time step before the RL algorithm reccives them as input. Our main theoretical result shows that the value-function approximation error when applying standard RL algorithms directly to the privatized states shrinks quickly as the population size and privacy budget increase. This highlights that reasonable privacy-utility trade-offs are possible for differentially private RL algorithms in population processes. Our theoretical findings are validated by experiments performed simulated epidemic control problem over large population sizes.
1 Introduction
The increasing adoption of Reinforcement Learning (RL) algorithms in many practical applications such digital marketing, finance, and public health (Mao et al., 2020; Wang & Yu 2021 Charpentier al., 2020) have led new, challenging privacy considerations for the research community. This is a particularly important issue in domains like healthcare where highly sensitive personal information is routinely collected and the use of such data in training RL algorithms must be handled carefully, in light of successful privacy attacks on RL algorithms (Pan et al., 2019). Privacy Preserving Reinforcement Learning is an active research area looking to address these concerns, mostly via the now widely accepted concept of Differential Privacy (DP) (Dwork et al. (206)), which confers formal 'plausible deniability' guarantecs for users whose data are used in training RL algorithms,, thus offering them privacy protection.
In this paper, consider the setting where RL agent interacts with population of individuals and investigate how each individual's differential privacy can be protected. We assume interactions between individuals are not visible to the RL agent but the agent receives population-level statistics at every time step and can perform actions that affect the entire population. This class of environments, which we call population processes, models settings such as the control of epidemic spread by government interventions Kompella et al. 2020). As an individual's data is collected across multiple interactions, our goal is ensure that. individual's data contributions over all interactions differentially private. To the best of our

---

Published in Transactions on Machine Learning Research (12/2024)
knowledge, existing approaches to privacy-preserving reinforcement learning, which we survey next in do not cater to this natural and important problem setting and are unable to exploit the structure of the problem.
1.1 Related Work
The earliest works to consider differential privacy in a reinforcement learning context were focused the
bandit or contextual bandit settings (Guha Thakurta & Smith 2013
Mishra & Thakurta 2015
Tossou
& Dimitrakakis 2016 2017 [harrif & Sheffet, 2018 Sajed & Sheffet 2019 Zheng et al., 2020 Dubey &
Pentland 2020 Ren et al. 2020 Chowdhury & Zhou 2022b Azize & Basu 2022). A key negative result
is in Shariff & Shoffet (2018), who show that sublinear regret not possible under differential privacy in
contextual bandits, a result which also holds in the reinforcement learning setting.
Differentially private reinforcement learning beyond the bandit setting has been primarily considered in a personalization context. In Balle et al. (2016), the authors study policy evaluation under the setting where the RL algorithm receives set of trajectories, and a neighbouring dataset is one in which a single trajectory differs. In a regret minimization context, there is a body of work on designing RL algorithms to satisfy
either joint differential privacy (Vietri et al. 2020 Luyo et al. 2021 Chowdhury Zhou 2022a Ngo et al.
2022 Zhou 2022 Qiao & Wang 2023) or local differential privacy (Garcelon et al.J 20000] Luyo el al. 2021 Chowdhury & Zhou 2022a Liao et al. 2023). In all of these works, the RL algorithm is framed as interacting
with users in trajectories or episodes, with each trajectory representing multiple interactions with single user. A neighbouring dataset is then defined with respect to a neighbouring trajectory. Such DP-RL approaches cannot be easily adapted for privacy protection in population processes, where (i) each interaction is with an entire population (rather than a single individual); (ii) specific individual is typically not sampled in consecutive time steps so there is not a corresponding notion of a trajectory; and (ii)) an individual's data could actually be present across all time steps, a low-probability event that we nevertheless have handle.
In Wang & Hegde (2019), the authors analyse the performance of deep Q-learning (Mnih et al. 2015) under differential privacy guarantees specified with respect to neighbouring reward functions. This notion of privacy makes natural sense when the reward function is viewed as an individual's private preferences but is also inapplicable to our setting as it does not consider the privacy of the state.
In relation to our application domain and experimental results, the control of epidemics is a topical subject given the prevalence of COVID-19 recent years and many different practical approaches have been developed
(Arango & Pelov 2020 Charpentier et al.) 2020: Colas et al., 2020: Berestizshevsky et al. 2021 Kompella
et al. 2020 Chen et al. 2022). Whilst. the preservation of individual privacy has been considered in the context of public release of population-level epidemic statistics (Dyda et al. 2021 Li et al.
2023),
not
aware of other work that achieves individual privacy preservation in the modelling and control of epidemics
using reinforcement learning.
1.2 Contributions
The main questions we address in this paper are the following:
For an RL algorithm interacting with a population of individuals, what is the right notion of individual privacy we should care about, and can that individual privacy be protected using differential privacy?
2. Assuming the answer to the first question is positive, are good privacy-utility trade-offs possible for differentially private RL algorithms in population processes?
We answer the first question in two parts. We first show through a concrete example (see Example 4 that highly correlated data is possible in population processes and that some sensitive information that one may naturally wish to protect, like a person's 's infection status during an epidemic, cannot always be protected. We then give, using the general Pufferfish Privacy framework (Kifer & Machanavaijhala, 2014), precise semantic definition of the secrets around individual participation in samples that can actually be protected and show its equivalence to k-fold adaptive composition of DP mechanisms (see Lemma []. Building on that,
2

---

Published in Transactions on Machine Learning Research (12/2024)
we then describe family of DP-RL algorithms for population processes and show how differential privacy and correlated data are somewhat orthogonal issues in our set up.
On the second question, we note our DP-RL solution is a meta algorithm that takes any RL algorithm (whether online or based/policcy such a modular solution is desirable for its simplicity and generality, the trade-off is more difficult control problem because the underlying environment becomes partially observable to the RL agent. Standard methods for dealing with partial observability typically require expensive state-estimation techniques sampling based approximations MMonhan 1982. Shani et al., 2013 Kurniawati 2022). Instead of using these methods, we analyze the performance of standard RL algorithms as the sampled population size N and privacy budget increases. Under some assumptions, we obtain the following bound on the approximation error under privacy
as a black box and make it differentially private. Whilst
1|0- - 12 so 50(vKen (- ((Kesp((2//
2V2K (T
+ K exp (-VNe)
+
K VN
(1)
where Q" is the optimal value function for given (arbitrary) population process M, Q is the optimal value function for the privatized form of M, and K is the dimension of the state space. (The precise statement is Theorem in $ 4.2 Note that the RHS of (1) goes to 0 as N and increases, and that such a result. is not possible in the personalization setting (Shariff & Sheffet 2018). Whilst this result does not imply a fimite-time sample complexity guarantee, we validate empirically on an epidemic control problem simulated over large graphs that our DP-RL algorithm behaves well as the population size and privacy budget increases, as suggested by D Our results retenstrate that reasonable privacy-utility trade-offs are certainly possible for differentially private RL algorithms in population processes.
2 Preliminaries
2.1 Reinforcement Learning and Markov Decision Processes
We consider a time- homogenooosss Markov Decision Process (MDP) M = (S,A, with state space S, action space A, Iransition function P: S x A - D(S), reward function r: S x A [0, T'ma]), discount factor E 10, The notation D(S) defines the set of distributions over S. The rewards are assumed to be bounded between and Tmax E R. stationary policy a function x S + D(A) specifying a distribution over actions based on a given state, i.c a ~ st). A stationary deterministic policy assigns probability to a single will define stationary deterministic policy to have the signature π S + A. Let II denote the set of all stationary policies. The action-value function (Q- (Q-value) of a policy π is the expected cumulative discounted reward (" a) = r(s,a) a) + E, EE y'r(st, at),, where the expectation is taken with respect to the transition function P and policy æ at each time step. The value function is defined as (*))) = E.-n(( [=][["(( (s,a)]. The Q-value satisfics the Bellman equation given by Q" (s, a) = r(s, a) + yEp (s)]'
action in given state. With a slight. abuse of notation,
When considering the optimal policy, define V*(s)= = sup VT(s) and (s)s, = sup (s,,. The optimal action-value function satisfics the bellman optimality equation given by (s. = r(s,a) yEp [max. Q" Q'(s',a'' There exists an optimal stalionary deterministic policy x² E II such that V*(()= = F" (s). The greedy policy x" (s)) = arg max, Q" (s(ss) a) is in fact an optimal policy.
We primarily consider the case when S is finite. In this case, it is helpful to view our functions as vectors and matrices. We use P to refer to a matrix of size (IS) x [Al) x [S] where Ps is equal to P(s' ss a) and Psa is a length [S] vector denoting P(I a). Similarly, we can view Va as a vector of length [S] and Q" and r as vectors of length [S] x []. The Bellman equation can now be expressed as
=r=
2.2 Stochastic Population Processes
A stochastic population process models a stochastic system evolving over a collection of individuals and allows for heterogeneous interactions between them. Consider a population of N individuals indexed by
3

---

Published in Transactions on Machine Learning Research (12/2024)
the set [N*]] = N.) Individual i's status at time t is given by the random variable X1, [K], which takes one of K values, and X; (Xt,1,..., Xt,v-) denotes the random vector of all individuals' status. A graph at time t is denoted by G2 = (V, &)) where the nodes V represent the individuals and & represent the interactions between individuals at time t. We assume that the total number of individuals is fixed but the edges evolve over time. To denote sequences, let V1a = (Y,,..., Y)) and Yzu = .Y,,..., YY-))- The graph at time evolves according to distribution Ge (c))))). An individual's status depends only upon the previous graph and the previous status of its neighbours, thus satisfying the Markov properly, and can be expressed P(X, X<) P(X, X--). We will assume that individuals' initial status are drawn independently from distribution P(Xo Geo, X P(Xo) and are not dependent on any interaction graph.
2.3 Differential Privacy
Differential privacy is now commonly accepted definition of privacy with good guarantees even under adversarial settings (Dwork et al. 2006). The differential privacy definition allows different notions of privacy by defining the concept of a neighbouring dataset appropriately. The following definition is a common choice Dimitrakakis et al. 2017):
Definition 1 (Differential Privacy). A randomized mochanism M: + is (c, diifferrrrtlll private if for any E x and for any measurable subset f2 C U
P(M(D) E E S P(M((') E + 8,
for all D' in the Hamming-1 neighbourhood of D. That is, D' may differ in at most one entry from D: there exists at most one i [n] such that D, + D/-
A standard approach to privatising query over an input dataset is to design a mechanism M that samples noise from a carefully scaled distribution and add it to the true oulput of the query. To scale the noise level appropriately, the sensitivity of query is an important parameter.
Definition 2 (4 sensitivity). Let f be function f x - u. Let d 2 x Xm + {0,1) be a function indicating whether two inputs are neighbours. The sensitivity of f is defined as D = SUDe.r"x"=dd [xx(x) - f(x')l
Differential privacy has several well known properties, such as composing adaptively and being preserved under post-processing, that we will make use of.
2.4 Pufferfish Privacy.
Pufferfish privacy was introduced in Kifer & Machanavajjhala (014) and proposes a generalization of differential privacy from a Bayesian perspective. In the Pufferfish framework, privacy requirements are instantiated through three components: (i) S, the set of secrets represent ing functions of the data that we wish to protect; (ii) Q C S x S, set of secret pairs that need to be indistinguishable to an adversary; and (ifi) θ, class of distributions that plausibly generate the data. Typically θ is viewed the beliefs that adversary holds over how the data was generated. Pulferfish privacy is defined as follows:
Definition 3 (Pufferfish Privacy). Let (S, Q θ) denote the set of secrets, secret pairs, and data generating distributions and let D be a random variable representing the dataset. A privacy mechanism M is said to
be (c, (...)))ferffish private with respect to (S, Q 9) if for all A E θ, D ~ 0, for all (s), Q and for all w E Range(M), we have
P(M(D)
st, 0)
S 6
(2)
P(M(D) = w $5.. 0)
where 5; 8y are such that P(s; 10) + 0, P(s, 10) 4 0.
For 5 0, applying Bayes Theorem to Equation 2 shows that Pufferfish privacy can be interpreted as bounding the odds ratio of 8; to 8j; an attacker's belief in 8t being true over sj can only increase by factor
4

---

Published in Transactions on Machine Learning Research (12/2024)
of E" after seeing the mechanism's output. The main advantages of Pufferfish privacy that it provides formal way to explicitly codify what privacy means and what impact the data generating process has. This has been used to clarify, among other things, the semantics of differential privacy protection in the presence of possibly correlated data in Kifer & Machanavajjhala (2014), a topic that motivated multiple attacks and possible solutions (Kiler Machanavajjhala 2011 Liu et al. 2016 Srivatsa & Hicks 2012 Zhao al. 2017 Yang et al. 2015 Almadhoun et al., 2020 We will similarly use the Pufferfish framework to make the semanttcc of our privacy guarantees population processes, which can have correlated data, explicit.
3
Problem Setting
3.1
Model
We now describe how the problem of controlling population processes is modelled as an MDP and also the underlying data-generation process.
The environment & is modelled as a stochastic population process evolving over N individuals. The RL agent is denoted by s/. We assume there is a trusted data curator 2 that collects the data from the environment. At each time step, N individuals are randomly sampled (not necessarily uniformly) and their potentially sensitive data is collected by the data curator. We consider the case where the interactions between individuals are unknown, i.e. 2 has access to the graph sequence G1.T. This models many problem domains such the control of epidemics where the underlying interactions between people in population decisions can only be made based upon population statistics. We consider the case of histogram queries. The agent of picks actions al each lime step depending upon the received stale and also computes its reward rt = r(t, (4-1) as a function of the current state and previous action. In summary, the environment, agent, and data curator interact in the following manner, given an initial graph Go and status Xo generated from some distribution.
not visible and
For time = 1,..., T:
1. & generates the status for all individuals X, P(.1Gr-1, Xx-1), with X, "aal...,,,,,, 2 samples a subset Le S [N*] of size N and produces the dataset D, = (Xis)ieta
3. Ø answers histogram query = <(D:) = +/2 Eier, (I(X,,, = a)) and computes reward
re = r(s,, 11-)).
4. s receives state st and reward and forms the transition sample (5) to learn from.
5. s picks the next action at me(- [s))
The graph G. ~ G(11))) is sampled depending on the last graph and action selected.
The state space S thus consists of any vector = E 1]K that satisfies ΣiE[K] z 1 and 2, = e/N for some Q E 1, N}. The action space A is application-dependenn. In general, we consider the setting where a selected action a; E AA modifies the edges in the graph. For example an action could correspond to cutting all edges for a subset of nodes, emulating the effect of "quarantining' individuals an epidemic control context. Thus the graph at time & depends upon the action chosen and is distributed according to P(G, at). These underlying transitions on individuals' states and the graph structure will induce a transition function S:S x A D(S) over the state space that implicitly captures the impact of the agent's actions.
((D)). The state query has scnsitivity A, = 2/N as using individual j's data instead of individual i's data can change the counts in at most two bins of the histogram. Additionally an individual could be sampled multiple times by D over T interactions so we need to ensure that their combined data over steps are treated a differentially private way.
An individual's data is exposed via the state histogram query
Example (Epidemic Control). Throughout this paper we consider the Epidemic Control problem as a concrete instantiation of our problem setting. One particular example is the Recoovred--Susceepbbbe (SFIRS) process on contact networks (Pastor-Satorres al. 2015 Nowzari et. al.
5

---

Published in Transactions on Machine Learning Research (12/2024)
An SEIRS process contact networks is parametrized by graph G EV,E), representing interactions, and four transition rates 8, N. >> 0. At any point in time, each individual is in one of four states: Susceptible (S), Exposed (E), Infected (I), or Recovered (R). If individual i is Susceptible at time and has interacted with de, individuals who are Infected, then individual bocomes Exposed with probability - (1 - 3)d,... Once Exposed, an individual becomes Infected after Geometric(a) amount of time. Similarly, an Infected individual becomes Recovered with Geometric(7) time and a Recovered individual becomes Susceptible again with Geometric(p) time. At each time i, the state is a histogram representing the proportion of individuals that are of each status. Instead of allowing all interactions, the agent's actions allow for subset of nodes to be quarantined for one time step. This has the effect of modifying the graph's 's edges such that quarantined individuals have no edges for a single time step. A typical reward function provides a cost proportional to the number of individuals quarantined and the number of infected individuals.
2016: Newman 2018
P
S
R
3
Figure Visualisation of the parameters that govern the transitions between states for individuals in the SEIRS process over contact networks.
Example (Countering Misinformation). The spread of misinformation in online social media is one of the key threats to society. There is good literature on different (nis)information percolation and diffusion models [Del Vicario et al. 2016 Van Der Linden 2022) that take factors like homogeneity and polarisation into account, as well as containment strategies like running counter-informattio campaigns to debunk or 'prebunk' misinformation, possibly through targeting of influencers in social networks (Budak et al. 2011 Nguyen et al. 2012: Acemoglu et al. 2023 Ariely 2023). Designing reinforcement learning algorithms that can detect and control spread of misinformation in a differentially private manner is another example of our general problem setting.
Example 3 (Malware Detection and Control). Malware propagation models on large-scale networks (Yu ct al. 2014) and smartphones (Peng et al. 2013) have long been a subject of interest in cyber security, with more recent work focussing on malware propagation internet-of-things (Li et al.) 2020 Yu et al. 2022 Muthukrishnan et al.) 2021). Designing reinforcement learning algorithms to detect and control the spread of malware, espccially unknown malwares whose signatures can only be discerned from collecting data on potentially sensitive device-usage behaviour, is also example of our general problem setting.
3.2 Formalizing Privacy in the Presence of Correlated Data
In this section we clarify the precise privacy protections we will provide under differential privacy in our problem setting. Protecting privacy in population processes presents some unique issues that are not typically encountered in the standard application of differential privacy. In particular, correlations between different individuals' data can easily arise due to the fact that individuals interact with each other at each time step and also over multiple time steps. Whilst differential privacy's guarantees are a mathematical statement that hold regardless of the process that generated the data, the semantics of these guarantees are often misinterpreted when it is applied. This leads to misalignment between what one hopes to keep private and what is actually kept private. We illustrate this with an example.
Example 4. Consider a highly contagious but long recovery flu spreading in a tight-knit community of N* individuals who live in the same location. The dataset is D, (X,,))iet, where L, S [N*] denotes subset of individuals sampled for their flu status X E 10, As the individuals live in the same location, their interaction graph is a fully connected graph. The goal is to relcase the number of infected individuals ge = Eiet, Xz,; at time whilst still preventing an adversary from detecting whether a particular individual, say Alice, has the flu at that point in time. If the underlying data generating process is ignored, the statistic qe has sensitivity 1 and q. = ge + Lap(1/c), where Lap(1/c) is the noise generated from the Laplace mechanism, is an e-differentially private statistic. However, given the flu's characteristies and the fully connected interaction individuals are infected at any time t.
graph, we can say with high probability either all individuals
6

---

Published in Transactions on Machine Learning Research (12/2024)
Thus, adversary could guess from the value of q which of these two scenarios is the case, thereby also recovering Alice's s flu status with high probability.
It would be natural to hope that an individual's flu status could be protected under differential privacy but Example illustrates that this may not be possible if the data is correlated and the adversary has additional information about the problem. Solutions like Group Differential Privacy (Dwork & Roth 2014), which adds noise proportional to the largest connected component in a graph, and Dependent Differential Privacy (Liul et al. 2016), which adds noise proportional to the amount of correlation in the data, exist but the amount of additional noise that is required typically destroys utility. So what can differential privacy protect in population processes in general and in special scenarios like Example A The answer, as we shall see, is that differential privacy confers plausible deniability on an individual's participation or presence in dataset sampled from the underlying population, but not the individual's actual status, which can sometimes be inferred. Example | highlights the need for privacy researchers to be explicit about the data generating process, the adversary's assumptions, and what information one wishes to protect. This can be done using Pufferfish privacy and this how we will make explicit the guarantees provided by differential privacy in our problem setting.
Given the data-generation model described in 3.1 let Da.r be the sequence of sampled datasots, where D. (Xe,)) denote the dataset produced at time t. Given a subset S of [T], we first define the boolean variable (K.s) that indicates whether an individual i's data is present in D. for each E S and not anywhere else:
A A (NiE LES
(
( i i ($11) I..)
(1.S)
1E(T]VS
We then define the secret pairs Q as follows, which state, in extensional form, that for each individual is indistinguishable whether the person's is status exists in subset of the sampled datasets.
== U
U
(o
NE
SC[THS|2
Q U
U
U
[E[N-] SCITHSI2 RCS||R22
The additional element to specify in the Pufferfish framework is the data generating processes O representing the possible ways an attacker believes the data could have been generated. We define each 0 E to be a parameterization of the form 0 == (8, Mt.1.... h= where 6 represents the underlying stochastic population process and is a distribution over the graph and status sequences, and μ4, the probability that E L.- We assume the attacker also has distribution over the agent's policy that is integrated out in 6. Thus, have
T
10) E
(GIrT XI.) II [=1
P(D: X2,
(3)
GLDT X1:
where
P(D,
II H4, (1- p(.)).
(4)
iEL.
JEL.
We do not place any restriction on 8, which models the attacker's prior belief over the likely sequence of interactions between individuals in the population and the attacker's knowledge about the dynamics model of the underlying population process.
The following result states the equivalence between d) privacy with parameters (S, Q θ) and (c, -))ddifferentiall privacy under T-fold adaptive composition Dwork et al. 2010 Dwork & Roth 2014 The
full proof is given in Appendix A
Lemma family of mechanisms F satisfics (c, 8)-differenttal privacy under T-fold adaptive composition iff every sequence of mechanisms M (M....,, with M, F, satisfies (c, Puffffrrfsss privacy with parameters (S, Q O).
7

---

Published in Transactions on Machine Learning Research (12/2024)
Algorithm 1 Differentially Private Reinforcement Learning
Input: Environment M = A., RL algorithm RL : Axx - II, Privacy Mechanism M: 8 x R - S, initial stale 8o E.
2: Parameters Privacy parameter e', number of interactions T.
3: Randomly initialize policy nn-
4: dp = (s0).
for = 0. ,,.... do
āt (- (r))
Receive 8141 P(. s1: ā.).
5t-1 (M+())))).
Fr = --5411 aa).
10: T++1 + (Lt az, Fz, 8041) m.)
11: end for
4 Differentially Private Reinforcement Learning
Our solution for differentially private reinforcement learning presented in Algorithm [ It is meta algorithm that takes as input MDP environment M, reinforcement learning algorithm RL, privacy mechanism M, and parameters (c, and T that specify the level of privacy that should hold over T" interactions between the agent and the environment. The RT. algorithm can be any method that takes transition sample (s, a',,,,,' s') and a policy Told and outputs a new policy Nnew = RL((s, a, s'), Tota). (Appendix C describes a concrete using DQN as the RL algorithm.)
instantiation of Algorithm [
Our approach is privatise the inputs before the RL algorithm receives them. We begin by first showing that Algorithm | satisfies the privacy guarantees specified in $ $3.2 We then characterize the resulting control problem under our privacy approach before providing a utility bound.
4.1 Privacy Analysis
Algorithm [ is constructed using differential privacy tools to satisfy (c, diiffferrnt privacy under T-fold adaptive composition. Since an individual's data is used at each time t to output state 8t, need to privatise and ensure that all functions that take 8, as input are also differentially private. Algorit | does this by privatising every state using an e'-differenially private mechanism (lines 4 and 8). For instance, the Laplace mechanism with scale parameter 2/Ne' (since Ag 2/N) would satisfy e'ddifferential privacy. As the state space discrete and bounded, we also ncod project the output from the Laplace mechanism back to the closest element in the state space. (See Algorithm for more details.) The projection operation is guaranteed to be differentially private by Lemma 2
Lemma 2 mechanism and f: Y an arbitrary function. Then the composition M is (e, -ddifferrentt private.
(Dwork & Roth 2014)). Let M: X" Z be an (c, (c.0))differential)) private
In Algorithm [ the action å; is selected using the current policy with the privatized state š, as input at every time step (line 5) Once the next state 8441 is sampled, is immediately privatized to 8 (lines 7 and 8. The agent then receives reward F; = r((++1,, at). Since the action a and received reward F are functions of the privatized state, they are also guaranteed private by Lemma Thus, the entire transition sample received by the RL algorithm e'-differentially private.
Lemma 3 now states the cumulative privacy guarantee T interactions.
Lemma 3 (T-fold adaptive composition (Dwork et al.) 2010 Dwork & Roth 2014 For all 6,8 2 0, the class of (e', -dddf"diiffernntiaaly private mechanisms satisfies (e, T ddffferrrnl privacy under T'fold adaptive composition for:
e =
/2T + Té'le" 1).
(5)
Combining Lemma
Lemma and Lemma 3 then yields the following result.
8

---

Published in Transactions on Machine Learning Research (12/2024)
Theorem 1. Algorithm 1 lently (c, -ufffffffrss prinacy with porameters (8, Q. Q) defined in $ 3.2
sotisfies deiffeeiietlt privacy under T-fold adaptive composition, and equiva-
Truthfulness in Data Collection A related question to privacy protection is an individual's willingness to honestly disclose her data to the data curator. For example, in the context of epidemic control, each individual may have utility function S + [0, 1] mapping states to positive real number, with states that represent high infection rates assigned lower values because they are, perhaps, more likely to attract a mandated lock-down of the community. Would an individual who is sampled for data collection gain an advantage by misreporting her true infection status?
Definition 4. Given (randomized) mechanism M : S - S, truthful reporting is an e-approximate dominant strategy for individual i with utility us and status if, for every dataset D and every & xs
E Mo- (,( 2 E.)MM(((D(())))) (<(0) -c
If truth reporting is an e-dominant strategy for every individual in the population, we say M is e-apprxximately dominant strategy truthful.
In McSherry & Talwar 2007 the authors show that any (e, Oddifferrrrl private mechanism is approximately dominant strategy truthful, which we can see by noting that
Bo--M(((DU(a.)) uz(0) = Σ u(o)P(M((DD( 0) Σ
(u.)) = 0)
= Bo--Mi(DDUUu (0( 2 E.-MG(DUUO)) u,(0) c.
The first inequality follows from Definition 1 The second inequality follows by noting that for e < 1, 2 1-6. Note that the argument does not work for (e, diffferrettil private mechanisms where >> Algorithm uses only (e, 0) differentially private mechanism in lines 4 and g
4.2 Utility Analysis
We now analyze the utility of our DPRL approach and present theoretical result that bounds the approxi- mation error of the optimal value function under privacy from the true optimal value function. The analysis we provide is asymplotic in nature and serves as an important step in establishing that good solutions are possible in our problem setting.
Whilst our approach to privacy in Algorithm ! makes easy to guarantee the differential privacy of any downstream RI. algorithm, the learning and control problems are made more difficult. the true underlying process is now unobservable to the agent. Figure 2 visualizes the graphical model under approach and highlights that the state, privatized states and actions evolve according to partially-observable markov decision process (POMDP).
Unoberrvale:
80
Observable
Figure 2: A graphical model of the underlying state and action sequence under differentially private reinforcement learning approach. The true states are unobservable.

---

Published in Transactions on Machine Learning Research (12/2024)
One subtle difference between POMDP and our privatized system however is that the observed reward is not a direct function of the underlying state as that would constitute a privacy leak. The typical methods for solving POMDP problems resort to computationally expensive state-estimation techniques or sampling based approximations (Monahan 1982. Shani et al. 2013 Kurniawati] 2022). Instead, we analyse the approximation error when standard MDP RL a algorithms are applied directly on the observed privatized states without. resorting to state-cstimation. The analysis is done under several assumptions.
Assumption (Ergodicity).. The underlying MDP environment ergodic (Puterman 2014). An ergodic MDP ensures that stationary distribution over states well defined under any stationary policy.
Assumption is a necessary tool when analyzing the asymplotie performance of RL algorithms and is commonly used to ensure that every state-action pair is visited infinitely often (see e.g. (Singh et al. (1994)). Assumption 2 (Lipschitz dynamies). For all 8, E S, E A, there exists L > 0 such that
|((-)s,)) - P(-1s',a)1, S L ||s -
Since the privatized environment evolves as a POMDP, the distribution for the privatized state & will in general depend on the entire history of observed states, actions and rewards. However, when an MDP RL algorithm is directly applied on top of privatized states, the transitions between privatized states are assumed to be Markovian. The induced transition model will however depend on the asymptotic state distribution under behaviour policy generating interactions. For our analysis, we consider an off-policy setting where stationary behaviour policy æ generates a sequence of privatized states, actions, and rewards. The induced Markovian transition model px : S x A - D(S) describes the asymptotic transition probabilities and is given by (5
13, a1)
Σ Ux Ex (z, ScES
Σ StLIES
P(s st, 1ishilss,00 Pr, s(+1).
(6)
Here P(M()) =) denotes the distribution of the state privatization mechanism and P(s 88, at) denotes the transition matrix of the underlying MDP. The transition model jr depends upon the behaviour policy æ through the distribution (s $1, āz), which is the asymptotic probability of the underlying state being 8t under a when & is observed and ā, is performed. Using Bayes theorem, it can be expressed as
PM(3
(s 55
Eves PM((1 PM(31 P (s)(a
(7)
(
where (s â) denotes the asymptotic probability of the underlying state being when is performed, and 7. (5lā)= = Eves Pm [ā). To avoid degenerate cases, we will assume that the behaviour policy is stochastic and assigns non-zero probability to every action in all states.
Assumption 3. The behaviour policy π is a stochastic policy where vs S, E A, T(a 8) > 0.
Under Assumptions and 3 the distributions Vn (s @) and 7 are well defined.
Under our privatisation scheme, the induced MDP on top of privatized states is given by AM = (S,A, PT r. Note that the reward function does not change as the received rewards are functions of the privatized states. For any policy स E 11, the Q-value Q² in M satisfies the Bellman equation Q r 7= where (*(s) ( (s)
Our analysis is performed using the projected laplace mechanism detailed in Algorithm The projected laplace mechanism first applies additive noise to the input state as per the standard laplace mechanism. We require that the privacy mechanism we use has the state space as its output domain. Adding laplace noise no longer guarantees that the output will be the state space, and so we take the orthogonal projection back onto the state space. This operation is guaranteed be differentially private by Lemma 2
The projected laplace mechanism satisfies the following tail bound. The proof is provided in Appendix
B
10

---

Published in Transactions on Machine Learning Research (12/2024)
Algorithm Projected Laplace Mechanism
1: Input: state S VES. S
2: Parameters: Privacy parameter sensitivity parameter Aq.
= 5 + 7,, where E RK and for [K], " ~ Lap (2))
arg minzes s -8112
Return 3.
Theorem 2. Let X = (XL,) denote a datasel and let 8 = ((x)) and & = M(s), where M is the Projected Laplace mechanism. Then for all e > O and a > 0,
Nae
P ||s ál 2a a
S K exp
V2N
2V
Other privacy mechanisms were also considered but each have their own shortcomings. The exponential mechanism is a natural choice as it can be configured to output elements of the state space directly but the exponential mechanism impractical to sample from. The output domains of additive noise mechanisms are typically unbounded and need be modified for our problem setting- Whilst other approaches exist to bound the output a particular domain, such as truncating the output (Holohan al. 2020), we find working with the orthogonal projection simplifies the analysis. Another reason for working with the projected laplace mechanism is the fact that it satisfy 'pure' differential privacy (i.e. ò = 0). This is in contrast to mechanisms like the discrete or continuous gaussian mechanism (Dwork & Roth 2014 Canonne et al. 2020) which only satisfy approximate differential privacy (i.e. 6 > 0). Since we use adaplive composition, satislying approximate differential privacy at each time step would lead to the privacy budget increasing linearly with T which undesirable.
Our main utility result is the following bound on the approximation error between the optimal Q value in the underlying MDP M and the privatized MDP M.
Theorem 3. Let M be the MDP encironment and M denote the privotised MDP under an e e-differentially private projected laplace mechanism. Let Q* be the optimal value function in M and Q be the optimal value function in M. Then,
| - 10" so CO(VOOD (- 222K
K
K Kexp (-VNe)
+
Proof. (Sketch) The full proof is given in Appendix but we provide a sketch of the main ideas here.
The Simulation Lemma (Karns & Singh 2002 can be used to reduce the problem bounding the Q-value error to the L error |P... P. 1| between the transition models. Expanding the definition of Ps then allows to split into two terms:
PPa
Pxlll S Σ (a(s1/s,0) SIES
||au
Psu + (onE)
||
Paya (twa)
a) 0) Eenes P(02 81, a) PM ( 82). The first term can viewed as the error due privatising the output state from the transition model and the second term can be viewed as the error due to privatising the input state the transition model.
where P(s'| 81,
The first term is bound by first applying the Bretagnolle-Huber inequality. The KL divergence between P... and P... can be bound by noting that Ps.. is a convolution between the privacy mechanism and the true transition model. The sum in the convolution can be reduced to single element, leading to the bound:
PPa PTll 11 S 2 2 min PM (s)))
11

---

Published in Transactions on Machine Learning Research (12/2024)
where (s denotes the probability of the projected laplace mechanism outputting s' when the underlying state is s'. We can show (s) 2 K exp
2/2K thus yielding bound on term (onc).
The second term is first bound by Č PM Pee - Paiall where Ö' is constant. For 0, let (s(s) = fs' E S : Iss --ssss'lee s'lloo < a+t1//22 be the 20 ball centred on state a. The sum over $1 is then split into (x and its complement (s). The lipschitz property our transition model and the concentration property of the projected laplace mechanism then allow us to bound the sum over (s) and B respectively. Term
(two) is then bound as E.,e (= s, Pssa Pstall ll by O (2K (2Kexp exp (- Noc 2vK
T.Ka
LK V2N
Choosing
K and combining terms then gives the final result. VN
Theorem highlights how the approximation error scales the population sample size N and privacy parameter increase. For given K, the approximation error decreases exponentially quickly e increases and at rate of N- as N increases. Thus, increasing the sampled population size is important factor in attaining good quality solutions for RL in population processes. Importantly, there are components in the upper bound that depend on only one of N or e. This implies that both quantities must be increased to drive the error completely to zero. The bound also highlights that performance will degrade when the number of statuses of interest, K, increases. This is likely function of the fact that the state space is discrete and scales exponentially with the dimension:; its possible that formulating the problem with a query whose range is continuous and as continuous reinforcement learning problem could avoid this issue. Nevertheless, our theoretical result shows the scaling behaviour of the approximation crror and we corroborate this behaviour in our experiments.
5 Experiments
We present empirical results that corroborate our theoretical findings on the SEIRS Epidemic Control problem detailed in $ 3 Our experiments on the Epidemic Control problem are representative of the class of population process environments as alternate problems will primarily differ in their transition dynamics. We encapsulate this by running experiments that vary the graph structure, population size, and transition parameters.
Table 1: Transition parameters for each experiment.
Experiment
B
0.3
0.5
0.143
0.015
2
0.5
0.1
0.15
0.01
3
0.2
0.3
0.1
0.01
We conduct three experiments. Each experiment corresponds to different set of transition parameters for the SEIRS epidemic model (sce Example [] and the transition parameters used in cach experiment are listed in Table I graphical representation of the transition parameters and how they govern state transitions is shown in Figure I. Every run of each experiment conducted over T 2e5 steps and the sample size taken to be 90% of the population size.
In each experiment the Epidemic Control problem is simulated over four large social networks from the Stanford Large Graph Network Dataset (Leskovec. & Krev]] 2014). Table 2 lists the details of the datasets used, including the number of nodes and edges in each graph. These social networks represent reasonable models of social interactions in a population. The state space for each of these models is O(N*), and that is computationally challenging for RL algorithms.
On each graph, the agent has access to actions (Quarantinc(i) : E {0, 0.25, 0.5, 0.75, 1.0)), where Quarantine(i) quarantines the top ith percent of nodes ranked by degree centrality by modifying the interaction matrix in the way described in $ The reward function is given by r(st,a)) (s)((s. + - a)C(a.)
12

---

Published in Transactions on Machine Learning Research (12/2024)
Table 2: Summary of network datasets used in experiments.
Dataset
Name
Nodes
Edges
Slashdot (Leskovec et al. 2009)
82K
82,168
948,464
Twitch (Rozemberczki & Barkar
2021
168k
168,114
6,797,557
Gowalla Cho et al. 2011
196K
196,591
950,327
Youtube Yang & Leskovec 2012
1.1M
1,134,890
2,987,624
and is taken as convex combination between two functions (st) and C(a.). The function I(si) returns the proportion of Exposed and Infected individuals at time L and C(a,) returns the proportion of individuals quarantined by action dg. We set 0.8 in all experiments.
For each graph, we run simulations that vary the population size and the target cumulative privacy budget to see how the RL algorithm's performance changes as these key variables change. For given target cumulattvee privacy parameters 6), we set the per-stop privacy budget as
é' f(, 2 2T 1og(1/0)
(8)
and 8' = 0. Under Lemma 3 setting the per-step privacy budget in this manner only satisfies the larget value of e for certain range of values for 5. As the value of 8 decreases, the gap between the privacy achieved and the target privacy widens. In practice, values under 10 are of interest and we find that this can be achieved when T = 2c5 if 5 < 10-2 -2 For more details see Figure
5 Appendix C
The RL algorithm we use is the DQN algorithm (Mnih et al. 2015 initialized with an experience replay buffer Lin 1992). We refer to its differentially private version as DP-DQN. DP-DQN can only store privatized transitions in its replay buffer. The DQN algorithm and the environment interact in an online fashion and exploration is performed using spsilon-greedy. The projected laplace mechanism was used as the state privatisation mechanism. A full description of the DP-DQN algorithm, a concrete algorithm for computing the projected laplace mechanism, and pepraaaraeeters used is provided in Appendix C
5.1 Results
Pritte award, 62k
Phote IAA/1 166k
KINStS resord 1964
Maay: reword, L:3M
310-
0:05
4.14
4.88
432
0:25
0.5 018
5:50
0.75
100
155
1400
230
+.20
000
025
055
7:00
003 325
550
015
1.0
155
1.2 2an
855
075
3:50
0.15
120
1.5
150
115 7.0
Privto Ei
Privte
P1att: 1961
Klaat reword
4002
4.06
433
0.00
4.1
434
4.25
21000
053
6.5
Sept
1964
40
4.18
430
20p4
14
2824
145
1c5
Figure 3: Private reward received by DP-DQN in Experiment (top row), Experiment 2 (middle row), and Experiment 3 (bottom row).
13

---

Published in Transactions on Machine Learning Research (12/2024)
Figures 8 and plot the private reward and true reward performance of DP-DQN across all experiments. In each plot, we compare the performance of DP-DQN under differential privacy as is varied against the default performance of DP-DQN under no privacy. Each curve displays the mean and standard deviation over five random sceds. The privacy paramcter 5 was kept fixed across all runs at = 10-5. In all plots, the blue curve indicates the default performance of DP-DQN without differential privacy. Note that the blue curve does not change between the corresponding true reward and private reward plots.
The plots in Figure 3 show the performance of DP-DQN increases increases. Notably, the performance clusters close to the default performance under low privacy (i.e. e < 5), and is indistinguishable from the default performance in the 1.1M graph. Additionally as the population size increases, the overall performance also improves. This falls in line with intuition as the noise added under a given privacy parameter has absolute scale and as the population size increases, the relative error due to privacy is much smaller. On the 1.1M graph we additionally plot the performance of DP-DQN under c = 0.1. Thus, the empirical results demonstrate in a finite sample sctting the relationship between performance and the population size and privacy parameters highlighted by Theorem
Tue revard 928
Tue rewad 1e0k
Tue reard. 1966
The moard. J:19
433
4.10
645-
414
4.1
0.0
035
1:50
6.5
LOE
153
L75
3:30
0.0
425
050
0.5
1.5
3.0
135
3000
0.0
925
1.00
035
LO
125
153
Ltt
630
025
3.50
6.5
1/0
1.5
150 175 2:30
Tue revadd 924
The resard
Tue 196
"rue mAsis 1.1V
0.55
0.02
0.2-
4.14
0.00
018-
633
4.00
+000
1955
145
0.55
4.0
4.14
A11
635
2014
632
625
14
165
Maps
145
Figure 4: True reward reccived by DP-DQN in Experiment 1 (top row), Experiment 2 (middle row), and Experiment 3 (bottom row).
Whilst the results in Figure 3 are useful for corroborating our theoretical experiments, it is also important to investigate how the policy learnt under our privacy setup performs. Figure ! plots the true reward received by DP-DQN across different graphs as 6 varies. Overall, DP-DQN's performance increases as increases across all networks. Additionally, performance under privacy is clustered much closer to the default performance across all e values in the 82k and 196k graphs than in the private reward case. The plots for the 1.1M graph show that performance under high privacy is indistinguishable from default performance. The gap in performance between the high privacy setting (i.c. c (0.1, 0.5)) and the low privacy setting the 1.1M graph suggest that in some cases there may be a threshold value for e that needs to be crossed to obtain almost optimal performance. Thus, we find that the policy learnt under our privacy setup can perform well and improves, drastically in some cases, as the privacy budget increases.
6 Limitations and Future Work
One limitation of our thcoretical results is that they are asymptotic in nature. This analysis provides guarantees on the error between the solution under privacy and the true solution without privacy, but does not provide any guidance on whether such solution can be learned. Nevertheless, our empirical results
14

---

Published in Transactions on Machine Learning Research (12/2024)
provide some confidence the solutions found by learning algorithms will scale the way results predict. Also, understanding the asymplotic properties of problem setting is an important first step. Constructing and proving sublinear-regret algorithms in our problem setting is important future work. Additionally, whilst we have shown experimentally that the policy learnt under privacy can perform well, it would be useful to bound this performance theoretically and the subject further investigation.
Whilst our approach to achieving differential privacy is desirable as is agnostic to the RL algorithm itself, it leaves open the possibility that the same privacy guarantees could be achieved by directly modifying an RL algorithm. Such approach may be able to better deal with higher dimensional state spaces, which adversely impact the approximation error, and is one of the limitations of our approach. Our analysis is also performed under some regularity assumptions; removing these assumptions would provide more generally applicable theoretical guarantees and is an interesting topic for future research.
Impact Statement
As reinforcement learning algorithms see wider adoption and begin interacting with humans and their data, issues around protecting privacy become more pertinent. Our work can be seen as providing a promising start and solid theoretical foundation to providing privacy protections in an important problem class where reinforcement learning may be applied in the future.
Acknowledgements
The authors would like to thank Mike Purcell for the many helpful discussions and whiteboard sessions during the early stages of the project.
References
Daron Acemoglu, Asuman Ozdaglar, and James Siderius. A model of online misinformation. Review of Economic Studies, pp. rdad111, 2023.
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. URL https://rttheergbook.ihhtt io, 2022.
Nour Almadhoun, Erman Ayday, and Özgür Ulusoy. Differential privacy under dependent tuples the case of genomic privacy. Bioinformatics, 36(6):1696 1703, 2020.
Mauricio Arango and Lyudmil Pelov. COVID-19 pandemic cyelic lockdown optimization using reinforcement learning. CoRR, abs/2009.04661 2020. URL htttp:://arrd..org/abaa/// 04647
Dan Ariely. Misbelief: What Makes Rational People Believe Irvalional Things. Heligo Books, 2023.
Achraf Azize and Debabrota Basu. When privacy meets partial information: A refined analysis of differentially private bandits. Advances in Neural Information Processing Systems, 35:32199 00:32119-33210, 2022.
Borja Balle, Maziar Gomrokchi, and Doina Precup. Differentially private policy evaluation, 2016. URL http///awwww.rrr/////////.//// 02000
Konstantin Berestizshevsky, Foffi-Emmanull Sadzi, Guy Even, and Moni Shahar. Optimization of resource- constrained policies for covid-19 testing and quarantining. Journal of Communications and Networks, 23 (5):326 339, 2021. doi: 10. 10.23919/ St////N.2000 JCN.2021.00002
Jean Bretagnolle and Catherine Huber. Estimation des densités: risque minimax. Zeitschrift für Wahrschein- lichkeilstheorie und verwandte Gebiete, 47:119 137, 1979.
Ceren Budak, Divyakant Agrawal, and Amr El Abbadi. Limiting the spread of misinformation in social networks. Tn Proceedings of the 20th international conference on World wide web, pp. 674, 2011.
15

---

Published in Transactions on Machine Learning Research (12/2024)
Clément L Canonne. A short note on inequality between KL and TV. arXiv preprint arXto:2202.07118, 2023.
Clément L Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. Advances in Newral Information Processing Systems, 33:15676-15688 2020.
Arthur Charpentier, Romuald Elie, Mathieu Laurière, and Viet Chi Tran. Covid-19 pandemic control:
balancing detection policy and lockdown intervention under ICU sustainability. Mathemattiaal Modelling of Natural Phenomena, 15:57, 2020.
Dawci Chen, Samuel Yang-Zhao, John Lloyd, and Kee Siong Ng. Factored conditional filtering: Tracking stales and estimating parameters in high-dimensional spaces. NXi:22206002172 2022.
Eunjoon Cho, Scth A Mycrs, and Jure Leskovec. Friendship and mobility: user movement in location-basod social networks. In Proceedings of the 17th ACM SIGKDD, pp. 1082-1090, 2011.
Sayak Ray Chowdhury and Xingyu Zhou. Differentially private regret minimization in episodic markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6375-6383, 2022a.
Sayak Ray Chowdhury and Xingyu Zhou. Distributed differential privacy in multi-armed bandits. arXiv preprint trXiv:2206.057 05772, 2022b.
Cédric Colas, Boris Hejblum, Sébastien Rouillon, Rodolphe Thiébaut, Pierre- Yves Oudeyer, Clément Moulin- Frier, and Mélanie Prague. EpidemiOptim: A toolbox for the optimization of control policies in epidemio- logical models, 2020. URL, htttps://arxiv.rrrg/t atrg/abs/2010..0 04452
Michela Del Vicario, Alessandro Bessi, Fabiana Zollo, Fabio Petroni, Antonio Scala, Guido Caldarelli, H Eugene Stanley, and Walter Quattrociocchi. The spreading of misinformation online. Proceedings of the National Academy of Sciences, 113(3):554-559, 2016.
Christos Dimitrakakis, Blaine Nelson, Zuhe Zhang, Aikaterini Mitrokotsa, and Benjamin IP Rubinstein. Differential privacy for Bayesian inference through posterior sampling. Journal of Machine Learning Research, 18(11):1-39, 2017.
Abhimanyu Dubey and Alex Pentland. Differentiallly-rivaae federated linear bandits. Advances in Neural Information Processing Systems, 33:6003 6014, 2020.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3-4):211-407, 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In 3rd Theory of Cryptography Conference, pp. 265-284. Springer, 2006.
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 51st Annual Symposium on Foundalions of Computer Science, pp. 51 60. IEEE, 2010.
Amalic Dyda, Michael Purcoll, Stephanic Curtis, Emma Field, Priyanka Pillai, Kieran Ricardo, Haotian Weng, Jessica C Moore, Michael Hewett, Graham Williams, and Colleen Lau. Differential privacy for public health data: An innovative tool to optimize information sharing while protecting data confidentiality. Potterns, 2(12), 2021.
Evrard Garcelon, Vianney Perchet, Ciara Pike- BukkBBurke, and Matteo Pirotta. Local differential privacy for regret minimization in reinforcement learning, 2020. URL hattps://arxxivoorgaasss wtwp:r/ggaa//rooooo////// htt.b///210007770
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, 2013.
Naoise Holohan, Spiros Antonatos, Stefano Braghin, and Pôl Mac Aonghusa. The bounded laplace mechanism in differential privacy. Journal of Privacy and Confidentialily, 10:1, 2020.
16

---

Published in Transactions on Machine Learning Research (12/2024)
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning,
2002.
Daniel Kifer and Ashwin Machanavajjhala. No free lunch in data privacy. In ACM International Conference Monagement of Data (SIGMOD), pp. 193 204. ACM, 2011.
Daniel Kifer and Ashwin Machanavajlhala. Pufferfish: A framework for mathematical privacy definitions. ACM Trunsactions on Database Systems (TODS), 39(1):1 36, 2014.
Varun Kompella, Roberto Capobianco, Stacy Jong, Jonathan Browne, Spencer Fox, Lauren Meyers, Peter
Wurman, and Peter Stone. Reinforcement learning for optimization of covid-19 mitigation policies, 2020.
URL htttp::/aaraxx..or//a//////////s
Hanna Kurniawati. Partially observable markov decision processes and robotics. Annual Review of Control, Robolics, and Autonomous Systems, 5:253 277, 2022.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection.
http:
//snap. stanford. edu June 2014.
Jure Leskovee, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney. Community structure in large nelworks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathemalics, 6(1):
29-123, 2009.
Li Li, Jufu Cui, Rui Zhang, Hui Xia, and Xiangguo Cheng, Dynamics of complex networks: Malware propagation modeling and analysis in industrial internet of things. IEEE Access, 8:64184-648 64192, 2020.
Yang Li, Michael Purcell, Thierry Rakotoarivelo, David Smith, Thilina Ranbaduge, and Kee Siong Ng. Private graph data release: A survey. ACM Computing Surveys, 55(11):1-39, 2023.
Chonghua Liao, Jiafan He, and Quanquan Gu. Locally differentially private reinforcement learning for linear mixture markov decision processes. In Asian Conference on Machine Learning, pp. 627-642. PMLR, 2023.
Long-Ji Lin. Reinforcement learning for robots using neural networks. Carnegie Mellon University, 1992.
Changchang Liu, Supriyo Chakraborly, and Prateek Mittal. Dependence makes you vulnerable: Differential privacy under dependent tuples. In Network and Distributed System Security Symposium, pp. 21-24. The Internet Society, 2016.
Paul Luyo, Evrard Garcelon, Alessandro Lazaric, and Matteo Pirotta. Differentially private exploration in reinforcement learning with lincar representation. arXiv preprint orXiv:2112.01585, 2021.
Hongzi Mao, Shannon Chen, Drew Dimmery, Shaun Singh, Drew Blaisdell, Yuandong Tian, Mohammad Alizadeh, and Eytan Bakshy. Real-world video adaptation with reinforcement learning. arXiv preprint 2008 1 12858, 2020.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Aneuua IEEE Symposium on Foundations of Computer Science, pp. 94- 143. IEEE, 2007.
Nikita Mishra and Abhradeep Thakurta. (Nearly) optimal differentially private stochastic multi-arm bandits. In Proceedings of the Phirty-First Conference on Uncertainty in Artificial Intelligence, pp. 592-601, 2015.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529 533, 2015.
George E Monahan. State of the art A survey of partially observable markov decision processes: theory, models, and algorithms. Management science, 28(1):1-16, 1982.
Senthilkumar Muthukrishnan, Sumathi Muthukumar, and Vecramani Chinnadurai. Optimal control of malware spreading model with tracing and patching in wireless sensor networks. Wireless Personal Communications, 117:2061- -2-803,. 2021.
17

---

Published in Transactions on Machine Learning Research (12/2024)
Mark Newman, Networks. Oxford University Press, 2018.
Dung Daniel T Ngo, Giuseppe Victri, and Steven Wu. Improved regret for diffcrentially private exploration in linear mdp. In International Conference on Machine Learning, pp.
PMLR, 2022.
Nam P Nguyen, Guanhua Yan, My T Thai, and Stephan Eidenbenz. Containment of misinformation spread in online social networks. In Proceedings of the 4th Annual ACM Web Science Conference, pp. 213-222, 2012.
Cameron Nowzari, Victor M Preciado, and George J Pappas. Analysis and control of epidemics: A survey of spreading processes on complex networks. IEEE Control Systems Magazine, 36(1):26-44) 2016.
Xinlei Pan, Weiyao Wang, Xiaoshuai Zhang, Bo Li, Jinfeng Yi, and Dawn Song. How you act tells lot: Privacy-leaking attack on deep reinforcement learning. In Proceedings of the 18th International Conference on Aulonomous Agents and MulliAgenl Systems, pp. 368 376. IFAAMAS, 2019.
Romualdo Pastor-Satorras, Claudio Castellano, Pict Van Mieghem, and Alessandro Vespignani. Epidemic processes in complex networks. Reviews of Modern Physics, 87(3), 2015.
Sancheng Peng, Shui Yu, and Aimin Yang. Smartphone malware and its propagation modeling: survey. IEFE Communications Surveys & Tutorials, 16(2):925-99) 0009259941111 2013.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic progromming. John Wiley &
Sons, 2014.
Dan Qiao and Yu-Xiang Wang. Near-optimal differentially private reinforcement learning. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent (eds.), Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206, pp. 9914 9940. PMLR, 25 27 Apr 2023.
Wenbo Ren, Xingyu Zhou, Jia Liu, and Ness B Shroff. Multi-armed bandits with local differential privacy. arXiv preprint arXi::2007.011 2020.
Benedek Rozemberezki and Rik Sarkar. Twitch gamers: dataset for evaluating proximity preserving and structural rose-based node embeddings, 2021.
Touqir Sajed and Or Sheffet. An optimal private stochastic-mab algorithm based on optimal private stopping rule. In International Conference on Machine Learning, pp. 5579 5588. PMLR, 2019.
Shai Shalev-Shwartz, Yoram Singer, Kristin P Bennett, and Emilio label ranking by soft projections onto polyhedra. Journal of Machine Learning Research, 7(7), 2006.
Efficient learning of
Guy Shani, Joelle Pinean, and Robert Kaplow. A survey of poset-based POMDP solvers. Autonomous Agents and Auett-Agent Systems, 27:1-5) 51, 2013.
Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits, 2018. URL. https://arxiv org/abs/1810.000 00068
Satinder P Singh, Tommi Jaakkola, and Michael Jordan. Learning without state-cstimation partially observable markovian decision processes. In Machine Learning Proceedings, pp. 284 292. Elsevier, 1994.
Mudhakar Srivatsa and Mike Hicks. Deanonymizing mobility traces: Using social network as a side-channel. ACM conference on Computer and Communiccttions Security (CCS), pp. 628 637. ACM, 2012.
Aristide Tossou and Christos Dimitrakakis. Algorithms for diffcrentially private multi-armed bandits. In Proceedings of the AAAI Conference on Arlificial Intelligence, volume 30, 2016.
Aristide Tossou and Christos Dimitrakakis. Achieving privacy in the adversarial multi-armed bandit. In Procetdings of the AAAI Conference on Arlificial Intelligence, volume 31, 2017.
Sander Van Der Linden. Misinformation: Susceptibility, spread, and interventions to immunize the public.
Nature Medicine, 28(3):460-455 2022.
18

---

Published in Transactions on Machine Learning Research (12/2024)
Giuseppe Vietri, Borja Balle, Akshay Krishnamurthy, and Zhiwei Steven Wu. Private reinforcement learning with PAC and regret guarantees, 2020. URL
2009000000000000000200 09052
Baoxiang Wang and Nidhi Hegde. Privacy-preserving q-learning with functional noise in continuous spaces. Advances in Newral Information Processing Systems, 32, 2019.
Haoran Wang and Shi Yu. Robo-advising: Enhancing investment with inverse optimization and deep reinforcement learning. In 20th IEEE International Conference on Machine Learning and Applications (ICMLA), pp. 365-372. IEEE, 2021.
Bin Yang, Issei Sato, and Hiroshi Nakagawa. Bayesian differential privacy on correlated data. In ACM International Conference on Managemend of Dala (SIGMOD), pp.
ACM, 2015.
Jacwon Yang and Jure Leskovec. Defining and evaluating network communities based ground-truth. In Proceedings of the ACM SIGKDD Workshop Mining Dala Semanlics, pp. 1-8, 2012.
Shui Yu, Guofei Gu, Ahmed Barnawi, Song Guo, and Ivan Stojmenovic. Malware propagation in large-scale networks. IEEE Tronsactions on Knowledge and data engineering, 27(1):170 109,1199,900 2014.
Zhenhua Yu, Hongxia Gao, Dan Wang, Abeer Ali Alnuaim, Muhammad Firdausi, and Almetwally M Mostafa.
SEI2RS malware propagation model considering two infection rates cyber physical systems. Physica A: Statistical Mechanics and Applications, 597:127207, 2022.
Jun Zhao, Junshan Zhang, and H Vincent Poor. Dependent differential privacy for correlated data. In IEEE Globecom Workshops, pp. 1- IEEE, 2017.
Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang. Locally differentially private (contextual) bandits learning. Advances in Neural Information Processing Systems, 15-12300-123111 2020.
Xingyu Zhou. Differentially private reinforcement learning with linear function approxination. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(1):1-22 27, 2022.
19

---

Published in Transactions on Machine Learning Research (12/2024)
Appendix
A
Proof of Lemma
family of mechanisms F satisfics (c, (c.8f-diifrrential privacy under T-fold adaptive composition iff every sequence of mechanisms M Mr), with Mi F, satisfies (e,d)-Pullerfish privacy with parameters (S, Q θ) as defined in Section 3.2
Lemma
1
Proof. We first show T-fold adaptive composition implies (e. 8)-Pufferfish privacy.
Suppose M = iM....,, Mr) satisfies (c, differential privacy under T-fold adaptive composition. Let D 1.T be a random variable denoting the sequence of databases. Given an arbitrary 9, secret os,s, we have for each non-empty R C S.
P(M(21.) yIr (1.))
-EE Σ
P(G XIsT (0)(1)))) Dir (1s,, -V:T)
GuT Xur Durl (u.
< < ΣE Σ
Dir Gur (1 =y:r), (9)
GUT Xur Di.T o(1.8)
where Dir is obtained from Dur by removing individual i's data from De, te R. The inequality from the property of T-fold adaptive composition:
follows
P(M(DIT) - Se. P(M(D(sr) - =w)
max w: P((((D..)=
(10)
Given a Dis satisfying (1,9), we have
P(Drr= Der GI., XIT, ()))
II P -
II 1ET
P(D. D D Lu 0,
TES
Given Dir is obtained from Da.r described above, it satisfies (1.8AR) and we have
P(D1r Pirl GI:T, X1.1, (1.s,)). 0)
II P(D, D2 X1, Tu, 0) 1ER
II rES
P(Ω, D, D. ex,iieT, II 1ET,5
P(D: D. X i
For cach E R, we have
P(D: = D X2, P = D21 X2, L,, 9)
(11)
since, by Equation both the LHS and RHS of [1 are equal to
II M4
II
(1 pt.j).
JEL(() JE[N"]VL.)
We have thus established that
P(Drr = Dr:r Grar, X1.r, (i.5). 8) P(D 1:T = Di.r GETs X1.,, ((,S))))))
(12)
Substituting Equation
12 into 99, and noting that the innermost summation ED.r (o0s)) in can be
rewritten in the equivalent form Di (ow.sw)) allows us to claim
P(M(D = Va. (u.s), 0) 2 vı. (1.rl% 0).
20

---

Published in Transactions on Machine Learning Research (12/2024)
Given 0 E i S [T) and R S S are all arbitrary, have shown M satisfies (c, Pufffrfft privacy with parameters (8, Q ().
We next show (efff-Puff privacy implies T-fold adaptive composition.
Suppose M (M,,..., Mr) satisfies (e, Pulferfish privacy with parameters (8, Q) We show for any pair of neighbouring databases there 0 E θ that preserves differential privacy.
Let Dur be arbitrary sequence of datasets. For each individual in Di.r let Dír be obtained from D by removing individual i's data from Di.r satisfies (i.8) and D'.T satisfies (i.S))))
more of the datasets. Thus, there exists S and R R.C such that
We choose = {(6, Pt,,, Mt,N= Jtn.. to be the following, can be any stochastic population process. For each t E S, define Pt., = 1/2, and Hr, = 1 for each j E Le \ S and Pa, =0 for each & & Lt. And for each & S, define Mt.j for cach j L and Pt,k for each & $ L. Given M satisfies (c, 6) Pufferfish privacy, have for any 01.T:
P(M(DI:) = V1. (t.S), 0) e P(M(( Vı.r (u.)))) 0) +
(13)
((M(D Vur (i.s): f) e P(M(D'..)) yır (L.S))
(14)
+ P(M(DITT) = UIT S P(M(Di..)) |1.T(0) +
(15)
Step 14 follows because of all the dataset sequences that can be generated using 0, only D1.r satisfies (1.S)
and only Pir satisfies (1.S)R)- Step (15 follows because P(o () ((s () = (1)
Choosing 0 e θ in this manner for all neighbouring database sequences and repeating the calculations proves the final result.
In the proof of Lemma D we have only considered neighbouring datasets where an individual's data is dropped. The case when neighbouring dataset D' is obtained from a dataset D by replacing individual i's data with another individual j's data, where is not in D, can be formulated using the following secrets and secret pairs:
(AA LE(TT\S
(1.S) = A
iE Lu
A
i i It
IES
( jEL( (L.)EW
A
iE
A
i4L.)
(s,S(W))
WED
(ENT)(SSW)))))
S' U
U
(ou.))}
8CPHS122
Q' = U
U
U
((...),
SEMTI1211
(ER((E)))ER)EENN) ACSM
In the above, given W = [), define W1 (t (t, W). Using very similar arguments, can show that () differential privacy under T-fold adaptive composition is equivalent to d) Pufferfish privacy with parameters (8', Q O).
For each of the secret pairs (s1, $2) E Q' the Pufferfish privacy guarantecs that
P(s) (6) h < P(s2 M(D = w. P(s2 () $ e..
P(s) (()r)) w.
(16)
By inspecting the proof of Lemma] D is clear that secret pairs that represent an individual having two different status given time cannot be accommodated, and this is consistent with Example 4
21

---

Published in Transactions on Machine Learning Research (12/2024)
B Utility Analysis Proofs
B.1 Laplace and Projected Laplace Mechanism Properties
The mechanism we consider using is the projected laplace mochanism. Denote by Mr the laplace mechanism which outputs 8' - -M2(s) = + (Y,,..., k),, Y; ~ Lap(Ag/e). The projected laplace mechanism outputs = (s) by first applying the laplace mechanism (s) and then takes the & projection back onto the state space, i.e. arg minses || 2'122
A concentration bound for the Laplace mechanism is given follows.
Theorem 4 (Dwork & Roth 2014)). Let Xt = (Xe,))ee, denote a dataset, = ((X,) and s' = -M((s). For 0 and 5 E 10,
K
Ag
P|s--811 811 2 In
S 6.
The following is a simple corollary of Theorem Corollary 1. Let X, (Xr,) denote dataset and let ((x)) and s' Mr(s). Then for >> 0 and O,
Nae 2
P (I|s - sl a) S K exp
We now prove Theorem 2 a concentration bound for the projected laplace mechanism.
Theorem 2 Let X, = (X,,)EL. denote a dataset and let & ((x)) and M(s), where M is the Projected Laplace mechanism. Then for all c and O,
( 11s [|s-5l] all a
1
(-
Nave
P
& K exp
V2N
22K
Proof. First, define PAx (s) arg min ||s - =|ا2 and Ps(s) arg min ||s sll2 the la projections onto the K - 1 probability simplex Ax and the state space S, noting that S C Ak. Letting s' = M,(s),, we can express á as 3 = M(s) Ps(s').
Rather than finding an upper bound on [P[[s 3l 2 a), we instead find a lower bound on IP[[|s al < a). Note that the loo ball of radius a (actually a hypercube) has greater volume than the E ball of radius a. Thus,
P P[ls 51 <a) 2 P(|s $12 <a)
(17)
Now define the following sets:
A s E E |||s - Ps(5')112 a 1
V2N
B = (s' R (ax())) <a}
Note that Ps(s') must be a point that minimizes the ls distance to PAx (s'), as Pax the minimum distance to the simplex AK and minimizing the distance to S thus involves minimizing the distance along Ag from PAR (6'). Also for two neighbouring points 81,82 must have two dimensions # j where 81, 82 N and 81. = 82,1 + N and 81,8 82 for # i,j. Thus
(i.e. 81 f 82 and closest in & distance), we
the minimum distance between two neighbouring points is ||si - s2ll2 = x and Ps(s') can be at most V2N away from PAg (s'). Then for s' E B, we have:
- Ps(s')l) & ||s PAx (s))l2) (s') Ps(s')122
Sa I
V2N
22

---

Published in Transactions on Machine Learning Research (12/2024)
Thus s' E = 8 E A, implying B S A and giving P(A) 2 P(B) equivalently:
-1s-- Ps(' 2 < a+ V2N
1
(1|s Pax (s) < a.)
(18)
Let 8 E [0. 3] denote the angle between s -- s' and the plane AK. Since PAx (s') is the orthogonal projection,
have ||s - s'1l2 ||s Pax (s' 1l2 cos (0). Then we have:
PP [[] Pax (8') (8')l2 a)) P (Ils 8'112 aos coco0-11(0) (0))
acoss acoos-100) (0) (a) PP ||s 5'1000
VK
a cos (() K
||s s' 5'1100
(6)
Nax COS
(0)
2 11-
K exp
(19)
2
where (a) follows {s' RK I|ss -|s- s' /a/v/j S fs' ||s- - 1112 a} the former is a hypercube
with side length 2a/v sitting completely inside the l ball of radius and (b) follows by Corollary |
Combining
17
18 and
19 then gives us:
P(|s- ||s
00 < a
2 -
Kexp
Nac 2VK
V2N
where we drop cos (0) as cos (0) E [1] for 0 [0, 3.. Thus, we have:
1
PP ||s - k1 2 +
1
||s (5-5äly -11000 <at
V2N
V2N
Nac
K exp
2
B.2 Additional Lemmas
The Simulation Lemma Kearns & Singh 2002 Agarwal et al. 2022 lets bound the value function error in terms of the error in the transition functions.
Lemma (Simulation Lemma). Let M (S, A. r. P.7) and M (S,Ar P,y) be two MDPs that differ only in the transition model. Given policy n, let Q" be the value function under n in M and Q" be the value function under in M. Then for all π
Q2Th - Q² 11.0 -
(P-PP)
Lemma (Lipschitz preservation under convolution). Suppose f L-Lipschitz function and is a function such that f d(x)dr 1 and ((x) 2 0 for all Then f * is also T-Lipschitz function.
Proof.
lla()) - -0(=)) s / (f(2 (((2+)) f(z' x))o())dz)
- / [[(=+ x) f(= x))l olo)dr
S L 2|2 2/11 / ((z)do
|| z'1l
23

---

Published in Transactions on Machine Learning Research (12/2024)
B.3 Proof of Theorem
3
Theorem 3
Let M be the MDP environment and M denote the privatised MDP under an e-differentiall private projected laplace mechanism. Let Q be the optimal value function in M and Q be the optimal value function in M. Then,
110- -0-10 so c0(Voss) (
K VN
222K (-2V2K)
K Kexp (-VNe) +
Proof. We have
as) -s)
sup Q" - sup (s,
sup Q" (s. a) i²
sup | 20
(20)
Then
20 can be bound with Lemma 4 For any policy ग and any behaviour policy satislying Assumption
10
(|(P P=)V=
7
max || Psn
P V x
s,a
y max
max ) 8.0
|Pa.
px
(21)
In the above, 1a is as defined in 6 and denotes the transition model in M under behaviour policy x. Writing P(s'| $1. 0).0) = Σ P(s2 $1, (M 82), we have, for any s, a,
Psa ps |||||
Psa Σ
(51 s, a.
S1ES
Σ (=(8118,0)) Psa Σ
V= 8, P
FLES
#1ES
Va(8i s5 || Payelli
Σ (s s,
Pea Peu 1 +
Peu - Parall
$ISS
(one)
(bwa)
where the last two steps follows from the triangle inequality and splitting Pxa P P= The first term can be viewed the error due output privatisation and the second term can be viewed the error due input privatisation. We will look to bound the two terms separately.
Term (one)
By the Bretagnolle- Huber inequality (Brttgnolle & Huber 1979
Canonne 2023
term (one) can be bound
as:
P.. - Peall $2 1 Cap(--DK(C Poa).
24

---

Published in Transactions on Machine Learning Research (12/2024)
The KL divergence term can be lower bound follows:
Ps ps
(Dxx(Psa
Poa)
Σ sLES
sa
log
Emes PM((s'
P
Pma
pd
sa log
Ps
S'ES
PM(s' ss)
Σ s'ES
ps'
sa log
(22)
Pe
Σ E'SS
pe' sa log (M (5)
2 min log P PM s')
S'ES
Here (22 follows shrink the sum to just when $2 s'.
Note that (s is smallest when s' is an interior point as it has the smallest subspace of IR that projects back onto itself. So let s' ESS \ as denote an interior point going forward. Thus term (one) can be bound as:
Pea - Psall S $2 PM((' 8*)
(23)
We now look to lower bound (s (8"). Letting R(s') denote the subspace that projects onto s', PM (s)) can be expressed as
PM(6'1 = (s (s)))(s')
= - (SER(E))
Ne K
||s (-Ne Ne (-2
o'Ih) ds.
exp
Let 8 = 1 and (3((')== = E ||s s'112 S 6}
denote the la ball of radius 6. Clearly, all points inside
V2N (53 are closest to compared to any other point in the state space. Also, we have that (3((') S R(s'). Integrating, we get:
Ne
K
Ne 2
(M E R(d')ss)) [SER(E))
exp
||s
81111
ds
4
Ne
Ne
|s; s/5 ds
exp
4
2
Let 8x 8/VK. We now integrate over Csx(x') =
x
K
18/ - 8K, o6 + 5K] to get lower bound
Cop (x') C (I'). The integral is then:
K
Ne
Ne
(M E R(s')(s)2
II
exp
|s;
ds
(EBB(+))
4
2
1=1
Nc
Ne
II
exp
|t
2/2
ds
SEC
(af)
i=1
4
2
K
Ne
Ne
exp
|s;
s
ds
2
K
.8k
Ne
(-
Ne
cxp
|sa|
dsi
4
2
-8x
25

---

Published in Transactions on Machine Learning Research (12/2024)
K
II (1
xxp(=)0xx)
(24)
[=1
k
1 exp
exexp
2/2K
c
2 K exp
(25)
2V2K
where step
24
follows by noting that for, all a 0
a 6k exp (a)) a (f.00 exp (-axr) dx = exp(-add
a
exp(-cxdx)
2
-x
and setting Ne/2, and step (25 follows by noting that for all [0, 1], (1 p)c 2 1 kp. Substituting into equation
23 gives the following bound on term (one):
Σ un s) PPs. - -Poall 22V1 Pm(5'60
=2 2/ 1 1 Kexp (I-exx
2/2K
2 K exp
E
(26)
222K
Term (two)
Using equation
7
have;
PM((s 81 (1 a) || - Psja
Σ 8
(81 (8 Pssa - -Piall = Σ
1z(510) a)
S1ES
< HH
PM(( [[(s|ss] 81) |P - -P.all
8168
PM(s 51)
H
PM( ()) |Pa Pajall
PMr(1 [s)
HC Caax
Σ PMi(1 (8) P PPPa-ll
Psiall,
8.ES
where max, [a(s/a]
(a)sila) and Cuux max
PM 81) PM 8)
We now look to bound E. (M 1s) Psaa Patallr- For 0, define the fo ball of radius = V2N around state 8 and its complement as:
s'1 () (s) = (s' E S: ||s -lll 2 8).
(s) = (s' E : --s-
26

---

Published in Transactions on Machine Learning Research (12/2024)
Splitting E., Es PM (s) Pso Psiall, over Bs(s) and Bī(s) gives us the following bound:
Σ PMM(slls]|E) - Poiall1
Σ Pu(Ssl8)||Pa (1EBg(s)
Pssalli+ Σ
-Psjall
s1EBg(s)
Nae
LK3 + +2 exp
exp
(27)
2vK
Nave
LK
2K exp
+ LKa + V2N
(28)
2vK
The first term in inequality 227 follows by noting that P is L-Lipschitz by Lemma 5 and Assumption 2 and
that, for all & E RK ||=|| & | The second term in inequality 27 follows by noting that the b norm
between distributions is bound by and applying Proposition 2 Picking
2vK
gives us
vN
Σ PM(si Pmo Paialli 5o coKesyy Keepp (-VNe) K FI
VN
Thus the final bound on term (two) is:
Σ
(s1 PPa) Paia so K Kexp (-VNe)+ +
K3/2
(29)
VN
ES
Combining 26 and 29
and picking the higher growth rate terms gives the final result.
C Implementation Details
20
target
6=10-1
6 6=10-²
Achieved e
15
5=10
10-1010
10
5
0
5
10
15
20
Target
Figure 5: Target privacy privacy achieved under equations ( and {8) d is varied. T 2e5.
Figure 5 plots the curves for Equation g as function of for different and T 2e5 and shows that decreasing the value of 8 increases the gap between the privacy achieved and the target privacy. Target values under 10 can be achieved for 8 = 10-2
Our experimental results use a concrete instantiation Algorithm with DQN Mnih et al. 2015 and epsilon-greede for exploration. We display the full algorithm details in Algorithm
The state privatisation mechanism used is the projected laplace mechanism. We provide particular instantiation of Algorithm in Algorithm 3 Algorithm works by first performing projection onto the
27

---

Published in Transactions on Machine Learning Research (12/2024)
simplex using the sorting method from Shalev-Shwartz et al. (2006) before finding the nearest point in the state space. The sorting method has complexity O(K log K) and finding the nearest point in the state space can be done in O(K).
Algorithm 4 has few minor differences to Algorithm [ Firstly, the algorithm takes the target cumulative privacy parameters as input instead of the per-step privacy parameters. The per-step privacy budget is calculated in line 5 Lines 10-21 of can be considered the RL algorithm in Algorithm [ expanded. The replay buffer and target network are written such that they not part of the RL algorithm itself. This is done to make clear that the buffer and target network maintain state across all iterations. Finally, DQN returns value function instead of policy. This is minor change however the policy used is simply the epsilon-greedy policy with respect to the returned value function.
The parameters used in each experiment are listed in Table 3 The neural network used in all experiments was layer, fully connected MLP. The learning rate (a) not listed as we use the default settings of the RMSProp optimizer in PyTTorhh optimize the neural network.
All experiments were performed on shared server with 32-Core Intel(R) Xeon(R) Gold 5218 CPU, 192 gigabytes of RAM.. A single NVIDIA GeForce RTX 3090 GPU was also used.
Table 3: DP-DQN parameters used for every experiment.
7
T
B
D
Estart
0.999
2c5
128
800
0.9999
10-5
Algorithm Ez-projected laplace mechanism
Input: state E S R Parameters: Privacy parameter e, population size N.
='= + 7), where E R and for i E [K], ` Lap 2 Sort s' = (s....., s'x) in descending order: $/11
Ne
5 [n)
Define (mm) = Em (())-)) -1)
6: Compute p = max m [K] mmm)) - (mm) > of
Compute 5 where 5; = max 8/ x (p))
Compute e RK where e, I2 5; and I; arg minnes, 5y| for {0, N.
N-1
- 1}.
9: Find J C [K] with |J] = K that minimizes /Eies eg. Let j = [K] \ and set ej = EieJ Ci.
10: return +
28

---

Published in Transactions on Machine Learning Research (12/2024)
Algorithm Differentially Private DQN (DP-DQN)
1: Input: Environment M = AS, ?), initial state E S, privacy mechanism M 8 x R S. 2: Parameters: cumulative privacy parameters (e, 6), time horizon T, batch size B, target update step D, population size N, learning rate a, initial cxploration rate Estart < 1, decay rate K <
Initialize: nelwork parameters randomly, larget net parameters 0 0, Ceaplore Estart-
Buffer 0
c' 2
6: án (.))
7: for = 0, 1. T do
p ~ Uniform((0, 1))
if p Eeaplore then ā. arg max, Qo(5e, a) else Uniform(A).
10: Receive $1+1 P(- sc,
11:
8t-1 = -Me(()+1).
12:
Fr = at),
13: Append (3r, āz, Fr, 8(+1) to Buffer.
14:
if t B then
15:
for i 1....,,B B do
16:
(s, 0, s'), Uniform(Buffer). y/ + max, Qa(s'aa).
17:
f, - (Q a) yz)²²
18:
19:
end for
20:
Run one step SGD 0 t A a Ef ej.
21:
end if
22:
if f mod D = then
23:
Update target network parameters + 0.
24:
end
25:
Eezplore + 0.03 + (Estant - 0.03) -st
end for
29


Reviews:
[{"review_id": "vowGT9pC6T", "reviewer": "Reviewer_1uT5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The paper is written very well. The introduction, relevant works, and technical preliminaries are complete and concise. \n- The meta-algorithm is presented in full generality, and sufficient detail is provided in the empirical results for the reader to understand a tangible instantiation of the method.\n- The technical analysis is thorough and relevant proofs are clear. The analysis appears to be correct on initial inspection.\n\nWeaknesses\n- The asymptotic result requires both $\\epsilon$ and $N$ to grow large. This asymptotic result would be much stronger if this result would hold when only $N$ grows large. Although I am not an expert in DP, this seems like a weak result because of this. \n- The empirical evaluation is limited in the number of problems considered. Specifically, only the SEIRS problem is considered on 3 graphs.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider the problem of differential privacy in RL algorithms on population processes and provide a meta-algorithm with asymptotic guarantees. The authors provide empirical results that demonstrate the effectiveness of this method on 3 real graphs which gives credibility to their claim that the algorithm is useful in fixed time.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Since the technical analysis does not offer any fixed-time guarantees, I believe that the empirical results need to be a bit more extensive. The presentation of the empirical results is clear and details are provided, but in its current form, I only have confidence in the main result holding for the SEIRS problem. Empirical evaluation on other problems would give more confidence in this result holding elsewhere. Alternatively, if the SEIRS problem encompasses most population processes this should be more clearly stated.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TriqxvUuQL", "reviewer": "Reviewer_x386", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem seems relevant and it provides an interesting insight on differential and Pufferfish privacy for population processes.\n\nThe proposed algorithm is reasonable, but there is no significantly new idea in it.\n\nMy main concern regards the reward function. The reward function is computed by the learning agent, which is already unorthodox, since the reward is usually provided by the environment in reinforcement learning. This choice is less problematic though. The bigger problem is that reward depends on the privatized state. Given that the reward is computed by the learning agent, which is not trusted, this seems a natural choice. However, because the bound on the optimal Q-value considers the difference between the optimal Q-value corresponding to the 'true' states and the the optimal Q-value corresponding to the 'privatized' states, the bound becomes meaningless. It is quite easy to see that it is possible to design a privatization function that maximizes the reward function while giving no information out (the state becomes a constant vector that achieves the highest regret). It would probably better to bound the difference between the optimal Q-value in the original MDP and the expected 'true' reward achieved by the policy that is optimal in the privatized MDP.  \n\nAnother issue is that the setting is one of online reinforcement learning, where one would be expected to analyze the regret of the algorithm, i.e. a bound on the cumulative reward.\n\nThe experiment suffer the same problem that it is comparing average reward corresponding to different reward functions, therefore an algorithm might achieve higher average reward because it is performing better, but also because it works with a more favorable reward function.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers privacy preserving reinforcement learning where the state space consists of some aggregation of the nodes of an evolving graph. The actions influence the edges of the graph, which in turn influence the evolution of the state of the nodes. The paper advocates the use of Pufferfish privacy that seems to capture better the correlated data in the population than differential privacy. A differentially private reinforcement learning algorithm is proposed that treats the (online) reinforcement learning algorithm as black box. The algorithm induces privacy by adding noise to the state (i.e. the aggregated statistics). The algorithm is shown to achieve differential privacy and Pufferfish privacy. Moreover, an asymptotic bound is proven for the drop in the optimal Q/value depending on the privacy level. Empirical analysis on some standard networks using DQN as learning component demonstrate the behavior of the privacy preserving algorithm, showing that the average reward does indeed depend on the privacy.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Even if the reward is computed by the agent, the theoretical analyses and the experimental evaluations should be in the realm of the true reward function.\n\nThe presentation of the setting implies that the agent actions have direct influence on the edges of the graph, e.g. quarantining an individual. That would seem to be a clear breach of privacy (the agent should not know the state of a node). I could understand a more indirect influence, like changing the quarantining rules, which if acted upon by the trusted owner of the data could indeed lead to limiting the edges of a node. This issue should be clarified by the authors.\n\nI the intended RL setting is online, then this issue should be highlighted and the appropriate theoretical discussion should be provided.\n\nThe experiments do not include any baselines. I understand that this is a fairly different setting than the existent private RL dealt with, but perhaps more effort could have been made to include some baseline that are possible to adapt to the setting at hand.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CoNCh80yPT", "reviewer": "Reviewer_K4Lb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nExtensive experiments based on different parameters.\nClear explanations of basic concepts.\n\nWeaknesses:\n\nShort of using the latest datasets, the latest dataset that this paper uses is 12 years old, and there are some newer datasets available.\nLack of comparison with other similar works that use DP and RL", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a theory that reinforcement learning can be introduced with privacy-preserving for population processes, and experiments validate this idea.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please add some newer dataset.\n2. Add some comparisons with other works.", "broader_impact_concerns": "I do not see any broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two reviewers recommended an accept and one reviewer leaned towards a reject.
Decision: Accept (poster)