Offline Reinforcement Learning with Differential Privacy

Summary

This paper proposes two offline RL algorithms with differential privacy guarantees. The two pessimism-based algorithms apply to both tabular and linear MDP settings. In theory, the authors prove that the proposed algorithms achieve instance-dependent sub-optimality bounds while guaranteeing differential privacy. A nice property is that the cost of privacy only appears as lower order terms, thus become negligible as the number of samples goes large.

Strengths

(1) While DP algorithm has been studied in online RL settings, the study of DP in offline RL is limited. This paper provides the first provable study along this line. (2) In spite of a theoretical paper, it is well written and easy to follow.

Weaknesses

(1) The motivation of the considered problem needs more real justifications. In the introduction, the authors used a medical example to motivate the need of considering privacy in offline RL. Why could not the data owner (hospital or doctors) do offline policy evaluation or policy optimization directly on the raw data? Why do we need to generate a private policy? On the other hand, if the offline policy optimization is requested from a third-part not the data owner, it is justified that the patient's data needs to be protected. However, in this case, the third-part would not have access to the raw data. This contradicts with the setting considered in this paper as in the proposed Algorithm 1 and Algorithm 2, the input is the raw data. Therefore, it is important and helpful to provide a convincing real example to justify the problem setting and algorithm designs. (2) In Assumption 2.2, the data distribution needs to satisfy the minimum eigenvalue condition. This assumption might be violated when the feature space is large or some features are highly correlated. It is helpful to provide some discussion on this assumption and how to remedy it when this assumption is violated. (3) In the tabular MDP (DP-APVI) algorithm, the Gaussian noise is added to the integer counts $n_{s_h, a_h}$ and $n_{s_h, a_h, s_{h+1}}$ to obtain a private estimation of the transition kernel. Because of the design, the private counts might be negative or very small, which makes the uncertainty estimation (line 5 of Algorithm 1) to be unstable. To handle it, the authors used some truncation approach with some theoretical truncation rate $E_{\rho}$. It is unclear if it is a good choice to add the Gaussian noise to the count statistics. Can we add the Gaussian noise directly to the non-private estimation of transition kernel? Some justifications on the proposed private estimation would be helpful. It is also important to discuss the advantages and limitations of the proposed private estimation while comparing with other choices in existing RL literature. (4) In Algorithm 2 and line 235 of Page 7, the authors require two independent offline dataset with equal length. Can authors clarify what the rigorous condition of the "two independent offline dataset"? Do you need each sample (across $K$) at each time horizon (across $H$) to be independent in each offline data? If yes, this is an unrealistic condition in offline RL problem. Moreover, I did not find such condition in the statement of Theorem 4.1. Where do you use this "independence" assumption? (5) In the experiments (Figure 1), the simulations are for 5 replicates. Can authors include the uncertainty in Figure 1? If the uncertainty is large, it is helpful to increase the replication times. ~~~~~~~~~~~ After rebuttal: my major comments have been nicely addressed. I have increased the score to 7.

Questions

See Weakness section

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

None.

Summary

This paper addresses the offline RL with Differential Privacy constraints problem. Tabular and linear MDP are considered, while both forms of DP, traditional DP and zCDP are studied. The authors cast the DP definition into the offline RL problem as a constraint for protecting trajectories. Two algorithms, DP-APVI (resp. DP-VAPVI), are introduced, treating the tabular (resp. linear) case. Those algorithms rely on the pessimism principle, and DP is obtained by adding a Gaussian mechanism, either on the counts or during variance estimation. Authors prove zCDP compliance for both algorithms, and a comparison with non-private algorithms is provided. Finally, authors empirically evaluate the performance of DP-VAPVI under different privacy budgets.

Strengths

The main strength of this paper is that it is, according to my knowledge, the first to tackle the offline RL with DP constraints, which is an important problem. This paper introduce two sound and practical algorithms, respecting Differential Privacy by design. Furthermore, we have a discussion comparing the algorithms with their non-private counterpart and experimental validation.

Weaknesses

