May, 2024
无悔的 M${}^{atural}$ 凹函数最大化：随机赌博算法和对抗完全信息设置的 NP 困难性
No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and NP-Hardness of Adversarial Full-Information Setting
Taihei Oki, Shinsaku Sakaue
TL;DR基于反馈的交互式最大化在线 M${}^{atural}$- 凹函数研究中，我们提出了 $O (T^{-1/2})$-simple regret 和 $O (T^{2/3})$-regret 算法，证明了贪心算法对于 M${}^{atural}$- 凹函数最大化中的局部误差的鲁棒性，并对于多项式时间每回合运行算法无法实现 $O (T^{1-c})$ regret 的可能性给出了证明。