No-regret 학습·Hedge·평균 전략 보장

완벽한 예측보다 정확한 비교 목표부터 정한다

매일 두 학습 파이프라인 중 하나를 평가 전에 선택한다고 생각해 봅시다. 어제까지 가장 좋은 파이프라인이 오늘도 좋을지는 알 수 없습니다. No-regret 학습은 매번 정답을 미리 맞히라고 요구하지 않습니다. 같은 관측 기록에서 처음부터 끝까지 한 행동만 사용한 기준과 비교해, 누적 성능의 손해가 기간에 비례해 커지지 않도록 하는 것이 목표입니다.

이 단원에서는 두 행동의 보수를 [0,1]로 정규화합니다. 라운드 t에 먼저 확률 혼합 p_t를 정하고, 이후 환경이 보수 벡터 g_t를 공개합니다. 두 행동의 보수를 모두 알게 되는 전체 정보 설정입니다. 혼합의 보수는 내적 p_t·g_t로 계산합니다. 선택한 행동의 보수만 관측하는 bandit과 달리, 두 번째 좌표까지 알고 갱신할 수 있습니다.

실습은 확률에서 행동 하나를 추출하지 않습니다. 내적으로 계산한 분수 보수와 실제 추출 경로의 실현 보수는 구분해야 합니다. 특히 상대가 언제 어떤 정보를 보는지에 따라 확률적 보장의 의미가 달라집니다.

고정 행동과 비교하는 외부 regret

앞 n라운드에서 행동 i의 보수 합을 G_n(i), 실제 혼합 내적 보수 합을 S_n이라 정의합니다.

$$R_n=\max_iG_n(i)-S_n,\qquad G_n(i)=\sum_{t=0}^{n-1}g_t(i),\qquad S_n=\sum_{t=0}^{n-1}p_t\cdot g_t.$$

최대값을 고르는 시점은 사후이지만, 비교 행동 i는 전체 구간에서 고정합니다. 매 라운드 보수를 본 뒤 다른 행동을 고르는 oracle과 다릅니다. 내 정책을 바꿨을 때 반응형 환경의 이후 행동까지 다시 생성하는 정책 regret과도 다릅니다.

변하는 혼합이 모든 고정 행동보다 잘할 수 있으므로 signed regret은 음수가 될 수 있습니다. No-regret의 한 편리한 정의는 양의 부분 max(0,R_n)을 n으로 나눈 값이 0으로 수렴한다는 것입니다. 이는 signed 평균의 limsup가 0 이하라는 표현과 같습니다. 보편적인 상한이 있다고 해서 모든 기록에서 signed 평균의 절댓값까지 0으로 수렴해야 하는 것은 아닙니다.

과거 선두를 부드럽게 따라간다

FTL, Follow the Leader는 과거 보수 합이 가장 큰 행동을 하나 고릅니다. 이 실습에서는 동률일 때 행동 0을 선택합니다. 누적 보수가 거의 같아도 한 좌표가 조금만 앞서면 선택 확률이 0에서 1로 바뀌는 불연속적인 규칙입니다.

Hedge는 선두에 확률을 더 주되 다른 행동도 남깁니다. 모든 행동에 양의 사전확률 pi_i를 주고 합을 1로 정합니다. 학습률 eta에서 선택 확률은 다음과 같습니다.

$$p_t(i)=\frac{\pi_i e^{\eta G_t(i)}}{\sum_j\pi_j e^{\eta G_t(j)}}.$$

여기서 G_t는 현재 라운드 이전인 0부터 t−1까지의 보수 합입니다. 현재 피드백 g_t를 받은 뒤 누적 합을 바꾸고 다음 확률 p_(t+1)을 계산합니다. 큰 eta는 작은 누적 차이에도 강하게 반응합니다. 작은 eta는 확률을 천천히 바꿉니다. eta가 0이면 항상 사전확률을 유지합니다. FTL은 학습률과 사전확률 입력을 사용하지 않습니다.

Arora·Hazan·Kale의 정리 §2.1은 지수 갱신을 multiplicative weights 계열과 연결합니다. 해당 문헌의 비용 범위와 상수를 그대로 옮기는 대신, 아래에서는 이 실습의 정규화 보수와 사전확률에 맞는 식을 유도합니다.

그림 전에 두 라운드를 손으로 계산한다

사전확률이 (1/2,1/2), eta가 1이고 매번 보수 벡터 (1,0)이 주어진다고 합시다. 아직 아무 피드백도 받지 않은 첫 혼합은 (1/2,1/2)이므로 첫 보수는 1/2입니다. 한 번 관측한 뒤 가중치 비는 e:1입니다.

