최종-최종 밴딧 피드백을 갖춘 다단계 시스템을 위한 분산 무후회 학습

이 논문은 최종-최종 밴딧 피드백을 갖춘 다단계 시스템을 연구한다. 이러한 시스템에서는 각 작업이 여러 단계를 거쳐야 하며, 각각은 다른 에이전트가 관리하여 결과를 생성한다. 각 에이전트는 자신의 행동만을 제어할 수 있고 작업의 최종 결과를 학습할 수 있다. 다음 단계에서 에이전트가 실행하는 행동에 대한 지식이나 제어권이 없다. 이 논문의 목표는 적대적 환경에서 하위 선형 후회를 달성하는 분산 온라인 학습 알고리즘을 개발하는 것이다. 본 논문의 설정은 단일 에이전트와 단일 단계만 고려하는 전통적인 다중 무장 밴딧 문제를 크게 확장한다. 전통적인 다중 무장 밴딧 문제의 탐험-착취 딜레마 외에, 여러 단계를 고려해야 함에 따라 에이전트가 다음 단계의 에이전트 학습을 촉진하기 위해 행동을 선택해야 하는 교육이라는 세 번째 요소가 도입된다. 이 새롭게 도입된 탐험-착취-교육 삼중 은유를 해결하기 위해 간단한 분산 온라인 학습 알고리즘인 -EXP3을 제안한다. 이론적으로 -EXP3 알고리즘이 하위 선형 후회를 달성하는 무후회 정책임을 증명한다. 시뮬레이션 결과는 -EXP3 알고리즘이 전통적인 다중 무장 밴딧 문제에 대한 기존 무후회 온라인 학습 알고리즘보다 상당히 우수함을 보여준다.