히스토리 의존적 로깅 하에서 오프-폴리시 평가의 지수적 어려움
요약
본 논문은 로깅된 데이터셋이 모든 숨겨진 상태를 자주 방문하더라도, 목표 정책의 가치에 대한 정보가 기하급수적으로 부족할 수 있음을 증명합니다. 특히 히스토리에 의존하는 로거 환경에서, 특정 결정론적 목표 정책을 평가하기 위해서는 에피소드 수가 $H$에 대해 $ ext{O}((3/2)^H)$로 증가해야 함을 보여줍니다.
핵심 포인트
- 히스토리 의존적 로깅은 정보 부족 문제를 야기할 수 있습니다.
- 목표 정책 평가를 위해 필요한 에피소드 수가 기하급수적으로 증가합니다.
- 리셋 메커니즘이 목표 가치를 결정하는 전이를 지워버리는 것이 핵심 원인입니다.
로깅된 데이터셋이 모든 숨겨진 상태를 자주 방문하더라도, 목표 정책의 가치에 대해 기하급수적으로 정보량이 부족할 수 있을까요? 우리는 로거가 히스토리에 의존하는 경우 그렇게 될 수 있음을 보여줍니다. 모든 지평 $H ge 3$에 대해, 우리는 각 단계당 최대 두 개의 잠재 상태와 세 가지 행동을 가진 두 개의 POMDP를 구성하고, 세 개의 메모리 상태를 가진 공통 로거를 사용합니다. 행동 커버리지(Action coverage), 믿음 커버리지(belief coverage), 그리고 두 가지 동작-주변 결과 공개 조건(behavior-marginal outcome-revealing conditions) 모두 $H$에 독립적인 상수 값을 가집니다. 그럼에도 불구하고, 두 후보 모델이 알려져 있는 경우에도, 정확도 $1/8$로 알려진 결정론적 목표 정책을 평가하려면 신뢰도 $1-\delta$에서 $\Theta((3/2)^H \log(1/\delta))$개의 로깅된 에피소드가 필요합니다 (단, $0 < \delta\le 1/4$). 그 메커니즘은 간단합니다: 리셋이 목표 가치를 결정하는 알려지지 않은 전이를 지워버립니다. 우리는 결과적인 통계적 실험을 정확하게 특성화하고 일치하는 최적 추정기를 얻습니다. 방향성 두 차선 그리드월드가 이 구성을 실현하며, 궤적 시뮬레이션은 그 유한 표본 예측과 일치합니다. 이 결과는 Zhang와 Jiang가 (2025, arXiv:2503.01134) 제시한 히스토리 의존적 로깅, 모델 기반 사례에 대해, 그들의 동작-주변 정의의 공개성 하에서 계산 불가능성을 확립합니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.LG (Machine Learning)의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기