No-Regret M-Concave Function Maximization: Stochastic Bandit Algorithms and NP-Hardness of Adversarial Full-Information Setting

Taihei Oki, Hokkaido University, Hokkaido, Japan, oki@icredd.hokudai.ac.jp "3026 Shinsaku Sakaue[1], The University of Tokyo and RIKEN AIP, Tokyo, Japan, sakaue@mist.i.u-tokyo.ac.jp

Mar-21-2025, 21:17:04 GMT–Neural Information Processing Systems 

While we obtain those positive results for the stochastic setting, another main result of our work is an impossibility in the adversarial setting.