무작위 최소제곱 가치 반복 (Randomized Least Squares Value Iteration) 자체는 결합 차분 프라이버시

강화학습 (RL)이 의료 및 추천 시스템과 같은 민감한 영역에 점점 더 많이 적용됨에 따라, 사용자의 민감한 정보를 보호하기 위한 프라이버시 보존 기술 (privacy-preserving techniques)이 필수적이 되었습니다. 본 연구에서는 무작위 탐색 (randomized exploration)에 기반한 알고리즘, 예를 들어 무작위 최소제곱 가치 반복 (Randomized Least Squares Value Iteration, RLSVI)에 초점을 맞추어 에피소드 설정 (episodic setting) 하에서의 프라이버시 보존 RL을 조사합니다. 전체적인 목표는 무작위 탐색이 프라이버시 메커니즘에 의해 요구되는 주입된 노이즈 (injected noise)와 어떻게 상호작용하는지 연구하는 것입니다. 본 연구에서 우리는 탐색을 위해 설정된 RLSVI의 노이즈가 어떻게 동시에 프라이버시 보호를 제공하는지를 규명하는 새로운 프라이버시 분석을 제시합니다. 구체적으로, 우리는 RLSVI가 테이블형 MDP (tabular MDP)에서 $(\varepsilon(\delta), \delta)$-결합 차분 프라이버시 (joint differentially private)를 만족함을 증명하며, 이때 $\varepsilon(\delta) = \frac{2AK}{H^2\log(2HSA)} + 2\sqrt{\frac{2AK\log(1/\delta)}{H^2\log(2HSA)}}$ 입니다. 여기서 $S$와 $A$는 각각 상태 (states)와 행동 (actions)의 수이며, $H$는 에피소드 (episode)의 길이이고 $K$는 에피소드의 횟수입니다.