Search papers, labs, and topics across Lattice.
This paper explores adversarial bandit optimization with a focus on non-convex and non-smooth loss functions, where the learner faces adversarial perturbations that are constrained by a global budget. By extending the perturbation model from linear to general convex and 尾-smooth losses, the authors derive expected regret guarantees that quantify the impact of the perturbation budget on performance. The findings reveal that the modified bandit optimization algorithm effectively manages additional regret introduced by perturbations, maintaining a connection to traditional regret guarantees in the absence of such adversarial influences.
Adversarial perturbations can be effectively managed in bandit optimization, revealing how budget constraints shape regret outcomes in complex loss landscapes.
We study adversarial bandit optimization in which the loss functions may be non-convex and non-smooth. In each round, the learner selects an action and observes only the loss incurred at that action. The loss consists of an underlying convex and $尾$-smooth component and an adversarial perturbation that may be chosen after observing the learner's action. The perturbations are subject to a global budget controlling their cumulative magnitude over time. This framework extends the globally budgeted, post-action perturbation model from underlying linear losses to general convex and $尾$-smooth losses. For this broader class, we establish expected regret guarantees that explicitly characterize the effect of the perturbation budget. To establish these guarantees, we modify a standard bandit optimization algorithm and develop an analysis that controls the additional regret caused by the perturbations. In the absence of perturbations, our results reduce to regret guarantees for the standard bandit convex optimization setting with $尾$-smooth losses.
