Buchumschlag

Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Blum, Avrim, Ravichandran, Kavya
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Machine Learning Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

A Model for Combinatorial Dictionary Learning and Inference
von: Blum, Avrim, et al.
Veröffentlicht: (2024)

Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem
von: Blum, Avrim, et al.
Veröffentlicht: (2025)

Competitive strategies to use "warm start" algorithms with predictions
von: Srinivas, Vaidehi, et al.
Veröffentlicht: (2024)

Adversarial Attacks on Combinatorial Multi-Armed Bandits
von: Balasubramanian, Rishab, et al.
Veröffentlicht: (2023)

Unlearning Offline Stochastic Multi-Armed Bandits
von: Ye, Zichun, et al.
Veröffentlicht: (2026)

Stochastic Multi-Objective Multi-Armed Bandits: Regret Definition and Algorithm
von: Davoodi, Mansoor, et al.
Veröffentlicht: (2025)

Introduction to Multi-Armed Bandits
von: Slivkins, Aleksandrs
Veröffentlicht: (2019)

Regularized Robustly Reliable Learners and Instance Targeted Attacks
von: Blum, Avrim, et al.
Veröffentlicht: (2024)

Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits
von: He, Yuchen, et al.
Veröffentlicht: (2024)

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

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

Improved Approximations for Hard Graph Problems using Predictions
von: Aamand, Anders, et al.
Veröffentlicht: (2025)

Dynamic Spectral Clustering with Provable Approximation Guarantee
von: Laenen, Steinar, et al.
Veröffentlicht: (2024)

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

A Theoretical Model for Grit in Pursuing Ambitious Ends
von: Blum, Avrim, et al.
Veröffentlicht: (2025)

Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits
von: Ye, Zichun, et al.
Veröffentlicht: (2025)

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

Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
von: Blum, Avrim, et al.
Veröffentlicht: (2025)

Online Multi-Class Selection with Group Fairness Guarantee
von: Zargari, Faraz, et al.
Veröffentlicht: (2025)

Convergence of a L2 regularized Policy Gradient Algorithm for the Multi Armed Bandit
von: Anita, Stefana, et al.
Veröffentlicht: (2024)

Stochastic $k$-Submodular Bandits with Full Bandit Feedback
von: Nie, Guanyu, et al.
Veröffentlicht: (2024)

Linear Submodular Maximization with Bandit Feedback
von: Chen, Wenjing, et al.
Veröffentlicht: (2024)

High-dimensional Linear Bandits with Knapsacks
von: Ma, Wanteng, et al.
Veröffentlicht: (2023)

Spectral Guarantees for Adversarial Streaming PCA
von: Price, Eric, et al.
Veröffentlicht: (2024)

Stochastic Bandits with ReLU Neural Networks
von: Xu, Kan, et al.
Veröffentlicht: (2024)

Semi-Bandit Learning for Monotone Stochastic Optimization
von: Agarwal, Arpit, et al.
Veröffentlicht: (2023)

Minimizing Cost Rather Than Maximizing Reward in Restless Multi-Armed Bandits
von: Witter, R. Teal, et al.
Veröffentlicht: (2024)

MNL-Bandit with Knapsacks: a near-optimal algorithm
von: Aznag, Abdellah, et al.
Veröffentlicht: (2021)

New Approximation Guarantees for The Inventory Staggering Problem
von: Alon, Noga, et al.
Veröffentlicht: (2025)

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
von: Chen, Yixin, et al.
Veröffentlicht: (2026)

Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees
von: Chandrasekaran, Gautam, et al.
Veröffentlicht: (2025)

Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret
von: Harada, Tsubasa, et al.
Veröffentlicht: (2025)

Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure
von: Slivkins, Aleksandrs, et al.
Veröffentlicht: (2025)

Near-Optimal Algorithms for Omniprediction
von: Okoroafor, Princewill, et al.
Veröffentlicht: (2025)

Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees
von: Zhao, Jingyang, et al.
Veröffentlicht: (2023)

On the Hardness of Approximation of the Fair k-Center Problem
von: Thejaswi, Suhas
Veröffentlicht: (2026)

Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor
von: Aliakbarpour, Maryam, et al.
Veröffentlicht: (2025)

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

The Space Complexity of Approximating Logistic Loss
von: Dexter, Gregory, et al.
Veröffentlicht: (2024)

Approximation Algorithms for Combinatorial Optimization with Predictions
von: Antoniadis, Antonios, et al.
Veröffentlicht: (2024)