4 ms·

> So it makes sense to go with the plan with the best payout in case there will be no unknown unknowns. Yes, this intuition is in the right direction. A key po

> So it makes sense to go with the plan with the best payout in case there will be no unknown unknowns. Yes, this intuition is in the right direction. A key point about online learning is that we usually measure the performance of online algorithms by static regret, which is the difference between the reward/cost incurred by the online learner and the reward/cost of the best fixed action (for example, the payout of the best single arm in the multi-armed bandit setting). The goal is usually to design algorithms whose static regret is sublinear in the number of rounds played; the intuition here is that if the learner's regret is sublinear, then the average reward/cost incurred by the online learner across rounds converges to the average reward/cost of the best fixed action, so in that sense the online learner's choices are converging to the optimal choices. Any online learner which incurs an additive constant more cost per round (on average) relative to the best fixed action cannot have sublinear regret; hence it is important that the learner aggressively exploit any upside it finds. Put another way, if the learner consistently misses the mark per round, for example by being too conservative, it will not achieve sublinear regret.

vladf 7y ago
I think there's a really important caveat to OFU here. Namely, we have your higher-level interpretation in the GGP ("great-grandparent post"): > The intuition here is that if your optimism turns out to be correct, you can capture most of the upside, but if your optimism is misguided, you can quickly gather information and reassess. A _really_ important characteristic that lets UCB work is that its environment is stochastic, not adversarial. If you're OFU in an adversarial environment, you will get penalized for it and won't achieve sublinear regret. So I think there's an important taxonomy here, between an indifferent ("stochastic") and adversarial nature. These principles get stretched a little bit when you further compare oblivious to adaptive adversaries (or, in the stochastic case, stationary vs non-stationary). My point here is that the exact contours of the exploration/exploitation tradeoff are delicately dependent on the problem setting, so it's a bit dangerous to make generalized conclusions about OFU as a principle without also acknowledging when it's relevant. And from the GP: > Known unknowns can be handled with statistics... so go with the plan with the best payout in case there will be no unknown unknowns. I don't know about that. It's statistics all the way down.
- gautamcgoel 7y ago
  Yes, good catch! As this comment points out, OFU only makes sense when talking about stochastic environments (the OFU algorithm is described in terms of confidence intervals). The adversarial setting is quite different.

vladf 7y ago

I think there's a really important caveat to OFU here. Namely, we have your higher-level interpretation in the GGP ("great-grandparent post"): > The intuition here is that if your optimism turns out to be correct, you can capture most of the upside, but if your optimism is misguided, you can quickly gather information and reassess. A _really_ important characteristic that lets UCB work is that its environment is stochastic, not adversarial. If you're OFU in an adversarial environment, you will get penalized for it and won't achieve sublinear regret. So I think there's an important taxonomy here, between an indifferent ("stochastic") and adversarial nature. These principles get stretched a little bit when you further compare oblivious to adaptive adversaries (or, in the stochastic case, stationary vs non-stationary). My point here is that the exact contours of the exploration/exploitation tradeoff are delicately dependent on the problem setting, so it's a bit dangerous to make generalized conclusions about OFU as a principle without also acknowledging when it's relevant. And from the GP: > Known unknowns can be handled with statistics... so go with the plan with the best payout in case there will be no unknown unknowns. I don't know about that. It's statistics all the way down.

gautamcgoel 7y ago
Yes, good catch! As this comment points out, OFU only makes sense when talking about stochastic environments (the OFU algorithm is described in terms of confidence intervals). The adversarial setting is quite different.