EXP3 Class Reference

Implementation of the EXP3 algorithm for multiarmed bandits. More...

#include <EXP3.hpp>

Collaboration diagram for EXP3:

Public Member Functions
	EXP3 (size_t, double)
size_t	get_choice () const
void	set_gamma (double)
	Reset gamma and associated members to something different.
size_t	choose ()
	Choose using the current state.
void	reward (double)
	Provide reward for the most recent choice.

Private Attributes
vector< double >	omega
vector< double >	p_values
double	gamma
size_t	K
double	one_minus_gamma
double	gamma_over_K
bool	choose_next
	Belt-and braces: warn if choose/reward happens in the wrong order.
size_t	choice
	Store the last choice made.

Static Private Attributes
static boost::random::mt19937	random_generator
	Random source.

Friends
ostream &	operator<< (ostream &, const EXP3 &)

Detailed Description

Implementation of the EXP3 algorithm for multiarmed bandits.

It's easy enough to find a description of this algorithm. The implementation here is pretty much straight from:

https://en.wikipedia.org/wiki/Multi-armed_bandit

Definition at line 51 of file EXP3.hpp.

Constructor & Destructor Documentation

EXP3()

EXP3::EXP3	(	size_t	_K,
		double	_gamma )

Definition at line 36 of file EXP3.cpp.

: K(_K)
, gamma(_gamma)
, omega(_K, 1.0)
, p_values(_K, 0.0)
, choose_next(true)
, one_minus_gamma(1 - _gamma)
, gamma_over_K(_gamma / static_cast<double>(_K))
, choice(0)
{}

Member Function Documentation

choose()

size_t EXP3::choose

(

)

Choose using the current state.

Definition at line 53 of file EXP3.cpp.

                    {
    if (!choose_next) {
        cerr << "STOP IT!! EXP3 should be receiving reward..." << endl;
    }
    choose_next = false;
    double omega_sum = 0.0;
    for (size_t i = 0; i < K; i++) {
        omega_sum += omega[i];
        p_values[i] = gamma_over_K;
    }
    for (size_t i = 0; i < K; i++) {
        p_values[i] += (one_minus_gamma * (omega[i]/omega_sum));
    }
    boost::random::discrete_distribution<> p(p_values.begin(), p_values.end());
    choice = p(random_generator);
    return choice;
}

get_choice()

size_t EXP3::get_choice ( ) const

inline

Definition at line 79 of file EXP3.hpp.

                                     {
        return choice;
    }

reward()

void EXP3::reward

(

double

r

)

Provide reward for the most recent choice.

Definition at line 71 of file EXP3.cpp.

                          {
    if (choose_next) {
        cerr << "STOP IT!! EXP3 should be choosing..." << endl;
    }
    choose_next = true;
    if (r < 0.0 || r > 1.0) {
        cerr << "STOP IT!! The reward needs to be in [0,1]." << endl;
    }
    double x = r / p_values[choice];
    omega[choice] = omega[choice] * exp(x * gamma_over_K);
}

set_gamma()

void EXP3::set_gamma

(

double

_gamma

)

Reset gamma and associated members to something different.

Definition at line 47 of file EXP3.cpp.

                                  {
    gamma = _gamma;
    one_minus_gamma = 1 - _gamma;
    gamma_over_K = _gamma / static_cast<double>(K);
}

Friends And Related Symbol Documentation

operator<<

ostream & operator<< ( ostream & out, const EXP3 & exp3 )

friend

Definition at line 83 of file EXP3.cpp.

                                                    {
    out << "Omegas:" << endl;
    for (size_t i = 0; i < exp3.K; i++)
        out << exp3.omega[i] << " ";
    out << endl << "p values:" << endl;
    for (size_t i = 0; i < exp3.K; i++)
        out << exp3.p_values[i] << " ";
    out << endl;
    return out;
}

Member Data Documentation

choice

size_t EXP3::choice

private

Store the last choice made.

Definition at line 74 of file EXP3.hpp.

choose_next

bool EXP3::choose_next

private

Belt-and braces: warn if choose/reward happens in the wrong order.

Definition at line 70 of file EXP3.hpp.

gamma

double EXP3::gamma

private

Definition at line 62 of file EXP3.hpp.

gamma_over_K

double EXP3::gamma_over_K

private

Definition at line 65 of file EXP3.hpp.

K

size_t EXP3::K

private

Definition at line 63 of file EXP3.hpp.

omega

vector<double> EXP3::omega

private

Definition at line 60 of file EXP3.hpp.

one_minus_gamma

double EXP3::one_minus_gamma

private

Definition at line 64 of file EXP3.hpp.

p_values

vector<double> EXP3::p_values

private

Definition at line 61 of file EXP3.hpp.

random_generator

boost::random::mt19937 EXP3::random_generator

staticprivate

Random source.

Underlying random number generator for boost::random::discrete_distribution.

Definition at line 59 of file EXP3.hpp.

---

The documentation for this class was generated from the following files:

• /Users/sbh11/Desktop/connection-prover/c++/connect++/source/bandits/EXP3.hpp
• /Users/sbh11/Desktop/connection-prover/c++/connect++/source/bandits/EXP3.cpp