$$p_1(0)=\frac e{1+e}\approx0.731059, \qquad p_1(1)=\frac1{1+e}.$$

둘째 보수는 약 0.731059입니다. 두 보수를 더하면 S_2≈1.231059이고 고정 행동 0의 보수는 2이므로 R_2≈0.768941입니다. 첫 라운드부터 0.731059를 쓰면 아직 받지 않은 첫 피드백을 미리 사용한 계산이 됩니다.

여덟 라운드에서는 S_8≈7.036367, R_8≈0.963633입니다. 같은 구간의 이론 상한은 log2+1≈1.693147입니다. 실제 regret과 보편적 상한은 서로 다른 값입니다. 유리한 한 환경에서 상한이 실제 곡선에 꼭 붙어야 하는 것은 아닙니다.

가정과 단위를 붙여 상한을 읽는다

전체 정보, 각 좌표 [0,1] 보수, 양의 고정 학습률, 모든 행동에 양의 사전확률을 가정합니다. 다음 복잡도 항을 둡니다.

$$C=\log\frac1{\min_i\pi_i}.$$

이때 분수 보수 실행의 각 접두 구간에서 다음이 성립합니다.

$$R_n\le B_n(\eta)=\frac C\eta+\frac{\eta n}{8}.$$

균등한 두 행동이면 C=log2입니다. 한 행동에 강하게 치우친 사전확률은 그 행동이 좋을 때 빠르게 시작하도록 돕지만, 가장 불리한 고정 비교 행동에 대한 C를 키웁니다. 특정 행동 i만 비교한다면 log(1/pi_i)를 쓸 수 있고, 화면은 모든 행동에 공통인 보수적 상한을 표시합니다.

계수 1/8은 보수 범위가 1이라는 조건에 맞습니다. 원래 보수에 다른 단위를 곱하면 regret 단위와 상한도 함께 바꿔야 합니다. 주황 표시를 확률적 신뢰 구간으로 읽으면 안 됩니다. 이 식은 혼합 내적 보수에 대한 결정론적 부등식입니다.

지수 잠재함수로 두 경계를 연결한다

누적된 증거의 양을 다음 잠재함수로 나타냅니다. 사전확률 합이 1이므로 Z_0=1입니다.

$$Z_n=\sum_i\pi_i e^{\eta G_n(i)}.$$

한 라운드가 만드는 로그 잠재함수의 변화는 다음과 같습니다.

$$\log Z_{t+1}-\log Z_t =\log\sum_i p_t(i)e^{\eta g_t(i)} \le\eta p_t\cdot g_t+\frac{\eta^2}{8}.$$

마지막 부등식은 [0,1] 값을 갖는 유한 확률변수에 대한 Hoeffding 보조정리입니다. 여기서 확률분포는 해당 라운드의 p_t입니다. 라운드 사이 보수열이 서로 독립이어야 하는 단계가 아닙니다. 위 식을 더하면 log Z_n≤eta S_n+n eta²/8을 얻습니다.

다른 방향에서는 Z_n 합의 행동 i 항 하나만 남겨도 log Z_n≥log pi_i+eta G_n(i)입니다. 두 식을 연결하고 양의 eta로 나눈 뒤 i에 대해 최대값을 취하면 앞의 상한이 나옵니다. 특정 알고리즘의 선택 규칙, 보수 범위, 비교 기준을 함께 사용한 증명이지, 한 실행의 그래프를 보고 만든 경험칙이 아닙니다.

Bartlett의 exponential weights 강의는 bounded loss의 Hoeffding 잠재함수 증명을 설명합니다. 손실을 1−보수로 바꾸고 사전확률 항을 유지하면 이 단원의 보수 최대화 표기를 얻습니다.

이 특정 고정 학습률 Hedge에는 추가 성질도 있습니다. Jensen 부등식으로 log Z_n≥eta S_n이고, Z_n≤exp(eta max_i G_n(i))이므로 수학적인 regret은 음수가 아닙니다. 앞의 음수 가능성은 일반적인 변화 정책에 대한 설명이며 이 알고리즘이 음수를 만든다는 주장이 아닙니다. 표시 계산에는 작은 부동소수점 잔차가 남을 수 있습니다.

한 고정 학습률과 no-regret 보장은 구분한다

상한을 T로 나누면 다음과 같습니다.

