A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model

기술 요약: 약간의 자유가 큰 차이를 만든다: 생성 모델 하에서의 강화 학습을 위한 고전 및 양자 알고리즘

문제 정의

본 논문은 온라인 설정에서 마르코프 결정 과정(MDP)을 학습하는 문제, 특히 후회(regret, 에이전트가 얻은 누적 보상과 최적 정책의 보상 사이의 차이)를 최소화하는 문제에 초점을 맞춥니다. 저자들은 세 가지 뚜렷한 MDP 설정을 고려합니다:

1. 유한 지평(Finite-horizon) MDP: 상호작용이 고정된 단계 $H$ 동안 발생합니다.
2. 무한 지평 할인(Infinite-horizon discounted) MDP: 상호작용이 할인 계수 $\gamma \in [0, 1)$와 함께 무기한 지속됩니다.
3. 무한 지평 비할인(Infinite-horizon undiscounted) MDP: 평균 보상 기준을 사용하며, 특히 약한 통신(weakly communicating) MDP에 초점을 맞춥니다.

강화 학습(RL)의 핵심 과제는 탐색-활용(exploration-exploitation) 트레이드오프입니다. 고전적인 설정에서 에이전트는 환경과 상호작용하면서 전이 확률 $p(\cdot|s, a)$를 학습해야 합니다. 양자 설정에서는 근본적인 문제가 발생합니다. 표준 양자 오라클은 중첩(superposition)과 역연산(inverse operations)을 허용하는데, 이는 만약 에이전트가 학습 과정 내내 양자 방식으로 환경과 상호작용한다면 정의되지 않은 후회 척도로 이어질 수 있기 때문입니다. 또한, 시간 $T$에 대해 폴리로그(polylogarithmic) 후회를 달성하려고 시도했던 이전의 양자 RL 연구들은 양자 진폭 추정(quantum amplitude estimation)의 일관된 적용에 관한 결함이 있는 가정을 기반으로 하고 있습니다.

방법론

하이브리드 온-오프라인 RL 모델

양자 RL의 정의 문제를 해결하고 양자 가속을 활용하기 위해, 저자들은 하이브리드 온-오프라인 RL 모델을 제안합니다. 이 모델은 학습 과정을 두 개의 뚜렷한 단계로 분리합니다:

1. 온라인 단계 (탐색): 에이전트는 고전적으로 환경과 상호작용합니다. 에이전트는 행동을 선택하고, 보상을 받고, 상태 전이를 관찰합니다. 결정적으로, 후회는 이 단계 동안 축적됩니다. 에이전트는 여기에서 양자 오라클에 접근할 수 없습니다.
2. 오프라인 단계 (생성 학습): 에이전트는 생성 모델을 통해 환경과 상호작용할 수 있는 "자유"를 부여받습니다.
   • 고전적 오프라인 단계에서, 에이전트는 $(s, a)$가 주어졌을 때 다음 상태 $s'$를 반환하는 샘플링 오라클 $C_p$에 접근합니다.
   • 양자 오프라인 단계에서, 에이전트는 다음 상태들의 중첩을 준비하는 양자 오라클 $Q_p$(및 그 역연산)에 접근합니다.
   • 제약 조건: 오프라인 단계의 오라클 호출 횟수는 이전 온라인 단계의 길이 $\tau$에 대한 함수인 $O(\tau^\beta)$로 제한됩니다 (여기서 $\beta \in [0, \infty)$는 "예산" 파라미터입니다). 이는 에이전트가 오라클을 과도하게 쿼리함으로써 후회가 거의 없는 최적에 가까운 정책을 얻는 것을 방지합니다.

알고리즘 접근 방식

제안된 알고리즘(Algorithm 1)은 에포크(epoch) 단위로 진행됩니다. 각 에포크 $\ell$에서:

