기술 요약: 강화 학습에서의 정밀 삭제 (Exact Unlearning)

1. 문제 정의

본 논문은 강화 학습(RL), 특히 테이블형 마르코프 결정 과정(Tabular MDPs)의 맥락에서 정밀 삭제(Exact Unlearning) 문제를 다룹로다. 정적인 데이터 포인트를 다루는 지도 학습과 달리, RL 시스템은 사용자 및 상태, 행동, 보상의 궤적(Trajectories)을 생성하며 순차적으로 상호작용합니다.

핵심 목표는 사용자의 삭제 요청이 있을 때, 시스템이 해당 사용자의 상호작용 이력의 영향을 제거할 수 있는 효율적인 프레임워크를 설계하는 것입니다. 결과 모델은 삭제된 사용자가 시스템과 상호작용하지 않았던 것처럼, 남은 데이터로만 학습된 모델과 **분포상 구분이 불가능(Indistinguishable in distribution)**해야 합니다. 이는 정밀 삭제(정의 2.1)로 공식화되며, 임의의 사용자 시퀀스 $z_{1:T}$와 더미 $z'$로 대체된 삭제된 사용자 $z_t$에 대해, 삭제 알고리즘 $U$가 다음을 만족할 것을 요구합니다:
$$U(A(z_{1:T}), z_t, z') \stackrel{D}{=} A(z_1, \dots, z_{t-1}, z', z_{t+1}, \dots, z_T)$$

본 논문은 정밀 삭제를 (종종 차분 프라이버시(Differential Privacy)에 기반하는) *근사적 삭제(Approximate Unlearning)*와 구분하며, 아주 작은 잔류 영향력조차 프라이버시 침해나 안전성 위반으로 이어질 수 있는 고위험 애플리케이션(예: 의료, 개인화 비서)에서는 정밀 삭제가 필수적이라고 주장합니다.

2. 방법론

제안된 솔루션은 전변동(Total Variation, TV) 안정성, 이진 트리 메커니즘(Binary Tree Mechanisms), 그리고 **최대 결합(Maximal Coupling)**이라는 세 가지 주요 구성 요소를 통합합니다.

2.1. TV-안정성 및 삭제 프레임워크

저자들은 단일 데이터 포인트가 수정될 때 알고리즘의 출력 분포가 전변동 거리(Total Variation distance)에서 최대 $\rho$만큼 변화하는 개념인 $\rho$-TV-안정성(정의 2.2)을 기반으로 구축하였습니다. 저자들은 $\rho$-TV-안정성이 정밀 삭제를 위한 충분조건임을 입증하는 이론적 결과를 활용합니다.

삭제 메커니즘은 최대 결합에 의존합니다. 만약 알고리즘이 $\rho$-TV-안정적이라면, 원래 데이터로 학습된 모델의 분포($P$)와 사용자가 교체된 데이터의 분포($Q$)는 두 분포 간의 불일치 확률이 정확히 $\text{TV}(P, Q) \leq \rho$인 결합(Coupling)을 가집니다. 이를 통해 삭제 알고리즘은 다음을 수행할 수 있습니다:

1. 기존 모델 상태(P로부터 샘플링)를 $Q$에 대한 유효한 샘플로 재사용을 시도합니다.
2. 확률 $1 - \text{TV}(P, Q)$로 재사용을 수락합니다(재학습 없음).
3. 확률 $\text{TV}(P, Q)$로 재사용을 거부하고 처음부터 다시 학습하거나 특정 체크포인트에서 재학습을 수행합니다.

2.2. 접두사 합(Prefix Sums)을 위한 이진 트리 메커니즘

온라인 환경에서 TV-안정성을 달성하기 위해, 저자들은 차분 프라이버시의 이진 트리 메커니즘(Dwork et al., 2010)을 응용합니다.

• 구조: 원시 충분 통계량(예: 방문 횟수, 보상)을 직접 저장하는 대신, 각 노드가 노이즈가 섞인 접두사 합을 저장하는 완전 이진 트리를 유지합니다.
• 노이즈 주입: 이진 분해(Dyadic decomposition)를 통해 노드에 가우시안 노이즈를 추가합니다. 접두사 합 $u_t = \sum_{i=1}^t x_i$는 $O(\log T)$개의 노이즈 섞인 노드 값들을 합산하여 계산됩니다.
• 안정성: 이 구조는 단일 사용자의 데이터 $x_t$를 변경하는 것이 트리의 $O(\log T)$개 노드에만 영향을 미치도록 보장하여, 업데이트의 민감도를 제한하고 $\rho$-TV-안정성 보장을 가능하게 합니다.

2.3. 거부 샘플링(Rejection Sampling) 및 반사(Reflection)를 통한 삭제

삭제 알고즘(Algorithm 3)은 삭제된 리프 노드에서 루트까지 경로를 따라 이동합니다:

