notebooks/RL_mean_variance_MDP_NP_hard.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Mean-Variance MDPとNP困難\n",
    "\n",
    "参考：\n",
    "* [Mean-Variance Optimization in Markov Decision Processes](https://arxiv.org/abs/1104.5601)\n",
    "\n",
    "MDPの目的は一般に累積報酬和の**期待値**を最大化することを目的にしますが，実応用では期待値だけの最大化では不十分なケースがあります．\n",
    "累積報酬和の分散が大きいと，デプロイごとに性能にバラついてしまい，製品として販売するには困ります．\n",
    "\n",
    "Mean-variance MDPは次の問題を考えます．\n",
    "\n",
    "---\n",
    "\n",
    "**Mean-variance MDP**\n",
    "\n",
    "方策$\\pi$の累積報酬和の期待値を$J_\\pi$とし，その分散を$V_\\pi$とする．\n",
    "与えられたMDPと定数$\\lambda$, $v$のもとで，$J_\\pi \\geq \\lambda$かつ$V_\\pi \\leq v$を保証する$\\pi$は存在するか？\n",
    "\n",
    "---\n",
    "\n",
    "実はこれはNP困難になります．証明しましょう．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mean-Variance MDPはNP困難\n",
    "\n",
    "Mean-Variance MDPにおいて，分散が０になる方策を見つけるのがNP困難であることを，３−SAT問題を使って証明します．\n",
    "３−SAT問題については[RL_CMDP_feasibility_NP_hard.ipynb](RL_CMDP_feasibility_NP_hard.ipynb)などを参照してください．\n",
    "\n",
    "---\n",
    "\n",
    "**３−SAT問題**\n",
    "* $n$個のリテラル：$x_1, x_2, \\dots, x_n$．例えば$x_3 = \\text{true}$．\n",
    "* $m$個の節：$C_1, C_2, \\dots, C_n$．例えば$C_3=x_2 \\vee \\bar{x}_5 \\vee x_7$．\n",
    "\n",
    "このときに，$C_1\\wedge C_2 \\wedge \\dots \\wedge C_n$を満たすようにリテラルに$\\text{true}$，$\\text{false}$を入れることはできるか？がNP困難です．\n",
    "\n",
    "---\n",
    "\n",
    "次のMDPを考えましょう．\n",
    "\n",
    "* 状態集合：$\\{s_0, d_0, c_1, \\dots, c_m, y_1, \\dots, y_n\\}$\n",
    "    * 状態$c_i$が節$C_i$に相当します．\n",
    "    * 状態$y_i$はリテラル$x_i$に相当します．\n",
    "    * 状態$d_0$は吸収状態です\n",
    "    * 状態$s_0$は初期状態です\n",
    "\n",
    "* 遷移と報酬：\n",
    "    * 行動に関わらず，$s_0$から$d_0, c_1, \\dots, c_m$に確率$1/(m+1)$に遷移します．このときに報酬は発生しません．\n",
    "    * 各$c_i$での遷移と報酬．\n",
    "        * 各$c_i$は節に対応するため，$C_j$における３つのリテラルが割り当てられています．\n",
    "        * $c_i$では，３つのリテラルに対応した状態に進むような３つの行動を取ることができます．\n",
    "            * 例えば３つのリテラルが$x_1, \\bar{x}_4, x_5$の場合，３つの行動はそれぞれ$y_1, y_4, y_5$に遷移します．\n",
    "        * もし遷移したリテラルがnegatedな場合，つまり$\\bar{x}$みたいな場合，-1の報酬が発生します．unnegatedな場合は+1の報酬が発生します．\n",
    "    * 各$y_i$での遷移と報酬．\n",
    "      * 各$y_i$では２つの行動$a_i$と$b_i$を選択することができます．\n",
    "      * $a_i$を選ぶと+1，$b_i$を選ぶと-1の報酬が返ります．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "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=\"218pt\" height=\"305pt\"\n",
       " viewBox=\"0.00 0.00 218.24 305.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 301)\">\n",
       "<title>G</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-301 214.24,-301 214.24,4 -4,4\"/>\n",
       "<!-- s0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>s0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"75.24\" cy=\"-279\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"75.24\" y=\"-275.3\" font-family=\"Times,serif\" font-size=\"14.00\">s0</text>\n",
       "</g>\n",
       "<!-- d0 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>d0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"52.24\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"52.24\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">d0</text>\n",
       "</g>\n",
       "<!-- s0&#45;&gt;d0 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>s0&#45;&gt;d0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M64.72,-262.15C47.48,-235.04 14.05,-177.42 3.24,-123 0.12,-107.31 -1.68,-102.23 3.24,-87 8.77,-69.85 20.42,-53.37 30.98,-40.94\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"33.66,-43.19 37.68,-33.38 28.42,-38.54 33.66,-43.19\"/>\n",
       "</g>\n",
       "<!-- ci -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>ci</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"75.24\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"75.24\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">ci</text>\n",
       "</g>\n",
       "<!-- s0&#45;&gt;ci -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>s0&#45;&gt;ci</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M75.24,-260.8C75.24,-249.16 75.24,-233.55 75.24,-220.24\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"78.74,-220.18 75.24,-210.18 71.74,-220.18 78.74,-220.18\"/>\n",
       "</g>\n",
       "<!-- ... -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>...</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"147.24\" cy=\"-192\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"147.24\" y=\"-188.3\" font-family=\"Times,serif\" font-size=\"14.00\">...</text>\n",
       "</g>\n",
       "<!-- s0&#45;&gt;... -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>s0&#45;&gt;...</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M88.11,-262.8C99.17,-249.75 115.27,-230.74 127.88,-215.85\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"130.68,-217.96 134.48,-208.06 125.34,-213.43 130.68,-217.96\"/>\n",
       "<text text-anchor=\"middle\" x=\"138.24\" y=\"-231.8\" font-family=\"Times,serif\" font-size=\"14.00\">1/(m+1)</text>\n",
       "</g>\n",
       "<!-- y3 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>y3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"39.24\" cy=\"-105\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"39.24\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">y3</text>\n",
       "</g>\n",
       "<!-- ci&#45;&gt;y3 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>ci&#45;&gt;y3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M59.92,-177.03C54.38,-171.1 48.65,-163.77 45.24,-156 42.18,-149.04 40.5,-141.03 39.63,-133.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"43.1,-133.02 38.86,-123.32 36.12,-133.55 43.1,-133.02\"/>\n",
       "<text text-anchor=\"middle\" x=\"69.24\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">&#45;1 if _x3</text>\n",
       "</g>\n",
       "<!-- y5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>y5</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"111.24\" cy=\"-105\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"111.24\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">y5</text>\n",
       "</g>\n",
       "<!-- ci&#45;&gt;y5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>ci&#45;&gt;y5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M84.11,-174.83C87.17,-168.98 90.51,-162.27 93.24,-156 96.51,-148.47 99.69,-140.13 102.43,-132.46\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"105.79,-133.47 105.77,-122.88 99.17,-131.17 105.79,-133.47\"/>\n",
       "</g>\n",
       "<!-- y6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>y6</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"183.24\" cy=\"-105\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"183.24\" y=\"-101.3\" font-family=\"Times,serif\" font-size=\"14.00\">y6</text>\n",
       "</g>\n",
       "<!-- ci&#45;&gt;y6 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>ci&#45;&gt;y6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M92.11,-177.72C109.94,-163.68 138.25,-141.41 158.58,-125.41\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"160.79,-128.12 166.48,-119.19 156.46,-122.62 160.79,-128.12\"/>\n",
       "<text text-anchor=\"middle\" x=\"157.74\" y=\"-144.8\" font-family=\"Times,serif\" font-size=\"14.00\">+1 if x6</text>\n",
       "</g>\n",
       "<!-- y5&#45;&gt;d0 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>y5&#45;&gt;d0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M89.77,-93.82C75.05,-86.35 57.44,-76.28 53.24,-69 49.3,-62.18 48.02,-53.91 48.02,-46.08\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"51.53,-46.05 48.68,-35.84 44.54,-45.6 51.53,-46.05\"/>\n",
       "<text text-anchor=\"middle\" x=\"71.24\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\">a5, +1</text>\n",
       "</g>\n",
       "<!-- y5&#45;&gt;d0 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>y5&#45;&gt;d0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M105.66,-86.91C101.9,-76.81 96.34,-64.08 89.24,-54 85.65,-48.91 81.23,-43.97 76.71,-39.48\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"78.84,-36.68 69.15,-32.41 74.07,-41.79 78.84,-36.68\"/>\n",
       "<text text-anchor=\"middle\" x=\"113.74\" y=\"-57.8\" font-family=\"Times,serif\" font-size=\"14.00\">b5, &#45;1</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7f82e43611f0>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 状態と遷移の関係．行動は固定されてることに注意\n",
    "\n",
    "from graphviz import Digraph\n",
    "\n",
    "g = Digraph('G')\n",
    "\n",
    "g.node(\"s0\")\n",
    "g.node(\"d0\")\n",
    "\n",
    "g.edge(\"s0\", \"ci\")\n",
    "g.edge(\"s0\", \"...\", label=\"1/(m+1)\")\n",
    "g.edge(\"s0\", \"d0\")\n",
    "\n",
    "g.edge(\"ci\", \"y3\", label=\"-1 if _x3\")\n",
    "g.edge(\"ci\", \"y5\")\n",
    "g.edge(\"ci\", \"y6\", label=\"+1 if x6\")\n",
    "\n",
    "g.edge(\"y5\", \"d0\", label=\"a5, +1\")\n",
    "g.edge(\"y5\", \"d0\", label=\"b5, -1\")\n",
    "g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "**３−SATから方策へ**\n",
    "\n",
    "以下，３−SAT問題の答えがtrueであるとして，次の方策を考えてみましょう．つまり，全ての節をtrueにするようなリテラルへのバイナリが存在します．\n",
    "\n",
    "* 状態$c_i$では，節$C_i$をtrueにするような行動を取るとします．全ての節はtrueなので，各$C_i$には必ず一つリテラルがtrueになるような状態$y_\\square$が存在します．\n",
    "* このとき，リテラル$x_i$がunnegatedであれば，+1の報酬が発生します．\n",
    "* 状態$y_i$ではリテラル$x_i$がunnegatedであれば，行動$b_i$を取るとします．このとき-1の報酬が発生します．\n",
    "    * neggatedなときは$a_i$を取るとします．\n",
    "\n",
    "このとき，発生する報酬和は常に$1 - 1 = 0$なので，リターンの分散は確率１で０になります．\n",
    "\n",
    "---\n",
    "\n",
    "**方策から３−SATへ**\n",
    "\n",
    "mean-variance MDPにおいて，分散を０にする方策が存在するとします．\n",
    "このとき，$s_0$で$d_0$に遷移する可能性があるため，分散を０に維持するには，このMDPにおけるReturnは常に０である必要があります．\n",
    "\n",
    "次のようにリテラルにtrueとfalseを割り当ててみましょう．\n",
    "方策が$y_i$において$\\pi(b_i\\mid y_i) > 0$であれば，$x_i=\\text{true}$とします．\n",
    "\n",
    "例えばまず状態が$c_i$に遷移し，その後で方策によって状態$y_i$に遷移したとします．\n",
    "$x_i$のリテラルがunnegatedであるとしましょう．すると，リターンが０なので，$y_i$では必ず$b_i$を選択します．\n",
    "このとき，$y_i$では$b_i$が選択されるので，$x_i$はtrueです．\n",
    "よって，$C_i$もtrueになります．\n",
    "\n",
    "同様にして，$x_i$がneggatedなときも$C_i$がtrueになります．\n",
    "\n",
    "これより，全ての$C_i$がtrueになるので，3-SAT問題が解けることになります．\n",
    "\n",
    "---\n",
    "\n",
    "３−SAT問題はNP困難なので，以上から，mean-variance MDPはstrongly NP-hardであることがわかります．\n",
    "\n",
    "**コメント**\n",
    "\n",
    "これは決定的な方策でfeasibleな方策を見つけるのががNP困難になることの証明にも使えるかも．方策が決定的である場合，$C_i$からどれか一つの$y_\\square$に遷移するのを利用すれば示せるかも．\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
}