무후회 학습

최적설계 통계 게임 개발 마지막 수정: 2026-08-24 04:37:08

1. 개요[편집]

무후회 학습 No-Regret Learning
정의	외부 후회 $R_T$ 가 $o(T)$인 알고리즘
대표	헤지/MWU, 후회 매칭, FTRL, 온라인 미러 하강
전문가 문제 최적률	$\Theta(\sqrt{T\log N})$
후회 계층	강도 순으로 외부 < 내부·스와프 ($R_T \le R^{\mathrm{swap}}_T \le N R^{\mathrm{int}}_T$)
수렴처	외부 → 조대 상관균형, 스와프 → 상관균형, 2인 영합 → 내시
대표 응용	CFR — 헤즈업 홀덤 포커 해결

“돌이켜 보니 그냥 한 가지만 계속 밀 걸 그랬다”는 아쉬움이 시간이 갈수록 0으로 수렴하는 학습. 이기는 것이 아니라, 나중에 후회할 거리를 안 만드는 것이 목표다.

무후회 학습(no-regret learning)은 매 라운드 결정을 먼저 내고 손실을 나중에 보는 반복 상황에서, 사후에 가장 좋았을 고정 행동 대비 누적 손실 초과분이 라운드 수보다 느리게 자라는(부분선형) 알고리즘들의 총칭이다. 행동 집합 $\mathcal A$ ( $|\mathcal A| = N$ )에서 매 라운드 $a_t$ 를 뽑고 손실벡터 $\ell_t$ 를 받을 때, 외부 후회는

R_T \;=\; \sum_{t=1}^{T}\ell_t(a_t) \;-\; \min_{a \in \mathcal A}\sum_{t=1}^{T}\ell_t(a)

이고, $R_T = o(T)$ 즉 $R_T/T \to 0$ 이면 무후회라 부른다.¹

이 문서는 후회라는 개념의 계층 구조와, 무후회 학습자들을 서로 붙여 놓았을 때 게임이 어디로 가는가를 다룬다. 후회 척도의 정의와 부분선형성이 왜 가능한지, FTRL·온라인 미러 하강이 어떻게 통일되는지는 온라인 볼록 최적화에, 지수 가중 갱신 자체의 증명·변형·적응형 스텝은 헤지 알고리즘에 이미 있으므로 여기서 반복하지 않는다. 여기서 새로 나오는 것은 후회를 강화하면 균형 개념이 강화된다는 대응, 그리고 시간평균은 수렴하는데 궤적은 안 하는 구조적 함정이다.

2. 무엇이 무후회인가 — 최소한의 목록[편집]

부분선형 후회를 내는 알고리즘은 이미 잘 정리돼 있다. 뼈대만 짚으면 이렇다.

헤지 / 곱셈 가중치(MWU). $p_{t+1,i} \propto p_{t,i}e^{-\eta\ell_{t,i}}$ . $\eta = \sqrt{8\ln N/T}$ 에서 $R_T \le \sqrt{\tfrac12 T\ln N}$ .
하한. 손실을 독립 동전던지기로 주면 어떤 알고리즘도 $R_T \gtrsim \sqrt{(T/2)\ln N}$ 를 피할 수 없다. 즉 헤지는 상수까지 최적이고, 이 분야에서 “더 나은 알고리즘”은 최악경우 차수가 아니라 문제가 쉬울 때의 적응성에서 나온다.
FTRL / 온라인 미러 하강. 누적 손실에 강볼록 정규화항을 얹어 안정성을 사는 틀. 정규화항을 $\tfrac12\|x\|_2^2$ 로 두면 온라인 경사하강, 음의 엔트로피로 두면 헤지가 나온다. 선형 손실에서 게으른 OMD와 FTRL은 같은 알고리즘이다.
적응적 스텝. $T$ 를 모를 때의 표준 처방이 두 배 트릭(구간을 $1,2,4,8,\dots$ 로 쪼개 재시작)과 시간가변 $\eta_t \propto 1/\sqrt t$ 이며, 문제가 쉬우면 후회가 상수로 떨어지고 어려우면 최악경우 상한으로 부드럽게 복귀하는 AdaHedge 계열이 그다음이다. 셋 다 헤지 알고리즘 문서에서 다룬다.
후회 매칭(Hart & Mas-Colell 2000). 누적 후회 $R_t(i)$ 의 양수부에 비례해 확률을 준다.

