TITLE:
Playing against Hedge
AUTHORS:
Miltiades E. Anagnostou, Maria A. Lambrou
KEYWORDS:
Hedge Algorithm, Adversary, Online Algorithm, Greedy Algorithm, Periodic Performance, Binary Penalties, Path Selection, Network Interdiction
JOURNAL NAME:
International Journal of Communications, Network and System Sciences,
Vol.7 No.12,
December
3,
2014
ABSTRACT: Hedge has been proposed as an adaptive
scheme, which guides the player’s hand in a multi-armed bandit full information
game. Applications of this game exist in network path selection, load
distribution, and network interdiction. We perform a worst case analysis of
the Hedge algorithm by using an adversary, who will consistently select
penalties so as to maximize the player’s loss, assuming that the adversary’s
penalty budget is limited. We further explore the performance of binary
penalties, and we prove that the optimum binary strategy for the adversary is
to make greedy decisions.