MDP for Differentially Private Reinforcement Learning

MDP for Differentially Private Reinforcement Learning Using the PUCB Algorithm

Principal Author: Yilin Yang

Here we will look at two papers that use Markov Decision Processes for Reinforcement Learning, the first paper will introduce an algorithm that has very good theoretical bounds, and the second paper will construct a variant of the algorithm proposed by the first algorithm that has Differentially Private (DP) guarantees.

Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning

Private Reinforcement Learning with PAC and Regret Guarantees

Collaborators:

Abstract

Data safety issues nowadays have become more prevalent as we rely more on technology. For Episodic RL applications, states and awards of the MDP may contain sensitive information such as personalized medical treatment applications. In this scenario, users/patients will communicate with the agent for a fixed duration and obtain a corresponding medical treatment. As information is sensitive and will influence the policy produced, it will affect the subsequent actions as well. Adversarial users can input intentional, coordinated data in an attempt to reveal the sensitive state and actions of a target user. These harmful attack methods facilitate a need for a gold standard privacy notion. In recent years, DP has risen in popularity as it provides many useful properties and is a mathematical guarantee of privacy. The UBEV Algorithm proposed by Dann et al. is a recent advancement in the episodic RL regime, providing both near-optimal PAC and regret guarantees, this has inspired Vietri et al. to create PUCB, a privatized variant of UBEV. For this page, we will be introducing the definitions and required background information to understand both papers, and introduce the pseudo-code of the two algorithms as well as their PAC and regret guarantees.

Builds on

Markov Decision Process (MDP)

Reinforcement Learning

Differential Privacy (DP)

Related Pages

Q-Learning and MDP for healthcare are two interesting reads related to these two papers

Paper 1 Background: Markov Decision Process (MDP), Q-learning, and Episodic RL

Following the notation by Dann et al. and Vietri et al., here we briefly go over MDP, the notation is slightly different for the two papers, here we will follow the notation by Vietri et al. as it is our main focus and define a time-dependent fixed-horizon Markov decision process (MDP) as $M=(S,A,R,P,p_{0},H)$, where:

• $S$ is a finite set of states.
• $A$ is the finite set of actions.
• $R$ is the reward function where $R(s_{h},a_{h},h)$ has the range $[0,1]$ with mean $r(s_{h},a_{h},h)$, for a given time $h\in [H]$.
• $P(s_{h+1}|s_{h},a_{h},h)$ is the transition function, for state $s_{h}$, action $a_{h}$ and time $h\in [H]$. The next state $s_{h+1}$ will be sampled from this distribution.
• $p_{0}$ is the initial state distribution at time $h=0$ for each episode.
• $h$ is the number of time steps in an interval $H$, we also call this time interval an episode.
• An agent will use a policy $\pi \in \Pi \ s.t.\pi (s,h)\in A$ to determine its next action.
• Here $T$ is the number of episodes, therefore the total timestep would be $HT$ after $T$ episodes. We use $t$ to denote the episode index.

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

