Pure Exploration in Finitely-Armed and Continuous-Armed Bandits: Bubeck, Munos, Stoltz (Arxiv version)

  1. Considers case of simple regret, where exploration and exploitation are separated
  2. In the setting, the agent is allowed n pulls of arms and at the end must recommend an arm.  The agent is not necessarily aware of the value of n.
  3. Costs during exploration are not in terms of regret, but some other resource, such as computation time
  4. May also require anytime performance
  5. The smaller the cumulative regret, the larger the simple regret
    1. Related to exploration/exploitation tradeoff
    2. Simple regret can be upper bounded in terms of cumulative regret
    3. For finite-armed bandits, best simple regret is achieved by sampling each arm a linear number of times, whereas in cumulative regret suboptimal arms should not be sampled more than a logarithmic number of times
  6. The statement that each arm should get linear number of pulls for best simple regret is true only in case of large n.  For smaller values other techniques will yield better results (UCB type is better)
  7. Rate of decrease of simple regret is 1/sqrt(n) in distribution free case, in distribution dependent case the decrease is exponential.  I’m not sure what the difference is here though.
  8. In continuous spaces the regret bound seems to be O(n) which i dont understand

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: