📊 statistics

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

이 논문은 낙관주의나 사후 샘플링과 같은 전통적인 패러다임을 우회하여 직접적인 최적 정책 계산을 활용함으로써, 양자 방법의 경우 시간 단계에 대한 다항 로그 의존성을 포함하여 개선된 후회 상한을 달성하는 생성 모델 하의 유한 및 무한 지평 마르코프 결정 과정에 대한 새로운 고전 및 양자 온라인 강화 학습 알고리즘을 소개한다.

원저자: Andris Ambainis, Joao F. Doriguello, Debbie Lim

게시일 2026-07-20

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Andris Ambainis, Joao F. Doriguello, Debbie Lim

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 규칙이 숨겨진 비디오 게임을 플레이하고 있다고 상상해 보세요. 어떤 버튼이 보물로 이끌고 어떤 버튼이 당신을 구덩이로 떨어뜨릴지 알 수 없습니다. 승리하기 위해서 당신은 계속 버튼을 누르고, 일어나는 일을 관찰하며, 서서히 최선의 전략을 파악해 나가야 합니다. 이것이 강화 학습(Reinforcement Learning, RL)의 핵심입니다. 강화 학습은 컴퓨터 '에이전트'가 보상을 극대화하기 위해 환경과 상호작용하며 배우는 인공지능의 한 분야입니다. 이 과정의 수학적 프레임워크를 마르코프 결정 과정(Markov Decision Process, MDP)이라고 합니다. MDP를 모든 가능한 게임 상태(예: "절벽 위에 서 있음" 또는 "열쇠를 쥐고 있음")와 어떤 행동을 취했을 때 다음에 일어날 확률을 나타내는 지도로 생각하세요. 목표는 에이전트에게 모든 상황에서 가장 높은 점수를 얻기 위해 정확히 무엇을 해야 하는지 알려주는 완벽한 '정책(policy)' 즉, 규칙책을 찾는 것입니다.

오랫동안 과학자들은 이러한 학습 에이전트를 더 똑똑하고 빠르게 만들기 위해 노력해 왔습니다. 주요 장애물은 '탐험(exploration) 대 이용(exploitation)'의 딜레마였습니다. 에이전트가 세상에 대해 더 많이 배우기 위해 새롭고 위험한 움직임을 시도해야 할까요(탐험), 아니면 이미 좋다고 알고 있는 움직임을 고수해야 할까요(이용)? 대부분의 전통적인 방법은 에이전트가 미지의 경로가 아주 멋질 수도 있다고 가정하여 새로운 시도를 하도록 유도하는 '불확실성에 대한 낙관주의(optimism in the face of uncertainty)'라는 전략에 의존합니다. 하지만 이 논문은 다음과 같은 반전을 제시합니다. 만약 에이전트가 실제로 게임을 플레이하지 않고도 움직임을 테스트할 수 있는 '치트키'나 '시뮬레이터'를 가끔 사용할 수 있다면 어떨까요? 저자들은 이 특별한 접근 권한을 제공하는 것이 양자 컴퓨팅(quantum computing)의 힘과 결합되었을 때, 에이전트가 얼마나 빠르게 학습할 수 있는지에 대한 혁명을 일으킬 수 있음을 탐구합니다.

논문의 핵심 아이디어: 하이브리드 훈련 캠프

저자인 안드리스 암바인스(Andris Ambainis), 조아오 F. 도리고엘로(Joao F. Doriguello), 데비 림(Debbie Lim)은 이러한 AI 에이전트를 훈련하는 새로운 방법을 제안합니다. 그들은 하이브리드 온-오프라인 모델을 제안합니다. 에이전트를 학생이라고 상상해 보세요. '온라인' 단계에서 학생은 실제 교실에서 시험을 치르고 있습니다. 틀린 답을 낼 때마다 점수가 깎입니다(이것이 '후회(regret)' 또는 완벽하지 못함에 대한 벌점입니다). 이는 비용이 많이 드는 실제 세계의 부분입니다. 하지만 그 후 학생은 휴식을 취합니다. 그들은 '시뮬레이션 실험실'(오프라인 단계)로 들어갑니다. 이 실험실에서 그들은 마법 같은 '생성 모델(generative model)'을 가지고 있습니다. 이 시뮬레이터는 어떤 움직임을 원하든 그 결과를 즉각적으로, 그리고 아무런 벌칙 없이 반복해서 보여줄 수 있습니다.

