notebooks/RL_LowerBound_statistical_limits.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 強化学習のサンプル効率の下界\n",
    "\n",
    "参考\n",
    "\n",
    "* [Reinforcement Learning: Theory and Algorithms](https://rltheorybook.github.io/)の５章\n",
    "\n",
    "今回は強化学習におけるサンプル効率の下界について見ていきます．\n",
    "特に，\n",
    "\n",
    "* Agnostic Learning：何らかの仮説集合（方策，価値関数，もしくはモデル）に対して、その中から最良な仮説を見つけるために必要なサンプル効率はいくつか？（Agnostic learningでは，仮説集合は別にnon-realizableでも構わない．[これ](https://www.cs.cornell.edu/courses/cs6781/2020sp/lectures/07-agnostic-pac.pdf)など参照．）\n",
    "* Linearly realizable values or policies：$d$-次元の特徴ベクトルが与えられ、最適価値関数が線形に表せる or 最適方策が線形にパラメータ化されているとします。このとき、$d$に依存するが、$S$や$A$に非依存なサンプル効率は達成可能か？\n",
    "\n",
    "一般に，教師あり学習ではこの２つに対してポジティブな回答が存在します．一方で，RLでは上の２つだけでは良いサンプル効率にはなり得ません．"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Agnostic Learning\n",
    "\n",
    "**表記**\n",
    "\n",
    "* 仮説集合：$\\mathcal{H}$\n",
    "    * $f\\in \\mathcal{H}$に対して方策$\\pi_f:\\mathcal{S}\\to\\mathcal{A}$を割り当てる．今回は簡単のために決定的とします．\n",
    "* 方策の集合：$\\Pi=\\left\\{\\pi_f \\mid f \\in \\mathcal{H}\\right\\}$ 例えば以下のケースがあります．\n",
    "    * $\\mathcal{H}$自体が方策の集合\n",
    "    * $\\mathcal{H}$はQ関数の集合で，$\\pi_f$は対応する貪欲方策\n",
    "    * $\\mathcal{H}$はモデルのクラスであり，$\\pi_f$をそのモデルの最適方策\n",
    "* Agnostic Learningの目標：$\\max _{\\pi \\in \\Pi} \\mathbb{E}_{s_0 \\sim \\mu} V^\\pi\\left(s_0\\right)$\n",
    "\n",
    "\n",
    "### 二値分類問題\n",
    "\n",
    "Agnostic learningのサンプル効率を見る前に、二値分類問題（$H=1$, $|\\mathcal{A}|=2$, $\\mathrm{label}(s)=a$のとき$r(s, a)=1$）のサンプル効率で練習してみましょう。\n",
    "\n",
    "表記：\n",
    "* ClassifierのDomain：$\\mathcal{X}$（$\\mathcal{S}$のアナロジー）\n",
    "* $N$個のデータ：$\\left(x_i, y_i\\right)_{i=1}^N$\n",
    "    * $x_i \\in \\mathcal{X}$, $y_i \\in \\{0, 1\\}$\n",
    "* $h \\in \\mathcal{H}: \\mathcal{X} \\rightarrow\\{0,1\\}$\n",
    "* $\\widehat{h}=\\arg \\min _{h \\in \\mathcal{H}} \\widehat{\\operatorname{err}}(h)$\n",
    "\n",
    "次の経験損失と真の損失を考えます。\n",
    "$$\\widehat{\\operatorname{err}}(h)=\\frac{1}{N} \\sum_{i=1}^N \\mathbf{1}\\left(h\\left(x_i\\right) \\neq y_i\\right), \\quad \\operatorname{err}(h)=\\mathbb{E}_{(X, Y) \\sim D} \\mathbf{1}(h(X) \\neq Y)$$\n",
    "\n",
    "これに対して、Hoeffdingの不等式を使えば\n",
    "$$\n",
    "|\\operatorname{err}(h)-\\widehat{\\operatorname{err}}(h)| \\leq \\sqrt{\\frac{1}{2 N} \\log \\frac{2}{\\delta}}\n",
    "$$\n",
    "\n",
    "が確率$1-\\delta$以上で成立します。Union Boundを使えば、次の「オッカムの剃刀」バウンドが簡単に導出されます：\n",
    "\n",
    "---\n",
    "\n",
    "**オッカムの剃刀**\n",
    "\n",
    "$\\mathcal{H}$が有限のとき、\n",
    "\n",
    "$$\n",
    "\\operatorname{err}(\\widehat{h}) \\leq \\min _{h \\in \\mathcal{H}} \\operatorname{err}(h)+\\sqrt{\\frac{2}{N} \\log \\frac{2|\\mathcal{H}|}{\\delta}}\n",
    "$$\n",
    "\n",
    "とくに、$N \\geq \\frac{2 \\log \\frac{2|\\mathcal{H}|}{\\delta}}{\\epsilon^2}$ならば、\n",
    "\n",
    "$$\\operatorname{err}(\\widehat{h}) \\leq \\min _{h \\in \\mathcal{H}} \\operatorname{err}(h)+\\epsilon$$\n",
    "\n",
    "が成り立つ。よく見ると、これは入力のサイズ$\\mathcal{X}$に依存していないことがわかります。\n",
    "\n",
    "**オッカムの剃刀について**：オッカムの剃刀は，「ある２つの理論が同程度にデータを説明できているとき，より単純な方が好まれる」という原則です．上のバウンドから，「経験誤差が同程度に小さいモデルがあるなら，よりモデルサイズが小さいほうが期待誤差が小さくなる」ことを示しています．これはオッカムの剃刀そのものです．\n",
    "\n",
    "---\n",
    "\n",
    "### 強化学習におけるオッカムの剃刀\n",
    "\n",
    "さて，強化学習の話に戻りましょう。ランダムな方策（$\\text {Unif }_\\mathcal{A}$）を実行して$N$個の軌跡を収集したとします（教師あり学習では一様なデータを拾ってきたので，そのアナロジーとして一様方策でデータを集めた時を考えましょう）。\n",
    "また、$\\pi$を決定的な方策とします。このとき、　\n",
    "\n",
    "$$\n",
    "V_0^\\pi(\\mu)=|\\mathcal{A}|^H \\cdot \\mathbb{E}_{\\tau \\sim \\operatorname{Pr}_{\\text {Unif }_\\mathcal{A}}}\\left[\\mathbf{1}\\left(\\pi\\left(s_0\\right)=a_0, \\ldots, \\pi\\left(s_{H-1}\\right)=a_{H-1}\\right) \\sum_{h=0}^{H-1} r\\left(s_h, a_h\\right)\\right]\n",
    "$$\n",
    "\n",
    "が成り立ちます。ここで、$\\operatorname{Pr}_{\\text {Unif }_\\mathcal{A}}$は$\\text {Unif }_\\mathcal{A}$における$\\tau=\\left(s_0, a_0, r_0, \\ldots s_{H-1}, a_{H-1}, r_{H-1}\\right)$の分布です。\n",
    "証明は簡単です。\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "V_0^\\pi(\\mu) & =\\mathbb{E}_{\\tau \\sim \\operatorname{Pr}_\\pi}\\left[\\sum_{h=0}^{H-1} r_h\\right] \\\\\n",
    "& =\\mathbb{E}_{\\tau \\sim \\operatorname{Pr}_{\\mathrm{Unif}_{\\mathcal{A}}}}\\left[\\frac{\\operatorname{Pr}_\\pi(\\tau)}{\\operatorname{Pr}_{\\mathrm{Unif}_{\\mathcal{A}}}(\\tau)} \\sum_{h=0}^{H-1} r_h\\right] \\\\\n",
    "& =|\\mathcal{A}|^H \\cdot \\mathbb{E}_{\\tau \\sim \\operatorname{Pr}_{\\mathrm{Unif}_{\\mathcal{A}}}}\\left[\\mathbf{1}\\left(\\pi\\left(s_0\\right)=a_0, \\ldots, \\pi\\left(s_{H-1}\\right)=a_{H-1}\\right) \\sum_{h=0}^{H-1} r_h\\right]\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "ここで、最後の等式は$\\text {Unif }_\\mathcal{A}$が一様であることを利用しています。\n",
    "この等式はつまり、ランダムな方策があれば任意の方策の価値を普遍推定できることを表しています。そこで、$N$個の軌跡を使って次のように方策の価値を推定した時を考えてみましょう：\n",
    "\n",
    "$$\n",
    "\\widehat{V}_0^\\pi(\\mu)=\\frac{|\\mathcal{A}|^H}{N} \\sum_{n=1}^N \\mathbf{1}\\left(\\pi\\left(s_0^n\\right)=a_0^n, \\ldots \\pi\\left(s_{H-1}^n\\right)=a_{H-1}^n\\right) \\sum_{t=0}^{H-1} r\\left(s_t^n, a_t^n\\right)\n",
    "$$\n",
    "ここで、$\\left(s_0^n, a_0^n, r_1^n, s_1^n, \\ldots, s_{H-1}^n, a_{H-1}^n, r_{H-1}^n\\right)$は$n$番目の軌跡です。\n",
    "これに対して、次のバウンドが成立します：\n",
    "\n",
    "---\n",
    "\n",
    "**オッカムの剃刀（強化学習版）**\n",
    "\n",
    "$\\widehat{\\pi}=\\arg \\max _{\\pi \\in \\Pi} \\widehat{V}_0^\\pi(\\mu)$とします。このとき、確率$1-\\delta$以上で\n",
    "\n",
    "$$\n",
    "V_0^{\\widehat{\\pi}}(\\mu) \\geq \\max _{\\pi \\in \\Pi} V_0^\\pi(\\mu)-H|\\mathcal{A}|^H \\sqrt{\\frac{2}{N} \\log \\frac{2|\\Pi|}{\\delta}} .\n",
    "$$\n",
    "\n",
    "が成立します。証明は簡単です。まず、$|\\mathcal{A}|^H \\mathbf{1}\\left(\\pi\\left(s_0^n\\right)=a_0^n, \\ldots \\pi\\left(s_{H-1}^n\\right)=a_{H-1}^n\\right) \\sum_{t=0}^{H-1} r\\left(s_t^n, a_t^n\\right)$が$H|\\mathcal{A}^H$でバウンドされることに注意します。\n",
    "後はオッカムの剃刀の証明と同じです。\n",
    "\n",
    "また、$N \\geq H|\\mathcal{A}|^H \\frac{2 \\log (2|\\Pi| / \\delta)}{\\epsilon^2}$のとき、確率$1-\\delta$以上で$V_0^{\\widehat{\\pi}}\\left(s_0\\right) \\geq \\max _{\\pi \\in \\Pi} V_0^\\pi\\left(s_0\\right)-\\epsilon$が成立します。\n",
    "\n",
    "---\n",
    "\n",
    "ここから何がわかるでしょうか？Agnostic learningでは状態数に非依存なサンプル効率で学習ができますが、そのサンプル効率はホライゾンに指数的に依存していることがわかります。後で見ますが、これは更に仮定を置かなければ回避できません。\n",
    "\n",
    "\n",
    "TODO: 今までは$\\mathcal{H}$が有限の場合のみ対応していましたが、無限の場合でもVC次元を使えば対処できます。\n",
    "\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## サンプル効率の下界\n",
    "\n",
    "上のオッカムの剃刀で見たような$O(\\log |\\Pi|)$に依存したサンプル効率は、実はこれ以上の仮定を置かなければ、ホライゾンに指数依存であることは回避できません。これを見てみましょう。\n",
    "\n",
    "---\n",
    "\n",
    "**Agnostic Learningの下界（Generative Modelあり）**\n",
    "\n",
    "アルゴリズム$A$はgenerative modelを使って良いとします。また、$\\Pi$を$|\\Pi|=|\\mathcal{A}|^H$なる方策の集合とします。アルゴリズム$A$が次を満たすような方策を確率$1-\\delta$以上で返すとします（この$\\pi$は$\\Pi$になくても構いません）：\n",
    "\n",
    "$$\n",
    "V_0^\\pi(\\mu) \\geq \\max _{\\pi \\in \\Pi} V_0^\\pi(\\mu)-0.5\n",
    "$$\n",
    "\n",
    "このとき、$A$はこれを達成するために、最低$N \\geq c|\\mathcal{A}|^H$回はgenerative modelにクエリを投げる必要があるような$\\Pi$が存在します。\n",
    "\n",
    "これを満たすような$\\Pi$を構築してみましょう。\n",
    "$|\\mathcal{A}|$分岐なバランス木を考えます（状態数$|\\mathcal{A}|^H$かつ行動数$|\\mathcal{A}|$です）。\n",
    "また、方策のクラスとして、すべての$|\\mathcal{A}|^H$個の方策を考えます。\n",
    "また、報酬はどこかのリーフノードに単一で割り当てられているとします。\n",
    "\n",
    "このとき、$\\mathcal{A}^H$の中から当たりの方策を一つを見つけ出さない限り報酬の情報が得られないので、$|\\mathcal{A}|^H$のサンプル効率がかかることがすぐわかります。\n",
    "\n",
    "---\n",
    "\n",
    "このようなMDPの図を下に描画しておきます。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: G Pages: 1 -->\n",
       "<svg width=\"495pt\" height=\"402pt\"\n",
       " viewBox=\"0.00 0.00 495.00 402.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 398)\">\n",
       "<title>G</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-398 491,-398 491,4 -4,4\"/>\n",
       "<g id=\"clust1\" class=\"cluster\">\n",
       "<title>cluster_1</title>\n",
       "<polygon fill=\"none\" stroke=\"blue\" points=\"261,-311 261,-386 345,-386 345,-311 261,-311\"/>\n",
       "<text text-anchor=\"middle\" x=\"303\" y=\"-370.8\" font-family=\"Times,serif\" font-size=\"14.00\">h=1</text>\n",
       "</g>\n",
       "<g id=\"clust2\" class=\"cluster\">\n",
       "<title>cluster_2</title>\n",
       "<polygon fill=\"none\" stroke=\"blue\" points=\"131,-203 131,-278 479,-278 479,-203 131,-203\"/>\n",
       "<text text-anchor=\"middle\" x=\"305\" y=\"-262.8\" font-family=\"Times,serif\" font-size=\"14.00\">h=2</text>\n",
       "</g>\n",
       "<g id=\"clust3\" class=\"cluster\">\n",
       "<title>cluster_H</title>\n",
       "<polygon fill=\"none\" stroke=\"blue\" points=\"8,-8 8,-83 371,-83 371,-8 8,-8\"/>\n",
       "<text text-anchor=\"middle\" x=\"189.5\" y=\"-67.8\" font-family=\"Times,serif\" font-size=\"14.00\">h=H</text>\n",
       "</g>\n",
       "<!-- s(1, 1) -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>s(1, 1)</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"303\" cy=\"-337\" rx=\"33.6\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"303\" y=\"-333.3\" font-family=\"Times,serif\" font-size=\"14.00\">s(1, 1)</text>\n",
       "</g>\n",
       "<!-- s(2, 1) -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>s(2, 1)</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"173\" cy=\"-229\" rx=\"33.6\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"173\" y=\"-225.3\" font-family=\"Times,serif\" font-size=\"14.00\">s(2, 1)</text>\n",
       "</g>\n",
       "<!-- s(1, 1)&#45;&gt;s(2, 1) -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>s(1, 1)&#45;&gt;s(2, 1)</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M280.82,-323.36C262.56,-312.46 236.44,-295.72 216,-278 207.63,-270.75 199.3,-261.92 192.24,-253.83\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"194.78,-251.42 185.64,-246.07 189.45,-255.95 194.78,-251.42\"/>\n",
       "<text text-anchor=\"middle\" x=\"252.5\" y=\"-289.8\" font-family=\"Times,serif\" font-size=\"14.00\">a1</text>\n",
       "</g>\n",
       "<!-- s(2, 2) -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>s(2, 2)</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"259\" cy=\"-229\" rx=\"33.6\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"259\" y=\"-225.3\" font-family=\"Times,serif\" font-size=\"14.00\">s(2, 2)</text>\n",
       "</g>\n",
       "<!-- s(1, 1)&#45;&gt;s(2, 2) -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>s(1, 1)&#45;&gt;s(2, 2)</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M295.93,-318.97C288.86,-301.95 277.91,-275.55 269.76,-255.93\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"272.97,-254.53 265.91,-246.64 266.51,-257.22 272.97,-254.53\"/>\n",
       "<text text-anchor=\"middle\" x=\"293.5\" y=\"-289.8\" font-family=\"Times,serif\" font-size=\"14.00\">a2</text>\n",
       "</g>\n",
       "<!-- s(2, ...) -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>s(2, ...)</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"347\" cy=\"-229\" rx=\"36.29\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"347\" y=\"-225.3\" font-family=\"Times,serif\" font-size=\"14.00\">s(2, ...)</text>\n",
       "</g>\n",
       "<!-- s(1, 1)&#45;&gt;s(2, ...) -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>s(1, 1)&#45;&gt;s(2, ...)</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M310.07,-318.97C317.09,-302.05 327.96,-275.86 336.09,-256.28\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"339.35,-257.57 339.95,-246.99 332.88,-254.88 339.35,-257.57\"/>\n",
       "<text text-anchor=\"middle\" x=\"329\" y=\"-289.8\" font-family=\"Times,serif\" font-size=\"14.00\">...</text>\n",
       "</g>\n",
       "<!-- s(2, A) -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>s(2, A)</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"436\" cy=\"-229\" rx=\"35.19\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"436\" y=\"-225.3\" font-family=\"Times,serif\" font-size=\"14.00\">s(2, A)</text>\n",
       "</g>\n",
       "<!-- s(1, 1)&#45;&gt;s(2, A) -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>s(1, 1)&#45;&gt;s(2, A)</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M325.66,-323.39C344.33,-312.5 371.04,-295.77 392,-278 400.54,-270.76 409.05,-261.94 416.28,-253.85\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"419.12,-255.92 423.04,-246.08 413.84,-251.33 419.12,-255.92\"/>\n",
       "<text text-anchor=\"middle\" x=\"388\" y=\"-289.8\" font-family=\"Times,serif\" font-size=\"14.00\">aA</text>\n",
       "</g>\n",
       "<!-- s(H&#45;1, 1) -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>s(H&#45;1, 1)</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"173\" cy=\"-142\" rx=\"42.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"173\" y=\"-138.3\" font-family=\"Times,serif\" font-size=\"14.00\">s(H&#45;1, 1)</text>\n",
       "</g>\n",
       "<!-- s(2, 1)&#45;&gt;s(H&#45;1, 1) -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>s(2, 1)&#45;&gt;s(H&#45;1, 1)</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M173,-210.8C173,-199.16 173,-183.55 173,-170.24\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"176.5,-170.18 173,-160.18 169.5,-170.18 176.5,-170.18\"/>\n",
       "<text text-anchor=\"middle\" x=\"179\" y=\"-181.8\" font-family=\"Times,serif\" font-size=\"14.00\">...</text>\n",
       "</g>\n",
       "<!-- s(H, 1) -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>s(H, 1)</title>\n",
       "<ellipse fill=\"lightgreen\" stroke=\"lightgreen\" cx=\"52\" cy=\"-34\" rx=\"36\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"52\" y=\"-30.3\" font-family=\"Times,serif\" font-size=\"14.00\">s(H, 1)</text>\n",
       "</g>\n",
       "<!-- s(H&#45;1, 1)&#45;&gt;s(H, 1) -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>s(H&#45;1, 1)&#45;&gt;s(H, 1)</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M151.26,-126.24C135.36,-115.07 113.59,-98.98 96,-83 87.71,-75.48 79.26,-66.59 72,-58.53\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"74.43,-56 65.19,-50.81 69.19,-60.63 74.43,-56\"/>\n",
       "<text text-anchor=\"middle\" x=\"129.5\" y=\"-94.8\" font-family=\"Times,serif\" font-size=\"14.00\">a1</text>\n",
       "</g>\n",
       "<!-- s(H, 2) -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>s(H, 2)</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"141\" cy=\"-34\" rx=\"36\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"141\" y=\"-30.3\" font-family=\"Times,serif\" font-size=\"14.00\">s(H, 2)</text>\n",
       "</g>\n",
       "<!-- s(H&#45;1, 1)&#45;&gt;s(H, 2) -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>s(H&#45;1, 1)&#45;&gt;s(H, 2)</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M167.86,-123.97C162.8,-107.2 154.99,-81.34 149.09,-61.81\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"152.37,-60.55 146.13,-51.99 145.67,-62.57 152.37,-60.55\"/>\n",
       "<text text-anchor=\"middle\" x=\"168.5\" y=\"-94.8\" font-family=\"Times,serif\" font-size=\"14.00\">a2</text>\n",
       "</g>\n",
       "<!-- s(H, ...) -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>s(H, ...)</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"233\" cy=\"-34\" rx=\"38.19\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"233\" y=\"-30.3\" font-family=\"Times,serif\" font-size=\"14.00\">s(H, ...)</text>\n",
       "</g>\n",
       "<!-- s(H&#45;1, 1)&#45;&gt;s(H, ...) -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>s(H&#45;1, 1)&#45;&gt;s(H, ...)</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M182.64,-123.97C192.36,-106.79 207.49,-80.07 218.63,-60.39\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"221.7,-62.07 223.58,-51.64 215.61,-58.62 221.7,-62.07\"/>\n",
       "<text text-anchor=\"middle\" x=\"208\" y=\"-94.8\" font-family=\"Times,serif\" font-size=\"14.00\">...</text>\n",
       "</g>\n",
       "<!-- s(H, A) -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>s(H, A)</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"326\" cy=\"-34\" rx=\"37.09\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"326\" y=\"-30.3\" font-family=\"Times,serif\" font-size=\"14.00\">s(H, A)</text>\n",
       "</g>\n",
       "<!-- s(H&#45;1, 1)&#45;&gt;s(H, A) -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>s(H&#45;1, 1)&#45;&gt;s(H, A)</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M201.7,-128.44C224.12,-117.95 255.47,-101.71 280,-83 289.32,-75.89 298.48,-66.87 306.15,-58.57\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"308.93,-60.71 312.99,-50.92 303.72,-56.04 308.93,-60.71\"/>\n",
       "<text text-anchor=\"middle\" x=\"274\" y=\"-94.8\" font-family=\"Times,serif\" font-size=\"14.00\">aA</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7f6e806bec40>"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Digraph\n",
    "\n",
    "g = Digraph('G')\n",
    "\n",
    "# h=1\n",
    "with g.subgraph(name='cluster_1') as c:\n",
    "    c.attr(color='blue')\n",
    "    c.node('s(1, 1)')\n",
    "    c.attr(label='h=1')\n",
    "\n",
    "# h=2\n",
    "with g.subgraph(name='cluster_2') as c:\n",
    "    c.attr(color='blue')\n",
    "    c.node('s(2, 1)')\n",
    "    c.node('s(2, 2)')\n",
    "    c.node('s(2, ...)')\n",
    "    c.node('s(2, A)')\n",
    "    c.attr(label='h=2')\n",
    "\n",
    "g.node('s(1, 1)')\n",
    "g.edge(\"s(1, 1)\", \"s(2, 1)\",label=\"a1\")\n",
    "g.edge(\"s(1, 1)\", \"s(2, 2)\",label=\"a2\")\n",
    "g.edge(\"s(1, 1)\", \"s(2, ...)\",label=\"...\")\n",
    "g.edge(\"s(1, 1)\", \"s(2, A)\",label=\"aA\")\n",
    "\n",
    "g.edge(\"s(2, 1)\", \"s(H-1, 1)\", label=\"...\")\n",
    "\n",
    "# h=H\n",
    "with g.subgraph(name='cluster_H') as c:\n",
    "    c.attr(color='blue')\n",
    "    c.node('s(H, 1)')\n",
    "    c.node('s(H, 2)')\n",
    "    c.node('s(H, ...)')\n",
    "    c.node('s(H, A)')\n",
    "    c.attr(label='h=H')\n",
    "\n",
    "g.node(\"s(H, 1)\", style=\"filled\", color=\"lightgreen\")\n",
    "g.edge(\"s(H-1, 1)\", \"s(H, 1)\",label=\"a1\")\n",
    "g.edge(\"s(H-1, 1)\", \"s(H, 2)\",label=\"a2\")\n",
    "g.edge(\"s(H-1, 1)\", \"s(H, ...)\",label=\"...\")\n",
    "g.edge(\"s(H-1, 1)\", \"s(H, A)\",label=\"aA\")\n",
    "\n",
    "g"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $Q^\\pi$-Linear Realizability\n",
    "\n",
    "さっきの仮定だけでは$H$に対して指数的なサンプル効率がかかってしまいました。次からより強い仮定を考えてみましょう。\n",
    "まずは$Q^\\pi$が線形近似可能である状況を考えてみます。実は、これから見るように、$Q^\\pi$の線形近似可能性だけでは多項式サンプル効率は達成できません．\n",
    "\n",
    "以下ではoffline policy evaluationの設定を考えます。\n",
    "\n",
    "* ステップ$h$でのデータの分布：$\\left\\{\\mu_h\\right\\}_{h=0}^{H-1}$\n",
    "    * $\\mu_h \\in \\Delta\\left(\\mathcal{S}_h \\times \\mathcal{A}\\right)$ \n",
    "* エージェントに与えられるデータセット：$\\left\\{D_h\\right\\}_{h=0}^{H-1}$\n",
    "    * $D_h$は独立したサンプルで構築される: $\\left(s, a, r, s^{\\prime}\\right) \\in\\mathcal{S}_h \\times \\mathcal{A} \\times \\mathbb{R} \\times \\mathcal{S}_{h+1}$\n",
    "    * $(s, a) \\sim \\mu_h, r \\sim r(s, a), s^{\\prime} \\sim P(s, a)$\n",
    "    * エージェントは$\\left\\{D_h\\right\\}_{h=0}^{H-1}$を使って$V^\\pi$を近似するのが目標\n",
    "* 方策：$\\pi: \\mathcal{S} \\rightarrow \\Delta(\\mathcal{A})$\n",
    "* 特徴ベクトル：$\\phi: \\mathcal{S} \\times \\mathcal{A} \\rightarrow \\mathbb{R}^d$\n",
    "\n",
    "また、次の仮定を考えます：\n",
    "\n",
    "---\n",
    "\n",
    "**仮定：$Q^\\pi$の線形実現可能性**\n",
    "\n",
    "任意の方策$\\pi$について、次を満たす$\\theta_0^\\pi, \\ldots \\theta_{H-1}^\\pi \\in \\mathbb{R}^d$が存在する：\n",
    "\n",
    "$$Q_h^\\pi(s, a)=\\left(\\theta_h^\\pi\\right)^{\\top} \\phi(s, a)$$\n",
    "\n",
    "この仮定は**全ての**方策が線形に実現可能という点で、結構強い仮定であることに注意しましょう。\n",
    "\n",
    "---\n",
    "\n",
    "---\n",
    "\n",
    "**仮定：Coverage**\n",
    "\n",
    "任意の$(s, a)$について、$\\|\\phi(s, a)\\|_2 \\leq 1$とします。また、任意の$h\\in [H]$について、$\\mu$は次を満たすとします：\n",
    "\n",
    "$$\\mathbb{E}_{(s, a) \\sim \\mu_h}\\left[\\phi(s, a) \\phi(s, a)^{\\top}\\right]=\\frac{1}{d} I$$\n",
    "\n",
    "これはデータの分布$\\mu_h$がD-optimal designであるという仮定と等価であることに注意しましょう。\n",
    "また、対角行列の成分は固有値なので、この行列の最小の固有値は$1/d$です。\n",
    "さらに、任意のデータ分布$\\widetilde{\\mu}_h$についての最小の固有値の最大値は$1/d$になります（$\\|\\phi(s, a)\\|_2 \\leq 1$なので$\\sigma_{\\min }\\left(\\mathbb{E}_{(s, a) \\sim \\widetilde{\\mu}_h}\\left[\\phi(s, a) \\phi(s, a)^{\\top}\\right]\\right)$が成り立つためです）。\n",
    "\n",
    "---\n",
    "\n",
    "Coverageの仮定と線形実現性の仮定から、通常の最小二乗法で$Q_h^\\pi$が良く近似できることが保証されています。しかし、実はこの仮定だけでは強化学習は効率よく解けません。\n",
    "\n",
    "---\n",
    "\n",
    "**定理： Exponential Lower Bound**\n",
    "\n",
    "仮定：Coverageが成り立っているとします。また、方策と特徴ベクトルを入力として受けるアルゴリズムを考えます。\n",
    "このとき、どんなアルゴリズムに対しても、次を満たすような実現可能性の仮定を満たすMDPが存在します。\n",
    "\n",
    "「どんな方策$\\pi: \\mathcal{S} \\rightarrow \\Delta(\\mathcal{A})$に対しても、確率$0.9$以上で$\\pi$の価値を定数誤差で吐き出すために$\\Omega\\left((d / 2)^H\\right)$のサンプルが必要になる。」\n",
    "\n",
    "---\n",
    "\n",
    "これは方策評価についての話ですが、簡単な例によって一般のOffline RLが最適方策を近似する場合についても成り立つことがわかります。\n",
    "例えば、初期状態で行動$a_1$を選択し、報酬$0.5$を受け取って終了するとします。\n",
    "一方、$a_2$を選択するとムズMDPに遷移するとします。\n",
    "このとき、準最適性が$0.5$以下になるような方策を獲得するには、ムズMDPの方策を$0.5$以下の精度で評価しなければなりません。\n",
    "よって、方策評価がちゃんとできないと最適方策もわかりません。\n",
    "\n",
    "このムズMDPを構築してみましょう。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ムズMDPの構築\n",
    "\n",
    "**基本的な制作方針**：最後の層で生じる非常に小さい報酬の誤差が，層が戻るに従って増大されるようなMDPを作ろう！\n",
    "\n",
    "* $\\hat{d}=d/2$\n",
    "* 行動集合：$\\mathcal{A}=\\left\\{a_1, a_2\\right\\}$\n",
    "* $h$での状態集合（$\\hat{d}+1$個）：$s_h^1, s_h^2, \\ldots, s_h^{\\hat{d}}$ and $s_h^{\\hat{d}+1}$\n",
    "* 遷移確率：任意の$h \\in\\{0,1, \\ldots, H-2\\}$と$c \\in\\{1,2, \\ldots, \\hat{d}+1\\}$について、\n",
    "$$\n",
    "P\\left(s \\mid s_h^c, a\\right)= \\begin{cases}1 & s=s_{h+1}^{\\hat{d}+1}, a=a_1 \\\\ 1 & s=s_{h+1}^c, a=a_2 \\\\ 0 & \\text { else }\\end{cases}\n",
    "$$\n",
    "\n",
    "* 報酬の分布：\n",
    "    * $0\\leq r_\\infty\\leq \\hat{d}^{-H / 2}$を後で決めるパラメータとします。\n",
    "    * 最終層以前：それぞれの$(h, c) \\in \\{0,1, \\ldots, H-2\\} \\times [\\hat{d}]$と$a\\in \\mathcal{A}$について、\n",
    "        * $r(s_h^c, a)=0$\n",
    "        * $r(s_h^{\\hat{d}+1}, a)=r_\\infty \\cdot (\\hat{d}^{1/2}-1) \\cdot \\hat{d}^{(H-h-1)/2}$\n",
    "    * 最終層：それぞれの$c \\in [\\hat{d}]$と$a\\in \\mathcal{A}$について、\n",
    "        $$\n",
    "        r(s_{H-1}^c, a)=\\begin{cases}1 & \\text{ with probability } (1 + r_\\infty) / 2\\\\ -1 & \\text{ with probability } (1 - r_\\infty) / 2\\end{cases}\n",
    "        $$\n",
    "\n",
    "* 特徴ベクトル：\n",
    "    * $e_1, e_2, \\dots e_d$を$\\mathbb{R}^d$上の基底ベクトルとする。\n",
    "    * それぞれの$(h, c) \\in [H] \\times [\\hat{d}]$と$a\\in \\mathcal{A}$について、$\\phi(s_h^c, a_1)=e_c$, $\\phi(s_h^c, a_2)=e_{c+\\hat{d}}$とする。\n",
    "    * また、任意の$a\\in \\mathcal{A}$と$h\\in [H]$に対して次を設定します\n",
    "    $$\\phi(s_h^{\\hat{d}+1}, a)=\\frac{1}{\\hat{d}^{1/2}}\\sum_{c\\in \\hat{d}}e_c$$\n",
    "\n",
    "このようなMDPの構築は実際に$Q^\\pi$の実現性の仮定を満たしています。(TODO: 証明)\n",
    "\n",
    "* データの分布：\n",
    "    * それぞれの$h\\in [H]$でデータの分布$\\mu_h$は$\\{(s_h^1, a_1), (s_h^1, a_2), (s_h^2, a_1), (s_h^2, a_2), \\dots, (s_h^{\\hat{d}}, a_1), (s_h^{\\hat{d}}, a_2)\\}$の一様分布とします。\n",
    "    * $(s_h^{\\hat{d}+1}, a)$は$\\mu_h$のサポートではないことに注意しましょう。\n",
    "    * 次が成り立ちます：$\\mathbb{E}_{(s, a) \\sim \\mu_h}[\\phi(s, a)\\phi(s, a)^T]=\\frac{1}{d}\\sum^d_{c=1}e_c e_c^T=\\frac{1}{d}I$\n",
    "\n",
    "### Lower boundの証明\n",
    "\n",
    "このMDPでの挙動はハイパーパラメータ$r_\\infty$で決まります。特に、この値が$r_\\infty=0$と$r_\\infty = \\hat{d}^{-H/2}$のときを考えてみましょう。\n",
    "また、初期状態は$s_0^{\\hat{d}+1}$で固定します。\n",
    "このとき、価値関数については次が成り立ちます：\n",
    "* $r_\\infty=0$のとき：任意の方策の価値は$0$\n",
    "* $r_\\infty = \\hat{d}^{-H/2}$のとき：$r_\\infty \\cdot \\hat{d}^{H/2}=1$\n",
    "\n",
    "すこし上でも説明しましたが、最適方策を正しく得るためには方策評価を正しく行わなければいけません。\n",
    "よって、上のムズMDPが与えられたときに、$r_\\infty=0$のときと、$r_\\infty= \\hat{d}^{-H/2}$のときを高速で判別しなければ、正しく方策評価が行なえません。\n",
    "\n",
    "この２つのMDPは遷移確率やデータの分布、特徴ベクトルが全く同じです。よって、2つのMDPを見分ける唯一の方法は、報酬関数の分布をデータの分布$\\{\\mu_h\\}_{h=0}^{H-1}$からのサンプルを使った推定です。\n",
    "\n",
    "さて、最初の$H-1$層におけるデータの分布では、全ての$(s, a)$において報酬の分布は全く同じです（$s\\in S_h \\setminus \\{s_h^{\\hat{d}+1}\\}$と$a\\in \\mathcal{A}$について、$r(s, a)=0$のせいです）。\n",
    "最終層の報酬関数を思い出すと、最終層での報酬の分布は\n",
    "$$\n",
    "r(s, a)=\\begin{cases}1 & \\text{ with probability } (1 + r_\\infty) / 2\\\\ -1 & \\text{ with probability } (1 - r_\\infty) / 2\\end{cases}\n",
    "$$\n",
    "であることがわかります。よって、2つのMDPを見分けるためは、次の２つの報酬関数の分布を見分ける必要があります。\n",
    "$$\n",
    "r^{(1)}(s, a)=\\begin{cases}1 & \\text{ with probability } 1 / 2\\\\ -1 & \\text{ with probability } 1 / 2\\end{cases}\n",
    "$$\n",
    "$$\n",
    "r^{(2)}(s, a)=\\begin{cases}1 & \\text{ with probability } (1 + \\hat{d}^{-H/2}) / 2\\\\ -1 & \\text{ with probability } (1 - \\hat{d}^{-H/2}) / 2\\end{cases}\n",
    "$$\n",
    "\n",
    "つまり、確率0.9以上で(1) 期待値=0と(2)期待値=$\\hat{d}^{-H/2}$を見分けたいわけですね。\n",
    "これはどれくらいのサンプルが必要になるでしょうか？期待値を$\\frac{1}{N}\\sum^N r_i$で近似することを考え、Hoeffdingを思い出すと、この判別には$\\mathcal{O}(\\hat{d}^H)$のサンプルが必要であることがすぐにわかります。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear $Q^*$ realizability\n",
    "\n",
    "上の例では，$Q^\\pi$だけでは無理なことがわかりました．\n",
    "他の仮定を導入すると何か言えるでしょうか？\n",
    "そのために，次の２つの仮定について考えてみます．\n",
    "\n",
    "---\n",
    "\n",
    "**Linear $Q^*$-realizability**\n",
    "\n",
    "次が成立していると仮定します．\n",
    "$$\n",
    "Q_h^*(s, a)=\\theta_h^* \\cdot \\phi(s, a)\n",
    "$$\n",
    "\n",
    "---\n",
    "\n",
    "**Constant sub-optimality gap**\n",
    "\n",
    "Action gapが大きいことを仮定します．つまり，\n",
    "$$\n",
    "\\Delta_h(s, a):=V_h^*(s)-Q_h^*(s, a)\n",
    "$$\n",
    "として，\n",
    "$$\n",
    "\\min _{h \\in[H], s \\in \\mathcal{S}, a \\in \\mathcal{A}}\\left\\{\\Delta_h(s, a): \\Delta_h(s, a)>0\\right\\} \\geq \\Delta_{\\min }\n",
    "$$\n",
    "を仮定します．（この仮定は最適方策を見つけやすくします）\n",
    "\n",
    "---\n",
    "\n",
    "さて，この仮定に対して，次が成立します：\n",
    "\n",
    "1. **Linear $Q^*$-realizability** + **Generative model**では，exponentialな下界になる\n",
    "2. **Linear $Q^*$-realizability** + **Constant Sub-optimality gap**では，exponentialな下界になる\n",
    "3. **Linear $Q^*$-realizability** + **Generative model** + **Constant Sub-optimality gap**の場合，多項式サンプル効率で解ける．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear $\\pi^*$ realizability\n",
    "\n",
    "最後に，最適方策が線形に表現可能である場合を考えましょう．\n",
    "\n",
    "---\n",
    "\n",
    "**Linear $\\pi^*$ realizability**\n",
    "\n",
    "$$\n",
    "\\pi^*(s) \\in \\operatorname{argmax}_a\\left\\langle\\theta_h, \\phi(s, a)\\right\\rangle\n",
    "$$\n",
    "\n",
    "---\n",
    "\n",
    "また，上でやったようなConstant gapと同様の仮定を考えます．\n",
    "\n",
    "---\n",
    "\n",
    "次を仮定します．\n",
    "\n",
    "$$\n",
    "\\left\\langle\\theta_h, \\phi\\left(s, \\pi^*(s)\\right)\\right\\rangle-\\left\\langle\\theta_h, \\phi(s, a)\\right\\rangle \\geq \\Delta_{\\min }\n",
    "$$\n",
    "\n",
    "---\n",
    "\n",
    "このとき，次が成立します．\n",
    "\n",
    "* **Linear $\\pi^*$ realizability**とConstant gapだけでは，exponentialな下界になる．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 理論研究で大事なポイント\n",
    "\n",
    "上で見たように，Agnostic learningはRLでは多項式サンプル効率で解くことはできず，また，線形な実現可能性だけでも多項式サンプル効率にはなりません．\n",
    "よって，理論研究では次のパターンを考えることが多いです：\n",
    "\n",
    "1. 仮説集合がMDPと何らかの関連した構造をもつことを仮定する．これによりAgnostic learning lower boundを解決できることがあります（例えばLinear Bellman Completenessなどですね．）\n",
    "2. 模倣学習などの教師データなどを利用する．"
   ]
  }
 ],
 "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
}