Bilinear Thompson Sampling in Sequential Decision Making

About

Bilinear stochastic bandits are sequential decision-making problems where, at each round $t$, a learner selects $(x_t,z_t)\in\mathbb{R}^{d_1}\times\mathbb{R}^{d_2}$ and observes $y_t=x_t^\top\Theta^\star z_t+\varepsilon_t$, where $\Theta^\star\in\mathbb{R}^{d_1\times d_2}$ is an unknown low-rank matrix. A direct reduction to a linear bandit may incur regret scaling with the ambient dimension $d_1d_2$. Existing approaches such as ESTR in Jun et al. [2019] exploit low-rank structure through subspace exploration, but require careful tuning of the exploration length. We propose Bilinear Thompson Sampling, which uses low-rank posterior samples to adaptively balance exploration and exploitation in selecting action pairs. We implement the posterior sampling procedure using a Gibbs sampler, evaluate the method empirically, and study its frequentist regret.

Details

Date:

Friday, November 13, 2026

Time:

12:00 PM - 1:00 PM

Location:

CDS 1646

Theme:

Computational Methodology