Kevin Jamieson
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Kevin Jamieson has a total of 58 co-authors. Here are the top co-authors by number of shared publications:
Andrew Wagenmaker
University of California Berkeley
10 shared publications- Lillian J. Ratliff
University of Washington
5 shared publications - Arnab Maiti
University of Washington
4 shared publications - Lalit Jain
University of Washington Seattle WA
4 shared publications - Simon Shaolei Du
Tsinghua University University of Washington University of Washington University of Washington
4 shared publications - Yifang Chen
University of Washington Seattle
4 shared publications
Latest Publications
- Open Access
- 12 September 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Economics and Computation
- Vol. 13 (3) , 1-18
Query-Efficient Algorithm to Find all Nash Equilibria in a Two-Player Zero-Sum Matrix Game
We study the query complexity of finding the set of all Nash equilibria \(\mathcal {X}_\star \unicode{x00D7} \mathcal {Y}_\star\) in two-player zero-sum matrix games. Fearnley and Savani [ 18 ] showed that for any randomized algorithm, there exists an n × n input matrix where it needs to query Ω ( n 2 ) entries in expectation to compute a single Nash equilibrium. On the other hand, Bienstock et al. [ 5 ] showed that there is a special class of matrices for which one can query O(n) entries and compute its set of all Nash equilibria. However, these results do not fully characterize the query complexity of finding the set of all Nash equilibria in two-player zero-sum matrix games. In this work, we characterize the query complexity of finding the set of all Nash equilibria \(\mathcal {X}_\star \unicode{x00D7} \mathcal {Y}_\star\) in terms of the number of rows n of the input matrix \(A \in \mathbb {R}^{n \unicode{x00D7} n}\) , row support size \(k_1 := |\bigcup \nolimits _{x \in \mathcal {X}_\star } \text{supp}(x)|\) , and column support size \(k_2 := |\bigcup \nolimits _{y \in \mathcal {Y}_\star } \text{supp}(y)|\) . We design a simple yet non-trivial randomized algorithm that returns the set of all Nash equilibria \(\mathcal {X}_\star \unicode{x00D7} \mathcal {Y}_\star\) by querying at most \(O(nk^5 \cdot \text{polylog}(n))\) entries of the input matrix \(A \in \mathbb {R}^{n \unicode{x00D7} n}\) in expectation, where \(k := \max \lbrace k_1, k_2\rbrace\) . This upper bound is tight up to a factor of poly( k ), as we show that for any randomized algorithm, there exists an n × n input matrix with \(\min \lbrace k_1, k_2\rbrace = 1\) , for which it needs to query Ω ( nk ) entries in expectation in order to find the set of all Nash equilibria \(\mathcal {X}_\star \unicode{x00D7} \mathcal {Y}_\star\) .- 12 September 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Economics and Computation
- Vol. 13 (3) , 1-18
Open AccessQuery-Efficient Algorithm to Find all Nash Equilibria in a Two-Player Zero-Sum Matrix Game
We study the query complexity of finding the set of all Nash equilibria \(\mathcal {X}_\star \unicode{x00D7} \mathcal {Y}_\star\) in two-player zero-sum matrix games. Fearnley and Savani [ 18 ] showed that for any randomized algorithm, there exists an n × n input matrix where it needs to query Ω ( n 2 ) entries in expectation to compute a single Nash equilibrium. On the other hand, Bienstock et al. [ 5 ] showed that there is a special class of matrices for which one can query O(n) entries and compute its set of all Nash equilibria. However, these results do not fully characterize the query complexity of finding the set of all Nash equilibria in two-player zero-sum matrix games. In this work, we characterize the query complexity of finding the set of all Nash equilibria \(\mathcal {X}_\star \unicode{x00D7} \mathcal {Y}_\star\) in terms of the number of rows n of the input matrix \(A \in \mathbb {R}^{n \unicode{x00D7} n}\) , row support size \(k_1 := |\bigcup \nolimits _{x \in \mathcal {X}_\star } \text{supp}(x)|\) , and column support size \(k_2 := |\bigcup \nolimits _{y \in \mathcal {Y}_\star } \text{supp}(y)|\) . We design a simple yet non-trivial randomized algorithm that returns the set of all Nash equilibria \(\mathcal {X}_\star \unicode{x00D7} \mathcal {Y}_\star\) by querying at most \(O(nk^5 \cdot \text{polylog}(n))\) entries of the input matrix \(A \in \mathbb {R}^{n \unicode{x00D7} n}\) in expectation, where \(k := \max \lbrace k_1, k_2\rbrace\) . This upper bound is tight up to a factor of poly( k ), as we show that for any randomized algorithm, there exists an n × n input matrix with \(\min \lbrace k_1, k_2\rbrace = 1\) , for which it needs to query Ω ( nk ) entries in expectation in order to find the set of all Nash equilibria \(\mathcal {X}_\star \unicode{x00D7} \mathcal {Y}_\star\) . - 1 September 2025
- Published by Springer Nature
- p. 3-20
On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games Under Noisy Feedback
- 1 September 2025
- Published by Springer Nature
- p. 3-20
On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games Under Noisy Feedback
- Open Access
Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RL
In order to mitigate the sample complexity of real-world reinforcement learning, common practice is to first train a policy in a simulator where samples are cheap, and then deploy this policy in the real world, with the hope that it generalizes effectively. Such \emph{direct sim2real} transfer is not guaranteed to succeed, however, and in cases where it fails, it is unclear how to best utilize the simulator. In this work, we show that in many regimes, while direct sim2real transfer may fail, we can utilize the simulator to learn a set of \emph{exploratory} policies which enable efficient exploration in the real world. In particular, in the setting of low-rank MDPs, we show that coupling these exploratory policies with simple, practical approaches -- least-squares regression oracles and naive randomized exploration -- yields a polynomial sample complexity in the real world, an exponential improvement over direct sim2real transfer, or learning without access to a simulator. To the best of our knowledge, this is the first evidence that simulation transfer yields a provable gain in reinforcement learning in settings where direct sim2real transfer fails. We validate our theoretical results on several realistic robotic simulators and a real-world robotic sim2real task, demonstrating that transferring exploratory policies can yield substantial gains in practice as well.
Open AccessOvercoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RL
In order to mitigate the sample complexity of real-world reinforcement learning, common practice is to first train a policy in a simulator where samples are cheap, and then deploy this policy in the real world, with the hope that it generalizes effectively. Such \emph{direct sim2real} transfer is not guaranteed to succeed, however, and in cases where it fails, it is unclear how to best utilize the simulator. In this work, we show that in many regimes, while direct sim2real transfer may fail, we can utilize the simulator to learn a set of \emph{exploratory} policies which enable efficient exploration in the real world. In particular, in the setting of low-rank MDPs, we show that coupling these exploratory policies with simple, practical approaches -- least-squares regression oracles and naive randomized exploration -- yields a polynomial sample complexity in the real world, an exponential improvement over direct sim2real transfer, or learning without access to a simulator. To the best of our knowledge, this is the first evidence that simulation transfer yields a provable gain in reinforcement learning in settings where direct sim2real transfer fails. We validate our theoretical results on several realistic robotic simulators and a real-world robotic sim2real task, demonstrating that transferring exploratory policies can yield substantial gains in practice as well.
- Open Access
- 2 August 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Recommender Systems
- Vol. 3 (1) , 1-22
Unbiased Identification of Broadly Appealing Content Using a Pure Exploration Infinitely Armed Bandit Strategy
Podcasting is an increasingly popular medium for entertainment and discourse around the world, with tens of thousands of new podcasts released on a monthly basis. We consider the problem of identifying from these newly released podcasts those with the largest potential audiences so they can be considered for personalized recommendation to users. We first study and then discard a supervised approach due to the inadequacy of either content or consumption features for this task and instead propose a novel non-contextual bandit algorithm in the fixed-budget infinitely armed pure-exploration setting. We demonstrate that our algorithm is well suited to the best-arm identification task for a broad class of arm reservoir distributions, out-competing a large number of state-of-the-art algorithms. We then apply the algorithm to identifying podcasts with broad appeal in a simulated study and show that it efficiently sorts podcasts into groups by increasing appeal while avoiding the popularity bias inherent in supervised approaches. Finally, we study a setting in which users are more likely to stream more-streamed podcasts independent of their general appeal and find that our proposed algorithm is robust to this type of popularity bias. 1
- 2 August 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Recommender Systems
- Vol. 3 (1) , 1-22
Open AccessUnbiased Identification of Broadly Appealing Content Using a Pure Exploration Infinitely Armed Bandit Strategy
Podcasting is an increasingly popular medium for entertainment and discourse around the world, with tens of thousands of new podcasts released on a monthly basis. We consider the problem of identifying from these newly released podcasts those with the largest potential audiences so they can be considered for personalized recommendation to users. We first study and then discard a supervised approach due to the inadequacy of either content or consumption features for this task and instead propose a novel non-contextual bandit algorithm in the fixed-budget infinitely armed pure-exploration setting. We demonstrate that our algorithm is well suited to the best-arm identification task for a broad class of arm reservoir distributions, out-competing a large number of state-of-the-art algorithms. We then apply the algorithm to identifying podcasts with broad appeal in a simulated study and show that it efficiently sorts podcasts into groups by increasing appeal while avoiding the popularity bias inherent in supervised approaches. Finally, we study a setting in which users are more likely to stream more-streamed podcasts independent of their general appeal and find that our proposed algorithm is robust to this type of popularity bias. 1
- Open Access
LabelBench: A Comprehensive Framework for Benchmarking Adaptive Label-Efficient Learning
Labeled data are critical to modern machine learning applications, but obtaining labels can be expensive. To mitigate this cost, machine learning methods, such as transfer learning, semi-supervised learning and active learning, aim to be label-efficient: achieving high predictive performance from relatively few labeled examples. While obtaining the best label-efficiency in practice often requires combinations of these techniques, existing benchmark and evaluation frameworks do not capture a concerted combination of all such techniques. This paper addresses this deficiency by introducing LabelBench, a new computationally-efficient framework for joint evaluation of multiple label-efficient learning techniques. As an application of LabelBench, we introduce a novel benchmark of state-of-the-art active learning methods in combination with semi-supervised learning for fine-tuning pretrained vision transformers. Our benchmark demonstrates better label-efficiencies than previously reported in active learning. LabelBench's modular codebase is open-sourced for the broader community to contribute label-efficient learning methods and benchmarks. The repository can be found at: https://github.com/EfficientTraining/LabelBench.
Open AccessLabelBench: A Comprehensive Framework for Benchmarking Adaptive Label-Efficient Learning
Labeled data are critical to modern machine learning applications, but obtaining labels can be expensive. To mitigate this cost, machine learning methods, such as transfer learning, semi-supervised learning and active learning, aim to be label-efficient: achieving high predictive performance from relatively few labeled examples. While obtaining the best label-efficiency in practice often requires combinations of these techniques, existing benchmark and evaluation frameworks do not capture a concerted combination of all such techniques. This paper addresses this deficiency by introducing LabelBench, a new computationally-efficient framework for joint evaluation of multiple label-efficient learning techniques. As an application of LabelBench, we introduce a novel benchmark of state-of-the-art active learning methods in combination with semi-supervised learning for fine-tuning pretrained vision transformers. Our benchmark demonstrates better label-efficiencies than previously reported in active learning. LabelBench's modular codebase is open-sourced for the broader community to contribute label-efficient learning methods and benchmarks. The repository can be found at: https://github.com/EfficientTraining/LabelBench.
- Open Access
A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity
We investigate the fixed-budget best-arm identification (BAI) problem for linear bandits in a potentially non-stationary environment. Given a finite arm set $\mathcal{X}\subset\mathbb{R}^d$, a fixed budget $T$, and an unpredictable sequence of parameters $\left\lbraceθ_t\right\rbrace_{t=1}^{T}$, an algorithm will aim to correctly identify the best arm $x^* := \arg\max_{x\in\mathcal{X}}x^\top\sum_{t=1}^{T}θ_t$ with probability as high as possible. Prior work has addressed the stationary setting where $θ_t = θ_1$ for all $t$ and demonstrated that the error probability decreases as $\exp(-T /ρ^*)$ for a problem-dependent constant $ρ^*$. But in many real-world $A/B/n$ multivariate testing scenarios that motivate our work, the environment is non-stationary and an algorithm expecting a stationary setting can easily fail. For robust identification, it is well-known that if arms are chosen randomly and non-adaptively from a G-optimal design over $\mathcal{X}$ at each time then the error probability decreases as $\exp(-TΔ^2_{(1)}/d)$, where $Δ_{(1)} = \min_{x \neq x^*} (x^* - x)^\top \frac{1}{T}\sum_{t=1}^T θ_t$. As there exist environments where $Δ_{(1)}^2/ d \ll 1/ ρ^*$, we are motivated to propose a novel algorithm $\mathsf{P1}$-$\mathsf{RAGE}$ that aims to obtain the best of both worlds: robustness to non-stationarity and fast rates of identification in benign settings. We characterize the error probability of $\mathsf{P1}$-$\mathsf{RAGE}$ and demonstrate empirically that the algorithm indeed never performs worse than G-optimal design but compares favorably to the best algorithms in the stationary setting.Open AccessA/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity
We investigate the fixed-budget best-arm identification (BAI) problem for linear bandits in a potentially non-stationary environment. Given a finite arm set $\mathcal{X}\subset\mathbb{R}^d$, a fixed budget $T$, and an unpredictable sequence of parameters $\left\lbraceθ_t\right\rbrace_{t=1}^{T}$, an algorithm will aim to correctly identify the best arm $x^* := \arg\max_{x\in\mathcal{X}}x^\top\sum_{t=1}^{T}θ_t$ with probability as high as possible. Prior work has addressed the stationary setting where $θ_t = θ_1$ for all $t$ and demonstrated that the error probability decreases as $\exp(-T /ρ^*)$ for a problem-dependent constant $ρ^*$. But in many real-world $A/B/n$ multivariate testing scenarios that motivate our work, the environment is non-stationary and an algorithm expecting a stationary setting can easily fail. For robust identification, it is well-known that if arms are chosen randomly and non-adaptively from a G-optimal design over $\mathcal{X}$ at each time then the error probability decreases as $\exp(-TΔ^2_{(1)}/d)$, where $Δ_{(1)} = \min_{x \neq x^*} (x^* - x)^\top \frac{1}{T}\sum_{t=1}^T θ_t$. As there exist environments where $Δ_{(1)}^2/ d \ll 1/ ρ^*$, we are motivated to propose a novel algorithm $\mathsf{P1}$-$\mathsf{RAGE}$ that aims to obtain the best of both worlds: robustness to non-stationarity and fast rates of identification in benign settings. We characterize the error probability of $\mathsf{P1}$-$\mathsf{RAGE}$ and demonstrate empirically that the algorithm indeed never performs worse than G-optimal design but compares favorably to the best algorithms in the stationary setting. - Open Access
Fair Active Learning in Low-Data Regimes
In critical machine learning applications, ensuring fairness is essential to avoid perpetuating social inequities. In this work, we address the challenges of reducing bias and improving accuracy in data-scarce environments, where the cost of collecting labeled data prohibits the use of large, labeled datasets. In such settings, active learning promises to maximize marginal accuracy gains of small amounts of labeled data. However, existing applications of active learning for fairness fail to deliver on this, typically requiring large labeled datasets, or failing to ensure the desired fairness tolerance is met on the population distribution. To address such limitations, we introduce an innovative active learning framework that combines an exploration procedure inspired by posterior sampling with a fair classification subroutine. We demonstrate that this framework performs effectively in very data-scarce regimes, maximizing accuracy while satisfying fairness constraints with high probability. We evaluate our proposed approach using well-established real-world benchmark datasets and compare it against state-of-the-art methods, demonstrating its effectiveness in producing fair models, and improvement over existing methods.
Open AccessFair Active Learning in Low-Data Regimes
In critical machine learning applications, ensuring fairness is essential to avoid perpetuating social inequities. In this work, we address the challenges of reducing bias and improving accuracy in data-scarce environments, where the cost of collecting labeled data prohibits the use of large, labeled datasets. In such settings, active learning promises to maximize marginal accuracy gains of small amounts of labeled data. However, existing applications of active learning for fairness fail to deliver on this, typically requiring large labeled datasets, or failing to ensure the desired fairness tolerance is met on the population distribution. To address such limitations, we introduce an innovative active learning framework that combines an exploration procedure inspired by posterior sampling with a fair classification subroutine. We demonstrate that this framework performs effectively in very data-scarce regimes, maximizing accuracy while satisfying fairness constraints with high probability. We evaluate our proposed approach using well-established real-world benchmark datasets and compare it against state-of-the-art methods, demonstrating its effectiveness in producing fair models, and improvement over existing methods.
- Open Access
Near-Optimal Pure Exploration in Matrix Games: A Generalization of Stochastic Bandits & Dueling Bandits
We study the sample complexity of identifying the pure strategy Nash equilibrium (PSNE) in a two-player zero-sum matrix game with noise. Formally, we are given a stochastic model where any learner can sample an entry $(i,j)$ of the input matrix $A\in[-1,1]^{n\times m}$ and observe $A_{i,j}+η$ where $η$ is a zero-mean 1-sub-Gaussian noise. The aim of the learner is to identify the PSNE of $A$, whenever it exists, with high probability while taking as few samples as possible. Zhou et al. (2017) presents an instance-dependent sample complexity lower bound that depends only on the entries in the row and column in which the PSNE lies. We design a near-optimal algorithm whose sample complexity matches the lower bound, up to log factors. The problem of identifying the PSNE also generalizes the problem of pure exploration in stochastic multi-armed bandits and dueling bandits, and our result matches the optimal bounds, up to log factors, in both the settings.Open AccessNear-Optimal Pure Exploration in Matrix Games: A Generalization of Stochastic Bandits & Dueling Bandits
We study the sample complexity of identifying the pure strategy Nash equilibrium (PSNE) in a two-player zero-sum matrix game with noise. Formally, we are given a stochastic model where any learner can sample an entry $(i,j)$ of the input matrix $A\in[-1,1]^{n\times m}$ and observe $A_{i,j}+η$ where $η$ is a zero-mean 1-sub-Gaussian noise. The aim of the learner is to identify the PSNE of $A$, whenever it exists, with high probability while taking as few samples as possible. Zhou et al. (2017) presents an instance-dependent sample complexity lower bound that depends only on the entries in the row and column in which the PSNE lies. We design a near-optimal algorithm whose sample complexity matches the lower bound, up to log factors. The problem of identifying the PSNE also generalizes the problem of pure exploration in stochastic multi-armed bandits and dueling bandits, and our result matches the optimal bounds, up to log factors, in both the settings. - Open Access
Optimal Exploration is no harder than Thompson Sampling
Given a set of arms $\mathcal{Z}\subset \mathbb{R}^d$ and an unknown parameter vector $θ_\ast\in\mathbb{R}^d$, the pure exploration linear bandit problem aims to return $\arg\max_{z\in \mathcal{Z}} z^{\top}θ_{\ast}$, with high probability through noisy measurements of $x^{\top}θ_{\ast}$ with $x\in \mathcal{X}\subset \mathbb{R}^d$. Existing (asymptotically) optimal methods require either a) potentially costly projections for each arm $z\in \mathcal{Z}$ or b) explicitly maintaining a subset of $\mathcal{Z}$ under consideration at each time. This complexity is at odds with the popular and simple Thompson Sampling algorithm for regret minimization, which just requires access to a posterior sampling and argmax oracle, and does not need to enumerate $\mathcal{Z}$ at any point. Unfortunately, Thompson sampling is known to be sub-optimal for pure exploration. In this work, we pose a natural question: is there an algorithm that can explore optimally and only needs the same computational primitives as Thompson Sampling? We answer the question in the affirmative. We provide an algorithm that leverages only sampling and argmax oracles and achieves an exponential convergence rate, with the exponent being the optimal among all possible allocations asymptotically. In addition, we show that our algorithm can be easily implemented and performs as well empirically as existing asymptotically optimal methods.Open AccessOptimal Exploration is no harder than Thompson Sampling
Given a set of arms $\mathcal{Z}\subset \mathbb{R}^d$ and an unknown parameter vector $θ_\ast\in\mathbb{R}^d$, the pure exploration linear bandit problem aims to return $\arg\max_{z\in \mathcal{Z}} z^{\top}θ_{\ast}$, with high probability through noisy measurements of $x^{\top}θ_{\ast}$ with $x\in \mathcal{X}\subset \mathbb{R}^d$. Existing (asymptotically) optimal methods require either a) potentially costly projections for each arm $z\in \mathcal{Z}$ or b) explicitly maintaining a subset of $\mathcal{Z}$ under consideration at each time. This complexity is at odds with the popular and simple Thompson Sampling algorithm for regret minimization, which just requires access to a posterior sampling and argmax oracle, and does not need to enumerate $\mathcal{Z}$ at any point. Unfortunately, Thompson sampling is known to be sub-optimal for pure exploration. In this work, we pose a natural question: is there an algorithm that can explore optimally and only needs the same computational primitives as Thompson Sampling? We answer the question in the affirmative. We provide an algorithm that leverages only sampling and argmax oracles and achieves an exponential convergence rate, with the exponent being the optimal among all possible allocations asymptotically. In addition, we show that our algorithm can be easily implemented and performs as well empirically as existing asymptotically optimal methods. - Open Access
Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design
While much progress has been made in understanding the minimax sample complexity of reinforcement learning (RL) -- the complexity of learning on the "worst-case" instance -- such measures of complexity often do not capture the true difficulty of learning. In practice, on an "easy" instance, we might hope to achieve a complexity far better than that achievable on the worst-case instance. In this work we seek to understand the "instance-dependent" complexity of learning near-optimal policies (PAC RL) in the setting of RL with linear function approximation. We propose an algorithm, \textsc{Pedel}, which achieves a fine-grained instance-dependent measure of complexity, the first of its kind in the RL with function approximation setting, thereby capturing the difficulty of learning on each particular problem instance. Through an explicit example, we show that \textsc{Pedel} yields provable gains over low-regret, minimax-optimal algorithms and that such algorithms are unable to hit the instance-optimal rate. Our approach relies on a novel online experiment design-based procedure which focuses the exploration budget on the "directions" most relevant to learning a near-optimal policy, and may be of independent interest.
Open AccessInstance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design
While much progress has been made in understanding the minimax sample complexity of reinforcement learning (RL) -- the complexity of learning on the "worst-case" instance -- such measures of complexity often do not capture the true difficulty of learning. In practice, on an "easy" instance, we might hope to achieve a complexity far better than that achievable on the worst-case instance. In this work we seek to understand the "instance-dependent" complexity of learning near-optimal policies (PAC RL) in the setting of RL with linear function approximation. We propose an algorithm, \textsc{Pedel}, which achieves a fine-grained instance-dependent measure of complexity, the first of its kind in the RL with function approximation setting, thereby capturing the difficulty of learning on each particular problem instance. Through an explicit example, we show that \textsc{Pedel} yields provable gains over low-regret, minimax-optimal algorithms and that such algorithms are unable to hit the instance-optimal rate. Our approach relies on a novel online experiment design-based procedure which focuses the exploration budget on the "directions" most relevant to learning a near-optimal policy, and may be of independent interest.