notebooks/RL_General_ABC_class.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 強化学習とABCクラス\n",
    "\n",
    "* 参考：[A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning](https://arxiv.org/abs/2209.15634)\n",
    "\n",
    "強化学習の複雑度として，Bellman rankやBilinear class，Bellman Eluder dimensionなど様々なものが開発されてきました．\n",
    "[Decision Estimation Coefficient](RL_General_DEC.ipynb)はかなり広範なクラスをカバーできますが，DEC用のアルゴリズムはMinimaxサンプル効率を達成しません．\n",
    "ほぼすべてのクラスを含み，かつタイトなサンプル効率になるようなクラスは作れないでしょうか？\n",
    "\n",
    "![ABC](figs/ABC.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**準備**\n",
    "\n",
    "* 仮説クラス：$\\mathcal{F}:=\\mathcal{F}_1 \\times \\ldots \\times \\mathcal{F}_H$\n",
    "    * 仮説に対する価値関数：$\\left\\{Q_f, V_f\\right\\}=\\left\\{Q_{h, f}, V_{h, f}\\right\\}_{h \\in[H]}$\n",
    "    * 仮説に対する方策：$\\pi_f(s)=\\arg \\max _\\pi \\mathbb{E}_{a \\sim \\pi}\\left[Q_{h, f}(s, a)\\right]$\n",
    "  \n",
    "次を仮定します\n",
    "\n",
    "---\n",
    "\n",
    "**Realizability**\n",
    "\n",
    "次を満たす仮説$f^* \\in \\mathcal{F}$が存在する．\n",
    "\n",
    "$$Q_h^*(s, a)=Q_{h, f^*}(s, a)$$\n",
    "\n",
    "---\n",
    "\n",
    "次のCovering numberを導入します．\n",
    "\n",
    "---\n",
    "\n",
    "**$\\epsilon$-covering number**\n",
    "\n",
    "任意の$\\epsilon > 0$と仮説クラス$\\mathcal{F}$に対して，$N_\\mathcal{F}(\\epsilon)$が次を満たすとき，$\\epsilon$-covering numberと呼びます．\n",
    "\n",
    "任意の$f \\in \\mathcal{F}$について，$\\rho\\left(f, f^{\\prime}\\right) \\leq \\epsilon$であるような$f'\\in \\mathcal{F}_\\epsilon$が存在するとき，$\\mathcal{F}_\\epsilon$の要素数のこと．\n",
    "\n",
    "---\n",
    "\n",
    "そして，Eluder dimensionを一般化するために，Functional Eluder Dimensionを導入します．\n",
    "\n",
    "---\n",
    "\n",
    "**Functional Eluder Dimension**\n",
    "\n",
    "仮説クラス$\\mathcal{F}$と$\\mathcal{F} \\times \\mathcal{F}$上の関数$G$に対して，次を満たす$\\operatorname{dim}_{F E}(\\mathcal{F}, G, \\epsilon)$を，Functional Eluder dimensionと呼びます．\n",
    "\n",
    "任意の$2 \\leq t \\leq n$と，なんらかの$\\epsilon' \\geq \\epsilon$について，$\\sqrt{\\sum_{i=1}^{t-1}\\left(G\\left(g, f_i\\right)\\right)^2} \\leq \\epsilon^{\\prime}$ while $\\left|G\\left(g, f_t\\right)\\right|>\\epsilon^{\\prime}$を満たすような$g \\in \\mathcal{F}$が存在するような最長の系列$f_1, \\ldots, f_n \\in \\mathcal{F}$の長さを$\\operatorname{dim}_{F E}(\\mathcal{F}, G, \\epsilon)$とする．\n",
    "\n",
    "---\n",
    "\n",
    "これは明らかにEluder dimensionを一般化してますね．また，例えば$G_h(g, f):=\\mathbb{E}_{\\pi_{h, f}}\\left(Q_{h, g}-\\mathcal{T}_h Q_{g, h+1}\\right)$とすれば，これはBellman Eluder dimensionと同じです．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ABCクラス\n",
    "\n",
    "準備：\n",
    "* MDP : $M$\n",
    "* $s_1, a_1, \\dots, S_H$\n",
    "* 仮説クラス：$\\mathcal{F} \\subset \\mathcal{G}$\n",
    "* $\\mathcal{V} = \\left\\{v\\left(s, a, s^{\\prime}\\right): \\mathcal{S} \\times \\mathcal{A} \\times \\mathcal{S} \\rightarrow \\mathbb{R}\\right\\}$\n",
    "* $\\ell=\\left\\{\\ell_{h, f^{\\prime}}\\right\\}_{h \\in[H], f^{\\prime} \\in \\mathcal{F}}$ は $\\mathbb{R}^{d_s}$次元関数．（**元論文の$\\ell$は根本的にNotationが間違ってそう．そもそも$f_h$とかが引数に取れないのでは？**）\n",
    "    * $o_h:=\\left(s_h, a_h, s_{h+1}\\right) \\in \\mathcal{S} \\times \\mathcal{A} \\times \\mathcal{S}, f \\in \\mathcal{F}, g \\in \\mathcal{G}$ and $v \\in \\mathcal{V}$ を入力されると，Bellman 誤差のSurrogateを返します．\n",
    "    * また，$\\left\\|\\ell_{h, f^{\\prime}}\\left(\\cdot, f, g, v\\right)\\right\\|_2 \\leq R$ for $\\forall h \\in[H], f^{\\prime}, f \\in \\mathcal{F}, g \\in \\mathcal{G}, v \\in \\mathcal{V}$を仮定します．\n",
    "* $G_{h, f^*}(f, g)$を$\\mathcal{F}\\times \\mathcal{F}$上の関数とし，$f, g\\in \\mathcal{F}$同士の関係を表す関数とします（後で具体例が出ます）\n",
    "\n",
    "このとき，次のAdmissible Bellman Characterizationを導入します．\n",
    "\n",
    "---\n",
    "\n",
    "**Admissible Bellman Characterization**\n",
    "\n",
    "MDP $M$，realizabilityを満たす仮説クラス$\\mathcal{F} \\subset \\mathcal{G}$，そして，推定関数$\\ell_{h, f'}: (\\mathcal{S} \\times \\mathcal{A} \\times \\mathcal{S}) \\times \\mathcal{F} \\times \\mathcal{G} \\times \\mathcal{V} \\rightarrow \\mathbb{R}^{\\mathbb{d}_s}$，探索方策$\\pi_{\\text{op}}$そして定数$\\kappa (0, 1]$に対して，次を満たすGを，$(M, \\mathcal{F}, \\mathcal{G}, \\ell)$のadmissible Bellman characterizationと呼びます：\n",
    "\n",
    "1. Dominating Average Estimation Function: 任意の$f, g\\in \\mathcal{F}$について，\n",
    "\n",
    "$$\n",
    "\\max _{v \\in \\mathcal{V}} \\mathbb{E}_{s_h \\sim \\pi_g, a_h \\sim \\pi_{\\mathrm{op}}}\\left\\|\\mathbb{E}_{s_{h+1}}\\left[\\ell_{h, g}\\left(o_h, f, f, v\\right) \\mid s_h, a_h\\right]\\right\\|_2^2 \\geq\\left(G_{h, f^*}(f, g)\\right)^2\n",
    "$$\n",
    "\n",
    "2. Bellman Dominance: 任意の$(h, f) \\in [H] \\times \\mathcal{F}$について，\n",
    "\n",
    "$$\n",
    "\\kappa \\cdot\\left|\\mathbb{E}_{s_h, a_h \\sim \\pi_f}\\left[Q_{h, f}\\left(s_h, a_h\\right)-r\\left(s_h, a_h\\right)-V_{h+1, f}\\left(s_{h+1}\\right)\\right]\\right| \\leq\\left|G_{h, f *}(f, f)\\right|\n",
    "$$\n",
    "\n",
    "また，\n",
    "$(M, \\mathcal{F}, \\mathcal{G}, \\ell)$のことを，ABCクラスと呼びます．\n",
    "\n",
    "---\n",
    "\n",
    "**Decomposable Estimation Function**\n",
    "\n",
    "推定関数\n",
    "$\\ell_{h, f'}: (\\mathcal{S} \\times \\mathcal{A} \\times \\mathcal{S}) \\times \\mathcal{F} \\times \\mathcal{G} \\times \\mathcal{V} \\rightarrow \\mathbb{R}^{\\mathbb{d}_s}$に対して，\n",
    "次の構造を考えます．\n",
    "\n",
    "1. （**Decomposability**）: 任意の$f \\in \\mathcal{F},\\left(h, f^{\\prime}, g, v\\right) \\in[H] \\times \\mathcal{F} \\times \\mathcal{G} \\times \\mathcal{V}$と任意の$o_h$について，次を満たす写像$\\mathcal{T}(\\cdot): \\mathcal{F}\\to \\mathcal{G}$が存在する：\n",
    "$$\n",
    "\\ell_{h, f^{\\prime}}\\left(o_h, f, g, v\\right)-\\mathbb{E}_{s_{h+1}}\\left[\\ell_{h, f^{\\prime}}\\left(o_h, f, g, v\\right) \\mid s_h, a_h\\right]=\\ell_{h, f^{\\prime}}\\left(o_h, f, \\mathcal{T}(f), v\\right)\n",
    "$$\n",
    "また，$f=f^*$なら，$\\mathcal{T}(f)=f^*$であるとする．\n",
    "（Decomposabilityは推定関数がベルマン誤差っぽい挙動をしていることを表してます．）\n",
    "\n",
    "例えば\n",
    "$$\n",
    "\\ell_{h, f^{\\prime}}\\left(o_h, f, g, v\\right):=Q_{h, g}\\left(s_h, a_h\\right)-r\\left(s_h, a_h\\right)-V_{h+1, f}\\left(s_{h+1}\\right)\n",
    "$$\n",
    "の場合は，$\\mathcal{T}_h$を$h$ステップ目のベルマン作用素とすれば，\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& {\\left[Q_{h, g}\\left(s_h, a_h\\right)-r\\left(s_h, a_h\\right)-V_{h+1, f}\\left(s_{h+1}\\right)\\right]-\\left[Q_{h, g}\\left(s_h, a_h\\right) - \\left(\\mathcal{T}_h V_{h+1, f}\\right)\\left(s_h, a_h\\right)\\right]} \\\\\n",
    "& =\\left(\\mathcal{T}_h V_{h+1, f}\\right)\\left(s_h, a_h\\right)-r\\left(s_h, a_h\\right)-V_{h+1, f}\\left(s_{h+1}\\right) .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "と同じです．\n",
    "\n",
    "また，特に$f=g=f^*$なら，\n",
    "$$\n",
    "\\ell_{h, f^{\\prime}}\\left(o_h, f^*, f^*, v\\right)-\\mathbb{E}_{s_{h+1}}\\left[\\ell_{h, f^{\\prime}}\\left(o_h, f^*, f^*, v\\right) \\mid s_h, a_h\\right]=\\ell_{h, f^{\\prime}}\\left(o_h, f^*, f^*, v\\right)\n",
    "$$\n",
    "なので，\n",
    "$$\n",
    "\\mathbb{E}_{s_{h+1}}\\left[\\ell_{h, f^{\\prime}}\\left(o_h, f^*, f^*, v\\right) \\mid s_h, a_h\\right]=0\n",
    "$$\n",
    "です．\n",
    "\n",
    "2. (**Global Discriminator Optimality**): 与えられた任意の$f \\in \\mathcal{F}$と$h \\in [H]$に対して，次を満たす大域的極大値$v^*_h(f) \\in \\mathcal{V}$が存在する．任意の$\\left(f', v\\right) \\in \\mathcal{F} \\times \\mathcal{V}$と$o_h$について，\n",
    "$$\n",
    "\\left\\|\\mathbb{E}_{s_{h+1}}\\left[\\ell_{h, f'}\\left(o_h, f, f, v_h^*(f)\\right) \\mid s_h, a_h\\right]\\right\\|_2 \\geq\\left\\|\\mathbb{E}_{s_{h+1}}\\left[\\ell_{h, f'}\\left(o_h, f, f, v\\right) \\mid s_h, a_h\\right]\\right\\|_2\n",
    "$$\n",
    "（任意の$(s_h, a_h)$に対して，discriminatorの大域的極大値が存在することが重要っぽいです）\n",
    "\n",
    "\n",
    "最後に，Estimation functionにリプシッツ連続性を導入します．\n",
    "\n",
    "---\n",
    "\n",
    "**リプシッツ連続性**\n",
    "\n",
    "任意の\n",
    "$\\left(h, f^{\\prime}, f, g, v\\right) \\in [H] \\times \\mathcal{F} \\times \\mathcal{F} \\times \\mathcal{G} \\times \\mathcal{V},\\left(\\tilde{f}, \\tilde{g}, \\tilde{v}, \\tilde{f}^{\\prime}\\right) \\in \\mathcal{F} \\times \\mathcal{G} \\times \\mathcal{V} \\times \\mathcal{F}$そして任意の$o_h$について，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\left\\|\\ell_{h, f^{\\prime}}(\\cdot, f, g, v)-\\ell_{h, f^{\\prime}}(\\cdot, \\tilde{f}, g, v)\\right\\|_{\\infty} \\leq L \\rho(f, \\tilde{f}), \\quad\\left\\|\\ell_{h, f^{\\prime}}(\\cdot, f, g, v)-\\ell_{h, f^{\\prime}}(\\cdot, f, \\tilde{g}, v)\\right\\|_{\\infty} \\leq L \\rho(g, \\tilde{g}), \\\\\n",
    "& \\left\\|\\ell_{h, f^{\\prime}}(\\cdot, f, g, v)-\\ell_{h, f^{\\prime}}(\\cdot, f, g, \\widetilde{v})\\right\\|_{\\infty} \\leq L\\|v-\\widetilde{v}\\|_{\\infty}, \\quad\\left\\|\\ell_{h, f^{\\prime}}(\\cdot, f, g, v)-\\ell_{h, \\tilde{f}^{\\prime}}(\\cdot, f, g, v)\\right\\|_{\\infty} \\leq L \\rho\\left(f^{\\prime}, \\tilde{f}^{\\prime}\\right) .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "を満たすような$L > 0$が存在する．\n",
    "\n",
    "---\n",
    "\n",
    "また，\n",
    "$\\mathcal{L}=\\left\\{\\ell_{h, f^{\\prime}}(\\cdot, f, g, v):\\left(h, f^{\\prime}, f, g, v\\right) \\in[H] \\times\n",
    "\\mathcal{F} \\times \\mathcal{F} \\times \\mathcal{G} \\times \\mathcal{V}\\right\\} $\n",
    "を，誘導される推定関数のクラスとします．\n",
    "ちなみに上のリプシッツ関数の仮定のもとでは，\n",
    "$N_{\\mathcal{L}}(\\epsilon) \\leq N_{\\mathcal{F}}^2\\left(\\frac{\\epsilon}{4 L}\\right) N_{\\mathcal{G}}\\left(\\frac{\\epsilon}{4 L}\\right) N_{\\mathcal{V}}\\left(\\frac{\\epsilon}{4 L}\\right)$\n",
    "が成立します．ここで，\n",
    "$N_{\\mathcal{F}}(\\epsilon), N_{\\mathcal{G}}(\\epsilon), N_{\\mathcal{F}}(\\epsilon)$\n",
    "はそれぞれ対応する仮説クラスの$\\epsilon$-covering numberです．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ABCクラスに含まれるMDPの例\n",
    "\n",
    "### Low BE dimension\n",
    "\n",
    "$$\n",
    "\\ell_{h, f^{\\prime}}\\left(o_h, f, g, v\\right):=Q_{h, g}\\left(s_h, a_h\\right)-r_h-V_{h+1, f}\\left(s_{h+1}\\right) .\n",
    "$$\n",
    "として，\n",
    "$$\n",
    "G_{h, f^*}(f, g)=\\mathbb{E}_{s_h \\sim \\pi_g, a_h \\sim \\pi_{\\mathrm{op}}}\\left[Q_{h, f}\\left(s_h, a_h\\right)-r_h-V_{h+1, f}\\left(s_{h+1}\\right)\\right]\n",
    "$$\n",
    "とします．また，$g=f$とします．すると，$G$についてのFE dimensionはBE dimensionと同じです（少々ややこしいですが，Distributional Eluder dimensionの定義と，元論文における$\\Pi$の選び方ですぐわかります．）．\n",
    "つまり，これはLow BE dimensionの場合の問題設定になります．\n",
    "\n",
    "**注意** モデルフリーの場合は$Q_{h, g}$と$V_{h+1, f}$において，$g$と$f$はそれぞれ$h$ステップ目と$h+1$ステップ目のQとV値を表します．そのため，表記としては$g_h$, $f_{h+1}$みたいにしても良さそうです．しかし，モデルベースの場合は$Q_{h, g}$みたいに全てのステップの仮説から$Q_h$が誘導されるので，$g_h$としてはいけないと思われます．\n",
    "\n",
    "### Linear Mixture MDP\n",
    "\n",
    "ヒルベルト空間$\\mathcal{H}$について，\n",
    "$\\phi\\left(s, a, s^{\\prime}\\right): \\mathcal{S} \\times \\mathcal{A} \\times \\mathcal{S} \\rightarrow \\mathcal{H}, \\psi(s, a): \\mathcal{S} \\times \\mathcal{A} \\rightarrow \\mathcal{H}$\n",
    "および未知の$\\theta^*\\in \\mathcal{H}$を考えます．Linear mixture MDPでは，\n",
    "\n",
    "$$\n",
    "\\mathbb{P}_h\\left(s^{\\prime} \\mid s, a\\right)=\\left\\langle\\theta_h^*, \\phi\\left(s, a, s^{\\prime}\\right)\\right\\rangle, \\quad r(s, a)=\\left\\langle\\theta_h^*, \\psi(s, a)\\right\\rangle\n",
    "$$\n",
    "\n",
    "が成立します．仮説クラスを$\\mathcal{F}_h=\\mathcal{G}_h=\\left\\{\\theta_h \\in \\mathcal{H}\\right\\}$としましょう．このとき，\n",
    "\n",
    "$$\n",
    "\\ell_{h, f^{\\prime}}\\left(o_h, f, g, v\\right)=\\theta_{h, g}^{\\top}\\left[\\psi\\left(s_h, a_h\\right)+\\sum_{s^{\\prime}} \\phi\\left(s_h, a_h, s^{\\prime}\\right) V_{h+1, f^{\\prime}}\\left(s^{\\prime}\\right)\\right]-r_h-V_{h+1, f^{\\prime}}\\left(s_{h+1}\\right)\n",
    "$$\n",
    "\n",
    "および\n",
    "\n",
    "$$\n",
    "G_{h, f^*}(f, g)=\\left\\langle\\theta_{h, g}-\\theta_h^*, \\mathbb{E}_{s_h, a_h \\sim \\pi_f}\\left[\\psi\\left(s_h, a_h\\right)+\\sum_{s^{\\prime}} \\phi\\left(s_h, a_h, s^{\\prime}\\right) V_{h+1, f}\\left(s^{\\prime}\\right)\\right]\\right\\rangle\n",
    "$$\n",
    "\n",
    "とすれば，ABCクラスはLinear mixture MDPと等価です．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Witness rankとABCクラス\n",
    "\n",
    "Witness rankの定義を思い出しましょう．\n",
    "\n",
    "discriminator class $\\mathcal{V}=\\left\\{\\mathcal{V}_h\\right\\}_{h \\in[H]}, \\mathcal{V}_h \\subset \\mathcal{S} \\times \\mathcal{A} \\times \\mathcal{S} \\mapsto \\mathbb{R}$と仮説クラス$\\mathcal{F}$に対して，Witness rankは\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\max _{v \\in \\mathcal{V}_h} \\mathbb{E}_{s_h \\sim \\pi_f, a_h \\sim \\pi_g}\\left[\\mathbb{E}_{\\widetilde{s} \\sim g_h} v\\left(s_h, a_h, \\widetilde{s}\\right)-\\mathbb{E}_{\\widetilde{s} \\sim \\mathbb{P}_h} v\\left(s_h, a_h, \\widetilde{s}\\right)\\right] \\geq\\left\\langle W_h(g), X_h(f)\\right\\rangle, \\\\\n",
    "& \\kappa \\cdot \\mathbb{E}_{s_h \\sim \\pi_f, a_h \\sim \\pi_g}\\left[\\mathbb{E}_{\\widetilde{s} \\sim g_h} V_{h+1, g}(\\widetilde{s})-\\mathbb{E}_{\\widetilde{s} \\sim \\mathbb{P}_h} V_{h+1, g}(\\widetilde{s})\\right] \\leq\\left\\langle W_h(g), X_h(f)\\right\\rangle . \\\\\n",
    "&\n",
    "\\end{aligned}\n",
    "$$\n",
    "が成り立つ場合の$X_h$および$W_h$の次元数です．\n",
    "\n",
    "このとき，\n",
    "* $\\ell_{h, f^{\\prime}}\\left(o_h, f, g, v\\right)=\\mathbb{E}_{\\widetilde{s} \\sim g_h} v\\left(s_h, a_h, \\widetilde{s}\\right)-v\\left(s_h, a_h, s_{h+1}\\right)$\n",
    "* $G_{h, f^*}(f, g)=\\left\\langle W_h(g), X_h(f)\\right\\rangle$\n",
    "\n",
    "とすれば，low witness rankはlow FE dimensionになります．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Operaアルゴリズム\n",
    "\n",
    "ABCクラスに対して，次のOPERAアルゴリズムを考えます．\n",
    "\n",
    "![OPERA](figs/OPERA.png)\n",
    "\n",
    "\n",
    "このアルゴリズムについて，次のリグレットバウンドが成立します．\n",
    "\n",
    "---\n",
    "\n",
    "MDP $M$と仮説クラス$\\mathcal{F}, \\mathcal{G}$，Decomposable Estimation Function $\\ell$，そして admissible Bellman characterization $G$を考えます．また，$(M, \\mathcal{F}, \\mathcal{G}, \\ell, G)$がABCクラスであり，Low functional eluder dimensionであるとします．このとき，任意の$\\delta \\in (0, 1)$について，\n",
    "$\\beta=\\mathcal{O}\\left(\\log \\left(T H N_{\\mathcal{L}}(1 / T) / \\delta\\right)\\right)$とします．\n",
    "このとき，on-policyな場合，つまり，$\\pi_{\\mathrm{op}}=\\pi_{\\mathrm{est}}=\\pi^t$のとき，リグレットは\n",
    "\n",
    "$$\n",
    "\\operatorname{Regret}(T)=\\mathcal{O}\\left(\\frac{H}{\\kappa} \\sqrt{T \\cdot \\operatorname{dim}_{\\mathrm{FE}}(\\mathcal{F}, G, \\sqrt{1 / T}) \\cdot \\beta}\\right)\n",
    "$$\n",
    "\n",
    "で抑えられます．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "**証明**\n",
    "\n",
    "### ステップ１：$f^*$の実行可能性\n",
    "\n",
    "まず，$f^*$が実行可能解であることを示します．\n",
    "\n",
    "---\n",
    "\n",
    "アルゴリズム１において，$\\rho > 0$と$\\delta > 0$に対して，\n",
    "$\\beta = c\\left(\\log \\left(T H \\mathcal{N}_{\\mathcal{L}}(\\rho) / \\delta\\right)+T\\rho \\right)$\n",
    "を十分大きな$c$で設定するとします．\n",
    "ここで$\\rho$は$\\mathcal{L}$の$\\epsilon$-covering numberかな？\n",
    "このとき，確率$1-\\delta$以上で，\n",
    "\n",
    "$$\n",
    "\\max _{v \\in \\mathcal{V}}\\left\\{\\sum_{i=1}^{t-1}\\left\\|\\ell_{h, f_h^i}\\left(o_h^i, f^*, f^*, v\\right)\\right\\|_2^2-\\inf _{g \\in \\mathcal{G}} \\sum_{i=1}^{t-1}\\left\\|\\ell_{h, f_h^i}\\left(o_h^i, f^*, g, v\\right)\\right\\|_2^2\\right\\} \\leq \\mathcal{O}(\\beta)\n",
    "$$\n",
    "\n",
    "が任意の$t\\in T$で成立します．\n",
    "\n",
    "**証明**\n",
    "\n",
    "まずは固定された$f \\in \\mathcal{F}$と$v \\in \\mathcal{V}$を考えます．\n",
    "\n",
    "データセット\n",
    "$\\mathcal{D}_h=\\left\\{r_h^t, s_h^t, a_h^t, s_{h+1}^t\\right\\}_{t=1,2, \\ldots T}$\n",
    "について，\n",
    "$$\n",
    "X_i(h, f, v):=\\left\\|\\ell_{h, f^i}\\left(o_h^i, f^*, f, v\\right)\\right\\|_2^2-\\left\\|\\ell_{h, f^i}\\left(o_h^i, f^*, f^*, v\\right)\\right\\|_2^2 .\n",
    "$$\n",
    "なる確率変数を導入します．\n",
    "このとき，$\\left|X_t(h, f, v)\\right| \\leq R^2$です．\n",
    "また，$s_{h+1}$についての期待値を考えると，$\\|a\\|^2-\\|b\\|^2=\\langle a-b, a+b\\rangle$から，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\mathbb{E}_{s_{h+1}}\\left[X_i(h, f, v) \\mid s_h, a_h\\right] \\\\\n",
    "& =\\mathbb{E}_{s_{h+1}}\\left[\\left\\|\\ell_{h, f^i}\\left(o_h^i, f^*, f, v\\right)\\right\\|_2^2-\\left\\|\\ell_{h, f^i}\\left(o_h^i, f^*, f^*, v\\right)\\right\\|_2^2 \\mid s_h, a_h\\right]\\\\\n",
    "& = \\mathbb{E}_{s_{h+1}}\\left[\\left\\langle\\ell_{h, f^i}\\left(o_h^i, f^*, f, v\\right)-\\ell_{h, f^{\\prime}}\\left(o_h^i, f^*, f^*, v\\right), \\ell_{h, f^i}\\left(o_h^i, f^*, f, v\\right)+\\ell_{h, f^{\\prime}}\\left(o_h^i, f^*, f^*, v\\right)\\right\\rangle  \\mid s_h, a_h\\right]\\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "が成り立ちます（元論文は普通に表記ミスってる）．ここで，Decomposabilityから\n",
    "$$\n",
    "\\ell_{h, f^{\\prime}}\\left(o_h, f^*, f, v\\right)-\\ell_{h, f^{\\prime}}\\left(o_h, f^*, f^*, v\\right)\n",
    "=\\mathbb{E}_{s_{h+1}}\\left[\\ell_{h, f^{\\prime}}\\left(o_h, f^*, f, v\\right) \\mid s_h, a_h\\right]\n",
    "$$\n",
    "\n",
    "なので，\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\mathbb{E}_{s_{h+1}}\\left[X_i(h, f, v) \\mid s_h, a_h\\right] \\\\\n",
    "& = \\mathbb{E}_{s_{h+1}}\\left[\\left\\langle\\ell_{h, f^i}\\left(o_h^i, f^*, f, v\\right)-\\ell_{h, f^{\\prime}}\\left(o_h^i, f^*, f^*, v\\right), \\ell_{h, f^i}\\left(o_h^i, f^*, f, v\\right)+\\ell_{h, f^{\\prime}}\\left(o_h^i, f^*, f^*_h, v\\right)\\right\\rangle  \\mid s_h, a_h\\right]\\\\\n",
    "& = \\mathbb{E}_{s_{h+1}}\\left[\\left\\langle \\mathbb{E}_{s_{h+1}}\\left[\\ell_{h, f^{\\prime}}\\left(o_h, f^*, f, v\\right) \\mid s_h, a_h\\right] , \\ell_{h, f^i}\\left(o_h^i, f^*, f, v\\right)+\\ell_{h, f^{\\prime}}\\left(o_h^i, f^*, f^*, v\\right)\\right\\rangle  \\mid s_h, a_h\\right]\\\\\n",
    "& = \\left\\langle \\mathbb{E}_{s_{h+1}}\\left[\\ell_{h, f^{\\prime}}\\left(o_h, f^*, f, v\\right) \\mid s_h, a_h\\right] , \\mathbb{E}_{s_{h+1}}\\left[\\ell_{h, f^i}\\left(o_h^i, f^*, f, v\\right)+\\ell_{h, f^{\\prime}}\\left(o_h^i, f^*, f^*, v\\right) \\mid s_h, a_h\\right]\\right\\rangle \\\\\n",
    "& = \\left\\langle \\mathbb{E}_{s_{h+1}}\\left[\\ell_{h, f^{\\prime}}\\left(o_h, f^*, f, v\\right) \\mid s_h, a_h\\right] , \\mathbb{E}_{s_{h+1}}\\left[\\ell_{h, f^i}\\left(o_h^i, f^*, f, v\\right)  \\mid s_h, a_h\\right]\\right\\rangle\\\\\n",
    "&=\\left\\|\\mathbb{E}_{s_{h+1}}\\left[\\ell_{h, f^i}\\left(o_h^i, f, f, v\\right) \\mid s_h, a_h\\right]\\right\\|_2^2 .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "一方で，\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\mathbb{E}_{s_{h+1}}\\left[\\left(X_i(h, f, v)\\right)^2 \\mid s_h, a_h\\right] \n",
    "\\leq & \\mathbb{E}_{s_{h+1}}\\left[\\| \\ell_{h, f^i}\\left(o_h^i, f^*, f, v\\right)-\\ell_{h, f^i}\\left(o_h^i, f^*, f^*, v\\right)\\|_2^2 \\right.\\\\\n",
    "& \\left.\\cdot\\left\\|\\ell_{h, f^{\\prime}}\\left(o_h^i, f^*, f, v\\right)+\\ell_{h, f^{\\prime}}\\left(o_h^i, f^*, f^*, v\\right)\\right\\|_2^2 \\mid s_h, a_h\\right] \\\\\n",
    "\\leq & 4\\left\\|\\mathbb{E}_{s_{h+1}}\\left[\\ell_{h, f^i}\\left(o_h^i, f, f, v\\right) \\mid s_h, a_h\\right]\\right\\|_2^2 R^2 \\\\\n",
    "\\leq & 4 R^2 \\mathbb{E}_{s_{h+1}}\\left[X_i(h, f, v) \\mid s_h, a_h\\right] .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "も成り立ちます．２行目の変形にはDecomposabilityと$\\ell$の上界を使えばいけます．３行目ではひとつ上の等式変形を使いました．\n",
    "\n",
    "\n",
    "ここで，Freedmanの不等式を導入します：\n",
    "\n",
    "---\n",
    "\n",
    "**Freedmanの不等式**\n",
    "\n",
    "$X_1, X_2, \\dots, X_T$を実数の確率変数の列とします．\n",
    "任意の$t\\in \\{1, 2, \\dots, T\\}$において，$X_t \\leq R$および$\\mathbb{E}\\left[X_t \\mid X_1, \\ldots, X_{t-1}\\right]=0$とします．\n",
    "このとき，任意の$\\delta \\in (0, 1)$ と$\\eta \\in [0, 1/R]$について，確率$1-\\delta$以上で，\n",
    "\n",
    "$$\n",
    "\\sum_{t=1}^T X_t \n",
    "\\leq(e-2) \\eta \\sum_{t=1}^T \\mathbb{E}\\left[X_t^2 \\mid X_1, \\dots, X_{t-1} \\right]+\\frac{\\log \\left(\\delta^{-1}\\right)}{\\eta}\n",
    "$$\n",
    "\n",
    "証明は[Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://arxiv.org/abs/1402.0555)を参考にしてください．\n",
    "\n",
    "---\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ここで，\n",
    "$Z_t=\\mathbb{E}_{s_{h+1}}\\left[X_t(h, f, v) \\mid s_h, a_h\\right] - X_t(h, f, v)$ とすると，$\\mathbb{E}[Z_t\\mid Z_1, \\dots, Z_{t-1}]=0$であり，$\\left|Z_t\\right| \\leq 2 R^2$です．\n",
    "\n",
    "Freedmanの不等式を使うと，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\sum_{i=1}^t \\mathbb{E}_{s_{h+1}}\\left[X_i(h, f, v) \\mid s_h, a_h\\right] - \\sum_{i=1}^t X_i(h, f, v)\\\\\n",
    "\\leq & (e-2) \\eta \\sum_{i=1}^t \\mathbb{E}_{s_{h+1}}\\left[\\left(X_i(h, f, v) - \\mathbb{E}_{s_{h+1}}\\left[X_i(h, f, v) \\mid s_h, a_h\\right]\\right)^2\\mid s_h, a_h\\right] +\\frac{\\log \\left(\\delta^{-1}\\right)}{\\eta}\\\\\n",
    "\\leq & (e-2) \\eta \\sum_{i=1}^t \\mathbb{E}_{s_{h+1}}\\left[\\left(X_i(h, f, v)\\right)^2\\mid s_h, a_h\\right] +\\frac{\\log \\left(\\delta^{-1}\\right)}{\\eta}\\\\\n",
    "\\leq & (e-2) 4 R^2 \\eta \\sum_{i=1}^t \\mathbb{E}_{s_{h+1}}\\left[X_i(h, f, v) \\mid s_h, a_h\\right] +\\frac{\\log \\left(\\delta^{-1}\\right)}{\\eta}\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が成立します．\n",
    "ここで２つ目は$\\mathbb{V}[X]= \\mathbb{E}[X^2] - (\\mathbb{E}[X])^2 \\leq \\mathbb{E}[X^2]$を使っており，３つ目は上でやった不等式です．\n",
    " \n",
    "$\\eta=\\frac{1}{4(e-2) R^2}$とすると，\n",
    "$$\n",
    "\\begin{aligned}\n",
    "- \\sum_{i=1}^t X_i(h, f, v)\n",
    "\\leq 4(e-2) R^2\\log \\left(\\delta^{-1}\\right) = \\mathcal{O}(R^2 \\log(\\delta^{-1}))\n",
    "\\end{aligned}\n",
    "$$\n",
    "が確率$1-\\delta$以上で成立します．\n",
    "\n",
    "続いて，この結果を任意の$f$と$v$に拡張しましょう．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "まず，リプシッツ連続性の仮定より，$\\mathcal{L}$のcovering numberは$\\mathcal{F}, \\mathcal{G}, \\mathcal{V}$のcovering numberで抑えることができます．\n",
    "よって，任意の$\\ell_{h, f^{\\prime}}(\\cdot, f, g, v)$と$\\rho > 0$について，$\\tilde{\\rho}$と$\\left(\\tilde{f}^{\\prime}, \\tilde{f}, \\widetilde{g}, \\widetilde{v}\\right) \\in \\mathcal{F}_{\\widetilde{\\rho}} \\times \\mathcal{F}_{\\widetilde{\\rho}} \\times \\mathcal{G}_{\\widetilde{\\rho}} \\times \\mathcal{V}_{\\widetilde{\\rho}}$が存在し，\n",
    "\n",
    "$$\n",
    "\\left\\|\\ell_{h, \\widetilde{f}^{\\prime}}(\\cdot, \\widetilde{f}, \\widetilde{g}, \\widetilde{v})-\\ell_{h, f^{\\prime}}(\\cdot, f, g, v)\\right\\|_{\\infty}\n",
    "\\leq \\rho\n",
    "$$\n",
    "が成立します．ここで，$\\mathcal{F}_{\\widetilde{\\rho}}, \\mathcal{G}_{\\widetilde{\\rho}}, \\mathcal{V}_{\\widetilde{\\rho}}$は$\\mathcal{F}, \\mathcal{G}, \\mathcal{V}$の$\\tilde{\\rho}$-coverです．\n",
    "つまり，$\\left(\\widetilde{f^{\\prime}}, \\widetilde{f}, \\widetilde{g}, \\widetilde{v}\\right) \\in \\mathcal{L}_\\rho$が成立してます．\n",
    "\n",
    "$$\n",
    "\\tilde{X}_i(h, \\tilde{f}, \\widetilde{v}):=\\left\\|\\ell_{h, \\tilde{f}^i}\\left(o_h^i, {f}^*, \\tilde{f}, \\widetilde{v}\\right)\\right\\|_2^2-\\left\\|\\ell_{h, \\tilde{f}^i}\\left(o_h^i, {f}^*, {f}^*, \\widetilde{v}\\right)\\right\\|_2^2\n",
    "$$\n",
    "および\n",
    "$$\n",
    "\\iota=\\log \\left(\\frac{H T \\mathcal{N}_{\\mathcal{L}}(\\rho)}{\\delta}\\right)\n",
    "$$\n",
    "とします．\n",
    "$\\mathcal{L}_\\rho$上のUnion boundを取ると，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "- \\sum_{i=1}^t \\tilde{X}_i(h, \\tilde{f}, \\tilde{v})\n",
    "\\leq \\mathcal{O}(R^2 \\iota)\n",
    "\\end{aligned}\n",
    "$$\n",
    "が任意の$(\\tilde{f}^i, \\tilde{f}, \\tilde{v}) \\in \\mathcal{L}_\\rho$で成立します．\n",
    "\n",
    "さて，$X_i(h, f, v)$について，covering numberを使えば（多分$|X_i - \\tilde{X}_i| \\leq \\rho$になるように選べるはず）\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "-\\sum_{i=1}^{t} X_i\\left(h, {f}, v\\right)\n",
    "=&-\\sum_{i=1}^{t} \n",
    "\\widetilde{X}_i\\left(h, \\widetilde{f}, \\widetilde{v}\\right)\n",
    "+ X_i\\left(h, {f}, v\\right)\n",
    "-\\widetilde{X}_i\\left(h, \\widetilde{f}, \\widetilde{v}\\right)\\\\\n",
    "\\leq&-\\sum_{i=1}^{t} \n",
    "\\widetilde{X}_i\\left(h, \\widetilde{f}, \\widetilde{v}\\right)\n",
    "+ |X_i\\left(h, {f}, v\\right) -\\widetilde{X}_i\\left(h, \\widetilde{f}, \\widetilde{v}\\right)|\\\\\n",
    "\\leq &\\mathcal{O}(R^2 \\iota + Rt\\rho)\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "が任意の$f, v$で成立する．\n",
    "これで証明終わりです．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ステップ２（リグレットの分解）\n",
    "\n",
    "ステップ１よりOptimismが成立し，\n",
    "\n",
    "$$V_1^*\\left(s_1\\right)-V_1^{\\pi^t}\\left(s_1\\right) \\leq V_{1, f^t}\\left(s_1\\right)-V_1^{\\pi^t}\\left(s_1\\right)$$\n",
    "\n",
    "が成立します．Performance difference Lemma を使えば，\n",
    "\n",
    "$$\n",
    "V_1^*\\left(s_1\\right)-V_1^{\\pi^t}\\left(s_1\\right) \\leq V_{1, f^t}\\left(s_1\\right)-V_1^{\\pi^t}\\left(s_1\\right)=\\sum_{h=1}^H \\mathbb{E}_{s_h, a_h \\sim \\pi^t}\\left[Q_{h, f^t}\\left(s_h, a_h\\right)-r_h-V_{h+1, f^t}\\left(s_{h+1}\\right)\\right]\n",
    "$$\n",
    "\n",
    "が成り立ちます．"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ステップ３\n",
    "\n",
    "最後にリグレットをバウンドするために，ABCクラスのBellman Dominanceを使います．\n",
    "$$\n",
    "\\kappa \\cdot\\left|\\mathbb{E}_{s_h, a_h \\sim \\pi_f}\\left[Q_{h, f}\\left(s_h, a_h\\right)-r\\left(s_h, a_h\\right)-V_{h+1, f}\\left(s_{h+1}\\right)\\right]\\right| \\leq\\left|G_{h, f^*}(f, f)\\right| .\n",
    "$$\n",
    "\n",
    "これを使うと，\n",
    "$$\n",
    "\\sum_{t=1}^T V_1^*\\left(s_1\\right)-V_1^{\\pi^t}\\left(s_1\\right) \\leq \\frac{1}{\\kappa} \\sum_{t=1}^T \\sum_{h=1}^H\\left|G_{h, f^*}\\left(f^t, f^t\\right)\\right|\n",
    "$$\n",
    "が成立します．\n",
    "\n",
    "なので$\\sum_{t=1}^T \\sum_{h=1}^H\\left|G_{h, f^*}\\left(f^t, f^t\\right)\\right|$を上から抑えたいわけですね．\n",
    "そのために，次の定理を証明します．\n",
    "\n",
    "---\n",
    "\n",
    "アルゴリズム１において，任意の$\\rho > 0$と$\\delta > 0$において，$\\beta=c\\left(\\log \\left(T H \\mathcal{N}_{\\mathcal{L}}(\\rho) / \\delta\\right)+T \\rho\\right)$とします．また，定数$c$は十分大きいとします．\n",
    "このとき，確率$1-\\delta$以上で，任意の$(t, h) \\in[T] \\times[H]$について，\n",
    "\n",
    "$$\\sum_{i=1}^{t-1}\\left(G_{h, f^*}\\left(f^t, f^i\\right)\\right)^2 \\leq \\mathcal{O}(\\beta)$$\n",
    "\n",
    "が成立します．\n",
    "\n",
    "---\n",
    "\n",
    "証明はDominating Average Estimation Functionの性質と，$f^*$の実行可能解の証明を合体させたらできます．\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ステップ４\n",
    "\n",
    "$\\sum_{i=1}^t\\left|G\\left(f_i, g_i\\right)\\right|$をFunctional Eluder dimensionとステップ３をつかってバウンドします．\n",
    "次が成立します．\n",
    "\n",
    "---\n",
    "\n",
    "仮説クラス$\\mathcal{F}$とcoupling function $G(\\cdot, \\cdot): \\mathcal{F} \\times \\mathcal{F}\\to \\mathbb{R}$かつ$\\|G\\|_\\infty \\leq C$を考えます．\n",
    "$\\sum_{i=1}^{t-1}\\left(G\\left(f_t, g_i\\right)\\right)^2 \\leq \\beta$を全ての$t\\in [T]$で満たすような任意の系列\n",
    "$\\left\\{f_t\\right\\}_{t \\in[T]},\\left\\{g_t\\right\\}_{t \\in[T]} \\subseteq \\mathcal{F}$\n",
    "について，次の不等式が任意の$t \\in [T]$と$\\omega > 0$で成立します．\n",
    "\n",
    "$$\n",
    "\\sum_{i=1}^t\\left|G\\left(f_i, g_i\\right)\\right| \\leq \\mathcal{O}\\left(\\sqrt{\\operatorname{dim}_{\\mathrm{FE}}(\\mathcal{F}, G, \\omega) \\beta t}+C \\cdot \\min \\left\\{t, \\operatorname{dim}_{\\mathrm{FE}}(\\mathcal{F}, G, \\omega)\\right\\}+t \\omega\\right)\n",
    "$$\n",
    "\n",
    "**証明**\n",
    "\n",
    "まず，任意の$t\\in [T]$で\n",
    "$$\n",
    "\\sum_{k=1}^t \\mathbb{1}\\left(\\left|G\\left(f_k, g_k\\right)\\right|>\\epsilon\\right) \\leq\\left(\\beta / \\epsilon^2+1\\right) \\operatorname{dim}_{F E}(\\mathcal{F}, G, \\epsilon)\n",
    "$$\n",
    "が成立することを示します．\n",
    "\n",
    "$m:=\\sum_{k=1}^t \\mathbb{1}\\left(\\left|G\\left(f_k, g_k\\right)\\right|>\\epsilon\\right)$とします．すると，\n",
    "$G\\left(f_{s_1}, g_{s_1}\\right), \\ldots, G\\left(f_{s_m}, g_{s_m}\\right)>\\epsilon$であるような系列$\\left\\{s_1, \\ldots, s_m\\right\\}$が存在します．\n",
    "\n",
    "$L=\\left\\lceil(m-1) / \\operatorname{dim}_{F E}(\\mathcal{F}, G, \\epsilon)\\right\\rceil$とします．\n",
    "さて，$\\left\\{f_{s_1}, \\ldots, f_{s_m}\\right\\} \\subseteq \\mathcal{F}$について，$\\left\\{f_{s_1}, \\ldots, f_{s_{j-1}}\\right\\}$から少なくとも$L$個，$f_{s_j}$について$\\epsilon$-独立な系列を取り出すことができます．\n",
    "これを証明しましょう．\n",
    "\n",
    "まず，$$\n",
    "B_1=\\left\\{f_{s_1}\\right\\}, \\ldots, B_L=\\left\\{f_{s_L}\\right\\} \\text { and } j=L+1\n",
    "$$\n",
    "なる１つの要素からなる系列を考えます．$f_{s_j}$が$B_1, \\dots, B_L$について$\\epsilon$独立ならば，目標達成です．\n",
    "\n",
    "そうでない場合，$f_{s_j}$が$\\epsilon$-依存な$B_i$が存在します．この$B_i$を$B_i=B_i \\cup\\left\\{f_{s_j}\\right\\}$と更新します．\n",
    "そして$j=L+1$と更新し，この工程を続けます．\n",
    "\n",
    "\n",
    "すると，FE次元の定義から，$B_1, \\dots, B_L$のそれぞれの要素数は$\\operatorname{dim}_{F E}(\\mathcal{F}, G, \\epsilon)$よりも大きくなれません．\n",
    "故に，鳩の巣原理から，この工程は\n",
    "$j=L \\operatorname{dim}_{F E}(\\mathcal{F}, G, \\epsilon)+1 \\leq m$で停止します．\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "---\n",
    "\n",
    "### ステップ５\n",
    "\n",
    "後は全部合体させたら完成です．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}