Table of Contents

1  Visualizing detection of change points for nonstationary problems

1.1  Creating the MAB problems

1.2  Plotting the history of means

1.3  Plotting with indications on the restart times

1.4  Data for problem 1

1.5  Data for problem 2

---

Visualizing detection of change points for nonstationary problems

First, be sure to be in the main folder, or to have installed `SMPyBandits <https://github.com/SMPyBandits/SMPyBandits>`__, and import MAB from Environment package:

!pip install SMPyBandits watermark

import sys
sys.path.append("..")

%load_ext watermark
%watermark -v -m -a "Lilian Besson"

The watermark extension is already loaded. To reload it, use:
  %reload_ext watermark
Lilian Besson

CPython 3.6.7
IPython 7.4.0

compiler   : GCC 8.2.0
system     : Linux
release    : 4.15.0-48-generic
machine    : x86_64
processor  : x86_64
CPU cores  : 4
interpreter: 64bit

from SMPyBandits.Environment.MAB import PieceWiseStationaryMAB, MAB

%matplotlib notebook
import matplotlib as mpl
mpl.rcParams['figure.dpi'] = 120
mpl.rcParams['figure.figsize'] = (10, 5.6)
import matplotlib.pyplot as plt

import seaborn as sns

sns.set(context="talk", style="whitegrid", palette="hls", font="sans-serif", font_scale=0.9)

from SMPyBandits.Environment.plotsettings import nrows_ncols

def palette(nb):
    return sns.hls_palette(nb + 1)[:nb]

def makemarkers(nb):
    allmarkers = ['o', 'D', '^', '<', 'v', 'p', 's', '*', 'h', '>']
    longlist = allmarkers * (1 + int(nb / float(len(allmarkers))))  # Cycle the good number of time
    return longlist[:nb]  # Truncate

Creating the MAB problems

from SMPyBandits.configuration_nonstationary import *

envs = configuration['environment']
envs

[{'arm_type': SMPyBandits.Arms.Bernoulli.Bernoulli,
  'params': {'listOfMeans': [[0.3, 0.5, 0.9],
    [0.3, 0.2, 0.9],
    [0.3, 0.2, 0.1],
    [0.7, 0.2, 0.1],
    [0.7, 0.5, 0.1]],
   'changePoints': [0, 1000, 2000, 3000, 4000]}},
 {'arm_type': SMPyBandits.Arms.Bernoulli.Bernoulli,
  'params': {'listOfMeans': [[0.4, 0.5, 0.9],
    [0.5, 0.4, 0.7],
    [0.6, 0.3, 0.5],
    [0.7, 0.2, 0.3],
    [0.8, 0.1, 0.1]],
   'changePoints': [0, 1000, 2000, 3000, 4000]}}]

env1 = envs[0]
env2 = envs[1]

pb1 = PieceWiseStationaryMAB(env1)

  Special MAB problem, with arm (possibly) changing at every time step, read from a dictionnary 'configuration' = {'arm_type': <class 'SMPyBandits.Arms.Bernoulli.Bernoulli'>, 'params': {'listOfMeans': [[0.3, 0.5, 0.9], [0.3, 0.2, 0.9], [0.3, 0.2, 0.1], [0.7, 0.2, 0.1], [0.7, 0.5, 0.1]], 'changePoints': [0, 1000, 2000, 3000, 4000]}} ...
 - with 'arm_type' = <class 'SMPyBandits.Arms.Bernoulli.Bernoulli'>
 - with 'params' = {'listOfMeans': [[0.3, 0.5, 0.9], [0.3, 0.2, 0.9], [0.3, 0.2, 0.1], [0.7, 0.2, 0.1], [0.7, 0.5, 0.1]], 'changePoints': [0, 1000, 2000, 3000, 4000]}
 - with 'listOfMeans' = [[0.3 0.5 0.9]
 [0.3 0.2 0.9]
 [0.3 0.2 0.1]
 [0.7 0.2 0.1]
 [0.7 0.5 0.1]]
 - with 'changePoints' = [0, 1000, 2000, 3000, 4000]


 ==> Creating the dynamic arms ...
   - with 'nbArms' = 3
   - with 'arms' = [B(0.3), B(0.5), B(0.9)]
 - Initial draw of 'means' = [0.3 0.5 0.9]

