Improved Regret for Differentially Private Exploration in Linear MDP

Watch a research presentation from the 2022 Symposium on Foundations of Responsible Computing where Giuseppe Vietri discusses improved regret rates for differentially private exploration in linear Markov Decision Processes (MDPs). Explore how to achieve privacy-preserving reinforcement learning in environments with sensitive data like medical records. Learn about a novel algorithm that maintains differential privacy while achieving optimal O(K^{1/2}) regret dependence on episode count through adaptive policy updates. Understand how this approach reduces privacy noise by limiting updates to only when significant data changes occur, resulting in just O(log(K)) total updates. Discover why this method shows minimal privacy cost impact in common privacy parameter scenarios, with privacy-related regret appearing only in lower-order terms compared to non-private approaches. Follow along through key concepts including differential privacy, function approximation, and least squares analysis.