Tracking Adversarial Targets

Yasin Abbasi-Yadkori, Peter Bartlett, Varun Kanade
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(1):369-377, 2014.

Abstract

We study linear control problems with quadratic losses and adversarially chosen tracking targets. We present an efficient algorithm for this problem and show that, under standard conditions on the linear system, its regret with respect to an optimal linear policy grows as O(\log^2 T), where T is the number of rounds of the game. We also study a problem with adversarially chosen transition dynamics; we present an exponentially-weighted average algorithm for this problem, and we give regret bounds that grow as O(\sqrt T).

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-abbasi-yadkori14, title = {Tracking Adversarial Targets}, author = {Abbasi-Yadkori, Yasin and Bartlett, Peter and Kanade, Varun}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {369--377}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/abbasi-yadkori14.pdf}, url = {https://proceedings.mlr.press/v32/abbasi-yadkori14.html}, abstract = {We study linear control problems with quadratic losses and adversarially chosen tracking targets. We present an efficient algorithm for this problem and show that, under standard conditions on the linear system, its regret with respect to an optimal linear policy grows as O(\log^2 T), where T is the number of rounds of the game. We also study a problem with adversarially chosen transition dynamics; we present an exponentially-weighted average algorithm for this problem, and we give regret bounds that grow as O(\sqrt T).} }
Endnote
%0 Conference Paper %T Tracking Adversarial Targets %A Yasin Abbasi-Yadkori %A Peter Bartlett %A Varun Kanade %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-abbasi-yadkori14 %I PMLR %P 369--377 %U https://proceedings.mlr.press/v32/abbasi-yadkori14.html %V 32 %N 1 %X We study linear control problems with quadratic losses and adversarially chosen tracking targets. We present an efficient algorithm for this problem and show that, under standard conditions on the linear system, its regret with respect to an optimal linear policy grows as O(\log^2 T), where T is the number of rounds of the game. We also study a problem with adversarially chosen transition dynamics; we present an exponentially-weighted average algorithm for this problem, and we give regret bounds that grow as O(\sqrt T).
RIS
TY - CPAPER TI - Tracking Adversarial Targets AU - Yasin Abbasi-Yadkori AU - Peter Bartlett AU - Varun Kanade BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-abbasi-yadkori14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 1 SP - 369 EP - 377 L1 - http://proceedings.mlr.press/v32/abbasi-yadkori14.pdf UR - https://proceedings.mlr.press/v32/abbasi-yadkori14.html AB - We study linear control problems with quadratic losses and adversarially chosen tracking targets. We present an efficient algorithm for this problem and show that, under standard conditions on the linear system, its regret with respect to an optimal linear policy grows as O(\log^2 T), where T is the number of rounds of the game. We also study a problem with adversarially chosen transition dynamics; we present an exponentially-weighted average algorithm for this problem, and we give regret bounds that grow as O(\sqrt T). ER -
APA
Abbasi-Yadkori, Y., Bartlett, P. & Kanade, V.. (2014). Tracking Adversarial Targets. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(1):369-377 Available from https://proceedings.mlr.press/v32/abbasi-yadkori14.html.

Related Material