direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Selected Publications on Game Theory

about game theory

From Optimization to Regret Minimization and Back Again
Citation key ARS-FORMBA-08
Author Avramopoulos, Ioannis and Rexford, Jennifer and Schapire, Robert
Title of Book Proc. of the Third Workshop on Tackling Computer System Problems with Machine Learning Techniques (SysML '08)
Year 2008
Location San Diego, CA, USA
Month December
Abstract Internet routing is mostly based on static information–-it's dynamicity is limited to reacting to changes in topology. Adaptive performance-based routing decisions would not only improve the performance itself of the Internet but also its security and availability. However, previous approaches for making Internet routing adaptive based on optimizing network-wide objectives are not suited for an environment in which autonomous and possibly malicious entities interact. In this paper, we propose a different framework for adaptive routing decisions based on regret-minimizing online learning algorithms. These algorithms, as applied to routing, are appealing because adopters can independently improve their own performance while being robust to adversarial behavior. However, in contrast to approaches based on optimization theory that provide guarantees from the outset about network-wide behavior, the network-wide behavior if online learning algorithms were to interact with each other is less understood. In this paper, we study this interaction in a realistic Internet environment, and find that the outcome is a stable state and that the optimality gap with respect to the networkwide optimum is small. Our findings suggest that online learning may be a suitable framework for adaptive routing decisions in the Internet.
Link to publication Link to original publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions