Name
Abstract | ||
|---|---|---|
This work studies external regret in sequential prediction games with both positive and negative payoffs. External regret measures the difference between the payoff obtained by the forecasting strategy and the payoff of the best action. In this setting, we derive new and sharper regret bounds for the well-known ex- ponentially weighted average forecaster and for a new forecaster with a different multiplicative update rule. Our analysis has two main advantages: first, no prelim- inary knowledge about the payoff sequence is needed, not even its range; second, our bounds are expressed in terms of sums of squared payoffs, replacing larger first- order quantities appearing in previous bounds. In addition, our most refined bounds have the natural and desirable property of being stable under rescalings and general translations of the payoff sequence. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/s10994-006-5001-7 | Machine Learning |
Keywords | Field | DocType |
Individual sequences,Prediction with expert advice,Exponentially weighted averages | Sequence prediction,Discrete mathematics,Online algorithm,Square (algebra),Regret,Absolute value,Upper and lower bounds,Artificial intelligence,Machine learning,Mathematics,Stochastic game | Journal |
Volume | Issue | ISSN |
66 | 2-3 | 0885-6125 |
ISBN | Citations | PageRank |
3-540-26556-2 | 45 | 2.60 |
References | Authors | |
11 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolò Cesa-Bianchi | 1 | 4609 | 590.83 |
| Yishay Mansour | 2 | 6211 | 745.95 |
| Gilles Stoltz | 3 | 351 | 31.53 |