Regret Minimization
A core concept in online learning theory that defines 'regret' as the difference between an algorithm's actual cumulative loss and the loss of the best fixed strategy in hindsight. Theoretically, a well-performing algorithm's regret should grow at O(√T); common algorithms include Exponential Weights (Hedge) and UCB.
Timeline (last 90 days)
In standard regret minimization, the regret upper bound typically takes the form O(√T), whereas under the tilted sampling framework, sampling regret is dominated by the square of the confidence width, yielding logarithmic-level regret O(log T).
Regret is defined as the difference between the algorithm's actual cumulative loss and the loss of the best fixed strategy in hindsight.
A good online learning algorithm should guarantee that regret grows far below linearly with the number of rounds, with a typical target on the order of O(√T); Exponential Weights (Hedge) and UCB have been proven to achieve this guarantee.
All Facts (3)
In standard regret minimization, the regret upper bound typically takes the form O(√T), whereas under the tilted sampling framework, sampling regret is dominated by the square of the confidence width, yielding logarithmic-level regret O(log T).
50%UnverifiedRegret is defined as the difference between the algorithm's actual cumulative loss and the loss of the best fixed strategy in hindsight.
50%UnverifiedA good online learning algorithm should guarantee that regret grows far below linearly with the number of rounds, with a typical target on the order of O(√T); Exponential Weights (Hedge) and UCB have been proven to achieve this guarantee.
50%