notebooks/RL_General_linearMDP-Model-based.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linear MDPでモデルベース探索\n",
    "\n",
    "参考：\n",
    "* [Reinforcement Learning: Theory and Algorithms](https://rltheorybook.github.io/)\n",
    "\n",
    "今回はLinear MDPをモデルベースアルゴリズムで解く話です．\n",
    "\n",
    "表記：\n",
    "* $\\{P_h\\}_h$と$\\{r_h\\}_h$を考えましょう．Linear MDPでは次を仮定します：\n",
    "* $r_h(s, a)=\\theta_h^{\\star} \\cdot \\phi(s, a), \\quad P_h(\\cdot \\mid s, a)=\\mu_h^{\\star} \\phi(s, a), \\forall h$\n",
    "* $\\sup _{s, a}\\|\\phi(s, a)\\|_2 \\leq 1$\n",
    "* $\\left\\|v^{\\top} \\mu_h^{\\star}\\right\\|_2 \\leq \\sqrt{d}$ for any $v$ such that $\\|v\\|_\\infty \\leq 1$\n",
    "* $\\left\\|\\theta_h^{\\star}\\right\\|_2 \\leq W$\n",
    "\n",
    "* $\\|A\\|_2=\\sup _{x:\\|x\\|_2=1}\\|A x\\|_2$：最大のsingular value（スペクトルノルム）\n",
    "* $\\|A\\|_F^2=\\sum_{i, j} A_{i, j}^2$\n",
    "* $x^{\\top} \\Lambda x=\\|x\\|_{\\Lambda}^2$\n",
    "* $\\operatorname{det}(\\Lambda)=\\prod_{i=1}^d \\sigma_i$：ここで$\\sigma_i$は固有値"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "---\n",
    "\n",
    "**行列関連の性質**\n",
    "\n",
    "* $A = \\sum_i \\phi_i \\phi^\\top_i (= \\sum_i d \\times 1 \\times 1 \\times dの行列)$とする．その固有値を$\\sigma$とすると，対応する固有ベクトル$x\\in \\mathbb{R}^d$について$A x = \\sum_i \\phi_i \\phi^\\top_i x = \\sigma x$．左側にも$x^\\top$をかけると，$\\sum_i x^\\top \\phi_i \\phi^\\top_i x = \\sigma x^\\top x$．左辺が非負なので，$\\sigma \\geq 0$．よって，$A$は半正定値行列．\n",
    "* $B = A+ \\alpha I$とする．$A$の固有値と固有ベクトルを$\\sigma$と$x$とする．このとき，$Bx = Ax + \\alpha x=(\\sigma +\\alpha) x$なので，$B$の固有値は$\\sigma +\\alpha$であり，固有ベクトルは同じ．\n",
    "* $A = \\sum_i \\phi_i \\phi^\\top_i + \\lambda I$とする．上の２つの性質から，明らかにその最**小**固有値は$\\geq \\lambda$．よって，$A^{-1}$が存在し，その最大固有値は$\\leq 1 / \\lambda$．また，$A$が正定値行列なので，$A^{-1}$も正定値行列であり，$A^{-1}$の特異値は固有値に等しい．よって，$\\|A^{-1}\\|_2$は$A^{-1}$の最大固有値に等しく，それは$\\leq 1/\\lambda$．$A^{-1}$の標準化された固有ベクトルを$x$とおくと，$\\phi^\\top A^{-1} \\phi \\leq \\phi^\\top x / \\lambda$．$\\|\\phi\\|_2\\leq 1$のとき，コーシー・シュワルツから，$\\phi^\\top A^{-1} \\phi \\leq \\phi^\\top x / \\lambda \\leq 1/\\lambda$．\n",
    "<!-- * スペクトルノルムの定義と，$\\|\\phi\\|_2 \\leq 1$より，$\\phi^\\top A^{-1} \\phi$ -->\n",
    "* 普通$n$次正方行列$A$に対して，$A^* A$を$A$のグラム行列と呼ぶ．$A=(v_1, \\dots, v_n)$の形をしているなら，\n",
    "以下のように，各要素にベクトルの内積が入った行列のことを指す．\n",
    "$$\n",
    "A^* A=\\left(\\begin{array}{ccc}\n",
    "\\left\\langle\\boldsymbol{v}_1, \\boldsymbol{v}_1\\right\\rangle & \\ldots & \\left\\langle\\boldsymbol{v}_{\\boldsymbol{n}}, \\boldsymbol{v}_1\\right\\rangle \\\\\n",
    "\\vdots & \\ddots & \\vdots \\\\\n",
    "\\left\\langle\\boldsymbol{v}_1, \\boldsymbol{v}_n\\right\\rangle & \\ldots & \\left\\langle\\boldsymbol{v}_n, \\boldsymbol{v}_n\\right\\rangle\n",
    "\\end{array}\\right)\n",
    "$$\n",
    "* ここで，$\\Lambda_h^n=\\sum_{i=0}^{n-1} \\phi\\left(s_h^i, a_h^i\\right) \\phi\\left(s_h^i, a_h^i\\right)^{\\top}$を考えてみよう．\n",
    "$i$行目に$\\phi(s_h^i, a_h^i)$を入れた行列を$\\Phi=(\\phi_1, \\phi_2, \\dots)^\\top \\in \\mathbb{R}^{n \\times d}$とすると，明らかに$\\Phi^* \\Phi$は$d\\times d$の行列で，$\\Lambda_h^n$と同じ．よって，$\\Lambda_h^n$を最小二乗法のグラム行列と呼ぶ（正則化された場合は$\\lambda I$を足して，グラム行列と改めて呼称する）．\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear MDPでのプランニング\n",
    "\n",
    "Linear MDPでのプランニングは普通のVIとやることがほぼ変わりません．\n",
    "* $Q_{H-1}^{\\star}(s, a)=\\theta_{H-1}^{\\star} \\cdot \\phi(s, a)$\n",
    "* $\\pi_{H-1}^{\\star}(s)=\\operatorname{argmax}_a Q_{H-1}^{\\star}(s, a)=\\operatorname{argmax}_a \\theta_{H-1}^{\\star} \\cdot \\phi(s, a)$,\n",
    "* $V_{H-1}^{\\star}(s)=\\operatorname{argmax}_a Q_{H-1}^{\\star}(s, a)$.\n",
    "\n",
    "とします．これについて動的計画法を実行しましょう．つまり，\n",
    "$$\n",
    "\\begin{aligned}\n",
    "Q_h^{\\star}(s, a) & =\\theta_h^{\\star} \\cdot \\phi(s, a)+\\mathbb{E}_{s \\sim P_h(\\cdot \\mid s, a)} V_{h+1}^{\\star}\\left(s^{\\prime}\\right)=\\theta_h^{\\star} \\cdot \\phi(s, a)+P_h(\\cdot \\mid s, a) \\cdot V_{h+1}^{\\star}=\\theta_h^{\\star} \\cdot \\phi(s, a)+\\left(\\mu_h^{\\star} \\phi(s, a)\\right)^{\\top} V_{h+1}^{\\star} \\\\\n",
    "& =\\phi(s, a) \\cdot\\left(\\theta_h^{\\star}+\\left(\\mu_h^{\\star}\\right)^{\\top} V_{h+1}^{\\star}\\right)=\\phi(s, a) \\cdot w_h\n",
    "\\end{aligned}\n",
    "$$\n",
    "と更新します．\n",
    "\n",
    "Linear MDPでは次が成立します：\n",
    "\n",
    "---\n",
    "\n",
    "任意の関数 $f: S\\mapsto [0, H]$を考えましょう．次を満たすベクトル$w \\in \\mathbb{R}^d$が必ず存在します：\n",
    "\n",
    "$$\n",
    "r_h(s, a)+P_h(\\cdot \\mid s, a) \\cdot f=w^{\\top} \\phi(s, a)\n",
    "$$\n",
    "\n",
    "---\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear MDPでの探索\n",
    "\n",
    "今回はモデルベース，つまり$P_h$を直接学習する手法について考えます．\n",
    "\n",
    "### モデルの推定について\n",
    "\n",
    "Linear MDPでは，これは$\\mu^\\star \\in \\mathbb{R}^{|S|\\times d}$を学習することに相当しますが，Linear MDPでは$S$が無限かもしれません．よって，$\\mu^\\star$を計算してメモリに保持しておくのは現実的ではありません．\n",
    "先にモデルをnon-parametricな方法で表す方法を紹介します．\n",
    "\n",
    "表記：\n",
    "* データセット：$\\mathcal{D}_h^n=\\left\\{s_h^i, a_h^i, s_{h+1}^i\\right\\}_{i=0}^{n-1}$\n",
    "* 訪問のカウント：$\\Lambda_h^n=\\sum_{i=0}^{n-1} \\phi\\left(s_h^i, a_h^i\\right) \\phi\\left(s_h^i, a_h^i\\right)^{\\top}+\\lambda I$\n",
    "  * これは実際訪問のカウントになってます．$\\phi(s, a)$がone-hotベクトルな状況を考えてみればわかるよ．\n",
    "* さて，$\\delta(s)$を$s$だけ１で他が０のone-hotベクトルとしましょう．\n",
    "* $\\epsilon^i_h= P(\\cdot \\mid s_h^i, a_h^i) - \\delta(s^i_{h+1})$と更新します．\n",
    "  * 明らかに$\\mathbb{E}\\left[\\epsilon_h^i \\mid \\mathcal{H}_h^i\\right]=0$です．\n",
    "  * また，$\\left\\|\\epsilon_h^i\\right\\|_1 \\leq 2$でもあります．\n",
    "\n",
    "\n",
    "$\\mu_h^{\\star} \\phi\\left(s_h^i, a_h^i\\right)=P_h\\left(\\cdot \\mid s_h^i, a_h^i\\right)$なので，次のリッジ回帰をすれば$\\mu_h^\\star$が普遍推定できます：\n",
    "$$\n",
    "\\widehat{\\mu}_h^n=\\operatorname{argmin}_{\\mu \\in \\mathbb{R}^{|\\mathcal{S}| \\times d}} \\sum_{i=0}^{n-1}\\left\\|\\mu \\phi\\left(s_h^i, a_h^i\\right)-\\delta\\left(s_{h+1}^i\\right)\\right\\|_2^2+\\lambda\\|\\mu\\|_F^2 .\n",
    "$$\n",
    "この解析解は\n",
    "$$\n",
    "\\widehat{\\mu}_h^n=\\sum_{i=0}^{n-1} \\delta\\left(s_{h+1}^i\\right) \\phi\\left(s_h^i, a_h^i\\right)^{\\top}\\left(\\Lambda_h^n\\right)^{-1}\n",
    "$$\n",
    "になります．\n",
    "\n",
    "ただし，$\\widehat{\\mu}_h^n \\in \\mathbb{R}^{|\\mathcal{S}| \\times d}$なので，$\\mu$を保持したくありません．ここで，価値反復法を思い出すと，基本的にモデルは\n",
    "\n",
    "$$\n",
    "\\widehat{P}_h^n(\\cdot \\mid s, a) \\cdot V:=\\left(\\widehat{\\mu}_h^n \\phi(s, a)\\right) \\cdot V=\\phi(s, a)^{\\top} \\sum_{i=0}^{n-1}\\left(\\Lambda_h^n\\right)^{-1} \\phi\\left(s_h^i, a_h^i\\right) V\\left(s_{h+1}^i\\right)\n",
    "$$\n",
    "\n",
    "の形でしか使用しません．以降では，データを蓄えて，そのデータを使って\n",
    "$\\widehat{P}_h^n(\\cdot \\mid s, a) \\cdot V$を計算するアプローチを考えていきましょう．\n",
    "\n",
    "この場合は計算効率が$(d, n)$であり，$S$には依存しません．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 便利な補題\n",
    "\n",
    "$\\mu$の推定値について，次が成立します：\n",
    "\n",
    "$$\n",
    "\\widehat{\\mu}_h^n-\\mu_h^{\\star}=-\\lambda \\mu_h^{\\star}\\left(\\Lambda_h^n\\right)^{-1}+\\sum_{i=1}^{n-1} \\epsilon_h^i \\phi\\left(s_h^i, a_h^i\\right)^{\\top}\\left(\\Lambda_h^n\\right)^{-1}\n",
    "$$\n",
    "\n",
    "**証明**\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\widehat{\\mu}_h^n & =\\sum_{i=0}^{n-1} \\delta\\left(s_{h+1}^i\\right) \\phi\\left(s_h^i, a_h^i\\right)^{\\top}\\left(\\Lambda_h^n\\right)^{-1}=\\sum_{i=0}^{n-1}\\left(P\\left(\\cdot \\mid s_h^i, a_h^i\\right)+\\epsilon_h^n\\right) \\phi\\left(s_h^i, a_h^i\\right)^{\\top}\\left(\\Lambda_h^n\\right)^{-1} \\\\\n",
    "& =\\sum_{i=0}^{n-1}\\left(\\mu_h^{\\star} \\phi\\left(s_h^i, a_h^i\\right)+\\epsilon_h^i\\right) \\phi\\left(s_h^i, a_h^i\\right)^{\\top}\\left(\\Lambda_h^n\\right)^{-1}=\\sum_{i=0}^{n-1} \\mu_h^* \\phi\\left(s_h^i, a_h^i\\right) \\phi\\left(s_h^i, a_h^i\\right)^{\\top}\\left(\\Lambda_h^n\\right)^{-1}+\\sum_{i=0}^{n-1} \\epsilon_h^i \\phi\\left(s_h^i, a_h^i\\right)^{\\top}\\left(\\Lambda_h^n\\right)^{-1} \\\\\n",
    "& =\\sum_{i=0}^{n-1} \\mu_h^{\\star} \\phi\\left(s_h^i, a_h^i\\right) \\phi\\left(s_h^i, a_h^i\\right)^{\\top}\\left(\\Lambda_h^n\\right)^{-1}+\\sum_{i=0}^{n-1} \\epsilon_h^i \\phi\\left(s_h^i, a_h^i\\right)^{\\top}\\left(\\Lambda_h^n\\right)^{-1} \\\\\n",
    "& =\\mu_h^{\\star}\\left(\\Lambda_h^n-\\lambda I\\right)\\left(\\Lambda_h^n\\right)^{-1}+\\sum_{i=0}^{n-1} \\epsilon_h^i \\phi\\left(s_h^i, a_h^i\\right)^{\\top}\\left(\\Lambda_h^n\\right)^{-1}=\\mu_h^*-\\lambda \\mu_h^{\\star}\\left(\\Lambda_h^n\\right)^{-1}+\\sum_{i=0}^{n-1} \\epsilon_h^i \\phi\\left(s_h^i, a_h^i\\right)^{\\top}\\left(\\Lambda_h^n\\right)^{-1}\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "\n",
    "---\n",
    "\n",
    "固定された$V:\\mathcal{S}\\mapsto [0, H]$について，次が高確率で成立します：\n",
    "\n",
    "$$\n",
    "\\left\\|\\sum_{i=0}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)\\left(V^{\\top} \\epsilon_h^i\\right)\\right\\|_{\\left(\\Lambda_h^n\\right)^{-1}} \\leq 3 H \\sqrt{\\ln \\frac{H \\operatorname{det}\\left(\\Lambda_h^n\\right)^{1 / 2} \\operatorname{det}(\\lambda I)^{-1 / 2}}{\\delta}}\n",
    "$$\n",
    "\n",
    "**証明**\n",
    "\n",
    "まず，\n",
    "$$\n",
    "\\mathbb{E}\\left[V^{\\top} \\epsilon_h^i \\mid \\mathcal{H}_h^i\\right]=0, \\quad\\left|V^{\\top} \\epsilon_h^i\\right| \\leq\\|V\\|_{\\infty}\\left\\|\\epsilon_h^i\\right\\|_1 \\leq 2 H, \\forall h, i .\n",
    "$$\n",
    "が明らかに成立します．\n",
    "あとは次のSelf-normalized boundを使えば証明終わりです：\n",
    "\n",
    "--- \n",
    "**定理：Self-Normalized Bound for Vector Valued Martingales**\n",
    "\n",
    "$\\left\\{F_t\\right\\}_{t=0}^{\\infty}$をフィルトレーションとする。 \n",
    "$\\left\\{\\eta_t\\right\\}_{t=1}^{\\infty}$を$\\eta_t$が$F_t$-可測な実数値確率過程とする。また、$\\eta_t$は条件付き$R$-sub-Gaussianとする ($R \\geq 0$)。つまり、\n",
    "$$\n",
    "\\forall \\lambda \\in \\mathbb{R} \\quad \\mathbf{E}\\left[e^{\\lambda \\eta_t} \\mid F_{t-1}\\right] \\leq \\exp \\left(\\frac{\\lambda^2 R^2}{2}\\right)\n",
    "$$\n",
    "\n",
    "$\\left\\{X_t\\right\\}_{t=1}^{\\infty}$は$X_t$が$F_{t-1}$-可測である$\\mathbb{R}^d$の確率過程とする。\n",
    "$V$を$d \\times d$の正則行列とする。任意の$t \\geq 0$について、\n",
    "$$\n",
    "\\bar{V}_t=V+\\sum_{s=1}^t X_s X_s^{\\top} \\quad S_t=\\sum_{s=1}^t \\eta_s X_s .\n",
    "$$\n",
    "すると、任意の$\\delta>0$について、最低でも確率$1-\\delta$で、任意の$t \\geq 0$について、\n",
    "$$\n",
    "\\left\\|S_t\\right\\|_{\\bar{V}_t^{-1}}^2 \\leq 2 R^2 \\log \\left(\\frac{\\operatorname{det}\\left(\\bar{V}_t\\right)^{1 / 2} \\operatorname{det}(V)^{-1 / 2}}{\\delta}\\right)\n",
    "$$\n",
    "が成り立つ。\n",
    "\n",
    "---\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CoveringによるUnion bound\n",
    "\n",
    "上の補題では，固定された$V$についてSelf normalized boundを適用しました．\n",
    "これでは任意の$V$について成り立つ議論ができません．そこで，Coveringを使ってUnion boundを適用します．\n",
    "\n",
    "半径$R$の球を考えましょう．\n",
    "\n",
    "$$\n",
    "\\Theta=\\left\\{\\theta \\in \\mathbb{R}^d:\\|\\theta\\|_2 \\leq R \\in \\mathbb{R}^{+}\\right\\}\n",
    "$$\n",
    "\n",
    "この球に対して，次を満たす$\\mathcal{N}_\\epsilon \\subset \\Theta$を$\\epsilon$-ネットと呼びます：\n",
    "\n",
    "* 任意の$\\theta \\in \\Theta$に対して，$\\left\\|\\theta-\\theta^{\\prime}\\right\\|_2 \\leq \\epsilon$を満たす$\\theta'\\in \\mathcal{N}_\\epsilon$が存在する．特に一番小さい$\\epsilon$-ネットのことを$\\epsilon$-被覆と呼びます．かんたんのため，$\\mathcal{N}_\\epsilon$を単に$\\epsilon$-被覆と呼ぶことにしましょう．\n",
    "* $\\epsilon$-被覆数とは，$\\epsilon$-被覆 $\\mathcal{N}_\\epsilon$の要素の数のことです．\n",
    "* $\\ln \\left(\\left|\\mathcal{N}_\\epsilon\\right|\\right)$を被覆次元と呼ぶことにします\n",
    "\n",
    "このとき，次が成立します：\n",
    "\n",
    "---\n",
    "\n",
    "球$\\Theta=\\left\\{\\theta \\in \\mathbb{R}^d:\\|\\theta\\|_2 \\leq R \\in \\mathbb{R}^{+}\\right\\}$の被覆数は\n",
    "$$\n",
    "(1+2 R / \\epsilon)^d\n",
    "$$\n",
    "で抑えられる．\n",
    "\n",
    "---\n",
    "\n",
    "さて，この定義を関数クラスに拡張しましょう．次の$(w, \\beta, \\Lambda)$で定義される関数$f_{w, \\beta, \\Lambda}: \\mathcal{S} \\mapsto[0, R]$を考えます（後で見ますが，このクラスにはLinear MDPにおける全ての価値関数が入ります）：\n",
    "\n",
    "$$\n",
    "f_{w, \\beta, \\Lambda}(s)=\\min \\left\\{\\max _a\\left(w^{\\top} \\phi(s, a)+\\beta \\sqrt{\\phi(s, a)^{\\top} \\Lambda^{-1} \\phi(s, a)}\\right), H\\right\\}, \\forall s \\in \\mathcal{S}\n",
    "$$\n",
    "この関数のクラスを\n",
    "$$\n",
    "\\mathcal{F}=\\left\\{f_{w, \\beta, \\Lambda}:\\|w\\|_2 \\leq L, \\beta \\in[0, B], \\sigma_{\\min }(\\Lambda) \\geq \\lambda\\right\\}\n",
    "$$\n",
    "としましょう．\n",
    "このとき，上の$\\mathcal{F}$の$\\epsilon$-被覆を$\\mathcal{N}_\\epsilon$とすると，$\\ell_\\infty$ノルムを距離測度として導入すれば，\n",
    "\n",
    "$$\n",
    "\\ln \\left(\\left|\\mathcal{N}_\\epsilon\\right|\\right) \\leq d \\ln (1+6 L / \\epsilon)+\\ln (1+6 B /(\\sqrt{\\lambda} \\epsilon))+d^2 \\ln \\left(1+18 B^2 \\sqrt{d} /\\left(\\lambda \\epsilon^2\\right)\\right)\n",
    "$$\n",
    "が成立します．つまり，$\\epsilon$-被覆次元が$d$に対して二乗のオーダーでスケールしてます．\n",
    "\n",
    "**証明**\n",
    "\n",
    "２つのパラメータ$(w, \\beta, \\Lambda)$ and $(\\hat{w}, \\hat{\\beta}, \\widehat{\\Lambda})$について，次が成立します：\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "|f(s)-\\hat{f}(s)| \\leq & \\mid \\max _a\\left(w^{\\top} \\phi(s, a)+\\beta \\sqrt{\\phi(s, a)^{\\top} \\Lambda^{-1} \\phi(s, a)}\\right)-\\max _a\\left(\\hat{w}^{\\top} \\phi(s, a)+\\hat{\\beta} \\sqrt{\\phi(s, a)^{\\top} \\hat{\\Lambda}-1} \\phi(s, a)\\right. \\\\\n",
    "\\leq & \\max _a\\left|\\left(w^{\\top} \\phi(s, a)+\\beta \\sqrt{\\phi(s, a)^{\\top} \\Lambda^{-1} \\phi(s, a)}\\right)-\\left(\\hat{w}^{\\top} \\phi(s, a)+\\hat{\\beta} \\sqrt{\\phi(s, a)^{\\top} \\hat{\\Lambda}^{-1} \\phi(s, a)}\\right)\\right| \\\\\n",
    "\\leq & \\max _a\\left|(w-\\hat{w})^{\\top} \\phi(s, a)\\right|+\\max _a\\left|(\\beta-\\hat{\\beta}) \\sqrt{\\phi(s, a)^{\\top} \\Lambda^{-1} \\phi(s, a)}\\right| \\\\\n",
    "& +\\max _a\\left|\\hat{\\beta}\\left(\\sqrt{\\phi(s, a)^{\\top} \\Lambda^{-1} \\phi(s, a)}-\\sqrt{\\phi(s, a)^{\\top} \\hat{\\Lambda}^{-1} \\phi(s, a)}\\right)\\right| \\\\\n",
    "\\leq & \\|w-\\hat{w}\\|_2+|\\beta-\\hat{\\beta}| / \\sqrt{\\lambda}+B \\sqrt{\\left|\\phi(s, a)^{\\top}\\left(\\Lambda^{-1}-\\hat{\\Lambda}^{-1}\\right) \\phi(s, a)\\right|} \\\\\n",
    "\\leq & \\|w-\\hat{w}\\|_2+|\\beta-\\hat{\\beta}| / \\sqrt{\\lambda}+B \\sqrt{\\left\\|\\Lambda^{-1}-\\hat{\\Lambda}-1\\right\\|_F}\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "ここで，$\\Lambda^{-1}$は正定値行列であり，$\\sigma_{\\max }\\left(\\Lambda^{-1}\\right) \\leq 1 / \\lambda$であることに注意しましょう．\n",
    "そして，\n",
    "* $\\left\\{w:\\|w\\|_2 \\leq L\\right\\}$上の$\\epsilon/3$-ネット：$\\mathcal{N}_{\\epsilon/3}, w$\n",
    "* $\\beta \\in [0, B]$上の$\\sqrt{\\lambda}\\epsilon/3$ネット：$\\mathcal{N}_{\\sqrt{\\lambda} \\epsilon / 3, \\beta}$\n",
    "* $\\left\\{\\Lambda:\\|\\Lambda\\|_F \\leq \\sqrt{d} / \\lambda\\right\\}$上の$\\epsilon^2 /\\left(9 B^2\\right)$ネット：$\\mathcal{N}_{\\epsilon^2 /(9 B), \\Lambda}$\n",
    "\n",
    "を考えましょう．すると，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\ln \\left|\\mathcal{N}_\\epsilon\\right| & \\leq \\ln \\left|\\mathcal{N}_{\\epsilon / 3, w}\\right|+\\ln \\left|\\mathcal{N}_{\\sqrt{\\lambda} \\epsilon / 3, \\beta}\\right|+\\ln \\left|\\mathcal{N}_{\\epsilon^2 /\\left(9 B^2\\right), \\Lambda}\\right| \\\\\n",
    "& \\leq d \\ln (1+6 L / \\epsilon)+\\ln (1+6 B /(\\sqrt{\\lambda} \\epsilon))+d^2 \\ln \\left(1+18 B^2 \\sqrt{d} /\\left(\\lambda \\epsilon^2\\right)\\right)\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成り立ちます．\n",
    "\n",
    "---\n",
    "\n",
    "さて，この補題を遷移関数の推定バウンドに使いましょう．次が成立します．\n",
    "\n",
    "$\\lambda=1$とします．$\\delta \\in (0,1)$で固定します．任意の$n, h, s, a, f\\in \\mathcal{F}$について，確率$1-\\delta$以上で，\n",
    "\n",
    "$$\n",
    "\\left|\\left(\\widehat{P}_h^n(\\cdot \\mid s, a)-P(\\cdot \\mid s, a)\\right) \\cdot f\\right| \\lesssim H\\|\\phi(s, a)\\|_{\\left(\\Lambda_h^n\\right)^{-1}}\\left(\\sqrt{d \\ln (1+6 L \\sqrt{N})}+d \\sqrt{\\ln \\left(1+18 B^2 \\sqrt{d} N\\right)}+\\sqrt{\\ln \\frac{H}{\\delta}}\\right)\n",
    "$$\n",
    "\n",
    "が成立します．\n",
    "\n",
    "**証明**\n",
    "\n",
    "上でやった補題から，固定された$V$については\n",
    "\n",
    "$$\n",
    "\\left\\|\\sum_{i=1}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)\\left(V^{\\top} \\epsilon_h^i\\right)\\right\\|_{\\left(\\Lambda_h^n\\right)^{-1}}^2 \\leq 9 H^2 \\ln \\frac{H \\operatorname{det}\\left(\\Lambda_h^n\\right)^{1 / 2} \\operatorname{det}(\\lambda I)^{-1 / 2}}{\\delta}\n",
    "$$\n",
    "\n",
    "が成立します．さらに，$\\lambda=1$とすると，\n",
    "\n",
    "$$\n",
    "\\left\\|\\sum_{i=1}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)\\left(V^{\\top} \\epsilon_h^i\\right)\\right\\|_{\\left(\\Lambda_h^n\\right)^{-1}}^2 \n",
    "\\leq 9 H^2 \\ln \\frac{H \\operatorname{det}\\left(\\Lambda_h^n\\right)^{1 / 2}}{\\delta}\n",
    "= 9 H^2\\left(\\ln \\frac{H}{\\delta}+\\ln \\operatorname{det}\\left(\\Lambda_h^n\\right)^{1 / 2}\\right)\n",
    "$$\n",
    "$\\operatorname{det}\\left(\\Lambda_h^n\\right)^{1 / 2}$をバウンドしましょう．\n",
    "\n",
    "---\n",
    "\n",
    "* [Improved Algorithms for Linear Stochastic Bandits](https://sites.ualberta.ca/~szepesva/papers/linear-bandits-NeurIPS2011.pdf)のLemma 10\n",
    "\n",
    "準備：\n",
    "* $X_1, X_2, \\dots, X_t\\in \\mathbb{R}^d$\n",
    "* $1\\leq s \\leq t$ \n",
    "* $\\left\\|X_s\\right\\|_2 \\leq L$\n",
    "* $\\bar{V}_t=\\lambda I+\\sum_{s=1}^t X_s X_s^{\\top}$\n",
    "\n",
    "を考えます．このとき，次が成立します：\n",
    "\n",
    "$$\n",
    "\\ln \\operatorname{det}\\left(\\bar{V}_t\\right) \\leq d\\ln \\left(\\lambda+t L^2 / d\\right)\n",
    "$$\n",
    "\n",
    "**証明**\n",
    "\n",
    "$\\bar{V}_t$の固有値を$\\alpha_1, \\alpha_2, \\dots, \\alpha_d$とする．\n",
    "このとき，$\\bar{V}_t$は正定値行列なので，その固有値は正です．また，\n",
    "$$\n",
    "\\operatorname{det}\\left(\\bar{V}_t\\right)=\\prod_{s=1}^t \\alpha_s\n",
    "\\quad \\text{ and }\\quad\n",
    "\\operatorname{trace}\\left(\\bar{V}_t\\right)=\\sum_{s=1}^t \\alpha_s\n",
    "$$\n",
    "\n",
    "このとき，AM-GM不等式から，\n",
    "$$\n",
    "\\sqrt[d]{\\alpha_1 \\alpha_2 \\cdots \\alpha_d} \\leq \\frac{\\alpha_1+\\alpha_2+\\cdots+\\alpha_d}{d}\n",
    "$$\n",
    "なので，\n",
    "$$\n",
    "\\operatorname{det}\\left(\\bar{V}_n\\right) \\leq\\left(\\operatorname{trace}\\left(\\bar{V}_n\\right) / d\\right)^d\n",
    "$$\n",
    "が成り立ちます．あとはトレースを上からバウンドすればOKです．\n",
    "\n",
    "$$\n",
    "\\operatorname{trace}\\left(\\bar{V}_n\\right)=\\operatorname{trace}(\\lambda I)+\\sum_{s=1}^t \\operatorname{trace}\\left(X_s X_s^{\\top}\\right)=d \\lambda+\\sum_{s=1}^t\\left\\|X_s\\right\\|_2^2 \\leq d \\lambda+t L^2\n",
    "$$\n",
    "これで証明終わりです．\n",
    "\n",
    "\n",
    "\n",
    "---\n",
    "\n",
    "\n",
    "上の結果と$\\|\\phi\\|_2 \\leq 1$を使うと，\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\left\\|\\sum_{i=1}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)\\left(V^{\\top} \\epsilon_h^i\\right)\\right\\|_{\\left(\\Lambda_h^n\\right)^{-1}}^2 \n",
    "&\\leq 9 H^2\\left(\\ln \\frac{H}{\\delta}+\\ln \\operatorname{det}\\left(\\Lambda_h^n\\right)^{1 / 2}\\right)\\\\\n",
    "&\\leq 9 H^2\\left(\\ln \\frac{H}{\\delta}+ d \\ln (N+1)\\right)\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "さて，$\\mathcal{F}$の$\\epsilon$-被覆を$\\mathcal{N}_\\epsilon$としましょう．このとき，任意の$V \\in \\mathcal{N}_\\epsilon$に対して，\n",
    "\n",
    "$$\n",
    "\\left\\|\\sum_{i=1}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)\\left(V^{\\top} \\epsilon_h^i\\right)\\right\\|_{\\left(\\Lambda_h^n\\right)^{-1}}^2 \\leq 9 H^2\\left(\\ln \\frac{H}{\\delta}+\\ln \\left(\\left|\\mathcal{N}_\\epsilon\\right|\\right)+d \\ln (1+N)\\right)\n",
    "$$\n",
    "\n",
    "が成り立ちます．さらに$\\epsilon$-被覆のバウンドを使えば，\n",
    "$$\n",
    "\\left\\|\\sum_{i=1}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)\\left(V^{\\top} \\epsilon_h^i\\right)\\right\\|_{\\left(\\Lambda_h^n\\right)^{-1}}^2 \\leq 9 H^2\\left(\\ln \\frac{H}{\\delta}+d \\ln (1+6 L / \\epsilon)+d^2 \\ln \\left(1+18 B^2 \\sqrt{d} / \\epsilon^2\\right)+d \\ln (1+N)\\right)\n",
    "$$\n",
    "が成り立ちます．いよいよ任意の$f\\in \\mathcal{F}$について考えましょう．$\\epsilon$-被覆の定義から，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\left\\|\\sum_{i=1}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)\\left(f^{\\top} \\epsilon_h^i\\right)\\right\\|_{\\left(\\Lambda_h^n\\right)^{-1}}^2 & \\leq 2\\left\\|\\sum_{i=1}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)\\left(V^{\\top} \\epsilon_h^i\\right)\\right\\|_{\\left(\\Lambda_h^n\\right)^{-1}}^2+2\\left\\|\\sum_{i=1}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)\\left((V-f)^{\\top} \\epsilon_h^i\\right)\\right\\|_{\\left(\\Lambda_h^n\\right)^{-1}}^2 \\\\\n",
    "& \\leq 2\\left\\|\\sum_{i=1}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)\\left(V^{\\top} \\epsilon_h^i\\right)\\right\\|_{\\left(\\Lambda_h^n\\right)^{-1}}^2+8 \\epsilon^2 N \\\\\n",
    "& \\leq 9 H^2\\left(\\ln \\frac{H}{\\delta}+d \\ln (1+6 L / \\epsilon)+d^2 \\ln \\left(1+18 B^2 \\sqrt{d} / \\epsilon^2\\right)+d \\ln (1+N)\\right)+8 \\epsilon^2 N\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成り立ちます．ここで，二個目の不等式では\n",
    "\n",
    "$$\n",
    "\\left\\|\\sum_{i=1}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)(V-f)^{\\top} \\epsilon_h^i\\right\\|_{\\left(\\Lambda_h^n\\right)^{-1}}^2 \\leq\\left\\|\\sum_{i=1}^{n-1} \\phi\\left(s_h^i, a_h^i\\right) 2 \\epsilon\\right\\|_{\\left(\\Lambda_h^n\\right)^{-1}}^2 \\leq \\frac{4 \\epsilon^2}{\\lambda}\\left\\|\\sum_{i=1}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)\\right\\|_2 \\leq 4 \\epsilon^2 N\n",
    "$$\n",
    "\n",
    "を使いました．$\\epsilon=1/\\sqrt{N}$としましょう．\n",
    "すると，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\left\\|\\sum_{i=1}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)\\left(f^{\\top} \\epsilon_h^i\\right)\\right\\|_{\\left(\\Lambda_h^n\\right)^{-1}}^2 & \\leq 9 H^2\\left(\\ln \\frac{H}{\\delta}+d \\ln (1+6 L \\sqrt{N})+d^2 \\ln \\left(1+18 B^2 \\sqrt{d} N\\right)+d \\ln (1+N)\\right)+8 \\\\\n",
    "& \\lesssim H^2\\left(\\ln \\frac{H}{\\delta}+d \\ln (1+6 L \\sqrt{N})+d^2 \\ln \\left(1+18 B^2 \\sqrt{d} N\\right)\\right)\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成り立ちます（最後の不等式は絶対定数を無視してます）．\n",
    "\n",
    "ここで，$\\left(\\widehat{P}_h^n(\\cdot \\mid s, a)-P(\\cdot \\mid s, a)\\right) \\cdot f=\\phi(s, a)^{\\top}\\left(\\widehat{\\mu}_h^n-\\mu_h^{\\star}\\right)^{\\top} f$であることを思い出しましょう．すると，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\left|\\left(\\widehat{\\mu}_h^n \\phi(s, a)-\\mu_h^{\\star} \\phi(s, a)\\right) \\cdot f\\right| \\leq\\left|\\lambda \\phi(s, a)^{\\top}\\left(\\Lambda_h^n\\right)^{-1}\\left(\\mu_h^{\\star}\\right)^{\\top} f\\right|+\\left|\\sum_{i=1}^{n-1} \\phi(s, a)^{\\top}\\left(\\Lambda_h^n\\right)^{-1} \\phi\\left(s_h^i, a_h^i\\right)\\left(\\epsilon_h^i\\right)^{\\top} f\\right| \\\\\n",
    "& \\lesssim H \\sqrt{d}\\|\\phi(s, a)\\|_{\\left(\\Lambda_h^n\\right)^{-1}}+\\|\\phi(s, a)\\|_{\\left(\\Lambda_h^n\\right)^{-1}} \\sqrt{\\left(H^2\\left(\\ln \\frac{H}{\\delta}+d \\ln (1+6 L \\sqrt{N})+d^2 \\ln \\left(1+18 B^2 \\sqrt{d} N\\right)\\right)\\right)} \\\\\n",
    "& \\approx H\\|\\phi(s, a)\\|_{\\left(\\Lambda_h^n\\right)^{-1}}\\left(\\sqrt{\\ln \\frac{H}{\\delta}}+\\sqrt{d \\ln (1+6 L \\sqrt{N})}+d \\sqrt{\\ln \\left(1+18 B^2 \\sqrt{d} N\\right)}\\right)\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成立します．これで証明終わりです．\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## アルゴリズムへ\n",
    "\n",
    "上の章では，モデルの近似精度についてバウンドを導出しました．\n",
    "続いて，UCB-VIベースのアルゴリズムを考えます．\n",
    "次のボーナス関数を考えましょう：\n",
    "$$\n",
    "b_h^n(s, a)=\\beta \\sqrt{\\phi(s, a)^{\\top}\\left(\\Lambda_h^n\\right)^{-1} \\phi(s, a)}\n",
    "$$\n",
    "\n",
    "そして，次の価値反復法による更新を考えましょう：\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\widehat{V}_H^n(s)=0, \\forall s \\\\\n",
    "& \\widehat{Q}_h^n(s, a)=\\theta^{\\star} \\cdot \\phi(s, a)+\\beta \\sqrt{\\phi(s, a)^{\\top}\\left(\\Lambda_h^n\\right)^{-1} \\phi(s, a)}+\\phi(s, a)^{\\top}\\left(\\widehat{\\mu}_h^n\\right)^{\\top} \\widehat{V}_{h+1}^n \\\\\n",
    "& \\quad=\\beta \\sqrt{\\phi(s, a)^{\\top}\\left(\\Lambda_h^n\\right)^{-1} \\phi(s, a)}+\\left(\\theta^{\\star}+\\left(\\widehat{\\mu}_h^n\\right)^{\\top} \\widehat{V}_{h+1}^n\\right)^{\\top} \\phi(s, a) \\\\\n",
    "& \\widehat{V}_h^n(s)=\\min \\left\\{\\max _a \\widehat{Q}_h^n(s, a), H\\right\\}, \\quad \\pi_h^n(s)=\\operatorname{argmax}_a \\widehat{Q}_h^n(s, a)\n",
    "\\end{aligned}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## リグレット解析\n",
    "\n",
    "\n",
    "まず，$\\widehat{V}_h^k$の被覆についてバウンドを出しておきましょう．モチベーションは次が成立します．\n",
    "\n",
    "---\n",
    "\n",
    "$\\beta \\in [0, B]$とします．このとき，$\\widehat{V}_h^n$は次のクラスに属します：\n",
    "\n",
    "$$\n",
    "\\mathcal{V}=\\left\\{f_{w, \\beta, \\Lambda}:\\|w\\|_2 \\leq W+\\frac{H N}{\\lambda}, \\beta \\in[0, B], \\sigma_{\\min }(\\Lambda) \\geq \\lambda\\right\\}\n",
    "$$\n",
    "\n",
    "**証明**\n",
    "\n",
    "証明には，$\\theta^{\\star}+\\left(\\widehat{\\mu}_h^n\\right)^{\\top} \\widehat{V}_{h+1}^n$が$\\ell_2$ノルムのバウンドを導出するだけで良いです．\n",
    "\n",
    "まず，$\\left\\|\\widehat{V}_{h+1}^n\\right\\|_{\\infty} \\leq H$が成立してます．また，次も成立しています：\n",
    "\n",
    "$$\n",
    "\\left\\|\\theta^{\\star}+\\left(\\widehat{\\mu}_h^n\\right)^{\\top} \\widehat{V}_{h+1}^n\\right\\|_2 \\leq W+\\left\\|\\left(\\widehat{\\mu}_h^n\\right)^{\\top} \\widehat{V}_{h+1}^n\\right\\|_2\n",
    "$$\n",
    "\n",
    "$\\widehat{\\mu}_h^n$の解析解を使えば，\n",
    "$$\n",
    "\\left\\|\\left(\\widehat{\\mu}_h^n\\right)^{\\top} \\widehat{V}_{h+1}^n\\right\\|_2=\\left\\|\\sum_{i=1}^{n-1} \\widehat{V}_{h+1}^n\\left(s_{h+1}^i\\right) \\phi\\left(s_h^i, a_h^i\\right)^{\\top}\\left(\\Lambda_h^n\\right)^{-1}\\right\\|_2 \\leq H\\left\\|\\left(\\Lambda_h^n\\right)^{-1} \\sum_{i=0}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)\\right\\|_2 \\leq \\frac{H n}{\\lambda}\n",
    "$$\n",
    "ここで，$\\left\\|\\widehat{V}_{h+1}^n\\right\\|_{\\infty} \\leq H, \\sigma_{\\max }\\left(\\Lambda^{-1}\\right) \\leq 1 / \\lambda$, and $\\sup _{s, a}\\|\\phi(s, a)\\|_2 \\leq 1$を使いました．\n",
    "\n",
    "---\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Optimismの証明\n",
    "\n",
    "これまでの議論を使うと，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\left|\\left(\\widehat{P}_h^n(\\cdot \\mid s, a)-P(\\cdot \\mid s, a)\\right) \\cdot f\\right| \\leq H\\|\\phi(s, a)\\|_{\\left(\\Lambda_h^n\\right)^{-1}}\\left(\\sqrt{\\ln \\frac{H}{\\delta}}+\\sqrt{d \\ln (1+6(W+H N) \\sqrt{N})}+d \\sqrt{\\ln \\left(1+18 B^2 \\sqrt{d} N\\right)}\\right) \\\\\n",
    "& \\lesssim H d\\|\\phi(s, a)\\|_{\\left(\\Lambda_h^n\\right)^{-1}}\\left(\\sqrt{\\ln \\frac{H}{\\delta}}+\\sqrt{\\ln \\left(W N+H N^2\\right)}+\\sqrt{\\ln \\left(B^2 d N\\right)}\\right) \\\\\n",
    "& \\lesssim\\|\\phi(s, a)\\|_{\\left(\\Lambda_h^n\\right)^{-1}} \\underbrace{H d\\left(\\sqrt{\\ln \\frac{H}{\\delta}}+\\sqrt{\\ln (W+H)}+\\sqrt{\\ln B}+\\sqrt{\\ln d}+\\sqrt{\\ln N}\\right)}_{:=\\beta} .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "このイベントを$\\mathcal{E}_{\\text {model }}$として，このイベントが成立していると仮定します．\n",
    "また，表記の単純化のために，\n",
    "$$\n",
    "\\beta=H d\\left(\\sqrt{\\ln \\frac{H}{\\delta}}+\\sqrt{\\ln (W+H)}+\\sqrt{\\ln B}+\\sqrt{\\ln d}+\\sqrt{\\ln N}\\right)=\\widetilde{O}(H d) .\n",
    "$$\n",
    "とします．\n",
    "\n",
    "* 注意：$\\beta \\in [0, B]$なのに，$\\beta$の中に$B$があることに注意しましょう．これは$\\beta \\leq B$を$B$について解くことで解決します．\n",
    "\n",
    "$\\mathcal{E}_{\\text {model }}$が成立しているとき，次のOptimismが成立します：\n",
    "\n",
    "$$\n",
    "\\widehat{V}_h^n(s) \\geq V_h^{\\star}(s), \\forall s\n",
    "$$\n",
    "\n",
    "**証明**\n",
    "\n",
    "帰納法で示します．まず，$\\widehat{V}_{h+1}^n(s) \\geq V_{h+1}^{\\star}(s)$ for all $s$が成り立っているとしましょう．すると，\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\hat{Q}_h^n(s, a)-Q_h^{\\star}(s, a) \\\\\n",
    "& =\\theta^{\\star} \\cdot \\phi(s, a)+\\beta \\sqrt{\\phi(s, a)^{\\top}\\left(\\Lambda_h^n\\right)^{-1} \\phi(s, a)}+\\phi(s, a)^{\\top}\\left(\\widehat{\\mu}_h^n\\right)^{\\top} \\widehat{V}_{h+1}^n-\\theta^{\\star} \\cdot \\phi(s, a)-\\phi(s, a)^{\\top}\\left(\\mu_h^{\\star}\\right)^{\\top} V_{h+1}^{\\star} \\\\\n",
    "& \\geq \\beta \\sqrt{\\phi(s, a)^{\\top}\\left(\\Lambda_h^n\\right)^{-1} \\phi(s, a)}+\\phi(s, a)^{\\top}\\left(\\widehat{\\mu}_h^n-\\mu_h^{\\star}\\right)^{\\top} \\widehat{V}_{h+1}^n\n",
    "\\end{aligned}\n",
    "$$\n",
    "が言えます．そして，$\\mathcal{E}_{\\text{ model }}$が起きているので，\n",
    "\n",
    "**コメント**：この証明よりは[Notes on Exploration in Linear MDPs](https://nanjiang.cs.illinois.edu/files/cs542f22/note8.pdf)のほうがわかりやすいよ．\n",
    "\n",
    "$$\n",
    "\\left|\\left(\\widehat{P}_h^n(\\cdot \\mid s, a)-P(\\cdot \\mid s, a)\\right) \\cdot \\widehat{V}_{h+1}^n\\right| \\lesssim \\beta\\|\\phi(s, a)\\|_{\\left(\\Lambda_h^n\\right)^{-1}}\n",
    "$$\n",
    "\n",
    "が言えます．これで証明終わりです．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 補足：別のOptimism\n",
    "\n",
    "参考：\n",
    "* [Provably Efficient Exploration in Policy Optimization](https://arxiv.org/abs/1912.05830)\n",
    "\n",
    "上でやった補題を振り返ると，固定された$\\epsilon \\in (0,1)$および任意の$n, h, s, a$について，確率$1-\\epsilon$以上で，\n",
    "\n",
    "$$\n",
    "\\left|\\left(\\widehat{P}_h^n(\\cdot \\mid s, a)-P(\\cdot \\mid s, a)\\right) \\cdot \\widehat{V}_{h+1}^n\\right| \\lesssim \\beta\\|\\phi(s, a)\\|_{\\left(\\Lambda_h^n\\right)^{-1}}\n",
    "$$\n",
    "\n",
    "が成立します．ただ，その証明では$|\\max_a \\dots - \\max_a \\dots| \\leq \\max_a |\\dots - \\dots|$を利用していました．これは貪欲方策でしか成立しません．\n",
    "例えば自然方策勾配ベースの更新では問題がでます（[RL_useful_lemma/useful_inequalities](RL_useful_lemma/useful_inequalities.ipynb)でちょっと頑張ったんですが，やっぱ無理でした．）．\n",
    "\n",
    "そこで，別のやり方でOptimismを出してみましょう．\n",
    "まず簡単なFiltrationを定義します：\n",
    "* $\\{\\mathcal{F}_{n, h, 1}\\}$を$n$イテレーションで$h$ステップまで動いたときのFiltration：$\\left\\{\\left(x_i^\\tau, a_i^\\tau\\right)\\right\\}_{(\\tau, i) \\in[n-1] \\times[H]} \\cup\\left\\{\\left(x_i^n, a_i^n\\right)\\right\\}_{i \\in[h]}$\n",
    "* $\\{\\mathcal{F}_{n, h, 2}\\}$を$n$イテレーションで$h$ステップまで動いき，さらに次状態が返ってきたときのFiltration：$\\left\\{\\left(x_i^\\tau, a_i^\\tau\\right)\\right\\}_{(\\tau, i) \\in[n-1] \\times[H]} \\cup\\left\\{\\left(x_i^n, a_i^n\\right)\\right\\}_{i \\in[h]} \\cup\\left\\{x_{h+1}^n\\right\\}$\n",
    "\n",
    "とします．このとき，$\\mathcal{F}_{n, h, 1}$で条件付けられたときの$\\widehat{V}^n_{h+1}$を考えると，$\\widehat{V}^n_{h+1}$に含まれるランダムネスは$x^n_{h+1}$しかありません（アルゴリズムの仕組み上成り立ちます）．よって，\n",
    "$$\n",
    "\\mathbb{E}[\\widehat{V}^n_{h+1}(x^n_{h+1}) \\mid \\mathcal{F}_{n, h, 1}] = P \\widehat{V}^n_{h+1}(x_h^n, a_h^n)\n",
    "$$\n",
    "が成り立ちます．\n",
    "ここで，\n",
    "$$\n",
    "\\epsilon^n_{h} = \\widehat{V}^n_{h+1}(x^n_{h+1}) - P \\widehat{V}^n_{h+1}(x_h^n, a_h^n)\n",
    "$$\n",
    "としましょう．すると，\n",
    "\n",
    "* $\\epsilon^n_h$は$\\mathcal{F}_{n, h, 1}$のもとでは平均ゼロの確率変数\n",
    "* $\\epsilon^n_h$は$H/2$-sub-gaussian\n",
    "* $\\epsilon^n_h$は$\\mathcal{F}_{n, h, 2}$-可測\n",
    "* $\\phi(x^n_h, a^n_h)$は$\\mathcal{F}_{n, h, 1}$-可測\n",
    "\n",
    "なので，self-normalization boundに突っ込むと，\n",
    "\n",
    "$$\n",
    "\\left\\|\\sum_{i=0}^{n-1} \\phi\\left(s_h^i, a_h^i\\right)\n",
    "\\left(\\widehat{V}^i_{h+1}(x^i_{h+1}) - P \\widehat{V}^i_{h+1}(x_h^i, a_h^i)\\right)\n",
    "\\right\\|_{\\left(\\Lambda^n_h\\right)^{-1}}\n",
    "\\leq 3 H \\sqrt{\\ln \\frac{H \\operatorname{det}\\left(\\Lambda_h^n\\right)^{1 / 2} \\operatorname{det}(\\lambda I)^{-1 / 2}}{\\delta}}\n",
    "$$\n",
    "\n",
    "が成り立ちます．あとは$\\det(\\Lambda^n_h)$を上からバウンドすれば同じです．\n",
    "\n",
    "* **コメント**：こっちのほうが明らかに簡単なのに，なんでこれやらないんだろ．\n",
    "* → これは多分今回はやっちゃダメかも．\n",
    "* 参考論文では$w_h^k \\leftarrow\\left(\\Lambda_h^k\\right)^{-1} \\sum_{\\tau=1}^{k-1} \\phi_h^\\tau\\left(x_h^\\tau, a_h^\\tau\\right) \\cdot V_{h+1}^\\tau\\left(x_{h+1}^\\tau\\right)$の形で更新していて，過去の価値関数を全部足してることに注意しましょう．これのおかげで上のバウンドが使えるみたい．\n",
    "<!-- * RL Theory Bookのリグレット解析とはちょっと違うやり方になるかも．[Provably Efficient Model-Free Constrained RL with Linear Function Approximation](https://arxiv.org/abs/2206.11889)の解析を参考にしよう． -->\n",
    "\n",
    "<!-- * $\\to$ **追加コメント**：これはLinear Mixture MDPではできるけど，Linear MDPでは多分ダメ． -->\n",
    "<!-- $\\left|\\left(\\widehat{P}_h^n(\\cdot \\mid s, a)-P(\\cdot \\mid s, a)\\right) \\cdot \\widehat{V}_{h+1}^n\\right|$ -->\n",
    "<!-- Linear MDPでは結局Model basedな解析と同じで，$\\widehat{P}_h^n(\\cdot \\mid s, a)$と$\\widehat{V}_{h+1}^n$が同じデータから出てるので，Coveringが必須． -->\n",
    "<!-- Linear Mixture MDPなら特殊な分解ができるから大丈夫． -->\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "---\n",
    "\n",
    "### リグレットの分解\n",
    "\n",
    "Optimismが成立しているので，\n",
    "$V^{\\star}-V^{\\pi_n} \\leq \\widehat{V}_0^n\\left(s_0\\right)-V_0^{\\pi_n}\\left(s_0\\right)$\n",
    "が成り立ちます．\n",
    "また，Simulation lemmaより，\n",
    "$$\n",
    "\\widehat{V}_0^n\\left(s_0\\right)-V_0^{\\pi_n}\\left(s_0\\right) \\leq \\sum_{h=0}^{H-1} \\mathbb{E}_{s, a \\sim d_h^{\\pi_n}}\\left[b_h^n(s, a)+\\left(\\widehat{P}_h^n(\\cdot \\mid s, a)-P(\\cdot \\mid s, a)\\right) \\cdot \\widehat{V}_{h+1}^n\\right]\n",
    "$$\n",
    "も成り立ちます．\n",
    "\n",
    "$\\mathcal{E}_{\\text{ model }}$より，\n",
    "$\\left(\\widehat{P}_h^n(\\cdot \\mid s, a)-P(\\cdot \\mid s, a)\\right) \\cdot \\widehat{V}_{h+1}^n \\lesssim \\beta\\|\\phi(s, a)\\|_{\\left(\\Lambda_h^n\\right)^{-1}}=b^n_h(s, a)$が成り立っています．よって，\n",
    "$$\n",
    "\\widehat{V}_0^n\\left(s_0\\right)-V_0^{\\pi_n}\\left(s_0\\right) \\leq \\sum_{h=0}^{H-1} \\mathbb{E}_{s, a \\sim d_h^{\\pi_n}}\\left[2 b_h^n(s, a)\\right] \\lesssim \\sum_{h=0}^{H-1} \\mathbb{E}_{s, a \\sim d_h^{\\pi_n}}\\left[b_h^n(s, a)\\right]\n",
    "$$\n",
    "\n",
    "まとめると，次が成立します：\n",
    "$$\n",
    "\\sum_{n=0}^{N-1}\\left(V_0^{\\star}\\left(s_0\\right)-V_0^{\\pi_n}\\left(s_0\\right)\\right) \\leq \\sum_{n=0}^{N-1} \\sum_{h=0}^{H-1} \\mathbb{E}_{s_h^n, a_h^n \\sim d_h^{\\pi_n}}\\left[b_h^n\\left(s_h^n, a_h^n\\right)\\right]\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### リグレットで合体\n",
    "\n",
    "次のElliptical potential lemmaを使ってリグレットバウンドを導出します：\n",
    "\n",
    "---\n",
    "\n",
    "* $\\sup _{s, a}\\|\\phi(s, a)\\|_2 \\leq 1$と仮定します．\n",
    "* $\\Lambda_h^n=I+\\sum_{i=0}^{n-1} \\phi\\left(s_h^i, a_h^i\\right) \\phi\\left(s_h^i, a_h^i\\right)^{\\top}$\n",
    "\n",
    "このとき，次が成立します：\n",
    "$$\n",
    "\\sum_{i=0}^{N-1} \\phi\\left(s_h^i, a_h^i\\right)\\left(\\Lambda_h^i\\right)^{-1} \\phi\\left(s_h^i, a_h^i\\right) \\leq 2 \\ln \\left(\\frac{\\operatorname{det}\\left(\\Lambda_h^{N+1}\\right)}{\\operatorname{det}(I)}\\right) \\lesssim 2 d \\ln (N)\n",
    "$$\n",
    "\n",
    "**証明**\n",
    "\n",
    "* TODO: Elliptical potential Lemmaの証明ちゃんと書こう\n",
    "\n",
    "次が成立します：\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\sum_{i=1}^N \\phi\\left(s_h^i, a_h^i\\right)\\left(\\Lambda_h^i\\right)^{-1} \\phi\\left(s_h^i, a_h^i\\right) & \\leq 2 \\sum_{i=1}^N \\ln \\left(1+\\phi\\left(s_h^i, a_h^i\\right)\\left(\\Lambda_h^i\\right)^{-1} \\phi\\left(s_h^i, a_h^i\\right)\\right) \\\\\n",
    "& \\leq 2 \\ln \\left(\\frac{\\operatorname{det}\\left(\\Lambda_h^{N+1}\\right)}{\\operatorname{det}(I)}\\right) \\\\\n",
    "& \\leq 2 d \\ln \\left(1+\\frac{N+1}{d \\lambda}\\right) \\lesssim 2 d \\ln (N) .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "最初の不等式では$0 \\leq y \\leq 1, \\ln (1+y) \\geq y / 2$を使いました．\n",
    "\n",
    "---\n",
    "\n",
    "最後に全部合体しましょう．\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\mathbb{E}\\left[N V^{\\star}-\\sum_{n=1}^N V^{\\pi_n}\\right]= & \\mathbb{E}\\left[\\mathbf{1}\\left\\{\\mathcal{E}_{\\text {model }} \\text { holds }\\right\\}\\left(N V^{\\star}-\\sum_{n=1}^N V^{\\pi_n}\\right)\\right] \\\\\n",
    "& +\\mathbb{E}\\left[\\mathbf{1}\\left\\{\\mathcal{E}_{\\text {model }} \\text { doesn't hold }\\right\\}\\left(N V^{\\star}-\\sum_{n=1}^N V^{\\pi_n}\\right)\\right] \\\\\n",
    "\\leq & \\mathbb{E}\\left[\\mathbf{1}\\left\\{\\mathcal{E}_{\\text {model }} \\text { holds }\\right\\}\\left(N V^{\\star}-\\sum_{n=1}^N V^{\\pi_n}\\right)\\right]+\\delta N H \\\\\n",
    "\\lesssim & \\mathbb{E}\\left[\\sum_{n=1}^N \\sum_{h=0}^{H-1} b_h^n\\left(s_h^n, a_h^n\\right)\\right]+\\delta N H\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成立します．ボーナスをさらに上からバウンドすれば，\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\sum_{n=1}^N \\sum_{h=0}^{H-1} b_h^n\\left(s_h^n, a_h^n\\right) & =\\beta \\sum_{n=1}^N \\sum_{h=0}^{H-1} \\sqrt{\\phi\\left(s_h^n, a_h^n\\right)^{\\top}\\left(\\Lambda_h^n\\right)^{-1} \\phi\\left(s_h^n, a_h^n\\right)} \\\\\n",
    "& =\\beta \\sum_{h=0}^{H-1} \\sum_{n=1}^N \\sqrt{\\phi\\left(s_h^n, a_h^n\\right)^{\\top}\\left(\\Lambda_h^n\\right)^{-1} \\phi\\left(s_h^n, a_h^n\\right)} \\\\\n",
    "& \\leq \\beta \\sum_{h=0}^{H-1} \\sqrt{N \\sum_{n=1}^N \\phi\\left(s_h^n, a_h^n\\right)\\left(\\Lambda_h^n\\right)^{-1} \\phi\\left(s_h^n, a_h^n\\right)} \\lesssim \\beta H \\sqrt{N d \\ln (N)}\n",
    "\\end{aligned}\n",
    "$$\n",
    "が得られます．これで証明終わりです．\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}