반복 게임·이력·Regret 비교 기준

반복은 합만 늘리는 것이 아니라 이력을 만든다

반복 게임은 단계 게임을 여러 날짜에 수행합니다. 라운드 t가 시작할 때는 0부터 t−1까지 관측한 행동을 사용할 수 있습니다. 전략은 한 실행에서 도달한 이력뿐 아니라 가능한 모든 이력에 대해 무엇을 할지 정하는 규칙입니다. 실제로 같은 행동열을 만든 두 규칙도 이탈 뒤의 반응은 다를 수 있습니다.

실습의 두 현재 행동은 동시에 결정합니다. P1 정책은 항상 0, 항상 1, 시계에 맞춘 교대, 상대 이전 행동 복사의 네 가지입니다. 상대는 항상 0, 교대, floor(horizon/2)에서 한 번 전환, P1 이전 행동 복사를 사용할 수 있습니다. 복사는 0에서 시작합니다. 어느 규칙도 현재 상대 행동을 먼저 보고 자신의 행동을 정하지 않습니다.

단계 보수 행렬은 앞서 사용한 세 게임입니다. 파란 ○는 P1, 주황 □는 P2의 실제 행동입니다. 굵은 상자는 조회 라운드, 점선 상자는 직전 이력입니다. 표시 접두 구간 이후의 라운드는 나타내지 않습니다.

단계 균형과 반복 게임 균형은 다르다

MIT 반복 게임 강의노트는 유한 반복, 이력 의존 전략, 할인한 무한 반복을 구분합니다. 알려진 유한 기간, 관측된 이력, 더하는 보수, 유일한 단계 Nash라는 조건에서는 역진 귀납으로 모든 부분게임이 그 단계 균형을 반복합니다. 마지막 라운드에는 이후 유인이 없고, 그 연속 가치가 고정되면 앞 라운드를 같은 방식으로 검토할 수 있습니다.

이 교재의 사회적 딜레마에서 두 행동 1은 유일한 단계 균형입니다. 이는 해당 가정의 부분게임 완전 유인에 대한 설명이며, 협력 이력 그림만 보고 얻는 결론은 아닙니다. 기간·정보·연속 보수 가정이 달라지면 결론도 바뀔 수 있습니다. 여기의 네 간단한 정책은 평가할 규칙이지 반복 게임 균형으로 인증한 정책이 아닙니다.

관측한 보수열 정의하기

실제 행동을 a_t,b_t라 하면 P1의 누적 실현 효용은 다음과 같습니다.

$$S_T=\sum_{t=0}^{T-1}u(a_t,b_t).$$

이 교육 모형에서는 보수 행렬과 관측한 상대 행동을 알기 때문에 두 고정 행동의 기록 재생 보수도 계산할 수 있습니다.

$$C_T(a)=\sum_{t=0}^{T-1}u(a,b_t),\qquad a\in\{0,1\}.$$

기록 재생은 보수 계산에서 자신의 행동을 바꾸더라도 실제 상대 행동 b_t를 고정합니다. 상대의 반응을 새로 생성하지 않습니다. 명시한 사후 비교 기준이지 처음부터 그 정책을 썼다면 실제로 벌어졌을 결과와 언제나 같은 것은 아닙니다.

Signed 외부 regret과 양의 부분

보수 관점에서 고정 행동과 비교하는 signed 외부 regret을 정의합니다.

$$R_T=\max_{a\in\{0,1\}}C_T(a)-S_T.$$

비교 대상은 접두 구간 전체에서 한 행동을 고정한 규칙이며 관측 뒤에 고릅니다. 주황 곡선은 접두 길이마다 최고 고정 행동 보수를 따로 계산하므로 그 행동의 정체는 바뀔 수 있습니다. 주황 포락선 자체가 실행한 온라인 정책은 아닙니다.

행동을 바꾸는 정책이 모든 고정 행동보다 잘할 수 있으므로 이 signed 차이는 음수가 될 수 있습니다. 양의 부분을 사용하는 표기도 구분합니다.

$$R_T^+=\max(0,R_T).$$

화면은 두 값을 모두 표시하고 T가 양수일 때만 R_T/T와 R_T^+/T를 계산합니다. 빈 실행에 평균 0을 표시하면 관측 증거가 있는 것처럼 보일 수 있어 사용 불가로 둡니다. 이후 no-regret 보장은 특정 알고리즘·비교 집합·상대 모형에서 기간이 커질 때의 정리입니다. 이 네 간단한 정책에 그런 보장을 붙이지 않습니다.

매 라운드 정답을 아는 더 강한 비교

매 라운드의 사후 oracle 보수는 다음과 같습니다.

$$D_T=\sum_{t=0}^{T-1}\max_a u(a,b_t).$$

그때의 상대 행동을 알고 매번 다른 행동을 고를 수 있습니다. 한 고정 행동보다 강한 비교 기준입니다.

