Copertina

Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Karpov, Nikolai, Wang, Chen
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Machine Learning Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
di: Assadi, Sepehr, et al.
Pubblicazione: (2023)

Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
di: Ye, Zichun, et al.
Pubblicazione: (2025)

Parallel Best Arm Identification in Heterogeneous Environments
di: Karpov, Nikolai, et al.
Pubblicazione: (2022)

Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits
di: Ye, Zichun, et al.
Pubblicazione: (2025)

Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits
di: He, Yuchen, et al.
Pubblicazione: (2024)

Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem
di: Blum, Avrim, et al.
Pubblicazione: (2024)

Tight Bounds for Learning Polyhedra with a Margin
di: Patel, Shyamal, et al.
Pubblicazione: (2026)

Tight Bounds for Answering Adaptively Chosen Concentrated Queries
di: Rapoport, Emma, et al.
Pubblicazione: (2025)

Unlearning Offline Stochastic Multi-Armed Bandits
di: Ye, Zichun, et al.
Pubblicazione: (2026)

Adversarial Attacks on Combinatorial Multi-Armed Bandits
di: Balasubramanian, Rishab, et al.
Pubblicazione: (2023)

A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
di: Fahrbach, Matthew, et al.
Pubblicazione: (2025)

Near-Optimal Algorithms for Omniprediction
di: Okoroafor, Princewill, et al.
Pubblicazione: (2025)

Stochastic Multi-Objective Multi-Armed Bandits: Regret Definition and Algorithm
di: Davoodi, Mansoor, et al.
Pubblicazione: (2025)

Linear Submodular Maximization with Bandit Feedback
di: Chen, Wenjing, et al.
Pubblicazione: (2024)

Stochastic $k$-Submodular Bandits with Full Bandit Feedback
di: Nie, Guanyu, et al.
Pubblicazione: (2024)

Nearly Tight Bounds for the Online Sorting Problem
di: Azar, Yossi, et al.
Pubblicazione: (2025)

Towards Optimal Differentially Private Regret Bounds in Linear MDPs
di: Sahu, Sharan
Pubblicazione: (2025)

Almost Tight Error Bounds on Differentially Private Continual Counting
di: Henzinger, Monika, et al.
Pubblicazione: (2022)

Nearly Optimal Bounds for Computing Decision Tree Splits in Data Streams
di: Ta, Hoang, et al.
Pubblicazione: (2026)

Ads that Stick: Near-Optimal Ad Optimization through Psychological Behavior Models
di: Darmasubramanian, Kailash Gopal, et al.
Pubblicazione: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
di: Fei, Yumou, et al.
Pubblicazione: (2026)

Tight Differentially Private PCA via Matrix Coherence
di: d'Orsi, Tommaso, et al.
Pubblicazione: (2025)

High-dimensional Linear Bandits with Knapsacks
di: Ma, Wanteng, et al.
Pubblicazione: (2023)

Introduction to Multi-Armed Bandits
di: Slivkins, Aleksandrs
Pubblicazione: (2019)

Stochastic Bandits with ReLU Neural Networks
di: Xu, Kan, et al.
Pubblicazione: (2024)

Semi-Bandit Learning for Monotone Stochastic Optimization
di: Agarwal, Arpit, et al.
Pubblicazione: (2023)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
di: Das, Syamantak, et al.
Pubblicazione: (2024)

Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
di: Dvijotham, Krishnamurthy, et al.
Pubblicazione: (2024)

MNL-Bandit with Knapsacks: a near-optimal algorithm
di: Aznag, Abdellah, et al.
Pubblicazione: (2021)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
di: Wang, Yichuan
Pubblicazione: (2024)

Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling
di: Qin, Hao, et al.
Pubblicazione: (2025)

The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
di: Ahmadian, Sara, et al.
Pubblicazione: (2025)

Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models
di: Diakonikolas, Ilias, et al.
Pubblicazione: (2025)

Towards Optimal Robustness in Learning-Augmented Paging
di: Chen, Peng, et al.
Pubblicazione: (2026)

Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure
di: Slivkins, Aleksandrs, et al.
Pubblicazione: (2025)

Spectral Guarantees for Adversarial Streaming PCA
di: Price, Eric, et al.
Pubblicazione: (2024)

Optimal Approximate Matrix Multiplication over Sliding Windows
di: Yao, Ziqi, et al.
Pubblicazione: (2025)

Learning-Augmented Streaming Algorithms for Correlation Clustering
di: Dong, Yinhao, et al.
Pubblicazione: (2025)

Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor
di: Aliakbarpour, Maryam, et al.
Pubblicazione: (2025)

Nearly Tight Bounds on Testing of Metric Properties
di: Bao, Yiqiao, et al.
Pubblicazione: (2024)