  In decision-making problems, the actions of an agent may reveal sensitive
information that drives its decisions. For instance, a corporation's investment
decisions may reveal its sensitive knowledge about market dynamics. To prevent
this type of information leakage, we introduce a policy synthesis algorithm
that protects the privacy of the transition probabilities in a Markov decision
process. We use differential privacy as the mathematical definition of privacy.
The algorithm first perturbs the transition probabilities using a mechanism
that provides differential privacy. Then, based on the privatized transition
probabilities, we synthesize a policy using dynamic programming. Our main
contribution is to bound the "cost of privacy," i.e., the difference between
the expected total rewards with privacy and the expected total rewards without
privacy. We also show that computing the cost of privacy has time complexity
that is polynomial in the parameters of the problem. Moreover, we establish
that the cost of privacy increases with the strength of differential privacy
protections, and we quantify this increase. Finally, numerical experiments on
two example environments validate the established relationship between the cost
of privacy and the strength of data privacy protections.
