{ "cells": [ { "cell_type": "markdown", "id": "d0c9c1d0-ee11-48e5-9415-90d10b24d1fb", "metadata": {}, "source": [ "# Simulations" ] }, { "cell_type": "markdown", "id": "92423af7-7d23-47e7-96d0-abb6909fed85", "metadata": {}, "source": [ "A significant part of the [Stochastic Matching package](https://balouf.github.io/stochastic_matching/index.html) is devoted to simulations, allowing to check the practical value of theoretical results and to explore new conjectures." ] }, { "cell_type": "markdown", "id": "1674e3bd-6197-4fd9-b2fa-94760b617c55", "metadata": {}, "source": [ "First, some settings that should apply to all our simulations.\n", "\n", ":::note\n", "The *refresh* parameter below tells if the simulation should run if a simulation file already exists.\n", ":::" ] }, { "cell_type": "code", "execution_count": 1, "id": "386c92be-468f-45c8-aa13-d5208c237ae1", "metadata": { "execution": { "iopub.execute_input": "2025-09-28T07:11:22.287900Z", "iopub.status.busy": "2025-09-28T07:11:22.286889Z", "iopub.status.idle": "2025-09-28T07:11:22.290595Z", "shell.execute_reply": "2025-09-28T07:11:22.290595Z", "shell.execute_reply.started": "2025-09-28T07:11:22.287900Z" } }, "outputs": [], "source": [ "refresh = False\n", "n_steps = 10**10\n", "common = {\n", " \"n_steps\": n_steps,\n", " \"max_queue\": 50000,\n", " \"seed\": 42,\n", "}" ] }, { "cell_type": "markdown", "id": "97a7eb06-c8f9-4204-80bb-3acde7ca1400", "metadata": {}, "source": [ "## Approaching vertices" ] }, { "cell_type": "markdown", "id": "dd1f04b2-5f54-4348-9a14-a9adadde4b01", "metadata": {}, "source": [ "### Preparation" ] }, { "cell_type": "markdown", "id": "22c414d8-68b1-4f05-9120-57f00bb98b01", "metadata": {}, "source": [ "First, we define the set of simulations we want to run. Let's make a small mixer of common and specific parameters." ] }, { "cell_type": "code", "execution_count": 2, "id": "9679b7e7-c4d6-4819-8c58-5760df7567bc", "metadata": { "execution": { "iopub.execute_input": "2025-09-28T07:11:22.291616Z", "iopub.status.busy": "2025-09-28T07:11:22.291616Z", "iopub.status.idle": "2025-09-28T07:11:23.541220Z", "shell.execute_reply": "2025-09-28T07:11:23.541220Z", "shell.execute_reply.started": "2025-09-28T07:11:22.291616Z" } }, "outputs": [], "source": [ "import numpy as np\n", "from stochastic_matching import XP, Iterator, evaluate\n", "from multiprocess import Pool\n", "from numba import njit\n", "\n", "def xp_builder(common, specific):\n", " return sum([XP(name=k, **common, **v) for k, v in specific.items()])" ] }, { "cell_type": "markdown", "id": "6581d4b3-e688-41b4-bf17-bea7395ee12e", "metadata": {}, "source": [ "Prepare specific parameters for each policy." ] }, { "cell_type": "code", "execution_count": 3, "id": "8291582f-7714-43a4-9c84-2bead720a31d", "metadata": { "execution": { "iopub.execute_input": "2025-09-28T07:11:23.541220Z", "iopub.status.busy": "2025-09-28T07:11:23.541220Z", "iopub.status.idle": "2025-09-28T07:11:23.545743Z", "shell.execute_reply": "2025-09-28T07:11:23.545743Z", "shell.execute_reply.started": "2025-09-28T07:11:23.541220Z" } }, "outputs": [], "source": [ "k_range = Iterator(\"k\", [2**i for i in range(14)])\n", "e_range = Iterator(\"epsilon\", np.logspace(-3, 0, 10), name=\"ϵ\")\n", "b_range = Iterator(\"beta\", np.logspace(-3, 1, 10), name=\"β\")\n", "def exp_fad(x):\n", " return njit(lambda t: (t+1)**x)\n", "v_range = Iterator(\"fading\", [exp_fad(x) for x in np.linspace(0., 1., 10)], name=\"V\")\n", "\n", "specific = {\n", " 'k-filtering': {'simulator': \"longest\", 'forbidden_edges': True, \n", " 'iterator': k_range},\n", " 'EGPD': {'simulator': \"virtual_queue\", \n", " 'iterator': b_range},\n", " \"ϵ-filtering\": {'simulator': \"e_filtering\", \n", " 'iterator': e_range},\n", " \"EGPD+\": {'simulator': \"virtual_queue\", 'alt_rewards': 'gentle', \n", " 'iterator': b_range},\n", " \"CRPD\": {'simulator': 'constant_regret', \n", " 'iterator': v_range},\n", " \"Taboo\": {'simulator': 'longest', 'forbidden_edges': True}\n", " }" ] }, { "cell_type": "markdown", "id": "ebe7917e-4310-46e7-83a1-f85671ff9d50", "metadata": {}, "source": [ "Finally, a display function with a few options." ] }, { "cell_type": "code", "execution_count": 4, "id": "701aad9d-48a4-48c8-8e60-07ae125e7218", "metadata": { "execution": { "iopub.execute_input": "2025-09-28T07:11:23.545743Z", "iopub.status.busy": "2025-09-28T07:11:23.545743Z", "iopub.status.idle": "2025-09-28T07:11:23.551896Z", "shell.execute_reply": "2025-09-28T07:11:23.551896Z", "shell.execute_reply.started": "2025-09-28T07:11:23.545743Z" } }, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "\n", "name_relabelling = {'Taboo': '$\\\\Phi_{E^*}$'}\n", "def display_res(res, view=\"loglog\", x_max=None, y_min=10**-8, y_max=None):\n", " if view == \"loglog\":\n", " plot = plt.loglog\n", " elif view == \"logx\":\n", " plot = plt.semilogx\n", " else:\n", " raise ValueError(f\"{view} is not a recognized display view.\")\n", " names = [k for k in res] \n", " colors = {k: v for k, v in zip(names, \n", " plt.rcParams['axes.prop_cycle'].by_key()['color'])}\n", " for k in sorted(names, key=lambda k: -np.average(res[k]['regret'])):\n", " v = res[k]\n", " name = name_relabelling.get(k, k)\n", " delay, regret = np.array(v[\"delay\"]), np.array(v[\"regret\"])\n", " if isinstance(v[\"delay\"], list):\n", " mask = delay > 0\n", " plot(np.abs(delay[mask]), np.abs(regret[mask]), marker=\"o\", \n", " label=name, color=colors[k])\n", " else:\n", " if y_max is None:\n", " plot([delay], [regret], marker=\"o\", label=name, color=colors[k])\n", " else:\n", " plot([delay, delay], [y_min, y_max], '--', label=name, color=colors[k])\n", " \n", " plt.ylabel(\"Regret\")\n", " plt.xlabel(\"Delay\")\n", " if view == \"logx\":\n", " plt.ylim([0, None])\n", " plt.xlim([None, x_max])\n", " if y_max:\n", " plt.ylim([y_min, y_max])\n", " plt.legend()\n", " plt.show()" ] }, { "cell_type": "markdown", "id": "70b21ad4-ae75-4687-ab0f-791f7b362340", "metadata": {}, "source": [ "### Diamond" ] }, { "cell_type": "markdown", "id": "0f2a948e-8636-4130-9e8d-00aec9b0af8f", "metadata": {}, "source": [ "#### Injective-only vertex" ] }, { "cell_type": "markdown", "id": "d9042c3e-6552-4a7c-9681-fca6a6db3523", "metadata": {}, "source": [ "Let's reach an injective-only vertex." ] }, { "cell_type": "code", "execution_count": 5, "id": "3b8e3bc0-2960-4945-8a72-3a59976d35b0", "metadata": { "execution": { "iopub.execute_input": "2025-09-28T07:11:23.553399Z", "iopub.status.busy": "2025-09-28T07:11:23.551896Z", "iopub.status.idle": "2025-09-28T07:11:23.562950Z", "shell.execute_reply": "2025-09-28T07:11:23.562446Z", "shell.execute_reply.started": "2025-09-28T07:11:23.551896Z" } }, "outputs": [ { "data": { "text/html": [ "\n", "