$$\frac{R_T}{T}\le\frac{C}{\eta T}+\frac\eta8.$$

eta를 하나의 양수로 고정하면 두 번째 항은 사라지지 않습니다. 따라서 이 식만으로 그 실행을 무한히 이어갈 때 no regret이라고 증명할 수 없습니다. 기간 T를 미리 아는 경우, 해당 실행에 사용할 고정 학습률을 다음처럼 정할 수 있습니다.

$$\eta_T=\sqrt{\frac{8C}{T}},\qquad B_T(\eta_T)=\sqrt{\frac{CT}{2}}.$$

이제 평균의 양의 상한은 1/√T 규모로 작아집니다. 이것은 서로 다른 기간 T에 맞춘 실행들의 보장입니다. 실습의 연속 최적 학습률 표시는 참고값입니다. 실제 입력은 eta×100의 정수이고 최대값도 있으므로 참고값과 일치하지 않을 수 있습니다. 화면의 상한은 언제나 실제 입력한 eta로 계산합니다.

기간을 모르면 길이 1,2,4,...인 블록마다 그 길이에 맞춘 학습자를 재시작하는 doubling 구성을 생각할 수 있습니다. 각 블록의 고정 행동 보장들을 더하면, 마지막 미완료 블록까지 포함해 제곱근 크기의 전체 상한을 얻습니다. 시변 학습률도 다른 방법이지만 그 갱신에 맞는 분석이 필요합니다. 기존 증명에서 eta만 매번 교체했다고 끝나는 것은 아닙니다. 실습은 고정 학습률의 접두 구간을 구현하며 doubling을 숨겨 실행하지 않습니다.

FTL이 선형 regret을 얻는 반례

현재 혼합 반응 환경은 가장 확률이 큰 행동에 보수 0, 다른 행동에 1을 줍니다. 확률이 같으면 행동 0을 벌줍니다. 현재 공개 확률을 확인하지만, 아직 추출하지 않은 무작위 행동을 미리 보는 환경은 아닙니다.

FTL은 첫 동률에 행동 0을 골라 0을 받습니다. 과거 기록에서 행동 1은 1을 받았으므로 다음에 행동 1로 바꾸지만, 그 행동이 다시 벌을 받습니다. 누적 보수가 동률이 되면 행동 0으로 돌아갑니다. 이 순서가 계속됩니다. 16라운드 FTL 보수는 0이고 두 고정 행동의 보수는 각각 8이어서 regret은 8입니다. 짝수 기간에서 평균 regret 1/2인 반례 계열입니다.

Hedge로 바꾸면 확률이 바뀌므로 같은 환경 규칙도 다른 보수열을 만들 수 있습니다. 따라서 두 알고리즘을 하나의 동일한 기록에 재생한 통제 비교라고 부르면 안 됩니다. 각 regret은 자기 실행에서 생성한 보수 벡터열의 고정 좌표와 비교한 값입니다.

적응적 상대와 표본 경로를 구분한다

잠재함수 부등식은 결과적으로 만들어진 모든 벡터열에 성립합니다. 현재 공개 혼합에 반응한 벡터라도 분수 보수의 대수적 증명은 유지됩니다. 이 설정에는 숨겨야 하는 실제 추출 행동 자체가 없습니다.

반면 확률적으로 행동 하나를 뽑는 구현에서 내적을 조건부 기대 보수로 읽으려면, 보수 벡터가 현재의 미공개 추출 결과에 의존하지 않는다는 시간 순서가 필요합니다. 실현된 표본 regret에는 추가 무작위성이 있습니다. 기대값·고확률 보장, 적응적 사후 최고 행동과의 비교에는 상대의 정보와 기대값 또는 마팅게일 논증을 명시해야 합니다. 화면의 분수 인증을 표본 경로 인증으로 이름만 바꾸면 안 됩니다.

또한 외부 regret은 정책 regret으로 바뀌지 않습니다. 내 정책을 바꾸면 반응형 환경의 이후 보수열도 달라질 수 있습니다. 이전 단원의 기록 재생과 정책 재실행 구분이 여기에서도 필요합니다.

두 학습자의 평균을 minimax와 연결한다

마지막 모드는 원래 제로섬 행렬 A=(1,−1;−1,1)을 사용하며 게임 값은 0입니다. [0,1] 피드백을 사용하도록 P1에는 G=(A+1)/2, 즉 단위행렬의 보수를 주고 P2에는 1−G를 줍니다. 열 혼합 q에 대한 P1의 행동별 벡터는 (q0,q1), 행 혼합 p에 대한 P2의 벡터는 (p1,p0)입니다. 두 플레이어는 각자의 이전 누적 벡터로 현재 혼합을 정한 뒤, 동시에 두 좌표의 피드백을 받습니다.

