# -*- coding: utf-8 -*-
""" The SparseUCB policy, designed to tackle sparse stochastic bandit problems:
- This means that only a small subset of size ``s`` of the ``K`` arms has non-zero means.
- The SparseUCB algorithm requires to known **exactly** the value of ``s``.
- Reference: [["Sparse Stochastic Bandits", by J. Kwon, V. Perchet & C. Vernade, COLT 2017](https://arxiv.org/abs/1706.01383)].
.. warning:: This algorithm only works for sparse Gaussian (or sub-Gaussian) stochastic bandits.
"""
from __future__ import division, print_function # Python 2 compatibility
__author__ = "Lilian Besson"
__version__ = "0.6"
from math import sqrt, log
from enum import Enum # For the different states
import numpy as np
np.seterr(divide='ignore') # XXX dangerous in general, controlled here!
try:
from .UCBalpha import UCBalpha
except ImportError:
from UCBalpha import UCBalpha
#: Different states during the SparseUCB algorithm.
#:
#: - ``RoundRobin`` means all are sampled once.
#: - ``ForceLog`` uniformly explores arms that are in the set :math:`\mathcal{J}(t) \setminus \mathcal{K}(t)`.
#: - ``UCB`` is the phase that the algorithm should converge to, when a normal UCB selection is done only on the "good" arms, i.e., :math:`\mathcal{K}(t)`.
Phase = Enum('Phase', ['RoundRobin', 'ForceLog', 'UCB'])
#: Default parameter for :math:`\alpha` for the UCB indexes.
ALPHA = 4
# --- The interesting class
[docs]class SparseUCB(UCBalpha):
""" The SparseUCB policy, designed to tackle sparse stochastic bandit problems.
- By default, assume ``sparsity`` = ``nbArms``.
"""
[docs] def __init__(self, nbArms, sparsity=None, alpha=ALPHA, lower=0., amplitude=1.):
super(SparseUCB, self).__init__(nbArms, alpha=alpha, lower=lower, amplitude=amplitude)
if sparsity is None or sparsity == nbArms:
sparsity = nbArms
print("Warning: regular UCBalpha should be used instead of SparseUCB if 'sparsity' = 'nbArms' = {} ...".format(nbArms)) # DEBUG
assert 1 <= sparsity <= nbArms, "Error: 'sparsity' has to be in [1, nbArms = {}] but was {} ...".format(nbArms, sparsity) # DEBUG
self.sparsity = sparsity #: Known value of the sparsity of the current problem.
self.phase = Phase.RoundRobin #: Current phase of the algorithm.
# internal memory
self.force_to_see = np.full(nbArms, True) #: Binary array for the set :math:`\mathcal{J}(t)`.
self.goods = np.full(nbArms, True) #: Binary array for the set :math:`\mathcal{K}(t)`.
self.offset = -1 #: Next arm to sample, for the Round-Robin phase
# --- pretty printing
[docs] def __str__(self):
return r"SparseUCB($s={}$, $\alpha={:.3g}$)".format(self.sparsity, self.alpha)
[docs] def startGame(self):
""" Initialize the policy for a new game."""
super(SparseUCB, self).startGame()
self.phase = Phase.RoundRobin
self.force_to_see.fill(True) # faster than sets
self.goods.fill(True) # faster than sets
self.offset = -1
# --- Update the two sets
[docs] def update_j(self):
r""" Recompute the set :math:`\mathcal{J}(t)`:
.. math:: \mathcal{J}(t) = \left\{ k \in [1,...,K]\;, \frac{X_k(t)}{N_k(t)} \geq \sqrt{\frac{\alpha \log(N_k(t))}{N_k(t)}} \right\}.
"""
# assert np.all(self.pulls >= 1), "Error: at least one arm was not already pulled: pulls = {} ...".format(self.pulls) # DEBUG
self.force_to_see.fill(False) # faster than sets
means = self.rewards / self.pulls
means[self.pulls < 1] = float('+inf')
UCB_J = np.sqrt((self.alpha * np.log(self.pulls)) / self.pulls)
UCB_J[self.pulls < 1] = float('+inf')
self.force_to_see[means >= UCB_J] = True
[docs] def update_k(self):
r""" Recompute the set :math:`\mathcal{K}(t)`:
.. math:: \mathcal{K}(t) = \left\{ k \in [1,...,K]\;, \frac{X_k(t)}{N_k(t)} \geq \sqrt{\frac{\alpha \log(t)}{N_k(t)}} \right\}.
"""
# assert np.all(self.pulls >= 1), "Error: at least one arm was not already pulled: pulls = {} ...".format(self.pulls) # DEBUG
self.goods.fill(False) # faster than sets
means = self.rewards / self.pulls
means[self.pulls < 1] = float('+inf')
UCB_K = np.sqrt((self.alpha * np.log(self.t)) / self.pulls)
UCB_K[self.pulls < 1] = float('+inf')
self.goods[means >= UCB_K] = True
# --- SparseUCB choice() method
[docs] def choice(self):
r""" Choose the next arm to play:
- If still in a Round-Robin phase, play the next arm,
- Otherwise, recompute the set :math:`\mathcal{J}(t)`,
- If it is too small, if :math:`\mathcal{J}(t) < s`:
+ Start a new Round-Robin phase from arm 0.
- Otherwise, recompute the second set :math:`\mathcal{K}(t)`,
- If it is too small, if :math:`\mathcal{K}(t) < s`:
+ Play a Force-Log step by choosing an arm uniformly at random from the set :math:`\mathcal{J}(t) \setminus \mathcal{K}(t)`.
- Otherwise,
+ Play a UCB step by choosing an arm with highest UCB index from the set :math:`\mathcal{K}(t)`.
"""
# print(" At step t = {} a SparseUCB algorithm was in phase {} ...".format(self.t, self.phase)) # DEBUG
if (self.phase == Phase.RoundRobin) and ((1 + self.offset) < self.nbArms):
# deterministic phase
self.offset += 1
return self.offset
else:
self.update_j()
j = self.force_to_see
# DEBUG small checks, to remove soon
# assert np.all(j[k]), "Error: set k = {} was not found include in set j = {} but it should be...".format(k, j) # DEBUG
# set_j = set(np.nonzero(j)[0])
# set_k = set(np.nonzero(k)[0])
# assert set_k <= set_j, "Error: set k = {} was not found include in set j = {} but it should be...".format(set_k, set_j) # DEBUG
# print(" At step t = {}, set j = {} and set k = {} ...".format(self.t, set_j, set_k)) # DEBUG
# 1st case: Round-Robin phase
if np.sum(j) < self.sparsity:
self.phase = Phase.RoundRobin
self.offset = 0
return self.offset
# 2nd case: Force-Log Phase
else:
self.update_k()
k = self.goods
if np.sum(k) < self.sparsity:
self.phase = Phase.ForceLog
diff_of_set = j & (~k) # component-wise boolean operations to the numpy array
return np.random.choice(np.nonzero(diff_of_set)[0])
# 3rd case: UCB phase
else:
# if self.phase != Phase.UCB: print("{}: at time t = {}, the set of good arms was identified as {} for the first time...".format(self, self.t, np.nonzero(self.goods)[0])) # DEBUG
self.phase = Phase.UCB
return self.choiceFromSubSet(availableArms=np.nonzero(self.goods)[0])
# --- computeIndex and computeAllIndex are the same as UCBalpha