Course:CPSC522/Locally Differentially Private Reinforcement Learning

From UBC Wiki

Title

Principal Author: Yilin Yang

Here we will look at two papers that uses Linear Mixture Markov Decision Processes for Locally Differentially Private Reinforcement Learning (LDP-RL)


https://arxiv.org/pdf/2009.09052.pdf


https://arxiv.org/pdf/1703.07710.pdf


https://link.springer.com/chapter/10.1007/978-3-540-72927-3_23


Collaborators:

Abstract

Data safety issues nowadays have become more prevalent as we rely more on technology. In particular,

image tasks such as Medical Imaging are facing the challenge of privacy risks, adversaries can easily

obtain sensitive information through various attacks such as membership inference attacks [ 12 ].

This dramatically discourages patients and clients from contributing invaluable data that may be

beneficial to research. Additionally, traditional privacy measures such as adding noise or aggregating

the statistics are infeasible in high-dimensional settings [2 ]. This problem facilitates the need for

a gold standard privacy notion.


For this page, we will be skipping/briefly mentioning the many theoretical guarantees of these two papers as it is outside the scope of this course.

Builds on

Markov Decision Process (MDP)

Differential Privacy (DP)

Related Pages

This should contain the reverse links to the "builds on" links as well as other related pages. Use in sentences.

Paper 1: Markov Descision Process (MDP) and UBEV Algorithm [todo]

Here we breifly go over MDP, here the definition is slightly different from the CPSC 522 wiki page:

Following the notation by [todo] and Vietri et al.[1] The notation is slightly different for the two papers, here we will follow the notation by Vietri et al.[1] and define a time-dependent fixed-horizon Markov decision process (MDP) as , where:

  • a finite set of states.
  • is the finite set of actions.
  • is the reward function where has the range with mean , for a given time .
  • is the transition function, for state , action and time . The next state will be sampled from this distribution.
  • is the initial state distribution at time for each episode.
  • is the number of time steps in an interval , we also call this time interval an episode.
  • An agent will use a policy to determine its next action.
  • Here is the number of episodes, therefore the total timestep would be after episodes. Generally, we will follow the notation by Vietri et al.[1] and use to denote episode index.

In order to find the optimal policy, we first specify the two following definitions:

  • Given a policy and a time step , the value function is defined as:
  • For the entire episode, the expected total reward is defined as:

Using these two definitions, intuitively the optimal value function can be found by: for a given state and time . Any policy that achives the optimal value for all time and state is called an optimal policy. And the policy will acheieve the optimal (maximum) total reward.

The objective/goal for the agent is to learn a (near-)optimal policy after finite episodes, each episode the agent will take a policy given the prior information and outputs a policy for the next episode/output.

The UBEV Algorithm

Episodic RL

Algorithm 1: Episodic RL Protocol
Input: Agent  and users 
For  do:
 | For  do:
 |  |  sends state  to 
 |  |  sends action  to 
 |  |  sends reward  to 
 | End
End
 releases policy 

Background: Differential Privacy in RL

First proposed by Dwork et al. [2] Differential Privacy (DP) has risen in popularity in recent years as it has been recognized as the gold standard notion of privacy due to its useful properties of composition and post-processing invariance, the various mathematical details of DP will be omitted as it is outside the scope of this page and course. This section is not integral for the understanding of the paper, but is crucial to know if you are concerned with privacy in ML, therefore in this section we will first list the formal definition followed by a high-level intuition that is sufficient to understand the paper.

Joint Differential Privacy[1]

Definition: An agent is -jointly differentialy private (JDP) is for any time , all -neighboring user sequences , , and all events we have:

Here, the user scequence represents the scequence of users participating in the RL algorithmn. The is the depth of the tree structure for all state and reward sequences, overall the possible sequences can be denoted as , during the RL training the agent only has limited knowledge of each user, and only knows the single root-to-leaf path. We use to represent the output of the agent if the episode is removed, essentially removing all the sensitive information for user . Lastly, and are -neighboring user sequences if they only differ by the -th user.

Intuition of JDP

Generally, DP methods aim to protect specific users/data in a task by adding controlled noise from a known distribution to sensitive data so that the output will contain useful aggregated statistical information while also not revealing any specific participants data. For JDP, the controlled noise is from the Leplace distribution and is called the Laplace mechanism [todo], it ensures that when one of the users in the sequence changes, the learned information does not change greatly. It should be emphasized that this condition holds true even in the extreme case where all the remaining are adversarial users that use coordinated attack method to attempt to get the sensitive information of the remaining user by fixing the the state and actions.

Paper 2: Private Reinforcement Learning with PAC and Regret Guarantees [1]

So far we have introducted the MDP algorithmn and a privitaization method, in this paper the author privitizes the general episodic RL algorithmn and creates a DP variant that has many useful bounds and guarantees. The remaining element is the counting mechanism, which we will describe in the following section. The private counter mechanism takes a stream of data as input and releases an approximation of the prefix count.

Private Counting Mechanism

The counting mechanism is a method used to keep track of events that occur while interacting with an MDP (Markov Decision Process). Following the definitions by Vietri et al.[1] Here we outline the notation for the counters needed for MDP to work. Let be the number of vists to state before episode , where the state tuple contains the action taken on the state on time step before episode . However as this counter depends on sensitive data in our defined sceanario, we must derive a method that privately releases the counts. The private counter mechanism takes a data stream as input and releases an approximation of the prefix count. We denote this privacy counting mechanism as PC and it takes and as input paramters, thus for all , we have:

However as this bound only applies to a single -DP counter, maintaining all counters will incur a large amount of weight that sclaes polynomailly with , and . Here the authors use the fact that the total change across all counters a user can have scales linearly with the episode to add a much smaller amount of DP noise.

Now that we have all the ingredients, we can finally introduce the private MDP algorithm introduced by this paper called the PUCB algorithm:

The PUCB Algorithm[1]

At a high level, Private Upper Confidence Bound (PUCB) is a variation of the UBEV [todo] algorithm, specifically designed for privacy-sensitive environments using JDP. The pseudo-code is shown in Algorithm 2. The calculatated policy at each step depends on the average empirical reward , the number of times the agent has been to state and the number of times the agent has transitioned from to state , denoted as . Thus in the PUCB, as the policy only depends on these privitized statistics from the private counters, if we set the privacy level correctly (adding the correct amount of controlled noise), JDP is satisfied.

Algorithm 2: Private Upper Confidence Bound (PUCB)                                                                                                                                

Parameters: Privacy parameter , target failure probability 
Input: Maximum number of episodes , horizon , state space , action space 

For  do:
 | Initialize private counters: 
End
For  ← 1 to  do:
| Private planning: 
| For  ← 1 to  do:
|  |  Let  denote the state during step  and episode 
|  |  Execute 
|  |  Observe  and 
|  |  Feed r to 
|  |  Feed 1 to  and  and 0 to all other counters  and
|  |  
| End
End

Private Counting Details: The PUCB initilzes private counters for all , , and . By requiring that each set of counters ( , , and ) is -JDP, with

we can ensure that thus for all , we have:
Here the and are the count and release right before episode , this guarantee is uniform in and also holds simultaneously for and . Similar to the Private Counting Mechanism, the full understanding of the details above is not required.

In algorithm 3, we calculate the private Q-function for t-th episode, PrivQ is a standard batch Q-learning update, with serving as an optimism bonus. The resulting Q-function, denoted as , is a greedy policy which we use for the t-th episode.

Algorithm 3: PrivQ
Input: Private counters  privacy parameter , target failure probability 


For  ← 1 to  do:
 | For  do:
 |  | If  then:
 |  |  | 
 |  | Else:
 |  |  | 
 |  | End
 |  | 
 |  | 
 | End
 | 
End
Output: 

Here the bonus function for each can be decomped to two components and where:

The component can be roughly thought of as the sampling error, where represents the errors introduced by private counters.

Notible theoretical guarantees of the PUCB Algorithm

In the section we breifly showcase two of the theoretical guarantees of the PUCB alogorithmn, we first introduce two definitions used the evaulate similar problem, PAC and Regret before we show the bounds proved by this paper.

PAC in RL:

An agent is called -probably approximately correct (PAC) with sample complexity , if it follows an -optimal policy such that except for at most episodes with at least proability of .

Regret in RL:

The (expected cumulative) regret of an agent after episodes is given by:

where are the policies the agent follows for each episode .

Theorem 3 (PAC guarantee for PUCB)[1] PUCB follows a policy that with probability at least is -optimal on all but

episodes, where .

This mean that suffient epiodes of PUCB, a large fraction of the episodes will act near-optimally. The cost of privacy is very low as the privacy parameter is only in the term scaling as , and typically is small and this term is of a lower order.

Theorem 3 (Regret bound for PUCB)[1] With probability at least , the regret of PUCB up to episode is at most

The remark is similar to the PAC guarantee, as the privacy parameter is only in the term scaling , the utilitiy cost for privacy is negligible as the leading order term scales with . If the readers are interested in the proof, a high level sketch as well as the detailed proof is provided in the paper.

Conclusion

This paper provide a novel study of reinforment learning with differential privacy, the authors utilizes joint differential privacy to select future decisions based off privitazed data rether than sensitive data. The paper established a JDP alortihmn along with an analysis for its PAC and regret utility guarantees. Surprisingly, the utility cost for privacy is asymptotically negligible, in the future the author plans to further close the bound between DP and non-DP settings as well as the designing RL algorithmns in non-tabular settings has the potential to many real-life applications.

Annotated Bibliography

Put your annotated bibliography here. Add links where appropriate.

  1. 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 Vietri, Giuseppe; et al. "Private Reinforcement Learning with PAC and Regret Guarantees" (PDF). International Conference on Machine Learning – via arxiv. line feed character in |journal= at position 36 (help)
  2. Dwork, Cynthia; Roth, Aaron (2014). The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science.

To Add

Put links and content here to be added. This does not need to be organized, and will not be graded as part of the page. If you find something that might be useful for a page, feel free to put it here.

https://papers.nips.cc/paper/2017/file/17d8da815fa21c57af9829fb0a869602-Paper.pdf


Following the definitions by Ngo & Vietri et al.[1] The difference between LMDP and MDP is the additional assumtion that the reward function and transiton functions are linear. Therefore we can focus on linear action-value funtions.

Linear MDP [TODO]

A deterministic policy is

Some rights reserved
Permission is granted to copy, distribute and/or modify this document according to the terms in Creative Commons License, Attribution-NonCommercial-ShareAlike 3.0. The full text of this license may be found here: CC by-nc-sa 3.0
By-nc-sa-small-transparent.png
  1. Ngo, Dung Daniel; Vietri, Giuseppe; et al. "Improved Regret for Differentially Private Exploration in Linear MDP" (PDF). International Conference on Machine Learning.