# Sequential Experimental Design for Transductive Linear Bandits

arXiv: https://arxiv.org/abs/1906.08399 · HTML: https://mlsanity.com/paper/1906.08399/

## Key facts

- Cited by 91 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2019.

## Built on by (most cited first, 30 of 91)

- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Leveraging Offline Data in Online Reinforcement Learning](https://mlsanity.com/paper/2211.04974/) (2022)
- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)
- [Contextual Bandits with Large Action Spaces: Made Practical](https://mlsanity.com/paper/2207.05836/) (2022)
- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [Active learning for data streams: a survey](https://mlsanity.com/paper/2302.08893/) (2023)
- [Information Directed Reward Learning for Reinforcement Learning](https://mlsanity.com/paper/2102.12466/) (2021)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Parallelizing Thompson Sampling](https://mlsanity.com/paper/2106.01420/) (2021)
- [Design of Experiments for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2107.09912/) (2021)
- [Near-Optimal Collaborative Learning in Bandits](https://mlsanity.com/paper/2206.00121/) (2022)
- [Nearly Optimal Algorithms for Level Set Estimation](https://mlsanity.com/paper/2111.01768/) (2021)
- [PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits](https://mlsanity.com/paper/2210.15345/) (2022)
- [Optimal Design for Human Preference Elicitation](https://mlsanity.com/paper/2404.13895/) (2024)
- [Active Learning with Safety Constraints](https://mlsanity.com/paper/2206.11183/) (2022)
- [Instance-optimal PAC Algorithms for Contextual Bandits](https://mlsanity.com/paper/2207.02357/) (2022)
- [Improved Algorithms for Agnostic Pool-based Active Classification](https://mlsanity.com/paper/2105.06499/) (2021)
- [Fast Rates in Pool-Based Batch Active Learning](https://mlsanity.com/paper/2202.05448/) (2022)
- [Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.11612/) (2021)
- [Pure Exploration in Kernel and Neural Bandits](https://mlsanity.com/paper/2106.12034/) (2021)
- [Collaborative Pure Exploration in Kernel Bandit](https://mlsanity.com/paper/2110.15771/) (2021)
- [Sample Efficient Demonstration Selection for In-Context Learning](https://mlsanity.com/paper/2506.08607/) (2025)
- [Targeted Active Learning for Bayesian Decision-Making](https://mlsanity.com/paper/2106.04193/) (2021)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [Norm-Agnostic Linear Bandits](https://mlsanity.com/paper/2205.01257/) (2022)
- [Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications](https://mlsanity.com/paper/2302.03683/) (2023)
- [Top-m identification for linear bandits](https://mlsanity.com/paper/2103.10070/) (2021)
- [Interactively Learning Preference Constraints in Linear Bandits](https://mlsanity.com/paper/2206.05255/) (2022)
- [Additive Causal Bandits with Unknown Graph](https://mlsanity.com/paper/2306.07858/) (2023)
- [Active Self-Supervised Learning: A Few Low-Cost Relationships Are All You Need](https://mlsanity.com/paper/2303.15256/) (2023)

## Abstract (arXiv)

In this paper we introduce the transductive linear bandit problem: given a set of measurement vectors Xsubset ℝd, a set of items Zsubset ℝd, a fixed confidence δ, and an unknown vector θast∈ ℝd, the goal is to infer argmaxz∈ Z z^topθ^ast with probability 1-δ by making as few sequentially chosen noisy measurements of the form x^topθast as possible. When X=Z, this setting generalizes linear bandits, and when X is the standard basis vectors and Zsubset 0,1d, 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 X 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 Z that can be safely administered to patients in vivo. Alternatively, in recommender systems for books, the set of books X a user is queried about may be restricted to well known best-sellers even though the goal might be to recommend more esoteric titles Z. 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.