$$D_T\ge\max_a C_T(a),\qquad D_T-S_T\ge R_T,\qquad D_T-S_T\ge0.$$

oracle을 실행 정책이라고 하거나 고정 비교를 조용히 대신하지 않습니다. 고정 행동 기준을 이기는 것과 매 라운드 정답을 예측하는 것은 다릅니다. 한 비교에 대한 regret 정리가 다른 비교에도 자동으로 성립하지는 않습니다.

손계산: 미리 보지 않아도 signed regret이 음수일 수 있다

상반 보수 게임에서 두 행동이 같으면 P1은 1, 다르면 −1을 받고 P2는 그 음수를 받습니다. 네 라운드 동안 두 플레이어가 시계에 맞춰 교대하면 행동열은 각각 (0,1,0,1)입니다. P1은 매번 1을 받아 S_4=4입니다. 그 상대 기록에 항상 0을 쓴 보수도 0, 항상 1을 쓴 보수도 0입니다.

따라서 R_4=0−4=−4, 양의 부분은 0, 동적 oracle regret도 0입니다. 현재 상대 행동을 먼저 본 것은 아닙니다. 두 결정론적 규칙이 알려진 라운드 시계에 우연히 맞는 예제입니다. 이것으로 교대 정책이 임의의 상대를 예측하거나 보편적인 no-regret 알고리즘이라고 결론 내릴 수는 없습니다.

반응형 상대에는 다른 반사실 비교가 필요하다

상대가 내 과거 행동에 의존하면 정책을 바꿀 때 이후 상대 행동도 달라집니다. 고정 정책 재실행은 그 고정 정책 아래의 상대 반응 전체를 다시 만듭니다. 그 보수를 S_T^(a)라 쓰면 비교는 다음과 같습니다.

$$R_T^{\rm rerun}=\max_a S_T^{(a)}-S_T.$$

기록 재생 C_T(a)와 다를 수 있습니다. Arora·Dekel·Tewari는 적응적 상대에 대한 일반 regret이 실제 이전 이력을 비교식에 남기는 반면, policy regret은 그 이력도 바꾸는 차이를 명시합니다. 논문은 bandit 환경을 다룹니다. 여기서는 비교 기준의 구분을 사용하며 그 알고리즘 보장을 이 완전 정보 시뮬레이션에 옮겨 붙이지 않습니다.

재실행이 가능한 것은 이 시뮬레이터의 반응 규칙과 초기 조건을 알기 때문입니다. 한 번 관측한 행동열만으로 모든 반사실 반응을 식별할 수는 없습니다. 화면은 서로 다른 비교 세계를 명시하고 기록 재생을 인과적인 정책 가치 추정인 것처럼 표시하지 않습니다.

손계산: 기록 재생과 반응 재생성

상반 보수에서 P1이 교대하고 P2가 P1의 이전 행동을 복사하게 합니다. 처음 네 행동 쌍은 (0,0),(1,0),(0,1),(1,0)입니다. P1 보수는 (1,−1,−1,−1)로 합이 −2입니다.

관측 상대 행동은 (0,0,1,0)입니다. 고정 0의 기록 재생은 2, 고정 1은 −2여서 외부 regret은 2−(−2)=4입니다. 실제로 항상 0을 쓰는 재실행에서는 상대 행동이 (0,0,0,0)이 되어 보수 4입니다. 항상 1이면 상대는 (0,1,1,1)이 되어 보수 2입니다. 최고 고정 정책 재실행의 regret은 4−(−2)=6입니다.

숫자 불일치가 아니라 개입한 비교 대상이 다릅니다. 내 행동에 반응하지 않는 외생적인 상대에서는 두 세계의 상대 행동열이 같아 고정 행동의 재생과 정책 재실행 보수도 같습니다.

유한 할인 평가는 별도 목적이다

표시한 T개 라운드의 유한 할인 보수는 다음과 같습니다.

$$V_T(\delta)=\sum_{t=0}^{T-1}\delta^t u_t,\qquad 0\le\delta\le1.$$

할인 0에서는 존재하는 첫 라운드의 가중치가 1, 이후는 0입니다. 할인 1에서는 유한 합이 일반 누적 보수와 같습니다. 어느 경우도 1−delta로 나눌 필요가 없습니다. 유한 할인 평균은 존재하는 가중치의 합으로 나누는데, 빈 구간에서는 두 합이 0이므로 평균을 정의하지 않습니다.

할인 조작을 바꿔도 그래프와 외부 regret은 할인하지 않습니다. 두 목적을 섞으면 비교 기준이 조용히 바뀝니다. 할인하지 않은 행동 보수·regret은 정수이고 유한 할인 합은 부동소수점으로 계산해 반올림 표시합니다.

