🤖 machine learning

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance

본 논문은 공유된 정보나 알고리즘을 요구하지 않으면서도 다항식 샘플 복잡도 경계를 확립하기 위해 기대 조건부 거리(Expected Conditional Distance) 파라미터의 게임 이론적 일반화를 도입함으로써, 도달 가능성 목표를 가진 턴 기반 확률 게임에서의 분산형 및 프라이빗 PAC 학습에 대한 첫 번째 긍정적인 결과를 제시한다.

원저자: Ali Asadi, Krishnendu Chatterjee, Pavol Kebis

게시일 2026-07-17

📖 6 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Ali Asadi, Krishnendu Chatterjee, Pavol Kebis

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

당신은 두 명의 라이벌 비디오 게임 캐릭터에게 새로운 신비로운 보드 게임을 가르치려 한다고 상상해 보세요. 한 캐릭터인 "맥스(Max)"는 가능한 한 빨리 보물 상자에 도달하고 싶어 합니다. 다른 캐릭터인 "민(Min)"은 그를 막고 싶어 하며, 아마도 그를 함정으로 유인하거나 영원히 제자리를 맴돌게 만들려 할 것입니다. 이것은 단순히 운에 맡기는 단순한 게임이 아닙니다. 모든 움직임이 확률을 변화시키는 지략의 대결입니다. 컴퓨터 과학의 세계에서, 이것은 "차례 기반 확률 게임(Turn-Based Stochastic Game)"이라고 불립니다. 이는 두 상대방이 차례를 바꾸어 결정을 내리지만, 그 결정의 결과에는 주사위 굴리기가 포함되는 상황을 설명하는 멋진 표현입니다.

보통 컴퓨터에게 게임을 가르칠 때, 우리는 컴퓨터가 규칙, 보드, 그리고 상대방이 무엇을 생각하는지까지 모든 것을 볼 수 있다고 가정합니다. 하지만 현실 세계는 훨씬 더 복잡합니다. 종종 컴퓨터는 규칙을 전혀 모른 채, 직접 플레이하고, 실수하고, 그 결과를 지켜보며 규칙을 배워나가야 합니다. 이것을 "강화 학습(Reinforcement Learning)"이라고 합니다. 목표는 "아마도 대략적으로 옳은(Probably Approximately Correct, PAC)" 전략을 찾는 것입니다. 이 말은 입에 잘 붙지 않지만, 간단히 말해 "적절한 양의 연습을 거친 후에, 우리는 거의 확실하게 최선의 전략과 거의 맞먹는 전략을 찾아낼 수 있는 학습 방법을 설계할 수 있는가?"라는 뜻입니다.

까다로운 점은, "언젠가는 보물에 도달한다"와 같은 특정 유형의 목표를 위해서는, 게임이 영원히 지속될 수 있고 플레이어들이 진정으로 적대적이라면 학습이 수학적으로 불가능하다는 것입니다. 만약 상대방이 당신을 속이려 한다면, 그들은 당신이 배우는 것을 돕는 척하다가 나중에 함정을 드러낼 수도 있습니다. 이 논문은 이 문제의 매우 까다로운 버전을 다룹니다. 즉, 두 플레이어가 서로 대화할 수 없고, 서로의 움직임을 볼 수 없으며, 규칙을 모르는 상태에서 이 게임을 잘 플레이하는 법을 배울 수 있는가 하는 문제입니다.

주사위와 함께하는 숨바꼭질 대게임

이 논문에서 저자들인 알리 아사디(Ali Asadi), 크리슈네두 채터지(Krishnendu Chatterjee), 파볼 케비스(Pavol Kebis)는 역설처럼 들리는 도전에 맞섭니다. 그들은 맥스와 민이라는 두 라이벌 플레이어에게, 맥스는 목표에 도달하려 하고 민은 그를 막으려는 게임을 가르치고자 합니다. 문제는 무엇일까요? 그들은 어둠 속에서 게임을 한다는 것입니다. 그들은 보드의 규칙을 모르고, 노트를 공유할 수 없으며, 매 순간 상대방이 무엇을 하고 있는지조차 알 수 없습니다.

