jkomiyama / banditlib Goto Github PK

Thank you for this excellent implementation of UCB.

While going through your code we found that you store each estimates of all arms as in a vector. Then for selecting the next arm you call selectNextArm() which finds the best arm by computing the maximum element in this vector using the vectorMaxIndex () function in utils.

template<class T>
int vectorMaxIndex(const std::vector<T> &elems){
  int m=0;
  T mv=elems[0];
  for(uint i=0;i<elems.size();++i){
    if(elems[i]>mv){
      mv=elems[i];
      m=i;
    }
  }
  return m;
}

This function seems to be linear in the number of arms. We (I and @bagavi) were thinking of implementing a UCB for a very large number of arms and were thinking of storing all arms as a priority queue so that this function can be achieved in logarithmic time (in the number of arms). We were wondering if we missed something there.