Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model

당신이 눈을 깜빡일 때마다 물리 법칙이 변하는 은하계를 항해하는 우주선의 선장이라고 상상해 보십시오. 당신의 목표는 연료가 떨어지기 전에 최대한 많은 '스타더스트(star-dust)' 포인트를 모으는 것입니다. 이를 위해 당신에게는 완벽한 지도와 매 순간 정확히 어느 방향으로 회전해야 하는지를 알려주는 지침서가 필요합니다. 이것이 바로 인공지능(AI)의 한 분야인 **강화 학습(Reinforcement Learning)**의 핵심입니다. 강화 학습은 인공적인 '에이전트(agent)'가 세상과 상호작용하고, 이것저것 시도해 보고, 그 결과로 가장 큰 보상을 얻는 방법을 배우며 똑똑한 결정을 내리는 법을 익히는 과정입니다.

에이전트가 살아가는 세상은 종종 **마르코프 결정 과정(Markov Decision Process, MDP)**으로 모델링됩니다. 이것을 거대한 다층 보드게임이라고 생각해 보십시오. 당신은 특정 칸(‘상태(state)’)에 있고, 선택할 수 있는 이동 목록(‘행동(action)’)이 있습니다. 각 이동은 점수(‘보상(reward)’)를 주며 새로운 칸으로 이동하게 만들 수도 있지만, 함정이 하나 있습니다. 바로 보드가 미끄럽다는 것입니다. 당신은 어떤 칸에 착륙할지 확실히 알 수 없으며, 오직 그곳에 착륙할 확률만을 알 수 있습니다. 문제는 보드가 너무 거대해서(수백만 개의 칸과 이동이 있는 경우), 일반적인 컴퓨터가 이를 빠르게 해결하는 것이 불가능하다는 점입니다. 이를 '차원의 저주(curse of dimensionality)'라고 부릅니다.

여기에 **양자 컴퓨팅(Quantum Computing)**이 등장합니다. 일반 컴퓨터가 비트(0과 1)로 생각한다면, 양자 컴퓨터는 '큐비트(qubit)'를 사용하여 마치 앞면과 뒷면이 동시에 존재하는 회전하는 동전처럼 여러 상태에 동시에 존재할 수 있습니다. 이를 통해 양자 컴퓨터는 많은 가능성을 병렬적으로 탐색할 수 있으며, 잠재적으로 복잡한 퍼즐을 훨씬 더 빠르게 해결할 수 있습니다. 과학자들은 이 강력한 힘을 사용해 강화 학습의 암호를 풀고, 우리 우주선이 답을 기다리느라 평생을 허비하지 않고도 완벽한 항해 전략을 찾을 수 있기를 기대하며 이 기술을 활용하려 노력해 왔습니다.

논문의 거대한 도약: 더 빠른 양자 항해

이 연구에서 저자 조아오 F. 도리고엘로(Joao F. Doriguello)는 이러한 완벽에 가까운 항해 전략을 이전 방식보다 훨씬 빠르게 찾아내기 위한 새로운 양자 알고리즘 세트를 제안합니다. 저자는 두 가지 특정 유형의 보드게임을 다룹니다. 하나는 **유한 지평선 MDP(Finite-Horizon MDPs)**로, 결승선이 있는 경주처럼 정해진 횟수의 턴 후에 게임이 끝나는 형태입니다. 다른 하나는 **무한 지평선 할인 MDP(Infinite-Horizon Discounted MDPs)**로, 게임은 영원히 계속되지만 나중에 얻는 점수는 지금 얻는 점수보다 가치가 낮아지는 형태입니다.

저자의 주요 발견은 '거의 완벽한' 전략(이를 $\epsilon$-최적 정책이라 부름)을 이전의 그 어떤 방법보다 훨씬 적은 횟수의 '질문(queries)'만으로 계산할 수 있다는 것입니다. 컴퓨터 과학의 언어로 말하자면, 저자는 **질의 복잡도(query complexity)**를 개선했습니다. 여기서 '질의(queries)'란 컴퓨터가 이동의 확률을 이해하기 위해 게임의 규칙을 얼마나 자주 훔쳐봐야 하는지를 의미합니다. 확인해야 하는 횟수가 적을수록 해결 속도는 빨라집니다.

어떻게 해냈는가: "슈퍼 스캐너"와 "안전망"