손계산: 협력 접두 구간과 할인

사회적 딜레마에서 두 복사 규칙은 0에서 시작해 계속 0을 유지하여 매번 3을 받습니다. 계획한 8라운드 중 앞 3개만 표시하면 실제 누적 보수는 9입니다. 할인 0.8이면 다음과 같습니다.

$$V_3=3+0.8\cdot3+0.8^2\cdot3=7.32.$$

고정 1의 기록 재생은 실제 상대가 계속 0이었다는 기록에 대해 15를 받아 외부 regret이 6입니다. 그러나 항상 1을 쓰면 복사하는 상대도 바뀝니다. 세 라운드의 재실행 보수는 5,1,1로 합이 7입니다. 항상 0은 9여서 최고 고정 정책 재실행 regret은 0입니다.

조회 라운드 23을 요청해도 표시한 마지막 라운드 2로 제한합니다. 계획한 미래 라운드를 가져와 보여주지 않습니다. 접두 길이를 0으로 바꾸면 모든 라운드 셀과 선택 행동이 사라집니다. 누적 곡선의 시작점 (0,0)은 플레이한 라운드가 아니라 시작 잔액입니다.

무한 반복의 유인은 별도 가정이 필요하다

별도의 해석 예제로 완전 공적 관측, 공통 할인 delta∈[0,1), 무한 반복 사회적 딜레마의 grim-trigger를 생각해 봅시다. 한 번이라도 배신이 있기 전까지 협력하고 이후 둘 다 영원히 배신합니다. 우리 보수 R=3, 유혹 5, 처벌 1에서는 협력 가치가 3/(1−delta), 한 번 배신 뒤 처벌 가치는 5+delta/(1−delta)입니다.

$$\frac3{1-\delta}\ge5+\frac\delta{1-\delta} \quad\Longleftrightarrow\quad\delta\ge\frac12.$$

처벌 뒤 두 배신은 단계 균형이어서 처벌이 신뢰 가능합니다. 유한 행동, 유계 보수, 1 미만 할인과 위 관측 가정 아래에서 한 번의 이탈 논증으로 관련 이력을 검사할 수 있습니다. 경계에서는 무차별입니다. 할인 1에서는 유한한 무한기간 현재가치를 얻지 못합니다.

이 grim-trigger 해석은 유한 이력과 별개입니다. 이전 행동 복사는 grim-trigger가 아니고, 협력 몇 라운드를 봤다고 부분게임 완전성을 인증하지 않습니다. 할인 경계도 보수 행렬에 따라 달라지므로 다른 딜레마 예제의 수치를 그대로 쓰면 안 됩니다.

조작과 시간 범위 읽기

중간 전환 상대는 floor(계획 기간/2)에서 바뀝니다. 계획 기간을 바꾸면 환경 일정 자체가 달라져 이른 행동도 달라질 수 있으며 학습자가 미래를 관측했다는 뜻은 아닙니다. 다른 상대 규칙에서는 기간을 늘려도 이미 만든 접두 이력이 같습니다.

모든 합계·비교 재실행·곡선은 표시한 접두 구간만 사용합니다. 곡선의 가로축은 완료 라운드 수이고 이력 표는 0부터 시작하는 라운드 번호입니다. 조회 라운드나 할인만 바꿔서는 실제 행동열이 바뀌지 않습니다. 이런 구분으로 실험을 재현하고 미래 증거가 섞이는 것을 막습니다.

연습 문제와 해설

문제 1: 반응 상대 예제의 네 라운드를 계산하고 두 고정 재생 보수와 두 재실행 보수를 구하세요.

해설: 실제 쌍은 (0,0),(1,0),(0,1),(1,0)이고 효용은 −2입니다. 재생 보수 (2,−2), 재실행 보수 (4,2), 외부 regret 4, 재실행 정책 regret 6입니다. 복사 상대를 바꾸는 것은 학습자의 변경된 이력입니다.

문제 2: 양의 부분 외부 regret이 0이면 반복 게임 균형이거나 동적 oracle에 대해서도 최적인가요?

해설: 아닙니다. 이 접두 구간에서 실제 보수가 최고 고정 행동 재생 보수 이상이라는 뜻만입니다. 균형은 전략에 대한 유인 조건이 필요하고 매 라운드 oracle도 다른 비교입니다. 여기의 네 규칙에는 점근적인 보장을 붙이지 않습니다.

문제 3: 세 협력 라운드의 할인 0,0.8,1을 비교하고 빈 구간에서는 무엇이 달라지는지 설명하세요.

해설: 보수는 각각 3,7.32,9이고 가중치 합은 1,2.44,3입니다. 빈 접두 구간의 합계는 0이지만 조회 라운드·행동, 평균 regret, 할인 평균은 사용 불가입니다. 관측 0개를 학습 성공으로 표시해서는 안 됩니다.