The Sample Complexity of Policy Learning with Mu-Resets

당신이 로봇에게 거대하고 뒤틀린 미로를 통과하는 법을 가르치려 한다고 상상해 보세요. 인공지능의 세계에서는 이를 강화 학습(Reinforcement Learning)이라고 부릅니다. 로봇은 시행착오를 겪고, 실수를 하고, 보상을 수집하며 무언가를 배웁니다. 마치 게임에서 높은 점수를 얻기 위해 노가다를 하는 게이머처럼 말이죠. 하지만 문제가 하나 있습니다. 미로는 믿을 수 없을 정도로 길 수 있고, 만약 로봇이 초반에 길을 잃으면 출구를 영영 찾지 못할 수도 있습니다. 이를 돕기 위해 연구자들은 "마법의 리셋 버튼"을 발명했습니다. 로봇을 매번 처음부터 시작하게 하는 대신, 이 버튼을 사용하면 미로 깊숙한 곳의 무작위 지점에 로봇을 떨어뜨릴 수 있습니다. 이것을 **$\mu$-리셋 프로토콜($\mu$-resets protocol)**이라고 부릅니다. 이것은 학습 속도를 엄청나게 빠르게 만들어 줄 지름길처럼 들립니다, 그렇죠?

과학자들이 던진 핵심적인 질문은 이것입니다: 만약 로봇의 두뇌(그것의 "정책(policy)")가 미로 내의 가능한 최선의 경로만큼 똑똑하다면, 이 마법의 버튼은 실제로 효과가 있을까요? 다시 말해, 완벽한 경로가 존재한다는 것을 우리가 알고 있고 로봇이 그 경로를 배울 능력이 있다면, 리셋 버튼이 그 경로를 빠르게 찾는 데 도움을 줄 수 있을까요? 오랫동안 그 답은 매우 긴 미로의 경우 "아니오"이거나, 혹은 로봇이 믿을 수 없을 정도로 강력한 성능을 가졌을 때만 "예"인 것처럼 보였습니다. 이 논문은 미로의 길이가 작업의 난이도를 어떻게 변화시키는지 알아내기 위해 이 깊은 미스터리를 파고듭니다.

---

위대한 미로 리셋 미스터리

이 논문은 리셋 버튼을 사용하여 로봇을 어디든 떨어뜨릴 수 있을 때, 길고 복잡한 미로를 가르치는 것이 얼마나 어려운지에 대한 탐정 이야기입니다. 저자인 Gene Li와 동료들은 샘플 복잡도(sample complexity), 즉 "로봇이 마침내 완벽한 경로를 배울 때까지 미로를 몇 번이나 통과해야 하는가?"라는 질문을 해결하려 합니다.

그들은 특정 시나리오에 집중합니다: 로봇은 완벽한 경로를 배울 만큼 충분히 똑똑하며(이를 **실현 가능성(realizability)**이라 부릅니다), 우리에게는 유용한 리셋 버튼이 있는 상황입니다. 반전은, 난이도가 리셋 버튼이 어떻게 작동하느냐에 전적으로 달려 있다는 점입니다. 저자는 리셋 버튼의 "커버리지(coverage)"가 결정적이라고 밝혔는데, 이는 리셋 버튼이 로봇을 안전하고 도움이 되는 곳에 떨어뜨리는지, 아니면 위험하고 혼란스러운 곳에 떨어뜨리는지를 묻는 것과 같습니다.

"모든 정책(All-Policy)"의 함정: 리셋 버튼이 거짓말일 때

먼저, 저자는 리셋 버튼이 매우 관대한 시나리오를 살펴보았습니다. 이 버튼은 어떤 로봇이 미로를 통과하든 상관없이, 결국 그 경로 위에 로봇을 떨어뜨려 놓는다는 것을 보장합니다. 이를 **유계된 모든 정책 집중성(bounded all-policy concentrability)**이라고 부릅니다.

여러분은 이렇게 생각할지도 모릅니다. "좋아! 버튼이 모든 가능한 경로를 커버하고 우리 로봇이 최선의 경로를 배울 만큼 똑똑하다면, 아주 잘 풀리겠네." 하지만 이 논문은 이것이 사실이 아님을 증명합니다.

저자는 수학적인 미로(층으로 이루어진 "조합 자물쇠")를 구축하여, 이처럼 매우 관대한 리셋 버튼이 있더라도 미로가 길면(호라이즌 $H$가 크면) 로봇이 학습하는 데 여전히 천문학적인 횟수의 시도가 필요함을 보여주었습니다. 구체적으로, 필요한 시도의 횟수는 미로의 길이에 따라 지수적으로 증가하며, 이를 $2^{\Omega(H)}$라고 표기합니다.

이를 시각화하기 위해, 100단계 길이의 미로를 상상해 보세요. 리셋 버튼이 "모든 정책(all-policy)" 방식이라면, 로봇은 올바른 길을 찾기 위해 우주의 원자 수보다 더 많은 경로를 시도해야 할 수도 있습니다. 논문은 이 특정 설정에서 리셋 버튼이 속도를 높이는 데 사실상 무용지물임을 보여줍니다. 로봇은 시작부터 전체 움직임의 순서를 추측해야 하며, 리셋 버튼은 이 추측 게임을 건너뛰게 도와주지 못합니다. 이 결과는 단순히 "좋은" 리셋 분포를 갖는 것만으로는 학습을 효율적으로 만드는 데 충분하지 않으며, 그보다 훨씬 더 강력한 무언가가 필요하다는 점을 시사합니다.

"푸시포워드(Pushforward)"의 돌파구: 더 똑똑한 리셋

