다음 토큰 예측과 후회 최소화

Next-Token Prediction and Regret Minimization

본 논문에서는 다음 토큰 예측 알고리즘을 적대적인 온라인 의사 결정 환경에서 어떻게 활용할 수 있는지에 대해 고찰합니다. 구체적으로, 상대방의 행동 시퀀스에 대한 분포 $\mathcal{D}$를 사용하여 다음 토큰 예측 모델을 학습할 때, 이 모델의 예측에 근사적으로 최적화하여 온라인 의사 결정 알고리즘을 구성했을 때, 이 알고리즘이 낮은 수준의 적대적 후회를 갖는 조건(즉, $\mathcal{D}$가 '낮은 후회 분포'인 조건)은 언제일까요? 무한한 컨텍스트 윈도우(모델의 예측이 상대방이 지금까지 수행한 모든 행동에 의존할 수 있는 경우)의 경우, 모든 분포 $\mathcal{D}$가 낮은 후회 분포는 아니지만, 모든 분포 $\mathcal{D}$는 TV 거리를 기준으로 하나의 낮은 후회 분포와 지수적으로 가깝다는 것을 보여줍니다. 따라서 원래의 다음 토큰 예측 모델의 정확도에 거의 영향을 주지 않고 항상 하위 선형 수준의 후회를 달성할 수 있습니다. 이에 반해, 유한한 컨텍스트 윈도우(모델의 예측이 상대방이 지금까지 수행한 최근 $w$개의 행동에만 의존하는 경우, 이는 현대 트랜스포머 아키텍처에서 흔히 나타나는 경우입니다)의 경우, 상대방의 플레이 분포 중 일부는 어떤 낮은 후회 분포 $\mathcal{D'}$로부터 $Θ(1)$만큼 멀리 떨어져 있습니다(심지어 $w = Ω(T)$인 경우에도 그러한 분포가 존재합니다). 마지막으로, 본 논문에서는 무한한 컨텍스트의 강건성 확보 절차를 표준 트랜스포머 아키텍처의 레이어로 구현할 수 있음을 보여주고, 트랜스포머 모델을 효율적으로 학습하여 이러한 새로운 낮은 후회 분포를 표현할 수 있다는 경험적 증거를 제공합니다.

We consider the question of how to employ next-token prediction algorithms in adversarial online decision-making environments. Specifically, if we train a next-token prediction model on a distribution $\mathcal{D}$ over sequences of opponent actions, when is it the case that the induced online decision-making algorithm (by approximately best responding to the model's predictions) has low adversarial regret (i.e., when is $\mathcal{D}$ a \emph{low-regret distribution})? For unbounded context windows (where the prediction made by the model can depend on all the actions taken by the adversary thus far), we show that although not every distribution $\mathcal{D}$ is a low-regret distribution, every distribution $\mathcal{D}$ is exponentially close (in TV distance) to one low-regret distribution, and hence sublinear regret can always be achieved at negligible cost to the accuracy of the original next-token prediction model. In contrast to this, for bounded context windows (where the prediction made by the model can depend only on the past $w$ actions taken by the adversary, as may be the case in modern transformer architectures), we show that there are some distributions $\mathcal{D}$ of opponent play that are $Θ(1)$-far from any low-regret distribution $\mathcal{D'}$ (even when $w = Ω(T)$ and such distributions exist). Finally, we complement these results by showing that the unbounded context robustification procedure can be implemented by layers of a standard transformer architecture, and provide empirical evidence that transformer models can be efficiently trained to represent these new low-regret distributions.