기술적 요약: 보상 무관 및 보상 자유 탐색을 위한 개선된 경계

문제 정의

본 논문은 데이터 수집 단계에서 에이전트가 외부 보상 신호를 관측하지 않는 episodic 유한 시간 범위 표형 마르코프 결정 과정 (MDP) 에서의 탐색 과제를 다룬다. 저자들은 두 가지 구체적인 프레임워크를 연구한다:

1. 보상 자유 탐색 (RFE): 에이전트는 보상 신호 없이 미지의 환경을 탐색한다. 목표는 탐색 단계가 끝난 후 공개되는 임의의 보상 함수에 대해 $\epsilon$-최적인 정책을 생성하는 것이다.
2. 보상 무관 탐색 (RAE): RFE 와 유사하지만, 보상 함수는 $|S|, |A|, H$의 다항식 크기를 가진 작고 미리 정의된 유한 클래스에서 추출된다. 목표는 이 클래스에서 추출된 특정 보상에 대해 $\epsilon$-최적인 정책을 찾는 것이다.

핵심적인 어려움은 보상 신호의 안내 없이 상태 - 행동 전이 역학을 정확하게 추정할 만큼 충분한 데이터를 수집하고, 결과적으로 생성된 모델이 하류 작업에 대한 준최적 정책의 계산을 지원하도록 보장하는 데 있다.

방법론

제안된 접근법은 기존 연구에서 발견된 여러 개의 독립적인 후회 없음 (no-regret) 서브루틴에 대한 의존성을 통합된 온라인 학습 절차로 대체한다. 알고리즘 (알고리즘 1) 은 세 단계로 운영된다:

1. 탐색 정책 생성

Jin 등 (2020b) 및 Li 등 (2024b) 이 수행한 것처럼 여러 개의 확률적 후회 없음 알고리즘을 실행하는 대신, 저자들은 정교하게 구성된 보조 보상 함수 시퀀스에 대해 온라인 미러 강하 (OMD) 알고리즘을 단일 실행으로 적용한다.

• 메커니즘: 알고리즘은 에이전트를 덜 방문된 상태 - 행동 쌍으로 유도하도록 설계된 보상 시퀀스 $\{\lambda_t\}$를 생성한다. $t$ 단계의 보상은 상태 - 행동 쌍의 방문 횟수에 반비례하며 (낮은 확률 방문을 처리하기 위해 상수 $c$를 더함).
• 최적화 관점: 이 과정은 유효한 점유 측정 (occupancy measures) 공간에서 볼록 최적화 문제를 근사적으로 해결하는 것으로 프레임된다. 구체적으로, 음의 로그 배리어 목적 함수 $f(\mu) = -\sum \log \mu_h(s,a)$를 최소화하는 것을 목표로 한다.
• 의의: Frank-Wolfe 스타일의 반복을 사용하는 대신 단일 온라인 MDP 알고리즘 (Rosenberg & Mansour, 2019 에서 적응됨) 을 사용함으로써, 이 방법은 저차수 샘플 복잡도 항을 크게 줄인다. 학습 전반에 걸쳐 샘플을 재사용하여 중요한 상태 - 행동 삼중항의 준균일 탐색을 보장하는 "정책 커버 (policy cover)"를 구축한다.

2. 역학 추정

1 단계에서 생성된 탐색 정책을 사용하여 에이전트는 $N$개의 궤적을 수집한다. 궤적 데이터에 내재된 시간적 상관관계를 처리하기 위해 저자들은 이중 하위 표본 추출 프레임워크 (Li 등, 2024a) 를 활용한다. 이 기술은 데이터 세트를 주 세트와 보조 세트로 분할하여 통계적 독립성을 유도하며, 엄격한 집중 보장을 갖춘 경험적 전이 커널 $\hat{P}$를 구축할 수 있게 한다.

3. 정책 추정

실제 보상 함수가 공개되면, 알고리즘은 **불확실성에 대한 비관주의 (pessimism in the face of uncertainty)**를 사용하여 $\epsilon$-최적 정책을 계산한다.

