Bandits with Anytime Knapsacks
The paper introduces SUAK, an algorithm for a problem called Bandits with Anytime Knapsacks (BwAK). This setting involves maximizing reward while adhering to an anytime cost constraint, meaning the average cost must stay below a certain limit throughout. SUAK uses upper confidence bounds to balance exploration and exploitation and strategically skips rounds when the constraint is at risk, achieving an improved regret bound of O(K log T).