finding-maxima-minimum-regret.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "99c9b53b",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "c3168bdd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.8476627200369931\n"
     ]
    }
   ],
   "source": [
    "eps = 1e-5\n",
    "n = 10000\n",
    "x = np.random.beta(10, 10, size = n)\n",
    "x_star = np.max(x)\n",
    "print(x_star)\n",
    "\n",
    "def offer(i, p):\n",
    "    global regret, count\n",
    "    is_accepted = x[i] > p\n",
    "    regret += x_star - is_accepted * x[i]\n",
    "    count += 1\n",
    "    return is_accepted"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1f01497",
   "metadata": {},
   "source": [
    "### our alg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "07236a9a",
   "metadata": {},
   "outputs": [],
   "source": [
    "regret = 0\n",
    "count = 0\n",
    "\n",
    "I = np.arange(n).tolist()\n",
    "beta = n * [1]\n",
    "a = n * [0]\n",
    "b = n * [1]\n",
    "s = 0\n",
    "t = n-1\n",
    "\n",
    "while beta[s] > eps:\n",
    "    if offer(I[s], a[t]):\n",
    "        p_start, p_end = a[t], b[t]\n",
    "        while offer(I[s], p_end):\n",
    "            p_start, p_end = b[t], b[t-1]\n",
    "            t = t - 1\n",
    "            I.pop()\n",
    "            beta.pop()\n",
    "            a.pop()\n",
    "            b.pop()\n",
    "\n",
    "        beta.append(np.minimum(0.5, beta[s]) * (p_end - p_start))\n",
    "        p = p_start + beta[t + 1]\n",
    "        while offer(I[s], p):\n",
    "            p = p + beta[t + 1]\n",
    "            if p >= p_end:\n",
    "                break\n",
    "                \n",
    "        I.append(I[s])\n",
    "        a.append(p - beta[t + 1])\n",
    "        b.append(p)\n",
    "        s = s + 1\n",
    "        t = t + 1\n",
    "    else:\n",
    "        s = s + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "1a8bcc53",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10004\n",
      "0.8476627200369931\n",
      "0.8476627200369931\n",
      "0.8476626873016357 0.8476627469062805\n",
      "regret =  8492.284012722776\n",
      "count =  10177\n"
     ]
    }
   ],
   "source": [
    "print(s)\n",
    "print(x_star)\n",
    "print(x[I[s]])\n",
    "print(a[s], b[s])\n",
    "print(\"regret = \", regret)\n",
    "print(\"count = \", count)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d95be245",
   "metadata": {},
   "source": [
    "### independent incremental search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "79f73598",
   "metadata": {},
   "outputs": [],
   "source": [
    "regret = 0\n",
    "count = 0\n",
    "\n",
    "a = np.zeros(n)\n",
    "b = np.ones(n)\n",
    "beta = 0.5 * np.ones(n)\n",
    "\n",
    "while True:\n",
    "    ucb_idx = np.argmax(b)\n",
    "    if b[ucb_idx] - a[ucb_idx] < eps:\n",
    "        break\n",
    "        \n",
    "    p = a[ucb_idx] + beta[ucb_idx]\n",
    "    while offer(ucb_idx, p):\n",
    "        p = p + beta[ucb_idx]\n",
    "    a[ucb_idx] = p - beta[ucb_idx]\n",
    "    b[ucb_idx] = p\n",
    "    beta[ucb_idx] = beta[ucb_idx] ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "b7e8c5ff",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6493\n",
      "0.8476627200369931\n",
      "0.8476627200369931\n",
      "regret =  14151.638208463604\n",
      "count =  48101\n"
     ]
    }
   ],
   "source": [
    "ucb_idx = np.argmax(b)\n",
    "\n",
    "print(ucb_idx)\n",
    "print(x_star)\n",
    "print(x[ucb_idx])\n",
    "print(\"regret = \", regret)\n",
    "print(\"count = \", count)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "657eb4b8",
   "metadata": {},
   "source": [
    "### minimum number of queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "8c39c0d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "regret = 0\n",
    "count = 0\n",
    "\n",
    "I = np.arange(n).tolist()\n",
    "a = n * [0]\n",
    "b = n * [1]\n",
    "s = 0\n",
    "t = n-1\n",
    "\n",
    "while True:\n",
    "    if b[s] - a[s] < eps or s == t:\n",
    "        break\n",
    "    a_max = np.max(a[s:(t+1)])\n",
    "    b_min = np.min(b[t])\n",
    "    p = (a_max + b_min)/2\n",
    "    p_prev = a[s]\n",
    "    while offer(I[s], p):\n",
    "        t = t - 1\n",
    "        I.pop()\n",
    "        a.pop()\n",
    "        b.pop()\n",
    "        p_prev = p\n",
    "        p = np.min(b[t])\n",
    "\n",
    "    I.append(I[s])\n",
    "    a.append(p_prev)\n",
    "    b.append(p)\n",
    "    s = s + 1\n",
    "    t = t + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "5e41b17b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10005\n",
      "0.8476627200369931\n",
      "0.8476627200369931\n",
      "0.84765625 0.859375\n",
      "regret =  8663.687415480332\n",
      "count =  20004\n"
     ]
    }
   ],
   "source": [
    "print(s)\n",
    "print(x_star)\n",
    "print(x[I[s]])\n",
    "print(a[s], b[s])\n",
    "print(\"regret = \", regret)\n",
    "print(\"count = \", count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5c78644b",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}