Cover Image

No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Oki, Taihei, Sakaue, Shinsaku
Format:	Preprint
Published:	2024
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

Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets
by: Oki, Taihei, et al.
Published: (2026)

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
by: Sakaue, Shinsaku, et al.
Published: (2026)

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

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

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

Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits
by: He, Yuchen, 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)

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

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

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

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)

Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming
by: Sakaue, Shinsaku, et al.
Published: (2023)

Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities
by: Su, Yuexin, et al.
Published: (2025)

Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret
by: Harada, Tsubasa, et al.
Published: (2025)

Accelerated Relax-and-Round for Concave Coverage Problems
by: Fahrbach, Matthew, et al.
Published: (2026)

Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound
by: Sakaue, Shinsaku, et al.
Published: (2025)

Bandit Sequential Posted Pricing via Half-Concavity
by: Singla, Sahil, et al.
Published: (2023)

Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications
by: Zhu, Yanhui, et al.
Published: (2024)

Practical Parallel Algorithms for Non-Monotone Submodular Maximization
by: Cui, Shuang, et al.
Published: (2023)

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

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

Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems
by: Grigorescu, Elena, et al.
Published: (2024)

A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives
by: Grigorescu, Elena, et al.
Published: (2024)

Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint
by: Chen, Yixin, et al.
Published: (2020)

Complexity of Non-Log-Concave Sampling in Fisher Information
by: Chewi, Sinho, et al.
Published: (2026)

Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers
by: Mangoubi, Oren, et al.
Published: (2024)

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity
by: Amanatidis, Georgios, et al.
Published: (2021)

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

Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
by: John, Philips George, et al.
Published: (2024)

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

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

Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacy
by: Wu, Ruihan, et al.
Published: (2025)

Negative Momentum for Convex-Concave Optimization
by: Shugart, Henry, et al.
Published: (2026)

Consistent Submodular Maximization
by: Dütting, Paul, et al.
Published: (2024)

A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming
by: Xu, Haoran, et al.
Published: (2026)

Algorithmic aspects of semistability of quiver representations
by: Iwamasa, Yuni, et al.
Published: (2024)

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

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

Computational and Statistical Hardness of Calibration Distance
by: Qiao, Mingda
Published: (2026)