Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems

기술 요약: 장기 의사결정 문제에서의 쌍체 선호도를 이용한 강화 학습

문제 정의
전통적인 강화 학습(RL)은 목표를 마르코프 결정 과정(MDP) 내에서 스칼라 보상 함수의 기대값을 최대화하는 것으로 정식화합니다. 그러나 대규모 언어 모델(LLM)의 미세 조정과 같이, 스칼라 보상을 정의하는 것보다 쌍체 선호도(예: "궤적 A가 궤적 B보다 더 좋다")를 지정하는 것이 더 자연스럽고 실행 가능한 경우가 많습니다. 쌍체 선호도를 이용한 기존의 강화 학습 방식들은 보상 함수를 추론하거나 선호도를 직접 최적화하지만, 다음과 같은 두 가지 결정적인 한계를 가집니다:

1. 이들은 유한하고 고정된 시간 지평(time horizon)에 의존하며, 이는 에이전트가 고정된 단계에서 종료되지 않는 장기 의사결정 문제에서는 비실용적입니다.
2. 이들은 정적 마르코프 정책(stationary Markov policies)이 이력 의존적 정책(history-dependent policies)에 대해 최적이라는 이론적 보장이 부족하며, 이는 표준 MDP 이론의 핵심 요소입니다.

또한, 표준적인 접근 방식은 비이행적 선호도(non-transitive preferences, 예: 콘도르세의 역설)를 포착하지 못하는 경우가 많습니다. 여기서 비이행성이란 집단의 집합적 선호나 다중 특징 평가가 이행적인 순서를 형성하지 않는 것을 의미합니다.

방법론: 마르코프 결정 콘테스트 (MDC)
저자들은 이러한 격차를 해소하기 위해 **마르코프 결정 콘테스트(Markov Decision Contest, MDC)**라는 새로운 문제 모델을 제안합니다. MDC는 유한한 환경 $(S, A, P, \mu)$와 마르코프 선호도 마진 $M: (S \times A) \times (S \times A) \to \mathbb{R}$로 정의됩니다. 목표는 임의의 다른 정책 $\pi'$에 대해 평균 선호도 마진을 최대화하는 정책 $\pi$를 찾는 것이며, 이는 다음과 같은 제로섬 게임으로 정식화됩니다:
$$\max_{\pi} \min_{\pi'} \sum_{s,a} \sum_{s',a'} x_\pi(s,a) x_{\pi'}(s',a') M((s,a), (s',a'))$$
여기서 $x_\pi$는 극한 평균 상태-행동 빈도(limiting average state-action frequency, 즉 점유 측도)를 나타냅니다.

무한 지평 설정에서 이론적 다루기 쉬움을 보장하기 위해, 저자들은 전이 확률 함수가 **단일 체인(unichain)**이며 **비주기적(aperiodic)**이라고 가정합니다. 이러한 조건 하에서, 이력 의존적 정책의 점유 측도 집합은 정적 결정론적 정책의 점유 측도의 볼록 껍질(convex hull)과 동일함을 입증합니다.

핵심 기여

1. 정적 정책의 최적성: 본 논문은 유한 단일 체인 MDC 내에서 **정적 확률적 정책(stationary randomized policy)**이 모든 이력 의존적 정책 중에서 최적임을 증명합니다. 이는 선호도 기반 강화 학습의 이론과 실제 사이의 간극을 메우며, 탐색 공간을 마르코프 정책으로 제한하는 것을 정당화합니다.
2. 계산 복잡도: 저자들은 MDC를 정확하게 푸는 것이 P(다항 시간) 내에 있음을 보여줍니다. 구체적으로, $|S||A| + |S| + 1$개의 변수와 $2|S||A| + |S| + 1$개의 제약을 가진 선형 계획법을 구성합니다. 이러한 복잡도는 MDC가 비이행적 선호도를 지원하는 엄격한 일반화임에도 불구하고, 표준 평균 보상 MDP와 유사한 수준입니다.
3. 헤지드 정책 반복 (Hedged Policy Iteration, HPI): 근사 반복 알고리즘인 **헤지드 정책 반복(HPI)**이 소개됩니다. 이는 "한계 가치"(누적 선호도 마진)를 기반으로 결정 규칙을 업데이트하기 위해 Hedge 알고리즘을 활용합니다.
   • 수렴성: HPI는 반복 횟수 $K$에 대해 $O(1/\sqrt{K})$의 부하적(sublinear) 속도로 최적 정책으로 수렴합니다.
   • 확장성: 저자들은 HPI의 정책 경사(policy-gradient) 형태와 버퍼 및 가치 함수 근사를 활용하는 딥러ニング 구현(알고리즘 3)을 도출하여, 고차원 환경에 적합하도록 만들었습니다.

실험 결과
저자들은 긴 시간 지평(2048 단계)을 가진 13개의 고차원 작업(Mujoco-v5 수트 사용)에 대해 HPI 및 그 클리핑 변형인 HPI-Clip을 자기 놀이 선호도 최적화(Self-Play Preference Optimization, SPPO) (Swamy et al., 2024)와 비교 평가했습니다.

• 설정: 작업에는 표준 연속 제어 문제(보상 차이로부터 선호도가 도출됨)와 명시적인 비이행적 선호도 마진(예: 3개 중 상위 2개 선택 규칙)을 특징으로 하는 "Mujoco-NT" 작업이 포함되었습니다.
• 성능: 13개 작업 중 12개에서 HPI와 HPI-Clip은 SPPO에 비해 현저히 높은 학습 효율성(에피소드 리턴의 곡선 아래 면적 또는 역 최적성 갭으로 측정됨)을 보여주었습니다.
• 절제 실험(Ablation): 선호도 모델이 오프라인 데이터로부터 학습되었을 때도 결과는 유효했습니다.

의의 및 주장
본 논문은 장기 의사결정 문제에서 쌍체 선호도를 이용한 강화 학습이 기존 생각보다 더 다루기 쉽다는 점을 주장합니다. MDC 모델을 도입함으로써 저자들은 다음과 같은 프레임워크를 제공합니다:

• 정적 정책이 이론적으로 충분하며, 이를 통해 복잡한 이력 의집적 전략의 필요성을 제거합니다.
• 비이행적 선호도가 존재하더라도 문제는 여전히 계산 효율적(P 내에 존재)입니다.
• 실용적인 알고리즘(HPI)은 고차원, 장기 지평 문제로 확장 가능하며, 기존의 최첨단 방법들을 능가합니다.

저자들은 이러한 결과가 장기 과업을 수행하는 LLM과 같은 응용 분야에 유망하지만, 언제 선호도 마진 학습이 보상 기반 학습보다 우위에 있는지, 그리고 이러한 방법들이 실제로 언어 모델을 얼마나 효과적으로 정렬(align)하는지에 대한 추가 조사가 필요하다고 언급합니다. 본 연구의 목적은 쌍체 선호도 기반 강화 학습의 이론과 실제를 가깝게 만드는 데 있습니다.