notebooks/RL_CMDP_Lagrange.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CMDPとラグランジュ関数について\n",
    "\n",
    "参考\n",
    "* [Constrained MDPs and the reward hypothesis](http://readingsml.blogspot.com/2020/03/constrained-mdps-and-reward-hypothesis.html)\n",
    "\n",
    "CMDPは制約のもとでの報酬の最大化を目指すMDPであり，普通のMDPの一般化です．\n",
    "CMDPは制約付き最適化なので，ラグランジュ関数を使って表現することができます．\n",
    "今回は，ラグランジュ関数を使った解法の落とし穴について見ていきます．\n",
    "\n",
    "表記\n",
    "* 報酬関数：$r_1, r_2, \\dots, r_n$．$Z \\subset S\\times A$についての関数．\n",
    "* $A$は行動の集合であり，$Z$は各状態と行動の集合．$z=(s, a) \\in Z$と書く．\n",
    "* 割引占有率の集合：$X_\\gamma \\subset\\left\\{x \\in[0, \\infty)^Z: \\sum_a x(s, a)=(1-\\gamma) \\mu(s)+\\gamma \\sum_{s^{\\prime}, a^{\\prime}} x\\left(s^{\\prime}, a^{\\prime}\\right) P_{s^{\\prime}, a^{\\prime}}(s), \\forall s \\in S\\right\\}$\n",
    "* CMDPの最適化対象：\n",
    "\n",
    "$$\n",
    "\\max _\\pi V^\\pi\\left(r_0, \\mu\\right) \\quad \\text { s.t. } \\quad V^\\pi\\left(r_i, \\mu\\right) \\geq \\theta_i, i=1, \\ldots, n .\n",
    "$$\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. CMDPでは一様に最適な方策が存在しないかもしれない\n",
    "\n",
    "以下では，任意の初期状態について最適な方策のことを**一様に最適な方策**と呼ぶことにします．\n",
    "\n",
    "次のCMDPを考えてみます．（[Constrained MDPs and the reward hypothesis](http://readingsml.blogspot.com/2020/03/constrained-mdps-and-reward-hypothesis.html)から引用．）\n",
    "\n",
    "![CMDP-example](figs/2stateexample150.png)\n",
    "\n",
    "* 状態Lについて\n",
    "  * 確率$p$でLEFTを選択，$1-p$でRIGHTを選択\n",
    "  * $r_0(L, RIGHT)=1$, $r_1(L, RIGHT)=-1$\n",
    "  * 確率$\\beta$でLからスタート\n",
    "* 状態Rについて\n",
    "  * $r_0(R, STAY)=r_1(R, STAY)=1$\n",
    "  * 確率$1-\\beta$でRからスタート\n",
    "* $\\gamma=0$\n",
    "* $\\theta_1=0$\n",
    "\n",
    "制約が無い状況では，状態LでRIGHTを選択するのが最適解ですが，CMDPではRIGHTを選択することができません（$\\theta_1=0$なので）\n",
    "\n",
    "CMDPでの価値関数は次のようになります：\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& V^p\\left(r_0, \\beta\\right)=\\beta(1-p)+1-\\beta \\\\\n",
    "& V^p\\left(r_1, \\beta\\right)=\\beta(p-1)+1-\\beta\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "よって，方策$p$は次を満たす必要があります．\n",
    "\n",
    "$$\n",
    "\\beta(p-1)+1-\\beta \\geq 0 \\quad \\Leftrightarrow \\quad p \\geq \\frac{2 \\beta-1}{\\beta}\n",
    "$$\n",
    "\n",
    "例えば$\\beta>0.5$のとき，$[(2 \\beta-1) / \\beta, 1] \\subsetneq[0,1]$である必要があります.\n",
    "また，$V^p\\left(r_0, \\beta\\right)$は$p$について単調に減少するため，最適な$p$は$p^*=(2\\beta-1) / \\beta$になります．\n",
    "\n",
    "これは$\\beta$に依存することに注意しましょう．よって，定常な方策については，一様に最適な方策は存在しません．\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 定常方策は最適方策を含む\n",
    "\n",
    "CMDPでは最適方策は定常方策だけ考えても問題ありません．\n",
    "これは省略します．[Constrained MDPs and the reward hypothesis](http://readingsml.blogspot.com/2020/03/constrained-mdps-and-reward-hypothesis.html)のPart2を参照してください．\n",
    "\n",
    "\n",
    "## 3. 決定的な方策の実行可能性を調べるのはNP困難\n",
    "\n",
    "これも省略します．[Constrained MDPs and the reward hypothesis](http://readingsml.blogspot.com/2020/03/constrained-mdps-and-reward-hypothesis.html)のPart3を参照してください．"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. ラグランジュ関数を使ったときの落とし穴\n",
    "\n",
    "CMDPは次の線形計画問題によって解くことができます．\n",
    "\n",
    "$$\n",
    "\\begin{array}{cl}\n",
    "\\min _x & -\\left\\langle x, r_0\\right\\rangle \\\\\n",
    "\\text { s.t. } \\quad & x \\in X_\\gamma, \\\\\n",
    "& (1-\\gamma) \\theta_i-\\left\\langle x, r_i\\right\\rangle \\leq 0, \\quad i=1, \\ldots, n .\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "これはでかい問題になると解くのが大変です．よく使われる代替法として，次のラグランジュ関数を使った方法があります．\n",
    "\n",
    "$$\n",
    "L(x, \\lambda)=-\\left\\langle x, r_0\\right\\rangle+\\sum_i \\lambda_i\\left((1-\\gamma) \\theta_i-\\left\\langle x, r_i\\right\\rangle\\right),\n",
    "$$\n",
    "\n",
    "これを使うと，CMDPは次を解くのと等価です．\n",
    "\n",
    "$$\n",
    "\\min _{x \\in X_\\gamma} \\max _{\\lambda \\geq 0} L(x, \\lambda)\n",
    "$$\n",
    "\n",
    "こうすると，報酬関数が$r=r_0+\\sum_{i=1}^n \\lambda_i^* r_i$である制約なしMDPを解くのと同じになるので，通常のRLアルゴリズムで解けるはずです．\n",
    "\n",
    "しかし，ここに落とし穴があります．この制約なし問題を解けば十分であれば，決定的な方策だけ考えればCMDPが解けるはずです．しかし，1で見たように，実際はそうではありません．\n",
    "\n",
    "なぜこのような矛盾が起きるのでしょうか？これは，決定的な方策はラグランジュ双対問題の最小値を与えますが，実はそれ以外の方策も最小値を与えるためです．\n",
    "\n",
    "例として，じゃんけんについてのMin-maxゲームを考えてみましょう．\n",
    "田中と佐藤がじゃんけんをしているとします．\n",
    "\n",
    "このMin-maxゲームの均衡は明らかに両者が一様な手を出す方策のときだけです．\n",
    "ここで，佐藤が一様な手を出すとします．すると，**このときの田中の勝率はどんな方策でも同じ**です．\n",
    "つまり，佐藤が最適解である一様な手を出す場合，田中の最適解は無限に存在します．\n",
    "\n",
    "しかし，田中が一様な手以外を選択した場合，佐藤はそれに勝つように方策を選択し直すことができます．\n",
    "つまり，このMin-Maxゲームの均衡を得るためには，佐藤が方策を選択し直しても，田中の勝率が変わらないような方策だけです．\n",
    "\n",
    "これはCMDPでも同じです．$L(\\cdot, \\lambda^*)$の最小値を与える$x$は無限に存在します．\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. 勾配法で解決しよう \n",
    "\n",
    "表記\n",
    "* $L'_x$を$L=L(x, \\lambda)$の$x$についての勾配とします\n",
    "\n",
    "次のDanskinの定理が便利です\n",
    "\n",
    "---\n",
    "\n",
    "**Danskinの定理**\n",
    "\n",
    "$\\Phi(x)=L\\left(x, \\lambda_*(x)\\right)$とします．ここで，$\\lambda_*(x)$が$(0, \\infty)^n$であり微分可能ならば，$\\nabla \\Phi(x)=L_x^{\\prime}\\left(x, \\lambda_*(x)\\right)$．\n",
    "\n",
    "証明は省略．\n",
    "\n",
    "---\n",
    "\n",
    "この定理から，$\\dot{x}=-L_x^{\\prime}\\left(x, \\lambda_*(x)\\right)$に沿って更新すれば，$\\lambda_*(x)$が有限であるなら，$\\Phi(x)$の最小値に収束することがわかります．\n",
    "\n",
    "$\\lambda_*(x)$はどうやって計算すればいいでしょうか？\n",
    "固定された$x$について，$\\dot{\\lambda}=L_\\lambda^{\\prime}(x, \\lambda)$を考えれば，これは$\\lambda_*(x)$に収束します．そこで，次のような更新を考えましょう（ここでW_k$とU_k$は適当な期待値ゼロのノイズです）\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& x_{k+1}-x_k=-a_k\\left(L_x^{\\prime}\\left(x_k, \\lambda_k\\right)+W_k\\right), \\\\\n",
    "& \\lambda_{k+1}-\\lambda_k=b_k\\left(L_\\lambda^{\\prime}\\left(x_k, \\lambda_k\\right)+U_k\\right),\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "また，$a_k \\ll b_k$として，それぞれ次の様にゼロに収束するとします．\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& a_k=o\\left(b_k\\right) \\quad k \\rightarrow \\infty, \\\\\n",
    "& \\sum_k a_k=\\sum_k b_k=\\infty, \\quad \\sum_k a_k^2<\\infty, \\sum_k b_k^2<\\infty . \\\\\n",
    "&\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "この更新方法は**two-timescale stochastic approximation**として知られています．\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}