Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studied the regret analysis of reinforcement learning under the tabular setting and the LDP (local differential privacy) constraint. The authors first showed a minimax lower bound that, unlike the additive dependence on $\varepsilon$ under the JDP (joint differential privacy) constraint, the stronger LDP constraint must incur a minimax regret multiplicative in $1/\varepsilon$. Then the authors provided a general paradigm of the upper bound analysis: find private versions of aggregated statistics (rewards, number of visits), and then carry out an optimistic policy (called the LDP-OBI algorithm) based on (UCBs of) these noisy statistics. Depending on the usage of different private mechanisms, a regret multiplicative in $\sqrt{K}/\varepsilon$ could be obtained, but with worse dependence on other parameters $(H,S,A)$. Discussions and numerical experiments on the result are also provided. 
main_review: Overall I like this paper. The LDP constraint in reinforcement learning is useful to preserve privacy, and the separation between LDP and JDP constraints shown in the paper is interesting. The authors proposed a general paradigm for the upper bound analysis which could be useful in other papers, and also gave a lower bound analysis with a tight dependence on $(K,\varepsilon)$ to support the optimality of the proposed mechanism. The writing is mostly clear to me. 

However, I can also list some drawbacks of this work: 

1. The upper bound analysis, mainly Section 4.2, is technical while quite standard. I do like the current presentation which summarizes all necessary conditions as Assumption 3 and proves a general result in Proposition 4, but the essentially the same argument was applied in the non-constrained RL setting, and it seems that this part does not add much novelty to the RL literature. If this is the case, then the contribution of just applying various private mechanisms to obtain aggregated statistics is limited. I suggest the authors to highlight the main novel points in Section 4.2 to differentiate from the non-constrained RL regret analysis.

2. The current upper bound has a potentially loose dependence on parameters (H,S,A). This may suggest that the privacy constraint is currently not handled in a most appropriate way, and there might be room for significant improvement. In fact, Table I already shows that using one private mechanism could have a much worse performance than using another one. 

3. In the discussion the authors provided some evidence that the current dependence on (H,S,A) might not be tight. If this is the case, ideally I hope the authors could provide a rigorous argument (a partial result is okay) instead of only conjecturing it. I have to say that the current lower bound analysis is pretty standard - it is essentially the estimation of the bias of a coin under the LDP constraint (or in other words, a simple combination of the non-constrained case and the strong data-processing inequality applied to the LDP constraint). So a stronger lower bound would also increase the significance of the lower bound. 

One minor comment: I do not understand why a minimum is present in Eqn. (14). Isn't it the case that by the data-processing inequality for general f-divergences, the first term is always no greater than the second term? Consequently, I also do not understand why these two terms need to be obtained from two different equations (11) and (13). 
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper examines reinforcement learning under local differential privacy constraints. The paper proposes an algorithm, LDP-OBI, derives its regret bounds as well as privacy guarantees, and provided some simulation results.
main_review: - Originality: the paper focuses on the new intersection between local differential privacy and reinforcement learning. The author proposes local differential privacy adapted to RL and also applied existing privacy mechanisms in a RL setting, differentiating it from existing private RL works. Related works are cited and discussed thoroughly.

- Quality: the technical proofs are sound and simulations support the authors' claims in simple tasks. While implementation is not included in the supplement, the paper is largely theoretical and the experiment results should be sound. 

- Clarity: the paper is clear and well-written.

- Significance: while local DP + RL is an interesting problem with great significance, LDP-OBI appears to be a direct combination of existing privacy mechanisms and existing RL algorithms and its regret bound is much greater than the derived lower bound. However, the results in the paper are still worth examining and the could pave way for future studies at the intersection of privacy and RL. 
limitations_and_societal_impact: Limitations of the paper are clearly stated.

There are no potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces the concept of Local Differential Privacy for RL, a stronger notion of privacy than Joint Differential Privacy for RL. The authors both prove a regret bound for LDP in RL and provide a novel algorithm that achieves good regret in this setting. Furthermore, empirical experiments are provided that validate the method.  

main_review: Unfortunately I am not familiar with this literature at all, but I will try to provide some good feedback. 

My main concerns are that it seems that LDP is simply too strict of a privacy guarantee for RL, and that this will make it impractical in practice. With that being said, it seems that the main results in this paper show that decent results are possible in this setting, so this worry might be unfounded. 

The authors submitted this work to two conferences before. At the first conference the reviewers said that the work was not well written and that the main contributions and importance of the problem were missing. I think these points have been solved, as the paper is very well written and the main contributions are clear. In the second conference, reviewers thought that the regret bound could be improved with shuffling. In lines 69 - 73 the authors address this issue, but not enough in my opinion. They refer to Theorem 5.2 in Feldman et. al., but it is not immediately clear to me why that theorem backs their claim. This could be because I am not familiar with the field, but regardless I think the paper could be improved with a more extensive discussion of this issue, perhaps in the appendix. 

Other than that issue, I was not able to find any faults in the paper. The problem seems well motivated and the theory looks good. The experimental results back up the theory and the paper is well written.   

--------------------------------
I have read the rebuttal and do not change my score. 

limitations_and_societal_impact: NA
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: An interesting study on discrete MDP under LDP.
main_review: This manuscript investigates discrete MDPs under LDP constraints. The contribution is two-fold. First, it shows that the problem incurs a regret at least \Omega(K^1/2). The hardness is through the information theory-based technique previously used in bandits and a construction of an A-fold tree MDP. The contribution is significant. Second, armed with an LDP mechanism, it proposes a model-based exploration method for discrete MDP. The regret is upper bounded by O(H^3 S^2 A K^1/2) up to some logarithm factors. The upper bound is reasonably tight though there leaves a gap between the upper and the lower bounds. The techniques used in the proof of the upper bound are standard in discrete MDPs.

I suggest the authors have a thorough revision of their manuscript. The reading might not be very smooth. Here are a few examples:
line 17 - Privacy should be protected. It is not just due to that "users are becoming increasingly wary of that"
line 29 - circle 2 can be confusing (say something more explicitly when you define your scenarios)
line 55 - I don't see this footnote 2 very useful
line 57 - I don't think you can conclude that one problem is harder than another one simply by comparing their best known lower bounds. You'll need to compare a lower and an upper, or use a direct argument.
Also, the way the mathematical formulation are presented are not very professional (like the use of terms and punctuation). 
limitations_and_societal_impact: N/A
review_title: null

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