mdp.tex

In differential privacy, an \emph{offline} mechanism releases outputs only
once and plays no further role; an \emph{online} (or \emph{interactive}) mechanism
allows analysts to ask queries adaptively based on previous
responses. The mechanisms considered previously are offline
mechanisms. 
Since offline mechanisms only release one query result, they are
relatively easy to analyze. For online mechanisms, one has to consider
all possible adaptive queries. We therefore use MDPs to model these
non-deterministic behaviors.
Specifically, adaptive queries are modeled by
actions. Randomized computation associated with different queries is
modeled by distributions associated with actions.

\hide{
On the other hand, online mechanisms permit further queries. 
To maintain
privacy, online mechanisms may decide to release
information differently. For instance, they may disable further
queries after a certain output is disclosed.
}

Consider again the survey mechanism. Suppose we would like to design
an interactive mechanism which adjusts random noises on surveyors'
requests. When the surveyor requests low-accuracy answers, the
surveyee uses the survey mechanism in Section~\ref{subsec:survey}. 
When high-accuracy
answers are requested, the surveyee answers $1$ with
probability $\frac{4}{5}$ and $0$ with probability $\frac{1}{5}$ when she has
positive diagnosis. She answers $1$ with probability $\frac{1}{5}$
and $0$ with probability $\frac{4}{5}$ when she is not
diagnosed with the disease X. This gives an interactive mechanism
corresponding to the MDP shown in
Figure~\ref{figure:simple-mdp}.

\begin{wrapfigure}[14]{r}{.45\columnwidth}
%\begin{figure}
  \centering
    \resizebox{.45\columnwidth}{!}{
    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node
      distance=2cm,node/.style={circle,draw}]
      \node[node] (p) at ( 0,  1.5) { $+$ };
      \node[node] (q) at ( 0, -1.5) { $-$ };
      \node[node] (F) at (-1.5,  0) { $s$ };
      \node at (-2, .5) { $\mathit{out}_Y$ };
      \node[node] (T) at ( 1.5,  0) { $t$ };
      \node at ( 2, .5) { $\mathit{out}_N$ };

      \path
      (p) edge [bend right=45] node [left] { $L, .75$ } (F)
      (p) edge [bend left=45] node [right] { $L, .25$ } (T)
      (p) edge [bend left=45] node [right=-12,above] { $H, .8$ } (F)
      (p) edge [bend right=45] node [right=12,above] { $H, .2$ } (T)

      (q) edge [bend left=45] node [left] { $L, .25$ } (F)
      (q) edge [bend right=45] node [right] { $L, .75$ } (T)
      (q) edge [bend right=45] node [left=12,below] { $H, .2$ } (F)
      (q) edge [bend left=45] node [right=12,below] { $H, .8$ } (T)

%      (F) edge [loop left] node [below] { $-, 1$ } (F)
%      (T) edge [loop right] node [below] { $-, 1$ } (T)
      ;
      \end{tikzpicture}
    }
    \caption{Markov Decision Process}
    \label{figure:simple-mdp}
\end{wrapfigure}
%\end{figure}

\hide{Mechanisms are not necessarily closed randomized algorithms; they may
perform different computation on users' requests.
We use Markov decision processes to model such
interactive mechanisms. Specifically, external inputs are modeled by
actions. Behaviors associated with different inputs are modeled by
distributions associated with actions.
}

In the figure, the states $+$,
$-$, $s$, and $t$ are interpreted as before. The actions $L$ and $H$
denote low- and high-accuracy queries respectively. 
Note that the high-accuracy survey mechanism is $(\ln
4,0)$-differentially private. Unlike non-interactive mechanisms, the
privacy guarantees vary from queries with different accuracies.