Policies.Exp3R module¶
The Drift-Detection algorithm for non-stationary bandits.
Reference: [[“EXP3 with Drift Detection for the Switching Bandit Problem”, Robin Allesiardo & Raphael Feraud]](https://www.researchgate.net/profile/Allesiardo_Robin/publication/281028960_EXP3_with_Drift_Detection_for_the_Switching_Bandit_Problem/links/55d1927808aee19936fdac8e.pdf)
It runs on top of a simple policy like
Exp3
, andDriftDetection_IndexPolicy
is a wrapper:>>> policy = DriftDetection_IndexPolicy(nbArms, C=1) >>> # use policy as usual, with policy.startGame(), r = policy.choice(), policy.getReward(arm, r)
It uses an additional \(\mathcal{O}(\tau_\max)\) memory for a game of maximum stationary length \(\tau_\max\).
Warning
It works on Exp3
or other parametrizations of the Exp3 policy, e.g., Exp3PlusPlus
.
-
Policies.Exp3R.
VERBOSE
= False¶ Whether to be verbose when doing the search for valid parameter \(\ell\).
-
Policies.Exp3R.
CONSTANT_C
= 1.0¶ The constant \(C\) used in Corollary 1 of paper [[“EXP3 with Drift Detection for the Switching Bandit Problem”, Robin Allesiardo & Raphael Feraud]](https://www.researchgate.net/profile/Allesiardo_Robin/publication/281028960_EXP3_with_Drift_Detection_for_the_Switching_Bandit_Problem/links/55d1927808aee19936fdac8e.pdf).
-
class
Policies.Exp3R.
DriftDetection_IndexPolicy
(nbArms, H=None, delta=None, C=1.0, horizon=None, policy=<class 'Policies.Exp3.Exp3'>, *args, **kwargs)[source]¶ Bases:
Policies.CD_UCB.CD_IndexPolicy
The Drift-Detection generic policy for non-stationary bandits, using a custom Drift-Detection test, for 1-dimensional exponential families.
From [[“EXP3 with Drift Detection for the Switching Bandit Problem”, Robin Allesiardo & Raphael Feraud]](https://www.researchgate.net/profile/Allesiardo_Robin/publication/281028960_EXP3_with_Drift_Detection_for_the_Switching_Bandit_Problem/links/55d1927808aee19936fdac8e.pdf).
-
__init__
(nbArms, H=None, delta=None, C=1.0, horizon=None, policy=<class 'Policies.Exp3.Exp3'>, *args, **kwargs)[source]¶ New policy.
-
H
= None¶ Parameter \(H\) for the Drift-Detection algorithm. Default value is \(\lceil C \sqrt{T \log(T)} \rceil\), for some constant \(C=\)
C
(=CONSTANT_C
by default).
-
delta
= None¶ Parameter \(\delta\) for the Drift-Detection algorithm. Default value is \(\sqrt{\frac{\log(T)}{K T}}\) for \(K\) arms and horizon \(T\).
-
property
proba_random_exploration
¶ Parameter \(\gamma\) for the Exp3 algorithm.
-
property
threshold_h
¶ Parameter \(\varepsilon\) for the Drift-Detection algorithm.
\[\varepsilon = \sqrt{\frac{K \log(\frac{1}{\delta})}{2 \gamma H}}.\]
-
property
min_number_of_pulls_to_test_change
¶ Compute \(\Gamma_{\min}(I) := \frac{\gamma H}{K}\), the minimum number of samples we should have for all arms before testing for a change.
-
detect_change
(arm, verbose=False)[source]¶ Detect a change in the current arm, using a Drift-Detection test (DD).
\[\begin{split}k_{\max} &:= \arg\max_k \tilde{\rho}_k(t),\\ DD_t(k) &= \hat{\mu}_k(I) - \hat{\mu}_{k_{\max}}(I).\end{split}\]The change is detected if there is an arm \(k\) such that \(DD_t(k) \geq 2 * \varepsilon = h\), where
threshold_h
is the threshold of the test, and \(I\) is the (number of the) current interval since the last (global) restart,where \(\tilde{\rho}_k(t)\) is the trust probability of arm \(k\) from the Exp3 algorithm,
and where \(\hat{\mu}_k(I)\) is the empirical mean of arm \(k\) from the data in the current interval.
Warning
FIXME I know this implementation is not (yet) correct… I should count differently the samples we obtained from the Gibbs distribution (when Exp3 uses the trust vector) and from the uniform distribution This \(\Gamma_{\min}(I)\) is the minimum number of samples obtained from the uniform exploration (of probability \(\gamma\)). It seems painful to code correctly, I will do it later.
-
__module__
= 'Policies.Exp3R'¶
-
class
Policies.Exp3R.
Exp3R
(nbArms, policy=<class 'Policies.Exp3.Exp3'>, *args, **kwargs)[source]¶ Bases:
Policies.Exp3R.DriftDetection_IndexPolicy
The Exp3.R policy for non-stationary bandits.
-
__module__
= 'Policies.Exp3R'¶
-
-
class
Policies.Exp3R.
Exp3RPlusPlus
(nbArms, policy=<class 'Policies.Exp3PlusPlus.Exp3PlusPlus'>, *args, **kwargs)[source]¶ Bases:
Policies.Exp3R.DriftDetection_IndexPolicy
The Exp3.R++ policy for non-stationary bandits.
-
__init__
(nbArms, policy=<class 'Policies.Exp3PlusPlus.Exp3PlusPlus'>, *args, **kwargs)[source]¶ New policy.
-
__module__
= 'Policies.Exp3R'¶
-