• 알고리즘은 $\hat{P}$와 공개된 보상을 사용하여 경험적 MDP 를 구축한다.
• Q-값 추정에 베르누이 스타일 집중 부등식에서 유도된 벌칙 항 $b_h(s,a)$를 적용한다. 이 벌칙은 경험적 분산과 방문 횟수에 비례하여 스케일링되며, 정책이 잘 커버되지 않은 상태 - 행동 쌍을 방문하는 것을 억제한다.
• 최종 정책 $\hat{\pi}$는 이 비관적 경험적 MDP 에 대한 최적 정책이다.

주요 기여 및 결과

1. 보상 무관 탐색 (RAE) 을 위한 개선된 샘플 복잡도

본 논문은 최하위 정책 식별 (BPI) 에 대한 하한과 일치하는 RAE 에 대한 최적의 고차수 샘플 복잡도를 달성하는 새로운 알고리즘을 제시한다.

• 결과: 샘플 복잡도는 $O\left(\frac{|S||A|H^3 \ell_0^3}{\epsilon^2} + \frac{|S|^2|A|H^4 \ell_0^3}{\epsilon}\right)$이다.
• 개선: 이전 연구 (Li 등, 2024b) 는 최적의 고차수 항 $O(|S||A|H^3/\epsilon^2)$을 달성했지만, 그들의 경계는 매우 작은 $\epsilon$에 대해서만 최적이 되도록 만든 고복잡도 저차수 항으로 고통받았다. 제안된 방법은 이 저차수 항을 크게 줄여 알고리즘이 더 넓은 범위의 정확도 매개변수에 적용 가능하도록 한다.

2. 보상 자유 탐색 (RFE) 을 위한 엄격한 하한

저자들은 시간 비동질 (time-inhomogeneous) MDP 에서 RFE 의 샘플 복잡도에 대한 엄격한 하한을 증명한다.

• 결과: 모든 RFE 알고리즘은 기대값으로 $\Omega\left(\frac{|S|^2|A|H^3}{\epsilon^2}\right)$개의 궤적이 필요하다.
• 의의: 이는 Li 등 (2024b) 의 시간 동질 사례보다 $H$배 더 큰 미니맥스 하한에 대한 추측을 해결한다. 이는 기존 상한 (예: M´enard 등, 2021) 이 로그 인자까지 최적임을 확립한다.

3. 이론적 프레임워크

본 논문은 점유 측정 (occupancy measures) 에 대한 로그 배리어 목적 함수의 최소화와 탐색 정책 생성을 연결함으로써 새로운 기술적 관점을 제공한다. 이는 온라인 미러 강하 접근 방식이 이전 Frank-Wolfe 기반 방법보다 이 해를 더 효율적으로 근사할 수 있음을 보여주며, 저차수 항에서 문제 차원에 대한 의존성을 줄인다.

의의 및 주장

본 논문은 다음과 같은 방식으로 보상 없이 탐색에 대한 이론적 이해를 진전시킨다고 주장한다:

1. 탐색과 활용의 분리: 유한 시간 범위 MDP 에서 탐색의 고유한 샘플 복잡도를 명확히 한다.
2. RAE 의 실용성: 이전 최적 경계에서 발견된 정확도 매개변수 $\epsilon$에 대한 제한적인 요구 사항을 완화함으로써, 제안된 방법은 중간 정확도 영역에서도 보상 무관 탐색을 실용적으로 만든다.
3. 특성의 완전성: RAE 에 대한 새로운 상한과 RFE 에 대한 엄격한 하한의 결합은 (로그 인자까지) 이러한 문제에 대한 샘플 복잡도의 완전한 미니맥스 특성을 제공한다.

저자들은 명시적으로 유한 시간 범위 표형 MDP 의 이론적 분석에 초점을 맞추고 있으며, 비표형 MDP 와 경험적 결과는 향후 연구 과제로 남겨두었다고 명시한다. 그들은 로봇 공학이나 의학과 같은 특정 현실 세계 도메인에 대한 즉각적인 적용을 주장하기보다는, 그러한 응용을 가능하게 하는 기초 이론적 개선을 강조한다.