강화학습을 위한 최적의 데이터 수집: 대편차(Large Deviations) 관점

데이터 수집 효율성은 상호작용 비용이 높고 속도가 느리며 종종 인간이 개입(human in the loop)해야 하는 비즈니스 및 의료 운영 분야에서 강화학습 (Reinforcement Learning, RL)을 배포할 때 직면하는 핵심 과제입니다. 본 논문은 무한 시계 (infinite-horizon) 강화학습에서의 데이터 수집을 위한 통합된 대편차 (large deviations) 프레임워크를 개발합니다. 우리는 정책 선택 오류 확률 (policy-selection error probability)의 지수적 감소율 (exponential decay rate)을 원칙적인 효율성 지표로 도입하며, 마르코프 체인 (Markov chains)에 대한 대편차 이론을 통해 이 비율의 변분 특성 (variational characterization)을 도출하여 중첩 최적화 문제 (nested optimization problem)를 생성합니다. 이러한 특성을 바탕으로, 우리는 중첩 문제의 최적해 관점에서 상호 보완적인 두 가지 최적성 (optimality) 개념을 공식화합니다. 결과적으로 도출된 프로그램은 암시적 (implicit)이며 일반적으로 다루기 어렵기 때문에(intractable), 우리는 명시적인 제약 조건이 있는 다루기 쉬운 볼록 완화 (convex relaxation)를 제안합니다. 그런 다음 완화된 문제를 해결하기 위해 게으른 일보 투영 하강법 (lazy one-step projected subgradient method)을 개발하고, 그 반복값 (iterates)을 사용하여 적응형 데이터 수집 정책을 구축합니다. 우리는 결과적으로 도출된 강화학습 알고리즘이 우리의 최적성 기준 하에서 상수 인자(constant factor) 범위 내에서 근사적으로 강건한 최적성 (near-robustly optimal)을 가짐을 증명합니다. 마지막으로, 확장성을 개선하기 위해 이 프레임워크를 선형 함수 근사 (linear function approximation)로 확장하며, 수치 실험을 통해 제안된 접근 방식의 효과를 입증합니다.