On Local Regret. Bowling, Zinkevich. ICML 2012.

  1. Didn’t read this totally carefully, so this is just a skeleton of the paper
  2. Deals with local regret, which is a generalization of normal regret that measures performance relative to “nearby” options as opposed to globally
  3. An algorithm is presented that minimizes local regret with arbitrary locality graphs, and show how graph structure can be used to speed learning
  4. The only assumption is that the action set has some defined notion of locality, but otherwise makes no assumptions (such as convexity or smoothness)
    1. This allows the method to be applied to tasks that were previously considered intractible
    2. I still don’t understand how this can work if there are infinite options with no smoothness, will try to go over it later
  5. They discuss a few different types of regret: internal, swap, and external, and rank the difficulty.  They then introduce local versions of those types of regret
  6. Ah they do say that it is impossible to have no regret in some infinite cases.  That makes more sense, but the earlier statement is a bit misleading then
  7. Local regret is a generalization of regret, because when all options are related, local regret becomes normal regret

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: