Cheap Bandits
Cheap Bandits introduces CheapUCB, an algorithm for learning from groups of actions where observing averages is cheaper than individual rewards. It minimizes both cumulative regret and sensing cost, achieving a linear cost gain over existing methods while matching state-of-the-art regret guarantees based on the effective dimension.