🔢 mathematics

Policy Iteration for Two-Player General-Sum Stochastic Stackelberg Games

이 논문은 리더의 정책이 최선의 대응을 하는 팔로워를 고려할 때 단조로운 개선을 보장하는 정책 개선 정리를 유도하고, 이를 기반으로 새로운 정책 반복 알고리즘을 제안하며, 리더가 단기적일 경우 파레토 프론트로 수렴함을 증명합니다.

원저자: Mikoto Kudo, Youhei Akimoto

게시일 2026-03-17

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Mikoto Kudo, Youhei Akimoto

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

1. 배경: 쇼핑몰 사장과 손님의 게임

상상해 보세요. 어떤 쇼핑몰의 **사장님 (리더)**이 있습니다. 사장님은 페이지 구성, 광고, 할인 쿠폰 등을 조절할 수 있습니다. 반면, **손님 (팔로워)**은 자신의 취향과 필요에 따라 물건을 구매합니다.

사장님의 목표: 장기적인 매출을 극대화하는 것.
손님의 목표: 자신의 만족도를 최대로 하는 것 (가장 좋은 상품을 가장 싸게 사는 것).

이때 사장님은 "내가 이런 광고를 내면 손님은 어떨까?"라고 생각하며 정책을 결정합니다. 손님은 항상 자신의 이익이 가장 큰 행동을 선택합니다 (이를 최적 반응이라고 합니다).

기존 연구들은 사장님이 손님의 반응을 고려해 정책을 바꿀 때, **"무조건 매출이 오르는지 보장할 수 없다"**는 문제가 있었습니다. 마치 미끄러운 언덕을 올라가다가 갑자기 아래로 미끄러져 내리는 것처럼, 정책이 나빠질 수도 있다는 뜻입니다. 특히, 두 사람의 목표가 완전히 일치하지 않는 (일반적인) 상황에서는 '완벽한 균형점 (SSE)'이 아예 존재하지 않는 경우도 많습니다.

2. 이 논문의 핵심 해결책: "점진적인 개선"과 "파레토 최적"

이 논문은 두 가지 중요한 아이디어를 제시합니다.

① "한 걸음씩, 절대 뒤로 가지 않기" (단조 개선)

기존 방법들은 큰 도약을 시도하다가 실패하면 상태가 나빠질 수 있었습니다. 하지만 이 논문은 **"지금보다 조금이라도 더 나은 정책으로만 넘어가라"**는 규칙을 만들었습니다.

비유: 산을 오를 때, 실수해서 아래로 떨어지는 것은 허용하지 않고, 무조건 한 발짝씩 위로만 올라가는 길만 찾습니다. 이렇게 하면 비록 정상에 바로 닿지 못하더라도, 결코 나빠지지 않고 계속 나아집니다.

② "완벽한 해답이 없다면, '최고의 타협점'을 찾자" (파레토 최적)

종종 "모든 상황에서 최고의 해답"은 존재하지 않습니다. (예: A 상황을 좋게 만들면 B 상황이 나빠지는 식)
이때 이 논문은 **"어떤 상황에서도 더 이상 개선할 수 없는 상태 (파레토 프론트)"**를 목표로 삼습니다.

비유: 두 사람이 케이크를 나누는 상황입니다. "누군가 더 많이 먹으면 다른 사람이 더 적게 먹어야 한다"는 한계가 있을 때, **"더 이상 한쪽이 손해 보지 않고는 다른 쪽이 더 먹을 수 없는 상태"**를 찾습니다. 이것이 바로 '파레토 최적'입니다.

3. 새로운 알고리즘의 작동 원리

이 논문이 제안한 '정책 반복 (Policy Iteration)' 알고리즘은 다음과 같이 작동합니다.

시작: 사장님이 임의의 정책 (예: 모든 상품에 10% 할인) 으로 시작합니다.
손님 반응 예측: "이 정책일 때 손님은 어떻게 행동할까?"를 계산합니다. (손님은 항상 자신의 이익을 최대로 합니다.)
개선 시도: "손님의 반응을 고려했을 때, 지금보다 매출이 더 오르는 다른 정책이 있을까?"를 찾습니다.
- 만약 더 좋은 정책이 있다면, 그쪽으로 넘어갑니다.
- 만약 지금보다 나쁜 정책은 절대 선택하지 않습니다.
종료: 더 이상 개선할 수 없는 상태 (파레토 최적) 에 도달하면 멈춥니다.

4. 왜 이것이 중요한가요?

