강건한 밴딧 문제의 계산적 처리 가능성에 관하여

원문 발행 2026. 10. 07. 02:38원문 언어 영어AI 한국어 번역arXiv cs.LG (Machine Learning) 원문 보기

요약

본 논문은 학습 환경이 분포를 벗어나는 경우(out-of-distribution)의 강건한 밴딧 문제에 대한 계산적 처리 가능성을 탐구합니다. 기존 연구에서 제시된 $ ilde{O}(\sqrt{T})$ 후회율을 갖는 학습자가 다항 시간 내에 허용되는 특별한 경우를 식별했습니다. 또한, 이 특별한 경우가 NP-난해임을 보여주어 이론적 경계를 제시합니다.

핵심 포인트

Out-of-distribution 환경의 강건한 밴딧 문제 접근
다항 시간 내 $ ilde{O}(\sqrt{T})$ 후회 학습 가능 조건 식별
특정 경우의 NP-난해성 입증을 통한 계산적 경계 제시
AI 정렬 문제 해결에 기여하는 이론적 연구 방향 제시

학습 환경이 학습자의 가설 클래스에 속하지 않는 경우(out-of-distribution)를 다루는 것은 일반적으로 비가정적 학습 보장(agnostic learning guarantees)을 사용하여 처리됩니다. 하지만 지도 학습(supervised learning)을 넘어서는 영역에서는 비가정적 보장을 얻기가 어렵습니다. 최근에는 부정확한 밴딧(imprecise bandits) (Kosoy, 2025) (이후 Appel과 Kosoy, 2025에서 강건한 밴딧(robust bandits)으로 이름 변경됨)이 밴딧 설정에서의 실현 불가능 학습(unrealizable learning)에 대한 또 다른 접근 방식으로 소개되었으며, 큰 클래스에 대해 $\Theta(\sqrt{T})$의 후회(regret)를 갖는 학습자가 제시되었습니다. 하지만 계산적 보장은 제공되지 않았습니다. 본 논문에서는 다항 시간 내에 $\tilde{O}(\sqrt{T})$의 후회를 갖는 학습자를 허용하는 특별한 경우를 식별합니다. 또한 이 특별한 경우의 몇 가지 작은 일반화들이 NP-난해(NP-hard)임을 보여주어, 해당 특별한 경우가 계산적으로 처리 가능한 것의 경계에 있음을 시사합니다. 최근 (Kosoy, 2018)에서는 실현 불가능 학습 문제에 대한 계산적으로 효율적인 학습자가 AI 정렬 문제(AI alignment problem)를 해결하는 데 중요하다고 제안되었습니다. 본 연구는 그 방향으로 나아가는 작은 단계입니다.

AI 자동 생성 콘텐츠

원문 바로가기

강건한 밴딧 문제의 계산적 처리 가능성에 관하여

요약

핵심 포인트

댓글