- Globally, the paper is well-written, however, I found the section on DP-VAPVI very hard to follow, especially the algorithm - Experiments study the performance of the algorithms under differential privacy budgets, but it feels very hard to have an interpretation of those budgets for zCDP. In the traditional DP case, one often sees very high values of \epsilon, leading to a discussable Differentially Private algorithm in practice. Would it be possible to have a discussion about \alpha? What would be reasonable values? - Although there may not be other paper directly studying directly DP offline RL, there is work in literature on privacy attacks in RL, such as membership inference attack: R. Shokri, M. Stronati, C. Song, and V. Shmatikov. Membership inference attacks against machine learning models) or Maziar Gomrokchi, Susan Amin, Hossein Aboutalebi, Alexander Wong, and Doina Precup. Membership Inference Attacks Against Temporally Correlated Data in Deep Reinforcement Learning. It would have been nice to have a discussion on those attacks to have a better estimation of the practical impact of DP casted like this.

Questions

- See section weakness, could the authors comment on the \rho factor? And would it allow to robustness to membership inference attacks? - You only consider an MDP with 2 states in the experiments, would the algorithm scale to bigger MDPs?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

yes

Summary

This paper focuses on reinforcement learning (RL) in an offline setting under differential privacy considerations. It studies the proposal and analysis of a new approach to learning policies in this specific setting, leveraging the Bernstein concentration inequality. Reinforcement learning explores an agent's interaction with its environment over a series of episodes. The environment is defined as a Markov decision process (MDP) comprising states, actions available to the agent, a reward function, and transition dynamics. Through this interaction, the agent gathers feedback to learn a policy that optimizes the cumulative reward. In this paper, the agent operates under the constraints of differential privacy, implying that it interacts in an environment with sensitive data. Here, observations from each episode are deemed private, being tied to individual users. Traditionally, two settings have been studied: the online and offline settings. In the online setting, an agent learns a policy through active data collection by exploring the environment. Conversely, the offline setting involves the agent receiving all data upfront, barring any access to the environment for training. Prior studies have explored these settings without privacy constraints, but only the online setting has been studied under differential privacy. This paper breaks new ground by studying reinforcement learning in the offline setting under differential privacy. Like its online counterpart, the offline setting necessitates the construction of tight confidence bounds around sufficient statistics for policy approximation. However, due to privacy-induced noise, the algorithm must inflate the confidence bounds to compensate. The primary innovation of this paper is the proposal of new confidence bounds, utilizing the Bernstein concentration inequality, a departure from the traditional Hoeffding concentration. This novel method offers improved error bounds under specific instance-dependent conditions, although the bounds are equivalent to Hoeffding's in the worst-case scenario. The authors cleverly adapt techniques from previous research while also introducing new methodologies that could potentially extend beyond this work. A significant contribution lies in the estimation of variance from noisy statistics, thereby enabling the utilization of the Bernstein concentration. In sum, this paper illuminates a hitherto unexplored area in the RL community, offering innovative solutions and techniques for reinforcement learning in the offline setting under differential privacy.

Strengths

The primary strength of this paper lies in its pioneering examination of differential privacy reinforcement learning (DP-RL) in the offline setting, effectively bridging a notable gap in existing academic literature. By venturing into this uncharted territory, the paper opens up possibilities for practical applications in real-world scenarios where sensitive data may be involved. The paper's successful application of differential privacy to offline RL deserves commendation, given the unique challenges associated with this endeavor. While one might assume that the principles governing DP-RL in the online setting would seamlessly translate to the offline setting, this is not the case. The paper adeptly navigates these challenges, setting a benchmark for future investigations into this area. Another significant contribution of this work is the innovative use of Bernstein concentration in the estimation of error bounds. Prior studies primarily employed Hoeffding concentration, which, although effective, offered limited utility under specific conditions. In contrast, Bernstein concentration proves to be more flexible, offering improved error bounds, particularly under specific instance-dependent conditions. This innovative application, therefore, has the potential to enhance results not only in the offline setting but also in the online RL environment. Furthermore, the paper presents an empirical evaluation that provides rich insights into the practical implications of their proposed techniques. This robust empirical analysis not only validates the theoretical contributions but also offers tangible results that underscore the effectiveness of the proposed methods. In conclusion, the paper's merits extend from filling a knowledge void in DP-RL literature, effectively tackling challenges in translating DP-RL principles from online to offline settings, to innovatively employing Bernstein concentration in error bound estimation. The comprehensive empirical evaluation serves as the icing on the cake, demonstrating the practicality and effectiveness of the proposed methods. The paper's contributions are both theoretical and practical, promising to advance understanding and application of DP-RL in offline settings.

Weaknesses

Many of the techniques presented in this paper are not new. The concentration bounds utilized, for instance, have been previously developed and employed in other works. However, the paper's merit lies in its successful adaptation of these existing techniques for a specific context. Therefore, this paper effectively demonstrates how to repurpose these pre-existing tools for its unique setting, thereby contributing to the literature in a meaningful way.

