Differentially Private Reinforcement Learning with Self-Play
Authors: Dan Qiao
Yu-Xiang Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: differential privacy
multi-agent reinforcement learning
trajectory-wise privacy protection
Primary area: privacy
TL;DR: We study multi-agent reinforcement learning with the guarantee of differential privacy.

Abstract: We study the problem of multi-agent reinforcement learning (multi-agent RL) with differential privacy (DP) constraints. This is well-motivated by various real-world applications involving sensitive data, where it is critical to protect users' private information. We first extend the definitions of Joint DP (JDP) and Local DP (LDP) to two-player zero-sum episodic Markov Games, where both definitions ensure trajectory-wise privacy protection. Then we design a provably efficient algorithm based on optimistic Nash value iteration and privatization of Bernstein-type bonuses.  The algorithm is able to satisfy JDP and LDP requirements when instantiated with appropriate privacy mechanisms. Furthermore, for both notions of DP, our regret bound generalizes the best known result under the single-agent RL case, while our regret could also reduce to the best known result for multi-agent RL without privacy constraints. To the best of our knowledge, these are the first results towards understanding trajectory-wise privacy protection in multi-agent RL.

Differentially Private Reinforcement Learning with Self-Play
Dan Qiao
Yu-Xiang Wang
Department of Computer Science & Engineering University of California, San Diego
Halıcoollu Data Science Institute University California, San Diego San Diego, CA 92093
San Diego, CA 92093
d2qiao@ucsd.co
yuxiangwQucsd.
Abstract
We study the problem of multi-agent reinforcement learning (multi-agent RL) with differential privacy (DP) constraints. This is well-motivatee by various real-world applications involving sensitive data, where it is critical to protect users' private information. We first extend the definitions of Joint DP (JDP) and Local DP (LDP) to two-player zero-sum episodic Markov Games, where both definitions ensure trajectory-wise privacy protection. Then design provably efficient algorithm based on optimistic Nash value iteration and privatization of Bernstein- type bonuses. The algorithm is able satisfy JDP and LDP requirements when instantiated with appropriate privacy mechanisms. Furthermore, for both notions of DP, our regret bound generalizes the best known result under the single-agent RL case, while our regret could also reduce to the best known result for multi- RL without privacy constraints. the best of our knowledge, these the first results towards understanding trajectory-win privacy protection in multi-agent RL.
Introduction
This paper considers the problem of multi-agent reinforcement learning (multi-agent RL), wherein several agents simultancously make decisions in unfamiliar environment with the goal of maximiz- ing their individual cumulative rewards. Multi-agent RL has been deployed not only in large-scale strategy games like Go [Silver al. 2017], Poker [Brown and Sandholm 2019 and MOBA games
(Ye et al. [2020]. but also in various worldw applications such as autonomous driving [Shalev. Shwartz et [016]] negotiation [Bachrach et al.) [2020), and trading in financial markets (Shavandi and Khedmati [2022]. In these applications, the learning agent analyzes users' private feedback in order to refine its performance, where the data from users usually contain sensitive information. Take autonomous driving an instance, here a trajectory describes the interaction between the cars in neighborhood during a fixed time window. At each timestamp, given the current situation of each car, the system (central agent) will send a command for each car to take (e.g. speed up, pull over), and finally the system gathers the feedback from each car (e.g. whether the driving is safe, whether the customer feels comfortable) and enhances its policy. Here, (situation, command, feedback) corresponds to (state, action, reward) Markov Game where the state and reward of each user considered as sensitive information. Therefore, leakage of such information is not acceptable. Regrettably, it has been demonstrated that without the implementation of privacy safeguards, learning agents tend to inadvertently memorize details from individual training data points [Carlini al. 2019], regardless of their relevance to the learning process [Brown et al. 2021 This susceptibility exposes multi-agent RL agents potential privacy threats.
To handle the above privacy issue, Differential privacy (DP) (Dwork et al. 2006 has been widely considered. The output of a differentially private reinforcement learning algorithm cannot be discerned
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Algecramm Markow danes
Reaell willou paossy
Ropee under JDP
unde Otyi 1 S 17/4
DF Naa VLur Aacrram Nish
Or SAAI)
Otvir SADT I' (SSaBjj
2021
Djv R-SABTT
Lower
BCV S DyT)
B (ISSs amasm))
VISSI DyF y
Algenillma MP
Rogicl wallin poosss
Ropal made
Ragad anike LLDP
PUCB
Viesi et al. 2020
OVV
O(yIsSPAr 4 P'5AAj0"
N.A.
L.P--RI
(VV7557777
Oly St STAy
Privat-UCI-- UCII-1
bowduur 1M 200 0022
0ivTPSAT IPSSARd 0.VIPSA #SSPA/
OIVISAAT + S'AVIT//O)
DP UCBVE
Vua and Walg
O'iisaa + STAVPTI
Table 1: Comparison of our results (in blue) to existing work regarding regret without privacy (i.e. the privacy budget is infinity), regret under c-Joint DP and regret under c-Local DP. In the above, S is the number of states, A, B are the number of actions for both players, is the planning horizon and K is the number of episodes (T = HK is the number of steps). Markov decision processes (MDPs) is a special case of Markov Games where B 1. *: This result is the best known regret bound when there is privacy concern. More discussions about this bound can be found in Chowdhury and Zhou [2022] f: The original regret bound in Garcelon et al. [021]] is derived under the setting of stationary MDP, and can be directly transferred to the bound here by adding vH to the first term. f: This algorithm achieved the best known results under single-agent MDPs, and our Algorithm I can obtain the same regret bounds under this setting.
from its output in an alternative reality where any specific user is substituted, which effectively mitigates the privacy risks mentioned earlier. However, it is shown (Shariff' and Sheffet 2018 that
standard DP will lead to linear regret even under contextual bandits. Therefore, Vietri et al. [2020]
considered a relaxed surrogate of DP: Joint Differential Privacy (JDP) (Kearns et al. 2014] for RL.
Briefly speaking. JDP protects the information about any specific user even given the output of all other users. Meanwhile, another variant of DP: Local Differential Privacy (LDP) [uuchi al. 2013]
has also been extended to RL by Garcelon et al. 2021 I] due to its stronger privacy protection. LDP requires that the raw data of each user is privatized before being sent the agent. Although following works (Chowdhury and Zhou 2022 Qiao and Wang 2023] established near optimal results under these two notions of DP, all of the previous works focused on the single-agent RL setting while the
solution to multi-agent RL with differential privacy is still unknown. Therefore we question:
Question 1.1. Is it possible to design a provably efficient self-play algorithm to solve Markov games while satisfying the constraints of differential privacy?
Our contributions. In this paper, we answer the above question affirmatively by proposing general algorithm for DP multi-agent RL: DP-Nash-VE VI (Algorithm Our contributions are threefold.
We first extend the definitions of Joint DP (Definition) 2.2) and Local DP (Definition 2.3 to the multi-agent RL setting. Both notions of DP focus protecting the sensitive information of each trajectory, which is consistent with the counterparts under single-agent RL.
We design new algorithm DP-Nash-VI (Algorithm [ based on optimistic Nash value iteration and privatization of Bermstein-type bonuses. The algorithm can be combined with any Privatizer (for JDP or LDP) that possesses corresponding regret bound (Theorem 4.1) Moreover, when there is no privacy constraint (i.e. the privacy budget is infinity), our regret reduces to the best known regret for non- non-private multi-agent RL.
Under the constraint of e-JDP, DP-Nash-VI achieves a regret of D(VH2SABT 5² AB/e) (Theorem 5.2p. Compared to the regret lower bound (Theorem 5.3 the main term is nearly optimal while the additional cost due to JDP has optimal dependence on Under the c-LDP constraint, DP-Nash-V VI achieves regret of D(VH2SAD + S2 ABB (AB/HTT/e) (Theorem 5.5), where the dependence on K, is optimal according the lower bound (Theorem 3.66). The pair of results strictly generalizes the best known results for single-agent RL with DP [Qiao and Wang 2023
1.1 Related work
We compare our results with existing works on differentially private reinforcement learning [Vietri et al. 2020, Garcelon et al. 2021 Chowdhury and Zhou| 2022 Qiao and Wang 2023 and regret minimization under Markov Games (Liu et al. [021]] Table I while more discussions about differentially private learning algorithms are deferred to Appendix A Notably, all existing DP RL

---

algorithms focus on the single-agent case. In comparison, our algorithm works for the more general two-player setting and our results directly match the best known regret bounds (Qiao and Wang when applied to the single-agent setting.
2023
Recently, several works provide non-asympiotic theoretical guarantees for learning Markov Games. algorithms in MGs based on optimistic value iteration, and the result improved by Liu et al. [202I) using model-based approach. Meanwhile,
Bai and Jin [2020) developed the first provably-
model-free approaches are shown to break the curse of multiagency and improve the dependence on
action space (Bai et al. 2020 Jin et al.
2021 Mao et al.
2022 Wang et al. 2023 Cui et al. 2023]
However, all these algorithms base on the original data from users, and thus are vulnerable to various
privacy attacks. While several works [Hossain and Lee 2023 Hossain et al.) 2023 Zhao et al. 2023b]
Gohari et al. [2223] study the privatization of communication between muluple agents, none of them provide regret guarantees. In comparison, we design algorithms that provably protect the sensitive information in each trajectory, while achieving near-optimal regret bounds simultaneously.
Technically speaking, we follow the idea of optimistic Nash value iteration and privatization of Bernstein-type bonuses. Optimistic Nash value iteration aims to construct both upper bounds and lower bounds for value functions, which could guide the exploration. Such idea has been applied by previous model-based approaches [Bai and Jin 2020 Liu et al. 2021] to derive tight regret bounds. To satisfy the privacy guarantees, we are required to construct the UCB and LCB privately. In this work, we privatize the transition kernel estimate and construct a private bonus function for our purpose. Among different bomuses, we generalize the approach in Qiao and Wang (2023 and directly operate on the Bernstein-type bonus, which could enable tight regret analysis while the privatization is more technically demanding due to the variance term. To handle this, we first privatize the visitation counts such that they satisfy several nice properties, then we use these counts to construct private transition estimates and private bonuses. Lastly, we manage to prove UCB and LCB, and bound the private terms by their non-private counterparts to complete the regret analysis.
2 Problem Setup
We consider reinforcement learning under Markov Games (MGs) (Shapley 1953) with Differential Privacy (DP) [Dwork et al. 2006). Below we introduce MGs and define DP under multi-agent RL.
2.1 Markoy Games and Regret
Markov Games (MGs) are the generalization of Markov Decision Processes (MDPs) to the multi- player setting, where each player aims to maximize her own reward. We consider two-player zero-sum // episodic MGs, denoted by a tuple Mg = (S, A, B, H, {P ( $1), where S is the state space with S = |8], A and B the action space for the max-player (who aims to maximize the total reward) and the min-player (who aims to minimize the total reward) respectively with A ==|AA, B = | Besides, H is the horizon while the non-stationary transition kernel Pa (-(-1s, a, b) gives the distribution of the next state if action (a. b) is taken at state and time step h. In addition, we assume that the reward function rh (s, a, b) [0, 1] is deterministic and known]] For simplicity, we assume each episode starts from a fixed initial state sj. Then at each time step h E [M], two players observe 5h and choose their actions ag E A and by B simultaneously, after which both players observe the action of their opponent and receive reward rh (Sh, 4h by., the environment will transit to $h+1 ~ (r an, br).
Markov policy, value function. A Markov policy p of the max-player can be seen as a series of mappings μ {pn ) where each fah maps each state E S to a probability distribu- tion over actions A, i.e. 14 S + A(A). A Markov policy v for the min-player is defined similarly. Given pair of policies (H,r) and time step h E [H], the value function (-) is
defined as V/ (s) = Eu EEn relsh, = s] while the Q-value function (..:)) is defined as Q a, Ey, I E re 1218h, ah, bn. s,a,b) for all s, a, b. According the definitions, the following Bellman equation holds:
Qth (s. a, 6) = [r, + PA PAVAnllss, (s) = 12 V (h,
'This assumption is wlog since the uncertainty of reward is dominated by that of transition kernel.
3

---

Best responses, Nash equilibrium. For any policy μ of the max playerr there exists a best response (1) policy (1) of the min-player such that V/ Vi (s) = inf, (s) for all (s, h). For simplicity, we denote V.a.1 := Valel (n) Also, p² (v) and vil"" can be defined by symmetry. It is shown [Filar and Vrieze, 2012] that there exists pair of policies (u²,"*) that are best responses against each other, i.e. V/ . (s) = Vi """""" (s) = vit" (s), V (s, h) E S x [H]. The pair of policies (n², .V") is called the Nash equilibrium of the Markov game, which further satisfies the following minimax property: for all hs, E S x (H], sup, inf, V/ (s) = V2"" (s) inf, sup,, V (s). The value functions of (**) are called Nash value functions and denote V h.
pa ,² Qi = 0% :"" for
simplicity. Nash equilibrium means that no player could gain more from updating her own policy.
Learning objective: regret. Following previous works Bai and Jin 2020 to minimize the regret, which is defined as below:
Liu et al. 2021]. we aim
K Σ
(51) V (01))
Regret(K) (K)
where K is the number of episodes the agent interacts with the environment and (n* u²) are the policies executed by the agent in the k-th episode. Note that any sub-linear regret bound can be transferred to a PAC guarantee according to the standard online-to-batch conversion (Jin et al. 2018
2.2 Differential Privacy in Multi-agent RL
For RL with self-play, each trajectory corresponds to the interaction between a pair of users and the environment. The interaction generally follows the protocol below. At time step h of the k-th episode, the users send their state sf. to central agent M, then M sends back a pair of actions (af, 6%) for the users to take, and finally the users send their reward rf. to M.. Following previous works Vietti et al. 2020 Chowdhury and Zhou| 2022, Qiao and Wang 2023 here we let 2 (wI,-.. ux) denote the sequence of K unique pairs of users who participate in the above RL protocol. Besides, each pair of
users ug is characterized by the {s% r r= information they would respond to all (AB) MB possible
sequences of actions from the agent. Let M(4) = {(af. bi, denote the whole sequence of actions suggested by the agent M. Then a direct adaptation of differential privacy [Dwork et al., 2006) is defined below, which says that M(U) and all other pairs excluding ug together will not disclose much information about user UA.
Definition 2.1 (Differential Privacy (DP)). For any 0 and ô E [0, a mechanism M u + (A x B) (3 H is (c, () diffferrentill private for any possible user sequences Ui and U' that is different on one pair of users and any subset E of (A B) KH.
P(M(L) E E S e P(((()) E F. +
If 8 0, we say that M is e-differentially private (E-DP).
Unfortunately, privately recommending actions to the pair of users di while protecting their own state and reward information is shown to be impractical even for the single-player setting. Therefore, we consider a relaxed version of DP, known as Joint Differential Privacy (JDP) [Kearns et al., 2014]. JDP says that for all pairs of users Ug. the recommendation to all other pairs excluding uą will not disclose the sensitive information about ug. Although being weaker than DP, JDP could still provide meaningful privacy protection by ensuring that even if an adversary can observe the interactions between all other users and the environment, it is statistically hard to reconstruct the interaction between uk and the environment. JDP is first studied by Vietri al. [2020) under ingle-agent reinforcement learning, and we extend the definition to the two-player setting.
Definition 2.2 (Joint Differential Privacy (JDP)). For any e >> O, a mechanism :: + (Ax K is e-joint differentially private for any k E [K]. any user sequences I and Ut that is different on the k-th pair of users and any subset E of (A x B) 1)H
(U) E S e P(M E E).
2 Uniqueness assumed wlog. as for a returning user pair one can group them with their previous occurrences.
3 At each time step A E [L]]. the agent suggests actions to both players, and thus there are AB possibilities for each time step h.

---

where M=)(U) E E means the sequence of actions sent to all pairs of users excluding Wj belongs to set E.
In the example of autonomous driving. JDP ensures that even if an adversary observes the interactions between cars within all time windows except one, is hard to know what happens during the specific time window. While providing strong privacy protection, JDP requires the central agent M to have access to the real trajectories from users. However, in various scenarios the users are not even willing to directly share their data with the agent. To address such cireumstances, Duchi et al.) 2013] developed a stronger notion of privacy named Local Differential Privacy (LDP). Now that when considering LDP, the agent can not observe the state of users, consider the following protocol specific for LDP: at the beginning of the k-th episode, the agent M first sends a policy pair Ta (14, to the pair of users Ug. after running тT and getting trajectory Xk. Wg privatizes their trajectory to X and sends it back to M. We present the definition of Local DP below, which generalizes the LDP under magll-agent reinforcement learning by Garcelon et al. (2021). Briefly speaking, Local DP ensures that it is impractical for an adversary to reconstruct the whole trajectory of ug even if observing their whole response.
Definition 2.3 (Local Differential Privacy (LDP)). For any E > O, a mechanism M is E- local differentially private if for any possible trajectories X' and any possible set E S
{M(X)]X X is any possible trajectory).
P(M()) -P(M(X)) E E].
In the example of autonomous driving, LDP ensures that the system can only observe a private version of the interactions between cars instead of the raw data.
Remark 2.4. Note that here our definitions of JDP and LDP both provide trajectory-wise privacy protection, which is consistent with previous works (Chowdhury and Zhou [022 Qiao and Wang 2023y. Moreover, under the special case where the min-playe plays a fixed and known deterministic policy (or equivalently, B only contains a single action and B = 1), the Markoy Game setting reduces to a single-agent Markov decision process while our JDP and LDP directly matches previous definitions for the MDP setting. Therefore, our setting strictly generalizes previous works and requires novel techniques to handle the min-player.
Remark 2.5. In the following sections we will show that LDP is consistent with sub-linear regret bounds, while it known that we can not derive sub-linear regret bounds under the constraint of DP. We remark that there is no contradictory since here the RL protocols for DP and LDP are different. As a result, here a guarantee of LDP does not directly imply a guarantee of DP and the two notions are indeed not directly comparable.
3 Algorithm
In this part, we introduce DP-Nash- VI (Algorithm D. Note that the algorithm takes Privatizer as an input. We analyze the regret of Algorithm for all Privatizers satisfying the Assumption 331 below, which includes the cases where the Privatizer chosen as Central (for JDP) or Local (for LDP).
We first introduce the definition of visitation counts, where N a, b) = =' 1 (s),, bj a, b) denotes the visitation count of (s, a, b) at time step h until the beginning of the k-th episode. k-1 Similarly, we let N (s, a, b, b,))) = Σ/= (s), ai, b/,-- 1/.41 = 8, a, b, s') be the visitation count of (h, 8, a, b, s') before the k-th episode. In multi-agent RL without privacy constraints, such visitation counts are sufficient for estimating the transition kernel (Pr, M and updating the exploration policy, as in previous model- approaches [Liu et al. 2021]. However, these counts base the original trajectories from the users, which could reveal sensitive information. Therefore, with the concern of privacy, we can only incorporate these counts after privacy-preserving step. In other words, we use a Privatizer to transfer the original counts to the private version (s, a, b), N% (s, a, b, s'). We make the following Assumption 3.1 for Privatizer, which says that the private counts are close to real ones. Privatizers for JDP and LDP that satisfy Assumption 3.I will be proposed in Section
Assumption 3.1 (Private counts), For any privacy budget c 0 and failure probability 3 E [0. 1]. there exists some Ex,9 > such that with probability at least 1 8/3, for all (h, s, a, b', E
[H] x S x A x
B x S x [K], the Ni (s, a, b, s.) and N& (s, a, b) from Privatizer satisfies:
5

---

Algorithm 1 Differentially Private Optimistic Nash Value Iteration (DP-Nash-VI)
1: Input: Number of episodes K, privacy budget e, failure probability B and Privatizer (can be either Central or Local).
2: Initialize: Private counts NA a, b) = [s a, a,,, 8²) = 0 for all (h, 8, a, b, 8'). Set up the confidence bound Er. w.r.t the Privatizer, the minimal gap A = H and universal constants C1 C2 > 0. L (gg33HSAAK/3))
3: for k 1.2....
do
4:
V (+++(,))
V (-) =0
5:
for h H 1, do
6:
for (s, a, E S x A B do
7:
Compute private transition kernel PA (-1s, a, a, in I
8:
Compute (3, a, -
(V h+1 11++1) a, b).
r 1xh+
Var Var
(9)
9:
Compute b)) =0 C2\ C
CyHSE,, C.H
UCB (s. 1in / ( a. b) (s') + Ir t + [s, a, H}.
10:
11:
LCB (s, = max (s V (6') + |r - 2 [ a. b).
12:
end for
13:
for s S do
14:
Compute the policy =xC, (1) (s) (x,,,,,)))))
(s.
Compute the value functions Vi((s) - E,g (s), [i(s) = Em 2² (t). end for end for
15:
16:
17:
18:
Deploy policy x = ( ... xH and get trajectory (st, at, bt,r (,,,,,... , #422)
Update the private counts to N via Privatizer.
20:
if (V (s1) A then
21:
A= = (t)s) and π Th = (TT T
22: end if
23:
end for
24: Return: The marginal policies of π ou, (ycou, Dou).
(I) (s, a, (s s')l S E. (s, bN as, a.b)] s Ec,g. (s o.
(2) (s, a, b) =ves (s, a, b') 2 (s,
Given the private counts satisfying Assumption 3.1 the private estimate of transition kernel is defined as below.
as,,,,, A (h,
Ph (s'ls,
(s,
Remark 3.2. Assumption 3.7 is a generalization of Assumption 3.1 of Qiao and Wang (2023) the
two-player setting. The assumption (2) guarantees that the private transition kernel Pł (-Is, a, b) is valid probability distribution, which enables our usage of Bernstein-rype bonus. Besides, P is close the empirical transition kernel based original visitation counts according to Assumption (1).
Algorithmic design. Following previous non con-private approaches [Liu al., 2021). DP-Nash- VI (Algorithm 1b maintains a pair of value functions Q and Q which are the upper bound and lower bound of the Q value of the current policy when facing best responses (with high probability). More specifically, we use private visitation counts N to construct private estimate of transition kernel Ps (line 7) and a pair of private bonus 7/ (line 8) and 1 (line 9). Intuitively, the first term of 1 is derived from Bernstein's 's inequality while the second term is the additional bonus due to differential
privacy. Next we do value iteration with bonuses construct the UCB function Q (line 10) and the LCB function Of (line I1). The policy - for the k-th episode calculated using the CCE function (discussed below) and we run & to collect a trajectory (line 14.18). Finally, the Privatizer transfers the

---

non non-private counts to private ones for the next episode (line 19). The output policy xh is chosen as
the policy nh with minimal gap (Vī VV--V (x (line 21). Decomposing the output policy, the output policy (uau ( for both players are the marginal policies of π T i.e. paa (-1s) LbEB Th (. b())
"ft and oa (11s)=Eae. "h (a. -18) for all (h, s) E [#] S.
Coarse Correlated Equilibrium (CCE). Intuitively speaking, CCE of Markov Game is a potentially correlated policy where no player could benefit from unilateral unconditional deviation. As computationally friendly relaxation of Nash Equilibrium, CCE has been applied by previous works
[Xie et al. 2020 Liu et al. 2021] to design efficient algorithms. Formally, for any two functions
2(:-)).0 (..Q(.)) Ax 0, H. CC Q) returns a policy π E A(A x B) such that
((a.b)--Q(aa 2 max E (a.b)= Q(a' (((',)), b), B(a,b)~- Q(a, b) - min [(a,b)-=((a,
Since Nash Equilibrium (NE) is special case of CCE and a NE always exists, CCE always exists. Moreover, a CCE can be derived polynomial time via linear programming. Note that the policies given by CCE can be correlated for the two players, therefore deploying such policy requires the cooperation of both players (line 18).
4
Main results
We first state the regret analysis of DP-Nash-VI VI (Algorithm T based on Assumption 3. which can
be combined with any Privatizers. The proof of Theorem 4.1 is sketched in Appendix B with details
in the Appendix. Note that (p* v²*) denote the marginal policies of π for both players.
Theorem 4.1. For any privacy budget e > O, failure probability 3 [0, and any Privatizer satisfying Assumption 3.1
with probability at least 1 - B, the regret of DP-Nash-V VI (Algorithm) ! is
K
Regret (K)
Σ
Vyti" (51) -1 .t (((""((s)))))))))))) So (VHISABB + S² ABE..).
(2)
k=1
where K is the number of episodes and T HK.
Under the special case where the privacy budget e + oo (i.e. there is no privacy concern), plugging
Fe,g = 0 in Theorem 4.1 will imply a regret bound of D(VH2SABBT) Such result directly matches the best known result for regret minimization without privacy constraints [Liu et al. 2021
and nearly matches the lower bound of Φ(, HH>SAA - B)T) Bai and Jin 2020). Furthermore, under the special case of single-agent MDP (where B = 1), our result reduces to Regret(K) S O(VH2SAT + 52 conditions (Theorem 4.1 of Qiao and Wangl (2023]) Therefore, Theorem 4. is a generalization of the best known results under MARL [Liu et al. 2021 and Differentially Private (single-agent) RL
Such result matches the best known result under the same set of
(Qiao and Wang 2023 simultaneously.
PAC guarantee. Recall that we output a policy nh whose marginal policies are (n²TH " We highlight that the output policy for each player is single Markov policy that is convenient to store and deploy. Moreover, as a corollary of the regret bound, we give a PAC bound for the output policy,
Theorem 4.2. For any privacy budget Privatizer that satisfies Assumption
>> O, failure probability B E [0, and any if the number of episodes satisfies that K Z
3.1
á HSSAB + minn [K' S2 ABE..
S a
with probability 1- 3, (nonr, (out) is a-approximate
a²
K³
Nash, ie,, V.l. (81)
(81) aa.
The proof is deferred to Appendix C.4 Here the second term of the sample complexity bound") ensures that the additional cost due to DP is bounded by (aa). The detailed PAC guarantees under the special cases where the Privatizer is either Central or Local will be provided in Section
Privatizers for JDP and LDP
In this section, we propose Privatizers that provide DP guarantees (JDP or LDP) while satisfying Assumption 3.1 The proofs for this section can be found in Appendix DD.
*The presentation here is because the term És.s is indeed dependent of the number of episodes K.
7

---

5.1 Central Privatizer for Joint DP
Given the number of episodes K, the Central Privatizer applies K-bounded Binary Mechanism CChan et al., 2011] to privatize all the visitation counter streams N (s, b), N b, s'), thus protecting the information of all single users. Briefly speaking, Binary mechanism takes a stream of partial sums as input and outputs surrogate stream satisfying differential privacy, while the error for each item scales only logarithmically on the length of the stream Here in multi-agent RI., for each (h, S, a, b), the stream (NN a, b) = -i-l ((s) d/ bj, = S, a, b) (R((K) can be considered as the partial sums of {1(s), dj b/2 = 8, 6)). Therefore, after observing 1 (s ait by = b) at the end of episode k; the Binary Mechanism will output a private version of > (s). at, Uf 8, a, b). However, Binary Mechanism alone does not satisfy (2) of Assumption 3.1 and a post-processing step required. To sum up, we let the Central Privatizer follow the workflow below:
Given the privacy budget for JDP E > O,
(I) For all (h, a. b, s'), we apply Binary Mechanism (Algorithm 2 in Chan et al. (2011) with input parameter e' = TH K to privatize all the visitation counter streams {NE a) k)]ke[k] and (N% (s, a, b, b,))))k(()) We denote the output of Binary Mechanism by .i..
(2) The private counts N are derived through Section 5.3 with E,,s - O # log (og(HSABK/)))
Our Central Privatizer satisfies the privacy guarantee below.
Lemma 5.1. For any possible e, 3, the Central Privatizer satisfies e-JDP and Assumption 3.1 with
Eg,3 = #.
Combining Lemma 5.1 with Theorem 4.1 and Theorem 4.2 we have the following regret & PAC guarantee under e-JDP.
Theorem 5.2 (Results under JDP), For any possible 3, with probability 1 1- B, the regret from running DP-Nash-V VI (Algorithm)
7
instantiated with Central Privatizer satisfies:
Regret s HSATT + AB/ee./)).
(3)
Moreover, if the number of episodes K is larger than d1( SAB the output policy (n yout) is a-approximate Nash.
SHAAAB with probability
ea
Similar to the aingle-agent (MDP) setting (B 1), the additional cost due JDP is a lower order term under the most prevalent regime where the privacy budget is constant. When applied to the single-agent case, regret matches the best known regret Ö O(VH2SA + ² A/e) QQao and Wang 2023 J. Moreover, when compared to the regret lower bound below, our main term is nearly c.
optimal while the lower order term has optimal dependence
Theorem 5.3. For any algorithm Alg satisfying e-JDP, there exists a Markov Game such that the expected regret from rumning Alg.or K episodes (T = HK steps) satisfies:
[RRegre(K))] 2 H(VHPS((A+ BYT HS(A+ + B)
e
The regret lower bound results from the lower bound for the non-private learning Bai and Jin 2020) and an adaptation of the lower bound under JDP guarantees [Vietri et al.) 2020 to the multi- setting. Details are deferred the appendix.
5.2 Local Privatizer for Local DP
At the end of episode k, the Local Privatizer perturbs the statistics calculated from the new tra- jectory before sending it the agent. Since the set of original visitation counts (s,(s,,)) 1 (s) aft, by s, a, b)) (h. has & sensitivity H, can achieve 5-LDP by directly adding Laplace noise, ie, ā. (s, a, b) = (s, + Lap( 2 Similarly, repeating the above perturbation to (1)),, aft by, s/t = 8, a, b, s')(nnaaad..)) will lead to identical results. Therefore, the Local
Privatizer with budget is as below:
MMor details in Chan et al. 2011 and Kairouz al.
2021

---

(I) We perturb (s. 1( o by - a. and as, - 1 & lb: 1/2 s411
a, b, s') by adding independent Laplace noises: for all (h,
2H
2H o Lap
Lap
(4)
(2) Then the noisy counts are derived according to
k-1 (s = (ss,,, N((s,,,,,))) = Σ
oh (s,,,,,,
(5)
==1
1=1
and the private counts NA are solved through Section 5.3 with E.g = 0 Log(HSABK/DD 3))
Our Local Privatizer satisfies the privacy guarantee below.
Lemma 5.4. For any possible 3, the Local Privatizer satisfies c-LDP and Assumption 3.1 with
F,,3 0 VK).
Combining Lemma 5.4 with Theorem 4.1 and Theorem 4.2 we have the following regret & PAC guarantee under e-LDP.
Theorem 5.5 (Results under LDP). For any possible e, with probability 1 the regret from running DP-Nash-Ve VI (Algorithm ! instantiated with Local Privatizer satisfies:
Regret (K) s (VHHVAAHTTT + S
(6)
Moreover, if the number of episodes K is larger than (
SABBB a²
A² 2a
with probability
1 - B, the output policy (n you) is a-approximate Nash.
Similar to the single- aggett case, the additional cost due to LDP is a multiplicative factor to the regret bound. When applied to the single-agent case, regret matches the best known regret
Ö H'SAT + S Av HST/c) /c) [Qiao and Wang 2023 Moreover, we state the lower bound.
Theorem 5.6. For any algorithm Alg satisfying e-LDP, there exists Markov Game such that the expected regret from running for episodes (T .K steps) satisfies:
E RRegret (K)) (VIPS(A+ B V VHS(A+ BYT
The lower bound is adapted from Garcelon et al. 2021 While our regret has optimal dependence on and K, the optimal dependence H, A, remains open.
5.3 The post-processing step
Now we introduce the post-processing step. At the end of episode k, given the noisy counts Ñ (s, a, b) and (s, ass.a,b. b, s') for all s,,,,a, a, b, s'), the private visitation counts constructed following: for all (h, 8,a,), b).
( S
argmin max x. Not (s,
WES (nyhess e'ES
such that
Σx x - No (s,
E.g and as 2 0, Ag.
(s, Σ (,
4
EES
''E
(7)
Lastly, we add constant term each count ensure no underestimation (with high probability).
Nk(s.a,b,5)) (s, -((..bb)) + E.g
25 (t
(s (....,))(((ss...b)
E.s
(8)

---

Remark 5.7. Solving problem
is equivalent to solving:
Ec,g
min i, s.l. Ix (K St, 2 0, Vo'
Σ Us - E'ES
T (s, b) S
which is a Linear Programming problem with (S)) variables and O(S) linear constraints. This can be solved in polynomial time (Nemhauser and Wolsey 19881. Note that the computation of CCE (line 14 in Algorithm TV is also a L.P problem, therefore the computational complexity of DP-Nash-Vi dominated by OHHSABK) ABK) Linear Programming problems, which is computationally friendly.
We summarize the properties of private counts N below, which says that the post-processing step ensures that our private transition kernel estimate is a valid probability distribution while only enlarging the error by a constant factor.
Lemma 5.8. Suppose Nţ satisfies that with probability 1 - S. uniformly over all (h, 8, a, b, k),
Ee.g
Ni(s,,,)) (N, Ec,
b, (
then the Nt derived above satisfies Assumption 3.1
5,4 Some discussions
In this part, generalize the Privatizers in Qiao and Wang 2023 (for single-agent case) to the two-player setting, which enables our usage of Bernstein-type bonuses. Such techniques lead to tight regret analysis and a near-optimal "non-private part" of the regret bound eventually.
Meanwhile, the additional cost due to DP has sub-optimal dependence on parameters regarding the Markov Game. The issue appears even in the aegle-agent case and is considered be inherent to model-basee algorithms due to the explicit estimation of private transitions [Garcelon et al. [021]] The improvement requires new algorithmic designs (e.g., private Q-leaniigg) and we leave those as future works.
Lastly, the Laplace Mechanism can be replaced with other mechanisms, such as Gaussian Mechanism [Dwork al. 2014] with approximate DP guarantee (or zCDP). The regret and PAC guarantees are readily derived by plugging in the corresponding E.,e to Theorem 4. and Theorem 4.2
6 Conclusion
We take the initial steps to study trajectory-wise privacy protection multi-agent RL. We extend the definitions of Joint DP and Local DP to multi-player RI.. In addition, we design provably- efficient algorithm: DP-Nash-VI (Algorithm[] TD that could satisfy either of the two DP constraints with corresponding regret guarantee. Moreover, our regret bounds strictly generalize the best known results under DP single-agent RL. There are various interesting future directions, such as improving the additional cost due to DP via model-free approaches and considering Markov Games with function approximations. believe the techniques in this paper could serve as basic building blocks.
Acknowledgments
The research is partially supported by NSF Awards #2007117 and #2048091. The work was done while DQ and YW were with the Department of Computer Science at UCSB.
References
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pages 463-474. PMLR, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 263-272. JMLR. org, 2017.
10

---

Yoram Bachrach, Richard Everett, Edward Hughes, Angeliki Lazaridou, Joel Z Leibo. Marc Lanctot, Michael Johanson, Wojciech M Czarnecki, and Thore Graepel. Negotiating team formation using deep reinforcement learning. Artificial Intelligence, 288: 103356, 2020.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In International Conference on Machine Learning, pages 551-560. PMLR, 2020.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-2170, 2020.
Borja Balle, Maziar Gomrokchi, and Doina Precup. Differentially private policy evaluation. In International Conference on Machine Learning, pages 2130-2138. PMLR, 2016.
Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar. When is memorization of irrelevant training data necessary for high-accuracy learning? In ACM SIGACT Symposium on Theeory of Computing, pages 123-132, 2021.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885-890, 2019.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635-658. Springer, 2016.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jemnj Kos, and Dawn Song. The secret sharer: Evalu- ating and testing unintended memorization neural networks. In USENIX Security Symposium (USENIX Security 19), pages 267-284, 2019.
T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1-24, 2011.
Sayak Ray Chowdhury and Xingyu Zhou. Differentially private regret minimization in episodic markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
Sayak Ray Chowdhury, Xingyu Zhou, and Ness Shroff. Adaptive control of differentially private linear quadratic systems. 2021 IEEE International Symposium on Information Theory (ISIT), pages 485-490. IEEE, 2021.
Sayak Ray Chowdhury, Xingyu Zhou, and Nagarajan Natarajan. Differentially private reward estimation with preference feedback. arXiv preprint arXiv:2310.1973: 2023.
Qiwen Cui, Kaiqing Zhang, and Simon Du. Breaking the curse of multiagents in large state space: RI in markov games with independent linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pages 2651-2652. PMLR, 2023.
Chris Cundy and Stefano Enmon. Privacy-connstranned policies via mutual information regularized policy gradients. arXiv preprint arXiv:2012.15019, 2020.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, pages 5713-5723, 2017.
John C Duchi, Michael Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 429-438. IEEE, 2013.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor: Comput. Sci., 9(3-4):211-40) 2014.
Jerzy Filar and Koos Vrieze. Competitive Markoy decision processes. Springer Science & Business Media, 2012.

---

Evrard Garcelon, Vianney Perchet, Ciara Pike-Burke and Matteo Pirotta. Local differential privacy for regret minimization in reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
Parham
Gohari, Matthew Hale, and Ufuk Topcu. Privacy-enginerred value decomposition networks for cooperative multi-agent reinforcement learning. 2023 62nd IEEE Conference on Decision and Control (CDC), pages 8038-8044. IEEE, 2023.
Md Tamjid Hossain and John WT Lee. Hiding in plain sight: Differential privacy noise exploitation for ovasion-resilien localized poisoning attacks in multiagent reinforcement learning. In 2023 International Conference on Machine Learning and Cybernetics (ICMLC), pages 209-216. IEEE, 2023.
Md Tamjid Hossain, Hung Manh La, Shahriar Badsha, and Anton Netchaev. Brnes: Enabling security and privacy-aware experience sharing in multiagent robotic and autonomous systems. In 2023 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 9269-9276. IEEE, 2023.
Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, and Zhiwei Steven Wu. Private matchings and allocations. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing. pages 21-30, 2014.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(,), 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863-4873, 2018.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020.
Chi Jin, Qinghua Liu, Yuanhao Wang. and Tiancheng Yu. V-learning- simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:21 10.11155.,4,,5 2021.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning, pages 5213-5225, PMLR, 2021.
Michael Kearns, Mallesh Pai, Aaron Roth, and Jonathan Ullman. Mechanism design in large games: Incentives and privacy. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 403-410, 2014.
Jonathan Lebensold, William Hamilton, Borja Balle, and Doina Precup. Actor critic with differentially private critic. arXiv preprint arXiv: 19Xiv:1900005766 2019.
Chonghua Liao, Jiafan He, and Quanquan Gu. Locally differentially private reinforcement learning for linear mixture markov decision processes. In Asian Conference on Machine Learning, pages 627-642. PMLR, 2023.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, pages 7001-7010. PMLR, 2021.
Paul Luyo, Evrard Garcelon, Alessandro Lazaric, and Matteo Pirotta. Differentially private explo- ration in reinforcement learning with linear representation. arXiv preprint arXiv:21 2021.
Weichao Mao, Lin Yang, Kaiqing Zhang, and Tamer Basar. On improving model-free algorithms for decentralized multi-agent reinforcement learning. In International Conference on Machine Learning, pages -5007-15049. PMLR, 2022.
George Nemhauser and Laurence Wolsey, Polynomial-time algorithms for linear programming. Integer and Combinatorial Optimization, pages 146-181, 1988.
12

---

Dung Daniel T Ngo, Giuseppe Vietri, and Steven Wu. Improved regret for differentially private exploration in linear mdp. In International Conference on Machine Learning, pages 16529-16552. PMLR, 2022.
Hajime Ono and Tsubasa Takahashi. Locally private distributed reinforcement learning. arXiv preprint arXiv:2001.11716 2020.
Dan Qiao and Yu- Yu-Xiang Wang. Near-optimal deployment efficiency in reward-fres reinforcement learning with linear function approximation. arXiv preprini 1rXi::2210.00700, 2022a.
Dan Qiao and Yu-Xiang Wang. Offline reinforcement learning with differential privacy, arXiv preprint arXiv:2206.00880 2022b.
Dan Qiao and Yu-Xiang Wang. Near-optimal differentially private reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 9914-9940. PMLR, 2023.
Dan Qiao and Yu-Xiang Wang. Near-optimal reinforcement learning with self-play under adaptivity constraints. arXiv preprint arXiv:2402.01111 2024.
Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang. Sample-efficient reinforcement learning with loglog(T) switching cost. In International Conference on Machine Learning, pages 18031-18061. PMLR, 2022.
Dan Qiao, Ming Yin, and Yu-Xiang Wang. Logarithmic switching cost in reinforcement learning beyond linear mdps. arXiv preprint 230.. 2023.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint 1rXiv:1610.03295, 2016.
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits. Advances in Neural Information Processing Systems, 31, 2018.
Ali Shavandi and Majid Khedmati. multi-agent deep reinforcement learning framework for algorithmic trading in financial markets. Expert Systems with Applications, 208: 18124, 2022.
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676:354-33555 2017.
Imdad Ullah, Najm Hassan, Sukhpal Singh Gill, Basem Suleiman, Tariq Ahamed Ahanger, Zawar Shah, Junaid Qadir, and Salil Kanhere. Privacy preserving large language models: Chatgpt case study based vision and framework. arXiv preprint 2XXv:2310.1222.. 2023.
Giuseppe Vietri, Borja Balle, Akshay Krishnamurthy, and Steven Wu. Private reinforcement learning with pac and regret guarantees. In International Conference on Machine Learning, pages 9754- 9764. PMLR, 2020.
Baoxiang Wang and Nidhi Hegde. Privacy- q-learming with functional noise in continuous spaces. Advances Neural Information Processing Systems, 32, 2019.
Yuanhao Wang, Qinghua Liu, Yu Bai, and Chi Jin. Breaking the curse of multiagency: Provably effi- cient decentralized multi-agent rl with function approximation. arXiv preprint arXiv:2302.066666 2023.
Fan Wu, Huseyin A Inan, Arturs Backurs, Varun Chandrasekaran, Janardhan Kulkarni, and Robert Sim. Privately aligning language models with reinforcement learning. arXiv preprint arXiv:2310. 16.660..0. 2023a.
Yulian Wu, Xingyu Zhou, Sayak Ray Chowdhury, and Di Wang. Differentially private episodic reinforcement learning with heavy-tailed rewards. arXiv preprint arXiv:2306.00 2312.01106611,,.1 2023b.
13

---

Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous move markov games using function approximation and correlated equilibrium. Conference on learning theory, pages -682. PMLR, 2020.
Tengyang Xie, Philip S Thomas, and Gerome Miklau. Privacy preserving off-policy evaluation. arXiv preprint arXiv:1902.001 2019.
Deheng Ye, Guibin Chen, Wen Zhang, Sheng Chen, Bo Yuan, Bo Liu, Jia Chen, Zhao Liu, Fuhao Qiu, Hongsheng Yu, al. Towards playing full moba games with deep reinforcement learning. Advances in Neural Information Processing Systems, 33:621-632, 2020.
Canzhe Zhao, Yanjie Ze, Jing Dong, Baoxiang Wang, and Shuai Li. Differentially private temporal difference learning with stochastic maaconnex-ttrongly-conee optimization. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pages 985-993, 2023a.
Canzhe Zhao, Yanjie Ze, Jing Dong, Baoxiang Wang, and Shuai Li. Dpmac: differentially private com- munication for cooperative multi-agent reinforcement learning, arXiv preprint 2XXi:2308.00902 2023b.
Fuheng Zhao, Dan Qiao, Rachel Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu-Xiang Wang. Differentially private linear sketches: Efficient implementations and applications. arXiv preprint arXiv:2205.09883, 2022.
Xingyu Zhou. Differentially private reinforcement learning with linear function approximation. Proceedings of the ACM Measurement and Analysis of Computing Systems, 6(1):1-27, 2022.
14

---

A Extended related works
Differentially private reinforcement learning. The stream of research on DP RL started from the offline setting. Balle et al. [2016] first studied privately evaluating the value of a fixed policy from running for several episodes (the on policy setting). Later, Xie et al. [2019] considered a more general setting of DP off policy evaluation. Recently, Qiao and Wang 2022b] provided the first
results for offline reinforcement learning with DP guarantees.
More efforts focused on solving regret minimization. Under the setting of tabular MDP, Vietri et al. 2020) designed PUCB by privatizing UBEV [Dann al. 2017 to satisfy Joint DP. Besides, under the constraints of Local DP, Garcelon et al.
[022]] designed LDP-OBI based on UCRL22 [Jaksch] al. 2010). Chowdhury and Zhou [2022] designed general framework for both JDP and LDP
based on UCBVI [Azar et al. [217]]. and improved upon previous results. Finally, the best known results are obtained by Qiao and Wang [2023 via incorporating Bernstein-type bonuses. Meanwhile,
Wu et al. [023b) studied the case with heavy-tailed rewards. Under linear MDP, the only algorithm with JDP guarantee: Private LSVI-UCB [ggo al., 2022] is a private and low switching version of
LSVI-UCB [Jin et al. 2020]. while LDP under linear MDP still remains open. Under linear mixture
MDP, LinOpt VI-Reg [Zhou 2022] generalized UCRL-VTR [Ayoub al.) [020 guarantee JDP,
while Liao et al.
2023] also privatized UCRL-VTR for LDP guarantee. In addition, Luyo et al.
2021
provided a unified framework for analyzing joint and local DP exploration.
There are several other works regarding DP RI. Wang and Hegde [019 proposed privacy-preserving
Q-learning to protect the reward information. Ono and Takahashi [2020] studied the problem of
distributed reinforcement learning under LDP. Lebensold et al. 2019] presented an actor critic algorithm with differentially private critic. Cundy and Ermon| [020 tackled DP-RL under the policy gradient framework. [Chowdhury et al. [2021] considered the adaptive control of differentially private linear quadratic (LQ) systems. Zhao et al. [2023a] studied differentially private temporal difference (TD) learning. [Chowdhury et al. 20023 analyzed reward estimation with preference feedback under the constraints of DP. Hossain and Lee 2023 Hossain et al. 2023 Zhao et al.) 2023b Gohari et al..
(2023) focused on the privatization of communications between multiple agents in multi-agent RI.. For applications, DP RL was applied to protect sensitive information natural language processing
and large language models (LLM) (Ullah al., 2023 Wu et al. 2023a Meanwhile, Zhao et al.
2022] considered linear sketches with DP.
B Proof overview
In this section, provide proof sketch of Theorem 4.1 which can further imply the PAC guarantee (Theorem 4.2) and the regret bounds under JDP (Theorem 3.2) or LDP (Theorem 5.5) The proof
consists of the following steps:
(1) Bound the difference between the private statistics and their non-private counterparts.
(2) Prove that UCB and LCB hold with high probability.
(3) Bound the regret via telescoping over time steps and replace the private terms by non-private ones.
Below we explain the key steps in detail. Recall that NF denotes the real visitation counts, while NA, Ph are the private visitation counts and private transition kernel respectively.
Step (1). According to Assumption 3.1 and standard concentration inequalities, we pro- vide high probability upper bounds for ||P (-1s, a, b) - Px(-ls, a, b]]l, and [P] (6')s,, a, b) Pa(s" as), b)). Besides, we upper bound the following key term [(P) Pp) V (s, a, b) by
δ Var pa (l(laa))) Vitaa (it1()/%% a,
HSE., //S Details are deferred to Appendix
Step (2). Then we prove that UCB and LCB hold with high probability via backward induction over timesteps (Appendix C.2). More specifically, the variance term of 1 is the private Bernstein-type
Forr low switching RL, please refer to Qiao et al. 2022 Qiao and Wang and Wang 2024
2022a
Qiao et al. 2023
Qiao
15

---

bonus, while the difference between the private variance and its non-private counterpart can be bounded by vh and the lower order terms I
Step (3), Lastly, the regret can be bounded by telescoping:
Regret ( so 00
ΣΣ r (o% ant bl:
k=1A==
bound by non-private torms
K H ΣΣ
Par of ( V
K
HSE. N (s a (
<ō
( ah b
k=l mihhl
bound by Cauchty Schwarz inequality and L.T.V
SH2 ABEga
1O(VH2SABT) 5² ,
The details about each inequality above and the lower order terms we ignore are deferred to Appendix
C Proof of main theorems
In this section, we prove Theorem 4.1 and Theorem 4.2
C.1 Properties of private estimations
We begin with some concentration results about private transition kernel estimate P that will be useful for the proof. Throughout the paper, let the non-private empirical transition kernel be:
(H,,,,,,s)) A (h,s,,,b,s'',k (,,,,,
(s
(9)
In addition, recall that our private transition kernel estimate is defined as below.
as,,,,,,s') (,,s,,,,,,,',k (),,,,
(s'
(10)
Now we are ready to list the properties below. Note that log (0g(30FS)BK/3) throughout the paper.
Lemma C.1. With probability 1 13. for all (h, [ X X X Ax B [K]. it holds that:
St 2SE.
Ph( a, 22 (*(,)a,)) (s,
(11)
2SE,,
(12)
(3,00))))
The proof is direct generalization of Lemma B.2 and Remark B.3 in Qiao and Wang 2023 to the two-player setting.
Proof of Lemma C.1
Lemma C.2. With probability holds that:
29 1 for all s,,, E [M] S Ax Ax
K]
min(Pa(s'ls,, a, b), (s +
2E,
(h(ss,, a, - Ph(s'ls,, a,b) (is/|s,,,bbl $
(13)
N)((,,,b)
N4(s,,,b)
2E,
-) (s)
(14)
N)(s,a,b)
16

---

Proof of Lemma C.2
The proof is direct generalization of Lemma B.4 and Remark B.5 in Qiao to the two-player setting.
and Wang 2023
Lemma C.3. With probability 1 - 15 for all a. E [ x x A [K], it holds that:
28
2Varp, (+))
2ar (l (ht+
2HS SISEE,,.
(P% Ph)) (itz(s,,,,b) b)) min
N (s,
(8,
(15)
(ptt Px) (1, 5
2HSE,,
(16)
as,
The proof is a direct generalization of Lemma B.6 and Remark B.7 in Qiao and Wang 2023 to the two-player setting.
Proof of Lemma C.3
According to a union bound, the following lemma holds.
Lemma C.4. Under the high probability event that Assumption 3.7 holds, with probability at least
1 8 3- the conclusions in Lemma C.1 Lemma C.2 Lemma C.3 hold simultaneously.
Throughout the proof, we will assume that Assumption 3.1 and Lemma C.4]hold, which will happen with high probability. Before we prove the main theorems, we present the following lemma which bounds the two variances.
Lemma C.5 (Lemma C.5 Qiao and Wang 2022b ). For any function V E RRS such that [|V S H, it holds that
Var Varje (1 V Var (1sa)))))))))))))))))))) S V3H
VI a, (H(,,,, (17)
In addition, according to Lemma C.1 the left hand side can be further bounded by
SE,
V Varps v /Vrrp (V) S3H
(18)
(s,
C.2 Proof of UCB and LCB
For notational simplicity, for E RS such that [V S H. we define
VV Var Varpe (4 V(). Vv, b) Var V(-).
(19)
Then the bonus term I can be represented as below (C2 is the universal constant in Algorithm D
+i A1l
V
(s)
2
C2HSE + C2H () (s,
b) Cz1
+
(20)
(s,
We state the following lemma that can bound the lower order term, which is helpful for proving UCB and LCB.
Lemma C.6. Suppose Assumption 3.1 and Lemma C.4 hold, then there exists a universal constant
> 0 such that: if function g(s) satisfies (g((s) S (V h+1 Vhh then it holds that:
(P) - PP)glss, b) 1 9 min P h+1 - v (s, a, b), P) (V - vh Vs,
(v
H
C St H...
(21)
No ())
(s.
17

---

2 sup E mutte @hui Proof of Lemma C.6 If [g](s) S (V h+1 -s)+1)(s), holds that:
(Ph aa) b) - <Σ (p% -P-p Ph) (0' (s'1a,
ssls,a,)) a, (191(()))(
(PA - Ph) (5 (s)1s,a,b)
(Vit1- -Kitt) khtt)) (5')
a,,
(K N (Vite V (8')
2E
V
(22)
Pn(5'Is,a,b)
+ 2E,,gh
N (viti
Vil (6')
H
(R,,,,b) (g
C1 PM K+1 - (s, 9
CHSE,
(s, (s,
where the third inequality is because of Lemma C.2 The forth inequality results from AM-GM inequality. The last inequality holds for some universal constant
The empirical part with the R.H.S to be P/ can be proven using identical proof according to
Then we prove that the UCB and LCB functions actually upper and lower bounds of the best responses. Recall that n is the (correlated) policy executed the k-th episode and (1²", v*) for both players are the marginal policies of x². In other words, (+(ss)) = EbES # bls) and (-ss) = E.EA (a, -ss) for all (h, s) E [H] x S.
Lemma C.7. Suppose Assumption 3.1 and Lemma C.4 hold, then there exist universal constants
C1, C2 > 0 (in Algorithm ! such that for all (h, 8, a, k)
E [H]] x S x A x B x [K], it holds that:
(% 2 oi
ti (s, O (s, (5,
(23)
(s(s) V (s) VI (s) > (s).
Proof of Lemma C.7 We prove by backward induction. For each k E [K) the conclusion is obvious for h = H + 1. Suppose UCB and LCB hold for Q value functions in the (h + 1) 1-th time step, we first prove the bounds for V functions the (h + 1)-th step and then prove the bounds for Q functions in the h-th step. For all s E S, it holds that
Vh+1(1) (8) = B (
a
(24)
2 sup E ponter 21(7((()
h+1 (s).
The conclusion 1 S Vhti 1 (s) can be proven by symmetry. Therefore, it holds that Vi
V (s) 2 b+1 (s) 2 (s))(() 2 Vi 2 v (s).
(25)
Next prove the bounds for Q value functions the h-th step. For all (s, a, b), it holds that
(Øh - (6--Q) (s,a,b) b) 2 min { (PXV h+1 - Pavita + nh + r%) (s.
( - Pa PAy + + + r (s,a.)).0}
2 min
pk Pb) (vite² - Vitta) (s, b)
(Ph Ph Vhta (8, +1h b1,,,,,,,)))
min
(1i)
(26)
18

---

The absolute value of term (i) can be bounded as below.
1i) - (V h+1 Vh (s, Ci 11
C.
(27)
(s,
N as,
for universal constant с₁ according to Lemma C.6 The absolute value of term (ii) can be bounded below.
2Var (1s.a. (
2HSE.
2 (11.0,)) (++1())
SHSE.
[ii] S
<
NO a))
(s,0,))
(s,
(s, a, b)
(28)
where the first incquality is because of Lemma C.3
while the second inequality holds due to Lemma
C
We further bound the term Var (
Vitt (-) as below.
h+1 +
Vh+t1
V/ Vitiit(() (s,a.
h
vih h-1 + -hh+1
(Vi+i + +Viti h+l
2
<
Ph
(8, (s,0,b) -Pp (Vi+t)²
+ pp.
(8, a)
2
2
<AHPI
(Vi+1 whttt) (8, b).
(29)
Therefore, the term (ii) can be further bounded as below.
2Varptt-la., (
S.SE
[(i)| <
(s,
(s
21 Vb
Vd Vhsi+Viuu
(s) + 2 4HP/
(vh+z vh+za) (s,
8HSE,,0
(H,
(s,
v +
2
(s,a,b)c
PK (V Vhtt) (8,a,
2H
8HSE,,9L
(s,
(s,
(s, a,
(30)
where the second inequality results from 29 and the third inequality is due to AM-GM inequality. Combining the upper bounds of (i) and (ii) there exist universal constants C₁ C2 such that
(i) + (ii) (s, b) (1,,,, 20 O.
(31)
The inequality implies that (Ø% Q (s, b) N 0.
By symmetry, we have
(ot @h"11 (s, a, b) 5. As result, it holds that (s. b) 2 Q (s,a, b) 2 (7, Q (ss, a. b) 2 O (s, a. b).
According to backward induction, the conclusion holds for all (h, s, a, k.).
C.3 Proof of Theorem
Given the UCB and LCB property, we are now ready to prove our main results. We first state the following lemma that controls the error of the empirical variance estimator.
19

---

Lemma C.8. Suppose Assumption 3.1 and Lemma C.4 hold, then there exists a universal constant 22 such that for all (h, 8, a. b, k) H] S
B x [K]. it holds that
h+1 + +Kit1 V
V
Vn k+z
(s,
2
(32)
<4HPh (V h+t1 Vh+1)
(s,
S2 ogH2
St
as
(s,
Proof of Lemma C.8 holds that
According to Lemma
C.7
(s) 2 (s) always holds. Then (s) 2 (s)
V
h+1 +
hh+1
Vi A+1
(8, b)
2
2
h+1 + 1h+t1 )] + (Pavatt)) (s, a)
h+1 + vh++1
PPh (vatz)²
2
2
V h+1 )² 3
-Pr
Ph (v -
)²
2
PPaV 1+11) ) 2 (8,
+
Ph
Ph)) (vh+1) 2
(s) + Ph (Vatt) (k
2
(s,
(i)
(ii)
P h+1
(s)
(PAV (tt
- (s,
V h+1)
22
(iL)
(Iv)
(33)
The term (i) can be bounded as below due to Lemma
C.I
St
2H'
(i) S 2H²
(34)
(s, b)
(s)
The term (ii) can be directly bounded below.
(ii] < 2HPb (vh+1 V (s)
(35)
The term (iii) can be bounded as below due to Lemma
C.1
(iii) < 2H (P) Ps. Pa) yhul (s, < 2
St
4H2
(36)
V
The term (iv) can be directly bounded as below.
(iv) S 2HP, (V - Vb vh+i (s, a, b).
(37)
The conclusion holds according the upper bounds of term (i), (ii), (iii) and (iv).
Finally we prove the regret bound of Algorithm
Proof of Theorem 4.1 notations.
Our proof base on Assumption 3.1 and Lemma C.4 We define the following
A h vk) (oh) b
(s k bl)). ch Pa (hh+1 - (hh+1)
ct A (Q) (2
(38)
(s/ att U/)
A A
20

---

Then it holds that 5 and 5% are martingale differences bounded by H. In addition, we use the following abbreviations for notational simplicity.
d
1he (5
I 1 ( Th: Un)
(39)
NJ No. (s 0 b5),
No NAA (5 4/ b/)-
a
Then we have the following analysis about A
4 ch + E 2%) (sh: uh 1/)))
sch + 2 + 21 + P/t (VD+1- 1 (sh ahi b%:
<ch + +2 + 1+ H
2C1
[1+
C1
Pn (v h+t1 - khtta (0 (h. + 12
+
e2 C.HSE,.
N
N
Sch + 1 +
C3
Ph (V h+1 - Vh+t)
(sh: az. b//) + CgH
C3 cgHSEE,.
+
H
No.
N
V 1 +
V
azh
+ C3
N
(1)
(40)
where the first inequality holds because of the definition of Q and Q. The second inequality holds due to the definition of 7 and Lemma C.6 The last inequality holds for some universal constant C3 >> O.
The term (i) can be further bounded below according to Lemma C.8 and AM-GM inequality.
Vn Var (oh al Df)e
4HP,
h+1
Vi kh+1)
(5 ot by))
H HeeeSEe,
H22voz2
(i) S
+ t0V
N/. VA Vmt
N
No.
N
N*.
1 (oh al bf:)e
PaPh
(vh h+1
Vi-1i
(sh ai by))
H,H2
H.H
C
SE,,3t
+
N
H
N
Ñ
N
(41)
where the first inequality results from Lemma The second inequality holds for some universal constant C4 according to AM-GM inequality.
C.8 and AM-GM inequality on the last term of (32).
Plugging in the upper bound of term (i), for some universal constant C5 > 0, it holds that:
A < ch + (1+ C5 ch + (1
C5 ) A + C00
V1, Vi (s), a bf))
05 C.HSE
C5
+
H
N
N
N
N
(42)
Summing Af over & E [K], we have for some universal constant cs > 0, it holds that:
K
K
K
"
Vn Vi h+t (sh a Dy))
+CB
H
H
N
k=1
k= -=1
(ii)
(i11)
(iv)
K
H
H + HS
L
k
A=
1=
-=1
(vi)
(43)
21

---

The term (ii) and term (iii) can be bounded by Azuma- Hoeff-ig inequality. With probability 1 it holds that
28
(()) S O (VH*K)):
((ii)] S (VHaKi)
(44)
The main term (iv) is bounded as below.
Vh V
(sh ait. U//ee
(iv) ΣΣ
h+1
N
K H
K
H
Vi VAVV (5 ( of 1g
(45)
N
k=1
SVO(HRK+
-ō -V + V
The first inequality is because N 2 No (Assumption 3.1 The second inequality holds due to Cauchy-Schwarz inequality. The third inequality holds with probability 1 5 total variance and standard concentration inequalities (for details please refer to Lemma 8 of Azar
& because of Law of
et al.. (2077).
The term (v) bounded below due to pigeon-hole principle.
SOVHPSABKI) N
(46)
where the first incquality because N 2 N (Assumption 3.1 hole principle.
The last one results from pigeon-
The term (vi) can be bounded below.
H + HSE,
(vi)
SO(H'S OH ABE,,
(47)
N
Combining the upper bounds for term (ti)), (fii)), (iv), (v) and (vi). The regret of Algorithm 1 can be bounded as below.
Regret K)
Σ
( (81) (81) ((1) S (1))) 2+(0s)
k=1
(48)
K
Σ
Af S (VHOVAHHSBBBB..... + H2 AB + H² ABE..)
km1
where T' HK' is the number of steps.
The failure probability bounded by 8 @ for Assumption 3.1 for Lemma C.4 for terms (ii).
(iii) and (iv)). The proof of Theorem 4.1 is complete.
C.4 Proof of Theorem
In this part, provide proof of the PAC guarantee: Theorem the proof of the regret bound (Theorem
4.2 The proof directly follows from
Proof of Theorem 4.2 Recall that choose out n such that To argming (v) (V-- (V- k4) (81). Therefore, we have
Viuwou (s1) Vi (si) - - 1
(VI'SABK O 52 (49)
K
if ignoring the lower order term of the regret bound.
Therefore, choosing K Ā
[
min
K²
8² ABE.,
S <a)) K¹
bounds the R.H.S by a.
a²
22

---

D Missing proof in Section
In this section, we provide the missing proof for results in Section Recall that Nţ is the real visitation count, N is the intermediate noisy count calculated by both Privatizers and Ñ is the final private count after the post-processing step. Note that most of the proof here generalizations of Appendix Qiao and Wang [2023] to the multi-player setting, and here we state the proof for completeness.
Proof of Lemma 5.7 Due to Theorem 3.5 of Chan et al. 2011 and Lemma 34 of Hsu et al. 2014], the release of (N (8, a, b)) (h.ss,.bb satisfies G-DP. Similarly, the release of also satisfies 2-DP. Therefore, the release of the following private (N a, ".sis,,,,)))(,a......... satisfy c-DP. Due to post-processing (Lemma 2.3 of Bun and Steinke (0166), the release of both private counts { (<V (s, a, (h,,, also satisfies c-DP. Then it holds that the release of all T" is e-DP according to post-pron post-proessingg Finally, the guarantee of c-JD results from Billboard Lemma (Lemma 9 of Hsu al. (2014)).
{N (s, a, b, b,), ( counters {N (s. a, (he..,)))
and {Nr, (s,
s') (1,),,,
For utility analysis, because of Theorem 3.6 Chan et al. 2011 our choice é' Mechanism and union bound, with probability 1 5. for all (h, s, a,a.b,b.. kk),,k),
2H log K in Binary
b, - (s, b.
log Jog(HSABK/3))
(50)
() - (N, 6)
0
H log (ggHHABK/3}
Together with Lemma 5.8
the Central Privatizer satisfies Assumption 3.1 with E., = Ō (
Proof of Theorem 5.2
The proof directly results from plugging F.,g Ö ( into Theorem 4.1
and Theorem 4.2
Proof of Theorem 5.3 The first term results from the non-private regret lower bound
(MVH2S((4 + B)T) Bai and Jin 2020). The second term is direct adaptation of the (HHAA/e)
lower bound for any algorttmms with e-JDP guarantee under single-agent MDP (Vietri et al. 2020
Proof of Lemma 5.4 The privacy guarantee directly results from properties of Laplace Mechanism and composition of DP [Dwork et 2014
For utility analysis, because of Corollary 12.4 of Dwork et al. [0144 and a union bound, with probability 3.
3 for all possible (h, s, a, b, s',
No (s,,,,, (x, 5
H
V KK log(HSABK/3))
(51)
[h(s,,,b) - (s)
H
K log HSg(HSAB//3)
3.1 with Ec, Ō @
Together with Lemma 5.8 the Local Privatizer satisfies Assumption
Proof of Theorem 5.3
The proof directly results from plugging Ec, = Ō (V) into Theorem
and Theorem
The first term results from the non-private regret lower bound Bai and Jin 2020)] The second term is direct adaptation of the 2( D(VHSAT) /e) lower bound for any algorithms with e-LDP guarantee under single-agent MDP
Proof of Theorem 5.6
2 H A B))
Garcelon et al.
2021
D
23

---

Proof of Lemma 5.8 For clarity, we denote the solution of 7 by N2 and therefore (s,, = (s, a, s')
B 25
(s, a, b) (s, a, b) E
When the condition (two inequalities) in Lemma 5.8 holds, the original counts (,, is a feasible solution to the optimization problem, which means that
max Ns. a, s') (s, a.,, - max (s. a, s') Ny (s,
b, b') S E
Combining with the condition in Lemma 5.8 with respect to N a, s¹), holds that (s, a, b,5') (i(s, - (s, (8,
Be,
2
Fie and as, 2 0. we have Since = +
28
((,,,,,,)) 0, (,(s,,,b,'') N s E.g.
(52)
For (s, a, b), according to the constraints in the optimization problem it holds that
(s a, (s, a, b)
E 4
Combining with the condition in Lemma 5.8 with respect to N%. (s, a, b), holds that
Ec,3
(s, b) N a. 6) < (h. (s, b) + (s. (5, s
2
Since (s, = (s, a, b) Bug we have
(5 a. b) (s a. (s, + E.,g.
(53)
According to the last line of the optimization problem we have (s, Eves as, and therefore.
(s, Σ (,
(54)
EES
The proof is complete by combining and 54
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract claims that this paper is about differentially private reinforcement learning with self-play.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss in Section 5 that the additional cost due to DP does not have optimal dependence on H, A,
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
25

---

Answer: [Yes]
Justification:
The paper provides the full set of assumptions and complete proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This is theory paper and do not conduct experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
26

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This is theory paper and do not conduct experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "cipps.c/ppulli//guu /tto://uuuddeeoooouuuubmmiibia ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is theory paper and do not conduct experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is a theory paper and we do not conduct experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
27

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This is theory paper and we do not conduct experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:s////eaursss.ccoooooo/hhaaa
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This is theory paper regarding privacy protection, which does not have negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: There is no risk of misuse of the algorithm in this paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This is theory paper and we do not other assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
29

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not introduce any assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This is theory paper and we do not conduct any experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "7V3Z4cgsqy", "reviewer": "Reviewer_Bzin", "summary": "This paper gives an algorithm for differentially private reinforcement learning in two-player zero-sum games. The paper considers a standard model for differential privacy already established for single-agent RL. In this model, in each episode a unique user follows a policy $\\pi$ recommended by the RL agent i.e. the user encounters states $s$, takes actions $a$ sampled from $\\pi(s)$, and receives rewards $r$. The goal is for the RL agent to learn optimal policy recommendations, without revealing the private information of each user consisting of the trajectory of states, actions, and rewards. The paper considers two standard models for privacy in RL, joint differential privacy (JDP) and local differential privacy (LDP). The proposed algorithm achieves nearly optimal (in certain parameter regimes) regret in both of these privacy constrained settings.", "questions": "1. Are there any technical challenges to overcome when combining the known algorithm for private single-agent RL with the algorithm for self-play in zero-sum games? \n2. Why is privacy across episodes of two-player zero-sum games an interesting problem? Is there some natural approach to generalize to mutli-agent RL? Are there natural examples where one would want to preserve privacy in a sequence of direct competitions between two players?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Differential privacy in multi-agent reinforcement learning is an important problem, and achieving this in two-player zero-sum games could be step towards the general multi-agent case.", "weaknesses": "- The algorithm proposed is a straightforward combination of prior work [1] achieving privacy for single-agent RL and [2] achieving low-regret learning for self-play in zero-sum games. It is not clear from the paper what new ideas, if any, are needed, beyond directly applying the private counts and bonuses from [1] to compute the upper and lower confidence bounds used in [2].\n\n- While privacy for multi-agent RL seems quite relevant and interesting, privacy for two-player zero-sum games seems much less well-motivated. For example, in the autonomous driving case, general multi-agent RL corresponds to learning in a setting where there are many autonomous vehicles on the road and one wants to keep the information of each one private. Two-player zero-sum markov games instead correspond to the setting where there are exactly two autonomous vehicles on the road in each episode, and somehow they are in direct zero-sum competition (e.g. a one-on-one race). In fact, the only reason differential privacy makes sense in this setting is that the paper assumes that a different pair of users competes in each episode, and it is privacy across these different pairs that is preserved. In general, it really seems to me that the most important questions regarding privacy in RL relate to a large number of interacting agents, and that the setting of this paper was chosen specifically so that the techniques of [1] and [2] could be directly applied, rather than because the problem itself seemed important to solve.\n\nSpecific Issues:\n\n- The text in Table 1 is too small to read.\n\n[1] Qiao, Dan, and Yu-Xiang Wang. \"Near-optimal differentially private reinforcement learning.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023.\n\n[2] Liu, Qinghua, et al. \"A sharp analysis of model-based reinforcement learning with self-play.\" International Conference on Machine Learning. PMLR, 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your high quality review. Below we will reply to your comments.\n\n**The algorithm proposed is a straightforward combination of prior work [1] achieving privacy for single-agent RL and [2] achieving low-regret learning for self-play in zero-sum games. It is not clear from the paper what new ideas, if any, are needed, beyond directly applying the private counts and bonuses from [1] to compute the upper and lower confidence bounds used in [2].**\n\nFirst of all, almost all the algorithms in the DP-RL literature are based on some well-known non-private algorithms. For instance, Private-UCB-VI and DP-UCBVI (in our Table 1) are both based on the famous UCBVI algorithm. Therefore, we choose the non-private algorithm Nash-VI as a base algorithm for designing private self-play algorithms. In addition, we only apply the technique for privatizing visitation counts from [Qiao and Wang, 2023], the construction of private bonus here is different. In the two player setting, we need to handle the other player, and the upper (lower) bound is for the Q value of the current policy when facing best responses. Therefore, the bonus is more complex compared to the single-agent setting. We manage to design a new private bonus term for the two-player setting, prove the validity of optimism and pessimism, and derive a near-optimal regret bound. These are the main techinical contributions of the paper.\n\n**While privacy for multi-agent RL seems quite relevant and interesting, privacy for two-player zero-sum games seems much less well-motivated. Is there some natural approach to generalize to mutli-agent RL?**\n\nWe agree that privacy for two-player zero-sum games is not as important as the multi-agent case, while we believe the progression of science is based on several small steps. This is the first paper considering trajectory-wise privacy protection in the multi-agent RL setting, and we believe this can be an important middle step towards understanding the role of privacy in multi-agent RL. Regarding extension to the case with more agents, some techniques in this paper can be readily applied. The privatization of visitation counts and the bonus can be combined with current model-based MARL algorithms, and a result like \nRegret $\\leq$ non-private regret + addition cost due to DP can be expected. The issue of such approach is that model-based approaches generally suffer from a regret with dependence $\\Pi_i A_i$ ($A_i$ is the number of actions for the i-th player). To overcome such issue, we need to privatize model-free algorithms, which is still an open problem in the DP-RL literature, and we leave this as future work.\n\n**The text in Table 1 is too small to read.**\n\nThanks for the comment, we will edit it to improve readability.\n\nThanks again for the high-quality review. We hope our response could address your main concerns and we are happy to answer any further questions. We would greatly appreciate it if you could consider raising your score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rxzNHDDER4", "reviewer": "Reviewer_vYkZ", "summary": "This paper explores multi-agent reinforcement learning (RL) with differential privacy (DP) constraints. The authors extend the concepts of Joint DP (JDP) and Local DP (LDP) to two-player zero-sum episodic Markov Games. They develop a provably efficient algorithm that combines optimistic Nash value iteration with the privatization of Bernstein-type bonuses, ensuring satisfaction of JDP and LDP requirements with appropriate privacy mechanisms. The algorithm achieves a regret bound that generalizes the best-known results in single-agent RL and could reduce to the best-known results in multi-agent RL without privacy constraints.", "questions": "Could the authors highlight the key technical challenges involved in combining the techniques from Liu et al. [2021] and Qiao and Wang [2023]?", "limitations": "No negative societal impact of this work.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. This paper extends the concepts of Joint DP (JDP) and Local DP (LDP) to two-player zero-sum episodic Markov Games, which is important and inspiring for future studies on differential privacy in multi-agent RL.\n\n2. The proposed DP-Nash-VI algorithm could satisfy either Joint DP (JDP) and Local DP (LDP)constraints with corresponding regret guarantees. Their regret bounds strictly generalize the best-known results under DP single-agent RL, and their results could be reduced to the best-known results in multi-agent RL without privacy constraints.", "weaknesses": "Though this is a purely theoretical paper, it may be better to include some simulation results to validate the theoretical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your high quality review and the positive score. Below we will reply to your comments.\n\n**Though this is a purely theoretical paper, it may be better to include some simulation results to validate the theoretical results.**\n\nThanks for the comment, we will conduct some experiments in the next version.\n\n**Could the authors highlight the key technical challenges involved in combining the techniques from Liu et al. [2021] and Qiao and Wang [2023]?**\n\nFirst of all, almost all the algorithms in the DP-RL literature are based on some well-known non-private algorithms. For instance, Private-UCB-VI and DP-UCBVI (in our Table 1) are both based on the famous UCBVI algorithm. Therefore, we choose the non-private algorithm Nash-VI as a base algorithm for designing private self-play algorithms. In addition, we only apply the technique for privatizing visitation counts from [Qiao and Wang, 2023], the construction of private bonus here is different. In the two player setting, we need to handle the other player, and the upper (lower) bound is for the Q value of the current policy when facing best responses. Therefore, the bonus is more complex compared to the single-agent setting. We manage to design a new private bonus term for the two-player setting, prove the validity of optimism and pessimism, and derive a near-optimal regret bound. These are the main techinical contributions of the paper.\n\nThanks again for the high-quality review. We hope our response could address your main concerns and we are happy to answer any further questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GZno2qAUl3", "reviewer": "Reviewer_3xco", "summary": "The authors address multi-agent self-play reinforcement learning (RL) with differential privacy (DP) constraints to protect sensitive data. They propose an efficient algorithm that meets JDP and LDP requirements, and its regret bounds generalize the best-known results for single-agent RL, marking the first study of trajectory-wise privacy in multi-agent RL.", "questions": "1. The technical convenience of using Definition 2.2 instead of Definition 2.1 is not clear. Can the authors confirm if their proposed algorithm also satisfies the differential privacy requirements of Definition 2.1? If it does not, could you provide an intuitive explanation?\n\n2. Given that the reward value is known and determined, why does the agent still require reward feedback from the user (as mentioned in line 135)?", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed algorithm demonstrates a statistically tight regret bound, supported by the authors' derived lower bound.\n2. The differential privacy analysis is comprehensive, encompassing both Joint Differential Privacy (JDP) and Local Differential Privacy (LDP).\n3. The writing is generally clear and concise.", "weaknesses": "1. The overall technical contribution seems limited. Could the authors emphasize their primary technical contributions? Specifically, is it feasible to address the problem setting using existing algorithms augmented with the Laplacian mechanism?\n2. The absence of an experimental study, even a simple one, is noticeable. Conducting experiments is crucial to validate the efficacy of the proposed algorithm, especially given the authors' claims of its efficiency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your high quality review and the positive score. Below we will reply to your comments.\n\n**The overall technical contribution seems limited. Could the authors emphasize their primary technical contributions? Specifically, is it feasible to address the problem setting using existing algorithms augmented with the Laplacian mechanism?**\n\nFirst of all, almost all the algorithms in the DP-RL literature are based on some well-known non-private algorithms. For instance, Private-UCB-VI and DP-UCBVI (in our Table 1) are both based on the famous UCBVI algorithm. Therefore, we choose the non-private algorithm Nash-VI as a base algorithm for designing private self-play algorithms. In addition, we only apply the technique for privatizing visitation counts from [Qiao and Wang, 2023], the construction of private bonus here is different. In the two player setting, we need to handle the other player, and the upper (lower) bound is for the Q value of the current policy when facing best responses. Therefore, the bonus is more complex compared to the single-agent setting. We manage to design a new private bonus term for the two-player setting, prove the validity of optimism and pessimism, and derive a near-optimal regret bound. These are the main techinical contributions of the paper.\n\n**The absence of an experimental study, even a simple one, is noticeable. Conducting experiments is crucial to validate the efficacy of the proposed algorithm, especially given the authors' claims of its efficiency.**\n\nThanks for the comment, we will conduct some experiments in the next version.\n\n**The technical convenience of using Definition 2.2 instead of Definition 2.1 is not clear. Can the authors confirm if their proposed algorithm also satisfies the differential privacy requirements of Definition 2.1? If it does not, could you provide an intuitive explanation?**\n\nOur algorithm satisfies Def 2.2 but could not satisfy Def 2.1. Indeed, Def 2.1 is not consistent with a sublinear regret bound, even for the simpler single-agent RL setting and contextual bandit setting. An intuitive explanation is that Def 2.1 requires the agent to privately recommend an action to the user while protecting her own state, where a constant regret is inevitable in each episode in the worst case. Therefore, our algorithm with sublinear regret bound could not satisfy Def 2.1.\n\n**Given that the reward value is known and determined, why does the agent still require reward feedback from the user (as mentioned in line 135)?**\n\nThe RL protocol we introduced is for the general case where the reward can be stochastic. The DP guarantees are also defined for the general setting. Actually our techniques can be easily extended to handle the setting with stochastic rewards, and the assumption of known rewards is only for the ease of presentation.\n\nThanks again for the high-quality review. We hope our response could address your main concerns and we are happy to answer any further questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JiPdVl4kwU", "reviewer": "Reviewer_f4t2", "summary": "The paper studied two-player zero-sum episodic Markov Games under JDP and LDP. The authors designed DP-Nash-VI algorithm for the problems and derives both upper bounds and lower bounds.", "questions": "1. In this paper, you consider bounded reward case. Can your method extend to heavy-tailed reward case in [1]?\n2. Is it possible to further improve the gaps between your upper bounds and lower bounds?\n\n[1] Yulian Wu, Xingyu Zhou, Sayak Ray Chowdhury, and Di Wang. Differentially private episodic reinforcement learning with heavy-tailed rewards. arXiv preprint arXiv:2306.01121, 2023b", "limitations": "There is no experiment but I understand the main contributions of paper is on theoretical side.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper investigated interesting problem of  two-player zero-sum episodic Markov Games under JDP and LDP.\n2. It is good to derive the  the best known regret for non-private multi-agent RL as byproduct.\n3. The authors give algorithms design and solid proofs of upper bounds and lower bounds for the problems.", "weaknesses": "There is no experimental result to verify their theoretical findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your high quality review and the positive score. Below we will reply to your comments.\n\n**There is no experimental result to verify their theoretical findings.**\n\nThanks for the comment, we will conduct some experiments in the next version.\n\n**In this paper, you consider bounded reward case. Can your method extend to heavy-tailed reward case in [1]?**\n\nThis is a very good question. [1] handled the heavy-tailed reward using a truncation step. Then a privatization step is followed. We are not sure whether this can be extended to the multi-player setting, while we believe incorporating the truncation step to deal with heavy-tailed rewards is an interesting future direction.\n\n**Is it possible to further improve the gaps between your upper bounds and lower bounds?**\n\nThe gap for the JDP case is mostly on the lower order term, while there is a gap on the main term under the LDP case. Since our algorithm generalizes the best-known result under the single-agent RL case, we believe the practical way to close the gap is to improve the regret bound under the single-agent RL case. [2] argues that the extra dependency on the parameters may be inherent to model-based algorithms due to the explicit estimation of private rewards and transitions. Therefore, a possible direction is to privatize model-free algorithms, which is still an open problem in the literature.\n\n[2] Evrard Garcelon, Vianney Perchet, Ciara Pike-Burke, and Matteo Pirotta. Local differential privacy for regret minimization in reinforcement learning.\n\nThanks again for the high-quality review. We hope our response could address your main concerns and we are happy to answer any further questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper takes the first step in studying privacy protection in Markov games from a theoretical perspective. It considers both central and local models of DP and establishes corresponding regret bounds that capture the cost due to privacy. The reviewers appreciate the contribution, and all tend to accept it. 

One possible improvement the authors could consider is to motivate the problem in more detail, i.e., by highlighting the importance of privacy protection in zero-sum Markov games.
Decision: Accept (poster)