Cover Image

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Assadi, Sepehr, Wang, Chen
Format:	Preprint
Published:	2023
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap
by: Karpov, Nikolai, et al.
Published: (2025)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
by: Assadi, Sepehr
Published: (2024)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
by: Assadi, Sepehr, et al.
Published: (2024)

On the Problem of Best Arm Retention
by: Chen, Houshuang, et al.
Published: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
by: Assadi, Sepehr
Published: (2023)

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

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

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

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
by: Assadi, Sepehr, et al.
Published: (2024)

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $Δ$-Coloring
by: Assadi, Sepehr, et al.
Published: (2022)

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

An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication
by: Assadi, Sepehr, et al.
Published: (2025)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
by: Assadi, Sepehr, et al.
Published: (2026)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
by: Assadi, Sepehr, et al.
Published: (2025)

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

Coloring Graphs with Few Colors in the Streaming Model
by: Assadi, Sepehr, et al.
Published: (2025)

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

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

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

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

Streaming and Communication Complexity of Load-Balancing via Matching Contractors
by: Assadi, Sepehr, et al.
Published: (2024)

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

Vizing's Theorem in Near-Linear Time
by: Assadi, Sepehr, et al.
Published: (2024)

Lower Bounds for the Algorithmic Complexity of Learned Indexes
by: Croquevielle, Luis Alberto, et al.
Published: (2026)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
by: Assadi, Sepehr, et al.
Published: (2025)

Covering Approximate Shortest Paths with DAGs
by: Assadi, Sepehr, et al.
Published: (2025)

Statistical Query Lower Bounds for Smoothed Agnostic Learning
by: Diakonikolas, Ilias, et al.
Published: (2026)

Introduction to Multi-Armed Bandits
by: Slivkins, Aleksandrs
Published: (2019)

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

Fast, robust approximate message passing
by: Ivkov, Misha, et al.
Published: (2024)

A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature
by: Gu, Xiang, et al.
Published: (2026)

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

Near-optimal Swap Regret Minimization for Convex Losses
by: Hu, Lunjia, et al.
Published: (2026)

Near-optimal Active Regression of Single-Index Models
by: Li, Yi, et al.
Published: (2025)

Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
by: Klivans, Adam R., et al.
Published: (2024)

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

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

Lower Bounds for Greedy Teaching Set Constructions
by: Compton, Spencer, et al.
Published: (2025)

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