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, the best currently available algorithm. We prove the uniform logarithmic bound for the tuned $\eps$-greedy algorithm. 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 :
Rapport
[Research Report] RR-7917, INRIA. 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00683827
Contributeur : Konstantin Avrachenkov <>
Soumis le : dimanche 1 avril 2012 - 23:08:42
Dernière modification le : jeudi 11 janvier 2018 - 16:58:52
Document(s) archivé(s) le : lundi 2 juillet 2012 - 03:23:36

Fichiers

RR-7917.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00683827, version 2
  • ARXIV : 1204.0416

Collections

Citation

Konstantin Avrachenkov, Peter Jacko. CCN Interest Forwarding Strategy as Multi-Armed Bandit Model with Delays. [Research Report] RR-7917, INRIA. 2012. 〈hal-00683827v2〉

Partager

Métriques

Consultations de la notice

284

Téléchargements de fichiers

222