notebooks/RL_robust_MDP_NP_hard.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ロバストMDPとNP困難\n",
    "\n",
    "参考\n",
    "* [Robust Markov Decision Processes](https://pubsonline.informs.org/doi/abs/10.1287/moor.1120.0566?journalCode=moor)\n",
    "    * [途中版は読むべきではないよ．図とかが途中でかなり適当](https://optimization-online.org/wp-content/uploads/2010/05/2610.pdf)\n",
    "    * ジャーナル版はかなり重要なことが書いてあるので必読\n",
    "\n",
    "[RL_robust_rectangularity](RL_robust_rectangularity.ipynb) で説明したように，ロバストMDPは適切なUncertainty setの仮定をいれないとNP-hardになります．\n",
    "これを示します．\n",
    "\n",
    "$$\n",
    "z^*=\\inf _{P \\in \\mathcal{P}} \\mathbb{E}^{P, \\pi}\\left[\\sum_{t=0}^{\\infty} \\lambda^t r\\left(s_t, a_t, s_{t+1}\\right) \\mid s_0 \\sim p_0\\right]\n",
    "$$\n",
    "\n",
    "---\n",
    "\n",
    "* 表記など\n",
    "\n",
    "以下，Uncertainty setを\n",
    "$$\n",
    "\\mathcal{P}:=\\left\\{P \\in[\\mathcal{M}(\\mathcal{S})]^{S \\times A}: \\exists \\xi \\in \\Xi \\text { such that } P_{s a}=p^{\\xi}(\\cdot \\mid s, a) \\quad \\forall(s, a) \\in \\mathcal{S} \\times \\mathcal{A}\\right\\}\n",
    "$$\n",
    "とし，$p^{\\xi}(\\cdot \\mid s, a):=k_{s a}+K_{s a} \\xi$としました．（$k_{s a} \\in \\mathbb{R}^S$ and $K_{s a} \\in \\mathbb{R}^{S \\times q}$です．）\n",
    "また，$\\Xi$が\n",
    "\n",
    "$$\n",
    "\\Xi:=\\left\\{\\xi \\in \\mathbb{R}^q: \\xi^{\\top} O_l \\xi+o_l^{\\top} \\xi+\\omega \\geq 0 \\forall l=1, \\ldots, L\\right\\}\n",
    "$$\n",
    "\n",
    "の形式とします．（ここで$O_l \\in \\mathbb{S}^q$ satisfies $O_l \\preceq 0$とします）．\n",
    "\n",
    "$\\Xi$は有界であり，Slater point $\\bar{\\xi}^{\\top} O_l \\bar{\\xi}+o_l^{\\top} \\bar{\\xi}+\\omega>0$を持つとします．\n",
    "\n",
    "---\n",
    "\n",
    "\n",
    "これが次の0/1整数計画問題で書き換えられることを示します．\n",
    "\n",
    "---\n",
    "\n",
    "**0/1整数計画問題（IP問題）**\n",
    "\n",
    "* インスタンス：\n",
    "  * 行列$F \\in \\mathbb{Z}^{m \\times n}$\n",
    "  * ベクトル$g \\in \\mathbb{Z}^m$\n",
    "  * ベクトル$c\\in \\mathbb{Z}^n$\n",
    "  * 定数$\\zeta$\n",
    "* 問：$F x \\leq g$ such that $c^\\top x \\leq \\zeta$ となる0/1ベクトル$x \\in\\{0,1\\}^n$は存在するか？\n",
    "\n",
    "この0/1整数計画問題は，$Fx\\leq g$の解が十分$0$か$1$に近ければ，その値を丸めることで解くことができます．\n",
    "\n",
    "---\n",
    "\n",
    "**IP問題と近似による解法**\n",
    "\n",
    "* $0<\\epsilon \\leq \\min \\left\\{\\epsilon_F, \\epsilon_c\\right\\}$\n",
    "* $0<\\epsilon_F<\\min _i\\left\\{\\left(\\sum_j\\left|F_{i j}\\right|\\right)^{-1}\\right\\}$\n",
    "* $0<\\boldsymbol{\\epsilon}_c<\\left(\\sum_j\\left|c_j\\right|\\right)^{-1}$\n",
    "* $x \\in([0, \\epsilon] \\cup[1-\\epsilon, 1])^n$が$F x \\leq g$と$c^\\top x \\leq \\zeta$を満たすとする．\n",
    "\n",
    "このとき，$y_j:=1$ if $x_j \\geq 1-\\epsilon$ and $y_j:=0$ otherwise とすれば，$F y \\leq g$ かつ $c^\\top y \\leq \\zeta$ for $y \\in\\{0,1\\}^n$である．\n",
    "\n",
    "証明は省略します．\n",
    "\n",
    "---\n",
    "\n",
    "以下，ロバスト評価問題を近似するのが難しいことを示します．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ロバストMDPはNP困難\n",
    "\n",
    "次を示します．\n",
    "\n",
    "---\n",
    "\n",
    "* P=NPでなければ，決定的 or 確率的な定常方策について，ロバスト評価問題を任意の相対誤差$\\beta$かつ多項式時間で近似するようなアルゴリズムは存在しない．\n",
    "\n",
    "**証明**\n",
    "\n",
    "$F, g, c, \\zeta$を固定します．また，$\\zeta \\leq \\sum_j\\left[c_j\\right]^{+}$とします（これはIP問題の解がバイナリなので，一般性を損ないません）．\n",
    "\n",
    "続いて，次のMDPを考えます（下図参照）：\n",
    "* 状態集合：$\\mathcal{S}=\\left\\{b_j, b_j^0, b_j^1: j=1, \\ldots, n\\right\\} \\cup\\{c_0, \\tau\\}$\n",
    "* 行動集合：$\\mathcal{A}=\\{a\\}$\n",
    "* 割引率：$\\lambda \\in (0, 1)$\n",
    "* 報酬関数：下図参照\n",
    "* 初期状態：$b1 \\dots bn$に$1/n$の確率を振る\n",
    "\n",
    "また，不確実集合$\\mathcal{P}$は\n",
    "\n",
    "$$\n",
    "\\xi \\in \\Xi:=\\left\\{\\xi \\in[0,1]^n: F \\xi \\leq g \\right\\}\n",
    "$$\n",
    "\n",
    "に関する全ての遷移確率とします（$\\xi$は連続値を取ることに注意しましょう）．\n",
    "\n",
    "以下，$M>\\left(\\lambda n \\sum_j\\left|c_j\\right|\\right) /\\left(2 \\epsilon^2\\right)$として，$\\gamma:=\\lambda^2 \\zeta$とします．\n",
    "\n",
    "まず， **このIP問題への答えがYESである必要十分条件は「上のMDPにおけるロバスト収益が$\\gamma$を超えない」** であることを示しましょう．\n",
    "\n",
    "---\n",
    "\n",
    "IP問題への答えがYESである状況を考えます．つまり，$F x \\leq g$ and $c^{\\top} x \\leq \\zeta$を満たす$x \\in\\{0,1\\}^n$ が存在するとします．\n",
    "このとき，$\\xi=x \\in \\mathcal{P}$による報酬を考えます．\n",
    "\n",
    "1. １ステップ目の報酬は常に０\n",
    "2. $\\xi$が０か１なのを踏まえて，図をよく見れば，２ステップ目の報酬も０\n",
    "3. 報酬が得られるのは３ステップ目だけ\n",
    "\n",
    "よって，$\\xi$のときの期待収益は$\\lambda^2 c^\\top \\xi$です．$\\xi$が満たす制約より，\n",
    "$$\\lambda^2 c^\\top \\xi \\leq \\lambda^2 \\zeta =\\gamma$$\n",
    "が成り立ちます．\n",
    "ロバスト期待収益は$\\xi$のうち最悪ケースを考えるので，これは$\\gamma$を超えません．\n",
    "\n",
    "---\n",
    "\n",
    "逆に，ロバスト期待収益が$\\gamma$を超えない場合を考えましょう．まず，設定したロバストMDPについて，その期待収益は$\\xi$について連続です．\n",
    "$\\mathcal{P}$がコンパクトなので，ロバスト期待収益は何らかの$\\xi^*\\in \\Xi$によって達成され，それは\n",
    "$\\xi^*\\in [0, 1]^n$かつ$F\\xi^* \\leq g$を満たします．\n",
    "\n",
    "ここで，何らかの$q\\in \\{1, \\dots, n\\}$について$\\xi_q^* \\notin([0, \\epsilon] \\cup[1-\\epsilon, 1])$とします．このときの報酬を考えましょう．\n",
    "\n",
    "1. １ステップ目の報酬は常に０\n",
    "2. ２ステップ目は，各$q$について$2\\lambda \\xi^*_q (1 - \\xi^*_q) M / n > \\frac{2\\lambda^2\\xi^*_q (1 - \\xi^*_q)}{2\\epsilon^2}\\sum_j |c_j|$\n",
    "3. ３ステップ目の報酬は$\\lambda^2 \\sum_j c_j \\geq -\\lambda^2 \\sum_j [-c_j]^+ $\n",
    "\n",
    "全部合わせると，期待収益は\n",
    "\n",
    "$$\n",
    "2\\lambda \\xi^*_q (1 - \\xi^*_q) M / n  + \\lambda^2 \\sum_j c_j > \\lambda^2 \\sum_j [c_j]^+ \\geq \\gamma\n",
    "$$\n",
    "\n",
    "となり，矛盾．\n",
    "\n",
    "続いて，$\\xi^* \\in([0, \\epsilon] \\cup[1-\\epsilon, 1])^n$とします．\n",
    "このときの報酬は，\n",
    "\n",
    "1. １ステップ目の報酬は常に０\n",
    "2. ２ステップ目は非負\n",
    "3. ３ステップ目の報酬は$\\lambda^2 c^\\top \\xi^*$\n",
    "\n",
    "ロバスト期待収益が$\\gamma$を超えない仮定より，$\\lambda^2 c^\\top \\xi^* \\leq \\gamma = \\lambda^2 \\zeta$です．\n",
    "よって，$c^\\top \\xi^*\\leq \\zeta$です．\n",
    "\n",
    "上で示したように，この$\\xi^*$は0か1に十分近いので，$F \\xi^{\\prime} \\leq g$ and $c^{\\top} \\xi^{\\prime} \\leq \\zeta$を満たすベクトル$\\xi^{\\prime} \\in\\{0,1\\}^n$が存在します．\n",
    "\n",
    "---\n",
    "\n",
    "さて，上で見たように，\n",
    "**IP問題への答えがYESである必要十分条件は「上のMDPにおけるロバスト収益が$\\gamma$を超えない」**\n",
    "でした．\n",
    "よって，「上のMDPにおけるロバスト収益が$\\gamma$を超えるか？」を多項式時間で評価できれば，IP問題に回答することができます．\n",
    "しかし，IP問題はstrongly NP-hardであることが知られています．よって，上のMDPのロバスト収益の評価はStrongly NP-hardであり，Uncertainty set$\\Xi$の下ではロバストMDPを解くのはNP困難です．\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "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=\"618pt\" height=\"344pt\"\n",
       " viewBox=\"0.00 0.00 618.09 344.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 340)\">\n",
       "<title>G</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-340 614.09,-340 614.09,4 -4,4\"/>\n",
       "<g id=\"clust1\" class=\"cluster\">\n",
       "<title>cluster_1</title>\n",
       "<polygon fill=\"none\" stroke=\"blue\" points=\"14.09,-166 14.09,-328 156.09,-328 156.09,-166 14.09,-166\"/>\n",
       "<text text-anchor=\"middle\" x=\"85.09\" y=\"-312.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=\"236.09,-166 236.09,-328 378.09,-328 378.09,-166 236.09,-166\"/>\n",
       "<text text-anchor=\"middle\" x=\"307.09\" y=\"-312.8\" font-family=\"Times,serif\" font-size=\"14.00\">h=2</text>\n",
       "</g>\n",
       "<g id=\"clust3\" class=\"cluster\">\n",
       "<title>cluster_n</title>\n",
       "<polygon fill=\"none\" stroke=\"blue\" points=\"458.09,-166 458.09,-328 600.09,-328 600.09,-166 458.09,-166\"/>\n",
       "<text text-anchor=\"middle\" x=\"529.09\" y=\"-312.8\" font-family=\"Times,serif\" font-size=\"14.00\">h=n</text>\n",
       "</g>\n",
       "<!-- b1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>b1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"78.09\" cy=\"-279\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"78.09\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\">b1</text>\n",
       "</g>\n",
       "<!-- b01 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>b01</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"49.09\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"49.09\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">b01</text>\n",
       "</g>\n",
       "<!-- b1&#45;&gt;b01 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>b1&#45;&gt;b01</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M68.77,-262.01C65.66,-256.18 62.41,-249.43 60.09,-243 57.44,-235.64 55.31,-227.43 53.66,-219.83\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"57.08,-219.1 51.7,-209.97 50.22,-220.46 57.08,-219.1\"/>\n",
       "<text text-anchor=\"middle\" x=\"77.59\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">1&#45;ξ1:0</text>\n",
       "</g>\n",
       "<!-- b11 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>b11</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"121.09\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"121.09\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">b11</text>\n",
       "</g>\n",
       "<!-- b1&#45;&gt;b11 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>b1&#45;&gt;b11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M86.38,-261.61C92.57,-249.38 101.14,-232.44 108.21,-218.46\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"111.44,-219.84 112.83,-209.34 105.19,-216.68 111.44,-219.84\"/>\n",
       "<text text-anchor=\"middle\" x=\"115.09\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">ξ1:0</text>\n",
       "</g>\n",
       "<!-- c0 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>c0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"307.09\" cy=\"-105\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"307.09\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">c0</text>\n",
       "</g>\n",
       "<!-- b01&#45;&gt;c0 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>b01&#45;&gt;c0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M28.31,-180.3C11.33,-170.19 -8.03,-154.6 4.09,-141 21.51,-121.46 192.73,-111.23 269.82,-107.58\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"270.22,-111.06 280.04,-107.11 269.89,-104.07 270.22,-111.06\"/>\n",
       "<text text-anchor=\"middle\" x=\"19.09\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">ξ1:M</text>\n",
       "</g>\n",
       "<!-- b01&#45;&gt;c0 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>b01&#45;&gt;c0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M52.17,-173.98C55.11,-162.85 60.69,-148.94 71.09,-141 101.55,-117.76 211.22,-109.83 269.72,-107.22\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"270.17,-110.71 280.02,-106.79 269.88,-103.71 270.17,-110.71\"/>\n",
       "<text text-anchor=\"middle\" x=\"88.59\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">1&#45;ξ1:0</text>\n",
       "</g>\n",
       "<!-- b11&#45;&gt;c0 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>b11&#45;&gt;c0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M113.35,-174.36C109.65,-163.67 107.48,-150.13 115.09,-141 134.39,-117.86 219.54,-109.98 269.73,-107.33\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"270.06,-110.81 279.88,-106.83 269.72,-103.82 270.06,-110.81\"/>\n",
       "<text text-anchor=\"middle\" x=\"127.09\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">ξ1:0</text>\n",
       "</g>\n",
       "<!-- b11&#45;&gt;c0 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>b11&#45;&gt;c0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M134.24,-176.27C145,-165.07 161.16,-150.09 178.09,-141 207.25,-125.36 243.94,-116.28 270.73,-111.31\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"271.59,-114.71 280.84,-109.54 270.38,-107.82 271.59,-114.71\"/>\n",
       "<text text-anchor=\"middle\" x=\"198.59\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">1&#45;ξ1:M</text>\n",
       "</g>\n",
       "<!-- b2 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>b2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"300.09\" cy=\"-279\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"300.09\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\">b2</text>\n",
       "</g>\n",
       "<!-- b02 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>b02</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"271.09\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"271.09\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">b02</text>\n",
       "</g>\n",
       "<!-- b2&#45;&gt;b02 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>b2&#45;&gt;b02</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M290.77,-262.01C287.66,-256.18 284.41,-249.43 282.09,-243 279.44,-235.64 277.31,-227.43 275.66,-219.83\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"279.08,-219.1 273.7,-209.97 272.22,-220.46 279.08,-219.1\"/>\n",
       "<text text-anchor=\"middle\" x=\"299.59\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">1&#45;ξ2:0</text>\n",
       "</g>\n",
       "<!-- b12 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>b12</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"343.09\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"343.09\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">b12</text>\n",
       "</g>\n",
       "<!-- b2&#45;&gt;b12 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>b2&#45;&gt;b12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M308.38,-261.61C314.57,-249.38 323.14,-232.44 330.21,-218.46\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"333.44,-219.84 334.83,-209.34 327.19,-216.68 333.44,-219.84\"/>\n",
       "<text text-anchor=\"middle\" x=\"336.09\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">ξ2:0</text>\n",
       "</g>\n",
       "<!-- b02&#45;&gt;c0 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>b02&#45;&gt;c0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M250.33,-180.48C234.27,-170.87 216.28,-155.93 226.09,-141 236.06,-125.84 254.14,-117.22 270.69,-112.33\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"271.9,-115.63 280.71,-109.74 270.15,-108.85 271.9,-115.63\"/>\n",
       "<text text-anchor=\"middle\" x=\"241.09\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">ξ2:M</text>\n",
       "</g>\n",
       "<!-- b02&#45;&gt;c0 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>b02&#45;&gt;c0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M273.61,-173.83C275.45,-163.94 278.45,-151.44 283.09,-141 284.76,-137.24 286.84,-133.46 289.08,-129.85\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"292.14,-131.56 294.8,-121.3 286.33,-127.66 292.14,-131.56\"/>\n",
       "<text text-anchor=\"middle\" x=\"300.59\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">1&#45;ξ2:0</text>\n",
       "</g>\n",
       "<!-- b12&#45;&gt;c0 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>b12&#45;&gt;c0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M335.98,-174.21C330.87,-162.14 323.88,-145.64 318.06,-131.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"321.19,-130.31 314.07,-122.47 314.75,-133.04 321.19,-130.31\"/>\n",
       "<text text-anchor=\"middle\" x=\"339.09\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">ξ2:0</text>\n",
       "</g>\n",
       "<!-- b12&#45;&gt;c0 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>b12&#45;&gt;c0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M352.37,-175.02C356.97,-164.86 360.51,-151.66 355.09,-141 351.09,-133.14 344.41,-126.62 337.28,-121.43\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"339.13,-118.46 328.84,-115.94 335.32,-124.33 339.13,-118.46\"/>\n",
       "<text text-anchor=\"middle\" x=\"377.59\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">1&#45;ξ2:M</text>\n",
       "</g>\n",
       "<!-- bn -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>bn</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"522.09\" cy=\"-279\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"522.09\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\">bn</text>\n",
       "</g>\n",
       "<!-- b0n -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>b0n</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"493.09\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"493.09\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">b0n</text>\n",
       "</g>\n",
       "<!-- bn&#45;&gt;b0n -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>bn&#45;&gt;b0n</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M512.77,-262.01C509.66,-256.18 506.41,-249.43 504.09,-243 501.44,-235.64 499.31,-227.43 497.66,-219.83\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"501.08,-219.1 495.7,-209.97 494.22,-220.46 501.08,-219.1\"/>\n",
       "<text text-anchor=\"middle\" x=\"521.59\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">1&#45;ξn:0</text>\n",
       "</g>\n",
       "<!-- b1n -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>b1n</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"565.09\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"565.09\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">b1n</text>\n",
       "</g>\n",
       "<!-- bn&#45;&gt;b1n -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>bn&#45;&gt;b1n</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M530.38,-261.61C536.57,-249.38 545.14,-232.44 552.21,-218.46\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"555.44,-219.84 556.83,-209.34 549.19,-216.68 555.44,-219.84\"/>\n",
       "<text text-anchor=\"middle\" x=\"558.09\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">ξn:0</text>\n",
       "</g>\n",
       "<!-- b0n&#45;&gt;c0 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>b0n&#45;&gt;c0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M473.65,-179.2C455.51,-168.47 427.52,-152.59 402.09,-141 382.12,-131.9 359.03,-123.35 340.61,-116.98\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"341.51,-113.58 330.91,-113.67 339.25,-120.21 341.51,-113.58\"/>\n",
       "<text text-anchor=\"middle\" x=\"445.09\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">ξn:M</text>\n",
       "</g>\n",
       "<!-- b0n&#45;&gt;c0 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>b0n&#45;&gt;c0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M487.41,-174.14C482.82,-163.07 475.26,-149.18 464.09,-141 428.98,-115.27 378.42,-107.9 344.24,-106.07\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"344.33,-102.57 334.2,-105.66 344.05,-109.56 344.33,-102.57\"/>\n",
       "<text text-anchor=\"middle\" x=\"494.59\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">1&#45;ξn:0</text>\n",
       "</g>\n",
       "<!-- b1n&#45;&gt;c0 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>b1n&#45;&gt;c0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M554.07,-175.31C545.18,-163.9 531.61,-149.09 516.09,-141 461.1,-112.32 387.89,-106.23 344.31,-105.42\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"344.2,-101.92 334.16,-105.32 344.13,-108.92 344.2,-101.92\"/>\n",
       "<text text-anchor=\"middle\" x=\"547.09\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">ξn:0</text>\n",
       "</g>\n",
       "<!-- b1n&#45;&gt;c0 -->\n",
       "<g id=\"edge18\" class=\"edge\">\n",
       "<title>b1n&#45;&gt;c0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M569.42,-174.11C571.11,-163.31 571.04,-149.75 563.09,-141 534.52,-109.55 408.03,-105.48 344.2,-105.49\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"344.14,-101.99 334.15,-105.53 344.17,-108.99 344.14,-101.99\"/>\n",
       "<text text-anchor=\"middle\" x=\"589.59\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">1&#45;ξn:M</text>\n",
       "</g>\n",
       "<!-- τ -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>τ</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"307.09\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"307.09\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">τ</text>\n",
       "</g>\n",
       "<!-- c0&#45;&gt;τ -->\n",
       "<g id=\"edge19\" class=\"edge\">\n",
       "<title>c0&#45;&gt;τ</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M280.27,-102.45C257.41,-99.54 225.84,-91.42 210.09,-69 192.43,-43.85 236.1,-30.5 270.47,-24.09\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"271.49,-27.46 280.76,-22.32 270.31,-20.56 271.49,-27.46\"/>\n",
       "<text text-anchor=\"middle\" x=\"230.09\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\">ξ1/n:nc</text>\n",
       "</g>\n",
       "<!-- c0&#45;&gt;τ -->\n",
       "<g id=\"edge20\" class=\"edge\">\n",
       "<title>c0&#45;&gt;τ</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M289.59,-90.93C283.12,-85.03 276.53,-77.48 273.09,-69 268.76,-58.32 274.4,-47.6 282.26,-38.84\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"284.85,-41.2 289.54,-31.7 279.95,-36.2 284.85,-41.2\"/>\n",
       "<text text-anchor=\"middle\" x=\"296.59\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\">ξ2/n:nc2</text>\n",
       "</g>\n",
       "<!-- c0&#45;&gt;τ -->\n",
       "<g id=\"edge21\" class=\"edge\">\n",
       "<title>c0&#45;&gt;τ</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M314.55,-87.61C316.8,-81.85 318.97,-75.25 320.09,-69 321.5,-61.14 320.36,-52.71 318.27,-45.04\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"321.59,-43.91 315.12,-35.53 314.94,-46.12 321.59,-43.91\"/>\n",
       "<text text-anchor=\"middle\" x=\"343.59\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\">ξn/n:ncn</text>\n",
       "</g>\n",
       "<!-- c0&#45;&gt;τ -->\n",
       "<g id=\"edge22\" class=\"edge\">\n",
       "<title>c0&#45;&gt;τ</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M331.92,-97.32C346.07,-92.1 362.63,-83.27 371.09,-69 381.15,-52.04 361.12,-38.69 340.87,-30.06\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"341.94,-26.72 331.35,-26.33 339.38,-33.24 341.94,-26.72\"/>\n",
       "<text text-anchor=\"middle\" x=\"401.09\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\">1&#45;e^Tξn:0</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7f72ec1552b0>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 状態と遷移の関係．行動は固定されてることに注意\n",
    "\n",
    "from graphviz import Digraph\n",
    "\n",
    "g = Digraph('G')\n",
    "\n",
    "with g.subgraph(name='cluster_1') as c:\n",
    "    c.attr(color='blue')\n",
    "    c.node('b1')\n",
    "    c.node('b01')\n",
    "    c.node('b11')\n",
    "    c.attr(label='h=1')\n",
    "\n",
    "with g.subgraph(name='cluster_2') as c:\n",
    "    c.attr(color='blue')\n",
    "    c.node('b2')\n",
    "    c.node('b02')\n",
    "    c.node('b12')\n",
    "    c.attr(label='h=2')\n",
    "\n",
    "with g.subgraph(name='cluster_n') as c:\n",
    "    c.attr(color='blue')\n",
    "    c.node('bn')\n",
    "    c.node('b0n')\n",
    "    c.node('b1n')\n",
    "    c.attr(label='h=n')\n",
    "\n",
    "g.node(\"c0\")\n",
    "g.node(\"τ\")\n",
    "\n",
    "g.edge(\"b1\", \"b01\", label=\"1-ξ1:0\")\n",
    "g.edge(\"b1\", \"b11\", label=\"ξ1:0\")\n",
    "g.edge(\"b2\", \"b02\", label=\"1-ξ2:0\")\n",
    "g.edge(\"b2\", \"b12\", label=\"ξ2:0\")\n",
    "g.edge(\"bn\", \"b0n\", label=\"1-ξn:0\")\n",
    "g.edge(\"bn\", \"b1n\", label=\"ξn:0\")\n",
    "\n",
    "g.edge(\"b01\", \"c0\", label=\"ξ1:M\")\n",
    "g.edge(\"b11\", \"c0\", label=\"ξ1:0\")\n",
    "g.edge(\"b02\", \"c0\", label=\"ξ2:M\")\n",
    "g.edge(\"b12\", \"c0\", label=\"ξ2:0\")\n",
    "g.edge(\"b0n\", \"c0\", label=\"ξn:M\")\n",
    "g.edge(\"b1n\", \"c0\", label=\"ξn:0\")\n",
    "\n",
    "g.edge(\"b01\", \"c0\", label=\"1-ξ1:0\")\n",
    "g.edge(\"b11\", \"c0\", label=\"1-ξ1:M\")\n",
    "g.edge(\"b02\", \"c0\", label=\"1-ξ2:0\")\n",
    "g.edge(\"b12\", \"c0\", label=\"1-ξ2:M\")\n",
    "g.edge(\"b0n\", \"c0\", label=\"1-ξn:0\")\n",
    "g.edge(\"b1n\", \"c0\", label=\"1-ξn:M\")\n",
    "\n",
    "g.edge(\"c0\", \"τ\", label=\"ξ1/n:nc\")\n",
    "g.edge(\"c0\", \"τ\", label=\"ξ2/n:nc2\")\n",
    "g.edge(\"c0\", \"τ\", label=\"ξn/n:ncn\")\n",
    "g.edge(\"c0\", \"τ\", label=\"1-e^Tξn:0\")\n",
    "\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "このようにNon-rectangularなロバストMDPはNP困難になりえます．\n",
    "\n",
    "一方で，$s$-rectangularなロバストMDPについては多項式時間で解けることが知られています．\n",
    "これは\n",
    "* $s$-rectangularなロバストMDPは２プレイヤー確率ゲームと同じ（[Robust dynamic programming](http://www.corc.ieor.columbia.edu/reports/techreports/tr-2002-07.pdf)）\n",
    "* ２プレイヤー確率ゲームは多項式時間で解ける（[Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor](https://arxiv.org/abs/1008.0530)）\n",
    "\n",
    "ことからわかります．\n",
    "しかし，non-rectangularの場合は確率ゲームとの明確なコネクションがあるかはわかりません．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "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
 },
 "nbformat": 4,
 "nbformat_minor": 2
}