Search for: All records

Creators/Authors contains: "Jamieson, Kevin"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Free, publicly-accessible full text available July 10, 2027
  2. Free, publicly-accessible full text available July 2, 2027
  3. We study the fixed-budget best-arm identification (BAI) problem in non-stationary linear bandits. Concretely, given a fixed time budget T, finite arm set X (in d dimensions), and a potentially adversarial sequence of unknown parameters \theta_t, t=1,...T (hence non-stationary), a learner aims to identify the arm with the largest cumulative reward with high probability. In this setting, it is well-known that i.i.d. sampling arms from the G-optimal design yields a minimax-optimal error probability of exp (-\Theta(T/H)), where H scales proportionally with the dimension d. However, this notion of complexity is overly pessimistic, as it is derived from a lower bound in which the arm set consists only of the standard basis vectors, thus masking any potential advantages arising from arm sets with richer geometric structure. To address this, we establish an arm-set-dependent lower bound that, in contrast, holds for any arm set. Motivated by the ideas underlying our lower bound, we propose the Adjacent-optimal design, a specialization of the well-known XY-optimal design, and develop the Adjacent-BAI algorithm. We prove that the error probability of Adjacent-BAI matches our lower bound up to constants, verifying the tightness of our lower bound, and establishing the arm-set-dependent complexity of this setting. 
    more » « less
    Free, publicly-accessible full text available June 29, 2027
  4. Free, publicly-accessible full text available May 2, 2027
  5. Free, publicly-accessible full text available May 1, 2027
  6. Free, publicly-accessible full text available June 1, 2027
  7. This paper studies last-iterate convergence for uncoupled learning dynamics in bilinear saddle-point problems under bandit feedback. 
    more » « less
    Free, publicly-accessible full text available May 2, 2027
  8. Free, publicly-accessible full text available May 2, 2027
  9. Free, publicly-accessible full text available May 2, 2027
  10. Free, publicly-accessible full text available May 1, 2027