Cover Image

Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Slivkins, Aleksandrs, Xu, Yunzong, Zuo, Shiliang
Format:	Preprint
Published:	2025
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

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

Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning
by: Podimata, Chara, et al.
Published: (2020)

Bandit Social Learning: Exploration under Myopic Behavior
by: Banihashem, Kiarash, et al.
Published: (2023)

Incentivizing Exploration with Selective Data Disclosure
by: Immorlica, Nicole, et al.
Published: (2018)

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

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
by: Hanneke, Steve, et al.
Published: (2026)

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

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

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
by: Chen, Yixin, et al.
Published: (2026)

Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management
by: Hsieh, Wen-Han, et al.
Published: (2026)

No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting
by: Oki, Taihei, et al.
Published: (2024)

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
by: Fahrbach, Matthew, et al.
Published: (2024)

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

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

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

On the Robustness of the Successive Projection Algorithm
by: Barbarino, Giovanni, et al.
Published: (2024)

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

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

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

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

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

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

Connectivity Oracles for Predictable Vertex Failures
by: Hu, Bingbing, et al.
Published: (2023)

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

GreedyML: A Parallel Algorithm for Maximizing Constrained Submodular Functions
by: Gopal, Shivaram, et al.
Published: (2024)

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

A Characterization of List Regression
by: Pabbaraju, Chirag, et al.
Published: (2024)

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

Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover
by: Harris, Blake, et al.
Published: (2024)

Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedback
by: Pedramfar, Mohammad, et al.
Published: (2023)

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

Sublinear Time Algorithm for Online Weighted Bipartite Matching
by: Hu, Hang, et al.
Published: (2022)

A Faster $k$-means++ Algorithm
by: Liang, Jiehao, et al.
Published: (2022)

From Dynamic Programs to Greedy Algorithms
by: van Melkebeek, Dieter
Published: (2025)

A Competitive Algorithm for Agnostic Active Learning
by: Price, Eric, et al.
Published: (2023)

A Simple Approximation Algorithm for Optimal Decision Tree
by: Zhuo, Zhengjia, et al.
Published: (2025)

A Dynamic Algorithm for Weighted Submodular Cover Problem
by: Banihashem, Kiarash, et al.
Published: (2024)

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

A Threshold Greedy Algorithm for Noisy Submodular Maximization
by: Chen, Wenjing, et al.
Published: (2023)

A Provably Accurate Randomized Sampling Algorithm for Logistic Regression
by: Chowdhury, Agniva, et al.
Published: (2024)