Higher-Order Regret Bounds with Switching Costs

Eyal Gofer
Proceedings of The 27th Conference on Learning Theory, PMLR 35:210-243, 2014.

Abstract

This work examines online linear optimization with full information and switching costs (SCs) and focuses on regret bounds that depend on properties of the loss sequences. The SCs considered are bounded functions of a pair of decisions, and regret is augmented with the total SC. We show under general conditions that for any normed SC, σ(\mathbfx,\mathbfx’)=\|\mathbfx-\mathbfx’\|, regret \textitcannot be bounded given only a bound Q on the quadratic variation of losses. With an additional bound Λon the total length of losses, we prove O(\sqrtQ+Λ) regret for Regularized Follow the Leader (RFTL). Furthermore, an O(\sqrtQ) bound holds for RFTL given a cost \|\mathbfx-\mathbfx’\|^2. By generalizing the Shrinking Dartboard algorithm, we also show an expected regret bound for the best expert setting with any SC, given bounds on the total loss of the best expert and the quadratic variation of any expert. As SCs vanish, all our bounds depend purely on quadratic variation. We apply our results to pricing options in an arbitrage-free market with proportional transaction costs. In particular, we upper bound the price of “at the money” call options, assuming bounds on the quadratic variation of a stock price and the minimum of summed gains and summed losses.

Cite this Paper

BibTeX
@InProceedings{pmlr-v35-gofer14, title = {Higher-Order Regret Bounds with Switching Costs}, author = {Gofer, Eyal}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {210--243}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/gofer14.pdf}, url = {https://proceedings.mlr.press/v35/gofer14.html}, abstract = {This work examines online linear optimization with full information and switching costs (SCs) and focuses on regret bounds that depend on properties of the loss sequences. The SCs considered are bounded functions of a pair of decisions, and regret is augmented with the total SC. We show under general conditions that for any normed SC, σ(\mathbfx,\mathbfx’)=\|\mathbfx-\mathbfx’\|, regret \textitcannot be bounded given only a bound Q on the quadratic variation of losses. With an additional bound Λon the total length of losses, we prove O(\sqrtQ+Λ) regret for Regularized Follow the Leader (RFTL). Furthermore, an O(\sqrtQ) bound holds for RFTL given a cost \|\mathbfx-\mathbfx’\|^2. By generalizing the Shrinking Dartboard algorithm, we also show an expected regret bound for the best expert setting with any SC, given bounds on the total loss of the best expert and the quadratic variation of any expert. As SCs vanish, all our bounds depend purely on quadratic variation. We apply our results to pricing options in an arbitrage-free market with proportional transaction costs. In particular, we upper bound the price of “at the money” call options, assuming bounds on the quadratic variation of a stock price and the minimum of summed gains and summed losses.} }
Endnote
%0 Conference Paper %T Higher-Order Regret Bounds with Switching Costs %A Eyal Gofer %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-gofer14 %I PMLR %P 210--243 %U https://proceedings.mlr.press/v35/gofer14.html %V 35 %X This work examines online linear optimization with full information and switching costs (SCs) and focuses on regret bounds that depend on properties of the loss sequences. The SCs considered are bounded functions of a pair of decisions, and regret is augmented with the total SC. We show under general conditions that for any normed SC, σ(\mathbfx,\mathbfx’)=\|\mathbfx-\mathbfx’\|, regret \textitcannot be bounded given only a bound Q on the quadratic variation of losses. With an additional bound Λon the total length of losses, we prove O(\sqrtQ+Λ) regret for Regularized Follow the Leader (RFTL). Furthermore, an O(\sqrtQ) bound holds for RFTL given a cost \|\mathbfx-\mathbfx’\|^2. By generalizing the Shrinking Dartboard algorithm, we also show an expected regret bound for the best expert setting with any SC, given bounds on the total loss of the best expert and the quadratic variation of any expert. As SCs vanish, all our bounds depend purely on quadratic variation. We apply our results to pricing options in an arbitrage-free market with proportional transaction costs. In particular, we upper bound the price of “at the money” call options, assuming bounds on the quadratic variation of a stock price and the minimum of summed gains and summed losses.
RIS
TY - CPAPER TI - Higher-Order Regret Bounds with Switching Costs AU - Eyal Gofer BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-gofer14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 210 EP - 243 L1 - http://proceedings.mlr.press/v35/gofer14.pdf UR - https://proceedings.mlr.press/v35/gofer14.html AB - This work examines online linear optimization with full information and switching costs (SCs) and focuses on regret bounds that depend on properties of the loss sequences. The SCs considered are bounded functions of a pair of decisions, and regret is augmented with the total SC. We show under general conditions that for any normed SC, σ(\mathbfx,\mathbfx’)=\|\mathbfx-\mathbfx’\|, regret \textitcannot be bounded given only a bound Q on the quadratic variation of losses. With an additional bound Λon the total length of losses, we prove O(\sqrtQ+Λ) regret for Regularized Follow the Leader (RFTL). Furthermore, an O(\sqrtQ) bound holds for RFTL given a cost \|\mathbfx-\mathbfx’\|^2. By generalizing the Shrinking Dartboard algorithm, we also show an expected regret bound for the best expert setting with any SC, given bounds on the total loss of the best expert and the quadratic variation of any expert. As SCs vanish, all our bounds depend purely on quadratic variation. We apply our results to pricing options in an arbitrage-free market with proportional transaction costs. In particular, we upper bound the price of “at the money” call options, assuming bounds on the quadratic variation of a stock price and the minimum of summed gains and summed losses. ER -
APA
Gofer, E.. (2014). Higher-Order Regret Bounds with Switching Costs. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:210-243 Available from https://proceedings.mlr.press/v35/gofer14.html.

Related Material