• Given a policy $\pi$ and a time step $h\in [H]$, the value function is defined as:
  $$V_{h}^{\pi }(s)=\mathbb {E} {\bigg [}\sum _{i=h}^{H}r(s_{i},a_{i},i){\bigg |}s_{h}=s,\pi {\bigg ]}=r(s,\pi (s,h),h)+\sum _{s'\in S}V_{h+1}^{\pi }(s')P(s'|s,\pi (s,h),h)$$

• For the entire episode, the expected total reward is defined as:
  $$\rho ^{\pi }=\mathbb {E} {\bigg [}\sum _{i=1}^{H}r(s_{i},a_{i},i){\bigg |}\pi {\bigg ]}=p_{0}^{\top }V_{1}^{\pi }$$

Using these two definitions, intuitively the optimal value function can be found by: $V_{h}^{*}(s)=\max _{\pi \in \Pi }V_{h}^{\pi }(s)$ for a given state $s\in [S]$ and time $h\in [H]$. Any policy that achieves the optimal value for all times and states is called an optimal policy. And the policy will achieve the optimal (maximum) total reward.

Q-Learning

In reinforcement learning, for any finite Markov decision process (FMDP), we can use Q-learning to learn the MDP task. For those who are interested in the details of Q-learning, the related page on Q-Learning is strongly recommended. From a high level, Q-Learning is an algorithm that finds the optimal policy by maximizing the expected total reward $\rho ^{\pi }$ for all successive steps starting from the current state. Given infinite exploration time, Q-learning can find an optimal action-selection policy for any MDP. An example of a Q-function can be found on the Q-Learning page. In our papers, the Q-function will be defined differently.

Episodic RL

The objective/goal for the agent is to learn a (near-)optimal policy after finite episodes, each episode the agent will take a policy $\pi$ given the prior information and outputs a policy $\pi$ for the next episode/output. Using MDP, we can construct an episodic RL algorithm as follows:

Algorithm 0: Episodic RL Protocol
Input: Agent $\mathrm {M}$ and users $u_{1},\dots ,u_{T}$
For $t\in [T]$ do:
 | For $h\in [H]$ do:
 |  | $u_{t}$ sends state $s_{h}^{(t)}$ to $\mathrm {M}$
 |  | $\mathrm {M}$ sends action $a_{h}^{(t)}$ to $u_{t}$
 |  | $u_{t}$ sends reward $r_{h}^{(t)}$ to $\mathrm {M}$
 | End
End
$\mathrm {M}$ releases policy $\pi$

Here, in contrast to directly interacting with an environment, the agent $\mathrm {M}$ will communicate with a user $u_{t}$ for a fixed horizon for all users. Each $u_{t}$ will interact with the environment and send their current state and $\mathrm {M}$ will recommend an action, and $u_{t}$ will send the reward received to $\mathrm {M}$.

Paper 1: Markov Decision Process (MDP) and UBEV Algorithm

We now introduce the UBEV Algorithm, to the authors' knowledge, UBEV is the first algorithm with both near-optimal PAC and regret guarantees (We will introduce PAC and regret in the analysis section):

The UBEV Algorithm

At a high level, during each episode $t$, the agent follows an optimal policy $\pi _{t}$ by backward induction and a curated confidence interval for the transition probabilities in each state. Here $Q(a)$ is an optimistic estimate of the Q-function for the current $(s,a,h)$ using the empirical estimates of the next state value ${\hat {V}}_{\text{next}}$, and the expected immediate reward ${\hat {r}}$ and the confidence bounds $(H-h)\phi$ and $\phi$. Additionally, $n(s,a,h),l(s,a,h),$ and $m(s',s,a,h)$ are the counters used to make MDP work, we will be outlining the details in the second paper as the high-level intuition is very similar.

Algorithm 1: Upper Bounding the Expected Next State Value (UBEV)
Input: Failure tolerance $\delta \in (0,1]$
$n(s,a,h)=l(s,a,h)=m(s',s,a,h)=0$; ${\widetilde {V}}_{H+1}(s'):=0\ \ \ \forall s,s'\in S\times S,a\in A,h\in [H]$
For $t\in [T]$ do:
 | /* Optimistic planning */
 | For $h\in [H]$ do:
 |  | For $s\in S$ do:
 |  |  | For $a\in A$ do:
 |  |  |  | $\phi :={\sqrt {\frac {2\ln \ln(\max\{e,n(s,a,h)\})+\ln(18SAH/\delta )}{n(s,a,h)}}}$ // confidence bound
 |  |  |  | ${\hat {r}}:={\frac {l(s,a,h)}{n(s,a,h)}}$; ${\hat {V}}_{\text{next}}:={\frac {m(\cdot ,s,a,h)^{\top }{\widetilde {V}}_{h+1}}{n(s,a,h)}}$ // empirical estimates
 |  |  |  | $Q(a):=\min\{1,{\hat {r}}+\phi \}+\min {\bigg \{}\max\{{\tilde {V}}_{t+1},{\hat {V}}_{\text{next}}+(H-t)\phi \}{\bigg \}}$
 |  |  | End
 |  |  | $\pi _{t}(s,h):={\text{argmax}}_{a}Q(a)$, ${\widetilde {V}}_{h}(s):=Q(\pi _{t}(s,h))$
 |  | End
 | End
 | /* Execute policy for one episode */
 | $s_{1}\sim p_{0}$
 | For $h\in [H]$ do:
 |  | $a_{h}:=\pi _{t}(s_{h},h)$, $r_{h}\sim R(s_{h},a_{h},h)$ and $s_{h+1}\sim P(s_{h},a_{h},h)$
 |  | $n(s_{h},a_{h},h)$++; $m(s_{h+1},s_{h},a_{h},h)$++; $l(s_{h},a_{h},h)$ += $r_{h}$ // update statistics
 | End
End

Notible theoretical guarantees of the UBEV Algorithm

In this section we briefly showcase two of the theoretical guarantees of the UBEV algorithm, we first introduce two definitions used the evaluate these types of algorithms——PAC and Regret before we show the bounds proved by this paper.

PAC in RL:

An agent is called $(\alpha ,\beta )$-probably approximately correct (PAC) with sample complexity $f(S,A,H,{\frac {1}{\alpha }},\log({\frac {1}{\beta }}))$, if it follows an $\alpha$-optimal policy $\pi$ such that $\rho ^{*}-\rho ^{\pi }\leq \alpha$ except for at most $f(S,A,H,{\frac {1}{\alpha }},\log({\frac {1}{\beta }}))$ episodes with at least proability of $\beta$ .

Regret in RL:

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

$${\text{Regret}}(T)=\sum _{t=1}^{T}(\rho ^{*}-\rho ^{\pi _{t}})$$

where $\pi _{1},\dots ,\pi _{T}$ are the policies the agent follows for each episode $t$.

Theorem 1 (PAC guarantee for UBEV) UBEV follows a policy that with probability at least $1-\beta$ is $\alpha$-optimal on all but

$${\bigg (}{\frac {SAH^{4}}{\alpha ^{2}}}\min\{1+\alpha S^{2}A,S\}\ {\text{polylog}}(A,S,H,{\frac {1}{\alpha }},{\frac {1}{\beta }}){\bigg )}$$

episodes, where $\alpha \in (0,H]$. Here the ${\text{polylog}}(x,\dots )$ is a function that is bounded by a polynomial of logarithms, that is: ${\textstyle \exists k,C\ :\ {\text{polylog}}(x,\dots )\leq \ln(x,\dots )^{k}+C}$

Theorem 2 (Regret bound for UBEV) With probability at least $1-\beta$ , the regret of UBEV for all episodes $T$ is at most:

$$O{\bigg (}(H^{2}{\sqrt {SAT}}+S^{3}A^{2})\ {\text{polylog}}(T,S,A,H){\bigg )}$$

For people interested in the proof details, a high-level sketch, as well as the detailed proof, is provided in the paper. To the authors' knowledge, UBEV is the first algorithm with both near-tight (up to a factor of $H$) high probability regret and $(\alpha ,\beta )$-PAC bounds as well as the first algorithm with any nontrivial uniform-PAC bound. The good theoretical guarantees in the first paper essentially motivated and inspired the authors from the second paper to incorporate privacy concerns into this algorithm, starting an interesting line of research. Thus, in the following sections, we will first formally define privacy, as well as provide a high-level intuition for the privacy setting, we will then introduce the PUCB algorithm, and discuss the results.

Paper 2 Background: Differential Privacy in RL

First proposed by Dwork et al. 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

Definition: An agent $\mathrm {M}$ is $\varepsilon$-jointly differentialy private (JDP) is for any time $t$, all $t$-neighboring user sequences $U$, $U'$, and all events $E\subseteq A^{H\times [T-1]}\times \Pi$ we have:

$$\Pr[\mathrm {M} _{-t}(U)\in E]\leq e^{\varepsilon }\Pr[\mathrm {M} _{-t}(U')\in E]$$

Here, the user sequence $U=(u_{1},\dots ,u_{T})$ represents the sequence of $T$ users participating in the RL algorithm. The $H$ is the depth of the tree structure for all state and reward sequences, overall the possible sequences can be denoted as $A^{H}$, during the RL training the agent only has limited knowledge of each user, and only knows the single root-to-leaf path. We use $\mathrm {M} _{-t}(U)$ to represent the output of the agent if the episode $t$ is removed, essentially removing all the sensitive information for user $t$. Lastly, $U$ and $U'$ are $t$-neighboring user sequences if they only differ by the $t$-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 participant's data. For JDP, the controlled noise is from the Laplace distribution and is called the Laplace mechanism , it ensures that when one of the users in the sequence $T$ 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 $T-1$ are adversarial users that use coordinated attack methods to attempt to get the sensitive information of the remaining user by fixing the state and actions.

Paper 2: Private Reinforcement Learning with PAC and Regret Guarantees

So far we have introduced the UBEV algorithm and a privatization method, in this paper, the author privatizes the general episodic RL algorithm and creates a DP variant that has many useful bounds and guarantees. The remaining element is the counting mechanism, similar to states and values, counts for the states and actions visted are also considered private. Therefore we will describe in the following section a private counter mechanism that takes a stream of data as input and releases an approximation of such a 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. Here we outline the notation for the counters needed for MDP to work. Let ${\widehat {n_{t}}}(s,a,h)$ be the number of visits to state $(s,a,h)$ before episode $t$, where the state tuple contains the action $a$ taken on the state $s$ on time step $h$ before episode $t$. However as this counter depends on sensitive data in our defined scenario, 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 count. We denote this privacy counting mechanism as PC and it takes $\varepsilon$ and $T$ as input parameters, thus for all $1\leq t\leq T$, we have:

$$\Pr {\bigg (}{\big |}\mathrm {M} (\sigma )(t)-c(\sigma )(t){\big |}\leq {\frac {4}{\varepsilon }}\ln(1/\beta )\log(T)^{5/2}{\bigg )}\geq 1-\beta$$

However as this bound only applies to a single $\varepsilon$-DP counter, maintaining all $S^{2}AH$ counters will incur a large amount of weight that scales polynomially with $S$, $A$ and $H$. Here the authors use the fact that the total change across all counters a user can have scales linearly with the episode $H$ 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

At a high level, Private Upper Confidence Bound (PUCB) is a variation of the UBEV algorithm, specifically designed for privacy-sensitive environments using JDP. The pseudo-code is shown in Algorithm 2. The calculated policy at each step depends on the average empirical reward ${\widetilde {r}}(s,a,h)$, the number of times ${\widetilde {n}}(s,a,h)$ the agent has been to state $(s,a,h)$ and the number of times the agent has transitioned from $(s,a,h)$ to state $s'$, denoted as ${\widetilde {m}}(s,a,s',h)$. Thus in the PUCB, as the policy only depends on these privatized 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 $\varepsilon$, target failure probability $\beta$
Input: Maximum number of episodes $T$, horizon $H$, state space $S$, action space $A$
$\varepsilon ':=\varepsilon /(3H)$
For $s,a,s',h\in S\times A\times S\times [H]$ do:
 | Initialize private counters: ${\widetilde {r}}(s,a,h),{\widetilde {n}}(s,a,h),{\widetilde {m}}(s,a,s',h):={\text{PC}}(T,\varepsilon ',\beta )$
End
For $t$ ← 1 to $T$ do:
| Private planning: ${\widetilde {Q}}_{t}^{+}:={\text{PrivQ}}({\tilde {r}},{\tilde {n}},{\tilde {m}},\varepsilon ,\beta )$
| For $h$ ← 1 to $H$ do:
|  |  Let $s$ denote the state during step $h$ and episode $t$
|  |  Execute $a:={\text{argmax}}_{a'}{\widetilde {Q}}_{t}^{+}(s,a',h)$
|  |  Observe $r\sim R(s,a,h)$ and $s'\sim P(\cdot |s,a,h)$
|  |  Feed r to ${\widetilde {r}}(s,a,h)$
|  |  Feed 1 to ${\widetilde {n}}(s,a,h)$ and ${\widetilde {m}}(s,a,s',h)$ and 0 to all other counters ${\widetilde {n}}(\cdot ,\cdot ,h)$ and
|  |  ${\widetilde {m}}(\cdot ,\cdot ,\cdot ,h)$
| End
End

Private Counting Details: The PUCB initilzes $2SAH+S^{2}AH$ private counters for all ${\widetilde {r}}_{t}$, ${\widetilde {n}}_{t}$, and ${\widetilde {m}}_{t}$. By requiring that each set of counters ( $\{{\widetilde {r}}_{t}\}$, $\{{\widetilde {n}}_{t}\}$, and $\{{\widetilde {m}}_{t}\}$) is $\varepsilon /3$-JDP, with

$$E_{\varepsilon }={\frac {3}{\varepsilon }}H\log {\bigg (}{\frac {2SAH+S^{2}AH}{\beta '}}{\bigg )}\log(T)^{5/2}$$

we can ensure that thus for all $1\leq t\leq T$, we have:

$$\Pr {\bigg (}{\big |}{\widehat {n}}_{t}(s,a,h)-{\widetilde {n}}_{t}(s,a,h){\big |}<E_{\varepsilon }{\bigg )}\geq 1-\beta$$

Here the ${\widehat {n}}_{t}$ and ${\widetilde {n}}_{t}$ are the count and release right before episode $t$, this guarantee is uniform in $(s,a,h)$ and also holds simultaneously for ${\widetilde {r}}_{t}$ and ${\widetilde {m}}_{t}$. Similar to the Private Counting Mechanism, a full understanding of the details above is not required.

In algorithm 3, we calculate the private Q-function for the $t$-th episode, PrivQ is a standard batch Q-learning update, with ${\widetilde {conf}}_{t}(s,a,h)$ serving as an optimism bonus. The resulting Q-function denoted as ${\widetilde {Q}}_{t}^{+}$, is a greedy policy that we use for the t-th episode.

Algorithm 3: PrivQ
Input: Private counters ${\tilde {r}},{\tilde {n}},{\tilde {m}},$ privacy parameter $\varepsilon$, target failure probability $\beta$
$E_{\varepsilon }:={\frac {3}{\varepsilon }}H\log {\bigg (}{\frac {2SAH+S^{2}AH}{\beta '}}{\bigg )}\log(T)^{5/2}$
${\widetilde {V}}_{H+1}(s):=0\ \ \ \ \ \forall s\in S$
For $h$ ← 1 to $H$ do:
 | For $s,a\in S\times A$ do:
 |  | If ${\widetilde {n}}(s,a,h)\geq 2E_{\varepsilon }$ then:
 |  |  | ${\widetilde {conf}}_{t}(s,a,h):=(H+1){\widetilde {\phi }}_{t}(s,a,h)+{\widetilde {\psi }}_{t}(s,a,h)$
 |  | Else:
 |  |  | ${\widetilde {conf}}_{t}(s,a,h):=H$
 |  | End
 |  | ${\widetilde {Q}}_{t}(s,a,h):={\frac {1}{{\tilde {n}}_{t}(s,a,h)}}{\bigg (}{\tilde {r}}_{t}(s,a,h)+\sum _{s\in S}{\widetilde {V}}_{h+1}(s'){\widetilde {m}}_{t}(s,a,s',h){\bigg )}$
 |  | ${\tilde {Q}}_{t}^{+}(s,a,h):=\min {\bigg \{}H,{\widetilde {Q}}_{t}(s,a,h)+{\widetilde {\text{conf}}}_{t}(s,a,h){\bigg \}}$
 | End
 | ${\widetilde {V}}_{h}(s):=\max _{a}{\widetilde {Q}}_{t}^{+}(s,a,h)\ \ \ \ \ \ \forall s\in S$
End
Output: ${\tilde {Q}}_{t}^{+}$

Here the bonus function ${\widetilde {conf}}_{t}(s,a,h)$ for each $(s,a,h)$ can be decomped to two components ${\widetilde {\phi }}_{t}(s,a,h)$ and ${\widetilde {\psi }}_{t}(s,a,h)$ where:

$${\widetilde {\phi }}_{t}(s,a,h)={\sqrt {\frac {2\ln(T/\beta ')}{\max({\widetilde {n}}_{t}(s,a,h)-E_{\varepsilon },1)}}}$$

$${\widetilde {\psi }}_{t}(s,a,h)=(1+SH){\bigg (}{\frac {3E_{\varepsilon }}{{\widetilde {n}}_{t}(s,a,h)}}+{\frac {2E_{\varepsilon }^{2}}{{\widetilde {n}}_{t}(s,a,h)^{2}}}{\bigg )}$$

The component ${\widetilde {\phi }}_{t}(s,a,h)$ can be roughly thought of as the sampling error, where ${\widetilde {\psi }}_{t}(s,a,h)$ represents the errors introduced by private counters.

Notable theoretical guarantees of the PUCB Algorithm

Theorem 3 (PAC guarantee for PUCB) PUCB follows a policy that with probability at least $1-\beta$ is $\alpha$-optimal on all but

$$O{\bigg (}{\bigg (}{\frac {SAH^{4}}{\alpha ^{2}}}+{\frac {S^{2}AH^{4}}{\varepsilon \alpha }}{\bigg )}{\text{polylog}}(T,S,A,H,{\frac {1}{\alpha }},{\frac {1}{\beta }},{\frac {1}{\varepsilon }}){\bigg )}$$

episodes, where $\alpha \in (0,H]$.

This means that with sufficient episodes of PUCB, a large fraction of the episodes will act near-optimally. The cost of privacy is very low as the privacy parameter $\varepsilon$ is only in the term scaling as ${\frac {1}{\alpha }}$, and typically $\alpha$ is small and this term is of a lower order.

Theorem 4 (Regret bound for PUCB) With probability at least $1-\beta$ , the regret of PUCB up to episode $T$ is at most

$$O{\bigg (}{\bigg (}H^{2}{\sqrt {SAT}}+{\frac {SAH^{3}+S^{2}AH^{3}}{\varepsilon }}{\bigg )}{\text{polylog}}(T,S,A,H,{\frac {1}{\beta }},{\frac {1}{\varepsilon }}){\bigg )}$$

The remark is similar to the PAC guarantee, as the privacy parameter $\varepsilon$ is only in the term scaling ${\text{polylog}}(T)$, the utility cost for privacy is negligible as the leading order term scales with ${\sqrt {T}}$. There is a PAC and a regret guarantee. For the readers interested in the proof details, a high-level sketch and detailed proof are provided in the paper.

Conclusion

In this page, we introduced two novel RL algorithms that have outstanding theoretical guarantees. In the first paper, we introduced the UBEV algorithm, UBEV is the first algorithm with both near-tight (up to a factor of $H$) high probability regret and $(\alpha ,\beta )$-PAC bounds as well as the first algorithm with any nontrivial uniform-PAC bound. This novel advancement has inspired researchers to consider a DP setting, where user data is considered sensitive, here the authors utilize joint differential privacy to select future decisions based on privatized data rather than sensitive data. The paper established a JDP algorithm along with an analysis of its PAC and regret utility guarantees. Surprisingly, the author has proven that the utility cost for privacy is asymptotically negligible, creating a novel direction in differentially private algorithms. For future work, the author plans to further close the bond between DP and non-DP settings as well as design RL algorithms in non-tabular environments such as real-life applications.

Annotated Bibliography

Put your annotated bibliography here. Add links where appropriate.

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.