{
  "cells": [
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "ee20da60",
      "metadata": {},
      "outputs": [],
      "source": [
        "- title: Занятие 6\n",
        "- author: Ivan Stepanov\n",
        "- date: 2026-11-12\n",
        "- lecture_pdf: extra/lectures/sem3/sem3_lecture06.pdf\n",
        "- slug: s3_lab06_2026\n",
        "- ipynb_url: download/s3_lab06_2026.ipynb"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "5f29f437",
      "metadata": {
        "id": "5f29f437"
      },
      "source": [
        "# Лабораторная 6. Введение в обучение с подкреплением: MDP"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "982dfd5b",
      "metadata": {
        "id": "982dfd5b"
      },
      "source": [
        "## 0. Подготовка окружения\n",
        "\n",
        "Убедимся, что нужные библиотеки установлены."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "b0322849",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "b0322849",
        "outputId": "6bc9f41f-ead6-45ab-9737-9e0bcc0cb62e"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "numpy: 2.4.6\n",
            "gymnasium: 1.4.0\n"
          ]
        }
      ],
      "source": [
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "\n",
        "try:\n",
        "    import gymnasium as gym\n",
        "except ImportError:\n",
        "    %pip install gymnasium\n",
        "    import gymnasium as gym\n",
        "\n",
        "print('numpy:', np.__version__)\n",
        "print('gymnasium:', gym.__version__)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "25606299",
      "metadata": {
        "editable": true,
        "id": "25606299"
      },
      "source": [
        "## 1. Цикл «агент — среда»\n",
        "\n",
        "В RL агент и среда обмениваются сообщениями: агент видит состояние $s$, выбирает действие $a$, а среда возвращает награду $r$ и следующее состояние $s'$. В библиотеке Gymnasium этот цикл уже реализован.\n",
        "\n",
        "**Шаг (step)** — один такт взаимодействия: агент наблюдает состояние, выбирает действие, получает награду и новое состояние.\n",
        "\n",
        "**Эпизод (episode)** — последовательность шагов от начального состояния до завершения. В CartPole эпизод заканчивается, когда шест падает (terminated) или достигнут лимит шагов (truncated).\n",
        "\n",
        "Посмотрим на среду CartPole: тележка на рельсе, на ней шарнирно закреплён шест. Наблюдение — вектор из четырёх чисел:\n",
        "\n",
        "- $x$ — положение тележки;\n",
        "- $\\dot{x}$ — скорость тележки;\n",
        "- $\\theta$ — угол шеста;\n",
        "- $\\dot{\\theta}$ — угловая скорость шеста.\n",
        "\n",
        "Действий два: $0$ — толкать влево, $1$ — толкать вправо. Награда $+1$ за каждый шаг, пока шест не упал."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "37990000",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 367
        },
        "id": "37990000",
        "outputId": "e87091ad-2f3f-44cb-afe6-e2245d39d974"
      },
      "outputs": [
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeEAAAFeCAYAAACy1qeuAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjAsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvlHJYcgAAAAlwSFlzAAAPYQAAD2EBqD+naQAAEQxJREFUeJzt3W+MXWWdwPHfvTOd6VBaCl0KFsbptA20omAsKWo3FsENUbA2u6iQrMKLQo3omoCy0TcETTD4okiMqZRIbUiMoS+qNG1ww8ILW1l0NysrSAFLZYElxbp26N/5d5590XTWSqedTkt/90w/n6QJ3HvOvQ9NTr48z/lzG6WUEgDAKdfMHgAAnK5EGACSiDAAJBFhAEgiwgCQRIQBIIkIA0ASEQaAJCIMAElEGHibK6+8Mq688srsYcCEJ8JwEmzbti1WrFgRc+bMicmTJ8e0adNi8eLFcf/998f+/ftP2vfcc8898dOf/vRtr//oRz+KRqMx8mfy5Mlx0UUXxZe+9KXYsWPHSft+4ORqzx4A1N3GjRvj05/+dHR2dsbnP//5eO973xsDAwOxefPm+NrXvhbPPfdcrF69+qR81z333BPXX399LFu27Ijvf/Ob34ze3t44cOBAbN68OVatWhWbNm2KZ599Ns4444yTMgbg5BFhOAHbt2+PG264IXp6euKJJ56Id73rXSPv3XbbbfH73/8+Nm7ceELfUUqJAwcORFdX1zG3/fjHPx6XX355REQsX748ZsyYEStXroyf/exnceONN57QOICTz3I0nIDvfOc7sWfPnvjhD394WIAPmTdvXnzlK1+JiIg1a9bEVVddFTNnzozOzs54z3veE6tWrXrbPrNnz47rrrsufv7zn8fll18eXV1d8cADD0Sj0Yi9e/fG2rVrR5adb7755qOO76qrroqIg/+zEBExNDQU3/rWt2Lu3LnR2dkZs2fPjm984xvR399/zP/W/v7+uOuuu2LevHnR2dkZ3d3dceedd45pX+DIzIThBGzYsCHmzJkTH/7wh4+57apVq+KSSy6JpUuXRnt7e2zYsCG++MUvRlVVcdtttx227QsvvBA33nhjrFixIm655Za4+OKL4+GHH47ly5fHokWL4tZbb42IiLlz5x71O7dt2xYRETNmzIiIg7PjtWvXxvXXXx933HFHPP300/Htb387nn/++Vi/fv2on1NVVSxdujQ2b94ct956ayxYsCB++9vfxn333RcvvvjiEc9TA2NQgHHp6+srEVE+9alPjWn7ffv2ve21a665psyZM+ew13p6ekpElMcee+xt20+ZMqXcdNNNb3t9zZo1JSLK448/Xv74xz+WV199tfzkJz8pM2bMKF1dXeW1114rv/nNb0pElOXLlx+271e/+tUSEeWJJ54YeW3JkiVlyZIlI//+8MMPl2azWX7xi18ctu8PfvCDEhFly5YtY/krAP6K5WgYp7feeisiIqZOnTqm7f/ynG5fX1/s3LkzlixZEi+//HL09fUdtm1vb29cc801xz2mj33sY3HuuedGd3d33HDDDXHmmWfG+vXr44ILLohNmzZFRMTtt99+2D533HFHRMRRz12vW7cuFixYEPPnz4+dO3eO/Dm03P3kk08e91gBy9EwbtOmTYuIiN27d49p+y1btsRdd90VTz31VOzbt++w9/r6+uKss84a+ffe3t5xjen73/9+XHTRRdHe3h7nnXdeXHzxxdFsHvx/7VdeeSWazWbMmzfvsH3OP//8mD59erzyyiujfu5LL70Uzz//fJx77rlHfP/NN98c13jhdCfCME7Tpk2LWbNmxbPPPnvMbbdt2xZXX311zJ8/P1auXBnd3d3R0dERmzZtivvuuy+qqjps+7FcCX0kixYtGrk6ejSNRuO4P7eqqnjf+94XK1euPOL73d3dx/2ZgAjDCbnuuuti9erV8dRTT8WHPvShUbfbsGFD9Pf3x6OPPhrvfve7R14/3mXc8QT0kJ6enqiqKl566aVYsGDByOs7duyIXbt2RU9Pz6j7zp07N5555pm4+uqrT2gMwOGcE4YTcOedd8aUKVNi+fLlR3wy1bZt2+L++++Ptra2iDh4z+8hfX19sWbNmuP6vilTpsSuXbvGNdZPfOITERHx3e9+97DXD81ur7322lH3/cxnPhOvv/56PPjgg297b//+/bF3795xjQlOd2bCcALmzp0bP/7xj+Ozn/1sLFiw4LAnZv3yl7+MdevWxc033xy33357dHR0xCc/+clYsWJF7NmzJx588MGYOXNmvPHGG2P+voULF8bjjz8eK1eujFmzZkVvb29cccUVY9r3sssui5tuuilWr14du3btiiVLlsSvfvWrWLt2bSxbtiw++tGPjrrv5z73uXjkkUfiC1/4Qjz55JOxePHiGB4ejq1bt8Yjjzwyck8zcJyyL8+GieDFF18st9xyS5k9e3bp6OgoU6dOLYsXLy7f+973yoEDB0oppTz66KPl0ksvLZMnTy6zZ88u9957b3nooYdKRJTt27ePfFZPT0+59tprj/g9W7duLR/5yEdKV1dXiYiR25UO3aL061//+qjjHBwcLHfffXfp7e0tkyZNKt3d3eXrX//6yBgP+etblEopZWBgoNx7773lkksuKZ2dneXss88uCxcuLHfffXfp6+s7vr8woJRSSqOUv1gfAwBOGeeEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkESEASCJCANAEhEGgCTt2QMATlzfa7+LXX94ZtT3G81mdH/w+mg0207hqIBjEWGouVJK7H3zD/Hmc0+Ouk2j2RYXXvH30QgRhlZiORrqrlRRqqHsUQDjIMJQc6WUKNVw9jCAcRBhqLtSRTVsJgx1JMJQc2bCUF8iDHUnwlBbIgw1V1yYBbUlwlB3pUQZNhOGOhJhqLlSqqjMhKGWRBjqzkwYakuEoeZKuDAL6kqEoebK0GAMHdh91G3au6ZFROPUDAgYMxGGmhvc/1bsfXP7Ubc5e/b7o9FwuEOrcVTCaaDRNil7CMARiDCcBprtIgytSIThNNBsm+SUMLQgEYbTgJkwtCYRhtOAc8LQmkQYTgPNtvawHg2tR4ThNGAmDK1JhOE00BRhaEkiDKcBEYbWJMJwGmi2t2cPATgCEYYaK6WMabtmW8c7PBJgPEQYaq4ayy8oNRrRaLg6GlqNCEPNleGh7CEA4yTCUHPV8GD2EIBxEmGouSLCUFsiDDVXDYkw1JUIQ60Vy9FQYyIMNWc5GupLhKHmLEdDfYkw1FlxdTTUmQhDzblPGOpLhKHmzIShvkQYaq3E/v99/ahbTDrjrGi2e3Y0tCIRhhorpYrd//PCUbfpmnFhtE8+8xSNCDgeIgwTXLPZHuHHG6AliTBMcI1mWzQaDnVoRY5MmOAabWbC0KpEGCa4gzNhEYZWJMIwwTWa7RGWo6ElOTJhgmu2tUUjzIShFYkwTHCNZptzwtCiRBgmuEaz3dXR0KIcmTDBNdrMhKFViTBMcGbC0LocmVBn5dibOCcMrUuEocZKVR1zG7NgaF2OTqixqhrbzxh6WAe0JhGGGit+SxhqTYShxqohEYY6E2GosWp4MEoZw9VZQEsSYaixYiYMtSbCUGPV8FD2EIATIMJQY9XwQPYQgBMgwlBjLsyCehNhqLFiORpqTYShxqrhwRjTsyuBliTCUGOVh3VArYkw1NiuPzwTcZT7hDvOPCfOmHHhKRwRcDxEGGpscH/fUd9vTuqM9slnnqLRAMdLhGECazSaB3/KEGhJIgwTWaPppwyhhTk6YQJrNJrRaGvPHgYwChGGCazRbESj6TCHVuXohInMOWFoaSIME5gLs6C1iTBMYCIMrU2EYSJrijC0MhGGCazRaEajIcLQqkQYaqoc5XGVIyxHQ0sTYairUo763OiIiEbDLUrQyhydUFOlGjpmhIHWJsJQU1U1PLYlaaBliTDUVBkeiggRhjoTYaipUg1HKVX2MIATIMJQU6Uadk4Yak6EoabK8JBzwlBzIgw1VVVDEZajodZEGGrKcjTUnwhDTVmOhvoTYaipgzNhy9FQZyIMNVWq4SjuE4ZaE2Goqbde3xqD+/pGfb/RNinOnvOBUzgi4Hg1ipNKkKKUEhs3boyhoaFx7T9t9/Mxdd/2Ud+vohl/mvb+GOg6f1yfv2jRopg1a9a49gXGRoQhSVVVMX369Ni9e/e49v+nf7gi/vHvLh31/f39g/HPDzwe//a718b1+evXr49ly5aNa19gbNqzBwCcmFIiSjSjRCNG/qlx8GzxwOBw9vCAoxBhqLFSInYMzI6X918Wu4fOiY7mgbig88Xo6XouogxG/+D4lrqBU0OEocZe658fz+752zh0jeWBalJs278w9gyfHXPa/zUGh9zCBK1MhKGmXj0wP7bu/WAc6SaHHQNzYvf+KgaGHjn1AwPGzC1KUFN7h6fHUOkY9f0/D57nnDC0OBGGCapEif4hEYZWJsIwUZWIQTNhaGkiDDU194z/jLPb34g4wqMr22IgFk57LAbMhKGliTDU1KRGfyw6a2P8zaTXYlJjfxy8R3gwprbtjA9M+5eY3r4jBkUYWpqro6GmNv/Xf8ef+vbFYPn32DlwYfRXU6KtMRjTJ+2I/2j7c/QPDsdw5YF40MrG/NjKxYsXv9NjgdPO008/HcPDrTlbnT9/fpxzzjnZw4Da2rJlyzG3GXOEBwYGTnhAwP+rqipmzpw57mdHv9PWrVsXS5cuzR4G1FZHx+i3EB4y5uXosXwYMHZV1dpPs2pvb3fcwzvMhVkAkESEASCJCANAEhEGgCQiDABJRBgAkogwACQRYQBIIsIAkMQPOECiL3/5y9Hf3589jCOaN29e9hBgwhvzs6MBgJPLcjQAJBFhAEgiwgCQRIQBIIkIA0ASEQaAJCIMAElEGACSiDAAJBFhAEgiwgCQRIQBIIkIA0ASEQaAJCIMAElEGACSiDAAJBFhAEgiwgCQRIQBIIkIA0ASEQaAJCIMAElEGACSiDAAJBFhAEgiwgCQRIQBIIkIA0ASEQaAJCIMAElEGACSiDAAJBFhAEgiwgCQRIQBIIkIA0ASEQaAJCIMAElEGACSiDAAJBFhAEgiwgCQRIQBIIkIA0ASEQaAJCIMAElEGACSiDAAJBFhAEgiwgCQRIQBIIkIA0ASEQaAJCIMAElEGACSiDAAJBFhAEgiwgCQRIQBIIkIA0ASEQaAJCIMAElEGACSiDAAJBFhAEgiwgCQRIQBIIkIA0ASEQaAJCIMAElEGACSiDAAJBFhAEjyf0+i1LlJftkxAAAAAElFTkSuQmCC",
            "text/plain": [
              "<Figure size 600x400 with 1 Axes>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "env = gym.make('CartPole-v1', render_mode='rgb_array')\n",
        "obs, info = env.reset(seed=42)\n",
        "frame = env.render()\n",
        "env.close()\n",
        "\n",
        "plt.figure(figsize=(6, 4))\n",
        "plt.imshow(frame)\n",
        "plt.axis('off')\n",
        "plt.title('CartPole')\n",
        "plt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "CjJC8uVcTYfm",
      "metadata": {
        "id": "CjJC8uVcTYfm"
      },
      "source": [
        "Реализуем простейшую стратегию (политику): на каждом шаге будем выбирать случайное действие."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "759ac117",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 736
        },
        "id": "759ac117",
        "outputId": "7be34d3e-f4f5-4a8b-e4c3-89b3fae8dd42"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "a=0, r=1.0, obs=[ 0.013 -0.217 -0.047  0.23 ]\n",
            "a=0, r=1.0, obs=[ 0.009 -0.412 -0.042  0.507]\n",
            "a=1, r=1.0, obs=[ 0.001 -0.216 -0.032  0.201]\n",
            "a=0, r=1.0, obs=[-0.004 -0.411 -0.028  0.484]\n",
            "a=1, r=1.0, obs=[-0.012 -0.215 -0.018  0.182]\n",
            "a=0, r=1.0, obs=[-0.016 -0.41  -0.015  0.469]\n",
            "a=0, r=1.0, obs=[-0.024 -0.605 -0.005  0.757]\n",
            "a=1, r=1.0, obs=[-0.037 -0.41   0.01   0.463]\n",
            "a=1, r=1.0, obs=[-0.045 -0.215  0.019  0.173]\n",
            "a=1, r=1.0, obs=[-0.049 -0.02   0.022 -0.114]\n",
            "a=1, r=1.0, obs=[-0.049  0.175  0.02  -0.399]\n",
            "a=0, r=1.0, obs=[-0.046 -0.021  0.012 -0.1  ]\n",
            "a=1, r=1.0, obs=[-0.046  0.174  0.01  -0.389]\n",
            "a=1, r=1.0, obs=[-0.043  0.369  0.002 -0.678]\n",
            "a=1, r=1.0, obs=[-0.035  0.564 -0.011 -0.97 ]\n",
            "a=1, r=1.0, obs=[-0.024  0.76  -0.031 -1.266]\n",
            "a=0, r=1.0, obs=[-0.009  0.565 -0.056 -0.983]\n",
            "a=1, r=1.0, obs=[ 0.002  0.761 -0.076 -1.293]\n",
            "a=1, r=1.0, obs=[ 0.018  0.957 -0.101 -1.608]\n",
            "a=1, r=1.0, obs=[ 0.037  1.153 -0.134 -1.931]\n",
            "a=0, r=1.0, obs=[ 0.06   0.959 -0.172 -1.683]\n",
            "a=1, r=1.0, obs=[ 0.079  1.156 -0.206 -2.023]\n",
            "a=1, r=1.0, obs=[ 0.102  1.353 -0.246 -2.372]\n"
          ]
        },
        {
          "name": "stderr",
          "output_type": "stream",
          "text": [
            "/usr/local/lib/python3.13/dist-packages/matplotlib/animation.py:908: UserWarning: Animation was deleted without rendering anything. This is most likely not intended. To prevent deletion, assign the Animation to a variable, e.g. `anim`, that exists until you output the Animation using `plt.show()` or `anim.save()`.\n",
            "  warnings.warn(\n"
          ]
        },
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD7CAYAAABKfn7LAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjAsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvlHJYcgAAAAlwSFlzAAAPYQAAD2EBqD+naQAAB9lJREFUeJzt3V+LXHcZwPHnnJnZZJNsJcWwqYVqCWq9UIoI8a6C+A5642vIpXe+kL6EXPVOCgFfgBiKFFqQWtqiRY3BYpLN35k55+dF9KJ212zTnZl9nvl8LmcOO89F8uXHb+Z3TtdaawFAGv2mBwDgqxFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIRrgBkhFugGSEGyAZ4QZIZrrpAeAk/O0P78TDf/7lS69f2L8S+z/6RXRdt4GpYDWEmxLu3/o47n72wZdeb63F/g9/HtFNNjAVrIatEkpr4xBtHDc9Bpwo4aa0NiyjtWHTY8CJEm5Ka+PSiptyhJvSxnGINlpxU4twU1obhohmxU0twk0J/ezsoa8Pi0cxLudrngZWS7gp4YWXv3/o60/u3o75w7trngZWS7gpoZ/ubHoEWBvhpoSn4XY6ku0g3JRgxc02EW5KEG62iXBTgnCzTYSbEoSbbSLclND1R9/9r41DtNbWOA2slnBTngM4VCPclDcuhJtahJvyrLipRrip44jzN8JNNcJNHUd8/zgOwk0twk159ripRrgpYbqzG7svfuvQ9w5ufbTmaWC1hJsSusksZrt7h763fHx/zdPAagk3JXRdH91ktukxYC2Emxq6LvrJdNNTwFoINyVYcbNNhJsaui564WZLCDcldF1vq4StIdzU0HXRCTdbQrgpoeu6OOrMe2tjtHG53oFghYSb8to4xjgIN3UIN/W1MZpwU4hwU14bbZVQi3BTXrPiphjhpr5xsMdNKcJNGdOzFyK6L/+yZFjO3WiKUoSbMs5f+s6hpyeHJw/i8d3bG5gIVkO4KaOfzg5dcUM1wk0Z/XQWRz54EgoRbsroJjv/OUEJtQk3ZTxdcUN9wk0Z/XTHHjdbQbgpo5/MorPHzRYQbsro+v7I7ybbOERrbb0DwYoIN1thHOabHgFOjHCzFcbFPCKsuKlBuNkK47DQbcoQbrbCuLTipg7hZis8DTfUINwUc/jPSsblwq9KKEO4KaPrJ3Hh8ncPfe/g7x9GG4c1TwSrIdzU0fUxO3vh0LfGxZOwx00Vwk0ZXUR07lfCFhBuCume3q8EihNu6uhCuNkKwk0hVtxsB+GmlMOeOQnVCDel/N9w+x03RQg3ZXRdd/QjJ1uLcViudR5YFeFmK7Rojr1ThnCzHVqLcbnY9BRwIoSbreFhClQh3GyF1lo0K26KmG56AHiW+Xwejx49Ota1R13X2hgH9+7EsHv32J+7t7cXfW9tw+nTNfe65JS7fv16XLt27VjXXn3tcvz6lz+N3TNf/FngYjnGW795L975/cfH+jvT6TRu3rwZr7766leeF1bNiptTbz6fx507d4517Z/+HHHv4ZM4s7MTB8OLsWw7cbZ/EOcm9+KbF6bH/juTySTGcXz+oWGFhJtSFsshFkMfHz38SXz2+LVYtDNxrj+I752/GS3e3/R4cCJs4FHKfDnGh/d/HJ88ej0WbTci+ng4fiPeP/hZ3J5/e9PjwYkQbkpZLIf4x5OX43+PUA4xi38tLm9mKDhhwk0p88Vgb5ryhJtSFssxXpr9Mfr44n1JzvQP4vKZTzc0FZwsX05SymIY4qXpB7G7uxefPHw9Ho/n4oXp5/GDc7+Lv05ubXo8OBHHDvfbb7+9yjngSO++++6xr20t4ldv3Yjp5Lcxb2djbJOYdouY9fN48Oj4R95ba3Hjxo3Y399/npHhub355pvPvObY4b506dLXGgae197e3le6/vN7/z09ef9rfe7Fixf9u+dUOna433jjjVXOAUf69NP17013XRdXr16NK1eurP2z4Vl8OQmQjHADJCPcAMkIN0Aywg2QjHADJOPkJKfe+fPn45VXXlnrZ04mk5hO/ffgdPIEHE69YRhiGIa1f+5sNouu6559IayZcAMkY48bIBnhBkhGuAGSEW6AZIQbIBnhBkhGuAGSEW6AZIQbIBnhBkhGuAGSEW6AZIQbIBnhBkhGuAGSEW6AZIQbIBnhBkhGuAGSEW6AZIQbIBnhBkhGuAGSEW6AZIQbIBnhBkhGuAGSEW6AZIQbIBnhBkhGuAGSEW6AZIQbIBnhBkhGuAGSEW6AZIQbIBnhBkhGuAGSEW6AZIQbIBnhBkhGuAGSEW6AZIQbIBnhBkhGuAGSEW6AZIQbIBnhBkhGuAGSEW6AZIQbIBnhBkhGuAGSEW6AZIQbIJl/A/sUdQxwhK63AAAAAElFTkSuQmCC",
            "text/plain": [
              "<Figure size 500x300 with 1 Axes>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "env = gym.make('CartPole-v1', render_mode='rgb_array')\n",
        "obs, info = env.reset(seed=0)\n",
        "\n",
        "from matplotlib import animation\n",
        "\n",
        "frames = []\n",
        "done = False\n",
        "while not done:\n",
        "    action = env.action_space.sample()  # случайное действие\n",
        "    obs, reward, terminated, truncated, info = env.step(action)\n",
        "    frames.append(env.render())\n",
        "    print(f'a={action}, r={reward}, obs={np.round(obs, 3)}')\n",
        "    done = terminated or truncated\n",
        "\n",
        "env.close()\n",
        "\n",
        "# Анимация эпизода\n",
        "fig = plt.figure(figsize=(5, 3))\n",
        "img = plt.imshow(frames[0])\n",
        "plt.axis('off')\n",
        "\n",
        "def animate(i):\n",
        "    img.set_data(frames[i])\n",
        "    return [img]\n",
        "\n",
        "ani = animation.FuncAnimation(fig, animate, frames=len(frames), interval=80)\n",
        "plt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "cea23ddf",
      "metadata": {
        "id": "cea23ddf"
      },
      "source": [
        "**Задача 1**\n",
        "Напишите свою эвристическую политику для CartPole, которая балансирует шест лучше случайной.\n",
        "\n",
        "Затем сравните награду (за эпизод) вашей политики и случайной."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "bZbntgYfTlBv",
      "metadata": {
        "id": "bZbntgYfTlBv"
      },
      "outputs": [],
      "source": [
        "# Ваш Код"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "b05f4330",
      "metadata": {
        "id": "b05f4330"
      },
      "source": [
        "## 2. Доход и дисконтирование\n",
        "\n",
        "Доход (return) — это дисконтированная сумма будущих наград:\n",
        "\n",
        "$$G_t = R_{t+1} + \\gamma R_{t+2} + \\gamma^2 R_{t+3} + \\dots$$\n",
        "\n",
        "Коэффициент $\\gamma \\in [0, 1]$ определяет, насколько агент ценит будущее. Реализуем подсчёт дохода двумя способами: «в лоб» и рекурсивно (справа налево)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "f65f2ea7",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "f65f2ea7",
        "outputId": "54f11cc8-d306-43e3-c846-e9cc61703b12"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "gamma=0.0: loop=1.0000, recursive=1.0000\n",
            "gamma=0.5: loop=1.8750, recursive=1.8750\n",
            "gamma=0.9: loop=3.4390, recursive=3.4390\n",
            "gamma=1.0: loop=4.0000, recursive=4.0000\n"
          ]
        }
      ],
      "source": [
        "rewards = [1.0, 1.0, 1.0, 1.0, 0.0]\n",
        "\n",
        "def discounted_return_loop(rewards, gamma):\n",
        "    G = 0.0\n",
        "    for k, r in enumerate(rewards):\n",
        "        G += (gamma ** k) * r\n",
        "    return G\n",
        "\n",
        "def discounted_return_recursive(rewards, gamma):\n",
        "    G = 0.0\n",
        "    for r in reversed(rewards):\n",
        "        G = r + gamma * G\n",
        "    return G\n",
        "\n",
        "for gamma in [0.0, 0.5, 0.9, 1.0]:\n",
        "    a = discounted_return_loop(rewards, gamma)\n",
        "    b = discounted_return_recursive(rewards, gamma)\n",
        "    print(f'gamma={gamma}: loop={a:.4f}, recursive={b:.4f}')"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "629b7c68",
      "metadata": {
        "id": "629b7c68"
      },
      "source": [
        "**Задача 2**\n",
        "\n",
        "- Чему равен доход при γ = 1, если наград бесконечно много и все они равны 1?\n",
        "- Зачем вводят γ < 1, если горизонт эпизода конечен?"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "KThfLKW_XVZG",
      "metadata": {
        "id": "KThfLKW_XVZG"
      },
      "source": [
        "**Ваш ответ:**"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "9562b07a",
      "metadata": {
        "id": "9562b07a"
      },
      "source": [
        "## 3. MDP: полоска из трёх клеток\n",
        "\n",
        "Среда: полоска клеток 0, 1, 2. В клетке 2 — цель (награда +1, эпизод завершается). В каждой клетке два действия: «вправо» и «стоять». Переходы детерминированы, γ = 0.9.\n",
        "\n",
        "Посчитаем функции ценности V и Q для политики «всегда вправо» вручную, как на лекции."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "291fc1be",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "291fc1be",
        "outputId": "076efe5b-94d9-46a8-b539-02e047579f6d"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "V = [0.9 1.  0. ]\n",
            "Q(0, вправо) = 0.900,  Q(0, стоять) = 0.810\n",
            "Q(1, вправо) = 1.000,  Q(1, стоять) = 0.900\n"
          ]
        }
      ],
      "source": [
        "gamma = 0.9\n",
        "\n",
        "# Ценность терминальной клетки равна нулю\n",
        "V = np.zeros(3)\n",
        "V[2] = 0.0\n",
        "V[1] = 1.0 + gamma * V[2]   # из 1 вправо: награда +1 и терминал\n",
        "V[0] = 0.0 + gamma * V[1]   # из 0 вправо: награда 0, попадаем в 1\n",
        "\n",
        "print('V =', V)\n",
        "\n",
        "# Q(s, a) = r(s, a) + gamma * V(s')\n",
        "def q_value(s, action):\n",
        "    if action == 'вправо':\n",
        "        r = 1.0 if s == 1 else 0.0\n",
        "        s_next = s + 1\n",
        "    else:  # 'стоять'\n",
        "        r = 0.0\n",
        "        s_next = s\n",
        "    return r + gamma * V[s_next]\n",
        "\n",
        "for s in [0, 1]:\n",
        "    qr = q_value(s, 'вправо')\n",
        "    qs = q_value(s, 'стоять')\n",
        "    print(f'Q({s}, вправо) = {qr:.3f},  Q({s}, стоять) = {qs:.3f}')"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "b7818e55",
      "metadata": {
        "id": "b7818e55"
      },
      "source": [
        "**Жадная политика** — это правило, по которому в каждом состоянии выбирается действие с наибольшей ценностью: $\\pi_{\\text{greedy}}(s) = \\arg\\max_a Q(s,a)$.\n",
        "\n",
        "Посмотрим на значения $Q$, которые мы получили для политики «всегда вправо»:\n",
        "\n",
        "- в клетке 0: для действия «вправо» $Q = 0{,}9$, для действия «стоять» $Q = 0{,}81$;\n",
        "- в клетке 1: для действия «вправо» $Q = 1$, для действия «стоять» $Q = 0{,}9$.\n",
        "\n",
        "В клетке 0 число $0{,}9$ больше, чем $0{,}81$, поэтому $\\arg\\max_a Q(0,a)$ выбирает действие «вправо». В клетке 1 число $1$ больше, чем $0{,}9$, поэтому $\\arg\\max_a Q(1,a)$ тоже выбирает «вправо».\n",
        "\n",
        "Значит, жадная политика в обеих клетках говорит «вправо», то есть совпадает с исходной политикой «всегда вправо». Если попытаться улучшить её, заменив действия на более выгодные по $Q$, ничего не изменится — она уже выбирает самые ценные действия. В нашей среде это признак оптимальности: именно «вправо» ведёт к цели и приносит награду $+1$."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "6231cf52",
      "metadata": {
        "id": "6231cf52"
      },
      "source": [
        "## 4. Выбор лучшей политики\n",
        "\n",
        "Качество политики измеряем функционалом $$J(π) = V^π(0)$$ — ценностью стартовой клетки (эпизод всегда начинается в клетке 0).\n",
        "\n",
        "Решим уравнение Беллмана для нескольких политик и сравним их."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "50ad149b",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "50ad149b",
        "outputId": "245c1fea-80dc-4efd-9916-575549417c3a"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "pi1: всегда вправо           -> J(pi) = V(0) = 0.9000\n",
            "pi2: всегда стоять           -> J(pi) = V(0) = 0.0000\n",
            "pi3: вправо, потом стоять    -> J(pi) = V(0) = 0.0000\n",
            "pi4: стохастическая 0.8      -> J(pi) = V(0) = 0.8566\n"
          ]
        }
      ],
      "source": [
        "gamma = 0.9\n",
        "\n",
        "def evaluate_strip(p):\n",
        "    \"\"\"p[s] = вероятность действия 'вправо' в клетке s.\n",
        "    Решаем уравнение Беллмана в замкнутой форме.\"\"\"\n",
        "    p0, p1 = p[0], p[1]\n",
        "    V1 = p1 * 1.0 / (1.0 - (1.0 - p1) * gamma)\n",
        "    V0 = p0 * gamma * V1 / (1.0 - (1.0 - p0) * gamma)\n",
        "    return np.array([V0, V1, 0.0])\n",
        "\n",
        "policies = {\n",
        "    'pi1: всегда вправо':        [1.0, 1.0],\n",
        "    'pi2: всегда стоять':        [0.0, 0.0],\n",
        "    'pi3: вправо, потом стоять': [1.0, 0.0],\n",
        "    'pi4: стохастическая 0.8':   [0.8, 0.8],\n",
        "}\n",
        "\n",
        "for name, p in policies.items():\n",
        "    V = evaluate_strip(p)\n",
        "    print(f'{name:28s} -> J(pi) = V(0) = {V[0]:.4f}')"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "-18TqfICb3Se",
      "metadata": {
        "id": "-18TqfICb3Se"
      },
      "source": [
        "## 5. Среда Taxi\n",
        "\n",
        "На поле 5×5 такси должно подобрать пассажира на одном из четырёх пунктов (R, G, Y, B) и довезти его до пункта назначения.\n",
        "\n",
        "- **Состояний**: 500 — это комбинации положения такси (25 клеток), местоположения пассажира (5 вариантов: R/G/Y/B или «уже в такси») и пункта назначения (4 варианта).\n",
        "- **Действий**: 6 — 0 вниз, 1 вверх, 2 вправо, 3 влево, 4 подобрать, 5 высадить.\n",
        "- **Награда**: −1 за каждый шаг, +20 за успешную доставку, −10 за неверные pickup/dropoff.\n",
        "\n",
        "Каждое состояние можно расшифровать функцией `decode`: она возвращает (строка такси (положение в табличке), столбец такси (положение в табличке), местоположение пассажира, пункт назначения). Индексы пассажира и назначения: 0=R, 1=G, 2=Y, 3=B, а 4 у пассажира означает «уже в такси»."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "hkHZJqeWb6Pt",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hkHZJqeWb6Pt",
        "outputId": "cc4ed2fa-df54-408c-977a-6fcf3870e2a4"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Начальное состояние: 314\n",
            "Расшифровка (строка, столбец, пассажир, назначение): (3, 0, 3, 2)\n",
            "\n",
            "+---------+\n",
            "|R: | : :G|\n",
            "| : | : : |\n",
            "| : : : : |\n",
            "|\u001b[43m \u001b[0m| : | : |\n",
            "|\u001b[35mY\u001b[0m| : |\u001b[34;1mB\u001b[0m: |\n",
            "+---------+\n",
            "\n",
            "\n"
          ]
        }
      ],
      "source": [
        "taxi = gym.make('Taxi-v4', render_mode='ansi')\n",
        "obs, info = taxi.reset(seed=0)\n",
        "\n",
        "print('Начальное состояние:', obs)\n",
        "print('Расшифровка (строка, столбец, пассажир, назначение):', taxi.unwrapped.decode(obs))\n",
        "print()\n",
        "print(taxi.render())\n",
        "taxi.close()"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "uOFncKpke3N6",
      "metadata": {
        "id": "uOFncKpke3N6"
      },
      "source": [
        "Текстовый вывод не слишком нагляден, поэтому нарисуем немного другой"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "yZohJpNXe4GF",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 323
        },
        "id": "yZohJpNXe4GF",
        "outputId": "5ea706c9-3780-4f8d-c984-cd33d8b3b624"
      },
      "outputs": [
        {
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAUoAAAEyCAYAAACcWJmpAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjAsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvlHJYcgAAAAlwSFlzAAAPYQAAD2EBqD+naQAAHMNJREFUeJzt3Xl4HOV9B/DvOzN7aqXVYVvyIVsm+OQyOBAMDRDjBDd5nJCa0qbpQwg5IaGkCWkT2uACSYhbF9omxDRPwpWEHg/0gECb0Ic6oQQcsAM22Pi+LVuSZUl7aI+Z9+0fsmSvJOtdHauZ2f1+nkePnp2d2fmNdvereWfeeUcopRSIiOisDLcLICLyOgYlEZEGg5KISINBSUSkwaAkItJgUBIRaTAoiYg0GJRERBoMSiIiDQYllYWWlhbcfPPNbpdBZYpBSRNOCFHUz4YNG9wulagoltsFUPn58Y9/XPD4iSeewAsvvDBk+qJFiyZsnTt27IBh8P8+lYbgoBhUal/84hfx0EMPgR818iv+CyZXPProo1i+fDmmTZuGUCiExYsXY/369QXzvPjiizAMA3fffXfB9CeffBJCiIL5eYySSolNb3LF+vXrcd555+HDH/4wLMvCs88+i9tuuw1SSnzhC18AACxfvhy33XYb7r//flx//fW45JJL0Nraittvvx0rVqzA5z//eZe3gioFm95UcsM1vXt7exGJRArmW7lyJXbt2oU9e/YMTEun07jooosQCoWwadMmrF69Gi+99BK2bt2K2bNnD8zX0tKCa665Bo899ljJt4cqD5ve5IozQ7K7uxsdHR24+uqrsXfvXnR3dw88F41G8dhjj2H79u246qqr8Nxzz+HBBx8sCEmiUmNQkitefvllrFixAlVVVaitrcXUqVNx1113AUBBUALAlVdeiVtvvRW/+c1vcN111+GWW25xo2SqYDxGSZNuz549uPbaa7Fw4UI88MADaG5uRjAYxPPPP48HH3wQUsqC+bPZ7ECfyz179iCdTiMajbpQOVUq7lHSpHv22WeRzWbxzDPP4HOf+xw++MEPYsWKFUOOWfZbs2YNtm/fjnXr1mHfvn342te+NskVU6XjHiVNOtM0AaDg5E53dzceffTRIfNu3LgR69atw5e+9CV85StfQUdHB9auXYvVq1fj6quvnrSaqbJxj5Im3Qc+8AEEg0GsWrUKDz30ENauXYulS5di2rRpBfNlMhl84hOfwLx58/Ctb30LAHDPPfdg8eLF+OQnP4lUKuVG+VSBGJQ06RYsWICnnnoKQgjceeedePjhh/HZz34Wd9xxR8F8d911F3bv3o3HH38c4XAYABAMBvH444/j0KFD+OpXv+pG+VSB2I+SiEiDe5RERBoMSiIiDQYlEZEGg5KISINBSUSkwaAkItJgUBIRaRR9CWM+31vKOoiIJl0gMPz4AoNxj5KISINBSUSkwaAkItJgUBIRaTAoiYg0GJRERBoMSiIiDQYlEZEGg5KISINBSUSkwaAkItJgUBIRaTAoiYg0GJRERBoMSiIiDQYlEZEGg5KISINBSUSkwaAkItIo+p45RFQ+kskUjrd1lOS1w6EQZs5sKslru4VBSVSBXt24Cffe90BJXvv88xbi+w99pySv7RYGJVEFUUqd+l3StQysBwCEEKVc2aQQShX3J+Ptaon87x+++0O8/vqbmGPYuMLMlmQdHcrAC3YEpmXib9bejSlT6kuynolQ7O1quUdJVEHa2jqw/8Ah1MdDmN4cL8k6Muk89h84BMsyYTtOSdYx2bhHSVTmcrkcfvrkvyGbzaJ365tw2o+jMWThgppQSdbXlXfwelcGEAaiy34HRjiMq69ahkWL5pdkfePBPUoiAgDk8zaeevpnSCSSuKW5BkumVpV0fbUBEyumVsFWCvf97Oc4mZeYOXO6J4OyWAxKojKVSCRx4OBh5DJZzAwayEQsVJmT13VaAJgVthC3JBJtbXjr7XcQi1WhZU7zpNUwUdj0JipTr7zyOv78699EyBD4q/kNqLLcu77kn4704JWTGVx26cVY9zdrXKtjMDa9iSqU4zhQSkFKCQOA6YHeOQb6LwNUsG0bAGCapm+6DnGPkqjMfH/9Y9iw4WXMDgC/G5UQAGoDBgwXQylpS2SlwiFb4PmUQDgcxve++23U1FS7VhPAPUqiitXd3YNjx9tRHwuiobbW7XIAADHLQAxAWzaLY8e7EYmEIaV0u6yicY+SqAzYtoMfPfIkEskksjveRv7YUdQFDCyuLk0XoLHqyjt4O5GDME1E3/NeiEAAqz70fixYcK4r9XCPkqiCSCnxixc2oL39BN5fa+DCqr4jgolsaa6+GSsTwIVVBnJS4pGfv4iMBC65+ALXgrJYDEqiMnMir3Aw6+1mra0AWdLrzScWg5KozGxOKWxO+SiFfIBBSVRmDAEYp7pMerb3jQLyProMnEFJVGbed76BxTMFQuEAGurd7X5zNrm8wtp/PYF01h97vgxKojITsoCqsEA4LFATNd0uZ1iZnPTu3u4wGJREFeR/30jhQFt+xHkWNAexbFF02Oe27Mtg867MiMtPrbXwoctiY67RixiURBVk99Ec3tg7cpehcFBg2aLhn2s9YeO1nSMH5dymAIOSiPwvUl2LuunNMAyB2lgYAsC+ne8g2dNT1PJWMIxpLfMAALWxMExDoPXwIXQcay1h1e5hUBJVoCnN5+A919+EgGngkgVNMA0DD3/7Xux8a0tRy0fjdVi2+hYIIbDk3EZEwwE889MnsOG5Z0pcuTsYlEQVSAjANATMMY5PKQBYptE3+o+PTsqMFYOSqALVV0ewdMF0ABjTqEKRkIWl85sAIWAa5Z+UDEqiCiRE3x7heF7A7N+jrAAMSqIKtPed7fjR336nYNqRA/uLXv5kezse+du1Bc3uY4cPT1B13sOgJKpA3Sc70b2pc8zLZzO9eHvz6xNYkbcxKIkqyLyZQQQDIzeXWxqDZ31uRoOFyxaER1x+Wm35xUr5bRERndU1F43vVrUXzA3jgrkjB2U5cu+2bEREPsGgJCLSYFASEWnwGCVRBXluYwK7j448etAFc0NYvmT4Y5mv7ejFr7eNfKPB6fUWbry6Zsw1ehGDkqiCHD1hY+eR3IjzNNadfQzLzoSjXT7v+GMw3tFgUBJVoFjdVDSeswCGEJhaG4UQAm9teg3dnSeKWj4YiaJ50SWAAKbEo7BMA/t3vjOqTut+wqAkqkB105tx8XU3FIwe1N56tOigDMfiWHLd6iGjBzEoiahsGIZAKGAiYBkYy/A/hgDCQQtCePgGZhOIQUlUgeqrw7hkftOYlw+HArh4XlNFhCTA7kFEBECp0Z+AOTMkx7K8n3CPkqgC7dj6Jv7uG18rmNbWerTo5U8cPzZk+a4TxR3f9CMGJVEFSieTSCeTY14+n8vh0N49E1iRtzEoiSrIkneF0Vg38tfeMID/fn34EN11qg9lLGLgysWRYeepq/bmvcTHg0FJVEEuXTB8uJ3pV1vT+Jdfjnw3xpqogVWXxzjCORFVNgGFqCULpuWlQE5W3jlgBiURDStkKlza2FvQy/JAIoC9PSHXanKLa0FZ7t0JiCZTKb9PpW5dK1V8/W419V0LygMHD+PuNX8NMC+Jxk1BobOzy+0yxuT76x/F44//y8gzCeC+e/8cc2bPmpyiBnEtKHO5PPbvP+TW6onII9rbT6Ad+j6YudzIw8OVUuUdlSUiGiUGJRGRhqfOejc1TkVDQ73bZRD5jlQKu3bthW3bbpcyarNmTUe8pm9E9H37DyKdPj2CejAYxLnntkBAIBx272y7p4LyhhtW4cbf/7DbZRD5Ti6Xx8c+/nm0t/vveutPf+rjWP6+3wEAfPH2u7Bl67aB5xobp+L73/sODMPdxq+ngrIfuw4Rjdbp74xSgCMVpOz7PepXOuP7pwAM9xJ96wCEGNt3VZ7Zj72ge5A3v/ueDMpMphetR3hGnKhYtm0PNLs3bJN4eQdgGBkYRnbUr5XJ9YVV1hHYeCxauB7Z14+xrcvGPT9pH3O9SgHpbN962tpasW/Pzr51Z0a+cZlbPBmUSinYtntdAYj8Jp+3+9IHQG8O6IsbhfHsoSkIZJzhO3g7EuhMyGGfGy3Htge+715tTXoyKPspKZF/9RUgO/r/im6LLb0UwRkzYNs2MpleCCEQjcZ8OSL0fzzzC7S2tg08rq2twR/euMrXAyJks1nk8zmYpolIJKpfwMMymV5IKfGBDy3FgZPb9At4jKhvR1VVFYQwYJreHHnI00EJKeHseAcqlXK7klGzFp+PSCSKTCYz0JyIRMIQwn89srZs3Ylt23cNPJ45oxE333Sj6wfYx8NxHOTzORiG4fug7N+OJe9+FyInW90uZ/QCPQiFIzANE4bhzaD07yediGiSMCiJiDQYlEREGgxKIiINBiURkYa3z3pPoNiCRai//Iphn+vZ8ga6frtpkisi8q53v2slqkLxIdOVUvjN7ueQyfuvJ8p4VExQhqZNQ/2l7xn2uXznCQYl0RmaGxaiLtY0ZLqUDjbvewFgUJY3J5tF4p1tgFKIzV8AK1rldklEnnUyeRzd6dOXKioo2E7OxYrcUXFBaSd6sP9H/whIiXlf/TqsOXPdLonIs/Yc34wtB37pdhmuq7igFELAjEYBR0L4+MoSoskkIBCwwgAUcnYWXh3lp1QqLigDdfVYvOabAAAjFHa5GiJ/qK+egd+9+NOQUuI/X/suUtkut0uaVBUXlMIwYPr82l6iyWYIAwEzDGVIXw+GMlYVF5T9lFI4+u9PIdvehmzbcbfLISIPq9igBIDU7l1IH9zvdhlE5HEVF5ROJoPuLW8ASiHaMhehpiZkjh5B72GOqE40WENsJs5tuhjVkQa3S3FVxQWlnUzg4E8eG+geVDVnLo7//HkGJdEw5jZeiLmNFw489ugA5CVXMUEpcznku7tgJxID05xkEvnuLjiZjIuVEXlPJp9COtszZLpUEkpNzC0g/KRigvLkaxvRtel1AGrgFnD7frAeEAJKOu4WR+QxP3/jkbOe3Xak/+4dPl4VE5SQEkoW/idUTuW94UTFkMqptD7lI+KlKUREGgxKIiINBiURkQaDkohIg0FJRKTBoCQi0mBQEhFpeLofpTBNTP34Tb5Mc6u+3u0SqMJMi83B9Clz3C5j1IQwYAhvf8s9HZQQAsGm6TBN0+1KiDwvaIVRE611u4yy5O2gBNDbm/b1QKHOqat/lFJIp9MuVzM2zqBLPKVSSKdTvn5f8vk8AMBxHKRSSZerGR/bdgZ++31bBn/WvMIXQVku0ml/3uJTOoUfXiUlUqkkjDK455CU0rfvy2COYyOd9vdluYM/a17h+aDsa3b7d89FKQl56hpzv27LcHuOlmVBePy40kikdKBOjRlmmp7/Goyof1uEEDAMPx6mUnA8GpD9PP8JicfrfL3nks1mkUh0QwiB2tp6XzZXLStQ8Ng0TdTVNfhyW/qlUkn09qYRCAQQj9e5Xc649PR0I5fLIhgMoro67nY5oyalRGdnh9tljMjzQQkMv0fjR0KUz7YA5bMtft+OM8v3+7Z4lX931YiIJgmDkohIg0FJRKTBoCQi0mBQEhFpMCiJiDQYlEREGgxKIiINBiURkQaDkohIg0FJRKTBoCQi0mBQEhFpMCiJiDQYlEREGgxKIiINBiURkQaDkohIg0FJRKTBoCQi0mBQEhFpMCiJiDQYlEREGgxKIiINBiURkQaDkohIg0FJRKRhuV2AjpTS7RLGRanT9fdti3KvmDGqqoogXhMbeByLVUFKCaX8ty39+mtXCnAcx+Vqxsfv2+KH77jng7Krq9PtEiaEUgqdnSfcLmNMPnXz70HK06EohMDJk/7clsFsO4/Ozg63y5gQuVwWnZ1Zt8soS54PSnKfZfFjQpXN89+A6uo4DMO/h1Lz+RzS6RSEEKiujkMI4XZJY5bNZpDJ9MIwDFRX1wDw77b09qaRy2VhmhZisWq3yxmXdDqJfD6PQCCAaDSmX8BjpJRIJLrdLmNEng/KQCAA0zTdLmPMzjz+EgwGIIR/Q9+28wD6mt6BQNDXoZ/L9TVRDUMgGAy6XM34ZDJ9nynDMHy5LX44rurfby0R0SRhUBIRaTAoiYg0GJRERBoMSiIiDQYlEZEGg5KISINBSUSkwaAkItJgUBIRaTAoiYg0GJRERBoMSiIiDQYlEZEGg5KISINBSUSkwaAkItJgUBIRaTAoiYg0GJRERBoMSiIiDQYlEZEGg5KISINBSUSkwaAkItJgUBIRaTAoiYg0GJRERBqW2wXoJJMJCCHcLmPMHMcBACilkEj0APDzttgAACnlqW3xL9vOn/pto6en2+Vqxiefzw/89uO2KKXcLkHL80GZy2XdLmHCZLPlsS1KKWSzGbfLmBDltC1SyrLZFq/xfFAGAsEx7VEebT2OgwePnDFF4KILFyISiQyZVymFN97cVhBk8XgNFi08dywlAwB27dqHE50nBx5bAQuXLDkfhuHfox2O48BxbAghEAgE3S5nDBTeeHM7MpnTYVJdHcN5i+e7WNP42XYeUkoYhgHLCrhdzqgppZDP59wuY0SeD8rq6hqYpjnq5f7nxVfwxE/+rWDaPzz4V2hqqh0yr207+Ok/PYu29hMD05ZctBiXv+fdo15vvxc3bMTLr2waeFxTE8MVyy5DJBwe82u6LZ1OIZVKwjAM1NTEfXdIREqJf/7X53C0tW1g2nmL5+GKZZe5WNX49fR0IZvNIhAIoKam1u1yRs1xHHR2drhdxog8H5Sjle7thXQkcrn8kOd6ezNIJlNDpjuOhBx0nMRxnL55hUBVNOK7UCCiiVN2QXn/2vXYvWf/wAHuM62598GzNn17ewuP7by9bRc+c+vXEQoF8fcPrEG8prok9RKR95VdUGYyGaTTvWd5rviTKVJKpNO9cBzHF2fliKh0yi4oB5tSa+AzH4kWPf9/v5LFb3cO3RslospV9kEZCQlctjhQ9DHGTe8wJImoUNkGZVPIRHMkgKnVozsJ0xIN4NJage68g50phiYRlXFQnlcdwkeaYgjEFQCn6OUurw3j/FkGtiey2Jny31UORDTxyjYoDQswIgpGeHQnYkTw1HLe7v9KRJOobIMyNl9i5kpn1JdW114sUXsR0LZLAjtLUxsR+UvZBiUMQIxh64RxatnRXwxERGXKvxceExFNEgYlEZFG2TW9r1i2FOe+aw6CViue//UhxCIC711S/AhEW/fkcei4g4yM44Mrl8KyLISCfhwph4gmStkF5Uc/ch0A4Ol//y/84Cc70Nxo4r1Lig+6l97I4Rcbs1hyUQvuufvjpSqTiHyETW8iIg0GJRGRRtk1vc+G4/8Q0ViVfVDa1hQcmXYnih13Nx15GsCrJa2JiPyl7INSiSCywZaiz3o7BgfoJaJCPEZJRKTBoCQi0ijbpne8phpzZs9ETX0dWg8dhAAwfYqJwHB381TAkXYJx1EIhyzMmT0TjdOmTHbJRORRZRuU1y6/EtcuvxIHDx3FHV++E4DC3/9pHLOaho524TjAfX/dhbaTErd+7o9xx6fWTH7BRORZZRuUZ568OX1zMHWWUddUQfch3pqWiM7EY5RERBoMSiIijbJteverq63BTX+8GoDCr7a+BGdzYsg8AgIrr7sOwopg/ry5k18kEXla2QdlTU01Vn90JZRS+JM/fRUHD2WGzGOaBtZ/7yqe6SaiYXk+KG3bhpTF30XxbJQCZs1shGUNPettmgYEFPL5ibujmFSDri5XgJ23kTf9e9ey/vdBKQXb9t+tfKVUGPy2SDmx77sbpJSnfvtzW/rr9zLPB2VPT9eEvdYtN68e4VmJrq6TE7aufK7wAyuVRFd3J8KZ0IStwy1STuzfarJIKYf807Vt25fbMpx8PoeuLv8FpR94OiiVUr74bzMcNXjXBX3HQslNw//9pfTn2FKGwc/TZPF0UDqOg7XrfoienqTbpYxaIpkqeGwYBurqGhAO+3ePMpPpRTqdgmGYqK2txajvBewyKSUMs/DQS0dS4elN4z+0M9kCpsAfXTUV4aCBZLIHuVwOwWAQsViN26WNmpSO5/fqPR2USgEnu7rR1TX0TLUfGaYB0/TvfXD7O+ILARiG6buO+UIM3ad3JJDKulLOuARMQBh9n6fT74vw9efLy9iPkohIg0FJRKTh6ab3cGqqBOZO91bzoietsO+o/45zEVFxfBeU82db+MtPemsU8s07crj3R/474URExfFdUI6dARhW3xkidaqztLAAYQDK6fshGgfTEDizx44CYDv+7HpEhSomKINTliHafANk9gR6tn0bgERs3u2wqmYjc+wFZFqfd7tE8rkbr5mDlqaqgcddyRwefnbXkKuByH8qJiiFEYQRiEM5p/uCGFYMRiAOYYZdrIzKRSRkIhoysHPnXjjSQU8qj0T7YZjBCCI1DW6XR+NQMUFJNBnSvRl85c41SKbSA9MuvXwZ6meuQmeClxf6FbsHEZVYXXUIkRD3SfysYt49mW1HrnMTlMwgUHcxAAU7fRAy1wmn96jb5VEZ607lEMnZbpdB41AxQZnvfgv57rdghKYifuG3ARjo2XYfnNR+t0ujMre3NYnAOWx2+1nFBCVRKaVOHsMTj/wK0aBAJlsYiomOw9i98WcwAyHMWbIchuGtCyZIj0FJNAEyyS789pcvDv9cohPHEp0IhGOYc+E1AIPSdxiURBMgEK7C4vPPQ9AS2Lp1Gxzn9Diq9fV1CMQa4IhQ39BL5DsMSqIJUDO1GbfcdA0a4wb+4A8+U9A9qH7GOWi57Hpkcrz6y6/YPYioxLpTeYakz1XcHqVyMsh1vAIIAWVzIAuaOLuPJHC8Q8L26a0l6OwqLyjtBFL7HnG7DCpDv9rSBjuXQd72532e6OwqLiiJJsuMhcsQa5iOXDqBHf/3NKxgGHPfvZLdg3yIxyiJSiTeOAfT5l6IYCSG9v1b0XFwO+DTu4pWOu5REk0gYRion7UA0s4hGOkbYDpUFUdD80JYwUjf+KfkO74Lyh0HbHzjH3vcLqNAIs2D99THtIJYcOXvFUyLN7Yg3tjiTkE0IXwXlIm0wtY9HGCAiCYP2wFERBoMSiIiDU83vYUApk5pQCgUcruUUevq6kF20Cgy0pFwHP8eNlBKnvoNSOm/K02kVBh8NNkygHjUf911ApaAMei6caWULz9f0gc9ATwdlJZl4f5v/hkMw387vuse+AF+/ermgcdSSpw8eQKhUNDFqiaGlA46O0+4XcaoSakgncKAb6oL4tPvb3SpovEZPL5GLpfz5fviB54LSnXqlnVKKQghYBiGL4NSDDNKjIIa2D5yw9C/vRD+HtBHKdV3B+Yy/1z1b99w36vJIFSRf+F8vndCV7xz1158+jNfLpg2bdoU1NfXQkqJXLbvbomWZfnyk3zsWBuSydMjyBiGgeZZTa690dTn8JHjsO3TzdNwOIRZs6a7WNH4ScfxRfO1GK3H2gsOWQWDAZwzdw4ggG/8xZfR3DxjQtcXCESKms9Te5RtbR1oa+twu4ySkFLiwEHem8drMpksdu/e73YZdBa5XB7v7NgNAMhks5q5S8d/bVoioknGoCQi0vBU07uhvg7xeLXbZRCRS462Hkcmc7qJHQhYmDVrBoQQCAXd6zHiqaD82Mc+it+/YZXbZRCRS27/k7/Alq3bBh43NTXikR/+HQzD3ZOgrgalEKKgW4OAe6f/ich9g7/+/d233M4F17oHZbM5HG09VjCtvo5Nb6JK1tp6vODsdsAKYObM0nWrK7Z7kGtBSUTktmKDkme9iYg0GJRERBoMSiIiDQYlEZEGg5KISINBSUSkwaAkItJgUBIRaTAoiYg0GJRERBoMSiIiDQYlEZEGg5KISINBSUSkwaAkItJgUBIRaTAoiYg0GJRERBoMSiIijaLvmUNEVKm4R0lEpMGgJCLSYFASEWkwKImINBiUREQaDEoiIg0GJRGRBoOSiEiDQUlEpPH/LojqRC6jkHwAAAAASUVORK5CYII=",
            "text/plain": [
              "<Figure size 400x400 with 1 Axes>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "taxi = gym.make('Taxi-v4', render_mode='rgb_array')\n",
        "obs, info = taxi.reset(seed=0)\n",
        "frame = taxi.render()\n",
        "taxi.close()\n",
        "\n",
        "plt.figure(figsize=(4, 4))\n",
        "plt.imshow(frame)\n",
        "plt.axis('off')\n",
        "plt.title('Taxi')\n",
        "plt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "NjyJJln9cusZ",
      "metadata": {
        "id": "NjyJJln9cusZ"
      },
      "source": [
        "**Задача 3.** Сделайте несколько шагов случайными действиями и понаблюдайте за наградой. Когда она становится −10, а когда +20? Подтвердите наблюдение, глядя на `decode(obs)`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "bi2sfgEwfQ0n",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "bi2sfgEwfQ0n",
        "outputId": "dcd126c8-3079-4559-afb5-11b90a3b22e1"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "a=5, r=-10, obs=252, decode=(2, 2, 3, 0)\n",
            "a=0, r=-1, obs=352, decode=(3, 2, 3, 0)\n",
            "a=3, r=-1, obs=332, decode=(3, 1, 3, 0)\n",
            "a=1, r=-1, obs=232, decode=(2, 1, 3, 0)\n",
            "a=5, r=-10, obs=232, decode=(2, 1, 3, 0)\n",
            "a=1, r=-1, obs=132, decode=(1, 1, 3, 0)\n",
            "a=3, r=-1, obs=112, decode=(1, 0, 3, 0)\n",
            "a=4, r=-10, obs=112, decode=(1, 0, 3, 0)\n",
            "a=2, r=-1, obs=132, decode=(1, 1, 3, 0)\n",
            "a=5, r=-10, obs=132, decode=(1, 1, 3, 0)\n"
          ]
        }
      ],
      "source": [
        "taxi = gym.make('Taxi-v4', render_mode='ansi')\n",
        "obs, info = taxi.reset(seed=1)\n",
        "\n",
        "for _ in range(10):\n",
        "    action = taxi.action_space.sample()\n",
        "    obs, reward, terminated, truncated, info = taxi.step(action)\n",
        "    print(f'a={action}, r={reward}, obs={obs}, decode={taxi.unwrapped.decode(obs)}')\n",
        "    if terminated or truncated:\n",
        "        break\n",
        "taxi.close()"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "1TXzjglViNxm",
      "metadata": {
        "id": "1TXzjglViNxm"
      },
      "source": [
        "**Ваш ответ:**"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "oAXVOUW_fbF_",
      "metadata": {
        "id": "oAXVOUW_fbF_"
      },
      "source": [
        "## 6. Модель среды: env.P\n",
        "\n",
        "Taxi — среда с известной моделью: переходы и награды можно прочитать из `env.P`. Для пары (состояние, действие) там лежит список записей (вероятность, следующее_состояние, награда, завершённость эпизода).\n",
        "\n",
        "В новых версиях Gymnasium среда обёрнута в `TimeLimit`, поэтому модель достаём через `.unwrapped`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "EHFSXMkdfcMY",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "EHFSXMkdfcMY",
        "outputId": "cb7ae738-f0fc-41a7-b0a0-3c6b26d86a26"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Состояний: 500 , действий: 6\n",
            "Состояние 123 = (1, 1, 0, 3)\n",
            "Переходы по действиям:\n",
            "  действие 0: [(1.0, 223, -1, False)]\n",
            "  действие 1: [(1.0, 23, -1, False)]\n",
            "  действие 2: [(1.0, 123, -1, False)]\n",
            "  действие 3: [(1.0, 103, -1, False)]\n",
            "  действие 4: [(1.0, 123, -10, False)]\n",
            "  действие 5: [(1.0, 123, -10, False)]\n"
          ]
        }
      ],
      "source": [
        "taxi = gym.make('Taxi-v4').unwrapped\n",
        "\n",
        "nS = taxi.observation_space.n\n",
        "nA = taxi.action_space.n\n",
        "print('Состояний:', nS, ', действий:', nA)\n",
        "\n",
        "s = 123  # произвольное состояние\n",
        "print('Состояние', s, '=', taxi.decode(s))\n",
        "print('Переходы по действиям:')\n",
        "for a in range(nA):\n",
        "    print(f'  действие {a}:', taxi.P[s][a])"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "I8pBsGELfkpa",
      "metadata": {
        "id": "I8pBsGELfkpa"
      },
      "source": [
        "**Задача 4.** Найдите состояние, в котором пассажир уже находится в такси, и посмотрите на его переходы. Почему при действии «высадить» эпизод может завершиться, а при «подобрать» — нет?"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "kdryl5z6fpCH",
      "metadata": {
        "id": "kdryl5z6fpCH"
      },
      "source": [
        "**Ваш ответ:**"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "SSL34t5AfwIo",
      "metadata": {
        "id": "SSL34t5AfwIo"
      },
      "source": [
        "## 7. Оценка политики (policy evaluation) — теория\n",
        "\n",
        "**Задача:** дана политика $\\pi$. Нужно найти её функцию ценности $V^\\pi(s)$ — ожидаемый дисконтированный доход из каждого состояния при следовании $\\pi$.\n",
        "\n",
        "**Уравнение Беллмана для ожидания** — самосогласованное равенство, которому удовлетворяет $V^\\pi$:\n",
        "\n",
        "$$V^\\pi(s) = \\sum_a \\pi(a|s) \\sum_{s',r} p(s',r|s,a) \\left[ r + \\gamma V^\\pi(s') \\right]$$\n",
        "\n",
        "**Итеративный алгоритм.** Задаём произвольное начальное приближение $V_0$ (обычно нули) и повторяем:\n",
        "\n",
        "$$V_{k+1}(s) \\leftarrow \\sum_a \\pi(a|s) \\sum_{s',r} p(s',r|s,a) \\left[ r + \\gamma V_k(s') \\right]$$\n",
        "\n",
        "**Почему сходится.** Оператор Беллмана — сжимающее отображение с коэффициентом $\\gamma$: каждое применение умножает ошибку на $\\gamma$. По теореме Банаха о неподвижной точке последовательность $V_k$ сходится к единственному решению $V^\\pi$ независимо от начального приближения. Останавливаемся, когда максимальное изменение $\\max_s |V_{k+1}(s) - V_k(s)|$ станет меньше $\\theta$."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "BgB7yhCjfwqZ",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "BgB7yhCjfwqZ",
        "outputId": "e618b260-b52e-4206-8c73-879694e1b6a9"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Мин/макс V при случайной политике: -395.5 -88.06\n",
            "V состояния 0: -217.88\n"
          ]
        }
      ],
      "source": [
        "def policy_evaluation_taxi(env, policy, gamma=0.99, theta=1e-6):\n",
        "    nS = env.observation_space.n\n",
        "    nA = env.action_space.n\n",
        "    V = np.zeros(nS)\n",
        "    while True:\n",
        "        V_new = np.zeros(nS)\n",
        "        for s in range(nS):\n",
        "            val = 0.0\n",
        "            for a in range(nA):\n",
        "                q_sa = 0.0\n",
        "                for prob, s2, r, done in env.P[s][a]:\n",
        "                    q_sa += prob * (r + (0.0 if done else gamma * V[s2]))\n",
        "                val += policy[s, a] * q_sa\n",
        "            V_new[s] = val\n",
        "        if np.max(np.abs(V_new - V)) < theta:\n",
        "            return V_new\n",
        "        V = V_new\n",
        "\n",
        "taxi = gym.make('Taxi-v4').unwrapped\n",
        "uniform = np.full((taxi.observation_space.n, taxi.action_space.n), 1.0 / taxi.action_space.n)\n",
        "V_uniform = policy_evaluation_taxi(taxi, uniform)\n",
        "\n",
        "print('Мин/макс V при случайной политике:', round(V_uniform.min(), 2), round(V_uniform.max(), 2))\n",
        "print('V состояния 0:', round(V_uniform[0], 2))"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "asPYwfQ5f54i",
      "metadata": {
        "id": "asPYwfQ5f54i"
      },
      "source": [
        "**Задача 5.** Сравните значения $V$ для состояний, где пассажир ещё на пункте (ожидает такси), и для состояний, где он уже в такси. Где ценность выше и почему?"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "B0iWyWY3foTA",
      "metadata": {
        "id": "B0iWyWY3foTA"
      },
      "outputs": [],
      "source": [
        "# Ваш Код"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "vtZar6ExgIDq",
      "metadata": {
        "id": "vtZar6ExgIDq"
      },
      "source": [
        "## 8. Value iteration — теория\n",
        "\n",
        "**Оптимальная ценность.** $V^*(s) = \\max_\\pi V^\\pi(s)$ — наилучший возможный доход из состояния $s$. Аналогично $Q^*(s,a)$ — наилучший доход, если сначала выполнить действие $a$, а дальше действовать оптимально.\n",
        "\n",
        "**Уравнение оптимальности Беллмана:**\n",
        "\n",
        "$$V^*(s) = \\max_a \\sum_{s',r} p(s',r|s,a) \\left[ r + \\gamma V^*(s') \\right]$$\n",
        "\n",
        "Отличие от уравнения для $V^\\pi$ — максимум вместо усреднения по политике.\n",
        "\n",
        "**Алгоритм value iteration.**\n",
        "\n",
        "$$V_{k+1}(s) \\leftarrow \\max_a \\sum_{s',r} p(s',r|s,a) \\left[ r + \\gamma V_k(s') \\right]$$\n",
        "\n",
        "После сходимости получаем $V^*$, а оптимальную политику строим **жадно**:\n",
        "\n",
        "$$\\pi^*(s) = \\arg\\max_a \\sum_{s',r} p(s',r|s,a) \\left[ r + \\gamma V^*(s') \\right] = \\arg\\max_a Q^*(s,a)$$\n",
        "\n",
        "**Связь с policy iteration.** Value iteration — это «усечённая» итерация политики: вместо полной оценки текущей политики до сходимости мы делаем один проход с максимумом. Оба метода находят $V^*$, но value iteration обычно требует меньше вычислений."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "pvLkwEkigIjJ",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "pvLkwEkigIjJ",
        "outputId": "ef0757cd-3f9c-481f-81ec-0ad710865fd2"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "V* состояния 0: 18.8\n"
          ]
        }
      ],
      "source": [
        "def value_iteration_taxi(env, gamma=0.99, theta=1e-6):\n",
        "    nS = env.observation_space.n\n",
        "    nA = env.action_space.n\n",
        "    V = np.zeros(nS)\n",
        "    while True:\n",
        "        V_new = np.zeros(nS)\n",
        "        for s in range(nS):\n",
        "            q = np.zeros(nA)\n",
        "            for a in range(nA):\n",
        "                for prob, s2, r, done in env.P[s][a]:\n",
        "                    q[a] += prob * (r + (0.0 if done else gamma * V[s2]))\n",
        "            V_new[s] = np.max(q)\n",
        "        if np.max(np.abs(V_new - V)) < theta:\n",
        "            return V_new\n",
        "        V = V_new\n",
        "\n",
        "taxi = gym.make('Taxi-v4').unwrapped\n",
        "V_star = value_iteration_taxi(taxi)\n",
        "print('V* состояния 0:', round(V_star[0], 2))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "xApC_BOsgWYs",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "xApC_BOsgWYs",
        "outputId": "8ae4f083-1823-420b-d202-1ff6d8f486c7"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Политика построена: для каждого из 500 состояний выбрано действие.\n"
          ]
        }
      ],
      "source": [
        "def greedy_policy_taxi(env, V, gamma=0.99):\n",
        "    nS = env.observation_space.n\n",
        "    nA = env.action_space.n\n",
        "    policy = np.zeros(nS, dtype=int)\n",
        "    for s in range(nS):\n",
        "        q = np.zeros(nA)\n",
        "        for a in range(nA):\n",
        "            for prob, s2, r, done in env.P[s][a]:\n",
        "                q[a] += prob * (r + (0.0 if done else gamma * V[s2]))\n",
        "        policy[s] = int(np.argmax(q))\n",
        "    return policy\n",
        "\n",
        "policy = greedy_policy_taxi(taxi, V_star)\n",
        "print('Политика построена: для каждого из 500 состояний выбрано действие.')"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "fZSuVt4IgZLy",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "fZSuVt4IgZLy",
        "outputId": "7968a1a4-9a6e-4e16-d741-7efee6efd7b3"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0 (0, 0, 0, 0) -> подобрать\n",
            "100 (1, 0, 0, 0) -> вверх\n",
            "200 (2, 0, 0, 0) -> вверх\n",
            "300 (3, 0, 0, 0) -> вверх\n",
            "400 (4, 0, 0, 0) -> вверх\n"
          ]
        }
      ],
      "source": [
        "taxi = gym.make('Taxi-v4').unwrapped\n",
        "actions_names = ['вниз', 'вверх', 'вправо', 'влево', 'подобрать', 'высадить']\n",
        "\n",
        "for s in [0, 100, 200, 300, 400]:\n",
        "    print(s, taxi.decode(s), '->', actions_names[policy[s]])"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "HJ-wtiKWgcX6",
      "metadata": {
        "id": "HJ-wtiKWgcX6"
      },
      "source": [
        "**Задача 6.** Возьмите несколько состояний с разных этапов поездки (пассажир на пункте / пассажир в такси) и выведите выбранные политикой действия. Логичны ли они?"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "gQqsr7M7gfBy",
      "metadata": {
        "id": "gQqsr7M7gfBy"
      },
      "outputs": [],
      "source": [
        "# Ваш Код"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "f0GzOi9rgjTb",
      "metadata": {
        "id": "f0GzOi9rgjTb"
      },
      "source": [
        "## 9. Проверка политики в среде — теория\n",
        "\n",
        "**Идея.** До этого мы использовали модель `env.P` и считали ценности точно. Теперь проверим политику без модели: запустим её в среде и усредним фактически полученные награды.\n",
        "\n",
        "**Монте-Карло оценка $J(\\pi)$.** Запускаем политику $N$ эпизодов, в каждом получаем суммарную награду (доход) $G^{(i)}$, и усредняем:\n",
        "\n",
        "$$\\hat{J}(\\pi) = \\frac{1}{N} \\sum_{i=1}^{N} G^{(i)}$$\n",
        "\n",
        "Это оценка ожидаемого дохода $J(\\pi) = \\mathbb{E}_\\pi[G_0]$.\n",
        "\n",
        "**Зачем сравнивать со случайной политикой.** Случайная политика — простой baseline: если наша политика не лучше случайной, значит, она ничему не научилась. Разница между средней наградой оптимальной и случайной политики показывает «выигрыш» от обучения.\n",
        "\n",
        "**Отличие от точного расчёта.** Здесь есть шум выборки: при малом $N$ оценка колеблется. Поэтому берём много эпизодов, а для воспроизводимости фиксируем сиды (`seed=ep`)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "Zbwozxm5gjxw",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Zbwozxm5gjxw",
        "outputId": "9060ef95-da30-4258-bb1e-59c04c552bba"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Средняя награда случайной политики: -1348.85\n",
            "Средняя награда оптимальной политики: 7.69\n"
          ]
        }
      ],
      "source": [
        "def evaluate_policy(env, policy, n_episodes=100):\n",
        "    total = 0.0\n",
        "    for ep in range(n_episodes):\n",
        "        obs, info = env.reset(seed=ep)\n",
        "        done = False\n",
        "        while not done:\n",
        "            obs, reward, terminated, truncated, info = env.step(int(policy[obs]))\n",
        "            total += reward\n",
        "            done = terminated or truncated\n",
        "    return total / n_episodes\n",
        "\n",
        "env = gym.make('Taxi-v4')\n",
        "random_pol = np.random.randint(0, 6, size=env.observation_space.n)\n",
        "\n",
        "print('Средняя награда случайной политики:', round(evaluate_policy(env, random_pol), 2))\n",
        "print('Средняя награда оптимальной политики:', round(evaluate_policy(env, policy), 2))\n",
        "env.close()"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "LoK1DUVNgrka",
      "metadata": {
        "id": "LoK1DUVNgrka"
      },
      "source": [
        "**Задание 7.** Визуализируйте один эпизод оптимальной политики (через `render_mode='ansi'` или функцию `render_taxi`): видно ли, как такси едет к пассажиру, подбирает и довозит его?"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "s3Adzotwi2Ha",
      "metadata": {
        "id": "s3Adzotwi2Ha"
      },
      "outputs": [],
      "source": [
        "# Ваш Код"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}
