전환 비용이 있는 두 가지 동작 사과 맛보기 문제

우리는 무관심한 적대자(oblivious adversary)를 대상으로 전환 비용(switching costs)이 존재하는 두 가지 동작 사과 맛보기(two-action apple-tasting) 문제를 연구합니다. 동등한 정규화된 공식화(normalized formulation)에서, 매 라운드 학습자는 드러내는 동작(revealing action)과 눈먼 동작(blind action) 중 하나를 선택합니다. 드러내는 동작은 보상 $0$을 주며 눈먼 동작의 숨겨진 값 $x_t \in [-1,1]$을 드러냅니다. 눈먼 동작은 보상 $x_t$를 주지만 아무것도 드러내지 않습니다. 학습자는 동작을 전환할 때마다 1단위의 비용을 지불하며, 후회(regret)는 사후적으로 가장 좋았던 고정 동작(best fixed action)을 기준으로 측정됩니다. 전환 비용이 있는 일반적인 피드백 그래프(feedback-graph) 알고리즘은 이 문제에 대해 $\widetilde O(T^{2/3})$의 후회 보장(regret guarantees)을 제공합니다. 두 가지 동작 사과 맛보기 그래프는 전환 비용 분류 체계에서 누락된 $\Omega(T^{2/3})$ 장애물(obstruction)의 자연스러운 후보였습니다. 만약 그러한 하한(lower bound)이 존재했다면, 아직 분류되지 않은 방대한 피드백 그래프 제품군으로 전이되었을 것입니다. 우리는 이러한 장애물이 존재하지 않음을 증명합니다. 이 문제에 대한 무관심한 미니맥스 기대 후회(oblivious minimax expected regret)는 다음을 만족합니다.
[ \frac{1}{2\sqrt3}\cdot\sqrt T \le R_T^\star \le 2\sqrt{3}\cdot \sqrt{T}. ]