다중 암 밴딧(multi-armed bandit) 문제에서 사용자 개인화 선호와 시간에 따른 컨텍스트 분포 변화를 동시에 처리하는 새 알고리즘이 제안됐다. 연구진은 각 사용자가 고유한 선호 벡터를 갖고, 추천 시스템이 매 결정 단계마다 기준 정책(베이스라인) 대비 평균 보상 조건을 반드시 충족해야 하는 선형 컨텍스트 확률적 밴딧 변형 문제를 다뤘다. 이는 새로운 선택지를 탐색하면서도 기존 안전 기준선보다 나쁜 결과를 내지 않아야 하는, 현실 서비스에서 흔히 마주치는 제약 상황을 형식화한 것이다.
학습자가 마주하는 컨텍스트 분포가 시간에 따라 변하는 점이 이 문제의 핵심 난점이다. 사용자마다 선호가 다른 데다 환경 자체가 비정상적으로 움직이기 때문에, 단순히 보수적으로 기준선만 따르는 방식으로는 변화하는 수요를 따라잡지 못한다. 연구진은 이러한 설정을 평균은 고정돼 있으나 분산이 균일하지 않게 변하는 선형 밴딧 문제로 환원하는 분석 틀을 제시했다.
핵심 기여는 Dri-MED 알고리즘이다. 이 알고리즘은 선형 MED(Minimum Empirical Divergence) 전략에서 착안해 비정상(non-stationary) 이분산(heteroskedastic) 잡음 환경에 맞게 설계됐다. 이분산 회귀(heteroskedastic regression) 기반 분산 추정 항을 도입해 컨텍스트 드리프트와 사용자 다양성에서 비롯되는 잡음 구조를 처리한다.
이론 분석에서 Dri-MED의 인스턴스 의존적 후회(regret) 상계는 정책 기준 제약을 고려한 최적성 갭과 차원 수에 의해 결정되는 것으로 나타났다. 기댓값 제약 위반 횟수도 입력 차원 수의 스케일로 제한됨을 보였다. 수치 실험에서는 드리프트와 선호 구조를 무시하는 보수적 기준선(conservative baseline) 방법들에 비해 Dri-MED가 유의미하게 우수한 성능을 기록했다. 이 연구는 개인화 추천, A/B 테스트 효율화, 동적 환경에서의 의사결정 시스템 설계에 적용 가능한 이론적 토대를 제공한다.
