Research map / Federated learning and privacy / Differential privacy

Differentially Private Reinforcement Learning with Self-Play

NeurIPS 2024 · Federated learning and privacy › Differential privacy · approach: Private online and user-level learning · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Extends joint and local differential privacy to two-player zero-sum episodic Markov games and proposes DP-Nash-VI, an optimistic Nash value iteration algorithm with privatized Bernstein-type bonuses that achieves near-optimal regret under JDP and LDP.

Problem

Multi-agent reinforcement learning in two-player zero-sum Markov games must protect trajectory-wise privacy of users, which prior DP RL work (single-agent only) does not address.

Approach

Extend JDP and LDP definitions to Markov games and build a self-play optimistic Nash value iteration algorithm that uses privately released visitation counts (binary mechanism for JDP, Laplace noise for LDP) and privatized Bernstein-type UCB/LCB bonuses, with a post-processing LP to make private transitions valid distributions.

Key results

• Under epsilon-JDP, DP-Nash-VI achieves regret Õ(sqrt(H^2SABT) + H^3S^2AB/epsilon), with the main term nearly matching the non-private lower bound.
• Under epsilon-LDP, regret is Õ(sqrt(H^2SABT) + S^2AB sqrt(H^5T)/epsilon), with optimal dependence on K and epsilon per the stated lower bound.
• Without privacy, the bound reduces to the best known Õ(sqrt(H^2SABT)) for Markov games.

Measured effects reported in the paper

Limitations

• Additional privacy cost has sub-optimal dependence on Markov game parameters inherent to model-based algorithms.
• Optimal dependence on H,S,A,B for the lower bounds remains open.

Experimental setup

Metrics: regret PAC sample complexity

Baselines: Nash VI PUCB LDP-OBI Private-UCB-VI DP-UCBVI

Builds on: Nash value iteration UCBVI Bernstein-type bonuses Joint differential privacy for RL Local differential privacy for RL

Closest papers by meaning

• Differentially Private Regret Minimization in Episodic Markov Decision Processes (AAAI 2022 · similarity 0.92)
• Private Reinforcement Learning with PAC and Regret Guarantees (ICML 2020 · similarity 0.92)
• Local Differential Privacy for Regret Minimization in Reinforcement Learning (NeurIPS 2021 · similarity 0.92)
• On the Sample Complexity of Differentially Private Policy Optimization (NeurIPS 2025 · similarity 0.90)
• Towards Differentially Private Reinforcement Learning with General Function Approximation (NeurIPS 2026 · similarity 0.88)
• Contextualized Privacy Defense for LLM Agents (ICML 2026 · similarity 0.86)