Bilinear Matching Bandits

We study bilinear matching bandits, an online sequential decision problem in which at each round a learner assigns $M$ users to $N$ items via an injective matching $\pi :[M]\hookrightarrow [N]$ and observes semi-bandit feedback with bilinear mean reward ${\mathbf{x}}_i^{\top }{\mathbf{\Theta }}^{\star }{\mathbf{y}}_{\pi (i)}$, where the parameter ${\mathbf{\Theta }}^{\star }\in {\mathbb{R}}^{d_1\times d_2}$ is unknown. We propose HybridRRD, a hybrid algorithm that combines high-width elimination with a row-wise regularized design sampler over the fractional matching polytope. Without assuming ${\mathbf{\Theta }}^{\star }$ is low-rank, HybridRRD achieves a high-probability regret bound of $\tilde{O}(d_2\sqrt{d_{1}MT}+M{d}_1{d}_2)$, suppressing problem-scale constants. This improves the leading dimension dependence from $d_1{d}_2$ to $d_2\sqrt{d_1}$ over the standard Kronecker-linearized contextual combinatorial semi-bandit baseline. We further prove a minimax lower bound of $\Omega (d_2\sqrt{d_{1}MT})$ in a large-item regime, matching the leading regret term up to logarithmic factors. Numerical experiments show that HybridRRD performs favorably against Kronecker-linearized baselines.