I recently started learning about randomized online algorithms, and the Wikipedia definitions for the three adversary models are very unhelpful to put it mildly. From poking around I think I have a good understanding of what an oblivious adversary is. From my understanding, the oblivious adversary must determine the "worst possible input sequence" before we even start running our algorithm. Let $$I_w$$ denote the worst possible input sequence this adversary comes up with. (I.e., the input sequence that produces the greatest gap between the best that can be done and what we expect our algorithm to do.)
We then say that our algorithm is $$c$$-competitive (for a minimization problem) under this adversary if $$E[Alg(I_w)] \le c \cdot Opt(I_w) + b$$ where $$c,b$$ are some constants, $$E[Alg(I_w)]$$ is the expected value of our algorithm on the input, and $$Opt(I_w)$$ is the cost if we had made perfect decisions. (I.e., if the problem went offline.)
• As I understand it, both of these adversaries somehow build the input sequences as your online algorithm runs. This says before you create the input at time $$t$$, unlike in the case of the oblivious adversary, both the adaptive online and adaptive offline adversaries have access to the outcomes of your algorithm at time steps $$1, \ldots , t-1$$. Then it says that in both cases the adversary "incurs the costs of serving the requests online." The difference being that for the online adaptive adversary, it "will only receive the decision of the online algorithm after it decided its own response to the request." Does this mean that the difference is that the offline adaptive adversary can see how your algorithm performs during future steps? Or just the present step? But then why is it still incurring the cost of serving requests online?