{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exploring different doubling tricks for different kinds of regret bounds\n", "\n", "- Author: [Lilian Besson](https://perso.crans.org/besson/) and [Emilie Kaufmann](http://chercheurs.lille.inria.fr/ekaufman/),\n", "- License: [MIT License](https://lbesson.mit-license.org/).\n", "- Date: 19 September 2018." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## What do we want?\n", "\n", "This notebooks studies and plot the ratio between a sum like the following\n", "$$ \\sum_{i=0}^{L_T} (T_i - T_{i-1})^\\gamma \\ln(T_i - T_{i-1})^\\delta $$\n", "and the quantity $T^\\gamma (\\ln(T))^\\delta$, where $T \\in\\mathbb{N}$ is a time horizon of some multi-armed bandit problem, and $\\gamma,\\delta \\geq 0$ but not simultaneously zero.\n", "\n", "The successive horizon (in a [doubling trick scheme](https://hal.inria.fr/hal-01736357/)) are defined by $\\forall i\\in\\mathbb{N},\\; T_i := \\lfloor \\exp(\\alpha \\times \\exp(f(i))) \\rfloor$, for some function $f: i \\mapsto f(i)$.\n", "\n", "We study a generic form of functions $f$, with parameters $c,d,e \\geq 0$: $f(i) = c (i^d) (\\log(i))^e$.\n", "\n", "- $d, e = 0, 1$ corresponds to the geometric doubling trick, with $T_i = \\mathcal{O}(2^i)$,\n", "- $d, e = 1, 0$ corresponds to the exponential doubling trick, with $T_i = \\mathcal{O}(2^{2^i})$,\n", "- we are curious about intermediate sequences, that grow faster than any geometric scheme but slower than any exponential scheme. Mathematically, it corresponds to the generic case of $0 < d < 1$ and $e \\geq 0$.\n", "\n", "Moreover, we are especially interested in these two cases:\n", "- $\\gamma, \\delta = 0, 1$ for bounds in regret like $R_T(\\mathcal{A}) = \\mathcal{O}(\\log T)$ (stochastic problem and problem dependent bounds),\n", "- $\\gamma, \\delta = 1/2, 0$ for bounds in regret like $R_T(\\mathcal{A}) = \\mathcal{O}(\\sqrt{T})$ (stochastic problem and worst-case bounds, ie \"minimax bounds\", or adversarial regret).\n", "\n", "To conclude these quick explanation, the notation $L_T$ is the \"last term operator\", for a fixed increasing sequence $(T_i)_{i\\in\\mathbb{N})$:\n", "\n", "$$ L_T = \\min\\{ i \\in\\mathbb{N}, T_{i-1} < T \\leq T_{i} \\}.$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> For more details, please check [this page on SMPyBandits documentation](https://smpybandits.github.io/DoublingTrick.html) or this article: [[What the Doubling Trick Can or Can’t Do for Multi-Armed Bandits, Lilian Besson and Emilie Kaufmann, 2018]](https://hal.inria.fr/hal-01736357)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Dependencies\n", "Here we import some code." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Requirement already satisfied: watermark in ./venv3/lib/python3.6/site-packages (1.7.0)\n", "Requirement already satisfied: ipython in ./venv3/lib/python3.6/site-packages (from watermark) (7.1.1)\n", "Requirement already satisfied: pexpect; sys_platform != \"win32\" in ./venv3/lib/python3.6/site-packages (from ipython->watermark) (4.6.0)\n", "Requirement already satisfied: prompt-toolkit<2.1.0,>=2.0.0 in ./venv3/lib/python3.6/site-packages (from ipython->watermark) (2.0.7)\n", "Requirement already satisfied: setuptools>=18.5 in ./venv3/lib/python3.6/site-packages (from ipython->watermark) (40.6.2)\n", "Requirement already satisfied: pygments in ./venv3/lib/python3.6/site-packages (from ipython->watermark) (2.2.0)\n", "Requirement already satisfied: pickleshare in ./venv3/lib/python3.6/site-packages (from ipython->watermark) (0.7.5)\n", "Requirement already satisfied: decorator in ./venv3/lib/python3.6/site-packages (from ipython->watermark) (4.3.0)\n", "Requirement already satisfied: jedi>=0.10 in ./venv3/lib/python3.6/site-packages (from ipython->watermark) (0.13.1)\n", "Requirement already satisfied: traitlets>=4.2 in ./venv3/lib/python3.6/site-packages (from ipython->watermark) (4.3.2)\n", "Requirement already satisfied: backcall in ./venv3/lib/python3.6/site-packages (from ipython->watermark) (0.1.0)\n", "Requirement already satisfied: ptyprocess>=0.5 in ./venv3/lib/python3.6/site-packages (from pexpect; sys_platform != \"win32\"->ipython->watermark) (0.6.0)\n", "Requirement already satisfied: six>=1.9.0 in ./venv3/lib/python3.6/site-packages (from prompt-toolkit<2.1.0,>=2.0.0->ipython->watermark) (1.11.0)\n", "Requirement already satisfied: wcwidth in ./venv3/lib/python3.6/site-packages (from prompt-toolkit<2.1.0,>=2.0.0->ipython->watermark) (0.1.7)\n", "Requirement already satisfied: parso>=0.3.0 in ./venv3/lib/python3.6/site-packages (from jedi>=0.10->ipython->watermark) (0.3.1)\n", "Requirement already satisfied: ipython-genutils in ./venv3/lib/python3.6/site-packages (from traitlets>=4.2->ipython->watermark) (0.2.0)\n", "Lilian Besson and Emilie Kaufmann \n", "\n", "CPython 3.6.6\n", "IPython 7.1.1\n", "\n", "numpy 1.15.4\n", "matplotlib 3.0.2\n", "seaborn 0.9.0\n", "\n", "compiler : GCC 8.0.1 20180414 (experimental) [trunk revision 259383\n", "system : Linux\n", "release : 4.15.0-38-generic\n", "machine : x86_64\n", "processor : x86_64\n", "CPU cores : 4\n", "interpreter: 64bit\n" ] } ], "source": [ "!pip install watermark\n", "%load_ext watermark\n", "%watermark -v -m -p numpy,matplotlib,seaborn -a \"Lilian Besson and Emilie Kaufmann\"" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "from __future__ import division, print_function # Python 2 compatibility\n", "\n", "__author__ = \"Lilian Besson and Emilie Kaufmann\"\n", "\n", "import numpy as np\n", "import matplotlib as mpl\n", "import matplotlib.pyplot as plt\n", "import seaborn as sns" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "mpl.rcParams['figure.figsize'] = (16, 9)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Change here if needed, use 128 bits floats instead of 64 bits." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "_f = np.float\n", "_f = np.float128" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Defining the functions $f$\n", "\n", "Let's start by defining the functions.\n", "\n", "This is some experimental code to plot some doubling sequences and check numerically some inequalities : like controlling a sum $\\Sigma_i=0^n u_i$ by a constant times to last term $u_n$ and controlling the last term $u_{L_T}$ as a function of $T$." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "#: The constant c in front of the function f.\n", "constant_c_for_the_functions_f = _f(1.0)\n", "constant_c_for_the_functions_f = _f(0.1)\n", "constant_c_for_the_functions_f = _f(0.5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We recall that we are interested by sequences $(T_i)_i$ that grows about $$T_i = \\mathcal{O}(\\exp(\\alpha \\exp(f(i)),$$ and $$f(i) = c \\, i^d \\, (\\log i)^e, \\forall i\\in\\mathbb{N}$$\n", "for $c > 0, d \\geq 0, e \\geq 0$ and $d, e$ not zero simultaneously." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Cheating with a \"safe\" log\n", "I don't want to have $\\log(T_i - T_{i-1}) = -\\infty$ if $T_i = T_{i-1}$ but I want $\\log(0) = 0$. Let's hack it!" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "def mylog(x):\n", " res = np.log(x)\n", " if np.shape(res):\n", " res[np.isinf(res)] = _f(0.0)\n", " else:\n", " if np.isinf(res):\n", " res = _f(0.0)\n", " return res" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Geometric sequences\n", "\n", "$$ f(i) = \\log(i) \\Leftrightarrow T_i = \\mathcal{O}(2^i). $$" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "def function_f__for_geometric_sequences(i, c=constant_c_for_the_functions_f):\n", " r\"\"\" For the *geometric* doubling sequences, :math:`f(i) = c \\times \\log(i)`.\"\"\"\n", " if i <= 0: return _f(0.0)\n", " return c * mylog(i)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exponential sequences\n", "\n", "$$ f(i) = i \\Leftrightarrow T_i = \\mathcal{O}(2^{2^i}). $$" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "def function_f__for_exponential_sequences(i, c=constant_c_for_the_functions_f):\n", " r\"\"\" For the *exponential* doubling sequences, :math:`f(i) = c \\times i`.\"\"\"\n", " return c * i" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Generic function $f$\n", "\n", "As soon as $0 < d < 1$, no matter the value of $e$, $T_i$ will essentially **faster than any geometric sequence** and **slower than any exponential sequence**." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "def function_f__for_generic_sequences(i, c=constant_c_for_the_functions_f, d=_f(0.5), e=_f(0.0)):\n", " r\"\"\" For a certain *generic* family of doubling sequences, :math:`f(i) = c \\times i^{d} \\times (\\log(i))^{e}`.\n", "\n", " - ``d, e = 0, 1`` gives :func:`function_f__for_geometric_sequences`,\n", " - ``d, e = 1, 0`` gives :func:`function_f__for_geometric_sequences`,\n", " - ``d, e = 0.5, 0`` gives an intermediate sequence, growing faster than any geometric sequence and slower than any exponential sequence,\n", " - any other combination has not been studied yet.\n", "\n", " .. warning:: ``d`` should most probably be smaller than 1.\n", " \"\"\"\n", " i = float(i)\n", " if i <= 0: return _f(0.0)\n", " if e == 0:\n", " assert d > 0, \"Error: invalid value of d = {} for function_f__for_generic_sequences, cannot be <= 0.\".format(d) # DEBUG\n", " return c * (i ** d)\n", " assert e > 0, \"Error: invalid value of e = {} for function_f__for_generic_sequences, cannot be <= 0.\".format(e) # DEBUG\n", " if d == 0:\n", " return c * ((mylog(i)) ** e)\n", " return c * (i ** d) * ((mylog(i)) ** e)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Some specific case of intermediate sequences\n", "\n", "Analytically (mathematically) we started to study $f(i) = \\sqrt{i}$." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "def function_f__for_intermediate_sequences(i):\n", " return function_f__for_generic_sequences(i, c=constant_c_for_the_functions_f, d=_f(0.5), e=_f(0.0))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And empirically, I'm curious about other sequences, including $f(i) = i^{1/3}$, $f(i) = i^{2/3}$ and $f(i) = \\sqrt{i} \\sqrt{\\log(i)}$." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "def function_f__for_intermediate2_sequences(i):\n", " return function_f__for_generic_sequences(i, c=constant_c_for_the_functions_f, d=_f(0.3333), e=_f(0.0))\n", "\n", "def function_f__for_intermediate3_sequences(i):\n", " return function_f__for_generic_sequences(i, c=constant_c_for_the_functions_f, d=_f(0.6667), e=_f(0.0))\n", "\n", "def function_f__for_intermediate4_sequences(i):\n", " return function_f__for_generic_sequences(i, c=constant_c_for_the_functions_f, d=_f(0.5), e=_f(0.5))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Defining the sequences and last term" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "#: Value of the parameter :math:`\\alpha` for the :func:`Ti_from_f` function.\n", "alpha_for_Ti = _f(0.1)\n", "alpha_for_Ti = _f(1.0)\n", "alpha_for_Ti = _f(0.5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Sequence $f \\mapsto (T_i)_i$\n", "We need to define a function that take $f$ and give the corresponding sequence $(T_i)$, given as a function $Ti: i \\mapsto T_i$." ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "def Ti_from_f(f, alpha=alpha_for_Ti, *args, **kwargs):\n", " r\"\"\" For any non-negative and increasing function :math:`f: i \\mapsto f(i)`, the corresponding sequence is defined by:\n", "\n", " .. math:: \\forall i\\in\\mathbb{N},\\; T_i := \\lfloor \\exp(\\alpha \\times \\exp(f(i))) \\rfloor.\n", "\n", " .. warning:: :math:`f(i)` can need other parameters, see the examples above. They can be given as ``*args`` or ``**kwargs`` to :func:`Ti_from_f`.\n", "\n", " .. warning:: it should be computed otherwise, I should give :math:`i \\mapsto \\exp(f(i))` instead of :math:`f: i \\mapsto f(i)`. I need to try as much as possible to reduce the risk of overflow errors!\n", " \"\"\"\n", " # WARNING don't forget the floor!\n", " def Ti(i):\n", " this_Ti = np.floor(np.exp(alpha * np.exp(f(float(i), *args, **kwargs))))\n", " if not (np.isinf(this_Ti) or np.isnan(this_Ti)):\n", " this_Ti = int(this_Ti)\n", " # print(\" For f = {}, i = {} gives Ti = {}\".format(f, i, this_Ti)) # DEBUG\n", " return this_Ti\n", " return Ti" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Last term operator $T \\mapsto L_T$\n", "Then we can define the \"last term operator\", by a naive search (and not an analytic derivation).\n", "I don't care if this is not efficient, it works and at least we are sure that $L_T$ satisfies its definition." ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "def last_term_operator_LT(Ti, max_i=10000):\n", " r\"\"\" For a certain function representing a doubling sequence, :math:`T: i \\mapsto T_i`, this :func:`last_term_operator_LT` function returns the function :math:`L: T \\mapsto L_T`, defined as:\n", "\n", " .. math:: \\forall T\\in\\mathbb{N},\\; L_T := \\min\\{ i \\in\\mathbb{N},\\; T \\leq T_i \\}.\n", "\n", " :math:`L_T` is the only integer which satisfies :math:`T_{L_T - 1} < T \\leq T_{L_T}`.\n", " \"\"\"\n", " def LT(T, max_i=max_i):\n", " i = 0\n", " while Ti(i) < T: # very naive loop!\n", " i += 1\n", " if i >= max_i:\n", " raise ValueError(\"LT(T={T}) was unable to find a i <= {max_i} such that T_i >= T.\".format(T, max_i)) # DEBUG\n", " assert Ti(i - 1) < T <= Ti(i), \"Error: i = {} was computed as LT for T = {} and Ti = {} but does not satisfy T_(i-1) < T <= T(i)\".format(i, T, Ti) # DEBUG\n", " # print(\" For LT: i = {} was computed as LT for T = {} and Ti = {} and satisfies T(i-1) = {} < T <= T(i) = {}\".format(i, T, Ti, Ti(i-1), Ti(i))) # DEBUG\n", " return i\n", " return LT" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Helper for the plot" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [], "source": [ "def markers_colors(nb):\n", " \"\"\"Make unique markers and colors for nb plots.\"\"\"\n", " allmarkers = ['o', 'D', 'v', 'p', '<', 's', '^', '*', 'h', '>']\n", " longlist = allmarkers * (1 + int(nb / float(len(allmarkers)))) # Cycle the good number of time\n", " markers = longlist[:nb] # Truncate\n", " colors = sns.hls_palette(nb + 1)[:nb]\n", " return markers, colors" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Plotting what we want\n", "\n", "By default, we will study the following doubling sequences:\n", "\n", "- **Geometric** doubling with $d=0, e=1$,\n", "- Intermediate doubling with $d=1/2, e=0$ (the one I'm excited about), \n", "- Intermediate doubling with $d=1/3, e=0$,\n", "- Intermediate doubling with $d=2/3, e=0$,\n", "- Intermediate doubling with $d=1/2, e=1/2$,\n", "- **Exponential** doubling with $d=1, e=0$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Plotting the values of the sequences\n", "\n", "First, we want to check how much do these sequences increase." ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": [ "def plot_doubling_sequences(\n", " i_min=1, i_max=30,\n", " list_of_f=(\n", " function_f__for_geometric_sequences,\n", " function_f__for_intermediate_sequences,\n", " function_f__for_intermediate2_sequences,\n", " function_f__for_intermediate3_sequences,\n", " function_f__for_intermediate4_sequences,\n", " function_f__for_exponential_sequences,\n", " ),\n", " label_of_f=(\n", " \"Geometric doubling (d=0, e=1)\",\n", " \"Intermediate doubling (d=1/2, e=0)\",\n", " \"Intermediate doubling (d=1/3, e=0)\",\n", " \"Intermediate doubling (d=2/3, e=0)\",\n", " \"Intermediate doubling (d=1/2, e=1/2)\",\n", " \"Exponential doubling (d=1, e=0)\",\n", " ),\n", " *args, **kwargs\n", " ):\n", " r\"\"\" Display a plot to illustrate the values of the :math:`T_i` as a function of :math:`i` for some i.\n", "\n", " - Can accept many functions f (and labels).\n", " \"\"\"\n", " markers, colors = markers_colors(len(list_of_f))\n", " fig = plt.figure()\n", "\n", " i_s = np.arange(i_min, i_max, dtype=np.float128)\n", " # now for each function f\n", " for num_f, (f, la) in enumerate(zip(list_of_f, label_of_f)):\n", " print(\"\\n\\nThe {}th function is referred to as {} and is {}\".format(num_f, la, f)) # DEBUG\n", " Ti = Ti_from_f(f)\n", " values_of_Ti = [Ti(i) for i in i_s]\n", " plt.plot(i_s, values_of_Ti, label=la, lw=4, ms=7, color=colors[num_f], marker=markers[num_f])\n", "\n", " plt.legend()\n", " plt.xlabel(r\"Value of the time horizon $i = {},...,{}$\".format(i_min, i_max))\n", " plt.title(r\"Comparison of the values of $T_i$\")\n", " plt.show()\n", " # return fig" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Plotting the ratio for our upper-bound" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [], "source": [ "def plot_quality_first_upper_bound(\n", " Tmin=2, Tmax=int(1e8), nbTs=100,\n", " gamma=_f(0.0), delta=_f(1.0), # XXX bound in RT <= log(T)\n", " # gamma=_f(0.5), delta=_f(0.0), # XXX bound in RT <= sqrt(T)\n", " # gamma=_f(0.5), delta=_f(0.5), # XXX bound in RT <= sqrt(T * log(T))\n", " # gamma=_f(0.66667), delta=_f(1.0), # XXX another weird bound in RT <= T^2/3 * log(T)\n", " list_of_f=(\n", " function_f__for_geometric_sequences,\n", " function_f__for_intermediate_sequences,\n", " function_f__for_intermediate2_sequences,\n", " function_f__for_intermediate3_sequences,\n", " function_f__for_intermediate4_sequences,\n", " function_f__for_exponential_sequences,\n", " ),\n", " label_of_f=(\n", " \"Geometric doubling (d=0, e=1)\",\n", " \"Intermediate doubling (d=1/2, e=0)\",\n", " \"Intermediate doubling (d=1/3, e=0)\",\n", " \"Intermediate doubling (d=2/3, e=0)\",\n", " \"Intermediate doubling (d=1/2, e=1/2)\",\n", " \"Exponential doubling (d=1, e=0)\",\n", " ),\n", " show_Ti_m_Tim1=True,\n", " *args, **kwargs\n", " ):\n", " r\"\"\" Display a plot to compare numerically between the following sum :math:`S` and the upper-bound we hope to have, :math:`T^{\\gamma} (\\log T)^{\\delta}`, as a function of :math:`T` for some values between :math:`T_{\\min}` and :math:`T_{\\max}`:\n", "\n", " .. math:: S := \\sum_{i=0}^{L_T} (T_i - T_{i-1})^{\\gamma} (\\log (T_i - T_{i-1}))^{\\delta}.\n", "\n", " - Can accept many functions f (and labels).\n", " - Can use :math:`T_i` instead of :math:`T_i - T_{i-1}` if ``show_Ti_m_Tim1=False`` (default is to use the smaller possible bound, with difference of sequence lengths, :math:`T_i - T_{i-1}`).\n", "\n", " .. warning:: This is still ON GOING WORK.\n", " \"\"\"\n", " markers, colors = markers_colors(len(list_of_f))\n", " fig = plt.figure()\n", "\n", " Ts = np.floor(np.linspace(_f(Tmin), _f(Tmax), num=nbTs, dtype=np.float128))\n", " the_bound_we_want = (Ts ** gamma) * (mylog(Ts) ** delta)\n", "\n", " # now for each function f\n", " for num_f, (f, la) in enumerate(zip(list_of_f, label_of_f)):\n", " print(\"\\n\\nThe {}th function is referred to as {} and is {}\".format(num_f, la, f)) # DEBUG\n", " Ti = Ti_from_f(f)\n", " LT = last_term_operator_LT(Ti)\n", " the_sum_we_have = np.zeros_like(Ts, dtype=np.float128)\n", " for j, Tj in enumerate(Ts):\n", " LTj = LT(Tj)\n", " if show_Ti_m_Tim1:\n", " the_sum_we_have[j] = sum(\n", " ((Ti(i)-Ti(i-1)) ** gamma) * (mylog((Ti(i)-Ti(i-1))) ** delta)\n", " for i in range(1, LTj + 1)\n", " )\n", " else:\n", " the_sum_we_have[j] = sum(\n", " (Ti(i) ** gamma) * (mylog(Ti(i)) ** delta)\n", " for i in range(0, LTj + 1)\n", " )\n", " # print(\"For j = {}, Tj = {}, gives LTj = {}, and the value of the sum from i=0 to LTj is = \\n{}.\".format(j, Tj, LTj, the_sum_we_have[j])) # DEBUG\n", " plt.plot(Ts, the_sum_we_have / the_bound_we_want, label=la, lw=4, ms=4, color=colors[num_f], marker=markers[num_f])\n", "\n", " plt.legend()\n", " plt.xlabel(r\"Value of the time horizon $T = {},...,{}$\".format(Tmin, Tmax))\n", " str_of_Tj_or_dTj = \"T_i - T_{i-1}\" if show_Ti_m_Tim1 else \"T_i\"\n", " plt.title(r\"Ratio of the sum $\\sum_{i=0}^{L_T} (%s)^{\\gamma} (\\log(%s))^{\\delta}$ and the upper-bound $T^{\\gamma} \\log(T)^{\\delta}$, for $\\gamma=%.3g$, $\\delta=%.3g$.\" % (str_of_Tj_or_dTj, str_of_Tj_or_dTj, gamma, delta)) # DEBUG\n", " plt.show()\n", " # return fig" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "## Results" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Values of the doubling sequences\n", "We check that the exponential sequence is growing WAY faster than all the others." ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "scrolled": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "\n", "The 0th function is referred to as Geometric doubling (d=0, e=1) and is