제한된 적응성을 가진 문맥적 슬레이트 GLM 밴딧 (Contextual Slate GLM Bandits)
요약
제한된 적응성 환경에서 일반화 선형 보상을 갖는 문맥적 슬레이트 밴딧 문제를 다루는 연구입니다. 배치형 및 드물게 전환되는 방식의 새로운 알고리즘을 제안하며, 이론적 후회 한계 증명과 함께 언어 모델의 인컨텍스트 예시 선택 작업에서의 성능을 입증했습니다.
핵심 포인트
- 제한된 적응성 하의 B-SlateGLinCB 및 RS-SlateGLinCB 알고리즘 제안
- 비선형성 파라미터 κ와 무관한 후회 한계(regret bounds) 달성 증명
- 슬레이트 조합 폭발에도 불구하고 라운드당 다항 시간의 계산 효율성 확보
- LLM의 인컨텍스트 예시 선택 작업에서 실질적인 성능 우수성 확인
우리는 제한된 적응성 (limited adaptivity) 하에서 일반화 선형 보상 (generalized linear rewards)을 갖는 문맥적 슬레이트 밴딧 (contextual slate bandit) 문제를 조사합니다. 매 라운드마다 학습자에게는 각 아이템이 $d$차원 특징 벡터 (feature vector)로 표현되는 $N$개의 아이템 세트가 제공됩니다. 학습자는 각 세트에서 하나의 아이템을 선택하여 슬레이트 (slate)를 구성하며, 결과적으로 생성된 슬레이트는 일반화 선형 모델 (Generalized Linear Model, GLM)에서 샘플링된 스칼라 보상을 산출합니다. 우리는 두 가지 제한된 적응성 설정 하에서의 알고리즘을 제안합니다: (a) 배치형 (Batched) 및 (b) 드물게 전환되는 방식 (Rarely-Switching). 배치형 설정의 경우, 각 배치의 정책이 이전 배치의 데이터에만 의존하도록 시간 지평 (time horizon)을 $\mathcal{O}(\log\log T)$개의 배치로 분할하는 B-SlateGLinCB를 도입합니다. 드물게 전환되는 방식의 경우, 적응적으로 $\mathcal{O}(Nd\log T)$번의 파라미터 업데이트만을 수행하는 RS-SlateGLinCB를 제안합니다. 아이템 시퀀스에 대한 다양성 가정 (diversity assumption) 하에서, 우리는 B-SlateGLinCB와 RS-SlateGLinCB가 각각 $\mathcal{O}(Nd^{3/2}\sqrt{T})$ 및 $\mathcal{O}(Nd\sqrt{T})$의 후회 한계 (regret bounds)를 달성함을 증명합니다. 특히, 두 한계 모두 일반적으로 GLM 밴딧 알고리즘의 후회를 확장시키는 비선형성 파라미터 (non-linearity parameter) $κ$와 무관합니다. 우리의 알고리즘은 $2^{Ω(N)}$개의 가능한 슬레이트에도 불구하고 라운드당 $\text{poly}(N)$ 시간만을 요구하여 계산 효율적입니다. 시뮬레이션 결과, 우리의 알고리즘은 제한된 적응성을 가진 기존 베이스라인보다 우수한 성능을 보였으며, 완전 적응형 최첨단 알고리즘인 Slate-GLM-OFU와도 경쟁력 있는 성능을 유지함을 보여줍니다. 특히, 약간 수정된 B-SlateGLinCB는 경험적으로 이 베이스라인과 일치하는 성능을 보입니다. 마지막으로, 우리는 언어 모델을 위한 실제적인 인컨텍스트 예시 선택 (in-context example selection) 작업에서 강력한 성능을 입증합니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.LG의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기