여기서 핵심적인 혁신은 에이전트가 이 두 모드 사이를 전환할 수 있다는 점입니다. 에이전트는 실제 게임을 플레이하며 약간의 실수를 쌓은 다음, 시뮬레이터로 가서 숫자를 계산하고 완벽한 전략을 파악합니다. 더 나은 계획을 세우면 다시 실제 게임으로 돌아갑니다. 논문은 시뮬레이터를 사용하는 이 '자유의 한 조각'이 모든 것을 바꾼다고 주장합니다.

기존의 규칙을 버리다

이 논문에서 가장 흥eli로운 부분 중 하나는 우리가 하지 말아야 할 일을 알려준다는 점입니다. 수십 년 동안 RL 에이전트를 위한 표준 권고는 '불확실성에 대한 낙관주의'를 사용하는 것이었습니다. 이것은 학생에게 "그 문이 금괴로 이어지는지 함정으로 이어지는지 모르니, 일단 금괴라고 가정하고 확인하러 가라"고 말하는 것과 같습니다. 저자들은 만약 시뮬레이터(심지어 가끔이라도)에 접근할 수 있다면, 추측할 필요가 없다는 것을 보여줍니다. 그냥 시뮬레이터로 들어가서 숫자를 돌려보고, 실제 최선의 움직임을 직접 계산할 수 있기 때문입니다.

그들은 이 특정 설정에서 '낙관주의'나 '사후 샘플링(posterior sampling, 또 다른 복잡한 추측 방법)'의 필요성에 대해 명시적으로 반대합니다. 무엇이 사실일지 추측하는 대신, 에이전트는 시뮬레이터 데이터를 사용하여 최적의 정책을 직접 계산할 수 있습니다. 이러한 전환을 통해 전통적인 학습의 복잡하고 불확실한 부분을 피하고 곧바로 해결책으로 뛰어들 수 있습니다.

양자의 초능력

이제 '양자' 부분을 이야기해 봅시다. 저자들은 단순히 시뮬레이터를 사용하는 데 그치지 않고, "만약 시뮬레이터가 양자 컴퓨터에서 실행된다면 어떨까?"라고 질문했습니다. 양자 컴퓨터는 방대한 양의 가능성을 동시에 처리할 수 있는 것으로 유명합니다. 시뮬레이터 단계 내에서 양자 알고리즘을 사용함으로써, 에이전트는 고전적인 컴퓨터가 할 수 있는 것보다 훨씬 빠르게 행동의 결과를 추정할 수 있습니다.

논문은 세 가지 다른 유형의 게임 시나리오에 대한 새로운 알고리즘을 제시합니다:

유한 호라이즌(Finite-Horizon): 정해진 단계 후에 끝나는 게임 (비디오 게임의 한 레벨처럼).
무한 호라이즌 할인형(Infinite-Horizon Discounted): 계속 이어지지만, 미래의 보상이 현재의 보상보다 가치가 약간 낮은 게임 (돈에 이자가 붙는 것처럼).
무한 호라이즌 비할인형(Infinite-Horizon Undiscounted): 모든 보상에 동일한 가중치를 두고 계속 이어지는 게임 (꾸준한 직업처럼).

이 모든 시나리오에 대해, 저자들은 자신들의 양자 알고리즘이 시간 단계( $T$ )에 대해서만 아주 작은 값(예: $\log T$ )으로 의존하는 '후회 경계(regret bound)'를 달성할 수 있음을 발견했습니다. 하지만, 성능이 여전히 게임 세계의 크기에 크게 의존한다는 점을 유념하는 것이 매우 중요합니다. 알고리즘의 효율성은 가능한 상태의 수( $S$ ), 가능한 행동의 수( $A$ ), 그리고 게임의 길이 또는 유효 호라이즌( $H$ 또는 $\Gamma$ )에 의해 크게 좌우됩니다. 양자 에이전트의 오차는 게임이 길어짐에 따라 매우 느리게 증가하지만(시간에 대해 다항 로그 수준), 계산의 복잡성은 여전히 상태 및 행동 공간의 크기에 따라 달라집니다.

쉬운 말로 설명하자면, 게임이 길어질수록 양자 에이전트의 성능은 시간 대비 거의 저하되지 않지만, 게임을 배우기 위한 초기 '비용'은 여전히 게임 지도의 복잡성에 의해 결정됩니다. 반면, 고전적인 알고리즘은 보통 시간의 제곱근( $\sqrt{T}$ )에 따라 오차가 증가합니다. 논문은 양자 시뮬레이터를 사용함으로써, 에이전트가 시뮬레이터에서 사용할 수 있는 일정량의 시간(1과 2 사이의 '예산' 매개변수 $\beta$ 에 의해 제어됨)이 허용될 때, 에이전트가 지수적으로 더 빠르게 학습하여 고전적인 장벽을 깰 수 있음을 보여줍니다. 만약 시뮬레이터에서의 연습 시간이 너무 짧다면, 그 이점은 줄어듭니다.