이를 해결하려는 이전의 많은 시도에서, 연구자들은 두 가지 크고 비현실적인 가정을 했습니다. 첫째, 플레이어들이 자신이 배운 모든 것을 기록하는 "공용 노트"를 공유할 수 있다고 가정했습니다. 둘째, 플레이어들이 마치 같은 교과서로 공부하는 두 학생처럼 정확히 같은 학습 알고리즘을 사용한다고 가정했습니다. 이 논문의 저자들은 "잠깐만요, 실제 세상은 그렇게 돌아가지 않습니다"라고 말합니다. 실제로 플레이어들은 종종 개인적인 정보를 가지고 있으며 각자 다른 방식으로 학습합니다. 그들은 알고 싶었습니다. "모두가 자신만의 비밀을 간직하고 각자의 뇌를 사용한다면, 여전히 게임을 잘 플레이하도록 배울 수 있는가?"

"기다림의 게임" 문제

이것이 왜 어려운지 이해하려면, 보물 상자가 백만 년에 한 번만 열리는 문 뒤에 숨겨져 있는 게임을 상상해 보세요. 플레이어들이 그저 추측만 하고 있다면, 그들은 영원히 기다리게 될지도 모릅니다. 수학의 세계에서 이것은 "무한 지평(infinite horizon)" 문제입니다. 만약 게임이 영원히 지속될 수 있고 상대방이 당신을 지연시키기 위해 똑똑하게 행동한다면, 당신은 자신이 올바른 것을 배우고 있는 것인지, 아니면 결코 일어나지 않을지도 모르는 기적을 기다리며 시간을 허비하고 있는 것인지 결코 확신할 수 없습니다.

저자들은 학습이 가능하기 위해서는 안전망이 필요하다는 것을 깨달았습니다. 그들은 **기대 조건 거리(Expected Conditional Distance, ECD)**라는 개념을 도입했습니다. 이것을 게임의 "인내 측정기"라고 생각해 보세요. 이것은 다음과 같은 질문을 측정합니다: "목표에 도달 가능하다면, 평균적으로 도달하는 데 시간이 얼마나 걸리는가?" 만약 ECD가 작다면, 이는 게임이 영원히 길어지지 않고 보물을 비교적 빨리 찾는다는 것을 의미합니다. 만 만약 ECD가 매우 크다면, 이는 게임이 믿기 힘들 정도로 긴 시간 동안 기다리는 루프에 빠질 수 있음을 의미합니다.

논문은 만약 이 "인내 측정기"가 유계(bounded, 즉 게임이 끝나는 데 영원히 걸리지 않는다는 것)라면, 어둠 속에서도 학습이 가능하다는 것을 증명합니다. 그들은 이 수치를 알고 있다면, 당신이 무한한 게임을 유한한 게임으로 효과적으로 바꿀 수 있다는 것을 보여주었습니다. 즉, 보물이 발견되었을 것이라고 예상되는 특정 횟수 이후에 게임을 끊어버림으로써 게임을 유한하게 만드는 것입니다. ECD나 이전 문헌에서 발견되는 다른 유사한 제약 조건(예: ECD)과 같은 가정 없이 학습하는 것은 일반적으로 불가능하다는 점을 유념하는 것이 중요합니다. 이 논문이 ECD가 유일한 방법이라고 주장하는 것은 아니지만, 이 새로운 설정에서 문제를 해결하기 위해 사용된 구체적인 열쇠는 바로 이것입니다.

비법: 단계별 학습

그렇다면 그들은 실제로 플레이어들을 어떻게 가르칠까요? 저자들은 동굴을 탐험하며 지도를 그리는 탐험가 팀처럼 작동하는 정교한 한 쌍의 학습 알고리즘(맥스를 위한 것과 민을 위한 것)을 설계했습니다.

