Hacker News Reader

Comment by bagrow | Hacker News Reader

Anyone aware of research on bandits with a growing set of arms? Meaning, every so often when you play an arm part of your reward is revealing a new arm!

This seems to not fit the criteria anymore (not tabular, not Markov). Is it related to structured bandits?

View on HN

Hmm, perhaps something like UCB1? The UCB (upper-confidence-bound) family of algorithms might be appropriate—it's not quite what you've described though.

They'll explore the arm with the highest potential payoff i.e. the highest upper-confidence-bound, which often is the arm you know the least about since they're roughly calculated as (average + confidence interval) and early on the confidence bound is large. This style of algorithm means you can add arms as you go through the experiment and they'll be explored/exploited in a reasonable way.

What you're describing sounds more like you're exploring a frontier and "discovering" new options along the way..?

Consider any arm not pulled is "a new arm". A growing set of arms is similar to case where k >> T. This creates innovate vs. exploit problem. The learner must choose between exploiting what it already knows and searching for better rewards.

Variations of this scheme include exploit vs. copy vs. innovate used in computational biology. Learning agent can copy what others do or innovate and try something new.

Adding new arms in a bandit problem doesn't pose a problem for most bandit algorithms. Any of the common algorithms will handle it just fine. Arms disappearing is more interesting, as that effects the explore / exploit tradeoff. It's been a while since I was studying bandit algorithms but "Mortal multi-armed bandits" is one paper that addresses this.

If the additional arms appear late, my intuition is to use one algorithm for the old parts and one for the new arms, and a weighting factor to decide which model to use. This procedure can be generalized for generational partitions. For example you group the old arms into group A and the new arms in group B, and a bandit with two arms to decide which group to use, then inside each group you apply your favorite bandit algorithm, that is not a divide and conquer algorithm but has something in common. This is a hierarchical model.

I don't work in this area, but googled for HMM + indian buffet process and found this page. I'd guess some of the nonparametric bayesian models focus on the problem you mentioned.

http://research.cs.rutgers.edu/~cmansley/fall08/cs500.html

Reply on news.ycombinator.com