Differentially Private No-regret Exploration in Adversarial Markov Decision Processes
Shaojie Bai, Lanting Zeng, Chengcheng Zhao, Xiaoming Duan, Mohammad Sadegh Talebi, Peng Cheng, Jiming Chen
Abstract
We study learning adversarial Markov decision process (MDP) in the episodic setting under the constraint of differential privacy (DP). This is motivated by the widespread applications of reinforcement learning (RL) in non-stationary and even adversarial scenarios, where protecting users’ sensitive information is vital. We first propose two efficient frameworks for adversarial MDPs, spanning full-information and bandit settings. Within each framework, we consider both Joint DP (JDP), where a central agent is trusted to protect the sensitive data, and Local DP (LDP), where the information is protected directly on the user side. Then, we design novel privacy mechanisms to privatize the stochastic transition and adversarial losses. By instantiating such privacy mechanisms to satisfy JDP and LDP requirements, we obtain near-optimal regret guarantees for both frameworks. To our knowledge, these are the first algorithms to tackle the challenge of private learning in adversarial MDPs.
BibTeX
@InProceedings{pmlr-v244-bai24a,
title = {Differentially Private No-regret Exploration in Adversarial Markov Decision Processes},
author = {Bai, Shaojie and Zeng, Lanting and Zhao, Chengcheng and Duan, Xiaoming and Sadegh Talebi, Mohammad and Cheng, Peng and Chen, Jiming},
booktitle = {Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence},
pages = {235--272},
year = {2024},
editor = {Kiyavash, Negar and Mooij, Joris M.},
volume = {244},
series = {Proceedings of Machine Learning Research},
month = {15--19 Jul},
publisher = {PMLR},
pdf = {https://raw.githubusercontent.com/mlresearch/v244/main/assets/bai24a/bai24a.pdf},
url = {https://proceedings.mlr.press/v244/bai24a.html},
abstract = {We study learning adversarial Markov decision process (MDP) in the episodic setting under the constraint of differential privacy (DP). This is motivated by the widespread applications of reinforcement learning (RL) in non-stationary and even adversarial scenarios, where protecting users’ sensitive information is vital. We first propose two efficient frameworks for adversarial MDPs, spanning full-information and bandit settings. Within each framework, we consider both Joint DP (JDP), where a central agent is trusted to protect the sensitive data, and Local DP (LDP), where the information is protected directly on the user side. Then, we design novel privacy mechanisms to privatize the stochastic transition and adversarial losses. By instantiating such privacy mechanisms to satisfy JDP and LDP requirements, we obtain near-optimal regret guarantees for both frameworks. To our knowledge, these are the first algorithms to tackle the challenge of private learning in adversarial MDPs.}
}