이전의 양자 시도들은 초고속 손전등을 사용하긴 했지만, 여례 모든 턴을 하나씩 확인하며 미로의 최적 경로를 찾는 것과 같았습니다. 매우 빠르긴 했지만, 여전히 확인해야 할 턴이 많았습니다. 저자의 새로운 방법은 두 가지 강력한 아이디어를 결합하여 엄청난 속도 향상을 이끌어냅니다.

1. "슈퍼 스캐너" (양자 평균 추정, Quantum Mean Estimation): 단순히 어떤 이동의 평균 보상을 추측하는 대신, 새로운 알고리즘은 양자 기법을 사용하여 평균값과 결과가 얼마나 변동될 수 있는지(분산, variance)를 동시에 추정합니다. 이는 마치 고속도로의 평균 차량 속도뿐만 아니라 도로가 얼마나 울퉁불퉁한지도 한 번의 눈길로 파악하는 스캐너를 가진 것과 같습니다.
2. "안전망" (단조성 및 총 분산, Monotonicity and Total-Variance): 저자는 고전 수학에서 사용되는 '총 분산(total-variance)'이라는 영리한 기법을 빌려왔습니다. 어두운 복도를 걷고 있다고 상상해 보십시오. 발을 헛디디면 넘어질 수도 있습니다. 하지만 만약 당신의 비틀거림이 서로 상쇄된다는 것(어떤 걸음은 흔들리고 어떤 걸음은 안정적임)을 안다면, 두려움 없이 더 빨리 걸을 수 있습니다. 이 알고리즘은 이 수학적 원리를 사용하여 개별적인 추측이 완벽하지 않더라도 전체 게임 동안의 총 오차는 작게 유지된다는 것을 증명합니다. 이를 통해 양자 컴퓨터는 덜 조심스럽고 더 공격적으로 탐색할 수 있으며, 불필요한 확인 과정을 건너뛸 수 있습니다.

이 "슈퍼 스캐너"를 "양자 최대값 찾기(Quantum Maximum Finding)" 루틴(거대한 목록에서 가장 높은 숫자를 즉시 찾아내는 도구) 안에 중첩함으로써, 저자는 이전보다 제곱(quadratically) 더 빠르게 최선의 이동을 찾아내는 시스템을 구축했습니다.

결과: 새로운 기록

이 논문은 새로운 알고리즘이 높은 확률로 작동함을 수학적으로 증명합니다. 저자는 $S$개의 상태, $A$개의 행동, 그리고 $H$(또는 $\Gamma$)의 지평선을 가진 게임에 대해, 이 방법이 대략 다음과 같은 횟수의 질의를 요구함을 보여줍니다.

• 유한 지평선 게임의 경우: $\tilde{O}\left(\frac{H^{2.5} S \sqrt{A}}{\epsilon}\right)$ 질의.
• 무한 지평선 게임의 경우: $\tilde{O}\left(\frac{\Gamma^{2.5} S \sqrt{A}}{\epsilon}\right)$ 질의.

여기서 $\epsilon$은 솔루션이 얼마나 완벽에 가까워야 하는지를 나타내며, $\epsilon$이 작을수록 더 정밀한 답을 의미합니다. "틸데($\tilde{O}$)" 표기법은 로그와 같은 아주 작고 복잡한 세부 사항들은 무시하고 주요 성장률에 집중했음을 의미합니다.

이 수치들은 $H^3$ 또는 $\Gamma^3$와 같은 더 높은 차수에 머물러 있던 기존의 최선 양자 알고리즘들에 비해 측정 가능한 수준의 개선을 보여줍니다. 저자는 계산 작업의 상당 부분을 깎아낸 것입니다. 비록 아직 절대적인 이론적 한계(하한선, lower bound)에 도달한 것은 아니지만, 저자는 목표 지점을 크게 앞당겼으며, 양자 컴퓨터가 이전에 생각했던 것보다 훨씬 더 효율적으로 복잡한 의사결정 세계를 항해할 수 있음을 입증했습니다.

요약하자면, 이 논문은 단순히 게임을 플레이하는 새로운 방법을 제시하는 것이 아니라, 더 빠르고 효율적인 새로운 양자 전략이 존재한다는 엄격한 수학적 증명을 제공함으로써, 인공지능의 '차원의 저주'를 해결하는 데 한 걸음 더 다가갔습니다.