표시 구간에서 실제 사용한 혼합들의 산술평균을 p-bar, q-bar라 합시다. 원래 A 단위의 보장 하한과 상한은 다음과 같습니다.

$$L_A=2\min(\bar p_0,1-\bar p_0)-1, \qquad U_A=2\max(\bar q_0,1-\bar q_0)-1.$$

따라서 L_A≤0≤U_A입니다. 두 정규화 regret을 더하면 두 실제 보수 합이 매 라운드 1이라는 성질로 실제 보수들이 소거됩니다. 고정 행동 비교에 나타나는 상대 혼합은 쌍선형성 때문에 평균으로 모을 수 있어 다음 항등식을 얻습니다.

$$U_A-L_A=\frac{2(R_n^{(1)}+R_n^{(2)})}{n}.$$

실습은 평균 확률에서 직접 계산한 간극과 두 regret으로 복원한 간극을 모두 표시하고 부동소수점 잔차도 공개합니다. 한 표현을 그대로 재사용한 결과를 독립적인 증거라고 부르지 않습니다. 반대인 두 사전확률의 C는 같으므로, 양의 eta를 쓰는 두 Hedge의 경우 간극≤4B_n/n도 얻습니다.

이는 평균 혼합의 인증입니다. 마지막 혼합은 진동할 수 있습니다. 제로섬 구조도 필요합니다. 일반합 게임에서 외부 regret이 작다고 독립적인 마지막 혼합이 Nash에 수렴한다고 결론 내릴 수 없습니다. 경험적 결합 행동 분포, coarse correlated equilibrium, 더 강한 swap regret은 비교 기준을 구분해야 하는 후속 연구 연결입니다. 현재 모드가 추가로 인증한 결과는 아닙니다.

접두 구간과 빈 이력을 정직하게 읽는다

모든 표·보수·상한·평균은 표시한 접두 구간만 사용합니다. 중간 전환 환경은 floor(계획 기간/2)에서 바뀌므로 기간을 바꾸면 환경 일정도 달라집니다. 나머지 단일 학습자 환경은 기간을 늘려도 기존 접두 기록을 유지합니다.

조회 라운드는 표시된 마지막 라운드로 제한합니다. 빈 접두 구간에는 선택·피드백·평균 regret·평균 게임 간극을 만들어 넣지 않습니다. 아직 실행하지 않은 첫 다음 혼합은 사전확률로 정의할 수 있습니다. eta 0의 Hedge는 사전확률 고정 정책이며 양의 eta 상한은 표시하지 않습니다. FTL에도 Hedge 상한은 없습니다. 아래 곡선은 signed regret과 가능한 이론 상한이며, 표본 보수 경로가 아닙니다.

확인 문제와 해설

문제 1. 균등 사전확률, eta 1, 고정 벡터 (1,0)의 첫 두 확률과 보수를 구하세요. 첫 확률부터 e/(1+e)를 쓰면 무엇이 잘못되나요?

해설. 라운드 0과 1의 선택 전 확률은 1/2와 e/(1+e)입니다. 보수 합은 약 1.231059, regret은 0.768941입니다. 첫 확률부터 바꾸면 현재 피드백을 미리 사용하는 시간 순서 오류입니다.

문제 2. 균등 사전확률과 T=64에서 eta_T와 최적 평균 상한을 구하세요. eta 1을 그대로 유지한 상한도 같은 점근 결론을 주나요?

해설. eta_T=√(8log2/64)≈0.294353이고 평균 상한은 √(log2/128)≈0.073588입니다. eta 1의 식에는 log2/T+1/8이 남습니다. 특정 기록에서 성능이 좋을 수 있어도 이 식만으로 평균 regret이 사라진다고 증명하지 못합니다.

문제 3. 평균 게임 간극에 왜 계수 2가 필요한가요? 마지막 반복의 인증과는 왜 다른가요?

해설. G=(A+1)/2로 정규화했으므로 A 단위의 차이는 G 단위의 두 배입니다. 누적 고정 행동 비교는 쌍선형성 때문에 상대가 사용한 혼합의 평균에 의존합니다. 마지막 한 쌍의 혼합에 대한 성능을 직접 제한한 식이 아닙니다.