다음으로, 저자는 "그렇다면 정말로 효과가 있는 다른 종류의 리셋 버튼이 있을까?"라고 물었습니다. 그들은 **유계된 푸시포워드 집중성(bounded pushforward concentrability)**이라는 조건에 주목했습니다.

이것은 단순히 아무 데나 떨어뜨리는 것이 아니라, 다음 단계를 명확히 볼 수 있는 지점에 로봇을 떨어뜨리는 리셋 버튼을 의미합니다. 즉, 리셋 지점에서 한 걸음을 내디디면, 그 다음 위치 또한 리셋 버튼이 다시 떨어질 수 있는 장소가 되도록 보장하는 것입니다. 마치 리셋 버튼이 항상 따라갈 수 있는 빵 부스러기 길을 만들어 놓은 것과 같습니다.

이 특정한 종류의 리셋을 사용하면 이야기가 극적으로 바뀝니다. 저자는 로봇이 경로를 학습할 수 있음을 증명했지만, 난이도가 이전만큼 빠르게 증가하지는 않았습니다. $2^H$ 번의 시도가 필요한 대신, 이제 로봇은 대략 $2^{\Theta(\sqrt{H})}$ 번의 시도만 필요합니다.

이 차이를 비유로 풀어보겠습니다. 미로가 100단계 길이($H=100$)라면:

• 기존의 "모든 정책(all-policy)" 방식은 약 $2^{100}$ 번의 시도가 필요합니다 (우주적인 규모의 엄청난 숫자입니다).
• 새로운 "푸시포워드(pushforward)" 방식은 약 $2^{10}$ 번, 즉 1,024 번의 시도만 필요합니다.

이것은 엄청난 차이입니다! 은하계 크기의 건초더미에서 바늘을 찾는 것과 침실 크기의 건초더미에서 바늘을 찾는 것의 차이와 같습니다. 논문은 이 더 똑똑한 리셋을 사용하면 로봇이 경로를 훨씬 빠르게 학습할 수 있지만, 여전히 "쉽다"는 의미(즉, 즉각적이라는 의미)는 아님을 보여줍니다.

알고리즘: 블록 단위 탐험가

그렇다면 푸시포워드 리셋을 사용할 때 로봇은 실제로 어떻게 학습할까요? 저자는 BlockPSDP라고 불리는 새로운 학습 전략을 설계했습니다.

긴 미로를 한꺼번에 다루기에는 너무 무섭다고 상상해 보세요. 대신 미로 전체를 통째로 외우려 하는 대신, 로봇은 미로를 덩어리(블록)로 나눕니다. 첫 번째 블록을 배우고, 그다음 두 번째, 그다음 세 번째를 배우며 끝에서부터 역순으로 진행합니다.

1. 리셋 버튼을 사용하여 블록의 시작 지점에 자신을 떨어뜨립니다.
2. 최선의 결과를 이끌어내는 움직임이 무엇인지 확인하기 위해 해당 블록 내에서 가능한 모든 움직임을 시도합니다.
3. 해당 블록에 대한 최선의 움직임을 파악하면, 그것을 "고정"하고 다음 블록으로 넘어갑니다.

리셋 버튼이 "푸시포워드(연결형)" 방식이기 때문에(블록들을 매끄럽게 연결해주기 때문에), 로봇이 한 블록에서 저지르는 실수가 전체 게임을 망치지 않습니다. 오류는 범위 내에 갇혀 있게 됩니다. 수학적 계산에 따르면, 이 방법은 이러한 조건 하에서 가장 효율적인 학습 방법이며, 저자는 이보다 더 나은 성과를 낼 수 없음을 증명했습니다.

결론: 우리가 배운 것

논문은 다음과 같이 명확한 지형도를 제시하며 마무리됩니다:

• 만약 리셋 버튼이 "모든 정책(all-policy)"을 커버한다면: 미로가 길 경우 학습은 여전히 불가능할 정도로 어렵습니다. 리셋 버튼이 충분한 도움을 주지 못합니다. 난이도는 미로 전체 길이에 대한 **지수 함수($2^H$)**로 증가합니다.
• 만약 리셋 버튼이 "푸시포워드(pushforward)" 방식이라면 (단계를 연결한다면): 여전히 어렵긴 하지만, 훨씬 덜 어렵습니다. 난이도는 미로 길이의 **제곱근($2^{\sqrt{H}}$)**에 대한 지수 함수로 증가합니다.

저자는 또한 PSDP라는 유명한 기존 알고리즘이 실제로는 하위 최적(suboptimal)이라는 점을 보여주었습니다. 좋은 리셋 버튼이 있더라도 PSDP는 너무 많은 시도를 요구합니다. 그들의 새로운 "BlockPSDP" 알고리즘은 이 문제에 대한 이론적 효율성의 한계치에 도달한 최초의 알고리즘입니다.

요약하자면, 이 논문은 리셋 버튼을 갖는 것이 강력한 도구이지만, 그 힘은 리셋이 어떻게 이루어지느냐에 전적으로 달려 있다는 것을 알려줍니다. 만약 단순히 무작위로 떨어뜨린다면, 당신은 여전히 추측 게임에 갇혀 있을 뿐입니다. 하지만 다음 단계와 연결되도록 떨어뜨려 준다면, 훨씬 적은 시간 안에 퍼즐을 풀 수 있습니다. 이는 인공지능의 세계에서 데이터의 품질(로봇을 어디에 떨어뜨리는가)이 로봇 자체의 지능만큼이나 중요하다는 사실을 상기시켜 줍니다.