PaperlayerView exact revision on arXiv

Source-linked AI summary

Sequential Experimental Design for Transductive Linear Bandits

Tanner Fiez, Lalit Jain, Kevin Jamieson, Lillian Ratliff

arXiv:1906.08399v1stat.MLcs.LG

TL;DR

Best-item identification is difficult when the available measurements differ from the items to be ranked. The paper formalizes this transductive setting and develops a sequential allocation algorithm. Its analysis provides matching upper and lower bounds, subject to a full-span assumption on the measurement set.

  • Problem

    The paper asks how to identify the best item when noisy measurements come from a probe set that can differ from the candidate items.

    Source: §1 · pp. 1–2

  • Method

    The paper develops an algorithm that sequentially chooses measurements from X to identify the best item in Z with high probability.

    Source: §1 · p. 2

  • Results

    The paper provides matching upper and lower bounds for best-arm identification in transductive linear bandits.

    Source: §6 · p. 10

  • Takeaways & Limitations

    The algorithm can be stopped early to return an ε-good arm.

    Source: §6 · p. 10

    The least-squares analysis assumes span(X)=R^d, a condition needed in general for unbiased estimates of differences between items.

    Source: §2.2 · p. 4

Abstract

from arXiv · show

In this paper we introduce the transductive linear bandit problem: given a set of measurement vectors $\mathcal{X}\subset \mathbb{R}^d$, a set of items $\mathcal{Z}\subset \mathbb{R}^d$, a fixed confidence $\delta$, and an unknown vector $\theta^{\ast}\in \mathbb{R}^d$, the goal is to infer $\text{argmax}_{z\in \mathcal{Z}} z^\top\theta^\ast$ with probability $1-\delta$ by making as few sequentially chosen noisy measurements of the form $x^\top\theta^{\ast}$ as possible. When $\mathcal{X}=\mathcal{Z}$, this setting generalizes linear bandits, and when $\mathcal{X}$ is the standard basis vectors and $\mathcal{Z}\subset \{0,1\}^d$, 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 $\mathcal{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 $\mathcal{Z}$ that can be safely administered to patients in vivo. Alternatively, in recommender systems for books, the set of books $\mathcal{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 $\mathcal{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.

1 Introduction

The introduction frames best-item identification when measurements may come from a different set than the items being ranked. It presents instance-dependent bounds and an adaptive algorithm, then situates the approach in applications and prior bandit settings.

1 Introduction

  • For X=Z, the problem recovers pure-exploration linear bandits; with standard-basis probes and binary item vectors, it recovers combinatorial bandits.In content recommendation, X=Z can represent songs queried directly, while disjoint X and Z can encode attributes used to assess homes.Source: §1 · p. 2
  • When X and Z differ, probes can be chosen for their information about items that are unavailable, unsafe, or impractical to test directly.Examples include testing unsafe compounds to predict among medically approved drugs, or querying affordable whiskies before recommending pricier ones.Source: §1 · p. 2
  • The goal is to identify the highest-response item in Z using noisy, sequential probes from X, which may differ from the items being ranked.The paper models an item's expected response as z^Tθ* and selects probes adaptively because their number and choice affect estimation accuracy.Source: §1 · pp. 1–2

1.1 Contributions

  • The paper gives instance-dependent lower bounds and an algorithm whose sample complexity matches the lower bound up to logarithmic factors.It also reports that the algorithm is empirically competitive with previous algorithms across a range of scenarios.Source: §1.1 · pp. 2–3

1.2 Notation

  • The notation defines pairwise arm-difference directions and an allocation criterion based on the worst-case induced norm over a direction set.Y(S) contains pairwise differences within S, while Y*(S) contains differences from the optimal arm to other arms.Source: §1.2 · p. 3

2 Transductive Linear Bandits Problem

The paper formalizes best-arm identification with measurements drawn from a known probe set and analyzes how to allocate those measurements. It contrasts an oracle-optimal static allocation with adaptive allocation, least-squares guarantees, and efficient rounding.

2 Transductive Linear Bandits Problem

  • The task is to identify the best item in Z with probability at least 1−δ while taking as few measurements from X as possible.The analysis assumes independent, zero-mean, 1-sub-Gaussian noise; the least-squares discussion assumes span(X)=R^d.Source: §2 · p. 3, §2.2 · p. 4

2.1 Optimal allocations

  • A static allocation attaining the lower bound depends on the unknown θ*, while a fixed allocation without that knowledge can require a factor of d more samples.The adaptive strategy instead allocates probes in rounds to remove arms whose gaps exceed successively smaller thresholds.Source: §2.1 · p. 4

2.2 Review of Least Squares

  • The least-squares argument shows that the oracle allocation separates the optimal arm from every suboptimal arm with probability at least 1−δ.The allocation λ* minimizes the bound driving the sample complexity; unbiased estimation of item differences requires span(X)=R^d.Source: §2.2 · pp. 4–5, §2.1 · p. 4

2.3 Rounding Procedures

  • Rounding converts a fractional allocation into an integer sample design while approximating the target directional variance within a factor of 1+ϵ.Naive rounding can use too few samples or exceed the total budget, whereas efficient procedures provide the stated approximation above a minimum sample threshold.Source: §2.3 · p. 5

3 Sequential Experimental Design for Transductive Linear Bandits

RAGE eliminates arms in successive rounds using measurements allocated to the active set’s pairwise differences. Its sample complexity matches the lower bound up to logarithmic factors, and a geometric example shows how adaptation can reduce dependence on the smallest gap.

3 Sequential Experimental Design for Transductive Linear Bandits

  • Each round allocates measurements to remove arms with gaps above a shrinking threshold, using pairwise differences among active arms to guide the allocation.The algorithm constructs confidence intervals for active-arm differences and removes arms whose empirical gaps exceed the round threshold.Source: §3 · pp. 5–6
  • With probability greater than 1 − δ, RAGE identifies the optimal arm with sample complexity matching the lower bound up to logarithmic factors.The bound is for an ϵ-efficient rounding procedure.Source: §3 · p. 6, §3.1 · p. 7
  • The sample-complexity bound sums the active-set costs across gap scales, with logarithmic factors and an additional rounding term.The rounding procedure can be chosen with r(ϵ) = O(d/ϵ^2).Source: §3 · p. 6

3.1 Interpreting the sample complexity.

  • For a singleton difference set, ρ(Y) is bounded by the inverse squared gauge, linking sample complexity to the geometry of the measurement set.The gauge is defined relative to conv(X ∪ −X).Source: §3.1 · p. 7
  • In the example with θ* = e1, after the first round only e1 and z′ remain, yielding complexity O(d log(log(1/α)d^2/δ)) rather than the static allocation’s d/α^2.The adaptive bound is independent of the gap up to logarithmic factors.Source: §3.1 · p. 7

4 Related Work

The section situates transductive pure exploration among linear, combinatorial, and multi-armed bandit work. It contrasts prior algorithms’ allocation strategies, sample-complexity behavior, and practical properties.

4 Related Work

  • Pure exploration for linear bandits with X = Z was introduced in and developed in, while combinatorial-bandit work studies X as the standard basis and Z ⊂ {0,1}^d [9] [7].When X = Z is the standard basis, the problem reduces to best-arm identification for multi-armed bandits [10].Source: §4 · p. 7
  • Soare et al. connect linear-bandit pure exploration to G-optimal design and provide passive and adaptive algorithms, but their adaptive sample complexity includes a term for removing suboptimal directions.Their adaptive method uses a greedy iterative allocation and does not discard provably suboptimal items.Source: §4 · pp. 7–8
  • Tao et al. develop alternative estimators and ALBA, whose sample complexity can overcount repeated gap directions and whose allocation is optimized over X rather than difference vectors.The paper notes that identical vectors among the smallest-gap arms need only be removed once.Source: §4 · p. 8
  • Karnin gives an asymptotically optimal algorithm as δ → 0, but its passive G-optimal exploration is described as impractical.LinGapE is fully adaptive and requires each arm to be pulled once; [21] extends it to generalized linear models, and studies transductive design computationally.Source: §4 · p. 8

5 Experiments

The simulations compare RAGE with adaptive and non-adaptive strategies across linear-bandit and transductive settings. RAGE is competitive in the benchmark, outperforms ALBA as the sphere example grows, and beats static allocation in the transductive example.

5 Experiments

  • The simulations use confidence δ = 0.05, and the empirical failure probability is zero for every algorithm in the presented simulations.RAGE uses Frank-Wolfe to find λt followed by a rounding procedure.Source: §5 · p. 8
  • On the benchmark linear-bandit example, RAGE performs competitively with existing algorithms and the oracle, while LinGapE falls behind as the number of arms grows.ALBA performs worst among the recently proposed algorithms, and adaptive sampling outperforms static XY-allocation.Source: §5 · p. 9, Figure 1 · p. 10
  • For many arms with moderate gaps, LinGapE’s sample count scales linearly with the number of arms because it samples each arm once.RAGE instead focuses on the informative x2 direction and gains information about nearly duplicate arms.Source: §5 · p. 9
  • RAGE significantly outperforms ALBA as the number of sphere-distributed arms increases, which the authors attribute primarily to ALBA optimizing over active vectors rather than their differences.The resulting ALBA sampling distribution can focus on a very different set of arms from the optimal one.Source: §5 · p. 9, Figure 1 · p. 10
  • In the transductive example, RAGE significantly outperforms static XY-allocation.Existing linear-bandit algorithms do not generalize to this setting; the comparison also includes an oracle allocation.Source: §5 · pp. 9–10, Figure 1 · p. 10

6 Conclusion

The paper proposes best-arm identification for transductive linear bandits and gives an algorithm with matching upper and lower bounds. It identifies open directions in anytime algorithms and extensions to regret and fixed-budget settings.

6 Conclusion

  • The paper proposes transductive best-arm identification, an algorithm, and matching upper and lower bounds.The algorithm can also be stopped early to return an ε-good arm.Source: §6 · p. 10
  • Anytime algorithms that do not discard samples remain an open direction for this problem.The paper contrasts this with work in pure-exploration multi-armed bandits.Source: §6 · p. 10
  • The authors suspect their algorithm matches the lower bound without the log(1/∆min) factor.Source: §6 · p. 10
  • The authors identify possible extensions to instance-based regret bounds for linear bandits and to fixed-budget settings.They leave both connections for future work.Source: §6 · p. 10

A Proof of Theorem 2

The proof establishes a high-probability good event across phases, where the optimal arm is retained and arms beyond the phase gap threshold are eliminated. It then sums phase sample bounds to obtain the stated sample-complexity guarantee.

A Proof of Theorem 2

  • On the good event, the active set contains the optimal arm and is restricted to arms whose gaps are below that phase's elimination threshold.For t > log2(1/∆min), the threshold set contains only the optimal arm.Source: A Proof of Theorem 2 · pp. 14–15
  • The proof bounds each phase's failure probability conditioned on prior good phases, then combines the events to obtain success probability at least 1 − δ.The overall probability bound is stated for phases through ⌈log2(1/∆min)⌉.Source: A Proof of Theorem 2 · pp. 14–15
  • Within a phase, a union bound over pairwise arm-difference vectors gives the confidence bound used to justify the elimination rule.The proof bounds the probability that any such vector exceeds the stated threshold by δt.Source: A Proof of Theorem 2 · p. 14
  • The theorem's sample-complexity bound follows by summing the per-phase sample bounds, which hold with probability at least 1 − δt.The proof obtains the phase bound conditioned on the preceding good event.Source: A Proof of Theorem 2 · pp. 14–15

B Efficient Rounding Procedures

The appendix describes rounding procedures that convert a continuous design into a finite sample allocation. It presents procedures from and [2], along with their stated efficiency conditions and guarantees.

B Efficient Rounding Procedures

  • The rounding discussion assumes that the measurement vectors span a d-dimensional space.Source: B Efficient Rounding Procedures · p. 16
  • A rounding procedure converts a design and sample count into a finite allocation whose total number of samples is N and whose discrepancy is controlled when N exceeds r(ε).Source: B Efficient Rounding Procedures · p. 16
  • The procedure from allocates integer pulls across the support of the design in two phases and has r(ε) = d^2/ε.The passage attributes the d^2 factor to the support size of λ.Source: B Efficient Rounding Procedures · p. 16
  • The rounding result from [2] gives a polynomial-time allocation guarantee with r(ε) = 180d/ε^2 under its stated conditions.The authors note that r(ε) = d/ε^2 may suffice, but say they are unaware of such a result in the literature.Source: B Efficient Rounding Procedures · p. 17

C Proof of Theorem 1

The proof of the lower bound compares the best arm with alternatives under a δ-PAC strategy. It uses the sampling design and a transportation lemma to relate pull counts to distinguishing parameter instances.

C Proof of Theorem 1

  • The proof designates z1 as an optimal item and defines alternatives through parameters under which z1 is no longer best.Source: C Proof of Theorem 1 · p. 17
  • The transportation lemma relates the pull counts under a δ-PAC strategy to distinguishing the instance from an alternative.The passage defines Ti as the random number of times arm i is pulled and νθ,i as its reward distribution.Source: C Proof of Theorem 1 · p. 17
  • The sampling design enters through A(λ) = Σ_i λ_i x_i x_i^⊤ in the proof's comparison of alternatives.Source: C Proof of Theorem 1 · p. 18

D Proof of Proposition 1

The proof constructs paired hypotheses in an even-dimensional Gaussian-noise instance and uses testing requirements across all pairs to obtain a sample lower bound.

D Proof of Proposition 1

  • The construction assumes even d, standard normal noise, and an angle α ∈ (0, 1) in an instance with X = Z formed from standard basis vectors.The proof later relates α to γ.Source: D Proof of Proposition 1 · p. 18
  • Distinguishing θ = z_j from θ = z_{j+d/2} requires N_j + N_{j+d/2} ≥ c log(1/δ)(1 − cos(α))² samples for each j ≤ d/2, for universal c > 0.The proof uses standard Le Cam arguments.Source: D Proof of Proposition 1 · p. 18
  • Because the pairwise requirements must hold simultaneously for all d/2 pairs under one static allocation, and (1 − cos(α))^2 ≈ α^4/4, they yield the stated result.Source: D Proof of Proposition 1 · p. 18

E Proof of Lemma 1

The proof uses a vertex property of convex functions and invokes G-optimal design and Elfving’s theorem in deriving design bounds.

E Proof of Lemma 1

  • A convex function on a convex set attains its maximum at a vertex, which justifies the third equality in the proof.Source: E Proof of Lemma 1 · p. 19
  • The proof invokes the Kiefer-Wolfowitz theorem for G-optimal design in its design argument.The passage also gives an optimization over measurement vectors, but its expression is incomplete.Source: E Proof of Lemma 1 · p. 19
  • For the singleton case, the final statement is identified as Elfving’s Theorem, with a reference to Section 2.14 in.Source: E Proof of Lemma 1 · p. 19

F Experiment Details

The experiments report mean sample complexity over repeated simulations and specify implementation choices for the evaluated algorithms, including design optimization and allocation procedures.

F Experiment Details

  • Experiments were repeated 20 times, with mean sample complexity and standard-error bars reported under standard normal observation noise.Simulations used Python 3 and were parallelized on an Intel Xeon E5-2690.Source: F Experiment Details · p. 19
  • RAGE, XY-Static, XY-Oracle, and ALBA compute designs with Franke-Wolfe optimization, stopping at relative change below .01 or 1000 iterations, then thresholding and rescaling λ.Values below 10^-5 are set to zero and λ is scaled to sum to 1.Source: F Experiment Details · p. 19
  • XY-Adaptive uses α = 0.1 and greedy arm selection, without resetting the active arm set after a phase, matching the simulations in.Its confidence interval uses the phase index rather than the sample count.Source: F Experiment Details · pp. 19–20
  • XY-Static and XY-Oracle use optimal designs on Y(Z) and gap-normalized Y*(Z), respectively, and sample from their allocations in phases.The value of v was optimized in (1, 2), and the stopping condition is checked at each phase end.Source: F Experiment Details · p. 20
  • LinGapE is run with ε = 0 for exact identification and in its analyzed form, rather than the greedy procedure used in its paper’s simulations.The authors note that their simulations may differ from because its code uses ε equal to the minimum gap, unknown in advance.Source: F Experiment Details · p. 20
  • ALBA uses Y-ElimTil for improved empirical results, while RAGE uses a rounding procedure and has at most ⌊log2(1/Δ_min)⌋ phases.The RAGE phases require design optimization, rounding, and least-squares estimation.Source: F Experiment Details · p. 20

Related papers

Loading 1906.08399v1…