notebooks/RL_entropy_regularization.ipynb

{
    "cells": [
        {
            "attachments": {},
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "# RLにおけるKLとエントロピー正則化\n",
                "\n",
                "強化学習アルゴリズムではKLやエントロピー正則化がよく出てきます。\n",
                "この正則化を導入すると、アルゴリズムにどのような違いが生じるでしょうか？\n",
                "今回は強化学習と正則化の理論について見ていきます。\n",
                "\n",
                "参考：\n",
                "\n",
                "* [Leverage the Average: an Analysis of KL Regularization in Reinforcement Learning](https://arxiv.org/abs/2003.14089)\n",
                "* [Theoretical Analysis of Efficiency and Robustness of Softmax and Gap-Increasing Operators in Reinforcement Learning](https://proceedings.mlr.press/v89/kozuno19a.html)\n",
                "* [Tsallis Reinforcement Learning: A Unified Framework for Maximum Entropy Reinforcement Learning](https://arxiv.org/abs/1902.00137)"
            ]
        },
        {
            "attachments": {},
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## 方策更新でのエントロピー正則化\n",
                "\n",
                "[RL_multi_step.ipynb](RL_multi_step.ipynb)でも説明しましたが、強化学習の基本は``方策評価``と``方策更新``にあります。\n",
                "そして、正則化をそのどちらかもしくは両方に導入することで、強化学習アルゴリズムの誤差に対する頑健性を著しく向上することが理論的に可能です。\n",
                "まずは``方策更新``側に正則化が入っている場合の理論を見てみましょう。\n",
                "\n",
                "参考\n",
                "* [Theoretical Analysis of Efficiency and Robustness of Softmax and Gap-Increasing Operators in Reinforcement Learning](https://proceedings.mlr.press/v89/kozuno19a.html)\n",
                "* [Leverage the Average: an Analysis of KL Regularization in Reinforcement Learning](https://arxiv.org/abs/2003.14089)\n",
                "* [Convex Optimization](https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf)\n",
                "\n",
                "まず次の貪欲方策を見てみましょう。これはQ学習系のアルゴリズムでよく使われます（e.g., DQN, DDPG）\n",
                "\n",
                "$$\\mathcal{G}(q) = \\argmax_{\\pi} \\langle q, \\pi \\rangle$$\n",
                "\n",
                "貪欲方策はQ値が最大の行動だけがサンプルされるように確率を割り当てます。\n",
                "この貪欲方策は単純ですが、あまり誤差に強くありません。(TODO: 参考文献)\n",
                "\n",
                "これを緩和するために、次のように正則化を導入した更新則を考えることができます。\n",
                "\n",
                "$$\\mathcal{G}(q) = \\argmax_{\\pi} \\langle q, \\pi \\rangle$$\n",
                "\n",
                "TODO: これの正当化。貪欲方策を考えるといいことがあるのか？\n",
                "**ルジャンドル変換**を使うと更新式をきれいに書くことができます。見てみましょう。"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": 11,
            "metadata": {},
            "outputs": [
                {
                    "data": {
                        "text/plain": [
                            "<matplotlib.legend.Legend at 0x7fa21e9af220>"
                        ]
                    },
                    "execution_count": 11,
                    "metadata": {},
                    "output_type": "execute_result"
                },
                {
                    "data": {
                        "image/png": "iVBORw0KGgoAAAANSUhEUgAAAiMAAAGwCAYAAAB7MGXBAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjYuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/P9b71AAAACXBIWXMAAA9hAAAPYQGoP6dpAAAlgklEQVR4nO3df3CUhZ3H8c8Skw3UJIiYXxIJBxr5IQECwcBUowQj5jhiO4pWJ5gCc9dJOqTp6RlrUfCc0FoKzAEBhh+ZSimICrRAwRgKqRIOAqQSKhycAqlmExRIJEjAZO8PyvZ2SDAbEr758X7N7Iz77PPs891nHPKeZ5/ddbjdbrcAAACMdLMeAAAAdG3ECAAAMEWMAAAAU8QIAAAwRYwAAABTxAgAADBFjAAAAFO3WA/QHA0NDfr8888VFBQkh8NhPQ4AAGgGt9utr776SpGRkerWrenzHx0iRj7//HNFRUVZjwEAAFqgvLxcffr0afLxDhEjQUFBkq68mODgYONpAABAc9TU1CgqKsrzd7wpHSJGrr41ExwcTIwAANDBfNslFlzACgAATBEjAADAFDECAABMdYhrRgAAuFnq6+t1+fJl6zE6BH9/f/n5+d3w8xAjAADoyndiuFwunTt3znqUDqVnz54KDw+/oe8BI0YAAJA8IRIaGqoePXrwJZvfwu1268KFC6qqqpIkRUREtPi5iBEAQJdXX1/vCZHbb7/depwOo3v37pKkqqoqhYaGtvgtGy5gBQB0eVevEenRo4fxJB3P1WN2I9fZECMAAPwdb834rjWOGTECAABMESMAAMCUTxew5uXlKS8vTydOnJAkDR48WDNnztSECROa3Gb9+vX6+c9/rhMnTujuu+/WL37xCz322GM3NDQAADdL9Itbbur+TsxJuan7aw98OjPSp08fzZkzR/v371dJSYkefvhhTZo0SYcPH250/d27d+vpp5/W1KlTdfDgQaWmpio1NVVlZWWtMjwAALiivLxcP/zhDxUZGamAgAD17dtXM2bM0Jdffmk92rfyKUYmTpyoxx57THfffbfuuecevf7667r11lu1Z8+eRtdfsGCBHn30UT3//PMaOHCgXnvtNY0YMUILFy5sleEBAID0ySefaOTIkTp27Jh+97vf6fjx41qyZIkKCwuVkJCgM2fOWI94XS3+npH6+nqtX79etbW1SkhIaHSd4uJiZWdney1LTk7Wxo0br/vcdXV1qqur89yvqalp6ZgAAHR6GRkZCggI0Hvvvef57o+77rpLw4cPV//+/fWzn/1MeXl5xlM2zecYOXTokBISEnTx4kXdeuut2rBhgwYNGtToui6XS2FhYV7LwsLC5HK5rruP3NxczZo1y9fR0IHc7PdgO7Ku+P4xgOY7c+aMtm/frtdff90TIleFh4frmWee0bp167R48eJ2+9Flnz9NExMTo9LSUv33f/+3fvSjH2nKlCn661//2qpD5eTkqLq62nMrLy9v1ecHAKCzOHbsmNxutwYOHNjo4wMHDtTZs2d1+vTpmzxZ8/l8ZiQgIEADBgyQJMXFxWnfvn1asGCBli5des264eHhqqys9FpWWVmp8PDw6+7D6XTK6XT6OhoAAF2W2+2+7uMBAQE3aRLf3fD3jDQ0NHhd3/H/JSQkqLCw0GtZQUFBk9eYAAAA3wwYMEAOh0Mff/xxo49//PHHuuOOO9SzZ8+bO5gPfIqRnJwcFRUV6cSJEzp06JBycnK0c+dOPfPMM5KktLQ05eTkeNafMWOGtm3bprlz5+rIkSN69dVXVVJSoszMzNZ9FQAAdFG33367xo8fr8WLF+vrr7/2eszlcum3v/2tnnvuOZvhmsmnGKmqqlJaWppiYmI0btw47du3T9u3b9f48eMlSadOnVJFRYVn/TFjxmjNmjVatmyZYmNj9fbbb2vjxo0aMmRI674KAAC6sIULF6qurk7JyckqKipSeXm5tm3bpvHjx+uee+7RzJkzrUe8Lof7295kagdqamoUEhKi6upqBQcHW4+DVsCnaZqPT9MAbe/ixYv69NNP1a9fPwUGBlqP0yInTpzQq6++qm3btqmqqkput1vf+9739Oabb7bprxFf79g19+83v00DAEAnEB0drfz8fLlcLjU0NGjmzJl677339NFHH1mP9q1a/KVnAACg/Zo1a5aio6O1Z88excfHq1u39nv+gRgBAKCTSk9Ptx6hWdpvJgEAgC6BGAEAAKaIEQAAYIoYAQAApogRAABgihgBAACmiBEAAGCKGAEAAKaIEQAAuoAvv/xSoaGhOnHiRLO3eeqppzR37ty2G+rv+AZWAACu59WQm7y/6hvavKSkRBs2bJDL5dIPfvADjRs3TpL0+uuva9KkSYqOjm72c7388st64IEHNG3aNIWEtN1x4MwIAACdQG1trZ566iktX75c6enpGj16tJ544glJ0oULF7RixQpNnTrVp+ccMmSI+vfvr9WrV7fFyB7ECAAAHdylS5eUlJSkwYMHa8mSJRowYICKioo0YcIESdLWrVvldDp1//33e2135MgRPfTQQwoMDNQ999yjrVu3yuFwqLS01LPOxIkTtXbt2jadnxgBAKCD+/nPf666ujq9/PLLnmWrV6/Wb3/7W0nSn//8Z8XFxXltc+TIEY0ePVrf/e53dfjwYf3iF79QWlqa/P39NWjQIM968fHx2rt3r+rq6tpsfq4ZAQCgAzt37pwWLVqkRYsWyeFwNLrOyZMnFRkZ6bUsIyND3//+9zV79mxJ8rwdc+zYMQUEBHjWi4yM1KVLl+RyudS3b982eQ3ECAAAHdiOHTtUW1urxMTEax47cuSI7r33Xn399dcKDAz0LD958qR27Nihv/zlL17rBwQEKDY21mtZ9+7dJV257qSt8DYNAAAd2MmTJyVJ4eHhXssbGhqUl5cnSerdu7fOnj3reay0tPSat2Mkqays7JoYOXPmjCTpjjvuaPXZryJGAADowK5GyJdffum1/Je//KWCgoIkScOHD9df//pXz2PdunVTfX296uvrPcu2bdvWaIyUlZWpT58+6t27d1u9BGIEAICO7J//+Z/Vt29fvfTSSzp37pw++eQT/fu//7t+9rOf6V/+5V8kScnJyTp8+LDn7EhcXJz8/f310ksv6ZNPPtE777yjjIwMSbomRv785z/rkUceadPXQIwAANCBBQUFae/evYqIiNAPf/hDLV68WBcuXNB3v/tdxcfHS5Luu+8+jRgxQm+99ZakKxelLl++XG+99ZZiY2O1bt06TZ8+XeHh4QoNDfU898WLF7Vx40ZNnz69TV8DF7ACAHA9N/iNqG3t0qVLuu2225Sbmyu3261Vq1Zp1qxZev/9973Wmzlzpp5//nlNnz5d3bp107PPPqtnn33W83h2dvY1Z0VWrVql+Pj4a76fpLURIwAAdGBut1u/+tWvdOzYMZ0+fVr9+vVTcXHxNR/lTUlJ0bFjx/TZZ58pKirqmuf56KOPrvkuEn9/f/3Xf/1Xm84vESMAAHRoTqdTL730UrPWzcrKavKxQ4cOKT093WvZtGnTbmS0ZiNGAACAKisrzfbNBawAAMAUMQIAAEwRIwAAwBQxAgDA37ndbusROpzWOGbECACgy/P395fUtj8G11ldPWZXj2FL8GkaAECX5+fnp549e6qqqkqS1KNHDzkcDuOp2je3260LFy6oqqpKPXv2lJ+fX4ufixgBAED/+MG5q0GC5unZs+c1vxjsK2IEAABJDodDERERCg0N1eXLl63H6RD8/f1v6IzIVcQIAAD/j5+fX6v8gUXzcQErAAAwRYwAAABTxAgAADBFjAAAAFPECAAAMMWnaQAAnVL0i1usR+gwTsxJMd0/Z0YAAIApYgQAAJgiRgAAgCliBAAAmCJGAACAKWIEAACYIkYAAIApn2IkNzdXo0aNUlBQkEJDQ5WamqqjR49ed5v8/Hw5HA6vW2Bg4A0NDQAAOg+fYmTXrl3KyMjQnj17VFBQoMuXL+uRRx5RbW3tdbcLDg5WRUWF53by5MkbGhoAAHQePn0D67Zt27zu5+fnKzQ0VPv379cDDzzQ5HYOh0Ph4eHN3k9dXZ3q6uo892tqanwZEwAAdCA3dM1IdXW1JKlXr17XXe/8+fPq27evoqKiNGnSJB0+fPi66+fm5iokJMRzi4qKupExAQBAO9biGGloaFBWVpbGjh2rIUOGNLleTEyMVq5cqU2bNmn16tVqaGjQmDFj9Le//a3JbXJyclRdXe25lZeXt3RMAADQzrX4h/IyMjJUVlamDz744LrrJSQkKCEhwXN/zJgxGjhwoJYuXarXXnut0W2cTqecTmdLRwMAAB1Ii2IkMzNTmzdvVlFRkfr06ePTtv7+/ho+fLiOHz/ekl0DAIBOxqe3adxutzIzM7Vhwwbt2LFD/fr183mH9fX1OnTokCIiInzeFgAAdD4+nRnJyMjQmjVrtGnTJgUFBcnlckmSQkJC1L17d0lSWlqa7rzzTuXm5kqSZs+erfvvv18DBgzQuXPn9MYbb+jkyZOaNm1aK78UAADQEfkUI3l5eZKkxMREr+WrVq3Sc889J0k6deqUunX7xwmXs2fPavr06XK5XLrtttsUFxen3bt3a9CgQTc2OQAA6BR8ihG32/2t6+zcudPr/rx58zRv3jyfhgIAAF0Hv00DAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATPkUI7m5uRo1apSCgoIUGhqq1NRUHT169Fu3W79+ve69914FBgbqvvvu09atW1s8MAAA6Fx8ipFdu3YpIyNDe/bsUUFBgS5fvqxHHnlEtbW1TW6ze/duPf3005o6daoOHjyo1NRUpaamqqys7IaHBwAAHZ/D7Xa7W7rx6dOnFRoaql27dumBBx5odJ3JkyertrZWmzdv9iy7//77NWzYMC1ZsqRZ+6mpqVFISIiqq6sVHBzc0nHRjkS/uMV6hA7jxJwU6xGADol/Z5qvrf6dae7f7xu6ZqS6ulqS1KtXrybXKS4uVlJSktey5ORkFRcXN7lNXV2dampqvG4AAKBzanGMNDQ0KCsrS2PHjtWQIUOaXM/lciksLMxrWVhYmFwuV5Pb5ObmKiQkxHOLiopq6ZgAAKCda3GMZGRkqKysTGvXrm3NeSRJOTk5qq6u9tzKy8tbfR8AAKB9uKUlG2VmZmrz5s0qKipSnz59rrtueHi4KisrvZZVVlYqPDy8yW2cTqecTmdLRgMAAB2MT2dG3G63MjMztWHDBu3YsUP9+vX71m0SEhJUWFjotaygoEAJCQm+TQoAADoln86MZGRkaM2aNdq0aZOCgoI8132EhISoe/fukqS0tDTdeeedys3NlSTNmDFDDz74oObOnauUlBStXbtWJSUlWrZsWSu/FAAA0BH5dGYkLy9P1dXVSkxMVEREhOe2bt06zzqnTp1SRUWF5/6YMWO0Zs0aLVu2TLGxsXr77be1cePG6170CgAAug6fzow05ytJdu7cec2yJ554Qk888YQvuwIAAF0Ev00DAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAlM8xUlRUpIkTJyoyMlIOh0MbN2687vo7d+6Uw+G45uZyuVo6MwAA6ER8jpHa2lrFxsZq0aJFPm139OhRVVRUeG6hoaG+7hoAAHRCt/i6wYQJEzRhwgSfdxQaGqqePXv6vB0AAOjcbto1I8OGDVNERITGjx+vDz/88Lrr1tXVqaamxusGAAA6pzaPkYiICC1ZskTvvPOO3nnnHUVFRSkxMVEHDhxocpvc3FyFhIR4blFRUW09JgAAMOLz2zS+iomJUUxMjOf+mDFj9L//+7+aN2+e3nzzzUa3ycnJUXZ2tud+TU0NQQIAQCfV5jHSmPj4eH3wwQdNPu50OuV0Om/iRAAAwIrJ94yUlpYqIiLCYtcAAKCd8fnMyPnz53X8+HHP/U8//VSlpaXq1auX7rrrLuXk5Oizzz7Tb37zG0nS/Pnz1a9fPw0ePFgXL17U8uXLtWPHDr333nut9yoAAECH5XOMlJSU6KGHHvLcv3ptx5QpU5Sfn6+KigqdOnXK8/ilS5f005/+VJ999pl69OihoUOH6v333/d6DgAA0HX5HCOJiYlyu91NPp6fn+91/4UXXtALL7zg82AAAKBr4LdpAACAKWIEAACYIkYAAIApYgQAAJgiRgAAgCliBAAAmCJGAACAKWIEAACYIkYAAIApYgQAAJgiRgAAgCliBAAAmCJGAACAKWIEAACYIkYAAIApYgQAAJi6xXoAADdP9ItbrEfoME7MSbEeAegyODMCAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABM+RwjRUVFmjhxoiIjI+VwOLRx48Zv3Wbnzp0aMWKEnE6nBgwYoPz8/BaMCgAAOiOfY6S2tlaxsbFatGhRs9b/9NNPlZKSooceekilpaXKysrStGnTtH37dp+HBQAAnc8tvm4wYcIETZgwodnrL1myRP369dPcuXMlSQMHDtQHH3ygefPmKTk5udFt6urqVFdX57lfU1Pj65gAAKCD8DlGfFVcXKykpCSvZcnJycrKympym9zcXM2aNauNJ4OlE4E/sB6hA6m2HgAA2lSbX8DqcrkUFhbmtSwsLEw1NTX6+uuvG90mJydH1dXVnlt5eXlbjwkAAIy0+ZmRlnA6nXI6ndZjAACAm6DNz4yEh4ersrLSa1llZaWCg4PVvXv3tt49AABo59o8RhISElRYWOi1rKCgQAkJCW29awAA0AH4HCPnz59XaWmpSktLJV356G5paalOnTol6cr1HmlpaZ71/+3f/k2ffPKJXnjhBR05ckSLFy/WW2+9pZ/85Cet8woAAECH5nOMlJSUaPjw4Ro+fLgkKTs7W8OHD9fMmTMlSRUVFZ4wkaR+/fppy5YtKigoUGxsrObOnavly5c3+bFeAADQtfh8AWtiYqLcbneTjzf27aqJiYk6ePCgr7sCAABdAL9NAwAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEy1KEYWLVqk6OhoBQYGavTo0dq7d2+T6+bn58vhcHjdAgMDWzwwAADoXHyOkXXr1ik7O1uvvPKKDhw4oNjYWCUnJ6uqqqrJbYKDg1VRUeG5nTx58oaGBgAAnYfPMfLrX/9a06dPV3p6ugYNGqQlS5aoR48eWrlyZZPbOBwOhYeHe25hYWE3NDQAAOg8fIqRS5cuaf/+/UpKSvrHE3TrpqSkJBUXFze53fnz59W3b19FRUVp0qRJOnz48HX3U1dXp5qaGq8bAADonHyKkS+++EL19fXXnNkICwuTy+VqdJuYmBitXLlSmzZt0urVq9XQ0KAxY8bob3/7W5P7yc3NVUhIiOcWFRXly5gAAKADafNP0yQkJCgtLU3Dhg3Tgw8+qHfffVd33HGHli5d2uQ2OTk5qq6u9tzKy8vbekwAAGDkFl9W7t27t/z8/FRZWem1vLKyUuHh4c16Dn9/fw0fPlzHjx9vch2n0ymn0+nLaAAAoIPy6cxIQECA4uLiVFhY6FnW0NCgwsJCJSQkNOs56uvrdejQIUVERPg2KQAA6JR8OjMiSdnZ2ZoyZYpGjhyp+Ph4zZ8/X7W1tUpPT5ckpaWl6c4771Rubq4kafbs2br//vs1YMAAnTt3Tm+88YZOnjypadOmte4rAQAAHZLPMTJ58mSdPn1aM2fOlMvl0rBhw7Rt2zbPRa2nTp1St27/OOFy9uxZTZ8+XS6XS7fddpvi4uK0e/duDRo0qPVeBQAA6LB8jhFJyszMVGZmZqOP7dy50+v+vHnzNG/evJbsBgAAdAH8Ng0AADBFjAAAAFPECAAAMEWMAAAAU8QIAAAw1aJP0wAAmi/6xS3WI3QYJ+akWI8AA5wZAQAApogRAABgihgBAACmiBEAAGCKGAEAAKaIEQAAYIoYAQAApogRAABgihgBAACmiBEAAGCKGAEAAKaIEQAAYIoYAQAApogRAABgihgBAACmiBEAAGCKGAEAAKaIEQAAYIoYAQAApogRAABgihgBAACmiBEAAGDqFusBrEW/uMV6hA7jxJwU6xEAAJ0QZ0YAAIApYgQAAJgiRgAAgCliBAAAmCJGAACAKWIEAACYIkYAAIApYgQAAJgiRgAAgCliBAAAmCJGAACAKWIEAACYIkYAAIApYgQAAJgiRgAAgCliBAAAmCJGAACAKWIEAACYIkYAAICpFsXIokWLFB0drcDAQI0ePVp79+697vrr16/Xvffeq8DAQN13333aunVri4YFAACdj88xsm7dOmVnZ+uVV17RgQMHFBsbq+TkZFVVVTW6/u7du/X0009r6tSpOnjwoFJTU5WamqqysrIbHh4AAHR8PsfIr3/9a02fPl3p6ekaNGiQlixZoh49emjlypWNrr9gwQI9+uijev755zVw4EC99tprGjFihBYuXHjDwwMAgI7vFl9WvnTpkvbv36+cnBzPsm7duikpKUnFxcWNblNcXKzs7GyvZcnJydq4cWOT+6mrq1NdXZ3nfnV1tSSppqbGl3GbpaHuQqs/Z2fVqse/zt16z9XZteJx5//35mvN/9857s3HcbfRFn9f///zut3X/zffpxj54osvVF9fr7CwMK/lYWFhOnLkSKPbuFyuRtd3uVxN7ic3N1ezZs26ZnlUVJQv46KVhcy3nqCLmhNiPUGXxP/vNjjuNtr6uH/11VcKCWn63zKfYuRmycnJ8Tqb0tDQoDNnzuj222+Xw+EwnOzmqKmpUVRUlMrLyxUcHGw9TpfBcbfBcbfBcbfR1Y672+3WV199pcjIyOuu51OM9O7dW35+fqqsrPRaXllZqfDw8Ea3CQ8P92l9SXI6nXI6nV7Levbs6cuonUJwcHCX+J+1veG42+C42+C42+hKx/16Z0Su8ukC1oCAAMXFxamwsNCzrKGhQYWFhUpISGh0m4SEBK/1JamgoKDJ9QEAQNfi89s02dnZmjJlikaOHKn4+HjNnz9ftbW1Sk9PlySlpaXpzjvvVG5uriRpxowZevDBBzV37lylpKRo7dq1Kikp0bJly1r3lQAAgA7J5xiZPHmyTp8+rZkzZ8rlcmnYsGHatm2b5yLVU6dOqVu3f5xwGTNmjNasWaOXX35ZL730ku6++25t3LhRQ4YMab1X0ck4nU698sor17xVhbbFcbfBcbfBcbfBcW+cw/1tn7cBAABoQ/w2DQAAMEWMAAAAU8QIAAAwRYwAAABTxEg7s2jRIkVHRyswMFCjR4/W3r17rUfq9IqKijRx4kRFRkbK4XBc93eT0Dpyc3M1atQoBQUFKTQ0VKmpqTp69Kj1WJ1eXl6ehg4d6vnCrYSEBP3xj3+0HqvLmTNnjhwOh7KysqxHaTeIkXZk3bp1ys7O1iuvvKIDBw4oNjZWycnJqqqqsh6tU6utrVVsbKwWLVpkPUqXsWvXLmVkZGjPnj0qKCjQ5cuX9cgjj6i2ttZ6tE6tT58+mjNnjvbv36+SkhI9/PDDmjRpkg4fPmw9Wpexb98+LV26VEOHDrUepV3ho73tyOjRozVq1CgtXLhQ0pVvt42KitKPf/xjvfjii8bTdQ0Oh0MbNmxQamqq9ShdyunTpxUaGqpdu3bpgQcesB6nS+nVq5feeOMNTZ061XqUTu/8+fMaMWKEFi9erP/8z//UsGHDNH/+fOux2gXOjLQTly5d0v79+5WUlORZ1q1bNyUlJam4uNhwMqDtVVdXS7ryhxE3R319vdauXava2lp+nuMmycjIUEpKite/87iiXf5qb1f0xRdfqL6+3vNNtleFhYXpyJEjRlMBba+hoUFZWVkaO3Ys38x8Exw6dEgJCQm6ePGibr31Vm3YsEGDBg2yHqvTW7t2rQ4cOKB9+/ZZj9IuESMATGVkZKisrEwffPCB9ShdQkxMjEpLS1VdXa23335bU6ZM0a5duwiSNlReXq4ZM2aooKBAgYGB1uO0S8RIO9G7d2/5+fmpsrLSa3llZaXCw8ONpgLaVmZmpjZv3qyioiL16dPHepwuISAgQAMGDJAkxcXFad++fVqwYIGWLl1qPFnntX//flVVVWnEiBGeZfX19SoqKtLChQtVV1cnPz8/wwntcc1IOxEQEKC4uDgVFhZ6ljU0NKiwsJD3c9HpuN1uZWZmasOGDdqxY4f69etnPVKX1dDQoLq6OusxOrVx48bp0KFDKi0t9dxGjhypZ555RqWlpV0+RCTOjLQr2dnZmjJlikaOHKn4+HjNnz9ftbW1Sk9Ptx6tUzt//ryOHz/uuf/pp5+qtLRUvXr10l133WU4WeeVkZGhNWvWaNOmTQoKCpLL5ZIkhYSEqHv37sbTdV45OTmaMGGC7rrrLn311Vdas2aNdu7cqe3bt1uP1qkFBQVdcz3Ud77zHd1+++1cJ/V3xEg7MnnyZJ0+fVozZ86Uy+XSsGHDtG3btmsuakXrKikp0UMPPeS5n52dLUmaMmWK8vPzjabq3PLy8iRJiYmJXstXrVql55577uYP1EVUVVUpLS1NFRUVCgkJ0dChQ7V9+3aNHz/eejR0cXzPCAAAMMU1IwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAMzl5+erZ8+e1mMAMEKMAGiR4uJi+fn5KSUlxaftoqOjNX/+fK9lkydP1v/8z/+04nQAOhJiBECLrFixQj/+8Y9VVFSkzz///Iaeq3v37goNDW2lyQB0NMQIAJ+dP39e69at049+9COlpKRc84OCf/jDHzRq1CgFBgaqd+/eevzxxyVd+WG8kydP6ic/+YkcDoccDoekxt+mycvLU//+/RUQEKCYmBi9+eabXo87HA4tX75cjz/+uHr06KG7775bv//979vsNQNoO8QIAJ+99dZbuvfeexUTE6Nnn31WK1eu1NXf3NyyZYsef/xxPfbYYzp48KAKCwsVHx8vSXr33XfVp08fzZ49WxUVFaqoqGj0+Tds2KAZM2bopz/9qcrKyvSv//qvSk9P15/+9Cev9WbNmqUnn3xSH330kR577DE988wzOnPmTNu+eACtjl/tBeCzsWPH6sknn9SMGTP0zTffKCIiQuvXr1diYqLGjBmjf/qnf9Lq1asb3TY6OlpZWVnKysryLMvPz1dWVpbOnTvnef7Bgwdr2bJlnnWefPJJ1dbWasuWLZKunBl5+eWX9dprr0mSamtrdeutt+qPf/yjHn300bZ54QDaBGdGAPjk6NGj2rt3r55++mlJ0i233KLJkydrxYoVkqTS0lKNGzfuhvbx8ccfa+zYsV7Lxo4dq48//thr2dChQz3//Z3vfEfBwcGqqqq6oX0DuPlusR4AQMeyYsUKffPNN4qMjPQsc7vdcjqdWrhwobp3737TZvH39/e673A41NDQcNP2D6B1cGYEQLN98803+s1vfqO5c+eqtLTUc/vLX/6iyMhI/e53v9PQoUNVWFjY5HMEBASovr7+uvsZOHCgPvzwQ69lH374oQYNGtQqrwNA+8KZEQDNtnnzZp09e1ZTp05VSEiI12Pf//73tWLFCr3xxhsaN26c+vfvr6eeekrffPONtm7dqv/4j/+QdOWakaKiIj311FNyOp3q3bv3Nft5/vnn9eSTT2r48OFKSkrSH/7wB7377rt6//33b8rrBHBzcWYEQLOtWLFCSUlJ14SIdCVGSkpK1KtXL61fv16///3vNWzYMD388MPau3evZ73Zs2frxIkT6t+/v+64445G95OamqoFCxboV7/6lQYPHqylS5dq1apVSkxMbKuXBsAQn6YBAACmODMCAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATBEjAADAFDECAABMESMAAMAUMQIAAEwRIwAAwBQxAgAATP0fmA7k4C6obE8AAAAASUVORK5CYII=",
                        "text/plain": [
                            "<Figure size 640x480 with 1 Axes>"
                        ]
                    },
                    "metadata": {},
                    "output_type": "display_data"
                }
            ],
            "source": [
                "import numpy as np\n",
                "import matplotlib.pyplot as plt\n",
                "\n",
                "A = 5\n",
                "actions = np.arange(A)\n",
                "q = [0.2, 3.0, 1.3, 0.4, 2.6]\n",
                "Gq = np.zeros(A)\n",
                "Gq[np.argmax(q)] = 1.0\n",
                "\n",
                "plt.bar(actions, q, label=\"Q\")\n",
                "plt.bar(actions, Gq, label=r\"$\\mathcal{G}(q)$\")\n",
                "\n",
                "plt.xlabel(\"Action\")\n",
                "plt.legend()"
            ]
        },
        {
            "attachments": {},
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "\n",
                "これは\n",
                "次のように、方策更新と方策評価のそれぞれについてKLやエントロピー正則化が入ったアルゴリズムを見ていきます。\n",
                "\n",
                "* KLとエントロピー正則化のもとでの貪欲方策：$\\mathcal{G}^{\\lambda, \\tau}_{\\mu}(q) = \\argmax_{\\pi} \\langle q, \\pi \\rangle - \\lambda \\mathrm{KL}(\\pi \\| \\mu) + \\tau \\mathcal{H}(\\pi)$\n",
                "* KLとエントロピー正則化のもとでのベルマン期待作用素：$T_{\\pi | \\mu}^{\\lambda, \\tau} q = r + \\gamma P (\\langle \\pi, q\\rangle - \\lambda \\mathrm{KL}(\\pi \\| \\mu) + \\tau \\mathcal{H}(\\pi))$\n",
                "\n",
                "簡単のため、行動空間が有限であり、期待値が厳密に計算できる場合を考えましょう。\n",
                "このとき、KLダイバージェンスやエントロピーは簡単に計算することができます。そのため、ベルマン期待作用素の計算は簡単に計算できます。では、正則化がある場合の貪欲方策はどうでしょうか？$\\argmax$の中にKLやエントロピーが入っているので、一見すると厄介な計算に見えます。\n",
                "\n",
                "実は、凸共役の性質（ルジャンドル変換）を上手く使うと、KLとエントロピーによって正則化された貪欲方策は解析解が求まります。\n",
                "\n",
                "---\n",
                "\n",
                "**ルジャンドル変換とエントロピー正則化**\n",
                "\n"
            ]
        },
        {
            "attachments": {},
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## KLとエントロピーとルジャンドル変換\n",
                "\n",
                "参考\n",
                "* [Leverage the Average: an Analysis of KL Regularization in Reinforcement Learning](https://arxiv.org/abs/2003.14089)\n",
                "\n",
                "表記\n",
                "* $q$についての貪欲方策：$\\mathcal{G}(q) = \\argmax_{\\pi} \\langle q, \\pi \\rangle$\n",
                "* ベルマン期待作用素：$T_\\pi q = r + \\gamma P_{\\pi} q$\n",
                "* KLとエントロピー正則化のもとでの貪欲方策：$\\mathcal{G}^{\\lambda, \\tau}_{\\mu}(q) = \\argmax_{\\pi} \\langle q, \\pi \\rangle - \\lambda \\mathrm{KL}(\\pi \\| \\mu) + \\tau \\mathcal{H}(\\pi)$\n",
                "* KLとエントロピー正則化のもとでのベルマン期待作用素：$T_{\\pi | \\mu}^{\\lambda, \\tau} q = r + \\gamma P (\\langle \\pi, q\\rangle - \\lambda \\mathrm{KL}(\\pi \\| \\mu) + \\tau \\mathcal{H}(\\pi))$\n",
                "\n",
                "---\n",
                "\n",
                "**Approximate Modified Policy Iteration**\n",
                "\n",
                "Approximate Modified Policy Iteration (AMPI) は動的計画法の漸近的な挙動が誤差にどれくらい影響されるかを解析するためのフレームワークです。\n",
                "[Approximate modified policy iteration and its application to the game of tetris](https://mohammadghavamzadeh.github.io/PUBLICATIONS/jmlr-ampi.pdf)などが参考になります。\n",
                "\n",
                "今回は「Q関数の更新にのみ」誤差が乗った形を考えます。方策側にも誤差が乗ると解析が難しくなります。\n",
                "AMPIは次の更新を繰り返します。\n",
                "\n",
                "$$\n",
                "\\begin{cases}\n",
                "\\pi_{k+1} \\in \\mathcal{G}(q_k) \\\\\n",
                "q_{k+1} = (T_{\\pi_{k+1}})^m q_k + \\epsilon_{k+1}\n",
                "\\end{cases}\n",
                "$$\n",
                "\n",
                "* $m=1$のとき：**Approximate Value Iteration**と呼ばれます。\n",
                "* $m=\\infty$のとき：**Approximate Policy Iteration**と呼ばれます。\n",
                "* $\\epsilon_k$はなんらかの近似誤差です。\n",
                "  * 例えばDQNなら１ステップ回帰に伴う誤差になります。\n",
                "  * $m$ステップ回帰を回した場合、$m>1$に相当します。\n",
                "\n",
                "---\n",
                "\n",
                "---\n",
                "\n",
                "**Mirror Descent MPI**\n",
                "\n",
                "TODO: 名前の由来やFrank wolfとの関連\n",
                "AMPIにKLとエントロピー正則化が乗ったアルゴリズムはMirror Descent MPI (MD-MPI) と呼ばれます。\n",
                "\n",
                "MD-MPIは次の更新を繰り返します。\n",
                "\n",
                "$$\n",
                "\\begin{cases}\n",
                "\\pi_{k+1} \\in \\mathcal{G}^{\\lambda, \\tau}_{\\pi_k}(q_k) \\\\\n",
                "q_{k+1} = (T^{\\lambda, \\tau}_{\\pi_{k+1} | \\pi_{k}})^m q_k + \\epsilon_{k+1}\n",
                "\\end{cases}\n",
                "$$\n",
                "\n",
                "\n",
                "---"
            ]
        },
        {
            "attachments": {},
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## 動的計画法での誤差頑健性　"
            ]
        },
        {
            "attachments": {},
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## Tabularでの解析"
            ]
        },
        {
            "attachments": {},
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## Linearの解析"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {},
            "outputs": [],
            "source": []
        }
    ],
    "metadata": {
        "kernelspec": {
            "display_name": "Python 3.9.12 ('shumi-VTLwuKSy-py3.9')",
            "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.9.12"
        },
        "orig_nbformat": 4,
        "vscode": {
            "interpreter": {
                "hash": "d6b7cac5e0d2ff733f340da4d53ae5ecfef7f7ad39623f5982b029a09306b36b"
            }
        }
    },
    "nbformat": 4,
    "nbformat_minor": 2
}