CCN Interest Forwarding Strategy as Multi-Armed Bandit Model with Delays

Konstantin Avrachenkov 1 Peter Jacko 2
1 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
2 Networks
BCAM - Basque Center for Applied Mathematics
Abstract : We consider Content Centric Network (CCN) interest forwarding problem as a Multi-Armed Bandit (MAB) problem with delays. We investigate the transient behaviour of the $\eps$-greedy, tuned $\eps$-greedy and Upper Confidence Bound (UCB) interest forwarding policies. Surprisingly, for all the three policies very short initial exploratory phase is needed. We demonstrate that the tuned $\eps$-greedy algorithm is nearly as good as the UCB algorithm, commonly reported as the best currently available algorithm. We prove the uniform logarithmic bound for the tuned $\eps$-greedy algorithm in the presence of delays. In addition to its immediate application to CCN interest forwarding, the new theoretical results for MAB problem with delays represent significant theoretical advances in machine learning discipline.
Type de document :
Communication dans un congrès
NetGCoop'12: The 6th International Conference on Network Games, Control and Optimization, Nov 2012, Avignon, France. 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00764011
Contributeur : Konstantin Avrachenkov <>
Soumis le : mercredi 12 décembre 2012 - 10:58:22
Dernière modification le : samedi 27 janvier 2018 - 01:31:43

Identifiants

  • HAL Id : hal-00764011, version 1

Collections

Citation

Konstantin Avrachenkov, Peter Jacko. CCN Interest Forwarding Strategy as Multi-Armed Bandit Model with Delays. NetGCoop'12: The 6th International Conference on Network Games, Control and Optimization, Nov 2012, Avignon, France. 2012. 〈hal-00764011〉

Partager

Métriques

Consultations de la notice

104