Learning Kernel-Based MDPs from Episodic Preferential Feedback

기술적 요약: 에피소드적 선호 피드백을 통한 커널 기반 MDP 학습

문제 정의
본 연구는 에피소드적 마르코프 결정 과정 (MDP) 환경 내 인간 피드백을 통한 강화 학습 (RLHF) 문제를 다룹니다. 에이전트가 스칼라 보상을 받는 표준 RL 과 달리, 여기서는 학습자가 이진 선호 피드백만을 받습니다. 각 에피소드 $k$에서 학습자는 공통 시작 상태에서 두 정책 $\pi$와 $\pi'$를 배포하여 두 개의 궤적 $\tau_k$와 $\tau'_k$를 생성합니다. 피드백은 어느 궤적이 선호되는지를 나타내는 단일 이진 레이블 $y_k \in \{0, 1\}$로 구성됩니다. 이 선호도는 누적 (관측되지 않은) 보상 차이에 적용된 Bradley–Terry–Luce(BTL) 링크 함수를 통해 모델링됩니다:
$$y_k \sim \text{Ber}\left(\sigma\left(\sum_{h=1}^H r_h(z^k_h) - \sum_{h=1}^H r_h(z'^k_h)\right)\right)$$
여기서 $\sigma$는 시그모이드 함수입니다. 목표는 최적 가치와 배포된 정책들의 평균 가치 간의 차이로 정의된 누적 후회 (regret) 를 최소화하면서 가치 함수 $V^\pi_1$을 최대화하는 정책을 학습하는 것입니다.

이 설정은 알려진 커널 $k$에 의해 유도된 재생 커널 힐베르트 공간 (RKHS) $\mathcal{H}_k$의 요소인 보상 함수 $r_h$와 전이 연산자 $P_h$를 갖는 커널 MDP 구조를 가정합니다. 구체적으로, 저자들은 비선형 구조를 포착하고 Sobolev 공간과 노름 동치 (norm-equivalent) 를 이루어 선형 MDP 를 넘어선 일반화를 제공하는 Matérn 커널 계열에 초점을 맞춥니다.

방법론: PROSTO 알고리즘
저자들은 PROSTO(Preference based Regularized Optimization via Sampled Trajectory induced Optimism, 샘플링된 궤적에 의한 낙관주의를 통한 선호 기반 정규화 최적화) 알고리즘을 제안합니다. 이 알고리즘은 에피소드 단위로 작동하며, 선호 피드백과 커널 함수 근사를 위해 적응된 가치 반복 (value iteration) 접근법을 활용합니다.

1. 정규화 커널 로지스틱 회귀 (KLRR) 를 통한 보상 추정:
   피드백이 궤적 수준이고 이진적이므로, 보상 벡터 $\theta$는 노름 가중 페널티를 포함한 최대우도추정 (MLE) 을 통해 추정됩니다. 추정기 $\hat{\theta}_k$는 관측된 선호도의 음의 로그우도에서 정규화 항 $\tau \|\theta\|^2_{\mathcal{H}_k}$를 최소화합니다. 이 회귀의 공변량은 궤적 차이 특징 $\phi_i = \sum_{h=1}^H \phi(z^i_h) - \phi(z'^i_h)$입니다.

2. 랜덤화 GP 교란을 통한 탐색:
   사전에 전이 역학을 알지 못해 (이는 결정론적 타원 보너스를 불가능하게 함) 궤적 수준에서 충분한 탐색을 보장하기 위해, PROSTO 는 랜덤화된 탐색을 사용합니다. 궤적 차이의 경험적 공분산에 의존하는 공분산 구조를 가진 가우시안 프로세스 (GP) 에서 교란 벡터 $\epsilon_k$를 샘플링합니다. 이 노이즈는 보상 추정치에 추가되어 낙관주의를 유도합니다.

3. 커널 릿지 회귀 (KRR) 를 통한 가치 함수 추정:
   가치 함수는 재귀적으로 추정됩니다. 다음 상태의 기대 가치는 전이 샘플에 대한 표준 커널 릿지 회귀를 사용하여 근사됩니다. 최종 Q-함수 추정치 $\hat{Q}^k_h$는 보상 추정치 (KLRR + GP 노이즈) 와 전이 추정치 (KRR) 를 결합하며, 유계성을 보장하기 위해 클리핑 (clipping) 을 적용합니다.

4. 정책 실행:
   학습자는 각자의 낙관적 Q-함수 추정치에 대해 탐욕적인 두 정책 $\pi$와 $\pi'$를 선택합니다. 이러한 정책들은 다음 에피소드의 궤적과 선호 피드백을 생성하기 위해 실행됩니다.

주요 기술적 기여 및 과제
본 논문은 커널 MDP 와 궤적 수준 선호 피드백을 결합하는 데 특화된 세 가지 주요 기술적 과제를 식별하고 새로운 해결책을 제시합니다:

• 로그-커버링 수 (Log-Covering Numbers) 제어: 커널 MDP 에서 가치 함수 클래스의 로그-커버링 수는 커버링 메쉬 $\epsilon$의 역수에 대해 다항식적으로 스케일링되며, 추정기의 RKHS 노름에 의존합니다. 에피소드 수에 대해 로그적인 커버링 수를 갖는 선형 MDP 와 달리, 커널 설정에서는 추정기 노름이 너무 커지면 후회 상한이 무의미 (vacuous) 해질 수 있습니다.

  • 해결책: 저자들은 KLRR 에서 정규화 매개변수 $\tau$를 신중하게 조정하여 보상 추정기의 RKHS 노름을 명시적으로 제어합니다. 이로써 유도된 함수 클래스의 커버링 수를 작게 유지하여 의미 있는 신뢰 구간을 가능하게 합니다.

• 비매끄러운 노이즈를 통한 궤적 수준 탐색: 표준 탐색 보너스 (타원 보너스) 는 결정 시점에 사용할 수 없는 전체 궤적에 대한 지식을 요구합니다. GP 샘플링을 통한 랜덤화된 탐색이 사용되지만, Matérn 커널에서 생성된 GP 샘플 경로는 일반적으로 해당 RKHS 에 속하지 않습니다 (덜 매끄러움). 이로 인해 표준 커버링 상한이 적용 불가능해집니다.

  • 해결책: 저자들은 사후 GP 샘플 경로에 대한 새로운 고확률 가우시안 커버링 상한을 유도합니다. van der Vaart 와 van Zanten [2008] 의 결과를 활용하여, GP 경로가 RKHS 공 (ball) 밖에는 있지만, 높은 확률로 적절히 확장된 RKHS 공의 $\epsilon$-근방 ($\ell_\infty$ 노름 기준) 에 있음을 보입니다. 이를 통해 후회 분석에 필요한 커버링 상한을 유도할 수 있습니다.

• 정규화 및 커버링 매개변수 균형: 정규화 매개변수 (보상에 대한 $\tau$, 전이에 대한 $\lambda$) 와 커버링 메쉬 $\epsilon$을 조정하는 것은 간단하지 않습니다. 작은 $\epsilon$은 오지정 (misspecification) 오차를 줄이지만 커버링 수를 팽창시키고, 큰 $\epsilon$은 그 반대의 효과를 냅니다.

  • 해결책: 저자들은 에피소드 수 $K$와 커널 매끄러움 매개변수 $\beta_p$의 함수로서 $\tau$, $\lambda$, $\epsilon$을 공동으로 최적화합니다. 이러한 균형 조정은 함수 클래스의 복잡성을 제어하면서도 선형이 아닌 후회를 위해 신뢰 구간 폭이 충분히 좁게 유지되도록 보장합니다.

결과 및 후회 상한
본 논문은 PROSTO 가 Matérn 계열의 모든 커널에 대해 선형이 아닌 누적 후회 상한을 달성함을 증명합니다. 구체적으로, 후회 $R(K)$는 다음과 같이 스케일링됩니다:
$$R(K) \leq \tilde{O}\left( \kappa_Z \max\left( H^{2.5} K^{1 - \frac{(\beta_p-1)^2}{2\beta_p(\beta_p+1)}}, H^3 K^{1 - \frac{\beta_p-1}{2(\beta_p+1)}} \right) \right)$$
여기서 $\beta_p > 1$은 커널의 고유값 감쇠 매개변수, $H$는 시간 범위 (horizon), $\kappa_Z$는 최대 역링크 기울기입니다. $K$의 지수는 1 보다 엄격하게 작아, $K \to \infty$일 때 최적 정책으로 수렴함을 의미합니다.

또한, 이 알고리즘은 계산적으로 효율적이며, 에피소드 수 $K$에 대해 다항식 시간으로 실행됩니다. 이는 선형이 아닌 후회를 달성하지만 일반적인 커널 설정에서 다항식 시간으로 계산적으로 처리 가능한 것으로 알려진 도메인 분할이나 최적화 오라클에 의존하는 이전의 커널 MDP 연구 (예: Maran et al. [2024b]) 와 구별되는 점입니다.

의의 및 주장
저자들은 본 연구가 전체 Matérn 커널 계열에 대해 증명 가능한 선형이 아닌 후회를 달성하면서 계산적으로 효율적인 첫 번째 선호 기반 RL 알고리즘을 제공한다고 주장합니다.

• 이론적 신규성: 이 연구는 일반적으로 표본 또는 선형 설정을 다루는 선호 기반 RL 과 비선형 설정을 다루는 커널 기반 함수 근사 사이의 간극을 메웁니다. 가치 반복의 맥락에서 GP 탐색 노이즈의 매끄러움 부족을 처리하는 새로운 기법을 도입합니다.
• 계산적 효율성: 비선형 후회 알고리즘이 종종 다루기 어려운 최적화를 필요로 하는 이전의 매끄러운 MDP 연구와 달리, PROSTO 는 다항식 시간 구현을 제공합니다.
• 한계: 저자들은 후회 상한이 차수 최적 (order-optimal) 일 수 있음을 인정합니다. 현재 일부 커널 설정에서 차수 최적 상한을 제공하는 도메인 분할 접근법은 전이의 확률성으로 인해 국소화된 벨만 연산자 추정이 불가능하여 궤적 수준 피드백과 양립할 수 없다고 지적합니다.

본 논문은 유도된 후회 상한이 선형이 아니지만, 차수 최적 상한을 달성하는 것은 현재 도메인 분할이나 균일 커버링 방법을 넘어선 근본적으로 다른 기법이 필요할 것으로 보이는 열린 질문으로 남는다고 결론지었습니다.