얼마나 확신하는가?

저자들은 자신들의 수학적 증명에 매우 자신감이 있습니다. 그들은 단순히 컴퓨터 시뮬레이션을 돌려보고 "작동하는 것 같다"고 말한 것이 아닙니다. 그들은 자신들의 알고리즘이 특정 확률(보통 실패 확률 $\delta$ 에 대해 $1 - \delta$ )로 최적의 정책을 생성할 것임을 보여주는 엄격한 수학적 증명을 제공했습니다. 그들은 자신들의 양자 알고리즘이 최상의 알려진 고전적 방법들과 비교했을 때 더 적은 '쿼리(query, 시뮬레이터 확인)'를 사용하여 좋은 해결책에 도달함을 증명했습니다.

그러나 그들은 또한 조건들을 주의 깊게 명시했습니다. 그들의 '초고속' 결과는 에이전트가 실제 세계와 시뮬레이터 중 어디에 시간을 더 쓸지를 결정하는 '예산' 매개변수( $\beta$ )에 크게 의존합니다. 만약 에이전트가 시뮬레이터에서 충분한 시간을 보낼 수 있다면(특히 $\beta$ 가 1과 2 사이일 때), 양자 이점은 엄청납니다. 만약 시뮬레이터 시간이 너무 짧다면, 그 이점은 줄어듭니다. 또한 그들은 자신들의 방법이 에이전트가 '생성 모델'(시뮬레이터)에 접근할 수 있다는 전제에 기반하고 있으며, 이는 모든 실제 상황에서 항상 사용 가능한 것은 아닌 특정 유형의 설정임을 지적합니다.

결론

이 논문은 만약 우리가 AI 에이전트에게 자유롭게 움직임을 테스트할 수 있는 '샌드박스'(시뮬레이터)를 제공하고, 그 샌드박스를 양자 컴퓨터에서 실행할 수 있다면, 복잡한 환경을 믿을 수 없을 정도로 빠르게 마스터하도록 가르칠 수 있다는 것을 시사합니다. 그들은 추측하거나 지나치게 낙관적일 필요가 없습니다. 그저 최선의 경로를 계산하면 됩니다. 비록 이것이 특정 설정(하이브리드 모델 및 양자 접근 권한)을 요구하며, 시뮬레이터에서의 '연습 시간'이 많을 때 효과가 가장 극적이라는 점을 전제로 하지만, 그 결과는 고전적인 컴퓨터는 도저히 따라잡을 수 없는 효율성으로 학습하는 AI를 향한 명확한 길을 보여줍니다. 이는 때때로, 결과에 대한 책임 없이 자유롭게 연습할 수 있는 작은 여유가 아주 큰 차이를 만든다는 점을 상기시켜 줍니다.

기술 요약: 약간의 자유가 큰 차이를 만든다

문제 정의

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

유한 지평 MDP (Finite-horizon MDPs): 에이전트가 고정된 $H$ 단계 동안 상호작용합니다.
무한 지평 할인 MDP (Infinite-horizon discounted MDPs): 에이전트가 $\gamma \in [0, 1)$ 의 할인 계수에 따라 무기한 상호작용합니다.
무한 지평 비할인 MDP (Infinite-horizon undiscounted MDPs): 에이전트가 평균 보상 기준에 따라 무기한 상호작용하며, 특히 약한 통신(weakly communicating) MDP에 집중합니다.

강화 학습(RL)의 핵심 과제는 탐색-활용(exploration-exploitation) 트레이드오프입니다. 전통적인 온라인 RL 알고리즘은 환경의 전이 확률에 대한 불확실성을 관리하기 위해 "불확실성에 직면한 낙관주의(optimism in the face of uncertainty)" 또는 "사후 샘플링(posterior sampling)"과 같은 원리에 의존하는 경우가 많습니다. 본 논문은 "오프라인" 생성적 접근을 통해 환경에 대한 생성적 액세스를 허용하는 하이브리드 상호작용 모델을 도입함으로써 이러한 패러다임을 우회할 수 있는지 조사합니다.

방법론

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

핵심적인 방법론적 기여는 하이브리드 온라인-오프라인 RL 모델의 제안입니다. 이 모델은 학습 과정을 두 가지 교대 단계로 분리합니다:

