확률적 다중 팔트 밴디트와 에피소드 강화학습의 분포적 regret에 대한 통합 프레임워크

우리는 확률적 다중 팔트 밴디트 (stochastic multi-armed bandits) 와 에피소드 강화 학습 (episodic reinforcement learning) 의 regret 분포를 하나의 통합된 프레임워크를 통해 연구합니다. 우리는 모든 신뢰 수준 $δ\in (0,1]$에 대해 균일하게 성립하는 확률적 보장을 통해 분포적 regret bound 를 공식화함으로써, 전체 $δ$ 범위에서의 regret 분포를 특징짓습니다. 탐험 보너스 (exploration bonus) 가 $\min{c_{1,k}/N, c_{2,k}/\sqrt{N}}$인 간단한 UCBVI 스타일 알고리즘을 제시합니다. 여기서 $N$은 방문 횟수 (visit count) 를 나타내고, $(c_{1,k},c_{2,k})$는 사용자가 지정하는 파라미터입니다. 임의의 파라미터 시퀀스 (arbitrary parameter sequences) 에 대해 gap-independent 와 gap-dependent 분포적 regret bound 를 유도하며, 이는 파라미터가 기대 성능 (expected performance), 꼬리 리스크 (tail risk), 그리고 인스턴스 의존적 행동 (instance-dependent behavior) 간의 균형을 어떻게 제어하는지를 원칙적으로 특징짓습니다. 특히, 우리의 bound 는 minimax 와 instance-dependent regime 모두에서 기대 regret 과 분포적 regret 간의 최적의 균형을 달성합니다. 특수한 경우로, $A$개의 팔과 지평선 $T$를 가진 다중 팔트 밴디트 (multi-armed bandits) 에 대해 순서 $\mathcal{O}(\sqrt{AT}\log(1/δ))$의 분포적 regret bound 를 얻었으며, 이는 Lattimore & Szepesvári (2020, Section 17.1) 의 추측을 처음으로 확인했습니다.