증명 가능한 최적 학습 알고리즘: 지원 게임

Provably Optimal Learning Algorithms for Assistance Games

본 논문에서는 '지원 게임' 프레임워크의 온라인 버전을 연구합니다. 여기서 정보가 있는 에이전트와 정보가 없는 에이전트는 $T$ 단계 동안 반복적으로 상호 작용하며, 공통적인 보상 함수를 최적화합니다. 정보가 있는 에이전트(사람)는 세상의 숨겨진 상태를 관찰하는 반면, 정보가 없는 에이전트(조력자)는 사람의 행동만을 관찰합니다. 우리는 반복적인 지원 게임에 대한 최초의 증명 가능한 효율적인 학습 알고리즘을 제시합니다. 우리는 '지원 후회'라는 개념을 도입하며, 이는 숨겨진 상태를 행동 쌍으로 매핑하는 최적의 공동 정책과 실제 상호 작용의 누적 유틸리티 간의 차이를 의미합니다. 우리는 사람과 조력자 모두에게 적용 가능한 분산 알고리즘을 제시하며, 이 알고리즘들은 실행 시간 측면에서 행동 및 상태 공간의 크기에 다항식적으로 의존하며, $(1-1/e)$에 근사하는 지원 후회율 $ ilde{O}(T^{3/4})$를 달성합니다. 이러한 알고리즘은 일반적이며, 특히 조력자를 위한 모든 후회 없는 알고리즘을 수용할 수 있습니다. 우리는 $(1-1/e)$보다 더 나은 후회 근사 계수를 달성하는 것은 계산적으로 불가능하다는 것을 증명합니다. 더욱이, 우리는 이러한 범용적인 후회 없는 알고리즘이 공유된 임의 문자열을 사용하여 '준-분산' 환경에 맞게 조정되어 $ ilde{O}(T^{1/2})$의 성능, 즉 로그 스케일까지 최적의 성능을 달성할 수 있음을 보여줍니다.

This paper studies an online variant of the assistance games framework, where an informed agent and an uninformed agent repeatedly interact over $T$ timesteps to optimize a common reward function. While the informed agent (the human) observes a latent state of the world, the uninformed agent (the assistant) observes only the human's actions. We provide the first provably efficient learning algorithms for repeated assistance games. We introduce the notion of assistance regret: the gap between the cumulative utility of interactions and that of the optimal joint policies in hindsight, which map latent states to action pairs. We present decentralized algorithms for both the human and the assistant that achieve a $(1-1/e)$-approximate assistance regret rate of $\widetilde{O}(T^{3/4})$, with runtime polynomial in the size of the action and state spaces. These algorithms are general; in particular, they accommodate any no-regret algorithm for the assistant. We prove that achieving a regret approximation factor better than $(1-1/e)$ is computationally intractable. Furthermore, we demonstrate how these generic no-regret algorithms can be tailored to a pseudo-decentralized setting -- using a shared random string -- to achieve a rate of $\widetilde{O}(T^{1/2})$, optimal up to logarithmic factors.