온라인 단계 (탐색): 에이전트가 고전적으로 환경과 상호작용합니다. 에이전트는 행동을 선택하고, 보상을 받고, 상태 전이를 관찰합니다. 결정적으로, 이 단계 동안에는 후회가 축적됩니다.
오프라인 단계 (생성적 학습): 에이전트는 환경으로부터 전이를 생성적인 방식으로 샘플링할 수 있는 "시뮬레이터" 또는 오라클( $C_p$ 는 고전적, $Q_p$ 는 양자적)에 접근할 수 있습니다. 이 단계에서 에이전트는 양자 연산 및 오라클의 역행렬 접근을 포함한 임의의 계산을 수행할 수 있으며, 이때 후하는 축적되지 않습니다.

이 모델에서의 "자유"는 예산 파라미터 $\beta$ 에 의해 규제됩니다. 만약 온라인 단계가 $\tau$ 단계 동안 지속된다면, 에이전트는 이후의 오프라인 단계에서 오라클에 대해 $O(\tau^\beta)$ 번의 쿼리를 허용받습니다. 이 제약은 에이전트가 온라인으로 상호작용하기 전에 환경을 충분히 시뮬레이션하여 최적 정책을 완벽하게 학습함으로써 문제를 사소하게 해결하는 것을 방지합니다.

알고리즘 접근 방식

제안된 알고리즘은 다음과 같은 단계적 구조(알고리즘 1)를 따릅니다:

에이전트는 길이 $\tau_\ell$ 의 온라인 단계를 실행합니다.
이어지는 오프라인 단계에서, 에이전트는 섹션 2에서 유도된 서브루틴을 사용하여 $\epsilon_\ell$ -최적 정책을 계산하기 위해 오라클을 사용합니다.
온라인 단계의 길이는 탐색 비용과 계산된 정책의 정밀도 사이의 균형을 맞추기 위해 증가합니다(doubling trick).

저자들은 표준적인 "낙관주의" 휴리스틱을 피합니다. 대신, 오프라인 단계 동안 다음을 사용하여 근사 최적 정책을 직접 계산합니다:

