Improved Regret Bounds of Bilinear Bandits using Action Space Analysis

We consider the bilinear bandit problem where the learner chooses a pair of arms, each from two different action spaces of dimension d₁ and d₂, respectively. The learner then receives a reward whose expectation is a bilinear function of the two chosen arms with an unknown matrix parameter Θ^∗ ∈ Rd¹×d² 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 Õ(√d₁d₂(d₁ + d₂)rT) by Jun et al. (2019) where Õ 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 Õ(√d₁d₂(d₁ + d₂)T) using the fact that the action space dimension O(d₁+d₂) is significantly lower than the matrix parameter dimension O(d₁d₂). Second, we additionally devise an algorithm with better empirical performance than previous algorithms.