pb2 = PieceWiseStationaryMAB(env2)

  Special MAB problem, with arm (possibly) changing at every time step, read from a dictionnary 'configuration' = {'arm_type': <class 'SMPyBandits.Arms.Bernoulli.Bernoulli'>, 'params': {'listOfMeans': [[0.4, 0.5, 0.9], [0.5, 0.4, 0.7], [0.6, 0.3, 0.5], [0.7, 0.2, 0.3], [0.8, 0.1, 0.1]], 'changePoints': [0, 1000, 2000, 3000, 4000]}} ...
 - with 'arm_type' = <class 'SMPyBandits.Arms.Bernoulli.Bernoulli'>
 - with 'params' = {'listOfMeans': [[0.4, 0.5, 0.9], [0.5, 0.4, 0.7], [0.6, 0.3, 0.5], [0.7, 0.2, 0.3], [0.8, 0.1, 0.1]], 'changePoints': [0, 1000, 2000, 3000, 4000]}
 - with 'listOfMeans' = [[0.4 0.5 0.9]
 [0.5 0.4 0.7]
 [0.6 0.3 0.5]
 [0.7 0.2 0.3]
 [0.8 0.1 0.1]]
 - with 'changePoints' = [0, 1000, 2000, 3000, 4000]


 ==> Creating the dynamic arms ...
   - with 'nbArms' = 3
   - with 'arms' = [B(0.4), B(0.5), B(0.9)]
 - Initial draw of 'means' = [0.4 0.5 0.9]

Plotting the history of means

horizon = 5000

fig = pb1.plotHistoryOfMeans(horizon=horizon)

Plotting with indications on the restart times

Now in a function, we use this data:

def plotHistoryOfMeans_with_restart(restart_points, labels, pb, problemId=1, horizon=horizon):
    nbAlgorithms = len(labels)
    nbArms = pb.nbArms
    means_of_all_arms = pb.get_allMeans(horizon=horizon)

    colors1 = sns.hls_palette(nbArms + 1)[:nbArms]
    markers1 = makemarkers(nbArms)
    linestyles1 = ['--', '-.', ':'] * nbArms
    linestyles1 = linestyles1[:nbArms]
    linewidths1 = [5, 3] * nbArms
    linewidths1 = linewidths1[:nbArms]

    colors2 = sns.husl_palette(nbAlgorithms + 1)[:nbAlgorithms]
    markers2 = makemarkers(nbAlgorithms)

    nrows, ncols = nrows_ncols(nbAlgorithms)

    fig, axes = plt.subplots(nrows, ncols, sharex=True, sharey=True)
    fig.suptitle("Locations of change-points detected by different algorithms (problem {})".format(problemId))

    # start for each algorithm
    for policyId, ax in enumerate(axes.flat[:nbAlgorithms]):
    # for policyId, label in enumerate(labels):
        label = labels[policyId]
        data = restart_points[label]
        regret = data["regret"]

        for armId in range(nbArms):
            meanOfThisArm = means_of_all_arms[armId, :]
            ax.plot(meanOfThisArm,
                     color=colors1[armId],
                     # marker=markers[armId], markevery=(armId / 50., 0.1),
                     label='Arm #{}'.format(armId),
                     #linestyle=linestyles1[armId],
                     #linewidth=linewidths1[armId],
                     linewidth=linewidths1[0],
                     alpha=0.7)

        plt.ylim(0, 1)
        ymin, ymax = plt.ylim()
        # for tau in pb.changePoints:
        #     if tau > 0 and tau < horizon:
        #         plt.vlines(tau, ymin, ymax, linestyles='dotted', alpha=0.7)

        #ax.set_xlabel(r"Time steps $t = 1...T$, horizon $T = {}$".format(horizon))
        #ax.set_ylabel(r"Successive means of the $K = {}$ arms".format(nbArms))
        ax.set_title("{} (regret $= {}$)".format(label, regret))
        #ax.set_title("Location of change-points detected by algorithm {} (regret = {})".format(label, regret))

        Xs, Ys = [], []
        for armId in range(nbArms):
            means = means_of_all_arms[armId]
            restarts = data[armId]
            times = [ time for time, nbsample in restarts ]
            Xs = times
            Ys = [ means[time] for time in times ]
            if Xs:
                ax.plot(Xs, Ys,
                        #color=colors2[policyId],
                        color=colors1[armId],
                        marker=markers2[policyId], markersize=15,
                        linestyle='',
                        label=label,
                        alpha=0.9)

    #plt.tight_layout(rect=[0.04, 0.04, 0.75, 0.92])
    #plt.legend(loc='center left', bbox_to_anchor=(1, 0.5), numpoints=1, fancybox=True, framealpha=0.8)

    plt.show()
    return fig, axes

