Back when I was in college, an online algorithm was one where you had to make scheduling decisions as the jobs came in. There would be an optimal schedule (say differing size jobs coming in with n cpus) if you knew the future, and you prove things like "this algorithm can hit that optimal time with 1.x as many CPUs" or "this algorithm is within 1.x of optimal".

This also applies to stuff like swapping / expiring cache - if you knew all of the future disk / memory accesses you could hit optimal, otherwise you need some heuristics.

It's been a couple of decades, but I think some the proofs involved playing the part of an omniscient adversary.

> If by "online algorithm" you mean incremental learning, the problem is that they still don't work well due to catastrophic forgetting...

I rather think that with "online algorithm", gnull means exactly this classic computer science topic:

> https://en.wikipedia.org/wiki/Online_algorithm