안정성: 기존 방법들은 실패할 경우 결과가 엉망이 될 수 있었지만, 이 방법은 절대 나빠지지 않는 것을 수학적으로 보장합니다.
현실성: "완벽한 해답"이 없는 복잡한 상황에서도, "최대한 좋은 해답"을 찾아줍니다.
적용 가능성: 이 방법은 게임 이론뿐만 아니라, 인공지능이 상대방의 행동을 예측하며 학습하는 모든 분야 (예: 자율주행차가 보행자의 반응을 예측하거나, 기업이 경쟁사의 반응을 예측하는 경우) 에 적용할 수 있습니다.

5. 요약

이 논문은 **"상대방이 항상 똑똑하게 반응할 때, 내가 실수하지 않고 계속 발전하며 최고의 결과를 얻을 수 있는 방법"**을 찾아냈습니다.

마치 미끄러운 빙판 위에서 넘어지지 않고, 한 걸음씩 안전하게 정상에 도달하는 등반 기술을 개발한 것과 같습니다. 비록 정상의 정점 (완벽한 균형) 에 항상 도달할 수는 없더라도, 그 과정에서 가장 좋은 지점 (파레토 최적) 에 도달할 수 있다는 것이 이 연구의 가장 큰 성과입니다.

이 논문은 **이중 플레이어 일반합 확률적 스택버그 게임 (Two-Player General-Sum Stochastic Stackelberg Games, SSGs)**을 대상으로 하며, 리더 (Leader) 의 정책이 팔로워 (Follower) 의 최적 대응 (Best Response) 을 고려하여 최적화되는 문제를 다룹니다. 기존 방법론들의 한계를 극복하고, 리더의 성능이 단조롭게 개선됨을 보장하는 새로운 정책 반복 (Policy Iteration) 알고리즘을 제안합니다.

주요 내용은 다음과 같습니다.

1. 문제 정의 및 배경

스택버그 게임 (Stackelberg Game): 리더가 먼저 전략을 선택하고, 팔로워는 리더의 전략에 대해 자신의 보상을 최대화하는 최적 대응 (Best Response) 전략을 선택하는 게임 모델입니다.
확률적 스택버그 게임 (SSG): 마르코프 의사결정 과정 (MDP) 을 다중 에이전트로 확장한 것으로, 상태 전이가 모든 에이전트의 행동에 의존합니다.
문제점:
- 기존 연구 (Bucarey et al., 2022; Zhang et al., 2020a 등) 는 동적 프로그래밍 연산자 (Dynamic Programming Operator) 기반의 고정점 (Fixed Point) 을 찾거나 정책 경사 (Policy Gradient) 방법을 사용했습니다.
- 그러나 일반합 (General-Sum) 환경에서는 **정상 스택버그 균형 (Stationary Stackelberg Equilibrium, SSE)**이 항상 존재하지 않을 수 있습니다.
- 기존 알고리즘은 SSE 가 존재하지 않거나 수렴하지 않을 경우, 리더의 정책이 저품질로 수렴할 수 있으며, 리더의 성능이 단조롭게 개선됨 (Monotone Improvement) 을 보장하지 못합니다.

2. 핵심 방법론: 파레토 최적 정책 반복 (Pareto-Optimal Policy Iteration)

저자는 SSE 가 존재하지 않는 상황에서도 합리적인 해를 찾기 위해 파레토 최적 (Pareto-Optimality) 개념을 도입하고, 이를 기반으로 한 새로운 정책 반복 알고리즘을 제안합니다.

A. 기존 DP 연산자의 한계 분석

기존 연구에서 사용하는 동적 프로그래밍 연산자의 고정점은 팔로워의 최적 대응을 보장하지 않을 수 있습니다. 즉, 고정점에서의 리더 정책은 실제 팔로워의 최적 대응 하에서 기대되는 성능 (SE Value) 보다 낮을 수 있으며, 이는 리더의 성능을 예측 불가능하게 만듭니다.

B. 정책 개선 정리 (Policy Improvement Theorem)