Data for problem 1

labels_1 = [
    "M-klUCB",
    "CUSUM-klUCB",
    "GLR-klUCB Local",
    "GLR-klUCB Global",
]

Then we have a dictionary mapping a label to the data of interest. This is a dictionary mapping arm to list of couple (time, nb of samples since last restart).

restart_points_1 = {
    "M-klUCB": {
        0: [(3080, 828)],
        1: [],
        2: [(2055, 1811)],
        "regret": 280,
    },
    "CUSUM-klUCB": {
        0: [(3027, 825), (3505, 466), (4914, 1304)],
        1: [(2512, 249), (4383, 123)],
        2: [(2011, 1861), ],
        "regret": 150,
    },
    "GLR-klUCB Local": {
        0: [(3032, 840)],
        1: [],
        2: [(2014, 1970)],
        "regret": 63,
    },
    "GLR-klUCB Global": {
        0: [(3031, 827)],
        1: [],
        2: [(2009, 1972)],
        "regret": 71,
    },
}

Let’s try!

plotHistoryOfMeans_with_restart(restart_points_1, labels_1, pb1, problemId=1, horizon=horizon)

(<Figure size 1200x672 with 4 Axes>,
 array([[<matplotlib.axes._subplots.AxesSubplot object at 0x7f3148dbccf8>,
         <matplotlib.axes._subplots.AxesSubplot object at 0x7f3148d66dd8>],
        [<matplotlib.axes._subplots.AxesSubplot object at 0x7f3148d7c4a8>,
         <matplotlib.axes._subplots.AxesSubplot object at 0x7f3148d179b0>]],
       dtype=object))

plt.savefig("Visualizing_locations_of_change_points_for_different_algorithms__4algs_Pb1.png")
plt.savefig("Visualizing_locations_of_change_points_for_different_algorithms__4algs_Pb1.pdf")

Data for problem 2

labels_2 = labels_1

restart_points_2 = {
    "M-klUCB": {
        0: [],
        1: [],
        2: [],
        "regret": 570,
    },
    "CUSUM-klUCB": {
        0: [(2305, 185), (2591, 272), (3387, 770)],
        1: [(3677, 169)],
        2: [(1055, 963), (2051, 922)],
        "regret": 150,
    },
    "GLR-klUCB Local": {
        0: [(2367, 1006), (4203, 1873)],
        1: [],
        2: [(1070, 1030)],
        "regret": 115,
    },
    "GLR-klUCB Global": {
        0: [(2705, 1038)],
        1: [],
        2: [(1111, 1060)],
        "regret": 125,
    },
}

plotHistoryOfMeans_with_restart(restart_points_2, labels_2, pb2, problemId=2, horizon=horizon)

(<Figure size 1200x672 with 4 Axes>,
 array([[<matplotlib.axes._subplots.AxesSubplot object at 0x7f3148cc22b0>,
         <matplotlib.axes._subplots.AxesSubplot object at 0x7f31495acb70>],
        [<matplotlib.axes._subplots.AxesSubplot object at 0x7f3148cff9b0>,
         <matplotlib.axes._subplots.AxesSubplot object at 0x7f314d42dcc0>]],
       dtype=object))

plt.savefig("Visualizing_locations_of_change_points_for_different_algorithms__4algs_Pb2.png")
plt.savefig("Visualizing_locations_of_change_points_for_different_algorithms__4algs_Pb2.pdf")