# Minimal Exploration in Structured Stochastic Bandits

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Nov 2017.

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

- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/2107.01264/) (2021)
- [Fair Exploration via Axiomatic Bargaining](https://mlsanity.com/paper/2106.02553/) (2021)
- [Information Directed Sampling for Sparse Linear Bandits](https://mlsanity.com/paper/2105.14267/) (2021)
- [Near-Optimal Collaborative Learning in Bandits](https://mlsanity.com/paper/2206.00121/) (2022)
- [Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications](https://mlsanity.com/paper/2302.03683/) (2023)
- [Best Arm Identification with Fixed Budget: A Large Deviation Perspective](https://mlsanity.com/paper/2312.12137/) (2023)
- [Best-Arm Identification in Correlated Multi-Armed Bandits](https://mlsanity.com/paper/2109.04941/) (2021)
- [Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs](https://mlsanity.com/paper/2110.13876/) (2021)
- [Fast online inference for nonlinear contextual bandit based on Generative Adversarial Network](https://mlsanity.com/paper/2202.08867/) (2022)
- [Optimal Batched Linear Bandits](https://mlsanity.com/paper/2406.04137/) (2024)
- [Thompson Sampling for Bandits with Clustered Arms](https://mlsanity.com/paper/2109.01656/) (2021)
- [Causally Abstracted Multi-armed Bandits](https://mlsanity.com/paper/2404.17493/) (2024)
- [Multi-armed Bandit Algorithm against Strategic Replication](https://mlsanity.com/paper/2110.12160/) (2021)
- [On the Suboptimality of Thompson Sampling in High Dimensions](https://mlsanity.com/paper/2102.05502/) (2021)
- [Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time](https://mlsanity.com/paper/2102.07254/) (2021)
- [Indexed Minimum Empirical Divergence for Unimodal Bandits](https://mlsanity.com/paper/2112.01452/) (2021)
- [Quantum contextual bandits and recommender systems for quantum data](https://mlsanity.com/paper/2301.13524/) (2023)
- [Competing Bandits in Matching Markets via Super Stability](https://mlsanity.com/paper/2506.15926/) (2025)
- [FraPPE: Fast and Efficient Preference-based Pure Exploration](https://mlsanity.com/paper/2508.16487/) (2025)
- [SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits](https://mlsanity.com/paper/2301.12357/) (2023)
- [Matroid Semi-Bandits in Sublinear Time](https://mlsanity.com/paper/2405.17968/) (2024)
- [Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Model](https://mlsanity.com/paper/2207.05437/) (2022)
- [On the Complexity of Representation Learning in Contextual Linear Bandits](https://mlsanity.com/paper/2212.09429/) (2022)
- [Regret Minimization via Saddle Point Optimization](https://mlsanity.com/paper/2403.10379/) (2024)
- [A Complete Characterization of Learnability for Stochastic Noisy Bandits](https://mlsanity.com/paper/2410.09597/) (2024)
- [Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure](https://mlsanity.com/paper/2503.04010/) (2025)
- [Optimal Best-Arm Identification under Fixed Confidence with Multiple Optima](https://mlsanity.com/paper/2505.15643/) (2025)
- [Transfer Learning in Bandits with Latent Continuity](https://mlsanity.com/paper/2102.02472/) (2021)
- [Truncated LinUCB for Stochastic Linear Bandits](https://mlsanity.com/paper/2202.11735/) (2022)

## Abstract (arXiv)

This paper introduces and addresses a wide class of stochastic bandit problems where the function mapping the arm to the corresponding reward exhibits some known structural properties. Most existing structures (e.g. linear, Lipschitz, unimodal, combinatorial, dueling, ...) are covered by our framework. We derive an asymptotic instance-specific regret lower bound for these problems, and develop OSSB, an algorithm whose regret matches this fundamental limit. OSSB is not based on the classical principle of "optimism in the face of uncertainty" or on Thompson sampling, and rather aims at matching the minimal exploration rates of sub-optimal arms as characterized in the derivation of the regret lower bound. We illustrate the efficiency of OSSB using numerical experiments in the case of the linear bandit problem and show that OSSB outperforms existing algorithms, including Thompson sampling.