notebooks/RL_CMDP_last_iterate_convergence.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Last iterate convergenceを保証するPrimal dual法\n",
    "\n",
    "参考：\n",
    "* [ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPs](https://arxiv.org/abs/2302.01275)\n",
    "* [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://arxiv.org/abs/2306.11700)：こっちをベースにします\n",
    "* なんで正則化入れるのか？みたいな話を[RL_CMDP_Lagrange_regularized.ipynb](RL_CMDP_Lagrange_regularized.ipynb)に書いてみました．\n",
    "\n",
    "CMDPにおいて，単純にprimal-dual法を実現しても実行可能な方策は得られません．\n",
    "簡単な手法は過去の方策の期待値を取る方法ですが，これはNNなどの関数近似が入ると難しいです．\n",
    "\n",
    "今回は方策勾配法を使ってlast-iterate convergenceを実現する方法を見てみましょう．\n",
    "\n",
    "表記：\n",
    "\n",
    "* 制約付きMDP：$\\underset{\\pi \\in \\Pi}{\\operatorname{maximize}} V_r^\\pi(\\rho) \\quad \\text { subject to } V_u^\\pi(\\rho) \\geq b$：\n",
    "* $g:=u-(1-\\gamma) b$とする\n",
    "* $L(\\pi, \\lambda):=V_r^\\pi(\\rho)+\\lambda V_g^\\pi(\\rho)$\n",
    "* ラグランジュ形式：$\\underset{\\pi \\in \\Pi}{\\operatorname{maximize}} \\underset{\\lambda \\in[0, \\infty]}{\\operatorname{minimize}} V_{r+\\lambda g}^\\pi(\\rho)$\n",
    "    * 鞍点$(\\pi', \\lambda')$：$V_{r+\\lambda^{\\prime} g}^\\pi(\\rho) \\leq V_{r+\\lambda^{\\prime} g}^{\\pi^{\\prime}}(\\rho) \\leq V_{r+\\lambda g}^{\\pi^{\\prime}}(\\rho)$\n",
    "\n",
    "\n",
    "**Last iterate convergenceの難しさ：**\n",
    "\n",
    "大きく３つあります\n",
    "1. Max側とMin側が非対称です．方策側は遷移についての最大化を目的としますが，$\\lambda$側は報酬を最小化します．\n",
    "2. 問題自体が非凸です． \n",
    "3. 全ての状態行動について最適な方策が鞍点にならないことがあります．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Last-iterate convergenceを達成するアルゴリズム\n",
    "\n",
    "\n",
    "次のように正則化されたラグランジアンを考えます：\n",
    "\n",
    "$$L_\\tau(\\pi, \\lambda):=V_{r+\\lambda g}^\\pi(\\rho)+\\tau\\left(\\mathcal{H}(\\pi)+\\frac{1}{2} \\lambda^2\\right)$$\n",
    "\n",
    "ここで，$\\mathcal{H}(\\pi):=(1-\\gamma) \\mathbb{E}\\left[\\sum_{t=0}^{\\infty}-\\gamma^t \\log \\pi\\left(a_t \\mid s_t\\right)\\right]$です．\n",
    "\n",
    "このラグランジアンには，次を満たす鞍点$(\\bar{\\pi}, \\bar{\\lambda}) \\in \\Pi \\times \\Lambda$が存在し，それは唯一存在します．\n",
    "任意の$\\pi \\in \\Pi$と$\\lambda \\in \\Lambda$について，\n",
    "\n",
    "$$\n",
    "L_\\tau(\\bar{\\pi}, \\lambda) \\geq L_\\tau(\\bar{\\pi}, \\bar{\\lambda}) \\geq L_\\tau(\\pi, \\bar{\\lambda})\n",
    "$$\n",
    "\n",
    "**証明**：Occupancy measureに直して適当に書けばいけます．\n",
    "\n",
    "\n",
    "---\n",
    "\n",
    "この唯一の鞍点を\n",
    "\n",
    "* $\\pi_\\tau^{\\star}=\\operatorname{argmax}_{\\pi \\in \\Pi} \\min _{\\lambda \\in \\Lambda} L_\\tau(\\pi, \\lambda)$\n",
    "* $\\lambda_\\tau^{\\star}=\\operatorname{argmin}_{\\lambda \\in \\Lambda} \\max _{\\pi \\in \\Pi} L_\\tau(\\pi, \\lambda)$\n",
    "\n",
    "としましょう．このとき，次が成立します．\n",
    "\n",
    "$$\n",
    "V_{r+\\lambda_\\tau^{\\star} g}^\\pi(\\rho)-\\tau \\mathcal{H}\\left(\\pi_\\tau^{\\star}\\right) \\leq V_{r+\\lambda_\\tau^{\\star} g}^{\\pi_\\tau^{\\star}}(\\rho) \\leq V_{r+\\lambda g}^{\\pi_\\tau^{\\star}}(\\rho)+\\frac{\\tau}{2} \\lambda^2 \\text { for all }(\\pi, \\lambda) \\in \\Pi \\times \\Lambda\n",
    "$$\n",
    "\n",
    "つまり，正則化された鞍点である$\\left(\\pi_\\tau^{\\star}, \\lambda_\\tau^{\\star}\\right)$は，もとのラグランジアンである$V_{r+\\lambda g}^\\pi(\\rho)$について，\n",
    "* $\\frac{\\tau}{2} \\lambda^2$\n",
    "* $\\tau \\mathcal{H}\\left(\\pi_\\tau^{\\star}\\right)$\n",
    "\n",
    "の２つについて誤差が生じた鞍点です．\n",
    "ここで，次のような更新を考えます\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\pi_{t+1}(\\cdot \\mid s) & =\\underset{\\pi(\\cdot \\mid s) \\in \\Delta(A)}{\\operatorname{argmax}}\\left\\{\\sum_a \\pi(a \\mid s) Q_{r+\\lambda_t g+\\tau \\psi_t}^{\\pi_t}(s, a)-\\frac{1}{\\eta} \\mathrm{KL}\\left(\\pi(\\cdot \\mid s), \\pi_t(\\cdot \\mid s)\\right)\\right\\} \\\\\n",
    "\\lambda_{t+1} & =\\underset{\\lambda \\in \\Lambda}{\\operatorname{argmin}}\\left\\{\\lambda\\left(V_g^{\\pi_t}(\\rho)+\\tau \\lambda_t\\right)+\\frac{1}{2 \\eta}\\left(\\lambda-\\lambda_t\\right)^2\\right\\},\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "つまり，\n",
    "* 方策側は$Q_{r+\\lambda_t g+\\tau \\psi_t}^{\\pi_t}(s, a)$の方向に対してMirror descentで更新します．\n",
    "* $\\lambda$側はprojected gradient descentで更新しています．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 解析\n",
    "\n",
    "次が成立します．\n",
    "\n",
    "---\n",
    "\n",
    "**定理**\n",
    "\n",
    "* $\\mathrm{KL}_t(\\rho):=\\sum_s d_\\rho^{\\pi_\\tau^{\\star}}(s) \\mathrm{KL}_t(s)$ \n",
    "* $\\mathrm{KL}_t(s):=\\mathrm{KL}\\left(\\pi_\\tau^{\\star}(\\cdot \\mid s), \\pi_t(\\cdot \\mid s)\\right)$\n",
    "* $\\Phi_t=\\mathrm{KL}_t(\\rho)+\\frac{1}{2}\\left(\\lambda_\\tau^{\\star}-\\lambda_t\\right)^2$\n",
    "\n",
    "として，$\\Phi_t$を$\\pi_t$と$\\lambda_t$の非最適性とします．\n",
    "このとき，次が成立します：\n",
    "\n",
    "$$\n",
    "\\Phi_{t+1} \\leq \\mathrm{e}^{-\\eta \\tau t} \\Phi_1+\\frac{\\eta}{\\tau} \\max \\left(\\left(C_{\\tau, \\xi}\\right)^2,\\left(C_{\\tau, \\xi}^{\\prime}\\right)^2\\right)\n",
    "$$\n",
    "\n",
    "ここで，\n",
    "$C_{\\tau, \\xi}:=(1+1 /((1-\\gamma) \\xi)+\\tau \\log |A|) /(1-\\gamma)$ \n",
    "および$C_{\\tau, \\xi}^{\\prime}:=(1+\\tau / \\xi) /(1-\\gamma)$\n",
    "です．\n",
    "\n",
    "---\n",
    "\n",
    "* 一項目は$t\\to \\infty$で線形に小さくなります．\n",
    "* 二項目は学習率$\\eta$と$\\tau$を調整することで小さくできます．\n",
    "\n",
    "実際，$\\eta=\\epsilon \\tau$とすれば，$t \\geq\\left(1 /\\left(\\epsilon \\tau^2\\right)\\right) \\log (1 / \\epsilon)$回の更新で$\\Phi_t=O(\\epsilon)$に収束します．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 証明\n",
    "\n",
    "まず，双対ギャップを次のように分解します：\n",
    "\n",
    "$$\n",
    "L_\\tau\\left(\\pi_\\tau^{\\star}, \\lambda_t\\right)-L_\\tau\\left(\\pi_t, \\lambda_\\tau^{\\star}\\right)=\\underbrace{L_\\tau\\left(\\pi_\\tau^{\\star}, \\lambda_t\\right)-L_\\tau\\left(\\pi_t, \\lambda_t\\right)}_{(\\mathrm{i})}+\\underbrace{L_\\tau\\left(\\pi_t, \\lambda_t\\right)-L_\\tau\\left(\\pi_t, \\lambda_\\tau^{\\star}\\right)}_{(\\mathrm{ii})}\n",
    "$$\n",
    "\n",
    "**(i)項目のバウンド**\n",
    "\n",
    "ここで，エントロピーは次で書けることに注意します．\n",
    "\n",
    "$$\n",
    "\\mathcal{H}(\\pi):=(1-\\gamma) \\mathbb{E}\\left[\\sum_{t=0}^{\\infty}-\\gamma^t \\log \\pi\\left(a_t \\mid s_t\\right)\\right]=-\\sum_{s, a} d_\\rho^\\pi(s) \\pi(a \\mid s) \\log \\pi(a \\mid s)\n",
    "$$\n",
    "\n",
    "すると，最初の項は\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "&L_\\tau\\left(\\pi_\\tau^{\\star}, \\lambda_t\\right)-L_\\tau\\left(\\pi_t, \\lambda_t\\right) \\\\\n",
    "= & V_{r+\\lambda_t g}^{\\pi_\\tau^{\\star}}(\\rho)-V_{r+\\lambda_t g}^{\\pi_t}(\\rho) \\\\\n",
    "& -\\tau \\sum_{s, a} d_\\rho^{\\pi_\\tau^{\\star}}(s) \\pi_\\tau^{\\star}(a \\mid s) \\log \\pi_\\tau^{\\star}(a \\mid s)+\\tau \\sum_{s, a} d_\\rho^{\\pi_t}(s) \\pi_t(a \\mid s) \\log \\pi_t(a \\mid s) \\\\\n",
    "= & V_{r+\\lambda_t g+\\tau \\psi_t}^{\\pi_\\tau^{\\star}}(\\rho)-V_{r+\\lambda_t g+\\tau \\psi_t}^{\\pi_t}(\\rho)-\\tau V_{\\psi_t}^{\\pi_\\tau^{\\star}}(\\rho)+\\tau V_{\\psi_t}^{\\pi_t}(\\rho) \\\\\n",
    "& -\\tau \\sum_{s, a} d_\\rho^{\\pi_\\tau^{\\star}}(s) \\pi_\\tau^{\\star}(a \\mid s) \\log \\pi_\\tau^{\\star}(a \\mid s)+\\tau \\sum_{s, a} d_\\rho^{\\pi_t}(s) \\pi_t(a \\mid s) \\log \\pi_t(a \\mid s)\\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "さらに[RL_useful_lemma.ipynb](RL_useful_lemma.ipynb)の\n",
    "**補題: Extended Value Difference**を使うと，\n",
    "$$\n",
    "\\begin{aligned}\n",
    "= & \\sum_{s, a} d_\\rho^{\\pi_\\tau^{\\star}}(s)\\left(\\pi_\\tau^{\\star}(a \\mid s)-\\pi_t(a \\mid s)\\right) Q_{r+\\lambda_t g+\\tau \\psi_t}^{\\pi_t}(s, a) \\\\\n",
    "& +\\tau \\sum_{s, a} d_\\rho^{\\pi_\\tau^{\\star}}(s) \\pi_\\tau^{\\star}(a \\mid s) \\log \\pi_t(a \\mid s)-\\tau \\sum_{s, a} d_\\rho^{\\pi_t}(s) \\pi_t(a \\mid s) \\log \\pi_t(a \\mid s) \\\\\n",
    "& -\\tau \\sum_{s, a} d_\\rho^{\\pi_\\tau^{\\star}}(s) \\pi_\\tau^{\\star}(a \\mid s) \\log \\pi_\\tau^{\\star}(a \\mid s)+\\tau \\sum_{s, a} d_\\rho^{\\pi_t}(s) \\pi_t(a \\mid s) \\log \\pi_t(a \\mid s)\\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "として変形できます．\n",
    "ここで，[RL_useful_lemma.ipynb](RL_useful_lemma.ipynb)の**補題：Mirror descentをKLで抑える**を使えば，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& =\\sum_{s, a} d_\\rho^{\\pi_\\tau^{\\star}}(s)\\left(\\pi_\\tau^{\\star}(a \\mid s)-\\pi_t(a \\mid s)\\right) Q_{r+\\lambda_t g+\\tau \\psi_t}^{\\pi_t}(s, a)-\\tau \\sum_s d_\\rho^{\\pi_\\tau^{\\star}}(s) \\mathrm{KL}_t(s) \\\\\n",
    "& \\leq \\sum_s d_\\rho^{\\pi_\\tau^{\\star}}(s)\\left(\\frac{\\mathrm{KL}_t(s)-\\mathrm{KL}_{t+1}(s)}{\\eta}\\right)+\\eta\\left(C_{\\tau, \\xi}\\right)^2-\\tau \\sum_s d_\\rho^{\\pi_\\tau^{\\star}}(s) \\mathrm{KL}_t(s) \\\\\n",
    "& =\\sum_s d_\\rho^{\\pi_\\tau^{\\star}}(s)\\left(\\frac{(1-\\eta \\tau) \\mathrm{KL}_t(s)-\\mathrm{KL}_{t+1}(s)}{\\eta}\\right)+\\eta\\left(C_{\\tau, \\xi}\\right)^2 \\\\\n",
    "& =\\frac{(1-\\eta \\tau) \\mathrm{KL}_t(\\rho)-\\mathrm{KL}_{t+1}(\\rho)}{\\eta}+\\eta\\left(C_{\\tau, \\xi}\\right)^2 .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "ここで，$Q_{r+\\lambda_t g+\\tau \\psi_t}^{\\pi_t}(s, a) \\leq \\frac{1}{1-\\gamma}\\left(1+\\frac{1}{(1-\\gamma) \\xi}+\\tau \\log |A|\\right):=C_{\\tau, \\xi}$としました．\n",
    "\n",
    "---\n",
    "\n",
    "**注意**\n",
    "\n",
    "これは元論文のミス！\n",
    "$-\\log \\pi_t(a \\mid s)$は$\\log |A|$で明らかにバウンドできない．\n",
    "これは[Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit FeedbackのLemma１１](https://arxiv.org/abs/2303.02738)を使って丁寧にバウンドしないといけない．\n",
    "\n",
    "---\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(ii)項目のバウンド**\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& L_\\tau\\left(\\pi_t, \\lambda_t\\right)-L_\\tau\\left(\\pi_t, \\lambda_\\tau^{\\star}\\right) \\\\\n",
    "& =V_{r+\\lambda_t g}^{\\pi_t}(\\rho)-V_{r+\\lambda_\\tau^{\\star} g}^{\\pi_t}(\\rho)+\\frac{1}{2} \\tau\\left(\\lambda_t\\right)^2-\\frac{1}{2} \\tau\\left(\\lambda_\\tau^{\\star}\\right)^2 \\\\\n",
    "& =\\left(\\lambda_t-\\lambda_\\tau^{\\star}\\right) V_g^{\\pi_t}(\\rho)+\\frac{1}{2} \\tau\\left(\\lambda_t\\right)^2-\\frac{1}{2} \\tau\\left(\\lambda_\\tau^{\\star}\\right)^2\\\\\n",
    "& =\\left(\\lambda_t-\\lambda_\\tau^{\\star}\\right)\\left(V_g^{\\pi_t}(\\rho)+\\tau \\lambda_t\\right)-\\frac{1}{2} \\tau\\left(\\lambda_t-\\lambda_\\tau^{\\star}\\right)^2 \\\\\n",
    "& \\leq \\frac{\\left(\\lambda_\\tau^{\\star}-\\lambda_t\\right)^2-\\left(\\lambda_\\tau^{\\star}-\\lambda_{t+1}\\right)^2}{2 \\eta}+\\frac{1}{2} \\eta\\left(C_{\\tau, \\xi}^{\\prime}\\right)^2-\\frac{1}{2} \\tau\\left(\\lambda_t-\\lambda_\\tau^{\\star}\\right)^2 \\\\\n",
    "& =\\frac{(1-\\eta \\tau)\\left(\\lambda_\\tau^{\\star}-\\lambda_t\\right)^2-\\left(\\lambda_\\tau^{\\star}-\\lambda_{t+1}\\right)^2}{2 \\eta}+\\frac{1}{2} \\eta\\left(C_{\\tau, \\xi}^{\\prime}\\right)^2\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "ここで，不等式は$V_g^{\\pi_t}(\\rho)+\\tau \\lambda_t \\leq \\frac{1}{1-\\gamma}\\left(1+\\frac{\\tau}{\\xi}\\right):=C_{\\tau, \\xi}^{\\prime}$と，[勾配降下の話](OPT_gradient.ipynb)を使いました．（ここで$\\lambda$の凸性を使ってる？）\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定義\n",
    "$\\Phi_t:=\\mathrm{KL}_t(\\rho)+\\frac{1}{2}\\left(\\lambda_\\tau^{\\star}-\\lambda_t\\right)^2$\n",
    "に従って，上の不等式を合体させれば，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\Phi_{t+1} & \\leq(1-\\eta \\tau) \\Phi_t-\\eta\\left(L_\\tau\\left(\\pi_\\tau^{\\star}, \\lambda_t\\right)-L_\\tau\\left(\\pi_t, \\lambda_\\tau^{\\star}\\right)\\right)+\\eta^2 \\max \\left(\\left(C_{\\tau, \\xi}\\right)^2,\\left(C_{\\tau, \\xi}^{\\prime}\\right)^2\\right) \\\\\n",
    "& \\leq(1-\\eta \\tau) \\Phi_t+\\eta^2 \\max \\left(\\left(C_{\\tau, \\xi}\\right)^2,\\left(C_{\\tau, \\xi}^{\\prime}\\right)^2\\right) .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が得られます．これを再帰的に繰り返して，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\Phi_{t+1} & \\leq(1-\\eta \\tau) \\Phi_t+\\eta^2 \\max \\left(\\left(C_{\\tau, \\xi}\\right)^2,\\left(C_{\\tau, \\xi}^{\\prime}\\right)^2\\right) \\\\\n",
    "& \\leq(1-\\eta \\tau)^2 \\Phi_{t-1}+\\left(\\eta^2+\\eta^2(1-\\eta \\tau)\\right) \\max \\left(\\left(C_{\\tau, \\xi}\\right)^2,\\left(C_{\\tau, \\xi}^{\\prime}\\right)^2\\right) \\\\\n",
    "& \\leq \\cdots \\\\\n",
    "& \\leq(1-\\eta \\tau)^t \\Phi_1+\\left(\\eta^2\\left(1+(1-\\eta \\tau)+(1-\\eta \\tau)^2+\\cdots\\right)\\right) \\max \\left(\\left(C_{\\tau, \\xi}\\right)^2,\\left(C_{\\tau, \\xi}^{\\prime}\\right)^2\\right) \\\\\n",
    "& \\leq(1-\\eta \\tau)^t \\Phi_1+\\frac{\\eta}{\\tau} \\max \\left(\\left(C_{\\tau, \\xi}\\right)^2,\\left(C_{\\tau, \\xi}^{\\prime}\\right)^2\\right) \\\\\n",
    "& \\leq \\mathrm{e}^{-\\eta \\tau t} \\Phi_1+\\frac{\\eta}{\\tau} \\max \\left(\\left(C_{\\tau, \\xi}\\right)^2,\\left(C_{\\tau, \\xi}^{\\prime}\\right)^2\\right)\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "を得ます．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $\\Phi$からsub-optimalityへの変換\n",
    "\n",
    "次が成立します．\n",
    "\n",
    "---\n",
    "\n",
    "十分小さい$\\epsilon > 0$について，$\\eta=\\Theta\\left(\\epsilon^4\\right)$\n",
    "および\n",
    "$\\tau=\\Theta\\left(\\epsilon^2\\right)$\n",
    "のとき，\n",
    "\n",
    "$$\n",
    "V_r^{\\pi^{\\star}}(\\rho)-V_r^{\\pi_t}(\\rho) \\leq \\epsilon \\text { and }-V_g^{\\pi_t}(\\rho) \\leq \\epsilon \\text { for any } t=\\Omega\\left(\\frac{1}{\\epsilon^6} \\log ^2 \\frac{1}{\\epsilon}\\right)\n",
    "$$\n",
    "\n",
    "が成立します．\n",
    "\n",
    "**証明**\n",
    "\n",
    "$\\tau=\\Theta(\\epsilon)$ と$\\eta=\\Theta\\left(\\epsilon^2\\right)$のとき，$t=\\Omega\\left(\\frac{1}{\\epsilon^3} \\log \\frac{1}{\\epsilon}\\right)$について，$\\Phi_{t+1}=O(\\epsilon)$であることはすぐにわかります．\n",
    "\n",
    "このような$t$について，$\\left(\\pi_t, \\lambda_t\\right)$を考えましょう．\n",
    "\n",
    "$\\Phi$の定義から，\n",
    "$$\\mathrm{KL}_t(\\rho)=O(\\epsilon)\\; \\text{ and } \\frac{1}{2}\\left(\\lambda_\\tau^{\\star}-\\lambda_t\\right)^2=O(\\epsilon)$$\n",
    "です．\n",
    "\n",
    "suboptimalityをバウンドしましょう．まず，\n",
    "\n",
    "$$\n",
    "V_r^{\\pi^{\\star}}(\\rho)-V_r^{\\pi_t}(\\rho)=\\underbrace{V_r^{\\pi^{\\star}}(\\rho)-V_r^{\\pi_\\tau^{\\star}}(\\rho)}_{(\\mathrm{i})}+\\underbrace{V_r^{\\pi_\\tau^{\\star}}(\\rho)-V_r^{\\pi_t}(\\rho)}_{(\\mathrm{ii})} .\n",
    "$$\n",
    "\n",
    "です．\n",
    "\n",
    "**(ii)のバウンド**\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\text { (ii) } & =\\sum_{s, a} d_\\rho^{\\pi_\\tau^{\\star}}(s)\\left(\\pi_\\tau^{\\star}(a \\mid s)-\\pi_t(a \\mid s)\\right) Q_r^{\\pi_t}(s, a) \\\\\n",
    "& \\leq \\frac{1}{1-\\gamma} \\sum_s d_\\rho^{\\pi_\\tau^{\\star}}(s)\\left\\|\\pi_\\tau^{\\star}(\\cdot \\mid s)-\\pi_t(\\cdot \\mid s)\\right\\|_1 \\\\\n",
    "& \\leq \\frac{1}{1-\\gamma} \\sum_s d_\\rho^{\\pi_\\tau^{\\star}}(s) \\sqrt{2 \\mathrm{KL}_t(s)} \\\\\n",
    "& \\leq \\frac{1}{1-\\gamma} \\sqrt{2 \\sum_s d_\\rho^{\\pi_\\tau^{\\star}}(s) \\mathrm{KL}_t(s)} \\\\\n",
    "& =\\frac{1}{1-\\gamma} \\sqrt{2 \\mathrm{KL}_t(\\rho)}\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成り立ちます．\n",
    "$\\mathrm{KL}_t(\\rho)=O(\\epsilon)$なので，(ii)$\\leq O(\\sqrt{\\epsilon})$です．\n",
    "\n",
    "**(i)のバウンド**\n",
    "\n",
    "エントロピー正則化の性質から，\n",
    "$$\n",
    "V_r^{\\pi^{\\star}}(\\rho)-\\tau \\mathcal{H}\\left(\\pi_\\tau^{\\star}\\right) \\leq V_r^{\\pi_\\tau^{\\star}}(\\rho)+\\lambda_\\tau^{\\star}\\left(V_g^{\\pi_\\tau^{\\star}}(\\rho)-V_g^{\\pi^{\\star}}(\\rho)\\right)\n",
    "$$\n",
    "\n",
    "であり，これを利用すると\n",
    "\n",
    "$$\n",
    "(\\mathrm{i})=V_r^{\\pi^{\\star}}(\\rho)-V_r^{\\pi_\\tau^{\\star}}(\\rho) \\leq \\tau \\mathcal{H}\\left(\\pi_\\tau^{\\star}\\right)\n",
    "$$\n",
    "\n",
    "がすぐにわかります．$\\tau=\\Theta(\\epsilon)$とすれば$V_r^{\\pi^{\\star}}(\\rho)-V_r^{\\pi_t}(\\rho) \\leq O(\\sqrt{\\epsilon})$が得られます．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}