고전적 서브루틴: 분산 감소 가치 반복(Sidford 등 [55] 기반) 및 표준 역방향 귀납법(backward induction).
양자 서브루틴: 기대값을 추정하기 위한 양자 평균 추정(Quantum Mean Estimation) (Kothari와 O'Donnell [57]) 및 최적의 행동을 선택하기 위한 양자 최소값 찾기(Quantum Minimum Finding) (Dürr와 Høyer [58])를 사용하는 양자화된 가치 반복.

이전의 양자 RL 연구들(예: [23, 24, 98])은 근본적인 결함이 있다고 비판적으로 분석합니다. 해당 연구들은 양자 진폭 추정(amplitude estimation)이 저장된 양자 상태들의 집합 $\{Q_p|s\rangle, Q_p^\dagger|s\rangle\}$ 에 대해 수행될 수 있다고 가정했습니다. 저자들은 진폭 추정이 정적인 상태의 집합에 대한 접근이 아니라, 단일 양자 상태에 대한 오라클의 순차적이고 결맞는(coherent) 적용을 필요로 한다는 점을 명확히 합니다. 제안된 하이브리드 모델은 탐색 단계의 집합을 "온라인" 단계로, 결맞는 양자 계산을 "오프라인" 단계로 취급함으로써 이를 해결합니다.

주요 기여 및 결과

1. 정책 계산을 위한 새로운 양자 알고리즘

저자들은 온라인 학습 과정의 서브루틴 역할을 하는, 생성 모델 하에서 $\epsilon$ -최적 정책을 계산하기 위한 새로운 양자 알고리즘을 제시합니다:

유한 지평 (Finite-Horizon): 쿼리 복잡도가 $\tilde{O}(\min\{H^{2.5}SA/\epsilon, H^3S\sqrt{A}/\epsilon\})$ 인 양자 알고리즘입니다. 이는 고전적 경계보다 개선되었으며 동시 연구 [60]와 일치합니다.
무한 지평 할인 (Infinite-Horizon Discounted): 쿼리 복잡도가 $\tilde{O}(\min\{\Gamma^{1.5}SA/\epsilon, \Gamma^3S\sqrt{A}/\epsilon\})$ 인 양자 알고리즘입니다.
무한 지평 비할인 (Infinite-Horizon Undiscounted): 벨만 연산자가 $J$ -단계 $\nu$ -span 축약(contraction)이라고 가정할 때, 쿼리 복잡도가 $\tilde{O}(\Lambda S \sqrt{A} / \epsilon)$ 인 약한 통신 MDP를 위한 새로운 양자 알고리즘입니다.

2. 개선된 후회 경계 (Regret Bounds)

하이브리드 모델과 새로운 서브루틴을 활용하여, 본 논문은 온라인 학습에 대한 새로운 후회 경계를 도출합니다:

유한 지평 (Finite-Horizon):
- 고전적: 특정 파라미터 범위에 대해 최첨단 수준인 $\tilde{O}(\sqrt{HSAT})$ 와 일치하지만, 이전 연구에서 발견된 추가 항들을 제거했습니다.
- 양자: $\tilde{O}(\min\{H^{1.5}SA, H^2S\sqrt{A}\} T^{1-\beta})$ 를 달성합니다. $\beta \in [1, 2)$ 인 경우, $T$ 에 대한 의존성이 감소하여 고전적인 $\sqrt{T}$ 장벽을 깨뜨립니다.
무한 지평 할인 (Infinite-Horizon Discounted):
- 고전적: 특정 조건 하에서 He 등 [97]의 $\tilde{O}(\sqrt{\Gamma^3SAT})$ 경계와 일치합니다.
- 양자: $\tilde{O}(\min\{\Gamma^{1.5}SA, \Gamma^3S\sqrt{A}\} T^{1-\beta})$ 를 달성합니다. $\beta \ge 1$ 인 경우, 후회는 $T$ 에 대해 다항 로그(polylogarithmic) 수준이며, 이는 새로운 결과입니다.
무한 지평 비할인 (Infinite-Horizon Undiscounted):
- 고전적: Bartlett와 Tewari [26]의 $\tilde{O}(\Lambda \sqrt{S^2AT})$ 를 $\tilde{O}(\sqrt{\Lambda SAT})$ 로 개선했습니다.
- 양자: $\tilde{O}(\Lambda S \sqrt{A} T^{1-\beta})$ 를 달성합니다. $\beta \ge 1$ 인 경우, 이는 이전 양자 연구 [98]의 $\tilde{O}(\Lambda S^5 A^4)$ 경계에 비해 상당한 개선입니다.

3. 예산 파라미터 $\beta$ 의 분석

본 논문은 예산 파라미터 $\beta$ 의 "스위트 스팟(sweet spot)"을 식별합니다:

$\beta < 1$ : 고전 및 양자 알고리즘 모두 $T$ 에 대해 다항식 형태의 후회를 보입니다.
$\beta \in [1, 2)$ : 양자 알고리즘은 고전 알고리즘(여전히 $\tilde{O}(\sqrt{T})$ 임)에 비해 $T$ 에 대해 지수적 개선(다항 로그 후회)을 달성합니다.
$\beta \ge 2$ : 고전 알고리즘 또한 다항 로그 후회를 달성함에 따라 양자 이점이 사라집니다.

의의 및 주장

본 논문은 "약간의 자유"(오프라인 생성 단계)를 도입하는 것이 RL의 지형을 근본적으로 변화시킨다고 주장합니다. 생성적 접근을 통해 후회 축적과 정책 계산을 분리함으로써, 저자들은 다음을 입증합니다:

패러다임의 전환: "불확실성에 직면한 낙관주의"와 같은 표준적인 RL 휴리스틱을 피하고, 대신 생성적 액세스를 사용하여 최적 정책을 직접 계산하는 것이 가능하다는 점입니다.
양자 이점: 양자 컴퓨터는 학습 과정에서 실질적인 이점을 제공할 수 있으며, 특히 특정 예산 파라미터 범위( $\beta \in [1, 2)$ )에서 시간 단계 $T$ 에 대해 다항 로그 후회를 달성할 수 있습니다.
모델 수정: 본 연구는 진폭 추정 구현에 관한 이전 양자 RL 문헌의 근본적인 오류를 바로잡고, 향-후 양자 RL 연구를 위한 엄격한 프레임워크를 구축합니다.

저자들은 오프라인 단계(모든 물리적 환경에 존재하는 것은 아님)를 가정하는 모델이 새로운 RL 모델의 탐구를 자극하고, 에이전트가 환경 시뮬레이션에 제한적이고 구조적인 접근 권한을 가질 때 양자 가속의 잠재력을 강조한다는 점을 언급하며 결론을 맺습니다. 또한, 오프라인 단계 없이도 여전히 다항 로그 후회를 달성할 수 있는 의미 있는 양자 RL 모델을 공식화하는 것은 여전히 열린 과제로 남아 있음을 인정합니다.