1. 클린 업데이트(Clean Update): $x_t$를 $x'_t$로 교체함을 반영하기 위해 경로상의 각 노드의 "클린(Clean)" 값을 업데이트합니다.
2. 노이즈 값 결합(Noisy Value Coupling): "노이즈" 값에 대해서는 거부 샘플링 단계를 수행합니다. 기존의 노이즈 값 $\tilde{v}_b$(기존 클린 평균 $v_b$ 하에서 생성됨)가 새로운 분포 $N(v'_b, \sigma^2 I)$로부터의 샘플로 취급될 수 있는지 확인합니다.
   • 수락: 수락되면 노드가 업데이트되고 프로세스가 부모 노드로 이동합니다.
   • 거부: 거부되면 알고 |즘은 반사 맵(Reflection map)(최대 결합 기법)을 적용하여 새로운 유효한 노이즈 값을 생성하고, 후순위 순회(Post-order traversal)의 다음 리프 노드부터 시작하는 재학습을 트리거합니다.

2.4. RL 알고리즘 인스턴스화 (노이즈가 포함된 UCB-VI)

저자들은 UCB-VI(Azar et al., 2017)를 수정하여 이 프레임워크를 테이블형 MDP에 적용합니다:

• 환경 오라클(Environment Oracle): 궤적 통계량(상태-행동 방문, 전이, 보상)을 접두사 합 구조로 인코딩합니다.
• 업데이트 함수: 노이즈가 섞인 접두사 합을 사용하여 낙관적인 가치 추정치를 계산합니다.
• 보너스 함수: 유한 샘플 추정 오차와 주입된 가우시안 노이즈로 인한 근사 오차를 모두 고려하는 특정 보너스 항 $b(\tilde{n})$을 도입합니다.

3. 주요 기여 및 결과

3.1. 알고리즘 보장

• 정밀 삭제: 제안된 알고리즘(Algorithm 2 + Algorithm 3)은 정밀 삭제를 달성합니다.
• 계산 효율성: 삭제의 기대 계산 비용은 처음부터 재학습하는 비용의 $\rho \sqrt{\ln T}$ 분량에 불과합니다. 재학습은 최대 결합이 실패할 때만 트리거되며, 이는 낮은 확률로 발생합니다.
• 후회 경계(Regret Bound): 알고리즘은 다음과 같은 후회 경계를 달성합니다:
  $$R(T) = \tilde{O}\left(H^2\sqrt{SAT} + H^3S^2A + \frac{H^{2.5}S^2A}{\rho}\right)$$
  여기서 $S$는 상태, $A$는 행동, $H$는 호라이즌, $T$는 에피소드입니다.
  • 처음 두 항은 표준 UCB-VI 동작에 해당합니다 ( $H^3S^2A$의 번인 비용 포함).
  • 세 번째 항은 노이즈를 통해 알고리즘을 안정화시키는 데 드는 비용을 나타냅니다.

3.2. 미니맥스 하한(Minimax Lower Bound)

본 논문은 모든 $\rho$-TV-안정적 RL 알고리즘에 대한 미니맥스 하한을 설정합니다:
$$R(T) = \Omega\left(H\sqrt{SAT} + \frac{HSA}{\rho}\right)$$
이 결과는 제안된 상한이 **거의 미니맥스 최적(Nearly minimax optimal)**임을 보여줍니다. 두 번째 항에서의 차이는 $H^{1.5}S$ 배수입니다. 저자들은 더 날카로운 분석(예: Hoeffding 유형 대신 Bernstein 유형의 보너스 사용)을 통해 이 격차를 좁힐 수 있다고 언급합니다.

3.3. 차분 프라이버시와의 비교

본 논문은 차분 프라이버시(DP)가 TV-안정성을 함의하지만, 그 역은 성립하지 않는다는 점을 강조합니다. 따라서 DP에 대한 하한이 TV-안정적 알고리즘에 자동으로 적용되지는 않습니다. 저자들은 자신들의 하한이 이전의 DP 기반 RL 하한보다 엄격하게 강력하다고 증명하는데, 이는 TV-안정성이 순수 DP보다 더 약한 제약 조건이기 때문입니다.

4. 의의 및 주장

본 논문은 강화 학습에서 증명 가능한 정밀 삭제를 위한 최초의 이론적 및 알고리즘적 프레임워크를 제공한다고 주장합니다. 그 의의는 다음과 같습니다:

1. 간극 해소: 배치 지도 학습에서 순차적이고 상호작용적인 RL 환경으로 정밀 삭제 이론을 확장했습니다.
2. 효율성: 정밀 삭제가 처음부터 전체 재학습을 하는 것보다 훨씬 낮은 계산 비용으로 달성될 수 있음을 입증하여, 대규모 상호작용 시스템(예: 추천 시스템, 음성 비서)에서 실현 가능하게 만들었습니다.
3. 최적성: 제안된 후회(Regret)와 삭제 안정성 사이의 트레이드오프가 거의 최적임을 확립했습니다.
4. 기초 단계: 삭제 가능한 알고리즘의 자연스러운 하위 클래스(TV-안정성을 가진 알고리즘)를 규정하고, 후회 최적 학습과 증명 가능한 삭제를 결មាន하는 엔드 투 엔드 보장을 제공합니다.

저자들은 다음과 같은 한계를 인정하며 겸허한 태도를 유지합니다:

• 결과가 현재 테이블형 MDP에 국한되어 있으며, 함수 근사(대규모/연속 상태 공간)로 확장하는 것은 여전히 미해결 과제로 남아 있습니다.
• 후회 분석에서 상한과 하한 사이에 무시할 수 없는 격차가 존재합니다.
• 이 접근 방식은 이진 트리 구조로 인해 선형 공간 복잡도($O(T)$)를 수반하며, 정밀 삭제를 위한 최적의 시공간-효용 트레이드오프는 아직 완전히 이해되지 않았습니다.