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.