notebooks/RL_robust_policy_gradient.ipynb

{
    "cells": [
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "# 一般のロバスト方策勾配の収束について\n",
                "\n",
                "**補足：最初single worst caseじゃないと無理かと思ったけどちょっと頑張ったらできた．論文の証明は色々間違ってると思う．**\n",
                "\n",
                "参考：\n",
                "* [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://arxiv.org/abs/2212.10439)\n",
                "\n",
                "[RL_robust_sa_gradient.ipynb](RL_robust_sa_gradient.ipynb)でやったロバストMDPに対する方策勾配法はSA-rectangularでしか成立しません．\n",
                "今回は一般のCompactなUncertainty setに対して成り立つ収束について見ていきます．\n",
                "表記は論文に任せます．\n",
                "\n",
                "ロバストMDPでは次の最適化問題を解くことを考えます：\n",
                "\n",
                "$$\n",
                "\\min _{\\boldsymbol{\\pi} \\in \\Pi} \\max _{\\boldsymbol{p} \\in \\mathcal{P}} J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p}):=\\boldsymbol{\\rho}^{\\top} \\boldsymbol{v}^{\\boldsymbol{\\pi}, \\boldsymbol{p}}=\\sum_{s \\in \\mathcal{S}} \\rho_s v_s^{\\boldsymbol{\\pi}, \\boldsymbol{p}}\n",
                "$$\n",
                "\n",
                "また，Occupancy measureを\n",
                "$$d_{\\boldsymbol{\\rho}}^{\\boldsymbol{\\pi}, \\boldsymbol{p}}\\left(s^{\\prime}\\right)=(1-\\gamma) \\sum_{s \\in \\mathcal{S}} \\sum_{t=0}^{\\infty} \\gamma^t \\rho(s) p_{s s^{\\prime}}^{\\boldsymbol{\\pi}}(t)$$\n",
                "で定義します．\n",
                "また，簡単のために次の表記も導入しておきます．\n",
                "\n",
                "$$\n",
                "\\min _{\\boldsymbol{\\pi} \\in \\Pi}\\left\\{\\Phi(\\boldsymbol{\\pi}):=\\max _{\\boldsymbol{p} \\in \\mathcal{P}} J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})\\right\\} .\n",
                "$$\n",
                "\n",
                "あとはこの$\\Phi(\\pi)$について勾配降下法をすればいい気がしますが，ことはそう単純ではありません．\n",
                "まず，$\\Phi$は一般には微分可能ではなく，さらに凸でも凹でもないので，一般には劣微分も存在しない場合があります（論文では[Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances](https://arxiv.org/abs/2006.08141)あたりを根拠にしていますが，[RL_robust_sa_gradient.ipynb](RL_robust_sa_gradient.ipynb)でみたようにフレシェ劣微分の意味で至るところ微分可能な気がする）．"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "\n",
                "---\n",
                "\n",
                "**補題：Danskinの定理**\n",
                "\n",
                "準備：\n",
                "* $\\mathcal{Z} \\subseteq \\mathbb{R}^m$をコンパクトな集合とします．\n",
                "* $\\phi: \\mathbb{R}^n \\times \\mathcal{Z} \\to \\mathbb{R}$を連続な関数とします．\n",
                "* $\\phi(\\cdot, z): \\mathbb{R}^n \\to \\mathbb{R}$はそれぞれの$z \\in \\mathcal{Z}$ で凸とします．\n",
                "  \n",
                "もし$\\phi(\\cdot, z)$が全ての$z \\in \\mathcal{Z}$で微分可能かつ$\\nabla\\phi(x, \\cdot)$がそれぞれの$x$について$\\mathcal{Z}$ で連続ならば，$f(\\boldsymbol{x}):=\\max _{z \\in \\mathcal{Z}} \\phi(\\boldsymbol{x}, z)$とすると，任意の$x \\in \\mathbb{R}^n$で\n",
                "\n",
                "$$\n",
                "\\partial f(\\boldsymbol{x})=\\operatorname{conv}\\left\\{\\nabla_x \\phi(\\boldsymbol{x}, z) \\mid z \\in \\underset{z \\in \\mathcal{Z}}{\\arg \\max } \\phi(\\boldsymbol{x}, z)\\right\\}\n",
                "$$\n",
                "\n",
                "つまり，各$x$における勾配は，各$\\argmax_z$での勾配の重み付き和で書けます．"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "## ロバスト方策勾配\n",
                "\n",
                "最悪ケースの遷移$p_t$は\n",
                "$$\n",
                "J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right) = \\max _{\\boldsymbol{p} \\in \\mathcal{P}} J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}\\right)\n",
                "$$\n",
                "を満たすとします（論文中では誤差がある場合を考えてますが，今回は面倒なので考えません）．\n",
                "\n",
                "これについて，次の方策更新を考えます．\n",
                "\n",
                "$$\n",
                "\\begin{aligned}\n",
                "\\boldsymbol{\\pi}_{t+1} & \\in \\arg \\min _{\\boldsymbol{\\pi} \\in \\Pi}\\left\\langle\\nabla_{\\boldsymbol{\\pi}} J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right), \\boldsymbol{\\pi}-\\boldsymbol{\\pi}_t\\right\\rangle+\\frac{1}{2 \\alpha_t}\\left\\|\\boldsymbol{\\pi}-\\boldsymbol{\\pi}_t\\right\\|^2 \\\\\n",
                "& =\\operatorname{Proj}_{\\Pi}\\left(\\boldsymbol{\\pi}_t-\\alpha_t \\nabla_{\\boldsymbol{\\pi}} J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right)\\right)\n",
                "\\end{aligned}\n",
                "$$\n",
                "\n",
                "これは各状態について考えると\n",
                "\n",
                "$$\n",
                "\\boldsymbol{\\pi}_{t+1, s}=\\operatorname{Proj}_{\\Delta A}\\left(\\boldsymbol{\\pi}_{t, s}-\\alpha_t \\nabla_{\\boldsymbol{\\pi}_s} J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right)\\right), \\quad \\forall s \\in \\mathcal{S}\n",
                "$$\n",
                "\n",
                "として書けます．\n",
                "$p_t$が固定されたときの勾配は通常のMDPの勾配と同じなので，\n",
                "\n",
                "$$\n",
                "\\frac{\\partial J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})}{\\partial \\pi_{s a}}=\\frac{1}{1-\\gamma} \\cdot d_{\\boldsymbol{\\rho}}^{\\boldsymbol{\\pi}, \\boldsymbol{p}}(s) \\cdot q_{s a}^{\\boldsymbol{\\pi}, \\boldsymbol{p}} .\n",
                "$$\n",
                "\n",
                "で与えられます．\n",
                "\n",
                "### 1. $J$と$\\Phi$のリプシッツ性，Smoothness，Convexityの証明\n",
                "\n",
                "$J_\\rho(\\boldsymbol{\\pi}, \\boldsymbol{p})$は$L_\\pi$-リプシッツであり，$\\ell_\\pi$-smoothです．ここで\n",
                "\n",
                "$$\n",
                "L_{\\boldsymbol{\\pi}}:=\\frac{\\sqrt{A}}{(1-\\gamma)^2}, \\quad \\ell_{\\boldsymbol{\\pi}}:=\\frac{2 \\gamma A}{(1-\\gamma)^3}\n",
                "$$\n",
                "\n",
                "としました．また，$\\Phi(\\pi)$は$L_\\pi$-リプシッツであり，$\\ell_\\pi$-weakly-convexです．\n",
                "\n",
                "**証明**　\n",
                "\n",
                "$\\ell_\\pi$-smoothの証明は簡単なので飛ばします．\n",
                "$L_\\pi$-リプシッツの証明をしましょう．\n",
                "\n",
                "$$\n",
                "\\begin{aligned}\n",
                "\\left\\|\\nabla_{\\boldsymbol{\\pi}} J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})\\right\\| & =\\sqrt{\\sum_{s, a}\\left(\\frac{\\partial J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})}{\\partial \\pi_{s a}}\\right)^2} \\\\\n",
                "& =\\frac{1}{1-\\gamma} \\sqrt{\\sum_a \\sum_s\\left(d_{\\boldsymbol{\\rho}}^{\\boldsymbol{\\pi}, \\boldsymbol{p}}(s) q_{s a}^{\\boldsymbol{\\pi}, \\boldsymbol{p}}\\right)^2} \\\\\n",
                "& \\leq \\frac{1}{(1-\\gamma)^2} \\sqrt{\\sum_a \\sum_s\\left(d_{\\boldsymbol{\\rho}}^{\\boldsymbol{\\pi}, \\boldsymbol{\\xi}}(s)\\right)^2} \\leq \\frac{\\sqrt{A}}{(1-\\gamma)^2},\n",
                "\\end{aligned}\n",
                "$$\n",
                "が成立します．これが$L_\\pi$リプシッツの証明そのものです．\n",
                "\n",
                "続いて$\\Phi$の証明をしましょう．\n",
                "$$\n",
                "\\begin{aligned}\n",
                "\\Phi\\left(\\boldsymbol{\\pi}_1\\right)-\\Phi\\left(\\boldsymbol{\\pi}_2\\right) & =\\max _{\\boldsymbol{p} \\in \\mathcal{P}} J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_1, \\boldsymbol{p}\\right)-\\max _{\\boldsymbol{p} \\in \\mathcal{P}} J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_2, \\boldsymbol{p}\\right) \\\\\n",
                "& =J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_1, \\boldsymbol{p}_1\\right)-J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_2, \\boldsymbol{p}_2\\right) \\\\\n",
                "& \\leq J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_1, \\boldsymbol{p}_1\\right)-J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_2, \\boldsymbol{p}_1\\right) \\\\\n",
                "& \\leq L_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_1-\\boldsymbol{\\pi}_2\\right\\| .\n",
                "\\end{aligned}\n",
                "$$\n",
                "なので，$\\Phi$は$L_\\pi$リプシッツです．\n",
                "\n",
                "$\\ell_\\pi$-weakly convexの証明は[Efficient Algorithms for Smooth Minimax Optimization](https://arxiv.org/abs/1907.01543)のLemma 3に載っています．\n",
                "\n",
                "<!-- ---\n",
                "\n",
                "### 2. $J$についてのGradient dominanceの証明\n",
                "\n",
                "[RL_PolicyGrad_convergence_rate.ipynb](RL_PolicyGrad_convergence_rate.ipynb)でやったように，次のGradient dominanceが成立します：\n",
                "\n",
                "$$\n",
                "J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})-J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}^{\\star}, \\boldsymbol{p}\\right) \\leq \\frac{D}{1-\\gamma} \\max _{\\overline{\\boldsymbol{\\pi}} \\in \\Pi}(\\boldsymbol{\\pi}-\\overline{\\boldsymbol{\\pi}})^{\\top} \\nabla_{\\boldsymbol{\\pi}} J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})\n",
                "$$ -->\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### 2. $J$についてのGradient dominanceの証明\n",
                "\n",
                "[RL_PolicyGrad_convergence_rate.ipynb](RL_PolicyGrad_convergence_rate.ipynb)でやったように，次のGradient dominanceが成立します：\n",
                "\n",
                "$$\n",
                "J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})-J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}^{\\star}, \\boldsymbol{p}\\right) \\leq \\frac{D}{1-\\gamma} \\max _{\\overline{\\boldsymbol{\\pi}} \\in \\Pi}(\\boldsymbol{\\pi}-\\overline{\\boldsymbol{\\pi}})^{\\top} \\nabla_{\\boldsymbol{\\pi}} J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})\n",
                "$$"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### 3. $\\Phi$のGradient dominance\n",
                "\n",
                "$\\Phi_\\lambda(\\pi)$は$\\Phi(\\pi)$のモーロー包とし，$D:=\\sup _{\\boldsymbol{\\pi} \\in \\Pi, \\boldsymbol{p} \\in \\mathcal{P}}\\left\\|\\boldsymbol{d}_{\\boldsymbol{\\rho}}^{\\boldsymbol{\\pi}, \\boldsymbol{p}} / \\boldsymbol{\\rho}\\right\\|_{\\infty}<\\infty$とします．\n",
                "\n",
                "さて，上でやったように，$J_\\rho(\\pi, p)$は$\\pi$について$\\ell_\\pi$-weakly convexです．\n",
                "よって，\n",
                "\n",
                "$$\n",
                "\\tilde{J}_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p}):=J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})+\\frac{\\ell_{\\boldsymbol{\\pi}}}{2}\\|\\boldsymbol{\\pi}\\|^2\n",
                "$$\n",
                "\n",
                "が$\\pi$について凸であり，$\\nabla_{\\boldsymbol{\\pi}} \\tilde{J}_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})=\\nabla_{\\boldsymbol{\\pi}} J_\\rho(\\boldsymbol{\\pi}, \\boldsymbol{p})+\\ell_{\\boldsymbol{\\pi}} \\boldsymbol{\\pi}$です．\n",
                "$\\tilde{\\Phi}(\\pi):=\\max _{\\boldsymbol{p} \\in \\mathcal{P}} \\tilde{J}_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})$\n",
                "とします．\n",
                "\n",
                "また，最悪ケースの$P$の集合を次で定めます：\n",
                "$$\n",
                "\\mathcal{G}(\\pi) := \n",
                "\\underset{\\boldsymbol{p} \\in \\mathcal{P}}{\\arg \\max } J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})\n",
                "=\\underset{\\boldsymbol{p} \\in \\mathcal{P}}{\\arg \\max } \\tilde{J}_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})\n",
                "$$\n",
                "\n",
                "$\\tilde{J}$の凸性と$\\partial \\tilde{\\Phi}(\\pi)=\\partial \\Phi(\\pi) + \\ell_\\pi \\pi$ を使えば，Danskinの定理から\n",
                "\n",
                "$$\n",
                "\\begin{aligned}\n",
                "\\partial \\tilde{\\Phi}(\\boldsymbol{\\pi}) & =\\operatorname{conv}\\left\\{\\nabla_\\pi \\tilde{J}_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p}) \\mid \\boldsymbol{p} \\in \\mathcal{G}\\right\\} \\\\\n",
                "\\Longrightarrow \\partial \\Phi(\\boldsymbol{\\pi})+\\ell_\\pi \\pi & =\\operatorname{conv}\\left\\{\\nabla_\\pi J_\\rho(\\pi, \\boldsymbol{p})+\\ell_\\pi \\pi \\mid \\boldsymbol{p} \\in \\mathcal{G}\\right\\} \\\\\n",
                "\\Longrightarrow \\partial \\Phi(\\boldsymbol{\\pi}) & =\\operatorname{conv}\\left\\{\\nabla_\\pi J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p}) \\mid \\boldsymbol{p} \\in \\mathcal{G}\\right\\} .\n",
                "\\end{aligned}\n",
                "$$\n",
                "が成り立ちます．３行目では$\\ell_\\pi \\pi$が$p$に依存しないので消しています．\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "$\\tilde{\\boldsymbol{\\pi}}=\\arg \\min _{\\hat{\\boldsymbol{\\pi}} \\in \\Pi} \\Phi(\\hat{\\boldsymbol{\\pi}})+\\ell_{\\boldsymbol{\\pi}}\\|\\boldsymbol{\\pi}-\\hat{\\boldsymbol{\\pi}}\\|^2$としましょう（これはMoreau Yoshida Regularizationみたいなやつです多分）．\n",
                "\n",
                "ここで，$J$についてのGradient dominanceを使えば，任意の$\\tilde{p} \\in \\mathcal{G}(\\tilde{\\pi})$について，\n",
                "$$\n",
                "\\begin{aligned}\n",
                "\\Phi(\\tilde{\\boldsymbol{\\pi}})-\\Phi\\left(\\boldsymbol{\\pi}^{\\star}\\right) \n",
                "& \\leq J(\\tilde{\\boldsymbol{\\pi}}, \\tilde{p})-J(\\pi^\\star, \\tilde{p}) \\\\\n",
                "&\\leq \n",
                "\\frac{D}{1-\\gamma}\n",
                "\\min_{\\tilde{p} \\in \\mathcal{G}}\n",
                "\\max _{\\boldsymbol{\\pi}' \\in \\Pi}\\left\\langle\\tilde{\\boldsymbol{\\pi}} - \\boldsymbol{\\pi}',\\nabla_{\\boldsymbol{\\pi}} J\\left(\\tilde{\\boldsymbol{\\pi}}, \\tilde{\\boldsymbol{p}}\\right)\\right\\rangle\\\\\n",
                "\\end{aligned}\n",
                "$$\n",
                "が成立します．\n",
                "ここでさらに[CVX_weakly_convex_and_Moreau_envelope.ipynb](CVX_weakly_convex_and_Moreau_envelope.ipynb)\n",
                "の補題を使うと，任意の$\\pi' \\in \\Pi$について，\n",
                "$$\n",
                "\\begin{aligned}\n",
                "\\left\\langle\\tilde{\\boldsymbol{\\pi}} - \\boldsymbol{\\pi}',\\tilde{\\boldsymbol{\\xi}}\\right\\rangle\n",
                "\\leq \n",
                "\\langle\\nabla \\Phi_{\\frac{1}{2\\ell_\\pi}(\\pi)}, \\tilde{\\pi} - \\pi' \\rangle \n",
                "\\leq \n",
                "\\left\\|\\nabla \\Phi_{\\frac{1}{2\\ell_\\pi}(\\pi)}\\right\\|_2 \\left\\|\\hat{\\pi} - \\pi'\\right\\|_2\n",
                "\\leq  2\\sqrt{S} \n",
                "\\left\\|\\nabla \\Phi_{\\frac{1}{2\\ell_\\pi}(\\pi)}\\right\\|_2 \n",
                "\\end{aligned}\n",
                "$$\n",
                "が成立するような劣微分 $\\xi \\in \\partial \\Phi(\\tilde{\\pi}) = \\operatorname{conv}\\left\\{\\nabla_\\pi J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p}) \\mid \\boldsymbol{p} \\in \\mathcal{G}\\right\\}$が存在します．\n",
                "２つ目の不等式はコーシー・シュワルツです．\n",
                "３つ目の不等式は，[分布の差についてのL1ノルムの不等式](https://math.stackexchange.com/questions/3835146/l1-norm-of-difference-between-two-probability-distributions-over-a-finite-set)を使ってます：\n",
                "\n",
                "$$\n",
                "\\begin{aligned}\n",
                "\\left\\|\\hat{\\pi} - \\pi'\\right\\|_2&=\n",
                "\\sqrt{\n",
                "\\sum_{s} \\sum_{a} \\left(\\hat{\\pi}(a \\mid s) - \\pi'(a \\mid s)\\right)^2\n",
                "}\\\\\n",
                "&\\leq \n",
                "\\sqrt{S} \n",
                "\\max_{s}\\sqrt{\n",
                "\\sum_{a} \\left(\\hat{\\pi}(a \\mid s) - \\pi'(a \\mid s)\\right)^2\n",
                "}\\\\\n",
                "&\\leq \n",
                "\\sqrt{S} \n",
                "\\max_{s}\n",
                "\\sum_{a} \\left|\\hat{\\pi}(a \\mid s) - \\pi'(a \\mid s)\\right|\n",
                "\\leq 2\\sqrt{S}\n",
                "\\end{aligned}\n",
                "$$\n",
                "\n",
                "ここで，$p$での勾配の集合を$\\mathcal{X} := \\left\\{\\nabla_{\\boldsymbol{\\pi}} J\\left(\\tilde{\\boldsymbol{\\pi}}, p\\right) \\mid p \\in \\mathcal{G}\\right\\}$と置くと，\n",
                "sionのminmax定理から\n",
                "$$\n",
                "\\min_{x \\in \\operatorname{conv}\\{\\mathcal{X}\\}} \\max _{\\boldsymbol{\\pi}' \\in \\Pi}\\left\\langle\\tilde{\\boldsymbol{\\pi}} - \\boldsymbol{\\pi}',x \\right\\rangle\n",
                "= \\max _{\\boldsymbol{\\pi}' \\in \\Pi}\\min_{x \\in \\operatorname{conv}\\{\\mathcal{X}\\}} \\left\\langle\\tilde{\\boldsymbol{\\pi}} - \\boldsymbol{\\pi}',x \\right\\rangle\n",
                "$$\n",
                "が成り立ちます．ここで，$\\min_{x \\in \\operatorname{conv}\\{\\mathcal{X}\\}} \\left\\langle\\tilde{\\boldsymbol{\\pi}} - \\boldsymbol{\\pi}',x \\right\\rangle$はConvex hull上の線形最適化問題なので，そのMinimizer $x^\\star$は極点に位置します（TODO: 少なくとも$\\mathcal{G}$が有限のときは成り立つはず．無限のときは要検証．）．\n",
                "つまり，$x^\\star \\in \\mathcal{X}$である$x^\\star$が存在します．\n",
                "さらにMinmax定理と合わせると，任意の$y \\in \\operatorname{conv}\\{\\mathcal{X}\\}$について，\n",
                "$$\n",
                "\\min_{x \\in \\mathcal{X}}\n",
                "\\max _{\\boldsymbol{\\pi}' \\in \\Pi}\\left\\langle\\tilde{\\boldsymbol{\\pi}} - \\boldsymbol{\\pi}',x\\right\\rangle\n",
                "= \\max _{\\boldsymbol{\\pi}' \\in \\Pi}\\left\\langle\\tilde{\\boldsymbol{\\pi}} - \\boldsymbol{\\pi}',x^\\star \\right\\rangle\n",
                "= \\min_{x \\in \\operatorname{conv}\\{\\mathcal{X}\\}} \\max _{\\boldsymbol{\\pi}' \\in \\Pi}\\left\\langle\\tilde{\\boldsymbol{\\pi}} - \\boldsymbol{\\pi}',x \\right\\rangle\n",
                "\\leq \\max _{\\boldsymbol{\\pi}' \\in \\Pi}\\left\\langle\\tilde{\\boldsymbol{\\pi}} - \\boldsymbol{\\pi}',y \\right\\rangle\n",
                "$$\n",
                "が成立します．よって，\n",
                "$$\n",
                "\\begin{aligned}\n",
                "\\Phi(\\tilde{\\boldsymbol{\\pi}})-\\Phi\\left(\\boldsymbol{\\pi}^{\\star}\\right) \n",
                "&\\leq \n",
                "\\frac{D}{1-\\gamma}\n",
                "\\min_{\\tilde{p} \\in \\mathcal{G}}\n",
                "\\max _{\\boldsymbol{\\pi}' \\in \\Pi}\\left\\langle\\tilde{\\boldsymbol{\\pi}} - \\boldsymbol{\\pi}',\\nabla_{\\boldsymbol{\\pi}} J\\left(\\tilde{\\boldsymbol{\\pi}}, \\tilde{\\boldsymbol{p}}\\right)\\right\\rangle\\\\\n",
                "&=\n",
                "\\frac{D}{1-\\gamma}\n",
                "\\min_{x \\in \\mathcal{X}}\n",
                "\\max _{\\boldsymbol{\\pi}' \\in \\Pi}\\left\\langle\\tilde{\\boldsymbol{\\pi}} - \\boldsymbol{\\pi}',x \\right\\rangle\\\\\n",
                "&\\leq\n",
                "\\frac{D}{1-\\gamma}\n",
                "\\max _{\\boldsymbol{\\pi}' \\in \\Pi}\\left\\langle\\tilde{\\boldsymbol{\\pi}} - \\boldsymbol{\\pi}',\\tilde{\\xi} \\right\\rangle\n",
                "\\leq \n",
                "\\frac{2\\sqrt{S}D}{1-\\gamma}\n",
                "\\left\\|\\nabla \\Phi_{\\frac{1}{2\\ell_\\pi}(\\pi)}\\right\\|_2 \n",
                "\\end{aligned}\n",
                "$$\n",
                "です．\n",
                "\n",
                "あとはLipschitz性と合わせれば\n",
                "\n",
                "$$\n",
                "\\begin{aligned}\n",
                "\\Phi(\\boldsymbol{\\pi})-\\Phi\\left(\\boldsymbol{\\pi}^{\\star}\\right) & =\\Phi(\\boldsymbol{\\pi})-\\Phi(\\tilde{\\boldsymbol{\\pi}})+\\Phi(\\tilde{\\boldsymbol{\\pi}})-\\Phi\\left(\\boldsymbol{\\pi}^{\\star}\\right) \\\\\n",
                "& \\leq \\frac{2 D \\sqrt{S}}{1-\\gamma}\\left\\|\\nabla \\Phi_{\\frac{1}{2 \\ell_\\pi}}(\\boldsymbol{\\pi})\\right\\|+\\Phi(\\boldsymbol{\\pi})-\\Phi(\\tilde{\\boldsymbol{\\pi}}) \\\\\n",
                "& \\leq \\frac{2 D \\sqrt{S}}{1-\\gamma}\\left\\|\\nabla \\Phi_{\\frac{1}{2 \\ell}}(\\boldsymbol{\\pi})\\right\\|+L_{\\boldsymbol{\\pi}}\\|\\boldsymbol{\\pi}-\\tilde{\\boldsymbol{\\pi}}\\| \\\\\n",
                "& =\\frac{2 D \\sqrt{S}}{1-\\gamma}\\left\\|\\nabla \\Phi_{\\frac{1}{2 \\ell \\pi}}(\\boldsymbol{\\pi})\\right\\|+L_{\\boldsymbol{\\pi}} \\cdot \\frac{\\left\\|\\nabla \\Phi_{\\frac{1}{2 \\ell \\pi}}(\\boldsymbol{\\pi})\\right\\|}{2 \\ell_{\\boldsymbol{\\pi}}}\\\\\n",
                "& =\\left(\\frac{2 D \\sqrt{S}}{1-\\gamma} + \\frac{L_\\pi}{2\\ell_\\pi}\\right)\\left\\|\\nabla \\Phi_{\\frac{1}{2 \\ell \\pi}}(\\boldsymbol{\\pi})\\right\\|\n",
                "\\end{aligned}\n",
                "$$\n",
                "が成り立ちます．"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### 4. $\\varepsilon$-stationary pointに収束することの証明\n",
                "\n",
                "$\\tilde{\\boldsymbol{\\pi}}_t=\\arg \\min _{\\tilde{\\boldsymbol{\\pi}} \\in \\Pi} \\Phi(\\tilde{\\boldsymbol{\\pi}})+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_t-\\tilde{\\boldsymbol{\\pi}}\\right\\|^2$としましょう．\n",
                "また，$\\pi_t$についての最悪ケースを$p_t$とし，\n",
                "$$\n",
                "\\begin{aligned}\n",
                "\\boldsymbol{\\pi}_{t+1} & \\in \\arg \\min _{\\boldsymbol{\\pi} \\in \\Pi}\\left\\langle\\nabla_{\\boldsymbol{\\pi}} J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right), \\boldsymbol{\\pi}-\\boldsymbol{\\pi}_t\\right\\rangle+\\frac{1}{2 \\alpha_t}\\left\\|\\boldsymbol{\\pi}-\\boldsymbol{\\pi}_t\\right\\|^2 \\\\\n",
                "& =\\operatorname{Proj}_{\\Pi}\\left(\\boldsymbol{\\pi}_t-\\alpha_t \\nabla_{\\boldsymbol{\\pi}} J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right)\\right)\n",
                "\\end{aligned}\n",
                "$$\n",
                "であることを思い出しましょう．\n",
                "\n",
                "\n",
                "このとき，\n",
                "\n",
                "$$\n",
                "\\begin{aligned}\n",
                "\\Phi_{\\frac{1}{2 \\ell_\\pi}}\\left(\\boldsymbol{\\pi}_{t+1}\\right) & =\\min _{\\boldsymbol{\\pi}} \\Phi(\\boldsymbol{\\pi})+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_{t+1}-\\boldsymbol{\\pi}\\right\\|^2 \\\\\n",
                "& \\leq \\Phi\\left(\\tilde{\\boldsymbol{\\pi}}_t\\right)+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_{t+1}-\\tilde{\\boldsymbol{\\pi}}_t\\right\\|^2 \\\\\n",
                "& =\\Phi\\left(\\tilde{\\boldsymbol{\\pi}}_t\\right)+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\mathcal{P}_{\\Pi}\\left(\\boldsymbol{\\pi}_t-\\alpha \\nabla_{\\boldsymbol{\\pi}} J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right)\\right)-\\mathcal{P}_{\\Pi}\\left(\\tilde{\\boldsymbol{\\pi}}_t\\right)\\right\\|^2 \\\\\n",
                "& \\leq \\Phi\\left(\\tilde{\\boldsymbol{\\pi}}_t\\right)+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_t-\\alpha \\nabla_{\\boldsymbol{\\pi}} J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right)-\\tilde{\\boldsymbol{\\pi}}_t\\right\\|^2 \\text{ Projしたほうがノルムは小さくなる }\\\\\n",
                "& =\\underbrace{\\Phi\\left(\\tilde{\\boldsymbol{\\pi}}_t\\right)+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_t-\\tilde{\\boldsymbol{\\pi}}_t\\right\\|^2}_{\\Phi_{\\frac{1}{2\\ell_\\pi}}(\\pi_t)}-2 \\ell_{\\boldsymbol{\\pi}} \\alpha\\left(\\nabla_{\\boldsymbol{\\pi}} J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right), \\boldsymbol{\\pi}_t-\\tilde{\\boldsymbol{\\pi}}_t\\right\\rangle+\\alpha^2 \\ell_{\\boldsymbol{\\pi}} \\underbrace{\\left\\|\\nabla_{\\boldsymbol{\\pi}} J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right)\\right\\|^2}_{\\leq L_\\pi^2 \\;\\text{ due to Lipschitz}} \\\\\n",
                "& \\leq \\Phi_{\\frac{1}{2 \\ell_\\pi}}\\left(\\boldsymbol{\\pi}_t\\right)+2 \\ell_{\\boldsymbol{\\pi}} \\alpha\\left(\\Phi\\left(\\tilde{\\boldsymbol{\\pi}}_t\\right)-\\Phi\\left(\\boldsymbol{\\pi}_t\\right)+\\frac{\\ell_{\\boldsymbol{\\pi}}}{2}\\left\\|\\boldsymbol{\\pi}_t-\\tilde{\\boldsymbol{\\pi}}_t\\right\\|^2\\right)+\\alpha^2 \\ell_{\\boldsymbol{\\pi}} L_{\\boldsymbol{\\pi}}^2,\n",
                "\\end{aligned}\n",
                "$$\n",
                "\n",
                "ここで最後の不等式は次の不等式を利用してます（$\\Phi$が$\\ell_\\pi$-weakly convexityであることを使ってます．）\n",
                "\n",
                "$$\n",
                "\\begin{aligned}\n",
                "\\Phi\\left(\\tilde{\\boldsymbol{\\pi}}_t\\right) \\geq J_{\\boldsymbol{\\rho}}\\left(\\tilde{\\boldsymbol{\\pi}}_t, \\boldsymbol{p}_t\\right) & \\geq J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right)+\\left\\langle\\nabla_{\\boldsymbol{\\pi}} J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right), \\tilde{\\boldsymbol{\\pi}}_t-\\boldsymbol{\\pi}_t\\right\\rangle-\\frac{\\ell_{\\boldsymbol{\\pi}}}{2}\\left\\|\\boldsymbol{\\pi}_t-\\tilde{\\boldsymbol{\\pi}}_t\\right\\|^2 \n",
                "\\end{aligned}\n",
                "$$\n",
                "\n",
                "です．\n",
                "上でやった不等式を$t$について和を取ると\n",
                "\n",
                "$$\n",
                "\\Phi_{\\frac{1}{2 \\ell \\pi}}\\left(\\boldsymbol{\\pi}_{T-1}\\right) \\leq \\Phi_{\\frac{1}{2 \\ell \\pi}}\\left(\\boldsymbol{\\pi}_0\\right)+2 \\ell_{\\boldsymbol{\\pi}} \\alpha \\sum_{t=0}^{T-1}\\left(\\Phi\\left(\\tilde{\\boldsymbol{\\pi}}_t\\right)-\\Phi\\left(\\boldsymbol{\\pi}_t\\right)+\\frac{\\ell \\boldsymbol{\\pi}}{2}\\left\\|\\boldsymbol{\\pi}_t-\\tilde{\\boldsymbol{\\pi}}_t\\right\\|^2\\right)+T \\alpha^2 \\ell_{\\boldsymbol{\\pi}} L_{\\boldsymbol{\\pi}}^2\n",
                "$$\n",
                "\n",
                "です．変形して\n",
                "\n",
                "$$\n",
                "\\sum_{t=0}^{T-1}\\left(\\Phi\\left(\\boldsymbol{\\pi}_t\\right)-\\Phi\\left(\\tilde{\\boldsymbol{\\pi}}_t\\right)-\\frac{\\ell_{\\boldsymbol{\\pi}}}{2}\\left\\|\\boldsymbol{\\pi}_t-\\tilde{\\boldsymbol{\\pi}}_t\\right\\|^2\\right) \\leq \\frac{\\Phi_{\\frac{1}{2 \\ell \\pi}}\\left(\\boldsymbol{\\pi}_0\\right)-\\Phi_{\\frac{1}{2 \\ell}}\\left(\\boldsymbol{\\pi}_{T-1}\\right)}{2 \\ell_{\\boldsymbol{\\pi}} \\alpha}+\\frac{T \\alpha L_\\pi^2}{2}.\n",
                "$$\n",
                "\n",
                "が得られます．また，凸関数の性質を使えば\n",
                "\n",
                "$$\n",
                "\\begin{aligned}\n",
                "&\\begin{aligned}\n",
                "& \\Phi\\left(\\boldsymbol{\\pi}_t\\right)-\\Phi\\left(\\tilde{\\boldsymbol{\\pi}}_t\\right)-\\frac{\\ell_{\\boldsymbol{\\pi}}}{2}\\left\\|\\boldsymbol{\\pi}_t-\\tilde{\\boldsymbol{\\pi}}_t\\right\\|^2 \\\\\n",
                "& =\\Phi\\left(\\boldsymbol{\\pi}_t\\right)+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_t-\\boldsymbol{\\pi}_t\\right\\|^2-\\Phi\\left(\\tilde{\\boldsymbol{\\pi}}_t\\right)-\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_t-\\tilde{\\boldsymbol{\\pi}}_t\\right\\|^2+\\frac{\\ell_{\\boldsymbol{\\pi}}}{2}\\left\\|\\boldsymbol{\\pi}_t-\\tilde{\\boldsymbol{\\pi}}_t\\right\\|^2 \\\\\n",
                "& =\\Phi\\left(\\boldsymbol{\\pi}_t\\right)+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_t-\\boldsymbol{\\pi}_t\\right\\|^2-\\min _{\\boldsymbol{\\pi} \\in \\Pi}\\left\\{\\Phi(\\boldsymbol{\\pi})+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_t-\\boldsymbol{\\pi}\\right\\|^2\\right\\}+\\frac{\\ell_{\\boldsymbol{\\pi}}}{2}\\left\\|\\boldsymbol{\\pi}_t-\\tilde{\\boldsymbol{\\pi}}_t\\right\\|^2\n",
                "\\end{aligned}\\\\\n",
                "&\\stackrel{(a)}{\\geq} \\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_t-\\tilde{\\boldsymbol{\\pi}}_t\\right\\|^2=\\frac{1}{4 \\ell_{\\boldsymbol{\\pi}}}\\left\\|\\nabla \\Phi_{\\frac{1}{2 \\ell \\pi}}\\left(\\boldsymbol{\\pi}_t\\right)\\right\\|^2 .\n",
                "\\end{aligned}\n",
                "$$\n",
                "が成立します．最後の式はモーロー包の勾配を使えば出てきます．\n",
                "\n",
                "$\\overline{\\boldsymbol{\\pi}}_1:=\\arg \\min _{\\overline{\\boldsymbol{\\pi}} \\in \\Pi} \\Phi(\\overline{\\boldsymbol{\\pi}})+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_1-\\overline{\\boldsymbol{\\pi}}\\right\\|^2$ and $\\overline{\\boldsymbol{\\pi}}_2:=\\arg \\min _{\\overline{\\boldsymbol{\\pi}} \\in \\Pi} \\Phi(\\overline{\\boldsymbol{\\pi}})+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_2-\\overline{\\boldsymbol{\\pi}}\\right\\|^2$\n",
                "とします．\n",
                "このとき，\n",
                "\n",
                "$$\n",
                "\\begin{aligned}\n",
                "\\Phi_{\\frac{1}{2 \\ell \\pi}}\\left(\\boldsymbol{\\pi}_1\\right)-\\Phi_{\\frac{1}{2 \\ell \\pi}}\\left(\\boldsymbol{\\pi}_2\\right) & =\\min _{\\overline{\\boldsymbol{\\pi}} \\in \\Pi}\\left(\\Phi(\\overline{\\boldsymbol{\\pi}})+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_1-\\overline{\\boldsymbol{\\pi}}\\right\\|^2\\right)-\\min _{\\overline{\\boldsymbol{\\pi}} \\in \\Pi}\\left(\\Phi(\\overline{\\boldsymbol{\\pi}})+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_2-\\overline{\\boldsymbol{\\pi}}\\right\\|^2\\right) \\\\\n",
                "& =\\Phi\\left(\\overline{\\boldsymbol{\\pi}}_1\\right)+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_1-\\overline{\\boldsymbol{\\pi}}_1\\right\\|^2-\\Phi\\left(\\overline{\\boldsymbol{\\pi}}_2\\right)-\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_2-\\overline{\\boldsymbol{\\pi}}_2\\right\\|^2 \\\\\n",
                "& \\leq \\Phi\\left(\\overline{\\boldsymbol{\\pi}}_2\\right)+\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_1-\\overline{\\boldsymbol{\\pi}}_2\\right\\|^2-\\Phi\\left(\\overline{\\boldsymbol{\\pi}}_2\\right)-\\ell_{\\boldsymbol{\\pi}}\\left\\|\\boldsymbol{\\pi}_2-\\overline{\\boldsymbol{\\pi}}_2\\right\\|^2 \\\\\n",
                "& =\\ell_{\\boldsymbol{\\pi}}\\left(\\left\\|\\boldsymbol{\\pi}_1-\\overline{\\boldsymbol{\\pi}}_2\\right\\|^2-\\left\\|\\boldsymbol{\\pi}_2-\\overline{\\boldsymbol{\\pi}}_2\\right\\|^2\\right) \\\\\n",
                "& \\leq 2 \\ell_{\\boldsymbol{\\pi}} S .\n",
                "\\end{aligned}\n",
                "$$\n",
                "\n",
                "です．全部合体させると\n",
                "\n",
                "$$\n",
                "\\sum_{t=0}^{T-1}\\left\\|\\nabla \\Phi_{\\frac{1}{2 \\ell \\pi}}\\left(\\boldsymbol{\\pi}_t\\right)\\right\\|^2 \\leq \\frac{4 \\ell_\\pi S}{\\alpha}+2 T \\alpha \\ell_\\pi L_\\pi^2\n",
                "$$\n",
                "\n",
                "が得られます．左辺が$T \\varepsilon^2$より小さい場合，つまり\n",
                "$$\n",
                "T \\cdot \\min _t\\left\\|\\nabla \\Phi_{\\frac{1}{2 \\ell \\pi}}\\left(\\boldsymbol{\\pi}_t\\right)\\right\\|^2 \\leq \\sum_{t=0}^{T-1}\\left\\|\\nabla \\Phi_{\\frac{1}{2 \\ell \\pi}}\\left(\\boldsymbol{\\pi}_t\\right)\\right\\|^2 \\leq T \\epsilon^2,\n",
                "$$\n",
                "のとき，$\\pi_{\\hat{t}}$が$\\varepsilon$-停留点になるような$\\hat{t}$が存在します．\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": [
                "### 5. 停留点が$\\varepsilon$-最適である証明\n",
                "\n",
                "ここでは\n",
                "$$\n",
                "J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}^{\\star}, \\boldsymbol{p}^{\\star}\\right)-\\max _{\\boldsymbol{p} \\in \\mathcal{P}} J_{\\boldsymbol{\\rho}}\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}\\right)=\\Phi\\left(\\boldsymbol{\\pi}^{\\star}\\right)-\\Phi\\left(\\boldsymbol{\\pi}_t\\right) \\leq \\epsilon .\n",
                "$$\n",
                "であるような$t$が存在することを示します．\n",
                "\n",
                "上でやったGradient dominanceから，\n",
                "\n",
                "$$\n",
                "J\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right)-\\min _{\\boldsymbol{\\pi} \\in \\Pi} \\max _{\\boldsymbol{p} \\in \\mathcal{P}} J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p}) \\leq \\Phi\\left(\\boldsymbol{\\pi}_t\\right)-\\Phi\\left(\\boldsymbol{\\pi}^{\\star}\\right) \\leq \n",
                "\\left(\\frac{2 D \\sqrt{S}}{1-\\gamma} + \\frac{L_\\pi}{2\\ell_\\pi}\\right)\\left\\|\\nabla \\Phi_{\\frac{1}{2 \\ell \\pi}}(\\boldsymbol{\\pi}_t)\\right\\|\n",
                "$$\n",
                "\n",
                "であり，変形すれば\n",
                "\n",
                "$$\n",
                "\\begin{aligned}\n",
                "\\min _{t \\in\\{0, \\cdots, T-1\\}}\\left\\{J\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right)-\\min _{\\boldsymbol{\\pi} \\in \\Pi} \\max _{\\boldsymbol{p} \\in \\mathcal{P}} J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})\\right\\} & \\leq \\frac{1}{T} \\sum_{t=0}^{T-1}\\left(J\\left(\\boldsymbol{\\pi}_t, \\boldsymbol{p}_t\\right)-\\min _{\\boldsymbol{\\pi} \\in \\Pi} \\max _{\\boldsymbol{p} \\in \\mathcal{P}} J_{\\boldsymbol{\\rho}}(\\boldsymbol{\\pi}, \\boldsymbol{p})\\right) \\\\\n",
                "& \\leq \\frac{1}{T} \\sum_{t=0}^{T-1}\\left(\\Phi\\left(\\boldsymbol{\\pi}_t\\right)-\\Phi\\left(\\boldsymbol{\\pi}^{\\star}\\right)\\right) \\\\\n",
                "& \\leq \\frac{1}{T}\\left(\\frac{2D \\sqrt{S}}{1-\\gamma}+\\frac{L_{\\boldsymbol{\\pi}}}{2 \\ell_{\\boldsymbol{\\pi}}}\\right) \\sum_{t=0}^{T-1}\\left\\|\\nabla \\Phi_{\\frac{1}{2 \\ell_{\\boldsymbol{\\pi}}}}\\left(\\boldsymbol{\\pi}_t\\right)\\right\\|\n",
                "\\end{aligned}\n",
                "$$\n",
                "\n",
                "です．コーシー・シュワルツの不等式から\n",
                "\n",
                "$$\n",
                "\\frac{1}{\\sqrt{T}} \\sum_{t=0}^{T-1}\\left\\|\\nabla \\Phi_{\\frac{1}{2 \\ell \\pi}}\\left(\\boldsymbol{\\pi}_t\\right)\\right\\| \\leq \\sqrt{\\sum_{t=0}^{T-1}\\left\\|\\nabla \\Phi_{\\frac{1}{2 \\ell} \\pi}\\left(\\boldsymbol{\\pi}_t\\right)\\right\\|^2} .\n",
                "$$\n",
                "\n",
                "です．さらにステップ４の不等式を使えば，\n",
                "\n",
                "$$\n",
                "\\begin{aligned}\n",
                "& \\leq \\frac{1}{\\sqrt{T}}\\left(\\frac{D \\sqrt{S}}{1-\\gamma}+\\frac{L_\\pi}{2 \\ell_\\pi}\\right) \\sqrt{\\sum_{t=0}^{T-1}\\left\\|\\nabla \\Phi_{\\frac{1}{2 \\ell_\\pi}}\\left(\\boldsymbol{\\pi}_t\\right)\\right\\|^2} \\\\\n",
                "& \\leq \\frac{1}{\\sqrt{T}}\\left(\\frac{D \\sqrt{S}}{1-\\gamma}+\\frac{L_\\pi}{2 \\ell_\\pi}\\right) \\sqrt{\\left(\\frac{4 \\ell_\\pi S}{\\alpha}+2 T \\alpha \\ell_\\pi L_\\pi^2\\right)} \\;.\n",
                "\\end{aligned}\n",
                "$$\n",
                "\n",
                "が成立します．あとはこれが$\\epsilon$になるように$\\alpha$と$T$を調整すれば終わりです．"
            ]
        }
    ],
    "metadata": {
        "kernelspec": {
            "display_name": ".venv",
            "language": "python",
            "name": "python3"
        },
        "language_info": {
            "codemirror_mode": {
                "name": "ipython",
                "version": 3
            },
            "file_extension": ".py",
            "mimetype": "text/x-python",
            "name": "python",
            "nbconvert_exporter": "python",
            "pygments_lexer": "ipython3",
            "version": "3.9.12"
        }
    },
    "nbformat": 4,
    "nbformat_minor": 2
}