지도 확장: 플레이어들은 단순히 "상태 A" 또는 "상태 B"라고 생각하는 대신, 세 번째 차원이 "시간"인 3D 지도를 상상합니다. 그들은 게임을 "상태-단계(State-Step)" 쌍으로 나눕니다. 이것은 마치 "1단계에서는 주방에 있고, 2단계에서는 복도에 있다"라고 말하는 것과 같습니다. 이는 끝에서부터 역으로 계획하는 데 도움을 줍니다.
"최고의 팔(Best Arm)" 기술: 지도의 모든 지점에서 플레이어들은 행동을 선택해야 합니다. 그들은 "밴딧 학습(Bandit Learning)"이라 불리는 분야의 기술을 사용합니다(마치 최고의 슬롯머신을 찾으려는 도박꾼처럼). 그들은 다양한 움직임을 시도하고, 어떤 것이 가장 잘 작동하는지 확인한 뒤, 그것을 고수합니다. 하지만 그들은 단순히 운이 좋은 것이 아니라 높은 확신을 가지고 이 과정을 수행합니다.
탐색 루프: 플레이어들은 지도의 "미탐사(unexplored)" 부분부터 탐색을 시작합니다. 그들은 알려지지 않은 이 지점들을 찾아야 할 새로운 "보물"로 취급합니다. 특정 지점에 대한 최선의 움직임을 파악하면, 그곳을 "탐사됨(explored)"으로 표시하고 다음으로 넘어갑니다. 이 과정을 반복하며 단계별로 전략을 구축하여 게임 전체에 대한 계획을 세웁니다.
사적인 합의: 여기에 마법이 있습니다. 그들은 결코 대화하지 않지만, 둘 다 유사한 리듬을 따릅니다. 그들은 둘 다 충분히 탐사했다고 느낄 때까지 계속 플레이합니다. 각자의 사적인 관점에서 더 이상 새로운 "미탐사" 지점을 찾을 수 없게 되면, 두 플레이어 모두 게임 시뮬레이터에 신호를 보냅니다: "다 됐습니다! 여기 우리의 전략이 있습니다."

결과: 새로운 종류의 학습

이 논문의 주요 결과는 강력한 "예"입니다. 그들은 이 방법을 통해 플레이어들이 높은 성공 확률로 거의 완벽한(아주 작은 오차 범위 내의) 전략을 학습할 수 있음을 증명했습니다. 결정적으로, 그들이 게임을 플레이해야 하는 횟수(샘플 복잡도)는 관리 가능한 다항식(polynomial) 방식으로 증가합니다. 이는 학습 시간이 무한대로 폭발하지 않고, 게임이 커지더라도 합리적인 수준을 유지함을 의미합니다.

이것은 매우 중요한 성과인데, 왜냐하면 누군가가 이러한 복잡하고 적대적인 게임을 분산된(공유된 뇌가 없는) 환경과 사적인(공 공유된 노트가 없는) 환경에서 학습할 수 있다는 것을 처음으로 보여주었기 때문입니다. 이전에는 효과적으로 학습하기 위해 정보를 공유해야 한다고 생각했습니다. 저자들은 "인내 측정기(ECD)"와 영리한 역방향 계획 전략을 사용함으로써, 어둠 속에서도 학습할 수 있다는 것을 보여주었습니다.

또한 그들은 (ECD와 같은 추가적인 가정 없이) 이러한 유형의 게임을 학습하는 것은 일반적으로 불가능하다는 점을 분명히 했습니다. 만약 게임이 목표에 도달하는 데 걸리는 제한 없이 영원히 지속될 수 있다면, 어떤 학습 알고리즘도 성공을 보장할 수 없습니다. 논문은 매우 명확하게 밝히고 있습니다: 수학적 성립을 위해서는 시간의 경계(ECD)가 반드시 필요합니다.

왜 관심을 가져야 하는가?

"이론적인 게임에서 주사위를 굴리는 두 플레이어가 왜 중요한가?"라고 의문을 가질 수 있습니다. 하지만 이것은 단지 보드 게임에 관한 이야기가 아닙니다. 이런 종류의 수학은 자율 주행 자동차, 네트워크 보안, 자동 거래와 같은 분야의 안전한 AI를 구축하는 근간이 됩니다. 이러한 실제 시나리오에서 서로 다른 시스템(또는 해커)은 상대방이 무엇을 하는지 완전히 알지 못한 채 끊임없이 상호작용합니다.

이 논문은 우리에게 새로운 도구 상자를 제공합니다. 이는 우리가 모든 AI 에이전트에게 비밀을 공유하도록 강제할 수 없고, 심지어 그들이 서로를 이기려고 노력하는 상황이라 할지라도, "나쁜 일"이 무한한 시간 후에 발생하지 않는다는 것을 안다면 그들을 똑똑하고 안전하게 가르칠 수 있다는 것을 알려줍니다. 이는 중앙 통제 장치가 없어도 혼란스럽고 불확실한 세상을 항해할 수 있는 AI를 구축하기 위한 한 걸음입니다.

