It would be nice if the greedy method was indeed optimal. If you're running a recommender system, just recommend greedily and you'll automatically discover which content people like! I think this is too good to be true, unfortunately. If you act greedily, you really will insufficiently explore your catalogue of options.
I think the papers that claim otherwise are interesting, but make assumptions that are less innocuous than they appear. For instance, the assumptions in this paper rule out inclusion of an intercept term, or nested categorical variables, in a linear regression.
It would be nice if the greedy method was indeed optimal. If you're running a recommender system, just recommend greedily and you'll automatically discover which content people like! I think this is too good to be true, unfortunately. If you act greedily, you really will insufficiently explore your catalogue of options.
I think the papers that claim otherwise are interesting, but make assumptions that are less innocuous than they appear. For instance, the assumptions in this paper rule out inclusion of an intercept term, or nested categorical variables, in a linear regression.
https://web.stanford.edu/~bayati/papers/greedy.pdf
Hi Dan,
I think in the context of recommender systems, you'd be surprised. Exploration-free algorithms are more the norm than not. Here's an example paper on this: https://www.jmlr.org/papers/volume17/15-109/15-109.pdf
But I understand where you're coming from. Maybe I'd put it this way:
1. it seems like in most bandit settings, there is some greedy algorithm that is usually very good, though seldom optimal.
2. many greedy algorithms are very bad.
Is that a more agreeable framing?
The link pointing to your book is broken.
Thanks. Fixed!