p_{t+1}(i) \;=\; \frac{[R_t(i)]_+}{\sum_j [R_t(j)]_+}

(분모가 0이면 균등분포.) 학습률이 없다는 것이 실전에서 결정적이다. 튜닝할 게 없고 손실 스케일 정규화도 필요 없어서, 뒤에 나올 CFR이 헤지 대신 이쪽을 쓴다.

밴딧 설정. 고른 행동의 손실만 보인다면 중요도 가중 추정 $\hat\ell_{t,i} = \ell_{t,i}\mathbf 1\{i=I_t\}/p_{t,i}$ 를 헤지에 먹이는 EXP3가 $\mathbb E[R_T] = O(\sqrt{TN\log N})$ 을 낸다. $\log N$ 이 $\sqrt N$ 으로 악화되는 것이 정보 부족의 가격이며, 하한 $\Omega(\sqrt{TN})$ 과 로그 인자만큼 떨어져 있다. 자세한 것은 다중 슬롯머신 문서.

3. 후회의 계층 — 외부·내부·스와프[편집]

여기서부터가 이 문서의 본론이다. 위의 외부 후회는 “한 가지 행동으로 통째로 바꿨더라면”만 비교한다. 비교 대상을 넓히면 더 강한 개념이 나온다.

내부 후회(internal regret)는 행동 쌍 $(i,j)$ 마다, 내가 $i$ 를 냈던 라운드들에서만 $j$ 로 바꿨을 때의 이득을 잰다.

R^{\mathrm{int}}_T \;=\; \max_{i \ne j}\ \sum_{t=1}^{T} p_{t,i}\bigl(\ell_{t,i} - \ell_{t,j}\bigr)

스와프 후회(swap regret)는 임의의 사상 $\phi: \mathcal A \to \mathcal A$ 로 모든 행동을 동시에 갈아치우는 것까지 허용한다.

R^{\mathrm{swap}}_T \;=\; \max_{\phi}\ \sum_{t=1}^{T}\sum_{i} p_{t,i}\bigl(\ell_{t,i} - \ell_{t,\phi(i)}\bigr)

관계는 다음과 같다. $\phi$ 를 상수 사상으로 두면 외부 후회가 나오므로 $R_T \le R^{\mathrm{swap}}_T$ 이고, 스와프는 최대 $N$ 개의 내부 교체를 합친 것이므로 $R^{\mathrm{swap}}_T \le N\,R^{\mathrm{int}}_T$ 이다. 즉 무내부후회 ⟹ 무스와프후회 ⟹ 무외부후회이고 역은 성립하지 않는다.

역이 왜 안 되는지가 직관적으로 중요하다. 절반의 라운드에서는 $A$ 가 좋고 절반에서는 $B$ 가 좋은데 내가 매번 반반 섞었다면, 어떤 고정 행동도 나보다 낫지 않으므로 외부 후회는 0이다. 그런데 “ $A$ 를 낼 때만 $B$ 로 바꿔라” 같은 조건부 조언은 여전히 나를 개선한다. 외부 후회는 조언을 받아들일 여지가 남아 있는데도 0이 될 수 있다 — 이 간극이 다음 절에서 그대로 균형 개념의 간극이 된다.²

무스와프후회 알고리즘은 공짜로 얻어지지 않지만, 블럼-맨수어 환원(2007)이 블랙박스 처방을 준다. 행동마다 무외부후회 알고리즘 $\mathcal A_i$ 를 하나씩 두고, 각자가 내놓은 분포 $q^{(i)}_t$ 를 행으로 쌓아 만든 행렬의 정상분포를 $p_t$ 로 쓴다. 그리고 $\mathcal A_i$ 에는 손실을 $p_{t,i}\ell_t$ 로 가중해 먹인다. 정상분포 조건 $p_t = \sum_i p_{t,i}q^{(i)}_t$ 이 “각 행동을 낸 몫이 그 행동 전용 학습기에 정확히 귀속되게” 만들어 주고, 그 결과 스와프 후회가 각 학습기의 외부 후회 합으로 묶여 $O(\sqrt{TN\log N})$ 이 나온다. 대가는 매 라운드 $N$ 개의 학습기와 $N \times N$ 정상분포 계산이다.