요약하자면, 저자들은 라이벌과 함께 어둠 속에서 게임을 배우는 것과 같이 불가능해 보이는 문제를 가져와서, 영리한 인내 측정기와 철저한 역방향 사고를 사용하여 한 단계씩 불을 밝히는 방법을 찾아냈습니다.

기술 요약: 도달 가능성 목적을 가진 턴 기반 확률 게임에서의 PAC 학습

문제 정의
본 논문은 도달 가능성(reachability) 목적을 가진 턴 기반 확률 게임(Turn-Based Stochastic Games, TBSGs)에 대한 확률적 근사 정확(Probably Approximately Correct, PAC) 학습 문제를 다룹니다. TBSGs에서 두 명의 적대적 플레이어(Max와 Min)는 확률적 전이가 존재하는 유한 상태 공간 위에서 상호작용합니다. 목적은 Max가 타겟 상태 집합에 도달할 확률을 최대화하고, Min이 그 확률을 최소화하는 것입니다.

저자들은 도달 가능성 목적을 위한 PAC 학습이 추가적인 가정 없이는 TBSGs(심지어 마르코프 결정 과정(MDP)에서도)에서 일반적으로 불가능하다는 근본적인 난해함(hardness) 결과를 강조합니다. 이러한 불가능성은 도달 가능성이 무한한 속성을 가지기 때문이며, 학습 단계 중의 적대적 행동은 학습을 무의 futile하게 만들 수 있습니다(예: 적대자가 실제 최적 전략을 가리기 위해 타겟에 즉시 도달하는 차선책을 선택할 수 있음).

이전의 TBSGs에 대한 긍정적인 결과들은 두 가지 강력한 가정에 의존했습니다:

공개 정보(Public Information): 두 플레이어가 모든 정보(상태, 행동, 전이)를 공유함.
중앙 집중식 학습(Centralized Learning): 두 플레이어가 동일한 학습 알고리즘을 사용함.

본 연구는 플레이어들이 서로 다른 알고리즘을 사용하고 개별적인 정보(구체적으로, 현재 상태는 해당 상태를 소유한 플레이어만 알 수 있음)를 갖는 분산된(decentralized) 환경에서 학습을 달성하기 위해 이러한 가정들을 완화하는 것을 목표로 합니다.

방법론
제안된 접근 방식은 2단계 축소(reduction)와 새로운 학습 알고리즘을 포함합니다:

기대 조건부 거리(Expected Conditional Distance, ECD)의 일반화:
저자들은 본래 MDP를 위해 정의된 ECD 파라미터의 게임 이론적 일반화를 도입합니다.
- 정의: 게임의 ECD는 모든 Min 전략에 대한 Sup(상한)이자, 타겟에 도달하는 조건 하에서 Max의 최적 대응(best-response)에 대한 Inf(하한)인 타겟 도달까지의 기대 시간으로 정의됩니다.
- 근거: TBSGs로의 여러 자연스러운 ECD 일반화 모델들이 실패함을 보였습니다(예: 근사를 위해 필요한 호라이즌(horizon)이 클 때도 ECD가 작을 수 있음). 제안된 정의는 만약 ECD가 $L$ 에 의해 유계(bounded)된다면, 무한 호라이즌 도달 가능성 문제가 호라이즌 $H \approx 2(L+1)/\epsilon$ 인 유한 호라이즌 문제로 축소될 수 있음을 보장합니다. 이 절단(truncation) 과정을 통해 다루기 힘든 무한 호라이즌 문제를 다룰 수 있는 유한 호라이즌 문제로 변환합니다.
유한 호라이즌 확장(Finite-Horizon Expansion):
유한 호라이즌 도달 가능성 문제를 해결하기 위해, 저자들은 확장된 게임(expanded game) $G'$ 를 정의합니다. 이 게임은 시간 호라이즌을 상태 공간으로 펼쳐서, $\ell$ 이 현재 단계를 나타내는 상태-단계 쌍 $(s, \ell)$ 을 생성합니다. 이 변환을 통해 역방향 귀납법(backward induction)을 사용할 수 있게 되며, 게임은 위치 전략(positional strategies)만으로 충분한 유한 호라이즌 MDP 유사 구조가 됩니다.
분산 학습 알고리즘 (LeTuReGa):
본 논문은 분산된 프라이빗 설정에 설계된 한 쌍의 알고리즘인 LeTuReGaMax와 LeTuReGaMin을 제시합니다.
- 메커니즘: 알고리즘은 단계별로 작동합니다. 각 단계에서 플레이어는 호라이즌 $L$ 에서 단계 0까지 역방향 귀납법을 사용하여 전략을 구성합니다.
- 지역 학습(Local Learning): 각 상태-단계 $(s, \ell)$ 에서 플레이어는 높은 신뢰도로 $\epsilon$ -최적 행동을 식별하기 위해 최적 팔 식별(Best-Arm Identification, BAI) 루틴을 사용합니다. 이는 전체 전이 확률을 추정할 필요 없이(프라이빗 설정에서는 불가능함), 최적 행동을 직접 식별하는 데 집중합니다.
- 탐색(Exploration): 알고리즘은 "미탐색(unexplored)" 상태-단계 세트를 유지합니다. 이 미탐색 세트는 플레이어들이 새로운 상태-단계 공간을 방문하도록 유도하는 보조 타겟 세트 역할을 합니다.
- 종료: 학습 과정은 두 플레이어가 시뮬레이터에 전략 프로필을 제안할 때 종료되며, 이는 두 플레이어 모두 현재 전략을 사용하여 새로운 상태-단계를 발견할 수 없을 때 발생합니다.

주요 기여

분산 프라이빗 PAC-RL: 본 연구는 도달 가능성 목적을 가진 TBSGs에서 분산 및 프라이빗 정보 설정 하에서의 PAC-RL에 대한 첫 번째 긍정적인 결과를 제공합니다. 플레이어들은 알고리즘이나 상태 정보를 공유하지 않습니다.
ECD 일반화: 본 논문은 ECD 파라미터의 미묘하고 올바른 TBSGs 일반화를 확립하여, 유계된 ECD가 무한 호라이즌 도달 가능성을 유한 호라이즌 도달 가능성으로 축소할 수 있음을 증명합니다.
다항 시간 샘플 복잡도: 저자들은 제안된 알고리즘에 대한 다항 시간 샘플 복잡도 상한을 설정합니다. 복잡도는 상태 수( $|S|$ ), 행동 수( $|A|$ ), ECD 파라미터( $L$ ), 그리고 오차 허용 범위의 역수( $1/\epsilon$ ) 및 실패 확률의 역수( $1/p$ )에 대해 다항식적으로 의존합니다.
알고리즘 설계: 전이 확률 추정 없이 역방향 귀납법, 최적 팔 식별, 그리고 상태-단계의 동적 탐색을 결합한 학습 절차를 도입합니다.

결과
주요 이론적 결과(Corollary 16)는 (LeTuReGaMax, LeTuReGaMin) 알고리즘 쌍이 ECD 가정 하에 도달 가능성 목적에 대해 PAC-RL임을 명시합니다. 샘플 복잡도는 다음과 같습니다:
$O\left( \frac{|S|^3 L^7 |A| \log(|S|^2 L^2 / (p \epsilon^2))}{\epsilon^{10}} \right)$
여기서 $L$ 은 ECD 파라미터의 상한입니다.

증명은 다음을 보여주는 것에 기초합니다:

학습 시뮬레이션이 $|S'|$ 단계(여기서 $S'$ 는 확장된 상태의 집합) 내에 종료됨을 보임.
높은 확률로, 구성된 전략 프로필은 유한 호라이즌 게임에 대해 $\epsilon$ -최적임.
ECD 상한 덕분에, 유한 호라이즌 게임에서의 $\epsilon$ -최적성은 원래의 무한 호라이즌 게임에서의 $\epsilon$ -최적으로 변환됨.

의의
본 논문은 이전 연구의 강력한 가정들을 완화했다는 점에서 주요한 의의를 가집니다. 이전의 TBSGs에 대한 PAC 학습 결과들은 공개 정보와 중앙 집중식 학습을 요구했습니다. 본 연구는 플레이어들이 독립적으로 행동하고 개별적인 상태 정보를 가지고 있더라도, ECD 파라미터가 유계되어 있다면 학습이 가능하다는 것을 보여줍니다. 또한, 샘플 복잡도 보장이 부족했던 기존의 TBSGs용 "anytime" 알고리즘들과 달리, 본 연구는 명시적인 다항식 상한을 제공합니다. 저자들은 이것이 도달 가능성 목적을 가진 TBSGs에서 분산 프라이빗 정보 PAC-RL에 대한 첫 번째 긍정적인 결과라고 언급합니다.