Private and Robust Learning for Decision Making

Overview

Decision-making algorithms are increasingly deployed in settings where data is both sensitive and unreliable. On the one hand, interactions between users and environments may reveal private information, calling for formal privacy guarantees. On the other hand, observed feedback—such as rewards or human preferences—often exhibits heavy tails, contamination, or systematic noise. These challenges motivate a study of private and robust decision-making.

This dissertation investigates how privacy and/or robustness affect the design and performance of decision-making learning algorithms. We develop a study that spans three increasingly expressive models: multi-armed bandits, reinforcement learning in Markov decision processes, and reinforcement learning from human feedback (RLHF).

We begin with private and robust multi-armed bandits as a foundational setting. Under heavy-tailed rewards and adversarial contamination, we establish minimax regret lower bounds that precisely characterize the cost of enforcing differential privacy and robustness. We then propose simple algorithms based on reward truncation and private robust estimation, achieving near-optimal regret. This part of the thesis reveals that a single statistical principle—controlled truncation—can simultaneously address privacy sensitivity and robustness to outliers.

Building on these insights, we extend the analysis to episodic reinforcement learning with heavy-tailed rewards. We develop private reinforcement learning algorithms under both joint and local differential privacy models, covering value-based and policy-based methods. Our regret guarantees explicitly quantify how privacy budgets and reward tail behavior affect learning efficiency. We further prove lower bounds that demonstrate a fundamental gap between private reinforcement learning with light-tailed and heavy-tailed rewards, highlighting the necessity of robustness-aware algorithm design.

Finally, we study private decision-making with human feedback through the lens of KL-regularized reinforcement learning from human preferences, a central paradigm in large language model alignment. We analyze both offline and online RLHF under local differential privacy on human labels. In the offline setting, we design pessimistic algorithms with optimal suboptimality guarantees under standard coverage assumptions. In the online setting, we propose optimism-based algorithms and establish logarithmic regret bounds characterized by an eluder-dimension–type complexity measure. These results provide the first theoretical guarantees for private online KL-regularized RLHF and yield new insights even in the absence of privacy constraints.

Overall, this dissertation studies private and robust decision-making. By connecting bandits, reinforcement learning, and RLHF, it clarifies fundamental limits, identifies reusable algorithmic principles, and contributes to the theoretical foundations of trustworthy learning systems that must operate under privacy requirements and imperfect data.