4. 그래서 게임은 어디로 가는가[편집]

플레이어들이 서로를 상대로 각자 무후회 알고리즘을 돌리면, 실제 플레이의 경험분포(joint empirical distribution)가 균형 집합으로 접근한다. 그리고 후회의 강도가 정확히 균형 개념의 강도로 번역된다.

각자가 최소화하는 후회	경험분포가 수렴하는 집합
외부 후회	조대 상관균형(CCE)
내부·스와프 후회	상관균형(CE)
외부 후회 (2인 영합, 주변분포)	내시 균형 = 미니맥스

논리는 한 줄이다. 후회의 정의식이 곧 균형의 정의식이다. 내시 균형 문서에 있는 상관균형 조건

\sum_{s_{-i}} p(a, s_{-i})\bigl[u_i(a,s_{-i}) - u_i(a', s_{-i})\bigr] \;\ge\; 0

을 경험분포로 쓰면 그대로 “내부 후회 $\le 0$ “이 된다. 조대 상관균형은 같은 조건을 조건부가 아니라 무조건부로 요구한 것 — 그게 외부 후회다. 그러니 후회가 $o(T)$ 면 위반량이 라운드당 0으로 가고, 극한점이 균형 집합 안에 들어간다. 하트와 마스콜렐(2000)이 후회 매칭 하나로 상관균형 수렴을 보인 것이 이 계열의 대표 결과이고, 포스터와 보라(1997)의 보정된 예측(calibrated forecasting)이 그 앞에 있다.

2인 영합 게임은 특별하다. 두 학습자의 시간평균 전략 $\bar p = \frac1T\sum p_t$ , $\bar q = \frac1T\sum q_t$ 에 대해

\max_q \bar p^\top A q - \min_p p^\top A \bar q \;\le\; \frac{R^{(1)}_T + R^{(2)}_T}{T}

가 성립한다. 즉 $(\bar p, \bar q)$ 는 $\varepsilon$ -내시이고 $\varepsilon = (R^{(1)}_T + R^{(2)}_T)/T \to 0$ 이다. 프룬드와 샤파이어의 이 논증은 폰 노이만 미니맥스 정리의 구성적 증명이기도 하다 — 두 무후회 학습기를 서로 돌리는 것만으로 쌍대성이 증명된다. 필요한 라운드 수는 $O(\log N/\varepsilon^2)$ .

일반합·다인 게임에서는 내시로 간다는 보장이 없다. 무후회 학습이 데려다주는 곳은 (조대) 상관균형까지다. 이는 알고리즘의 게으름이 아니라 원리적 장벽에 가깝다 — 하트와 마스콜렐(2003)은 각 플레이어가 자기 보수함수만 아는 비연동(uncoupled) 동역학은 일반 게임에서 내시 균형으로 수렴할 수 없음을 보였다. 자기대전 학습이 “왜 균형에 안 붙느냐”를 튜닝으로 해결하려 들기 전에 이 결과를 먼저 봐야 한다.

5. 평균은 가는데 궤적은 안 간다[편집]

시뮬레이션 하는 사람에게 가장 비싼 함정. 위 정리들이 보장하는 것은 전부 시간평균이지 마지막 반복이 아니다.

가위바위보에서 두 플레이어에게 MWU를 돌려 보면 현재 전략쌍은 균형 $(1/3,1/3,1/3)$ 주위를 영원히 돌고, 오히려 진폭이 커지며 단체 경계로 밀려나기까지 한다. 연속시간에서 MWU의 극한은 복제자 동역학이고, 영합 게임의 복제자 동역학은 보존량을 갖는 사실상 해밀토니안 계라 푸앵카레 재귀가 성립한다 — 궤적은 수렴하지 않고 초기값 근방으로 무한히 되돌아온다. 이산화하면 그 보존량이 단조 증가해 나선이 밖으로 벌어진다. “학습이 발산한다”고 보이는 현상이 사실은 계의 구조인 것이다.

실무적 귀결이 몇 개 있다.

평균 전략을 반드시 따로 저장해라. 마지막 반복점을 답으로 쓰면 틀린다. CFR 구현이 현재 전략과 별개로 누적 평균 전략을 유지하는 이유가 이것이다.
수렴 판정은 착취가능도(exploitability)로. $\max_q \bar p^\top A q$ 와 $\min_p p^\top A\bar q$ 의 차, 즉 “최선반응 상대에게 얼마나 털리는가”가 진짜 $\varepsilon$ 이다. 손실 곡선이 흔들리는지 여부는 아무 정보가 아니다.
마지막 반복 수렴이 필요하면 낙관적 변형을 쓴다. 직전 손실을 한 번 더 반영하는 낙관적(optimistic) MWU/FTRL은 상대의 갱신을 예측해 진동을 상쇄하고, 영합 게임에서 마지막 반복 수렴과 $O(1/T)$ 수렴률을 낸다. 일반 게임에서도 모두가 낙관적 알고리즘을 쓰면 개별 후회가 폴리로그까지 떨어진다는 결과가 있다. 적대자를 상정한 $\sqrt T$ 하한이 “모두가 협조적으로 같은 알고리즘을 쓰는” 상황에서는 적용되지 않는다는 것이 이 계열의 요점이다.
GAN·자기대전 강화 학습의 진동도 같은 뿌리다. 안장점 문제에 경사하강법의 직관을 그대로 가져오면 안 된다는 것을, 가위바위보 3×3 행렬 하나로 재현해 볼 수 있다.

6. CFR — 왜 포커에서 먹혔나[편집]

반사실적 후회 최소화(Counterfactual Regret Minimization, Zinkevich 등 2007)는 무후회 학습을 전개형 불완전정보 게임으로 끌어올린 것이다. 핵심 아이디어 하나로 요약된다.

게임 전체의 후회를 정보집합 하나하나의 반사실적 후회의 합으로 상계할 수 있다. 따라서 각 정보집합에서 독립적으로 후회 최소화를 돌리면, 전체 후회가 자동으로 부분선형이 된다.

반사실적 값 $v_i(\sigma, I)$ 는 “플레이어 $i$ 가 정보집합 $I$ 에 도달하려고 애썼다면”이라는 가정 아래 상대와 우연의 도달확률로만 가중한 기대보수다. 자기 자신의 도달확률을 빼는 이 정의 덕분에 각 정보집합의 후회가 다른 정보집합의 전략과 무관하게 정의되고, 국소 후회의 합이 전체 후회를 지배한다. 정리 형태로는

R^T_i \;\le\; \sum_{I \in \mathcal I_i} \max\bigl(0,\ R^T_{i}(I)\bigr)

이고, 각 $I$ 에서 후회 매칭을 쓰면 $R^T_i \le |\mathcal I_i|\,\Delta\sqrt{|A|}\sqrt{T}$ 가 나온다. 그리고 2인 영합이므로 앞 절의 정리에 의해 평균 전략이 내시 균형으로 수렴한다.

포커에서 이게 먹힌 이유는 네 가지가 겹쳤기 때문이다.

분해가 가능했다. 헤즈업 리밋 홀덤은 결정 상태가 $10^{17}$ 규모, 정보집합이 $10^{14}$ 규모다. 선형계획법으로 균형을 푸는 고전적 경로(수열형 LP)는 제약 수가 트리 크기에 비례하므로 메모리부터 불가능하다. CFR은 전역 LP 대신 정보집합당 후회 벡터 하나만 들고 다니면 된다 — 저장량이 트리 크기가 아니라 정보집합 수에 비례한다.
후회 매칭에 튜닝이 없다. 수억 개 정보집합마다 학습률을 맞출 수는 없다. 스케일 불변이고 파라미터가 없다는 성질이 여기서 결정적이었다.
표본화가 붙었다. 매 반복 전체 트리를 순회하는 대신 우연 노드나 상대 행동을 표집하는 몬테카를로 CFR(MCCFR)이 반복당 비용을 수십~수백 배 줄였다. 몬테카를로 트리 탐색과 사촌 관계지만, MCTS가 최선반응을 찾는 반면 CFR은 균형을 찾는다는 목표 차이가 있다.
CFR+가 상수를 갈아 냈다. 누적 후회의 음수부를 매번 0으로 잘라 내고(regret matching $^+$ ) 평균 전략을 선형 가중하는 변형이 수렴 상수를 크게 줄였다. 이걸로 볼링 등(2015)이 헤즈업 리밋 홀덤을 사실상 해결했다고 발표했다.

그 뒤 딥스택과 리브라투스(2017)가 노리밋 헤즈업에서 프로를 이겼고, 플루리버스(2019)가 6인 게임까지 갔다. 다만 마지막 것은 이론적 보장이 없다 — 3인 이상 일반합 게임에서 무후회 학습이 가는 곳은 상관균형이지 내시가 아니고, 애초에 다인 포커의 내시 균형은 개념적으로도 실전 강함을 보장하지 않는다. “이론이 안 되는데 되더라”가 정직한 요약이다.³

7. 실무 감각[편집]

후회는 누적 척도다. 부분선형 후회는 “장기적으로 최선 고정 행동만큼 한다”일 뿐, 초반에 크게 잃고 나중에 만회해도 상한은 예쁘게 나온다. 손실이 실제 비용인 시스템(입찰, 제어)에서는 그 초반이 사고다.
비교 대상을 확인해라. 외부 후회의 벤치마크는 “고정 행동 하나”다. 환경이 변하면 그 벤치마크 자체가 나빠서, 따라잡아 봐야 소용이 없다. 이동 후회(shifting regret)나 동적 후회로 기준을 바꿔야 한다.
게임에 쓸 때는 어느 균형인지 명시해라. “무후회 학습으로 균형을 찾았다”는 문장은 2인 영합에서만 내시를 뜻한다. 그 밖에서는 조대 상관균형이며, 둘의 사회후생 차이는 클 수 있다.
후회를 실제로 계산해서 로그로 남겨라. 이론 상한이 아니라 실측 $R_T/T$ 가 떨어지는지를 봐야 구현 버그(부호 반전, 정규화 누락, 도달확률 오류)가 잡힌다. CFR 구현에서 가장 흔한 버그가 반사실적 도달확률에 자기 자신의 확률을 포함시키는 것이고, 그러면 후회는 여전히 줄어드는 것처럼 보이는데 균형으로는 안 간다.
손실 스케일을 맞춰라. 헤지 계열 상한의 모든 상수는 $\ell \in [0,1]$ 위에 서 있다. 후회 매칭이 실전에서 사랑받는 이유의 절반이 이 걱정을 없애 준다는 것이다.

8. 관련 문서[편집]

강의 노트나 요약 자료에서 후회를 $\max_a \sum_t(\ell_t(a) - \ell_t(a_t))$ 처럼 쓰는 경우가 있는데 부호가 뒤집힌 것이다. 손실 기준이면 “내 손실 빼기 최선 고정 행동의 손실”이고, 보수 기준이면 “최선 고정 행동의 보수 빼기 내 보수”다. 어느 쪽이든 후회는 클수록 나쁘다. 구현에서 이 부호를 뒤집어 놓고 “후회가 음수로 잘 내려간다”며 좋아하는 사례가 꾸준히 나온다. ↩
이름이 헷갈리기로 유명한 구역이다. internal regret과 conditional regret이 같은 말로 쓰이고, swap regret과 $\Phi$ -regret이 겹치며, 어떤 문헌은 스와프 후회를 그냥 내부 후회라 부른다. 논문을 읽을 때는 이름 대신 최댓값을 어느 집합 위에서 잡는지를 보면 된다 — 상수 사상이면 외부, 한 쌍의 교체면 내부, 임의의 사상이면 스와프다. ↩
플루리버스가 6인 게임에서 통한 이유로 저자들이 든 것은 “균형을 찾아서”가 아니라 “인간이 못 하는 균형 잡힌 혼합을 일관되게 실행해서”에 가깝다. 3인 이상 게임에서 각자 균형 전략을 들고 와 붙이면 균형이 아니라는 것은 초등적 사실인데, 그래도 인간보다는 낫더라는 결과였다. 이론 보장과 실전 성능이 서로 별개로 굴러간 드문 사례로 남았다. ↩