Indeed. One impressive result I remember from that area (if I'm not mistaken) is that Least Recently Used cache policy with cache size S performs at least as we

Indeed. One impressive result I remember from that area (if I'm not mistaken) is that Least Recently Used cache policy with cache size S performs at least as well as an offline algorithm with cache size S/2. I don't remember the details now, but the proof wasn't too complicated, they gave it to us as an exercise.