1. 오프라인 계산: 이전 온라인 단계(길이 $\tau_{\ell-1}$)에서 수집된 데이터를 사용하여, 에이전트는 $\epsilon_\ell$-최적 정책을 계산합니다.
   • 고전적: 알려진 샘플 최적 알고리즘(예: Sidford et al.)을 사용하여 정책을 계산합니다.
   • 양자: 저자들은 생성 모델 하에서 최적 정책을 계산하기 위한 새로운 양자 알고리즘을 도입합니다. 이 알고리즘들은 가치 반복(value iteration)을 가속화하기 위해 양자 평균 추정(Kothari and O'Donnell)과 양자 최소/최대 찾기(Dürr and Høyer)를 활용합니다.
2. 온라인 실행: 계산된 정책 $\pi^{(\ell)}$은 더블링 트릭(doubling trick, 지평을 2배 또는 $2H$배로 증가시킴)에 따라 환경에서 실행됩니다.
3. 후회 분석: 총 후회는 각 온라인 단계에서 사용된 정책들의 부최적성(sub-optimality)을 합산하여 경계가 정해집니다.

주요 기술적 기여

1. 생성 모델을 위한 새로운 양자 알고리즘:

   • 유한 지평: 저자들은 고전적 쿼리 복잡도를 개선하는 양자 알고리즘을 설계합니다. 이들은 양자화된 가치 반복과 분산 감소 기법을 결합합니다. 쿼리 복잡도는 $\tilde{O}(\min\{H^{2.5}SA/\epsilon, H^3S\sqrt{A}/\epsilon\})$이며, 이는 $H$와 $A$에 대한 고전적 경계보다 개선된 의존성을 보입니다.
   • 무한 지평 할인: 유사한 개선이 이루어지며, 쿼리 복잡도는 $\tilde{O}(\min\{\Gamma^{1.5}SA/\epsilon, \Gamma^3S\sqrt{A}/\epsilon\})$입니다.
   • 무한 지평 비할인: 이는 새로운 기여입니다. 저자들은 최적 벨만 연산자가 $J$-단계 $\nu$-스팬 축약(span contraction)이라고 가정할 때, 약한 통신 MDP를 위한 양자 알고리즘을 제안합니다. 복잡도는 $\tilde{O}(\Lambda S \sqrt{A} / \epsilon)$입니다.

2. 이전 양자 RL 연구의 수정:
   본 논문은 폴리로그 후회를 주장했던 이전 연구들(예: Gangaly et al., Zhong et al.)을 비판합니다. 저자들은 이러한 연구들이 양자 진폭 추정이 저장된 상태들의 집합에 대해 수행될 수 있다고 잘못 가정했으나, 실제로는 오라클과 그 역연산의 순차적이고 일관된(coherent) 적용이 필요하다고 주장합니다. 제안된 하이브리드 모델은 이러한 일관된 연산을 수행할 수 있는 별도의 오프라인 단계를 강제함으로써 이를 바로잡습니다.

3. 하이브리드 모델 하에서의 후회 경계:
   저자들은 예산 파라미터 $\beta$의 함수로서 고전 및 양자 설정 모두에 대한 후회 경계를 도출합니다:

   • 유한 지평:
     • 고전적: $\beta \ge 2$일 때 $\tilde{O}(\sqrt{HSAT})$ (최신 기술 수준과 일치).
     • 양자: $\beta < 1$일 때 $\tilde{O}(\min\{H^{1.5}SA, H^2S\sqrt{A}\} T^{1-\beta})$, $\beta \ge 1$일 때 $T$에 대한 폴리로그.
   • 무한 지평 할인:
     • 양자: $\beta \ge 1$일 때 $\tilde{O}(\text{polylog}(T))$ 후회를 달성하여, 고전적 $\Omega(\sqrt{T})$ 장벽을 깹니다.
   • 무한 지평 비할인:
     • 양자: $\beta \ge 1$일 때 $\tilde{O}(\Lambda S \sqrt{A} \cdot \text{polylog}(T))$ 후회를 달성하며, 이는 이전 양자 연구의 $\tilde{O}(\Lambda S^5 A^4)$ 경계를 크게 개선한 것입니다.

결과 및 의의

본 논문은 오프라인 생성 단계에서 제공되는 "약간의 자유"가 학습 효율성을 크게 향상시킬 수 있다고 주장합니다.

• 양자 이점: 가장 중요한 결과는 양자 컴퓨터가 (특히 $\beta \in [1, 2)$인 경우) 시간 지평 $T$에 대해 폴리로그 후회를 달성할 수 있다는 것을 보여준 것입니다. 반면 고전적 알고리즘은 이러한 설정에서 근본적으로 $\Omega(\sqrt{T})$ 후위에 제한됩니다. 이는 $T$에 대한 의존성 측면에서 지수적인 개선을 의미합니다.
• 파라미터 의존성: 양자 알고리즘은 고전 알고리즘 및 이전의 양자 시도들과 비교했을 때 상태 공간 크기 $S$, 행동 공간 크기 $A$, 지평 $H$(또는 유효 지평 $\Gamma$)에 대한 의존성을 개선합니다.
• 모델 타당성: 본 논문은 하이브리드 온-오프라인 모델이 양자 RL을 위한 필수적이고 의미 있는 프레임워크임을 확립합니다. 이는 양자 상호작용에서 후제를 정의하는 모호함을 해결하고, 후제 없는 양자 탐색을 가정했던 기존 문헌의 이론적 결함을 바로잡습니다.

저자들은 예산 $\beta$가 매우 커질 때($\beta \ge 2$, 고전 알고리즘도 폴리로그 후회를 달성하는 지점) $T$에 대한 지수적 양자 이점이 사라진다는 점을 명시하면서도, 양자 컴퓨터가 실질적인 이점을 제공하는 임계 범위($\beta \in [1, 2)$)가 존재한다고 결론짓습니다. 이 범위를 제안된 모델 하에서 양자 가속이 가장 영향력 있는 주요 영역으로 식별합니다.