단일 에이전트 MDP 의 정책 개선 정리를 SSG 환경으로 확장하여 유도했습니다.
주요 내용: 현재 정책 $f'$ $f^{'}$ 에 대해, 새로운 정책 $f$ $f$ 가 특정 조건 (Q-함수 기반) 을 만족하면, 팔로워의 최적 대응 하에서 리더의 가치 함수가 단조롭게 증가하거나 적어도 감소하지 않음을 보장합니다.
- $Q^{f'\dagger}_A(\cdot, f) \succeq V^{f'\dagger}_A \implies V^{f\dagger}_A \succeq V^{f'\dagger}_A$
- 여기서 $\dagger$ 는 팔로워의 최적 대응을 의미합니다.

C. 파레토 최적성 (Pareto Optimality) 의 도입

모든 상태 (State) 에서 동시에 최대화되는 단일 최적 정책 (SSE) 이 존재하지 않을 수 있으므로, **파레토 프론트 (Pareto Front)**에 도달하는 것을 목표로 합니다.
파레토 최적 정책: 다른 어떤 정책도 모든 상태에서 더 나은 가치를 가지지 않는 정책 집합입니다.
수렴 보장: 제안된 알고리즘은 리더의 할인율 ( $\gamma_A$ ) 이 0 인 경우 (단기적 리더, Myopic Leader), 파레토 프론트로 단조 수렴함을 이론적으로 증명했습니다. $\gamma_A > 0$ 인 경우에도 파레토 프론트의 경계 (Boundary) 로 수렴함이 보장됩니다.

D. 알고리즘 절차 (Algorithm 1 & 2)

초기화: 임의의 리더 정책 $f_0$ 를 선택합니다.
가치 함수 계산: 현재 정책 $f_t$ 와 팔로워의 최적 대응 $R^*_B(f_t)$ 하에서 리더의 가치 함수 $V^{f_t\dagger}_A$ 를 계산합니다.
개선 가능 정책 집합 탐색: 정책 개선 정리에 따라 $Q^{f_t\dagger}_A(\cdot, f) \succeq V^{f_t\dagger}_A$ 를 만족하는 정책들의 집합 $W_{\succeq}(f_t)$ 를 찾습니다.
다음 정책 선택: 이 집합 내에서 스칼라화 함수 (Scalarization, 예: 가중치 합) 를 최대화하는 정책을 선택하여 $f_{t+1}$ 로 업데이트합니다.
반복: 더 이상 개선이 불가능할 때까지 반복합니다.
- 실용적 개선 (Appendix G): 정책 공간이 너무 클 경우, 최적 대응이 동일한 부분 공간으로 분할하여 효율적으로 탐색하는 전략도 제안했습니다.

3. 주요 기여 (Contributions)

기존 DP 연산자의 고정점 분석: Bucarey et al. (2022) 등의 방법에서 사용하는 연산자의 고정점이 반드시 합리적인 리더 정책을 보장하지 않음을 명시적으로 증명했습니다.
정책 개선 정리 유도: 일반합 SSG 와 최적 대응 팔로워 환경에 대한 새로운 정책 개선 정리를 유도했습니다.
새로운 알고리즘 제안: 단조 개선을 보장하는 파레토 최적 정책 반복 알고리즘을 제안했습니다.
수렴성 증명:
- 리더가 단기적 (Myopic, $\gamma_A=0$ ) 일 때, 제안된 방법이 파레토 프론트로 수렴함을 최초로 이론적으로 증명했습니다.
- SSE 가 존재하지 않는 경우에도 합리적인 성능을 보장하는 알고리즘을 제시했습니다.

4. 결과 및 의의

이론적 guarantee: 기존 방법론들이 SSE 가 존재하지 않을 때나 수렴하지 않을 때의 성능 보장이 없었던 반면, 본 논문은 리더의 성능이 단조롭게 개선됨을 보장합니다.
실용성: 전자상거래 플랫폼 설계 (사이트 소유자가 사용자의 최적 반응을 예측하여 이익 극대화) 와 같은 실제 시나리오에 적용 가능합니다. 사용자는 자신의 선호도에 따라 최적의 구매 결정을 내린다고 가정할 때, 소유자는 이를 통해 장기적 이익을 극대화할 수 있습니다.
한계 및 향후 과제:
- $\gamma_A > 0$ 인 경우 파레토 최적성 (Pareto-optimality) 이 항상 보장되지는 않습니다.
- 정책 공간이 매우 클 때 다음 정책을 선택하는 계산 효율성 (Equation 8 의 최적화 문제) 이 여전히 과제입니다.
- 팔로워의 최적 대응과 전이 확률을 알고 있어야 하므로, 완전한 강화학습 (Model-free) 환경으로의 확장이 필요합니다.

요약

이 논문은 일반합 확률적 스택버그 게임에서 SSE 가 존재하지 않거나 기존 알고리즘이 저품질로 수렴할 수 있는 문제를 해결하기 위해, 파레토 최적성을 새로운 목표로 설정하고 단조 개선을 보장하는 정책 반복 알고리즘을 개발했습니다. 특히 리더가 단기적일 때 파레토 프론트로의 수렴을 이론적으로 증명함으로써, 다중 에이전트 강화학습 및 게임 이론 분야에서 중요한 이론적 진전을 이루었습니다.