Author(s)

Miltiades E. Anagnostou¹, Maria A. Lambrou²

¹School of Electrical and Computer Engineering, National Technical University of Athens, Athens, Greece.
²Department of Shipping, Trade and Transport, University of the Aegean, Chios, Greece.

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.

Hedge Algorithm, Adversary, Online Algorithm, Greedy Algorithm, Periodic Performance, Binary Penalties, Path Selection, Network Interdiction

Anagnostou, M. and Lambrou, M. (2014) Playing against Hedge. International Journal of Communications, Network and System Sciences, 7, 497-507. doi: 10.4236/ijcns.2014.712050.