Markov 팀 게임·정책 가치·공동 최적과 최적 반응

같은 목적이어도 조정은 필요하다

두 유지보수 에이전트가 같은 시스템 점수를 받는다고 생각해 봅시다. 정상 상태에서는 생산하고 손상 상태에서는 수리할 수 있습니다. 보수가 같아도 서로 맞는 행동을 선택하기는 어려울 수 있습니다. 각자 혼자 바꿀 이유가 없는 정책이 항상 두 사람의 공동 최적인 것은 아닙니다.

이 단원은 유한 상태의 Markov 게임을 무한 할인 기간에서 다룹니다. 유한이라는 말은 두 상태와 각자의 두 행동을 뜻하며, 에피소드를 잘라 합한다는 뜻이 아닙니다. 두 플레이어는 현재 상태를 모두 관측하고 동시에 행동합니다. 보수는 공통이고 다음 상태는 현재 상태와 두 행동에 의존합니다.

앞 단원의 이전 가능한 연합 게임과도 구분합니다. 여기서는 두 사람에게 이미 같은 점수 함수가 주어져 있고, 동역학을 바꾸는 정책을 고릅니다. 연합의 총가치나 지급 배분을 추정하지 않습니다. 아래 가치는 각자가 받는 공통 점수의 가치이며, 같은 점수 두 개를 더한 총합이 아닙니다.

상태·공동 행동·전이를 분리한다

