부분 관측 하에서 암묵적 탐색으로 효율적 학습

한줄 요약

부분 관측 밴딧 문제에서 관측 시스템을 몰라도 준최적 후회를 보장하는 암묵적 탐색 기반 알고리즘을 제안한다.

풀어야 하는 문제

기존 밴딧 문제는 완전 정보(전체 관측) 또는 밴딧 피드백(자신의 행동만 관측)을 가정하지만, 실제로는 일부 추가 관측이 가능한 중간 상황이 많다. 이러한 부분 관측 하에서 관측 시스템을 사전에 알 수 없을 때 효율적으로 학습하는 알고리즘이 부재했다.

접근 방법

암묵적 탐색(implicit exploration)이라는 새로운 탐색 전략을 도입한다. 이 전략은 행동 선택 시 관측 가능성을 고려하여 탐색을 수행하며, 관측 시스템에 대한 사전 지식 없이도 후회 상한을 보장한다. 첫 번째 알고리즘은 일반적인 부분 관측 설정을 다루고, 두 번째 알고리즘은 조합 최적화 문제에 대해 계산 효율성을 높인 변형이다.

결과·기여

제안된 알고리즘은 관측 시스템을 모를 때에도 O(√T) 수준의 후회를 달성하며, 기존 탐색 전략보다 계산 및 정보 이론적으로 더 효율적임을 이론적으로 증명했다. 이는 부분 관측 밴딧 문제의 실용적 적용 가능성을 크게 높인다.