Questions

No questions.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes.

Summary

The paper proposes an algorithm for offline reinforcement learning with differential privacy (DP), which protects the privacy of the original information using a Gaussian mechanism based on pessimism. The motivation and ideas behind the paper are clear and meaningful. However, there are some issues with the methods and experiments. Overall, the paper presents some interesting ideas, but additional experiments and comparisons are needed to fully evaluate the proposed method and its practical value.

Strengths

1.The authors propose a method for protecting the privacy of original information in offline reinforcement learning. They achieve this goal by implementing differential privacy (DP) in their proposed method, which is a meaningful contribution to the field of privacy-preserving machine learning. 2. The authors implement their ideas in APVI and VAPVI models and provide a thorough theoretical analysis of the proposed method. The writing is clear and the theoretical analysis is extensive, providing a strong foundation for the authors' claims. 3. The authors conduct experiments on simulated datasets, which provide preliminary evidence of the method's performance.

Weaknesses

The paper proposes two models, DP-APVI and DP-VAPVI, for solving the offline reinforcement learning problem with privacy guarantees. While the paper presents some interesting ideas, there are several issues: 1. The paper only includes results for DP-VAPVI, and does not provide any experimental results for DP-APVI. It would be helpful to see how DP-APVI performs in comparison to DP-VAPVI and other baseline methods. 2. The results for DP-VAPVI consistently show a performance gap compared to VAPVI, which raises questions about the competitiveness of DP-VAPVI in practice. Without additional experiments or comparisons with other methods, it is difficult to assess the practical value of DP-VAPVI. 3. The paper claims that DP-VAPVI will converge to VAPVI as the dataset size increases, but there is no experimental evidence to support this claim. 4. The paper does not discuss the impact of the privacy budget (ρ) on the privacy protection and performance of the algorithms. It would be helpful to see how different values of ρ affect the results. 5. The paper lacks ablation experiments to investigate the extent to which DP itself as an optimization plug-in for APVI and VAPVI models maintains privacy and affects performance. It would be helpful to see how different components of the DP-APVI and DP-VAPVI models contribute to the overall performance. 6. The paper only compares DP-VAPVI and VAPVI with PEVI, which is not a privacy-preserving method. It would be helpful to see how DP-VAPVI and DP-APVI compare to other privacy-preserving methods. 7. The experiments are conducted on synthetic datasets, which may not fully reflect the complexity and diversity of real-world problems. It would be helpful to see how the proposed methods perform on real-world datasets. Methodologically, the paper proposes to add additional Gaussian mechanisms to APVI and VAPVI models to ensure privacy, but the main methods are still based on APVI and VAPVI. While the paper's definition of neighboring datasets and the use of Gaussian mechanism for differential privacy are contributions, the experimental results are not convincing enough. The authors should demonstrate the advantages of their proposed methods on a wider range of datasets and models. I'm not an expert on differential privacy. My evaluation is based on how well I was able to comprehend the information in the paper. I don't fully comprehend how this work contributes to the overall growth of the field.

Questions

Please refer to the weakness

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Please refer to the weakness

Summary

This paper focuses on the offline RL problem with differential privacy. The authors propose algorithms for offline tabular MDP and offline linear MDP with $\rho$-DP. For the first problem, the sub-optimality bound almost matches the best-existing non-private counter-part in spite of an additional term $O(\sqrt{\frac{1}{\rho}})$. For the second problem, the gap between the proposed sub-optimality bound to the best existing non-private counter part is $\mathrm{poly}(d,H,\kappa^{-1})/\sqrt{\rho}$, where $\kappa$ is the minimal coverage parameter.

Strengths

1. This paper firstly provides analysis for offline RL, and proposes error bounds which matches the non-privacy counterparts up to some lower order terms. 2. In technique, the authors make efforts to operate on Bernstein type pessimism while keeping privacy to achieve the tighter sub-optimality bound.

Weaknesses

1. The technique novelty is somewhat limited given literature in online RL with DP. 2. The discussion about related work is insufficient. In particular, I wonder what are the best existing regret bounds for online RL with DP (either tabular or linear MDPs)? If the regret bounds are not tight, could we use the Bernstein-style bonus with DP to improve the regret bounds?

Questions

1. For the non-privacy problem, does the error bound have a polynomial dependence on $\kappa$ for the linear MDP problem?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes