Algorithmes en ligne et modification des décisions passées

Question

Nous savons que pour certains problèmes en ligne, les algorithmes peuvent considérablement diminuer leur ratio compétitif s'ils sont autorisés à changer certaines de leurs décisions passées (voir http://epubs.siam.org/doi/pdf/10.1137/1.9781611973402.35).

Je me demande s'il y a des cas de problèmes en ligne tels que le ratio compétitif ne diminue pas même si l'algorithme est autorisé à changer ses décisions?