상태 s는 0 또는 1이고 각자의 행동을 a,b라 합시다. r(s,a,b)는 즉시 보수입니다. P(s'|s,a,b)는 다음 상태의 확률분포입니다. 이것은 행동을 선택할 확률과 다른 양입니다.

MIT Markov 게임 강의 §S6.1–S6.2는 상태 전이·보수·이력 의존 정책·정상 Markov 정책을 구분합니다. 실습에서는 현재 상태만 사용하는 정상 정책을 둡니다. 상태 s에서 P1은 행동 0을 확률 p_s로, P2는 q_s로 선택합니다. 서로 독립적으로 섞으므로 00,01,10,11 순서의 공동 확률은 다음과 같습니다.

$$(p_sq_s,\ p_s(1-q_s),\ (1-p_s)q_s,\ (1-p_s)(1-q_s)).$$

입력은 각 상태의 확률을 따로 지정합니다. 정책은 상태에서 행동분포로 가는 함수이지, 상태와 무관하게 행동 하나를 계속 재사용하는 지시가 아닙니다.

정책으로 모형을 평균한다

두 정책을 고정하고 공동 행동에 대해 평균하면 다음을 얻습니다.

$$r_\pi(s)=\sum_{a,b}p_s(a)q_s(b)r(s,a,b), \qquad P_\pi(s,s')=\sum_{a,b}p_s(a)q_s(b)P(s'|s,a,b).$$

이제 상태열은 Markov chain입니다. 첫 그림의 위 화살표는 이 평균 전이를 보여 줍니다. 아래 행동 표는 조회한 상태에서 행동별 조건부 모형과 현재 혼합 확률을 구분합니다. 서로 다른 확률을 하나로 뭉쳐 읽으면 안 됩니다.

예를 들어 수리 모형에서 네 공동 행동의 확률이 각각 1/4이면 즉시 보수 평균은 (9/4,1/4)입니다. 다음 상태 1 확률의 평균은 (9/32,5/8)입니다. 상태 0의 행동 00 자체가 갖는 다음 상태 1 확률은 여전히 1/2이며 평균 9/32와 다릅니다.

무한 할인 가치는 기대값이다

0≤gamma<1에서 시작 상태별 공통 가치를 다음처럼 정의합니다.

$$V^\pi(s)=\mathbb E_\pi\!\left[\sum_{t=0}^{\infty}\gamma^t r(s_t,a_t,b_t)\mid s_0=s\right].$$

행동 혼합과 상태 전이의 무작위성을 모두 평균한 값입니다. 한 번 실행한 표본 경로나 즉시 보수와 다릅니다. 여기서는 정규화하지 않은 할인 합을 쓰며 1−gamma를 곱하지 않습니다.

첫 전이에 조건을 걸어 정리하면 Bellman 방정식이 나옵니다.

$$V^\pi=r_\pi+\gamma P_\pi V^\pi, \qquad (I-\gamma P_\pi)V^\pi=r_\pi.$$

MIT의 Bellman 설명은 정책 평가와 할인 최적성을 다룹니다. P_pi가 확률행렬이므로 V를 r_pi+gamma P_pi V로 보내는 함수는 gamma<1에서 최댓값 노름 수축입니다. 유일한 고정점은 수렴하는 행렬급수로도 표현할 수 있습니다. 보수 절댓값이 M 이하이면 가치 절댓값은 M/(1−gamma) 이하입니다.

할인 0은 첫 보수만 남깁니다. 할인 1은 이 무한 기간 실습에서 제외합니다. 유한 에피소드라면 1을 허용할 수 있지만, 양의 보수를 계속 받는 무한 합은 일반적으로 발산합니다. 입력은 0.95까지로 제한해 유한한 모형과 읽을 수 있는 축척을 유지합니다.

한 번 강제한 행동의 Q는 정책 전체의 가치가 아니다

공동 행동을 한 번 강제하고 이후에는 현재 정책을 따르는 가치는 다음과 같습니다.

$$Q^\pi(s,a,b)=r(s,a,b)+\gamma\sum_{s'}P(s'|s,a,b)V^\pi(s').$$

이것은 앞으로의 정책을 전부 바꾸는 가치가 아닙니다. 현재 확률이 0인 행동이라도 보수와 전이가 모형에 지정되어 있으므로 Q를 계산할 수 있습니다. 한 정책에서 방문하지 않는다는 것과 그 행동의 모형이 정의되지 않았다는 것은 다릅니다.

실제 학습 시스템에서 모형을 모른다면 방문하지 않은 행동의 Q를 추정하려면 추가 관측이나 가정이 필요합니다. 실습은 알려진 작은 완전 모형을 제공할 뿐, 관측 데이터만으로 모든 반사실이 식별된다고 주장하지 않습니다.

상대를 고정한 최적 반응은 하나의 MDP다

상대의 정상 정책을 고정하면 그 상대 행동을 평균한 MDP가 생깁니다. 이탈을 고려하는 플레이어는 두 상태의 행동을 모두 바꿀 수 있고, 그에 따라 이후의 상태 방문도 달라집니다.

유한·할인·완전 관측 MDP에는 결정론적 정상 최적 정책이 존재합니다. 두 상태에서 각자 두 행동이므로 자신의 그런 정책은 네 개입니다. 실습은 네 정책을 모두 평가하고 두 상태에서 성분별 최적인 가치를 찾으며 모든 정확한 동률을 보존합니다. 작은 열거를 정당화하는 것은 할인 MDP의 최적성 정리이지, 임의의 모든 이력 의존 전략을 실제로 나열했다는 주장이 아닙니다.

플레이어 i의 최적 반응 가치를 V_BR_i라 하면 이득은 시작 상태별 V_BR_i−V_pi입니다. 화면의 전체 상태 정상 Nash 표시는 두 플레이어의 두 상태 이득이 모두 정확히 0일 때만 켜집니다. 한 상태를 방문하지 않는 초기분포에서만 조건을 검사하는 것보다 강한 조건입니다. Markov·완전 관측·정상 상대라는 가정에서는 최적 MDP 반응이 이력 의존 이탈의 가치도 제한합니다.

공동 최적의 기준선도 별도 MDP다

중앙 조정자가 공동 행동을 고르면 각 상태에 네 선택지가 있습니다. 결정론적 정상 공동 정책은 열여섯 개입니다. 같은 할인 MDP 논리에서 두 상태 모두에 최적인 정책이 존재합니다. 유용한 수리를 어느 플레이어가 담당해도 같은 경우처럼 모든 정확한 동률을 남깁니다.

공동 최적 V_team과 간극 V_team−V_pi는 공통 점수의 단위를 사용합니다. 공동 최적이면 일방 개선도 없습니다. 한 사람이 바꾼 정책도 가능한 공동 정책에 포함되기 때문입니다. 하지만 반대는 성립하지 않을 수 있습니다. 둘이 함께 바꿔야 좋아지는 조정 문제가 있기 때문입니다.

실습은 입력된 정책을 평가하고 기준선과 비교합니다. 표본에서 정책을 학습하거나 독립적인 강화학습자들이 수렴한다고 증명하는 알고리즘이 아닙니다.

손계산: Nash이지만 공동 최적이 아닌 조정 함정

상태 보존 모형에서는 어떤 행동을 해도 시작 상태가 유지됩니다. 공통 보수 행렬은 다음과 같습니다.

$$R_0=\begin{pmatrix}4&0\\0&3\end{pmatrix}, \qquad R_1=\begin{pmatrix}2&0\\0&1\end{pmatrix}.$$

두 사람이 항상 행동 1을 쓰고 gamma=0.8이라 합시다. 가치는 상태 0에서 3/(1−0.8)=15, 상태 1에서 1/(1−0.8)=5입니다. 한 사람만 행동 0으로 바꾸면 즉시 보수가 0이 되어 손해이므로 두 최적 반응 이득은 모두 0입니다.

반면 둘이 두 상태에서 함께 00을 쓰면 가치는 20과 10입니다. 현재 정책은 전체 상태 Nash이지만 팀 간극은 두 상태 모두 5입니다. 같은 보수를 받는다고 조정 문제가 사라지지 않습니다.

상태 0에서 00을 한 번만 강제하면 Q=4+0.8·15=16입니다. 현재 가치 15와도 다르고, 정책을 영원히 바꾼 가치 20과도 다릅니다. 이것은 일방 이탈이 아니라 공동의 일시적 변경이므로 이득이 있어도 Nash 판단과 모순되지 않습니다.

손계산: 지금 비용을 내고 미래 기회를 복구한다

두 번째 모형의 상태 0은 정상, 상태 1은 손상입니다. 행동 1은 비용이 드는 유지보수·수리 행동입니다. 공동 행동 00,01,10,11 순서의 보수는 다음과 같습니다.

$$r_0=(4,2,2,1),\qquad r_1=(0,1,1,-1).$$

다음 상태 1의 확률은 다음과 같습니다.

$$P(1\mid0,\cdot)=(1/2,1/4,1/4,1/8), \qquad P(1\mid1,\cdot)=(1,3/4,3/4,0).$$

이는 설명을 위해 만든 매개변수이며 실제 장치의 고장률을 추정한 값이 아닙니다. 손상 상태의 공동 수리는 지금 −1을 받지만 다음 정상 상태를 확률 1로 만듭니다. 한 사람의 수리는 지금 1을 받지만 복구 확률은 1/4입니다.

정상에서는 00, 손상에서는 11을 쓰고 gamma=0.8이라 합시다. Bellman 식은 다음과 같습니다.

$$V_0=4+0.8(\tfrac12V_0+\tfrac12V_1), \qquad V_1=-1+0.8V_0.$$

해는 V0=90/7, V1=65/7입니다. 정책 전수 비교에서도 공동 최적임을 확인합니다. 손상 상태에서 수리를 한 사람만 한 번 시키고 현재 정책을 다시 따르면 Q=64/7로 65/7보다 조금 낮습니다. 즉시 보수 1과 −1만 비교하면 이 연속 가치에서 잘못된 공동 행동을 고르게 됩니다.

할인율을 바꾸면 최적 결정도 달라진다

정책은 그대로 두고 gamma를 0.2로 바꾸면 가치는 (195/44,−5/44)입니다. 공동 최적 가치는 (175/38,55/38)이며 정상에서 00을 쓰고 손상에서 한 사람만 수리하는 두 정책이 동률입니다.

각 플레이어의 최적 반응 이득은 (145/836,1305/836)이므로 기존 공동 수리 정책은 이제 Nash도 팀 최적도 아닙니다. 미래 정상 운용의 가중치가 작아져 현재 비용을 낼 유인이 달라졌습니다.

곡선은 입력된 두 정책을 고정하고 할인만 바꿉니다. 매 할인에서 최적 정책을 다시 골라 그린 포락선이 아닙니다. 정확한 정책 표는 현재 할인에 관한 것이며 gamma를 바꾸면 최적인 행도 달라질 수 있습니다.

정확한 비교와 검산의 역할

입력은 제한된 정수 백분율이고 모형의 전이는 유리수인 1/8 단위입니다. 구현은 두 상태 Bellman 해, 후보 비교, 간극, Q를 유리수 분자·분모로 계산합니다. 그 산술에서 Bellman 잔차는 정확히 0입니다. 그림과 숫자 표시에만 소수를 사용합니다.

상태 가치의 합이 가장 큰 후보를 찾은 뒤, 그 후보가 각 상태에서 모든 후보를 성분별로 지배하는지도 정확히 확인합니다. 할인 MDP에 전체 상태 최적이 존재한다는 성질을 이용한 것입니다. 동률은 반올림 임계값이나 조회한 한 상태만으로 정하지 않고 전체 정확한 가치 벡터로 판정합니다.

검사에서는 별도로 V0−V1에 대한 식으로 가치를 계산하고 Bellman 최적성 식도 확인합니다. 긴 할인 전개 합과 기하급수 꼬리 상한으로 평가 값을 대조합니다. 이 검사는 구현된 평가·기준선의 근거이며, 실행하지도 않은 학습 알고리즘의 수렴 증거가 아닙니다.

연구 연결과 범위

부분 관측이면 정책이 실제 상태에 직접 의존할 수 있는지가 달라집니다. 상관된 공동 행동은 여기 입력한 독립 혼합과 다릅니다. 전이와 보수를 모르면 탐색과 식별 문제가 생깁니다. 일반합 게임은 각자 다른 목적을 가지므로 하나의 공통 점수 최대화를 넘어선 균형 분석이 필요합니다.

작은 정확한 모형은 구현을 확인하고 조정 함정을 구성하며 즉시 보수와 연속 유인을 구분하는 데 유용합니다. 하지만 그것만으로 다중 에이전트 학습이 Nash에 도달하거나 팀 최적을 찾거나 더 큰 물리 시스템에 전이된다고 결론 내릴 수 없습니다.

확인 문제와 해설

문제 1. 조정 함정의 상태 0에서 현재 가치, 한 번 강제한 Q00, 공동 최적 가치를 계산하고 차이를 설명하세요.

해설. 15는 11을 계속 따르는 가치, 16은 00을 한 번 강제하고 11로 돌아오는 가치, 20은 00을 계속 따르는 가치입니다. 첫 변화는 공동의 일시적 변경이고 팀 기준선은 두 사람의 미래 정책을 바꿉니다.

문제 2. gamma 0에서 V와 Q는 무엇이 되나요? 동적 수리 모형의 최적 공동 정책은 반드시 유일한가요?

해설. V는 정책으로 평균한 즉시 보수, Q는 행동별 조건부 즉시 보수입니다. 손상 상태의 01과 10이 모두 보수 1이므로 정상에서 00을 쓰는 두 공동 정책이 동률입니다.

문제 3. 네 일방 정책과 열여섯 공동 정책으로 충분한 이유와 숨은 상태에서 달라지는 점을 설명하세요.

해설. 유한 할인 완전 관측 MDP의 결정론적 정상 최적 정책 존재가 고정 상대와 중앙 조정자 각각의 열거를 정당화합니다. 상태가 숨으면 믿음이나 이력을 사용하는 정보 구조가 필요할 수 있으므로 현재의 상태별 정책 열거만으로 모든 문제를 다룰 수 없습니다.