다중 팔 강도기(Multi-Armed Bandit) 문제에서 후회 최소화를 위한 자유 탐색의 이점

On the Benefits of Free Exploration for Regret Minimization in Multi-Armed Bandits

본 연구는 에이전트가 누적된 후회보다 먼저 일정량의 자유 탐색 예산을 할당받는 확률적 다중 팔 강도기 문제를 다룬다. 이는 기존의 후회 최소화 또는 순수 탐색 방식으로는 설명할 수 없는 설정이다. 목표는 전략적으로 초기 자유 탐색 단계에서 강도기 인스턴스를 탐색하고, 이후 단계에서 누적된 후회를 최소화하는 적응형 정책을 설계하는 것이다. 본 연구에서는 자유 탐색이 가능한 후회 최소화 문제를 형식화하고, 자유 탐색 예산이 시간 지평선에 대해 로그 함수적으로 변하는 흥미로운 현상을 밝혀낸다. 자유 탐색 단계의 가용성이 결과적으로 발생하는 후회 감소량을 높은 확률로 정량화하기 위해, (α,β)-확률적 절약 정책이라는 새로운 정책 집합을 제안한다. 본 연구에서는 원칙적인 자유 탐색 정책인 UFE와 과거 정보를 활용하는 후회 최소화 정책 KLUCB-H를 결합한 두 단계의 확률적 절약 알고리즘, UFE-KLUCB-H를 제안한다. UFE-KLUCB-H에 대한 인스턴스 의존적인 상한 경계를 유도하여, UFE-KLUCB-H가 자유 탐색 단계를 활용하지 않는 정책보다 더 적은 후회를 누적함을 보여준다. 추가적으로, 본 연구는 자유 탐색 설정에 맞게 설계된 새로운 다중 인스턴스 교란 논증을 기반으로 인스턴스 의존적인 하한 경계를 유도하여, UFE-KLUCB-H가 이분 팔 강도기 문제에서 거의 최적의 성능을 보임을 입증한다. 상한 및 하한 경계는 사용 가능한 자유 탐색량에 따라 누적된 후회에 뚜렷한 변화를 보여주며, 이를 통해 강제적인 탐색과 알고리즘의 적응성이 더 큰 후회 감소로 이어짐을 시뮬레이션을 통해 입증한다.

We study a stochastic multi-armed bandit problem where an agent is granted a free exploration budget before regret accumulates, a setting not captured by the classic regret minimization or pure exploration paradigms. The goal is to design an adaptive policy that strategically explores the bandit instance in the initial free exploration phase and minimizes the cumulative regret in the subsequent phase. We formalize this regret minimization with free exploration problem and identify an interesting regime where the free exploration budget scales logarithmically with the time horizon. To quantify the amount of regret saved with high probability as a result of the availability of the free exploration phase, we introduce a novel set of policies known as $(α,β)$-probably saving policies. We propose a two-phase, probably saving algorithm, UFE-KLUCB-H, which consists of a principled free exploration policy, UFE, and a history-aware regret minimization policy KLUCB-H. Instance-dependent upper bounds on UFE-KLUCB-H are derived, showing that UFE-KLUCB-H accumulates strictly less regret than policies that do not have access to a free exploration phase. Complementarily, we derive instance-dependent lower bounds based on novel multi-instance perturbation arguments tailored to the free-exploration setting, demonstrating the near-optimality of UFE-KLUCB-H for two-valued bandits. Our upper and lower bounds reveal sharp phase transitions in the accumulated regret depending on the amount of available free exploration. Simulations are conducted to demonstrate that forced exploration and adaptivity in the algorithm lead to greater regret savings.