Bilinear Bandits with Partially Observable Features

We study bilinear bandits with partially observable features on both the user and item sides. In each of $T$ rounds, the learner selects a user--item pair and observes only the reward for the chosen pair. The reward model is bilinear in the user and item features with an unknown parameter matrix. Existing work commonly reduces this problem to a linear bandit via Kronecker-product features, increasing dimensionality and losing bilinear structure. We propose \texttt{BiRoLF}, an algorithm robust to latent features, which directly leverages the bilinear structure without such linearization. It augments observed feature spaces on both sides with orthogonal complement bases and employs doubly robust (DR) estimation to impute rewards for unselected pairs, constructing matrix-valued pseudo-rewards. We estimate the effective parameter using a bilinear DR-Lasso estimator, which promotes sparsity in components orthogonal to observed features. \texttt{BiRoLF} achieves a $\tilde{O}(\sqrt{(d_x + d_{h_x})(d_y + d_{h_y}) T})$ regret bound, where $d_x$ and $d_y$ are observable feature dimensions, and $d_{h_x}$ and $d_{h_y}$ denote effective orthogonal-complement dimensions. By exploiting the induced block-diagonal Gram structure, \texttt{BiRoLF} performs an exact blockwise update that preserves the full DR-Lasso objective. Numerical experiments show strong regret performance and computational gains.

We study decision-making problems where a learner repeatedly chooses a pair of entities, such as a user and an item, and observes the outcome only for the chosen pair. In many practical settings, including recommendation, matching, dispatch, and drug discovery, only part of the relevant information about each side is available, while hidden preferences or compatibility factors can still affect the outcome. Learning only from the observed information can therefore lead to poor decisions. We propose BiRoLF, an algorithm designed for such two-sided problems with hidden information on both sides. Instead of converting each pair into a large flat representation, BiRoLF keeps the two-sided interaction structure of the problem. It augments the observed information to account for hidden components and uses what it learns from the chosen pair to improve estimates for other possible pairs as well. We prove that BiRoLF learns effectively over time and show that its computation can be carried out more efficiently by splitting the main estimation problem into smaller parts. Experiments on synthetic and MovieLens-based recommendation settings show that BiRoLF maintains strong learning performance while reducing optimization and running time.