This post is about contextual bandit problems where, repeatedly:<\/p>\n
The goal in these situations is to learn a policy which maximizes ra<\/sub><\/em> in expectation efficiently. I’m thinking about all situations which fit the above setting, whether they are drawn IID or adversarially from round to round and whether they involve past logged data or rapidly learning via interaction.<\/p>\n One common drawback of all algorithms for solving this setting, is that they have a poor dependence on the number of actions. For example if k<\/em> is the number of actions, EXP4 (page 66)<\/a> has a dependence on k0.5<\/sup><\/em>, epoch-greedy<\/a> (and the simpler epsilon greedy) have a dependence on k1\/3<\/sup><\/em>, and the offset tree<\/a> has a dependence on k-1<\/em>. These results aren’t directly comparable because different things are being analyzed. The fact that all<\/em> analyses have poor dependence on k<\/em> is troublesome. The lower bounds in the EXP4 paper and the Offset Tree paper demonstrate that this isn’t a matter of lazy proof writing or a poor choice of algorithms: it’s essential to the nature of the problem.<\/p>\n In supervised learning, it’s typical to get no dependence or very weak dependence on the number of actions\/choices\/labels. For example, if we do empirical risk minimization over a finite hypothesis space H<\/em>, the dependence is at most ln |H|<\/em> using an Occam’s Razor<\/a> bound. Similarly, the PECOC algorithm (page 12)<\/a> has dependence bounded by a constant. This kind of dependence is great for the feasibility of machine learning: it means that we can hope to tackle seemingly difficult problems.<\/p>\n Why is there such a large contrast between these settings? At the level of this discussion, they differ only in step 3, where for supervised learning, all of the rewards are revealed instead of just one.<\/p>\n One of the intuitions you develop after working with supervised learning is that holistic information is often better. As an example, given a choice between labeling the same point multiple times (perhaps revealing and correcting noise) or labeling other points once, an algorithm with labels other points typically exists and typically yields as good or better performance in theory and in practice. This appears untrue when we have only partial observations.<\/p>\n For example, consider the following problem(*): “Find an action with average reward greater than 0.5 with probability at least 0.99” and consider two algorithms:<\/p>\n When there are 1010<\/sup><\/em> actions and 109<\/sup><\/em> of them have average reward 0.6, it’s easy to prove that algorithm 2 is much better than algorithm 1.<\/p>\n Lower bounds for the partial observation settings imply that more tractable algorithms only exist under additional assumptions. Two papers which do this without context features are:<\/p>\n Basic questions<\/strong>: Are there other kinds of natural structure which allows a good dependence on the total number of actions? Can these kinds of structures be extended to the setting with features? (Which seems essential for real applications.)<\/p>\n (*) Developed in discussion with Yisong Yue<\/a> and Bobby Kleinberg<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":" This post is about contextual bandit problems where, repeatedly: The world chooses features x and rewards for each action r1,…,rk then announces the features x (but not the rewards). A policy chooses an action a. The world announces the reward ra The goal in these situations is to learn a policy which maximizes ra in … <\/p>\n\n
\n