Differentially Private Reinforcement Learning with Self-Play

We appreciate your high quality review and the positive score. Below we will reply to your comments.

There is no experimental result to verify their theoretical findings.

Thanks for the comment, we will conduct some experiments in the next version.

In this paper, you consider bounded reward case. Can your method extend to heavy-tailed reward case in [1]?

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

Is it possible to further improve the gaps between your upper bounds and lower bounds?

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

[2] Evrard Garcelon, Vianney Perchet, Ciara Pike-Burke, and Matteo Pirotta. Local differential privacy for regret minimization in reinforcement learning.

Thanks 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 appreciate your high quality review and the positive score. Below we will reply to your comments.

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?

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

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.

Thanks for the comment, we will conduct some experiments in the next version.

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?

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

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

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

Thanks 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 appreciate your high quality review and the positive score. Below we will reply to your comments.

Though this is a purely theoretical paper, it may be better to include some simulation results to validate the theoretical results.

Thanks for the comment, we will conduct some experiments in the next version.

Could the authors highlight the key technical challenges involved in combining the techniques from Liu et al. [2021] and Qiao and Wang [2023]?

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

Thanks 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 appreciate your high quality review. Below we will reply to your comments.

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

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

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?

We 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 Regret $\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.

The text in Table 1 is too small to read.

Thanks for the comment, we will edit it to improve readability.

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

Dear reviewer,

Since the discussion deadline is approaching, please let the authors know if their rebuttal has addressed your concerns. If you still have concerns, you could first acknowledge that you have read the rebuttal and discuss them in the remaining time (with the authors) or the next phase (with other reviewers).

Best,

Your AC