MABSearch (Experiment Ready Version).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MABSearch: The Bandit Way of Learning the Learning Rate—A Harmony Between Reinforcement Learning and Gradient Descent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Published in: National Academy Science Letters Journal, Springer Publication [SCI Indexed].\n",
    "Link to paper: https://link.springer.com/article/10.1007/s40009-023-01292-1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How to Cite:\n",
    "Syed Shahul Hameed, A.S., Rajagopalan, N. MABSearch: The Bandit Way of Learning the Learning Rate—A Harmony Between Reinforcement Learning and Gradient Descent. Natl. Acad. Sci. Lett. (2023). https://doi.org/10.1007/s40009-023-01292-1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is an experiment ready version of the proposed MABSearch and Other Constant Gradient Descent Algorithms.\n",
    "For a clean, easier to understand version of the proposed algorithm please see the file titled: \"MABSearch.ipynb\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For Any suggestions or doubt mail to: shahulshan81@gmail.com\n",
    "Cite the paper, if you find it useful."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "import threading\n",
    "import time\n",
    "import math, statistics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Benchmark Test Functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How To Run: Run any one of the benchmark function first. And then run the required cells for the algorithm to be tried out.\n",
    "\n",
    "The code of the benchmark functions were taken from: https://github.com/nathanrooy/landscapes/blob/master/landscapes/single_objective.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "def f(x): #F1beale\n",
    "    x,y = x[0],x[1]\n",
    "    '''\n",
    "    Beale Function\n",
    "    global minimum: f(x=3, y=0.5) = 0\n",
    "    bounds: -4.5 <= x, y <= 4.5\n",
    "    '''\n",
    "    return ((1.500 - x + x*y)**2 +\n",
    "            (2.250 - x + x*y**2)**2 +\n",
    "            (2.625 - x + x*y**3)**2)  \n",
    "mrnge = [-5,5] # Feasible region.\n",
    "optimum = 0 #well known minimum value.\n",
    "dim=2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "def f(xy):#F2Gold-Stein\n",
    "    '''\n",
    "    Goldstein-Price Function\n",
    "    global minimum: f(0, -1) = 3\n",
    "    bounds: -2 <= x, y <= 2\n",
    "    '''\n",
    "    x, y = xy[0], xy[1]\n",
    "    return ((1 + (x + y + 1)**2 * (19 - 14*x + 3*x**2 - 14*y + 6*x*y + 3*y**2)) *\n",
    "            (30 + (2*x-3*y)**2 * (18 - 32*x + 12*x**2 + 48*y - 36*x*y + 27*y**2)))\n",
    "mrnge = [-2,2]\n",
    "optimum = 3\n",
    "dim=2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "def f(x):#F3Matyas\n",
    "    x,y = x[0],x[1]\n",
    "    '''\n",
    "    Matyas Function\n",
    "    global minimum: f(x=0, y=0) = 0\n",
    "    bounds: -10 <= x, y <= 10\n",
    "    '''\n",
    "    return 0.26*(x**2 + y**2) - 0.48*x*y #matyas\n",
    "mrnge = [-10,10]\n",
    "optimum = 0\n",
    "dim = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "def f(xy): #F4griewank\n",
    "    '''Griwank Function\n",
    "    Bounds: x_i in [-600, 600] for all i=1,...,d\n",
    "    Global minimum: f(x)=0 at x=(0,...,0)\n",
    "\n",
    "    '''\n",
    "    a, b, = 0, 1\n",
    "    for i, v in enumerate(xy):\n",
    "        a += v**2 / 4000.0\n",
    "        b *= np.cos(v/np.sqrt(i+1))\n",
    "    return a - b + 1\n",
    "mrnge = [-100,100]\n",
    "optimum = 0\n",
    "dim=5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "def f(x): #F5dixon price\n",
    "    '''Dixon and Price Function\n",
    "    Notes\n",
    "    -----\n",
    "    global minimum: f(x*)=0 at x_i = 2^-(((2^i)-2)/(2^i))\n",
    "    bounds: x_i in [-10, 10] for i=1,...,n\n",
    "    References\n",
    "    ----------\n",
    "    L. C. W. Dixon, R. C. Price, “The Truncated Newton Method for Sparse\n",
    "    Unconstrained Optimisation Using Automatic Differentiation,” Journal of\n",
    "    Optimization Theory and Applications, vol. 60, no. 2, pp. 261-275, 1989.\n",
    "    '''\n",
    "    return (x[0] - 1.0)**2.0 + sum([i*(2.0*x[i]**2.0 - x[i-1])**2.0 for i in range(1, len(x))])\n",
    "mrnge = [-10,10]\n",
    "optimum = 0\n",
    "dim = 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "#Run this cell before running any one of the CGD Algorithm\n",
    "def derivative (arr, pos):\n",
    "    h = 0.000000001\n",
    "    temp = arr.copy()\n",
    "    temp[pos] = temp[pos] + h\n",
    "    num = f(temp) - f(arr)\n",
    "    return num/h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Run this cell before running any of the algorithms\n",
    "def is_in_fsble_rgn (var) : \n",
    "#Function to check, whether the newly sampled point is within the feasible region or not. IF not within the feasibile region sample new location.\n",
    "    if math.floor (var) not in np.arange(mrnge[0],mrnge[1]):\n",
    "        return np.random.uniform(mrnge[0],mrnge[1])\n",
    "    else:\n",
    "        return var"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CGD - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "code_folding": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Finished in 1.3 second(s)\n"
     ]
    }
   ],
   "source": [
    "minima_arr = [] # to store the best value found in each of the 30 runs.\n",
    "start = time.perf_counter()\n",
    "for run in range(30): #Run Experiment for 30 Times\n",
    "    w = np.random.uniform(mrnge[0],mrnge[1], size=(dim)) #Random initial location/starting point\n",
    "    for i in range (dim * 1000):\n",
    "        for d in range (dim):\n",
    "            w[d] = w[d] - 0.1 * derivative(w,d) #learning rate = 0.1\n",
    "            w[d] = is_in_fsble_rgn(w[d])\n",
    "    minima_arr.append(f(w))\n",
    "finish = time.perf_counter()\n",
    "print(f'Finished in {round(finish-start, 2)} second(s)') #prints the time taken for this cell to execute."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "code_folding": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.251047652849416 0.3527592370344033 0.2951226639759463 0.05126329854176754\n",
      "SR:  0.0\n"
     ]
    }
   ],
   "source": [
    "#Summary (Best, Worst, Mean, SD and SR) of 30 runs. Run this cell to get the result of CGD-1\n",
    "print(min(minima_arr), max(minima_arr),statistics.mean(minima_arr) ,statistics.stdev(minima_arr))\n",
    "j=0\n",
    "for i in range(len(minima_arr)):\n",
    "    if abs(minima_arr[i] - optimum )< 0.000001 :\n",
    "        j+=1\n",
    "print(\"SR: \",j/30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CGD - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "code_folding": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Finished in 1.28 second(s)\n"
     ]
    }
   ],
   "source": [
    "minima_arr = []\n",
    "start = time.perf_counter()\n",
    "for run in range(30):\n",
    "    w = np.random.uniform(mrnge[0],mrnge[1], size=(dim))\n",
    "    for i in range (dim * 1000):\n",
    "        for d in range (dim):\n",
    "            w[d] = w[d] - 0.01 * derivative(w,d)\n",
    "            w[d] = is_in_fsble_rgn(w[d])\n",
    "    minima_arr.append(f(w))\n",
    "finish = time.perf_counter()\n",
    "print(f'Finished in {round(finish-start, 2)} second(s)')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "code_folding": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.3944201071186366e-08 1.7019307428013413 0.3859459517125288 0.7116001809737352\n",
      "SR:  0.7\n"
     ]
    }
   ],
   "source": [
    "#Summary (Best, Worst, Mean, SD and SR) of 30 runs. Run this cell to get the result of CGD-2\n",
    "print(min(minima_arr), max(minima_arr),statistics.mean(minima_arr) ,statistics.stdev(minima_arr))\n",
    "j=0\n",
    "for i in range(len(minima_arr)):\n",
    "    if abs(minima_arr[i] - optimum )< 0.000001 :\n",
    "        j+=1\n",
    "print(\"SR: \",j/30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CGD-3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "code_folding": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Finished in 1.29 second(s)\n"
     ]
    }
   ],
   "source": [
    "minima_arr = []\n",
    "start = time.perf_counter()\n",
    "for run in range(30): \n",
    "    w = np.random.uniform(mrnge[0],mrnge[1], size=(dim))\n",
    "    for i in range (dim * 1000):\n",
    "        for d in range (dim):\n",
    "            w[d] = w[d] - 0.001 * derivative(w,d)\n",
    "            w[d] = is_in_fsble_rgn(w[d])\n",
    "    minima_arr.append(f(w))\n",
    "finish = time.perf_counter()\n",
    "print(f'Finished in {round(finish-start, 2)} second(s)')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "code_folding": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0006269715420404748 9.809800110352445 0.7315496668090221 1.7837718578852468\n",
      "SR:  0.0\n"
     ]
    }
   ],
   "source": [
    "#Summary (Best, Worst, Mean, SD and SR) of 30 runs. Run this cell to get the result of CGD-3\n",
    "print(min(minima_arr), max(minima_arr),statistics.mean(minima_arr) ,statistics.stdev(minima_arr))\n",
    "j=0\n",
    "for i in range(len(minima_arr)):\n",
    "    if abs(minima_arr[i] - optimum )< 0.000001 :\n",
    "        j+=1\n",
    "print(\"SR: \",j/30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MABSearch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "code_folding": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Finished in 2.0 second(s)\n"
     ]
    }
   ],
   "source": [
    "minima_arr = []\n",
    "start = time.perf_counter()\n",
    "for run in range(30): \n",
    "    epsilon = 1 #initial values for exponential decay. These values are standard/typically used in RL and MAB.\n",
    "    max_epsilon = 1\n",
    "    min_epsilon = 0.001\n",
    "    epsilon_decay = 0.01\n",
    "    v, act = [9999,9999,9999],  [0.1, 0.01, 0.001]  #Value and Action array.\n",
    "    w = np.random.uniform(mrnge[0],mrnge[1], size=(dim))\n",
    "    for run in range (dim*1000):\n",
    "        if (random.uniform(0,1) < epsilon) :  #EXPLORATION\n",
    "            l = np.random.choice([0,1,2])\n",
    "            for d in range (dim):\n",
    "                w[d] = w[d] - act[l] * derivative(w,d)   \n",
    "                w[d] = is_in_fsble_rgn(w[d])\n",
    "            v[l] = v[l] +   (f(w) - v[l])*0.9\n",
    "        else:                                 #EXPLOITATION\n",
    "            l = np.argmin(v)\n",
    "            for d in range (dim):\n",
    "                w[d] = w[d] - act[l] * derivative(w,d)\n",
    "                w[d] = is_in_fsble_rgn(w[d])\n",
    "            v[l] = v[l] +   (f(w) - v[l]) *0.9\n",
    "        epsilon = min_epsilon + (max_epsilon - min_epsilon) * np.exp(-epsilon_decay*run)\n",
    "    minima_arr.append(f(w))\n",
    "finish = time.perf_counter()\n",
    "print(f'Finished in {round(finish-start, 2)} second(s)')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "code_folding": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.2334495610703587e-09 1.791533613181684e-08 6.255273233986238e-09 4.366380469567271e-09\n",
      "SR:  1.0\n"
     ]
    }
   ],
   "source": [
    "#Summary (Best, Worst, Mean, SD and SR) of 30 runs. Run this cell to get the result of MABSearch\n",
    "print(min(minima_arr), max(minima_arr),statistics.mean(minima_arr) ,statistics.stdev(minima_arr))\n",
    "j=0\n",
    "for i in range(len(minima_arr)):\n",
    "    if abs(minima_arr[i] - optimum )< 0.000001 :\n",
    "        j+=1\n",
    "print(\"SR: \",j/30)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}