Cover Image

A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chase, Zachary, Ito, Shinji, Mehalel, Idan
Format:	Preprint
Published:	2025
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Deterministic Apple Tasting
by: Chase, Zachary, et al.
Published: (2024)

Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
by: Filmus, Yuval, et al.
Published: (2023)

Replicability is Asymptotically Free in Multi-armed Bandits
by: Komiyama, Junpei, et al.
Published: (2024)

Improved Regret Bounds for Bandits with Expert Advice
by: Cesa-Bianchi, Nicolò, et al.
Published: (2024)

Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs
by: Filmus, Yuval, et al.
Published: (2024)

Most Convolutional Networks Suffer from Small Adversarial Perturbations
by: Daniely, Amit, et al.
Published: (2026)

Multiclass Online Learnability under Bandit Feedback
by: Raman, Ananth, et al.
Published: (2023)

Bandits with Abstention under Expert Advice
by: Pasteris, Stephen, 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)

Online Learning of Neural Networks
by: Daniely, Amit, et al.
Published: (2025)

Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End
by: Hanneke, Steve, et al.
Published: (2026)

A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning
by: Doron-Arad, Ilan, et al.
Published: (2026)

Online Realizable Regression and Applications for ReLU Networks
by: Doron-Arad, Ilan, et al.
Published: (2026)

Data-dependent Bounds with $T$-Optimal Best-of-Both-Worlds Guarantees in Multi-Armed Bandits using Stability-Penalty Matching
by: Nguyen, Quan, et al.
Published: (2025)

Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards
by: Qin, Hao, 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)

LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits
by: Kato, Masahiro, et al.
Published: (2024)

Influential Bandits: Pulling an Arm May Change the Environment
by: Sato, Ryoma, et al.
Published: (2025)

Bandit Max-Min Fair Allocation
by: Harada, Tsubasa, et al.
Published: (2025)

Open Problem: Tight Bounds for Kernelized Multi-Armed Bandits with Bernoulli Rewards
by: Mussi, Marco, et al.
Published: (2024)

Multi-armed Bandits with Missing Outcome
by: Mahrooghi, Ilia, et al.
Published: (2024)

Collaborating in Multi-Armed Bandits with Strategic Agents
by: Barnea, Idan, et al.
Published: (2026)

Heavy-tailed Linear Bandits: Adversarial Robustness, Best-of-both-worlds, and Beyond
by: Zhao, Canzhe, et al.
Published: (2025)

A Perturbation Approach to Unconstrained Linear Bandits
by: Jacobsen, Andrew, et al.
Published: (2026)

Offline Learning for Combinatorial Multi-armed Bandits
by: Liu, Xutong, et al.
Published: (2025)

Maximal Objectives in the Multi-armed Bandit with Applications
by: Ozbay, Eren, et al.
Published: (2020)

Combinatorial Allocation Bandits with Nonlinear Arm Utility
by: Shibukawa, Yuki, et al.
Published: (2026)

Deceptive Exploration in Multi-armed Bandits
by: Vurankaya, I. Arda, et al.
Published: (2025)

Causally Abstracted Multi-armed Bandits
by: Zennaro, Fabio Massimo, et al.
Published: (2024)

Individual Regret in Cooperative Stochastic Multi-Armed Bandits
by: Barnea, Idan, et al.
Published: (2024)

Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback
by: Huang, Ruiyuan, et al.
Published: (2025)

Fairness of Exposure in Online Restless Multi-armed Bandits
by: Sood, Archit, et al.
Published: (2024)

Rising Rested Bandits: Lower Bounds and Efficient Algorithms
by: Fiandri, Marco, et al.
Published: (2024)

Transfer Learning for Contextual Multi-armed Bandits
by: Cai, Changxiao, et al.
Published: (2022)

Non-stochastic Bandits With Evolving Observations
by: Bar-On, Yogev, et al.
Published: (2024)

Lower Bounds for Time-Varying Kernelized Bandits
by: Cai, Xu, et al.
Published: (2024)

Tight Lower Bounds and Improved Convergence in Performative Prediction
by: Khorsandi, Pedram, et al.
Published: (2024)

Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems
by: Lee, Jongyeong, et al.
Published: (2025)

Locally Private Nonparametric Contextual Multi-armed Bandits
by: Ma, Yuheng, et al.
Published: (2025)

Learning with Limited Shared Information in Multi-agent Multi-armed Bandit
by: Shao, Junning, et al.
Published: (2025)