Research map / Learning theory and algorithms / Sample complexity
Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Murphy Sampling instead of LCB | Sequential minimum-mean testing on H_< · Gaussian bandit, K=10, means linearly spaced between -1 and 1 | sample complexity | Helped |
| Use Murphy Sampling instead of vanilla Thompson Sampling | Sequential minimum-mean testing on H_> · Gaussian bandit, K=5, means linearly spaced between 0.5 and 1 | sample complexity | Helped |
| Use the Aggregate stopping rule instead of Box | Sequential minimum-mean testing on H_< · Gaussian bandit, K=10, means linearly spaced between -1 and 1 | sample complexity | Helped |
| Use the Box stopping rule instead of GLRT | Sequential minimum-mean testing on H_< · Gaussian bandit, K=10, means linearly spaced between -1 and 1 | sample complexity | Helped |
| Aggregate samples from subsets of arms rather than use Box stopping | Murphy Sampling and LCB · Gaussian bandit, K=100, k arms with mean -1 and K-k arms with mean 0 | sample complexity | Helped |
| Use GLRT stopping instead of Aggregate stopping | Murphy Sampling and LCB · Gaussian bandit, K=100, k arms with mean -1 and K-k arms with mean 0 | sample complexity | Mixed |
| Use Aggregate stopping instead of GLRT | Murphy Sampling and LCB · Gaussian bandit, K=100, k arms linearly spaced between -1 and 0; remaining arms have mean 0 | sample complexity | Helped |
| Use Murphy Sampling instead of LCB | Sequential minimum-mean testing on H_< · Gaussian bandit, K=100, k arms with mean -1 and K-k arms with mean 0 | sample complexity | Helped |
| Use Murphy Sampling instead of regular Thompson Sampling | Sequential minimum-mean testing on H_> · Gaussian bandit, K=5, means linearly spaced between 0.5 and 1 | sampling proportions | Helped |
| Aggregate samples from subsets when constructing an upper confidence bound on the minimum | UCB Aggregate versus UCB Box · Bernoulli bandit with k arms of mean 0.1 and four arms with means [0.2 0.3 0.4 0.5] | upper confidence bound on the minimum | Helped |
Closest papers by meaning
- Testing the Feasibility of Linear Programs with Bandit Feedback (ICML 2024 · similarity 0.87)
- The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models (AAAI 2024 · similarity 0.87)
- Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.87)
- No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes (NeurIPS 2025 · similarity 0.87)
- Test-Time Regret Minimization in Meta Reinforcement Learning (ICML 2024 · similarity 0.87)
- On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference (ICML 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.