notebooks/RL_CMDP_DOPE.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DOPEによる違反なしの探索\n",
    "\n",
    "**コメント**：多分Optimismのところ間違ってるかも．DOPEでは推定した$\\widehat{P}$を中心とした信頼区間からOptimisticな$P$も線型計画法で計算するが，そのときにValidな$P$が出てくる保証がなさそう．確率分布が出てこないと，Occupancy measureの存在も保証されなさそうである．\n",
    "\n",
    "参考\n",
    "* [DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning](https://arxiv.org/abs/2112.00885)\n",
    "\n",
    "\n",
    "表記\n",
    "* 論文参照．また，[RL_CMDP_explore_exploit.ipynb](RL_CMDP_explore_exploit.ipynb)とだいたい同じ\n",
    "* $\\pi^0$は$V_1^{\\pi^0}(\\mu ; c, P)=c^0<\\tau$を満たすときにStrictly safeといいます．\n",
    "* $\\Pi_{\\text {safe }}=\\left\\{\\pi: V_c^\\pi(P) \\leq \\bar{C}\\right\\}$とします．\n",
    "\n",
    "次のCMDPを考えます．報酬とコストは既知とします．\n",
    "\n",
    "$$\n",
    "\\min _\\pi \\quad V_r^\\pi(P) \\quad \\text { s.t. } \\quad V_c^\\pi(P) \\leq \\bar{C}\n",
    "$$\n",
    "\n",
    "仮定\n",
    "* $V_c^{\\pi_b}(P)=\\bar{C}_b$, where $\\bar{C}_b<\\bar{C}$を満たす$\\pi_b$が存在するとします．また，$C_b$は既知とします．\n",
    "* 多分$\\bar{C}_b$は既知じゃなくても，最初に$\\pi_b$を数回走らせて計算すれば良いです．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Good Event\n",
    "\n",
    "**遷移についての信頼区間**\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\beta_{h, k}^p\\left(s, a, s^{\\prime}\\right)=\\sqrt{\\frac{4 \\operatorname{Var}\\left(\\widehat{P}_{h, k}\\left(s^{\\prime} \\mid s, a\\right)\\right) \\log \\left(\\frac{2 S A K H}{\\delta}\\right)}{n_{h, k}(s, a) \\vee 1}}+\\frac{14 \\log \\left(\\frac{2 S A K H}{\\delta}\\right)}{\\left.3\\left(n_{h, k}(s, a) \\vee 1\\right)\\right)} \\\\\n",
    "& \\mathcal{P}_{h, k}(s, a)=\\left\\{P^{\\prime}:\\left|P_h^{\\prime}\\left(s^{\\prime} \\mid s, a\\right)-\\widehat{P}_{h, k}\\left(s^{\\prime} \\mid s, a\\right)\\right| \\leq \\beta_{h, k}^p\\left(s, a, s^{\\prime}\\right), \\forall s^{\\prime} \\in \\mathcal{S}\\right\\}\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "を遷移についての信頼区間とします．Eventを\n",
    "$$\n",
    "F^p=\\left\\{P \\in \\mathcal{P}_k, \\forall k \\in[K]\\right\\}\n",
    "$$\n",
    "とすると，Bernsteinの不等式から次が言えます．\n",
    "$$\n",
    "\\mathbb{P}\\left(F^p\\right) \\geq 1-2 \\delta\n",
    "$$\n",
    "\n",
    "**Nice Episode**\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& F^w \\\\\n",
    "& =\\left\\{n_{h, k}(s, a) \\geq \\frac{1}{2} \\sum_{j<k} w_{h, j}(s, a)-H \\log \\frac{S A H}{\\delta}, \\forall\\left(h, s, a, s^{\\prime}, k\\right) \\in[H] \\times \\mathcal{S} \\times \\mathcal{A} \\times \\mathcal{S} \\times[K]\\right\\}\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "とします．ここで$w_{h, j}$はエピソード$j$でのOccupancy Measureです．\n",
    "このとき，[RL_useful_lemma.ipynb](RL_useful_lemma.ipynb)でやったように，$\\mathbb{P}\\left(F^w\\right) \\geq 1-\\delta$が成り立ちます．\n",
    "\n",
    "以上を踏まえて，GoodEventを$G=F^p \\cap F^w$とすると，$\\mathbb{P}(G) \\geq 1-3 \\delta$が成り立ちます．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## アルゴリズム\n",
    "\n",
    "**報酬とコスト**\n",
    "\n",
    "DOPEでは次の報酬とコストを考えます．\n",
    "\n",
    "* $\\bar{\\beta}_{h, k}^p(s, a)=\\sum_{s^{\\prime} \\in \\mathcal{S}} \\beta_{h, k}^p\\left(s, a, s^{\\prime}\\right)$とします\n",
    "* コスト：$\\bar{c}_{h, k}(s, a)={c}_{h}(s, a) + H \\bar{\\beta}_{h, k}^p(s, a)$ \n",
    "* 報酬：$\\bar{r}_{h, k}(s, a)={r}_{h}(s, a)-\\frac{H^2}{\\bar{C}-\\bar{C}_b} \\bar{\\beta}_{h, k}^p(s, a)$.\n",
    "\n",
    "そして，方策を\n",
    "\n",
    "$$\n",
    "\\left(\\pi_k, P_k\\right)=\\underset{\\pi^{\\prime}, P^{\\prime} \\in \\mathcal{P}_k}{\\arg \\min } V_{\\bar{r}_k}^{\\pi^{\\prime}}\\left(P^{\\prime}\\right) \\text { s.t. } V_{\\bar{c}_k}^{\\pi^{\\prime}}\\left(P^{\\prime}\\right) \\leq \\bar{C} .\n",
    "$$\n",
    "\n",
    "によって選択します．\n",
    "\n",
    "**違反なしの工夫**\n",
    "\n",
    "最初の$K_o$エピソードは安全な方策$\\pi_b$によって十分なデータを集めます．ここで$K_o=\\tilde{\\mathcal{O}}\\left(\\frac{S^2 A H^4}{\\left(\\bar{C}-\\bar{C}_b\\right)^2}\\right)$とします．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 便利な補題\n",
    "\n",
    "準備\n",
    "* $\\epsilon_k^{\\pi}\\left(P\\right)=H \\mathbb{E}\\left[\\sum_{h=1}^H \\bar{\\beta}_{h, k}^p\\left(s_{h, k}, a_{h, k}\\right) \\mid \\pi, P, \\mathcal{F}_{k-1}\\right]$\n",
    "* $V_{\\bar{c}_k}^{\\pi}\\left(P\\right)=V_{{c}}^{\\pi}\\left(P\\right)+\\epsilon_k^{\\pi}(P)$\n",
    "* $V_{\\bar{r}_k}^{\\pi}\\left(P\\right)=V_{{r}}^{\\pi}\\left(P\\right)-\\frac{H}{\\bar{C}-\\bar{C}_b} \\epsilon_k^{\\pi}\\left(P\\right)$\n",
    "\n",
    "とします．\n",
    "\n",
    "Good Eventが成立するとき，次が成立します．（Nice Episodeについての話は[RL_useful_lemma.ipynb](RL_useful_lemma.ipynb)に任せます．\n",
    "\n",
    "---\n",
    "\n",
    "**補題(Lemma 15)**\n",
    "\n",
    "$G$が成立するとき，任意の$P' \\in \\mathcal{P}_k$について，\n",
    "\n",
    "$$\n",
    "\\left|P_h^{\\prime}\\left(s^{\\prime} \\mid s, a\\right)-P_h\\left(s^{\\prime} \\mid s, a\\right)\\right| \\leq C_1 \\sqrt{\\frac{P_h\\left(s^{\\prime} \\mid s, a\\right) L}{n_{h, k}(s, a) \\vee 1}}+C_2 \\frac{L}{n_{h, k}(s, a) \\vee 1}\n",
    "$$\n",
    "\n",
    "を満たす定数$C_1, C_2 > 0$が存在します．\n",
    "\n",
    "---\n",
    "\n",
    "**補題：$\\sum_k \\epsilon_k$のバウンド**\n",
    "\n",
    "GoodEventが成立しているとします．\n",
    "Niceエピソードの話と$\\beta^p$の定義から，\n",
    "$$\\sum_{k=1}^{K^{\\prime}} \\epsilon_k^{\\pi_k}(P) \\leq \\tilde{\\mathcal{O}}\\left(S \\sqrt{A H^4 K^{\\prime}}\\right)$$\n",
    "が成立します．\n",
    "\n",
    "---\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**補題：$\\pi_b$が実行可能解になるエピソード**\n",
    "\n",
    "Good Eventが成立するとき，$k \\geq K_o$について，$(\\pi_b, P)$は\n",
    "\n",
    "$$\n",
    "\\left(\\pi_k, P_k\\right)=\\underset{\\pi^{\\prime}, P^{\\prime} \\in \\mathcal{P}_k}{\\arg \\min } V_{\\bar{r}_k}^{\\pi^{\\prime}}\\left(P^{\\prime}\\right) \\text { s.t. } V_{\\bar{c}_k}^{\\pi^{\\prime}}\\left(P^{\\prime}\\right) \\leq \\bar{C} .\n",
    "$$\n",
    "\n",
    "の実行可能解になります．\n",
    "\n",
    "**証明**\n",
    "\n",
    "$\\pi_b$が実行可能解のとき，\n",
    "$$\n",
    "V_{\\bar{c}_k}^{\\pi_b}\\left(P\\right)\n",
    "=V_{{c}}^{\\pi_b}\\left(P\\right)+\\epsilon_k^{\\pi_b}(P)\n",
    "=\\bar{C}_b+\\epsilon_k^{\\pi_b}(P) \\leq \\bar{C}\n",
    "$$\n",
    "なので，\n",
    "$\\pi_b$が実行可能解であることの十分条件は\n",
    "\n",
    "$$\n",
    "\\epsilon_k^{\\pi_b}(P) \\leq (\\bar{C} - \\bar{C}_b)\n",
    "$$\n",
    "\n",
    "です．\n",
    "ここで，最初の$k \\leq K_o$エピソードでは$\\pi_k=\\pi_b$であることを思い出しましょう．\n",
    "よって，\n",
    "$$\\sum_{k=1}^{K_o} \\epsilon_k^{\\pi_b}(P) \\leq \\tilde{\\mathcal{O}}\\left(S \\sqrt{A H^4 K_o}\\right)$$\n",
    "\n",
    "が成り立ちます．$k \\leq K_o$まで$\\epsilon_k^{\\pi_b}(P) > (\\bar{C} - \\bar{C}_b)$であるとしましょう．\n",
    "すると，\n",
    "\n",
    "$$K_o(\\bar{C} - \\bar{C}_b) < \\sum_{k=1}^{K_o} \\epsilon_k^{\\pi_b}(P) \\leq \\tilde{\\mathcal{O}}\\left(S \\sqrt{A H^4 K_o}\\right)$$\n",
    "\n",
    "この不等式は$K_o \\geq \\tilde{\\mathcal{O}}\\left(\\frac{S^2 A H^4}{\\left(\\bar{C}-\\bar{C}_b\\right)^2}\\right)$では成立しません．よって，\n",
    "任意の$k \\geq K_o \\geq \\tilde{\\mathcal{O}}\\left(\\frac{S^2 A H^4}{\\left(\\bar{C}-\\bar{C}_b\\right)^2}\\right)$\n",
    "エピソードについては\n",
    "$\\epsilon_k^{\\pi_b}(P) \\leq (\\bar{C} - \\bar{C}_b)$である必要があります．以上から，$(\\pi_b, P)$は$k \\geq K_o$について実行可能解です．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "---\n",
    "\n",
    "**補題：$\\pi_k$は常に安全**\n",
    "\n",
    "GoodEventが成立しているとします．このとき，任意の$k$について$\\pi_k$は安全です．\n",
    "\n",
    "**証明**\n",
    "\n",
    "$k \\leq K_o$は$\\pi_b$を選択するので常に安全です．\n",
    "$k \\geq K_o$を考えてみましょう．\n",
    "\n",
    "上の補題より，$k \\geq K_o$でアルゴリズム中の最適化問題には実行可能解が存在します．\n",
    "また，$\\pi_k$の定義より，$V_{\\bar{c}_k}^{\\pi_k}\\left(P_k\\right) \\leq \\bar{C}$です．\n",
    "\n",
    "ここで，価値差分方程式より，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "V_c^{\\pi_k}(P)-V_c^{\\pi_k}\\left(P_k\\right) & =\\mathbb{E}\\left[\\sum_{h=1}^H\\left(\\left(P_h-P_{h, k}\\right)\\left(\\cdot \\mid s_{h, k}, a_{h, k}\\right)\\right)^{\\top} V_{c, h+1}^{\\pi_k}(\\cdot ; P) \\mid \\pi_k, P_k, \\mathcal{F}_{k-1}\\right] \\\\\n",
    "& \\stackrel{(a)}{\\leq} \\mathbb{E}\\left[\\sum_{h=1}^H\\left\\|\\left(\\left(P_h-P_{h, k}\\right)\\left(\\cdot \\mid s_{h, k}, a_{h, k}\\right)\\right)\\right\\|_1\\left\\|V_{c, h+1}^{\\pi_k}(\\cdot ; P)\\right\\|_{\\infty} \\mid \\pi_k, P_k, \\mathcal{F}_{k-1}\\right] \\\\\n",
    "& \\stackrel{(b)}{\\leq} H \\mathbb{E}\\left[\\sum^H \\bar{\\beta}_{h, k}^p\\left(s_{h, k}, a_{h, k}\\right) \\mid \\pi_k, P_k, \\mathcal{F}_{k-1}\\right]=\\epsilon_k^{\\pi_k}\\left(P_k\\right) .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成り立ちます．(a)はHolderの不等式，(b)はGoodEventを使ってます．\n",
    "変形して\n",
    "\n",
    "$$\n",
    "V_c^{\\pi_k}(P) \\leq V_c^{\\pi_k}\\left(P_k\\right)+\\epsilon_k^{\\pi_k}\\left(P_k\\right)\n",
    "=V_{\\bar{c}_k}^{\\pi_k}\\left(P_k\\right) \\leq \\bar{C}\n",
    "$$\n",
    "\n",
    "が成立します．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "---\n",
    "\n",
    "**補題：Optimism**\n",
    "\n",
    "$V_{\\bar{r}_k}^{\\pi_k}\\left(P_k\\right) \\leq V_{\\bar{r}_k}^{\\pi_k}\\left(P\\right) \\leq V_r^{\\pi^*}(P)$が成立します．\n",
    "$V_{\\bar{r}_k}^{\\pi_k}\\left(P_k\\right) \\leq V_{\\bar{r}_k}^{\\pi_k}\\left(P\\right)$は明らかなので，右側の不等式だけ証明しましょう．\n",
    "\n",
    "**方針**：$V_{\\tilde{r}_k}^{\\tilde{\\pi}_k}\\left(P\\right) \\leq V_{\\tilde{r}_k}^{\\tilde{\\pi}}(P) \\leq V_r^{\\pi^*}(P)$を満たすような実行可能解$\\widetilde{\\pi}$を見つければ良いです．\n",
    "\n",
    "\n",
    "**証明**\n",
    "\n",
    "$\\tilde{r}_h^k(s, a)=\\hat{r}_h(s, a) - b H \\bar{\\beta}_{h, k}^p(s, a)$として，\n",
    "\n",
    "$$\n",
    "\\tilde{\\pi}_k=\\underset{\\pi^{\\prime}}{\\arg \\min } V_{\\tilde{r}_k}^{\\pi^{\\prime}}\\left(P\\right) \\text { subject to } V_{\\bar{c}_k}^{\\pi^{\\prime}}\\left(P\\right) \\leq \\bar{C},\n",
    "$$\n",
    "\n",
    "を考えてみます．これは$b=\\frac{H}{\\bar{C} - \\bar{C}_b}$のときに$\\pi_k$と同じです．\n",
    "\n",
    "ここで，$\\alpha_k > 0$について，\n",
    "\n",
    "$$\n",
    "\\tilde{w}_h(s, a)=(1-\\alpha_k) w_h^{\\pi_b}(s, a ; P)+\\alpha_k w_h^{\\pi^*}(s, a ; P)\n",
    "$$\n",
    "\n",
    "なるOccupancy measureを考えてみます．Occupancy measureの集合の凸性から，$\\tilde{w}=w^{\\tilde{\\pi}}$である方策$\\tilde{\\pi}$ が存在します．\n",
    "ここで，次が成立します：\n",
    "\n",
    "**ステップ１**\n",
    "\n",
    "$$\n",
    "\\alpha_k \\leq \\frac{\\bar{C}-\\bar{C}_b-\\epsilon_k^{\\pi_b}(P)}{\\bar{C}-\\bar{C}_b+\\epsilon_k^{\\pi^*}(P)-\\epsilon_k^{\\pi_b}(P)}\n",
    "$$\n",
    "\n",
    "ならば$\\tilde{\\pi}$は\n",
    "$\n",
    "V_{\\bar{c}_k}^{\\tilde{\\pi}}\\left(P\\right) \\leq \\bar{C}\n",
    "$を満たします．\n",
    "\n",
    "**証明**\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& V_{\\bar{c}_k}^{\\tilde{\\pi}}(P)=\\left(1-\\alpha_k\\right) V_{\\bar{c}_k}^{\\pi_b}(P)+\\alpha_k V_{\\bar{c}_k}^{\\pi^*}(P) \\\\\n",
    "& =\\left(1-\\alpha_k\\right)\\left(V_{{c}}^{\\pi_b}(P)+\\epsilon_k^{\\pi_b}(P)\\right)+\\alpha_k\\left(V_{{c}}^{\\pi^*}(P)+\\epsilon_k^{\\pi^*}(P)\\right) \\\\\n",
    "& \\leq\\left(1-\\alpha_k\\right)\\left(\\bar{C}_b+\\epsilon_k^{\\pi_b}(P)\\right)+\\alpha_k\\left(\\bar{C}+\\epsilon_k^{\\pi^*}(P)\\right)\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "これを$\\leq\\bar{C}$として$\\alpha_k$について解けば補題が成立します．\n",
    "\n",
    "**ステップ２**\n",
    "\n",
    "$b \\geq \\frac{H}{\\bar{C}-\\bar{C}_b}$であれば，$V_{\\tilde{r}_k}^{\\tilde{\\pi}_k}\\left(P\\right) \\leq V_r^{\\pi^*}(P)$が成立します．\n",
    "\n",
    "**証明**\n",
    "\n",
    "ステップ１より，$V_{\\tilde{r}_k}^{\\tilde{\\pi}_k}\\left(P\\right) \\leq V_{\\tilde{r}_k}^{\\tilde{\\pi}}(P)$が成立します．\n",
    "よって，$V_{\\tilde{r}_k}^{\\tilde{\\pi}}(P) \\leq V_r^{\\pi^*}(P)$となるような$b$を見つければ良いです．\n",
    "つまり，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "V_{\\tilde{r}_k}^{\\tilde{\\pi}}(P)\n",
    "&=\n",
    "V_{r}^{\\tilde{\\pi}}(P)-b \\epsilon_k^{\\tilde{\\pi}}(P) \\\\\n",
    "&=\\left(1-\\alpha_k\\right)\\left(V_{{r}}^{\\pi_b}(P)-b \\epsilon_k^{\\pi_b}(P)\\right)+\\alpha_k\\left(V_{{r}}^{\\pi^*}(P)-b \\epsilon_k^{\\pi^*}(P)\\right) \n",
    "\\leq V^{\\pi^*}_r(P)\n",
    "\\end{aligned}\n",
    "$$\n",
    "を満たす$b$を見つけます．\n",
    "変形して，\n",
    "\n",
    "$$\n",
    "b \\geq \\frac{V_r^{\\pi_b}(P)-V_r^{\\pi^*}(P)}{\\epsilon_k^{\\pi_b}(P)+\\frac{\\alpha_k}{1-\\alpha_k}\\epsilon_k^{\\pi^*}(P)}\n",
    "$$\n",
    "\n",
    "ステップ１の$\\alpha_k$を持ってくると，$\\frac{\\alpha_k}{1-\\alpha_k}=\\frac{\\bar{C}-\\bar{C}_b-\\epsilon_k^{\\pi_b}(P)}{\\epsilon_k^{\\pi^*}(P)}$\n",
    "なので，代入して\n",
    "\n",
    "$$\n",
    "b \\geq \n",
    "\\frac{V_r^{\\pi_b}(P)-V_r^{\\pi^*}(P)}{\\bar{C}-\\bar{C}_b}\n",
    "$$\n",
    "\n",
    "であればよいです．\n",
    "Optimismはこれで明らかに成立します．\n",
    "\n",
    "**コメント**\n",
    "\n",
    "$\\Pi_k$を実行可能なPessimisticな方策の集合としましょう．$\\Pi_k$の中のなにかしらの$\\tilde{\\pi}$について，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "&V_{r}^{\\tilde{\\pi}}(P)-b \\epsilon_k^{\\tilde{\\pi}}(P) \\leq V^{\\pi^*}_r(P)\\\\\n",
    "\\Longrightarrow \\quad&\\frac{V_{r}^{\\tilde{\\pi}}(P) - V^{\\pi^*}_r(P)}{\\epsilon_k^{\\tilde{\\pi}}(P)} \\leq b\n",
    "\\end{aligned}\n",
    "$$\n",
    "が成り立てばいいわけですね．ただし，\n",
    "$\\epsilon_k^{\\pi}\\left(P\\right)=H \\mathbb{E}\\left[\\sum_{h=1}^H \\bar{\\beta}_{h, k}^p\\left(s_{h, k}, a_{h, k}\\right) \\mid \\pi, P, \\mathcal{F}_{k-1}\\right]$\n",
    "はモデルの信頼半径の累積和を表します．よって，雑に\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\frac{V_{r}^{\\tilde{\\pi}}(P) - V^{\\pi^*}_r(P)}{\\epsilon_k^{\\tilde{\\pi}}(P)}\n",
    "\\leq \\frac{H}{\\epsilon_k^{\\tilde{\\pi}}(P)} \\leq b\n",
    "\\end{aligned}\n",
    "$$\n",
    "とすると，たくさんサンプルが集まり，$\\epsilon_k^{\\tilde{\\pi}}(P) \\to 0$の場合に$b \\to \\infty$になってしまいます．\n",
    "よって，分子の方も，データが集まると$\\to 0$になるよう調整したいわけですね．\n",
    "\n",
    "ステップ１で設計した$\\tilde{\\pi}$は\n",
    "$$\n",
    "\\alpha_k \\leq \\frac{\\bar{C}-\\bar{C}_b-\\epsilon_k^{\\pi_b}(P)}{\\bar{C}-\\bar{C}_b+\\epsilon_k^{\\pi^*}(P)-\\epsilon_k^{\\pi_b}(P)}\n",
    "=\\frac{1}{1 +\\frac{\\epsilon_k^{\\pi^*}(P)}{\\bar{C}-\\bar{C}_b-\\epsilon_k^{\\pi_b}(P)}}\n",
    "$$\n",
    "のうち，最も大きい値を使って$\\pi_b$と$\\pi^\\star$を混合していました．\n",
    "つまり，サンプルが集まると$\\alpha_k\\to 1$であり，$\\tilde{\\pi}$は$\\pi^\\star$に近づきます．\n",
    "$\\tilde{\\pi}$が$\\pi^\\star$に対して線形？なので，分子と分母の減り方が定数で抑えられているのかも？です．\n",
    "\n",
    "<!-- ここで，$\\pi_b$を十分推定して，$\\epsilon_k^{\\pi_b}(P) \\leq \\epsilon$と十分小さくなった時を考えましょう．このとき\n",
    "$$\n",
    "\\alpha_k \\leq \\frac{1}{1 +\\frac{\\epsilon_k^{\\pi^*}(P)}{\\bar{C}-\\bar{C}_b-\\epsilon}}\n",
    "$$ -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## リグレットのバウンド\n",
    "\n",
    "$$\n",
    "R(K)=\\sum_{k=1}^{K_o}\\left(V_r^{\\pi_k}(P)-V_r^{\\pi^*}(P)\\right)+\\sum_{k=K_o}^K\\left(V_r^{\\pi_k}(P)-V_r^{\\pi^*}(P)\\right)\n",
    "$$\n",
    "\n",
    "であり，$K_o$の定義から，\n",
    "\n",
    "$$\n",
    "\\sum_{k=1}^{K_o}\\left(V_r^{\\pi_k}(P)-V_r^{\\pi^*}(P)\\right) \\leq H K_0 \\leq \\tilde{\\mathcal{O}}\\left(\\frac{S^2 A H^5}{\\left(\\bar{C}-\\bar{C}_b\\right)^2}\\right)\n",
    "$$\n",
    "\n",
    "です．二項目をバウンドしましょう．\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\sum_{k=K_o}^K \\left(V_r^{\\pi_k}(P)-V_r^{\\pi^*}(P)\\right) & \n",
    "\\stackrel{(a)}{\\leq} \\sum_{k=K_o}^K\\left(V_r^{\\pi_k}(P)-V_{\\bar{r}_k}^{\\pi_k}\\left(P_k\\right)\\right)\\\\\n",
    "& \\stackrel{(b)}{\\leq} \\sum_{k=K_0}^K\\left(V_{\\bar{r}_k}^{\\pi_k}(P)-V_{\\bar{r}_k}^{\\pi_k}\\left(P_k\\right)\\right)+\\frac{H}{\\bar{C}-\\bar{C}_b} \\sum_{k=K_0}^K\\epsilon_k^{\\pi_k}(P) \\\\\n",
    "& \\stackrel{(c)}{\\leq} \\sum_{k=K_o}^K\\left(V_{\\bar{r}_k}^{\\pi_k}(P)-V_{\\bar{r}_k}^{\\pi_k}\\left(P_k\\right)\\right)+\\tilde{O}\\left(\\frac{H^3}{\\bar{C}-\\bar{C}_b} S \\sqrt{A K}\\right),\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "(a)はOptimism，(b)は単純な変形，(c)は$\\epsilon_k$についてのバウンドを使ってます．\n",
    "\n",
    "この１項目をバウンドしましょう．\n",
    "価値差分方程式より，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\sum_{k=K_0}^K\\left(V_{\\bar{r}_k}^{\\pi_k}(P)-V_{\\bar{r}_k}^{\\pi_k}\\left(P_k\\right)\\right) \\\\\n",
    "& {=} \\sum_{k=K_0}^K \\sum_{h=1}^H \\mathbb{E}\\left[\\sum_{s^{\\prime}}\\left(P_h-P_{h, k}\\right)\\left(s^{\\prime} \\mid s_{h, k}, a_{h, k}\\right) V_{\\bar{r}_k, h+1}^{\\pi_k}\\left(s^{\\prime} ; P_k\\right) \\mid \\pi_k, P, \\mathcal{F}_{k-1}\\right] \\\\\n",
    "& \\leq \\sum_{k=K_0} \\sum_{h=1}^H \\mathbb{E}\\left[\\sum_{s^{\\prime}} \\mid\\left(P_h-P_{h, k}\\right)\\left(s^{\\prime} \\mid s_{h, k}, a_{h, k}\\right)\\left\\|V_{r, h+1}^{\\pi_k}\\left(s^{\\prime} ; P\\right)\\right\\| \\pi_k, P, \\mathcal{F}_{k-1}\\right]+ \\\\\n",
    "& \\sum_{k=K_0}^K \\sum_{h=1}^H \\mathbb{E}\\left[\\mid \\sum_{s^{\\prime}}\\left(P_h-P_{h, k}\\right)\\left(s^{\\prime} \\mid s_{h, k}, a_{h, k}\\right)\\left(V_{\\bar{r}_k, h+1}^{\\pi_k}\\left(s^{\\prime} ; P_k\\right)-V_{r, h+1}^{\\pi_k}\\left(s^{\\prime} ; P\\right)\\right) \\| \\pi_k, P, \\mathcal{F}_{k-1}\\right]\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成り立ちます．一項目をバウンドします．\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\sum_{k=K_0}^K \\sum_{h=1}^H \\mathbb{E}\\left[\\sum_{s^{\\prime}}\\left|\\left(P_h-P_{h, k}\\right)\\left(s^{\\prime} \\mid s_{h, k}, a_{h, k}\\right)\\right| \\mid V_{r, h+1}^{\\pi_k}\\left(s^{\\prime} ; P\\right) \\| \\pi_k, P, \\mathcal{F}_{k-1}\\right] \\\\\n",
    "& \\leq \\sum_{k=K_0}^K \\epsilon_k^{\\pi_k}(P) {\\leq} \\tilde{O}\\left(S \\sqrt{A H^4 K^{\\prime}}\\right),\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "２項目をバウンドしましょう．\n",
    "Niceエピソードの話を使えば，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\sum_{k=K_0}^K \\sum_{h=1}^H \\mathbb{E} & {\\left[\\mid \\sum_{s^{\\prime}}\\left(P_h-P_{h, k}\\right)\\left(s^{\\prime} \\mid s_{h, k}, a_{h, k}\\right)\\left(V_{\\bar{r}_k, h+1}^{\\pi_k}\\left(s^{\\prime} ; P_k\\right)-V_{r, h+1}^{\\pi_k}\\left(s^{\\prime} ; P\\right)\\right) \\| \\pi_k, P, \\mathcal{F}_{k-1}\\right] } \\\\\n",
    "& =\\sum_{k, h, s, a} w_h^{\\pi_k}(s, a ; P) \\sum_{s^{\\prime}}\\left(P_h-P_{h, k}\\right)\\left(s^{\\prime} \\mid s_{h, k}, a_{h, k}\\right)\\left(V_{\\bar{r}_k, h+1}^{\\pi_k}\\left(s^{\\prime} ; P_k\\right)-V_{r, h+1}^{\\pi_k}\\left(s^{\\prime} ; P\\right)\\right)\\\\\n",
    "& \\leq \\underbrace{\\sum_{k, h, s, a} w_h^{\\pi_k}(s, a ; P) \\sum_{s^{\\prime}} \\frac{\\sqrt{P_h\\left(s^{\\prime} \\mid s, a\\right)}}{\\sqrt{n_{h, k}(s, a) \\vee 1}}\\left|V_{\\bar{r}_k, h+1}^{\\pi_k}\\left(s^{\\prime} ; P_k\\right)-V_{r, h+1}^{\\pi_k}\\left(s^{\\prime} ; P\\right)\\right|}_{(A)} \\\\\n",
    "&\\quad +\\underbrace{\\sum_{k, h, s, a} w_h^{\\pi_k}(s, a ; P) \\frac{1}{n_{h, k}(s, a) \\vee 1}\\left|V_{\\bar{r}_k, h+1}^{\\pi_k}\\left(s^{\\prime} ; P_k\\right)-V_{r, h+1}^{\\pi_k}\\left(s^{\\prime} ; P\\right)\\right|}_{(B)},\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成り立ちます．（A）と（B）はNiceエピソードの話を使えばうまいことバウンドできます．\n",
    "\n",
    "これ以降は変形しまくればいけます．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}