Papers βΊ Sequential Experimental Design for Transductive Linear Bandits
Sequential Experimental Design for Transductive Linear Bandits
Tanner Fiez, Lalit Jain, Kevin Jamieson, Lillian Ratliff
In this paper we introduce the transductive linear bandit problem: given a set of measurement vectors π³ββα΅, a set of items π΅ββα΅, a fixed confidence Ξ΄, and an unknown vector ΞΈ^βββα΅, the goal is to infer argmax_(zβπ΅) z^β€ΞΈ^β with probability 1-Ξ΄ by making as few sequentially chosen noisy measurements of the form x^β€ΞΈ^β as possible. When π³=π΅, this setting generalizes linear bandits, and when π³ is the standard basis vectors and π΅β{0,1}α΅, combinatorial bandits. Such a transductive setting naturally arises when the set of measurement vectors is limited due to factors such as availability or cost. As an example, in drug discovery the compounds and dosages π³ a practitioner may be willing to evaluate in the lab in vitro due to cost or safety reasons may differ vastly from those compounds and dosages π΅ that can be safely administered to patients in vivo. Alternatively, in recommender systems for books, the set of books π³ a user is queried about may be restricted to well known best-sellers even though the goal might be to recommend more esoteric titles π΅. In this paper, we provide instance-dependent lower bounds for the transductive setting, an algorithm that matches these up to logarithmic factors, and an evaluation. In particular, we provide the first non-asymptotic algorithm for linear bandits that nearly achieves the information theoretic lower bound.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change Β· a person checks every report against the paper or source before anything changes; decisions are listed on /corrections