Multi-Armed Bandits에서의 유사성 활용

많은 온라인 학습(online learning) 및 밴딧(bandit) 문제에서, 우리가 고려하는 행동(actions)들은 잠재적 특성(latent traits), 태그(tags), 또는 계층적 구조(hierarchical structure)를 공유하기 때문에 본질적인 유사성을 가집니다. 본 연구에서는 리프 노드(leaves)가 행동(actions)이고 레벨(levels)이 두 행동 간의 관계 밀접도를 정량화하는 루트 트리(rooted tree)로 인코딩된, 유사성 구조를 가진 행동 집합(similarity-structured action set)에서의 온라인 학습을 연구합니다. 손실 시퀀스(loss sequence)는 트리 호환적(tree-compatible)이라고 가정합니다. 즉, 유사한 행동들의 손실은 서로 가깝게 유지되도록 제한됩니다. 우리는 일반적인 단일 지점 밴딧 피드백(one-point bandit feedback)이 매우 강력한 유사성 제약 조건 하에서도 일반적으로 범위(range) 또는 트리 유도 유사성(tree-induced similarity)을 활용할 수 없음을 보여주는 불가능성 결과(impossibility result)를 확립합니다. 그런 다음, 우리는 최소 2지점 피드백(two-point feedback) 설정을 포함하여, 세미 밴딧 피드백(semi-bandit feedback)부터 멀티 포인트 밴딧 프로토콜(multi-point bandit protocols)에 이르기까지 광범위하고 더 풍부한 피드백 모델에 적응하는 통합된 알고리즘 세트를 제공합니다. 우리는 이 알고리즘들이 'best-of-both-worlds' 보장을 나타내며, 후회 한계(regret bounds)에서 행동의 수 $K$를 유사성을 인식하는 유효 행동 수 $K_{\mathrm{eff}}$로 대체함으로써 행동 유사성을 증명 가능하게 활용함을 보여줍니다. 응용 사례로서, 우리는 2지점 피드백 하에서 $d \leq 2$일 때 Lipschitz 밴딧(Lipschitz bandits)에서 $\sqrt{T}$ 후회(regret)를 달성하는 것이 가능함을 보여줍니다.