This paper presents a scalable alternative for Bayesian optimization in large-scale, unstructured discrete spaces. Specifically, we propose a Thompson sampling-based approach to address the computational cost of maximizing the gain function due to gradient absence. Thompson sampling directly parameterizes the probability that a candidate will obtain the maximum reward and incrementally adapts the posterior probability by leveraging prior knowledge embedded in a prompt-based, large-scale language model. The proposed method, Thompson Sampling via Fine-Tuning (ToSFiT), derives a novel regret bound for variational Thompson sampling and theoretically demonstrates that it provides strong guarantees of standard Thompson sampling. ToSFiT is experimentally validated on three diverse tasks: improving FAQ answers, searching for thermally stable proteins, and designing quantum circuits, demonstrating significant improvements in sampling efficiency through online fine-tuning.
