This is a C++ package for multi-armed bandit simulations

Overview
BanditLib: a simple multi-armed bandit library 

.-. .-')     ('-.         .-') _  _ .-') _            .-') _                   .-. .-')   
\  ( OO )   ( OO ).-.    ( OO ) )( (  OO) )          (  OO) )                  \  ( OO )  
;-----.\   / . --. /,--./ ,--,'  \     .'_   ,-.-') /     '._ ,--.      ,-.-') ;-----.\  
| .-.  |   | \-.  \ |   \ |  |\  ,`'--..._)  |  |OO)|'--...__)|  |.-')  |  |OO)| .-.  |  
| '-' /_).-'-'  |  ||    \|  | ) |  |  \  '  |  |  \'--.  .--'|  | OO ) |  |  \| '-' /_) 
| .-. `.  \| |_.'  ||  .     |/  |  |   ' |  |  |(_/   |  |   |  |`-' | |  |(_/| .-. `.  
| |  \  |  |  .-.  ||  |\    |   |  |   / : ,|  |_.'   |  |  (|  '---.',|  |_.'| |  \  | 
| '--'  /  |  | |  ||  | \   |   |  '--'  /(_|  |      |  |   |      |(_|  |   | '--'  / 
`------'   `--' `--'`--'  `--'   `-------'   `--'      `--'   `------'  `--'   `------'  

1. About
2. Environment
3. Quick run
4. Misc


1. About

This is a C++ package for multi-armed bandit simulations. This package is designed to be

  1. Simple : easy to understand and extend, but not optimized for speed.
  2. Independent : does not require external library.
  • Arms:
  • Binary and Normal distribution of rewards (arms) are implemented.
  • Policies:
  • DMED for binary rewards [1]
  • Epsilon-Greedy
  • KL-UCB [2]
  • MOSS [3]
  • Thompson sampling for binary rewards [4]
  • UCB [5]
  • UCB-V [6]

2. Environment

This program supports a linux/GNU C++ environment. We do not check windows/MacOSX.

More formally, this program depends on:

  • C++0x: modern C++ compiler (preferably GNU C++ (g++))
  • waf (included) [7]: build script
  • cmdline.h (included) [8]: command line parser

3. Quick run

Type

./compile
./build/main -r 10

to run 10 simulation runs. The result of the runs will be written in out/example1.txt

This package also includes a simple plot tool (simpleplot.py) that is dependent on Python/Matplotlib. If your environment is g++/Python ready, try

./example.sh

4. Misc

The implementation of the beta distribution sampler is from [9]. The logo was generated by using [10].

References

[1] J. Honda, A. Takemura: An asymptotically optimal policy for finite support models in the multiarmed bandit problem.  Machine Learning 85(3) 2011, p.361-391

[2] Aurélien Garivier, Olivier Cappé: The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond. COLT 2011: 359-376

[3] J-Y. Audibert and S. Bubeck: Minimax Policies for Adversarial and Stochastic Bandits.  Proceedings of the 22nd Annual Conference on Learning Theory 2009

[4] Thompson, William R: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3–4):285–294, 1933

[5] Peter Auer, Nicolò Cesa-Bianchi and Paul Fische: Finite-time analysis of the multiarmed bandit problem.  Machine Learning 47 2002 p.235-256

[6] J.-Y. Audibert, R. Munos, Cs. Szepesvári: Exploration-exploitation trade-off using variance estimates in multi-armed bandits. Theoretical Computer Science Volume 410 Issue 19 Apr. 2009 pp. 1876-1902

[7] Waf - The meta build system: https://code.google.com/p/waf/

[8] Hideyuki Tanaka: cmdline https://github.com/tanakh/cmdline

[9] Joseph Mansfield: A comment on stackoverflow http://stackoverflow.com/questions/15165202/random-number-generat

[10] Text to Ascii Art Maker: http://patorjk.com/software/taag/

##Author Junpei Komiyama (junpei.komiyama atmark gmail.com)

This software is released under the MIT License, see LICENSE.txt.

You might also like...
An EDA toolchain for integrated core-memory interval thermal simulations of 2D, 2.5, and 3D multi-/many-core processors

CoMeT: An Integrated Interval Thermal Simulation Toolchain for 2D, 2.5D, and 3D Processor-Memory Systems With the growing power density in both cores

High-level networking API for real-time simulations with primitives for remote procedure call and object state replication

tnl2 - Torque Network Library version 2 tnl2 is a high-level networking API for real-time simulations with primitives for remote procedure call and o

 DLBFoam: Dynamic load balancing for fast reactive simulations
DLBFoam: Dynamic load balancing for fast reactive simulations

DLBFoam: Dynamic load balancing for fast reactive simulations DLBFoam v1.1 - What's new? DLBFoam v1.1 introduces a fully analytical chemistry Jacobian

Open-source node system framework, to change your algorithmic code into useful tools to create much more complicated simulations!
Open-source node system framework, to change your algorithmic code into useful tools to create much more complicated simulations!

Open-source node system framework, to change your algorithmic code into useful tools to create much more complicated simulations!

4eisa40 GPU computing : exploiting the GPU to execute advanced simulations

GPU-computing 4eisa40 GPU computing : exploiting the GPU to execute advanced simulations Activities Parallel programming Algorithms Image processing O

Event-driven molecular dynamics simulations for hard spheres

Event-driven molecular dynamics code for hard spheres This is an event-driven molecular dynamics (EDMD) code for hard spheres. It uses neighbor lists

C++11 provides chainable and iterable object for uniform die casts. Useful for statistics or table top RPG simulations.

12/1/2018 Due to feedback about compile-time limitations, the api has been changed since release. The api now supports user-defined literals which mak

SubLink is a C++ library used for constructing and analyzing merger trees in numerical simulations of galaxy formation

README SubLink is a C++ library used for constructing and analyzing merger trees in numerical simulations of galaxy formation. Brief description SubLi

Spack is a package manager, and package managers should be trivial to install.

🔋 Spack with batteries included (linux/x86_64) Spack is a package manager, and package managers should be trivial to install. This repo offers a sing

BakePKG is a package archive that can install itself without without a package manager.

BakePKG A bad way of packaging applications. Introduction BakePKG is a package archive that can install itself without without a package manager. The

This robot lcoalisation package for lidar-map based localisation using multi-sensor state estimation.
This robot lcoalisation package for lidar-map based localisation using multi-sensor state estimation.

A ROS-based NDT localizer with multi-sensor state estimation This repo is a ROS based multi-sensor robot localisation. An NDT localizer is loosely-cou

A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

moodycamel::ConcurrentQueue An industrial-strength lock-free queue for C++. Note: If all you need is a single-producer, single-consumer queue, I have

Minerva: a fast and flexible tool for deep learning on multi-GPU. It provides ndarray programming interface, just like Numpy. Python bindings and C++ bindings are both available. The resulting code can be run on CPU or GPU. Multi-GPU support is very easy. A bounded multi-producer multi-consumer concurrent queue written in C++11
A bounded multi-producer multi-consumer concurrent queue written in C++11

MPMCQueue.h A bounded multi-producer multi-consumer concurrent queue written in C++11. It's battle hardened and used daily in production: In the Frost

Multi-dimensional dynamically distorted staggered multi-bandpass LV2 plugin
Multi-dimensional dynamically distorted staggered multi-bandpass LV2 plugin

B.Angr A multi-dimensional dynamicly distorted staggered multi-bandpass LV2 plugin, for extreme soundmangling. Based on Airwindows XRegion. Key featur

Multi-Scale Geometric Consistency Guided and Planar Prior Assisted Multi-View Stereo

ACMMP [News] The code for ACMH is released!!! [News] The code for ACMM is released!!! [News] The code for ACMP is released!!! About This repository co

A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

moodycamel::ConcurrentQueue An industrial-strength lock-free queue for C++. Note: If all you need is a single-producer, single-consumer queue, I have

A bounded multi-producer multi-consumer concurrent queue written in C++11
A bounded multi-producer multi-consumer concurrent queue written in C++11

MPMCQueue.h A bounded multi-producer multi-consumer concurrent queue written in C++11. It's battle hardened and used daily in production: In the Frost

C++11 thread safe, multi-producer, multi-consumer blocking queue, stack & priority queue class

BlockingCollection BlockingCollection is a C++11 thread safe collection class that provides the following features: Modeled after .NET BlockingCollect

Comments
  • Complexity of finding the best arm

    Complexity of finding the best arm

    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.

    opened by govinda-kamath 1
Owner
jkomiyama
NYU Stern, assistant professor.
jkomiyama
A bounded multi-producer multi-consumer concurrent queue written in C++11

MPMCQueue.h A bounded multi-producer multi-consumer concurrent queue written in C++11. It's battle hardened and used daily in production: In the Frost

Erik Rigtorp 836 Dec 25, 2022
C++11 thread safe, multi-producer, multi-consumer blocking queue, stack & priority queue class

BlockingCollection BlockingCollection is a C++11 thread safe collection class that provides the following features: Modeled after .NET BlockingCollect

Code Ex Machina LLC 50 Nov 23, 2022
A library for enabling task-based multi-threading. It allows execution of task graphs with arbitrary dependencies.

Fiber Tasking Lib This is a library for enabling task-based multi-threading. It allows execution of task graphs with arbitrary dependencies. Dependenc

RichieSams 796 Dec 30, 2022
Optimized primitives for collective multi-GPU communication

NCCL Optimized primitives for inter-GPU communication. Introduction NCCL (pronounced "Nickel") is a stand-alone library of standard communication rout

NVIDIA Corporation 1.9k Dec 30, 2022
Powerful multi-threaded coroutine dispatcher and parallel execution engine

Quantum Library : A scalable C++ coroutine framework Quantum is a full-featured and powerful C++ framework build on top of the Boost coroutine library

Bloomberg 491 Dec 30, 2022
lc is a fast multi-threaded line counter.

Fast multi-threaded line counter in Modern C++ (2-10x faster than `wc -l` for large files)

Pranav 14 Oct 25, 2022
A library OS for Linux multi-process applications, with Intel SGX support

Graphene Library OS with Intel SGX Support A Linux-compatible Library OS for Multi-Process Applications NOTE: We are in the middle of transitioning ou

The Gramine Project 323 Jan 4, 2023
Multi-backend implementation of SYCL for CPUs and GPUs

hipSYCL - a SYCL implementation for CPUs and GPUs hipSYCL is a modern SYCL implementation targeting CPUs and GPUs, with a focus on leveraging existing

Aksel Alpay 609 Dec 26, 2022
KRATOS Multiphysics ("Kratos") is a framework for building parallel, multi-disciplinary simulation software

KRATOS Multiphysics ("Kratos") is a framework for building parallel, multi-disciplinary simulation software, aiming at modularity, extensibility, and high performance. Kratos is written in C++, and counts with an extensive Python interface.

KratosMultiphysics 774 Dec 29, 2022
A coupling library for partitioned multi-physics simulations, including, but not restricted to fluid-structure interaction and conjugate heat transfer simulations.

A coupling library for partitioned multi-physics simulations, including, but not restricted to fluid-structure interaction and conjugate heat transfer simulations.

preCICE 498 Jan 6, 2023