사이드 관측이 있는 밴디트 문제에서의 암묵적 탐색을 통한 효율적 학습

우리는 학습자에게 제공되는 정보가 완전 정보와 밴디드 피드백 사이의 상황에 해당하는 부분 관측성 (partial observability) 모델을 기반으로 하는 온라인 학습 문제를 고찰합니다. 가장 간단한 변형에서는 학습자가 자신의 손실뿐만 아니라 다른 일부 행동의 손실도 관측할 수 있다고 가정합니다. 공개된 손실은 학습자의 행동과 환경이 선택한 방향성 있는 관측 시스템 (directed observation system) 에 의존합니다. 이 설정을 위해 우리는 행동을 선택하기 전에 관측 시스템을 알아야 하지 않으면서 근사 최적의 후회 (regret) 보증을 누릴 수 있는 최초의 알고리즘을 제안합니다. 유사한 맥락에서, 우리는 학습자가 받는 피드백이 반 밴디드 (semi-bandit) 와 완전 피드백 사이의 온라인 조합 최적화 문제를 모델링하는 새로운 부분 정보 설정도 정의합니다. 우리의 첫 번째 알고리즘의 예측은 이 설정에서 항상 효율적으로 계산될 수 없으므로, 약간 더 복잡한 튜닝 메커니즘을 대가로 항상 계산적으로 효율적인 또 다른 알고리즘을 제안합니다. 두 알고리즘 모두 이전에 연구된 해당 문제의 탐색 전략보다 계산적 및 정보 이론적으로 더 효율적임이 입증된 새로운 '암묵적 탐색 (implicit exploration)' 전략에 의존합니다.