지연이 있는 근최적 확률적 선형 밴딧 (Near-Optimal Stochastic Linear Bandits with Delay)

우리는 여러 지연 모델(delay models) 하에서 피드백 지연이 발생하는 확률적 선형 밴딧 (stochastic linear bandits)을 연구하고 근최적 후회 보장 (near-optimal regret guarantees)을 확립합니다. 우리의 결과는 지연이 있는 선형 밴딧이 언제 다중 팔 밴딧 (multi-armed bandits, MAB)과 동일한 질적 동작을 보이는지, 그리고 언제 선형 구조가 근본적으로 새로운 과제를 생성하는지를 식별합니다. 구체적으로, (1) 지연이 실현된 손실 (loss)에 의존하지 않는 (단, 팔 (arm)에는 의존할 수 있는) extit{손실 독립적 지연 (loss-independent delays)}의 경우, 지연이 오직 가산적 후회 페널티 (additive regret penalty)만을 초래함을 보여줍니다. 확률적 지연 (stochastic delays) 하에서 이 페널티는 기대 지연 (expected delay)에 비례하며, 적대적 지연 (adversarial delays) 하에서는 미결 관측치 (outstanding observations)의 최대 수에 비례합니다. 특히, 두 지연 페널티 모두 차원 독립적 (dimension-free)이며, 이는 최신 기술 (state-of-the-art) 결과들을 개선한 것입니다; (2) extit{손실 의존적 지연 (loss-dependent delays)}의 경우, 선형 밴딧이 MAB보다 실질적으로 더 어렵다는 것을 보여줍니다. MAB와 달리, 우리는 선형 밴딧에서 (로그 인자를 제외하고) 일치하는 상한 (upper bound) 및 하한 (lower bound)을 증명하며, 여기서 지연 페널티는 차원의 제곱근에 의존합니다. (3) 손실 의존적 지연의 특수한 사례인 extit{보상으로서의 지연 (delay-as-payoff) 모델}의 경우, 최적의 팔의 지연에만 의존하는 최적의 MAB 보장이 선형 밴딧에서는 달성 불가능함을 보여줍니다. 종합적으로, 이러한 결과들은 지연된 피드백이 선형 일반화 (linear generalization)와 어떻게 상호작용하는지에 대한 날카로운 특성을 제공합니다.