No Free Experts, Hedging on Cost

Consider the following setting for learning from expert advice. In each round of the game between Player and Adversary, the player can ask for experts' suggestions but by paying some amount of money determined by each expert at the beginning of the round. In other words, at the beginning of each trial, the Player gets a cost vector which determines the cost of querying each expert for that round. Also let assume that Player has a budget constraint which would be for each round or long term constraint defined for all rounds. The goal of Player is to attain nontrivial regret bound under the budget constraint. Formally the Player tries to minimize and simultaneously satisfies the constraint .

The mentioned constraint is a long term constraint and we can alternatively define round based constraint as:.