Online Collaborative-Filtering on Graphs
  A common phenomena in modern recommendation systems is the use of feedback
from one user to infer the `value' of an item to other users. This results in
an exploration vs. exploitation trade-off, in which items of possibly low value
have to be presented to users in order to ascertain their value. Existing
approaches to solving this problem focus on the case where the number of items
are small, or admit some underlying structure -- it is unclear, however, if
good recommendation is possible when dealing with content-rich settings with
unstructured content.
  We consider this problem under a simple natural model, wherein the number of
items and the number of item-views are of the same order, and an `access-graph'
constrains which user is allowed to see which item. Our main insight is that
the presence of the access-graph in fact makes good recommendation possible --
however this requires the exploration policy to be designed to take advantage
of the access-graph. Our results demonstrate the importance of `serendipity' in
exploration, and how higher graph-expansion translates to a higher quality of
recommendations; it also suggests a reason why in some settings, simple
policies like Twitter's `Latest-First' policy achieve a good performance.
  From a technical perspective, our model presents a way to study
exploration-exploitation tradeoffs in settings where the number of `trials' and
`strategies' are large (potentially infinite), and more importantly, of the
same order. Our algorithms admit competitive-ratio guarantees which hold for
the worst-case user, under both finite-population and infinite-horizon
settings, and are parametrized in terms of properties of the underlying graph.
Conversely, we also demonstrate that improperly-designed policies can be highly
sub-optimal, and that in many settings, our results are order-wise optimal.
