We consider the bilinear bandit problem where the learner chooses a pair of arms, each from two different action spaces of dimension $d_1$ and $d_2$, respectively. The learner then receives a reward whose expectation is a bilinear function of the two chosen arms with an unknown matrix parameter $\Theta^*\in\mathbb{R}^{d_1 \times d_2}$ with rank $r$. Despite abundant applications such as drug discovery, the optimal regret rate is unknown for this problem, though it was conjectured to be $\tilde O(\sqrt{d_1d_2(d_1+d_2)r T})$ by \citet{jun2019bilinear} where $\tilde O$ ignores polylogarithmic factors in $T$. In this paper, we make progress towards closing the gap between the upper and lower bound on the optimal regret. First, we reject the conjecture above by proposing algorithms that achieve the regret $\tilde O(\sqrt{d_1 d_2 (d_1+d_2) T})$ using the fact that the action space dimension $O(d_1+d_2)$ is significantly lower than the matrix parameter dimension $O(d_1 d_2)$. Second, we additionally devise an algorithm with better empirical performance than previous algorithms. Finally, we propose an algorithm for the problem of the bilinear bandit with warm-up vectors.
이 논문에서는 쌍선형 밴딧 문제에 대해 다루었다. 쌍선형 밴딧 문제에서 학습자는 매 시간마다 각각 $d_1$, $d_2$차원인 서로 다른 집합에서 뽑은 한 쌍의 벡터 원소들을 작용으로서 선택한다. 학습자는 이에 따른 보상을 받는데, 보상은 확률변수이며 기댓값은 선택했던 두 벡터 원소에 대해 계수 $r$의 숨겨진 행렬변수 $\Theta^*\in\mathbb{R}^{d_1 \times d_2}$를 중심으로 한 쌍선형 함수이다. 쌍선형 밴딧 문제는 신약 재창출 분야 등 다양한 응용방안이 있음에도, 이 문제에 대한 최적의 후회값이 얼마인지 아직 밝혀지지 않았으며, 다만 \citet{jun2019bilinear}에 의해 후회값의 상한이 $\tilde O(\sqrt{d_1d_2(d_1+d_2)r T})$인 알고리즘이 존재한다는 정도만 증명되었을 따름이다 ($\tilde O$는 $\log T$에 대한 다항식 차수까지 무시하는 점근 분석 수치이다). 이 논문에서는 이론적 후회값 상한을 개선하거나, 실제 실험적 성능을 개선하는 다양한 방식의 알고리즘을 제안하였다. 첫 번째로, 우리는 후회값 상한이 $\tilde O(\sqrt{d_1 d_2 (d_1+d_2) T})$인 알고리즘을 고안해 내어 기존에 추정되어 오던 하한인 $\Omega(\sqrt{d_1d_2(d_1+d_2)r T})$를 부정하는 데에 성공했다. 이 과정에서 우리는 기존의 숨겨진 변수 $\Theta^*$에 집중하던 방식을 벗어나 작용공간에 집중하였으며, 실제 작용공간의 차원은 $O(d_1+d_2)$ 수준으로 기존에 계산에 고려되던 작용공간 차원 $O(d_1 d_2)$보다 훨씬 작음을 발견하고 이를 이용하여 후회값 상한을 낮추는 데에 성공했다. 두 번째로, 우리는 실성능이 기존 알고리즘 대비 더 나은 추가적인 알고리즘을 고안하였다. 마지막으로, 우리는 유의미한 선행지식 벡터를 알고있는 상태의 쌍선형 밴딧 문제를 고안하였고 이에 대한 새로운 알고리즘을 제시하였다.
